Auto-completion for names against a SQL database

Question

I have a text field in my web app where I want to do auto-completion (e.g. the user types "St" and I can suggest "Steve"). The names I'm matching against are in a SQL database table of users. My question is, how can I make this happen in a way that will scale to massive amounts of users?

1. There's DB full text search or something like Lucene. Would that even be appropriate for a "starts with" query like this?

2. Is there a way to set up a normal DB index for "starts with" type searches?

3. Any other ideas that I'm totally missing?

Any help would be appreciated. Thanks.

Answer 1

If you have an ordered index on the field you want to autocomplete then it can be used in a "starts with" style query.

Answer 2

These should do the job as long as you have an index on the name column.

SQL Server:

SELECT TOP 10 name FROM names WHERE name LIKE 'St%'

MySQL (according to Bart J):

SELECT name FROM names WHERE name LIKE 'St%' LIMIT 10

Oracle:

SELECT name FROM names WHERE name LIKE 'St%' AND rownum < 10

Answer 3

Most ascending indexes will be used for optimization with a LIKE 'xxx%'-type query. For performance, I would recommend you set a limit to the number of results you try to return from the database:

SELECT TOP 10 LastName
FROM tbl
WHERE LastName LIKE @start + '%'
ORDER BY LastName

There's a limit to the amount of scrolling you want to do.

Answer 4

Check this article on full-text-search in SQL Server.

And this one on the types of indexes there are and when to use them.

Answer 5

Don't do it in SQL...?

Send the list and autocomplete in the browser. This is what we do.

This way, we avoid something like a Hong Kong client -> Switzerland web server -> Switzerland SQL server round-trip per user key press. We do one trip to load the page, then it's all client side.

We have something like 9,000 items in our biggest data set that drives Auto Suggest control (most are far less)

Edit, after comment:

Like I said, most of our lists are far less. However, even loading an extra 200k is better then round-tripping to a database every key press.

The fact that you can round trip implies "intranet", so page load time is also irrelevant. 200k is nothing anyway compared to round trip latency...