Over on [1], Erwin mentions that row_number() over (ORDER BY ... ROWS
UNBOUNDED PRECEDING) is substantially faster than the default RANGE
UNBOUNDED PRECEDING WindowClause options. The difference between
these options are that nodeWindowAgg.c checks for peer rows for RANGE
but not for ROWS. That would make a difference for many of our
built-in window and aggregate functions, but row_number() does not
really care.
To quantify the performance difference, take the following example:
create table ab (a int, b int) ;
insert into ab
select x,y from generate_series(1,1000)x,generate_series(1,1000)y;
create index on ab(a,b);
-- range unbounded (the default)
explain (analyze, costs off, timing off)
select a,b from (select a,b,row_number() over (partition by a order by
a range unbounded preceding) rn from ab) ab where rn <= 1;
QUERY PLAN
---------------------------------------------------------------------------------------
Subquery Scan on ab (actual rows=1000 loops=1)
-> WindowAgg (actual rows=1000 loops=1)
Run Condition: (row_number() OVER (?) <= 1)
-> Index Only Scan using ab_a_b_idx on ab ab_1 (actual
rows=1000000 loops=1)
Heap Fetches: 1000000
Planning Time: 0.091 ms
Execution Time: 336.172 ms
(7 rows)
If that were switched to use ROWS UNBOUNDED PRECEDING then the
executor would not have to check for peer rows in the window frame.
explain (analyze, costs off, timing off)
select a,b from (select a,b,row_number() over (partition by a order by
a rows unbounded preceding) rn from ab) ab where rn <= 1;
QUERY PLAN
---------------------------------------------------------------------------------------
Subquery Scan on ab (actual rows=1000 loops=1)
-> WindowAgg (actual rows=1000 loops=1)
Run Condition: (row_number() OVER (?) <= 1)
-> Index Only Scan using ab_a_b_idx on ab ab_1 (actual
rows=1000000 loops=1)
Heap Fetches: 0
Planning Time: 0.178 ms
Execution Time: 75.101 ms
(7 rows)
Time: 75.673 ms (447% faster)
You can see that this executes quite a bit more quickly. As Erwin
pointed out to me (off-list), this along with the monotonic window
function optimisation that was added in PG15 the performance of this
gets close to DISTINCT ON.
explain (analyze, costs off, timing off)
select distinct on (a) a,b from ab order by a,b;
QUERY PLAN
----------------------------------------------------------------------------
Unique (actual rows=1000 loops=1)
-> Index Only Scan using ab_a_b_idx on ab (actual rows=1000000 loops=1)
Heap Fetches: 0
Planning Time: 0.071 ms
Execution Time: 77.988 ms
(5 rows)
I've not really done any analysis into which other window functions
can use this optimisation. The attached only adds support to
row_number()'s support function and only converts exactly "RANGE
UNBOUNDED PRECEDING AND CURRENT ROW" into "ROW UNBOUNDED PRECEDING AND
CURRENT ROW". That might need to be relaxed a little, but I've done
no analysis to find that out. Erwin mentioned to me that he's not
currently in a position to produce a patch for this, so here's the
patch. I'm hoping the existence of this might coax Erwin into doing
some analysis into what other window functions we can support and what
other frame options can be optimised.
[1]
https://postgr.es/m/caghenj7lbbszxs+skwwfvnbmot2ovsbhdmb1dfrgerceya_...@mail.gmail.com
diff --git a/src/backend/optimizer/plan/planner.c
b/src/backend/optimizer/plan/planner.c
index 5d0fd6e072..e55e0e49a5 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_clause_frameoptions(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,15 @@ 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 we can find more optimal version of
each
+ * WindowClause's frameOptions.
+ */
+ optimize_window_clause_frameoptions(root,
wflists);
+
activeWindows = select_active_windows(root,
wflists);
+ }
else
parse->hasWindowFuncs = false;
}
@@ -5391,6 +5402,83 @@ postprocess_setop_tlist(List *new_tlist, List
*orig_tlist)
return new_tlist;
}
+/*
+ * optimize_window_clause_frameoptions
+ * Call each WindowFunc's prosupport function to see if we're able
to
+ * make any adjustments to any of the WindowClause's frameOptions
so that
+ * the executor can execute the window functions in a more optimal
way.
+ */
+static void
+optimize_window_clause_frameoptions(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])
+ {
+ SupportRequestWFuncOptimizeFrameOpts req;
+ SupportRequestWFuncOptimizeFrameOpts *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_SupportRequestWFuncOptimizeFrameOpts;
+ req.window_clause = wc;
+ req.window_func = wfunc;
+ req.frameOptions = wc->frameOptions;
+
+ /* call the support function */
+ res = (SupportRequestWFuncOptimizeFrameOpts *)
+ 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..8a85204080 100644
--- a/src/backend/utils/adt/windowfuncs.c
+++ b/src/backend/utils/adt/windowfuncs.c
@@ -107,6 +107,30 @@ window_row_number_support(PG_FUNCTION_ARGS)
PG_RETURN_POINTER(req);
}
+ if (IsA(rawreq, SupportRequestWFuncOptimizeFrameOpts))
+ {
+ SupportRequestWFuncOptimizeFrameOpts *req =
(SupportRequestWFuncOptimizeFrameOpts *) rawreq;
+
+ /*
+ * row_number() does not care about RANGE UNBOUNDED PRECEDING vs
+ * ROWS UNBOUNDED PRECEDING. The latter will execute more
efficiently
+ * due to nodeWindowAgg.c not having to check if prior rows are
peers
+ * of the current row.
+ *
+ * XXX what to do about this FRAMEOPTION_NONDEFAULT option?
Are there
+ * any other variations that can be optimized?
+ */
+ if (req->frameOptions == (FRAMEOPTION_NONDEFAULT |
FRAMEOPTION_RANGE |
+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
+
FRAMEOPTION_END_CURRENT_ROW))
+ 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..7be75b06b8 100644
--- a/src/include/nodes/supportnodes.h
+++ b/src/include/nodes/supportnodes.h
@@ -299,4 +299,43 @@ 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() behaves the
+ * same way if it's called with "OVER (RANGE UNBOUNDED PRECEDING)" or if it's
+ * called with "OVER (ROWS UNBOUNDED PRECEDING)", the latter does not need to
+ * check if prior rows are peers of the current row, so should execute much
+ * more quickly than the RANGE version.
+ *
+ * Here we allow a WindowFunc's support function to output the most optimal
+ * version of window_clause.frameOptions for this particular window function.
+ * 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 frame options 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 to
+ * allow the support function to lookup details of how the WindowFunc is being
+ * used.
+ *
+ * 'frameOptions' is set by the planner to WindowClause.frameOptions. The
+ * support should only adjust this if optimizations are possible.
+ */
+typedef struct SupportRequestWFuncOptimizeFrameOpts
+{
+ 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
+ * optimization
is possible. */
+} SupportRequestWFuncOptimizeFrameOpts;
+
#endif /* SUPPORTNODES_H */
