NOCAP: Near-Optimal Correlation-Aware Partitioning Joins

Summary: NOCAP offers correlation-aware PK-FK partitioning, exploiting skew for near-optimal partitioning under a tunable memory budget. A cost-based analysis yields optimal/approximate partitions; it beats Grace Hash Join up to 4x and, with tight memory, HHJ by up to 10%. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6816
Venue: SIGMOD
Year: 2023
Pagerank: 5.5505651e-05
Overall Rank: 7,760 | 46.77%
DOI: 10.1145/3626739

Incoming Non-self Citations Over Time

Authors

1. Zichen Zhu (Boston University)
2. Xiao Hu (University of Waterloo)
3. Manos Athanassoulis (Boston University)

BibTeX Citation

@inproceedings{zhu_sigmod23,
        title = {{NOCAP: Near-Optimal Correlation-Aware Partitioning Joins}},
        author = {Zhu, Zichen and Hu, Xiao and Athanassoulis, Manos},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3626739},
        url = {https://dl.acm.org/doi/10.1145/3626739},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 3 of 3 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
10,621	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	5.093636e-05
11,200	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	5.093636e-05
11,204	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 25 of 25 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.00083340894
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
29	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00052093615
74	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00037330605
252	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023242719
360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020182846
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018725853
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
959	Memory-Efficient Hash Joins	2015	VLDB	0.00012953588
1,015	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00012647763
1,236	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011548179
1,265	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011415709
1,448	Skew in Parallel Query Processing	2014	PODS	0.00010758872
1,657	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	0.00010096933
2,230	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.9026958e-05
2,566	Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects	2020	SIGMOD	8.4116562e-05
2,962	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	7.9170451e-05
3,137	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.7204167e-05
3,577	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2930211e-05
5,897	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	6.0472244e-05
7,111	Submodularity of Distributed Join Computation	2018	SIGMOD	5.69924e-05
7,800	Design Trade-offs for a Robust Dynamic Hybrid Hash Join	2022	VLDB	5.5420279e-05
10,048	The Need for a New I/O Model	2021	CIDR	5.1685424e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	8,904	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB
2	959	Memory-Efficient Hash Joins	2015	VLDB
3	5,812	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD
4	8,965	Sharing-Aware Horizontal Partitioning for Exploiting Correlations During Query Processing	2010	VLDB
5	242	A Performance Evaluation of Four Parallel Join Algorithms in a Shared-Nothing Multiprocessor Environment	1989	SIGMOD
6	1,779	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB
7	7,800	Design Trade-offs for a Robust Dynamic Hybrid Hash Join	2022	VLDB
8	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
9	844	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB
10	360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD