# Beyond Equi-joins: Ranking, Enumeration and Factorization

arXiv: https://arxiv.org/abs/2101.12158 · HTML: https://mlsanity.com/paper/2101.12158/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2021.

## Built on by (most cited first, 1 of 1)

- [Integrating connection search in graph queries](https://mlsanity.com/paper/2208.04802/) (2022)

## Abstract (arXiv)

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 operatornamepolylog n + k log k) time. This is within a polylogarithmic factor of O(n + k log k), i.e., the best known complexity for equi-joins, and even of O(n+k), i.e., 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 (namely those called "free-connex" queries and those that use bag semantics). Remarkably, they hold even when the number of join results is nℓ for a join of ℓ relations. The key ingredient is a novel O(n operatornamepolylog 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.