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.8993233e-05
Overall Rank: 1,675 | 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
397	Worst-case Optimal Join Algorithms	2012	PODS	0.0001911958
982	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00012687016
1,025	High-Speed Query Processing over High-Speed Networks	2016	VLDB	0.00012396134
1,483	Skew in Parallel Query Processing	2014	PODS	0.00010500209
2,527	Adaptive and Big Data Scale Parallel Execution in Oracle	2013	VLDB	8.3243069e-05
3,638	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.1248634e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
5,367	Adaptive and Robust Query Execution for Lakehouses at Scale	2024	VLDB	6.1462017e-05
5,562	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.0663747e-05
6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6766099e-05
6,880	SquirrelJoin: Network-Aware Distributed Join Processing with Lazy Partitioning	2017	VLDB	5.6423904e-05
7,284	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5505534e-05
7,942	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4055234e-05
7,987	Resource Bricolage for Parallel Database Systems	2015	VLDB	5.3957073e-05
9,249	Chasing Similarity: Distribution-aware Aggregation Scheduling	2019	VLDB	5.1860134e-05
11,600	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.9605343e-05
11,915	Scaling Equi-Joins	2022	SIGMOD	4.9605343e-05
12,081	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	4.9605343e-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
491	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017383221
836	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013534835
1,215	Bucket Spreading Parallel Hash: A New, Robust, Parallel Hash Join Method for Data Skew in the Super Database Computer (SDC)	1990	VLDB	0.0001147464
1,259	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011296701
3,954	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.8871795e-05

Semantically Similar Papers

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