Beyond Equi-joins: Ranking, Enumeration and Factorization

We study full acyclic join queries with general join predicates that involve conjunctions and disjunctions of inequality. Specifically, we provide the first non-trivial algorithms for the problem of ranked enumeration where the query results are returned incrementally in an order dictated by a given ranking function. Our approach offers strong data-complexity guarantees in the standard RAM model of computation that are surprisingly close to those of equi-joins. Given an acyclic inequality join between tables of size $n$, it returns the join answers in order and guarantees 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. This matches the best-known guarantee for equi-joins up to a polylogarithmic factor. The key ingredient is an $\mathcal{O}(n \operatorname{polylog} n)$-size factorized representation of all query results that is constructed in a preprocessing step. As a side benefit, our techniques are also applicable to the easier task of unranked enumeration (i.e., without an output ordering) where we are able to return $k$ join results in $\mathcal{O}(n \operatorname{polylog} n + k)$. This guarantee is asymptotically superior to any known alternative 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.