Re: MergeAppend could consider sorting cheapest child path

On 27/7/2025 00:51, Alexander Korotkov wrote:
> On Tue, Jul 22, 2025 at 2:13 PM Andrei Lepikhov <lepihov@gmail.com 
> I've another idea.  cost_tuplesort() puts 2.0 under logarithm to prefer 
> tuplesort over heapsort.  I think we can adjust cost_gather_merge() and 
> cost_merge_append() to do the same.  0001 patch implements that.  I 
> think the plan changes of 0001 might be reasonable since most cases deal 
> with small rowsets.  One thing concerns me: 0002 still affects one of 
> the postgres_fdw checks.  Could you, please, take a look?
Thanks for the idea!
I analysed your approach a little bit.
Initially, I ran the test script I had created previously [1] and 
discovered that on a large scale (1e6 - 1e7 tuples), the plan still 
defaults to MergeAppend, which deviates from the execution time (7190 ms 
for Sort+Append and 8450 ms for MergeAppend+Sort).

Attempting to find out the reason, I combined all the costs into a 
single formula for each strategy:

MergeAppend+Sort:
total_cost =CO*ntuples*(1+2*log(ntuples)) + Ccput * 0.5 * ntuples+ 
2*CO*N*log(N) + A
Sort+Append:
total_cost = CO*ntuples*(1+2*log(ntuples))+ Ccput * 0.5 * ntuples + A

Terms:
- A - sum of total costs of underlying subtrees
- CO - cpu_operator_cost
- Ccput - cpu_tuple_cost
- N - number of subpaths (streams)

Given the significant gap in total execution time between these 
strategies, I believe it would be reasonable to introduce a coefficient 
to the equation's 'ntuples' variable component that will keep the gap 
between big quicksort and MergeAppend's heapsort out of the fuzzy factor 
gap.

Discovering papers on the value of constant in quicksort [2] and 
heapsort [3], I realised that there is a difference. The constant's 
value varies in a wide range: 1.3-1.5 for quicksort and 2-3 for 
heapsort. Considering that we should change the current cost model as 
little as possible, not to break the balance, we may just increase the 
constant value for the heap sort to maintain a bare minimum gap between 
strategies out of the fuzzy factor. In this case, the merge append 
constant should be around 3.8 - 4.0.

With this minor change, we see a shift in the regression tests. Most of 
these changes were introduced by the new append strategy. Although I 
haven't analysed these changes in depth yet, I believe they are all 
related to the small data sets and should fade out on a larger scale.

See this minor correction in the attachment. postgres_fdw tests are 
stable now.

[1] 
https://github.com/danolivo/conf/blob/main/Scripts/sort-vs-mergeappend-3.sql
[2] https://en.wikipedia.org/wiki/Quicksort?utm_source=chatgpt.com
[2] https://arxiv.org/abs/1504.01459

-- 
regards, Andrei Lepikhov