Sequential scan on FK join

All,

I can see why the query below is slow.  The lead table is 34 million rows,
and a sequential scan always takes 3+ minutes.  Mailing_id is the PK for
mailing and is constrained as a foreign key (NULLS allowed) in lead.
There is an index on lead.mailing_id.  I've just run VACUUM ANALYZE on
lead.  I don't understand why it isn't being used.

Thanks for your help,
Martin Nickel

SELECT m.mailcode, l.lead_id
  FROM mailing m
 INNER JOIN lead l ON m.mailing_id = l.mailing_id
 WHERE (m.maildate >= '2005-7-01'::date
         AND m.maildate < '2005-8-01'::date)
-- takes 510,145 ms

EXPLAIN SELECT m.mailcode, l.lead_id
  FROM mailing m
 INNER JOIN lead l ON m.mailing_id = l.mailing_id
 WHERE (m.maildate >= '2005-7-01'::date
         AND m.maildate < '2005-8-01'::date)

Hash Join  (cost=62.13..2001702.55 rows=2711552 width=20)
  Hash Cond: ("outer".mailing_id = "inner".mailing_id)
  ->  Seq Scan on lead l  (cost=0.00..1804198.60 rows=34065260 width=8)
  ->  Hash  (cost=61.22..61.22 rows=362 width=20)
        ->  Index Scan using mailing_maildate_idx on mailing m  (cost=0.00..61.22 rows=362 width=20)
              Index Cond: ((maildate >= '2005-07-01'::date) AND (maildate < '2005-08-01'::date))