pg_trgm performance

I've got a table with a few million rows, consisting of a single text
column.  The average length is about 17 characters.  For the sake of
an experiment, I put a trigram index on that table.  Unfortunately, %
queries without smallish LIMITs are ridiculously slow (they take
longer than an hour).  A full table scan with a "WHERE similarity(...)
>= 0.4" clause completes in just a couple of minutes.  The queries
only select a few hundred rows, so an index scan has got a real chance
to be faster than a sequential scan.

Am I missing something?  Or are trigrams just a poor match for my data
set?  Are the individual strings too long, maybe?

(This is with PostgreSQL 8.2.0, BTW.)

--
Florian Weimer                <fweimer@bfk.de>
BFK edv-consulting GmbH       http://www.bfk.de/
Kriegsstraße 100              tel: +49-721-96201-1
D-76133 Karlsruhe             fax: +49-721-96201-99