Thread: Avoid extra Sort nodes between WindowAggs when sorting can be reused
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
Attachment
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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
Attachment
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Alexander Kuzmenkov
Date:
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
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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_listcreates 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() comparatorreturning 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. Usingthis function to give you the pathkeys, and then comparing them, would be more future-proof in case we ever start usinghashing for windowing. Moreover, the canonical pathkeys can be compared with pointer comparison which is much fasterthan equal(). Still, I'm not sure whether it's going to be convenient to use in this case, or even whether it is aright 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
Attachment
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_listcreates 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.
Usingthis function to give you the pathkeys, and then comparing them, would be more future-proof in case we ever start
usinghashing for windowing. Moreover, the canonical pathkeys can be compared with pointer comparison which is much
fasterthan equal(). Still, I'm not sure whether it's going to be convenient to use in this case, or even whether it is
aright 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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
Attachment
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
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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
Attachment
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Alexander Kuzmenkov
Date:
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
Attachment
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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. Butdon't I think you have to compare eqop here, because if eqop differs, sortop will differ too. I removed the comparisonfrom 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 activeclauses. Please see the attached v6. Thanks, looks good. > Otherwise I think the patch is good. Cool, thanks for reviewing! cheers ./daniel
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Alexander Kuzmenkov
Date:
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)
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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) From 9c89883ffe2153cc9d047f71a2b0e611f2c60452 Mon Sep 17 00:00:00 2001 From: Andrew Gierth <rhodiumtoad@postgresql.org> Date: Thu, 13 Sep 2018 18:12:37 +0100 Subject: [PATCH] Order active window clauses for greater reuse of Sort nodes. By sorting the active window list lexicographically by the sort clause list but putting longer clauses before shorter prefixes, we generate more chances to elide Sort nodes when building the path. Author: Daniel Gustafsson (with some editorialization by me) Reviewed-by: Alexander Kuzmenkov, Masahiko Sawada, Tom Lane Discussion: https://postgr.es/m/124A7F69-84CD-435B-BA0E-2695BE21E5C2%40yesql.se --- src/backend/nodes/list.c | 7 +- src/backend/optimizer/plan/planner.c | 154 +++++++++++++++++++++++++---------- src/test/regress/expected/window.out | 60 +++++++++++--- src/test/regress/sql/window.sql | 16 ++++ 4 files changed, 177 insertions(+), 60 deletions(-) diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c index f3e1800708..55fd4c359b 100644 --- a/src/backend/nodes/list.c +++ b/src/backend/nodes/list.c @@ -1011,8 +1011,11 @@ list_append_unique_oid(List *list, Oid datum) * via equal(). * * This is almost the same functionality as list_union(), but list1 is - * modified in-place rather than being copied. Note also that list2's cells - * are not inserted in list1, so the analogy to list_concat() isn't perfect. + * modified in-place rather than being copied. However, callers of this + * function may have strict ordering expectations -- i.e. that the relative + * order of those list2 elements that are not duplicates is preserved. Note + * also that list2's cells are not inserted in list1, so the analogy to + * list_concat() isn't perfect. */ List * list_concat_unique(List *list1, List *list2) diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 96bf0601a8..94b85721fa 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -110,6 +110,17 @@ typedef struct int *tleref_to_colnum_map; } grouping_sets_data; +/* + * Temporary structure for use during WindowClause reordering in order to be + * be able to sort WindowClauses on partitioning/ordering prefix. + */ +typedef struct +{ + WindowClause *wc; + List *uniqueOrder; /* A List of unique ordering/partitioning + * clauses per Window */ +} WindowClauseSortData; + /* Local functions */ static Node *preprocess_expression(PlannerInfo *root, Node *expr, int kind); static void preprocess_qual_conditions(PlannerInfo *root, Node *jtnode); @@ -237,6 +248,7 @@ static void create_partitionwise_grouping_paths(PlannerInfo *root, static bool group_by_has_partkey(RelOptInfo *input_rel, List *targetList, List *groupClause); +static int common_prefix_cmp(const void *a, const void *b); /***************************************************************************** @@ -5260,68 +5272,120 @@ postprocess_setop_tlist(List *new_tlist, List *orig_tlist) static List * select_active_windows(PlannerInfo *root, WindowFuncLists *wflists) { - List *result; - List *actives; + List *windowClause = root->parse->windowClause; + List *result = NIL; ListCell *lc; + int nActive = 0; + WindowClauseSortData *actives = palloc(sizeof(WindowClauseSortData) + * list_length(windowClause)); - /* First, make a list of the active windows */ - actives = NIL; - foreach(lc, root->parse->windowClause) + /* First, construct an array of the active windows */ + foreach(lc, windowClause) { WindowClause *wc = lfirst_node(WindowClause, lc); /* It's only active if wflists shows some related WindowFuncs */ Assert(wc->winref <= wflists->maxWinRef); - if (wflists->windowFuncs[wc->winref] != NIL) - actives = lappend(actives, wc); + if (wflists->windowFuncs[wc->winref] == NIL) + continue; + + actives[nActive].wc = wc; /* original clause */ + + /* + * For sorting, we want the list of partition keys followed by the + * list of sort keys. But pathkeys construction will remove duplicates + * between the two, so we can as well (even though we can't detect all + * of the duplicates, since some may come from ECs - that might mean + * we miss optimization chances here). We must, however, ensure that + * the order of entries is preserved with respect to the ones we do + * keep. + * + * partitionClause and orderClause had their own duplicates removed in + * parse analysis, so we're only concerned here with removing + * orderClause entries that also appear in partitionClause. + */ + actives[nActive].uniqueOrder = + list_concat_unique(list_copy(wc->partitionClause), + wc->orderClause); + nActive++; } /* - * Now, ensure that windows with identical partitioning/ordering clauses - * are adjacent in the list. This is required by the SQL standard, which - * says that only one sort is to be used for such windows, even if they - * are otherwise distinct (eg, different names or framing clauses). + * Sort active windows by their partitioning/ordering clauses, ignoring + * any framing clauses, so that the windows that need the same sorting are + * adjacent in the list. When we come to generate paths, this will avoid + * inserting additional Sort nodes. * - * 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. - */ - result = NIL; - while (actives != NIL) - { - WindowClause *wc = linitial_node(WindowClause, actives); - ListCell *prev; - ListCell *next; - - /* Move wc from actives to result */ - actives = list_delete_first(actives); - result = lappend(result, wc); - - /* Now move any matching windows from actives to result */ - prev = NULL; - for (lc = list_head(actives); lc; lc = next) - { - WindowClause *wc2 = lfirst_node(WindowClause, lc); + * This is how we implement a specific requirement from the SQL standard, + * which says that when two or more windows are order-equivalent (i.e. + * have matching partition and order clauses, even if their names or + * 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 + * cases, we'd risk having the peer rows end up in different orders in + * equivalent windows due to sort instability. (See General Rule 4 of + * <window clause> in SQL2008 - SQL2016.) + * + * Additionally, if the entire list of clauses of one window is a prefix + * of another, put first the window with stronger sorting requirements. + * This way we will first sort for stronger window, and won't have to sort + * again for the weaker one. + */ + qsort(actives, nActive, sizeof(WindowClauseSortData), common_prefix_cmp); - next = lnext(lc); - /* framing options are NOT to be compared here! */ - if (equal(wc->partitionClause, wc2->partitionClause) && - equal(wc->orderClause, wc2->orderClause)) - { - actives = list_delete_cell(actives, lc, prev); - result = lappend(result, wc2); - } - else - prev = lc; - } - } + /* build ordered list of the original WindowClause nodes */ + for (int i = 0; i < nActive; i++) + result = lappend(result, actives[i].wc); + + pfree(actives); return result; } /* + * common_prefix_cmp + * QSort comparison function for WindowClauseSortData + * + * Sort the windows by the required sorting clauses. First, compare the sort + * clauses themselves. Second, if one window's clauses are a prefix of another + * one's clauses, put the window with more sort clauses first. + */ +static int +common_prefix_cmp(const void *a, const void *b) +{ + const WindowClauseSortData *wcsa = a; + const WindowClauseSortData *wcsb = b; + ListCell *item_a; + ListCell *item_b; + + forboth(item_a, wcsa->uniqueOrder, item_b, wcsb->uniqueOrder) + { + SortGroupClause *sca = lfirst_node(SortGroupClause, item_a); + SortGroupClause *scb = lfirst_node(SortGroupClause, item_b); + + 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; + /* no need to compare eqop, since it is fully determined by sortop */ + } + + if (list_length(wcsa->uniqueOrder) > list_length(wcsb->uniqueOrder)) + return -1; + else if (list_length(wcsa->uniqueOrder) < list_length(wcsb->uniqueOrder)) + return 1; + + return 0; +} + +/* * make_window_input_target * Generate appropriate PathTarget for initial input to WindowAgg nodes. * diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out index 562006a2b8..662d348653 100644 --- a/src/test/regress/expected/window.out +++ b/src/test/regress/expected/window.out @@ -504,9 +504,9 @@ SELECT sum(salary), FROM empsalary GROUP BY depname; sum | row_number | sum -------+------------+------- - 14600 | 3 | 14600 - 7400 | 2 | 22000 25100 | 1 | 47100 + 7400 | 2 | 22000 + 14600 | 3 | 14600 (3 rows) -- identical windows with different names @@ -2994,9 +2994,9 @@ SELECT sum(salary), row_number() OVER (ORDER BY depname), sum( FROM empsalary GROUP BY depname; sum | row_number | filtered_sum | depname -------+------------+--------------+----------- - 14600 | 3 | | sales - 7400 | 2 | 3500 | personnel 25100 | 1 | 22600 | develop + 7400 | 2 | 3500 | personnel + 14600 | 3 | | sales (3 rows) -- Test pushdown of quals into a subquery containing window functions @@ -3008,13 +3008,13 @@ SELECT * FROM min(salary) OVER (PARTITION BY depname || 'A', depname) depminsalary FROM empsalary) emp WHERE depname = 'sales'; - QUERY PLAN ---------------------------------------------------------------------- + QUERY PLAN +-------------------------------------------------------------------------- Subquery Scan on emp -> WindowAgg - -> Sort - Sort Key: (((empsalary.depname)::text || 'A'::text)) - -> WindowAgg + -> WindowAgg + -> Sort + Sort Key: (((empsalary.depname)::text || 'A'::text)) -> Seq Scan on empsalary Filter: ((depname)::text = 'sales'::text) (7 rows) @@ -3027,19 +3027,53 @@ SELECT * FROM min(salary) OVER (PARTITION BY depname) depminsalary FROM empsalary) emp WHERE depname = 'sales'; - QUERY PLAN ------------------------------------------------------------ + QUERY PLAN +------------------------------------------------------- Subquery Scan on emp Filter: ((emp.depname)::text = 'sales'::text) -> WindowAgg -> Sort - Sort Key: empsalary.depname + Sort Key: empsalary.enroll_date -> WindowAgg -> Sort - Sort Key: empsalary.enroll_date + Sort Key: empsalary.depname -> Seq Scan on empsalary (9 rows) +-- Test Sort node collapsing +EXPLAIN (COSTS OFF) +SELECT * FROM + (SELECT depname, + sum(salary) OVER (PARTITION BY depname order by empno) depsalary, + min(salary) OVER (PARTITION BY depname, empno order by enroll_date) depminsalary + FROM empsalary) emp +WHERE depname = 'sales'; + QUERY PLAN +---------------------------------------------------------------------- + Subquery Scan on emp + -> WindowAgg + -> WindowAgg + -> Sort + Sort Key: empsalary.empno, empsalary.enroll_date + -> Seq Scan on empsalary + Filter: ((depname)::text = 'sales'::text) +(7 rows) + +-- 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; + QUERY PLAN +------------------------------------------------------------- + WindowAgg + -> WindowAgg + -> Sort + Sort Key: depname, salary, enroll_date, empno + -> Seq Scan on empsalary +(5 rows) + -- cleanup DROP TABLE empsalary; -- test user-defined window function with named args and default args diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql index e2943a38f1..fc6d4cc903 100644 --- a/src/test/regress/sql/window.sql +++ b/src/test/regress/sql/window.sql @@ -892,6 +892,22 @@ SELECT * FROM FROM empsalary) emp WHERE depname = 'sales'; +-- Test Sort node collapsing +EXPLAIN (COSTS OFF) +SELECT * FROM + (SELECT depname, + sum(salary) OVER (PARTITION BY depname order by empno) depsalary, + min(salary) OVER (PARTITION BY depname, empno order by enroll_date) depminsalary + FROM empsalary) emp +WHERE depname = 'sales'; + +-- 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; + -- cleanup DROP TABLE empsalary; -- 2.11.1
Re: Avoid extra Sort nodes between WindowAggs when sorting can bereused
From
Daniel Gustafsson
Date:
> 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
>> 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)