Обсуждение: [Patch] Build the heap more efficient in tuplesort.c

Hi hackers,

Now we build the heap by using tuplesort_heap_insert(), which has a sift-up every call.

To make it more efficient, I want to add tuplesort_heap_insert_unordered() and tuplesort_heap_build()
just like binaryheap_add_unordered() and binaryheap_build().

Thoughts?

--
Regards,
ChangAo Chen

On Sun, 30 Nov 2025 at 22:36, cca5507 <cca5507@qq.com> wrote:
> Now we build the heap by using tuplesort_heap_insert(), which has a sift-up every call.
>
> To make it more efficient, I want to add tuplesort_heap_insert_unordered() and tuplesort_heap_build()
> just like binaryheap_add_unordered() and binaryheap_build().
>
> Thoughts?

For performance patches, you should include example workloads that
your patch speeds up. Include benchmark results with and without your
patch. Demonstrate you've not regressed any other workloads at the
expense of the ones you intend to speed up.

It's not up to reviewers to do this for you.

David

Hi,

> For performance patches, you should include example workloads that
> your patch speeds up. Include benchmark results with and without your
> patch. Demonstrate you've not regressed any other workloads at the
> expense of the ones you intend to speed up.
>
> It's not up to reviewers to do this for you.

Sry and thank you for pointing it out.

# Test
I test it by adding log to record the duration of make_bounded_heap().

## Sorted data
SET work_mem = '1GB';
SET max_parallel_workers_per_gather = 0;
CREATE UNLOGGED TABLE t1 AS SELECT i AS a FROM generate_series(1, 100000000) i;
create extension if not exists pg_prewarm;
select pg_prewarm('t1');

EXPLAIN ANALYZE select * from t1 order by a limit 100;
EXPLAIN ANALYZE select * from t1 order by a limit 1000;
EXPLAIN ANALYZE select * from t1 order by a limit 10000;
EXPLAIN ANALYZE select * from t1 order by a limit 100000;
EXPLAIN ANALYZE select * from t1 order by a limit 1000000;
EXPLAIN ANALYZE select * from t1 order by a limit 10000000;
drop table t1;

Raw log:
LOG:  make_bounded_heap(HEAD): tupcount: 201, duration: 0.006 ms
LOG:  make_bounded_heap(HEAD): tupcount: 2001, duration: 0.092 ms
LOG:  make_bounded_heap(HEAD): tupcount: 20001, duration: 0.701 ms
LOG:  make_bounded_heap(HEAD): tupcount: 200001, duration: 7.219 ms
LOG:  make_bounded_heap(HEAD): tupcount: 2000001, duration: 71.673 ms
LOG:  make_bounded_heap(HEAD): tupcount: 20000001, duration: 681.077 ms

LOG:  make_bounded_heap(PATCH): tupcount: 201, duration: 0.002 ms
LOG:  make_bounded_heap(PATCH): tupcount: 2001, duration: 0.022 ms
LOG:  make_bounded_heap(PATCH): tupcount: 20001, duration: 0.201 ms
LOG:  make_bounded_heap(PATCH): tupcount: 200001, duration: 1.607 ms
LOG:  make_bounded_heap(PATCH): tupcount: 2000001, duration: 13.547 ms
LOG:  make_bounded_heap(PATCH): tupcount: 20000001, duration: 164.527 ms

                     100                  1000              10000           100000         1000000           10000000
HEAD        0.006 ms        0.092 ms        0.701 ms        7.219 ms        71.673 ms        681.077 ms
PATCH      0.002 ms        0.022 ms        0.201 ms        1.607 ms        13.547 ms        164.527 ms

## Random data
SET work_mem = '1GB';
SET max_parallel_workers_per_gather = 0;
CREATE UNLOGGED TABLE t2 AS SELECT floor(random() * 1000000)::int AS a FROM generate_series(1, 100000000);
create extension if not exists pg_prewarm;
select pg_prewarm('t2');

EXPLAIN ANALYZE select * from t2 order by a limit 100;
EXPLAIN ANALYZE select * from t2 order by a limit 1000;
EXPLAIN ANALYZE select * from t2 order by a limit 10000;
EXPLAIN ANALYZE select * from t2 order by a limit 100000;
EXPLAIN ANALYZE select * from t2 order by a limit 1000000;
EXPLAIN ANALYZE select * from t2 order by a limit 10000000;
drop table t2;

Raw log:
LOG:  make_bounded_heap(HEAD): tupcount: 201, duration: 0.016 ms
LOG:  make_bounded_heap(HEAD): tupcount: 2001, duration: 0.096 ms
LOG:  make_bounded_heap(HEAD): tupcount: 20001, duration: 0.976 ms
LOG:  make_bounded_heap(HEAD): tupcount: 200001, duration: 13.395 ms
LOG:  make_bounded_heap(HEAD): tupcount: 2000001, duration: 233.741 ms
LOG:  make_bounded_heap(HEAD): tupcount: 20000001, duration: 4681.966 ms

LOG:  make_bounded_heap(PATCH): tupcount: 201, duration: 0.009 ms
LOG:  make_bounded_heap(PATCH): tupcount: 2001, duration: 0.129 ms
LOG:  make_bounded_heap(PATCH): tupcount: 20001, duration: 2.048 ms
LOG:  make_bounded_heap(PATCH): tupcount: 200001, duration: 16.736 ms
LOG:  make_bounded_heap(PATCH): tupcount: 2000001, duration: 204.125 ms
LOG:  make_bounded_heap(PATCH): tupcount: 20000001, duration: 4753.490 ms

                     100                  1000              10000           100000         1000000           10000000
HEAD        0.016 ms        0.096 ms        0.976 ms       13.395 ms     233.741 ms      4681.966 ms
PATCH      0.009 ms        0.129 ms        2.048 ms       16.736 ms     204.125 ms      4753.490 ms

The patch seems to worse than HEAD when handling random data.

--
Regards,
ChangAo Chen

Hi,

Generally speaking, build the heap by tuplesort_heap_build() is O(n) while tuplesort_heap_insert() is
O(n log n), so the former is better.

I'm not sure why tuplesort_heap_build() is worse than tuplesort_heap_insert() when handling random
data sometimes, maybe my test method is wrong? Any ideas?

The v2-0001 refactor some code, mark some function as always inline and reduce some useless copy
of SortTuple.

--
Regards,
ChangAo Chen