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: 8135
Venue: VLDB
Year: 1990
Pagerank: 0.00011756444
Overall Rank: 1,188 | 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
356	Efficient Parallel Set-Similarity Joins Using MapReduce	2010	SIGMOD	0.00020303289
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011548179
1,657	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	0.00010096933
2,104	Optimization of Multi-Way Join Queries for Parallel Execution	1991	VLDB	9.1594086e-05
2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.0594267e-05
3,578	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.2899943e-05
3,863	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	7.0649349e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	7.04191e-05
4,668	Performance Analysis of a Load Balancing Hash-Join Algorithm for a Shared Memory Multiprocessor	1991	VLDB	6.5761032e-05
5,411	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.2273741e-05
5,534	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.1831004e-05
6,596	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.828647e-05
7,111	Submodularity of Distributed Join Computation	2018	SIGMOD	5.69924e-05
9,082	An Application-Specific Instruction Set for Accelerating Set-Oriented Database Primitives	2014	SIGMOD	5.3251649e-05
11,204	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	5.093636e-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.0024089429
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
52	GAMMA - A High Performance Dataflow Database Machine	1986	VLDB	0.00041107291
152	Multiprocessor Hash-Based Join Algorithms	1985	VLDB	0.00029038365
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013664056
951	A Benchmark of NonStop SQL on the Debit Credit Transaction	1988	SIGMOD	0.00013021781
2,230	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.9026958e-05

Semantically Similar Papers

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