Parallel Full Hash Join

On Wed, Sep 11, 2019 at 11:23 PM Thomas Munro <thomas.munro@gmail.com>
wrote:

While thinking about looping hash joins (an alternative strategy for
limiting hash join memory usage currently being investigated by
Melanie Plageman in a nearby thread[1]), the topic of parallel query
deadlock hazards came back to haunt me. I wanted to illustrate the
problems I'm aware of with the concrete code where I ran into this
stuff, so here is a new-but-still-broken implementation of $SUBJECT.
This was removed from the original PHJ submission when I got stuck and
ran out of time in the release cycle for 11. Since the original
discussion is buried in long threads and some of it was also a bit
confused, here's a fresh description of the problems as I see them.
Hopefully these thoughts might help Melanie's project move forward,
because it's closely related, but I didn't want to dump another patch
into that other thread. Hence this new thread.

I haven't succeeded in actually observing a deadlock with the attached
patch (though I did last year, very rarely), but I also haven't tried
very hard. The patch seems to produce the right answers and is pretty
scalable, so it's really frustrating not to be able to get it over the
line.

Tuple queue deadlock hazard:

If the leader process is executing the subplan itself and waiting for
all processes to arrive in ExecParallelHashEndProbe() (in this patch)
while another process has filled up its tuple queue and is waiting for
the leader to read some tuples an unblock it, they will deadlock
forever. That can't happen in the the committed version of PHJ,
because it never waits for barriers after it has begun emitting
tuples.

Some possible ways to fix this:

1. You could probably make it so that the PHJ_BATCH_SCAN_INNER phase
in this patch (the scan for unmatched tuples) is executed by only one
process, using the "detach-and-see-if-you-were-last" trick. Melanie
proposed that for an equivalent problem in the looping hash join. I
think it probably works, but it gives up a lot of parallelism and thus
won't scale as nicely as the attached patch.

I have attached a patch which implements this
(v1-0001-Parallel-FOJ-ROJ-single-worker-scan-buckets.patch).

For starters, in order to support parallel FOJ and ROJ, I re-enabled
setting the match bit for the tuples in the hashtable which
3e4818e9dd5be294d97c disabled. I did so using the code suggested in [1]/messages/by-id/0F44E799048C4849BAE4B91012DB910462E9897A@SHSMSX103.ccr.corp.intel.com,
reading the match bit to see if it is already set before setting it.

Then, workers except for the last worker detach after exhausting the
outer side of a batch, leaving one worker to proceed to HJ_FILL_INNER
and do the scan of the hash table and emit unmatched inner tuples.

I have also attached a variant on this patch which I am proposing to
replace it (v1-0001-Parallel-FOJ-ROJ-single-worker-scan-chunks.patch)
which has a new ExecParallelScanHashTableForUnmatched() in which the
single worker doing the unmatched scan scans one HashMemoryChunk at a
time and then frees them as it goes. I thought this might perform better
than the version which uses the buckets because 1) it should do a bit
less pointer chasing and 2) it frees each chunk of the hash table as it
scans it which (maybe) would save a bit of time during
ExecHashTableDetachBatch() when it goes through and frees the hash
table, but, my preliminary tests showed a negligible difference between
this and the version using buckets. I will do a bit more testing,
though.

I tried a few other variants of these patches, including one in which
the workers detach from the batch inside of the batch loading and
probing phase machine, ExecParallelHashJoinNewBatch(). This meant that
all workers transition to HJ_FILL_INNER and then HJ_NEED_NEW_BATCH in
order to detach in the batch phase machine. This, however, involved
adding a lot of new variables to distinguish whether or or not the
unmatched outer scan was already done, whether or not the current worker
was the worker elected to do the scan, etc. Overall, it is probably
incorrect to use the HJ_NEED_NEW_BATCH state in this way. I had
originally tried this to avoid operating on the batch_barrier in the
main hash join state machine. I've found that the more different places
we add code attaching and detaching to the batch_barrier (and other PHJ
barriers, for that matter), the harder it is to debug the code, however,
I think in this case it is required.

2. You could probably make it so that only the leader process drops
out of executing the inner unmatched scan, and then I think you
wouldn't have this very specific problem at the cost of losing some
(but not all) parallelism (ie the leader), but there might be other
variants of the problem. For example, a GatherMerge leader process
might be blocked waiting for the next tuple for a tuple from P1, while
P2 is try to write to a full queue, and P1 waits for P2.

3. You could introduce some kind of overflow for tuple queues, so
that tuple queues can never block because they're full (until you run
out of extra memory buffers or disk and error out). I haven't
seriously looked into this but I'm starting to suspect it's the
industrial strength general solution to the problem and variants of it
that show up in other parallelism projects (Parallel Repartition). As
Robert mentioned last time I talked about this[2], you'd probably only
want to allow spooling (rather than waiting) when the leader is
actually waiting for other processes; I'm not sure how exactly to
control that.

4. <thinking-really-big>Goetz Graefe's writing about parallel sorting
comes close to this topic, which he calls flow control deadlocks. He
mentions the possibility of infinite spooling like (3) as a solution.
He's describing a world where producers and consumers are running
concurrently, and the consumer doesn't just decide to start running
the subplan (what we call "leader participation"), so he doesn't
actually have a problem like Gather deadlock. He describes
planner-enforced rules that allow deadlock free execution even with
fixed-size tuple queue flow control by careful controlling where
order-forcing operators are allowed to appear, so he doesn't have a
problem like Gather Merge deadlock. I'm not proposing we should
create a whole bunch of producer and consumer processes to run
different plan fragments, but I think you can virtualise the general
idea in an async executor with "streams", and that also solves other
problems when you start working with partitions in a world where it's
not even sure how many workers will show up. I see this as a long
term architectural goal requiring vast amounts of energy to achieve,
hence my new interest in (3) for now.</thinking-really-big>

Hypothetical inter-node deadlock hazard:

Right now I think it is the case the whenever any node begins pulling
tuples from a subplan, it continues to do so until either the query
ends early or the subplan runs out of tuples. For example, Append
processes its subplans one at a time until they're done -- it doesn't
jump back and forth. Parallel Append doesn't necessarily run them in
the order that they appear in the plan, but it still runs each one to
completion before picking another one. If we ever had a node that
didn't adhere to that rule, then two Parallel Full Hash Join nodes
could dead lock, if some of the workers were stuck waiting in one
while some were stuck waiting in the other.

If we were happy to decree that that is a rule of the current
PostgreSQL executor, then this hypothetical problem would go away.
For example, consider the old patch I recently rebased[3] to allow
Append over a bunch of FDWs representing remote shards to return
tuples as soon as they're ready, not necessarily sequentially (and I
think several others have worked on similar patches). To be
committable under such a rule that applies globally to the whole
executor, that patch would only be allowed to *start* them in any
order, but once it's started pulling tuples from a given subplan it'd
have to pull them all to completion before considering another node.

(Again, that problem goes away in an async model like (4), which will
also be able to do much more interesting things with FDWs, and it's
the FDW thing that I think generates more interest in async execution
than my rambling about abstract parallel query problems.)

The leader exclusion tactics and the spooling idea don't solve the
execution order deadlock possibility, so, this "all except last detach
and last does unmatched inner scan" seems like the best way to solve
both types of deadlock.
There is another option that could maintain some parallelism for the
unmatched inner scan.

This method is exactly like the "all except last detach and last does
unmatched inner scan" method from the perspective of the main hash join
state machine. The difference is in ExecParallelHashJoinNewBatch(). In
the batch_barrier phase machine, workers loop around looking for batches
that are not done.

In this "detach for now" method, all workers except the last one detach
from a batch after exhausting the outer side. They will mark the batch
they were just working on as "provisionally done" (as opposed to
"done"). The last worker advances the batch_barrier from
PHJ_BATCH_PROBING to PHJ_BATCH_SCAN_INNER.

All detached workers then proceed to HJ_NEED_NEW_BATCH and try to find
another batch to work on. If there are no batches that are neither
"done" or "provisionally done", then the worker will re-attach to
batches that are "provisionally done" and attempt to join in conducting
the unmatched inner scan. Once it finishes its worker there, it will
return to HJ_NEED_NEW_BATCH, enter ExecParallelHashJoinNewBatch() and
mark the batch as "done".

Because the worker detached from the batch, this method solves the tuple
queue flow control deadlock issue--this worker could not be attempting
to emit a tuple while the leader waits at the barrier for it. There is
no waiting at the barrier.

However, it is unclear to me whether or not this method will be at risk
of inter-node deadlock/execution order deadlock. It seems like this is
not more at risk than the existing code is for this issue.

If a worker never returns to the HashJoin after leaving to emit a tuple,
in any of the methods (and in master), the query would not finish
correctly because the workers are attached to the batch_barrier while
emitting tuples and, though they may not wait at this barrier again, the
hashtable is cleaned up by the last participant to detach, and this
would not happen if it doesn't return to the batch phase machine. I'm
not sure if this exhibits the problematic behavior detailed above, but,
if it does, it is not unique to this method.

Some other notes on the patch:

Aside from the deadlock problem, there are some minor details to tidy
up (handling of late starters probably not quite right, rescans not
yet considered).

These would not be an issue with only one worker doing the scan but
would have to be handled in a potential new parallel-enabled solution
like I suggested above.

There is a fun hard-coded parameter that controls
the parallel step size in terms of cache lines for the unmatched scan;
I found that 8 was a lot faster than 4, but no slower than 128 on my
laptop, so I set it to 8.

I didn't add this cache line optimization to my chunk scanning method. I
could do so. Do you think it is more relevant, less relevant, or the
same if only one worker is doing the unmatched inner scan?

More thoughts along those micro-optimistic

lines: instead of match bit in the header, you could tag the pointer
and sometimes avoid having to follow it, and you could prefetch next
non-matching tuple's cacheline by looking a head a bit.

I would be happy to try doing this once we get the rest of the patch
ironed out so that seeing how much of a performance difference it makes
is more straightforward.

[1]
/messages/by-id/CA+hUKGKWWmf=WELLG=aUGbcugRaSQbtm0tKYiBut-B2rVKX63g@mail.gmail.com
[2]
/messages/by-id/CA+TgmoY4LogYcg1y5JPtto_fL-DBUqvxRiZRndDC70iFiVsVFQ@mail.gmail.com
[3]
/messages/by-id/CA+hUKGLBRyu0rHrDCMC4=Rn3252gogyp1SjOgG8SEKKZv=FwfQ@mail.gmail.com

[1]: /messages/by-id/0F44E799048C4849BAE4B91012DB910462E9897A@SHSMSX103.ccr.corp.intel.com
/messages/by-id/0F44E799048C4849BAE4B91012DB910462E9897A@SHSMSX103.ccr.corp.intel.com

-- Melanie

On Tue, Sep 22, 2020 at 8:49 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

On Wed, Sep 11, 2019 at 11:23 PM Thomas Munro <thomas.munro@gmail.com> wrote:

1. You could probably make it so that the PHJ_BATCH_SCAN_INNER phase
in this patch (the scan for unmatched tuples) is executed by only one
process, using the "detach-and-see-if-you-were-last" trick. Melanie
proposed that for an equivalent problem in the looping hash join. I
think it probably works, but it gives up a lot of parallelism and thus
won't scale as nicely as the attached patch.

I have attached a patch which implements this
(v1-0001-Parallel-FOJ-ROJ-single-worker-scan-buckets.patch).

Hi Melanie,

Thanks for working on this! I have a feeling this is going to be much
easier to land than the mighty hash loop patch. And it's good to get
one of our blocking design questions nailed down for both patches.

I took it for a very quick spin and saw simple cases working nicely,
but TPC-DS queries 51 and 97 (which contain full joins) couldn't be
convinced to use it. Hmm.

For starters, in order to support parallel FOJ and ROJ, I re-enabled
setting the match bit for the tuples in the hashtable which
3e4818e9dd5be294d97c disabled. I did so using the code suggested in [1],
reading the match bit to see if it is already set before setting it.

Cool. I'm quite keen to add a "fill_inner" parameter for
ExecHashJoinImpl() and have an N-dimensional lookup table of
ExecHashJoin variants, so that this and much other related branching
can be constant-folded out of existence by the compiler in common
cases, which is why I think this is all fine, but that's for another
day...

Then, workers except for the last worker detach after exhausting the
outer side of a batch, leaving one worker to proceed to HJ_FILL_INNER
and do the scan of the hash table and emit unmatched inner tuples.

+1

Doing better is pretty complicated within our current execution model,
and I think this is a good compromise for now.

Costing for uneven distribution is tricky; depending on your plan
shape, specifically whether there is something else to do afterwards
to pick up the slack, it might or might not affect the total run time
of the query. It seems like there's not much we can do about that.

I have also attached a variant on this patch which I am proposing to
replace it (v1-0001-Parallel-FOJ-ROJ-single-worker-scan-chunks.patch)
which has a new ExecParallelScanHashTableForUnmatched() in which the
single worker doing the unmatched scan scans one HashMemoryChunk at a
time and then frees them as it goes. I thought this might perform better
than the version which uses the buckets because 1) it should do a bit
less pointer chasing and 2) it frees each chunk of the hash table as it
scans it which (maybe) would save a bit of time during
ExecHashTableDetachBatch() when it goes through and frees the hash
table, but, my preliminary tests showed a negligible difference between
this and the version using buckets. I will do a bit more testing,
though.

+1

I agree that it's the better of those two options.

[stuff about deadlocks]

The leader exclusion tactics and the spooling idea don't solve the
execution order deadlock possibility, so, this "all except last detach
and last does unmatched inner scan" seems like the best way to solve
both types of deadlock.

Agreed (at least as long as our threads of query execution are made
out of C call stacks and OS processes that block).

Some other notes on the patch:

Aside from the deadlock problem, there are some minor details to tidy
up (handling of late starters probably not quite right, rescans not
yet considered).

These would not be an issue with only one worker doing the scan but
would have to be handled in a potential new parallel-enabled solution
like I suggested above.

Makes sense. Not sure why I thought anything special was needed for rescans.

There is a fun hard-coded parameter that controls
the parallel step size in terms of cache lines for the unmatched scan;
I found that 8 was a lot faster than 4, but no slower than 128 on my
laptop, so I set it to 8.

I didn't add this cache line optimization to my chunk scanning method. I
could do so. Do you think it is more relevant, less relevant, or the
same if only one worker is doing the unmatched inner scan?

Yeah it's irrelevant for a single process, and even more irrelevant if
we go with your chunk-based version.

More thoughts along those micro-optimistic
lines: instead of match bit in the header, you could tag the pointer
and sometimes avoid having to follow it, and you could prefetch next
non-matching tuple's cacheline by looking a head a bit.

I would be happy to try doing this once we get the rest of the patch
ironed out so that seeing how much of a performance difference it makes
is more straightforward.

Ignore that, I have no idea if the maintenance overhead for such an
every-tuple-in-this-chain-is-matched tag bit would be worth it, it was
just an idle thought. I think your chunk-scan plan seems sensible for
now.

From a quick peek:

+/*
+ * Upon arriving at the barrier, if this worker is not the last
worker attached,
+ * detach from the barrier and return false. If this worker is the last worker,
+ * remain attached and advance the phase of the barrier, return true
to indicate
+ * you are the last or "elected" worker who is still attached to the barrier.
+ * Another name I considered was BarrierUniqueify or BarrierSoloAssign
+ */
+bool
+BarrierDetachOrElect(Barrier *barrier)

I tried to find some existing naming in writing about
barriers/phasers, but nothing is jumping out at me. I think a lot of
this stuff comes from super computing where I guess "make all of the
threads give up except one" isn't a primitive they'd be too excited
about :-)

BarrierArriveAndElectOrDetach()... gah, no.

+ last = BarrierDetachOrElect(&batch->batch_barrier);

I'd be nice to add some assertions after that, in the 'last' path,
that there's only one participant and that the phase is as expected,
just to make it even clearer to the reader, and a comment in the other
path that we are no longer attached.

+    hjstate->hj_AllocatedBucketRange = 0;
...
+    pg_atomic_uint32 bucket;    /* bucket allocator for unmatched inner scan */
...
+                //volatile int mybp = 0; while (mybp == 0)

Some leftover fragments of the bucket-scan version and debugging stuff.

On Mon, Sep 21, 2020 at 8:34 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Tue, Sep 22, 2020 at 8:49 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

On Wed, Sep 11, 2019 at 11:23 PM Thomas Munro <thomas.munro@gmail.com>

wrote:

I took it for a very quick spin and saw simple cases working nicely,
but TPC-DS queries 51 and 97 (which contain full joins) couldn't be
convinced to use it. Hmm.

Thanks for taking a look, Thomas!

Both query 51 and query 97 have full outer joins of two CTEs, each of
which are aggregate queries.

During planning when constructing the joinrel and choosing paths, in
hash_inner_and_outer(), we don't consider parallel hash parallel hash
join paths because the outerrel and innerrel do not have
partial_pathlists.

This code

if (joinrel->consider_parallel &&
save_jointype != JOIN_UNIQUE_OUTER &&
outerrel->partial_pathlist != NIL &&
bms_is_empty(joinrel->lateral_relids))

gates the code to generate partial paths for hash join.

My understanding of this is that if the inner and outerrel don't have
partial paths, then they can't be executed in parallel, so the join
could not be executed in parallel.

For the two TPC-DS queries, even if they use parallel aggs, the finalize
agg will have to be done by a single worker, so I don't think they could
be joined with a parallel hash join.

I added some logging inside the "if" statement and ran join_hash.sql in
regress to see what nodes were typically in the pathlist and partial
pathlist. All of them had basically just sequential scans as the outer
and inner rel paths. regress examples are definitely meant to be
minimal, so this probably wasn't the best place to look for examples of
more complex rels that can be joined with a parallel hash join.

Some other notes on the patch:

From a quick peek:

+/*
+ * Upon arriving at the barrier, if this worker is not the last
worker attached,
+ * detach from the barrier and return false. If this worker is the last
worker,
+ * remain attached and advance the phase of the barrier, return true
to indicate
+ * you are the last or "elected" worker who is still attached to the
barrier.
+ * Another name I considered was BarrierUniqueify or BarrierSoloAssign
+ */
+bool
+BarrierDetachOrElect(Barrier *barrier)

I tried to find some existing naming in writing about
barriers/phasers, but nothing is jumping out at me. I think a lot of
this stuff comes from super computing where I guess "make all of the
threads give up except one" isn't a primitive they'd be too excited
about :-)

BarrierArriveAndElectOrDetach()... gah, no.

You're right that Arrive should be in there.
So, I went with BarrierArriveAndDetachExceptLast()
It's specific, if not clever.

+ last = BarrierDetachOrElect(&batch->batch_barrier);

I'd be nice to add some assertions after that, in the 'last' path,
that there's only one participant and that the phase is as expected,
just to make it even clearer to the reader, and a comment in the other
path that we are no longer attached.

Assert and comment added to the single worker path.
The other path is just back to HJ_NEED_NEW_BATCH and workers will detach
there as before, so I'm not sure where we could add the comment about
the other workers detaching.

+    hjstate->hj_AllocatedBucketRange = 0;
...
+    pg_atomic_uint32 bucket;    /* bucket allocator for unmatched inner
scan */
...
+                //volatile int mybp = 0; while (mybp == 0)

Some leftover fragments of the bucket-scan version and debugging stuff.

cleaned up (and rebased).

I also changed ExecScanHashTableForUnmatched() to scan HashMemoryChunks
in the hashtable instead of using the buckets to align parallel and
serial hash join code.

Originally, I had that code freeing the chunks of the hashtable after
finishing scanning them, however, I noticed this query from regress
failing:

select * from
(values (1, array[10,20]), (2, array[20,30])) as v1(v1x,v1ys)
left join (values (1, 10), (2, 20)) as v2(v2x,v2y) on v2x = v1x
left join unnest(v1ys) as u1(u1y) on u1y = v2y;

It is because the hash join gets rescanned and because there is only one
batch, ExecReScanHashJoin reuses the same hashtable.

QUERY PLAN
-------------------------------------------------------------
Nested Loop Left Join
-> Values Scan on "*VALUES*"
-> Hash Right Join
Hash Cond: (u1.u1y = "*VALUES*_1".column2)
Filter: ("*VALUES*_1".column1 = "*VALUES*".column1)
-> Function Scan on unnest u1
-> Hash
-> Values Scan on "*VALUES*_1"

I was freeing the hashtable as I scanned each chunk, which clearly
doesn't work for a single batch hash join which gets rescanned.

I don't see anything specific to parallel hash join in ExecReScanHashJoin(),
so, it seems like the same rules apply to parallel hash join. So, I will
have to remove the logic that frees the hash table after scanning each
chunk from the parallel function as well.

In addition, I still need to go through the patch with a fine tooth comb
(refine the comments and variable names and such) but just wanted to
check that these changes were in line with what you were thinking first.

Regards,
Melanie (Microsoft)

I've attached a patch with the corrections I mentioned upthread.
I've gone ahead and run pgindent, though, I can't say that I'm very
happy with the result.

I'm still not quite happy with the name
BarrierArriveAndDetachExceptLast(). It's so literal. As you said, there
probably isn't a nice name for this concept, since it is a function with
the purpose of terminating parallelism.

Regards,
Melanie (Microsoft)

Hi Melanie,

On Thu, Nov 5, 2020 at 7:34 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I've attached a patch with the corrections I mentioned upthread.
I've gone ahead and run pgindent, though, I can't say that I'm very
happy with the result.

I'm still not quite happy with the name
BarrierArriveAndDetachExceptLast(). It's so literal. As you said, there
probably isn't a nice name for this concept, since it is a function with
the purpose of terminating parallelism.

You sent in your patch, v3-0001-Support-Parallel-FOJ-and-ROJ.patch to
pgsql-hackers on Nov 5, but you did not post it to the next
CommitFest[1]https://commitfest.postgresql.org/31/. If this was intentional, then you need to take no
action. However, if you want your patch to be reviewed as part of the
upcoming CommitFest, then you need to add it yourself before
2021-01-01 AOE[2]https://en.wikipedia.org/wiki/Anywhere_on_Earth. Also, rebasing to the current HEAD may be required
as almost two months passed since when this patch is submitted. Thanks
for your contributions.

Regards,

[1]: https://commitfest.postgresql.org/31/
[2]: https://en.wikipedia.org/wiki/Anywhere_on_Earth

Regards,

--
Masahiko Sawada
EnterpriseDB: https://www.enterprisedb.com/

On Mon, Dec 28, 2020 at 9:49 PM Masahiko Sawada <sawada.mshk@gmail.com> wrote:

On Thu, Nov 5, 2020 at 7:34 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I've attached a patch with the corrections I mentioned upthread.
I've gone ahead and run pgindent, though, I can't say that I'm very
happy with the result.

I'm still not quite happy with the name
BarrierArriveAndDetachExceptLast(). It's so literal. As you said, there
probably isn't a nice name for this concept, since it is a function with
the purpose of terminating parallelism.

You sent in your patch, v3-0001-Support-Parallel-FOJ-and-ROJ.patch to
pgsql-hackers on Nov 5, but you did not post it to the next
CommitFest[1]. If this was intentional, then you need to take no
action. However, if you want your patch to be reviewed as part of the
upcoming CommitFest, then you need to add it yourself before
2021-01-01 AOE[2]. Also, rebasing to the current HEAD may be required
as almost two months passed since when this patch is submitted. Thanks
for your contributions.

Thanks for this reminder Sawada-san. I had some feedback I meant to
post in November but didn't get around to:

+bool
+BarrierArriveAndDetachExceptLast(Barrier *barrier)

I committed this part (7888b099). I've attached a rebase of the rest
of Melanie's v3 patch.

+ WAIT_EVENT_HASH_BATCH_PROBE,

That new wait event isn't needed (we can't and don't wait).

  *  PHJ_BATCH_PROBING        -- all probe
- *  PHJ_BATCH_DONE           -- end
+
+ *  PHJ_BATCH_DONE           -- queries not requiring inner fill done
+ *  PHJ_BATCH_FILL_INNER_DONE -- inner fill completed, all queries done

Would it be better/tidier to keep _DONE as the final phase? That is,
to switch around these two final phases. Or does that make it too
hard to coordinate the detach-and-cleanup logic?

+/*
+ * ExecPrepHashTableForUnmatched
+ *             set up for a series of ExecScanHashTableForUnmatched calls
+ *             return true if this worker is elected to do the
unmatched inner scan
+ */
+bool
+ExecParallelPrepHashTableForUnmatched(HashJoinState *hjstate)

Comment name doesn't match function name.

On Tue, Dec 29, 2020 at 03:28:12PM +1300, Thomas Munro wrote:

I had some feedback I meant to
post in November but didn't get around to:

*  PHJ_BATCH_PROBING        -- all probe
- *  PHJ_BATCH_DONE           -- end
+
+ *  PHJ_BATCH_DONE           -- queries not requiring inner fill done
+ *  PHJ_BATCH_FILL_INNER_DONE -- inner fill completed, all queries done

Would it be better/tidier to keep _DONE as the final phase? That is,
to switch around these two final phases. Or does that make it too
hard to coordinate the detach-and-cleanup logic?

I updated this to use your suggestion. My rationale for having
PHJ_BATCH_DONE and then PHJ_BATCH_FILL_INNER_DONE was that, for a worker
attaching to the batch for the first time, it might be confusing that it
is in the PHJ_BATCH_FILL_INNER state (not the DONE state) and yet that
worker still just detaches and moves on. It didn't seem intuitive.
Anyway, I think that is all sort of confusing and unnecessary. I changed
it to PHJ_BATCH_FILLING_INNER -- then when a worker who hasn't ever been
attached to this batch before attaches, it will be in the
PHJ_BATCH_FILLING_INNER phase, which it cannot help with and it will
detach and move on.

+/*
+ * ExecPrepHashTableForUnmatched
+ *             set up for a series of ExecScanHashTableForUnmatched calls
+ *             return true if this worker is elected to do the
unmatched inner scan
+ */
+bool
+ExecParallelPrepHashTableForUnmatched(HashJoinState *hjstate)

Comment name doesn't match function name.

Updated -- and a few other comment updates too.

I just attached the diff.

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so
I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

On Fri, Mar 5, 2021 at 8:31 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so
I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

Feedback on
v6-0002-Improve-the-naming-of-Parallel-Hash-Join-phases.patch

I like renaming DONE to FREE and ALLOCATE TO REALLOCATE in the grow
barriers. FREE only makes sense for the Build barrier if you keep the
added PHJ_BUILD_RUN phase, though, I assume you would change this patch
if you decided not to add the new build barrier phase.

I like the addition of the asterisks to indicate a phase is executed by
a single arbitrary process. I was thinking, shall we add one of these to
HJ_FILL_INNER since it is only done by one process in parallel right and
full hash join? Maybe that's confusing because serial hash join uses
that state machine too, though. Maybe **? Maybe we should invent a
complicated symbolic language :)

One tiny, random, unimportant thing: The function prototype for
ExecParallelHashJoinPartitionOuter() calls its parameter "node" and, in
the definition, it is called "hjstate". This feels like a good patch to
throw in that tiny random change to make the name the same.

static void ExecParallelHashJoinPartitionOuter(HashJoinState *node);

static void
ExecParallelHashJoinPartitionOuter(HashJoinState *hjstate)

Hi,
For v6-0003-Parallel-Hash-Full-Right-Outer-Join.patch

+ * current_chunk_idx: index in current HashMemoryChunk

The above comment seems to be better fit
for ExecScanHashTableForUnmatched(), instead
of ExecParallelPrepHashTableForUnmatched.
I wonder where current_chunk_idx should belong (considering the above
comment and what the code does).

+       while (hashtable->current_chunk_idx <
hashtable->current_chunk->used)
...
+       next = hashtable->current_chunk->next.unshared;
+       hashtable->current_chunk = next;
+       hashtable->current_chunk_idx = 0;

Each time we advance to the next chunk, current_chunk_idx is reset. It
seems current_chunk_idx can be placed inside chunk.
Maybe the consideration is that, with the current formation we save space
by putting current_chunk_idx field at a higher level.
If that is the case, a comment should be added.

Cheers

On Fri, Mar 5, 2021 at 5:31 PM Thomas Munro <thomas.munro@gmail.com> wrote:

Show quoted text

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com>
wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so
I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

On Fri, Apr 2, 2021 at 3:06 PM Zhihong Yu <zyu@yugabyte.com> wrote:

Hi,
For v6-0003-Parallel-Hash-Full-Right-Outer-Join.patch

+ * current_chunk_idx: index in current HashMemoryChunk

The above comment seems to be better fit for ExecScanHashTableForUnmatched(), instead of ExecParallelPrepHashTableForUnmatched.
I wonder where current_chunk_idx should belong (considering the above comment and what the code does).

+       while (hashtable->current_chunk_idx < hashtable->current_chunk->used)
...
+       next = hashtable->current_chunk->next.unshared;
+       hashtable->current_chunk = next;
+       hashtable->current_chunk_idx = 0;

Each time we advance to the next chunk, current_chunk_idx is reset. It seems current_chunk_idx can be placed inside chunk.
Maybe the consideration is that, with the current formation we save space by putting current_chunk_idx field at a higher level.
If that is the case, a comment should be added.

Thank you for the review. I think that moving the current_chunk_idx into
the HashMemoryChunk would probably take up too much space.

Other places that we loop through the tuples in the chunk, we are able
to just keep a local idx, like here in
ExecParallelHashIncreaseNumBuckets():

case PHJ_GROW_BUCKETS_REINSERTING:
...
while ((chunk = ExecParallelHashPopChunkQueue(hashtable, &chunk_s)))
{
size_t idx = 0;

while (idx < chunk->used)

but, since we cannot do that while also emitting tuples, I thought,
let's just stash the index in the hashtable for use in serial hash join
and the batch accessor for parallel hash join. A comment to this effect
sounds good to me.

On Tue, Apr 6, 2021 at 11:59 AM Melanie Plageman <melanieplageman@gmail.com>
wrote:

On Fri, Apr 2, 2021 at 3:06 PM Zhihong Yu <zyu@yugabyte.com> wrote:

Hi,
For v6-0003-Parallel-Hash-Full-Right-Outer-Join.patch

+ * current_chunk_idx: index in current HashMemoryChunk

The above comment seems to be better fit for

ExecScanHashTableForUnmatched(), instead of
ExecParallelPrepHashTableForUnmatched.

I wonder where current_chunk_idx should belong (considering the above

comment and what the code does).

+ while (hashtable->current_chunk_idx <

hashtable->current_chunk->used)

...
+       next = hashtable->current_chunk->next.unshared;
+       hashtable->current_chunk = next;
+       hashtable->current_chunk_idx = 0;

Each time we advance to the next chunk, current_chunk_idx is reset. It

seems current_chunk_idx can be placed inside chunk.

Maybe the consideration is that, with the current formation we save

space by putting current_chunk_idx field at a higher level.

If that is the case, a comment should be added.

Thank you for the review. I think that moving the current_chunk_idx into
the HashMemoryChunk would probably take up too much space.

Other places that we loop through the tuples in the chunk, we are able
to just keep a local idx, like here in
ExecParallelHashIncreaseNumBuckets():

case PHJ_GROW_BUCKETS_REINSERTING:
...
while ((chunk = ExecParallelHashPopChunkQueue(hashtable,
&chunk_s)))
{
size_t idx = 0;

while (idx < chunk->used)

but, since we cannot do that while also emitting tuples, I thought,
let's just stash the index in the hashtable for use in serial hash join
and the batch accessor for parallel hash join. A comment to this effect
sounds good to me.

From the way HashJoinTable is used, I don't have better idea w.r.t. the
location of current_chunk_idx.
It is not worth introducing another level of mapping between HashJoinTable
and the chunk index.

So the current formation is fine with additional comment
in ParallelHashJoinBatchAccessor (current comment doesn't explicitly
mention current_chunk_idx).

Cheers

On Sat, Mar 6, 2021 at 12:31 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so
I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

Patches 0002, 0003 no longer apply to the master branch, seemingly
because of subsequent changes to pgstat, so need rebasing.

Regards,
Greg Nancarrow
Fujitsu Australia

On Mon, May 31, 2021 at 10:47 AM Greg Nancarrow <gregn4422@gmail.com> wrote:

On Sat, Mar 6, 2021 at 12:31 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so
I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

Patches 0002, 0003 no longer apply to the master branch, seemingly
because of subsequent changes to pgstat, so need rebasing.

I am changing the status to "Waiting on Author" as the patch does not
apply on Head.

Regards,
Vignesh

On Sat, Jul 10, 2021 at 9:13 AM vignesh C <vignesh21@gmail.com> wrote:

On Mon, May 31, 2021 at 10:47 AM Greg Nancarrow <gregn4422@gmail.com> wrote:

On Sat, Mar 6, 2021 at 12:31 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so
I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

Patches 0002, 0003 no longer apply to the master branch, seemingly
because of subsequent changes to pgstat, so need rebasing.

I am changing the status to "Waiting on Author" as the patch does not
apply on Head.

Regards,
Vignesh

Rebased patches attached. I will change status back to "Ready for Committer"

On Fri, Jul 30, 2021 at 04:34:34PM -0400, Melanie Plageman wrote:

On Sat, Jul 10, 2021 at 9:13 AM vignesh C <vignesh21@gmail.com> wrote:

On Mon, May 31, 2021 at 10:47 AM Greg Nancarrow <gregn4422@gmail.com> wrote:

On Sat, Mar 6, 2021 at 12:31 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Tue, Mar 2, 2021 at 11:27 PM Thomas Munro <thomas.munro@gmail.com> wrote:

On Fri, Feb 12, 2021 at 11:02 AM Melanie Plageman
<melanieplageman@gmail.com> wrote:

I just attached the diff.

Squashed into one patch for the cfbot to chew on, with a few minor
adjustments to a few comments.

I did some more minor tidying of comments and naming. It's been on my
to-do-list to update some phase names after commit 3048898e, and while
doing that I couldn't resist the opportunity to change DONE to FREE,
which somehow hurts my brain less, and makes much more obvious sense
after the bugfix in CF #3031 that splits DONE into two separate
phases. It also pairs obviously with ALLOCATE. I include a copy of
that bugix here too as 0001, because I'll likely commit that first, so

Hi Thomas,

Do you intend to commit 0001 soon? Specially if this apply to 14 should
be committed in the next days.

I rebased the stack of patches that way. 0002 includes the renaming I
propose (master only). Then 0003 is Melanie's patch, using the name
SCAN for the new match bit scan phase. I've attached an updated
version of my "phase diagram" finger painting, to show how it looks
with these three patches. "scan*" is new.

0002: my only concern is that this will cause innecesary pain in
backpatch-ing future code... but not doing that myself will let that to
the experts

0003: i'm testing this now, not at a big scale but just to try to find
problems

--
Jaime Casanova
Director de Servicios Profesionales
SystemGuards - Consultores de PostgreSQL

On Tue, Sep 21, 2021 at 9:29 AM Jaime Casanova
<jcasanov@systemguards.com.ec> wrote:

Do you intend to commit 0001 soon? Specially if this apply to 14 should
be committed in the next days.

Thanks for the reminder. Yes, I'm looking at this now, and looking
into the crash of this patch set on CI:

https://cirrus-ci.com/task/5282889613967360

Unfortunately, cfbot is using very simple and old CI rules which don't
have a core dump analysis step on that OS. :-( (I have a big upgrade
to all this CI stuff in the pipeline to fix that, get full access to
all logs, go faster, and many other improvements, after learning a lot
of tricks about running these types of systems over the past year --
more soon.)

0003: i'm testing this now, not at a big scale but just to try to find
problems

Thanks!

Rebased patches attached. I will change status back to "Ready for Committer"

The CI showed a crash on freebsd, which I reproduced.
https://cirrus-ci.com/task/5203060415791104

The crash is evidenced in 0001 - but only ~15% of the time.

I think it's the same thing which was committed and then reverted here, so
maybe I'm not saying anything new.

https://commitfest.postgresql.org/33/3031/
/messages/by-id/20200929061142.GA29096@paquier.xyz

(gdb) p pstate->build_barrier->phase
Cannot access memory at address 0x7f82e0fa42f4

#1 0x00007f13de34f801 in __GI_abort () at abort.c:79
#2 0x00005638e6a16d28 in ExceptionalCondition (conditionName=conditionName@entry=0x5638e6b62850 "!pstate || BarrierPhase(&pstate->build_barrier) >= PHJ_BUILD_RUN",
errorType=errorType@entry=0x5638e6a6f00b "FailedAssertion", fileName=fileName@entry=0x5638e6b625be "nodeHash.c", lineNumber=lineNumber@entry=3305) at assert.c:69
#3 0x00005638e678085b in ExecHashTableDetach (hashtable=0x5638e8e6ca88) at nodeHash.c:3305
#4 0x00005638e6784656 in ExecShutdownHashJoin (node=node@entry=0x5638e8e57cb8) at nodeHashjoin.c:1400
#5 0x00005638e67666d8 in ExecShutdownNode (node=0x5638e8e57cb8) at execProcnode.c:812
#6 ExecShutdownNode (node=0x5638e8e57cb8) at execProcnode.c:772
#7 0x00005638e67cd5b1 in planstate_tree_walker (planstate=planstate@entry=0x5638e8e58580, walker=walker@entry=0x5638e6766680 <ExecShutdownNode>, context=context@entry=0x0) at nodeFuncs.c:4009
#8 0x00005638e67666b2 in ExecShutdownNode (node=0x5638e8e58580) at execProcnode.c:792
#9 ExecShutdownNode (node=0x5638e8e58580) at execProcnode.c:772
#10 0x00005638e67cd5b1 in planstate_tree_walker (planstate=planstate@entry=0x5638e8e58418, walker=walker@entry=0x5638e6766680 <ExecShutdownNode>, context=context@entry=0x0) at nodeFuncs.c:4009
#11 0x00005638e67666b2 in ExecShutdownNode (node=0x5638e8e58418) at execProcnode.c:792
#12 ExecShutdownNode (node=node@entry=0x5638e8e58418) at execProcnode.c:772
#13 0x00005638e675f518 in ExecutePlan (execute_once=<optimized out>, dest=0x5638e8df0058, direction=<optimized out>, numberTuples=0, sendTuples=<optimized out>, operation=CMD_SELECT,
use_parallel_mode=<optimized out>, planstate=0x5638e8e58418, estate=0x5638e8e57a10) at execMain.c:1658
#14 standard_ExecutorRun () at execMain.c:410
#15 0x00005638e6763e0a in ParallelQueryMain (seg=0x5638e8d823d8, toc=0x7f13df4e9000) at execParallel.c:1493
#16 0x00005638e663f6c7 in ParallelWorkerMain () at parallel.c:1495
#17 0x00005638e68542e4 in StartBackgroundWorker () at bgworker.c:858
#18 0x00005638e6860f53 in do_start_bgworker (rw=<optimized out>) at postmaster.c:5883
#19 maybe_start_bgworkers () at postmaster.c:6108
#20 0x00005638e68619e5 in sigusr1_handler (postgres_signal_arg=<optimized out>) at postmaster.c:5272
#21 <signal handler called>
#22 0x00007f13de425ff7 in __GI___select (nfds=nfds@entry=7, readfds=readfds@entry=0x7ffef03b8400, writefds=writefds@entry=0x0, exceptfds=exceptfds@entry=0x0, timeout=timeout@entry=0x7ffef03b8360)
at ../sysdeps/unix/sysv/linux/select.c:41
#23 0x00005638e68620ce in ServerLoop () at postmaster.c:1765
#24 0x00005638e6863bcc in PostmasterMain () at postmaster.c:1473
#25 0x00005638e658fd00 in main (argc=8, argv=0x5638e8d54730) at main.c:198