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.00013534835
Overall Rank: 836 | 94.40%
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
474	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.00017638418
491	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017383221
1,360	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010893993
1,483	Skew in Parallel Query Processing	2014	PODS	0.00010500209
1,549	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010257684
1,633	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010002415
1,675	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.8993233e-05
2,911	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	7.8616647e-05
3,616	DFI: The Data Flow Interface for High-Speed Networks	2021	SIGMOD	7.1381983e-05
3,954	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.8871795e-05
3,977	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8707656e-05
4,332	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB	6.6448006e-05
4,491	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.561674e-05
4,864	Analysis of Dynamic Load Balancing Strategies for Parallel Shared Nothing Database Systems	1993	VLDB	6.3625965e-05
5,236	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2037372e-05
5,562	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.0663747e-05
5,680	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.0233693e-05
5,965	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	5.9144433e-05
6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.8905221e-05
6,743	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6766099e-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
9,341	SpongeFiles: Mitigating Data Skew in MapReduce Using Distributed Memory	2014	SIGMOD	5.1779529e-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.00081781676
194	Data Placement In Bubba	1988	SIGMOD	0.00025627096
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.00023099455
960	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.00012825107
3,072	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	7.6662888e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	1,296	From Theory to Practice: Efficient Join Query Evaluation in a Parallel Database System	2015	SIGMOD
2	3,954	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD
3	1,483	Skew in Parallel Query Processing	2014	PODS
4	5,680	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD
5	1,633	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
6	5,562	Efficient outer join data skew handling in parallel DBMS	2009	VLDB
7	1,675	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD
8	6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD
9	1,259	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
10	491	Practical Skew Handling in Parallel Joins	1992	VLDB