Subject: Re: Parallelize correlated subqueries that execute within each worker

From: James Coleman <[email-masked]>
Date: Mon, 23 Jan 2023 09:00:31 -0500

On Sat, Jan 21, 2023 at 10:07 PM James Coleman <[email-masked]> wrote:
> ...
> While working through Tomas's comment about a conditional in the
> max_parallel_hazard_waker being guaranteed true I realized that in the
> current version of the patch the safe_param_ids tracking in
> is_parallel_safe isn't actually needed any longer. That seemed
> suspicious, and so I started digging, and I found out that in the
> current approach all of the tests pass with only the changes in
> clauses.c. I don't believe that the other changes aren't needed;
> rather I believe there isn't yet a test case exercising them, but I
> realize that means I can't prove they're needed. I spent some time
> poking at this, but at least with my current level of imagination I
> haven't stumbled across a query that would exercise these checks.

I played with this a good bit more yesterday, I'm now a good bit more
confident this is correct. I've cleaned up the patch; see attached for
v7.

Here's some of my thought process:
The comments in src/include/nodes/pathnodes.h:2953 tell us that
PARAM_EXEC params are used to pass values around from one plan node to
another in the following ways:
1. Values down into subqueries (for outer references in subqueries)
2. Up out of subqueries (for the results of a subplan)
3. From a NestLoop plan node into its inner relation (when the inner
scan is parameterized with values from the outer relation)

Case (2) is already known to be safe (we currently add these params to
safe_param_ids in max_parallel_hazard_walker when we encounter a
SubPlan node).

I also believe case (3) is already handled. We don't build partial
paths for joins when joinrel->lateral_relids is non-empty, and join
order calculations already require that parameterization here go the
correct way (i.e., inner depends on outer rather than the other way
around).

That leaves us with only case (1) to consider in this patch. Another
way of saying this is that this is really the only thing the
safe_param_ids tracking is guarding against. For params passed down
into subqueries we can further distinguish between init plans and
"regular" subplans. We already know that params from init plans are
safe (at the right level). So we're concerned here with a way to know
if the params passed to subplans are safe. We already track required
rels in ParamPathInfo, so it's fairly simple to do this test.

Which this patch we do in fact now see (as expected) rels with
non-empty lateral_relids showing up in generate_[useful_]gather_paths.
And the partial paths can now have non-empty required outer rels. I'm
not able to come up with a plan that would actually be caught by those
checks; I theorize that because of the few places we actually call
generate_[useful_]gather_paths we are in practice already excluding
those, but for now I've left these as a conditional rather than an
assertion because it seems like the kind of guard we'd want to ensure
those methods are safe.

The other other place that we actually create gather[_merge] paths is
gather_grouping_paths(), and there I've chosen to use assertions,
because the point at which grouping happens in planning suggests to me
that we shouldn't have lateral dependencies at that point. If someone
is concerned about that, I'd be happy to change those to conditionals
also.

James Coleman

---

From: Antonin Houska <[email-masked]>
Date: Mon, 06 Feb 2023 17:40:55 +0100

> assertion because it seems like the kind of guard we'd want to ensure

Maybe we can later (in separate patches) relax the restrictions imposed on
partial path creation a little bit, so that more parameterized partial paths
are created.

One particular case that should be rejected by your checks is a partial index
path, which can be parameterized, but I couldn't construct a query that makes
your checks fire. Maybe the reason is that a parameterized index path is
mostly used on the inner side of a NL join, however no partial path can be
used there. (The problem is that each worker evaluating the NL join would only
see a subset of the inner relation, which whould lead to incorrect results.)

So I'd also choose conditions rather than assert statements.

Following are my (minor) findings:

In generate_gather_paths() you added this test

        /*
         * Delay gather path creation until the level in the join tree where all
         * params used in a worker are generated within that worker.
         */
        if (!bms_is_subset(required_outer, rel->relids))
                return;

but I'm not sure if required_outer can contain anything of rel->relids. How
about using bms_is_empty(required) outer, or even this?

	if (required_outer)
		return;

Similarly,

        /* We can't pass params to workers. */
        if (!bms_is_subset(PATH_REQ_OUTER(cheapest_partial_path), rel->relids))

might look like

        if (!bms_is_empty(PATH_REQ_OUTER(cheapest_partial_path)))

or

        if (PATH_REQ_OUTER(cheapest_partial_path))

In particular, build_index_paths() does the following when setting
outer_relids (which eventually becomes (path->param_info->ppi_req_outer):

        /* Enforce convention that outer_relids is exactly NULL if empty */
        if (bms_is_empty(outer_relids))
                outer_relids = NULL;

Another question is whether in this call

        simple_gather_path = (Path *)
                create_gather_path(root, rel, cheapest_partial_path, rel->reltarget,
                                                   required_outer, rowsp);

required_outer should be passed to create_gather_path(). Shouldn't it rather
be PATH_REQ_OUTER(cheapest_partial_path) that you test just above? Again,
build_index_paths() initializes outer_relids this way

        outer_relids = bms_copy(rel->lateral_relids);

but then it may add some more relations:

        /* OK to include this clause */
        index_clauses = lappend(index_clauses, iclause);
        outer_relids = bms_add_members(outer_relids,
                                                           rinfo->clause_relids);

So I think that PATH_REQ_OUTER(cheapest_partial_path) in
generate_gather_paths() can eventually contain more relations than
required_outer, and therefore it's safer to check the first.

Similar comments might apply to generate_useful_gather_paths(). Here I also
suggest to move this test

        /* We can't pass params to workers. */
        if (!bms_is_subset(PATH_REQ_OUTER(subpath), rel->relids))
                continue;

to the top of the loop because it's relatively cheap.

-- 
Antonin Houska
Web: https://www.cybertec-postgresql.com

---

From: James Coleman <[email-masked]>
Date: Wed, 8 Feb 2023 08:38:27 -0500

> So I'd also choose conditions rather than assert statements.

Thanks for confirming.

>         if (PATH_REQ_OUTER(cheapest_partial_path))

I'm not sure about this change. Deciding is difficult given the fact
that we don't seem to currently generate these paths, but I don't see
a reason why lateral_relids can't be present on the rel, and if so,
then we need to check to see if they're a subset of relids we can
satisfy rather than checking that they don't exist.

> required_outer, and therefore it's safer to check the first.

Yes, this is a good catch. Originally I didn't know about
PATH_REQ_OUTER, and I'd missed using it in these places.

> to the top of the loop because it's relatively cheap.

Moved.

Attached is v9.

James Coleman

---

From: Antonin Houska <[email-masked]>
Date: Wed, 08 Mar 2023 19:07:57 +0100

> Attached is v9.

ok, I've changed the status to RfC

---

From: Richard Guo <[email-masked]>
Date: Tue, 6 Jun 2023 17:35:51 +0800

> assertion because it seems like the kind of guard we'd want to ensure

I'm trying to understand this part.  AFAICS we will not create partial
paths for a rel, base or join, if it has lateral references.  So it
seems to me that in generate_[useful_]gather_paths after we've checked
that there are partial paths, the checks for lateral_relids are not
necessary because lateral_relids should always be empty in this case.
Maybe I'm missing something.

And while trying the v9 patch I came across a crash with the query
below.

set min_parallel_table_scan_size to 0;
set parallel_setup_cost to 0;
set parallel_tuple_cost to 0;

explain (costs off)
select * from pg_description t1 where objoid in
    (select objoid from pg_description t2 where t2.description =
t1.description);
                       QUERY PLAN
--------------------------------------------------------
 Seq Scan on pg_description t1
   Filter: (SubPlan 1)
   SubPlan 1
     ->  Gather
           Workers Planned: 2
           ->  Parallel Seq Scan on pg_description t2
                 Filter: (description = t1.description)
(7 rows)

select * from pg_description t1 where objoid in
    (select objoid from pg_description t2 where t2.description =
t1.description);
WARNING:  terminating connection because of crash of another server process

Seems something is wrong when extracting the argument from the Param in
parallel worker.

BTW another rebase is needed as it no longer applies to HEAD.

Thanks
Richard

---

From: James Coleman <[email-masked]>
Date: Sun, 11 Jun 2023 21:23:45 -0500

> Maybe I'm missing something.

At first I was thinking "isn't the point of the patch to generate
partial paths for rels with lateral references" given what I'd written
back in January, but I added "Assert(bms_is_empty(required_outer));"
to both of those functions and the assertion never fails running the
tests (including my newly parallelizable queries). I'm almost positive
I'd checked this back in January (not only had I'd explicitly written
that I'd confirmed we had non-empty lateral_relids there, but also it
was the entire based of the alternate approach to the patch), but...I
can't go back to 5 months ago and remember what I'd done.

Ah! Your comment about "after we've checked that there are partial
paths" triggered a thought. I think originally I'd had the
"bms_is_subset(required_outer, rel->relids)" check first in these
functions. And indeed if I run the tests with that the assertion moved
to above the partial paths check, I get failures in
generate_useful_gather_paths specifically. Mystery solved!

>     (select objoid from pg_description t2 where t2.description = t1.description);
>                        QUERY PLAN
>     (select objoid from pg_description t2 where t2.description = t1.description);

With what I'm trying to change I don't think this plan should ever be
generated since it means we'd have to pass a param from the outer seq
scan into the parallel subplan, which we can't do (currently).

I've attached the full backtrace to the email, but as you hinted at
the parallel worker is trying to get the param (in this case
detoasting it), but the param doesn't exist on the worker, so it seg
faults. Looking at this further I think there's an existing test case
that exposes the misplanning here (the one right under the comment
"Parallel Append is not to be used when the subpath depends on the
outer param" in select_parallel.sql), but it doesn't seg fault because
the param is an integer, doesn't need to be detoasted, and therefore
(I think) we skate by (but probably with wrong results in depending on
the dataset).

Interestingly this is one of the existing test queries my original
patch approach didn't change, so this gives me something specific to
work with improving the path. Thanks for testing this and bringing
this to my attention!

BTW are you by any chance testing on ARM macOS? I reproduced the issue
there, but for some reason I did not reproduce the error (and the plan
wasn't parallelized) when I tested this on linux. Perhaps I missed
setting something up; it seems odd.

> BTW another rebase is needed as it no longer applies to HEAD.

Apologies; I'd rebased, but hadn't updated the thread. See attached
for an updated series (albeit still broken on your test query).

Thanks,
James

---

From: Richard Guo <[email-masked]>
Date: Mon, 26 Jun 2023 14:47:57 +0800

> setting something up; it seems odd.

Hmm, that's weird.  I was also testing that query on linux.  But please
note that several GUC settings are needed to generate parallel plan for
that query.

Thanks
Richard

---

From: James Coleman <[email-masked]>
Date: Mon, 3 Jul 2023 21:26:44 -0400

> work with improving the path. Thanks for testing this and bringing

Here's what I've found debugging this:

There's only a single gather path ever created when planning this
query, making it easy to know which one is the problem. That gather
path is created with this stacktrace:

    frame #0: 0x0000000105291590
postgres`create_gather_path(root=0x000000013081ae78,
rel=0x000000013080c8e8, subpath=0x000000013081c080,
target=0x000000013081c8c0, required_outer=0x0000000000000000,
rows=0x0000000000000000) at pathnode.c:1971:2
    frame #1: 0x0000000105208e54
postgres`generate_gather_paths(root=0x000000013081ae78,
rel=0x000000013080c8e8, override_rows=false) at allpaths.c:3097:4
    frame #2: 0x00000001052090ec
postgres`generate_useful_gather_paths(root=0x000000013081ae78,
rel=0x000000013080c8e8, override_rows=false) at allpaths.c:3241:2
    frame #3: 0x0000000105258754
postgres`apply_scanjoin_target_to_paths(root=0x000000013081ae78,
rel=0x000000013080c8e8, scanjoin_targets=0x000000013081c978,
scanjoin_targets_contain_srfs=0x0000000000000000,
scanjoin_target_parallel_safe=true, tlist_same_exprs=true) at
planner.c:7696:3
    frame #4: 0x00000001052533cc
postgres`grouping_planner(root=0x000000013081ae78, tuple_fraction=0.5)
at planner.c:1611:3
    frame #5: 0x0000000105251e9c
postgres`subquery_planner(glob=0x00000001308188d8,
parse=0x000000013080caf8, parent_root=0x000000013080cc38,
hasRecursion=false, tuple_fraction=0.5) at planner.c:1062:2
    frame #6: 0x000000010526b134
postgres`make_subplan(root=0x000000013080cc38,
orig_subquery=0x000000013080ff58, subLinkType=ANY_SUBLINK,
subLinkId=0, testexpr=0x000000013080d848, isTopQual=true) at
subselect.c:221:12
    frame #7: 0x0000000105268b8c
postgres`process_sublinks_mutator(node=0x000000013080d6d8,
context=0x000000016b0998f8) at subselect.c:1950:10
    frame #8: 0x0000000105268ad8
postgres`SS_process_sublinks(root=0x000000013080cc38,
expr=0x000000013080d6d8, isQual=true) at subselect.c:1923:9
    frame #9: 0x00000001052527b8
postgres`preprocess_expression(root=0x000000013080cc38,
expr=0x000000013080d6d8, kind=0) at planner.c:1169:10
    frame #10: 0x0000000105252954
postgres`preprocess_qual_conditions(root=0x000000013080cc38,
jtnode=0x000000013080d108) at planner.c:1214:14
    frame #11: 0x0000000105251580
postgres`subquery_planner(glob=0x00000001308188d8,
parse=0x0000000137010d68, parent_root=0x0000000000000000,
hasRecursion=false, tuple_fraction=0) at planner.c:832:2
    frame #12: 0x000000010525042c
postgres`standard_planner(parse=0x0000000137010d68,
query_string="explain (costs off)\nselect * from pg_description t1
where objoid in\n    (select objoid from pg_description t2 where
t2.description = t1.description);", cursorOptions=2048,
boundParams=0x0000000000000000) at planner.c:411:9

There aren't any lateral markings on the rels. Additionally the
partial path has param_info=null (I found out from Tom in a separate
thread [1] that this is only set for outer relations from the same
query level).

The only param that I could easily find at first was a single param of
type PARAM_EXTERN in root->plan_params in make_subplan().

I spent a lot of time trying to figure out where we could find the
PARAM_EXEC param that's being fed into the subplan, but it doesn't
seem like we have access to any of these things at the point in the
path creation process that it's interesting to us when inserting the
gather nodes.

Given all of that I settled on this approach:
1. Modify is_parallel_safe() to by default ignore PARAM_EXEC params.
2. Add is_parallel_safe_with_params() that checks for the existence of
such params.
3. Store the required params in a bitmapset on each base rel.
4. Union the bitmapset on join rels.
5. Only insert a gather node if that bitmapset is empty.

I have an intuition that there's some spot (e.g. joins) that we should
be removing params from this set (e.g., when we've satisfied them),
but I haven't been able to come up with such a scenario as yet.

The attached v11 fixes the issue you reported.

Thanks,
James Coleman

---

From: vignesh C <[email-masked]>
Date: Tue, 9 Jan 2024 12:38:48 +0530

> The attached v11 fixes the issue you reported.

One of the tests has failed in CFBot at [1] with:
+++ /tmp/cirrus-ci-build/build/testrun/pg_upgrade/002_pg_upgrade/data/results/select_parallel.out
2023-12-20 20:08:42.480004000 +0000
@@ -137,23 +137,24 @@
 explain (costs off)
  select (select max((select pa1.b from part_pa_test pa1 where pa1.a = pa2.a)))
  from part_pa_test pa2;
-                          QUERY PLAN
---------------------------------------------------------------
- Aggregate
+                             QUERY PLAN
+--------------------------------------------------------------------
+ Finalize Aggregate
    ->  Gather
          Workers Planned: 3
-         ->  Parallel Append
-               ->  Parallel Seq Scan on part_pa_test_p1 pa2_1
-               ->  Parallel Seq Scan on part_pa_test_p2 pa2_2
+         ->  Partial Aggregate
+               ->  Parallel Append
+                     ->  Parallel Seq Scan on part_pa_test_p1 pa2_1
+                     ->  Parallel Seq Scan on part_pa_test_p2 pa2_2
+               SubPlan 1
+                 ->  Append
+                       ->  Seq Scan on part_pa_test_p1 pa1_1
+                             Filter: (a = pa2.a)
+                       ->  Seq Scan on part_pa_test_p2 pa1_2
+                             Filter: (a = pa2.a)
    SubPlan 2
      ->  Result
-   SubPlan 1
-     ->  Append
-           ->  Seq Scan on part_pa_test_p1 pa1_1
-                 Filter: (a = pa2.a)
-           ->  Seq Scan on part_pa_test_p2 pa1_2
-                 Filter: (a = pa2.a)
-(14 rows)
+(15 rows)

More details of the failure is available at [2].

[1] - https://cirrus-ci.com/task/5685696451575808
[2] - https://api.cirrus-ci.com/v1/artifact/task/5685696451575808/testrun/build/testrun/pg_upgrade/002_pg_upgrade/log/regress_log_002_pg_upgrade

Regards,
Vignesh

---

From: Akshat Jaimini <[email-masked]>
Date: Tue, 23 Jan 2024 14:33:22 +0000

Hello! 
I was going through the previous conversations for this particular patch and it seems that this patch failed some tests previously? 
Imo we should move it to the next CF so that the remaining issues can be resolved accordingly.

---

From: Robert Haas <[email-masked]>
Date: Tue, 23 Jan 2024 15:20:31 -0500

> Imo we should move it to the next CF so that the remaining issues can be resolved accordingly.

So I guess the question here is whether this is thought to be ready
for serious review or whether it is still thought to need work. If the
latter, it should be marked RwF until that happens -- if the former,
then we should try to review it rather than letting it languish
forever.

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

---

From: Akshat Jaimini <[email-masked]>
Date: Tue, 30 Jan 2024 16:16:20 +0000

I think we should move this patch to the next CF as I believe that work is still going on resolving the last reported bug.

---

From: Robert Haas <[email-masked]>
Date: Tue, 30 Jan 2024 11:54:34 -0500

> I think we should move this patch to the next CF as I believe that work is still going on resolving the last reported bug.

We shouldn't just keep pushing this forward to the next CF. It's been
idle since July. If it needs more work, mark it RwF and it can be
reopened when there's something for a reviewer to do.

---

From: James Coleman <[email-masked]>
Date: Tue, 30 Jan 2024 21:51:09 -0500

> +++ /tmp/cirrus-ci-build/build/testrun/pg_upgrade/002_pg_upgrade/data/results/select_parallel.out

Thanks for noting this here.

I've finally had a chance to look at this, and I don't believe there's
any real failure here, merely drift of how the planner works on master
resulting in this query now being eligible for a different plan shape.

I was a bit wary at first because the changing test query is one I'd
previously referenced in [1] as likely exposing the bug I'd fixed
where params where being used across worker boundaries. However
looking at the diff in the patch at that point (v10) that particular
test query formed a different plan shape (there were two gather nodes
being created, and params crossing between them).

But in the current revision of master with the current patch applied
that's no longer true: we have a Gather node, and the Subplan using
the param is properly under that Gather node, and the param should be
being both generated and consumed within the same worker process.

So I've updated the patch to show that plan change as part of the diff.

See attached v12

Regards,
James Coleman

1: https://www.postgresql.org/message-id/CAAaqYe-_TObm5KwmZLYXBJ3BJGh4cUZWM0v1mY1gWTMkRNQXDQ%40mail.gmail.com

---

From: James Coleman <[email-masked]>
Date: Tue, 30 Jan 2024 21:56:20 -0500

> reopened when there's something for a reviewer to do.

I don't follow the "Idle since July" since it just hasn't received
review since then, so there's been nothing to reply to.

That being said, Vignesh's note in January about a now-failing test is
relevant activity, and I've just today responded to that, so I'm
changing the status back from Waiting on Author to Needs Review.

Regards,
James Coleman

---

From: Tom Lane <[email-masked]>
Date: Tue, 30 Jan 2024 22:34:01 -0500

> being both generated and consumed within the same worker process.

Hmm ... so the question this raises for me is: was that test intended
to verify behavior of params being passed across workers?  If so,
haven't you broken the point of the test?  This doesn't mean that
your code change is wrong; but I think maybe you need to find a way
to modify that test case so that it still tests what it's meant to.
This is a common hazard when changing the planner's behavior.

			regards, tom lane

---

From: James Coleman <[email-masked]>
Date: Wed, 31 Jan 2024 08:53:39 -0500

> This is a common hazard when changing the planner's behavior.

I'd been thinking it was covered by another test I'd added in 0001,
but looking at it again that test doesn't exercise parallel append
(though it does exercise a different case of cross-worker param
usage), so I'll add another test for the parallel append behavior.

Regards,
James Coleman

---

From: Robert Haas <[email-masked]>
Date: Wed, 31 Jan 2024 15:18:43 -0500

> review since then, so there's been nothing to reply to.

It wasn't clear to me if you thought that the patch was ready for
review since July, or if it was waiting on you since July. Those are
quite different, IMV.

> changing the status back from Waiting on Author to Needs Review.

Sounds good.