On Tue, Jun 3, 2025 at 4:23 PM Andrei Lepikhov <lepihov@gmail.com> wrote:
> 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.
I run your tests. For Sort(Append()) case I've got actual
time=811.047..842.473. For MergeAppend case I've got actual time
actual time=723.678..967.004. That looks interesting. At some point
we probably should teach our Sort node to start returning tuple before
finishing the last merge stage.
However, I think costs are not adequate to the timing. Our cost model
predicts that startup cost of MergeAppend is less than startup cost of
Sort(Append()). And that's correct. However, in fast total time of
MergeAppend is bigger than total time of Sort(Append()). The
differences in these two cases are comparable. I think we need to
just our cost_sort() to reflect that.
------
Regards,
Alexander Korotkov
Supabase
