On the Complexity of Approximate Query Optimization

Summary: Proves strong inapproximability of join-order optimization: for any δ>0 finding a join order within factor 2^{Θ(log^{1-δ} K)} of optimal K is NP-hard. Hardness holds across a wide range of query-graph densities, so no polylog-competitive polytime optimizer unless P=NP. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1272
Venue: PODS
Year: 2002
Pagerank: 6.3681294e-05
Overall Rank: 4,189 | 70.89%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 11 of 11 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
3,476	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0560383e-05
4,876	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8544467e-05
5,073	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7118738e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7135369e-05
7,573	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7034681e-05
8,612	The Case for NLP-Enhanced Database Tuning: Towards Tuning Tools that "Read the Manual"	2021	VLDB	4.4807455e-05
9,312	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	4.353536e-05
10,295	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1905499e-05
10,990	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1905499e-05
10,997	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
3,702	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8251643e-05
6,541	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0160682e-05
3,505	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0304901e-05
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00041430126
1,621	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011105663
8,149	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5715614e-05
912	The Complexity of Evaluating Relational Queries	1983	PODS	0.00015374685
4,734	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9553181e-05
3,079	On the Complexity of the View-Selection Problem	1999	PODS	7.6036669e-05
8,850	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4324268e-05