Na verdade, não tenho disponibilidade do Oracle agora, mas a melhor consulta SQL para paginação é a seguinte, com certeza
select *
from (
select rownum as rn, a.*
from (
select *
from my_table
order by ....a_unique_criteria...
) a
)
where rownum <= :size
and rn > (:page-1)*:size
http://www.oracle.com/technetwork/issue-archive/2006/06-sep/o56asktom-086197.html
Para obter uma paginação consistente você deve ordenar as linhas usando um critério exclusivo , isso evitará carregar para a página X uma linha que você já carregou para uma página Y ( !=X ).
EDITAR:
1) Ordenar linhas usando um critério único significa ordenar dados de forma que cada linha mantenha a mesma posição em cada execução da consulta
2) Um índice com todas as expressões usadas na cláusula ORDER BY ajudará a obter resultados mais rápidos, especialmente para as primeiras páginas. Com esse índice o plano de execução escolhido pelo otimizador não precisa ordenar as linhas porque ele retornará linhas rolando o índice por sua ordem natural.
3) A propósito, a maneira mais rápida de paginar o resultado de uma consulta é executar a consulta apenas uma vez e lidar com todo o fluxo do lado do aplicativo.
