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: h125f815880c6b16b
Venue: SIGMOD
Year: 2023
Pagerank: 6.3149028e-05
Overall Rank: 5,010 | 66.32%
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 12 of 12 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,153	Robust Join Processing with Diamond Hardened Joins	2024	VLDB	7.5883271e-05
4,369	Predicate Transfer: Efficient Pre-Filtering on Multi-Join Queries	2024	CIDR	6.6315141e-05
4,950	Debunking the Myth of Join Ordering: Toward Robust SQL Analytics	2025	SIGMOD	6.3421691e-05
9,360	Extending SQL to Return a Subdatabase	2025	SIGMOD	5.1868213e-05
9,361	Subgraph Matching: A New Decomposition Based Approach	2025	VLDB	5.1868213e-05
9,950	HoneyComb: A Parallel Worst-Case Optimal Join on Multicores	2025	SIGMOD	5.1038322e-05
10,768	One Join Order Does Not Fit All: Reducing Intermediate Results with Per-Split Query Plans	2026	VLDB	4.9793485e-05
10,802	BaCon: Efficient Batch Processing of Counting Queries	2026	VLDB	4.9793485e-05
10,854	Worst-Case Optimal BGPs on Temporal Graphs	2026	VLDB	4.9793485e-05
10,884	FlowLog: Efficient and Extensible Datalog via Incrementality	2026	VLDB	4.9793485e-05
11,203	cuMatch: A GPU-based Memory-Efficient Worst-case Optimal Join Processing Method for Subgraph Queries with Complex Patterns	2025	SIGMOD	4.9793485e-05
11,546	Towards a Converged Relational-Graph Optimization Framework	2024	SIGMOD	4.9793485e-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.0023947656
15	How Good Are Query Optimizers, Really?	2016	VLDB	0.00061066921
21	Efficiently Compiling Efficient Query Plans for Modern Hardware	2011	VLDB	0.00056855599
53	Eddies: Continuously Adaptive Query Processing	2000	SIGMOD	0.00040860054
208	EmptyHeaded: A Relational Engine for Graph Processing	2016	SIGMOD	0.00024884544
253	Database Cracking	2007	CIDR	0.00023042111
315	Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems	2018	PODS	0.00021246
402	Worst-case Optimal Join Algorithms	2012	PODS	0.00019104625
605	Everything You Always Wanted to Know About Compiled and Vectorized Queries But Were Afraid to Ask	2018	VLDB	0.00015647561
712	Optimizing Subgraph Queries by Combining Binary and Worst-Case Optimal Joins	2019	VLDB	0.00014578373
1,091	What do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog have to do with one another?	2017	PODS	0.00012074152
1,596	Adopting Worst-Case Optimal Joins in Relational Database Systems	2020	VLDB	0.00010127607
1,752	Kuzu* Graph Database Management System	2023	CIDR	9.7289339e-05
1,802	Hash joins and hash teams in Microsoft SQL Server	1998	VLDB	9.6081518e-05
1,825	Data Management for Data Science: Towards Embedded Analytics	2020	CIDR	9.5603293e-05
3,606	Updating a Cracked Database	2007	SIGMOD	7.1686756e-05
5,530	Generalized Hash Teams for Join and Group-by	1999	VLDB	6.0935245e-05

Semantically Similar Papers

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