Q: Why is my SOQL query running so slowly?

A: If you have any of the following things in your query, Salesforce’s query optimizer can’t leverage indexed fields:

• !=
• NOT LIKE
• EXCLUDES
• [TEXTFIELD] >
• [TEXTFIELD] <
• [TEXTFIELD] >=
• [TEXTFIELD] <=
• LIKE '%[string]'

• cross-object formula fields

or, as the Salesforcies put it:

Full Query & Search Optimization Cheat Sheet is here!