Text pattern JOINs that use indexes

I'm having a lot of trouble getting JOINs to work well with text
patterns. I have a smallish table (4000 rows) containing prefixes that
I want to inner-join to a large table (500000 rows) of strings. In
other words, I want to look up the few entries in the 500000 row table
which start with the strings in the 4000 row table. PostgreSQL insists
on doing a sequential scan of the large table, even though it is
indexed on the field I'm using for the join.

Anyone got a solution?

Here are the "explains":

explain select * from files where name like 'foo%';
QUERY PLAN
------------------------------------------------------------------------
-----
Index Scan using files_name_key on files (cost=0.00..6.01 rows=1
width=97)
Index Cond: ((name >= 'foo'::text) AND (name < 'fop'::text))
Filter: (name ~~ 'foo%'::text)

explain select * from test join files on files.name like test.filename
|| '%';
QUERY PLAN
---------------------------------------------------------------------
Nested Loop (cost=20.00..9450496.28 rows=1888140 width=129)
Join Filter: ("outer".name ~~ ("inner".filename || '%'::text))
-> Seq Scan on files (cost=0.00..9776.28 rows=377628 width=97)
-> Materialize (cost=20.00..30.00 rows=1000 width=32)
-> Seq Scan on test (cost=0.00..20.00 rows=1000 width=32)