Worst Case Optimal Joins: Graph-Join Correspondence

Summary

WCOJ - Graph-Join correspondence 09 Dec 2025 An introduction and motivation for Worst Case Optimal Joins Consider the TPC-H query 5 (Local Supplier Volume) and just focus on the join part of the query. TPC-H is standardised benchmark with very common business queries on a synthetic dataset. SELECT n_name, SUM(l_extendedprice * (1 - l_discount)) AS revenue FROM customer JOIN orders ON c_custkey = o_custkey JOIN lineitem ON l_orderkey = o_orderkey JOIN supplier ON l_suppkey = s_suppkey AND c_nationkey = s_nationkey JOIN nation ON s_nationkey = n_nationkey JOIN region ON n_regionkey = r_regionkey WHERE r_name = 'ASIA' AND o_orderdate >= DATE '1994-01-01' AND o_orderdate < DATE '1994-01-01' + INTERVAL '1' YEAR GROUP BY n_name ORDER BY revenue DESC; If we create a graph for this query where nodes represent join variables (in SQL these are just join conditions as the notion of a join variable does not really exist in SQL) and where edges represent relations (tables), we get the following diagram. Notice that this is a hypergraph as relations might participate in more than 2 joins. There is a direct correspondence between graphs and joins. There are even whole database vendors who have made their data model graphs. Albeit in most cases the underlying model is for standard graphs (binary edges). You can of course also go the other way around and model graphs in the relational model. CREATE TABLE g(f INT, t INT); Finding all triangles in a graph can then be modelled as SELECT g1.f AS a, g1.t AS b, g2.t AS c FROM g AS g1, g AS g2, g AS g3 WHERE g1.t = g2.f AND g2.t = g3.t AND g1.f = g3.f; The main difference between this query and former one is that we are doing self joins. The similarity is that we are looking for a certain kind of pattern in our data. A triangle in the latter case and a more involved pattern in the TPC-H case. Writing the triangle in terms of three different relations you get \[Q(A,B,C) = R(A,B) \bowtie S(B,C) \bowtie T(C,A)\] and the corresponding hypergra...