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.00022881075
Overall Rank: 259 | 98.27%
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 29 of 79 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
8,869	Building Statistical Models and Scoring with UDFs	2007	SIGMOD	5.2463747e-05
8,902	Tiresias: Enabling Predictive Autonomous Storage and Indexing	2022	VLDB	5.2387388e-05
9,155	Towards Enhancing Database Education: Natural Language Generation Meets Query Execution Plans	2021	SIGMOD	5.204563e-05
9,647	A Theory of Regular Queries	2016	PODS	5.132775e-05
9,687	Window Function Expression: Let the Self-join Enter	2024	VLDB	5.1258854e-05
9,695	Parallel Query Processing: To Separate Communication from Computation	2022	SIGMOD	5.1258854e-05
9,785	PlinyCompute: A Platform for High-Performance, Distributed, Data-Intensive Tool Development	2018	SIGMOD	5.115551e-05
9,812	Online Optimization and Fair Costing for Dynamic Data Sharing in a Cloud Data Market	2014	SIGMOD	5.1123244e-05
10,064	Distributed Numerical and Machine Learning Computations via Two-Phase Execution of Aggregated Join Trees	2021	VLDB	5.0751093e-05
10,143	Still Asking: How Good Are Query Optimizers, Really?	2025	VLDB	5.0597449e-05
10,170	ParSEval: Plan-aware Test Database Generation for SQL Equivalence Evaluation	2025	VLDB	5.0559291e-05
10,249	Turbo-Charging SPJ Query Plans with Learned Physical Join Operator Selections	2022	VLDB	5.0412674e-05
10,281	Towards the Scheduling of Vertex-constrained Multi Subgraph Matching Query	2020	SIGMOD	5.0334833e-05
10,368	Efficient Enumeration of Recursive Plans in Transformation-based Query Optimizers	2024	VLDB	5.0064651e-05
10,416	When RAG Meets Query Planning: Logical Query Trees for Exploratory Reasoning Problems	2027	SIGMOD	4.9605343e-05
10,425	KathDB: Explainable Multimodal Database Management System with Human-AI Collaboration	2026	CIDR	4.9605343e-05
10,512	Detecting Join Bugs in Database Engines via Join Implication Reasoning	2026	SIGMOD	4.9605343e-05
10,590	Towards Selecting Informative Alternative Relational Query Plans for Database Education	2026	SIGMOD	4.9605343e-05
10,869	NeurIDA: Dynamic Modeling for Effective In-Database Analytics	2026	VLDB	4.9605343e-05
10,971	Overlay Bitmap Encoding for Efficient Consumption of Apache Parquet Files	2026	VLDB	4.9605343e-05
11,340	Unraveling the Impact of Window Semantics: Optimizing Join Order for Efficient Stream Processing	2025	VLDB	4.9605343e-05
11,564	Sub-optimal Join Order Identification with L1-error	2024	SIGMOD	4.9605343e-05
11,601	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.9605343e-05
11,990	Synchronization Schemas	2021	PODS	4.9605343e-05
12,424	Parallel Evaluation of Multi-Semi-Joins	2016	VLDB	4.9605343e-05
12,801	Ten Thousand SQLs: Parallel Keyword Queries Computing	2010	VLDB	4.9605343e-05
12,835	A Framework for Testing Query Transformation Rules	2009	SIGMOD	4.9605343e-05
12,842	Ordering, Distinctness, Aggregation, Partitioning and DQP Optimization in Sybase ASE 15	2009	SIGMOD	4.9605343e-05
13,136	The NEXT Framework for Logical XQuery Optimization	2004	VLDB	4.9605343e-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.0023948467
18	MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract)	1986	PODS	0.00058816744
36	Accurate Estimation Of The Number Of Tuples Satisfying A Condition	1984	SIGMOD	0.00047770864
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047654188
73	Including Group-By in Query Optimization	1994	VLDB	0.00037420958
78	Sampling-Based Estimation of the Number of Distinct Values of an Attribute	1995	VLDB	0.00036725074
99	Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers	1987	VLDB	0.00034024478
103	Selectivity Estimation Without the Attribute Value Independence Assumption	1997	VLDB	0.00033847446
109	Extensible/Rule Based Query Rewrite Optimization in Starburst	1992	SIGMOD	0.00032702871
118	The EXODUS Optimizer Generator	1987	SIGMOD	0.00031320165
119	Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries	1988	SIGMOD	0.00031291457
125	Predicate Migration: Optimizing Queries with Expensive Predicates	1993	SIGMOD	0.00030398363
133	Optimization of Nested SQL Queries Revisited	1987	SIGMOD	0.0003015194
155	Common Expression Analysis in Database Applications	1982	SIGMOD	0.0002844242
168	Query Transformation for PSJ-queries	1987	VLDB	0.00027117709
170	Combining Fuzzy Information from Multiple Systems	1996	PODS	0.0002707332
197	Grammar-like Functional Rules for Representing Query Optimization Alternatives	1988	SIGMOD	0.00025558952
204	Aggregate-Query Processing in Data Warehousing Environments	1995	VLDB	0.0002516936
213	Eager Aggregation and Lazy Aggregation	1995	VLDB	0.00024695393
242	Fast Incremental Maintenance of Approximate Histograms	1997	VLDB	0.00023327437
275	Extensible Query Processing in Starburst	1989	SIGMOD	0.000224395
322	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021032289
396	R* Optimizer Validation and Performance Evaluation for Local Queries	1986	SIGMOD	0.00019119719
479	Dynamic Query Evaluation Plans	1989	SIGMOD	0.00017595584
518	Random Sampling for Histogram Construction: How much is enough?	1998	SIGMOD	0.00016918797
567	Answering Queries with Aggregation Using Views	1996	VLDB	0.00016228477
687	Optimizing Queries over Multimedia Repositories	1996	SIGMOD	0.00014736766
726	Fundamental Techniques for Order Optimization	1996	SIGMOD	0.0001443284
792	Parametric Query Optimization	1992	VLDB	0.00013903954
806	Universality of Serial Histograms	1993	VLDB	0.00013752086
1,015	Improved Unnesting Algorithms for Join Aggregate SQL Queries	1992	VLDB	0.00012468327
1,032	Cost-Based Optimization for Magic: Algebra and Implementation	1996	SIGMOD	0.00012376627
1,063	Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins	1990	SIGMOD	0.00012198695
1,076	Towards an Open Architecture for LDL	1989	VLDB	0.00012128405
1,122	Query Optimization by Predicate Move-Around	1994	VLDB	0.00011915958
1,443	Magic is Relevant	1990	SIGMOD	0.00010618161
2,521	Optimization of Queries with User-defined Predicates	1996	VLDB	8.3339593e-05
3,702	Implementation of Magic-sets in a Relational Database System	1994	SIGMOD	7.0617354e-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,619	On the Calculation of Optimality Ranges for Relational Query Execution Plans	2018	SIGMOD
3	1,102	A General Framework for the Optimization of Object-Oriented Queries	1992	SIGMOD
4	2,888	Query Optimizers: Time to Rethink the Contract?	2009	SIGMOD
5	15	How Good Are Query Optimizers, Really?	2016	VLDB
6	10,181	How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches	2025	VLDB
7	144	Optimization of Nonrecursive Queries	1986	VLDB
8	2,521	Optimization of Queries with User-defined Predicates	1996	VLDB
9	2,151	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
10	996	Analyzing Plan Diagrams of Database Query Optimizers	2005	VLDB