Before revision:  This is within a polylogarithmic factor of the best-known guarantee for equi-joins and even  \mathcal{O}(n+k), the time it takes to look at the input and output k answers .
After revision:  This is within a polylogarithmic factor of the best-known guarantee for equi-joins and even \mathcal{O}(n+k), 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, such as the so-called free-connex queries. Remarkably, they hold even when the entire output is of size n^\ell for a join of \ell relations.