Re: Selecting K random rows - efficiently!

cluster wrote:
> It has been suggested [1] that a good way to select K random rows
> efficiently from a table is to
>   1) add a new column, random_number, to the table
>      and initialize it with random()
>   2) perform the following query:
>        SELECT *
>        FROM mydata
>        WHERE random_number >= (SELECT RANDOM() OFFSET 0)
>        ORDER BY random_number ASC LIMIT <K>
>      Here <K> is the number of random rows to pick. E.g. 100.
>
> The benefit in this solution is that the "random_number" column can be
> indexed, allowing the query to be performed using a simple and fast
> index scan.
>
> However, there is a couple of major drawbacks in this method:
>
> 1) The smaller "random_number" is, the less likely is it that it will
> be picked when using this method. Example: A random_number close to
> zero will only have a very small probability to be selected.
When the above query returns L rows (where L < K) then, you need to
append the first K - L  rows from the table to simulate a "ring" without
start or end.  (Conveniently, this also solves the problem of not
finding K rows because the random start value was too large.)

The second set of rows can certainly be fetched using a second SELECT
statement.   Whether this can be computed efficiently as a single SELECT
statement I am not sure but you might try something like this:

  (SELECT 1 AS seq, *
  FROM mydata
  WHERE random_number >= (SELECT RANDOM() OFFSET 0)
  ORDER BY random_number ASC LIMIT <K>)
UNION ALL
  (SELECT 2 AS seq, *
  FROM mydata
  ORDER BY random_number ASC LIMIT <K>)
ORDER BY seq ASC, random_number ASC LIMIT K;

This should provide each row with an equal chance of being selected
while requiring the database to fetch at most 2 * K rows.

Regards,

Paul Tillotson