public inbox for [email protected]
help / color / mirror / Atom feedFrom: Ankit Kumar Pandey <[email protected]>
To: David Rowley <[email protected]>
Cc: pghackers <[email protected]>
Cc: Vik Fearing <[email protected]>
Subject: Re: Todo: Teach planner to evaluate multiple windows in the optimal order
Date: Fri, 6 Jan 2023 18:41:33 +0530
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
<CAApHDvp=r1LnEKCmWCYaruMPL-jP4j_sdc8yeFYwaDT1ac5GsQ@mail.gmail.com>
<[email protected]>
<CAApHDvq=g2=ny59f1bvwRVvupsgPHK-KjLPBsSL25fVuGZ4idQ@mail.gmail.com>
<[email protected]>
<[email protected]>
<[email protected]>
<CAApHDvruS-3gG_KYXPb_=Um_TfUXi+G4o7VyBVbChTjThXF2yA@mail.gmail.com>
<[email protected]>
Sorry if multiple mails has been sent for this.
> On 05/01/23 12:53, David Rowley wrote:
>>
>> We *can* reuse Sorts where a more strict or equivalent sort order is
>> available. The question is how do we get the final WindowClause to do
>> something slightly more strict to save having to do anything for the
>> ORDER BY. One way you might think would be to adjust the
>> WindowClause's orderClause to add the additional clauses, but that
>> cannot be done because that would cause are_peers() in nodeWindowAgg.c
>> to not count some rows as peers when they maybe should be given a less
>> strict orderClause in the WindowClause.
I attempted this in attached patch.
#1. No op case
------------------------------------------In patched
version-----------------------------------------------
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd order by a;
QUERY PLAN
------------------------------------------
WindowAgg
-> Sort
Sort Key: a, b, c
-> WindowAgg
-> Sort
Sort Key: b
-> Seq Scan on abcd
(7 rows)
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd;
QUERY PLAN
------------------------------------------
WindowAgg
-> Sort
Sort Key: b
-> WindowAgg
-> Sort
Sort Key: a, b, c
-> Seq Scan on abcd
(7 rows)
----------------------------------------------In
master--------------------------------------------------------
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd order by a;
QUERY PLAN
------------------------------------------
WindowAgg
-> Sort
Sort Key: a, b, c
-> WindowAgg
-> Sort
Sort Key: b
-> Seq Scan on abcd
(7 rows)
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd;
QUERY PLAN
------------------------------------------
WindowAgg
-> Sort
Sort Key: b
-> WindowAgg
-> Sort
Sort Key: a, b, c
-> Seq Scan on abcd
(7 rows)
No change between patched version and master.
2. In case where optimization can happen
----------------------------In patched
version-------------------------------------------------------
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a) FROM abcd order by a,b;
QUERY PLAN
------------------------------------------
WindowAgg
-> Sort
Sort Key: a, b
-> WindowAgg
-> Sort
Sort Key: b
-> Seq Scan on abcd
(7 rows)
explain (costs off) SELECT rank() OVER (ORDER BY a), count(*) OVER
(ORDER BY b), count(*) OVER (PARTITION BY a ORDER BY b) FROM abcd order
by a,b,c,d;
QUERY PLAN
------------------------------------------------
WindowAgg
-> WindowAgg
-> Sort
Sort Key: a, b, c, d
-> WindowAgg
-> Sort
Sort Key: b
-> Seq Scan on abcd
(8 rows)
-------------------------------------------In
master--------------------------------------------------------
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a) FROM abcd order by a,b;
QUERY PLAN
------------------------------------------------
Incremental Sort
Sort Key: a, b
Presorted Key: a
-> WindowAgg
-> Sort
Sort Key: a
-> WindowAgg
-> Sort
Sort Key: b
-> Seq Scan on abcd
(10 rows)
explain (costs off) SELECT rank() OVER (ORDER BY a), count(*) OVER
(ORDER BY b), count(*) OVER (PARTITION BY a ORDER BY b) FROM abcd order
by a,b,c,d;
QUERY PLAN
------------------------------------------------------
Incremental Sort
Sort Key: a, b, c, d
Presorted Key: a, b
-> WindowAgg
-> WindowAgg
-> Sort
Sort Key: a, b
-> WindowAgg
-> Sort
Sort Key: b
-> Seq Scan on abcd
(11 rows)
Patched version removes few sorts.
Regression tests all passed so it is not breaking anything existing.
We don't have any tests for verifying sorting plan in window functions
(which would have failed, if present).
Please let me know any feedbacks (I have added some my own concerns in
the comments)
Thanks
--
Regards,
Ankit Kumar Pandey
Attachments:
[text/x-patch] v1-0002-Teach-planner-to-optimize-sorting-operations-for-win.patch (3.5K, ../[email protected]/2-v1-0002-Teach-planner-to-optimize-sorting-operations-for-win.patch)
download | inline diff:
From 8fb4b6188eda111bee2e47d3e85289064b428702 Mon Sep 17 00:00:00 2001
From: Ankit Kumar Pandey <[email protected]>
Date: Fri, 6 Jan 2023 14:30:38 +0530
Subject: [PATCH] Teach planner to optimize sorting operations for window
function
Additional sort for root's order by can be optimized if sorting for
extra columns are performed while sorting for window functions (if sort
clause of window functions are subset of root's sort clause).
---
src/backend/optimizer/plan/planner.c | 70 ++++++++++++++++++++++++++++
1 file changed, 70 insertions(+)
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index d6ba7589f3..048651dffe 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4448,11 +4448,81 @@ create_one_window_path(PlannerInfo *root,
int presorted_keys;
bool is_sorted;
bool topwindow;
+ List *window_sortclauses;
window_pathkeys = make_pathkeys_for_window(root,
wc,
root->processed_tlist);
+
+ /*
+ * Add aditional sorting clause from
+ * root's order by to window's order by clause,
+ * if they are compatible. This will save additional
+ * sorting at the end. This should happen only if sort
+ * clause in window function is subset of root's order by.
+ * XXX Ideally this check need to be performed on final
+ * window function but if I add condition here, for final
+ * window function, pathkeys would have been same as root's
+ * order by but for others, it would have been lesser number
+ * (if they are subset). So, system would ignore extra sort
+ * and take it as first step (where final function was expected
+ * to be), do regular sort as in master.
+ * Try adding (foreach_current_index(l) == list_length(activeWindows) - 1)
+ * in if condition which check if window_sortclause is subset lengthwise
+ */
+ window_sortclauses = list_concat_copy(wc->partitionClause, wc->orderClause);
+
+ if(list_length(window_sortclauses) < list_length(root->parse->sortClause))
+ {
+ ListCell *wsc;
+ ListCell *sc;
+ bool should_prepend = true; /* wishful thinking */
+
+ /*
+ * Same as in make_pathkeys_for_window
+ * for sorting, partition clause is taken first
+ */
+ window_sortclauses = list_concat_copy(wc->partitionClause, wc->orderClause);
+
+ /*
+ * Sort clauses of root can be prepended if and only if
+ * sort clause of window function is subset of root's sort clause
+ * XXX is there better way to find this?
+ */
+ forboth(wsc, window_sortclauses, sc, root->parse->sortClause)
+ {
+ SortGroupClause *window_sortclause = (SortGroupClause*) lfirst(wsc);
+ SortGroupClause *sortclause = (SortGroupClause*) lfirst(sc);
+ if (window_sortclause->tleSortGroupRef != sortclause->tleSortGroupRef)
+ {
+ should_prepend = false;
+ break;
+ }
+ }
+
+
+ /*
+ * Override window path key defined by make_pathkeys_for_window
+ * XXX since we are overriding make_pathkeys_for_window, it is
+ * a wasteful call in critical path. Should we call make_pathkeys_for_window
+ * after this function?
+ */
+ if (should_prepend)
+ {
+ /*
+ * add root's sort clauses in the end
+ */
+ window_sortclauses = list_concat_unique(window_sortclauses,
+ root->parse->sortClause);
+ window_pathkeys = make_pathkeys_for_sortclauses(root,
+ window_sortclauses,
+ root->processed_tlist);
+
+ }
+
+ }
+
is_sorted = pathkeys_count_contained_in(window_pathkeys,
path->pathkeys,
&presorted_keys);
--
2.37.2
view thread (60+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected], [email protected], [email protected], [email protected]
Subject: Re: Todo: Teach planner to evaluate multiple windows in the optimal order
In-Reply-To: <[email protected]>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox