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

On 9/14/24 05:37, Richard Guo wrote:
> On Fri, Sep 13, 2024 at 7:35 PM Tomas Vondra <tomas(at)vondra(dot)me> wrote:
>> On 9/13/24 06:04, Richard Guo wrote:
>>> It seems to me that some parts of our code assume that, for a given
>>> input path that is partially ordered, an incremental sort is always
>>> preferable to a full sort (see commit 4a29eabd1). Am I getting this
>>> correctly?
>>
>> I don't think we're making such assumption. I don't know which of the
>> many places modified by 4a29eabd1 you have in mind, but IIRC we always
>> consider both full and incremental sort.
>
> Hmm, I don't think it's true that we always consider both full and
> incremental sort on the same path. It was true initially, but that’s
> no longer the case.
>
> I checked the 9 callers of create_incremental_sort_path, and they all
> follow the logic that if there are presorted keys, only incremental
> sort is considered. To quote a comment from one of the callers:
>
> * ... We've no need to consider both
> * sort and incremental sort on the same path. We assume that
> * incremental sort is always faster when there are presorted
> * keys.
>
> I think this is also explained in the commit message of 4a29eabd1,
> quoted here:
>
> "
> Previously we would generally create a sort path on the cheapest input
> path (if that wasn't sorted already) and incremental sort paths on any
> path which had presorted keys. This meant that if the cheapest input path
> wasn't completely sorted but happened to have presorted keys, we would
> create a full sort path *and* an incremental sort path on that input path.
> Here we change this logic so that if there are presorted keys, we only
> create an incremental sort path, and create sort paths only when a full
> sort is required.
> "
>

Hmmm ... I wasn't involved in that discussion and I haven't studied the
thread now, but this seems a bit weird to me. If the presorted keys have
low cardinality, can't the full sort be faster?

Maybe it's not possible with the costing changes (removing the
penalization), in which case it would be fine to not consider the full
sort, because we'd just throw it away immediately. But if the full sort
could be costed as cheaper, I'd say that might be wrong.

regards

--
Tomas Vondra