Since it is a count of matched condition records I may not have a way around.
What you could do is cache the search results (just caching the id's of the rows to display is enough and uses little space) in a cache table, numbering them with your sort order using a temporary sequence, so that you can :
SELECT ... FROM cache WHERE row_position BETWEEN page_no*per_page AND (page_no+1)*per_page-1
to get the count :
SELECT row_position FROM CACHE ORDER BY row_position DESC LIMIT 1
Add a session_id referencing your sessions table with an ON DELETE CASCADE and the cache will be auto-purged when sessions expire.
---------------------------(end of broadcast)--------------------------- TIP 4: Don't 'kill -9' the postmaster
