Re: [PATCH] Incremental sort (was: PoC: Partial sort)

On Wed, Apr 01, 2020 at 09:05:27AM -0400, James Coleman wrote:
>On Tue, Mar 31, 2020 at 11:07 PM James Coleman <jtc331(at)gmail(dot)com> wrote:
>>
>> On Tue, Mar 31, 2020 at 10:44 PM Tomas Vondra
>> <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>> >
>> > On Tue, Mar 31, 2020 at 10:12:29PM -0400, James Coleman wrote:
>> > >On Tue, Mar 31, 2020 at 9:59 PM Tomas Vondra
>> > ><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>> > >>
>> > >> On Tue, Mar 31, 2020 at 08:42:47PM -0400, James Coleman wrote:
>> > >> >On Tue, Mar 31, 2020 at 8:38 PM Tomas Vondra
>> > >> ><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>> > >> >>
>> > >> >> On Tue, Mar 31, 2020 at 08:11:15PM -0400, James Coleman wrote:
>> > >> >> >On Tue, Mar 31, 2020 at 7:56 PM Tomas Vondra
>> > >> >> ><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>...
>> > >> >> >One small idea, but I'm not yet sure it helps us a whole lot: if the
>> > >> >> >query pathkeys is only length 1, then we could skip the additional
>> > >> >> >path creation.
>> > >> >> >
>> > >> >>
>> > >> >> I don't follow. Why would we create incremental sort in this case at
>> > >> >> all? With single-element query_pathkeys the path is either unsorted or
>> > >> >> fully sorted - there's no room for incremental sort. No?
>> > >> >
>> > >> >Well, we shouldn't, that's what I'm getting. But I didn't see anything
>> > >> >in the code now that explicitly excludes that case when decided
>> > >> >whether or not to create an incremental sort path, unless I'm missing
>> > >> >something obvious.
>> > >>
>> > >> Well, my point is that create_ordered_paths() looks like this:
>> > >>
>> > >> is_sorted = pathkeys_common_contained_in(root->sort_patkeys, ...);
>> > >>
>> > >> if (is_sorted)
>> > >> {
>> > >> ... old code
>> > >> }
>> > >> else
>> > >> {
>> > >> if (input_path == cheapest_input_path)
>> > >> {
>> > >> ... old code
>> > >> }
>> > >>
>> > >> /* With incremental sort disabled, don't build those paths. */
>> > >> if (!enable_incrementalsort)
>> > >> continue;
>> > >>
>> > >> /* Likewise, if the path can't be used for incremental sort. */
>> > >> if (!presorted_keys)
>> > >> continue;
>> > >>
>> > >> ... incremental sort path
>> > >> }
>> > >>
>> > >> Now, with single-item sort_pathkeys, the input path can't be partially
>> > >> sorted. It's either fully sorted - in which case it's handled by the
>> > >> first branch. Or it's not sorted at all, so presorted_keys==0 and we
>> > >> never get to the incremental path.
>> > >>
>> > >> Or did you mean to use the optimization somewhere else?
>> > >
>> > >Hmm, yes, I didn't think through that properly. I'll have to look at
>> > >the other cases to confirm the same logic applies there.
>
>I looked through this more carefully, and I did end up finding a few
>places where we can skip iterating through a list of paths entirely
>with this check, so I added it there. I also cleaned up some comments,
>added comments and asserts to the other places where
>list_length(pathkeys) should be guaranteed to be > 1, removed a few
>asserts I found unnecessary, and merged duplicative
>pathkeys_[count_]_contained_in calls.
>

OK

>> > >One other thing:in the code above we create the regular sort path
>> > >inside of `if (input_path == cheapest_input_path)`, but incremental
>> > >sort is outside of that condition. I'm not sure I'm remembering why
>> > >that was, and it's not obvious to me reading it right now (though it's
>> > >getting late here, so maybe I'm just not thinking clearly). Do you
>> > >happen to remember why that is?
>> > >
>> >
>> > It's because for the regular sort, the path is either already sorted or
>> > it requires a full sort. But full sort only makes sense on the cheapest
>> > path, because we assume the additional sort cost is independent of the
>> > input cost, essentially
>> >
>> > cost(path + Sort) = cost(path) + cost(Sort)
>> >
>> > and it's always
>> >
>> > cost(path) + cost(Sort) >= cost(cheapest path) + cost(Sort)
>> >
>> > and by checking for cheapest path we simply skip building all the paths
>> > that we'd end up discarding anyway.
>> >
>> > With incremental sort we can't do this, the cost of the incremental sort
>> > depends on how well presorted is the input path.
>
>Thanks for the explanation. I've added a comment to that effect.
>

Thanks.

I've realized the way get_useful_pathkeys_for_relation() is coded kinda
works against the fastpath we added when comparing pathkeys. That
depends on comparing pointers to the list, but we've been building new
lists (and then returned those) which defeats the optimization. Attached
is a patch that returns the original list in most cases (and only
creates a copy when really necessary). This might also save a few cycles
on bulding the new list, of course.

I've done a bunch of read-only pgbench tests with fairly small scales (1
and 10). First with the built-in read-only transaction, and also with a
simple custom query doing an order-by. And I did this both on the
default schema and with a bunch of extra indexes. The script I used to
run this is attached, along with a summary of results.

There are results for master and v40 and v50 patches (the v50 also
includes the extra patch fixing get_useful_pathkeys_for_relation).

Overall, I'm happy with those results - the v50 seems to be within 1% of
master, in both directions. This very much seems like a noise.

I still want to do a bit more review of the costing / tuplesort changes,
which I plan to do tomorrow. If that goes well, I plan to start
committing this. So please if you think this is not ready or wants more
time for a review, let me know. I'm not yet sure if I'll commit this as
a single change, or in three separate commits.

James, can you review the proposed extra fix and merge the fixes into
the main patches?

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services