Source-linked AI summary
Skew Strikes Back: New Developments in the Theory of Join Algorithms
Hung Q. Ngo, Christopher Re, Atri Rudra
TL;DR
The survey examines worst-case-optimal join processing through the triangle query, where traditional pairwise evaluation can require Ω(N^2) time despite an O(N^3/2) output bound. It synthesizes algorithms that avoid skew and challenge one-join-at-a-time plans, while presenting unified explanations and proofs of their guarantees.
Problem
Traditional pairwise join evaluation can take Ω(N^2) time on triangle-query instances, although the tight triangle bound is O(N^3/2).
Method
The survey develops triangle-query intuition, relates skew-avoidance techniques to geometry, and presents simplified proofs and algorithms based on recent size bounds.
Results
Worst-case-optimal algorithms match AGM bounds, while some join-project plans are slower than the best possible runtime by a polynomial factor.
Takeaways & Limitations
Avoiding skew and evaluating suitable joins beyond one join at a time provides a theoretical route to worst-case-optimal join processing.
Takeaways & Limitations
For certain queries, every join-project plan requires at least Ω(N^(2/n^2)) time, whereas the described algorithms run in O(N^(1+1/(n−1))) time.
Abstract
from arXiv · showhide
Evaluating the relational join is one of the central algorithmic and most well-studied problems in database systems. A staggering number of variants have been considered including Block-Nested loop join, Hash-Join, Grace, Sort-merge for discussions of more modern issues). Commercial database engines use finely tuned join heuristics that take into account a wide variety of factors including the selectivity of various predicates, memory, IO, etc. In spite of this study of join queries, the textbook description of join processing is suboptimal. This survey describes recent results on join algorithms that have provable worst-case optimality runtime guarantees. We survey recent work and provide a simpler and unified description of these algorithms that we hope is useful for theory-minded readers, algorithm designers, and systems implementors.
1 Introduction
The survey explains why traditional pairwise join processing can be suboptimal and presents worst-case optimal algorithms that account for skew, query structure, and relation sizes. It unifies recent algorithms and connects their guarantees to geometric bounds.
- Motivation: Triangle queries have a tight maximum of O(N3/2) triangles, motivating algorithms that enumerate them in O(N3/2) time.Pairwise evaluation can require Ω(N2) time on some triangle-query instances.
- Contribution: Worst-case optimal join algorithms match non-trivial output-size bounds for join queries rather than relying only on pairwise evaluation.The survey reviews algorithms designed to meet these bounds.
- Motivation: Skew is identified as the source of suboptimality that these algorithms address through theoretically grounded techniques related to geometry.The survey frames skew as a longstanding database-optimization problem.
- Cardinality and structure: Commercial systems often decompose multiway joins into pairwise joins, but this can be polynomially slower than the best possible runtime.Structural query information is lost when joins are processed one at a time.
- Cardinality and structure: AGM bounds combine individual relation cardinalities with query structure and lead to fractional query number and fractional hypertree width.The survey states the hierarchy fhw ≤ ghw ≤ qw ≤ tw + 1.
- Survey scope: The survey gives a unified and simplified framework showing that two recent worst-case optimal join algorithms are special cases of one algorithm.It also highlights connections between join algorithms and geometry.
2 Much ado about the triangle
The triangle query exposes why pairwise join plans can create quadratic intermediates, while skew-aware algorithms achieve optimal worst-case runtimes by adapting how they enumerate candidates.
- Traditional join plans: Q△ is the simplest cyclic join and illustrates traditional processing, skew, and the survey’s new algorithmic ideas.The query is R(A,B) ⋈ S(B,C) ⋈ T(A,C), and graph triangles can be represented with this join.
- Traditional join plans: Any pairwise join plan can require Ω(N^2) time even when the triangle output has only O(N) tuples.The constructed instance has N = 2m + 1 tuples per relation, 3m + 1 output tuples, and pairwise joins of size m^2 + m.
- Skew: The quadratic intermediate is caused by a high-degree heavy value, an instance of skew that makes pairwise materialization wasteful.The algorithm classifies values by whether their intermediate contribution exceeds their output contribution.
- Algorithm 1: The Power of Two Choices: Algorithm 1 uses two strategies: intersect-and-probe for light values, and scanning candidate tuples in S for heavy values.The choice uses |S| as a proxy for the unknown output contribution and applies different enumeration methods to low- and high-skew values.
- Algorithm 1: The Power of Two Choices: On the counterexample, Algorithm 1 runs in O(N) time, which is optimal because the output itself has Ω(N) tuples.The heavy value costs O(m), while each of the m light values costs O(1), giving O(m) overall.
- Algorithm analysis: For equal-sized relations, the resulting worst-case runtime is O(N^3/2), matching the tight triangle bound.The survey generalizes this analysis beyond triangles and connects the two algorithms through a unified framework.
- Algorithm 2: Delaying the Computation: Algorithm 2 delays computation by progressively intersecting candidate sets, and it has the same worst-case runtime as Algorithm 1.Both algorithms share a recursive structure and are presented as special cases of a generic worst-case optimal join algorithm.
3 A User’s Guide to the AGM bound
The AGM framework bounds join output size using both relation cardinalities and query structure, then supports instance-sensitive covers and extensions to conjunctive queries.
- AGM Bound: AGM’s inequality bounds a natural join using a fractional edge cover of its hypergraph representation.Each relation is an edge over attributes, and the cover weights satisfy a coverage constraint for every attribute.
- Example Bounds: For the triangle, different valid covers produce different bounds, so the tight choice depends on relation sizes.The equal-size case favors the N^3/2 bound, while |R| = |T| = 1 and |S| = N makes the |R|·|T| bound tight.
- AGM Bound: The optimal instance-dependent cover minimizes a linear-program objective, yielding the fractional edge cover number ρ*(Q,D).The resulting bound is |Q| ≤ 2^ρ*(Q,D).
- Conjunctive Queries: Conjunctive queries extend natural joins with projections, repeated variables, and functional dependencies, requiring adaptations such as output-variable restriction and fictitious relations.Examples reduce repeated-variable queries to natural joins and use functional dependencies to transform queries while preserving output.
- Conjunctive Queries: The survey excludes general functional-dependency, composite-key, and treewidth-preserving results because they require different machinery.These topics are identified as beyond the survey’s scope.
4 Worst-case-optimal algorithms
The survey derives worst-case-optimal join algorithms from a query decomposition lemma and AGM bounds, unifying NPRR and Leapfrog Triejoin. These methods address skew and can outperform join-project plans by polynomial factors.
- 4.1 Query decomposition and generic join: The query decomposition lemma yields AGM inequality and a generic worst-case-optimal recursive join algorithm.The proof uses a query decomposition lemma followed by induction, and the resulting framework captures both NPRR and Leapfrog Triejoin.
- 4.1 Query decomposition and generic join: For the triangle query, the fractional edge cover x = (1/2, 1/2, 1/2) supplies the runtime bound used by Algorithm 1.The same choice of cover is used to connect the triangle algorithm to the general lemma.
- 4.2 Generic-Join: Algorithm 3 recursively projects partial tuples, forms residual queries, and combines their results to evaluate the original join.For each projected tuple t_I, it defines a residual query Q[t_I] and unions t_I × Q[t_I] into the output.
- 4.2 Generic-Join: The resulting runtime is Õ(m^n Q_F∈E |R_F|^x_F), matching the AGM bound up to logarithmic factors.The induction combines the cost of computing projected tuples with the costs of recursively solving residual queries.
- 4.2 NPRR: NPRR is an instantiation of Algorithm 3 that chooses J ∈ E and uses the power-of-two-choices idea for residual subqueries.When x_J is below one, it bounds min{p,q} using a weighted geometric mean and chooses between two evaluation directions.
- 4.3 Limitation of join-project plans: Join-project plans can be polynomially slower than the AGM bound, whereas the Section 4 algorithms match AGM; for LW_n, NPRR runs in O(n^2N) data-complexity time.The cited LW_n instance gives join-project runtime Ω(N^(2/n^2)), while the worst-case-optimal algorithms achieve O(N^(1+1/(n−1))) and NPRR has linear data complexity in N.
5 Open Questions
The survey closes with open questions about whether worst-case-optimal ideas can improve database runtime efficiency and how to obtain complexity measures sensitive to instance difficulty.
- Systems question: Whether the surveyed algorithmic ideas improve runtime efficiency in database systems remains open.The survey contrasts asymptotic improvements with decades of engineering refinements in traditional join processing.
- Theory question: Worst-case results may mainly describe pathological instances, motivating complexity measures that reflect input difficulty rather than only input size.The survey specifically asks whether adaptive join algorithms can have runtime dictated by instance difficulty.
- Theory question: Current complexity measures are too weak to explain index use or provide insight into average-case behavior.This motivates more refined measures beyond the currently known worst-case framework.
A Relation Algebra Notation
This section defines the relational notation used for joins: schemas and instances, natural join queries and outputs, semijoins, selections, and projections.
- Schemas and instances: A relational instance is a set of tuples over the domains of a relation’s distinct attributes, and a database contains one instance per relational symbol.The schema specifies relation arity and attributes, while the instance contains tuples from the corresponding Cartesian product of domains.
- Natural joins: A natural join query is a finite set of relational symbols, modeled by requiring one compatible tuple from every relation in the query.The output Q(D) contains tuples over all query attributes whose restriction to each relation’s attributes belongs to that relation instance.
- Semijoins: A semijoin R ⋉ S retains tuples of R having a matching tuple in S on their shared attributes.The definition tests equality of the projections onto the intersection of the two attribute sets.
- Selections and projections: The projection π_S(R) contains the tuples obtained by restricting tuples of R to an attribute subset S.Projection removes the remaining attributes while preserving values that occur in R.
- Selections and projections: The selection σ_S=s(R) keeps tuples whose attributes in S equal the specified value vector s.The selection is defined over a chosen subset of relation attributes and a vector from their associated domains.
B Analysis of Algorithm 2
The appendix verifies Algorithm 2’s runtime by analyzing nested candidate sets and applying the query decomposition lemma. Its bound is N^(3/2), matching Algorithm 1.
- Runtime decomposition: Algorithm 2’s runtime is dominated by computing the set L_{a,b}.The analysis decomposes the work by fixing a value a, then summing over b and the remaining C-values.
- Runtime decomposition: Summing the per-b costs over b ∈ L^B_a and then over a ∈ L_A yields the total runtime expression.The nested summation uses bounds on the candidate sets and their projections.
- Final bound: The final sum is N^(3/2), establishing Algorithm 2’s claimed worst-case runtime.The appendix identifies this sum with the earlier triangle-query expression and applies the same bound.
- Connection to Lemma 4.1: The analysis follows directly from Lemma 4.1 by choosing I = I2, producing the same set L used in Algorithm 2.Under this choice, the relevant edge set is {{B,C},{A,C}}, and the lemma bounds the resulting left-hand side by N^(3/2).
- Analytic tool: Hölder’s inequality supplies the mathematical inequality used in the appendix’s runtime analysis.The appendix states the nonnegative-number form of Hölder’s inequality as the supporting analytic tool.
D.1 Entropy and Shearer’s inequality
This section introduces entropy and conditional entropy, then uses Shearer’s inequality to relate joint uncertainty to fractional edge covers. The proof relies on conditioning reducing entropy and the coverage property of fractional edge covers.
- Entropy: Entropy measures the uncertainty associated with a discrete random variable.Joint entropy extends the definition to tuples of random variables.
- Conditional entropy: Conditional entropy measures uncertainty about X after Y is known, and additional conditioning cannot increase it.The section states HrX | Y, Zs ≤ HrX | Ys.
- Shearer’s inequality: Shearer’s inequality applies to random variables indexed by a hypergraph and any fractional edge cover.The lemma bounds joint entropy using weighted conditional entropies over the hypergraph’s edges.
- Proof idea: The proof bounds each conditional entropy by conditioning on variables within an edge, then uses fractional coverage to aggregate these bounds.Every variable is covered with total fractional weight at least one.
D.2 AGM’s proof based on Shearer’s entropy inequality and a join-project plan
The section derives AGM’s inequality from Shearer’s entropy inequality and gives a recursive join-project plan. The resulting plan evaluates any query within a runtime controlled by the fractional edge-cover bound.
- AGM proof: A uniformly chosen output tuple has entropy log2 |Q|, while each projected edge tuple lies in its input relation.The proof compares output entropy with the entropy available on the query’s relations.
- AGM proof: Applying Shearer’s inequality to any fractional edge cover yields AGM’s inequality.The section explicitly identifies the resulting inequality with AGM’s bound.
- Join-project plan: A recursive join-project plan evaluates any query in Op|Q|2 ¨ 2ρ˚pQ,Dq ¨ Nq time.The bound depends on query size, the fractional edge-cover quantity, and input size.
- Join-project plan: The plan recursively joins projections, and all intermediate results are bounded by 2ρ˚pQ,Dq ¨ N.The base case is a simple set-intersection problem.
E A more formal description of GLVV results
This section describes GLVV’s transformation of conjunctive queries into natural join queries whose AGM bounds apply. The resulting bound is essentially tight up to a data-independent factor, and full conjunctive queries retain worst-case-optimal algorithms.
- Transformation: GLVV constructs a natural join query Q with |C| ≤ |Q|, allowing the AGM bound to be applied to the transformed query.The transformation provides size bounds for conjunctive queries with simple functional dependencies.
- Transformation: The transformation begins by chasing C, replacing repeated relation symbols, and deriving variable-level functional dependencies.The chase step runs in Op|C|4q-time, while duplicate relations can share an underlying index.
- Functional-dependency processing: For each dependency Xi Ñ X j, the method adds X j to atoms containing Xi but not X j, while representing the added field by a pointer.Dependencies are propagated and then removed according to the stated update rules.
- Functional-dependency processing: The canonical dependency-processing order terminates in about Opn2q time, and the resulting query C3 is equivalent to C2.Repeated variables are then removed by retaining tuples matching the repetition patterns.
- Results: GLVV’s bound is essentially tight up to a data-independent factor.For full conjunctive queries, no projection is needed and worst-case-optimal join algorithms can be applied.
F Proof of Lemma 4.2
This section constructs simple relations to show that non-contained attribute sets force large intermediate joins. Consequently, every join-project plan for the considered instance requires quadratic-scale runtime in N, up to factors depending on n.
- Construction: Each constructed relation Ri has size N.The domain and relation construction are chosen so every input relation has the same cardinality.
- Construction: A simple relation contains all tuples over its attributes with at most one non-zero value.The constructed input relations are simple, and arbitrary projections preserve simplicity.
- Join lower bound: If neither attribute set contains the other, joining two simple relations produces at least (1 + (N − 1)/(n − 1))^2 = Ω(N^2/n^2) tuples.Containment of one attribute set in the other is the contrasting case in which the join remains simple.
- Join lower bound: Every arbitrary join-project plan eventually joins two non-contained relations and therefore requires Ω(N^2/n^2) runtime.This establishes the lower bound for plans starting from the constructed simple relations.