Re: a large LIMIT makes some sorts slower

Hi,

> This can add work when bounded heapsort is used: abbreviated keys are
> generated and then restored at the heap transition. On the report's
> three-million-row table, LIMIT 1499999 reaches the 2 * bound + 1
> threshold at tuple 2999999, so almost all keys are restored. Across 100
> runs per version, median time increased from 2.840s to 2.888s, or about
> 1.7%.

I did some quick performance testing on this patch. What caught my
attention is a case Yan also reported.

It's the case where the restore cost from REMOVEABBREV before switching
to the bounded heap is at its worst (bound close to half the total row
count). Yan reported a median regression of about 1.7% for this case,
but in my environment (WSL2 / Ubuntu 22.04.4 LTS, gcc 11.4.0, 4 cores,
--enable-cassert --enable-debug build), testing under Jacob's
conditions, I saw about 12.7s before the patch vs. about 16.0s after,
a ~26% regression. That's not a small difference.

I dug into it a bit further. This is still exploratory, but I'm attaching
a short writeup and a sample patch in case it's useful.

## First attempt

Looking at the original comment in tuplesort_set_bound() ("Bounded
sorts are not an effective target for abbreviated key optimization"),
I questioned the premise that abbreviation shouldn't be used for a
bounded heap at all. The comparison make_bounded_heap() uses
(COMPARETUP) goes through comparetup_heap(), which already has a lazy
tie-break (comparetup_heap_tiebreak()) that only fetches the real
value when two abbreviated keys tie. Given that, it seemed like we
shouldn't need to eagerly restore/disable abbreviation for every
collected tuple when switching to the bounded heap -- the existing
lazy tie-break should handle it correctly on its own. So as a first
attempt, I simply removed that restore/disable block from
make_bounded_heap() entirely. That brought the case above down to
about 5.7s, even faster than before the patch.

However, when the bound is much smaller than the total row count -- an
ordinary pagination case (something like LIMIT 1000) -- with a very
large total row count, it actually regressed (20M rows, LIMIT 1000:
about 15.1s with the patch vs. about 18.4s with the naive removal,
a ~22% regression).

It looks like tuples arriving after the switch to the heap are each
compared against the heap root once and mostly discarded right there,
so the premise behind abbreviation -- pay the conversion cost once and
reuse it across many comparisons -- doesn't hold, and we end up
dutifully converting tuples that never pay for themselves.

## A revised second attempt

So instead of eagerly restoring/disabling everything at switch time, I
changed the design to separately monitor whether abbreviation is
actually paying for itself among the tuples arriving after the switch,
and only give up on it once it stops paying off. After the switch,
each new tuple is compared against the heap root exactly once, and
most are discarded right there. Abbreviation only pays for itself by
paying the conversion cost once and reusing it across many
comparisons, so there's no point paying that cost for a tuple that's
discarded after a single comparison.

- Count the number of arrivals each time a new tuple comes in
- Separately count how many actually replaced the heap root (i.e.
survived as one of the top N)
- Every time the arrival count reaches a threshold (starting at 1000,
doubling each time), check the survival rate, and abandon
abbreviation if it's below 5%

At this point the heap only ever holds `bound` tuples, so the restore
cost when abandoning abbreviation stays small regardless of the total
row count.

Re-measuring:

| | patch applied | naive
removal | revised |
| ------------------------------------------- | -------------- |
-------------------- | -------------------------- |
| bound ~= half the rows (3M rows) | ~16.0s | ~5.7s
| ~6.0s (unchanged) |
| bound ~= half the rows (6M rows, 2x scale) | ~34.9s | -
| ~15.0s (unchanged, similar ratio) |
| small bound, 20M rows (LIMIT 1000) | ~15.1s | ~18.4s
(regression) | ~15.0s (no regression) |

Out of the 20M rows, abbreviation's cost is only paid for the first
~130k or so; the remaining ~19.87M pay no cost, same as with the patch
applied. In the bound ~= half-the-rows case, almost no new tuples
arrive after the switch, so we essentially never get to the point
of giving up on abbreviation, and abbreviation stays enabled the whole time.

Sample patch attached.
Looking forward to any thoughts.

Regards,
Tatsuya Kawata