Execution plan in simple query in PgSQL depends on offset clause, why?

Question

Update on 2013-01-16 11:08: see below

I am working on PostgreSQL 8.4.14 with the following table fed with 53k lines:

CREATE TABLE botany.taxon_data_cache (
  taxon_id int NOT NULL,
  designation_minimalist text NOT NULL,
  designation_conventional text NOT NULL,
  designation_html text NOT NULL,
  picture_directory text NOT NULL,
  CONSTRAINT pk_taxon_data_cache PRIMARY KEY (taxon_id),
  CONSTRAINT ak_taxon_data_cache_1 UNIQUE (picture_directory)
);
CREATE INDEX idx_taxon_data_cache_designation_conventional ON botany.taxon_data_cache (designation_conventional);

I do not understand, why PostgreSQL choose a different execution plan depending on the OFFSET clause value in my query. Can anyone give me a clue?

Moreover, the query 2 below is executed very inefficiently, due to the non-use of the index I guess. Why such a poor plan decision from PostgreSQL?

Query 1:

EXPLAIN ANALYSE SELECT botany.taxon_data_cache.taxon_id
FROM botany.taxon_data_cache 
ORDER BY botany.taxon_data_cache.designation_conventional 
LIMIT 20 OFFSET 40000

"Limit  (cost=5388.93..5392.53 rows=20 width=24) (actual time=14.599..14.609 rows=20 loops=1)"
"  ->  Index Scan using idx_taxon_data_cache_designation_conventional on taxon_data_cache  (cost=0.00..9671.16 rows=53839 width=24) (actual time=0.020..12.887 rows=30020 loops=1)"
"Total runtime: 14.648 ms"

Query 2:

EXPLAIN ANALYSE SELECT botany.taxon_data_cache.taxon_id
FROM botany.taxon_data_cache 
ORDER BY botany.taxon_data_cache.designation_conventional 
LIMIT 20 OFFSET 50000

"Limit  (cost=7984.16..7984.21 rows=20 width=24) (actual time=1739.832..1739.949 rows=20 loops=1)"
"  ->  Sort  (cost=7859.16..7993.75 rows=53839 width=24) (actual time=1425.285..1737.260 rows=50020 loops=1)"
"        Sort Key: designation_conventional"
"        Sort Method:  external merge  Disk: 1808kB"
"        ->  Seq Scan on taxon_data_cache  (cost=0.00..2522.39 rows=53839 width=24) (actual time=0.012..15.457 rows=53839 loops=1)"
"Total runtime: 1748.912 ms"

Update of 2013-01-16 11:08: new results following the first answers

I am still working on PostgreSQL 8.4.14 with the same table structure fed with exactly 330780 lines:

CREATE TABLE botany.taxon_data_cache2 (
  taxon_id id NOT NULL,
  designation_minimalist text NOT NULL,
  designation_conventional text NOT NULL,
  designation_html text NOT NULL,
  picture_directory text NOT NULL,
  CONSTRAINT pk_taxon_data_cache2 PRIMARY KEY (taxon_id),
  CONSTRAINT ak_taxon_data_cache2_1 UNIQUE (picture_directory)
);
CREATE INDEX idx_taxon_data_cache2_designation_conventional ON botany.taxon_data_cache2 (designation_conventional);

The planner change its mind when changing from OFFSET 330342 to 330343, here the results:

-- Defaults: work_mem = '1MB' and random_page_cost = 4
EXPLAIN ANALYSE SELECT botany.taxon_data_cache2.taxon_id
FROM botany.taxon_data_cache2 
ORDER BY botany.taxon_data_cache2.designation_conventional 
LIMIT 20 OFFSET 330342

"Limit  (cost=60276.11..60279.76 rows=20 width=24) (actual time=296.222..296.253 rows=20 loops=1)"
"  ->  Index Scan using idx_taxon_data_cache2_designation_conventional on taxon_data_cache2  (cost=0.00..60356.03 rows=330780 width=24) (actual time=0.114..278.176 rows=330362 loops=1)"
"Total runtime: 296.356 ms"


-- Defaults: work_mem = '1MB' and random_page_cost = 4
EXPLAIN ANALYSE SELECT botany.taxon_data_cache2.taxon_id
FROM botany.taxon_data_cache2 
ORDER BY botany.taxon_data_cache2.designation_conventional 
LIMIT 20 OFFSET 330343

"Limit  (cost=60279.76..60279.81 rows=20 width=24) (actual time=14015.919..14016.032 rows=20 loops=1)"
"  ->  Sort  (cost=59453.90..60280.85 rows=330780 width=24) (actual time=12057.516..13997.024 rows=330363 loops=1)"
"        Sort Key: designation_conventional"
"        Sort Method:  external merge  Disk: 11248kB"
"        ->  Seq Scan on taxon_data_cache2  (cost=0.00..15555.80 rows=330780 width=24) (actual time=0.025..203.982 rows=330780 loops=1)"
"Total runtime: 14063.915 ms"


-- Defaults: work_mem = '1MB' and random_page_cost = 4
SET work_mem = '200MB';
EXPLAIN ANALYSE SELECT botany.taxon_data_cache2.taxon_id
FROM botany.taxon_data_cache2 
ORDER BY botany.taxon_data_cache2.designation_conventional 
LIMIT 20 OFFSET 330343

"Limit  (cost=46706.76..46706.81 rows=20 width=24) (actual time=8865.674..8865.679 rows=20 loops=1)"
"  ->  Sort  (cost=45880.90..46707.85 rows=330780 width=24) (actual time=8820.353..8848.369 rows=330363 loops=1)"
"        Sort Key: designation_conventional"
"        Sort Method:  quicksort  Memory: 37754kB"
"        ->  Seq Scan on taxon_data_cache2  (cost=0.00..15555.80 rows=330780 width=24) (actual time=0.037..148.738 rows=330780 loops=1)"
"Total runtime: 8872.271 ms"


-- Defaults: work_mem = '1MB' and random_page_cost = 4
SET random_page_cost = 3.0;
EXPLAIN ANALYSE SELECT botany.taxon_data_cache2.taxon_id
FROM botany.taxon_data_cache2 
ORDER BY botany.taxon_data_cache2.designation_conventional 
LIMIT 20 OFFSET 330343

"Limit  (cost=46465.88..46468.69 rows=20 width=24) (actual time=306.519..306.554 rows=20 loops=1)"
"  ->  Index Scan using idx_taxon_data_cache2_designation_conventional on taxon_data_cache2  (cost=0.00..46527.34 rows=330780 width=24) (actual time=0.180..288.228 rows=330363 loops=1)"
"Total runtime: 306.643 ms"

As we can see, work_mem does not have any influence but random_page_cost does. The PostgreSQL server is running on my local machine and I use an SSD drive, not a HDD drive.

Answer 1

While this may be surprising indeed, the documentation tells you to expect this phenomenon with OFFSET and LIMIT.

The planner chooses between possible plans based on a simple cost calculation (this is shown in the plan above). In your case, when it chooses an index, PostgreSQL first tries to find which rows to collect, then reads those rows (to be precise, the pages containing the rows) and only then picks the desired value. Sometimes it is simply more efficient to go for the pages directly, resulting in a sequential scan. Or at least, PostgreSQL thinks that it is faster... Unfortunately, in your case, the results of a Seq Scan does not fit into work_mem, the space reserved for sorting, and starts using a temporary file on disk instead. And this is where you lose so much time.

A few things you can do:

• increase work_mem to at least 2MB
• nudge PostgreSQL to prefer indexes by lowering random_page_cost
• if you have the option of upgrading to 9.2, then you can take advantage of covering indexes by defining an index on (designation_conventional, taxon_id)

By the way, are you sure that the first query and its plan match? There is an inconsistency in the row numbers.