Александр Рублев, при сортировке по фамилии будет так:
select count(id) from users where (surname < :surname) OR ((surname = :surname) AND (id < :id)) order by surname, id
, тут учитывается и то что будут одинаковые фамилии.
Узнаете кол-во ДО, соответственно узнаете и номер нужной вам страницы, и пойдет обычный пагинаторский запрос на нужную страницу - offset, limit