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: 4114
Venue: SIGMOD
Year: 2008
Pagerank: 0.00010096933
Overall Rank: 1,657 | 88.64%
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
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
954	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012997301
1,076	High-Speed Query Processing over High-Speed Networks	2016	VLDB	0.00012270109
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
2,664	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.2816537e-05
3,578	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.2899943e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
5,411	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.2273741e-05
5,983	Adaptive and Robust Query Execution for Lakehouses at Scale	2024	VLDB	6.0206841e-05
6,596	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.828647e-05
6,762	SquirrelJoin: Network-Aware Distributed Join Processing with Lazy Partitioning	2017	VLDB	5.7814194e-05
7,111	Submodularity of Distributed Join Computation	2018	SIGMOD	5.69924e-05
7,760	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.5505651e-05
7,822	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.5371287e-05
9,100	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.3250075e-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
11,556	Scaling Equi-Joins	2022	SIGMOD	5.093636e-05
11,728	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	5.093636e-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
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
811	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013859761
1,188	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.00011756444
1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011548179
3,863	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	7.0649349e-05

Semantically Similar Papers

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