Thread: switchover between index and sequential scans

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

"Abhijit Menon-Sen" <ams@oryx.com> writes:

>          ->  Index Scan using header_fields_message_key on header_fields  (cost=0.00..1126.73 rows=325 width=4)
(actualtime=9.003..12.330 rows=17 loops=75) 
>                Index Cond: (header_fields.message = "outer".message)
>
>          ->  Seq Scan on header_fields  (cost=0.00..85706.78 rows=1811778 width=4) (actual time=22.505..29281.553
rows=1812184loops=1) 

It looks to me like it's overestimating the number of rows in the index scan
by 20x and it's overestimating the cost of random accesses by about 100%.
Combined it's overestimating the cost of the index scan by about 40x.

> 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.

You could try dramatically increasing effective_cache_size to try to convince
it that most of the random accesses are cached. Or you could reach for the
bigger hammer and reduce random_page_cost by about half.

Also, if this box is dedicated you could make use of more than 24M for shared
buffers. Probably something in the region 64M-128M if your database is large
enough to warrant it.

And increase the statistics target on header_fields and re-analyze?

--
  Gregory Stark
  EnterpriseDB          http://www.enterprisedb.com
  Ask me about EnterpriseDB's RemoteDBA services!

Hi Greg.

At 2008-07-03 11:05:46 +0100, stark@enterprisedb.com wrote:
>
> And increase the statistics target on header_fields and re-analyze?

Aha! Thanks for the tip. I just changed the default_statistics_target to
100 (from 10) and ANALYSEd header_fields and mailbox_messages, and now
it ALWAYS uses the index scan if I specify a LIMIT. That is,

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

always uses the index scan on header_fields_message_key, even when N is
equal to the number of rows in mailbox_messages (109410).

 Aggregate  (cost=30779.98..30779.99 rows=1 width=0) (actual time=175040.923..175040.926 rows=1 loops=1)
   ->  Nested Loop  (cost=3279.73..30760.93 rows=7617 width=0) (actual time=2114.426..169137.088 rows=1771029 loops=1)
         ->  HashAggregate  (cost=3279.73..3281.73 rows=200 width=4) (actual time=2076.662..2649.541 rows=109365
loops=1)
               ->  Limit  (cost=0.00..1912.10 rows=109410 width=4) (actual time=0.029..1386.128 rows=109410 loops=1)
                     ->  Seq Scan on mailbox_messages  (cost=0.00..1912.10 rows=109410 width=4) (actual
time=0.022..744.190rows=109410 loops=1) 
         ->  Index Scan using header_fields_message_key on header_fields  (cost=0.00..136.92 rows=38 width=4) (actual
time=0.678..1.416rows=16 loops=109365) 
               Index Cond: (header_fields.message = "outer".message)
 Total runtime: 175041.496 ms

Note the massive _under_estimation in the hash aggregate and the
nestloop. If I don't specify a limit, it'll use a seq scan again.

Very interesting.

-- ams