Skip to content

Commit ed1a88d

Browse files
david-rowleydavid-rowley
committed
Allow window functions to adjust their frameOptions
WindowFuncs such as row_number() don't care if it's called with ROWS UNBOUNDED PRECEDING AND CURRENT ROW or with RANGE UNBOUNDED PRECEDING AND CURRENT ROW. The latter is less efficient as the RANGE option requires that the executor check for peer rows, so using the ROW option instead would cause less overhead. Because RANGE is part of the default frame options for WindowClauses, it means WindowAgg is, by default, working much harder than it needs to for window functions where the ROWS / RANGE option has no effect on the window function's result. On a test query from the discussion thread, a performance improvement of 344% was seen by using ROWS instead of RANGE. Here we add a new support function node type to allow support functions to be called for window functions so that the most optimal version of the frame options can be set. The planner has been adjusted so that the frame options are changed only if all window functions sharing the same window clause agree on what the optimized frame options are. Here we give the ability for row_number(), rank(), dense_rank(), percent_rank(), cume_dist() and ntile() to alter their WindowClause's frameOptions. Reviewed-by: Vik Fearing, Erwin Brandstetter, Zhihong Yu Discussion: https://postgr.es/m/CAGHENJ7LBBszxS+SkWWFVnBmOT2oVsBhDMB1DFrgerCeYa_DyA@mail.gmail.com Discussion: https://postgr.es/m/CAApHDvohAKEtTXxq7Pc-ic2dKT8oZfbRKeEJP64M0B6+S88z+A@mail.gmail.com
1 parent cc15059 commit ed1a88d

File tree

8 files changed

+480
-4
lines changed

8 files changed

+480
-4
lines changed

‎src/backend/optimizer/plan/planner.c

Lines changed: 156 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -41,6 +41,7 @@
4141
#ifdef OPTIMIZER_DEBUG
4242
#include "nodes/print.h"
4343
#endif
44+
#include "nodes/supportnodes.h"
4445
#include "optimizer/appendinfo.h"
4546
#include "optimizer/clauses.h"
4647
#include "optimizer/cost.h"
@@ -208,6 +209,8 @@ static PathTarget *make_partial_grouping_target(PlannerInfo *root,
208209
PathTarget *grouping_target,
209210
Node *havingQual);
210211
static List *postprocess_setop_tlist(List *new_tlist, List *orig_tlist);
212+
static void optimize_window_clauses(PlannerInfo *root,
213+
WindowFuncLists *wflists);
211214
static List *select_active_windows(PlannerInfo *root, WindowFuncLists *wflists);
212215
static PathTarget *make_window_input_target(PlannerInfo *root,
213216
PathTarget *final_target,
@@ -1430,7 +1433,16 @@ grouping_planner(PlannerInfo *root, double tuple_fraction)
14301433
wflists = find_window_functions((Node *) root->processed_tlist,
14311434
list_length(parse->windowClause));
14321435
if (wflists->numWindowFuncs > 0)
1436+
{
1437+
/*
1438+
* See if any modifications can be made to each WindowClause
1439+
* to allow the executor to execute the WindowFuncs more
1440+
* quickly.
1441+
*/
1442+
optimize_window_clauses(root, wflists);
1443+
14331444
activeWindows = select_active_windows(root, wflists);
1445+
}
14341446
else
14351447
parse->hasWindowFuncs = false;
14361448
}
@@ -5432,6 +5444,150 @@ postprocess_setop_tlist(List *new_tlist, List *orig_tlist)
54325444
return new_tlist;
54335445
}
54345446

5447+
/*
5448+
* optimize_window_clauses
5449+
* Call each WindowFunc's prosupport function to see if we're able to
5450+
* make any adjustments to any of the WindowClause's so that the executor
5451+
* can execute the window functions in a more optimal way.
5452+
*
5453+
* Currently we only allow adjustments to the WindowClause's frameOptions. We
5454+
* may allow more things to be done here in the future.
5455+
*/
5456+
static void
5457+
optimize_window_clauses(PlannerInfo *root, WindowFuncLists *wflists)
5458+
{
5459+
List *windowClause = root->parse->windowClause;
5460+
ListCell *lc;
5461+
5462+
foreach(lc, windowClause)
5463+
{
5464+
WindowClause *wc = lfirst_node(WindowClause, lc);
5465+
ListCell *lc2;
5466+
int optimizedFrameOptions = 0;
5467+
5468+
Assert(wc->winref <= wflists->maxWinRef);
5469+
5470+
/* skip any WindowClauses that have no WindowFuncs */
5471+
if (wflists->windowFuncs[wc->winref] == NIL)
5472+
continue;
5473+
5474+
foreach(lc2, wflists->windowFuncs[wc->winref])
5475+
{
5476+
SupportRequestOptimizeWindowClause req;
5477+
SupportRequestOptimizeWindowClause *res;
5478+
WindowFunc *wfunc = lfirst_node(WindowFunc, lc2);
5479+
Oid prosupport;
5480+
5481+
prosupport = get_func_support(wfunc->winfnoid);
5482+
5483+
/* Check if there's a support function for 'wfunc' */
5484+
if (!OidIsValid(prosupport))
5485+
break; /* can't optimize this WindowClause */
5486+
5487+
req.type = T_SupportRequestOptimizeWindowClause;
5488+
req.window_clause = wc;
5489+
req.window_func = wfunc;
5490+
req.frameOptions = wc->frameOptions;
5491+
5492+
/* call the support function */
5493+
res = (SupportRequestOptimizeWindowClause *)
5494+
DatumGetPointer(OidFunctionCall1(prosupport,
5495+
PointerGetDatum(&req)));
5496+
5497+
/*
5498+
* Skip to next WindowClause if the support function does not
5499+
* support this request type.
5500+
*/
5501+
if (res == NULL)
5502+
break;
5503+
5504+
/*
5505+
* Save these frameOptions for the first WindowFunc for this
5506+
* WindowClause.
5507+
*/
5508+
if (foreach_current_index(lc2) == 0)
5509+
optimizedFrameOptions = res->frameOptions;
5510+
5511+
/*
5512+
* On subsequent WindowFuncs, if the frameOptions are not the same
5513+
* then we're unable to optimize the frameOptions for this
5514+
* WindowClause.
5515+
*/
5516+
else if (optimizedFrameOptions != res->frameOptions)
5517+
break; /* skip to the next WindowClause, if any */
5518+
}
5519+
5520+
/* adjust the frameOptions if all WindowFunc's agree that it's ok */
5521+
if (lc2 == NULL && wc->frameOptions != optimizedFrameOptions)
5522+
{
5523+
ListCell *lc3;
5524+
5525+
/* apply the new frame options */
5526+
wc->frameOptions = optimizedFrameOptions;
5527+
5528+
/*
5529+
* We now check to see if changing the frameOptions has caused
5530+
* this WindowClause to be a duplicate of some other WindowClause.
5531+
* This can only happen if we have multiple WindowClauses, so
5532+
* don't bother if there's only 1.
5533+
*/
5534+
if (list_length(windowClause) == 1)
5535+
continue;
5536+
5537+
/*
5538+
* Do the duplicate check and reuse the existing WindowClause if
5539+
* we find a duplicate.
5540+
*/
5541+
foreach(lc3, windowClause)
5542+
{
5543+
WindowClause *existing_wc = lfirst_node(WindowClause, lc3);
5544+
5545+
/* skip over the WindowClause we're currently editing */
5546+
if (existing_wc == wc)
5547+
continue;
5548+
5549+
/*
5550+
* Perform the same duplicate check that is done in
5551+
* transformWindowFuncCall.
5552+
*/
5553+
if (equal(wc->partitionClause, existing_wc->partitionClause) &&
5554+
equal(wc->orderClause, existing_wc->orderClause) &&
5555+
wc->frameOptions == existing_wc->frameOptions &&
5556+
equal(wc->startOffset, existing_wc->startOffset) &&
5557+
equal(wc->endOffset, existing_wc->endOffset))
5558+
{
5559+
ListCell *lc4;
5560+
5561+
/*
5562+
* Now move each WindowFunc in 'wc' into 'existing_wc'.
5563+
* This required adjusting each WindowFunc's winref and
5564+
* moving the WindowFuncs in 'wc' to the list of
5565+
* WindowFuncs in 'existing_wc'.
5566+
*/
5567+
foreach(lc4, wflists->windowFuncs[wc->winref])
5568+
{
5569+
WindowFunc *wfunc = lfirst_node(WindowFunc, lc4);
5570+
5571+
wfunc->winref = existing_wc->winref;
5572+
}
5573+
5574+
/* move list items */
5575+
wflists->windowFuncs[existing_wc->winref] = list_concat(wflists->windowFuncs[existing_wc->winref],
5576+
wflists->windowFuncs[wc->winref]);
5577+
wflists->windowFuncs[wc->winref] = NIL;
5578+
5579+
/*
5580+
* transformWindowFuncCall() should have made sure there
5581+
* are no other duplicates, so we needn't bother looking
5582+
* any further.
5583+
*/
5584+
break;
5585+
}
5586+
}
5587+
}
5588+
}
5589+
}
5590+
54355591
/*
54365592
* select_active_windows
54375593
* Create a list of the "active" window clauses (ie, those referenced

‎src/backend/parser/parse_agg.c

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1025,6 +1025,10 @@ transformWindowFuncCall(ParseState *pstate, WindowFunc *wfunc,
10251025
/* matched, no refname */ ;
10261026
else
10271027
continue;
1028+
1029+
/*
1030+
* Also see similar de-duplication code in optimize_window_clauses
1031+
*/
10281032
if (equal(refwin->partitionClause, windef->partitionClause) &&
10291033
equal(refwin->orderClause, windef->orderClause) &&
10301034
refwin->frameOptions == windef->frameOptions &&

‎src/backend/utils/adt/windowfuncs.c

Lines changed: 148 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -107,6 +107,24 @@ window_row_number_support(PG_FUNCTION_ARGS)
107107
PG_RETURN_POINTER(req);
108108
}
109109

110+
if (IsA(rawreq, SupportRequestOptimizeWindowClause))
111+
{
112+
SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
113+
114+
/*
115+
* The frame options can always become "ROWS BETWEEN UNBOUNDED
116+
* PRECEDING AND CURRENT ROW". row_number() always just increments by
117+
* 1 with each row in the partition. Using ROWS instead of RANGE
118+
* saves effort checking peer rows during execution.
119+
*/
120+
req->frameOptions = (FRAMEOPTION_NONDEFAULT |
121+
FRAMEOPTION_ROWS |
122+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
123+
FRAMEOPTION_END_CURRENT_ROW);
124+
125+
PG_RETURN_POINTER(req);
126+
}
127+
110128
PG_RETURN_POINTER(NULL);
111129
}
112130

@@ -149,6 +167,27 @@ window_rank_support(PG_FUNCTION_ARGS)
149167
PG_RETURN_POINTER(req);
150168
}
151169

170+
if (IsA(rawreq, SupportRequestOptimizeWindowClause))
171+
{
172+
SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
173+
174+
/*
175+
* rank() is coded in such a way that it returns "(COUNT (*) OVER
176+
* (<opt> RANGE UNBOUNDED PRECEDING) - COUNT (*) OVER (<opt> RANGE
177+
* CURRENT ROW) + 1)" regardless of the frame options. We'll set the
178+
* frame options to "ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW"
179+
* so they agree with what window_row_number_support() optimized the
180+
* frame options to be. Using ROWS instead of RANGE saves from doing
181+
* peer row checks during execution.
182+
*/
183+
req->frameOptions = (FRAMEOPTION_NONDEFAULT |
184+
FRAMEOPTION_ROWS |
185+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
186+
FRAMEOPTION_END_CURRENT_ROW);
187+
188+
PG_RETURN_POINTER(req);
189+
}
190+
152191
PG_RETURN_POINTER(NULL);
153192
}
154193

@@ -190,6 +229,24 @@ window_dense_rank_support(PG_FUNCTION_ARGS)
190229
PG_RETURN_POINTER(req);
191230
}
192231

232+
if (IsA(rawreq, SupportRequestOptimizeWindowClause))
233+
{
234+
SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
235+
236+
/*
237+
* dense_rank() is unaffected by the frame options. Here we set the
238+
* frame options to match what's done in row_number's support
239+
* function. Using ROWS instead of RANGE (the default) saves the
240+
* executor from having to check for peer rows.
241+
*/
242+
req->frameOptions = (FRAMEOPTION_NONDEFAULT |
243+
FRAMEOPTION_ROWS |
244+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
245+
FRAMEOPTION_END_CURRENT_ROW);
246+
247+
PG_RETURN_POINTER(req);
248+
}
249+
193250
PG_RETURN_POINTER(NULL);
194251
}
195252

@@ -222,6 +279,37 @@ window_percent_rank(PG_FUNCTION_ARGS)
222279
PG_RETURN_FLOAT8((float8) (context->rank - 1) / (float8) (totalrows - 1));
223280
}
224281

282+
/*
283+
* window_percent_rank_support
284+
* prosupport function for window_percent_rank()
285+
*/
286+
Datum
287+
window_percent_rank_support(PG_FUNCTION_ARGS)
288+
{
289+
Node *rawreq = (Node *) PG_GETARG_POINTER(0);
290+
291+
if (IsA(rawreq, SupportRequestOptimizeWindowClause))
292+
{
293+
SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
294+
295+
/*
296+
* percent_rank() is unaffected by the frame options. Here we set the
297+
* frame options to match what's done in row_number's support
298+
* function. Using ROWS instead of RANGE (the default) saves the
299+
* executor from having to check for peer rows.
300+
*/
301+
req->frameOptions = (FRAMEOPTION_NONDEFAULT |
302+
FRAMEOPTION_ROWS |
303+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
304+
FRAMEOPTION_END_CURRENT_ROW);
305+
306+
PG_RETURN_POINTER(req);
307+
}
308+
309+
PG_RETURN_POINTER(NULL);
310+
}
311+
312+
225313
/*
226314
* cume_dist
227315
* return fraction between 0 and 1 inclusive,
@@ -265,6 +353,36 @@ window_cume_dist(PG_FUNCTION_ARGS)
265353
PG_RETURN_FLOAT8((float8) context->rank / (float8) totalrows);
266354
}
267355

356+
/*
357+
* window_cume_dist_support
358+
* prosupport function for window_cume_dist()
359+
*/
360+
Datum
361+
window_cume_dist_support(PG_FUNCTION_ARGS)
362+
{
363+
Node *rawreq = (Node *) PG_GETARG_POINTER(0);
364+
365+
if (IsA(rawreq, SupportRequestOptimizeWindowClause))
366+
{
367+
SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
368+
369+
/*
370+
* cume_dist() is unaffected by the frame options. Here we set the
371+
* frame options to match what's done in row_number's support
372+
* function. Using ROWS instead of RANGE (the default) saves the
373+
* executor from having to check for peer rows.
374+
*/
375+
req->frameOptions = (FRAMEOPTION_NONDEFAULT |
376+
FRAMEOPTION_ROWS |
377+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
378+
FRAMEOPTION_END_CURRENT_ROW);
379+
380+
PG_RETURN_POINTER(req);
381+
}
382+
383+
PG_RETURN_POINTER(NULL);
384+
}
385+
268386
/*
269387
* ntile
270388
* compute an exact numeric value with scale 0 (zero),
@@ -338,6 +456,36 @@ window_ntile(PG_FUNCTION_ARGS)
338456
PG_RETURN_INT32(context->ntile);
339457
}
340458

459+
/*
460+
* window_ntile_support
461+
* prosupport function for window_ntile()
462+
*/
463+
Datum
464+
window_ntile_support(PG_FUNCTION_ARGS)
465+
{
466+
Node *rawreq = (Node *) PG_GETARG_POINTER(0);
467+
468+
if (IsA(rawreq, SupportRequestOptimizeWindowClause))
469+
{
470+
SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
471+
472+
/*
473+
* ntile() is unaffected by the frame options. Here we set the frame
474+
* options to match what's done in row_number's support function.
475+
* Using ROWS instead of RANGE (the default) saves the executor from
476+
* having to check for peer rows.
477+
*/
478+
req->frameOptions = (FRAMEOPTION_NONDEFAULT |
479+
FRAMEOPTION_ROWS |
480+
FRAMEOPTION_START_UNBOUNDED_PRECEDING |
481+
FRAMEOPTION_END_CURRENT_ROW);
482+
483+
PG_RETURN_POINTER(req);
484+
}
485+
486+
PG_RETURN_POINTER(NULL);
487+
}
488+
341489
/*
342490
* leadlag_common
343491
* common operation of lead() and lag()

‎src/include/catalog/catversion.h

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -57,6 +57,6 @@
5757
*/
5858

5959
/* yyyymmddN */
60-
#define CATALOG_VERSION_NO 202212201
60+
#define CATALOG_VERSION_NO 202212231
6161

6262
#endif

0 commit comments

Comments
 (0)