# Box Covers and Domain Orderings for Beyond Worst-Case Join Processing

@inproceedings{Alway2021BoxCA, title={Box Covers and Domain Orderings for Beyond Worst-Case Join Processing}, author={Kaleb Alway and Eric Blais and Semih Salihoglu}, booktitle={ICDT}, year={2021} }

Recent beyond worst-case optimal join algorithms Minesweeper and its generalization Tetris have brought the theory of indexing and join processing together by developing a geometric framework for joins. These algorithms take as input an index $\mathcal{B}$, referred to as a box cover, that stores output gaps that can be inferred from traditional indexes, such as B+ trees or tries, on the input relations. The performances of these algorithms highly depend on the certificate of $\mathcal{B… Expand

#### 4 Citations

Combining Worst-Case Optimal and TraditionalBinary Join Processing

- 2020

Worst-case optimal join algorithms are attractive from a theoretical point of view, as they offer asymptotically better runtime than binary joins on certain types of queries. In particular, they… Expand

Adopting worst-case optimal joins in relational database systems

- Computer Science
- Proc. VLDB Endow.
- 2020

This paper presents a comprehensive implementation approach for worst-case optimal joins that is practical within general-purpose relational database management systems supporting both hybrid transactional and analytical workloads and implements a hybrid query optimizer that intelligently and transparently combines both binary and multi-way joins within the same query plan. Expand

Worst-Case Optimal Graph Joins in Almost No Space

- Computer Science
- SIGMOD Conference
- 2021

An indexing scheme that supports worst-case optimal graph joins in almost no space beyond storing the graph itself and offers the best overall performance for query times while using only a small fraction of the space when compared with several state-of-the-art approaches. Expand

Instance Optimal Join Size Estimation

- Computer Science
- ArXiv
- 2020

This work gives an instance optimal algorithm for estimating theJoin size for all instances, including when the join size is large, by removing the dependency on the joinsize. Expand

#### References

SHOWING 1-10 OF 31 REFERENCES

Beyond worst-case analysis for joins with minesweeper

- Computer Science, Mathematics
- PODS
- 2014

A new algorithm is described, Minesweeper, that is able to satisfy stronger runtime guarantees than previous join algorithms (colloquially ``beyond worst-case'' guarantees) for data in indexed search trees and a dichotomy theorem is developed for the certificate-based notion of complexity. Expand

Size Bounds and Query Plans for Relational Joins

- Mathematics, Computer Science
- 2008 49th Annual IEEE Symposium on Foundations of Computer Science
- 2008

This work studies relational joins from a theoretical perspective and shows 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. Expand

Computing Join Queries with Functional Dependencies

- Computer Science, Mathematics
- PODS
- 2016

This paper presents an algorithm for computing join queries with FDs, running within GLVV bound up to a poly-log factor, and shows that it is tight on distributive lattices and some other simple lattices. Expand

It's All a Matter of Degree: Using Degree Information to Optimize Multiway Joins

- Computer Science
- ICDT
- 2016

It is said that a join can be processed in subquadratic time if $x < 2, making it the only known tight bound for joins that does not require any assumption about the matrix multiplication exponent $\omega$. Expand

Size and treewidth bounds for conjunctive queries

- Mathematics, Computer Science
- JACM
- 2012

New worst-case bounds for the size and treewith of the result Q(D) of a conjunctive query Q to a database D are provided, based on a novel "coloring" of the query variables that associates a coloring number C(Q) to each query Q. Expand

Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems

- Computer Science
- PODS
- 2018

This paper discusses the key techniques for proving runtime and output size bounds, and focuses on the fascinating connection between join algorithms and information theoretic inequalities, and the idea of how one can turn a proof into an algorithm. Expand

Using Semi-Joins to Solve Relational Queries

- Mathematics, Computer Science
- JACM
- 1981

The exact class of relational queries that can be solved using semi-joins is shown and it is shown that queries outside of this class may not even be partially solvable using "short" semi-join programs. Expand

Polynomial Complete Consecutive Information Retrieval Problems

- Computer Science
- SIAM J. Comput.
- 1977

Both of the computational complexity of these problems are shown to be polynomial complete in the sense of Cook [2] an... Expand

Constraint solving via fractional edge covers

- Mathematics
- SODA 2006
- 2006

Many important combinatorial problems can be modelled as constraint satisfaction problems, hence identifying polynomial-time solvable classes of constraint satisfaction problems received a lot of… Expand

PERFORMANCE GUARANTEES ON A SWEEP-LINE HEURISTIC FOR COVERING RECTILINEAR POLYGONS WITH RECTANGLES *

Finding the minimum number of rectangles required to cover a rectilinear or orthogonal polygon, where overlapping of rectangles is allowed, is one of several well-known, hard geometric decomposition… Expand