Re: a large LIMIT makes some sorts slower

On Tue, Jul 28, 2026 at 9:09 AM Jacob Brazeal <jacob(dot)brazeal(at)gmail(dot)com> wrote:
> The difference is the INT_MAX / 2 check in tuplesort_set_bound(), which comes from the original abbreviated-key design.

Actually, the INT_MAX / 2 came in with bounded sorts in commit
d26559dbf35 in 2007 (git blame is your friend).

On Sun, Aug 2, 2026 at 6:09 PM Tatsuya Kawata
<kawatatatsuya0913(at)gmail(dot)com> wrote:
> > 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.

A couple things to note:
1) LIMIT or OFFSET+LIMIT are small for vast majority of bounded sorts.
2) All examples I've seen in this thread use text with C collation,
which is trivial to abbreviate. Other collations (aside from the
built-in fast collation) will use strxfrm or the ICU equivalent.

(Also for future reference, we cannot draw performance conclusions
with assert builds.)

I'm skeptical that any of these proposals will benefit common cases.
v1 really only helps the case where the total input is not much bigger
than the bound, and for small inputs the sort is already cheap. v2
does a full comparison against the root key, as in master, and we
expect that most tuples will be discarded then, so it makes little
difference. If not discarded immediately, they may only undergo a
small number of comparisons later. In short, the reasoning from when
abbreviation entered in 2014 still seems sound, and I haven't seen
evidence to the contrary for common inputs.

While refreshing my memory on this topic, I was reminded of this from
a couple years ago:

https://www.postgresql.org/message-id/20230211202959.lkhrxiy7awsyctef%40awork3.anarazel.de

Andres mentioned "The biggest source of individual pfree()s in the
bounded case is that we
unconditionally copy the tuple into base->tuplecontext during puttuple. Even
though quite likely we'll immediately free it in the "case TSS_BOUNDED" block."

The last few paragraphs of that message have some ideas for improving
memory use for bounded sorts. One or more of those might be worth
looking into.

--
John Naylor
Amazon Web Services