MIME-Version: 1.0
From: WU Yan <4wuyan@gmail.com>
Date: Mon, 17 Feb 2025 17:38:49 +1100
Message-ID: <CAAdwFAwm6HwXM_cuPWZBxrxX4E7pBdVg=KcVDSP6q9ume3hYpQ@mail.gmail.com>
Subject: Wasteful nested loop join when there is `limit` in the query
To: pgsql-general@lists.postgresql.org
Content-Type: multipart/alternative; boundary="000000000000953f0c062e50c745"
Archived-At: <https://www.postgresql.org/message-id/CAAdwFAwm6HwXM_cuPWZBxrxX4E7pBdVg%3DKcVDSP6q9ume3hYpQ%40mail.gmail.com>
Precedence: bulk

--000000000000953f0c062e50c745
Content-Type: text/plain; charset="UTF-8"

Hello everyone, I am still learning postgres planner and performance
optimization, so please kindly point out if I missed something obvious.

I've noticed that postgres joins all rows in two tables, even though
there's a `limit` in the query. It means lots of joined rows are discarded
eventually, and the performance can be better if postgres planner can do
`limit` before the `join`.

Here's my example. I am running postgres 17.3 in a container
```sh
docker run --rm -e POSTGRES_PASSWORD=mysecretpassword -d -p 5432:5432
postgres:17.3
```

```sql
create table department(
    id int primary key,
    name text);
create table employee(
    id int primary key,
    name text,
    department_id int);
insert into department values
    (1, 'sales'),
    (2, 'support'),
    (3, 'research'),
    (4, 'management'),
    (5, 'hr');
insert into employee values
    (101, 'alice', 1),
    (102, 'bob', 2),
    (103, 'ccc', 3),
    (104, 'ddd', 4),
    (105, 'eee', 999);
analyze department;
analyze employee;

set enable_mergejoin = off;
set enable_hashjoin = off;

explain analyze
select *
from employee left outer join department
    on employee.department_id = department.id
order by employee.name limit 2;
```

In this simple setup, I want to see the top 2 employees by name, and check
their department info. Here's the query plan:
```
                                                         QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=2.49..2.49 rows=2 width=23) (actual time=0.037..0.038 rows=2
loops=1)
   ->  Sort  (cost=2.49..2.50 rows=5 width=23) (actual time=0.036..0.037
rows=2 loops=1)
         Sort Key: employee.name
         Sort Method: top-N heapsort  Memory: 25kB
         ->  Nested Loop Left Join  (cost=0.00..2.44 rows=5 width=23)
(actual time=0.014..0.021 rows=5 loops=1)
               Join Filter: (employee.department_id = department.id)
               Rows Removed by Join Filter: 11
               ->  Seq Scan on employee  (cost=0.00..1.05 rows=5 width=12)
(actual time=0.006..0.007 rows=5 loops=1)
               ->  Materialize  (cost=0.00..1.07 rows=5 width=11) (actual
time=0.001..0.001 rows=3 loops=5)
                     ->  Seq Scan on department  (cost=0.00..1.05 rows=5
width=11) (actual time=0.001..0.002 rows=5 loops=1)
 Planning Time: 0.248 ms
 Execution Time: 0.062 ms
(12 rows)
```

Note `loops=5` in the plan. My understanding is, all 5 rows in table
employee are joined, although we only need 2. I think join before limit is
necessary if we do not know whether join will create multiple rows or
eliminate rows. However, in this setup, it's left outer join on a primary
key, so we know one employee will produce exactly one row. Similar
assumption can be made for `a inner join b on a.x = b.x` when a.x is a
foreign key referencing b.x and b.x has a unique constraint.


At the moment, my workaround is to rewrite the query with CTE. I need to
write `order by ... limit ...` twice. `loops=2` is observed.
```
postgres=# explain analyze
with t as (
    select * from employee order by employee.name limit 2
) select *
from t left outer join department on t.department_id = department.id
order by t.name limit 2;
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=1.10..2.32 rows=2 width=23) (actual time=0.045..0.049 rows=2
loops=1)
   ->  Nested Loop Left Join  (cost=1.10..2.32 rows=2 width=23) (actual
time=0.044..0.047 rows=2 loops=1)
         Join Filter: (employee.department_id = department.id)
         Rows Removed by Join Filter: 1
         ->  Limit  (cost=1.10..1.10 rows=2 width=12) (actual
time=0.032..0.033 rows=2 loops=1)
               ->  Sort  (cost=1.10..1.11 rows=5 width=12) (actual
time=0.032..0.033 rows=2 loops=1)
                     Sort Key: employee.name
                     Sort Method: top-N heapsort  Memory: 25kB
                     ->  Seq Scan on employee  (cost=0.00..1.05 rows=5
width=12) (actual time=0.015..0.016 rows=5 loops=1)
         ->  Materialize  (cost=0.00..1.07 rows=5 width=11) (actual
time=0.004..0.004 rows=2 loops=2)
               ->  Seq Scan on department  (cost=0.00..1.05 rows=5
width=11) (actual time=0.004..0.005 rows=2 loops=1)
 Planning Time: 0.196 ms
 Execution Time: 0.103 ms
(13 rows)
```

I wonder whether there's a better way to influence the planner to push the
`limit` down to the `employee` table first, or this optimization strategy
is not yet in the planner. The demo is trivial, but in some real cases,
it's possible to select top 100 from 1 million rows. Sorting 1 million rows
is slow but necessary and acceptable, but wasteful nested loop join on
millions of rows can make the performance much slower. Even worse, the
wasteful join can happen multiple times when it's more than 2 tables
joining.

Thank you

Best regards
Yan

--000000000000953f0c062e50c745
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hello everyone, I am still learning postgres planner and p=
erformance optimization, so please kindly point out if I missed something o=
bvious.<br><br>I&#39;ve noticed that postgres joins all rows in two tables,=
 even though there&#39;s a `limit` in the query. It means lots of joined ro=
ws are discarded eventually, and the performance can be better if postgres =
planner can do `limit` before the `join`.<br><br>Here&#39;s my example. I a=
m running postgres 17.3 in a container<br>```sh<br>docker run --rm -e POSTG=
RES_PASSWORD=3Dmysecretpassword -d -p 5432:5432 postgres:17.3<br>```<br><br=
>```sql<br>create table department(<br>=C2=A0 =C2=A0 id int primary key,<br=
>=C2=A0 =C2=A0 name text);<br>create table employee(<br>=C2=A0 =C2=A0 id in=
t primary key,<br>=C2=A0 =C2=A0 name text,<br>=C2=A0 =C2=A0 department_id i=
nt);<br>insert into department values<br>=C2=A0 =C2=A0 (1, &#39;sales&#39;)=
,<br>=C2=A0 =C2=A0 (2, &#39;support&#39;),<br>=C2=A0 =C2=A0 (3, &#39;resear=
ch&#39;),<br>=C2=A0 =C2=A0 (4, &#39;management&#39;),<br>=C2=A0 =C2=A0 (5, =
&#39;hr&#39;);<br>insert into employee values<br>=C2=A0 =C2=A0 (101, &#39;a=
lice&#39;, 1),<br>=C2=A0 =C2=A0 (102, &#39;bob&#39;, 2),<br>=C2=A0 =C2=A0 (=
103, &#39;ccc&#39;, 3),<br>=C2=A0 =C2=A0 (104, &#39;ddd&#39;, 4),<br>=C2=A0=
 =C2=A0 (105, &#39;eee&#39;, 999);<br>analyze department;<br>analyze employ=
ee;<br><br>set enable_mergejoin =3D off;<br>set enable_hashjoin =3D off;<br=
><br>explain analyze<br>select *<br>from employee left outer join departmen=
t<br>=C2=A0 =C2=A0 on employee.department_id =3D <a href=3D"http://departme=
nt.id">department.id</a><br>order by <a href=3D"http://employee.name">emplo=
yee.name</a> limit 2;<br>```<br><br>In this simple setup, I want to see the=
 top 2 employees by name, and check their department info. Here&#39;s the q=
uery plan:<br>```<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0QUERY PLAN<br>----------------------------------------------------------=
-------------------------------------------------------------------<br>=C2=
=A0Limit =C2=A0(cost=3D2.49..2.49 rows=3D2 width=3D23) (actual time=3D0.037=
..0.038 rows=3D2 loops=3D1)<br>=C2=A0 =C2=A0-&gt; =C2=A0Sort =C2=A0(cost=3D=
2.49..2.50 rows=3D5 width=3D23) (actual time=3D0.036..0.037 rows=3D2 loops=
=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Sort Key: <a href=3D"http://empl=
oyee.name">employee.name</a><br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Sort Meth=
od: top-N heapsort =C2=A0Memory: 25kB<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
-&gt; =C2=A0Nested Loop Left Join =C2=A0(cost=3D0.00..2.44 rows=3D5 width=
=3D23) (actual time=3D0.014..0.021 rows=3D5 loops=3D1)<br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Join Filter: (employee.department_id =
=3D <a href=3D"http://department.id">department.id</a>)<br>=C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Rows Removed by Join Filter: 11<br=
>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=A0Seq Sca=
n on employee =C2=A0(cost=3D0.00..1.05 rows=3D5 width=3D12) (actual time=3D=
0.006..0.007 rows=3D5 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0-&gt; =C2=A0Materialize =C2=A0(cost=3D0.00..1.07 rows=3D5 =
width=3D11) (actual time=3D0.001..0.001 rows=3D3 loops=3D5)<br>=C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=
=A0Seq Scan on department =C2=A0(cost=3D0.00..1.05 rows=3D5 width=3D11) (ac=
tual time=3D0.001..0.002 rows=3D5 loops=3D1)<br>=C2=A0Planning Time: 0.248 =
ms<br>=C2=A0Execution Time: 0.062 ms<br>(12 rows)<br>```<br><br>Note `loops=
=3D5` in the plan. My understanding is, all 5 rows in table employee are jo=
ined, although we only need 2. I think join before limit is necessary if we=
 do not know whether join will create multiple rows or eliminate rows. Howe=
ver, in this setup, it&#39;s left outer join on a primary key, so we know o=
ne employee will produce exactly one row. Similar assumption can be made fo=
r `a inner join b on a.x =3D b.x` when a.x is a foreign key referencing b.x=
 and b.x has a unique constraint.<br><br><br>At the moment, my workaround i=
s to rewrite the query with CTE. I need to write `order by ... limit ...` t=
wice. `loops=3D2` is observed.<br>```<br>postgres=3D# explain analyze<br>wi=
th t as (<br>=C2=A0 =C2=A0 select * from employee order by <a href=3D"http:=
//employee.name">employee.name</a> limit 2<br>) select *<br>from t left out=
er join department on t.department_id =3D <a href=3D"http://department.id">=
department.id</a><br>order by <a href=3D"http://t.name">t.name</a> limit 2;=
<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 QUERY PLAN<br>--------=
---------------------------------------------------------------------------=
----------------------------------------<br>=C2=A0Limit =C2=A0(cost=3D1.10.=
.2.32 rows=3D2 width=3D23) (actual time=3D0.045..0.049 rows=3D2 loops=3D1)<=
br>=C2=A0 =C2=A0-&gt; =C2=A0Nested Loop Left Join =C2=A0(cost=3D1.10..2.32 =
rows=3D2 width=3D23) (actual time=3D0.044..0.047 rows=3D2 loops=3D1)<br>=C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Join Filter: (employee.department_id =3D <a =
href=3D"http://department.id">department.id</a>)<br>=C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0Rows Removed by Join Filter: 1<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0-&gt; =C2=A0Limit =C2=A0(cost=3D1.10..1.10 rows=3D2 width=3D12) (actu=
al time=3D0.032..0.033 rows=3D2 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=A0Sort =C2=A0(cost=3D1.10..1.11 rows=
=3D5 width=3D12) (actual time=3D0.032..0.033 rows=3D2 loops=3D1)<br>=C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Sort K=
ey: <a href=3D"http://employee.name">employee.name</a><br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Sort Method: top=
-N heapsort =C2=A0Memory: 25kB<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=A0Seq Scan on employee =C2=A0(=
cost=3D0.00..1.05 rows=3D5 width=3D12) (actual time=3D0.015..0.016 rows=3D5=
 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=A0Materialize =
=C2=A0(cost=3D0.00..1.07 rows=3D5 width=3D11) (actual time=3D0.004..0.004 r=
ows=3D2 loops=3D2)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0-&gt; =C2=A0Seq Scan on department =C2=A0(cost=3D0.00..1.05 rows=3D5 wid=
th=3D11) (actual time=3D0.004..0.005 rows=3D2 loops=3D1)<br>=C2=A0Planning =
Time: 0.196 ms<br>=C2=A0Execution Time: 0.103 ms<br>(13 rows)<br>```<br><br=
>I wonder whether there&#39;s a better way to influence the planner to push=
 the `limit` down to the `employee` table first, or this optimization strat=
egy is not yet in the planner. The demo is trivial, but in some real cases,=
 it&#39;s possible to select top 100 from 1 million rows. Sorting 1 million=
 rows is slow but necessary and acceptable, but wasteful nested loop join o=
n millions of rows can make the performance much slower. Even worse, the wa=
steful join can happen multiple times when it&#39;s more than 2 tables join=
ing.<br><br>Thank you<br><br>Best regards<br>Yan</div>

--000000000000953f0c062e50c745--