The search query builder uses some terrible operations that will never scale:
1. Using LOWER() on every name. This immediately drops search performance from O(log(N)) to O(N). LOWER is also redundant when using a LIKE match.
2. Prefixing a wildcard to the search criteria. This also drops search performance to O(N).
I've modified the search file /CRM/Contact/BAO/Query.php (attached) for drastic performance increases. Perhaps CiviCRM could at least offer an option to run in a large dataset mode.
All my changes are in the sortName function.
I did a few key things:
1. Removed LOWER from the lefthand side of the LIKE clause
2. Removed the '%' prefixed to the search
3. Only activated email search if the criteria contain a '@'
Now MySQL can use an index. This bumps performance back to around O(log(N)), which is important because we have about 150,000 contacts.