Beyond Equi-joins: Ranking, Enumeration and Factorization

We study full acyclic join queries with general join predicates that involve conjunctions and disjunctions of inequalities, focusing on ranked enumeration where the answers are returned incrementally in an order dictated by a given ranking function. Our approach offers strong time and space complexity guarantees in the standard RAM model of computation, getting surprisingly close to those of equi-joins. With $n$ denoting the number of tuples in the database, we guarantee that for every value of $k$, the $k$ top-ranked answers are returned in $\mathcal{O}(n \operatorname{polylog} n + k \operatorname{log} k)$ time and $\mathcal{O}(n \operatorname{polylog} n + k)$ space. This is within a polylogarithmic factor of the best-known guarantee for equi-joins and even $\mathcal{O}(n + k)$, the time it takes to look at the input and output $k$ answers. The key ingredient is an $\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. As a side benefit, our techniques are also applicable to unranked enumeration (where answers can be returned in any order) for joins with inequalities, returning $k$ answers in $\mathcal{O}(n \operatorname{polylog} n + k)$. This guarantee improves over the state of the art for large values of $k$. In an experimental study, we show that our ranked-enumeration approach is not only theoretically interesting, but also fast and memory-efficient in practice.