Handling Data Skew in Parallel Joins in Shared-Nothing Systems

Summary: Introduces PRPD (Partial Redistribution & Partial Duplication) to mitigate data skew in parallel joins on shared-nothing DBMS. Demonstrates significant speedups and higher throughput under skew by reducing hot-spotting and balancing workload in high-concurrency data warehouses. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: h6210290028e08004
Venue: SIGMOD
Year: 2008
Pagerank: 9.9318041e-05
Overall Rank: 1,670 | 88.78%
DOI: 10.1145/1376616.1376720

Incoming Non-self Citations Over Time

Authors

1. Yu Xu (Teradata)
2. Pekka Kostamaa (Teradata)
3. Xin Zhou (Teradata)
4. Liang Chen (University of California San Diego)

BibTeX Citation

@inproceedings{xu_sigmod08,
        title = {{Handling Data Skew in Parallel Joins in Shared-Nothing Systems}},
        author = {Xu, Yu and Kostamaa, Pekka and Zhou, Xin and Chen, Liang},
        series = {{SIGMOD} '08},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/1376616.1376720},
        url = {https://dl.acm.org/doi/10.1145/1376616.1376720},
        year = {2008}
}

Incoming Citations (Sorted by Pagerank)

Showing 18 of 18 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
977	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012731794
1,028	High-Speed Query Processing over High-Speed Networks	2016	VLDB	0.00012422084
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
2,530	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.3391175e-05
3,636	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.1471007e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
5,348	Adaptive and Robust Query Execution for Lakehouses at Scale	2024	VLDB	6.1690434e-05
5,542	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.0891064e-05
6,721	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6981399e-05
6,858	SquirrelJoin: Network-Aware Distributed Join Processing with Lazy Partitioning	2017	VLDB	5.6631651e-05
7,259	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5716049e-05
7,923	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4260253e-05
7,967	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.415894e-05
9,215	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.2056826e-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
11,865	Scaling Equi-Joins	2022	SIGMOD	4.9793485e-05
12,031	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	4.9793485e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013583955
1,212	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00011513842
1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011330673
3,943	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.9122604e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
2	8,185	Progressive Optimization in a Shared-Nothing Parallel Database	2007	SIGMOD
3	1,212	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB
4	1,481	Skew in Parallel Query Processing	2014	PODS
5	5,542	Efficient outer join data skew handling in parallel DBMS	2009	VLDB
6	472	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD
7	3,943	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD
8	833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB
9	489	Practical Skew Handling in Parallel Joins	1992	VLDB
10	1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB