0

I have a query involving two tables, let's call them timeline and events, defined as follows:

create table timeline (
   event_id int,
   ts timestamptz
);

create table events (
   id int primary key,
   foo int,
   bar int,
   baz int
);

Then I have these indexes:

create index timeline_sorted_idx on timeline (ts desc, event_id desc)
create index events_foo_idx on events (foo);
create index events_bar_idx on events (bar);
create index events_baz_idx on events (baz);

Both tables contain circa 10 million rows.

Now I want to execute this type of query (to scroll through timeline in mobile app):

select * 
from events e
join timeline t on e.id = t.event_id
where (t.ts >= 2020-01-01 and t.ts <= 2021-01-01) and (e.foo = 1 or e.bar = 1 or e.baz = 1)
order by t.ts desc, t.event_id desc
offset 0 limit 10; 

which yields this execution plan for foo/bar/baz = 1 (there is lot of 1s in events table):

Limit  (cost=0.87..129.74 rows=10 width=328) (actual time=0.792..7.086 rows=10 loops=1)
  ->  Nested Loop  (cost=0.87..1432982.57 rows=111200 width=328) (actual time=0.790..7.080 rows=10 loops=1)
        ->  Index Only Scan using timeline_sorted_idx on timeline t  (cost=0.43..90018.01 rows=1158326 width=12) (actual time=0.030..1.358 rows=827 loops=1)
              Index Cond: ((ts >= '2020-01-01 00:00:00'::timestamp without time zone) AND (ts <= '2020-01-01 00:00:00'::timestamp without time zone))
              Heap Fetches: 827
        ->  Index Scan using events_pkey on events e  (cost=0.43..1.16 rows=1 width=304) (actual time=0.006..0.006 rows=0 loops=827)
              Index Cond: (id = t.event_id)
              Filter: (foo = 1 OR bar = 1 OR baz = 1)
              Rows Removed by Filter: 1
Planning time: 0.990 ms
Execution time: 7.248 ms

but this for foo/bar/baz = 2 (2 has zero occurrence in events table):

Limit  (cost=1000.89..1843.67 rows=10 width=328) (actual time=2737.428..2737.428 rows=0 loops=1)
  ->  Gather Merge  (cost=1000.89..644711.51 rows=7638 width=328) (actual time=2737.426..2737.426 rows=0 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        ->  Nested Loop  (cost=0.87..642829.87 rows=3182 width=316) (actual time=2691.361..2691.361 rows=0 loops=3)
              ->  Parallel Index Only Scan using timeline_sorted_idx on timeline t  (cost=0.43..83261.11 rows=482636 width=12) (actual time=0.097..484.201 rows=390318 loops=3)
                    Index Cond: ((ts >= '2020-01-01 00:00:00'::timestamp without time zone) AND (ts <= '2020-01-01 00:00:00'::timestamp without time zone))
                    Heap Fetches: 438622
              ->  Index Scan using events_pkey on events e (cost=0.43..1.16 rows=1 width=304) (actual time=0.005..0.005 rows=0 loops=1170954)
                    Index Cond: (id = t.event_id)
                    Filter: (foo = 2 OR bar = 2 OR baz = 2)
                    Rows Removed by Filter: 1
Planning time: 0.743 ms
Execution time: 3002.328 ms

OK, I understand... postgres chose nested loop, because there is a sorted index on a timeline and the only thing to do is to find matching records in events for the first N requested rows. But, that works well if there are lots of matching records, so it finds all matches in a few hundreds or thousands of iterations. But If there is no match, then it takes some serious amount of time to iterate over a million of records in timeline and find nothing in events.

The question is, is there a way how to convince Postgres to choose a different plan based on foo/bar/baz frequency? In my tests, materialize events first with CTE for small frequencies is much faster than this, but much slower for high frequencies...

-- EDIT --

Also, it is important to note that in reality, there are a lot of "events" tables and all of them share one common timeline table. I cannot change that schema, because I'm not an owner of that system and this is not the primary use case of it...

-- EDIT II --

There is turnover point between two different execution plans (Nested loop or BitmapOr) which are around one-month time span:

les than 28 days of data from timeline:

Limit  (cost=62717.86..62719.03 rows=10 width=34) (actual time=3.825..5.250 rows=0 loops=1)
  Buffers: shared hit=26 read=11
  ->  Gather Merge  (cost=62717.86..62723.46 rows=48 width=34) (actual time=3.823..5.248 rows=0 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        Buffers: shared hit=26 read=11
        ->  Sort  (cost=61717.83..61717.89 rows=24 width=34) (actual time=0.360..0.361 rows=0 loops=3)
              Sort Key: t.ts DESC, e.id DESC
              Sort Method: quicksort  Memory: 25kB
              Worker 0:  Sort Method: quicksort  Memory: 25kB
              Worker 1:  Sort Method: quicksort  Memory: 25kB
              Buffers: shared hit=26 read=11
              ->  Nested Loop  (cost=206.74..61717.32 rows=24 width=34) (actual time=0.310..0.311 rows=0 loops=3)
                    Buffers: shared read=9
                    ->  Parallel Bitmap Heap Scan on events e  (cost=206.30..29087.65 rows=4292 width=10) (actual time=0.309..0.310 rows=0 loops=3)
                          Recheck Cond: ((foo = 3809) OR (bar = 3809) OR (baz = 3809))
                          Buffers: shared read=9
                          ->  BitmapOr  (cost=206.30..206.30 rows=10302 width=0) (actual time=0.636..0.637 rows=0 loops=1)
                                Buffers: shared read=9
                                ->  Bitmap Index Scan on events_foo_idx  (cost=0.00..173.65 rows=9229 width=0) (actual time=0.592..0.592 rows=0 loops=1)
                                      Index Cond: (foo = 3809)
                                      Buffers: shared read=3
                                ->  Bitmap Index Scan on events_bar_idx  (cost=0.00..20.48 rows=1073 width=0) (actual time=0.021..0.021 rows=0 loops=1)
                                      Index Cond: (bar = 3809)
                                      Buffers: shared read=3
                                ->  Bitmap Index Scan on events_baz_idx  (cost=0.00..4.44 rows=1 width=0) (actual time=0.020..0.020 rows=0 loops=1)
                                      Index Cond: (baz = 3809)
                                      Buffers: shared read=3
                    ->  Index Scan using timeline_event_id on timeline t  (cost=0.43..7.60 rows=1 width=12) (never executed)
                          Index Cond: (event_id = e.id)
                          Filter: ((ts >= '2020-01-01 00:00:00'::timestamp without time zone) AND (ts <= '2020-01-27 00:00:00'::timestamp without time zone))
Planning Time: 0.339 ms
Execution Time: 5.288 ms

more than 27 days of data:

Limit  (cost=1001.02..62404.32 rows=10 width=34) (actual time=155.480..159.176 rows=0 loops=1)
  Buffers: shared hit=529109 read=18090
  ->  Gather Merge  (cost=1001.02..369420.83 rows=60 width=34) (actual time=155.478..159.173 rows=0 loops=1)
        Workers Planned: 2
        Workers Launched: 2
        Buffers: shared hit=529109 read=18090
        ->  Nested Loop  (cost=1.00..368413.88 rows=25 width=34) (actual time=148.922..148.923 rows=0 loops=3)
              Buffers: shared hit=529109 read=18090
              ->  Parallel Index Only Scan using timeline_sorted_idx on timeline t  (cost=0.56..186095.72 rows=36744 width=12) (actual time=0.062..33.047 rows=36466 loops=3)
                    Index Cond: ((ts >= '2020-01-01 00:00:00'::timestamp without time zone) AND (ts <= '2020-01-28 00:00:00'::timestamp without time zone))
                    Heap Fetches: 109397
                    Buffers: shared hit=105217 read=3792
              ->  Index Scan using events_pkey on events e  (cost=0.43..4.96 rows=1 width=10) (actual time=0.003..0.003 rows=0 loops=109397)
                    Index Cond: (id = t.event_id)
                    Filter: ((foo = 3809) OR (bar = 3809) OR (baz = 3809))
                    Rows Removed by Filter: 1
                    Buffers: shared hit=423892 read=14298
Planning Time: 0.271 ms
Execution Time: 159.208 ms
4
  • You say it changed to =2, but the plan still says =1.
    – jjanes
    Jul 27 at 16:44
  • What version of PostgreSQL are you using?
    – jjanes
    Jul 27 at 18:17
  • @jjanes it should be =2, this is a mocked-up example, but the plan numbers come from real tables and real value with zero occurrence...
    – DavidP
    Jul 28 at 7:18
  • @jjanes PG is version 10
    – DavidP
    Jul 28 at 7:27
0

With your current indexes, there is no efficient way to reverse the nested loop. The index on (ts desc, event_id desc) cannot be used to efficiently find rows with a specific event_id, because it would have to scan through all the different ts in the given range (which is large) in order to identify them.

With an appropriate index, such as one on either (event_id) or (event_id, ts), then in my hands it makes appropriate choices when faced with either very common or very rare conditions on the event table. That is, it uses your plan for common ones, and for rare ones uses a bitmapOr to get all the rows from events which match the criteria, then looks up in timeline for each one of them and sorts the results. https://explain.depesz.com/s/6xgUk

I think the remaining bad plan (once you have added the index) is down to poor selectivity estimates. Notice that it is expecting 9229 rows with foo = 3809, but there are really zero. That is a huge difference, and that bad estimate will of course lead to bad planning choices. Based on this other line, "Heap Fetches: 109397" I think your must not have done the VACUUM ANALYZE that I asked for, and your statistics are most likely out of date. Some things are inherently hard to estimate, but a simple index scan on a single-column unfiltered btree index usually is not one of them.

If manual VACUUM ANALYZE does fix the problem, then the question might become, why isn't autovacuum doing a good enough job?

4
  • I added unique index on event_id, but nothing happens... the same execution plan. I think PG assumes that fetching presorted rows with index is more effective than join them first and sort them afterward...
    – DavidP
    Jul 28 at 7:34
  • From my observations, PG chose nested loop or bitmap or based on timeline resultset size. If it spans more than one month (approx 40k rows) then it always chose nested loop. If It is less than that, then it chose bitmap or.
    – DavidP
    Jul 28 at 8:44
  • Could you show the EXPLAIN (ANALYZE, BUFFERS) for the query with the time range just on one side of the switchover point, and then just on the other side? But first VACUUM ANALYZE both tables to make sure it all up to date. You might need to re-find the switch-over point afterwards as it might change.
    – jjanes
    Jul 28 at 13:26
  • Of course, I can... please take a look at the original post edit...
    – DavidP
    Jul 29 at 10:35

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.