Why is Postgres so slow to order those 200 rows that are already ordered?

Question

I have two relatively complex SQL queries which I join using a UNION ALL. Each individual query is fast and returns instantly. The problem is that once joined together they perform terribly bad, and often times out.

This is the full query:

SELECT "id", "item_id", "item_name", "type", "updated_time", "counter" FROM (
    SELECT "id", "item_id", "item_name", "type", "updated_time", "counter"
    FROM "changes"
    WHERE counter > -1
    AND (type = 1 OR type = 3)
    AND user_id = 'USER_ID'
    ORDER BY "counter" ASC
    LIMIT 100
) as sub1
UNION ALL
SELECT "id", "item_id", "item_name", "type", "updated_time", "counter" FROM (
    SELECT "id", "item_id", "item_name", "type", "updated_time", "counter"
    FROM "changes"
    WHERE counter > -1
    AND type = 2
    AND item_id IN (SELECT item_id FROM user_items WHERE user_id = 'USER_ID')
    ORDER BY "counter" ASC
    LIMIT 100
) as sub2
ORDER BY counter ASC -- SLOW!!
LIMIT 100;

After some digging I found out the reason for being slow is the ORDER BY counter ASC at the end of the statement (not the ones in the inner statements - those are fine). If it's there it takes more than one minute and times out. Without it, it returns within 5ms.

This doesn't make any sense to me since by that time we have a total of 200 rows so ordering this should be very fast (especially since the rows are already ordered!).

I've tried to analyse the queries but nothing stands out to me:

• Full query (thakes more than 60 seconds)

 Limit  (cost=1.70..325537.14 rows=100 width=101)
   ->  Merge Append  (cost=1.70..651072.57 rows=200 width=101)
         Sort Key: changes.counter
         ->  Limit  (cost=0.56..106310.10 rows=100 width=101)
               ->  Index Scan using changes_pkey on changes  (cost=0.56..4162018.71 rows=3915 width=101)
                     Index Cond: (counter > '-1'::integer)
                     Filter: (((user_id)::text = 'USER_ID'::text) AND ((type = 1) OR (type = 3)))
         ->  Limit  (cost=1.12..544758.47 rows=100 width=101)
               ->  Nested Loop  (cost=1.12..11516171.34 rows=2114 width=101)
                     ->  Index Scan using changes_pkey on changes changes_1  (cost=0.56..3986383.73 rows=10843703 width=101)
                           Index Cond: (counter > '-1'::integer)
                           Filter: (type = 2)
                     ->  Index Only Scan using user_items_user_id_item_id_unique on user_items  (cost=0.56..0.69 rows=1 width=24)
                           Index Cond: ((user_id = 'USER_ID'::text) AND (item_id = (changes_1.item_id)::text))

• Full query without last ORDER BY (takes 5 ms):

 Limit  (cost=23934.97..180049.76 rows=100 width=101)
   ->  Append  (cost=23934.97..336164.56 rows=200 width=101)
         ->  Limit  (cost=23934.97..23935.22 rows=100 width=101)
               ->  Sort  (cost=23934.97..23944.76 rows=3915 width=101)
                     Sort Key: changes.counter
                     ->  Bitmap Heap Scan on changes  (cost=284.11..23785.34 rows=3915 width=101)
                           Recheck Cond: ((user_id)::text = 'USER_ID'::text)
                           Filter: ((counter > '-1'::integer) AND ((type = 1) OR (type = 3)))
                           ->  Bitmap Index Scan on changes_user_id_index  (cost=0.00..283.13 rows=6209 width=0)
                                 Index Cond: ((user_id)::text = 'USER_ID'::text)
         ->  Limit  (cost=312214.83..312226.33 rows=100 width=101)
               ->  Gather Merge  (cost=312214.83..312357.89 rows=1244 width=101)
                     Workers Planned: 1
                     ->  Sort  (cost=311214.82..311217.93 rows=1244 width=101)
                           Sort Key: changes_1.counter
                           ->  Nested Loop  (cost=148.64..311167.28 rows=1244 width=101)
                                 ->  Parallel Bitmap Heap Scan on user_items  (cost=148.07..11209.94 rows=1785 width=24)
                                       Recheck Cond: ((user_id)::text = 'USER_ID'::text)
                                       ->  Bitmap Index Scan on user_items_user_id_index  (cost=0.00..147.31 rows=3034 width=0)
                                             Index Cond: ((user_id)::text = 'USER_ID'::text)
                                 ->  Index Scan using changes_item_id_index on changes changes_1  (cost=0.56..167.91 rows=13 width=101)
                                       Index Cond: ((item_id)::text = (user_items.item_id)::text)
                                       Filter: ((counter > '-1'::integer) AND (type = 2))

I'm thinking I could just remove that "order by" statement and order them myself in code, but that doesn't feel very clean.

Any idea what can be done to improve this?

Answer 1

The added sort causes a completely different query plan, which should not occur, and can be avoided with CTEs if need be.

Whatever else you do, simplify the query first. The subqueries serve no purpose. All you need is parentheses around each SELECT to attach ORDER BY & LIMIT locally:

(  -- parentheses here
SELECT id, item_id, item_name, type, updated_time, counter
FROM   changes
WHERE  counter > -1
AND    type IN (1, 3)
AND    user_id = 'USER_ID'
ORDER  BY counter
LIMIT  100
)

UNION ALL
(  -- parentheses here
SELECT id, item_id, item_name, type, updated_time, counter
FROM   changes
WHERE  counter > -1
AND    type = 2
AND    item_id IN (SELECT item_id FROM user_items WHERE user_id = 'USER_ID')
ORDER  BY counter
LIMIT  100
)

ORDER  BY counter  -- SLOW!
LIMIT  100;

See:

• Combining 2 SELECT queries and printing the results in PostgreSQL

Not sure if that already helps.
If all else fails, materialize each SELECT in a separate CTE to enforce separate query plans for each:

WITH cte1 AS MATERIALIZED (
   SELECT id, item_id, item_name, type, updated_time, counter
   FROM   changes
   WHERE  counter > -1
   AND    type IN (1, 3)
   AND    user_id = 'USER_ID'
   ORDER  BY counter
   LIMIT  100
   )
, cte2 AS MATERIALIZED (
   SELECT id, item_id, item_name, type, updated_time, counter
   FROM   changes
   WHERE  counter > -1
   AND    type = 2
   AND    item_id IN (SELECT item_id FROM user_items WHERE user_id = 'USER_ID')
   ORDER  BY counter
   LIMIT  100
   )
TABLE cte1
UNION ALL
TABLE cte2
ORDER  BY counter
LIMIT  100;

Or with the "OFFSET 0 hack", also posing as optimization barrier, but without needlessly materializing intermediary results:

(  -- parentheses here
SELECT id, item_id, item_name, type, updated_time, counter
FROM   changes
WHERE  counter > -1
AND    type IN (1, 3)
AND    user_id = 'USER_ID'
ORDER  BY counter
LIMIT  100
OFFSET 0  -- optimization barrier
)

UNION ALL
(  -- parentheses here
SELECT id, item_id, item_name, type, updated_time, counter
FROM   changes
WHERE  counter > -1
AND    type = 2
AND    item_id IN (SELECT item_id FROM user_items WHERE user_id = 'USER_ID')
ORDER  BY counter
LIMIT  100
OFFSET 0  -- optimization barrier
)

ORDER  BY counter  -- SLOW!
LIMIT  100;

More forensic work might be done based on the complete (yet missing) picture.

Answer 2

This appears to be just another (but peculiar) manifestation of the classic ORDER BY...LIMIT problem. Notice the lack of Sort nodes in the first plan, so it is relying on the index scan to read the rows already in the desired order, and thinks this will win because it gets to stop early, once the LIMIT is met. But instead most of the rows with low values of "counter" fail the FILTER conditions or maybe the join condition in the 2nd branch, which means it doesn't get to stop nearly as early as it thinks it will.