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: h0d1ce666b15e0025
Venue: SIGMOD
Year: 2023
Pagerank: 5.4260253e-05
Overall Rank: 7,923 | 46.74%
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
11,067	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	4.9793485e-05
11,542	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	4.9793485e-05
11,545	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.9793485e-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.00081992507
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005158963
76	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00036898845
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023143736
361	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00020006406
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018491327
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
922	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00013068048
969	Memory-Efficient Hash Joins	2015	VLDB	0.0001278184
1,254	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011330673
1,266	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011269175
1,481	Skew in Parallel Query Processing	2014	PODS	0.00010539119
1,670	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9318041e-05
2,267	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.7222779e-05
2,284	Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects	2020	SIGMOD	8.6954168e-05
2,818	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	7.9739791e-05
3,073	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6777283e-05
3,479	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2695068e-05
6,023	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.9126153e-05
7,259	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5716049e-05
7,926	Design Trade-offs for a Robust Dynamic Hybrid Hash Join	2022	VLDB	5.425615e-05
10,243	The Need for a New I/O Model	2021	CIDR	5.0525742e-05

Semantically Similar Papers

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