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: hcd3ae88955943fbe
Venue: SIGMOD
Year: 2002
Pagerank: 5.9126153e-05
Overall Rank: 6,023 | 59.51%
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,636	Advanced Join Strategies for Large-Scale Distributed Computation	2014	VLDB	7.1471007e-05
5,213	A Padded Encoding Scheme to Accelerate Scans by Leveraging Skew	2015	SIGMOD	6.2250048e-05
5,608	On Producing Join Results Early	2003	PODS	6.0692914e-05
7,923	NOCAP: Near-Optimal Correlation-Aware Partitioning Joins	2023	SIGMOD	5.4260253e-05
12,031	Fangorn: Adaptive Execution Framework for Heterogeneous Workloads on Shared Clusters	2021	VLDB	4.9793485e-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.0023947656
166	On Supporting Containment Queries in Relational Database Management Systems	2001	SIGMOD	0.00027254612
220	An Evaluation of Non-Equijoin Algorithms	1991	VLDB	0.00024344086
351	Indexing and Querying XML Data for Regular Path Expressions	2001	VLDB	0.00020251513
489	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017441895
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013583955
853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013444911
1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011330673
2,267	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.7222779e-05

Semantically Similar Papers

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