>>Yes, EXISTS is a potentially alternative route to take. Unlike inner join or IN ( select ... ) -which both need an aggregate phase-, EXISTS returns a boolean true on first hit and doesn't check the rest.
>>Also, I would have those few provinces in their own table and check from there instead of searching them from a 200K or 2M records (they should be using it as foreign keys).
>
>But, it still requires to check for existance on all master record found. Thus, depending on the result on the number of records, this will require additional checkups in the child table. The WHERE clause benefits of a compound index where the EXISTS cannot.
>
>Is EXISTS still a better route? ...knowing those factors

Yes.
I don't understand why would EXISTS cannot utilise a compound index.