Re: [HACKERS] [PATCH] Incremental sort

Hi!

Thank you very much for review. I really appreciate this topic gets
attention. Please, find next revision of patch in the attachment.

On Wed, Nov 15, 2017 at 7:20 PM, Antonin Houska <ah(at)cybertec(dot)at> wrote:

> Antonin Houska <ah(at)cybertec(dot)at> wrote:
>
> > Alexander Korotkov <a(dot)korotkov(at)postgrespro(dot)ru> wrote:
> >
> > > Patch rebased to current master is attached. I'm going to improve my
> testing script and post new results.
> >
> > I wanted to review this patch but incremental-sort-8.patch fails to
> apply. Can
> > you please rebase it again?
>
> I could find the matching HEAD quite easily (9b6cb46), so following are my
> comments:
>
> * cost_sort()
>
> ** "presorted_keys" missing in the prologue
>

Comment is added.

** when called from label_sort_with_costsize(), 0 is passed for
> "presorted_keys". However label_sort_with_costsize() can sometimes be
> called on an IncrementalSort, in which case there are some "presorted
> keys". See create_mergejoin_plan() for example. (IIUC this should only
> make EXPLAIN inaccurate, but should not cause incorrect decisions.)
>

Good catch. Fixed.

** instead of
>
> if (!enable_incrementalsort)
> presorted_keys = false;
>
> you probably meant
>
> if (!enable_incrementalsort)
> presorted_keys = 0;
>

Absolutely correct. Fixed.

> ** instead of
>
> /* Extract presorted keys as list of expressions */
> foreach(l, pathkeys)
> {
> PathKey *key = (PathKey *)lfirst(l);
> EquivalenceMember *member = (EquivalenceMember *)
> lfirst(list_head(key->pk_eclass->ec_members));
>
> you can use linitial():
>
> /* Extract presorted keys as list of expressions */
> foreach(l, pathkeys)
> {
> PathKey *key = (PathKey *)lfirst(l);
> EquivalenceMember *member = (EquivalenceMember *)
> linitial(key->pk_eclass->ec_members);
>

Sure. Fixed.

>
> * get_cheapest_fractional_path_for_pathkeys()
>
> The prologue says "... at least partially satisfies the given pathkeys ..."
> but I see no change in the function code. In particular the use of
> pathkeys_contained_in() does not allow for any kind of partial sorting.
>

Good catch. This is a part of optimization for build_minmax_path() which
existed in earlier version of patch. That optimization contained set of
arguable solutions. This is why I decided to wipe it out from the patch,
and let it wait for initial implementation to be committed.

* pathkeys_useful_for_ordering()
>
> Extra whitespace following the comment opening string "/*":
>
> /*
> * When incremental sort is disabled, pathkeys are useful only when they
>

Fixed.

> * make_sort_from_pathkeys() - the "skipCols" argument should be mentioned
> in
> the prologue.
>

Comment is added.

> * create_sort_plan()
>
> I noticed that pathkeys_common() is called, but the value of
> n_common_pathkeys
> should already be in the path's "skipCols" field if the underlying path is
> actually IncrementalSortPath.
>

Sounds like reasonable optimization. Done.

> * create_unique_plan() does not seem to make use of the incremental
> sort. Shouldn't it do?
>

It definitely should. But proper solution doesn't seem to be easy for me.
We should construct possibly useful paths before. Wherein it should be
done in agnostic manner to the order of pathkeys. I'm afraid for possible
regression in query planning. Therefore, it seems like a topic for
separate discussion. I would prefer to commit some basic implementation
first and then consider smaller patches with possible enhancement including
this one.

* nodeIncrementalSort.c
>
> ** These comments seem to contain typos:
>
> "Incremental sort algorithm would sort by xfollowing groups, which have
> ..."
>
> "Interate while skip cols are same as in saved tuple"
>

Fixed.

>
> ** (This is rather a pedantic comment) I think prepareSkipCols() should be
> defined in front of cmpSortSkipCols().
>

That's a good comment. We're trying to be as pedantic about code as we can
:)
Fixed.

** the MIN_GROUP_SIZE constant deserves a comment.
>

Sure. Explanation was added.

> * ExecIncrementalSort()
>
> ** if (node->tuplesortstate == NULL)
>
> If both branches contain the expression
>
> node->groupsCount++;
>
> I suggest it to be moved outside the "if" construct.

Done.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company