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

On 9/24/24 00:21, David Rowley wrote:
> 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.
>

You're right, this wasn't a good example. I tried to come up with
something quickly, and I didn't realize the extra time comes from the
other node in the plan, not the sort :-(

I vaguely remember there were a couple reports about slow queries
involving incremental sort, but I didn't find any that would show
incremental sort itself being slower. So maybe I'm wrong ...

IIRC the concerns were more about planning - what happens when the
multi-column ndistinct estimates (which are quite shaky) are wrong, etc.
Or how it interacts with LIMIT with hidden correlations, etc.

Sure, those are not problems of incremental sort, it just makes it
easier to hit some of these issues. Of course, that doesn't mean the
1.5x penalty was a particularly good solution.

regards

--
Tomas Vondra