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: 3409
Venue: SIGMOD
Year: 2002
Pagerank: 6.0472244e-05
Overall Rank: 5,897 | 59.55%
DOI: 10.1145/564691.564711

Incoming Non-self Citations Over Time

Authors

1. Wei Li (Oracle)
2. Dengfeng Gao (University of Arizona)
3. Richard T. Snodgrass (University of Arizona)

BibTeX Citation

@inproceedings{li_sigmod02,
        title = {{Skew Handling Techniques in Sort-Merge Join}},
        author = {Li, Wei and Gao, Dengfeng and Snodgrass, Richard T.},
        series = {{SIGMOD} '02},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/564691.564711},
        url = {https://dl.acm.org/doi/10.1145/564691.564711},
        year = {2002}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,578	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.2899943e-05
5,122	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.3573169e-05
5,467	On Producing Join Results Early	2003	PODS	6.2074577e-05
7,760	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.5505651e-05
11,728	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	5.093636e-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.0024089429
163	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027839792
210	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024797689
341	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020704572
481	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017780716
811	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013859761
844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013664056
1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011548179
2,230	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.9026958e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB
2	209	Sort vs. Hash Revisited: Fast Join Implementation on Modern Multi-Core CPUs	2009	VLDB
3	3,011	Design and Evaluation of Parallel Pipelined Join Algorithms	1987	SIGMOD
4	360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD
5	5,534	Skew-Aware Join Optimization for Array Databases	2015	SIGMOD
6	5,411	Efficient outer join data skew handling in parallel DBMS	2009	VLDB
7	5,467	On Producing Join Results Early	2003	PODS
8	1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB
9	811	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB
10	481	Practical Skew Handling in Parallel Joins	1992	VLDB