Re: Quickselect instead of a heap for ORDER BY ... LIMIT N large bounded sorts

On Fri, Oct 23, 2026 at 9:57 PM Greg Burd <greg(at)burd(dot)me> wrote:

Quick thoughts:

> int8, reversed 10,000 1,023 485 0.47x
> random order, any key 100 364-541 368-548 0.98-1.01x

Do we get any improvement with smaller numbers than 10k?

> What I'd like to know before going further:
>
> 1. Is it reasonable to keep two strategies here, or should it be
> quickselect only and accept the loss at LIMIT 1-4?

It's not reasonable IMO. If there are enough advantages to a new
method, we should just switch. If not, then we won't. I do suspect the
regression at small LIMITs is because N*2 is not enough room to
accumulate enough tuples to make it worthwhile. Just a hunch, but
maybe a floor would help.

Also, with quickselect, it seems like an easy prerequisite to Andres'
idea of copying the survivors into a new context instead of
individually freeing the losers? That would allow a bump context, see
here:

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

> 2. EXPLAIN says "top-N heapsort" whichever method ran. Add a method,
> or reuse the name? A new one touches TuplesortMethod,
> NUM_TUPLESORTMETHODS and explain.c.

Polish comes last.

> Appendix:

> When finished, I asked the LLM to outline the set of things influencing
> this approach I got this impressive list of resources. I've not read
> everything listed myself,

Well, if you can't be bothered read them, why should I?

--
John Naylor
Amazon Web Services