a large LIMIT makes some sorts slower

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.

The difference is the INT_MAX / 2 check in tuplesort_set_bound(), which comes
from the original abbreviated-key design. The 2014 discussion says
abbreviation was disabled for bounded sorts because it generally did not
pay [0], and a later message describes it as unsuitable for top-N heapsorts.
The problem here is that it is applied when the bound is only a hint,
before tuplesort knows which algorithm it will use.

I did not find a prior report of this large-bound case, where the sort
remains a quicksort but has already lost abbreviation.

[0]
https://www.postgresql.org/message-id/CAM3SWZQ2xazBo8YdMKVhY1DgqyL0ynvYbfs6zD%3DQMkxWH_YDFg%40mail.gmail.com

Best,
Jacob Brazeal