On Wed, 12 Oct 2022 at 16:33, Vik Fearing <v...@postgresfriends.org> wrote:
> Per spec, the ROW_NUMBER() window function is not even allowed to have a
> frame specified.
>
> b) The window framing clause of WDX shall not be present.
>
> Also, the specification for ROW_NUMBER() is:
>
> f) ROW_NUMBER() OVER WNS is equivalent to the <window function>:
>
> COUNT (*) OVER (WNS1 ROWS UNBOUNDED PRECEDING)
>
>
> So I don't think we need to test for anything at all and can
> indiscriminately add or replace the frame with ROWS UNBOUNDED PRECEDING.
Thanks for digging that out.
Just above that I see:
RANK() OVER WNS is equivalent to:
( COUNT (*) OVER (WNS1 RANGE UNBOUNDED PRECEDING)
- COUNT (*) OVER (WNS1 RANGE CURRENT ROW) + 1 )
and
DENSE_RANK() OVER WNS is equivalent to the <window function>:
COUNT (DISTINCT ROW ( VE1, ..., VEN ) )
OVER (WNS1 RANGE UNBOUNDED PRECEDING)
So it looks like the same can be done for rank() and dense_rank() too.
I've added support for those in the attached.
This also got me thinking that maybe we should be a bit more generic
with the support function node tag name. After looking at the
nodeWindowAgg.c code for a while, I wondered if we might want to add
some optimisations in the future that makes WindowAgg not bother
storing tuples for row_number(), rank() and dense_rank(). That might
save a bit of overhead from the tuple store. I imagined that we'd
want to allow the expansion of this support request so that the
support function could let the planner know if any tuples will be
accessed by the window function or not. The
SupportRequestWFuncOptimizeFrameOpts name didn't seem very fitting for
that so I adjusted it to become SupportRequestOptimizeWindowClause
instead.
The updated patch is attached.
David
diff --git a/src/backend/optimizer/plan/planner.c
b/src/backend/optimizer/plan/planner.c
index 5d0fd6e072..74a8bafd8b 100644
--- a/src/backend/optimizer/plan/planner.c
+++ b/src/backend/optimizer/plan/planner.c
@@ -38,6 +38,7 @@
#include "miscadmin.h"
#include "nodes/makefuncs.h"
#include "nodes/nodeFuncs.h"
+#include "nodes/supportnodes.h"
#ifdef OPTIMIZER_DEBUG
#include "nodes/print.h"
#endif
@@ -207,6 +208,8 @@ static PathTarget *make_partial_grouping_target(PlannerInfo
*root,
PathTarget *grouping_target,
Node *havingQual);
static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
+static void optimize_window_clauses(PlannerInfo *root,
+
WindowFuncLists *wflists);
static List *select_active_windows(PlannerInfo *root, WindowFuncLists
*wflists);
static PathTarget *make_window_input_target(PlannerInfo *root,
PathTarget *final_target,
@@ -1422,7 +1425,16 @@ grouping_planner(PlannerInfo *root, double
tuple_fraction)
wflists = find_window_functions((Node *)
root->processed_tlist,
list_length(parse->windowClause));
if (wflists->numWindowFuncs > 0)
+ {
+ /*
+ * See if any modifications can be made to each
WindowClause
+ * to allow the executor to execute the
WindowFuncs more
+ * quickly.
+ */
+ optimize_window_clauses(root, wflists);
+
activeWindows = select_active_windows(root,
wflists);
+ }
else
parse->hasWindowFuncs = false;
}
@@ -5391,6 +5403,85 @@ postprocess_setop_tlist(List *new_tlist, List
*orig_tlist)
return new_tlist;
}
+/*
+ * optimize_window_clauses
+ * Call each WindowFunc's prosupport function to see if we're able
to
+ * make any adjustments to any of the WindowClause's so that the
executor
+ * can execute the window functions in a more optimal way.
+ *
+ * Currently we only allow adjustments to the WindowClause's frameOptions. We
+ * may allow more things to be done here in the future.
+ */
+static void
+optimize_window_clauses(PlannerInfo *root, WindowFuncLists *wflists)
+{
+ List *windowClause = root->parse->windowClause;
+ ListCell *lc;
+
+ foreach(lc, windowClause)
+ {
+ WindowClause *wc = lfirst_node(WindowClause, lc);
+ ListCell *lc2;
+ int optimizedFrameOptions = 0;
+
+ Assert(wc->winref <= wflists->maxWinRef);
+
+ /* skip any WindowClauses that have no WindowFuncs */
+ if (wflists->windowFuncs[wc->winref] == NIL)
+ continue;
+
+ foreach(lc2, wflists->windowFuncs[wc->winref])
+ {
+ SupportRequestOptimizeWindowClause req;
+ SupportRequestOptimizeWindowClause *res;
+ WindowFunc *wfunc = lfirst_node(WindowFunc, lc2);
+ Oid prosupport;
+
+ prosupport = get_func_support(wfunc->winfnoid);
+
+ /* Check if there's a support function for 'wfunc' */
+ if (!OidIsValid(prosupport))
+ break; /* can't optimize this
WindowClause */
+
+ req.type = T_SupportRequestOptimizeWindowClause;
+ req.window_clause = wc;
+ req.window_func = wfunc;
+ req.frameOptions = wc->frameOptions;
+
+ /* call the support function */
+ res = (SupportRequestOptimizeWindowClause *)
+ DatumGetPointer(OidFunctionCall1(prosupport,
+ PointerGetDatum(&req)));
+
+ /*
+ * Skip to next WindowClause if the support function
does not
+ * support this request type.
+ */
+ if (res == NULL)
+ break;
+
+ /*
+ * Save these frameOptions for the first WindowFunc for
this
+ * WindowClause.
+ */
+ if (foreach_current_index(lc2) == 0)
+ optimizedFrameOptions = res->frameOptions;
+
+ /*
+ * On subsequent WindowFuncs, if the frameOptions are
not the same
+ * then we're unable to optimize the frameOptions for
this
+ * WindowClause.
+ */
+ else if (optimizedFrameOptions != res->frameOptions)
+ break; /* skip to the next
WindowClause, if any */
+ }
+
+ /* adjust the frameOptions if all WindowFunc's agree that it's
ok */
+ if (lc2 == NULL)
+ wc->frameOptions = optimizedFrameOptions;
+ }
+}
+
/*
* select_active_windows
* Create a list of the "active" window clauses (ie, those
referenced
diff --git a/src/backend/utils/adt/windowfuncs.c
b/src/backend/utils/adt/windowfuncs.c
index 596564fa15..3bf90813cf 100644
--- a/src/backend/utils/adt/windowfuncs.c
+++ b/src/backend/utils/adt/windowfuncs.c
@@ -107,6 +107,23 @@ window_row_number_support(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(req);
}
+ if (IsA(rawreq, SupportRequestOptimizeWindowClause))
+ {
+ SupportRequestOptimizeWindowClause *req =
(SupportRequestOptimizeWindowClause *) rawreq;
+
+ /*
+ * The frame options can always become "ROWS BETWEEN UNBOUNDED
+ * PRECEDING AND CURRENT ROW". row_number() always just
increments
+ * by 1 with each row in the partition. Using ROWS instead of
RANGE
+ * saves effort during execution.
+ */
+ req->frameOptions = (FRAMEOPTION_ROWS |
+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
+
FRAMEOPTION_END_CURRENT_ROW);
+
+ PG_RETURN_POINTER(req);
+ }
+
PG_RETURN_POINTER(NULL);
}
@@ -149,6 +166,26 @@ window_rank_support(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(req);
}
+ if (IsA(rawreq, SupportRequestOptimizeWindowClause))
+ {
+ SupportRequestOptimizeWindowClause *req =
(SupportRequestOptimizeWindowClause *) rawreq;
+
+ /*
+ * rank() is coded in such a way that it returns "(COUNT (*)
OVER
+ *(<opt> RANGE UNBOUNDED PRECEDING) - COUNT (*) OVER (<opt>
RANGE
+ * CURRENT ROW) + 1 )" regardless of the frame options. We'll
set the
+ * frame options to "ROWS BETWEEN UNBOUNDED PRECEDING AND
CURRENT ROW"
+ * so they agree with what window_row_number_support()
optimized the
+ * frame options to be. Using ROWS instead of RANGE saves
effort
+ * during execution.
+ */
+ req->frameOptions = (FRAMEOPTION_ROWS |
+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
+
FRAMEOPTION_END_CURRENT_ROW);
+
+ PG_RETURN_POINTER(req);
+ }
+
PG_RETURN_POINTER(NULL);
}
@@ -190,6 +227,22 @@ window_dense_rank_support(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(req);
}
+ if (IsA(rawreq, SupportRequestOptimizeWindowClause))
+ {
+ SupportRequestOptimizeWindowClause *req =
(SupportRequestOptimizeWindowClause *) rawreq;
+
+ /*
+ * Like window_rank(), window_dense_rank() is also unaffected
by the
+ * frame options. Here we just set them to match what's done
for the
+ * row_number() and rank() window functions.
+ */
+ req->frameOptions = (FRAMEOPTION_ROWS |
+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
+
FRAMEOPTION_END_CURRENT_ROW);
+
+ PG_RETURN_POINTER(req);
+ }
+
PG_RETURN_POINTER(NULL);
}
diff --git a/src/include/nodes/supportnodes.h b/src/include/nodes/supportnodes.h
index 9fcbc39949..b446125b2b 100644
--- a/src/include/nodes/supportnodes.h
+++ b/src/include/nodes/supportnodes.h
@@ -299,4 +299,48 @@ typedef struct SupportRequestWFuncMonotonic
MonotonicFunction monotonic;
} SupportRequestWFuncMonotonic;
+/*
+ * Some WindowFunc behavior might not be affected by certain variations in
+ * the WindowClause's frameOptions. For example, row_number() is coded in
+ * such a way that the frame options don't change the returned row number.
+ * nodeWindowAgg.c will have less work to do if the ROWS option is used
+ * instead of the RANGE option as no check needs to be done for peer rows.
+ * Since RANGE is included in the default frame options, window functions
+ * such as row_number() might want to change that to ROW.
+ *
+ * Here we allow a WindowFunc's support function to determine which, if
+ * anything, can be changed about the WindowClause which the WindowFunc
+ * belongs to. Currently only the frameOptions can be modified. However,
+ * we may want to allow more optimizations in the future.
+ *
+ * The support function is responsible for ensuring the optimized version of
+ * the frameOptions doesn't affect the result of the window function. The
+ * planner is responsible for only changing the frame options when all
+ * WindowFuncs using this particular WindowClause agree on what the optimized
+ * version of the frameOptions are. If a particular WindowFunc being used
+ * does not have a support function then the planner will not make any changes
+ * to the WindowClause's frameOptions.
+ *
+ * 'window_func' and 'window_clause' are set by the planner before calling the
+ * support function so that the support function has these fields available.
+ * These may be required in order to determine which optimizations are
+ * possible.
+ *
+ * 'frameOptions' is set by the planner to WindowClause.frameOptions. The
+ * support function must only adjust this if optimizations are possible for
+ * the given WindowFunc.
+ */
+typedef struct SupportRequestOptimizeWindowClause
+{
+ NodeTag type;
+
+ /* Input fields: */
+ WindowFunc *window_func; /* Pointer to the window function data
*/
+ struct WindowClause *window_clause; /* Pointer to the window clause
data */
+
+ /* Input/Output fields: */
+ int frameOptions; /* New frameOptions, or left
untouched if no
+ *
optimizations are possible. */
+} SupportRequestOptimizeWindowClause;
+
#endif /* SUPPORTNODES_H */
