select key from (select key, count(1) 'seq' from table) where seq = $RAND or the equivalent using temporary tables. It's what databases do, so it will suck to build the temp table for large databases. If you can get the DBA to add a sequence number, then use that instead of the temp table. If your sequence number can have holes, then get the first record where seq >= $RAND. That's assuming your holes have even distribution also. barring that, I see no alternative to reading a cursor until your number is up (from a 'select key, count(1) from table' query. Do a 'select count(1) from table' to determine the number of records in the table. BTW, reading from the cursor until you get to the record you want (i.e. a sequential search) happens all the time in SQL. Its just called a 'table scan' instead, and happens when there's not an available index to locate matching records for a where clause.