Re: a large LIMIT makes some sorts slower

Hi,

> On Jul 28, 2026, at 10:09, Jacob Brazeal <jacob(dot)brazeal(at)gmail(dot)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