Multi-Join Optimization for Symmetric Multiprocessors

Summary: Memory- and pipeline-aware cost models for multi-join optimization on symmetric multiprocessors; analyzes DP and greedy methods analytically. Experiments show DP bests; heuristics are near-optimal; bushy trees outperform restricted shapes. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8149
Venue: VLDB
Year: 1993
Pagerank: 7.1134801e-05
Overall Rank: 3,422 | 76.20%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,825	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	0.00010401739
2,417	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.8604775e-05
5,392	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	5.5329138e-05
5,676	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	5.376109e-05
6,543	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.0208799e-05
12,745	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	4.1945683e-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.0040449103
9	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.0014279444
50	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00067394827
78	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00056413752
113	Encapsulation of Parallelism in the Volcano Query Processing System	1990	SIGMOD	0.00046764513
423	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.00023669348
438	Query Optimization for Parallel Execution	1992	SIGMOD	0.00023199245
807	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00016434207
813	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.0001639584
1,063	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00014362773
1,847	Using Segmented Right-Deep Trees for the Execution of Pipelined Hash Joins	1992	VLDB	0.00010333796
2,619	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.4431973e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,122	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS	4.8252188e-05
6,056	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD	5.2321475e-05
1,063	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB	0.00014362773
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
1,672	Scheduling Problems in Parallel Query Optimization	1995	PODS	0.00010949448
3,260	On Optimal Processor Allocation To Support Pipelined Hash Joins	1993	SIGMOD	7.3122611e-05
3,124	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB	7.5201555e-05
4,261	Parallelizing Query Optimization	2008	VLDB	6.31244e-05
7,839	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB	4.637294e-05
2,044	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.6953608e-05