Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> On 13 Sep 2018, at 19:50, Andrew Gierth 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
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
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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
Andrew Gierth 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> "Tom" == Tom Lane 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)
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
Andrew Gierth writes: > "Tom" == Tom Lane 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> "Tom" == Tom Lane 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)
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
Andrew Gierth 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> On 12 Sep 2018, at 22:15, Andrew Gierth 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
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 be reused
On Sat, Jul 28, 2018 at 4:12 AM, Alexander Kuzmenkov 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> On 27 Jul 2018, at 21:12, Alexander Kuzmenkov > 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
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
>From e6006da62d7d4c0c54750260e864e52e93e2dba9 Mon Sep 17 00:00:00 2001
From: Daniel Gustafsson
Date: Tue, 12 Jun 2018 14:13:48 +0200
Subject: [PATCH] Order windows on partition/ordering prefix to reuse Sort
nodes
By ordering the Windows on partitioning/ordering prefix, the result
from Sort nodes can be reused by multiple WindowAgg nodes and thus
we can avoid Sort nodes.
---
src/backend/optimizer/plan/planner.c | 126 ++-
src/test/regress/expected/window.out | 60 +
src/test/regress/sql/window.sql | 16 +
3 files changed, 144 insertions(+), 58 deletions(-)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index df4ec44..299149f 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 */
+} WindowClauseSortNode;
+
/* 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);
/*
@@ -5253,68 +5265,92 @@ postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
static List *
select_active_windows(PlannerInfo *root, WindowFuncLists *wflists)
{
- List *result;
- List *actives;
+ List *result = NIL;
ListCell *lc;
+ WindowClauseSortNode *actives = palloc(sizeof(WindowClauseSortNode)
+ * list_length(root->parse->windowClause));
+ int nActive = 0;
/* First, make a list of the active windows */
- actives = NIL;
- foreach(lc, root->parse->windowClause)
+ foreach (lc, root->parse->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;
+ 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).
- *
- * 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);
+ * Sort windows by their
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> On 3 Jul 2018, at 12:24, Masahiko Sawada 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 window_prefix_sort-v5.patch Description: Binary data
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
On Tue, Jul 3, 2018 at 6:19 AM, Daniel Gustafsson wrote: >> On 2 Jul 2018, at 14:01, Masahiko Sawada 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 be reused
> On 2 Jul 2018, at 14:01, Masahiko Sawada 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 window_prefix_sort-v4.patch Description: Binary data
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
On Mon, Jul 2, 2018 at 5:25 PM, Daniel Gustafsson wrote: >> On 26 Jun 2018, at 17:11, Alexander Kuzmenkov >> 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
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
> On 26 Jun 2018, at 17:11, Alexander Kuzmenkov > 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 window_prefix_sort-v3.patch Description: Binary data
Re: Avoid extra Sort nodes between WindowAggs when sorting can be reused
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 be reused
> On 30 May 2018, at 18:19, Daniel Gustafsson 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 window_prefix_sort-v2.patch Description: Binary data
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 window_prefix_sort.patch Description: Binary data
