switchover between index and sequential scans - Mailing list pgsql-performance

Hi.

I have a table with 1.8M rows on a Postgres 8.1.4 server, and I'm
executing a query which looks like:

    select count(*) from header_fields where message in
    (select message from mailbox_messages limit N);

I've found that when N==75, the query uses a fast index scan, but when
N==100, it switches to a seqscan instead. Here are the plans, first the
fast query (which retrieves 1306 rows):

> explain analyse select count(*) from header_fields where message in (select message from mailbox_messages limit 75);

 Aggregate  (cost=84873.57..84873.58 rows=1 width=0) (actual time=940.513..940.516 rows=1 loops=1)
   ->  Nested Loop  (cost=2.25..84812.59 rows=24391 width=0) (actual time=53.235..935.743 rows=1306 loops=1)
         ->  HashAggregate  (cost=2.25..3.00 rows=75 width=4) (actual time=1.351..1.969 rows=75 loops=1)
               ->  Limit  (cost=0.00..1.31 rows=75 width=4) (actual time=0.096..0.929 rows=75 loops=1)
                     ->  Seq Scan on mailbox_messages  (cost=0.00..1912.10 rows=109410 width=4) (actual
time=0.087..0.513rows=75 loops=1) 
         ->  Index Scan using header_fields_message_key on header_fields  (cost=0.00..1126.73 rows=325 width=4) (actual
time=9.003..12.330rows=17 loops=75) 
               Index Cond: (header_fields.message = "outer".message)
 Total runtime: 942.535 ms

And the slow query (which fetches 1834 rows):

> explain analyse select count(*) from header_fields where message in (select message from mailbox_messages limit 100);

 Aggregate  (cost=95175.20..95175.21 rows=1 width=0) (actual time=36670.432..36670.435 rows=1 loops=1)
   ->  Hash IN Join  (cost=3.00..95093.89 rows=32522 width=0) (actual time=27.620..36662.768 rows=1834 loops=1)
         Hash Cond: ("outer".message = "inner".message)
         ->  Seq Scan on header_fields  (cost=0.00..85706.78 rows=1811778 width=4) (actual time=22.505..29281.553
rows=1812184loops=1) 
         ->  Hash  (cost=2.75..2.75 rows=100 width=4) (actual time=1.708..1.708 rows=100 loops=1)
               ->  Limit  (cost=0.00..1.75 rows=100 width=4) (actual time=0.033..1.182 rows=100 loops=1)
                     ->  Seq Scan on mailbox_messages  (cost=0.00..1912.10 rows=109410 width=4) (actual
time=0.023..0.633rows=100 loops=1) 
 Total runtime: 36670.732 ms

(If I set enable_seqscan=off, just to see what happens, then it uses the
first plan, and executes much faster.)

I'd like to understand why this happens, although the problem doesn't
seem to exist with 8.3. The number of rows retrieved in each case is a
tiny fraction of the table size, so what causes the decision to change
between 75 and 100?

This machine has only 512MB of RAM, and is running FreeBSD 5.4. It has
shared_buffers=3072, effective_cache_size=25000, work_mem=sort_mem=2048.
Changing the last two doesn't seem to have any effect on the plan.

Thanks.

-- ams