[gregable]

Very well put together. If you are curious about the weighted version, I tried to explain it some here: https://gregable.com/2007/10/reservoir-sampling.html

There's also a distributed version, easy with a map reduce.

Or the very simple algorithm: generate a random paired for each item in the stream and keep the top N ordered by that random.

[tmoertel]

Two notes on the weighted version. First, the straightforward implementation of selecting the top N when ranked by POW(RANDOM(), 1.0 / weight) has stability problems when the weights are very large or very small. Second, the resulting sample does not have the same distribution in expectation as the population from which it was drawn. This is especially so when the overall weight is concentrated in a small number of population elements. But such samples are workable approximations in many cases.

I discuss these issues more here: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....