Found while working on T232040: Add label and description collision detectors for new terms store. The only implementation of EntitiesWithoutTermFinder is SqlEntitiesWithoutTermFinder which uses wb_terms table.
Check if there are indexes on new store tables too.
Needs discussion and decision with product after WikiCon is over.
The problem with new store that it will be very costly to implement this feature on database level. So need to look into alternative and weigh in product feedback on use-cases and importance of this feature.
This is potentially a duplicate of T194144.
As there are more thoughts in the other ticket I'll close this one