Skew Handling Techniques in Sort-Merge Join

Summary: Analyzes skew in sort-merge join and introduces refinements to mitigate its performance penalties, filling a gap left by hash-based skew handling. Near-zero overhead in non-skew cases and band-join gains; these refinements can replace standard sort-merge. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 3348
Venue: SIGMOD
Year: 2002
Pagerank: 5.1499439e-05
Overall Rank: 6,212 | 56.83%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,128	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	6.4214449e-05
5,523	On Producing Join Results Early	2003	PODS	5.4648346e-05
5,541	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4501856e-05
7,842	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	4.6336361e-05
11,535	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	4.1905499e-05

Outgoing Citations (Sorted by Pagerank)

Showing 9 of 9 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
1	Access Path Selection in a Relational Database Management System	1979	SIGMOD	0.0040465394
151	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00041010211
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035591171
392	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024546229
548	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00020369531
549	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00020348047
852	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00015896035
1,355	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00012417228
2,328	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	9.024235e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
403	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024176677
350	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.00026368305
2,599	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.4655075e-05
538	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020632609
5,961	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	5.2510172e-05
5,576	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	5.4251727e-05
5,523	On Producing Join Results Early	2003	PODS	5.4648346e-05
1,355	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00012417228
852	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00015896035
548	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00020369531