In Active Directory, using more specific matching criteria tends to boost search performance. This is because Active Directory evaluates all predicates, identifies the indices, and then picks one index that it considers most likely to yield the smallest set of returned values.
When possible, query on indexed attributes. Stay away from searching for text in the middle and on the end of a string. For example, "cn=*hille*" or "cn=*larouse".