Una posible solución es usar "LIMIT" en el "SELECT". No todos los DBMS lo tienen, pero permite paginar. Sería algo así como:
Código SQL
[-]SELECT *
FROM TablaDatos
LIMIT (NumPagina - 1) * NumElementosPorPagina, NumElementosPorPagina
Claro que aquí asumes que todos los registros tienen el mismo tamaño, por lo que en cada página entra un número fijo de elementos.