Size bounds and query plans for relational joins

DOI10.1137/110859440zbMATH Open1276.68066arXiv1711.03860OpenAlexW2169998163MaRDI QIDQ2862210FDOQ2862210

Authors: Albert Atserias, Martin Grohe, Dániel Marx 

Publication date: 14 November 2013

Published in: SIAM Journal on Computing (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1711.03860

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

zbMATH Keywords

linear programmingjoindatabase queryfractional edge coverquery plan

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Cited In (26)

• Title not available (Why is that?)
• Applications of range query theory to relational data base join and selection operations
• Tractability beyond \(\beta\)-acyclicity for conjunctive queries with negation and SAT
• Worst-case optimal join algorithms
• Tracking join and self-join sizes in limited storage
• Structural decompositions for problems with global constraints
• Linear Programs with Conjunctive Database Queries
• Fractional covers of hypergraphs with bounded multi-intersection
• Enumerating homomorphisms
• Covers of Query Results
• Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
• Size bounds for factorised representations of query results
• General space-time tradeoffs via relational queries
• On the complexity of division and set joins in the relational algebra
• I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration
• 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
• Title not available (Why is that?)
• Answering conjunctive queries with inequalities
• 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)