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: 3347
Venue: SIGMOD
Year: 2002
Pagerank: 5.1546943e-05
Overall Rank: 6,214 | 56.78%
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,132	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	6.4241067e-05
5,511	On Producing Join Results Early	2003	PODS	5.4699346e-05
5,532	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	5.4548897e-05
7,836	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	4.6380835e-05
11,531	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	4.1945683e-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.0040449103
152	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00040963225
193	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00035610321
391	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00024564567
550	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00020359891
588	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00019604754
861	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00015848554
1,365	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00012368421
2,326	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	9.0282969e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
404	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00024143076
351	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB	0.0002636504
2,640	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD	8.3924401e-05
540	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.0002063443
5,960	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD	5.2559595e-05
5,568	Efficient outer join data skew handling in parallel DBMS	2009	VLDB	5.4301489e-05
5,511	On Producing Join Results Early	2003	PODS	5.4699346e-05
1,365	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00012368421
861	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00015848554
588	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00019604754