cómo hacer que la selección de filas aleatorias en Oracle sea más rápida con una tabla con millones de filas

Usando los valores apropiados de sample(x) es la forma más rápida que puede. Es aleatorio por bloques y por filas dentro de los bloques, por lo que si solo desea una fila aleatoria:

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

Estoy usando una tabla subparticionada y obtengo una aleatoriedad bastante buena, incluso tomando varias filas:

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

Sospecho que probablemente deberías ajustar tu SAMPLE cláusula para usar un tamaño de muestra apropiado para lo que está buscando.