Source-linked AI summary
Size bounds and query plans for relational joins
Albert Atserias, Martin Grohe, Dániel Marx
TL;DR
The paper studies how to estimate relational-join answer sizes and execute join sequences in worst-case and average-case database models. It characterizes worst-case size using fractional edge covers, compares join-project and join plans, and shows how projections can be eliminated in the average case.
Problem
The paper addresses how to estimate the size of join-query answers and how to execute sequences of joins effectively, questions motivated by the high cost and potentially large outputs of joins.
Method
The paper analyzes natural-join queries theoretically using hypergraph parameters, fractional edge covers, linear programs, and execution plans with joins and projections.
Results
Worst-case query size is characterized by fractional edge covers with matching lower bounds, while join-project plans can outperform join plans; in the average case, projections can be removed with only a constant-factor increase in expected evaluation time.
Takeaways & Limitations
Worst-case optimization may require intermediate projections, whereas average-case execution can use projection-free join plans without size-dependent expected-time loss.
Takeaways & Limitations
The paper does not provide a high-probability size bound for the projection-elimination result, and finding some efficient join plans is generally NP-hard.
Abstract
from arXiv · showhide
Relational joins are at the core of relational algebra, which in turn is the core of the standard database query language SQL. As their evaluation is expensive and very often dominated by the output size, it is an important task for database query optimisers to compute estimates on the size of joins and to find good execution plans for sequences of joins. We study these problems from a theoretical perspective, both in the worst-case model, and in an average-case model where the database is chosen according to a known probability distribution. In the former case, our first key observation is that the worst-case size of a query is characterised by the fractional edge cover number of its underlying hypergraph, a combinatorial parameter previously known to provide an upper bound. We complete the picture by proving a matching lower bound, and by showing that there exist queries for which the join-project plan suggested by the fractional edge cover approach may be substantially better than any join plan that does not use intermediate projections. On the other hand, we show that in the average-case model, every join-project plan can be turned into a plan containing no projections in such a way that the expected time to evaluate the plan increases only by a constant factor independent of the size of the database. Not surprisingly, the key combinatorial parameter in this context is the maximum density of the underlying hypergraph. We show how to make effective use of this parameter to eliminate the projections.
1 Introduction
The paper characterizes join-query size and evaluation plans theoretically in worst-case and average-case database models. Fractional edge covers govern worst-case size and can make projections crucial, whereas maximum density enables projection elimination in the average case.
- Motivation: Join queries are costly because outputs can greatly exceed input relations, making size estimation and execution-order selection central optimizer tasks.The paper studies these questions theoretically for sequences of joins.
- Worst-case size: The worst-case answer size is characterized by the fractional edge cover number, which supplies both upper and matching lower bounds up to query-dependent factors.For every query, arbitrarily large databases attain a lower bound of (|D|/|Q|)^ρ∗(Q).
- Worst-case size: Polynomial answer size, polynomial-time evaluation, polynomial-time join-project evaluation, and bounded fractional edge cover number are equivalent for query classes.The equivalence connects a combinatorial structural parameter to both output size and evaluation complexity.
- Execution plans: Join-project plans can outperform every join-only plan substantially in the worst case, with arbitrarily large queries separating cubic-time evaluation from |D|^Ω(log|Q|) join plans.The join-project plan is efficiently computable, while a corresponding optimal join plan can be computationally difficult to find.
- Average-case analysis: In random databases, maximum density governs answer-size concentration, and every join-project plan can be converted to a join plan with only a constant-factor expected-time increase.The conversion balances delaying joins against retaining joins to control subquery attributes and density.
- Size constraints: With known relation sizes, modified edge-cover linear programs give analogous bounds, but better-than-exponential approximation is impossible in polynomial time unless NP = ZPP.The upper–lower-bound gap becomes 2^-n and is essentially tight.
2 Preliminaries
The paper formalizes join queries, database instances, query answers, and two classes of execution plans. These preliminaries represent queries as hypergraphs and distinguish plans with projections from plans using only joins.
- Database instances: A database instance assigns a finite relation to each relation name, and its size is the sum of all relation cardinalities.The active domain is the union of values appearing in the relations.
- Join queries: A join query’s answer contains tuples whose projection onto every relation’s attributes belongs to that relation.The query answer is an A_Q-relation, where A_Q is the union of query attributes.
- Hypergraph representation: The query hypergraph has attributes as vertices and relation attribute sets as edges, capturing the query’s structural overlap.The hypergraph may contain repeated edges when relation attribute sets repeat.
- Execution plans: A join plan is built from relation names and binary joins, whereas a join-project plan additionally permits unary projections.Both plan types can represent alternative evaluation orders for the same join query.
3 Worst-case model
The worst-case analysis characterizes join-answer size through fractional edge covers and establishes matching constructions. It also shows that projections can yield substantially better plans than join-only evaluation, while join plans remain within a logarithmic exponent factor.
- Fractional edge covers: Fractional edge covers assign nonnegative weights to relations so every query attribute receives total coverage at least one; their minimum cost is ρ∗(Q).The defining linear program minimizes ∑R x_R subject to ∑R:a∈A_R x_R ≥ 1 for every attribute.
- Size bounds: For every fractional edge cover, the join answer is bounded by the corresponding product of relation sizes, yielding the standard |D|^ρ∗(Q) worst-case bound.The proof uses Shearer’s lemma, which bounds joint entropy through marginal entropies.
- Size bounds: The fractional-edge-cover upper bound is tight: arbitrarily large instances attain answer size proportional to |D|^ρ∗(Q).The construction can equalize the sizes of relations with positive optimal cover weights.
- Join versus join-project plans: Some queries require join plans to take |D|^Ω(log|Q|) time, while a join-project plan runs in O(|Q|^2 · |D|^3).The lower bound follows from a large subplan that every join plan must evaluate.
- Join versus join-project plans: Every query also has a join plan evaluable in O(|Q| · |D|^(2ρ∗(Q)·log|Q|)), making the logarithmic exponent gap essentially tight.This construction uses the logarithmic integrality gap between edge covers and fractional edge covers.
- Join versus join-project plans: The join-plan construction may require solving an NP-hard problem and can be superpolynomially worse in |D| than the efficiently computable join-project approach.The relevant join-plan bound uses the integral edge-cover number ρ(Q), rather than ρ∗(Q).
4 Size constraints
With fixed relation sizes, the paper estimates worst-case join-answer size using a modified fractional-edge-cover linear program, proves matching bounds up to a 2^n factor, and shows substantially better approximation is computationally hard.
- Size bounds under size constraints: The linear program minimizes ∑R xR·logNR subject to the fractional-edge-cover constraints ∑R:a∈AR xR ≥ 1 for every attribute.Its feasible solutions are fractional edge covers, but the objective incorporates the prescribed relation sizes.
- Size bounds under size constraints: For every size-constrained instance, |Q(D)| ≤ ∏R NR^xR, while some instance satisfies |Q(D)| ≥ 2^-n ∏R NR^xR.Here n is the number of query attributes and xR is an optimal solution of the linear program.
- Size bounds under size constraints: The 2^n gap between the upper and lower bounds is essentially tight: an explicit family has relation-product scale roughly 2^n but answer size at most 2^(εn).Thus the lower-bound factor cannot generally be improved beyond 2^-(1-ε)n.
- Hardness of better approximation: No polynomial-time algorithm can approximate the worst-case answer size within a factor better than 2^(n^(1-ε)), unless ZPP = NP.The hardness follows by connecting constrained query size to maximum independent set.
5 Average-case model
In the average-case model, relations are generated independently with specified tuple probabilities, and query-answer concentration is governed by subquery density. The paper uses this structure to remove projections from join-project plans while increasing expected intermediate size by only a constant factor.
- 5.1 Size bounds and concentration: The random-instance model independently includes each tuple of relation R with probability pR(N) over the domain [N].The model includes uniform instances and probabilities such as 1/2, C·N^(1-|AR|), and N^(1-|AR|)logN.
- 5.1 Size bounds and concentration: Maximum density satisfies δ(Q,w) = max{δ(Q[B],w) : B ⊆ Aσ, B ≠ ∅}, so subqueries determine the relevant threshold behavior.With weights wR = log2(1/pR(N)), density compares subquery structure with tuple-inclusion probabilities.
- 5.1 Size bounds and concentration: When density exceeds log2(N), some subquery has expected solution count below 1, making the full query empty with probability bounded away from 0; below the threshold, variance can be bounded.The paper derives these consequences using Markov’s inequality and variance analysis.
- 5.2 Execution plans: Theorem 20 transforms any join-project plan into a join plan whose every subplan has expected size at most cϕT when the original plan’s subplans are bounded by T.The constant cϕ depends only on the original plan, not on database size.
- 5.2 Execution plans: The projection-elimination procedure repeatedly removes projections while increasing maximum expected subplan size by only a constant factor.The construction may depend on N because tuple probabilities can vary with N.
6 Conclusions
The paper’s theoretical results provide tight answer-size bounds and distinguish worst-case from average-case advantages of join-project plans. Remaining challenges include functional dependencies and high-probability concentration guarantees for join-project plans.
- Worst-case answer sizes can be bounded tightly using the fractional edge cover number or related linear programs.
- Join-project plans can be significantly more efficient than join plans for the same query in the worst-case model.
- In the average-case model, every join-project plan can be converted into a join plan with only a bounded performance loss.
- Functional dependencies remain an incompletely resolved direction for extending the paper’s bounds.
- Theorem 20 bounds expected size but not size with high probability, leaving concentration guarantees for join-project plans as a challenge.