Efficient method to request ajax autocomplete on large db table and busy site

Question

We are all familiar with setting autocomplete tags here on SO.

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

A busy site with a large number of users tagged with an autocomplete function requires a lot of requests. Say, at any time, 100 users type an average of 10 characters to search / create their tags. This is similar to many queries in one table and only one aspect of a busy site.

So, you just need to make sure that you have a reasonable delay on the client side before the request is made, or is it smart indexing in the data table, or does it regularly upload data to a more efficient server-side search server?

I would be grateful for any advice.

Using mysql and php.

Answer 1

Save all autocomplete options in memory. You can quickly filter parameters using Trie (for example, this Java implementation ). No matter how many options are available in Trie, it will remain O(1)effective.

Answer 2

Well, you should not ask. This should be cached. Think of it this way. Let's say there are 28,000 tags on SO. Let's say each tag is 128 bytes (this is not the case). This is just 3,584,000 bytes (basically nothing). There are many data structures in memory that can very quickly search for such data.