Database Paper Browser

Back to papers

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
1128
Venue
PODS
Year
1998
Pagerank
0.00022734812
Overall Rank
454 | 96.85%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 50 of 73 citing papers.

Rank Citing Paper Year Venue Pagerank
333 Neo: A Learned Query Optimizer 2019 VLDB 0.00027206884
461 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022499343
790 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.0001663283
1,057 Cosette: An Automated Prover for SQL 2017 CIDR 0.0001439886
1,307 SMCQL: Secure Querying for Federated Databases 2017 VLDB 0.0001266709
1,435 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00012004456
1,564 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00011350495
1,695 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010882793
1,758 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010655546
1,855 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00010315245
1,963 DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing 2025 VLDB 9.929429e-05
2,154 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 9.4208667e-05
2,296 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0776226e-05
2,529 Pregelix: Big(ger) Graph Analytics on A Dataflow Engine 2015 VLDB 8.5940768e-05
3,142 Active Learning for ML Enhanced Database Systems 2020 SIGMOD 7.4815444e-05
3,408 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.1288167e-05
3,704 How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates 2016 SIGMOD 6.827494e-05
4,161 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 6.3938006e-05
4,227 Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine 2022 VLDB 6.3434324e-05
4,409 Declarative Recursive Computation on an RDBMS 2019 VLDB 6.2104034e-05
4,687 Serving and Optimizing Machine Learning Workflows on Heterogeneous Infrastructures 2023 VLDB 5.9986055e-05
5,535 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 5.4539235e-05
5,633 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.4011156e-05
5,645 Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts 2022 SIGMOD 5.3923454e-05
5,727 Enabling Incremental Query Re-Optimization 2016 SIGMOD 5.3510544e-05
5,736 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 5.3482537e-05
5,744 Size and Treewidth Bounds for Conjunctive Queries 2009 PODS 5.3441438e-05
5,876 Membrane - Safe and Performant Data Access Controls in Apache Spark in the Presence of Imperative Code 2024 VLDB 5.2922419e-05
5,880 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 5.2898074e-05
5,930 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 5.2682075e-05
6,328 A Comparative Study and Component Analysis of Query Plan Representation Techniques in ML4DB Studies 2024 VLDB 5.1082882e-05
6,345 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.1023048e-05
6,498 Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs 2020 SIGMOD 5.0392468e-05
6,806 Query Optimization over Crowdsourced Data 2013 VLDB 4.9218336e-05
7,296 Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and Opportunities 2022 SIGMOD 4.7723197e-05
7,304 MRTuner: A Toolkit to Enable Holistic Optimization for MapReduce Jobs 2014 VLDB 4.7684491e-05
7,351 Distributed Outlier Detection using Compressive Sensing 2015 SIGMOD 4.7545562e-05
7,693 Processing and Optimizing Main Memory Spatial-Keyword Queries 2016 VLDB 4.6759281e-05
7,736 From a Stream of Relational Queries to Distributed Stream Processing 2010 VLDB 4.664248e-05
8,016 User-Optimizer Communication using Abstract Plans in Sybase ASE 2001 VLDB 4.6050078e-05
8,127 Robust Query Processing: Mission Possible 2020 VLDB 4.579056e-05
8,156 List Intersection for Web Search: Algorithms, Cost Models, and Optimizations 2019 VLDB 4.5741172e-05
8,158 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 4.5730772e-05
8,345 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 4.5426916e-05
8,466 Building Statistical Models and Scoring with UDFs 2007 SIGMOD 4.5050696e-05
8,488 Can Large Language Models Be Query Optimizer for Relational Databases? 2026 SIGMOD 4.4998609e-05
8,506 New Query Optimization Techniques in the Spark Engine of Azure Synapse 2022 VLDB 4.4957661e-05
8,697 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.4657888e-05
8,774 Tiresias: Enabling Predictive Autonomous Storage and Indexing 2022 VLDB 4.4559995e-05
8,990 Towards Enhancing Database Education: Natural Language Generation Meets Query Execution Plans 2021 SIGMOD 4.413295e-05
Previous Page 1 / 2 Next

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.0040449103
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.0010066783
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080435857
51 Including Group-By in Query Optimization 1994 VLDB 0.00067123727
59 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064501896
64 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063612837
72 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.00058577335
88 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00052316625
100 Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers 1987 VLDB 0.00049624696
106 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.00048400734
116 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046148737
130 Optimization of Nested SQL Queries Revisited 1987 SIGMOD 0.00044031247
132 The EXODUS Optimizer Generator 1987 SIGMOD 0.00042994082
138 Query Transformation for PSJ-queries 1987 VLDB 0.00042334092
139 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00042299329
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041786333
195 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00035406558
218 Aggregate-Query Processing in Data Warehousing Environments 1995 VLDB 0.00033503922
219 Grammar-like Functional Rules for Representing Query Optimization Alternatives 1988 SIGMOD 0.00033244259
248 Eager Aggregation and Lazy Aggregation 1995 VLDB 0.00030785339
268 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00029662304
269 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029656549
307 Extensible Query Processing in Starburst 1989 SIGMOD 0.00028211308
423 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00023669348
508 Dynamic Query Evaluation Plans 1989 SIGMOD 0.00021463742
530 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.00020803682
584 Answering Queries with Aggregation Using Views 1996 VLDB 0.0001971526
808 Universality of Serial Histograms 1993 VLDB 0.00016432772
876 Parametric Query Optimization 1992 VLDB 0.00015716096
896 Towards an Open Architecture for LDL 1989 VLDB 0.00015529255
901 Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins 1990 SIGMOD 0.00015487777
907 Fundamental Techniques for Order Optimization 1996 SIGMOD 0.00015435983
990 Improved Unnesting Algorithms for Join Aggregate SQL Queries 1992 VLDB 0.00014809094
1,302 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012705525
1,313 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.0001263831
1,423 Magic is Relevant 1990 SIGMOD 0.00012054867
2,860 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9934503e-05
4,199 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.3662839e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
220 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00033194808
8,213 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD 4.557937e-05
1,199 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD 0.00013354204
3,408 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.1288167e-05
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059038975
9,957 How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches 2025 VLDB 4.2373024e-05
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00041510555
2,860 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9934503e-05
2,044 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.6953608e-05
1,070 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00014316791