Size bounds and query plans for relational joins
From MaRDI portal
Publication:2862210
Abstract: 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.
Recommendations
- Size and treewidth bounds for conjunctive queries
- FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
- A generalization of relational joins
- Tracking join and self-join sizes in limited storage
- scientific article; zbMATH DE number 7650999
- On the complexity of finding bounds for projection cardinalities in relational databases
- Size bounds for factorised representations of query results
- On the complexity of join dependencies
- Applications of range query theory to relational data base join and selection operations
Cited in
(26)- scientific article; zbMATH DE number 7559412 (Why is no real title available?)
- Applications of range query theory to relational data base join and selection operations
- Tracking join and self-join sizes in limited storage
- Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
- Structural decompositions for problems with global constraints
- Worst-case optimal join algorithms
- Enumerating homomorphisms
- Fractional covers of hypergraphs with bounded multi-intersection
- Linear Programs with Conjunctive Database Queries
- Covers of Query Results
- Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
- Size bounds for factorised representations of query results
- On the complexity of division and set joins in the relational algebra
- I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration
- General space-time tradeoffs via relational queries
- It's all a matter of degree. Using degree information to optimize multiway joins
- It's all a matter of degree: using degree information to optimize multiway joins
- Structural tractability of enumerating CSP solutions
- Join cardinality estimation by combining operator-level deep neural networks
- Learned query optimizers
- Bounds and algorithms for joins via fractional edge covers
- Answering conjunctive queries with inequalities
- scientific article; zbMATH DE number 7566062 (Why is no real title available?)
- Joins via geometric resolutions. Worst case and beyond
- The ring: worst-case optimal joins in graph databases using (almost) no extra space
- Estimating list sizes in partial joins
This page was built for publication: Size bounds and query plans for relational joins
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862210)
