Worst-case optimal join algorithms
From MaRDI portal
Publication:4561503
Abstract: Efficient join processing is one of the most fundamental and well-studied tasks in database research. In this work, we examine algorithms for natural join queries over many relations and describe a novel algorithm to process these queries optimally in terms of worst-case data complexity. Our result builds on recent work by Atserias, Grohe, and Marx, who gave bounds on the size of a full conjunctive query in terms of the sizes of the individual relations in the body of the query. These bounds, however, are not constructive: they rely on Shearer's entropy inequality which is information-theoretic. Thus, the previous results leave open the question of whether there exist algorithms whose running time achieve these optimal bounds. An answer to this question may be interesting to database practice, as it is known that any algorithm based on the traditional select-project-join style plans typically employed in an RDBMS are asymptotically slower than the optimal for some queries. We construct an algorithm whose running time is worst-case optimal for all natural join queries. Our result may be of independent interest, as our algorithm also yields a constructive proof of the general fractional cover bound by Atserias, Grohe, and Marx without using Shearer's inequality. This bound implies two famous inequalities in geometry: the Loomis-Whitney inequality and the Bollob'as-Thomason inequality. Hence, our results algorithmically prove these inequalities as well. Finally, we discuss how our algorithm can be used to compute a relaxed notion of joins.
Recommendations
- Bounds and algorithms for joins via fractional edge covers
- Joins via geometric resolutions. Worst case and beyond
- Size bounds and query plans for relational joins
- 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
Cited in
(42)- It's all a matter of degree. Using degree information to optimize multiway joins
- Bounds and algorithms for joins via fractional edge covers
- A probabilistic model for assigning queries at the edge
- A formally verified, optimized monitor for metric first-order dynamic logic
- Answering conjunctive queries with inequalities
- Approximating max-min weighted \(T\)-joins
- Reverse and dual Loomis-Whitney-type inequalities
- Proceedings of the 17th international conference on database theory, ICDT 2014, Athens, Greece, March 24--28, 2014
- Entropy bounds for conjunctive queries with functional dependencies
- On the optimality of strategies for multiple join
- Avoiding Cartesian products for multiple joins
- Joins via geometric resolutions. Worst case and beyond
- Output-optimal massively parallel algorithms for similarity joins
- A Simple Sublinear-Time Algorithm for Counting Arbitrary Subgraphs via Edge Sampling
- scientific article; zbMATH DE number 7566062 (Why is no real title available?)
- Worst-case optimal algorithms for parallel query processing
- It's all a matter of degree: using degree information to optimize multiway joins
- scientific article; zbMATH DE number 7650999 (Why is no real title available?)
- scientific article; zbMATH DE number 7779293 (Why is no real title available?)
- Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries
- General space-time tradeoffs via relational queries
- The ring: worst-case optimal joins in graph databases using (almost) no extra space
- Learned query optimizers
- Join sampling under acyclic degree constraints and (cyclic) subgraph sampling
- Subgraph enumeration in optimal I/O complexity
- Information inequality problem over set functions
- Join and subgraph sampling under degree constraints
- Parallel acyclic joins: optimal algorithms and cyclicity separation
- Conjunctive queries with free access patterns under updates
- Counting simplices in hypergraph streams
- \textsf{PANDA}: query evaluation in submodular width
- Extensible query optimizers in practice
- Any-k algorithms for enumerating ranked answers to conjunctive queries
- TreeTracker Join: simple, optimal, fast
- Box covers and domain orderings for beyond worst-case join processing
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- I/O-efficient join dependency testing, Loomis-Whitney join, and triangle enumeration
- Problem of optimizing the number of block accesses in performing relational join is NP-hard
This page was built for publication: Worst-case optimal join algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4561503)
