  Sampling over joins is a fundamental task in large-scale data analytics.
Instead of computing the full join results, which could be massive, a uniform
sample of the join results would suffice for many purposes, such as answering
analytical queries or training machine learning models. In this paper, we study
the problem of how to maintain a random sample over joins while the tuples are
streaming in. Without the join, this problem can be solved by some simple and
classical reservoir sampling algorithms. However, the join operator makes the
problem significantly harder, as the join size can be polynomially larger than
the input. We present a new algorithm for this problem that achieves a
near-linear complexity. The key technical components are a generalized
reservoir sampling algorithm that supports a predicate, and a dynamic index for
sampling over joins. We also conduct extensive experiments on both graph and
relational data over various join queries, and the experimental results
demonstrate significant performance improvement over the state of the art.
