Optimizing big sorted join (nested loop) based on value frequency

Question

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

-- FINAL EDIT --

After some time, we decided to try Timescale for that and it worked a treat. We have to sync all the data to a different database (with Timescale), but it was definitely worth the hassle. Queries run under 100ms now, no matter of time span. The only significant change we made was transforming the timeline table into a Timescale hypertable with 1-month chunk size.

Answer 1

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?