Subject: Re: Should consider materializing the cheapest inner path in consider_parallel_nestloop()

From: Robert Haas <[email-masked]>
Date: Thu, 7 Sep 2023 15:14:50 -0400

On Tue, Sep 5, 2023 at 8:07 AM Richard Guo <[email-masked]> wrote:
> Yeah, this seems an omission in commit 45be99f8.

It's been a while, but I think I omitted this deliberately because I
didn't really understand the value of it and wanted to keep the
planning cost down.

The example query provided here seems rather artificial. Surely few
people write a join clause that references neither of the tables being
joined. Is there a more realistic case where this makes a big
difference?

-- 
Robert Haas
EDB: http://www.enterprisedb.com

---

From: Richard Guo <[email-masked]>
Date: Fri, 8 Sep 2023 14:06:44 +0800

> joined. Is there a more realistic case where this makes a big

Yes the given example query is not that convincing.  I tried a query
with plans as below (after some GUC setting) which might be more
realistic in real world.

unpatched:

explain select * from partsupp join lineitem on l_partkey > ps_partkey;
                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Gather  (cost=0.00..5522666.44 rows=160466667 width=301)
   Workers Planned: 4
   ->  Nested Loop  (cost=0.00..5522666.44 rows=40116667 width=301)
         Join Filter: (lineitem.l_partkey > partsupp.ps_partkey)
         ->  Parallel Seq Scan on lineitem  (cost=0.00..1518.44 rows=15044
width=144)
         ->  Seq Scan on partsupp  (cost=0.00..267.00 rows=8000 width=157)
(6 rows)

patched:

explain select * from partsupp join lineitem on l_partkey > ps_partkey;
                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Gather  (cost=0.00..1807085.44 rows=160466667 width=301)
   Workers Planned: 4
   ->  Nested Loop  (cost=0.00..1807085.44 rows=40116667 width=301)
         Join Filter: (lineitem.l_partkey > partsupp.ps_partkey)
         ->  Parallel Seq Scan on lineitem  (cost=0.00..1518.44 rows=15044
width=144)
         ->  Materialize  (cost=0.00..307.00 rows=8000 width=157)
               ->  Seq Scan on partsupp  (cost=0.00..267.00 rows=8000
width=157)
(7 rows)

The execution time (ms) are (avg of 3 runs):

unpatched:  71769.21
patched:    65510.04

So we can see some (~9%) performance gains in this case.

Thanks
Richard

---

From: tender wang <[email-masked]>
Date: Wed, 27 Sep 2023 21:06:03 +0800

Hi tom,
   Do you have any comments or suggestions on this issue? Thanks.

---

From: David Rowley <[email-masked]>
Date: Thu, 28 Sep 2023 12:41:03 +1300

> didn't really understand the value of it and wanted to keep the

I think the value is potentially not having to repeatedly execute some
expensive rescan to the nested loop join once for each outer-side
tuple.

The planning cost is something to consider for sure, but it seems
strange that we deemed it worthy to consider material paths for the
non-parallel input paths but draw the line for the parallel/partial
ones. It seems to me that the additional costs and the possible
benefits are the same for both.

David

---

From: David Rowley <[email-masked]>
Date: Thu, 28 Sep 2023 12:49:47 +1300

On Fri, 8 Sept 2023 at 19:14, Richard Guo <[email-masked]> wrote:
>          ->  Parallel Seq Scan on lineitem  (cost=0.00..1518.44 rows=15044 width=144)

This gap would be wider if the partsupp Seq Scan were filtering off
some rows and wider still if you added more rows to lineitem.
However, a clauseless seqscan is not the most compelling use case
below a material node. The inner side of the nested loop could be some
subquery that takes 6 days to complete. Running the 6 day query ~15044
times seems like something that would be good to avoid.

It seems worth considering Material paths to me.  I think that the
above example could be tuned any way you like to make it look better
or worse.

David

---

From: Alena Rybakina <[email-masked]>
Date: Wed, 18 Oct 2023 16:44:08 +0300

Hi!

Thank you for your work on the subject.

I reviewed your patch and found that your commit message does not fully 
explain your code, in addition, I found several spelling mistakes.

I think it's better to change to:

With parallel seqscan, we should consider materializing the cheapest 
inner path in
case of nested loop if it doesn't contain a unique node or it is unsafe 
to use it in a subquery.

Besides, I couldn't understand why we again check that material path is 
safe?

if (matpath != NULL && matpath->parallel_safe)
             try_partial_nestloop_path(root, joinrel, outerpath, matpath,
                                       pathkeys, jointype, extra);

-- 
Regards,
Alena Rybakina

---

From: "Andrey M. Borodin" <[email-masked]>
Date: Mon, 8 Apr 2024 12:40:17 +0300

> On 27 Sep 2023, at 16:06, tender wang <[email-masked]> wrote:
> 
Hi Tender,

there are some review comments in the thread, that you might be interested in.
I'll mark this [0] entry "Waiting on Author" and move to next CF.

Thanks!

Best regards, Andrey Borodin.

[0]https://commitfest.postgresql.org/47/4549/

---

From: Tender Wang <[email-masked]>
Date: Mon, 8 Apr 2024 18:54:41 +0800

> I'll mark this [0] entry "Waiting on Author" and move to next CF.

 Thank you for the reminder.  I will update the patch later.
I also deeply hope to get more advice about this patch.
(even the advice that not worth  continuint to work on this patch).

Thanks.

Thanks!

-- 
Tender Wang
OpenPie:  https://en.openpie.com/

---

From: Tender Wang <[email-masked]>
Date: Tue, 23 Apr 2024 16:59:42 +0800

> [0]https://commitfest.postgresql.org/47/4549/

I have rebased master and fixed a plan diff case.
-- 
Tender Wang
OpenPie:  https://en.openpie.com/

---

From: Tomasz Rybak <[email-masked]>
Date: Thu, 30 May 2024 22:21:14 +0200

On Tue, 2024-04-23 at 16:59 +0800, Tender Wang wrote:
[ cut ]
> I have rebased master and fixed a plan diff case.

We (me, Paul Jungwirth, and Yuki Fujii) reviewed this patch
at PgConf.dev Patch Review Workshop.
Here are our findings.

Patch tries to allow for using materialization together
with parallel subqueries.
It applies cleanly on 8fea1bd5411b793697a4c9087c403887e050c4ac
(current HEAD).
Tests pass locally on macOS and Linux in VM under Windows.
Tests are also green in cfbot (for last 2 weeks; they were
red previously, probably because of need to rebase).

Please add more tests.  Especially please add some negative tests;
current patch checks that it is safe to apply materialization. It would
be helpful to add tests checking that materialization is not applied
in both checked cases:
1. when inner join path is not parallel safe
2. when matpath is not parallel safe

This patch tries to apply materialization only when join type
is not JOIN_UNIQUE_INNER. Comment mentions this, but does not
explain why. So please either add comment describing reason for that
or try enabling materialization in such a case.

Best regards.

-- 
Tomasz Rybak, Debian Developer <[email-masked]>
GPG: A565 CE64 F866 A258 4DDC F9C7 ECB7 3E37 E887 AA8C

---

From: Tender Wang <[email-masked]>
Date: Tue, 4 Jun 2024 18:51:02 +0800

> at PgConf.dev Patch Review Workshop.

Thanks for reviewing this patch.

> 2. when matpath is not parallel safe

I added a test case that inner rel is not parallel safe. Actually, matpath
will not create
if inner rel is not parallel safe. So I didn't add test case for the
second  scenario.

> or try enabling materialization in such a case.

Yeah, Richard commented the v1 patch about JOIN_UNIQUE_INNER in [1]

* I think we should not consider materializing the cheapest inner path
if we're doing JOIN_UNIQUE_INNER, because in this case we have to
unique-ify the inner path.

We don't consider material inner path if jointype is JOIN_UNIQUE_INNER in
match_unsorted_order().
So here is as same logic as match_unsorted_order(). I added comments to
explain why.

[1]
https://www.postgresql.org/message-id/CAMbWs49LbQF_Z0iKPRPnTHfsRECT7M-4rF6ft5vpW1ARSpBkPA%40mail.gmail.com

---

From: Tender Wang <[email-masked]>
Date: Fri, 14 Jun 2024 11:02:43 +0800

Hi Robert,

    Since this patch had been reviewed at PgConf.dev Patch Review
Workshop.  And I have updated
the patch according to the review advice. Now there are no others to
comment this patch.
The status of this patch on commitfest have stayed "need review" for a long
time.
I want to know if it is ready to move to the next status "Ready for
commiter".

Thanks.

-- 
Tender Wang

---

From: Richard Guo <[email-masked]>
Date: Tue, 18 Jun 2024 17:24:05 +0800

On Tue, Jun 4, 2024 at 6:51 PM Tender Wang <[email-masked]> wrote:
> We don't consider material inner path if jointype is JOIN_UNIQUE_INNER in match_unsorted_order().
> So here is as same logic as match_unsorted_order(). I added comments to explain why.

I looked through the v4 patch and found an issue.  For the plan diff:

+         ->  Nested Loop
+               ->  Parallel Seq Scan on prt1_p1 t1_1
+               ->  Materialize
+                     ->  Sample Scan on prt1_p1 t2_1
+                           Sampling: system (t1_1.a) REPEATABLE (t1_1.b)
+                           Filter: (t1_1.a = a)

This does not seem correct to me.  The inner path is parameterized by
the outer rel, in which case it does not make sense to add a Materialize
node on top of it.

I updated the patch to include a check in consider_parallel_nestloop
ensuring that inner_cheapest_total is not parameterized by outerrel
before materializing it.  I also tweaked the comments, test cases and
commit message.

Thanks
Richard

---

From: Tender Wang <[email-masked]>
Date: Wed, 19 Jun 2024 10:55:25 +0800

> the outer rel, in which case it does not make sense to add a Materialize

Yeah, you're right.

> before materializing it.  I also tweaked the comments, test cases and

Thanks for the work. Now it looks better.
I have changed the status from "need review" to "ready for commiters"  on
the commitfest.

-- 
Tender Wang

---

From: Richard Guo <[email-masked]>
Date: Sat, 6 Jul 2024 17:32:41 +0800

On Wed, Jun 19, 2024 at 10:55 AM Tender Wang <[email-masked]> wrote:
> I have changed the status from "need review" to "ready for commiters"  on the commitfest.

Here is a new rebase.

I'm planning to push it next week, barring any objections.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Fri, 12 Jul 2024 10:29:48 +0800

> I'm planning to push it next week, barring any objections.

Pushed.

Thanks
Richard

---

From: Tender Wang <[email-masked]>
Date: Fri, 12 Jul 2024 10:43:58 +0800

> > I'm planning to push it next week, barring any objections.

Thanks for pushing.

-- 
Tender Wang

---

From: Alexander Lakhin <[email-masked]>
Date: Thu, 18 Jul 2024 11:00:00 +0300

Hello Richard,

>> I'm planning to push it next week, barring any objections.

Please look at a recent buildfarm failure [1], which shows some
instability of that test addition:
  -- the joinrel is not parallel-safe due to the OFFSET clause in the subquery
  explain (costs off)
      select * from tenk1 t1, (select * from tenk2 t2 offset 0) t2 where t1.two > t2.two;
-                QUERY PLAN
--------------------------------------------
+                   QUERY PLAN
+-------------------------------------------------
   Nested Loop
     Join Filter: (t1.two > t2.two)
-   ->  Gather
-         Workers Planned: 4
-         ->  Parallel Seq Scan on tenk1 t1
+   ->  Seq Scan on tenk2 t2
     ->  Materialize
-         ->  Seq Scan on tenk2 t2
+         ->  Gather
+               Workers Planned: 4
+               ->  Parallel Seq Scan on tenk1 t1
  (7 rows)

I've managed to reproduce this plan change when running
multiple 027_stream_regress.pl instances simultaneously, with
parallel_schedule reduced to:
test: test_setup
test: create_misc
test: create_index
test: sanity_check
test: select_parallel

I've added the following to the test and got two verbose plans for
comparison (see the attachment).
  -- the joinrel is not parallel-safe due to the OFFSET clause in the subquery
  explain (costs off)
      select * from tenk1 t1, (select * from tenk2 t2 offset 0) t2 where t1.two > t2.two;
+\o plan.txt
+explain (verbose)
+    select * from tenk1 t1, (select * from tenk2 t2 offset 0) t2 where t1.two > t2.two;
+\o
  alter table tenk2 reset (parallel_workers);

[1] https://buildfarm.postgresql.org/cgi-bin/show_log.pl?nm=tamandua&dt=2024-07-17%2017%3A12%3A53

Best regards,
Alexander

---

From: Richard Guo <[email-masked]>
Date: Thu, 18 Jul 2024 16:11:50 +0800

>       select * from tenk1 t1, (select * from tenk2 t2 offset 0) t2 where t1.two > t2.two;

Thank you for the report and investigation.  Will have a look.

Thanks
Richard

---

From: Richard Guo <[email-masked]>
Date: Thu, 18 Jul 2024 22:30:22 +0800

> Thank you for the report and investigation.  Will have a look.

The problemed plan is a non-parallel nestloop join.  It's just chance
which join order the planner will pick, and slight variations in
underlying statistics could result in a different displayed plan.
>From the two verbose plans, we can see slight variations in the
statistics for the parallel seqscan of tenk1.

->  Parallel Seq Scan on public.tenk1 t1  (cost=0.00..370.00 rows=2500
width=244)

VS.

->  Parallel Seq Scan on public.tenk1 t1  (cost=0.00..369.99 rows=2499
width=244)

I have no idea why the underlying statistics changed, but it seems
that this slight change is sufficent to result in a different plan.

According to the discussion in [1], I think what we wanted to test
with this query is that parallel nestloop join is not generated if the
inner path is not parallel-safe.  Therefore, I modified this test case
to use a lateral join, rendering the inner path not parallel-safe
while also enforcing the join order.  Please see attached.

[1] https://postgr.es/m/[email-masked]

Thanks
Richard

---

From: Alexander Lakhin <[email-masked]>
Date: Fri, 19 Jul 2024 07:00:01 +0300

Hello Richard,

> that this slight change is sufficent to result in a different plan.

I think it could be caused by the same reason as [1] and I really can
easily (without multiple instances/loops. just with `make check`) reproduce
the failure with cranky-ConditionalLockBufferForCleanup.patch (but
targeted for "VACUUM ANALYZE tenk1;").

> while also enforcing the join order.  Please see attached.

The modified test survives my testing procedure. Thank you for the patch!

[1] https://www.postgresql.org/message-id/flat/66eb9a6e-fc67-a230-c5b1-2a741e8b88c6%40gmail.com

Best regards,
Alexander

---

From: Richard Guo <[email-masked]>
Date: Mon, 22 Jul 2024 10:43:50 +0800

> targeted for "VACUUM ANALYZE tenk1;").

Yeah.  Anyway I think we need to make the test more tolerant of slight
variations in the statistics.

> The modified test survives my testing procedure. Thank you for the patch!

Thanks for testing this patch.  I've pushed it.

Thanks
Richard