Muitas querys repetidas em paginação

Olá desenvolvi um sistema de paginação que funciona da seguinte forma.

Faço um query buscando todos resultados relativos a paginação.

Desses resultados obtenho os dados para executar uma segunda query onde passo o offset de acordo com a paginação.

A questão é, se por exemplo tenho resultados para exibir digamos 8 páginas, mas vai lá um "zé" e resolve passar na url do navegador mais do que o resultado esperado.

Prevendo isso resolvi fazer um redirect até que a query encontre resultados. Exemplo

A url ficaria assim:

http://site/paginar/registro-8 esse seria o limite de quantidade máxima de registros que existem

Se por então a pessoa tentar acessar assim: http://site/paginar/registro-99999999 o sistema de paginação começa a redirecionar decrementando os números até chegar ao resultado de 8.

Seguindo.... Isso não seria prejudicial ao servidor de alguma forma? Uma vez que isso, muitas querys vão ser geradas repetitivamente.

Por outro lado a velocidade de execução vai depender da velocidade de conexão e da máquina do usuário.

Na sua opinião. O que acha disso?

Redirecionar até o resultado existente ou simplesmente passar um erro de resultado não obtido?