Initial Problem

Dump, query and the EXPLAINs are below.

row-goal-demo.dump.zip

query.sql

query-explains.sql

Synthetic trivial demo

Here is the simplified reproduction script:

DROP TABLE IF EXISTS a,b CASCADE;
CREATE TEMP TABLE a (x numeric, y numeric);
CREATE TEMP TABLE b (x numeric);
INSERT INTO a (x,y) SELECT random(), random() FROM generate_series(1,1E6);
INSERT INTO b (x) SELECT random() FROM generate_series(1,1E6);
CREATE INDEX b_idx ON b (x);
VACUUM ANALYZE a,b;

-- Current state of the problem
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, BUFFERS OFF)
SELECT * FROM a LEFT JOIN b ON (a.x = b.x AND a.y < 0.1)
ORDER BY a.x LIMIT 10;

-- An emulation of potentially more effective 'Row Goal' feature
-- (not semantically correct, just to touch the sky)
EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, BUFFERS OFF)
SELECT * FROM (SELECT x,y FROM a ORDER BY x LIMIT 10) AS q(x,y) LEFT JOIN b ON (q.x = b.x AND q.y < 0.1)
ORDER BY q.x LIMIT 10;

What do we see:

 Limit (actual rows=10 loops=1)
   ->  Sort (actual rows=10 loops=1)
         Sort Key: a.x
         Sort Method: top-N heapsort  Memory: 26kB
         ->  Hash Left Join (actual rows=1000000 loops=1)
               Hash Cond: (a.x = b.x)
               Join Filter: (a.y < 0.1)
               ->  Seq Scan on a (actual rows=1000000 loops=1)
               ->  Hash (actual rows=1000000 loops=1)
                     Buckets: 262144  Batches: 8  Memory Usage: 7297kB
                     ->  Seq Scan on b (actual rows=1000000 loops=1)
 Planning Time: 0.221 ms
 Execution Time: 998.139 ms
(13 rows)

 Limit (actual rows=10 loops=1)
   ->  Nested Loop Left Join (actual rows=10 loops=1)
         Join Filter: (a.y < 0.1)
         ->  Limit (actual rows=10 loops=1)
               ->  Sort (actual rows=10 loops=1)
                     Sort Key: a.x
                     Sort Method: top-N heapsort  Memory: 26kB
                     ->  Seq Scan on a (actual rows=1000000 loops=1)
         ->  Index Only Scan using b_idx on b (actual rows=0 loops=10)
               Index Cond: (x = a.x)
               Heap Fetches: 0
 Planning Time: 0.236 ms
 Execution Time: 157.943 ms
(13 rows)

Potential Solutions

1. Push Sort into the outer of OUTER JOIN - as the synthetic reproductive second query demonstrates.
2. ‘Lazy’ Join - do not evaluate the INNER side if the clause (a.y < 0.1) is false.

Type of Sort makes sense

Who chooses ‘SORT_TYPE_TOP_N_HEAPSORT’? state->boundUsed, sort_bounded_heap, make_bounded_heap, ExecSetTupleBound

Related

1. ‘Lazy’ Outer Join Technique https://www.postgresql.org/message-id/flat/CAKE%3DrqQ-LHuh2eVsKC7ihkRJoCBZafSR72o3Xk4Xb%3DLcQMQfsA%40mail.gmail.com
2. Claude’s explanation of the SQL Server feature:

sql_server_row_goal.md

0001-Skip-inner-scan-in-NestLoop-Left-Join-when-join-clau.patch