Before revision:  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).
After revision:  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 ( where answers can be returned in any order) for joins with inequalities, returning k answers in \mathcal{O}(n \operatorname{polylog} n + k).