A project I worked on used trigram indexes a few years ago to solve the autocomplete problem. They are AMAZING - they basically allow you to run LIKE queries with wildcards anywhere in the string (as opposed to suffix-only-wildcards) against an index.

An autocomplete search for e.g. "rub rai" becomes the following SQL query:

    select * from topics where name ilike "%rub%rai%";

Which, thanks to the magic of trigram indexes returns in just a few ms, even against hundreds of thousands of rows. Without trigram indexes, the same query would be a full scan and would be too slow to justify hooking up to a search-as-you-type UI.

    create extension pg_trgm;
    create index topic_name_gin on topics using gin (name gin_trgm_ops);