Can a LEFT JOIN be deferred to only apply to matching rows?

Question

When joining on a table and then filtering (LIMIT 30 for instance), Postgres will apply a JOIN operation on all rows, even if the columns from those rows is only used in the returned column, and not as a filtering predicate.

This would be understandable for an INNER JOIN (PG has to know if the row will be returned or not) or for a LEFT JOIN without a unique constraint (PG has to know if more than one row will be returned or not), but for a LEFT JOIN on a UNIQUE column, this seems wasteful: if the query matches 10k rows, then 10k joins will be performed, and then only 30 will be returned.

It would seem more efficient to "delay", or defer, the join, as much as possible, and this is something that I've seen happen on some other queries.

Splitting this into a subquery (SELECT * FROM (SELECT * FROM main WHERE x LIMIT 30) LEFT JOIN secondary) works, by ensuring that only 30 items are returned from the main table before joining them, but it feels like I'm missing something, and the "standard" form of the query should also apply the same optimization.

Looking at the EXPLAIN plans, however, I can see that the number of rows joined is always the total number of rows, without "early bailing out" as you could see when, for instance, running a Seq Scan with a LIMIT 5.

Example schema, with a main table and a secondary one: secondary columns will only be returned, never filtered on.

drop table if exists secondary;
drop table if exists main;

create table main(id int primary key not null, main_column int);
create index main_column on main(main_column);
insert into main(id, main_column) SELECT i, i % 3000 from generate_series( 1, 1000000, 1) i;
create table secondary(id serial primary key not null, main_id int references main(id) not null, secondary_column int);
create unique index secondary_main_id on secondary(main_id);
insert into secondary(main_id, secondary_column) SELECT i, (i + 17) % 113 from generate_series( 1, 1000000, 1) i;

analyze main;
analyze secondary;

Example query:

explain analyze verbose select main.id, main_column, secondary_column
from main
left join secondary on main.id = secondary.main_id
where main_column = 5
order by main.id
limit 50;

This is the most "obvious" way of writing the query, takes on average around 5ms on my computer.

Explain:

Limit  (cost=3742.93..3743.05 rows=50 width=12) (actual time=5.010..5.322 rows=50 loops=1)
  Output: main.id, main.main_column, secondary.secondary_column
  ->  Sort  (cost=3742.93..3743.76 rows=332 width=12) (actual time=5.006..5.094 rows=50 loops=1)
        Output: main.id, main.main_column, secondary.secondary_column
        Sort Key: main.id
        Sort Method: top-N heapsort  Memory: 27kB
        ->  Nested Loop Left Join  (cost=11.42..3731.90 rows=332 width=12) (actual time=0.123..4.446 rows=334 loops=1)
              Output: main.id, main.main_column, secondary.secondary_column
              Inner Unique: true
              ->  Bitmap Heap Scan on public.main  (cost=11.00..1036.99 rows=332 width=8) (actual time=0.106..1.021 rows=334 loops=1)
                    Output: main.id, main.main_column
                    Recheck Cond: (main.main_column = 5)
                    Heap Blocks: exact=334
                    ->  Bitmap Index Scan on main_column  (cost=0.00..10.92 rows=332 width=0) (actual time=0.056..0.057 rows=334 loops=1)
                          Index Cond: (main.main_column = 5)
              ->  Index Scan using secondary_main_id on public.secondary  (cost=0.42..8.12 rows=1 width=8) (actual time=0.006..0.006 rows=1 loops=334)
                    Output: secondary.id, secondary.main_id, secondary.secondary_column
                    Index Cond: (secondary.main_id = main.id)
Planning Time: 0.761 ms
Execution Time: 5.423 ms

explain analyze verbose select m.id, main_column, secondary_column
from (
    select main.id, main_column
    from main
    where main_column = 5
    order by main.id
    limit 50
) m
left join secondary on m.id = secondary.main_id
where main_column = 5
order by m.id
limit 50

This returns the same results, in 2ms. The total EXPLAIN cost is also three times higher, in line with the performance gain we're seeing.

Limit  (cost=1048.44..1057.21 rows=1 width=12) (actual time=1.219..2.027 rows=50 loops=1)
  Output: m.id, m.main_column, secondary.secondary_column
  ->  Nested Loop Left Join  (cost=1048.44..1057.21 rows=1 width=12) (actual time=1.216..1.900 rows=50 loops=1)
        Output: m.id, m.main_column, secondary.secondary_column
        Inner Unique: true
        ->  Subquery Scan on m  (cost=1048.02..1048.77 rows=1 width=8) (actual time=1.201..1.515 rows=50 loops=1)
              Output: m.id, m.main_column
              Filter: (m.main_column = 5)
              ->  Limit  (cost=1048.02..1048.14 rows=50 width=8) (actual time=1.196..1.384 rows=50 loops=1)
                    Output: main.id, main.main_column
                    ->  Sort  (cost=1048.02..1048.85 rows=332 width=8) (actual time=1.194..1.260 rows=50 loops=1)
                          Output: main.id, main.main_column
                          Sort Key: main.id
                          Sort Method: top-N heapsort  Memory: 27kB
                          ->  Bitmap Heap Scan on public.main  (cost=11.00..1036.99 rows=332 width=8) (actual time=0.054..0.753 rows=334 loops=1)
                                Output: main.id, main.main_column
                                Recheck Cond: (main.main_column = 5)
                                Heap Blocks: exact=334
                                ->  Bitmap Index Scan on main_column  (cost=0.00..10.92 rows=332 width=0) (actual time=0.029..0.030 rows=334 loops=1)
                                      Index Cond: (main.main_column = 5)
        ->  Index Scan using secondary_main_id on public.secondary  (cost=0.42..8.44 rows=1 width=8) (actual time=0.004..0.004 rows=1 loops=50)
              Output: secondary.id, secondary.main_id, secondary.secondary_column
              Index Cond: (secondary.main_id = m.id)
Planning Time: 0.161 ms
Execution Time: 2.115 ms

This is a toy dataset here, but on a real DB, the IO difference is significant (no need to fetch 1000 rows when 30 are enough), and the timing difference also quickly adds up (up to an order of magnitude slower).

So my question: is there any way to get the planner to understand that the JOIN can be applied much later in the process? It seems like something that could be applied automatically to gain a sizeable performance boost.

user_205608 · Answer

Deferred joins are good. It's usually helpful to run the limit operation on a subquery that yields only the id values. The order by....limit operation has to sort less data just to discard it.

select main.id, main.main_column, secondary.secondary_column
from main
join (
       select id
         from main
        where main_column = 5
        order by id
        limit 50
     ) selection on main.id = selection.id
left join secondary on main.id = secondary.main_id
order by main.id
limit 50

It's also possible adding id to your main_column index will help. With a BTREE index the query planner knows it can get the id values in ascending order from the index, so it may be able to skip the sort step entirely and just scan the first 50 values.

create index main_column on main(main_column, id);

Edit In a large table, the heavy lifting of your query will be the selection of the 50 main.id values to process. To get those 50 id values as cheaply as possible you can use a scan of the covering index I proposed with the subquery I proposed. Once you've got your 50 id values, looking up 50 rows' worth of details from your various tables by main.id and secondary.main_id is trivial; you have the correct indexes in place and it's a limited number of rows. Because it's a limited number of rows it won't take much time.

It looks like your table sizes are too small for various optimizations to have much effect, though. Query plans change a lot when tables are larger.

user_905902 · Answer

Alternative query, using row_number() instead of LIMIT (I think you could even omit LIMIT here):

-- prepare q3 AS
select m.id, main_column, secondary_column
from (
    select id, main_column
        , row_number() OVER (ORDER BY id, main_column) AS rn
    from main
    where main_column = 5
) m
left join secondary on m.id = secondary.main_id
WHERE m.rn <= 50
ORDER BY m.id
LIMIT 50
        ;

Puttting the subsetting into a CTE can avoid it to be merged into the main query:

PREPARE q6 AS
WITH
-- MATERIALIZED -- not needed before version 12
xxx AS (
        SELECT DISTINCT x.id
        FROM main x
        WHERE x.main_column = 5
        ORDER BY x.id
        LIMIT 50
        )
select m.id, m.main_column, s.secondary_column
from main m
left join secondary s on m.id = s.main_id
WHERE EXISTS (
        SELECT *
        FROM xxx x WHERE x.id = m.id
        )
order by m.id
-- limit 50
        ;

Can a LEFT JOIN be deferred to only apply to matching rows?

2 Answers