Revisiting Pipelined Parallelism in Multi-Join Query Processing

Summary: Challenging the assumption that maximal pipelined parallelism is best for multi-join processing. Proposes segmented bushy processing that blends parallelism forms, achieving about 50% faster total processing than state-of-the-art on a real cluster. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9361
Venue: VLDB
Year: 2005
Pagerank: 5.1074949e-05
Overall Rank: 6,322 | 56.07%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Bin Liu
2. Elke A. Rundensteiner

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
771	Relational Joins on Graphics Processors	2008	SIGMOD	0.00016813054
7,491	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	4.7135369e-05
9,083	A Dynamically Adaptive Distributed System for Processing Complex Continuous Queries	2005	VLDB	4.3951708e-05
9,939	Out-of-order Execution of Database Queries	2020	VLDB	4.2416883e-05

Outgoing Citations (Sorted by Pagerank)

Showing 14 of 14 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
113	Encapsulation of Parallelism in the Volcano Query Processing System	1990	SIGMOD	0.0004673401
230	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00032145125
439	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023183237
548	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00020369531
1,063	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00014352292
1,826	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	0.00010392071
1,851	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	0.00010326646
2,311	Parallel evaluation of multi-join queries	1995	SIGMOD	9.0610521e-05
2,416	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.8520203e-05
2,458	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD	8.7601979e-05
2,622	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.4404954e-05
3,113	Parallelism in a Main-Memory DBMS: The performance of PRISMA/DB	1992	VLDB	7.5433318e-05
3,265	On Optimal Processor Allocation To Support Pipelined Hash Joins	1993	SIGMOD	7.3055541e-05
9,083	A Dynamically Adaptive Distributed System for Processing Complex Continuous Queries	2005	VLDB	4.3951708e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,255	Parallelizing Query Optimization	2008	VLDB	6.3080082e-05
6,301	Elastic Pipelining in an In-Memory Database Cluster	2016	SIGMOD	5.1172165e-05
1,430	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB	0.0001202506
7,832	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB	4.636825e-05
2,051	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6871984e-05
1,851	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	0.00010326646
1,938	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD	0.00010025547
2,311	Parallel evaluation of multi-join queries	1995	SIGMOD	9.0610521e-05
2,599	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.4655075e-05
4,784	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD	5.9205964e-05