Beyond Equi-joins: Ranking, Enumeration and Factorization

We study theta-joins in general and join predicates with conjunctions and disjunctions of inequalities in particular, focusing on ranked enumeration where the answers are returned incrementally in an order dictated by a given ranking function. Our approach achieves strong time and space complexity properties: with $n$ denoting the number of tuples in the database, we guarantee for acyclic full join queries with inequality conditions that for every value of $k$, the $k$ top-ranked answers are returned in $O(n \operatorname{polylog} n + k \log k)$ time. This is within a polylogarithmic factor of the best known complexity for equi-joins and even of $\mathcal{O}(n+k)$, the time it takes to look at the input and return $k$ answers in any order. Our guarantees extend to join queries with selections and many types of projections, such as the so-called free-connex queries. Remarkably, they hold even when the entire output is of size $n^\ell$ for a join of $\ell$ relations. The key ingredient is a novel $\mathcal{O}(n \operatorname{polylog} n)$-size factorized representation of the query output, which is constructed on-the-fly for a given query and database. In addition to providing the first non-trivial theoretical guarantees beyond equi-joins, we show in an experimental study that our ranked-enumeration approach is also memory-efficient and fast in practice, beating the running time of state-of-the-art database systems by orders of magnitude.