I would suggest another approach. Instead of hitting the database every single keystroke or after a particular interval, why not hit the database one time on page load, pull down your dataset of possibilities, and filter off of that? Doing that would be nearly instantaneous.
It's a few years old, but this article may be of interest to you as well:
Here is a small excerpt:
There was one optimization we made to our AutoComplete configuration
that was particularly effective. Regardless of how much we optimized
our search method, we could never get results to return in less than
200ms (even for trivially small numbers of contacts). After a lot of
profiling and hair pulling, we found the queryDelay setting. This is
set to 200ms by default, and artificially delays every search in order
to reduce UI flicker for quick typists. After setting that to 0, we
found our search times improved dramatically.