An answer to this question on Stack Overflow.

Question

Some advice needed....

I've seen a lot of discussion about different approaches to performing an AJAX live search where an autocomplete function is used to suggest search terms. Like on the Google or YouTube.

Some tutorials suggest using AJAX to get results from an XML file. Some suggest querying the database directly. There seems to be a lot of conflicting advice on which approach to take - but no clear consensus on the pros/cons of each.

Lets say I have a table of structure:

ID   TITLE   AUTHOR   LINK

I want to have a search box that autocompletes to provide suggestions on the Title. The table is large - 100000+ rows.

What's the best approach:

1. Query DB directly on each keystroke (probably set up a function to limit # server requests per user per second).

2. Query an XML file. Is this more efficient? Do I risk overloading the server if I query the DB directly?

3. Something else?

Could someone summarise the things that need to be considered? If you have an AJAX live search on your site what approach do you take?

Answer

First off, 100,000+ rows is a small database. Computers today are fast, they have large amounts of RAM, they have speedy buses. But, even if it weren't for all this, a properly index database is going to use something like a binary search tree, or a more advanced variant, to ensure that searches happen in O(log N) time, or faster. For a 100,000 row database, this means the desired element will be found in at most 17 comparisons. Jacking this up to 10,000,000 rows requires only 23 comparisons. So, in this sense, size is hardly an issue.

How are you going to read that XML file in? Databases are well-engineered pieces of software often with years of testing, debugging, and optimization. And, if you're not happy with the DB as it comes, often times there are extensions or modifications you can perform to rip more efficiency out of the DB. For instance, Facebook takes about 60 million queries per second, and they're running on MySQL.

Your XML file, by comparison, doesn't have indexing at the beginning, so it requires a linear search (in O(N) time) each time you read it. File I/O is relatively slow and linear searches are slow.

Your database is also designed to take hits from many users at once without grumbling. Your OS may or may not have been designed to handle simultaneous access by many users to the same file.

A case in which the XML option may be better is if your DB is on a different server and there's significant lag time. In this case, you could look into using SQLite or try to optimize your connection to the DB.