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
From 8fb4b6188eda111bee2e47d3e85289064b428702 Mon Sep 17 00:00:00 2001
From: Ankit Kumar Pandey <itsanki...@gmail.com>
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
