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: h3dfc64603cf1c382
Venue: VLDB
Year: 1991
Pagerank: 8.9747973e-05
Overall Rank: 2,138 | 85.64%
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
845	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013527474
1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011147959
2,170	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	8.9233322e-05
2,267	Parallel evaluation of multi-join queries	1995	SIGMOD	8.7192424e-05
2,897	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	7.8817062e-05
4,712	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	6.4543768e-05
4,790	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.4114271e-05
5,584	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.073616e-05
5,736	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	6.0109095e-05
13,234	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.9769913e-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.0023943337
143	Optimization of Nonrecursive Queries	1986	VLDB	0.00029168671
156	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00028509887
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.0002316492
321	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021082176
469	Optimization of Large Join Queries	1988	SIGMOD	0.00017749337
487	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017455404
499	The Design of XPRS	1988	VLDB	0.00017291748
708	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014623779
920	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013075939
1,213	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00011508483
2,508	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.3685814e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,292	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	13,527	Using Semiouterjoins to Process Queries in Multidatabase Systems	1984	PODS
3	6,138	Parallelizing Extensible Query Optimizers	2009	SIGMOD
4	2,170	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
5	5,429	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
6	5,540	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB
7	446	Query Optimization for Parallel Execution	1992	SIGMOD
8	1,185	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
9	8,417	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB
10	3,777	Parallelizing Query Optimization	2008	VLDB