Thread

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

Windows support in pg_import_system_collations
- bf03cfd16217 16.0 cited
Remove pessimistic cost penalization from Incremental Sort
- 4a29eabd1d91 16.0 cited

Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2021-05-07T16:30:02Z

In a bug report back in November [1] a subthread explored why parallel
query is excluded any time we have "Plan nodes which reference a
correlated SubPlan". Amit's understanding was that the reasoning had
to do with inability to easily pass (potentially variable length)
Param values between workers.

However a decent-sized subset of this kind of query doesn't actually
require that we communicate between workers. If the Subplan executes
per-tuple within the worker then there's no reason I can see why it
needs to be marked parallel unsafe. Amit concurred but noted that
identifying that subset of plans is the difficult part (as is usually
the case!)

At the time I'd started work on an approach to handle this case and
hoped to "post about it in a new thread later this week." That didn't
happen, but here we are now, and I finally have this patch cleaned up
enough to share.

The basic idea is that we need to track (both on nodes and relations)
not only whether that node or rel is parallel safe but also whether
it's parallel safe assuming params are rechecked in the using context.
That allows us to delay making a final decision until we have
sufficient context to conclude that a given usage of a Param is
actually parallel safe or unsafe.

The first patch in this series was previously posted in the thread
"Consider parallel for lateral subqueries with limit" [2] and is
required as a precursor for various test cases to work here.

The second patch implements the core of the series. It results in
parallel query being possible for subplans that execute entirely
within the context of a parallel worker for cases where that subplan
is in the target, a LATERAL JOIN, or the WHERE and ORDER BY clauses.

The final patch notes several places where we set e.g.
rel->consider_parallel but setting the corresponding new value
rel->consider_parallel_recheckng_params wasn't yet necessary. It shows
opportunity either for further improvement or concluding certain cases
can't benefit and should be left unchanged.

James

1: https://www.postgresql.org/message-id/CAAaqYe_vihKjc%2B8LuQa49EHW4%2BKfefb3wHqPYFnCuUqozo%2BLFg%40mail.gmail.com
2: https://www.postgresql.org/message-id/flat/CAAaqYe_HEkmLwf_1iEHxXwQOWiRyiFd%3DuOu6kwj3sWYdVd1-zA%40mail.gmail.com

Re: Parallelize correlated subqueries that execute within each worker

Daniel Gustafsson <daniel@yesql.se> — 2021-09-01T11:06:04Z

> On 7 May 2021, at 18:30, James Coleman <jtc331@gmail.com> wrote:

> ..here we are now, and I finally have this patch cleaned up
> enough to share.

This patch no longer applies to HEAD, can you please submit a rebased version?

--
Daniel Gustafsson		https://vmware.com/

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2021-09-07T13:16:49Z

On Wed, Sep 1, 2021 at 7:06 AM Daniel Gustafsson <daniel@yesql.se> wrote:
>
> > On 7 May 2021, at 18:30, James Coleman <jtc331@gmail.com> wrote:
>
> > ..here we are now, and I finally have this patch cleaned up
> > enough to share.
>
> This patch no longer applies to HEAD, can you please submit a rebased version?

See attached.

Thanks,
James

Re: Parallelize correlated subqueries that execute within each worker

Zhihong Yu <zyu@yugabyte.com> — 2021-09-07T15:06:00Z

On Tue, Sep 7, 2021 at 6:17 AM James Coleman <jtc331@gmail.com> wrote:

> On Wed, Sep 1, 2021 at 7:06 AM Daniel Gustafsson <daniel@yesql.se> wrote:
> >
> > > On 7 May 2021, at 18:30, James Coleman <jtc331@gmail.com> wrote:
> >
> > > ..here we are now, and I finally have this patch cleaned up
> > > enough to share.
> >
> > This patch no longer applies to HEAD, can you please submit a rebased
> version?
>
> See attached.
>
> Thanks,
> James
>
Hi,
For v2-0002-Parallel-query-support-for-basic-correlated-subqu.patch :

+    * is when we're going to execute multiple partial parths in parallel

parths -> paths

        if (index->amcanparallel &&
-           rel->consider_parallel && outer_relids == NULL &&
-           scantype != ST_BITMAPSCAN)
+               rel->consider_parallel && outer_relids == NULL &&
+               scantype != ST_BITMAPSCAN)

the change above seems unnecessary since the first line of if condition
doesn't change.
Similar comment for the next hunk.

+            * It's not a partial path; it'a a full path that is executed
as a subquery.

it'a a -> it's a

+           /* rel->consider_parallel_rechecking_params = false; */
+           /* rel->partial_pathlist = NIL; */

The commented code can be taken out.

Cheers

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2021-09-08T12:47:35Z

On Tue, Sep 7, 2021 at 11:06 AM Zhihong Yu <zyu@yugabyte.com> wrote:
>
>
>
> On Tue, Sep 7, 2021 at 6:17 AM James Coleman <jtc331@gmail.com> wrote:
>>
>> On Wed, Sep 1, 2021 at 7:06 AM Daniel Gustafsson <daniel@yesql.se> wrote:
>> >
>> > > On 7 May 2021, at 18:30, James Coleman <jtc331@gmail.com> wrote:
>> >
>> > > ..here we are now, and I finally have this patch cleaned up
>> > > enough to share.
>> >
>> > This patch no longer applies to HEAD, can you please submit a rebased version?
>>
>> See attached.
>>
>> Thanks,
>> James
>
> Hi,
> For v2-0002-Parallel-query-support-for-basic-correlated-subqu.patch :
>
> +    * is when we're going to execute multiple partial parths in parallel
>
> parths -> paths
>
>         if (index->amcanparallel &&
> -           rel->consider_parallel && outer_relids == NULL &&
> -           scantype != ST_BITMAPSCAN)
> +               rel->consider_parallel && outer_relids == NULL &&
> +               scantype != ST_BITMAPSCAN)
>
> the change above seems unnecessary since the first line of if condition doesn't change.
> Similar comment for the next hunk.
>
> +            * It's not a partial path; it'a a full path that is executed as a subquery.
>
> it'a a -> it's a
>
> +           /* rel->consider_parallel_rechecking_params = false; */
> +           /* rel->partial_pathlist = NIL; */
>
> The commented code can be taken out.

Thanks for taking a look at this.

See updated patch series attached.

James Coleman

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2021-11-03T13:46:33Z

On Wed, Sep 8, 2021 at 8:47 AM James Coleman <jtc331@gmail.com> wrote:

> See updated patch series attached.

Jaime,

I noticed on 3-October you moved this into "waiting on author"; I
don't see anything waiting in this thread, however. Am I missing
something?

I'm planning to change it back to "needs review".

Thanks,
James

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2021-11-03T14:48:48Z

As a preliminary comment, it would be quite useful to get Tom Lane's
opinion on this, since it's not an area I understand especially well,
and I think he understands it better than anyone.

On Fri, May 7, 2021 at 12:30 PM James Coleman <jtc331@gmail.com> wrote:
> The basic idea is that we need to track (both on nodes and relations)
> not only whether that node or rel is parallel safe but also whether
> it's parallel safe assuming params are rechecked in the using context.
> That allows us to delay making a final decision until we have
> sufficient context to conclude that a given usage of a Param is
> actually parallel safe or unsafe.

I don't really understand what you mean by "assuming params are
rechecked in the using context." However, I think that a possibly
better approach to this whole area would be to try to solve the
problem by putting limits on where you can insert a Gather node.
Consider:

Nested Loop
-> Seq Scan on x
-> Index Scan on y
   Index Cond: y.q = x.q

If you insert a Gather node atop the Index Scan, necessarily changing
it to a Parallel Index Scan, then you need to pass values around. For
every value we get for x.q, we would need to start workers, sending
them the value of x.q, and they do a parallel index scan working
together to find all rows where y.q = x.q, and then exit. We repeat
this for every tuple from x.q. In the absence of infrastructure to
pass those parameters, we can't put the Gather there. We also don't
want to, because it would be really slow.

If you insert the Gather node atop the Seq Scan or the Nested Loop, in
either case necessarily changing the Seq Scan to a Parallel Seq Scan,
you have no problem. If you put it on top of the Nested Loop, the
parameter will be set in the workers and used in the workers and
everything is fine. If you put it on top of the Seq Scan, the
parameter will be set in the leader -- by the Nested Loop -- and used
in the leader, and again you have no problem.

So in my view of the world, the parameter just acts as an additional
constraint on where Gather nodes can be placed. I don't see that there
are any parameters that are unsafe categorically -- they're just
unsafe if the place where they are set is on a different side of the
Gather from the place where they are used. So I don't understand --
possibly just because I'm dumb -- the idea behind
consider_parallel_rechecking_params, because that seems to be making a
sort of overall judgement about the safety or unsafety of the
parameter on its own merits, rather than thinking about the Gather
placement.

When I last worked on this, I had hoped that extParam or allParam
would be the thing that would answer the question: are there any
parameters used under this node that are not also set under this node?
But I seem to recall that neither seemed to be answering precisely
that question, and the lousy naming of those fields and limited
documentation of their intended purpose did not help.

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

Re: Parallelize correlated subqueries that execute within each worker

Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-03T15:14:35Z

Robert Haas <robertmhaas@gmail.com> writes:
> When I last worked on this, I had hoped that extParam or allParam
> would be the thing that would answer the question: are there any
> parameters used under this node that are not also set under this node?
> But I seem to recall that neither seemed to be answering precisely
> that question, and the lousy naming of those fields and limited
> documentation of their intended purpose did not help.

FWIW, I've never been very happy with those fields either.  IIRC the
design in that area was all Vadim's, but to the extent that there's
any usable documentation of extParam/allParam, it was filled in by me
while trying to understand what Vadim did.  If somebody wants to step
up and do a rewrite to make the planner's Param management more useful
or at least easier to understand, I think that'd be great.

But anyway: yeah, those fields as currently constituted don't help
much.  They tell you which Params are consumed by this node or its
subnodes, but not where those Params came from.  The planner's
plan_params and outer_params fields might be more nearly the right
thing, but I'm not sure they're spot-on either, nor that they're
up-to-date at the point where you'd want to make decisions about
Gather safety.

			regards, tom lane

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2021-11-03T16:27:42Z

On Wed, Nov 3, 2021 at 11:14 AM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> FWIW, I've never been very happy with those fields either.  IIRC the
> design in that area was all Vadim's, but to the extent that there's
> any usable documentation of extParam/allParam, it was filled in by me
> while trying to understand what Vadim did.  If somebody wants to step
> up and do a rewrite to make the planner's Param management more useful
> or at least easier to understand, I think that'd be great.

Good to know, thanks.

> But anyway: yeah, those fields as currently constituted don't help
> much.  They tell you which Params are consumed by this node or its
> subnodes, but not where those Params came from.  The planner's
> plan_params and outer_params fields might be more nearly the right
> thing, but I'm not sure they're spot-on either, nor that they're
> up-to-date at the point where you'd want to make decisions about
> Gather safety.

One thing I discovered when I was looking at this a few years ago is
that there was only one query in the regression tests where extParam
and allParam were not the same. The offending query was select 1 =
all(select (select 1)), and the resulting plan has a Materialize node
with an attached InitPlan. For that Materialize node, extParam = {}
and allParam = {$0}, with $0 also being the output parameter of the
InitPlan attached that that Materialize node. In every other node in
that plan and in every node of every other plan generated by the
regression tests, the values were identical. So it's extremely niche
that these fields are even different from each other, and it's unclear
to me that we really need both of them.

What's also interesting is that extParam is computed (by
finalize_plan) as plan->extParam = bms_del_members(plan->extParam,
initSetParam). So I think it mostly ends up that extParam for a node
is not exactly all the parameters that anything under that node cares
about, but rather - approximately - all the things that anything under
that node cares about that aren't also set someplace under that node.
If it were exactly that, I think it would be perfect for our needs
here: if the set of things used but not set below the current level is
empty, it's OK to insert a Gather node; otherwise, it's not, at least,
not unless we find a way to pipe parameters from the leader into the
workers. But I think there's some reason that I no longer remember why
it's not exactly that, and therefore the idea doesn't work.

One problem I do remember is that attaching initplans at the top of
each subquery level as we presently do is really not good for this
kind of thing. Suppose you have several levels of Nested Loop and
someplace down in the plan you reference an InitPlan. The planner sees
no harm in attaching the InitPlan at the top level, which makes it
unsafe to put the Gather any place but at the top level. If you
attached the InitPlan to the lowest node in the plan tree that is high
enough to be above all the places that use the value from that
parameter, you could potentially shift the Gather down the plan tree,
which would be great if, for example, there's exactly one
parallel-restricted join and the rest are parallel-safe. The best plan
might be to do all the other joins under a Gather and then perform the
parallel-restricted join above it.

But I found it very hard to figure out how to rejigger the logic that
places InitPlans to be more intelligent, and eventually gave up.

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

Re: Parallelize correlated subqueries that execute within each worker

Tom Lane <tgl@sss.pgh.pa.us> — 2021-11-03T16:52:16Z

Robert Haas <robertmhaas@gmail.com> writes:
> One thing I discovered when I was looking at this a few years ago is
> that there was only one query in the regression tests where extParam
> and allParam were not the same. The offending query was select 1 =
> all(select (select 1)), and the resulting plan has a Materialize node
> with an attached InitPlan. For that Materialize node, extParam = {}
> and allParam = {$0}, with $0 also being the output parameter of the
> InitPlan attached that that Materialize node. In every other node in
> that plan and in every node of every other plan generated by the
> regression tests, the values were identical. So it's extremely niche
> that these fields are even different from each other, and it's unclear
> to me that we really need both of them.

Yeah, I've had that nagging feeling about them too.  But ISTR trying to
reduce them to one value years ago, and finding that it didn't quite work,
or at least would result in more subquery-re-evaluation than we do today.
You have to dig into what the executor uses these values for to really
grok them.  I'm afraid that that detail is all swapped out right now, so
I can't say much more.

			regards, tom lane

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2021-11-03T17:34:39Z

Hi Robert, thanks for the detailed reply.

On Wed, Nov 3, 2021 at 10:48 AM Robert Haas <robertmhaas@gmail.com> wrote:
>
> As a preliminary comment, it would be quite useful to get Tom Lane's
> opinion on this, since it's not an area I understand especially well,
> and I think he understands it better than anyone.
>
> On Fri, May 7, 2021 at 12:30 PM James Coleman <jtc331@gmail.com> wrote:
> > The basic idea is that we need to track (both on nodes and relations)
> > not only whether that node or rel is parallel safe but also whether
> > it's parallel safe assuming params are rechecked in the using context.
> > That allows us to delay making a final decision until we have
> > sufficient context to conclude that a given usage of a Param is
> > actually parallel safe or unsafe.
>
> I don't really understand what you mean by "assuming params are
> rechecked in the using context." However, I think that a possibly
> better approach to this whole area would be to try to solve the
> problem by putting limits on where you can insert a Gather node.
> Consider:
>
> Nested Loop
> -> Seq Scan on x
> -> Index Scan on y
>    Index Cond: y.q = x.q
>
> If you insert a Gather node atop the Index Scan, necessarily changing
> it to a Parallel Index Scan, then you need to pass values around. For
> every value we get for x.q, we would need to start workers, sending
> them the value of x.q, and they do a parallel index scan working
> together to find all rows where y.q = x.q, and then exit. We repeat
> this for every tuple from x.q. In the absence of infrastructure to
> pass those parameters, we can't put the Gather there. We also don't
> want to, because it would be really slow.
>
> If you insert the Gather node atop the Seq Scan or the Nested Loop, in
> either case necessarily changing the Seq Scan to a Parallel Seq Scan,
> you have no problem. If you put it on top of the Nested Loop, the
> parameter will be set in the workers and used in the workers and
> everything is fine. If you put it on top of the Seq Scan, the
> parameter will be set in the leader -- by the Nested Loop -- and used
> in the leader, and again you have no problem.
>
> So in my view of the world, the parameter just acts as an additional
> constraint on where Gather nodes can be placed. I don't see that there
> are any parameters that are unsafe categorically -- they're just
> unsafe if the place where they are set is on a different side of the
> Gather from the place where they are used. So I don't understand --
> possibly just because I'm dumb -- the idea behind
> consider_parallel_rechecking_params, because that seems to be making a
> sort of overall judgement about the safety or unsafety of the
> parameter on its own merits, rather than thinking about the Gather
> placement.

I had to read through this several times before I understood the point
(not your fault, this is, as you note, a complicated area). I *think*
if I grok it properly you're effectively describing what this patch
results in conceptually (but possibly solving it from a different
direction).

As I understand the current code, parallel plans are largely chosen
based not on where it's safe to insert a Gather node but rather by
determining if a given path is parallel safe. Through that lens params
are a bit of an odd man out -- they aren't inherently unsafe in the
way a parallel-unsafe function is, but they can only be used in
parallel plans under certain conditions (whether because of project
policy, performance, or missing infrastructure).

Under that paradigm the existing consider_parallel and parallel_safe
boolean values imply everything is about whether a plan is inherently
parallel safe. Thus the current doesn't have the context to handle the
nuance of params (as they are not inherently parallel-safe or unsafe).

Introducing consider_parallel_rechecking_params and
parallel_safe_ignoring_params allows us to keep more context on params
and make a more nuanced decision at the proper level of the plan. This
is what I mean by "rechecked in the using context", though I realize
now that both "recheck" and "context" are overloaded terms in the
project, so don't describe the concept particularly clearly. When a
path relies on params we can only make a final determination about its
parallel safety if we know whether or not the current parallel node
can provide the param's value. We don't necessarily know that
information until we attempt to generate a full parallel node in the
plan (I think what you're describing as "inserting a Gather node")
since the param may come from another node in the plan. These new
values allow us to do that by tracking tentatively parallel-safe
subplans (given proper Gather node placement) and delaying the
parallel-safety determination until the point at which a param is
available (or not).

Is that a more helpful framing of what my goal is here?

> When I last worked on this, I had hoped that extParam or allParam
> would be the thing that would answer the question: are there any
> parameters used under this node that are not also set under this node?
> But I seem to recall that neither seemed to be answering precisely
> that question, and the lousy naming of those fields and limited
> documentation of their intended purpose did not help.

I don't really know anything about extParam or allParam, so I can't
offer any insight here.

Thanks,
James Coleman

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2021-11-15T15:01:37Z

On Wed, Nov 3, 2021 at 1:34 PM James Coleman <jtc331@gmail.com> wrote:
> As I understand the current code, parallel plans are largely chosen
> based not on where it's safe to insert a Gather node but rather by
> determining if a given path is parallel safe. Through that lens params
> are a bit of an odd man out -- they aren't inherently unsafe in the
> way a parallel-unsafe function is, but they can only be used in
> parallel plans under certain conditions (whether because of project
> policy, performance, or missing infrastructure).

Right.

> Introducing consider_parallel_rechecking_params and
> parallel_safe_ignoring_params allows us to keep more context on params
> and make a more nuanced decision at the proper level of the plan. This
> is what I mean by "rechecked in the using context", though I realize
> now that both "recheck" and "context" are overloaded terms in the
> project, so don't describe the concept particularly clearly. When a
> path relies on params we can only make a final determination about its
> parallel safety if we know whether or not the current parallel node
> can provide the param's value. We don't necessarily know that
> information until we attempt to generate a full parallel node in the
> plan (I think what you're describing as "inserting a Gather node")
> since the param may come from another node in the plan. These new
> values allow us to do that by tracking tentatively parallel-safe
> subplans (given proper Gather node placement) and delaying the
> parallel-safety determination until the point at which a param is
> available (or not).

So I think I agree with you here. But I don't like all of this
"ignoring_params" stuff and I don't see why it's necessary. Say we
don't have both parallel_safe and parallel_safe_ignoring_params. Say
we just have parallel_safe. If the plan will be parallel safe if the
params are available, we label it parallel safe. If the plan will not
be parallel safe even if the params are available, we say it's not
parallel safe. Then, when we get to generate_gather_paths(), we don't
generate any paths if there are required parameters that are not
available. What's wrong with that approach?

Maybe it's clearer to say this: I feel like one extra Boolean is
either too much or too little. I think maybe it's not even needed. But
if it is needed, then why just a bool instead of, say, a Bitmapset of
params that are needed, or something?

I'm sort of speaking from intuition here rather than sure knowledge. I
might be totally wrong.

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

Re: Parallelize correlated subqueries that execute within each worker

Michael Paquier <michael@paquier.xyz> — 2021-12-03T07:35:08Z

On Mon, Nov 15, 2021 at 10:01:37AM -0500, Robert Haas wrote:
> On Wed, Nov 3, 2021 at 1:34 PM James Coleman <jtc331@gmail.com> wrote:
>> As I understand the current code, parallel plans are largely chosen
>> based not on where it's safe to insert a Gather node but rather by
>> determining if a given path is parallel safe. Through that lens params
>> are a bit of an odd man out -- they aren't inherently unsafe in the
>> way a parallel-unsafe function is, but they can only be used in
>> parallel plans under certain conditions (whether because of project
>> policy, performance, or missing infrastructure).
> 
> Right.

Please note that the CF bot is complaining here, so I have moved this
patch to the next CF, but changed the status as waiting on author.
--
Michael

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2022-01-14T19:15:40Z

On Fri, Dec 3, 2021 at 2:35 AM Michael Paquier <michael@paquier.xyz> wrote:
>
> On Mon, Nov 15, 2021 at 10:01:37AM -0500, Robert Haas wrote:
> > On Wed, Nov 3, 2021 at 1:34 PM James Coleman <jtc331@gmail.com> wrote:
> >> As I understand the current code, parallel plans are largely chosen
> >> based not on where it's safe to insert a Gather node but rather by
> >> determining if a given path is parallel safe. Through that lens params
> >> are a bit of an odd man out -- they aren't inherently unsafe in the
> >> way a parallel-unsafe function is, but they can only be used in
> >> parallel plans under certain conditions (whether because of project
> >> policy, performance, or missing infrastructure).
> >
> > Right.
>
> Please note that the CF bot is complaining here, so I have moved this
> patch to the next CF, but changed the status as waiting on author.

I rebased this back in December, but somehow forgot to reply with the
updated patch, so, here it is finally.

Thanks,
James Coleman

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2022-01-14T19:24:50Z

On Mon, Nov 15, 2021 at 10:01 AM Robert Haas <robertmhaas@gmail.com> wrote:
>
> On Wed, Nov 3, 2021 at 1:34 PM James Coleman <jtc331@gmail.com> wrote:
> > As I understand the current code, parallel plans are largely chosen
> > based not on where it's safe to insert a Gather node but rather by
> > determining if a given path is parallel safe. Through that lens params
> > are a bit of an odd man out -- they aren't inherently unsafe in the
> > way a parallel-unsafe function is, but they can only be used in
> > parallel plans under certain conditions (whether because of project
> > policy, performance, or missing infrastructure).
>
> Right.
>
> > Introducing consider_parallel_rechecking_params and
> > parallel_safe_ignoring_params allows us to keep more context on params
> > and make a more nuanced decision at the proper level of the plan. This
> > is what I mean by "rechecked in the using context", though I realize
> > now that both "recheck" and "context" are overloaded terms in the
> > project, so don't describe the concept particularly clearly. When a
> > path relies on params we can only make a final determination about its
> > parallel safety if we know whether or not the current parallel node
> > can provide the param's value. We don't necessarily know that
> > information until we attempt to generate a full parallel node in the
> > plan (I think what you're describing as "inserting a Gather node")
> > since the param may come from another node in the plan. These new
> > values allow us to do that by tracking tentatively parallel-safe
> > subplans (given proper Gather node placement) and delaying the
> > parallel-safety determination until the point at which a param is
> > available (or not).
>
> So I think I agree with you here. But I don't like all of this
> "ignoring_params" stuff and I don't see why it's necessary. Say we
> don't have both parallel_safe and parallel_safe_ignoring_params. Say
> we just have parallel_safe. If the plan will be parallel safe if the
> params are available, we label it parallel safe. If the plan will not
> be parallel safe even if the params are available, we say it's not
> parallel safe. Then, when we get to generate_gather_paths(), we don't
> generate any paths if there are required parameters that are not
> available. What's wrong with that approach?
>
> Maybe it's clearer to say this: I feel like one extra Boolean is
> either too much or too little. I think maybe it's not even needed. But
> if it is needed, then why just a bool instead of, say, a Bitmapset of
> params that are needed, or something?
>
> I'm sort of speaking from intuition here rather than sure knowledge. I
> might be totally wrong.

Apologies for quite the delay responding to this.

I've been chewing on this a bit, and I was about to go re-read the
code and see how easy it'd be to do exactly what you're suggesting in
generate_gather_paths() (and verifying it doesn't need to happen in
other places). However there's one (I think large) gotcha with that
approach (assuming it otherwise makes sense): it means we do
unnecessary work. In the current patch series we only need to recheck
parallel safety if we're in a situation where we might actually
benefit from doing that work (namely when we have a correlated
subquery we might otherwise be able to execute in a parallel plan). If
we don't track that status we'd have to recheck the full parallel
safety of the path for all paths -- even without correlated
subqueries.

Alternatively we could merge these fields into a single enum field
that tracked these states. Even better, we could use a bitmap to
signify what items are/aren't parallel safe. I'm not sure if that'd
create even larger churn in the patch, but maybe it's worth it either
way. In theory it'd open up further expansions to this concept later
(though I'm not aware of any such ideas).

If you think such an approach would be an improvement I'd be happy to
take a pass at a revised patch.

Thoughts?

Thanks,
James Coleman

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2022-01-21T20:20:44Z

On Fri, Jan 14, 2022 at 2:25 PM James Coleman <jtc331@gmail.com> wrote:
> I've been chewing on this a bit, and I was about to go re-read the
> code and see how easy it'd be to do exactly what you're suggesting in
> generate_gather_paths() (and verifying it doesn't need to happen in
> other places). However there's one (I think large) gotcha with that
> approach (assuming it otherwise makes sense): it means we do
> unnecessary work. In the current patch series we only need to recheck
> parallel safety if we're in a situation where we might actually
> benefit from doing that work (namely when we have a correlated
> subquery we might otherwise be able to execute in a parallel plan). If
> we don't track that status we'd have to recheck the full parallel
> safety of the path for all paths -- even without correlated
> subqueries.

I don't think there's an intrinsic problem with the idea of making a
tentative determination about parallel safety and then refining it
later, but I'm not sure why you think it would be a lot of work to
figure this out at the point where we generate gather paths. I think
it's just a matter of testing whether the set of parameters that the
path needs as input is the empty set. It may be that neither extParam
nor allParam are precisely that thing, but I think both are very
close, and it seems to me that there's no theoretical reason why we
can't know for every path the set of inputs that it requires "from the
outside."

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

Re: Parallelize correlated subqueries that execute within each worker

Tom Lane <tgl@sss.pgh.pa.us> — 2022-01-21T20:54:03Z

Robert Haas <robertmhaas@gmail.com> writes:
> I don't think there's an intrinsic problem with the idea of making a
> tentative determination about parallel safety and then refining it
> later, but I'm not sure why you think it would be a lot of work to
> figure this out at the point where we generate gather paths. I think
> it's just a matter of testing whether the set of parameters that the
> path needs as input is the empty set. It may be that neither extParam
> nor allParam are precisely that thing, but I think both are very
> close, and it seems to me that there's no theoretical reason why we
> can't know for every path the set of inputs that it requires "from the
> outside."

I'd be very happy if someone redesigned the extParam/allParam mechanism,
or at least documented it better.  It's confusing and I've never been
able to escape the feeling that it's somewhat redundant.

The real problem with it though is that we don't compute those values
until much too late to be useful in path construction; see comments
for SS_identify_outer_params.  To be helpful to the planner, we'd have
to rejigger things at least enough to calculate them earlier -- or
maybe better, calculate what the planner wants earlier, and then transform
to what the executor wants later.

			regards, tom lane

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2022-01-23T01:25:19Z

On Fri, Jan 21, 2022 at 3:20 PM Robert Haas <robertmhaas@gmail.com> wrote:
>
> On Fri, Jan 14, 2022 at 2:25 PM James Coleman <jtc331@gmail.com> wrote:
> > I've been chewing on this a bit, and I was about to go re-read the
> > code and see how easy it'd be to do exactly what you're suggesting in
> > generate_gather_paths() (and verifying it doesn't need to happen in
> > other places). However there's one (I think large) gotcha with that
> > approach (assuming it otherwise makes sense): it means we do
> > unnecessary work. In the current patch series we only need to recheck
> > parallel safety if we're in a situation where we might actually
> > benefit from doing that work (namely when we have a correlated
> > subquery we might otherwise be able to execute in a parallel plan). If
> > we don't track that status we'd have to recheck the full parallel
> > safety of the path for all paths -- even without correlated
> > subqueries.
>
> I don't think there's an intrinsic problem with the idea of making a
> tentative determination about parallel safety and then refining it
> later, but I'm not sure why you think it would be a lot of work to
> figure this out at the point where we generate gather paths. I think
> it's just a matter of testing whether the set of parameters that the
> path needs as input is the empty set. It may be that neither extParam
> nor allParam are precisely that thing, but I think both are very
> close, and it seems to me that there's no theoretical reason why we
> can't know for every path the set of inputs that it requires "from the
> outside."

As I understand it now (not sure I realized this before) you're
suggesting that *even when there are required params* marking it as
parallel safe, and then checking the params for parallel safety later.
>From a purely theoretical perspective that seemed reasonable, so I
took a pass at that approach.

The first, and likely most interesting, thing I discovered was that
the vast majority of what the patch accomplishes it does so not via
the delayed params safety checking but rather via the required outer
relids checks I'd added to generate_useful_gather_paths.

For that to happen I did have to mark PARAM_EXEC params as presumed
parallel safe. That means that parallel_safe now doesn't strictly mean
"parallel safe in the current context" but "parallel safe as long as
any params are provided". That's a real change, but probably
acceptable as long as a project policy decision is made in that
direction.

There are a few concerns I have (and I'm not sure what level they rise to):

1. From what I can tell we don't have access on a path to the set of
params required by that path (I believe this is what Tom was
referencing in his sister reply at this point in the thread). That
means we have to rely on checking that the required outer relids are
provided by the current query level. I'm not quite sure yet whether or
not that guarantees (or if the rest of the path construction logic
guarantees for us) that the params provided by the outer rel are used
in a correlated way that isn't shared across workers. And because we
don't have the param information available we can't add additional
checks (that I can tell) to verify that.
2. Are we excluding any paths (by having one that will always be
invalid win the cost comparisons in add_partial_path)? I suppose this
danger actually exists in the previous version of the patch as well,
and I don't actually have any examples of this being a problem. Also
maybe this can only be a problem if (1) reveals a bug.
3. The new patch series actually ends up allowing parallelization of
correlated params in a few more places than the original patch series.
>From what I can tell all of the cases are in fact safe to execute in
parallel, which, if true, means this is a feature not a concern. The
changed query plans fall into two categories: a.) putting a gather
inside a subplan and b.) correlated param usages in a subquery scan
path on the inner side of a join. I've separated out those specific
changes in a separate patch to make it easier to tell which ones I'm
referencing.

On the other hand this is a dramatically simpler patch series.
Assuming the approach is sound, it should much easier to maintain than
the previous version.

The final patch in the series is a set of additional checks I could
imagine to try to be more explicit, but at least in the current test
suite there isn't anything at all they affect.

Does this look at least somewhat more like what you'd envisionsed
(granting the need to squint hard given the relids checks instead of
directly checking params)?

Thanks,
James Coleman

Re: Parallelize correlated subqueries that execute within each worker

Andres Freund <andres@anarazel.de> — 2022-03-22T00:48:05Z

Hi,

On 2022-01-22 20:25:19 -0500, James Coleman wrote:
> On the other hand this is a dramatically simpler patch series.
> Assuming the approach is sound, it should much easier to maintain than
> the previous version.
> 
> The final patch in the series is a set of additional checks I could
> imagine to try to be more explicit, but at least in the current test
> suite there isn't anything at all they affect.
> 
> Does this look at least somewhat more like what you'd envisionsed
> (granting the need to squint hard given the relids checks instead of
> directly checking params)?

This fails on freebsd (so likely a timing issue): https://cirrus-ci.com/task/4758411492458496?logs=test_world#L2225

Marked as waiting on author.

Greetings,

Andres Freund

Re: Parallelize correlated subqueries that execute within each worker

Jacob Champion <jchampion@timescale.com> — 2022-08-02T20:57:42Z

This entry has been waiting on author input for a while (our current
threshold is roughly two weeks), so I've marked it Returned with
Feedback.

Once you think the patchset is ready for review again, you (or any
interested party) can resurrect the patch entry by visiting

    https://commitfest.postgresql.org/38/3246/

and changing the status to "Needs Review", and then changing the
status again to "Move to next CF". (Don't forget the second step;
hopefully we will have streamlined this in the near future!)

Thanks,
--Jacob

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2022-09-27T02:56:11Z

On Mon, Mar 21, 2022 at 8:48 PM Andres Freund <andres@anarazel.de> wrote:
>
> Hi,
>
> On 2022-01-22 20:25:19 -0500, James Coleman wrote:
> > On the other hand this is a dramatically simpler patch series.
> > Assuming the approach is sound, it should much easier to maintain than
> > the previous version.
> >
> > The final patch in the series is a set of additional checks I could
> > imagine to try to be more explicit, but at least in the current test
> > suite there isn't anything at all they affect.
> >
> > Does this look at least somewhat more like what you'd envisionsed
> > (granting the need to squint hard given the relids checks instead of
> > directly checking params)?
>
> This fails on freebsd (so likely a timing issue): https://cirrus-ci.com/task/4758411492458496?logs=test_world#L2225
>
> Marked as waiting on author.

I've finally gotten around to checking this out, and the issue was an
"explain analyze" test that had actual loops different on FreeBSD.
There doesn't seem to be a way to disable loop output, but instead of
processing the explain output with e.g. a function (as we do some
other places) to remove the offending and unnecessary output I've just
removed the "analyze" (as I don't believe it was actually necessary).

Attached is an updated patch series. In this version I've removed the
"parallelize some subqueries with limit" patch since discussion is
proceeding in the spun off thread. The first patch adds additional
tests so that you can see how those new tests change with the code
changes in the 2nd patch in the series. As before the final patch in
the series includes changes where we may also want to verify
correctness but don't have a test demonstrating the need.

Thanks,
James Coleman

Re: Parallelize correlated subqueries that execute within each worker

vignesh C <vignesh21@gmail.com> — 2023-01-04T09:49:24Z

On Tue, 27 Sept 2022 at 08:26, James Coleman <jtc331@gmail.com> wrote:
>
> On Mon, Mar 21, 2022 at 8:48 PM Andres Freund <andres@anarazel.de> wrote:
> >
> > Hi,
> >
> > On 2022-01-22 20:25:19 -0500, James Coleman wrote:
> > > On the other hand this is a dramatically simpler patch series.
> > > Assuming the approach is sound, it should much easier to maintain than
> > > the previous version.
> > >
> > > The final patch in the series is a set of additional checks I could
> > > imagine to try to be more explicit, but at least in the current test
> > > suite there isn't anything at all they affect.
> > >
> > > Does this look at least somewhat more like what you'd envisionsed
> > > (granting the need to squint hard given the relids checks instead of
> > > directly checking params)?
> >
> > This fails on freebsd (so likely a timing issue): https://cirrus-ci.com/task/4758411492458496?logs=test_world#L2225
> >
> > Marked as waiting on author.
>
> I've finally gotten around to checking this out, and the issue was an
> "explain analyze" test that had actual loops different on FreeBSD.
> There doesn't seem to be a way to disable loop output, but instead of
> processing the explain output with e.g. a function (as we do some
> other places) to remove the offending and unnecessary output I've just
> removed the "analyze" (as I don't believe it was actually necessary).
>
> Attached is an updated patch series. In this version I've removed the
> "parallelize some subqueries with limit" patch since discussion is
> proceeding in the spun off thread. The first patch adds additional
> tests so that you can see how those new tests change with the code
> changes in the 2nd patch in the series. As before the final patch in
> the series includes changes where we may also want to verify
> correctness but don't have a test demonstrating the need.

The patch does not apply on top of HEAD as in [1], please post a rebased patch:

=== Applying patches on top of PostgreSQL commit ID
bf03cfd162176d543da79f9398131abc251ddbb9 ===
=== applying patch ./v5-0002-Parallelize-correlated-subqueries.patch
patching file src/backend/optimizer/path/allpaths.c
...
Hunk #5 FAILED at 3225.
Hunk #6 FAILED at 3259.
Hunk #7 succeeded at 3432 (offset -6 lines).
2 out of 7 hunks FAILED -- saving rejects to file
src/backend/optimizer/path/allpaths.c.rej

[1] - http://cfbot.cputube.org/patch_41_3246.log

Regards,
Vignesh

Re: Parallelize correlated subqueries that execute within each worker

Tomas Vondra <tomas.vondra@enterprisedb.com> — 2023-01-18T19:09:21Z

Hi,

This patch hasn't been updated since September, and it got broken by
4a29eabd1d91c5484426bc5836e0a7143b064f5a which the incremental sort
stuff a little bit. But the breakage was rather limited, so I took a
stab at fixing it - attached is the result, hopefully correct.

I also added a couple minor comments about stuff I noticed while
rebasing and skimming the patch, I kept those in separate commits.
There's also a couple pre-existing TODOs.

James, what's your plan with this patch. Do you intend to work on it for
PG16, or are there some issues I missed in the thread?


One of the queries in in incremental_sort changed plans a little bit:

explain (costs off) select distinct
  unique1,
  (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
from tenk1 t, generate_series(1, 1000);

switched from

 Unique  (cost=18582710.41..18747375.21 rows=10000 width=8)
   ->  Gather Merge  (cost=18582710.41..18697375.21 rows=10000000 ...)
         Workers Planned: 2
         ->  Sort  (cost=18582710.39..18593127.06 rows=4166667 ...)
               Sort Key: t.unique1, ((SubPlan 1))
             ...

to

 Unique  (cost=18582710.41..18614268.91 rows=10000 ...)
   ->  Gather Merge  (cost=18582710.41..18614168.91 rows=20000 ...)
         Workers Planned: 2
         ->  Unique  (cost=18582710.39..18613960.39 rows=10000 ...)
               ->  Sort  (cost=18582710.39..18593127.06 ...)
                     Sort Key: t.unique1, ((SubPlan 1))
                   ...

which probably makes sense, as the cost estimate decreases a bit.

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2023-01-19T02:34:21Z

On Wed, Jan 18, 2023 at 2:09 PM Tomas Vondra
<tomas.vondra@enterprisedb.com> wrote:
>
> Hi,
>
> This patch hasn't been updated since September, and it got broken by
> 4a29eabd1d91c5484426bc5836e0a7143b064f5a which the incremental sort
> stuff a little bit. But the breakage was rather limited, so I took a
> stab at fixing it - attached is the result, hopefully correct.

Thanks for fixing this up; the changes look correct to me.

> I also added a couple minor comments about stuff I noticed while
> rebasing and skimming the patch, I kept those in separate commits.
> There's also a couple pre-existing TODOs.

I started work on some of these, but wasn't able to finish this
evening, so I don't have an updated series yet.

> James, what's your plan with this patch. Do you intend to work on it for
> PG16, or are there some issues I missed in the thread?

I'd love to see it get into PG16. I don't have any known issues, but
reviewing activity has been light. Originally Robert had had some
concerns about my original approach; I think my updated approach
resolves those issues, but it'd be good to have that sign-off.

Beyond that I'm mostly looking for review and evaluation of the
approach I've taken; of note is my description of that in [1].

> One of the queries in in incremental_sort changed plans a little bit:
>
> explain (costs off) select distinct
>   unique1,
>   (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
> from tenk1 t, generate_series(1, 1000);
>
> switched from
>
>  Unique  (cost=18582710.41..18747375.21 rows=10000 width=8)
>    ->  Gather Merge  (cost=18582710.41..18697375.21 rows=10000000 ...)
>          Workers Planned: 2
>          ->  Sort  (cost=18582710.39..18593127.06 rows=4166667 ...)
>                Sort Key: t.unique1, ((SubPlan 1))
>              ...
>
> to
>
>  Unique  (cost=18582710.41..18614268.91 rows=10000 ...)
>    ->  Gather Merge  (cost=18582710.41..18614168.91 rows=20000 ...)
>          Workers Planned: 2
>          ->  Unique  (cost=18582710.39..18613960.39 rows=10000 ...)
>                ->  Sort  (cost=18582710.39..18593127.06 ...)
>                      Sort Key: t.unique1, ((SubPlan 1))
>                    ...
>
> which probably makes sense, as the cost estimate decreases a bit.

Off the cuff that seems fine. I'll read it over again when I send the
updated series.

James Coleman

1: https://www.postgresql.org/message-id/CAAaqYe8m0DHUWk7gLKb_C4abTD4nMkU26ErE%3Dahow4zNMZbzPQ%40mail.gmail.com

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2023-01-22T03:07:58Z

On Wed, Jan 18, 2023 at 9:34 PM James Coleman <jtc331@gmail.com> wrote:
>
> On Wed, Jan 18, 2023 at 2:09 PM Tomas Vondra
> <tomas.vondra@enterprisedb.com> wrote:
> >
> > Hi,
> >
> > This patch hasn't been updated since September, and it got broken by
> > 4a29eabd1d91c5484426bc5836e0a7143b064f5a which the incremental sort
> > stuff a little bit. But the breakage was rather limited, so I took a
> > stab at fixing it - attached is the result, hopefully correct.
>
> Thanks for fixing this up; the changes look correct to me.
>
> > I also added a couple minor comments about stuff I noticed while
> > rebasing and skimming the patch, I kept those in separate commits.
> > There's also a couple pre-existing TODOs.
>
> I started work on some of these, but wasn't able to finish this
> evening, so I don't have an updated series yet.
>
> > James, what's your plan with this patch. Do you intend to work on it for
> > PG16, or are there some issues I missed in the thread?
>
> I'd love to see it get into PG16. I don't have any known issues, but
> reviewing activity has been light. Originally Robert had had some
> concerns about my original approach; I think my updated approach
> resolves those issues, but it'd be good to have that sign-off.
>
> Beyond that I'm mostly looking for review and evaluation of the
> approach I've taken; of note is my description of that in [1].

Here's an updated patch version incorporating feedback from Tomas as
well as some additional comments and tweaks.

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. One
of the reasons I'm fairly confident that this is true is that the
original approach (which was significantly more invasive) definitely
required rechecking parallel safety at each level until we reached the
point where the subquery was known to be generated within the current
worker through the safe_param_ids tracking mechanism. Of course it is
possible that that complexity is actually required and this simplified
approach isn't feasible (but I don't have a good reason to suspect
that currently). It's also possible that the restrictions on
subqueries just aren't necessary...but that isn't compelling because
it would require proving that you can never have a query level with
as-yet unsatisfied lateral rels.

Note: All of the existing tests for "you can't parallelize a
correlated subquery" are all simple versions which are not actually
parallel unsafe in theory. I assume they were added to show that the
code excluded that broad case, and there wasn't any finer grain of
detail required since the code simply didn't support making the
decision with that granularity anyway. But that means there weren't
any existing test cases to exercise the granularity I'm now trying to
achieve.

If someone is willing to help out what I'd like help with currently is
finding such a test case (where a gather or gather merge path would
otherwise be created but at the current plan level not all of the
required lateral rels are yet available -- meaning that we can't
perform all of the subqueries within the current worker). In support
of that patch 0004 converts several of the new parallel safety checks
into WARNING messages instead to make it easy to see if a query
happens to encounter any of those checks.

James Coleman

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2023-01-23T14:00:31Z

On Sat, Jan 21, 2023 at 10:07 PM James Coleman <jtc331@gmail.com> 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

Re: Parallelize correlated subqueries that execute within each worker

Antonin Houska <ah@cybertec.at> — 2023-02-06T16:40:55Z

James Coleman <jtc331@gmail.com> wrote:

> On Sat, Jan 21, 2023 at 10:07 PM James Coleman <jtc331@gmail.com> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2023-02-08T13:38:27Z

On Mon, Feb 6, 2023 at 11:39 AM Antonin Houska <ah@cybertec.at> wrote:
>
> James Coleman <jtc331@gmail.com> wrote:
> > 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.
>
> 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.

Thanks for confirming.

>
> 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))

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.

> 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.

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

>
> 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.

Moved.

Attached is v9.

James Coleman

Re: Parallelize correlated subqueries that execute within each worker

Antonin Houska <ah@cybertec.at> — 2023-03-08T18:07:57Z

James Coleman <jtc331@gmail.com> wrote:

> On Mon, Feb 6, 2023 at 11:39 AM Antonin Houska <ah@cybertec.at> wrote:

> Attached is v9.

ok, I've changed the status to RfC

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

Re: Parallelize correlated subqueries that execute within each worker

Richard Guo <guofenglinux@gmail.com> — 2023-06-06T09:35:51Z

On Mon, Jan 23, 2023 at 10:00 PM James Coleman <jtc331@gmail.com> wrote:

> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2023-06-12T02:23:45Z

On Tue, Jun 6, 2023 at 4:36 AM Richard Guo <guofenglinux@gmail.com> wrote:
>
>
> On Mon, Jan 23, 2023 at 10:00 PM James Coleman <jtc331@gmail.com> wrote:
>>
>> 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.
>
>
> 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.

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!

> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

Richard Guo <guofenglinux@gmail.com> — 2023-06-26T06:47:57Z

On Mon, Jun 12, 2023 at 10:23 AM James Coleman <jtc331@gmail.com> wrote:

> 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.

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.

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

Thanks
Richard

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2023-07-04T01:26:44Z

On Sun, Jun 11, 2023 at 10:23 PM James Coleman <jtc331@gmail.com> wrote:
>
> ...
> > 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.
>
> 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!

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

Re: Parallelize correlated subqueries that execute within each worker

vignesh C <vignesh21@gmail.com> — 2024-01-09T07:08:48Z

On Tue, 4 Jul 2023 at 06:56, James Coleman <jtc331@gmail.com> wrote:
>
> On Sun, Jun 11, 2023 at 10:23 PM James Coleman <jtc331@gmail.com> wrote:
> >
> > ...
> > > 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.
> >
> > 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!
>
> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

Akshat Jaimini <destrex271@gmail.com> — 2024-01-23T14:33:22Z

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.

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2024-01-23T20:20:31Z

On Tue, Jan 23, 2024 at 9:34 AM Akshat Jaimini <destrex271@gmail.com> wrote:
> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

Akshat Jaimini <destrex271@gmail.com> — 2024-01-30T16:16:20Z
```
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.
```

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2024-01-30T16:54:34Z

On Tue, Jan 30, 2024 at 11:17 AM Akshat Jaimini <destrex271@gmail.com> wrote:
> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2024-01-31T02:51:09Z

On Tue, Jan 9, 2024 at 2:09 AM vignesh C <vignesh21@gmail.com> wrote:
> ...
> > 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.
>
> 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

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

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2024-01-31T02:56:20Z

On Tue, Jan 30, 2024 at 11:54 AM Robert Haas <robertmhaas@gmail.com> wrote:
>
> On Tue, Jan 30, 2024 at 11:17 AM Akshat Jaimini <destrex271@gmail.com> wrote:
> > 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.

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

Re: Parallelize correlated subqueries that execute within each worker

Tom Lane <tgl@sss.pgh.pa.us> — 2024-01-31T03:34:01Z

James Coleman <jtc331@gmail.com> writes:
> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2024-01-31T13:53:39Z

On Tue, Jan 30, 2024 at 10:34 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
>
> James Coleman <jtc331@gmail.com> writes:
> > 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.
>
> 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.

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

Re: Parallelize correlated subqueries that execute within each worker

Robert Haas <robertmhaas@gmail.com> — 2024-01-31T20:18:43Z

On Tue, Jan 30, 2024 at 9:56 PM James Coleman <jtc331@gmail.com> wrote:
> 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.

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.

> 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.

Sounds good.

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

Re: Parallelize correlated subqueries that execute within each worker

James Coleman <jtc331@gmail.com> — 2024-02-01T02:11:54Z

On Wed, Jan 31, 2024 at 3:18 PM Robert Haas <robertmhaas@gmail.com> wrote:
>
> On Tue, Jan 30, 2024 at 9:56 PM James Coleman <jtc331@gmail.com> wrote:
> > 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.
>
> 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.

Agreed they're very different. I'd thought it was actually in "Needs
review" and with no outstanding questions on the thread since July,
but maybe I'm missing something -- I've definitely misunderstood CF
app status before, but usually that's been in the other direction
(forgetting to mark it back to Needs Review after responding to a
Waiting on Author.

Regards,
James Coleman

Re: Parallelize correlated subqueries that execute within each worker

Tomas Vondra <tomas.vondra@enterprisedb.com> — 2024-07-20T23:06:55Z

Hi,

I was going through the "needs review" patches with no recent messages,
trying to figure out what is needed to move them forward, and this one
caught my eye because I commented on it before. And it's also a bit sad
example, because it started in 2021 and is moving at glacier speed :-(

I read through the thread, to understand how the design changed over
time, and I like the current approach (proposed by Robert) much more
than the initial idea of adding new flag next to parallel_safe etc.

And in general the patch looks reasonably simple and clean, but my
knowledge of PARAM intricacies is pretty much nil, so I'm hesitant to
claim the patch is correct. And I'm not sure what exactly needs to
happen to validate the approach :-(


The regression tests currently fail, due to a different plan for one of
the new queries in select_parallel. I guess it's due to some committed
patch, and it looks like a sensible change, but I haven't looked closely.

Also, I do get this warning when building with GCC 12.2.0 on Debian:

clauses.c: In function ‘max_parallel_hazard_walker’:
clauses.c:961:49: warning: ‘save_safe_param_ids’ may be used
uninitialized [-Wmaybe-uninitialized]
  961 |                         context->safe_param_ids =
save_safe_param_ids;
      |
~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~
clauses.c:943:29: note: ‘save_safe_param_ids’ was declared here
  943 |                 List       *save_safe_param_ids;
      |                             ^~~~~~~~~~~~~~~~~~~

It's harmless, the compiler simply does not realize the two blocks
(where save_safe_param_ids is set and used) have exactly the same if
conditions, but it's a bit confusing for people too.


I was wondering if this could affect some queries in TPC-H, but the only
query affected seems to be Q2 - where it helps, cutting the time in
half, but Q2 is generally pretty fast / the expensive part was already
parallelized quite well (i.e. the correlated subquery is fairly cheap).

However, it's not difficult to construct a query where this helps a lot.
If the correlated subquery does something expensive (e.g. aggregation of
non-trivial amounts of data), this would help. So I wonder if e.g.
TPC-DS would benefit from this more ...


A couple review comments about the code:

1) new fields in max_parallel_hazard_context should have comments:

+	bool		check_params;
+	Bitmapset **required_params;


2) Do we need both is_parallel_safe and is_parallel_safe_with_params?
ISTM the main difference is the for() loop, so why not add an extra
parameter to is_parallel_safe() and skip that loop if it's null? Or, if
we worry about external code, keep is_parallel_safe_with_params() and
define is_parallel_safe() as is_parallel_safe_with_params(...,NULL)?

3) Isn't it a bit weird that is_parallel_safe_with_params() actually
sets check_params=false, which seems like it doesn't actually check
parameters? I'm a bit confused / unsure if this is a bug or how it
actually checks parameters. If it's correct, it may need a comment.

4) The only place setting check_params is max_parallel_hazard, which is
called only for the whole Query from standard_planner(). But it does not
set required_params - can't this be an issue if the pointer happens to
be random garbage?

5) It probably needs a pgindent run, there's a bunch of rather long
lines and those are likely to get wrapped and look weird.

6) Is the comment in max_parallel_hazard_walker() still accurate? It
talks about PARAM_EXTERN and PARAM_EXEC, but the patch removes the
PARAM_EXTERN check entirely. So maybe the comment needs updating?

7) I don't like the very complex if condition very much, it's hard to
understand. I'd split that into two separate conditions, and add a short
comment for each of them. I.e. instead of:

  if (param->paramkind != PARAM_EXEC || !(context->check_params ||
context->required_params != NULL))
    return false;

I'd do

  /* ... comment ... */
  if (param->paramkind != PARAM_EXEC)
    return false;

  /* ... comment ... */
  if (!(context->check_params || context->required_params != NULL))
    return false;

or something like that.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Re: Parallelize correlated subqueries that execute within each worker

Andy Fan <zhihuifan1213@163.com> — 2025-07-03T14:04:22Z

Hi James:

Very nice to find this topic, I am recently working on this topic [1] as 
well without finding this topic has been discussed before. I just go
through this thread and find it goes with a different direction with mine.
would you mind to check my soluation to see is there any case I can't
cover? I suggested this because my soluation should be much easier than
yours. But I'm not suprised to know I'm miss some obvious keypoint. 

>
>> One of the queries in in incremental_sort changed plans a little bit:
>>
>> explain (costs off) select distinct
>>   unique1,
>>   (select t.unique1 from tenk1 where tenk1.unique1 = t.unique1)
>> from tenk1 t, generate_series(1, 1000);
>>
>> switched from
>>
>>  Unique  (cost=18582710.41..18747375.21 rows=10000 width=8)
>>    ->  Gather Merge  (cost=18582710.41..18697375.21 rows=10000000 ...)
>>          Workers Planned: 2
>>          ->  Sort  (cost=18582710.39..18593127.06 rows=4166667 ...)
>>                Sort Key: t.unique1, ((SubPlan 1))
>>              ...
>>
>> to
>>
>>  Unique  (cost=18582710.41..18614268.91 rows=10000 ...)
>>    ->  Gather Merge  (cost=18582710.41..18614168.91 rows=20000 ...)
>>          Workers Planned: 2
>>          ->  Unique  (cost=18582710.39..18613960.39 rows=10000 ...)
>>                ->  Sort  (cost=18582710.39..18593127.06 ...)
>>                      Sort Key: t.unique1, ((SubPlan 1))
>>                    ...
>>
>> which probably makes sense, as the cost estimate decreases a bit.
>
> Off the cuff that seems fine. I'll read it over again when I send the
> updated series.

I had a detailed explaination for this plan change in [1] and I think
this could be amazing gain no matter which way we go finally. 

[1] https://www.postgresql.org/message-id/871pqzm5wj.fsf@163.com 

-- 
Best Regards
Andy Fan