Re: Consider explicit incremental sort for Append and MergeAppend

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