Optimization of Multi-Way Join Queries for Parallel Execution

Summary: Introduces a parallel-aware optimizer that explores bushy multi-way join plans rather than only linear plans. It jointly chooses join order/method, parallel join count, and processor allocation, achieving near-optimal plans with far lower overhead than exhaustive search. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8235
Venue: VLDB
Year: 1991
Pagerank: 9.1594086e-05
Overall Rank: 2,104 | 85.57%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Hongjun Lu (National University of Singapore)
2. Ming-Chien Shan (Hewlett Packard Enterprise)
3. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@article{lu_vldb91,
        title = {{Optimization of Multi-Way Join Queries for Parallel Execution}},
        author = {Lu, Hongjun and Shan, Ming-Chien and Tan, Kian-Lee},
        journal = {PVLDB},
        series = {{VLDB} '91},
        pages = {549},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 10 of 10 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
830	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013761367
1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011166426
2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	9.1242116e-05
2,272	Parallel evaluation of multi-join queries	1995	SIGMOD	8.8242407e-05
2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.0594267e-05
4,652	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	6.5851924e-05
5,014	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.4002123e-05
5,451	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.2139293e-05
5,615	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	6.1497352e-05
12,938	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 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.0024089429
143	Optimization of Nonrecursive Queries	1986	VLDB	0.0002959213
152	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00029038365
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
463	Optimization of Large Join Queries	1988	SIGMOD	0.00018064961
479	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017789732
497	The Design of XPRS	1988	VLDB	0.00017462492
698	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014879675
904	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013319798
1,188	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00011756444
2,470	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.5330174e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	13,231	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS
2	2,272	Parallel evaluation of multi-join queries	1995	SIGMOD
3	6,026	Parallelizing Extensible Query Optimizers	2009	SIGMOD
4	2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
5	5,399	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
6	5,402	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB
7	434	Query Optimization for Parallel Execution	1992	SIGMOD
8	1,286	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
9	8,243	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB
10	3,726	Parallelizing Query Optimization	2008	VLDB