Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism

Summary: Models pipelined parallelization of SQL plans as weighted operator-tree scheduling, explicitly balancing parallelism against communication overhead. Fast algorithms achieve near-optimal response times empirically, with worst-case performance ratios near 2 across broad cases. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 8370
Venue: VLDB
Year: 1994
Pagerank: 9.1242116e-05
Overall Rank: 2,131 | 85.39%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Waqar Hasan (Hewlett Packard Enterprise; Stanford University)
2. Rajeev Motwani (Stanford University)

BibTeX Citation

@article{hasan_vldb94,
        title = {{Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism}},
        author = {Hasan, Waqar and Motwani, Rajeev},
        journal = {PVLDB},
        series = {{VLDB} '94},
        pages = {36},
        year = {1994}
}

Incoming Citations (Sorted by Pagerank)

Showing 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,514	Upper and Lower Bounds on the Cost of a Map-Reduce Computation	2013	VLDB	0.00010527649
1,762	Multiobjective Query Optimization	2001	PODS	9.812504e-05
2,068	Scheduling Problems in Parallel Query Optimization	1995	PODS	9.2310451e-05
2,337	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD	8.7267117e-05
2,622	A Latency and Fault-Tolerance Optimizer for Online Parallel Query Plans	2011	SIGMOD	8.3330136e-05
2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.0594267e-05
3,046	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.8159925e-05
4,508	To Share or Not to Share?	2007	VLDB	6.6561159e-05
5,451	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.2139293e-05
6,515	Revisiting Pipelined Parallelism in Multi-Join Query Processing	2005	VLDB	5.8550491e-05
9,834	EinDecomp: Decomposition of Declaratively-Specified Machine Learning and Numerical Computations for Parallel Execution	2025	VLDB	5.2112879e-05
11,207	Pasta: A Cost-Based Optimizer for Generating Pipelining Schedules for Dataflow DAGs	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 7 of 7 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
434	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018531826
830	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013761367
2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.1594086e-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
3,508	Multi-Join Optimization for Symmetric Multiprocessors	1993	VLDB	7.3566888e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	2,337	Multi-dimensional Resource Scheduling for Parallel Queries	1996	SIGMOD
3	9,446	Parallelizing Query Optimization on Shared-Nothing Architectures	2016	VLDB
4	3,726	Parallelizing Query Optimization	2008	VLDB
5	3,046	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB
6	822	Pipelining in Multi-Query Optimization	2001	PODS
7	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB
8	434	Query Optimization for Parallel Execution	1992	SIGMOD
9	5,451	Coloring Away Communication in Parallel Query Optimization	1995	VLDB
10	2,068	Scheduling Problems in Parallel Query Optimization	1995	PODS