a large LIMIT makes some sorts slower

Hi,

On Jul 28, 2026, at 10:09, Jacob Brazeal <jacob.brazeal@gmail.com> wrote:

Hi hackers,

I found that adding a large LIMIT to a text sort can make the query substantially slower, even though the executor ultimately uses an ordinary quicksort rather than a bounded top-N sort.

A reproducer is:

CREATE TABLE sort_test AS
SELECT md5(g::text) AS s
FROM generate_series(1, 3000000) g;

ANALYZE sort_test;

SET work_mem = '1GB';
SET max_parallel_workers_per_gather = 0;
SET jit = off;

Then compare:

EXPLAIN (ANALYZE, COSTS OFF)
SELECT s
FROM sort_test
ORDER BY s COLLATE "C"
LIMIT 1073741823;

with:

EXPLAIN (ANALYZE, COSTS OFF)
SELECT s
FROM sort_test
ORDER BY s COLLATE "C"
LIMIT 1073741824;

Both queries return all 3,000,000 rows, use quicksort, and the same amount of memory while sorting.

On my build, however, the first query took about 7 seconds and the second about 2.5 seconds.

Thanks for the report. I reproduced the problem on a Mac M4 Max. In
repeated runs, LIMIT 1073741823 and LIMIT 1073741824 took 1.548s and
0.591s, respectively.

The problem here is that it is applied when the bound is only a hint, before tuplesort knows which algorithm it will use.

Agreed. The patch moves abbreviation shutdown to make_bounded_heap(),
when tuplesort actually switches to bounded heapsort. It restores any
abbreviated keys, switches to the full comparator, and then builds the
bounded heap.

With the patch, the two queries took 0.585s and 0.583s.

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 not add a regression test because there is no SQL-visible change.
Existing tuplesort coverage exercises this path, and make check passes.

I am unsure whether restoration should also be interruptible; the
self-abort restoration is not. One option is to restore, for example,
1024 tuples per batch and call CHECK_FOR_INTERRUPTS() between batches. I
left that out of this patch.

--
Best regards,
Chengpeng Yan

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

Hi Tatsuya,

On Aug 2, 2026, at 19:08, Tatsuya Kawata <kawatatatsuya0913@gmail.com> wrote:

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.

Thank you for digging into this and for sharing both the measurements
and the sample patch. Your analysis is very helpful and gave me another
way to think about the problem.

It made me wonder whether there might be another way to separate
admission from heap maintenance. I tried a small alternative that
retains abbreviated leading keys in the heap, while deferring
abbreviation of each incoming tuple until admission is decided. The
incoming tuple's authoritative leading key is first compared with a
cached authoritative leading key for the heap root. Rejected tuples
never pass through the abbreviation converter; eligible survivors are
abbreviated just before entering the heap.

Two follow-ups remain. For performance robustness, a bounded heap that
retains abbreviated keys should continue evaluating whether abbreviation
remains worthwhile for tuples admitted to the heap. Also, when the
authoritative leading keys compare equal, the current tiebreak path
starts again at the leading key before considering any additional sort
keys. Neither affects the basic idea, but both would need to be
addressed if this direction turns out to be useful.

The attached patch is only intended to illustrate another possible
direction, not to claim that it is the right solution. In the cases I
have tested so far, its results are broadly in line with yours. If the
approach seems reasonable, I would like to work through more concrete
examples, compare both approaches across a wider range of scenarios, and
address the two follow-ups above.

Thanks again for sharing this.

--
Best regards,
Chengpeng Yan