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

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.
"

Thanks
Richard