I have a search engine on a shared host that uses MySQL. This search engine potentially has millions/trillions etc of records.

Each time a search is performed I return a count of the records that can then be used for pagination purposes.

The count tells you how many results there are in regard to the search performed. MySQL count is I believe considered quite slow.

Order of search queries:

1. Search executed and results returned
2. Count query executed

I don't perform a PHP count as this will be far slower in larger data sets.

Question is, do I need to worry about MySQL "count" and at what stage should I worry about it. How do the big search engines perform this task?