Message-ID: <2a6b4c49-140b-48b1-ba68-b92857ca76c9@anayrat.info>
Date: Fri, 6 Mar 2026 19:41:30 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
From: Adrien Nayrat <adrien.nayrat@anayrat.info>
Content-Language: en-US
Subject: Sort and limit push down
Autocrypt: addr=adrien.nayrat@anayrat.info; keydata=
 xsBNBFq2NEMBCAC/W92hl6qJyXV5CkWQOt3WuKA3PwlNbVY8Cuu6BN4mzT56djDn+tTcOD15
 L6ExsIbL7p6y/w4lPtMM6Vmy6ByKVAZWNHFpvS6DvTaTDf/mfm1WwixOx5qLg4WyYuiohlCd
 8BebhrhS8Lav+Rn29cRUefQHQcnSyc0bX/6ebDgY7hTAvV/f9BJ+XT6uHfrmby0STORIO+Du
 xekN6rU8ZIORxsdvE9dda3zbQcNLtVe6Y3GJvz/AShI9HYvGkrJchsWeR8aiGmfaX5E/jEme
 Oe4T6nd/NmoZ8cEjF3rsbE3SYNjAsWmZOZ8HzDZ1gWSY4VtqpIMgF4jJpCu0dyogGLipABEB
 AAHNKkFkcmllbiBOYXlyYXQgPGFkcmllbi5uYXlyYXRAYW5heXJhdC5pbmZvPsLAlQQTAQgA
 PwIbAwYLCQgHAwIGFQgCCQoLBBYCAwECHgECF4AWIQQQX3VDo29CNmHcAhoktQFHcMXNFwUC
 ZH2miQUJD2xp3QAKCRAktQFHcMXNFz9RB/0ddaJECoc5DmEdrVOl2KTL/y/2z12U8k5fsCq+
 jOkLMz+AL2qnbtltdm7IZDyJ2yuYQg/0TWoYTl5LRvryEZGPy2gNhQJzsToTreDERw0IZxB4
 6x2+mtmIFPtk/d/9dTqsmYgoXEPViVs0Prl6YVk3ZyHmIqGoEFimuCAuKeOEfbMjMIIivrHL
 LwTtrrChqmm7t8EQf9nYFYMM37/YIn1VP2t7uwIkL+47haAY2qgbMVybXC1GabH3vNotFRci
 6aQCuwlmEuY98BMRcVgiEHuDqtWvvRdQ5OTuXOIr+cMOsPohK3Ig/k42txKoRvaCvGl3PSO2
 36TfulOilpuDBVCczsBNBFq2NEMBCACrk3pVPDk6XhBKgkVqmAX8uyqd3lfTZwXtkOpMLxzp
 iT3a6MWatHk1N9+SSTRl7KzLoOPoWDUMOE/l5OHDsLJN0JWnwQhazhFiujtePmdUVeAWkvvn
 SPaMKB/1UcRjuGuwSrVnZQc9faHi1fFhqCH00MntQ+/XJViQXWt92L2cw6VsBXM0ixVRTc7f
 vvQA1+sMBP5yAONgtRgOZxPH9MvL+Dw8Tae63kE6HwiymrrkHEi4AUhaqKGULj32a8FWgm42
 b4PIujE0w4wANrpct4t/aVDkdQ09Qd3ciXV7S+G80aP683ygplRFkZWwIJzwcNeHrJPyMDi9
 1i8rDNWe9PDxABEBAAHCwHwEGAEIACYCGwwWIQQQX3VDo29CNmHcAhoktQFHcMXNFwUCZH2q
 +wUJDx1P3QAKCRAktQFHcMXNF+LMB/9rWlIafKLfUqWLRhzzMEjq7j8Xuhv6VNDsO7+YCJq5
 YGtqAuvImxmrNtPCZqtoD+JUCMacGSjh/L7XhSy72zMkwDeFqj7IvrN3+CStCLV1lTPsE/AO
 yQzSaE6A8WfKLjEcZo+4yc33i/rfb0bCRj2Xm68g4XFw2EZIiUgR73L5n4+ga1gzAXnHEyfP
 iHB1jCwZtzjE74z6msmhAnlMDV5nKPKXsjP06kC9RCTzxJe+12od7V7sNLolqYy4upYxRowb
 9EWgWsbRNzbQTTZeTfTCBZUbwk3b1HcKCRQr66WY7vDERYuSUMlodiyL3oXQDXbiLWkMHxTj
 1aH1EzXQiGC7
To: PostgreSQL General <pgsql-general@lists.postgresql.org>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: <https://www.postgresql.org/message-id/2a6b4c49-140b-48b1-ba68-b92857ca76c9%40anayrat.info>
Precedence: bulk

Hello,

While working on a query, I found a possible optimization by pushing 
down sort and limit :


create table t1 (id int primary key) ;
create table t2 (c1_id int references t1(id), c2 int, primary 
key(c1_id,c2) );


insert into t1 values (1),(2);
insert into t2 (c1_id,c2) select 1,i from generate_series(1,10000) i;
insert into t2 (c1_id,c2) select 2,i from generate_series(1,10000) i;

create index on t2 (c1_id,c2);

vacuum analyze t1;
vacuum analyze t2;

Here is a simple query :

EXPLAIN SELECT * FROM t1
   JOIN t2 ON t1.id = t2.c1_id
WHERE t1.id = 1
ORDER BY c2 LIMIT 50;

It is quite straightforward, Postgres is able to read the index in the 
order (id,c2) :

  Limit  (cost=0.29..2.08 rows=50 width=12)
    ->  Nested Loop  (cost=0.29..359.32 rows=10000 width=12)
          ->  Index Only Scan using t2_c1_id_c2_idx on t2 
(cost=0.29..233.29 rows=10000 width=8)
                Index Cond: (c1_id = 1)
          ->  Materialize  (cost=0.00..1.03 rows=1 width=4)
                ->  Seq Scan on t1  (cost=0.00..1.02 rows=1 width=4)
                      Filter: (id = 1)


(I am surprised by this choice. I would rather first do a seqscan on t1 
then read t2 by traversing index)


But if I want two t1 ids :

EXPLAIN SELECT * FROM t1
   JOIN t2 ON t1.id = t2.c1_id
WHERE t1.id IN (1,2)
ORDER BY c2 LIMIT 50;

Postgres has no choice to read all t2 records, join them, sort, then limit :

  Limit  (cost=1118.19..1118.31 rows=50 width=12)
    ->  Sort  (cost=1118.19..1168.19 rows=20000 width=12)
          Sort Key: t2.c2
          ->  Hash Join  (cost=1.05..453.80 rows=20000 width=12)
                Hash Cond: (t2.c1_id = t1.id)
                ->  Seq Scan on t2  (cost=0.00..289.00 rows=20000 width=8)
                ->  Hash  (cost=1.02..1.02 rows=2 width=4)
                      ->  Seq Scan on t1  (cost=0.00..1.02 rows=2 width=4)
                            Filter: (id = ANY ('{1,2}'::integer[]))


We could push the order and limit farther in the plan :

EXPLAIN SELECT * FROM (
   SELECT * FROM t1 WHERE id IN (1, 2)) t1,
   LATERAL (
     SELECT * FROM t2
     WHERE c1_id = t1.id
     ORDER BY c2
     LIMIT 50) lat
ORDER BY lat.c2
LIMIT 50;

  Limit  (cost=8.25..8.38 rows=50 width=12)
    ->  Sort  (cost=8.25..8.50 rows=100 width=12)
          Sort Key: t2.c2
          ->  Nested Loop  (cost=0.29..4.93 rows=100 width=12)
                ->  Seq Scan on t1  (cost=0.00..1.02 rows=2 width=4)
                      Filter: (id = ANY ('{1,2}'::integer[]))
                ->  Limit  (cost=0.29..1.45 rows=50 width=8)
                      ->  Index Only Scan using t2_c1_id_c2_idx on t2 
(cost=0.29..233.29 rows=10000 width=8)
                            Index Cond: (c1_id = t1.id)


Difference can be huge, 90 blocks 11ms vs 6 blocks and 0.6ms on this 
simple example.

Am I wrong ? It also looks like close to Index skip scan work.

Thanks

-- 
Adrien NAYRAT