Horton

Thread

Commits

  1. Consider explicit incremental sort for Append and MergeAppend

  1. Consider explicit incremental sort for Append and MergeAppend

    Richard Guo <guofenglinux@gmail.com> — 2025-05-12T09:29:49Z

    For ordered Append or MergeAppend, it seems that incremental sort is
currently not considered when injecting an explicit sort into subpaths
that are not sufficiently ordered.  For instance:

set enable_seqscan to off;

explain (costs off)
select hundred as x, two as y from tenk1
union all
select thousand as x, tenthous as y from tenk1
order by x, y;
                            QUERY PLAN
-------------------------------------------------------------------
 Merge Append
   Sort Key: tenk1.hundred, tenk1.two
   ->  Sort
         Sort Key: tenk1.hundred, tenk1.two
         ->  Index Scan using tenk1_hundred on tenk1
   ->  Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
(6 rows)

Similar to what we do in 828e94c9d, I think we can also consider using
explicit incremental sort for ordered Append or MergeAppend.  Here is
a patch doing that.  With this patch, the plan above changes to:

                            QUERY PLAN
-------------------------------------------------------------------
 Merge Append
   Sort Key: tenk1.hundred, tenk1.two
   ->  Incremental Sort
         Sort Key: tenk1.hundred, tenk1.two
         Presorted Key: tenk1.hundred
         ->  Index Scan using tenk1_hundred on tenk1
   ->  Index Only Scan using tenk1_thous_tenthous on tenk1 tenk1_1
(7 rows)

This targets v19.

Thanks
Richard

  2. Re: Consider explicit incremental sort for Append and MergeAppend

    Andrei Lepikhov <lepihov@gmail.com> — 2025-05-15T13:03:36Z

    On 12/5/2025 11:29, Richard Guo wrote:
> For ordered Append or MergeAppend, it seems that incremental sort is
> currently not considered when injecting an explicit sort into subpaths
> that are not sufficiently ordered.  For instance:
Thanks for doing this job.
I have reviewed your patch and want to put here some thoughts:
0. The patch looks simple enough to be safe. I passed through the code 
and found no issues except comments (see thought No.1). I will be okay 
if you commit it.
1. I'm not very happy with the fact that it strengthens the cost_append 
connection with create_append_plan. At least, there should be 
cross-reference comments to let developers know if they change something 
inside one of these functions.
2. IncrementalSort is not always more effective - it depends on the 
column's number of groups. In my experience, a non-cost-based decision 
one day meets the problematic case, and the people who stick with it are 
much more confused than in the case when planner decision connected to 
the costings - they trust the cost model or the cost model tuned by GUCs.
3. The functions label_incrementalsort_with_costsize and 
label_sort_with_costsize are not ideal architectural decisions. 
Attempting to improve sort / incremental sort cost functions, I am 
always stuck in the absence of some necessary data from the sorting path 
and RelOptInfo at this stage.

As an alternative, you may check the approach of [1], where we decide 
how to adjust a subpath to MergeAppend needs inside 
generate_orderedappend_paths using a cost-based approach.

Also, would you have a chance to look into the [1,2]? It seems like a 
further improvement, bringing a bit closer optimality of appended path 
choice to single-table scan choice.

[1] 
https://www.postgresql.org/message-id/flat/25d6a2cd161673d51373b7e07e6d9dd6%40postgrespro.ru
[2] 
https://www.postgresql.org/message-id/f0206ef2-6b5a-4d07-8770-cfa7cd30f685@gmail.com

-- 
regards, Andrei Lepikhov

  3. Re: Consider explicit incremental sort for Append and MergeAppend

    Robert Haas <robertmhaas@gmail.com> — 2025-05-19T13:21:07Z

    On Thu, May 15, 2025 at 9:03 AM Andrei Lepikhov <lepihov@gmail.com> wrote:
> 2. IncrementalSort is not always more effective - it depends on the
> column's number of groups. In my experience, a non-cost-based decision
> one day meets the problematic case, and the people who stick with it are
> much more confused than in the case when planner decision connected to
> the costings - they trust the cost model or the cost model tuned by GUCs.

I wonder if this could be fixed in nodeIncrementalSort.c. I think it's
a problem to rely on planner estimates because planner estimates of
the # of groups are quite unreliable. But at runtime, we can notice
whether the groups are small or large and adjust the algorithm
accordingly. In fact, it looks like we already have some logic for
that:

/*
 * Sorting many small groups with tuplesort is inefficient. In order to
 * cope with this problem we don't start a new group until the current one
 * contains at least DEFAULT_MIN_GROUP_SIZE tuples (unfortunately this also
 * means we can't assume small groups of tuples all have the same prefix keys.)
 * When we have a bound that's less than DEFAULT_MIN_GROUP_SIZE we start looking
 * for the new group as soon as we've met our bound to avoid fetching more
 * tuples than we absolutely have to fetch.
 */
#define DEFAULT_MIN_GROUP_SIZE 32

But maybe this logic needs to be further refined somehow. I can't
shake the feeling that it's going to be really hard to have every
place that uses incremental sort decide whether to use an incremental
sort or a regular sort -- we should try to get to a place where it's
safe to use an incremental sort when it's possible without worrying
that it might actually be slower.

Or maybe that's not possible for some reason, but it is not clear to
me what that reason might be.

-- 
Robert Haas
EDB: http://www.enterprisedb.com

  4. Re: Consider explicit incremental sort for Append and MergeAppend

    Richard Guo <guofenglinux@gmail.com> — 2025-05-22T09:07:22Z

    On Mon, May 19, 2025 at 10:21 PM Robert Haas <robertmhaas@gmail.com> wrote:
> On Thu, May 15, 2025 at 9:03 AM Andrei Lepikhov <lepihov@gmail.com> wrote:
> > 2. IncrementalSort is not always more effective - it depends on the
> > column's number of groups. In my experience, a non-cost-based decision
> > one day meets the problematic case, and the people who stick with it are
> > much more confused than in the case when planner decision connected to
> > the costings - they trust the cost model or the cost model tuned by GUCs.

> I wonder if this could be fixed in nodeIncrementalSort.c. I think it's
> a problem to rely on planner estimates because planner estimates of
> the # of groups are quite unreliable. But at runtime, we can notice
> whether the groups are small or large and adjust the algorithm
> accordingly. In fact, it looks like we already have some logic for
> that:
>
> /*
>  * Sorting many small groups with tuplesort is inefficient. In order to
>  * cope with this problem we don't start a new group until the current one
>  * contains at least DEFAULT_MIN_GROUP_SIZE tuples (unfortunately this also
>  * means we can't assume small groups of tuples all have the same prefix keys.)
>  * When we have a bound that's less than DEFAULT_MIN_GROUP_SIZE we start looking
>  * for the new group as soon as we've met our bound to avoid fetching more
>  * tuples than we absolutely have to fetch.
>  */
> #define DEFAULT_MIN_GROUP_SIZE 32
>
> But maybe this logic needs to be further refined somehow. I can't
> shake the feeling that it's going to be really hard to have every
> place that uses incremental sort decide whether to use an incremental
> sort or a regular sort -- we should try to get to a place where it's
> safe to use an incremental sort when it's possible without worrying
> that it might actually be slower.

Agreed.  In some cases, we currently don't have the infrastructure to
consider both incremental sort and full sort and compare their costs —
for example, when inserting explicit sorts for mergejoins, or, as in
this case, for Append/MergeAppend.

Besides, I think the planner currently assumes that incremental sort
is always faster than full sort when there are presorted keys, and
this premise has been applied in various parts of the code.  I checked
all the callers of create_incremental_sort_path, and they all follow
the logic that if there are presorted keys, only incremental sort is
considered.

Also, to understand how incremental sort performs in the worst case, I
ran the following test.

create table ab (a int not null, b int not null);
insert into ab select 0,x from generate_Series(1,999000)x union all
select x%1000+1,0 from generate_Series(999001,1000000)x;

create index on ab (a);

vacuum analyze ab;

In this table, group 0 has 999000 rows, and the remaining groups
1-1000 have just 1 row each.

-- incremental sort
explain (analyze, costs off) select * from ab order by a,b;
                                           QUERY PLAN
------------------------------------------------------------------------------------------------
 Incremental Sort (actual time=585.093..714.589 rows=1000000.00 loops=1)
   Sort Key: a, b
   Presorted Key: a
   Full-sort Groups: 33  Sort Method: quicksort  Average Memory: 26kB
Peak Memory: 26kB
   Pre-sorted Groups: 1  Sort Method: external merge  Average Disk:
17680kB  Peak Disk: 17680kB
   Buffers: shared hit=5273, temp read=2210 written=2222
   ->  Index Scan using ab_a_idx on ab (actual time=0.192..330.289
rows=1000000.00 loops=1)
         Index Searches: 1
         Buffers: shared hit=5273
 Planning Time: 0.354 ms
 Execution Time: 759.693 ms
(11 rows)

-- full sort
explain (analyze, costs off) select * from ab order by a,b;
                                         QUERY PLAN
--------------------------------------------------------------------------------------------
 Sort (actual time=570.755..831.825 rows=1000000.00 loops=1)
   Sort Key: a, b
   Sort Method: external merge  Disk: 17704kB
   Buffers: shared hit=5273, temp read=2213 written=2225
   ->  Index Scan using ab_a_idx on ab (actual time=0.187..327.701
rows=1000000.00 loops=1)
         Index Searches: 1
         Buffers: shared hit=5273
 Planning Time: 0.304 ms
 Execution Time: 877.112 ms
(9 rows)

So with the same subpath, incremental sort still outperforms full sort
even if there is a big skew in the number of rows per pre-sorted group
(which is a bit surprising to me).

So, I think it's generally safe to use incremental sort whenever
possible.  There might be some corner cases where incremental sort is
slower than full sort, and I think it would be best to address those
in nodeIncrementalSort.c, as Robert suggested.

Thanks
Richard

  5. Re: Consider explicit incremental sort for Append and MergeAppend

    Richard Guo <guofenglinux@gmail.com> — 2025-07-07T07:37:54Z

    On Thu, May 22, 2025 at 6:07 PM Richard Guo <guofenglinux@gmail.com> wrote:
> So, I think it's generally safe to use incremental sort whenever
> possible.  There might be some corner cases where incremental sort is
> slower than full sort, and I think it would be best to address those
> in nodeIncrementalSort.c, as Robert suggested.

Here's the latest rebase.  I'm planning to push it soon, barring any
objections.

Thanks
Richard

  6. Re: Consider explicit incremental sort for Append and MergeAppend

    Andrei Lepikhov <lepihov@gmail.com> — 2025-07-07T13:38:58Z

    On 19/5/2025 15:21, Robert Haas wrote:
> On Thu, May 15, 2025 at 9:03 AM Andrei Lepikhov <lepihov@gmail.com> wrote:
>> 2. IncrementalSort is not always more effective - it depends on the
>> column's number of groups. In my experience, a non-cost-based decision
>> one day meets the problematic case, and the people who stick with it are
>> much more confused than in the case when planner decision connected to
>> the costings - they trust the cost model or the cost model tuned by GUCs.
> 
> I wonder if this could be fixed in nodeIncrementalSort.c. I think it's
> a problem to rely on planner estimates because planner estimates of
> the # of groups are quite unreliable. But at runtime, we can notice
> whether the groups are small or large and adjust the algorithm
> accordingly. In fact, it looks like we already have some logic for
> that:
Yes, the cost estimation issue is the source of my concern. Postgres 
estimation of the number of groups is still not ideal [1]. The cost sort 
model doesn't take into account the number of columns [2] - perhaps 
something else.
Therefore, if IncrementalSort performs worse in some cases, this change 
may result in an increase in user reports.

However, comparing Sort and IncrementalSort (see the attachment), I 
recall that IncrementalSort surpasses plain Sort in both corner cases: 
tiny groups (beating Sort in terms of memory consumption and smaller 
sorting sets) and massive groups (abbreviated keys reduce the number of 
compared columns). And it is not easy to invent the worst case where the 
Sort node wins.

The only aspect I can't stop thinking about is the cost balance: 
sometimes the planner prefers Sort+SeqScan to IncrementalSort+IndexScan 
(See explains in the attachment). A non-cost-based choice of 
IncrementalSort may result in an Append path with a higher cost, which 
can displace it from the path list and lead to another, less effective 
choice, such as a less effective IndexScan.
However, I can't support this opinion with any real examples.

In toto, IMO it makes sense to commit this feature now and see how it 
behaves.

[1] 
https://www.postgresql.org/message-id/ba0edc53-4b1f-4c67-92d1-29aeddb36a18@gmail.com
[2] 
https://www.postgresql.org/message-id/8742aaa8-9519-4a1f-91bd-364aec65f5cf%40gmail.com


-- 
regards, Andrei Lepikhov