0

Given the following table:

CREATE TABLE chat_message (
    id bigint DEFAULT nextval('public.chat_message_id_seq'::regclass) NOT NULL,
    "user" integer,
    type smallint,
    text text
);
ALTER TABLE ONLY chat_message ADD CONSTRAINT pk_chat_message PRIMARY KEY (id);
CREATE INDEX idx_chat_message_user_type ON chat_message USING btree ("user", type);
CREATE INDEX k_chat_message_user ON chat_message USING btree ("user");

where type is either 1 or NULL, then the query:

EXPLAIN ANALYZE
SELECT *
FROM "chat_message" AS t
WHERE true
  AND "type" = 1
  AND "user" = 1234567
ORDER BY "user", "type", "id" ASC
LIMIT 10 OFFSET 0;

gives following output:

                                                                       QUERY PLAN                                                                       
--------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=53644.94..53644.97 rows=10 width=127) (actual time=4.817..4.818 rows=6 loops=1)
   ->  Sort  (cost=53644.94..53681.60 rows=14663 width=127) (actual time=4.816..4.816 rows=6 loops=1)
         Sort Key: id
         Sort Method: quicksort  Memory: 26kB
         ->  Bitmap Heap Scan on chat_message t  (cost=362.86..53328.08 rows=14663 width=127) (actual time=1.975..2.181 rows=6 loops=1)
               Recheck Cond: (("user" = 1234567) AND (type = 1::smallint))
               Heap Blocks: exact=3
               ->  Bitmap Index Scan on idx_chat_message_user_type  (cost=0.00..359.19 rows=14663 width=0) (actual time=1.822..1.822 rows=6 loops=1)
                     Index Cond: (("user" = 1234567) AND (type = 1::smallint))
 Planning time: 0.348 ms
 Execution time: 5.028 ms

But once the LIMIT value reduced below some value (to 9 on my local machine) then the query plan changes to this:

                                                                        QUERY PLAN                                                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.56..50193.33 rows=9 width=127) (actual time=23119.188..46005.965 rows=6 loops=1)
   ->  Index Scan using pk_chat_message on chat_message t  (cost=0.56..81775168.50 rows=14663 width=127) (actual time=23119.187..46005.962 rows=6 loops=1)
         Filter: ((type = 1::smallint) AND ("user" = 1234567))
         Rows Removed by Filter: 49452956
 Planning time: 14.840 ms
 Execution time: 46006.683 ms

which is way to slow.

There's a huge data skew for this exact user: it's 50 000 rows WHERE type is NULL, and only 6 WHERE type = 1. Moreover, requesting the same LIMIT 9, but WHERE type is NULL has exactly the same query plan, but works fast:

                                                                         QUERY PLAN                                                                          
-------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=153793.13..153793.15 rows=9 width=127) (actual time=886.897..886.898 rows=9 loops=1)
   ->  Sort  (cost=153793.13..153909.07 rows=46374 width=127) (actual time=886.894..886.894 rows=9 loops=1)
         Sort Key: gs_type, id
         Sort Method: top-N heapsort  Memory: 27kB
         ->  Bitmap Heap Scan on chat_message t  (cost=1143.90..152826.25 rows=46374 width=127) (actual time=12.561..878.947 rows=49934 loops=1)
               Recheck Cond: (("user" = 1234567) AND (type IS NULL))
               Heap Blocks: exact=10903
               ->  Bitmap Index Scan on idx_chat_message_user_type  (cost=0.00..1132.31 rows=46374 width=0) (actual time=9.942..9.942 rows=49934 loops=1)
                     Index Cond: (("user" = 1234567) AND (type IS NULL))
 Planning time: 0.308 ms
 Execution time: 887.027 ms

On production server exactly same data loaded into a server with specs different from my laptop (more ram, huge shared_buffers, max_mem, constant workload from different other tables) behaves in similar fashion, only the limit threshold value is different (it's slow Index Scan up to 75, and then fast Bitmap Heap Scan + Bitmap Index Scan from 76 and further).

Some additional info:

SELECT * FROM pg_stat_user_tables WHERE relname = 'chat_message';

relname     |seq_scan   |seq_tup_read   |idx_scan   |idx_tup_fetch  |n_tup_ins  |n_tup_upd  |n_tup_del  |n_tup_hot_upd  |n_live_tup |n_dead_tup |n_mod_since_analyze|last_vacuum|last_autovacuum|last_analyze   |last_autoanalyze   |vacuum_count   |autovacuum_count   |analyze_count  |autoanalyze_count  |
chat_message|0          |0              |11         |197,652,914    |0          |0          |0          |0              |0          |0          |0                  |           |               |               |                   |0              |0                  |0              |0                  |

SELECT * FROM pg_stats where tablename = 'chat_message';

schemaname  |tablename      |attname       |inherited|null_frac|avg_width|n_distinct|most_common_vals
public      |chat_message   |id            |false    |0        |8        |-1        |
public      |chat_message   |user          |false    |0        |4        |30145     |{redacted}
public      |chat_message   |text          |false    |0        |38       |45553     |{redacted}
public      |chat_message   |type          |false    |0.7656   |2        |1         |{1}

My questions are:

  • Why the same Index Scan get very slow when it comes to those few rows?
  • Why the Index Scan always uses pk_chat_message index, even though there's more suitable idx_chat_message_user_type, even though ORDER BY clause has all fields from WHERE clause (order by influences Index usage)?
  • Why LIMIT N affects the query plan in that it prefers Index Scan over Bitmap Index + Heap Scan?
  • What can be done to make this query perform decently (under 1s) for this user + type and others?
2
  • 1
    @LaurenzAlbe since User and type are fixed to a single value by the where clause, doesn't it resolve to a sort by id?
    – Andrea B.
    Commented Jul 5 at 7:52
  • Just in case, rerun all the queries and updated the post with query plans Commented Jul 5 at 8:19

2 Answers 2

2

PostgreSQL has two choices to process the query:

  • it can use an index for the WHERE clause, then sort and return the first few results (that's your fast plan)

  • it can use an index for the ORDER BY clause and discard rows that don't match the WHERE condition until it has found enough result rows (that is your slow plan)

The decision which plan is better is difficult, and PostgreSQL is bound to get it wrong sometimes. In your slow case, it has to scan 49452957 rows until it finds one that meets the WHERE condition, even though there are an estimated 14663 (really 49934) rows that meet the WHERE condition. The problem is that PostgreSQL has no statistics that can tell it that all the matching rows have a large id, so it has to scan a lot of rows until it gets a hit.

Naturally, the second (in your case slow) strategy becomes more attractive if you need only few result rows, which explains that the optimizer switches to such a plan when you reduce the number of rows in the LIMIT.

Note that an "Index Scan" is processed quite differently from a "Bitmap Index Scan". The former will return the results in index order, while the latter returns the rows in table order, but performs better if there are many result rows.

You have two ways to improve the situation:

  1. create an index that supports both the ORDER BY and the WHERE condition:

    CREATE INDEX ON chat_message ("user", type, id);
    
  2. use a crude trick to prevent PostgreSQL from using the primary key index:

    ... ORDER BY "user", type, id + 0
    
4
  • What is the reason that existing indexes for ("user", type) and id have not been used with second approach, even for ORDER BY "user", type, id and it still used only index by id? Commented Jul 8 at 18:42
  • 1
    You cannot combine two indexes to support ORDER BY. Combining two indexes would mean a bitmap index scan in PostgreSQL, and that returns the result in table order, not in index order. But even without that implementation detail: how exactly would you use the two indexes to return the rows in the desired sorting order? I cannot think of a way. Commented Jul 8 at 19:53
  • I'd imagine that when I have ORDER BY "user", type, id and only have separate indexes ("user", type) and id it would attempt to use the ones that satisfy the "outermost" conditions, then do filtering by WHERE condition, and then sort the innermost that were not covered by index (eg sort by "user" and type, then filter by conditions, then sort the results). Wouldn't that be more efficient? Can PostgreSQL even estimate how efficient that would be? Commented Jul 8 at 21:18
  • 1
    You cannot sort an intermediate result set by an index. That only works when you scan a table. The plan you suggest is pretty similar to the "fast" plan in your question, except that sorting via the index is impossible. Commented Jul 9 at 6:20
1

Fastest solution for skewed data would be partial index. In your case an index like below will be fast as well super compact. You can tweak and test the index by changing index column or filtering column.

create index ix_partial_type on chat_message(<user_id/id>) where type=1;

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.