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 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 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).