Is there still some form of a limit, like selectivity criteria related limits, or can an arbitrary number of records be counted?
We have found that COUNT queries can still face limits in the form of exceeding CPU limits in the transaction, and I believe this is actually caused when the WHERE clause for the SOQL query requires significant filter-related processing against unindexed columns.
This help page discusses “selectivity”:
For best performance, SOQL queries must be selective, particularly for queries inside triggers. To avoid long execution times, the system can terminate nonselective SOQL queries. Developers receive an error message when a non-selective query in a trigger executes against an object that contains more than 200,000 records. To avoid this error, ensure that the query is selective.
It goes on to say:
A query is selective when one of the query filters is on an indexed field and the query filter reduces the resulting number of rows below a system-defined threshold. The performance of the SOQL query improves when two or more filters used in the WHERE clause meet the mentioned conditions.
Even then, the platform doesn’t always terminate the query and you face CPU limits being exceeded instead of the selectivity exception. I have a hunch this happens when the platform is forced to perform some post-query, in-memory filtering to fully apply all the conditions in the WHERE clause.