Optimizing simple but slow query with OR condition

Question

Some background: I'm running the following simple select statement on Postgres 15.3 server with 128GB memory, and contrary to my belief it takes ~6 minutes. The statement in involve two relations, big_table_70m with approximately 70M rows and other_table_50m with a bit less than 50M rows. In both tables I've Btree indexes on esat_last_modified and last_modified.

This takes 6 minutes to return:

select
    count(*)
FROM
    big_table_70m
where
    big_table_70m.esat_last_modified > (
        select
            max(esat_last_modified)
        from
            other_table_50m
    )
    OR big_table_70m.task_last_modified > (
        select
            max(last_modified)
        from
            other_table_50m
    );

However when dropping the OR condition and performing the query on either side, it returns very fast (>70ms):

select
    count(*)
FROM
    big_table_70m
where
    big_table_70m.esat_last_modified > (
        select
            max(esat_last_modified)
        from
            other_table_50m
    );

I've tried to add multi-column index on (esat_last_modified,last_modified) to make it more efficient without a success.

Can you please help me improve this query. Eventually the return count should be few thousands of rows.

explain analyze:

                                                                                               QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=1765894.63..1765894.64 rows=1 width=8) (actual time=403477.117..403477.314 rows=1 loops=1)
   Buffers: shared hit=77762962 read=848381 dirtied=27535
   I/O Timings: shared/local read=380517.629
   InitPlan 2 (returns $1)
     ->  Result  (cost=0.70..0.71 rows=1 width=8) (actual time=0.028..0.029 rows=1 loops=1)
           Buffers: shared hit=6
           InitPlan 1 (returns $0)
             ->  Limit  (cost=0.56..0.70 rows=1 width=8) (actual time=0.026..0.027 rows=1 loops=1)
                   Buffers: shared hit=6
                   ->  Index Only Scan Backward using f9b1917d68a5656ca14b2f5e12447c6a on other_table_50m  (cost=0.56..4671638.13 rows=33810205 width=8) (actual time=0.025..0.026 rows=1 loops=1)
                         Index Cond: (esat_last_modified IS NOT NULL)
                         Heap Fetches: 1
                         Buffers: shared hit=6
   InitPlan 4 (returns $3)
     ->  Result  (cost=0.67..0.68 rows=1 width=8) (actual time=0.013..0.014 rows=1 loops=1)
           Buffers: shared hit=5
           InitPlan 3 (returns $2)
             ->  Limit  (cost=0.56..0.67 rows=1 width=8) (actual time=0.013..0.013 rows=1 loops=1)
                   Buffers: shared hit=5
                   ->  Index Only Scan Backward using "429b05d0a626f21b4708244ab67da408" on other_table_50m other_table_50m_1  (cost=0.56..5092889.03 rows=47176591 width=8) (actual time=0.013..0.013 rows=1 loops=1)
                         Index Cond: (last_modified IS NOT NULL)
                         Heap Fetches: 1
                         Buffers: shared hit=5
   ->  Gather  (cost=1765893.02..1765893.23 rows=2 width=8) (actual time=403477.112..403477.306 rows=1 loops=1)
         Workers Planned: 2
         Params Evaluated: $1, $3
         Workers Launched: 0
         Buffers: shared hit=77762962 read=848381 dirtied=27535
         I/O Timings: shared/local read=380517.629
         ->  Partial Aggregate  (cost=1764893.02..1764893.03 rows=1 width=8) (actual time=403476.429..403476.429 rows=1 loops=1)
               Buffers: shared hit=77762951 read=848381 dirtied=27535
               I/O Timings: shared/local read=380517.629
               ->  Parallel Index Only Scan using multi_column_index on big_table_70m  (cost=0.57..1724191.80 rows=16280489 width=0) (actual time=403476.425..403476.425 rows=0 loops=1)
                     Filter: ((esat_last_modified > $1) OR (task_last_modified > $3))
                     Rows Removed by Filter: 70394276
                     Heap Fetches: 6894859
                     Buffers: shared hit=77762951 read=848381 dirtied=27535
                     I/O Timings: shared/local read=380517.629
 Planning:
   Buffers: shared hit=352
 Planning Time: 0.949 ms
 Execution Time: 403477.593 ms
(42 rows)

Here is a link to depesz It shows that significant amount of time is due to IO (reading from the disk).

Added multi-column index on big_table_70m without a success. I've also rewrite the select to use CTE but obviously it didn't make any change to the plan.

I expect the statement to return in the same speed as without the OR condition.

EDIT: Adding explain plan for the query without OR (added one but it's the same for both):

                                                                                           QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Finalize Aggregate  (cost=1322659.98..1322659.99 rows=1 width=8) (actual time=7.493..8.952 rows=1 loops=1)
   Buffers: shared read=10
   I/O Timings: shared/local read=6.931
   InitPlan 2 (returns $1)
     ->  Result  (cost=0.70..0.71 rows=1 width=8) (actual time=3.905..3.906 rows=1 loops=1)
           Buffers: shared read=6
           I/O Timings: shared/local read=3.872
           InitPlan 1 (returns $0)
             ->  Limit  (cost=0.56..0.70 rows=1 width=8) (actual time=3.902..3.903 rows=1 loops=1)
                   Buffers: shared read=6
                   I/O Timings: shared/local read=3.872
                   ->  Index Only Scan Backward using f9b1917d68a5656ca14b2f5e12447c6a on other_table_50m  (cost=0.56..4686718.49 rows=33918614 width=8) (actual time=3.901..3.901 rows=1 loops=1)
                         Index Cond: (esat_last_modified IS NOT NULL)
                         Heap Fetches: 1
                         Buffers: shared read=6
                         I/O Timings: shared/local read=3.872
   ->  Gather  (cost=1322659.05..1322659.26 rows=2 width=8) (actual time=7.447..8.946 rows=3 loops=1)
         Workers Planned: 2
         Params Evaluated: $1
         Workers Launched: 2
         Buffers: shared read=10
         I/O Timings: shared/local read=6.931
         ->  Partial Aggregate  (cost=1321659.05..1321659.06 rows=1 width=8) (actual time=1.289..1.289 rows=1 loops=3)
               Buffers: shared read=4
               I/O Timings: shared/local read=3.059
               ->  Parallel Index Only Scan using big_table_70m_esat_last_modified on big_table_70m  (cost=0.57..1297144.84 rows=9805685 width=0) (actual time=1.287..1.287 rows=0 loops=3)
                     Index Cond: (esat_last_modified > $1)
                     Heap Fetches: 0
                     Buffers: shared read=4
                     I/O Timings: shared/local read=3.059
 Planning:
   Buffers: shared hit=328 read=9
   I/O Timings: shared/local read=8.097
 Planning Time: 9.082 ms
 Execution Time: 9.073 ms
(35 rows)

Two ideas: 1) rewrite the query to a UNION of two queries instead of using OR 2) run the subqueries separately and query the big table with constant values. — Laurenz Albe
– Laurenz Albe, Commented Feb 6, 2024 at 13:34
Please show the plan for the fast version of the query as well. — jjanes
– jjanes, Commented Feb 6, 2024 at 15:01
thanks @LaurenzAlbe UNION has significantly improve the performance. — Cowabunga
– Cowabunga, Commented Feb 12, 2024 at 11:43

Charlieface · Accepted Answer · 2024-02-06 13:09:12Z

OR is often very difficult for an optimizer to deal with, as it cannot use an index on either column as that doesn't take into account the other.

Sometimes it can do an Index Union, but it often doesn't work that out. So you need to give it some help.

Use a UNION on the primary keys of the table, which should in theory allow it to use an efficient Merge Union, then aggregate again.

Note that you must use UNION not UNION ALL otherwise you could count a row twice.

select
    count(*)
from (
    select bg.PrimaryKeyHere
    from big_table_70m bg
    where
        bg.esat_last_modified > (
            select
                max(o.esat_last_modified)
            from
                other_table_50m o
        )

    union

    select bg.PrimaryKeyHere
    from big_table_70m bg
    where
        bg.task_last_modified > (
            select
                max(o.last_modified)
            from
                other_table_50m o
        )
) bg;

For this to work efficiently, you are going to want the following indexes:

big_table_70m (esat_last_modified)
big_table_70m (task_last_modified)
other_table_50m (esat_last_modified)
other_table_50m (last_modified)

You can add other columns into the key or the INCLUDE of the indexes, but those columns should be first, and should not be merged together into a single index.

jjanes · Accepted Answer · 2024-02-06 15:28:30Z

Since the values of the subqueries are not known at planning time, the planner assumes that each side of the OR is going to match 1/3 of the table. Which of course is a massive overestimate (the true value apparently is zero). If the estimate were more reasonable, it would realize that a BitmapOr of the two single-column indexes would be a fast way to run this query.

Unfortunately there is nothing you can do about this estimate, apart from pre-running the subqueries and then stuffing the results as literals into the main query.

Ways to fix this without fixing the estimate would be to set enable_seqscan to off and enable_indexscan to off, which of course is not very satisfying and would need to be done locally for just this query.

You could make the current plan far faster by vacuuming the table so that there weren't so many Heap Fetches, but if the table is very active it might be hard to keep the vacuuming sufficient.

There is nothing particularly magic about the OR here. It just happens that without the OR, the best plan under the bad estimation happens to also be a good one in reality, and with the OR it happens not to be the case.

Collectives™ on Stack Overflow

Optimizing simple but slow query with OR condition

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related