A query is not selective simply because it includes a where clause.
Per the SalesForce docs on the topic, Working with Very Large SOQL Queries specifically the section 'More Efficient SOQL Queries', a query is selective when it meets these criteria:
- 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.
- The selectivity threshold is 10% of the records for the first million records and less than 5% of the records after the first million records, up to a maximum of 333,000 records. In some circumstances, for example with a query filter that is an indexed standard field, the threshold may be higher. Also, the selectivity threshold is subject to change.
Because your query is on a field which is marked as an ExternalId, and thus indexed, it will be used in determining if the query meets the selectivity threshold. It is possible that your query could return a great enough number of rows to become non-selective. (Thresholds for this scenario are in the linked article as well.)
Be sure to note the items in the 'Custom Index Considerations for Selective SOQL Queries' section of the linked article.