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: 8340
Venue: VLDB
Year: 1993
Pagerank: 7.3566888e-05
Overall Rank: 3,508 | 75.94%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Eugene J. Shekita (IBM)
2. Honesty C. Young (IBM)
3. Kian-Lee Tan (National University of Singapore)

BibTeX Citation

@article{shekita_vldb93,
        title = {{Multi-Join Optimization for Symmetric Multiprocessors}},
        author = {Shekita, Eugene J. and Young, Honesty C. and Tan, Kian-Lee},
        journal = {PVLDB},
        series = {{VLDB} '93},
        pages = {479--490},
        year = {1993}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,131	Optimization Algorithms for Exploiting the Parallelism-Communication Tradeoff in Pipelined Parallelism	1994	VLDB	9.1242116e-05
2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.0594267e-05
5,451	Coloring Away Communication in Parallel Query Optimization	1995	VLDB	6.2139293e-05
5,615	Efficient and Accurate Cost Models for Parallel Query Optimization	1996	PODS	6.1497352e-05
6,164	On the Complexity of Generating Optimal Plans with Cross Products (extended abstract)	1997	PODS	5.9532278e-05
12,938	TOPAZ: a Cost-Based, Rule-Driven, Multi-Phase Parallelizer	1998	VLDB	5.093636e-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.0024089429
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
98	Encapsulation of Parallelism in the Volcano Query Processing System	1990	SIGMOD	0.00034510605
133	A Case for Redundant Arrays of Inexpensive Disks (RAID)	1988	SIGMOD	0.00030370315
152	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00029038365
316	Measuring the Complexity of Join Enumeration in Query Optimization	1990	VLDB	0.0002141607
434	Query Optimization for Parallel Execution	1992	SIGMOD	0.00018531826
708	Left-Deep Vs. Bushy Trees: An Analysis Of Strategy Spaces And Its Implications For Query Optimization	1991	SIGMOD	0.00014727576
830	Exploiting Inter-Operation Parallelism in XPRS	1992	SIGMOD	0.00013761367
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,470	Hash-Based Join Algorithms for Multiprocessor Computers with Shared Memory	1990	VLDB	8.5330174e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	7,143	Parallel Algorithms for Sparse Matrix Multiplication and Join-Aggregate Queries	2020	PODS
2	5,399	Efficient Massively Parallel Join Optimization for Large Queries*	2022	SIGMOD
3	904	Tradeoffs in Processing Complex Join Queries via Hashing in Multiprocessor Database Machines	1990	VLDB
4	3,268	Efficient and Provable Multi-Query Optimization	2017	PODS
5	2,068	Scheduling Problems in Parallel Query Optimization	1995	PODS
6	3,250	On Optimal Processor Allocation To Support Pipelined Hash Joins	1993	SIGMOD
7	3,046	Parallel Query Scheduling and Optimization with Time- and Space-Shared Resources	1997	VLDB
8	3,726	Parallelizing Query Optimization	2008	VLDB
9	8,243	Effective Resource Utilization for Multiprocessor Join Execution	1989	VLDB
10	2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB