Re: 回复: An implementation of multi-key sort

On Fri, Jul 26, 2024 at 6:18 PM Yao Wang <yao-yw(dot)wang(at)broadcom(dot)com> wrote:

> 2. Should we update optimizer to take in account statistic
> (pg_statistic->stadistinct) and choose mksort/qsort accordingly?

> According to the result, the choosing mechanism in optimizer
> almost eliminated all regressions. Please note that even when mksort is
> disabled (i.e. qsort was performed twice actually), there are still
> "regressions" which are usually less than 5% and should be accounted
> to kinda error range.

This is kind of an understatement. To be clear, I see mostly ~1%,
which I take to be in the noise level. If it were commonly 5%
regression, that'd be cause for concern. If actual noise were 5%, the
testing methodology is not strict enough.

> I am still hesitating about putting the code to final version because
> there are a number of concerns:
>
> a. for sort keys without a real table, stadistinct is unavailable.
> b. stadistinct may not be accurate as mentioned.
> c. the formula I used may not be able to cover all possible cases.
>
> On the other hand, the worst result may be just 5% regression. So the
> side effects may not be so serious?

FWIW, I share these concerns as well. I don't believe this proves a
bound on the worst result, since the test is using ideal well-behaved
data with no filter. The worst result is when the estimates are wrong,
so real world use could easily be back to 10-20% regression, which is
not acceptable. I believe this is what Robert and Tomas were warning
about.

It'd be good to understand what causes the differences, whether better
or worse. Some initial thoughts:

- If the first key is unique, then I would hope multikey would be no
different then a standard sort.

- If the first key commonly ties, and other following keys tie also,
those later comparisons are a waste. In that case, it's not hard to
imagine that partitioning on only one key at a time might be fast.

- If the first key commonly ties, but the second key is closer to
unique, I'm not sure which way is better. Have we tested this case?

- If we actually only have one sort key, a multi-key sort with a
single depth should ideally have no significant performance difference
than standard sort. That seems like a good sanity check. Has this been
tried?

- For the biggest benefit/regression cases, it'd be good to know what
changed at the hardware level. # comparsisons? # swaps? # cache
misses? # branch mispredicts?

Looking at the code a bit, I have some questions and see some
architectural issues. My thoughts below have a bunch of brainstorms so
should be taken with a large grain of salt:

1. The new single-use abstraction for the btree tid tiebreak seems
awkward. In standard sort, all that knowledge was confined to btree's
full comparetup function. Now it's spread out, and general code has to
worry about "duplicated" tuples. The passed-down isNull seems only
needed for this? (Quick idea: It seems we could pass a start-depth and
max-depth to some "comparetup_mk", which would be very similar to
current "comparetup + comparetup_tiebreak". The btree function would
have to know that a depth greater than the last sortkey is a signal to
do the tid comparison. And if start-depth and max-depth are the same,
that means comparing at a single depth. That might simplify the code
elsewhere because there is no need for a separate getDatum function.)

2. I don't understand why the pre-ordered check sometimes tolerates
duplicates and sometimes doesn't.

3. "tiebreak" paths and terminology is already somewhat awkward for
standard sort (my fault), but seems really out of place in multikey
sort. It already has a general concept of "depth", so that should be
used in fullest generality.

3A. Random thought: I wonder if the shortcut (and abbreviated?)
comparisons could be thought of as having their own depth < 0. If it's
worth it to postpone later keys, maybe it's worth it to postpone the
full comparison for the first key as well? I could be wrong, though.

3B. Side note: I've long wanted to try separating all NULL first keys
to a separate array, so we can remove all those branches for NULL
ordering and reduce SortTuple to 16 bytes. That might be easier to
code if we could simply specify "start_depth = 1" at the top level for
that.

4. Trying to stuff all our optimized comparators in the same path was
a heroic effort, but it's quite messy and seems pretty bad for the
instruction cache and branch predictor. I don't think we need yet
another template, but some of these branches should be taken as we
recurse into a partition to keep them out of the hot path.

5.
+ /*
+ * When the count < 16 and no need to handle duplicated tuples, use
+ * bubble sort.
+ *
+ * Use 16 instead of 7 which is used in standard qsort, because mk qsort
+ * need more cost to maintain more complex state.

Note: 7 isn't ideal for standard sort either, and should probably be
at least 10 (at least for single-key sorts). If one implementation's
parameter is more ideal than the other, it obscures what the true
trade-offs are. 16 happens to be a power of two -- how many different
values did you test? (And isn't this the same as our insertion sort,
not bubble sort?).