¿Existe una forma más eficiente de realizar la paginación en Hibernate que ejecutar consultas de selección y recuento?

Baron Schwartz en MySQLPerformanceBlog.com escribió un publicar sobre esto. Ojalá hubiera una varita mágica para este problema, pero no la hay. Resumen de las opciones que presentó:

1. En la primera consulta, obtenga y almacene en caché todos los resultados.
2. No mostrar todos los resultados.
3. No mostrar el recuento total ni los enlaces intermedios a otras páginas. Mostrar solo el enlace "siguiente".
4. Estime cuántos resultados hay.