The things you can do with search

I've just confirmed that running it as one query (do the search and figure out how many results there are whilst only returning the first 25) takes 1 minute and 38 seconds.

Running it as two queries (do the search, return 25 rows and then figure out how many results there are) takes 2.5 seconds in total.

Definitely will change this.

Though... there is a risk that the search will be slower on subsequent pages. i.e. it may take towards 15-20 seconds (and risk timing out on some queries that return very large result sets) to fetch page 2 or more.

In essence I had chosen to implement a way of searching in which the cost for all pages was equal, but it's probably best to tune for making page 1 very cheap, and subsequent pages expensive.