query planner woes

hi all,

I've constructed a simple query which takes too long
to finish. EXPLAIN ANALYZE ( all data shown below )
reports that at one stage there are >40K rows ( on a toy database,
>2M on the real one), and while I undertstand that this is the
most probable cause of the slowness, I cannot think of any change to
the query to aviod this. Any help?

Thanks,
Dmitry

mts=# \d addresses
Table "public.addresses"
Column | Type |
Modifiers
---------+--------------------------+-----------------------------------------------------------
id | integer | not null default
nextval('public.addresses_id_seq'::text)
address | text | not null
Indexes:
"addresses_pkey" primary key, btree (id)
"addresses_idx_address" btree (address)

mts=# \d recipients
Table "public.recipients"
Column | Type |
Modifiers
---------+--------------------------+------------------------------------------------------------
id | integer | not null default
nextval('public.recipients_id_seq'::text)
msgto | integer | not null
Indexes:
"recipients_pkey" primary key, btree (id)
"recipients_idx_msgto" btree (msgto)

mts=# explain analyze select *
mts-# from recipients,addresses
mts-# where addresses.address ~ '@cat' and
mts-# recipients.msgto = addresses.id;
QUERY
PLAN
-----------------------------------------------------------------------------------------------------------------------
Hash Join (cost=535.70..1603.96 rows=352 width=63)
(actual time=88.387..422.922 rows=576 loops=1)
Hash Cond: ("outer".msgto = "inner".id)
-> Seq Scan on recipients (cost=0.00..737.42 rows=43642 width=24)
(actual time=0.012..178.258 rows=43642
loops=1)
^^^^^
-> Hash (cost=535.34..535.34 rows=147 width=39)
(actual time=87.866..87.866 rows=0 loops=1)
-> Seq Scan on addresses (cost=0.00..535.34 rows=147 width=39)
(actual time=0.958..87.806 rows=3 loops=1)
Filter: (address ~ '@cat'::text)
Total runtime: 425.061 ms
(7 rows)

mts# select count(*) from recipients,addresses where
addresses.address ~ '@cat' and recipients.msgto = addresses.id;
count
-----
576