1

This is a query that occurs reasonably frequently:

SELECT DISTINCT id, published_year, first_author 
FROM publication 
ORDER BY published_year DESC NULLS LAST 
LIMIT 10;

There is an index that could be used for this:

CREATE INDEX publication_published_year_idcombineddesc2_btree 
   ON public.publication USING btree (published_year DESC NULLS LAST, id)

However, it is not used, and thus the query lasts 30-40 seconds:

EXPLAIN ANALYZE SELECT DISTINCT id, published_year, first_author FROM publication ORDER BY published_year DESC NULLS LAST LIMIT 10;
                                                              QUERY PLAN                                                                  
----------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=3527756.39..3527756.49 rows=10 width=23) (actual time=33860.282..33860.292 rows=10 loops=1)
   ->  Unique  (cost=3527756.39..3623290.85 rows=9553446 width=23) (actual time=33860.280..33860.288 rows=10 loops=1)
         ->  Sort  (cost=3527756.39..3551640.01 rows=9553446 width=23) (actual time=33860.278..33860.281 rows=10 loops=1)
               Sort Key: published_year DESC NULLS LAST, id, first_author
               Sort Method: external merge  Disk: 310440kB
               ->  Seq Scan on publication  (cost=0.00..2224226.46 rows=9553446 width=23) (actual time=0.036..20842.499 rows=9553526 loops=1)
 Planning time: 1.157 ms
 Execution time: 33945.457 ms

Now, if I remove the first_author or DISTINCT, the query runs nice and fast:

EXPLAIN ANALYZE SELECT DISTINCT id, published_year FROM publication ORDER BY published_year DESC NULLS LAST LIMIT 80;
                                                                                      QUERY PLAN                                                                                          
----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..4.57 rows=80 width=10) (actual time=0.055..0.250 rows=80 loops=1)
   ->  Unique  (cost=0.43..493764.18 rows=9553446 width=10) (actual time=0.053..0.236 rows=80 loops=1)
         ->  Index Only Scan using publication_published_year_idcombineddesc2_btree on publication  (cost=0.43..445996.95 rows=9553446 width=10) (actual time=0.051..0.204 rows=80 loops=1)
               Heap Fetches: 1
 Planning time: 1.487 ms
 Execution time: 0.300 ms

EXPLAIN ANALYZE SELECT id, published_year, first_author FROM publication ORDER BY published_year DESC NULLS LAST LIMIT 10;
                                                                                 QUERY PLAN                                                                                     
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.43..9.63 rows=10 width=23) (actual time=0.062..0.190 rows=10 loops=1)
   ->  Index Scan using publication_published_year_idcombineddesc2_btree on publication  (cost=0.43..8787896.00 rows=9553446 width=23) (actual time=0.061..0.186 rows=10 loops=1)
 Planning time: 1.380 ms
 Execution time: 0.223 ms

So my question is: is there a way to coerce the query planner to use an index in the first case?

UPDATE:

I tried to change random_page_cost, cursor_tuple_fraction (to various values, even to 0) and enable_seqscan to off; to no avail.

UPDATE 2:

I think I had a revelation about the "why first_author is included in the sort key": the DISTINCT keyword affects the whole retrieved tuple, so Postgres thinks that there may be duplicate (id, published_year, first_author) tuple, thus needs to check all potential such tuples so it does not miss one. Because it misses the fact that id is the primary key and thus unique, and so any tuple that contains it without joins in the FROM part is also necessarily unique. Even disregarding the above fact, it could take a gamble and get some (id, published_year) pairs from the appropriately sorted index, and start retrieving the corresponding first_author from the disk and select some unique from them (they are already in good order according to the query), and if the limit is not reached then try again with some more from the index, etc.

It would be nice to be able to force that behaviour, but it does not seem likely, thus at the end we will need to change the query generator to omit DISTINCT if there is no join in the query and it contains a primary key.

7
  • You may try to add INCLUDE first_author to the index definition.
    – Akina
    May 13, 2020 at 10:56
  • But why do I need it? It would be trivial to search out the 10 ids using the index in the appropriate order, and then fetch the first_author column from the table. Which it actually does if I omit the DISTINCT. It would also enlarge the index.
    – P.Péter
    May 13, 2020 at 11:01
  • Moreover, I am using postgres 10, where INCLUDE is not available. I updated the tags.
    – P.Péter
    May 13, 2020 at 11:05
  • When builder builds the plan it doesn't takes into account that LIMIT is used, it seems. So it decides that scanning the table only is better then seeking index and then accesing the table for a field not included into the index. I don't know why... does your version allows to force index usage?
    – Akina
    May 13, 2020 at 11:09
  • The distinct seems dubious to begin with as id is typically used for the name of a primary (or unique) key column.
    – user1822
    May 13, 2020 at 11:14

2 Answers 2

1

Why just take things by the smooth handle, and build the index that works?:

CREATE INDEX ON public.publication (published_year DESC NULLS LAST, id, first_author);

You can then get rid of the other one, as it serves no purpose that can't be served by this one (the other one may be slightly smaller, but that is generally not significant)

The version of PostgreSQL currently being developed, v13, introduces "incremental sort", which does more or less what you want with your existing index. But it still won't be as fast as just building the right index in the first place.

1
  • Well, I will keep the possibility of upgrading to v13 in mind. It is still OK if the incremental sort is 10 times slower than the normal index scan. It would mean that the query runs in about 200ms, instead of the 30000ms of the full table scan. Currently, we are a bit tight on space so rather that than inflating the index.
    – P.Péter
    May 13, 2020 at 16:09
0

You can force PostgreSQL to use the index in the first query, but that would probably be slower than the explicit sort.

The problem is that the index scan has to visit the table for each row to retrieve the first_author column. With an index scan, that would mean hitting the same table block many times with random reads, which is very inefficient.

In the second query, all the required information is stored in the index, so PostgreSQL can perform an index only scan, which does not visit the table and is fast.

Adding the column to the index would solve the problem:

CREATE INDEX ON public.publication (published_year NULLS FIRST)
   INCLUDE (first_author, id);

With PostgreSQL versions older than v11, you have to add the columns to the index key.

6
  • No, it is not slower. It is significantly faster. SELECT DISTINCT id, published_year, first_author FROM publication WHERE (id, published_year) IN (SELECT DISTINCT id, published_year FROM publication ORDER BY published_year DESC NULLS LAST LIMIT 10); runs in 10ms, and does just that. 10 table page reads cannot be slower than a full table scan on a 70GB table...
    – P.Péter
    May 13, 2020 at 14:03
  • That doesn't actually work, it still uses the same plan.
    – jjanes
    May 13, 2020 at 15:39
  • @P.Péter Running a different query is not a good test, you would test the original query with enable_sort = off to see if the index scan is really faster. If it is, first try ANALYZE on the query and see if that changes the plan. However, I cannot imagine that the index scan would not be cheaper with random_page_cost = 0, so there is something that I don't see. May 13, 2020 at 19:24
  • @jjanes No, it does not use the same plan. See: pastebin.com/9UWQTmgN I can imagine it uses the same plan on a very small table, where seq scan is also fast.
    – P.Péter
    May 19, 2020 at 12:00
  • @LaurenzAlbe I tried enable_sort=off and enable_seqscan=off, and it still sequential scans and sorts... Also tried setting random_page_cost and seq_page_cost to ridiculous values (10^20), but postgres refuses to change the plan.
    – P.Péter
    May 19, 2020 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.