Why is this SQL query with UNION significantly faster than the same query without?

Question

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)

Answer 1

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)

Answer 2

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

• Why is an OR statement slower than UNION?

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:

• UUID or BIGSERIAL Foreign Keys Postgres

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:

• https://www.postgresql.org/docs/current/collation.html

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:

• Calculating and saving space in PostgreSQL