[php/sql] Pager Opcje

[Beynar]

Nie mam pomysłu jak napisać pager.
Problem polega na tym, ze gdy skieruje zapytanie sql do bazy z klauzlą LIMIT np. 40, 70 to nie wiem ile tak naprawdę rekordów mam całej tabelce, a pod wyświetlonymi wynikami przydałoby się wypisać pokolei linki do kolejnych stron: 1,2,3,4,5 ale jak je moge wypisać skoro nie wiem ile rzeczywiście rekordów mam w tabelce?

Moge wydobyć liczbe wierszy za pomocą drugiego zapytania SELECT COUNT(ID) FROM tablename ale to jest już kosztowna operacja...
Bez liczby wszystkich wierszy nie moge wypisac na dole ile jest stron, z kolei zliczenie ich nie jest możliwe bez wybrania całosci.
Moge zrobic SELECT na wszystkim bez LIMITu, i robić paging w php ale to mija się z celem.