Building autosuggest

I'm building an autosuggest. For now the destination app is desktop, but the idea is to build it as strong as posible and then maybe include it in a web.

Right now I'm at the very beginning of the project: thinking the database (SQL Server 2008)

The autosuggest is going to be from a table of ~40.000.000 of rows.

Right now my options are: full text search or build a table like I'll describe now:

My autosuggest items:

a b c
1 2 3
x y z

The resulting table:

a b c              a b c
a b c              a c b
a b c              b a c
a b c         开发者_如何学JAVA     b c a
a b c              c a b
a b c              c b a

And so for each item.

Now my question:

Wich of those is best when I'm looking to minimize the search of the items for the autosuggest list? Is there any other better?

Thanks!

Diego

---

In my opinion FULLTEXT would be better, even if you only need exact matches.

However, even if you decide not to use FULLTEXT why do you need to index all permutations? You can index them once in alphabetical order (a, b, c) and just rearrange the items in the same order before providing them as a parameter to the query.

That is, you should always search for C, D, O even if your query says O, C, D

---

So... you want to query a table with 40 millions records based on partial input, matching any part of the column (or even multiple columns), probably from many users simultaneously ... and I'm assuming you are expecting sub-second response times.

Your DB server better be a real beast.

I'd strongly advice to rethink your plan or at least limit the choices users have, like restricting the search to only beginning of the column, etc.
But if you decide to go on with this, fulltext is out of the question, unless you include some kind of funny wait cursor in your application to entertain users while the autosuggestion query is running.