I just found this MSDN article about optimizing your queries. Besides good advice on how to create optimal queries, you can also instruct Active Directory to log expensive queries and even control the threshold value of when a query is expensive!
Furthermore, the ANR search is explained e.g. how you can search for 'Sam' when you do not know whether it is a name, a SAM account name etc. Just like the GUI search in Users and Computers.
And while you are at it, I can also recommend reading How Active Directory Searches Work.