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.9483042e-05
Overall Rank: 2,151 | 85.59%
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
842	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013501181
1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00011119184
2,182	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	8.9007338e-05
2,280	Parallel evaluation of multi-join queries	1995	SIGMOD	8.6972041e-05
2,911	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	7.8616647e-05
4,713	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	6.4397959e-05
4,809	Applying Hash Filters to Improving the Execution of Bushy Trees	1993	VLDB	6.3910269e-05
5,599	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.0535576e-05
5,730	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	5.9969396e-05
13,275	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.9605343e-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.0023948467
144	Optimization of Nonrecursive Queries	1986	VLDB	0.00029092688
156	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00028431734
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023099455
322	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00021032289
470	Optimization of Large Join Queries	1988	SIGMOD	0.00017699145
489	Randomized Algorithms For Optimizing Large Join Queries	1990	SIGMOD	0.00017402488
500	The Design of XPRS	1988	VLDB	0.0001724009
714	Optimization of Large Join Queries: Combining Heuristics and Combinatorial Techniques	1989	SIGMOD	0.00014578551
921	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013036878
1,215	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.0001147464
2,515	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.3437209e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	2,280	Parallel evaluation of multi-join queries	1995	SIGMOD
3	2,182	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB
4	6,154	Parallelizing Extensible Query Optimizers	2009	SIGMOD
5	5,446	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
6	5,523	Temporal Query Processing and Optimization in Multiprocessor Database Machines	1992	VLDB
7	448	Query Optimization for Parallel Execution	1992	SIGMOD
8	1,185	Adaptive Optimization of Very Large Join Queries	2018	SIGMOD
9	8,433	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB
10	3,785	Parallelizing Query Optimization	2008	VLDB