An Overview of Query Optimization in Relational Systems

Summary: Survey of SQL query optimization in RDBMS: optimizer vs executor, physical operators and execution plans, and why plan selection is performance-critical. Frames optimization as a hard search problem and pinpoints three core tasks—search-space definition, cost estimation, and efficient enumeration. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h723b36784e63ad88
Venue: PODS
Year: 1998
Pagerank: 0.0002251422
Overall Rank: 272 | 98.18%
DOI: 10.1145/275487.275492

Incoming Non-self Citations Over Time

Authors

1. Surajit Chaudhuri (Microsoft)

BibTeX Citation

@inproceedings{chaudhuri_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{An Overview of Query Optimization in Relational Systems}},
        url = {https://dl.acm.org/doi/10.1145/275487.275492},
        doi = {10.1145/275487.275492},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Chaudhuri, Surajit},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 50 of 78 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
144	Neo: A Learned Query Optimizer	2019	VLDB	0.00029090793
289	Graphs-at-a-time: Query Language and Access Methods for Graph Databases	2008	SIGMOD	0.00021960834
644	Exploiting Statistics on Query Expressions for Optimization	2002	SIGMOD	0.00015209065
658	DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing	2025	VLDB	0.00015058738
790	Cosette: An Automated Prover for SQL	2017	CIDR	0.00013971102
1,178	Simba: Efficient In-Memory Spatial Analytics	2016	SIGMOD	0.00011627256
1,258	Sampling-Based Query Re-Optimization	2016	SIGMOD	0.00011308863
1,280	AI Meets AI: Leveraging Query Executions to Improve Index Recommendations	2019	SIGMOD	0.00011224914
1,496	SMCQL: Secure Querying for Federated Databases	2017	VLDB	0.00010479934
1,501	Keyword Search in Databases: The Power of RDBMS	2009	SIGMOD	0.00010456517
1,743	Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation	1999	VLDB	9.7342409e-05
1,813	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS	9.5759542e-05
2,000	Pregelix: Big(ger) Graph Analytics on A Dataflow Engine	2015	VLDB	9.2101691e-05
2,162	DIFF: A Relational Interface for Large-Scale Data Explanation	2019	VLDB	8.9344773e-05
2,278	Active Learning for ML Enhanced Database Systems	2020	SIGMOD	8.7057608e-05
2,401	Declarative Recursive Computation on an RDBMS or, Why You Should Use a Database For Distributed Machine Learning	2019	VLDB	8.517457e-05
2,890	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD	7.9010819e-05
3,128	How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates	2016	SIGMOD	7.611678e-05
3,480	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2661848e-05
3,508	Serving and Optimizing Machine Learning Workflows on Heterogeneous Infrastructures	2023	VLDB	7.2455881e-05
3,597	Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe?	2017	SIGMOD	7.1759026e-05
4,559	Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts	2022	SIGMOD	6.5324275e-05
4,565	QUEST: Query Optimization in Unstructured Document Analysis	2025	VLDB	6.5295131e-05
5,006	COMPASS: Online Sketch-based Query Optimization for In-Memory Databases	2021	SIGMOD	6.3159614e-05
5,020	Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server	2023	VLDB	6.3096708e-05
5,047	Lightweight Cardinality Estimation in LSM-based Systems	2018	SIGMOD	6.2972183e-05
5,236	FASTgres: Making Learned Query Optimizer Hinting Effective	2023	VLDB	6.2153504e-05
5,482	A Comparative Study and Component Analysis of Query Plan Representation Techniques in ML4DB Studies	2024	VLDB	6.1123461e-05
5,583	Efficient Computation of Multiple Group By Queries	2005	SIGMOD	6.0739524e-05
5,663	Enabling Incremental Query Re-Optimization	2016	SIGMOD	6.0448133e-05
6,044	Size and Treewidth Bounds for Conjunctive Queries	2009	PODS	5.903331e-05
6,243	Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics	2016	SIGMOD	5.8357659e-05
6,305	Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs	2020	SIGMOD	5.8161222e-05
6,575	Can Large Language Models Be Query Optimizer for Relational Databases?	2026	SIGMOD	5.7428777e-05
6,607	Multi-Objective Agentic Rewrites for Unstructured Data Processing	2026	VLDB	5.73539e-05
6,672	Query Optimization over Crowdsourced Data	2013	VLDB	5.7120461e-05
6,758	Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and Opportunities	2022	SIGMOD	5.6877154e-05
7,468	Membrane - Safe and Performant Data Access Controls in Apache Spark in the Presence of Imperative Code	2024	VLDB	5.51782e-05
7,572	Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries	2024	SIGMOD	5.492682e-05
7,638	MRTuner: A Toolkit to Enable Holistic Optimization for MapReduce Jobs	2014	VLDB	5.4767699e-05
7,929	SlabCity: Whole-Query Optimization using Program Synthesis	2023	VLDB	5.4231855e-05
7,958	Robust Query Processing: Mission Possible	2020	VLDB	5.4164639e-05
7,959	Distributed Outlier Detection using Compressive Sensing	2015	SIGMOD	5.4160954e-05
7,995	From a Stream of Relational Queries to Distributed Stream Processing	2010	VLDB	5.4090565e-05
8,006	Processing and Optimizing Main Memory Spatial-Keyword Queries	2016	VLDB	5.4066876e-05
8,170	Efficient Query Re-optimization with Judicious Subquery Selections	2023	SIGMOD	5.3827384e-05
8,296	User-Optimizer Communication using Abstract Plans in Sybase ASE	2001	VLDB	5.3589207e-05
8,348	MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates	2020	SIGMOD	5.3486679e-05
8,372	List Intersection for Web Search: Algorithms, Cost Models, and Optimizations	2019	VLDB	5.3434309e-05
8,542	New Query Optimization Techniques in the Spark Engine of Azure Synapse	2022	VLDB	5.3188219e-05

Outgoing Citations (Sorted by Pagerank)

Showing 38 of 38 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0023943337
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058997063
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047864281
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.0004772731
73	Including Group-By in Query Optimization	1994	VLDB	0.0003750677
77	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036817139
97	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034111286
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033884854
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00032757423
118	The EXODUS Optimizer Generator	1987	SIGMOD	0.00031381726
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.0003136296
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030462671
132	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.00030228229
155	Common Expression Analysis in Database Applications	1982	SIGMOD	0.0002851688
167	Query Transformation for PSJ-queries	1987	VLDB	0.00027190577
172	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.00026824625
196	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00025616489
202	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.0002523837
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024753576
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023354266
273	Extensible Query Processing in Starburst	1989	SIGMOD	0.00022498382
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021082176
397	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019151375
477	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017640718
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016938992
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016264813
686	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00014769852
725	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.00014471289
792	Parametric Query Optimization	1992	VLDB	0.00013938197
806	Universality of Serial Histograms	1993	VLDB	0.00013786471
1,015	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00012495751
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012396854
1,057	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD	0.00012226471
1,076	Towards an Open Architecture for LDL	1989	VLDB	0.00012154177
1,119	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011946162
1,439	Magic is Relevant	1990	SIGMOD	0.000106437
2,516	Optimization of Queries with User-defined Predicates	1996	VLDB	8.3572065e-05
3,707	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD	7.0789307e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	149	Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans	1998	SIGMOD
2	7,603	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
3	1,099	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD
4	2,890	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD
5	15	How Good Are Query Optimizers, Really?	2016	VLDB
6	10,144	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB
7	143	Optimization of Nonrecursive Queries	1986	VLDB
8	2,516	Optimization of Queries with User-defined Predicates	1996	VLDB
9	2,138	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	995	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB