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: 1271
Venue: PODS
Year: 2002
Pagerank: 7.3175599e-05
Overall Rank: 3,553 | 75.63%
DOI: 10.1145/543613.543650

Incoming Non-self Citations Over Time

Authors

1. S. Chatterji (University of California Berkeley)
2. S.S.K. Evani (Sun Microsystems)
3. S. Ganguly (AT&T)
4. M.D. Yemmanuru (Sun Microsystems)

BibTeX Citation

@inproceedings{chatterji_pods02,
        address = {New York, NY, USA},
        series = {{PODS} '02},
        title = {{On the Complexity of Approximate Query Optimization}},
        url = {https://dl.acm.org/doi/10.1145/543613.543650},
        doi = {10.1145/543613.543650},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chatterji, S. and Evani, S.S.K. and Ganguly, S. and Yemmanuru, M.D.},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD	0.00011320736
3,158	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6888079e-05
4,880	An Incremental Anytime Algorithm for Multi-Objective Query Optimization	2015	SIGMOD	6.4656221e-05
5,124	Approximation Schemes for Many-Objective Query Optimization	2014	SIGMOD	6.3567981e-05
7,388	Synopses for Query Optimization: A Space-Complexity Perspective	2004	PODS	5.6268292e-05
7,910	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.5181056e-05
8,127	The Case for NLP-Enhanced Database Tuning: Towards Tuning Tools that “Read the Manual”	2021	VLDB	5.4826853e-05
9,042	DPconv: Super-Polynomially Faster Join Ordering	2024	SIGMOD	5.3256042e-05
9,446	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB	5.2667452e-05
9,969	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.1845938e-05
10,151	Coresets for Robust Query Optimization	2026	PODS	5.093636e-05
11,205	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.093636e-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
1	6,164	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS
2	10,296	Succinct Structure Representations for Efficient Query Optimization	2026	SIGMOD
3	3,268	Efficient and Provable Multi-Query Optimization	2017	PODS
4	143	Optimization of Nonrecursive Queries	1986	VLDB
5	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
6	7,882	Efficiently Computing Join Orders with Heuristic Search	2023	SIGMOD
7	1,467	The Complexity of Evaluating Relational Queries	1983	PODS
8	3,813	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
9	3,188	On the Complexity of the View-Selection Problem	1999	PODS
10	9,009	Efficient Approximations of Conjunctive Queries	2012	PODS