Re: Why don't we consider explicit Incremental Sort?

On Tue, 24 Sept 2024 at 02:01, Tomas Vondra <tomas(at)vondra(dot)me> wrote:
>
> On 9/23/24 05:03, Richard Guo wrote:
> > On Sun, Sep 22, 2024 at 1:38 PM David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
> >> Just looking at the commit message:
> >>
> >>> The rationale is based on the assumption that incremental sort is
> >>> always faster than full sort when there are presorted keys, a premise
> >>> that has been applied in various parts of the code. This assumption
> >>> does not always hold, particularly in cases with a large skew in the
> >>> number of rows within the presorted groups.
> >>
> >> My understanding is that the worst case for incremental sort is the
> >> same as sort, i.e. only 1 presorted group, which is the same effort to
> >> sort. Is there something I'm missing?
> >
> > I was thinking that when there’s a large skew in the number of rows
> > per pre-sorted group, incremental sort might underperform full sort.
> > As mentioned in the comments for cost_incremental_sort, it has to
> > detect the sort groups, plus it needs to perform tuplesort_reset after
> > each group. However, I doubt these factors would have a substantial
> > impact on the performance of incremental sort. So maybe in the worst
> > skewed groups case, incremental sort may still perform similarly to
> > full sort.
> >
> > Another less obvious reason is that in cases of skewed groups, we may
> > significantly underestimate the cost of incremental sort. This could
> > result in choosing a more expensive subpath under the sort. Such as
> > the example in [1], we end up with IndexScan->IncrementalSort rather
> > than SeqScan->FullSort, while the former plan is more expensive to
> > execute. However, this point does not affect this patch, because for
> > a mergejoin, we only consider outerrel's cheapest-total-cost when we
> > assume that an explicit sort atop is needed, i.e., we do not have a
> > chance to select which subpath to use in this case.
> >
> > [1] https://postgr.es/m/CAMbWs49+CXsrgbq0LD1at-5jR=AHHN0YtDy9YvgXAsMfndZe-w@mail.gmail.com
> >
>
> You don't need any skew. Consider this perfectly uniform dataset:
>
> Sort (cost=127757.34..130257.34 rows=1000000 width=8)
> (actual time=186.288..275.813 rows=1000000 loops=1)
> Sort Key: a, b
> Sort Method: external merge Disk: 17704kB
> -> Seq Scan on t (cost=0.00..14425.00 rows=1000000 width=8)
> (actual time=0.005..35.989 rows=1000000 loops=1)
> Planning Time: 0.075 ms
> Execution Time: 301.143 ms
>
> set enable_incremental_sort = on;

> Incremental Sort (cost=1.03..68908.13 rows=1000000 width=8)
> (actual time=0.102..497.143 rows=1000000 loops=1)
> Sort Key: a, b
> Presorted Key: a
> Full-sort Groups: 27039 Sort Method: quicksort
> Average Memory: 25kB Peak Memory: 25kB
> -> Index Scan using t_a_idx on t
> (cost=0.42..37244.25 rows=1000000 width=8)
> (actual time=0.050..376.403 rows=1000000 loops=1)
> Planning Time: 0.057 ms
> Execution Time: 519.301 ms

Ok, let's first look at the total Seq Scan cost of the first EXPLAIN.
14425.00 units and 35.989 milliseconds to execute. That's about 400.81
units per millisecond. The Index Scan is only being charged 98.94
units per millisecond of execution. If the Index Scan was costed the
same per unit as the Seq Scan, the total Index Scan cost would be
150868 which is already more than the Seq Scan plan without even
adding the Incremental Sort costs on. To me, that seems to be an
inaccuracy either with the Seq Scan costings coming out too expensive
or Index Scan coming out too cheap.

If you think that the Incremental Sort plan shouldn't be chosen
because the Index Scan costing came out too cheap (or the Seq Scan
costing was too expensive) then I disagree. Applying some penalty to
one node type because some other node type isn't costed accurately is
just not a practice we should be doing. Instead, we should be trying
our best to cost each node type as accurately as possible. If you
think there's some inaccuracy with Incremental Sort, then let's look
into that. If you want to re-add the penalty because Index Scan
costing isn't good, let's see if we can fix Index Scan costings.

David