On 09/01/23 03:48, David Rowley wrote:
On Mon, 9 Jan 2023 at 06:17, Ankit Kumar Pandey <itsanki...@gmail.com> wrote:
I have addressed all points 1-6 in the attached patch.
A few more things:
1. You're still using the 'i' variable in the foreach loop.
foreach_current_index() will work.
2. I think the "index" variable needs a better name. sort_pushdown_idx maybe.
Done these (1 & 2)
3. I don't think you need to set "index" on every loop. Why not just
set it to foreach_current_index(l) - 1; break;
Consider this query
EXPLAIN (COSTS OFF)
SELECT empno,
depname,
min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary,
sum(salary) OVER (PARTITION BY depname) depsalary,
count(*) OVER (ORDER BY enroll_date DESC) c
FROM empsalary
ORDER BY depname, empno, enroll_date;
Here, W1 = min(salary) OVER (PARTITION BY depname ORDER BY empno) W2 =
sum(salary) OVER (PARTITION BY depname)
W3 = count(*) OVER (ORDER BY enroll_date DESC)
(1,2,3 are winref).
activeWindows = [W3, W1, W2]
If we iterate from reverse and break at first occurrence, we will
break at W2 and add extra keys there, but what we want it to add
keys at W1 so that it gets spilled to W2 (as existing logic is designed to
carry over sorted cols first to last).
4. You're still setting orderby_pathkeys in the foreach loop. That's
already been set above and it won't have changed.
5. I don't think there's any need to check pathkeys_contained_in() in
the foreach loop anymore. With #3 the index will be -1 if the
optimisation cannot apply. You could likely also get rid of
try_sort_pushdown too and just make the condition "if
(sort_pushdown_idx == foreach_current_index(l))".
Done this.
Added pathkeys_contained_in as an assert, hope that's okay.
I'm a little unsure why there's still the is_sorted check there.
Shouldn't that always be false now that you're looping until the pathkeys
don't match in the foreach_reverse loop?
Removing is_sorted causes issue if there is matching pathkey which is
presorted
eg this case
-- Do not perform sort pushdown if column is presorted
CREATE INDEX depname_idx ON empsalary(depname);
SET enable_seqscan=0;
EXPLAIN (COSTS OFF)
SELECT empno,
min(salary) OVER (PARTITION BY depname) depminsalary
FROM empsalary
ORDER BY depname, empno;
We can move this to if (try_sort_pushdown) block but it looks to me bit
ugly.
Nevertheless, it make sense to have it here, sort_pushdown_index should
point to exact
window function which needs to be modified. Having extra check (for
is_sorted) in 2nd foreach loop
adds ambiguity if we don't add it in first check.
foreach_reverse(l, activeWindows)
{
WindowClause *wc = lfirst_node(WindowClause, l);
orderby_pathkeys =
make_pathkeys_for_sortclauses(root,root->parse->sortClause,root->processed_tlist);
window_pathkeys =
make_pathkeys_for_window(root,wc,root->processed_tlist);
is_sorted =
pathkeys_count_contained_in(window_pathkeys,path->pathkeys,&presorted_keys);
has_runcondition |= (wc->runCondition != NIL);
if (!pathkeys_contained_in(window_pathkeys, orderby_pathkeys) ||
has_runcondition)
break;
if(!is_sorted)
sort_pushdown_idx = foreach_current_index(l);
}
Tests passes on this so logically it is ok.
Correct me if I'm wrong as I've not tested, but I think the new code
in the foreach loop can just become:
if (sort_pushdown_idx == foreach_current_index(l))
{
Assert(!is_sorted);
window_pathkeys = orderby_pathkeys;
is_sorted = pathkeys_count_contained_in(window_pathkeys,
path->pathkeys, &presorted_keys);
}
Depending on where we have is_sorted (as mentioned above) it looks a lot
like you mentioned.
Also, we can add Assert(pathkeys_contained_in(window_pathkeys,
orderby_pathkeys))
I have one doubt regarding runCondition, do we only need to ensure
that window function which has subset sort clause of main query should
not have runCondition or none of the window functions should not contain
runCondition? I have gone with later case but wanted to clarify.
Actually, maybe it's ok just to check the top-level WindowClause for
runConditions. It's only that one that'll filter rows. That probably
simplifies the code quite a bit. Lower-level runConditions only serve
to halt the evaluation of WindowFuncs when the runCondition is no
longer met.
Okay, then this approach makes sense.
hmm, perhaps the Limit would have to be put between the WindowAgg and
Sort for it to work. Maybe that's more complexity than it's worth.
Yes, not specific to this change. It is more around allowing top-N sort in
window functions (in general). Once we have it there, then this could be
taken care of.
I have attached patch which fixes 1 & 2 and rearrange is_sorted.
Point #3 needs to be resolved (and perhaps another way to handle is_sorted)
Thanks,
--
Regards,
Ankit Kumar Pandey
diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 000d757bdd..7e7f95d929 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -4423,6 +4423,14 @@ create_one_window_path(PlannerInfo *root,
PathTarget *window_target;
ListCell *l;
List *topqual = NIL;
+ bool has_runcondition = false;
+
+ List *window_pathkeys;
+ List *orderby_pathkeys = NIL;
+ int sort_pushdown_idx = -1;
+ int presorted_keys;
+ bool is_sorted;
+ bool try_sort_pushdown = false;
/*
* Since each window clause could require a different sort order, we stack
@@ -4441,12 +4449,43 @@ create_one_window_path(PlannerInfo *root,
*/
window_target = input_target;
+ try_sort_pushdown = (root->parse->distinctClause == NIL &&
+ root->parse->sortClause != NIL &&
+ root->parse->limitCount == NULL &&
+ !contain_window_function((Node *) get_sortgrouplist_exprs(root->parse->sortClause,
+ root->processed_tlist)));
+
+
+ if (try_sort_pushdown)
+ {
+ /*
+ * Search for the window function whose path keys are
+ * subset of orderby_path keys, this allows us to perform
+ * order by pushdown from this position of window function onwards
+ */
+ foreach_reverse(l, activeWindows)
+ {
+ WindowClause *wc = lfirst_node(WindowClause, l);
+ orderby_pathkeys = make_pathkeys_for_sortclauses(root,
+ root->parse->sortClause,
+ root->processed_tlist);
+ window_pathkeys = make_pathkeys_for_window(root,
+ wc,
+ root->processed_tlist);
+ is_sorted = pathkeys_count_contained_in(window_pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+ has_runcondition |= (wc->runCondition != NIL);
+ if (!pathkeys_contained_in(window_pathkeys, orderby_pathkeys) || has_runcondition)
+ break;
+ if (!is_sorted)
+ sort_pushdown_idx = foreach_current_index(l);
+ }
+ }
+
foreach(l, activeWindows)
{
WindowClause *wc = lfirst_node(WindowClause, l);
- List *window_pathkeys;
- int presorted_keys;
- bool is_sorted;
bool topwindow;
window_pathkeys = make_pathkeys_for_window(root,
@@ -4457,6 +4496,30 @@ create_one_window_path(PlannerInfo *root,
path->pathkeys,
&presorted_keys);
+ /*
+ * If not sorted already and the query has an ORDER BY clause, then we
+ * try to push the entire ORDER BY below the final WindowAgg. We
+ * don't do this when the query has a DISTINCT clause as the planner
+ * might opt to do a Hash Aggregate and spoil our efforts here. We
+ * also can't do this when the ORDER BY contains any WindowFuncs as we
+ * obviously can't sort something that's yet to be evaluated. We also
+ * don't bother with this when there is a WindowClauses with a
+ * runCondition as those can reduce the number of rows to sort in the
+ * ORDER BY and we don't want add complexity to the WindowAgg sort if
+ * the final ORDER BY sort is going to have far fewer rows to sort.
+ * For the same reason, don't bother if the query has a LIMIT clause.
+ */
+ if (foreach_current_index(l) == sort_pushdown_idx)
+ {
+ Assert(!is_sorted);
+ Assert(pathkeys_contained_in(window_pathkeys, orderby_pathkeys));
+
+ window_pathkeys = orderby_pathkeys;
+ is_sorted = pathkeys_count_contained_in(window_pathkeys,
+ path->pathkeys,
+ &presorted_keys);
+ }
+
/* Sort if necessary */
if (!is_sorted)
{
diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h
index 529a382d28..82d108f672 100644
--- a/src/include/nodes/pg_list.h
+++ b/src/include/nodes/pg_list.h
@@ -378,6 +378,20 @@ lnext(const List *l, const ListCell *c)
(cell = NULL, false); \
cell##__state.i++)
+/*
+ * foreach_reverse -
+ * a convenience macro for looping through a list in reverse
+ *
+ * This is equivalent to foreach, only in reverse
+ */
+#define foreach_reverse(cell, lst) \
+ for (ForEachState cell##__state = {(lst), cell##__state.l->length-1}; \
+ (cell##__state.l != NIL && \
+ cell##__state.i >= 0) ? \
+ (cell = &cell##__state.l->elements[cell##__state.i], true) : \
+ (cell = NULL, false); \
+ cell##__state.i--)
+
/*
* foreach_delete_current -
* delete the current list element from the List associated with a
diff --git a/src/test/regress/expected/window.out b/src/test/regress/expected/window.out
index 90e89fb5b6..d83fea8091 100644
--- a/src/test/regress/expected/window.out
+++ b/src/test/regress/expected/window.out
@@ -3982,7 +3982,194 @@ ORDER BY depname, empno;
-> Seq Scan on empsalary
(11 rows)
+-- Do not perform sort pushdown if column is presorted
+CREATE INDEX depname_idx ON empsalary(depname);
+SET enable_seqscan=0;
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ min(salary) OVER (PARTITION BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+ QUERY PLAN
+-------------------------------------------------------
+ Incremental Sort
+ Sort Key: depname, empno
+ Presorted Key: depname
+ -> WindowAgg
+ -> Index Scan using depname_idx on empsalary
+(5 rows)
+
+-- Do perform sort pushdown if columns are only partially sorted
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ min(salary) OVER (PARTITION BY depname, empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+ QUERY PLAN
+-------------------------------------------------------
+ WindowAgg
+ -> Incremental Sort
+ Sort Key: depname, empno, enroll_date
+ Presorted Key: depname
+ -> Index Scan using depname_idx on empsalary
+(5 rows)
+
+DROP INDEX depname_idx;
+RESET enable_seqscan;
RESET enable_hashagg;
+-- If window function's ORDER BY is subset of QUERY's ORDER BY, sort as per as
+-- QUERY's ORDER BY to save additional sorting in the end
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (ORDER BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+ QUERY PLAN
+-----------------------------------
+ WindowAgg
+ -> Sort
+ Sort Key: depname, empno
+ -> Seq Scan on empsalary
+(4 rows)
+
+-- Same as above, but PARTITION BY clause is included as well
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+ QUERY PLAN
+-----------------------------------------------
+ WindowAgg
+ -> Sort
+ Sort Key: depname, empno, enroll_date
+ -> Seq Scan on empsalary
+(4 rows)
+
+-- Negation of above, when sort optimization is not needed to be performed
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY empno, enroll_date;
+ QUERY PLAN
+-----------------------------------------
+ Sort
+ Sort Key: empno, enroll_date
+ -> WindowAgg
+ -> Sort
+ Sort Key: depname, empno
+ -> Seq Scan on empsalary
+(6 rows)
+
+-- ORDER BY's in multiple Window functions can be combined into one
+-- if they are subset of QUERY's ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary,
+ sum(salary) OVER (PARTITION BY depname) depsalary,
+ count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+ QUERY PLAN
+------------------------------------------------------
+ WindowAgg
+ -> WindowAgg
+ -> Sort
+ Sort Key: depname, empno, enroll_date
+ -> WindowAgg
+ -> Sort
+ Sort Key: enroll_date DESC
+ -> Seq Scan on empsalary
+(8 rows)
+
+-- order of window function shouldn't affect query's ORDER BY pushdown
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ count(*) OVER (ORDER BY enroll_date DESC) c,
+ sum(salary) OVER (PARTITION BY depname) depsalary,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+ QUERY PLAN
+------------------------------------------------------
+ WindowAgg
+ -> WindowAgg
+ -> Sort
+ Sort Key: depname, empno, enroll_date
+ -> WindowAgg
+ -> Sort
+ Sort Key: enroll_date DESC
+ -> Seq Scan on empsalary
+(8 rows)
+
+-- SORT OPTIMIZATION (as in cases above) is not needed to be performed
+-- in cases, as mentioned below.
+-- Case #1: When distinct clause is included
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname) depminsalary,
+ sum(salary) OVER (PARTITION BY depname) depsalary,
+ count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno;
+ QUERY PLAN
+-------------------------------------------------------------------------------------------------------
+ Unique
+ -> Sort
+ Sort Key: depname, empno, (min(salary) OVER (?)), (sum(salary) OVER (?)), (count(*) OVER (?))
+ -> WindowAgg
+ -> Sort
+ Sort Key: depname
+ -> WindowAgg
+ -> Sort
+ Sort Key: enroll_date DESC
+ -> Seq Scan on empsalary
+(10 rows)
+
+-- Case #2: When Limit clause is specified
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY empno) depminsalary,
+ sum(salary) OVER (PARTITION BY empno) depsalary
+FROM empsalary
+ORDER BY empno, depname LIMIT 1;
+ QUERY PLAN
+-----------------------------------------------
+ Limit
+ -> Incremental Sort
+ Sort Key: empno, depname
+ Presorted Key: empno
+ -> WindowAgg
+ -> Sort
+ Sort Key: empno
+ -> Seq Scan on empsalary
+(8 rows)
+
+-- Case #3: When ORDER BY contains any WindowFuncs
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ row_number() over (PARTITION BY empno) esalary
+FROM empsalary
+ORDER BY empno, esalary;
+ QUERY PLAN
+--------------------------------------------
+ Incremental Sort
+ Sort Key: empno, (row_number() OVER (?))
+ Presorted Key: empno
+ -> WindowAgg
+ -> Sort
+ Sort Key: empno
+ -> Seq Scan on empsalary
+(7 rows)
+
-- Test Sort node reordering
EXPLAIN (COSTS OFF)
SELECT
diff --git a/src/test/regress/sql/window.sql b/src/test/regress/sql/window.sql
index b7bd0a83da..e989e93737 100644
--- a/src/test/regress/sql/window.sql
+++ b/src/test/regress/sql/window.sql
@@ -1324,8 +1324,102 @@ SELECT DISTINCT
FROM empsalary
ORDER BY depname, empno;
+-- Do not perform sort pushdown if column is presorted
+CREATE INDEX depname_idx ON empsalary(depname);
+SET enable_seqscan=0;
+
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ min(salary) OVER (PARTITION BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+
+-- Do perform sort pushdown if columns are only partially sorted
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ min(salary) OVER (PARTITION BY depname, empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+DROP INDEX depname_idx;
+RESET enable_seqscan;
RESET enable_hashagg;
+-- If window function's ORDER BY is subset of QUERY's ORDER BY, sort as per as
+-- QUERY's ORDER BY to save additional sorting in the end
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (ORDER BY depname) depminsalary
+FROM empsalary
+ORDER BY depname, empno;
+
+-- Same as above, but PARTITION BY clause is included as well
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+-- Negation of above, when sort optimization is not needed to be performed
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY empno, enroll_date;
+
+-- ORDER BY's in multiple Window functions can be combined into one
+-- if they are subset of QUERY's ORDER BY
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary,
+ sum(salary) OVER (PARTITION BY depname) depsalary,
+ count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+-- order of window function shouldn't affect query's ORDER BY pushdown
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ count(*) OVER (ORDER BY enroll_date DESC) c,
+ sum(salary) OVER (PARTITION BY depname) depsalary,
+ min(salary) OVER (PARTITION BY depname ORDER BY empno) depminsalary
+FROM empsalary
+ORDER BY depname, empno, enroll_date;
+
+-- SORT OPTIMIZATION (as in cases above) is not needed to be performed
+-- in cases, as mentioned below.
+
+-- Case #1: When distinct clause is included
+EXPLAIN (COSTS OFF)
+SELECT DISTINCT empno,
+ depname,
+ min(salary) OVER (PARTITION BY depname) depminsalary,
+ sum(salary) OVER (PARTITION BY depname) depsalary,
+ count(*) OVER (ORDER BY enroll_date DESC) c
+FROM empsalary
+ORDER BY depname, empno;
+
+-- Case #2: When Limit clause is specified
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ depname,
+ min(salary) OVER (PARTITION BY empno) depminsalary,
+ sum(salary) OVER (PARTITION BY empno) depsalary
+FROM empsalary
+ORDER BY empno, depname LIMIT 1;
+
+-- Case #3: When ORDER BY contains any WindowFuncs
+EXPLAIN (COSTS OFF)
+SELECT empno,
+ row_number() over (PARTITION BY empno) esalary
+FROM empsalary
+ORDER BY empno, esalary;
+
-- Test Sort node reordering
EXPLAIN (COSTS OFF)
SELECT
--
2.37.2
