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

On Wednesday, October 28th, 2026 at 10:11 AM, John Naylor <johncnaylorls(at)gmail(dot)com> wrote:

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

Hey John, thanks for giving this idea some thought.

>
> > 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?

Good question, I'll measure and find out.

>
> > 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.

That was my thought too, one "ring" to rule them all. I'll dig into your
hunch and measure that too.

> 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

Interesting idea, I'll dig into that and see how they might mesh.

> > 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.

Yes, yes. :)

1. make it work
2. make it right
3. make it fast (and polished)

> > 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?

I didn't say I wasn't /going/ to read it all... but yeah, I get your point.

> --
> John Naylor
> Amazon Web Services

best.

-greg