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