Re: Proposed Patch to Improve Performance of Multi-BatchHash Join for Skewed Data Sets

> > > Because there is no nice way in PostgreSQL (that I know of) to
derive
> > > a histogram after a join (on an intermediate result) currently
> > > usingMostCommonValues is only enabled on a join when the outer
(probe)
> > > side is a table scan (seq scan only actually). See
> > > getMostCommonValues (soon to be called
> > > ExecHashJoinGetMostCommonValues) for the logic that determines
this.
>
> So my test case of "do a whole bunch of hash joins in a test query"
> isn't really valid. Makes sense. I did another, more haphazard test on
a
> query with fewer joins, and saw noticeable speedups.
>
> > It's starting to seem to me that the case where this patch provides
a
> > benefit is so narrow that I'm not sure it's worth the extra code.
>
> Not that anyone asked, but I don't consider myself qualified to render
> judgement on that point. Code size is, I guess, a maintainability
issue,
> and I'm not terribly experienced maintaining PostgreSQL :)
>
> > Is it realistic to think that the MCVs of the base relation might
> > still be applicable to the joinrel? It's certainly easy to think of
> > counterexamples, but it might be a good approximation more often
than
> > not.
>
> It's equivalent to our assumption that distributions of values in
> columns in the same table are independent. Making that assumption in
> this case would probably result in occasional dramatic speed
> improvements similar to the ones we've seen in less complex joins,
> offset by just-as-occasional dramatic slowdowns of similar magnitude.
In
> other words, it will increase the variance of our results.
>
> - Josh

There is almost zero penalty for selecting incorrect MCV tuples to
buffer in memory. Since the number of MCVs is approximately 100, the
"overhead" is keeping these 100 tuples in memory where they *might* not
be MCVs. The cost is the little extra memory and the checking of the
MCVs which is very fast.

On the other hand, the benefit is potentially tremendous if the MCV is
very common in the probe relation. Every probe tuple that matches the
MCV tuple in memory does not have to be written to disk. The potential
speedup is directly proportional to the skew. The more skew the more
benefit.

An analogy is with a page buffering system where one goal is to keep
frequently used pages in the buffer. Essentially the goal of this patch
is to "pin in memory" the tuples that the join believes will match with
the most tuples on the probe side. This reduces I/Os by making more
probe relation tuples match during the first read of the probe relation.
Regular hash join has no way to guarantee frequently matched build
tuples remain memory-resident.

The particular join with Customer, Orders, LineItem, and Part is a
reasonable test case. There may be two explanations for the results.
(I am running tests for this query currently.) First, the time to
generate the tuples (select *) may be dominating the query time.
Second, as mentioned by Bryce, I expect the issue is that only the join
with Customer and Orders exploited the patch. Customer has some skew
(but not dramatic) so there would be some speedup.

However, the join with Part and LineItem *should* show a benefit but may
not because of a limitation of the patch implementation (not the idea).
The MCV optimization is only enabled currently when the probe side is a
sequential scan. This limitation is due to our current inability to
determine a stats tuple of the join attribute on the probe side for
other operators. (This should be possible - help please?).

Even if this stats tuple is on the base relation and may not exactly
reflect the distribution of the intermediate relation on the probe side,
it still could be very good. Even if it is not, once again the cost is
negligible.

In summary, the patch will improve performance of any multi-batch hash
join with skew. It is useful right now when the probe relation has skew
and is accessed using a sequential scan. It would be useful in even
more situations if the code was modified to determine the stats for the
join attribute of the probe relation in all cases (even when the probe
relation is produced by another operator).

--
Dr. Ramon Lawrence
Assistant Professor, Department of Computer Science, University of
British Columbia Okanagan
E-mail: ramon(dot)lawrence(at)ubc(dot)ca