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.4234567e-05
Overall Rank: 7,927 | 46.73%
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,076	Scalable Grid-based Computation of Kendall's tau Correlation	2026	VLDB	4.9769913e-05
11,548	High-Performance Query Processing with NVMe Arrays: Spilling without Killing Performance	2024	SIGMOD	4.9769913e-05
11,551	SPID-Join: A Skew-resistant Processing-in-DIMM Join Algorithm Exploiting the Bank- and Rank-level Parallelisms of DIMMs	2024	SIGMOD	4.9769913e-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.00081971778
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061067652
27	Database Architecture Optimized for the New Bottleneck: Memory Access	1999	VLDB	0.00051576613
76	Cache Conscious Algorithms for Relational Query Processing	1994	VLDB	0.00036891569
251	Multi-Core, Main-Memory Joins: Sort vs. Hash Revisited	2014	VLDB	0.00023136934
362	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD	0.00019999596
425	Massively Parallel Sort-Merge Joins in Main Memory Multi-Core Database Systems	2012	VLDB	0.00018485358
490	Practical Skew Handling in Parallel Joins	1992	VLDB	0.00017433989
833	A Taxonomy and Performance Model of Data Skew Effects in Parallel Joins	1991	VLDB	0.00013577649
853	Hash-Partitioned Join Method Using Dynamic Destaging Strategy	1988	VLDB	0.00013439366
921	AsterixDB: A Scalable, Open Source BDMS	2014	VLDB	0.00013064043
963	Memory-Efficient Hash Joins	2015	VLDB	0.00012815832
1,256	Handling Data Skew in Multiprocessor Database Computers Using Partition Tuning	1991	VLDB	0.00011325515
1,267	An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory	2016	SIGMOD	0.00011265987
1,482	Skew in Parallel Query Processing	2014	PODS	0.00010534147
1,671	Handling Data Skew in Parallel Joins in Shared-Nothing Systems	2008	SIGMOD	9.9271979e-05
2,268	The Effect of Bucket Size Tuning in the Dynamic Hybrid GRACE Hash Join Method	1989	VLDB	8.7182371e-05
2,287	Pump Up the Volume: Processing Large Data on GPUs with Fast Interconnects	2020	SIGMOD	8.691301e-05
2,818	To Partition, or Not to Partition, That is the Join Question in a Real System	2021	SIGMOD	7.9703078e-05
3,075	Pushing Data-Induced Predicates Through Joins in Big-Data Clusters	2020	VLDB	7.6742518e-05
3,480	Cosine: A Cloud-Cost Optimized Self-Designing Key-Value Storage Engine	2022	VLDB	7.2661848e-05
6,023	Skew Handling Techniques in Sort-Merge Join	2002	SIGMOD	5.9098342e-05
7,266	Submodularity of Distributed Join Computation	2018	SIGMOD	5.5689674e-05
7,932	Design Trade-offs for a Robust Dynamic Hybrid Hash Join	2022	VLDB	5.4230466e-05
10,249	The Need for a New I/O Model	2021	CIDR	5.0501823e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	9,073	A Design Space Exploration and Evaluation for Main-Memory Hash Joins in Storage Class Memory	2023	VLDB
2	963	Memory-Efficient Hash Joins	2015	VLDB
3	5,881	MCJoin: A Memory-Constrained Join for Column-Store Main-Memory Databases.	2012	SIGMOD
4	9,133	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,932	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	362	Design and Evaluation of Main Memory Hash Join Algorithms for Multi-core CPUs	2011	SIGMOD