In addition to what Justin Cave already wrote about PostgreSQL, there is a new feature in PostgreSQL 9.1 to speed up any search with
~~*). You can now use the operator classes provided by the module pg_trgm with a GIN or GiST index to speed up
LIKE expressions that are not left-anchored. To install the extension, run once per database:
CREATE EXTENSION pg_trgm;
Create an index of the form
CREATE INDEX tbl_col_gin_trgm_idx ON tbl USING gin (col gin_trgm_ops);
CREATE INDEX tbl_col_gist_trgm_idx ON tbl USING gist (col gist_trgm_ops);
Creating and maintaining a GIN or GiST index carries a cost, but if your table is not heavily written, this is a great feature for you.
Depesz has written an excellent article in his blog about the new feature.
GIN or GiST?
These two quotes from the manual should provide some guidance
The choice between GiST and GIN indexing depends on the relative
performance characteristics of GiST and GIN, which are discussed
elsewhere. As a rule of thumb, a GIN index is faster to search than a
GiST index, but slower to build or update; so GIN is better suited for
static data and GiST for often-updated data.
But, when working with the similarity operator
This can be implemented quite efficiently by GiST indexes, but not by