It's not that fast, Facebook actually starts the search query from the second letter (about 174 ms), before that, it uses the prefetched cache of first degree friends and apps.