MIME-Version: 1.0
References: <CAAdwFAwm6HwXM_cuPWZBxrxX4E7pBdVg=KcVDSP6q9ume3hYpQ@mail.gmail.com>
 <744079.1739775701@sss.pgh.pa.us>
In-Reply-To: <744079.1739775701@sss.pgh.pa.us>
From: WU Yan <4wuyan@gmail.com>
Date: Tue, 18 Feb 2025 12:14:23 +1100
Message-ID: <CAAdwFAxRwMeamr2f88rjLZCWRHmBk=FeWPuuf6TiYqEw64_F9g@mail.gmail.com>
Subject: Re: Wasteful nested loop join when there is `limit` in the query
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: pgsql-general@lists.postgresql.org
Content-Type: multipart/alternative; boundary="00000000000025840e062e605d2b"
Archived-At: <https://www.postgresql.org/message-id/CAAdwFAxRwMeamr2f88rjLZCWRHmBk%3DFeWPuuf6TiYqEw64_F9g%40mail.gmail.com>
Precedence: bulk

--00000000000025840e062e605d2b
Content-Type: text/plain; charset="UTF-8"

Thank you for your help, Tom.

You are right. I added an index on employee.name (by making it unique), and
then postgres can visit employee table in a pre-sorted manner, and can exit
early without joining more rows.


Just sharing the tweak I did to the example, if anyone else is interested
in a quick test. I also populated 1 million rows so the example is no
longer a toy demo.

```sql
drop table if exists department;
drop table if exists employee;

create table department(
    id int primary key,
    name text);
create table employee(
    id int primary key,
    name text unique,
    department_id int);

INSERT INTO department (id, name)
SELECT i+1, 'department' || i+1
FROM generate_series(0, 9) AS i;

INSERT INTO employee (id, name, department_id)
SELECT i+1, 'name' || i+1, i % 10 +1
FROM generate_series(0, 999999) AS i;

analyze department;
analyze employee;

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

And here is the plan:
```
                                                                     QUERY
PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.57..1.36 rows=10 width=34) (actual time=0.017..0.030
rows=10 loops=1)
   ->  Nested Loop Left Join  (cost=0.57..78630.06 rows=1000000 width=34)
(actual time=0.016..0.028 rows=10 loops=1)
         ->  Index Scan using employee_name_key on employee
 (cost=0.42..54855.68 rows=1000000 width=18) (actual time=0.008..0.015
rows=10 loops=1)
         ->  Memoize  (cost=0.15..0.16 rows=1 width=16) (actual
time=0.001..0.001 rows=1 loops=10)
               Cache Key: employee.department_id
               Cache Mode: logical
               Hits: 6  Misses: 4  Evictions: 0  Overflows: 0  Memory
Usage: 1kB
               ->  Index Scan using department_pkey on department
 (cost=0.14..0.15 rows=1 width=16) (actual time=0.001..0.001 rows=1 loops=4)
                     Index Cond: (id = employee.department_id)
 Planning Time: 0.189 ms
 Execution Time: 0.045 ms
(11 rows)
```

Personally I still wish someday postgres can push down `limit` node
together with `sort` node when certain conditions are met, so that there's
no need to add an index :D

Thank you again for your help!

On Mon, 17 Feb 2025 at 18:01, Tom Lane <tgl@sss.pgh.pa.us> wrote:

> WU Yan <4wuyan@gmail.com> writes:
> > Hello everyone, I am still learning postgres planner and performance
> > optimization, so please kindly point out if I missed something obvious.
>
> An index on employee.name would likely help here.  Even if we had
> an optimization for pushing LIMIT down through a join (which you
> are right, we don't) it could not push the LIMIT through a sort step.
> So you need presorted output from the scan of "employee".  I think
> this example would behave better with that.  You may also need to
> test with non-toy amounts of data to get the plan you think is
> better: an example with only half a dozen rows is going to be
> swamped by startup costs.
>
>                         regards, tom lane
>

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

<div dir=3D"ltr">Thank you for your help, Tom.<br><br>You are right. I adde=
d an index on <a href=3D"http://employee.name">employee.name</a> (by making=
 it unique), and then postgres can visit employee table in a pre-sorted man=
ner, and can exit early without joining more rows.<br><br><br>Just sharing =
the tweak I did to the example, if anyone else is interested in a quick tes=
t. I also populated 1 million rows so the example is no longer a toy demo.<=
br><br>```sql<br>drop table if exists department;<br>drop table if exists e=
mployee;<br><br>create table department(<br>=C2=A0 =C2=A0 id int primary ke=
y,<br>=C2=A0 =C2=A0 name text);<br>create table employee(<br>=C2=A0 =C2=A0 =
id int primary key,<br>=C2=A0 =C2=A0 name text unique,<br>=C2=A0 =C2=A0 dep=
artment_id int);<br><br>INSERT INTO department (id, name)<br>SELECT i+1, &#=
39;department&#39; || i+1<br>FROM generate_series(0, 9) AS i;<br><br>INSERT=
 INTO employee (id, name, department_id)<br>SELECT i+1, &#39;name&#39; || i=
+1, i % 10 +1<br>FROM generate_series(0, 999999) AS i;<br><br>analyze depar=
tment;<br>analyze employee;<br><br>explain analyze<br>select *<br>from empl=
oyee left outer join department<br>=C2=A0 =C2=A0 on employee.department_id =
=3D <a href=3D"http://department.id">department.id</a><br>order by <a href=
=3D"http://employee.name">employee.name</a> limit 10;<br>```<br><br>And her=
e is the 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=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0QUERY PLAN<br>-------------=
---------------------------------------------------------------------------=
------------------------------------------------------------<br>=C2=A0Limit=
 =C2=A0(cost=3D0.57..1.36 rows=3D10 width=3D34) (actual time=3D0.017..0.030=
 rows=3D10 loops=3D1)<br>=C2=A0 =C2=A0-&gt; =C2=A0Nested Loop Left Join =C2=
=A0(cost=3D0.57..78630.06 rows=3D1000000 width=3D34) (actual time=3D0.016..=
0.028 rows=3D10 loops=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=
=A0Index Scan using employee_name_key on employee =C2=A0(cost=3D0.42..54855=
.68 rows=3D1000000 width=3D18) (actual time=3D0.008..0.015 rows=3D10 loops=
=3D1)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0-&gt; =C2=A0Memoize =C2=A0(cost=
=3D0.15..0.16 rows=3D1 width=3D16) (actual time=3D0.001..0.001 rows=3D1 loo=
ps=3D10)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Cache Ke=
y: employee.department_id<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0Cache Mode: logical<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0Hits: 6 =C2=A0Misses: 4 =C2=A0Evictions: 0 =C2=A0Overflows: 0 =
=C2=A0Memory Usage: 1kB<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0-&gt; =C2=A0Index Scan using department_pkey on department =C2=A0(co=
st=3D0.14..0.15 rows=3D1 width=3D16) (actual time=3D0.001..0.001 rows=3D1 l=
oops=3D4)<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0Index Cond: (id =3D employee.department_id)<br>=C2=A0Planning=
 Time: 0.189 ms<br>=C2=A0Execution Time: 0.045 ms<br>(11 rows)<br>```<br><b=
r>Personally I still wish someday postgres can push down `limit` node toget=
her with `sort` node when certain conditions are met, so that there&#39;s n=
o need to add an index :D<br><br>Thank you again for your help!</div><br><d=
iv class=3D"gmail_quote gmail_quote_container"><div dir=3D"ltr" class=3D"gm=
ail_attr">On Mon, 17 Feb 2025 at 18:01, Tom Lane &lt;<a href=3D"mailto:tgl@=
sss.pgh.pa.us">tgl@sss.pgh.pa.us</a>&gt; wrote:<br></div><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rg=
b(204,204,204);padding-left:1ex">WU Yan &lt;<a href=3D"mailto:4wuyan@gmail.=
com" target=3D"_blank">4wuyan@gmail.com</a>&gt; writes:<br>
&gt; Hello everyone, I am still learning postgres planner and performance<b=
r>
&gt; optimization, so please kindly point out if I missed something obvious=
.<br>
<br>
An index on <a href=3D"http://employee.name" rel=3D"noreferrer" target=3D"_=
blank">employee.name</a> would likely help here.=C2=A0 Even if we had<br>
an optimization for pushing LIMIT down through a join (which you<br>
are right, we don&#39;t) it could not push the LIMIT through a sort step.<b=
r>
So you need presorted output from the scan of &quot;employee&quot;.=C2=A0 I=
 think<br>
this example would behave better with that.=C2=A0 You may also need to<br>
test with non-toy amounts of data to get the plan you think is<br>
better: an example with only half a dozen rows is going to be<br>
swamped by startup costs.<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 regards, tom lane<br>
</blockquote></div>

--00000000000025840e062e605d2b--