Pagination of search results

Hi,

I'm writing a search engine, the results of which will displayed in
blocks of 25, paginated. I will also display the number of records
found (1-25 of 345).

I'm trying to determine the most efficient way to implement this.
Since the session is dropped after the script is terminated, I'm
ruling our cursors. Also, cursors would prevent me from retrieving the
total number of records potentially returned from a search, and so I
couldn't display the correct number of page links. Also, this would
require persistent connections, which I'd like to avoid for a number
of reasons.

The best I've come up with is "SELECT b.*, c.cnt FROM table AS b,
(SELECT COUNT(1) AS cnt FROM table WHERE <LOTS OF CLAUSES>) AS c WHERE
<SAME LOT OF CLAUSES> LIMIT 25 OFFSET 0"

However this means that the query is essentially getting executed
twice for each page.

Is there any better way of implementing this? All advice gratefully received.

Kind Regards,

Neil Saunders.