Algorithms Every Programmer Should Know: Reservoir Sampling

Algorithms Every Programmer Should Know: Reservoir Sampling
omniref.com

http://www.cs.umd.edu/~samir/498/vitter.pdf

> "I have a database table with #{17.kajillion} records, and I want to take a random sample of #{X} of them. How can I do this efficently?"

And goes on to say that something like `YourBigTable.all.sample(X)` is bad in time and space. And the link that explains why doing `ORDER BY RANDOM()` is bad lists one reason being that generation of random numbers is relatively expensive.

But these problems aren't solved by reservoir sampling. Reservoir sampling is still O(N), and it requires generating a random number for every element. It still beats `ORDER BY RANDOM()` because it doesn't have to sort the numbers (or even keep them all in memory at the same time). But that doesn't make it a good choice.

More generally, reservoir sampling is appropriate when you don't know the size of the set beforehand. But in the premise, we do know the size of the set. And if you know the size of the set (and have some way to address arbitrary elements), then randomly generating a set of X indices is going to be much simpler and faster. Yeah, you have to deal with duplicate indices, but that's an easy problem to solve.

Reservoir sampling: I'm not sure that applying this algorithm to database sampling is the right thing to do. By its nature, the algorithm has to touch every single row in a database, and it does that because it's designed for data streams where you don't know in advance the size of the stream -- which isn't the case with database tables.

Assuming a uniform distribution in your database, you could instead do something like:

    SELECT *
    FROM (
        SELECT
            @row := @row +1 AS rownum, [column, column, columns...]
        FROM (
            SELECT @row :=0) r, [table name]
        ) ranked
    WHERE rownum % [n] = 1