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.4055234e-05
Overall Rank: 7,942 | 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
11,137	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	4.9605343e-05
11,597	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	4.9605343e-05
11,600	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.9605343e-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.00081781676
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061463175
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.0005146739
77	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00036821827
250	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023080446
360	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00019959166
423	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018450254
491	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017383221
836	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013534835
855	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.0001340982
923	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00013034457
965	Memory-Efficient Hash Joins	2015	VLDB	0.00012778081
1,259	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011296701
1,269	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011236561
1,483	Skew in Parallel Query Processing	2014	PODS	0.00010500209
1,675	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.8993233e-05
2,282	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.6925412e-05
2,294	Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects	2020	SIGMOD	8.67775e-05
2,827	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	7.9486247e-05
3,081	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6515625e-05
3,489	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2421958e-05
6,036	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.8905221e-05
7,284	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5505534e-05
7,939	Design Trade-offs for a Robust Dynamic Hybrid Hash Join	2022	VLDB	5.4058938e-05
10,279	The Need for a New I/O Model	2021	CIDR	5.0334833e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,093	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB
2	965	Memory-Efficient Hash Joins	2015	VLDB
3	5,897	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD
4	9,153	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,808	An Adaptive Hash Join Algorithm for Multiuser Environments	1990	VLDB
7	7,939	Design Trade-offs for a Robust Dynamic Hybrid Hash Join	2022	VLDB
8	1,603	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB
9	855	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