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: hfacb4695cfa37adf
Venue: VLDB
Year: 1991
Pagerank: 0.00013583955
Overall Rank: 833 | 94.41%
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
472	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.00017692264
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
1,351	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010934347
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
1,546	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010294163
1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010037937
1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9318041e-05
2,897	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	7.8854343e-05
3,608	DFI: The Data Flow Interface for High-Speed Networks	2021	SIGMOD	7.1650501e-05
3,943	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.9122604e-05
3,967	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8905715e-05
4,315	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB	6.6691188e-05
4,467	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.5865346e-05
4,841	Analysis of Dynamic Load Balancing Strategies for Parallel Shared Nothing Database Systems	1993	VLDB	6.3854243e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
5,542	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.0891064e-05
5,666	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.0462129e-05
5,949	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	5.9368754e-05
6,023	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.9126153e-05
6,721	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6981399e-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
9,307	SpongeFiles: Mitigating Data Skew in MapReduce Using Distributed Memory	2014	SIGMOD	5.197526e-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.00081992507
191	Data Placement In Bubba	1988	SIGMOD	0.00025700375
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023175253
956	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00012865801
3,059	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	7.694629e-05

Semantically Similar Papers

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