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.00013577649
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
473	Skew-Aware Automatic Database Partitioning in Shared-Nothing, Parallel OLTP Systems	2012	SIGMOD	0.00017684278
490	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017433989
1,351	SkewTune: Mitigating Skew in MapReduce Applications	2012	SIGMOD	0.00010929229
1,482	Skew in Parallel Query Processing	2014	PODS	0.00010534147
1,547	Building a Scalable Geo-Spatial DBMS: Technology, Implementation, and Evaluation	1997	SIGMOD	0.00010289422
1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD	0.00010033698
1,671	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9271979e-05
2,897	Dynamic Load Balancing in Hierarchical Parallel Database Systems	1996	VLDB	7.8817062e-05
3,609	DFI: The Data Flow Interface for High-Speed Networks	2021	SIGMOD	7.1617145e-05
3,944	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD	6.9090042e-05
3,969	Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing	1996	VLDB	6.8874168e-05
4,316	Dynamic Multi-Resource Load Balancing in Parallel Database Systems	1995	VLDB	6.6659792e-05
4,469	Distributed File Organization with Scalable Cost/Performance	1994	SIGMOD	6.5834186e-05
4,843	Analysis of Dynamic Load Balancing Strategies for Parallel Shared Nothing Database Systems	1993	VLDB	6.3824897e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.222614e-05
5,544	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	6.0862382e-05
5,668	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	6.0433507e-05
5,950	DEX: Scalable Range Indexing on Disaggregated Memory	2024	VLDB	5.934065e-05
6,023	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.9098342e-05
6,725	Near-Optimal Distributed Band-Joins through Recursive Partitioning	2020	SIGMOD	5.6954425e-05
7,266	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5689674e-05
7,927	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4234567e-05
9,316	SpongeFiles: Mitigating Data Skew in MapReduce Using Distributed Memory	2014	SIGMOD	5.1951189e-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.00081971778
192	Data Placement In Bubba	1988	SIGMOD	0.00025689465
249	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD	0.0002316492
955	Selectivity Estimation and Query Optimization in Large Databases with Highly Skewed Distributions of Column Values	1988	VLDB	0.0001286095
3,062	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	7.6910609e-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,944	Using Shared Virtual Memory for Parallel Join Processing	1993	SIGMOD
3	1,482	Skew in Parallel Query Processing	2014	PODS
4	5,668	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD
5	1,628	Adaptive Parallel Aggregation Algorithms	1995	SIGMOD
6	5,544	Efficient outer join data skew handling in parallel DBMS	2009	VLDB
7	1,671	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,256	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
10	490	Practical Skew Handling in Parallel Joins	1992	VLDB