Why does postgres choose to sort instead of scanning the index?

Question

I have the following table:

# \d service
       Table "public.service"
   Column    |   Type   | Modifiers 
-------------+----------+-----------
 customer_id | integer  | not null
 date        | date     | not null
 service     | smallint | not null
 has         | boolean  | 
Indexes:
    "service_customer_id_idx" btree (customer_id)

# select count(*) from service;
   count   
-----------
 327535416
(1 row)

Time: 75047.508 ms

# select version();
                                                   version                                                

-------------------------------------------------------------------------------------------------------------
 PostgreSQL 9.5.4 on x86_64-redhat-linux-gnu, compiled by gcc (GCC) 6.1.1 20160621 (Red Hat 6.1.1-3), 64-bit
(1 row)

I tried to come up with a query for which it is obviously beneficial to use the index, since the results can be taken directly from the index in the correct order:

# explain (analyze,verbose) select customer_id from service order by customer_id;
                                                               QUERY PLAN                                                               
----------------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=64804990.92..65623829.48 rows=327535424 width=4) (actual time=487209.250..546557.064 rows=327535416 loops=1)
   Output: customer_id
   Sort Key: service.customer_id
   Sort Method: external merge  Disk: 4482448kB
   ->  Seq Scan on public.service  (cost=0.00..5045816.24 rows=327535424 width=4) (actual time=2.705..49659.173 rows=327535416 loops=1)
         Output: customer_id
 Planning time: 0.093 ms
 Execution time: 554914.731 ms
(8 rows)

Time: 554919.649 ms

As you see, Postgres prefers to do a sequential scan and then sort the results.

Interestingly, if I add a limit clause, it does decide to use the index:

# explain (analyze,verbose) select customer_id from service order by customer_id limit 10;
                                                                             QUERY PLAN                                                                              
---------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.57..32.97 rows=10 width=4) (actual time=2.509..2.773 rows=10 loops=1)
   Output: customer_id
   ->  Index Only Scan using service_customer_id_idx on public.service  (cost=0.57..1061141647.19 rows=327535424 width=4) (actual time=2.503..2.760 rows=10 loops=1)
         Output: customer_id
         Heap Fetches: 10
 Planning time: 4.285 ms
 Execution time: 2.906 ms
(7 rows)

Time: 28.178 ms

Why does Postgres behave this way, and how could I debug this? Is there a way to ask it to show alternative plans and their cost calculations?

Here's the execution with seqscan turned off:

# explain (analyze,verbose) select customer_id from service order by customer_id;
                                                                                QUERY PLAN                                                                                 
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using service_customer_id_idx on public.service  (cost=0.57..1061141647.19 rows=327535424 width=4) (actual time=2.753..346400.896 rows=327535416 loops=1)
   Output: customer_id
   Heap Fetches: 327535416
 Planning time: 1.921 ms
 Execution time: 355637.985 ms
(5 rows)

Time: 355647.367 ms

cohenjo · Accepted Answer · 2016-11-05 19:49:37Z

0

Generally speaking, reading a tuple from an index is more expensive then reading directly from the relation. This is due to the overhead of traversing the tree as well as occasionally reading from the table (due to changes for example)

Thus, if you scan the entire table Postgres will come to the conclusion that it should scan the table. Limiting the scan immediately changes the above as the number of tuples that need scanning is much more limited.

answered Nov 5, 2016 at 19:49

cohenjo

1,1987 silver badges6 bronze badges

Thanks, that's an interesting consideration. I can see how that would apply if there was no order by clause. But it obviously ignores the cost of sorting. Even postgres's own cost model estimates the sort 13x as expensive as the scan, and in reality it is 24x as expensive.
– user109810
Commented Nov 5, 2016 at 23:47
You can alter the session to disable seqscan, it will probably use the index and you could see the estimate for the index. It will be higher... won't be the first time an optimizer was wrong - that's why DBAs still have a job :)
– cohenjo
Commented Nov 5, 2016 at 23:53
You are right (I've updated the post with the results). I do expect the optimizer to be wrong sometimes, but not on such stupidly simple queries. So why does this error happen and how do I fix it?
– user109810
Commented Nov 6, 2016 at 0:50
By the way, I withdraw my earlier claim about 24x — the early measurements were done on a busy system; I've updated them since. I'm also surprised that index scan appears to be 7 times as slow as seq scan, although the sort time still compensates for that.
– user109810
Commented Nov 6, 2016 at 0:59
Btw, you have the option to tune this by changing the random_page_cost (lower it to favor indexes) See: postgresql.org/docs/9.5/static/runtime-config-query.html
– cohenjo
Commented Nov 6, 2016 at 5:13

| Show 1 more comment

Stack Exchange Network

Why does postgres choose to sort instead of scanning the index?

1 Answer 1

Your Answer

Hot Network Questions

Why does postgres choose to sort instead of scanning the index?

1 Answer 1

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions