Re: Support run-time partition pruning for hash join

On Fri, Aug 25, 2023 at 11:03 AM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:

> I'd suggest writing some cost which costs an execution of run-time
> pruning. With LIST and RANGE you probably want something like
> cpu_operator_cost * LOG2(nparts) once for each hashed tuple to account
> for the binary search over the sorted datum array. For HASH
> partitions, something like cpu_operator_cost * npartcols once for each
> hashed tuple.
>
> You'll need to then come up with some counter costs to subtract from
> the Append/MergeAppend. This is tricky, as discussed. Just come up
> with something crude for now.
>
> To start with, it could just be as crude as:
>
> total_costs *= (Min(expected_outer_rows, n_append_subnodes) /
> n_append_subnodes);
>
> i.e assume that every outer joined row will require exactly 1 new
> partition up to the total number of partitions. That's pretty much
> worst-case, but it'll at least allow the optimisation to work for
> cases like where the hash table is expected to contain just a tiny
> number of rows (fewer than the number of partitions)
>
> To make it better, you might want to look at join selectivity
> estimation and see if you can find something there to influence
> something better.

I have a go at writing some costing codes according to your suggestion.
That's compute_partprune_cost() in the v2 patch.

For the hash side, this function computes the pruning cost as
cpu_operator_cost * LOG2(nparts) * inner_rows for LIST and RANGE, and
cpu_operator_cost * nparts * inner_rows for HASH.

For the Append/MergeAppend side, this function first estimates the size
of outer side that matches, using the same idea as we estimate the
joinrel size for JOIN_SEMI. Then it assumes that each outer joined row
occupies one new partition (the worst case) and computes how much cost
can be saved from partition pruning.

If the cost saved from the Append/MergeAppend side is larger than the
pruning cost from the Hash side, then we say that partition pruning is a
win.

Note that this costing logic runs for each Append-Hash pair, so it copes
with the case where we have multiple join levels.

With this costing logic added, I performed the same performance
comparisons of the worst case as in [1], and here is what I got.

tuples unpatched patched
10000 44.66 44.37 -0.006493506
20000 52.41 52.29 -0.002289639
30000 61.11 61.12 +0.000163639
40000 67.87 68.24 +0.005451599
50000 74.51 74.75 +0.003221044
60000 82.3 81.55 -0.009113001
70000 87.16 86.98 -0.002065168
80000 93.49 93.89 +0.004278532
90000 101.52 100.83 -0.00679669
100000 108.34 108.56 +0.002030644

So the costing logic successfully avoids performing the partition
pruning in the worst case.

I also tested the cases where partition pruning is possible with
different sizes of the hash side.

tuples unpatched patched
100 36.86 2.4 -0.934888768
200 35.87 2.37 -0.933928074
300 35.95 2.55 -0.92906815
400 36.4 2.63 -0.927747253
500 36.39 2.85 -0.921681781
600 36.32 2.97 -0.918226872
700 36.6 3.23 -0.911748634
800 36.88 3.44 -0.906724512
900 37.02 3.46 -0.906537007
1000 37.25 37.21 -0.001073826

The first 9 rows show that the costing logic allows the partition
pruning to be performed and the pruning turns out to be a big win. The
last row shows that the partition pruning is disallowed by the costing
logic because it thinks no partition can be pruned (we have 1000
partitions in total).

So it seems that the new costing logic is quite crude and tends to be
very conservative, but it can help avoid the large overhead in the worst
cases. I think this might be a good start to push this patch forward.

Any thoughts or comments?

[1]
https://www.postgresql.org/message-id/CAMbWs49%2Bp6hBxXJHFiSwOtPCSkAHwhJj3hTpCR_pmMiUUVLZ1Q%40mail.gmail.com

Thanks
Richard