Horton

Thread

Commits

  1. Order active window clauses for greater reuse of Sort nodes.

  1. Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-05-30T16:19:48Z

    Currently, we can only reuse Sort nodes between WindowAgg nodes iff the
partitioning and ordering clauses are identical.  If a window Sort node
sortorder is a prefix of another window, we could however reuse the Sort node
to hopefully produce a cheaper plan.  In src/backend/optimizer/plan/planner.c
there is a comment alluding to this:

        * ...
        *
        * There is room to be much smarter here, for example detecting whether
        * one window's sort keys are a prefix of another's (so that sorting for
        * the latter would do for the former), or putting windows first that
        * match a sort order available for the underlying query.  For the moment
        * we are content with meeting the spec.
        */

The attached patch takes a stab at implementing the sorting on partitioning/
ordering prefix, inspired by a similar optimization in the Greenplum planner.
In testing the impact on planning time seems quite minimal, or within the error
margin.

cheers ./daniel

  2. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-06-12T13:10:50Z

    > On 30 May 2018, at 18:19, Daniel Gustafsson <daniel@yesql.se> wrote:
> 
> Currently, we can only reuse Sort nodes between WindowAgg nodes iff the
> partitioning and ordering clauses are identical.  If a window Sort node
> sortorder is a prefix of another window, we could however reuse the Sort node
> to hopefully produce a cheaper plan.  In src/backend/optimizer/plan/planner.c
> there is a comment alluding to this:
> 
>        * ...
>        *
>        * There is room to be much smarter here, for example detecting whether
>        * one window's sort keys are a prefix of another's (so that sorting for
>        * the latter would do for the former), or putting windows first that
>        * match a sort order available for the underlying query.  For the moment
>        * we are content with meeting the spec.
>        */
> 
> The attached patch takes a stab at implementing the sorting on partitioning/
> ordering prefix, inspired by a similar optimization in the Greenplum planner.
> In testing the impact on planning time seems quite minimal, or within the error
> margin.

Attached is a rebased v2 addressing off-list review comments and including a
test.  Parking this in the commitfest.

cheers ./daniel

  3. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> — 2018-06-26T15:11:24Z

    Daniel,

I took a look at the patch. It applies and compiles, the tests pass.

Some thoughts about the code:

* Postgres lists cache their lengths, so you don't need uniqueLen.

* Use an array of WindowClauseSortNode's instead of a list. It's more 
suitable here because you are going to sort (qsort_list creates a 
temporary array).

* Reversing the sorted list looks more confusing to me than just sorting 
it in the proper order right away. A qsort() comparator returning 
negative means "left goes before right", but here it is effectively the 
other way around.

* This isn't relevant given the previous points, but to reverse a list, 
you can walk it with foreach() and construct a reversed version with 
lcons().

* There is a function named make_pathkeys_for_window that makes a list 
of canonical pathkeys given a window clause. Using this function to give 
you the pathkeys, and then comparing them, would be more future-proof in 
case we ever start using hashing for windowing. Moreover, the canonical 
pathkeys can be compared with pointer comparison which is much faster 
than equal(). Still, I'm not sure whether it's going to be convenient to 
use in this case, or even whether it is a right thing to do. What do you 
think?

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

  4. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-07-02T08:25:19Z

    > On 26 Jun 2018, at 17:11, Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> wrote:

> I took a look at the patch. It applies and compiles, the tests pass.

Thanks for reviewing, and apologies for the slow response.

> Some thoughts about the code:
> 
> * Postgres lists cache their lengths, so you don't need uniqueLen.

Good point, fixed.

> * Use an array of WindowClauseSortNode's instead of a list. It's more suitable here because you are going to sort (qsort_list creates a temporary array).

I was thinking about that, but opted for code simplicity with a List approach.
The required size of the array isn’t known ahead of time, so it must either
potentially overallocate to the upper bound of root->parse->windowClause or use
heuristics and risk reallocating when growing, neither of which is terribly
appealing.  Do you have any suggestions or preferences?

> * Reversing the sorted list looks more confusing to me than just sorting it in the proper order right away. A qsort() comparator returning negative means "left goes before right", but here it is effectively the other way around.

Changed.
	
> * There is a function named make_pathkeys_for_window that makes a list of canonical pathkeys given a window clause. Using this function to give you the pathkeys, and then comparing them, would be more future-proof in case we ever start using hashing for windowing. Moreover, the canonical pathkeys can be compared with pointer comparison which is much faster than equal(). Still, I'm not sure whether it's going to be convenient to use in this case, or even whether it is a right thing to do. What do you think?

That’s an interesting thought, one that didn’t occur to me while hacking.  I’m
not sure whether is would be wise/clean to overload with this functionality
though.

Attached updated version also adds a testcase that was clearly missing from the
previous version and an updated window.out.

cheers ./daniel

  5. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Masahiko Sawada <sawada.mshk@gmail.com> — 2018-07-02T12:01:15Z

    On Mon, Jul 2, 2018 at 5:25 PM, Daniel Gustafsson <daniel@yesql.se> wrote:
>> On 26 Jun 2018, at 17:11, Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> wrote:
>
>> I took a look at the patch. It applies and compiles, the tests pass.
>
> Thanks for reviewing, and apologies for the slow response.
>
>> Some thoughts about the code:
>>
>> * Postgres lists cache their lengths, so you don't need uniqueLen.
>
> Good point, fixed.
>
>> * Use an array of WindowClauseSortNode's instead of a list. It's more suitable here because you are going to sort (qsort_list creates a temporary array).
>
> I was thinking about that, but opted for code simplicity with a List approach.
> The required size of the array isn’t known ahead of time, so it must either
> potentially overallocate to the upper bound of root->parse->windowClause or use
> heuristics and risk reallocating when growing, neither of which is terribly
> appealing.  Do you have any suggestions or preferences?
>
>> * Reversing the sorted list looks more confusing to me than just sorting it in the proper order right away. A qsort() comparator returning negative means "left goes before right", but here it is effectively the other way around.
>
> Changed.
>
>> * There is a function named make_pathkeys_for_window that makes a list of canonical pathkeys given a window clause. Using this function to give you the pathkeys, and then comparing them, would be more future-proof in case we ever start using hashing for windowing. Moreover, the canonical pathkeys can be compared with pointer comparison which is much faster than equal(). Still, I'm not sure whether it's going to be convenient to use in this case, or even whether it is a right thing to do. What do you think?
>
> That’s an interesting thought, one that didn’t occur to me while hacking.  I’m
> not sure whether is would be wise/clean to overload with this functionality
> though.
>
> Attached updated version also adds a testcase that was clearly missing from the
> previous version and an updated window.out.
>
> cheers ./daniel
>

Thank you for updating the patch! There are two review comments.

The current select_active_windows() function compares the all fields
of WindowClause for the sorting but with this patch we compare only
tleSortGroupRef, sortop and the number of uniqueOrder. I think this
leads a degradation as follows.

=# explain select *, sum(b) over w1, sum(a) over w2, sum(b) over w3
from w window w1 as (partition by a order by a nulls first), w2 as
(partition by a order by a), w3 as (partition by a order by a nulls
first);

* Current HEAD
                                    QUERY PLAN
-----------------------------------------------------------------------------------
 WindowAgg  (cost=369.16..414.36 rows=2260 width=32)
   ->  Sort  (cost=369.16..374.81 rows=2260 width=24)
         Sort Key: a
         ->  WindowAgg  (cost=158.51..243.26 rows=2260 width=24)
               ->  WindowAgg  (cost=158.51..203.71 rows=2260 width=16)
                     ->  Sort  (cost=158.51..164.16 rows=2260 width=8)
                           Sort Key: a NULLS FIRST
                           ->  Seq Scan on w  (cost=0.00..32.60
rows=2260 width=8)
(8 rows)

* With patch
                                       QUERY PLAN
-----------------------------------------------------------------------------------------
 WindowAgg 3  (cost=500.72..545.92 rows=2260 width=32)
   ->  Sort  (cost=500.72..506.37 rows=2260 width=24)
         Sort Key: a NULLS FIRST
         ->  WindowAgg 2  (cost=329.61..374.81 rows=2260 width=24)
               ->  Sort  (cost=329.61..335.26 rows=2260 width=16)
                     Sort Key: a
                     ->  WindowAgg 1  (cost=158.51..203.71 rows=2260 width=16)
                           ->  Sort  (cost=158.51..164.16 rows=2260 width=8)
                                 Sort Key: a NULLS FIRST
                                 ->  Seq Scan on w  (cost=0.00..32.60
rows=2260 width=8)
(10 rows)

---
+                        * Generating the uniqueOrder can be offloaded
to the comparison
+                        * function to optimize for the case where we
only have a single
+                        * window.  For now, optimize for readibility.

s/readibility/readability/

Regards,

--
Masahiko Sawada
NIPPON TELEGRAPH AND TELEPHONE CORPORATION
NTT Open Source Software Center

  6. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-07-02T21:19:16Z

    > On 2 Jul 2018, at 14:01, Masahiko Sawada <sawada.mshk@gmail.com> wrote:

> Thank you for updating the patch! There are two review comments.

Thanks for reviewing!

> The current select_active_windows() function compares the all fields
> of WindowClause for the sorting but with this patch we compare only
> tleSortGroupRef, sortop and the number of uniqueOrder. I think this
> leads a degradation as follows.

You are right, that was an oversight.  The attached patch takes a stab at
fixing this.

> s/readibility/readability/

Fixed.

cheers ./daniel

  7. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Masahiko Sawada <sawada.mshk@gmail.com> — 2018-07-03T10:24:06Z

    On Tue, Jul 3, 2018 at 6:19 AM, Daniel Gustafsson <daniel@yesql.se> wrote:
>> On 2 Jul 2018, at 14:01, Masahiko Sawada <sawada.mshk@gmail.com> wrote:
>
>> Thank you for updating the patch! There are two review comments.
>
> Thanks for reviewing!
>
>> The current select_active_windows() function compares the all fields
>> of WindowClause for the sorting but with this patch we compare only
>> tleSortGroupRef, sortop and the number of uniqueOrder. I think this
>> leads a degradation as follows.
>
> You are right, that was an oversight.  The attached patch takes a stab at
> fixing this.
>
>> s/readibility/readability/
>
> Fixed.

Thank you for updating the patch.

+               if (sca->tleSortGroupRef > scb->tleSortGroupRef)
+                       return -1;
+               else if (sca->tleSortGroupRef < scb->tleSortGroupRef)
+                       return 1;
+               else if (sca->sortop > scb->sortop)
+                       return -1;
+               else if (sca->sortop < scb->sortop)
+                       return 1;
+               else if (sca->nulls_first && !scb->nulls_first)
+                       return -1;
+               else if (!sca->nulls_first && scb->nulls_first)
+                       return 1;

Hmm, this is missing the eqop fields of SortGroupClause. I haven't
tested yet but does the similar degradation happen if two
SortGroupCaluses have different eqop and the same other values?

--
The source code comments for common_prefix_cmp() function and
WindowClauseSortNode struct is needed.

--
+-- Test Sort node reordering
+EXPLAIN (COSTS OFF)
+SELECT
+  lead(1) OVER (PARTITION BY depname ORDER BY salary, enroll_date),
+  lag(1) OVER (PARTITION BY depname ORDER BY salary,enroll_date,empno)
+  from empsalary;

I think it's better to change "from empsalary" to "FROM empsalary" for
consistency with other code.

Regards,

--
Masahiko Sawada
NIPPON TELEGRAPH AND TELEPHONE CORPORATION
NTT Open Source Software Center

  8. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-07-24T22:37:06Z

    > On 3 Jul 2018, at 12:24, Masahiko Sawada <sawada.mshk@gmail.com> wrote:

> Thank you for updating the patch.

Thanks for reviewing!

> Hmm, this is missing the eqop fields of SortGroupClause. I haven't
> tested yet but does the similar degradation happen if two
> SortGroupCaluses have different eqop and the same other values?

I wasn’t able to construct a case showing this, but I also think you’re right.
Do you have an idea of a query that can trigger a regression?  The attached
patch adds a stab at this, but I’m not sure if it’s the right approach.

> The source code comments for common_prefix_cmp() function and
> WindowClauseSortNode struct is needed.

Fixed.

> +  from empsalary;
> 
> I think it's better to change "from empsalary" to "FROM empsalary" for
> consistency with other code.

Yes, that was a silly oversight. Fixed.

cheers ./daniel

  9. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> — 2018-07-27T19:12:02Z

    Daniel,

Thanks for the update.


On 07/25/2018 01:37 AM, Daniel Gustafsson wrote:
>
>> Hmm, this is missing the eqop fields of SortGroupClause. I haven't
>> tested yet but does the similar degradation happen if two
>> SortGroupCaluses have different eqop and the same other values?
> I wasn’t able to construct a case showing this, but I also think you’re right.
> Do you have an idea of a query that can trigger a regression?  The attached
> patch adds a stab at this, but I’m not sure if it’s the right approach.

To trigger that, in your test example you could order by empno::int8 for 
one window, and by empno::int2 for another. But don't I think you have 
to compare eqop here, because if eqop differs, sortop will differ too. I 
removed the comparison from the patch. I also clarified (I hope) the 
comments, and did the optimization I mentioned earlier: using array 
instead of list for active clauses. Please see the attached v6. 
Otherwise I think the patch is good.

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

  10. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-07-30T23:00:35Z

    > On 27 Jul 2018, at 21:12, Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> wrote:

> Thanks for the update.

Thank you for reviewing and hacking!

> On 07/25/2018 01:37 AM, Daniel Gustafsson wrote:
>> 
>>> Hmm, this is missing the eqop fields of SortGroupClause. I haven't
>>> tested yet but does the similar degradation happen if two
>>> SortGroupCaluses have different eqop and the same other values?
>> I wasn’t able to construct a case showing this, but I also think you’re right.
>> Do you have an idea of a query that can trigger a regression?  The attached
>> patch adds a stab at this, but I’m not sure if it’s the right approach.
> 
> To trigger that, in your test example you could order by empno::int8 for one window, and by empno::int2 for another. But don't I think you have to compare eqop here, because if eqop differs, sortop will differ too. I removed the comparison from the patch.

Right, that makes sense.

> I also clarified (I hope) the comments, and did the optimization I mentioned earlier: using array instead of list for active clauses. Please see the attached v6.

Thanks, looks good.

> Otherwise I think the patch is good.

Cool, thanks for reviewing!

cheers ./daniel

  11. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru> — 2018-09-10T09:50:31Z

    The last version looked OK, so I'm marking this patch as ready for 
committer in the commitfest app.

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

  12. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Masahiko Sawada <sawada.mshk@gmail.com> — 2018-09-11T08:28:38Z

    On Sat, Jul 28, 2018 at 4:12 AM, Alexander Kuzmenkov
<a.kuzmenkov@postgrespro.ru> wrote:
> Daniel,
>
> Thanks for the update.
>
>
> On 07/25/2018 01:37 AM, Daniel Gustafsson wrote:
>>
>>
>>> Hmm, this is missing the eqop fields of SortGroupClause. I haven't
>>> tested yet but does the similar degradation happen if two
>>> SortGroupCaluses have different eqop and the same other values?
>>
>> I wasn’t able to construct a case showing this, but I also think you’re
>> right.
>> Do you have an idea of a query that can trigger a regression?  The
>> attached
>> patch adds a stab at this, but I’m not sure if it’s the right approach.
>
>
> To trigger that, in your test example you could order by empno::int8 for one
> window, and by empno::int2 for another. But don't I think you have to
> compare eqop here, because if eqop differs, sortop will differ too. I
> removed the comparison from the patch. I also clarified (I hope) the
> comments, and did the optimization I mentioned earlier: using array instead
> of list for active clauses. Please see the attached v6. Otherwise I think
> the patch is good.
>

Thank you! That makes sense and the patch looks good to me. FWIW maybe
it's good idea to add the comment describing why we didn't that.

Regards,

--
Masahiko Sawada
NIPPON TELEGRAPH AND TELEPHONE CORPORATION
NTT Open Source Software Center

  13. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2018-09-12T20:15:02Z

    So I'm looking to commit this, and here's my comments so far:

WindowClauseSortNode - I don't like this name, because it's not actually
a Node of any kind. How about WindowSortData?

list_concat_unique(list_copy(x),y) is exactly list_union(x,y), which
looks a bit nicer to me.

re. this:

    for (; nActive > 0; nActive--)
        result = lcons(actives[nActive - 1].wc, result);

Now that we're allowed to use C99, I think it looks better like this:

    for (int i = 0; i < nActive; i++)
        result = lappend(result, actives[i].wc);

(Building lists in forward order by using a reversed construction and
iterating backwards seems like an unnecessary double-negative.)

I can add a comment about not needing to compare eqop (which is derived
directly from sortop, so it can't differ unless sortop also does -
provided sortop is actually present; if window partitions could be
hashed, this would be a problem, but that doesn't strike me as very
likely to happen).

Any comments? (no need to post further patches unless there's some major
change needed)

-- 
Andrew (irc:RhodiumToad)

  14. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-09-12T20:32:59Z

    > On 12 Sep 2018, at 22:15, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:

> WindowClauseSortNode - I don't like this name, because it's not actually
> a Node of any kind. How about WindowSortData?

That’s a good point.  I probably would’ve named it WindowClauseSortData since
it acts on WindowClauses, but that might just be overly verbose.

> Any comments? (no need to post further patches unless there's some major
> change needed)

I have no objections to the comments made in this review, only the above
nitpick.

Thanks for picking this up!

cheers ./daniel

  15. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-09-12T21:31:50Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> So I'm looking to commit this, and here's my comments so far:

I took a quick look over this.  I agree with your nitpicks, and have
a couple more:

* Please run it through pgindent.  That will, at a minimum, remove some
gratuitous whitespace changes in this patch.  I think it'll also expose
some places where you need to change the code layout to prevent pgindent
from making it look ugly.  Notably, this:

        actives[nActive].uniqueOrder = list_concat_unique(
                            list_copy(wc->partitionClause), wc->orderClause);

is not per project style for function call layout.  Given the other
comment about using list_union, I'd probably lay it out like this:

        actives[nActive].uniqueOrder = list_union(wc->partitionClause,
                                                  wc->orderClause);

* The initial comment in select_active_windows,

	/* First, make a list of the active windows */

is now seriously inadequate as a description of what the subsequent
loop does; it needs to be expanded.  I'd also say that it's not
building a list anymore, but an array.  Further, there needs to be
an explanation of why what it's doing is correct at all ---
list_union doesn't make many promises about the order of the resulting
list (nor did the phraseology with list_concat_unique), but what we're
doing below certainly requires that order to have something to do with
the window semantics.

* I'm almost thinking that changing to list_union is a bad idea, because
that obscures the fact that we're relying on the relative order of
elements in partitionClause and orderClause to not change; any future
reimplementation of list_union would utterly break this code.  I'm also a
bit suspicious as to whether the code is even correct; does it *really*
match what will happen later when we create sort plan nodes?  (Maybe it's
fine; I haven't looked.)

* The original comments also made explicit that we were not considering
framing options, and I'm not too happy that that disappeared.

* It'd be better if common_prefix_cmp didn't cast away const.

			regards, tom lane

  16. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2018-09-13T00:28:49Z

    >>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

 Tom> * I'm almost thinking that changing to list_union is a bad idea,

A fair point. Though it looks like list_union is used in only about 3
distinct places, and two of those are list_union(NIL, blah) to simply
remove dups from a single list. The third place is the cartesian-product
expansion of grouping sets, which uses list_union_int to remove
duplicates - changing the order there will give slightly user-surprising
but not actually incorrect results.

Presumably list_concat_unique should be considered to guarantee that it
preserves the relative order of the two lists and of the non-duplicate
items in the second list?

-- 
Andrew (irc:RhodiumToad)

  17. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-09-13T00:38:26Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:
>  Tom> * I'm almost thinking that changing to list_union is a bad idea,

> A fair point. Though it looks like list_union is used in only about 3
> distinct places, and two of those are list_union(NIL, blah) to simply
> remove dups from a single list. The third place is the cartesian-product
> expansion of grouping sets, which uses list_union_int to remove
> duplicates - changing the order there will give slightly user-surprising
> but not actually incorrect results.

> Presumably list_concat_unique should be considered to guarantee that it
> preserves the relative order of the two lists and of the non-duplicate
> items in the second list?

I'm thinking that whichever coding we use, the patch should include
comment additions in list.c documenting that some callers have assumptions
thus-and-so about list order preservation.  Then at least anybody who
got the idea to try to improve performance of those functions would be on
notice about the risks.

I see that list_union is currently documented like this:

 * Generate the union of two lists. This is calculated by copying
 * list1 via list_copy(), then adding to it all the members of list2
 * that aren't already in list1.

so as long as it stays like that, it's not unreasonable to use it in
this patch.  I just want the potential landmine to be obvious at that
end.

			regards, tom lane

  18. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2018-09-13T14:04:10Z

    >>>>> "Tom" == Tom Lane <tgl@sss.pgh.pa.us> writes:

 Tom> I'm also a bit suspicious as to whether the code is even correct;
 Tom> does it *really* match what will happen later when we create sort
 Tom> plan nodes? (Maybe it's fine; I haven't looked.)

As things stand before the patch, the code that actually generates the
path of sort+window nodes requires only this assumption: that
order-equivalent windows (as defined by the spec) must end up together
in the list, or otherwise separated only by entries that don't add a new
sort node.

(aside: I itch to rewrite the comment that says "the spec requires that
there be only one sort" - number of sorts is an implementation detail
about which the spec is silent, what it _actually_ requires is that peer
rows must be presented in the same order in all order-equivalent
windows, which we choose to implement by ensuring there is only one sort
for such windows, rather than, for example, adding extra sort keys to
provide stability.)

The path-generation code simply concatenates the partition and order
lists and creates pathkeys. The pathkeys creation removes redundant
entries. So if we're guaranteed that two entries considered equal by the
patch code are also considered equal by the pathkey mechanism, which I
believe is the case, then the logic is still correct (enough to satisfy
the spec and produce correct query results).

There are optimizations that can be done once we have the pathkeys that
can't be anticipated by select_active_windows because that function is
run before we set up equivalence classes. This might lead path creation
to produce fewer sorts than anticipated, but not more sorts.

So I'm satisfied, as far as I can tell, that the logic is both correct
and an improvement over what we currently have.

(Perhaps worth noting for future work is that this code and the grouping
sets code have a common issue: currently we allow only one sort order to
be requested as query_pathkeys, but this means that both window paths
and grouping sets paths have to make an essentially arbitrary choice of
query_pathkeys, rather than having a set of possible "useful" orderings
and taking whichever can be produced most cheaply.)

-- 
Andrew (irc:RhodiumToad)

  19. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Tom Lane <tgl@sss.pgh.pa.us> — 2018-09-13T14:25:21Z

    Andrew Gierth <andrew@tao11.riddles.org.uk> writes:
> (aside: I itch to rewrite the comment that says "the spec requires that
> there be only one sort" - number of sorts is an implementation detail
> about which the spec is silent, what it _actually_ requires is that peer
> rows must be presented in the same order in all order-equivalent
> windows, which we choose to implement by ensuring there is only one sort
> for such windows, rather than, for example, adding extra sort keys to
> provide stability.)

Sure, rewrite away.

> (Perhaps worth noting for future work is that this code and the grouping
> sets code have a common issue: currently we allow only one sort order to
> be requested as query_pathkeys, but this means that both window paths
> and grouping sets paths have to make an essentially arbitrary choice of
> query_pathkeys, rather than having a set of possible "useful" orderings
> and taking whichever can be produced most cheaply.)

Yeah, I've had a bee in my bonnet for awhile about replacing
query_pathkeys with a list of potentially-desirable result orderings.
So far there hasn't been a truly compelling reason to do it, but if
somebody felt like generalizing the window function ordering stuff
in that direction, it'd be a nice project.

			regards, tom lane

  20. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2018-09-13T17:50:13Z

    Here's what I have queued up to push.

My changes are:

 - added to the header comment of list_concat_unique that callers have
   ordering expectations. Didn't touch list_union, since I ended up
   sticking with list_concat_unique for this patch.

 - WindowClauseSortNode renamed WindowClauseSortData

 - added and rewrote some comments

 - tidied up some casting in common_prefix_cmp

 - pgindent and some layout tweaks

-- 
Andrew (irc:RhodiumToad)

  21. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Daniel Gustafsson <daniel@yesql.se> — 2018-09-14T11:34:22Z

    > On 13 Sep 2018, at 19:50, Andrew Gierth <andrew@tao11.riddles.org.uk> wrote:
> 
> Here's what I have queued up to push.

LGTM, thanks!

> +	 * framing clauses differ), then all peer rows must be presented in the
> +	 * same order in all of them. If we allowed multiple sort nodes for such

Should probably be capitalized as "Sort nodes” to match the rest of the comment.

cheers ./daniel

  22. Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused

    Andrew Gierth <andrew@tao11.riddles.org.uk> — 2018-09-14T16:38:28Z

     >> Here's what I have queued up to push.

 Daniel> LGTM, thanks!

Committed.

Many thanks for the contribution, and thanks to the reviewers for their
work.

-- 
Andrew (irc:RhodiumToad)