2

I'm trying to optimize a query, which never completes on Postgres 12.7. It takes hours, even days, make the CPU goes 100%, and never returns:

SELECT "id", "counter", "item_id", "item_name", "type", "updated_time"
FROM "changes"
WHERE (type = 1 OR type = 3) AND user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'
OR type = 2 AND item_id IN (SELECT item_id FROM user_items WHERE user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW')
ORDER BY "counter" ASC LIMIT 100;

I randomly tried to rewrite it using UNION instead, and I believe it's equivalent. Basically there's two parts in the query, one for type = 1 or 3, and one for type = 2.

(
    SELECT "id", "counter", "item_id", "item_name", "type", "updated_time"
    FROM "changes"
    WHERE (type = 1 OR type = 3) AND user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'
) UNION (
    SELECT "id", "counter", "item_id", "item_name", "type", "updated_time"
    FROM "changes"
    WHERE type = 2 AND item_id IN (SELECT item_id FROM user_items WHERE user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW')
) ORDER BY "counter" ASC LIMIT 100;

This query returns within 10 seconds, as opposed to never returning after several days for the other one. Any idea what's causing this huge difference?

Query plans

For the original query:

                                                                      QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1001.01..1697110.80 rows=100 width=119)
   ->  Gather Merge  (cost=1001.01..8625312957.40 rows=508535 width=119)
         Workers Planned: 2
         ->  Parallel Index Scan using changes_pkey on changes  (cost=0.98..8625253259.82 rows=211890 width=119)
               Filter: ((((type = 1) OR (type = 3)) AND ((user_id)::text = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'::text)) OR ((type = 2) AND (SubPlan 1)))
               SubPlan 1
                 ->  Materialize  (cost=0.55..18641.22 rows=143863 width=33)
                       ->  Index Only Scan using user_items_user_id_item_id_unique on user_items  (cost=0.55..16797.90 rows=143863 width=33)
                             Index Cond: (user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'::text)

And for the UNION query:

Limit  (cost=272866.63..272866.88 rows=100 width=212) (actual time=10564.742..10566.964 rows=100 loops=1)
   ->  Sort  (cost=272866.63..273371.95 rows=202128 width=212) (actual time=10564.739..10566.950 rows=100 loops=1)
         Sort Key: changes.counter
         Sort Method: top-N heapsort  Memory: 69kB
         ->  Unique  (cost=261604.20..265141.44 rows=202128 width=212) (actual time=9530.376..10493.030 rows=147261 loops=1)
               ->  Sort  (cost=261604.20..262109.52 rows=202128 width=212) (actual time=9530.374..10375.845 rows=147261 loops=1)
                     Sort Key: changes.id, changes.counter, changes.item_id, changes.item_name, changes.type, changes.updated_time
                     Sort Method: external merge  Disk: 19960kB
                     ->  Gather  (cost=1000.00..223064.76 rows=202128 width=212) (actual time=2439.116..7356.233 rows=147261 loops=1)
                           Workers Planned: 2
                           Workers Launched: 2
                           ->  Parallel Append  (cost=0.00..201851.96 rows=202128 width=212) (actual time=2421.400..7815.315 rows=49087 loops=3)
                                 ->  Parallel Hash Join  (cost=12010.60..103627.94 rows=47904 width=119) (actual time=907.286..3118.898 rows=24 loops=3)
                                       Hash Cond: ((changes.item_id)::text = (user_items.item_id)::text)
                                       ->  Parallel Seq Scan on changes  (cost=0.00..90658.65 rows=365215 width=119) (actual time=1.466..2919.855 rows=295810 loops=3)
                                             Filter: (type = 2)
                                             Rows Removed by Filter: 428042
                                       ->  Parallel Hash  (cost=11290.21..11290.21 rows=57631 width=33) (actual time=78.190..78.191 rows=48997 loops=3)
                                             Buckets: 262144  Batches: 1  Memory Usage: 12416kB
                                             ->  Parallel Index Only Scan using user_items_user_id_item_id_unique on user_items  (cost=0.55..11290.21 rows=57631 width=33) (actual time=0.056..107.247 rows=146991 loops=1)
                                                   Index Cond: (user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'::text)
                                                   Heap Fetches: 11817
                                 ->  Parallel Seq Scan on changes changes_1  (cost=0.00..95192.10 rows=36316 width=119) (actual time=2410.556..7026.664 rows=73595 loops=2)
                                       Filter: (((user_id)::text = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'::text) AND ((type = 1) OR (type = 3)))
                                       Rows Removed by Filter: 1012184
 Planning Time: 65.846 ms
 Execution Time: 10575.679 ms
(27 rows)

Definitions

                                         Table "public.changes"
    Column     |         Type          | Collation | Nullable |                 Default
---------------+-----------------------+-----------+----------+------------------------------------------
 counter       | integer               |           | not null | nextval('changes_counter_seq'::regclass)
 id            | character varying(32) |           | not null |
 item_type     | integer               |           | not null |
 item_id       | character varying(32) |           | not null |
 item_name     | text                  |           | not null | ''::text
 type          | integer               |           | not null |
 updated_time  | bigint                |           | not null |
 created_time  | bigint                |           | not null |
 previous_item | text                  |           | not null | ''::text
 user_id       | character varying(32) |           | not null | ''::character varying
Indexes:
    "changes_pkey" PRIMARY KEY, btree (counter)
    "changes_id_unique" UNIQUE CONSTRAINT, btree (id)
    "changes_id_index" btree (id)
    "changes_item_id_index" btree (item_id)
    "changes_user_id_index" btree (user_id)
                                      Table "public.user_items"
    Column    |         Type          | Collation | Nullable |                Default
--------------+-----------------------+-----------+----------+----------------------------------------
 id           | integer               |           | not null | nextval('user_items_id_seq'::regclass)
 user_id      | character varying(32) |           | not null |
 item_id      | character varying(32) |           | not null |
 updated_time | bigint                |           | not null |
 created_time | bigint                |           | not null |
Indexes:
    "user_items_pkey" PRIMARY KEY, btree (id)
    "user_items_user_id_item_id_unique" UNIQUE CONSTRAINT, btree (user_id, item_id)
    "user_items_item_id_index" btree (item_id)
    "user_items_user_id_index" btree (user_id)

Type count

postgres=> select count(*) from changes where type = 1;
  count
---------
 1201839
(1 row)

postgres=> select count(*) from changes where type = 2;
 count
--------
 888269
(1 row)

postgres=> select count(*) from changes where type = 3;
 count
-------
 83849
(1 row)

How many item_id per user_id

postgres=> SELECT min(ct), max(ct), avg(ct), sum(ct) FROM (SELECT count(*) AS ct FROM user_items GROUP BY user_id) x;
 min |  max   |          avg          |   sum
-----+--------+-----------------------+---------
   6 | 146991 | 2253.0381526104417671 | 1122013
(1 row)
2
  • Just for clarity, if nothing else, I strongly recommend adding another pair of parentheses around each of the expressions on either side of the OR, like this: WHERE ((type = 1 OR type = 3) AND user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW') OR (type = 2 AND item_id IN (SELECT item_id FROM user_items WHERE user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW')) There's an outside chance that might help with the query plan too?
    – Ed Sabol
    Sep 20 at 22:05
  • Comments should only be used for asking for clarification, or to leave constructive criticism that guides the author in improving the post, or to add relevant but minor or transient information to a post (e.g. a link to a related question, or an alert to the author that the question has been updated), or to provide site usage guidance. See the help for details.
    – Hannah Vernon
    Sep 21 at 1:57
3

The tolerable one with the OR got lucky, because it found 100 matching rows with types of 1 or 3, before it found any of type 2 which had to be checked against the other table. The intolerable one apparently did have to do the check against the other table, and it does it in a very slow way, by looping over all the rows in it. Now it should use a hashed subplan, rather than a regular subplan. The only reason it would not use the hashed subplan that I can think of is that your work_mem setting is quite low, so it doesn't think it can fit the hashed table into memory, so it falls back to a completely horrible method.

A "hashed subplan" has no way of spilling to disk, so if the planner thinks it will use too much memory, it just won't schedule one. On the union side, a hash join can spill to disk, so it is more willing to use that.

If you crank up your work_mem, the OR plan should get much faster. It shouldn't take much, in my hands 10MB is enough (but that is still pretty small for a modern server, i would probably set it to at least 100MB unless you have a good reason not to)

2
  • 1
    By the way, where can I see in the EXPLAIN result that it is a regular subplan, as opposed to an hash one?
    – laurent
    Sep 17 at 16:37
  • 1
    @laurent Where it says (type = 2) AND (SubPlan 1). The faster one with higher work_mem should say (type = 2) AND (hashed SubPlan 1)
    – jjanes
    Sep 17 at 19:24
4

It's typically a good idea to split up that ugly OR in to a UNION query. See:

The first SELECT of the UNION query should melt down to milliseconds with this partial multicolumn index:

CREATE INDEX ON changes (user_id, counter)
WHERE  type IN (1, 3);

And after adding ORDER BY counter LIMIT 100. Since the outer query has the same, we never need more than 100 rows from this part:

(  -- now parentheses are required
SELECT id, counter, item_id, item_name, type, updated_time
FROM   changes
WHERE  type IN (1, 3)
AND    user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'
ORDER  BY counter
LIMIT  100
)

You didn't provide actual numbers, so judging from the high number of items per user (rows=146991 in the query plan) try this one as 2nd SELECT:

(
SELECT id, counter, item_id, item_name, type, updated_time
FROM   changes c
WHERE  type = 2
AND    EXISTS (
   SELECT FROM user_items u
   WHERE  u.user_id = 'kJ6GYJNPM4wdDY5dUV1b8PqDRJj6RRgW'   
   AND    c.item_id = u.item_id
   )
ORDER  BY counter
LIMIT  100
);

In combination with this index:

CREATE INDEX ON changes (counter, item_id) WHERE  type = 2;

For substantially different cardinalities a different SELECT may be (much) better. In particular, this will backfire for users with few or no items.

The complete query then:

(<query 1>)
UNION
(<query 2>)
ORDER  BY counter
LIMIT  100;

Yes, that's 3x ORDER BY counter LIMIT 100 altogether.

Asides

The query plan shows (never executed) for SubPlan 1, which seems to imply that no row with type = 2 was found. Which is odd. (See jjanes' added answer for a possible explanation.)

You are operating with large varchar(32) IDs. If you really need globally unique identifiers, consider uuid instead. Much smaller and faster. Else, a plain bigint (or even integer) can easily cover your 2 million rows. Makes tables and indexes smaller and faster. Faster UNION, too. See:

Failing that, you could at least add COLLATE "C" to your varchar(32) columns to improve UNION performance (and all sorts and related operations). Unless you run the DB with COLLATE "C" anyway, which seems unlikely. See:

Your current table design is wasteful. Consider rewriting like this:

                                         Table "public.changes"
    Column     |         Type          | Collation | Nullable |                 Default
---------------+-----------------------+-----------+----------+------------------------------------------
 counter       | integer               |           | not null | nextval('changes_counter_seq'::regclass)
 type          | integer               |           | not null |
 item_type     | integer               |           | not null |
 item_id       | character varying(32) |           | not null |
 item_name     | text                  |           | not null | ''::text
 id            | character varying(32) |           | not null |
 previous_item | text                  |           | not null | ''::text
 user_id       | character varying(32) |           | not null | ''::character varying
 updated_time  | bigint                |           | not null |
 created_time  | bigint                |           | not null |

Should make the table ~ 15 MB smaller (comparing pristine tables without bloat) and everything slightly faster. See:

4
  • Many thanks for your answer. I've updated my question with the required information. As for the (never executed) it might be because the user never changed their data (1 = Create, 2 = Update, 3 = Delete).
    – laurent
    Sep 17 at 9:42
  • Thanks, I will give a try to these queries. In your 2nd one with AND EXISTS, why is it it that it's faster than the current one? It's not entirely clear to me. Also I forgot to mention that the original query may have an OFFSET parameter - so I guess it means I'll add this OFFSET to each sub-query and to the outer query (so 3x again), is that right?
    – laurent
    Sep 17 at 16:33
  • @laurent: If the OFFSET is much bigger, my queries stop making sense. I exploit the fact that we need so few from the bottom of the count. Also the 2nd query is not good for users with few items. I just didn't want to wait for actual numbers any longer. Please disclose relevant information up front in your next question - as instructed here Sep 17 at 16:43
  • Right, sorry about that. I've tried to provide as much info as possible but clearly that wasn't enough. I will investigate your suggested indexes, queries and other suggestions anyway and see what I can apply. Thanks for your help, much appreciated.
    – laurent
    Sep 17 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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