DBScholar

Back to papers

Measuring the Complexity of Join Enumeration in Query Optimization

Summary: Analyzes Starburst’s parameterized join enumeration, quantifying search-space complexity with composite inner operands and Cartesian joins. Derives and validates shape-dependent counts, showing linear join queries remain polynomial—and optimizable at 100-table scale. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID
hc1e8ac2f3feb88d5
Venue
VLDB
Year
1990
Pagerank
0.00021082176
Overall Rank
321 | 97.85%
DOI
-

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@article{ono_vldb90,
        title = {{Measuring the Complexity of Join Enumeration in Query Optimization}},
        author = {Ono, Kiyoshi and Lehman, Guy M.},
        journal = {PVLDB},
        series = {{VLDB} '90},
        pages = {314},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 43 of 43 citing papers.

Rank Citing Paper Year Venue Pagerank
243 Automating Physical Database Design in a Parallel Database 2002 SIGMOD 0.00023349603
272 An Overview of Query Optimization in Relational Systems 1998 PODS 0.0002251422
288 Optimization of Dynamic Query Evaluation Plans 1994 SIGMOD 0.00021964339
725 Fundamental Techniques for Order Optimization 1996 SIGMOD 0.00014471289
796 Rapid Bushy Join-order Optimization with Cartesian Products 1996 SIGMOD 0.00013931773
870 Query Optimization in the Presence of Limited Access Patterns 1999 SIGMOD 0.00013342453
1,301 Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees without Cross Products 2006 VLDB 0.00011107788
1,727 Optimal Top-Down Join Enumeration 2007 SIGMOD 9.7849752e-05
1,949 Quantifying TPC-H Choke Points and Their Optimizations 2020 VLDB 9.3172855e-05
2,115 Reusing Invariants: A New Strategy for Correlated Queries 1998 SIGMOD 9.0119103e-05
2,138 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 8.9747973e-05
2,225 Shared Workload Optimization 2014 VLDB 8.8062552e-05
2,252 Counter Strike: Generic Top-Down Join Enumeration for Hypergraphs 2013 VLDB 8.7480805e-05
2,341 Extending the Search Strategy in a Query Optimizer 1991 VLDB 8.6079269e-05
2,524 Multi-Objective Parametric Query Optimization 2015 VLDB 8.3400278e-05
2,618 The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database 2016 VLDB 8.2193318e-05
2,660 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 8.1574087e-05
2,686 Cost-based or Learning-based? A Hybrid Query Optimizer for Query Plan Selection 2022 VLDB 8.1300913e-05
2,746 Holistic Twig Joins on Indexed XML Documents 2003 VLDB 8.0587951e-05
3,043 Fast, Randomized Join-Order Selection—Why Use Transformations? 1994 VLDB 7.7178769e-05
3,140 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.6012971e-05
3,574 Multi-Join Optimization for Symmetric Multiprocessors 1993 VLDB 7.1932731e-05
3,777 Parallelizing Query Optimization 2008 VLDB 7.0240115e-05
3,800 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 7.0130412e-05
3,850 EROC: A Toolkit for Building NEATO Query Optimizers 1996 VLDB 6.9778459e-05
4,040 Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer 2000 SIGMOD 6.8357679e-05
4,052 Of Snowstorms and Bushy Trees 2014 VLDB 6.8257821e-05
4,394 Bitvector-aware Query Optimization for Decision Support Queries 2020 SIGMOD 6.6182964e-05
4,417 Estimating Compilation Time of a Query Optimizer 2003 SIGMOD 6.6064397e-05
6,051 Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs 2009 SIGMOD 5.9019888e-05
6,111 On the Complexity of Generating Optimal Plans with Cross Products (extended abstract) 1997 PODS 5.8815204e-05
6,399 Optimizing Join Enumeration in Transformation-based Query Optimizers 2014 VLDB 5.796784e-05
7,546 Learned Offline Query Planning via Bayesian Optimization 2025 SIGMOD 5.4966669e-05
7,603 On the Calculation of Optimality Ranges for Relational Query Execution Plans 2018 SIGMOD 5.4846849e-05
8,046 Efficiently Computing Join Orders with Heuristic Search 2023 SIGMOD 5.3992239e-05
8,576 The Fittest Survives: An Adaptive Approach to Query Optimization 1995 VLDB 5.3109021e-05
9,221 DPconv: Super-Polynomially Faster Join Ordering 2024 SIGMOD 5.2036474e-05
9,628 Parallelizing Query Optimization on Shared-Nothing Architectures 2016 VLDB 5.1473253e-05
10,144 How to Optimize SQL Queries? A Comparison Between Split, Holistic, and Hybrid Approaches 2025 VLDB 5.0718686e-05
10,459 EncoderForge: Generating Efficient SQL for Encoders in Machine Learning Inference Pipelines 2026 SIGMOD 4.9769913e-05
12,127 Towards Multi-way Join Aware Optimizer in SAP HANA 2020 VLDB 4.9769913e-05
12,235 Errata for "Analysis of two existing and one new dynamic programming algorithm for the generation of optimal bushy join trees without cross products" 2018 VLDB 4.9769913e-05
13,234 TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer 1998 VLDB 4.9769913e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
143 Optimization of Nonrecursive Queries 1986 VLDB 0.00029168671
196 Grammar-like Functional Rules for Representing Query Optimization Alternatives 1988 SIGMOD 0.00025616489
469 Optimization of Large Join Queries 1988 SIGMOD 0.00017749337
2,311 Optimization of Nested Queries in a Distributed Relational Database 1984 VLDB 8.6623569e-05
2,552 An Architecture For Query Optimization 1982 SIGMOD 8.304074e-05
3,211 Implementing an Interpreter for Functional Rules in a Query Optimizer 1988 VLDB 7.5331392e-05
Previous Page 1 / 1 Next

Semantically Similar Papers

# Overall Rank Paper Year Venue
1 796 Rapid Bushy Join-order Optimization with Cartesian Products 1996 SIGMOD
2 3,777 Parallelizing Query Optimization 2008 VLDB
3 3,800 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD
4 6,547 Ranked Enumeration of Join Queries with Projections 2022 VLDB
5 1,185 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD
6 2,593 Optimal Algorithms for Ranked Enumeration of Answers to Full Conjunctive Queries 2020 VLDB
7 2,138 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB
8 15 How Good Are Query Optimizers, Really? 2016 VLDB
9 4,417 Estimating Compilation Time of a Query Optimizer 2003 SIGMOD
10 2,660 The Complexity of Transformation-Based Join Enumeration 1997 VLDB