Non-selective query against large object type (more than 100000 rows)

Non-selective query against large object type (more than 100000 rows). Consider an indexed filter or contact salesforce.com about custom indexing.
Even if a field is indexed a filter might still not be selective when:
1. The filter value includes null (for instance binding with a list that contains null)
2. Data skew exists whereby the number of matching rows is very large (for instance, filtering for a particular foreign key value that occurs many times)

The above error occurs in production where we have approx 138000 records. We have couple of methods to get this rectified like optimizing the query, null check, making the field external id or unique. Somehow the query Threshold value goes out of the limit that is why the query is not selective. Any help would be appreciated.