In addition to what Sergey said if DELETED is set ON this will also slow down the locate,
so for fastest possible locate:

set order to
set deleted off
locate for not deleted() and ......

*restore order
*restore deleted status