Update: I have found a nicer way of doing autocomplete. Basically, use the string type with the "starting_with" method. See this ticket comment.
Solr is really nice search engine which has the added advantage of being able to return items that you put into the search engine, unlike say, sphinx (which is really fast but only returns the document id).
However, Solr is very complex.
Thankfully, there is a very neat ruby abstraction for Solr, called Sunspot. Given I needed to do autocomplete on it, i.e. "query*" type stuff, I had to fork Sunspot. Here is the relevant change I made to enable wildcard searches with Sunspot:
For those interested in how this works, it uses the q.alt parameter as Sunspot uses the rather "user-friendly" DisMaxRequestHandler, which ignores "*" characters.