Simple Random Samples from a Sql database

There's a very interesting discussion of this type of issue here: http://www.titov.net/2005/09/21/do-not-use-order-by-rand-or-how-to-get-random-rows-from-table/

I think with absolutely no assumptions about the table that your O(n lg n) solution is the best. Though actually with a good optimizer or a slightly different technique the query you list may be a bit better, O(m*n) where m is the number of random rows desired, as it wouldn't necesssarily have to sort the whole large array, it could just search for the smallest m times. But for the sort of numbers you posted, m is bigger than lg n anyway.

Three asumptions we might try out:

1. there is a unique, indexed, primary key in the table

2. the number of random rows you want to select (m) is much smaller than the number of rows in the table (n)

3. the unique primary key is an integer that ranges from 1 to n with no gaps

With only assumptions 1 and 2 I think this can be done in O(n), though you'll need to write a whole index to the table to match assumption 3, so it's not necesarily a fast O(n). If we can ADDITIONALLY assume something else nice about the table, we can do the task in O(m log m). Assumption 3 would be an easy nice additional property to work with. With a nice random number generator that guaranteed no duplicates when generating m numbers in a row, an O(m) solution would be possible.

Given the three assumptions, the basic idea is to generate m unique random numbers between 1 and n, and then select the rows with those keys from the table. I don't have mysql or anything in front of me right now, so in slightly pseudocode this would look something like:

create table RandomKeys (RandomKey int)
create table RandomKeysAttempt (RandomKey int)

-- generate m random keys between 1 and n
for i = 1 to m
  insert RandomKeysAttempt select rand()*n + 1

-- eliminate duplicates
insert RandomKeys select distinct RandomKey from RandomKeysAttempt

-- as long as we don't have enough, keep generating new keys,
-- with luck (and m much less than n), this won't be necessary
while count(RandomKeys) < m
  NextAttempt = rand()*n + 1
  if not exists (select * from RandomKeys where RandomKey = NextAttempt)
    insert RandomKeys select NextAttempt

-- get our random rows
select *
from RandomKeys r
join table t ON r.RandomKey = t.UniqueKey

If you were really concerned about efficiency, you might consider doing the random key generation in some sort of procedural language and inserting the results in the database, as almost anything other than SQL would probably be better at the sort of looping and random number generation required.

In certain dialects like Microsoft SQL Server, PostgreSQL, and Oracle (but not MySQL or SQLite), you can do something like

select distinct top 10000 customer_id from nielsen.dbo.customer TABLESAMPLE (20000 rows) REPEATABLE (123);

The reason for not just doing (10000 rows) without the top is that the TABLESAMPLE logic gives you an extremely inexact number of rows (like sometimes 75% that, sometimes 1.25% times that), so you want to oversample and select the exact number you want. The REPEATABLE (123) is for providing a random seed.

Try

SELECT TOP 10000 * FROM table ORDER BY NEWID()

Would this give the desired results, without being too over complicated?

If you need exactly m rows, realistically you'll generate your subset of IDs outside of SQL. Most methods require at some point to select the "nth" entry, and SQL tables are really not arrays at all. The assumption that the keys are consecutive in order to just join random ints between 1 and the count is also difficult to satisfy — MySQL for example doesn't support it natively, and the lock conditions are... tricky.

Here's an O(max(n, m lg n))-time, O(n)-space solution assuming just plain BTREE keys:

1. Fetch all values of the key column of the data table in any order into an array in your favorite scripting language in O(n)
2. Perform a Fisher-Yates shuffle, stopping after m swaps, and extract the subarray [0:m-1] in ϴ(m)
3. "Join" the subarray with the original dataset (e.g. SELECT ... WHERE id IN (<subarray>)) in O(m lg n)

Any method that generates the random subset outside of SQL must have at least this complexity. The join can't be any faster than O(m lg n) with BTREE (so O(m) claims are fantasy for most engines) and the shuffle is bounded below n and m lg n and doesn't affect the asymptotic behavior.

In Pythonic pseudocode:

ids = sql.query('SELECT id FROM t')
for i in range(m):
  r = int(random() * (len(ids) - i))
  ids[i], ids[i + r] = ids[i + r], ids[i]

results = sql.query('SELECT * FROM t WHERE id IN (%s)' % ', '.join(ids[0:m-1])

Select 3000 random records in Netezza:

WITH IDS AS (
     SELECT ID
     FROM MYTABLE;
)

SELECT ID FROM IDS ORDER BY mt_random() LIMIT 3000

Maybe you could do

SELECT * FROM table LIMIT 10000 OFFSET FLOOR(RAND() * 190000)