Free Join: Unifying Worst-Case Optimal and Traditional Joins

Summary: Free Join unifies WCOJ and traditional binary joins, using WCOJ for cyclic parts and binary plans for acyclic parts. A unifying plan, a hash+trie data structure, and Rust optimizations let the system match or beat both baselines on benchmarks. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 6715
Venue: SIGMOD
Year: 2023
Pagerank: 6.0910397e-05
Overall Rank: 5,781 | 60.34%
DOI: 10.1145/3589295

Incoming Non-self Citations Over Time

Authors

1. Yisu Remy Wang (University of Washington)
2. Max Willsey (University of Washington)
3. Dan Suciu (University of Washington)

BibTeX Citation

@inproceedings{wang_sigmod23,
        title = {{Free Join: Unifying Worst-Case Optimal and Traditional Joins}},
        author = {Wang, Yisu Remy and Willsey, Max and Suciu, Dan},
        series = {{SIGMOD} '23},
        booktitle = {Proceedings of the {ACM} {SIGMOD} International Conference on Management of Data},
        publisher = {Association for Computing Machinery},
        doi = {10.1145/3589295},
        url = {https://dl.acm.org/doi/10.1145/3589295},
        year = {2023}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,622	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.2465862e-05
4,553	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6346951e-05
5,529	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.18591e-05
9,183	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.3058708e-05
9,693	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.2351259e-05
10,582	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	5.093636e-05
10,765	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.093636e-05
10,787	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	5.093636e-05
11,205	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 17 of 17 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.0024089429
18	How Good Are Query Optimizers, Really?	2016	VLDB	0.00059284255
23	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00054886415
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00041071971
211	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024797217
259	Database Cracking	2007	CIDR	0.00023119313
321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021283186
411	Worst-case Optimal Join Algorithms	2012	PODS	0.00018902089
649	Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask	2018	VLDB	0.00015320656
809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00013874588
1,109	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012142685
1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	9.875587e-05
1,809	Hash joins and hash teams in Microsoft SQL Server	1998	VLDB	9.7034998e-05
2,000	Data Management for Data Science: Towards Embedded Analytics	2020	CIDR	9.3336258e-05
2,126	Kuzu* Graph Database Management System	2023	CIDR	9.1329991e-05
3,558	Updating a Cracked Database	2007	SIGMOD	7.3101789e-05
5,443	Generalized Hash Teams for Join and Group-by	1999	VLDB	6.2177595e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,090	Let's Rethink Join Optimization in Distributed Systems	2015	CIDR
2	809	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB
3	4,401	Towards a Worst-Case I/O-Optimal Algorithm for Acyclic Joins	2016	PODS
4	1,857	Joins via Geometric Resolutions: Worst-case and Beyond	2015	PODS
5	411	Worst-case Optimal Join Algorithms	2012	PODS
6	3,622	Robust Join Processing with Diamond Hardened Joins	2024	VLDB
7	5,364	Fast Join Project Query Evaluation using Matrix Multiplication	2020	SIGMOD
8	3,617	Scalable Computation of Acyclic Joins (Extended Abstract)	2006	PODS
9	321	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS
10	1,740	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB