Database Paper Browser

Back to papers

Optimization of Large Join Queries

Summary: Large-SPJ optimization modeled as join-order search (NP-hard). Applies iterative improvement and SA; uses factorial experiments and ANOVA to set parameters; finds iterative improvement generally best, though SA remains competitive at longer runtimes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID
2372
Venue
SIGMOD
Year
1988
Pagerank
0.00024654816
Overall Rank
388 | 97.31%
DOI
-

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank Citing Paper Year Venue Pagerank
63 Improved Histograms for Selectivity Estimation of Range Predicates 1996 SIGMOD 0.00063595699
400 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00024308369
422 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00023654556
782 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00016665859
811 Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization 1991 SIGMOD 0.00016385568
870 Parametric Query Optimization 1992 VLDB 0.00015709369
897 Estimating the Size of Generalized Transitive Closures 1989 VLDB 0.00015484372
2,051 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.6871984e-05
2,268 Extending the Search Strategy in a Query Optimizer 1991 VLDB 9.1524415e-05
2,311 Parallel evaluation of multi-join queries 1995 SIGMOD 9.0610521e-05
2,878 The Complexity of Transformation-Based Join Enumeration 1997 VLDB 7.9694937e-05
3,053 Fast, Randomized Join-Order Selection — Why Use Transformations? 1994 VLDB 7.6482987e-05
3,056 Multiple Join Size Estimation by Virtual Domains (extended abstract) 1993 PODS 7.6459653e-05
3,476 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.0560383e-05
4,255 Parallelizing Query Optimization 2008 VLDB 6.3080082e-05
4,734 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 5.9553181e-05
5,303 Applying Hash Filters To Improving The Execution Of Bushy Trees 1993 VLDB 5.5740327e-05
5,772 Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries 2024 CIDR 5.3313794e-05
6,336 Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs 2009 SIGMOD 5.1009488e-05
7,486 Quantum-Inspired Digital Annealing for Join Ordering 2024 VLDB 4.7135369e-05
7,979 On the Optimality of Strategies for Multiple Joins 1990 PODS 4.6089395e-05
8,192 The Fittest Survives: An Adaptive Approach to Query Optimization 1995 VLDB 4.5575625e-05
8,720 A Fast Randomized Algorithm for Multi-Objective Query Optimization 2016 SIGMOD 4.4563359e-05
10,295 Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation 2026 VLDB 4.1905499e-05
12,900 Avoiding Cartesian Products in Programs for Multiple Joins (Extended Abstract) 1992 PODS 4.1905499e-05
Previous Page 1 / 1 Next

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
9 Implementation Techniques For Main Memory Database Systems 1984 SIGMOD 0.001426258
144 Optimization of Nonrecursive Queries 1986 VLDB 0.00041430126
569 Query Optimization by Simulated Annealing 1987 SIGMOD 0.00019912758
Previous Page 1 / 1 Next

Semantically Similar Papers

Overall Rank Paper Year Venue Pagerank
3,476 Solving the Join Ordering Problem via Mixed Integer Linear Programming 2017 SIGMOD 7.0560383e-05
422 Measuring the Complexity of Join Enumeration in Query Optimization 1990 VLDB 0.00023654556
3,053 Fast, Randomized Join-Order Selection — Why Use Transformations? 1994 VLDB 7.6482987e-05
4,526 Simplicity Done Right for Join Ordering 2021 CIDR 6.1079584e-05
71 How Good Are Query Optimizers, Really? 2016 VLDB 0.00059446482
4,734 Query Simplification: Graceful Degradation for Join-Order Optimization 2009 SIGMOD 5.9553181e-05
2,051 Optimization of Multi-Way Join Queries for Parallel Execution 1991 VLDB 9.6871984e-05
1,621 Adaptive Optimization of Very Large Join Queries 2018 SIGMOD 0.00011105663
400 Randomized Algorithms For Optimizing Large Join Queries 1990 SIGMOD 0.00024308369
782 Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques 1989 SIGMOD 0.00016665859