Q:

What is a good way to index for such a query?

Jeff mentions in http://blog.stackoverflow.com/2011/03/redesigned-users-page/ that

Searches are “match anywhere” again, but the minimum match is now 3 characters.

Excellent stuff! This was "broken" for quite a while due to the performance of a LIKE match, and the fact that fulltext searching is inexactl (for example, initials in a user name would be too short to feature in any fulltext index).
There must be a way to to this and I have an idea, but I would like to see if anyone already has a solution (alternative) for this challenge.
Sample query:
SELECT TOP 36 *
FROM users
WHERE nickname LIKE '%' + @search + '%'

Note: even though the tag is sql-server due to maximum of 5 tags, I am more than happy to investigate solutions in other RDBMS for portability.

A:

Postgres at least recently added a trigram-matching solution to its standard modules. It rewrites a LIKE query into multiple trigram-matching queries. Unfortunately, the index sizes tend to be huge.
There is also Wildspeed, which also suffers from huge indices. I guess the size depends much on column length.

