Re: MergeAppend could consider sorting cheapest child path

On 2/6/2025 20:21, Alexander Korotkov wrote:
> I have the following question. I see patch changes some existing
> plans from Sort(Append(...)) to MergeAppend(Sort(), ..., Sort(...)) or
> even Materialize(MergeAppend(Sort(), ..., Sort(...))). This should be
> some problem in cost_sort(). Otherwise, that would mean that Sort
> node doesn't know how to do its job: explicit splitting dataset into
> pieces then merging sorting result appears to be cheaper, but Sort
> node contains merge-sort algorithm inside and it's supposed to be more
> efficient. Could you, please, revise the patch to avoid these
> unwanted changes?
I think, this issue is related to corner-cases of the
compare_path_costs_fuzzily.

Let's glance into one of the problematic queries:
EXPLAIN (COSTS ON)
SELECT c collate "C", count(c) FROM pagg_tab3 GROUP BY c collate "C"
ORDER BY 1;

if you play with the plan, you can find that total_cost of the
Sort->Append path is cheaper:

Sort (cost=2.40..2.41 rows=4 width=40)
-> Append (cost=1.15..2.36 rows=4 width=40)
Merge Append (cost=2.37..2.42 rows=4 width=40)

But the difference is less than fuzz_factor. In this case, Postgres
probes startup_cost, which is obviously less for the MergeAppend strategy.
This is a good decision, and I think it should stay as is.
What can we do here? We might change the test to increase the cost gap.
However, while designing this patch, I skimmed through each broken query
and didn't find a reason to specifically shift to the Sort->Append
strategy, as it tested things that were not dependent on Append or Sort.

To establish a stable foundation for discussion, I conducted simple
tests - see, for example, a couple of queries in the attachment. As I
see it, Sort->Append works faster: in my test bench, it takes 1250ms on
average versus 1430ms, and it also has lower costs - the same for data
with and without massive numbers of duplicates. Playing with sizes of
inputs, I see the same behaviour.

--
regards, Andrei Lepikhov