3 ms·

The `ORDER BY RANDOM() LIMIT n` idiom is fairly well established for taking a random sample of uniformly distributed rows. It is also easily augmented to take w

The `ORDER BY RANDOM() LIMIT n` idiom is fairly well established for taking a random sample of uniformly distributed rows. It is also easily augmented to take weighted samples: `WHERE weight > 0 ORDER BY -LN(RANDOM())/weight LIMIT n`. Queries of this form are easilly parallelized. Most systems that support distributed query processing, for example, optimize ORDER/LIMIT n queries such that each worker returns just the top n rows from its partition. These top rows are then merged in a central worker and limited one last time to produce the final result. Even so, if your system supports the TABLESAMPLE clause and offers a formulation that lets you specify your actual distribution of interest (TABLESAMPLE SYSTEM often does not), you're probably better off using it.

tmoertel 3y ago
For anyone who is curious, the weighted sampling logic is the SQL translation of Algorithm A from Efraimidis and Spirakis's 2006 paper [1]: Algorithm A Input: A population V of weighted items Output: A WRS of size n 1: For each v[i] in V, u[i] = random(0, 1) and k[i] = u^(1/w[i]) 2: Select the n items with the largest keys k[i] as a WRS Instead of the more direct tanslation of `ORDER BY POW(RANDOM(), (1/weight)) DESC`, we use the convenient fact that logarithm is a monotone transform over the positive reals to take the log of the ORDER BY argument without changing the sort order: ORDER BY POW(RANDOM(), (1/weight)) DESC => ORDER BY LN(POW(RANDOM(), (1/weight))) DESC -- LN preserves order. => ORDER BY LN(RANDOM()) / weight DESC -- LN(x^a) = LN(x) * a. => ORDER BY -LN(RANDOM()) / weight -- Order by `x DESC` is same as by `-x`. [1] Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with a reservoir. Information Processing Letters, 97(5):181–185, 2006
- funcDropShadow 3y ago
  Thanks for this cool bit of information.

tmoertel 3y ago

For anyone who is curious, the weighted sampling logic is the SQL translation of Algorithm A from Efraimidis and Spirakis's 2006 paper [1]: Algorithm A Input: A population V of weighted items Output: A WRS of size n 1: For each v[i] in V, u[i] = random(0, 1) and k[i] = u^(1/w[i]) 2: Select the n items with the largest keys k[i] as a WRS Instead of the more direct tanslation of `ORDER BY POW(RANDOM(), (1/weight)) DESC`, we use the convenient fact that logarithm is a monotone transform over the positive reals to take the log of the ORDER BY argument without changing the sort order: ORDER BY POW(RANDOM(), (1/weight)) DESC => ORDER BY LN(POW(RANDOM(), (1/weight))) DESC -- LN preserves order. => ORDER BY LN(RANDOM()) / weight DESC -- LN(x^a) = LN(x) * a. => ORDER BY -LN(RANDOM()) / weight -- Order by `x DESC` is same as by `-x`. [1] Pavlos S Efraimidis and Paul G Spirakis. Weighted random sampling with a reservoir. Information Processing Letters, 97(5):181–185, 2006

funcDropShadow 3y ago
Thanks for this cool bit of information.