Effcient method for ajax autocomplete query on big db table and busy site

Question

We're all familiar with the autocomplete tagging setup here on SO.

I'm wondering what is the most efficient method for querying the tag table in this scenario.

A busy site with many users tagging away with the autocomplete feature requires a lot of querying. Say at any one time there are 100 users typing an average of 10 characters to lookup/create their tags. That seems like a lot of queries on a single table and that's only one aspect of a busy site.

So, is it just a matter of making sure you have a sane delay on the client side before a request is made, or is it smart indexing on the data table, or is it offloading the data on a regular basis to a more efficient server-side lookup store?

I'd appreciate any tips.

Using mysql and php.

Answer 1

Store all the auto-complete options in memory. You can quickly filter the options with a Trie (e.g. this Java implementation). No matter how many options are in a Trie, it will stay O(1) efficiency.

Answer 2

Well, you shouldn't be querying. This should be cached. Think about it like this. Let's say there are 28,000 tags on SO. Let's say each tag is 128 bytes (it's not). That's just 3,584,000 bytes (basically nothing). There are many in-memory data structures that can make it very fast to search through such data.