Avoid extra Sort nodes between WindowAggs when sorting can be reused

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

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

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

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

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

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

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

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

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

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

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

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)

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

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

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

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

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

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

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)