On Join Sampling and the Hardness of Combinatorial Output-Sensitive Join Algorithms
Shiyuan Deng, Shangqi Lu, Yufei Tao
Abstract
We present a dynamic index structure for join sampling. Built for an (equi-) join Q --- let IN be the total number of tuples in the input relations of Q --- the structure uses ~O(IN) space, supports a tuple update of any relation in ~O(1) time, and returns a uniform sample from the join result in ~O(INρ* / /max{1, OUT} ) time with high probability (w.h.p.), where OUT and ρ* are the join's output size and fractional edge covering number, respectively; notation ~O(.) hides a factor polylogarithmic to IN. We further show how our result justifies the O(INρ* ) running time of existing worst-case optimal join algorithms (for full result reporting) even when OUT łl INρ*. Specifically, unless the combinatorial k-clique hypothesis is false, no combinatorial algorithms (i.e., algorithms not relying on fast matrix multiplication) can compute the join result in O(INρ*-ε ) time w.h.p. even if OUT łe INε, regardless of how small the constant ε > 0 is.