SOQL queries must be selective, particularly for queries inside triggers for the best performance. To avoid long execution times, non-selective SOQL queries may be terminated by the system. Developers will receive an error message when a non-selective query in a trigger executes against an object that contains more than 200,000 records.

Query Plan in Salesforce
The new Query Plan tool in the Developer Console can help speed up SOQL queries done over large volumes. Use the Query Plan tool to optimize and speed up queries done over large volumes. Check the below link for more details

https://www.infallibletechie.com/2015/07/query-plan-in-salesforce.html

The following fields are indexed by default that makes SOQL selective:

1. Primary keys (Id, Name and Owner fields).
2. Foreign keys (Lookup or Master-Detail relationship fields).
3. Audit dates (such as SystemModStamp).
4. Custom fields marked as External ID or Unique.

You can contact Salesforce.com support to make a field indexed(custom index).

Even indexing can fail your SOQL. So, consider the threshold. For standard index, 30% for first 1 million and 15% after that. For custom index 10% for first 1 million and 5% after that.

Check the below link for Salesforce SOQL Cheat Sheet

http://resources.docs.salesforce.com/194/0/en-us/sfdc/pdf/salesforce_query_search_optimization_developer_cheatsheet.pdf