Usando valores apropriados de
sample(x) é a maneira mais rápida que você pode. É aleatório de bloco e aleatório de linha dentro de blocos, portanto, se você quiser apenas uma linha aleatória:select dbms_rowid.rowid_relative_fno(rowid) as fileno,
dbms_rowid.rowid_block_number(rowid) as blockno,
dbms_rowid.rowid_row_number(rowid) as offset
from (select rowid from [my_big_table] sample (.01))
where rownum = 1
Estou usando uma tabela subparticionada e estou obtendo uma aleatoriedade muito boa, mesmo capturando várias linhas:
select dbms_rowid.rowid_relative_fno(rowid) as fileno,
dbms_rowid.rowid_block_number(rowid) as blockno,
dbms_rowid.rowid_row_number(rowid) as offset
from (select rowid from [my_big_table] sample (.01))
where rownum <= 5
FILENO BLOCKNO OFFSET
---------- ---------- ----------
152 2454936 11
152 2463140 32
152 2335208 2
152 2429207 23
152 2746125 28
Suspeito que você provavelmente deva ajustar seu
SAMPLE cláusula para usar um tamanho de amostra apropriado para o que você está buscando. 
