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.00022796106
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
329 Neo: A Learned Query Optimizer 2019 VLDB 0.00027301488
460 Graphs-at-a-time: Query Language and Access Methods for Graph Databases 2008 SIGMOD 0.00022679846
786 Exploiting Statistics on Query Expressions for Optimization 2002 SIGMOD 0.00016624743
1,056 Cosette: An Automated Prover for SQL 2017 CIDR 0.00014391317
1,291 SMCQL: Secure Querying for Federated Databases 2017 VLDB 0.00012771034
1,301 Simba: Efficient In-Memory Spatial Analytics 2016 SIGMOD 0.00012702767
1,564 Keyword Search in Databases: The Power of RDBMS 2009 SIGMOD 0.00011340407
1,691 Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-Size Estimation 1999 VLDB 0.00010890775
1,756 Sampling-Based Query Re-Optimization 2016 SIGMOD 0.00010659753
1,839 DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing 2025 VLDB 0.00010351287
1,856 AI Meets AI: Leveraging Query Executions to Improve Index Recommendations 2019 SIGMOD 0.00010319105
2,158 DIFF: A Relational Interface for Large-Scale Data Explanation 2019 VLDB 9.4117885e-05
2,298 Joins via Geometric Resolutions: Worst-case and Beyond 2015 PODS 9.0746479e-05
2,528 Pregelix: Big(ger) Graph Analytics on A Dataflow Engine 2015 VLDB 8.5953347e-05
3,144 Active Learning for ML Enhanced Database Systems 2020 SIGMOD 7.4844943e-05
3,402 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.134261e-05
3,703 How to Win a Hot Dog Eating Contest: Distributed Incremental View Maintenance with Batch Updates 2016 SIGMOD 6.8249334e-05
4,160 Access Path Selection in Main-Memory Optimized Data Systems: Should I Scan or Should I Probe? 2017 SIGMOD 6.3886736e-05
4,227 Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine 2022 VLDB 6.3381409e-05
4,406 Declarative Recursive Computation on an RDBMS 2019 VLDB 6.2044305e-05
4,686 Serving and Optimizing Machine Learning Workflows on Heterogeneous Infrastructures 2023 VLDB 5.9929067e-05
5,528 Warper: Efficiently Adapting Learned Cardinality Estimators to Data and Workload Drifts 2022 SIGMOD 5.4571136e-05
5,543 Lightweight Cardinality Estimation in LSM-based Systems 2018 SIGMOD 5.4486922e-05
5,639 Analyzing the Impact of Cardinality Estimation on Execution Plans in Microsoft SQL Server 2023 VLDB 5.3972261e-05
5,737 Enabling Incremental Query Re-Optimization 2016 SIGMOD 5.3459609e-05
5,742 Efficient Computation of Multiple Group By Queries 2005 SIGMOD 5.3432178e-05
5,752 Size and Treewidth Bounds for Conjunctive Queries 2009 PODS 5.3393414e-05
5,882 Membrane - Safe and Performant Data Access Controls in Apache Spark in the Presence of Imperative Code 2024 VLDB 5.2871604e-05
5,886 COMPASS: Online Sketch-based Query Optimization for In-Memory Databases 2021 SIGMOD 5.2847297e-05
5,931 FASTgres: Making Learned Query Optimizer Hinting Effective 2023 VLDB 5.2632167e-05
6,328 A Comparative Study and Component Analysis of Query Plan Representation Techniques in ML4DB Studies 2024 VLDB 5.1034426e-05
6,341 Operator and Query Progress Estimation in Microsoft SQL Server Live Query Statistics 2016 SIGMOD 5.0980049e-05
6,493 Memory-Aware Framework for Efficient Second-Order Random Walk on Large Graphs 2020 SIGMOD 5.0344095e-05
6,801 Query Optimization over Crowdsourced Data 2013 VLDB 4.9175463e-05
7,291 Multi-Tenant Cloud Data Services: State-of-the-Art, Challenges and Opportunities 2022 SIGMOD 4.7677422e-05
7,298 MRTuner: A Toolkit to Enable Holistic Optimization for MapReduce Jobs 2014 VLDB 4.7651301e-05
7,347 Distributed Outlier Detection using Compressive Sensing 2015 SIGMOD 4.7502395e-05
7,693 Processing and Optimizing Main Memory Spatial-Keyword Queries 2016 VLDB 4.6714423e-05
7,735 From a Stream of Relational Queries to Distributed Stream Processing 2010 VLDB 4.6599101e-05
8,020 User-Optimizer Communication using Abstract Plans in Sybase ASE 2001 VLDB 4.6005954e-05
8,130 Robust Query Processing: Mission Possible 2020 VLDB 4.5746794e-05
8,160 List Intersection for Web Search: Algorithms, Cost Models, and Optimizations 2019 VLDB 4.5697316e-05
8,162 MONSOON: Multi-Step Optimization and Execution of Queries with Partially Obscured Predicates 2020 SIGMOD 4.5686903e-05
8,339 SlabCity: Whole-Query Optimization using Program Synthesis 2023 VLDB 4.5383933e-05
8,462 Building Statistical Models and Scoring with UDFs 2007 SIGMOD 4.5007504e-05
8,479 Can Large Language Models Be Query Optimizer for Relational Databases? 2026 SIGMOD 4.4967983e-05
8,502 New Query Optimization Techniques in the Spark Engine of Azure Synapse 2022 VLDB 4.491819e-05
8,695 Convolution and Cross-Correlation of Count Sketches Enables Fast Cardinality Estimation of Multi-Join Queries 2024 SIGMOD 4.461508e-05
8,714 Tiresias: Enabling Predictive Autonomous Storage and Indexing 2022 VLDB 4.457682e-05
8,997 Towards Enhancing Database Education: Natural Language Generation Meets Query Execution Plans 2021 SIGMOD 4.4090643e-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.0040465394
16 MAGIC SETS AND OTHER STRANGE WAYS TO IMPLEMENT LOGIC PROGRAMS (Extended Abstract) 1986 PODS 0.00099936325
28 Accurate Estimation Of The Number Of Tuples Satisfying A Condition 1984 SIGMOD 0.00080571183
51 Including Group-By in Query Optimization 1994 VLDB 0.00067060283
60 Sampling-Based Estimation of the Number of Distinct Values of an Attribute 1995 VLDB 0.00064450997
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
72 Combining Fuzzy Information from Multiple Systems 1996 PODS 0.00058498396
89 Common Expression Analysis in Database Applications 1982 SIGMOD 0.00052299473
102 Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers 1987 VLDB 0.00049592627
107 Extensible/Rule Based Query Rewrite Optimization in Starburst 1992 SIGMOD 0.00048363446
114 Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries 1988 SIGMOD 0.00046317654
130 Optimization of Nested SQL Queries Revisited 1987 SIGMOD 0.00044001626
134 The EXODUS Optimizer Generator 1987 SIGMOD 0.00043070028
138 Query Transformation for PSJ-queries 1987 VLDB 0.00042322097
140 Predicate Migration: Optimizing Queries with Expensive Predicates 1993 SIGMOD 0.00042289025
141 Selectivity Estimation Without the Attribute Value Independence Assumption 1997 VLDB 0.00041819767
195 Optimizing Queries over Multimedia Repositories 1996 SIGMOD 0.00035317524
218 Aggregate-Query Processing in Data Warehousing Environments 1995 VLDB 0.00033489004
220 Grammar-like Functional Rules for Representing Query Optimization Alternatives 1988 SIGMOD 0.00033312045
249 Eager Aggregation and Lazy Aggregation 1995 VLDB 0.00030773137
269 R* Optimizer Validation and Performance Evaluation for Local Queries 1986 SIGMOD 0.00029665158
270 Fast Incremental Maintenance of Approximate Histograms 1997 VLDB 0.00029648047
309 Extensible Query Processing in Starburst 1989 SIGMOD 0.00028195213
422 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00023654556
509 Dynamic Query Evaluation Plans 1989 SIGMOD 0.00021463676
531 Random Sampling for Histogram Construction: How much is enough? 1998 SIGMOD 0.0002079072
583 Answering Queries with Aggregation Using Views 1996 VLDB 0.00019705383
801 Universality of Serial Histograms 1993 VLDB 0.00016440976
870 Parametric Query Optimization 1992 VLDB 0.00015709369
891 Towards an Open Architecture for LDL 1989 VLDB 0.00015531595
898 Query Graphs, Implementing Trees, and Freely-Reorderable Outerjoins 1990 SIGMOD 0.00015476243
904 Fundamental Techniques for Order Optimization 1996 SIGMOD 0.00015425636
991 Improved Unnesting Algorithms for Join Aggregate SQL Queries 1992 VLDB 0.00014797083
1,303 Query Optimization by Predicate Move-Around 1994 VLDB 0.00012692678
1,313 Cost-Based Optimization for Magic: Algebra and Implementation 1996 SIGMOD 0.00012629432
1,423 Magic is Relevant 1990 SIGMOD 0.00012047765
2,867 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9931252e-05
4,198 Implementation of Magic-sets in a Relational Database System 1994 SIGMOD 6.361961e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
221 Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans 1998 SIGMOD 0.00033182072
8,193 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD 4.5575291e-05
1,201 A General Framework for the Optimization of Object-Oriented Queries 1992 SIGMOD 0.00013341955
3,402 Query Optimizers: Time to Rethink the Contract? 2009 SIGMOD 7.134261e-05
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059446482
9,956 How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches 2025 VLDB 4.2332427e-05
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
2,867 Optimization of Queries with User-defined Predicates 1996 VLDB 7.9931252e-05
2,051 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.6871984e-05
1,064 Analyzing Plan Diagrams of Database Query Optimizers 2005 VLDB 0.00014348262