Include only the required fields in the list of Display and Search Fields. Limit the maximum number of records returned by lookup search. Define context, basic filters, and advanced filters as appropriate to the business requirements, to return the most relevant records. When using Is Null or Is Not Null or Contains operators in any filter, include at least one more filter condition such as picklist/check box with Equals/Not Equal operator, to make the query more specific and restrictive (and to avoid potential non-selective query failure, when the lookup object has large number of records).

For lookup queries on objects that have very large number of records, consider getting custom index created for appropriate search fields.