Why is this Postgres query so slow?

Question

I'm trying to debug the slow query below but I'm struggling to understand why it is slow. I can see that both plan and subplan do an index scan, including an "Index only scan" for the subplan so both should be fast. Yet it's taking 7 seconds for this particular query.

Any idea from this EXPLAIN output where the problem might be?

select "id", "item_id", "item_name", "type", "updated_time" from "changes"
where (
  ((type = 1 OR type = 3) AND user_id = 'USER_ID')
  or type = 2 AND item_id IN (SELECT item_id FROM user_items WHERE user_id = 'USER_ID')
) and "counter" > '35885954' order by "counter" asc limit 100;

 Limit  (cost=8409.70..8553.44 rows=100 width=101) (actual time=7514.730..7514.731 rows=0 loops=1)
   ->  Index Scan using changes_pkey on changes  (cost=8409.70..2387708.44 rows=1655325 width=101) (actual time=7514.728..7514.729 rows=0 loops=1)
         Index Cond: (counter > 35885954)
         Filter: ((((type = 1) OR (type = 3)) AND ((user_id)::text = 'USER_ID'::text)) OR ((type = 2) AND (hashed SubPlan 1)))
         Rows Removed by Filter: 11378536
         SubPlan 1
           ->  Index Only Scan using user_items_user_id_item_id_unique on user_items  (cost=0.56..8401.57 rows=3030 width=24) (actual time=0.085..3.011 rows=3589 loops=1)
                 Index Cond: (user_id = 'USER_ID'::text)
                 Heap Fetches: 2053
 Planning Time: 0.245 ms
 Execution Time: 7514.781 ms
(11 rows)

Answer 1

Split up the query along the ugly OR. The resulting two queries are mutually exclusive, so combine them with UNION ALL:

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

Support the first SELECT with this partial multicolumn index to make it lightning fast:

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

See:

• Multicolumn index and performance

The second SELECT is less clear. An index with leading counter should serve best while the LIMIT is small and the share of item_id for the given user_id isn't too small.

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

Else, switching index columns to (item_id, counter) might be better.

I slipped in a separate LIMIT 100 for the first SELECT, which is logically redundant but might produce a better query plan. The second LIMIT 100 applies to the whole query. It might even help to attach a separate LIMIT 100 to the second SELECT also (with an extra set of parentheses). Not sure. Test and report back which worked best.

Answer 2

Reading 11,378,536 rows isn't magically fast just because you do it with an index. And that is where the problem is, it has to read that number of rows.

We don't know which parts of that complex filter condition lead to most of the rows failing, which makes it hard to propose optimizations with confidence. Maybe an index on (type, counter) or (type, user_id) would help. Or you could break the query into 2 pieces on the OR condition, and combine them with a UNION.