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.3697822e-05
Overall Rank: 4,194 | 70.83%
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,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
3,474	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.0625972e-05
4,874	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	5.8594632e-05
5,075	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	5.7172118e-05
7,486	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	4.7180617e-05
7,581	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	4.7057641e-05
8,615	The Case for NLP-Enhanced Database Tuning: Towards Tuning Tools that "Read the Manual"	2021	VLDB	4.484683e-05
9,305	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	4.3577129e-05
10,283	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	4.1945683e-05
10,987	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	4.1945683e-05
10,994	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.1945683e-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,715	Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries	2020	VLDB	6.8220943e-05
6,543	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0208799e-05
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00041510555
1,619	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011111678
8,164	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD	4.5718104e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
4,738	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	5.9600502e-05
3,074	On the Complexity of the View-Selection Problem	1999	PODS	7.6110034e-05
8,851	Efficient Approximations of Conjunctive Queries	2012	PODS	4.4363908e-05