A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins

Summary: Taxonomy of data-skew effects in parallel joins and a new performance model for skew-aware evaluation. Distinguishes skew causes and characteristics to enable fair cross-algorithm comparisons, and uses the model to contrast two parallel join approaches. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 8234
Venue: VLDB
Year: 1991
Pagerank: 0.00013859761
Overall Rank: 811 | 94.44%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Christopher B. Walton (University of Texas)
2. Alfred G. Dale (University of Texas)
3. Roy M. Jenevein (University of Texas)

BibTeX Citation

@article{walton_vldb91,
        title = {{A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins}},
        author = {Walton, Christopher B. and Dale, Alfred G. and Jenevein, Roy M.},
        journal = {PVLDB},
        series = {{VLDB} '91},
        year = {1991}
}

Incoming Citations (Sorted by Pagerank)

Showing 23 of 23 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
471	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.0001793564
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
1,319	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00011175005
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,517	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010520118
1,596	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010247091
1,657	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	0.00010096933
2,846	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	8.0594267e-05
3,863	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	7.0649349e-05
3,868	DFI: The Data Flow Interface for High-Speed Networks	2021	SIGMOD	7.0614899e-05
3,893	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	7.04191e-05
4,241	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB	6.8094303e-05
4,374	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.7370696e-05
4,792	Analysis of Dynamic Load Balancing Strategies for Parallel Shared Nothing Database Systems	1993	VLDB	6.5059372e-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,534	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.1831004e-05
5,852	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	6.0658952e-05
5,897	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	6.0472244e-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
7,760	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.5505651e-05
9,137	SpongeFiles: Mitigating Data Skew in MapReduce Using Distributed Memory	2014	SIGMOD	5.3162511e-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
7	Implementation Techniques For Main Memory Database Systems	1984	SIGMOD	0.00083340894
188	Data Placement In Bubba	1988	SIGMOD	0.00026126036
242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023604323
934	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00013108714
3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	7.8532781e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,320	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	3,863	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD
3	1,448	Skew in Parallel Query Processing	2014	PODS
4	5,534	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD
5	1,596	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
6	5,411	Efficient outer join data skew handling in parallel DBMS	2009	VLDB
7	1,657	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD
8	5,897	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD
9	1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
10	481	Practical Skew Handling in Parallel Joins	1992	VLDB