Pagination control alternatives in large data sets?

miked

Background in my prev post at http://www.datatables.net/forums/discussion/25125/footer-showing-0-to-0-of-0-entries-issue-showing-up-in-large-data-sets#latest

I'm officially out of options, the problem I've discovered is that in order for the pagination controls to be setup correctly I need to run a query that I can't optimize further (count() and a where clause using wildcards = performance nightmare) and it takes somewhere between 20 seconds to 3 minutes or more to return the count() in order to get the total number of records matching the criteria (see #3 in the post above).

If I don't return the count from this query then I lose the pagination - the control has no idea how many records to set up for. If I set the value to 0 then the pagination control doesn't display at all. I can assign/hardcode some arbitrary count in order to get the control to display, but I don't have an accurate count of the actual number of pages available, and I get people using "first" and "last" quite a bit.

Are there any other options that will let me avoid running the count()/where/wildcard query yet give me a workable pagination control? ie I don't want to calc recordsFiltered while still allowing some sort of pagination control to appear.