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: hba30f0123d835d7a
Venue: SIGMOD
Year: 1988
Pagerank: 0.00017755852
Overall Rank: 470 | 96.85%
DOI: 10.1145/50202.50203

Incoming Non-self Citations Over Time

Authors

1. Arun Swami (Stanford University)
2. Anoop Gupta (Stanford University)

BibTeX Citation

@inproceedings{swami_sigmod88,
        title = {{Optimization of Large Join Queries}},
        author = {Swami, Arun and Gupta, Anoop},
        series = {{SIGMOD} '88},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/50202.50203},
        url = {https://dl.acm.org/doi/10.1145/50202.50203},
        year = {1988}
}

Incoming Citations (Sorted by Pagerank)

Showing 25 of 25 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
37	Improved Histograms for Selectivity Estimation of Range Predicates	1996	SIGMOD	0.00047731453
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021088704
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017462723
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014629998
725	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014465736
792	Parametric Query Optimization	1992	VLDB	0.00013942753
1,416	Estimating the Size of Generalized Transitive Closures	1989	VLDB	0.00010734049
2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	8.9789503e-05
2,266	Parallel evaluation of multi-join queries	1995	SIGMOD	8.7229053e-05
2,339	Extending the Search Strategy in a Query Optimizer	1991	VLDB	8.6118503e-05
2,660	The Complexity of Transformation-Based Join Enumeration	1997	VLDB	8.1611913e-05
3,005	Multiple Join Size Estimation by Virtual Domains (extended abstract)	1993	PODS	7.7621043e-05
3,042	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB	7.7213044e-05
3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD	7.6046928e-05
3,775	Parallelizing Query Optimization	2008	VLDB	7.0272615e-05
3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD	7.0163619e-05
4,369	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6315141e-05
4,786	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.4143659e-05
5,908	Quantum-Inspired Digital Annealing for Join Ordering	2024	VLDB	5.9506986e-05
6,049	Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs	2009	SIGMOD	5.9047797e-05
8,462	On the Optimality of Strategies for Multiple Joins	1990	PODS	5.3350162e-05
8,575	The Fittest Survives: An Adaptive Approach to Query Optimization	1995	VLDB	5.3115836e-05
8,651	Hybrid Mixed Integer Linear Programming for Large-Scale Join Order Optimisation	2026	VLDB	5.2945994e-05
8,971	A Fast Randomized Algorithm for Multi-Objective Query Optimization	2016	SIGMOD	5.2462912e-05
13,374	Avoiding Cartesian Products in Programs for Multiple Joins (Extended Abstract)	1992	PODS	4.9793485e-05

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.0023947656
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029179719
859	Query Optimization by Simulated Annealing	1987	SIGMOD	0.00013418999

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,139	Solving the Join Ordering Problem via Mixed Integer Linear Programming	2017	SIGMOD
2	321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB
3	3,042	Fast, Randomized Join-Order Selection—Why Use Transformations?	1994	VLDB
4	3,982	Simplicity Done Right for Join Ordering	2021	CIDR
5	15	How Good Are Query Optimizers, Really?	2016	VLDB
6	3,797	Query Simplification: Graceful Degradation for Join-Order Optimization	2009	SIGMOD
7	2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
8	1,186	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
9	487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD
10	708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD