My paginator does all this at the DB server level.
http://jongriffin.com/static/openacs/paginate/It involves practically no overhead beyond your original query. and works in PG and Oracle.
This is being used in production for about a year with no problems. I haven't tested against 5.1 but it should work.