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: 9551
Venue: VLDB
Year: 2005
Pagerank: 5.8550491e-05
Overall Rank: 6,515 | 55.31%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Bin Liu (Worcester Polytechnic Institute)
2. Elke A. Rundensteiner (Worcester Polytechnic Institute)

BibTeX Citation

@article{liu_vldb05,
        title = {{Revisiting Pipelined Parallelism in Multi-Join Query Processing}},
        author = {Liu, Bin and Rundensteiner, Elke A.},
        journal = {PVLDB},
        series = {{VLDB} '05},
        pages = {829},
        year = {2005}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
631	Relational Joins on Graphics Processors	2008	SIGMOD	0.00015591241
7,915	Krypton: Real-time Serving and Analytical SQL Engine at ByteDance	2023	VLDB	5.5181056e-05
9,269	A Dynamically Adaptive Distributed System for Processing Complex Continuous Queries	2005	VLDB	5.295102e-05
10,096	Out-of-order Execution of Database Queries	2020	VLDB	5.1523392e-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
98	Encapsulation of Parallelism in the Volcano Query Processing System	1990	SIGMOD	0.00034510605
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
434	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018531826
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
904	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00013319798
1,720	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	9.9265634e-05
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,337	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD	8.7267117e-05
2,470	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.5330174e-05
2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.0594267e-05
3,090	Parallelism in a Main-Memory DBMS: The performance of PRISMA/DB	1992	VLDB	7.7686303e-05
3,250	On Optimal Processor Allocation To Support Pipelined Hash Joins	1993	SIGMOD	7.597429e-05
9,269	A Dynamically Adaptive Distributed System for Processing Complex Continuous Queries	2005	VLDB	5.295102e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,726	Parallelizing Query Optimization	2008	VLDB
2	6,255	Elastic Pipelining in an In-Memory Database Cluster	2016	SIGMOD
3	1,022	A Scalable, Predictable Join Operator for Highly Concurrent Data Warehouses	2009	VLDB
4	8,243	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB
5	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
6	1,720	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB
7	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
8	2,272	Parallel evaluation of multi-join queries	1995	SIGMOD
9	3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
10	4,652	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD