Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)

Summary: Introduces bucket spreading, a skew-robust parallel hash join for SDC: buckets are fragmented and distributed incrementally rather than statically assigned. Dynamic bucket collection balances PM load, while network hardware support preserves scalability under severe data skew. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: hf0b0a0256d127664
Venue: VLDB
Year: 1990
Pagerank: 0.00011513842
Overall Rank: 1,212 | 91.86%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Masaru Kitsuregawa (University of Tokyo)
2. Yasushi Ogawa (Ricoh Co., Ltd.)

BibTeX Citation

@article{kitsuregawa_vldb90,
        title = {{Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)}},
        author = {Kitsuregawa, Masaru and Ogawa, Yasushi},
        journal = {PVLDB},
        series = {{VLDB} '90},
        volume = {16},
        pages = {210--221},
        year = {1990}
}

Incoming Citations (Sorted by Pagerank)

Showing 16 of 16 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
360	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020009936
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011330673
1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9318041e-05
2,136	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	8.9789503e-05
2,897	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	7.8854343e-05
3,636	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.1471007e-05
3,943	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.9122604e-05
3,967	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8905715e-05
4,754	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB	6.432504e-05
5,542	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.0891064e-05
5,666	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.0462129e-05
6,721	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6981399e-05
7,259	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5716049e-05
9,201	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	5.2083769e-05
11,545	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 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.0023947656
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00081992507
54	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00040499302
156	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00028522117
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023175253
853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013444911
973	A Benchmark of NonStop SQL on the Debit Credit Transaction	1988	SIGMOD	0.00012757586
2,267	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.7222779e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	3,967	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB
2	4,710	On Parallel Execution Of Multiple Pipelined Hash Joins	1994	SIGMOD
3	1,481	Skew in Parallel Query Processing	2014	PODS
4	2,267	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB
5	361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
6	1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD
7	4,754	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB
8	489	Practical Skew Handling in Parallel Joins	1992	VLDB
9	853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
10	1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB