public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v8 4/7] Row pattern recognition patch (executor).
5+ messages / 4 participants
[nested] [flat]
* [PATCH v8 4/7] Row pattern recognition patch (executor).
@ 2023-09-25 05:01 Tatsuo Ishii <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Tatsuo Ishii @ 2023-09-25 05:01 UTC (permalink / raw)
---
src/backend/executor/nodeWindowAgg.c | 1024 +++++++++++++++++++++++++-
src/backend/utils/adt/windowfuncs.c | 37 +-
src/include/catalog/pg_proc.dat | 6 +
src/include/nodes/execnodes.h | 26 +
4 files changed, 1080 insertions(+), 13 deletions(-)
diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 310ac23e3a..5f2dfdf943 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -36,6 +36,7 @@
#include "access/htup_details.h"
#include "catalog/objectaccess.h"
#include "catalog/pg_aggregate.h"
+#include "catalog/pg_collation_d.h"
#include "catalog/pg_proc.h"
#include "executor/executor.h"
#include "executor/nodeWindowAgg.h"
@@ -48,6 +49,7 @@
#include "utils/acl.h"
#include "utils/builtins.h"
#include "utils/datum.h"
+#include "utils/fmgroids.h"
#include "utils/expandeddatum.h"
#include "utils/lsyscache.h"
#include "utils/memutils.h"
@@ -159,6 +161,12 @@ typedef struct WindowStatePerAggData
bool restart; /* need to restart this agg in this cycle? */
} WindowStatePerAggData;
+typedef struct StringSet {
+ StringInfo *str_set;
+ Size set_size; /* current array allocation size in number of items */
+ int set_index; /* current used size */
+} StringSet;
+
static void initialize_windowaggregate(WindowAggState *winstate,
WindowStatePerFunc perfuncstate,
WindowStatePerAgg peraggstate);
@@ -182,8 +190,9 @@ static void begin_partition(WindowAggState *winstate);
static void spool_tuples(WindowAggState *winstate, int64 pos);
static void release_partition(WindowAggState *winstate);
-static int row_is_in_frame(WindowAggState *winstate, int64 pos,
+static int row_is_in_frame(WindowAggState *winstate, int64 pos,
TupleTableSlot *slot);
+
static void update_frameheadpos(WindowAggState *winstate);
static void update_frametailpos(WindowAggState *winstate);
static void update_grouptailpos(WindowAggState *winstate);
@@ -195,9 +204,37 @@ static Datum GetAggInitVal(Datum textInitVal, Oid transtype);
static bool are_peers(WindowAggState *winstate, TupleTableSlot *slot1,
TupleTableSlot *slot2);
-static bool window_gettupleslot(WindowObject winobj, int64 pos,
- TupleTableSlot *slot);
+static int WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot,
+ int relpos, int seektype, bool set_mark,
+ bool *isnull, bool *isout);
+static bool window_gettupleslot(WindowObject winobj, int64 pos, TupleTableSlot *slot);
+
+static void attno_map(Node *node);
+static bool attno_map_walker(Node *node, void *context);
+static int row_is_in_reduced_frame(WindowObject winobj, int64 pos);
+static bool rpr_is_defined(WindowAggState *winstate);
+
+static void create_reduced_frame_map(WindowAggState *winstate);
+static int get_reduced_frame_map(WindowAggState *winstate, int64 pos);
+static void register_reduced_frame_map(WindowAggState *winstate, int64 pos, int val);
+static void clear_reduced_frame_map(WindowAggState *winstate);
+static void update_reduced_frame(WindowObject winobj, int64 pos);
+
+static int64 evaluate_pattern(WindowObject winobj, int64 current_pos,
+ char *vname, StringInfo encoded_str, bool *result);
+
+static bool get_slots(WindowObject winobj, int64 current_pos);
+
+static int search_str_set(char *pattern, StringSet *str_set);
+static char pattern_initial(WindowAggState *winstate, char *vname);
+static int do_pattern_match(char *pattern, char *encoded_str);
+
+static StringSet *string_set_init(void);
+static void string_set_add(StringSet *string_set, StringInfo str);
+static StringInfo string_set_get(StringSet *string_set, int index);
+static int string_set_get_size(StringSet *string_set);
+static void string_set_discard(StringSet *string_set);
/*
* initialize_windowaggregate
@@ -673,6 +710,7 @@ eval_windowaggregates(WindowAggState *winstate)
WindowObject agg_winobj;
TupleTableSlot *agg_row_slot;
TupleTableSlot *temp_slot;
+ bool agg_result_isnull;
numaggs = winstate->numaggs;
if (numaggs == 0)
@@ -778,6 +816,9 @@ eval_windowaggregates(WindowAggState *winstate)
* Note that we don't strictly need to restart in the last case, but if
* we're going to remove all rows from the aggregation anyway, a restart
* surely is faster.
+ *
+ * - if RPR is enabled and skip mode is SKIP TO NEXT ROW,
+ * we restart aggregation too.
*----------
*/
numaggs_restart = 0;
@@ -788,8 +829,11 @@ eval_windowaggregates(WindowAggState *winstate)
(winstate->aggregatedbase != winstate->frameheadpos &&
!OidIsValid(peraggstate->invtransfn_oid)) ||
(winstate->frameOptions & FRAMEOPTION_EXCLUSION) ||
- winstate->aggregatedupto <= winstate->frameheadpos)
+ winstate->aggregatedupto <= winstate->frameheadpos ||
+ (rpr_is_defined(winstate) &&
+ winstate->rpSkipTo == ST_NEXT_ROW))
{
+ elog(DEBUG1, "peraggstate->restart is set");
peraggstate->restart = true;
numaggs_restart++;
}
@@ -861,8 +905,10 @@ eval_windowaggregates(WindowAggState *winstate)
* If we created a mark pointer for aggregates, keep it pushed up to frame
* head, so that tuplestore can discard unnecessary rows.
*/
+#ifdef NOT_USED
if (agg_winobj->markptr >= 0)
WinSetMarkPosition(agg_winobj, winstate->frameheadpos);
+#endif
/*
* Now restart the aggregates that require it.
@@ -917,6 +963,29 @@ eval_windowaggregates(WindowAggState *winstate)
{
winstate->aggregatedupto = winstate->frameheadpos;
ExecClearTuple(agg_row_slot);
+
+ /*
+ * If RPR is defined, we do not use aggregatedupto_nonrestarted. To
+ * avoid assertion failure below, we reset aggregatedupto_nonrestarted
+ * to frameheadpos.
+ */
+ if (rpr_is_defined(winstate))
+ aggregatedupto_nonrestarted = winstate->frameheadpos;
+ }
+
+ agg_result_isnull = false;
+ /* RPR is defined? */
+ if (rpr_is_defined(winstate))
+ {
+ /*
+ * If the skip mode is SKIP TO PAST LAST ROW and we already know that
+ * current row is a skipped row, we don't need to accumulate rows,
+ * just return NULL. Note that for unamtched row, we need to do
+ * aggregation so that count(*) shows 0, rather than NULL.
+ */
+ if (winstate->rpSkipTo == ST_PAST_LAST_ROW &&
+ get_reduced_frame_map(winstate, winstate->currentpos) == RF_SKIPPED)
+ agg_result_isnull = true;
}
/*
@@ -930,6 +999,11 @@ eval_windowaggregates(WindowAggState *winstate)
{
int ret;
+ elog(DEBUG1, "===== loop in frame starts: " INT64_FORMAT, winstate->aggregatedupto);
+
+ if (agg_result_isnull)
+ break;
+
/* Fetch next row if we didn't already */
if (TupIsNull(agg_row_slot))
{
@@ -945,9 +1019,28 @@ eval_windowaggregates(WindowAggState *winstate)
ret = row_is_in_frame(winstate, winstate->aggregatedupto, agg_row_slot);
if (ret < 0)
break;
+
if (ret == 0)
goto next_tuple;
+ if (rpr_is_defined(winstate))
+ {
+ /*
+ * If the row status at currentpos is already decided and current
+ * row status is not decided yet, it means we passed the last
+ * reduced frame. Time to break the loop.
+ */
+ if (get_reduced_frame_map(winstate, winstate->currentpos) != RF_NOT_DETERMINED &&
+ get_reduced_frame_map(winstate, winstate->aggregatedupto) == RF_NOT_DETERMINED)
+ break;
+ /*
+ * Otherwise we need to calculate the reduced frame.
+ */
+ ret = row_is_in_reduced_frame(winstate->agg_winobj, winstate->aggregatedupto);
+ if (ret == -1) /* unmatched row */
+ break;
+ }
+
/* Set tuple context for evaluation of aggregate arguments */
winstate->tmpcontext->ecxt_outertuple = agg_row_slot;
@@ -976,6 +1069,7 @@ next_tuple:
ExecClearTuple(agg_row_slot);
}
+
/* The frame's end is not supposed to move backwards, ever */
Assert(aggregatedupto_nonrestarted <= winstate->aggregatedupto);
@@ -996,6 +1090,16 @@ next_tuple:
peraggstate,
result, isnull);
+ /*
+ * RPR is defined and we just return NULL because skip mode is SKIP
+ * TO PAST LAST ROW and current row is skipped row.
+ */
+ if (agg_result_isnull)
+ {
+ *isnull = true;
+ *result = (Datum) 0;
+ }
+
/*
* save the result in case next row shares the same frame.
*
@@ -1090,6 +1194,7 @@ begin_partition(WindowAggState *winstate)
winstate->framehead_valid = false;
winstate->frametail_valid = false;
winstate->grouptail_valid = false;
+ create_reduced_frame_map(winstate);
winstate->spooled_rows = 0;
winstate->currentpos = 0;
winstate->frameheadpos = 0;
@@ -2053,6 +2158,8 @@ ExecWindowAgg(PlanState *pstate)
CHECK_FOR_INTERRUPTS();
+ elog(DEBUG1, "ExecWindowAgg called. pos: " INT64_FORMAT , winstate->currentpos);
+
if (winstate->status == WINDOWAGG_DONE)
return NULL;
@@ -2221,6 +2328,17 @@ ExecWindowAgg(PlanState *pstate)
/* don't evaluate the window functions when we're in pass-through mode */
if (winstate->status == WINDOWAGG_RUN)
{
+ /*
+ * If RPR is defined and skip mode is next row, we need to clear existing
+ * reduced frame info so that we newly calculate the info starting from
+ * current row.
+ */
+ if (rpr_is_defined(winstate))
+ {
+ if (winstate->rpSkipTo == ST_NEXT_ROW)
+ clear_reduced_frame_map(winstate);
+ }
+
/*
* Evaluate true window functions
*/
@@ -2388,6 +2506,9 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
TupleDesc scanDesc;
ListCell *l;
+ TargetEntry *te;
+ Expr *expr;
+
/* check for unsupported flags */
Assert(!(eflags & (EXEC_FLAG_BACKWARD | EXEC_FLAG_MARK)));
@@ -2483,6 +2604,16 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
winstate->temp_slot_2 = ExecInitExtraTupleSlot(estate, scanDesc,
&TTSOpsMinimalTuple);
+ winstate->prev_slot = ExecInitExtraTupleSlot(estate, scanDesc,
+ &TTSOpsMinimalTuple);
+
+ winstate->next_slot = ExecInitExtraTupleSlot(estate, scanDesc,
+ &TTSOpsMinimalTuple);
+
+ winstate->null_slot = ExecInitExtraTupleSlot(estate, scanDesc,
+ &TTSOpsMinimalTuple);
+ winstate->null_slot = ExecStoreAllNullTuple(winstate->null_slot);
+
/*
* create frame head and tail slots only if needed (must create slots in
* exactly the same cases that update_frameheadpos and update_frametailpos
@@ -2667,6 +2798,39 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
winstate->inRangeAsc = node->inRangeAsc;
winstate->inRangeNullsFirst = node->inRangeNullsFirst;
+ /* Set up SKIP TO type */
+ winstate->rpSkipTo = node->rpSkipTo;
+ /* Set up row pattern recognition PATTERN clause */
+ winstate->patternVariableList = node->patternVariable;
+ winstate->patternRegexpList = node->patternRegexp;
+
+ /* Set up row pattern recognition DEFINE clause */
+ winstate->defineInitial = node->defineInitial;
+ winstate->defineVariableList = NIL;
+ winstate->defineClauseList = NIL;
+ if (node->defineClause != NIL)
+ {
+ /*
+ * Tweak arg var of PREV/NEXT so that it refers to scan/inner slot.
+ */
+ foreach(l, node->defineClause)
+ {
+ char *name;
+ ExprState *exps;
+
+ te = lfirst(l);
+ name = te->resname;
+ expr = te->expr;
+
+ elog(DEBUG1, "defineVariable name: %s", name);
+ winstate->defineVariableList = lappend(winstate->defineVariableList,
+ makeString(pstrdup(name)));
+ attno_map((Node *)expr);
+ exps = ExecInitExpr(expr, (PlanState *) winstate);
+ winstate->defineClauseList = lappend(winstate->defineClauseList, exps);
+ }
+ }
+
winstate->all_first = true;
winstate->partition_spooled = false;
winstate->more_partitions = false;
@@ -2674,6 +2838,57 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
return winstate;
}
+/*
+ * Rewrite varno of Var node that is the argument of PREV/NET so that it sees
+ * scan tuple (PREV) or inner tuple (NEXT).
+ */
+static void
+attno_map(Node *node)
+{
+ (void) expression_tree_walker(node, attno_map_walker, NULL);
+}
+
+static bool
+attno_map_walker(Node *node, void *context)
+{
+ FuncExpr *func;
+ int nargs;
+ Expr *expr;
+ Var *var;
+
+ if (node == NULL)
+ return false;
+
+ if (IsA(node, FuncExpr))
+ {
+ func = (FuncExpr *)node;
+
+ if (func->funcid == F_PREV || func->funcid == F_NEXT)
+ {
+ /* sanity check */
+ nargs = list_length(func->args);
+ if (list_length(func->args) != 1)
+ elog(ERROR, "PREV/NEXT must have 1 argument but function %d has %d args", func->funcid, nargs);
+
+ expr = (Expr *) lfirst(list_head(func->args));
+ if (!IsA(expr, Var))
+ elog(ERROR, "PREV/NEXT's arg is not Var"); /* XXX: is it possible that arg type is Const? */
+ var = (Var *)expr;
+
+ if (func->funcid == F_PREV)
+ /*
+ * Rewrite varno from OUTER_VAR to regular var no so that the
+ * var references scan tuple.
+ */
+ var->varno = var->varnosyn;
+ else
+ var->varno = INNER_VAR;
+ elog(DEBUG1, "PREV/NEXT's varno is rewritten to: %d", var->varno);
+ }
+ }
+ return expression_tree_walker(node, attno_map_walker, NULL);
+}
+
/* -----------------
* ExecEndWindowAgg
* -----------------
@@ -2691,6 +2906,8 @@ ExecEndWindowAgg(WindowAggState *node)
ExecClearTuple(node->agg_row_slot);
ExecClearTuple(node->temp_slot_1);
ExecClearTuple(node->temp_slot_2);
+ ExecClearTuple(node->prev_slot);
+ ExecClearTuple(node->next_slot);
if (node->framehead_slot)
ExecClearTuple(node->framehead_slot);
if (node->frametail_slot)
@@ -2740,6 +2957,8 @@ ExecReScanWindowAgg(WindowAggState *node)
ExecClearTuple(node->agg_row_slot);
ExecClearTuple(node->temp_slot_1);
ExecClearTuple(node->temp_slot_2);
+ ExecClearTuple(node->prev_slot);
+ ExecClearTuple(node->next_slot);
if (node->framehead_slot)
ExecClearTuple(node->framehead_slot);
if (node->frametail_slot)
@@ -3100,7 +3319,7 @@ window_gettupleslot(WindowObject winobj, int64 pos, TupleTableSlot *slot)
return false;
if (pos < winobj->markpos)
- elog(ERROR, "cannot fetch row before WindowObject's mark position");
+ elog(ERROR, "cannot fetch row: " INT64_FORMAT " before WindowObject's mark position: " INT64_FORMAT, pos, winobj->markpos );
oldcontext = MemoryContextSwitchTo(winstate->ss.ps.ps_ExprContext->ecxt_per_query_memory);
@@ -3420,14 +3639,54 @@ WinGetFuncArgInFrame(WindowObject winobj, int argno,
WindowAggState *winstate;
ExprContext *econtext;
TupleTableSlot *slot;
- int64 abs_pos;
- int64 mark_pos;
Assert(WindowObjectIsValid(winobj));
winstate = winobj->winstate;
econtext = winstate->ss.ps.ps_ExprContext;
slot = winstate->temp_slot_1;
+ if (WinGetSlotInFrame(winobj, slot,
+ relpos, seektype, set_mark,
+ isnull, isout) == 0)
+ {
+ econtext->ecxt_outertuple = slot;
+ return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno),
+ econtext, isnull);
+ }
+
+ if (isout)
+ *isout = true;
+ *isnull = true;
+ return (Datum) 0;
+}
+
+/*
+ * WinGetSlotInFrame
+ * slot: TupleTableSlot to store the result
+ * relpos: signed rowcount offset from the seek position
+ * seektype: WINDOW_SEEK_HEAD or WINDOW_SEEK_TAIL
+ * set_mark: If the row is found/in frame and set_mark is true, the mark is
+ * moved to the row as a side-effect.
+ * isnull: output argument, receives isnull status of result
+ * isout: output argument, set to indicate whether target row position
+ * is out of frame (can pass NULL if caller doesn't care about this)
+ *
+ * Returns 0 if we successfullt got the slot. false if out of frame.
+ * (also isout is set)
+ */
+static int
+WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot,
+ int relpos, int seektype, bool set_mark,
+ bool *isnull, bool *isout)
+{
+ WindowAggState *winstate;
+ int64 abs_pos;
+ int64 mark_pos;
+ int num_reduced_frame;
+
+ Assert(WindowObjectIsValid(winobj));
+ winstate = winobj->winstate;
+
switch (seektype)
{
case WINDOW_SEEK_CURRENT:
@@ -3494,11 +3753,21 @@ WinGetFuncArgInFrame(WindowObject winobj, int argno,
winstate->frameOptions);
break;
}
+ num_reduced_frame = row_is_in_reduced_frame(winobj, winstate->frameheadpos);
+ if (num_reduced_frame < 0)
+ goto out_of_frame;
+ else if (num_reduced_frame > 0)
+ if (relpos >= num_reduced_frame)
+ goto out_of_frame;
break;
case WINDOW_SEEK_TAIL:
/* rejecting relpos > 0 is easy and simplifies code below */
if (relpos > 0)
goto out_of_frame;
+
+ /* RPR cares about frame head pos. Need to call update_frameheadpos */
+ update_frameheadpos(winstate);
+
update_frametailpos(winstate);
abs_pos = winstate->frametailpos - 1 + relpos;
@@ -3565,6 +3834,12 @@ WinGetFuncArgInFrame(WindowObject winobj, int argno,
mark_pos = 0; /* keep compiler quiet */
break;
}
+
+ num_reduced_frame = row_is_in_reduced_frame(winobj, winstate->frameheadpos + relpos);
+ if (num_reduced_frame < 0)
+ goto out_of_frame;
+ else if (num_reduced_frame > 0)
+ abs_pos = winstate->frameheadpos + relpos + num_reduced_frame - 1;
break;
default:
elog(ERROR, "unrecognized window seek type: %d", seektype);
@@ -3583,15 +3858,13 @@ WinGetFuncArgInFrame(WindowObject winobj, int argno,
*isout = false;
if (set_mark)
WinSetMarkPosition(winobj, mark_pos);
- econtext->ecxt_outertuple = slot;
- return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno),
- econtext, isnull);
+ return 0;
out_of_frame:
if (isout)
*isout = true;
*isnull = true;
- return (Datum) 0;
+ return -1;
}
/*
@@ -3622,3 +3895,732 @@ WinGetFuncArgCurrent(WindowObject winobj, int argno, bool *isnull)
return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno),
econtext, isnull);
}
+
+/*
+ * rpr_is_defined
+ * return true if Row pattern recognition is defined.
+ */
+static
+bool rpr_is_defined(WindowAggState *winstate)
+{
+ return winstate->patternVariableList != NIL;
+}
+
+/*
+ * row_is_in_reduced_frame
+ * Determine whether a row is in the current row's reduced window frame according
+ * to row pattern matching
+ *
+ * The row must has been already determined that it is in a full window frame
+ * and fetched it into slot.
+ *
+ * Returns:
+ * = 0, RPR is not defined.
+ * >0, if the row is the first in the reduced frame. Return the number of rows in the reduced frame.
+ * -1, if the row is unmatched row
+ * -2, if the row is in the reduced frame but needed to be skipped because of
+ * AFTER MATCH SKIP PAST LAST ROW
+ */
+static
+int row_is_in_reduced_frame(WindowObject winobj, int64 pos)
+{
+ WindowAggState *winstate = winobj->winstate;
+ int state;
+ int rtn;
+
+ if (!rpr_is_defined(winstate))
+ {
+ /*
+ * RPR is not defined. Assume that we are always in the the reduced
+ * window frame.
+ */
+ rtn = 0;
+ elog(DEBUG1, "row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT, rtn, pos);
+ return rtn;
+ }
+
+ state = get_reduced_frame_map(winstate, pos);
+
+ if (state == RF_NOT_DETERMINED)
+ {
+ update_frameheadpos(winstate);
+ update_reduced_frame(winobj, pos);
+ }
+
+ state = get_reduced_frame_map(winstate, pos);
+
+ switch (state)
+ {
+ int64 i;
+ int num_reduced_rows;
+
+ case RF_FRAME_HEAD:
+ num_reduced_rows = 1;
+ for (i = pos + 1; get_reduced_frame_map(winstate,i) == RF_SKIPPED; i++)
+ num_reduced_rows++;
+ rtn = num_reduced_rows;
+ break;
+
+ case RF_SKIPPED:
+ rtn = -2;
+ break;
+
+ case RF_UNMATCHED:
+ rtn = -1;
+ break;
+
+ default:
+ elog(ERROR, "Unrecognized state: %d at: " INT64_FORMAT, state, pos);
+ break;
+ }
+
+ elog(DEBUG1, "row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT, rtn, pos);
+ return rtn;
+}
+
+#define REDUCED_FRAME_MAP_INIT_SIZE 1024L
+
+/*
+ * Create reduced frame map
+ */
+static
+void create_reduced_frame_map(WindowAggState *winstate)
+{
+ winstate->reduced_frame_map =
+ MemoryContextAlloc(winstate->partcontext, REDUCED_FRAME_MAP_INIT_SIZE);
+ winstate->alloc_sz = REDUCED_FRAME_MAP_INIT_SIZE;
+ clear_reduced_frame_map(winstate);
+}
+
+/*
+ * Clear reduced frame map
+ */
+static
+void clear_reduced_frame_map(WindowAggState *winstate)
+{
+ Assert(winstate->reduced_frame_map != NULL);
+ MemSet(winstate->reduced_frame_map, RF_NOT_DETERMINED,
+ winstate->alloc_sz);
+}
+
+/*
+ * Get reduced frame map specified by pos
+ */
+static
+int get_reduced_frame_map(WindowAggState *winstate, int64 pos)
+{
+ Assert(winstate->reduced_frame_map != NULL);
+
+ if (pos < 0 || pos >= winstate->alloc_sz)
+ elog(ERROR, "wrong pos: " INT64_FORMAT, pos);
+
+ return winstate->reduced_frame_map[pos];
+}
+
+/*
+ * Add/replace reduced frame map member at pos.
+ * If there's no enough space, expand the map.
+ */
+static
+void register_reduced_frame_map(WindowAggState *winstate, int64 pos, int val)
+{
+ int64 realloc_sz;
+
+ Assert(winstate->reduced_frame_map != NULL);
+
+ if (pos < 0)
+ elog(ERROR, "wrong pos: " INT64_FORMAT, pos);
+
+ if (pos > winstate->alloc_sz - 1)
+ {
+ realloc_sz = winstate->alloc_sz * 2;
+
+ winstate->reduced_frame_map =
+ repalloc(winstate->reduced_frame_map, realloc_sz);
+
+ MemSet(winstate->reduced_frame_map + winstate->alloc_sz,
+ RF_NOT_DETERMINED, realloc_sz - winstate->alloc_sz);
+
+ winstate->alloc_sz = realloc_sz;
+ }
+
+ winstate->reduced_frame_map[pos] = val;
+}
+
+/*
+ * update_reduced_frame
+ * Update reduced frame info.
+ */
+static
+void update_reduced_frame(WindowObject winobj, int64 pos)
+{
+ WindowAggState *winstate = winobj->winstate;
+ ListCell *lc1, *lc2;
+ bool expression_result;
+ int num_matched_rows;
+ int64 original_pos;
+ bool anymatch;
+ StringInfo encoded_str;
+ StringInfo pattern_str = makeStringInfo();
+ StringSet *str_set;
+ int str_set_index = 0;
+
+ /*
+ * Set of pattern variables evaluted to true.
+ * Each character corresponds to pattern variable.
+ * Example:
+ * str_set[0] = "AB";
+ * str_set[1] = "AC";
+ * In this case at row 0 A and B are true, and A and C are true in row 1.
+ */
+
+ /* initialize pattern variables set */
+ str_set = string_set_init();
+
+ /* save original pos */
+ original_pos = pos;
+
+ /*
+ * Loop over until none of pattern matches or encounters end of frame.
+ */
+ for (;;)
+ {
+ int64 result_pos = -1;
+
+ /*
+ * Loop over each PATTERN variable.
+ */
+ anymatch = false;
+ encoded_str = makeStringInfo();
+
+ forboth(lc1, winstate->patternVariableList, lc2, winstate->patternRegexpList)
+ {
+ char *vname = strVal(lfirst(lc1));
+ char *quantifier = strVal(lfirst(lc2));
+
+ elog(DEBUG1, "pos: " INT64_FORMAT " pattern vname: %s quantifier: %s", pos, vname, quantifier);
+
+ expression_result = false;
+
+ /* evaluate row pattern against current row */
+ result_pos = evaluate_pattern(winobj, pos, vname, encoded_str, &expression_result);
+ if (expression_result)
+ {
+ elog(DEBUG1, "expression result is true");
+ anymatch = true;
+ }
+
+ /*
+ * If out of frame, we are done.
+ */
+ if (result_pos < 0)
+ break;
+ }
+
+ if (!anymatch)
+ {
+ /* none of patterns matched. */
+ break;
+ }
+
+ string_set_add(str_set, encoded_str);
+
+ elog(DEBUG1, "pos: " INT64_FORMAT " str_set_index: %d encoded_str: %s", pos, str_set_index, encoded_str->data);
+
+ /* move to next row */
+ pos++;
+
+ if (result_pos < 0)
+ {
+ /* out of frame */
+ break;
+ }
+ }
+
+ if (string_set_get_size(str_set) == 0)
+ {
+ /* no match found in the first row */
+ register_reduced_frame_map(winstate, original_pos, RF_UNMATCHED);
+ return;
+ }
+
+ elog(DEBUG2, "pos: " INT64_FORMAT " encoded_str: %s", pos, encoded_str->data);
+
+ /* build regular expression */
+ pattern_str = makeStringInfo();
+ appendStringInfoChar(pattern_str, '^');
+ forboth (lc1, winstate->patternVariableList, lc2, winstate->patternRegexpList)
+ {
+ char *vname = strVal(lfirst(lc1));
+ char *quantifier = strVal(lfirst(lc2));
+ char initial;
+
+ initial = pattern_initial(winstate, vname);
+ Assert(initial != 0);
+ appendStringInfoChar(pattern_str, initial);
+ if (quantifier[0])
+ appendStringInfoChar(pattern_str, quantifier[0]);
+ elog(DEBUG1, "vname: %s initial: %c quantifier: %s", vname, initial, quantifier);
+ }
+
+ elog(DEBUG2, "pos: " INT64_FORMAT " pattern: %s", pos, pattern_str->data);
+
+ /* look for matching pattern variable sequence */
+ num_matched_rows = search_str_set(pattern_str->data, str_set);
+ /*
+ * We are at the first row in the reduced frame. Save the number of
+ * matched rows as the number of rows in the reduced frame.
+ */
+ if (num_matched_rows <= 0)
+ {
+ /* no match */
+ register_reduced_frame_map(winstate, original_pos, RF_UNMATCHED);
+ }
+ else
+ {
+ int64 i;
+
+ register_reduced_frame_map(winstate, original_pos, RF_FRAME_HEAD);
+
+ for (i = original_pos + 1; i < original_pos + num_matched_rows; i++)
+ {
+ register_reduced_frame_map(winstate, i, RF_SKIPPED);
+ }
+ }
+
+ return;
+}
+
+/*
+ * Perform pattern matching using pattern against str_set. str_set is a set
+ * of StringInfo. Each StringInfo has a string comprising initial characters
+ * of pattern variables being true in a row. Returns the longest number of
+ * the matching rows.
+ */
+static
+int search_str_set(char *pattern, StringSet *str_set)
+{
+ int set_size; /* number of rows in the set */
+ int resultlen = 0;
+ int index;
+ StringSet *old_str_set, *new_str_set;
+ int new_str_size;
+
+ set_size = string_set_get_size(str_set);
+ new_str_set = string_set_init();
+
+ /*
+ * Generate all possible pattern variable name initials as a set of
+ * StringInfo named "new_str_set". For example, if we have two rows
+ * having "ab" (row 0) and "ac" (row 1) in the input str_set, new_str_set
+ * will have set of StringInfo "aa", "ac", "ba" and "bc" in the end.
+ */
+ for (index = 0; index < set_size; index++)
+ {
+ StringInfo str; /* search target row */
+ char *p;
+ int old_set_size;
+ int i;
+
+ if (index == 0)
+ {
+ /* copy variables in row 0 */
+ str = string_set_get(str_set, index);
+ p = str->data;
+
+ /*
+ * loop over each new pattern variable char in previous result
+ * char.
+ */
+ while (*p)
+ {
+ StringInfo new = makeStringInfo();
+
+ /* add pattern variable char */
+ appendStringInfoChar(new, *p);
+ /* add new one to string set */
+ string_set_add(new_str_set, new);
+ p++; /* next pattern variable */
+ }
+ }
+ else
+ {
+ old_str_set = new_str_set;
+ new_str_set = string_set_init();
+ str = string_set_get(str_set, index);
+ old_set_size = string_set_get_size(old_str_set);
+
+ /*
+ * loop over each rows in the previous result set.
+ */
+ for (i = 0; i < old_set_size ; i++)
+ {
+ StringInfo old = string_set_get(old_str_set, i);
+
+ p = str->data;
+
+ /*
+ * loop over each pattern variable char in the input set.
+ */
+ while (*p)
+ {
+ StringInfo new = makeStringInfo();
+
+ /* copy source string */
+ appendStringInfoString(new, old->data);
+ /* add pattern variable char */
+ appendStringInfoChar(new, *p);
+ /* add new one to string set */
+ string_set_add(new_str_set, new);
+ p++; /* next pattern variable */
+ }
+ }
+ /* we no long need old string set */
+ string_set_discard(old_str_set);
+ }
+ }
+
+ /*
+ * Perform pattern matching to find out the longest match.
+ */
+ new_str_size = string_set_get_size(new_str_set);
+
+ for (index = 0; index < new_str_size; index++)
+ {
+ int len;
+ StringInfo s;
+
+ s = string_set_get(new_str_set, index);
+ if (s == NULL)
+ continue; /* no data */
+
+ len = do_pattern_match(pattern, s->data);
+ if (len > resultlen)
+ {
+ /* remember the longest match */
+ resultlen = len;
+
+ /*
+ * If the size of result set is equal to the number of rows in the
+ * set, we are done because it's not possible that the number of
+ * matching rows exceeds the number of rows in the set.
+ */
+ if (resultlen >= set_size)
+ break;
+ }
+ }
+
+ /* we no long need new string set */
+ string_set_discard(new_str_set);
+
+ return resultlen;
+}
+
+/*
+ * do_pattern_match
+ * perform pattern match using pattern against encoded_str.
+ * returns matching number of rows if matching is succeeded.
+ * Otherwise returns 0.
+ */
+static
+int do_pattern_match(char *pattern, char *encoded_str)
+{
+ Datum d;
+ text *res;
+ char *substr;
+ int len = 0;
+
+
+ /*
+ * We first perform pattern matching using regexp_instr, then call
+ * textregexsubstr to get matched substring to know how long the
+ * matched string is. That is the number of rows in the reduced window
+ * frame. The reason why we can't call textregexsubstr in the first
+ * place is, it errors out if pattern does not match.
+ */
+ if (DatumGetInt32(DirectFunctionCall2Coll(regexp_instr, DEFAULT_COLLATION_OID,
+ PointerGetDatum(cstring_to_text(encoded_str)),
+ PointerGetDatum(cstring_to_text(pattern)))) > 0)
+ {
+ d = DirectFunctionCall2Coll(textregexsubstr,
+ DEFAULT_COLLATION_OID,
+ PointerGetDatum(cstring_to_text(encoded_str)),
+ PointerGetDatum(cstring_to_text(pattern)));
+ if (d != 0)
+ {
+ res = DatumGetTextPP(d);
+ substr = text_to_cstring(res);
+ len = strlen(substr);
+ }
+ }
+ return len;
+}
+
+
+/*
+ * Evaluate expression associated with PATTERN variable vname.
+ * relpos is relative row position in a frame (starting from 0).
+ * "quantifier" is the quatifier part of the PATTERN regular expression.
+ * Currently only '+' is allowed.
+ * result is out paramater representing the expression evaluation result
+ * is true of false.
+ * Return values are:
+ * >=0: the last match absolute row position
+ * other wise out of frame.
+ */
+static
+int64 evaluate_pattern(WindowObject winobj, int64 current_pos,
+ char *vname, StringInfo encoded_str, bool *result)
+{
+ WindowAggState *winstate = winobj->winstate;
+ ExprContext *econtext = winstate->ss.ps.ps_ExprContext;
+ ListCell *lc1, *lc2, *lc3;
+ ExprState *pat;
+ Datum eval_result;
+ bool out_of_frame = false;
+ bool isnull;
+
+ forthree (lc1, winstate->defineVariableList, lc2, winstate->defineClauseList, lc3, winstate->defineInitial)
+ {
+ char initial;
+ char *name = strVal(lfirst(lc1));
+
+ if (strcmp(vname, name))
+ continue;
+
+ initial = *(strVal(lfirst(lc3)));
+
+ /* set expression to evaluate */
+ pat = lfirst(lc2);
+
+ /* get current, previous and next tuples */
+ if (!get_slots(winobj, current_pos))
+ {
+ out_of_frame = true;
+ }
+ else
+ {
+ /* evaluate the expression */
+ eval_result = ExecEvalExpr(pat, econtext, &isnull);
+ if (isnull)
+ {
+ /* expression is NULL */
+ elog(DEBUG1, "expression for %s is NULL at row: " INT64_FORMAT, vname, current_pos);
+ *result = false;
+ }
+ else
+ {
+ if (!DatumGetBool(eval_result))
+ {
+ /* expression is false */
+ elog(DEBUG1, "expression for %s is false at row: " INT64_FORMAT, vname, current_pos);
+ *result = false;
+ }
+ else
+ {
+ /* expression is true */
+ elog(DEBUG1, "expression for %s is true at row: " INT64_FORMAT, vname, current_pos);
+ appendStringInfoChar(encoded_str, initial);
+ *result = true;
+ }
+ }
+ break;
+ }
+
+ if (out_of_frame)
+ {
+ *result = false;
+ return -1;
+ }
+ }
+ return current_pos;
+}
+
+/*
+ * Get current, previous and next tuples.
+ * Returns false if current row is out of partition/full frame.
+ */
+static
+bool get_slots(WindowObject winobj, int64 current_pos)
+{
+ WindowAggState *winstate = winobj->winstate;
+ TupleTableSlot *slot;
+ int ret;
+ ExprContext *econtext;
+
+ econtext = winstate->ss.ps.ps_ExprContext;
+
+ /* set up current row tuple slot */
+ slot = winstate->temp_slot_1;
+ if (!window_gettupleslot(winobj, current_pos, slot))
+ {
+ elog(DEBUG1, "current row is out of partition at:" INT64_FORMAT, current_pos);
+ return false;
+
+ ret = row_is_in_frame(winstate, current_pos, slot);
+ if (ret <= 0)
+ {
+ elog(DEBUG1, "current row is out of frame at: " INT64_FORMAT, current_pos);
+ return false;
+ }
+ }
+ econtext->ecxt_outertuple = slot;
+
+ /* for PREV */
+ if (current_pos > 0)
+ {
+ slot = winstate->prev_slot;
+ if (!window_gettupleslot(winobj, current_pos - 1, slot))
+ {
+ elog(DEBUG1, "previous row is out of partition at: " INT64_FORMAT, current_pos - 1);
+ econtext->ecxt_scantuple = winstate->null_slot;
+ }
+ else
+ {
+ ret = row_is_in_frame(winstate, current_pos - 1, slot);
+ if (ret <= 0)
+ {
+ elog(DEBUG1, "previous row is out of frame at: " INT64_FORMAT, current_pos - 1);
+ econtext->ecxt_scantuple = winstate->null_slot;
+ }
+ else
+ {
+ econtext->ecxt_scantuple = slot;
+ }
+ }
+ }
+ else
+ econtext->ecxt_scantuple = winstate->null_slot;
+
+ /* for NEXT */
+ slot = winstate->next_slot;
+ if (!window_gettupleslot(winobj, current_pos + 1, slot))
+ {
+ elog(DEBUG1, "next row is out of partiton at: " INT64_FORMAT, current_pos + 1);
+ econtext->ecxt_innertuple = winstate->null_slot;
+ }
+ else
+ {
+ ret = row_is_in_frame(winstate, current_pos + 1, slot);
+ if (ret <= 0)
+ {
+ elog(DEBUG1, "next row is out of frame at: " INT64_FORMAT, current_pos + 1);
+ econtext->ecxt_innertuple = winstate->null_slot;
+ }
+ else
+ econtext->ecxt_innertuple = slot;
+ }
+ return true;
+}
+
+/*
+ * Return pattern variable initial character
+ * matching with pattern variable name vname.
+ * If not found, return 0.
+ */
+static
+char pattern_initial(WindowAggState *winstate, char *vname)
+{
+ char initial;
+ char *name;
+ ListCell *lc1, *lc2;
+
+ forboth (lc1, winstate->defineVariableList, lc2, winstate->defineInitial)
+ {
+ name = strVal(lfirst(lc1)); /* DEFINE variable name */
+ initial = *(strVal(lfirst(lc2))); /* DEFINE variable initial */
+
+
+ if (!strcmp(name, vname))
+ return initial; /* found */
+ }
+ return 0;
+}
+
+/*
+ * string_set_init
+ * Create dynamic set of StringInfo.
+ */
+static
+StringSet *string_set_init(void)
+{
+/* Initial allocation size of str_set */
+#define STRING_SET_ALLOC_SIZE 1024
+
+ StringSet *string_set;
+ Size set_size;
+
+ string_set = palloc0(sizeof(StringSet));
+ string_set->set_index = 0;
+ set_size = STRING_SET_ALLOC_SIZE;
+ string_set->str_set = palloc(set_size * sizeof(StringInfo));
+ string_set->set_size = set_size;
+
+ return string_set;
+}
+
+/*
+ * Add StringInfo str to StringSet string_set.
+ */
+static
+void string_set_add(StringSet *string_set, StringInfo str)
+{
+ Size set_size;
+
+ set_size = string_set->set_size;
+ if (string_set->set_index >= set_size)
+ {
+ set_size *= 2;
+ string_set->str_set = repalloc(string_set->str_set,
+ set_size * sizeof(StringInfo));
+ string_set->set_size = set_size;
+ }
+
+ string_set->str_set[string_set->set_index++] = str;
+
+ return;
+}
+
+/*
+ * Returns StringInfo specified by index.
+ * If there's no data yet, returns NULL.
+ */
+static
+StringInfo string_set_get(StringSet *string_set, int index)
+{
+ /* no data? */
+ if (index == 0 && string_set->set_index == 0)
+ return NULL;
+
+ if (index < 0 ||index >= string_set->set_index)
+ elog(ERROR, "invalid index: %d", index);
+
+ return string_set->str_set[index];
+}
+
+/*
+ * Returns the size of StringSet.
+ */
+static
+int string_set_get_size(StringSet *string_set)
+{
+ return string_set->set_index;
+}
+
+/*
+ * Discard StringSet.
+ * All memory including StringSet itself is freed.
+ */
+static
+void string_set_discard(StringSet *string_set)
+{
+ int i;
+
+ for (i = 0; i < string_set->set_index; i++)
+ {
+ StringInfo str = string_set->str_set[i];
+ pfree(str->data);
+ pfree(str);
+ }
+ pfree(string_set);
+}
diff --git a/src/backend/utils/adt/windowfuncs.c b/src/backend/utils/adt/windowfuncs.c
index b87a624fb2..9ebcc7b5d2 100644
--- a/src/backend/utils/adt/windowfuncs.c
+++ b/src/backend/utils/adt/windowfuncs.c
@@ -13,6 +13,9 @@
*/
#include "postgres.h"
+#include "catalog/pg_collation_d.h"
+#include "executor/executor.h"
+#include "nodes/execnodes.h"
#include "nodes/supportnodes.h"
#include "utils/builtins.h"
#include "windowapi.h"
@@ -36,11 +39,19 @@ typedef struct
int64 remainder; /* (total rows) % (bucket num) */
} ntile_context;
+/*
+ * rpr process information.
+ * Used for AFTER MATCH SKIP PAST LAST ROW
+ */
+typedef struct SkipContext
+{
+ int64 pos; /* last row absolute position */
+} SkipContext;
+
static bool rank_up(WindowObject winobj);
static Datum leadlag_common(FunctionCallInfo fcinfo,
bool forward, bool withoffset, bool withdefault);
-
/*
* utility routine for *_rank functions.
*/
@@ -673,7 +684,7 @@ window_last_value(PG_FUNCTION_ARGS)
bool isnull;
result = WinGetFuncArgInFrame(winobj, 0,
- 0, WINDOW_SEEK_TAIL, true,
+ 0, WINDOW_SEEK_TAIL, false,
&isnull, NULL);
if (isnull)
PG_RETURN_NULL();
@@ -713,3 +724,25 @@ window_nth_value(PG_FUNCTION_ARGS)
PG_RETURN_DATUM(result);
}
+
+/*
+ * prev
+ * Dummy function to invoke RPR's navigation operator "PREV".
+ * This is *not* a window function.
+ */
+Datum
+window_prev(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_DATUM(PG_GETARG_DATUM(0));
+}
+
+/*
+ * next
+ * Dummy function to invoke RPR's navigation operation "NEXT".
+ * This is *not* a window function.
+ */
+Datum
+window_next(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_DATUM(PG_GETARG_DATUM(0));
+}
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 9805bc6118..d20f803cf5 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -10416,6 +10416,12 @@
{ oid => '3114', descr => 'fetch the Nth row value',
proname => 'nth_value', prokind => 'w', prorettype => 'anyelement',
proargtypes => 'anyelement int4', prosrc => 'window_nth_value' },
+{ oid => '6122', descr => 'previous value',
+ proname => 'prev', provolatile => 's', prorettype => 'anyelement',
+ proargtypes => 'anyelement', prosrc => 'window_prev' },
+{ oid => '6123', descr => 'next value',
+ proname => 'next', provolatile => 's', prorettype => 'anyelement',
+ proargtypes => 'anyelement', prosrc => 'window_next' },
# functions for range types
{ oid => '3832', descr => 'I/O',
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index cb714f4a19..63feb68f60 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2471,6 +2471,11 @@ typedef enum WindowAggStatus
* tuples during spool */
} WindowAggStatus;
+#define RF_NOT_DETERMINED 0
+#define RF_FRAME_HEAD 1
+#define RF_SKIPPED 2
+#define RF_UNMATCHED 3
+
typedef struct WindowAggState
{
ScanState ss; /* its first field is NodeTag */
@@ -2519,6 +2524,15 @@ typedef struct WindowAggState
int64 groupheadpos; /* current row's peer group head position */
int64 grouptailpos; /* " " " " tail position (group end+1) */
+ /* these fields are used in Row pattern recognition: */
+ RPSkipTo rpSkipTo; /* Row Pattern Skip To type */
+ List *patternVariableList; /* list of row pattern variables names (list of String) */
+ List *patternRegexpList; /* list of row pattern regular expressions ('+' or ''. list of String) */
+ List *defineVariableList; /* list of row pattern definition variables (list of String) */
+ List *defineClauseList; /* expression for row pattern definition
+ * search conditions ExprState list */
+ List *defineInitial; /* list of row pattern definition variable initials (list of String) */
+
MemoryContext partcontext; /* context for partition-lifespan data */
MemoryContext aggcontext; /* shared context for aggregate working data */
MemoryContext curaggcontext; /* current aggregate's working data */
@@ -2555,6 +2569,18 @@ typedef struct WindowAggState
TupleTableSlot *agg_row_slot;
TupleTableSlot *temp_slot_1;
TupleTableSlot *temp_slot_2;
+
+ /* temporary slots for RPR */
+ TupleTableSlot *prev_slot; /* PREV row navigation operator */
+ TupleTableSlot *next_slot; /* NEXT row navigation operator */
+ TupleTableSlot *null_slot; /* all NULL slot */
+
+ /*
+ * Each byte corresponds to a row positioned at absolute its pos in
+ * partition. See above definition for RF_*
+ */
+ char *reduced_frame_map;
+ int64 alloc_sz; /* size of the map */
} WindowAggState;
/* ----------------
--
2.25.1
----Next_Part(Mon_Sep_25_14_26_30_2023_752)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="v8-0005-Row-pattern-recognition-patch-docs.patch"
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Parallel CREATE INDEX for BRIN indexes
@ 2024-04-13 08:36 Andres Freund <[email protected]>
2024-04-13 09:19 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Andres Freund @ 2024-04-13 08:36 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>
Hi,
While preparing a differential code coverage report between 16 and HEAD, one
thing that stands out is the parallel brin build code. Neither on
coverage.postgresql.org nor locally is that code reached during our tests.
https://coverage.postgresql.org/src/backend/access/brin/brin.c.gcov.html#2333
Greetings,
Andres Freund
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Parallel CREATE INDEX for BRIN indexes
2024-04-13 08:36 Re: Parallel CREATE INDEX for BRIN indexes Andres Freund <[email protected]>
@ 2024-04-13 09:19 ` Tomas Vondra <[email protected]>
2024-04-13 21:04 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Tomas Vondra @ 2024-04-13 09:19 UTC (permalink / raw)
To: Andres Freund <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>
On 4/13/24 10:36, Andres Freund wrote:
> Hi,
>
> While preparing a differential code coverage report between 16 and HEAD, one
> thing that stands out is the parallel brin build code. Neither on
> coverage.postgresql.org nor locally is that code reached during our tests.
>
Thanks for pointing this out, it's definitely something that I need to
improve (admittedly, should have been part of the patch). I'll also look
into eliminating the difference between BTREE and BRIN parallel builds,
mentioned in my last message in this thread.
regards
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Parallel CREATE INDEX for BRIN indexes
2024-04-13 08:36 Re: Parallel CREATE INDEX for BRIN indexes Andres Freund <[email protected]>
2024-04-13 09:19 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
@ 2024-04-13 21:04 ` Tomas Vondra <[email protected]>
2024-08-15 13:48 ` Re: Parallel CREATE INDEX for BRIN indexes Peter Eisentraut <[email protected]>
0 siblings, 1 reply; 5+ messages in thread
From: Tomas Vondra @ 2024-04-13 21:04 UTC (permalink / raw)
To: Andres Freund <[email protected]>; +Cc: Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>
On 4/13/24 11:19, Tomas Vondra wrote:
> On 4/13/24 10:36, Andres Freund wrote:
>> Hi,
>>
>> While preparing a differential code coverage report between 16 and HEAD, one
>> thing that stands out is the parallel brin build code. Neither on
>> coverage.postgresql.org nor locally is that code reached during our tests.
>>
>
> Thanks for pointing this out, it's definitely something that I need to
> improve (admittedly, should have been part of the patch). I'll also look
> into eliminating the difference between BTREE and BRIN parallel builds,
> mentioned in my last message in this thread.
>
Here's a couple patches adding a test for the parallel CREATE INDEX with
BRIN. The actual test is 0003/0004 - I added the test to pageinspect,
because that allows cross-checking the index to one built without
parallelism, which I think is better than just doing CREATE INDEX
without properly testing it produces correct results.
It's not entirely trivial because for some opclasses (e.g. minmax-multi)
the results depend on the order in which values are added, and order in
which summaries from different workers are merged.
Funnily enough, while adding the test, I ran into two pre-existing bugs.
One is that brin_bloom_union forgot to update the number of bits set in
the bitmap, another one is that 6bcda4a721 changes PG_DETOAST_DATUM to
the _PACKED version, which however does the wrong thing. Both of which
are mostly harmless - it only affects the output function, which is
unused outside pageinspect. No impact on query correctness etc.
The test needs a bit more work to make sure it works on 32-bit machines
etc. which I think may affect available space on a page, which in turn
might affect the minmax-multi summaries. But I'll take care this early
next week.
Funnily
--
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
Attachments:
[text/x-patch] v20240413-0001-Update-nbits_set-in-brin_bloom_union.patch (1.2K, ../../[email protected]/2-v20240413-0001-Update-nbits_set-in-brin_bloom_union.patch)
download | inline diff:
From 450f992c12d43c14aa1b4b72cfd9d3ce0251eed1 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Sat, 13 Apr 2024 22:15:26 +0200
Subject: [PATCH v20240413 1/4] Update nbits_set in brin_bloom_union
When merging BRIN bloom summaries, it's not enough to merge the bitmaps,
we need to update the nbits_set counter too.
This is mostly harmless, as it does not affect correctness - as the
counter is used only in the out function, and that's used only in
pageinspect to show basic info about the summary.
Backpatch-through: 14
---
src/backend/access/brin/brin_bloom.c | 10 ++++++++++
1 file changed, 10 insertions(+)
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index ebf33016279..9e3bc567303 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -687,10 +687,20 @@ brin_bloom_union(PG_FUNCTION_ARGS)
nbytes = (filter_a->nbits) / 8;
+ filter_a->nbits_set = 0;
+
/* simply OR the bitmaps */
for (i = 0; i < nbytes; i++)
+ {
filter_a->data[i] |= filter_b->data[i];
+ for (int bit = 0; bit < 8; bit++)
+ {
+ if (filter_a->data[i] & (0x01 << bit))
+ filter_a->nbits_set++;
+ }
+ }
+
PG_RETURN_VOID();
}
--
2.44.0
[text/x-patch] v20240413-0002-Use-correct-PG_DETOAST_DATUM-macro-in-BRIN.patch (1.9K, ../../[email protected]/3-v20240413-0002-Use-correct-PG_DETOAST_DATUM-macro-in-BRIN.patch)
download | inline diff:
From 07739713893bb0f6be5853324e8897159cf2ad07 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Sat, 13 Apr 2024 22:18:37 +0200
Subject: [PATCH v20240413 2/4] Use correct PG_DETOAST_DATUM macro in BRIN
Commit 6bcda4a721 replaced PG_DETOAST_DATUM with PG_DETOAST_DATUM_PACKED
in two places, in output function for minmax-multi and bloom. But this
is incorrect - the structs backing both summaries include 4B header, so
we need to detoast them fully. With _PACKED we may end up with 1B
header, so the fields will be shifted and have incorrect values.
Backpatch-through: 16
---
src/backend/access/brin/brin_bloom.c | 2 +-
src/backend/access/brin/brin_minmax_multi.c | 2 +-
2 files changed, 2 insertions(+), 2 deletions(-)
diff --git a/src/backend/access/brin/brin_bloom.c b/src/backend/access/brin/brin_bloom.c
index 9e3bc567303..1c2437cef74 100644
--- a/src/backend/access/brin/brin_bloom.c
+++ b/src/backend/access/brin/brin_bloom.c
@@ -807,7 +807,7 @@ brin_bloom_summary_out(PG_FUNCTION_ARGS)
StringInfoData str;
/* detoast the data to get value with a full 4B header */
- filter = (BloomFilter *) PG_DETOAST_DATUM_PACKED(PG_GETARG_DATUM(0));
+ filter = (BloomFilter *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
initStringInfo(&str);
appendStringInfoChar(&str, '{');
diff --git a/src/backend/access/brin/brin_minmax_multi.c b/src/backend/access/brin/brin_minmax_multi.c
index c5962c00d64..e5d95de5d84 100644
--- a/src/backend/access/brin/brin_minmax_multi.c
+++ b/src/backend/access/brin/brin_minmax_multi.c
@@ -3023,7 +3023,7 @@ brin_minmax_multi_summary_out(PG_FUNCTION_ARGS)
* Detoast to get value with full 4B header (can't be stored in a toast
* table, but can use 1B header).
*/
- ranges = (SerializedRanges *) PG_DETOAST_DATUM_PACKED(PG_GETARG_DATUM(0));
+ ranges = (SerializedRanges *) PG_DETOAST_DATUM(PG_GETARG_DATUM(0));
/* lookup output func for the type */
getTypeOutputInfo(ranges->typid, &outfunc, &isvarlena);
--
2.44.0
[text/x-patch] v20240413-0003-Add-regression-tests-for-BRIN-parallel-bui.patch (11.1K, ../../[email protected]/4-v20240413-0003-Add-regression-tests-for-BRIN-parallel-bui.patch)
download | inline diff:
From e6c8c6f5d1d9420a5166512af25e7c3407a877d1 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Sat, 13 Apr 2024 22:25:35 +0200
Subject: [PATCH v20240413 3/4] Add regression tests for BRIN parallel builds
Adds regression test for parallel CREATE INDEX with a BRIN index. The
test is added to pageinspect, and which makes it easy to compare the
parallel index to an index built without parallelism.
---
contrib/pageinspect/expected/brin.out | 106 ++++++++++++++++++++++++++
contrib/pageinspect/sql/brin.sql | 85 +++++++++++++++++++++
2 files changed, 191 insertions(+)
diff --git a/contrib/pageinspect/expected/brin.out b/contrib/pageinspect/expected/brin.out
index 3f6e5174bc6..66b199dba8a 100644
--- a/contrib/pageinspect/expected/brin.out
+++ b/contrib/pageinspect/expected/brin.out
@@ -108,3 +108,109 @@ SELECT (COUNT(*) = (SELECT relpages FROM pg_class WHERE relname = 'test2')) AS r
DROP TABLE test1;
DROP TABLE test2;
+-- test that parallel index build produces the same BRIN index as serial build
+CREATE TABLE brin_parallel_test (a int, b text) WITH (fillfactor=25);
+-- a mix of NULLs and non-NULL values
+INSERT INTO brin_parallel_test
+SELECT (CASE WHEN (mod(i,231) = 0) OR (i BETWEEN 3500 AND 4000) THEN NULL ELSE i END),
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END)
+ FROM generate_series(1,10000) S(i);
+-- delete a couple pages, to make a range empty
+DELETE FROM brin_parallel_test WHERE a BETWEEN 1000 and 2000;
+-- vacuum to make the ranges actually empty
+VACUUM brin_parallel_test;
+-- We build index with different BRIN opclasses, but we can't use minmax-multi
+-- because the summary is not deterministic (i.e. the order of values affects
+-- how ranges get merged, and if workers see random subsets between runs, that
+-- affects the resulting summaries too). The summaries are equivalent in the
+-- sense that should give the same query results, but look different enough to
+-- not be very useful/convenient for this test.
+SET max_parallel_maintenance_workers = 0;
+CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+-- XXX we have to set some parameters to force parallel build, both because
+-- there's a requirement for table size and plan_create_index_workers assumes
+-- each worker will use work_mem=32MB for sorting (which works for btree, but
+-- not really for BRIN)
+SET min_parallel_table_scan_size = 0;
+SET max_parallel_maintenance_workers = 4;
+SET maintenance_work_mem = '128MB';
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
+ relname | relpages
+------------------------+----------
+ brin_test_parallel_idx | 4
+ brin_test_serial_idx | 4
+(2 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+-- now do the same parallel build, but don't allow starting parallel workers
+-- to force fallback to serial build, and repeat the checks
+DROP INDEX brin_test_parallel_idx;
+SET max_parallel_workers = 0;
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
+ relname | relpages
+------------------------+----------
+ brin_test_parallel_idx | 4
+ brin_test_serial_idx | 4
+(2 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx');
+ itemoffset | blknum | attnum | allnulls | hasnulls | placeholder | empty | value
+------------+--------+--------+----------+----------+-------------+-------+-------
+(0 rows)
+
+DROP TABLE brin_parallel_test;
+RESET min_parallel_table_scan_size;
+RESET max_parallel_maintenance_workers;
+RESET maintenance_work_mem;
diff --git a/contrib/pageinspect/sql/brin.sql b/contrib/pageinspect/sql/brin.sql
index 50f260b8e1f..affd805bb27 100644
--- a/contrib/pageinspect/sql/brin.sql
+++ b/contrib/pageinspect/sql/brin.sql
@@ -54,3 +54,88 @@ SELECT (COUNT(*) = (SELECT relpages FROM pg_class WHERE relname = 'test2')) AS r
DROP TABLE test1;
DROP TABLE test2;
+
+-- test that parallel index build produces the same BRIN index as serial build
+CREATE TABLE brin_parallel_test (a int, b text) WITH (fillfactor=25);
+
+-- a mix of NULLs and non-NULL values
+INSERT INTO brin_parallel_test
+SELECT (CASE WHEN (mod(i,231) = 0) OR (i BETWEEN 3500 AND 4000) THEN NULL ELSE i END),
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END)
+ FROM generate_series(1,10000) S(i);
+
+-- delete a couple pages, to make a range empty
+DELETE FROM brin_parallel_test WHERE a BETWEEN 1000 and 2000;
+
+-- vacuum to make the ranges actually empty
+VACUUM brin_parallel_test;
+
+-- We build index with different BRIN opclasses, but we can't use minmax-multi
+-- because the summary is not deterministic (i.e. the order of values affects
+-- how ranges get merged, and if workers see random subsets between runs, that
+-- affects the resulting summaries too). The summaries are equivalent in the
+-- sense that should give the same query results, but look different enough to
+-- not be very useful/convenient for this test.
+SET max_parallel_maintenance_workers = 0;
+CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+
+-- XXX we have to set some parameters to force parallel build, both because
+-- there's a requirement for table size and plan_create_index_workers assumes
+-- each worker will use work_mem=32MB for sorting (which works for btree, but
+-- not really for BRIN)
+SET min_parallel_table_scan_size = 0;
+SET max_parallel_maintenance_workers = 4;
+SET maintenance_work_mem = '128MB';
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+
+SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx');
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx');
+
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx');
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx');
+
+-- now do the same parallel build, but don't allow starting parallel workers
+-- to force fallback to serial build, and repeat the checks
+
+DROP INDEX brin_test_parallel_idx;
+
+SET max_parallel_workers = 0;
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+
+SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx');
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 2), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 2), 'brin_test_parallel_idx');
+
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx');
+
+SELECT * FROM brin_page_items(get_raw_page('brin_test_serial_idx', 3), 'brin_test_serial_idx')
+EXCEPT
+SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_test_parallel_idx');
+
+
+DROP TABLE brin_parallel_test;
+RESET min_parallel_table_scan_size;
+RESET max_parallel_maintenance_workers;
+RESET maintenance_work_mem;
--
2.44.0
[text/x-patch] v20240413-0004-add-minmax-multi-to-the-regression-test.patch (8.5K, ../../[email protected]/5-v20240413-0004-add-minmax-multi-to-the-regression-test.patch)
download | inline diff:
From a79446bdc46c85ae9e9386e55bc3f7da43523106 Mon Sep 17 00:00:00 2001
From: Tomas Vondra <[email protected]>
Date: Sat, 13 Apr 2024 22:50:53 +0200
Subject: [PATCH v20240413 4/4] add minmax-multi to the regression test
---
contrib/pageinspect/expected/brin.out | 25 ++++++++++++++-----------
contrib/pageinspect/sql/brin.sql | 25 ++++++++++++++-----------
2 files changed, 28 insertions(+), 22 deletions(-)
diff --git a/contrib/pageinspect/expected/brin.out b/contrib/pageinspect/expected/brin.out
index 66b199dba8a..33e565f8300 100644
--- a/contrib/pageinspect/expected/brin.out
+++ b/contrib/pageinspect/expected/brin.out
@@ -109,24 +109,27 @@ SELECT (COUNT(*) = (SELECT relpages FROM pg_class WHERE relname = 'test2')) AS r
DROP TABLE test1;
DROP TABLE test2;
-- test that parallel index build produces the same BRIN index as serial build
-CREATE TABLE brin_parallel_test (a int, b text) WITH (fillfactor=25);
+CREATE TABLE brin_parallel_test (a int, b text, c bigint) WITH (fillfactor=40);
-- a mix of NULLs and non-NULL values
INSERT INTO brin_parallel_test
SELECT (CASE WHEN (mod(i,231) = 0) OR (i BETWEEN 3500 AND 4000) THEN NULL ELSE i END),
- (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END)
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END),
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE (i/40) + mod(i,8) END)
FROM generate_series(1,10000) S(i);
-- delete a couple pages, to make a range empty
DELETE FROM brin_parallel_test WHERE a BETWEEN 1000 and 2000;
-- vacuum to make the ranges actually empty
VACUUM brin_parallel_test;
--- We build index with different BRIN opclasses, but we can't use minmax-multi
--- because the summary is not deterministic (i.e. the order of values affects
--- how ranges get merged, and if workers see random subsets between runs, that
--- affects the resulting summaries too). The summaries are equivalent in the
--- sense that should give the same query results, but look different enough to
--- not be very useful/convenient for this test.
+-- We build index with different BRIN opclasses - minmax, bloom and minmax-multi.
+-- With minmax-multi we need to be more careful, because the summary is not
+-- entirely deterministic - the order of values affects how ranges get merged,
+-- and if workers see random subsets between runs, that affects the resulting
+-- summaries too). The summaries would be equivalent in the sense that should
+-- give the same query results, but are not equal for EXCEPT to work. To work
+-- around that, we generate only small number of values to keep exact values,
+-- in which case the ordering does not matter.
SET max_parallel_maintenance_workers = 0;
-CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b, c int8_minmax_multi_ops) WITH (pages_per_range=7);
-- XXX we have to set some parameters to force parallel build, both because
-- there's a requirement for table size and plan_create_index_workers assumes
-- each worker will use work_mem=32MB for sorting (which works for btree, but
@@ -134,7 +137,7 @@ CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minma
SET min_parallel_table_scan_size = 0;
SET max_parallel_maintenance_workers = 4;
SET maintenance_work_mem = '128MB';
-CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b, c int8_minmax_multi_ops) WITH (pages_per_range=7);
SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
relname | relpages
------------------------+----------
@@ -174,7 +177,7 @@ SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_t
-- to force fallback to serial build, and repeat the checks
DROP INDEX brin_test_parallel_idx;
SET max_parallel_workers = 0;
-CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b, c int8_minmax_multi_ops) WITH (pages_per_range=7);
SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
relname | relpages
------------------------+----------
diff --git a/contrib/pageinspect/sql/brin.sql b/contrib/pageinspect/sql/brin.sql
index affd805bb27..f113de39c5d 100644
--- a/contrib/pageinspect/sql/brin.sql
+++ b/contrib/pageinspect/sql/brin.sql
@@ -56,12 +56,13 @@ DROP TABLE test1;
DROP TABLE test2;
-- test that parallel index build produces the same BRIN index as serial build
-CREATE TABLE brin_parallel_test (a int, b text) WITH (fillfactor=25);
+CREATE TABLE brin_parallel_test (a int, b text, c bigint) WITH (fillfactor=40);
-- a mix of NULLs and non-NULL values
INSERT INTO brin_parallel_test
SELECT (CASE WHEN (mod(i,231) = 0) OR (i BETWEEN 3500 AND 4000) THEN NULL ELSE i END),
- (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END)
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END),
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE (i/40) + mod(i,8) END)
FROM generate_series(1,10000) S(i);
-- delete a couple pages, to make a range empty
@@ -70,14 +71,16 @@ DELETE FROM brin_parallel_test WHERE a BETWEEN 1000 and 2000;
-- vacuum to make the ranges actually empty
VACUUM brin_parallel_test;
--- We build index with different BRIN opclasses, but we can't use minmax-multi
--- because the summary is not deterministic (i.e. the order of values affects
--- how ranges get merged, and if workers see random subsets between runs, that
--- affects the resulting summaries too). The summaries are equivalent in the
--- sense that should give the same query results, but look different enough to
--- not be very useful/convenient for this test.
+-- We build index with different BRIN opclasses - minmax, bloom and minmax-multi.
+-- With minmax-multi we need to be more careful, because the summary is not
+-- entirely deterministic - the order of values affects how ranges get merged,
+-- and if workers see random subsets between runs, that affects the resulting
+-- summaries too). The summaries would be equivalent in the sense that should
+-- give the same query results, but are not equal for EXCEPT to work. To work
+-- around that, we generate only small number of values to keep exact values,
+-- in which case the ordering does not matter.
SET max_parallel_maintenance_workers = 0;
-CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b, c int8_minmax_multi_ops) WITH (pages_per_range=7);
-- XXX we have to set some parameters to force parallel build, both because
-- there's a requirement for table size and plan_create_index_workers assumes
@@ -86,7 +89,7 @@ CREATE INDEX brin_test_serial_idx ON brin_parallel_test USING brin (a int4_minma
SET min_parallel_table_scan_size = 0;
SET max_parallel_maintenance_workers = 4;
SET maintenance_work_mem = '128MB';
-CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b, c int8_minmax_multi_ops) WITH (pages_per_range=7);
SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
@@ -113,7 +116,7 @@ SELECT * FROM brin_page_items(get_raw_page('brin_test_parallel_idx', 3), 'brin_t
DROP INDEX brin_test_parallel_idx;
SET max_parallel_workers = 0;
-CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b) WITH (pages_per_range=7);
+CREATE INDEX brin_test_parallel_idx ON brin_parallel_test USING brin (a int4_minmax_ops, a int4_bloom_ops, b, c int8_minmax_multi_ops) WITH (pages_per_range=7);
SELECT relname, relpages FROM pg_class WHERE relname IN ('brin_test_serial_idx', 'brin_test_parallel_idx') ORDER BY relname;
--
2.44.0
^ permalink raw reply [nested|flat] 5+ messages in thread
* Re: Parallel CREATE INDEX for BRIN indexes
2024-04-13 08:36 Re: Parallel CREATE INDEX for BRIN indexes Andres Freund <[email protected]>
2024-04-13 09:19 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
2024-04-13 21:04 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
@ 2024-08-15 13:48 ` Peter Eisentraut <[email protected]>
0 siblings, 0 replies; 5+ messages in thread
From: Peter Eisentraut @ 2024-08-15 13:48 UTC (permalink / raw)
To: Tomas Vondra <[email protected]>; +Cc: Andres Freund <[email protected]>; Matthias van de Meent <[email protected]>; PostgreSQL Hackers <[email protected]>
On 13.04.24 23:04, Tomas Vondra wrote:
>>> While preparing a differential code coverage report between 16 and HEAD, one
>>> thing that stands out is the parallel brin build code. Neither on
>>> coverage.postgresql.org nor locally is that code reached during our tests.
>>>
>>
>> Thanks for pointing this out, it's definitely something that I need to
>> improve (admittedly, should have been part of the patch). I'll also look
>> into eliminating the difference between BTREE and BRIN parallel builds,
>> mentioned in my last message in this thread.
>>
>
> Here's a couple patches adding a test for the parallel CREATE INDEX with
> BRIN. The actual test is 0003/0004 - I added the test to pageinspect,
> because that allows cross-checking the index to one built without
> parallelism, which I think is better than just doing CREATE INDEX
> without properly testing it produces correct results.
These pageinspect tests added a new use of the md5() function. We got
rid of those in the tests for PG17. You could write the test case with
something like
SELECT (CASE WHEN (mod(i,231) = 0) OR (i BETWEEN 3500 AND 4000) THEN NULL ELSE i END),
- (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE md5(i::text) END),
+ (CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3750 AND 4250) THEN NULL ELSE encode(sha256(i::text::bytea), 'hex') END),
(CASE WHEN (mod(i,233) = 0) OR (i BETWEEN 3850 AND 4500) THEN NULL ELSE (i/100) + mod(i,8) END)
But this changes the test output slightly and I'm not sure if this gives
you the data distribution that you need for you test. Could your check
this please?
^ permalink raw reply [nested|flat] 5+ messages in thread
end of thread, other threads:[~2024-08-15 13:48 UTC | newest]
Thread overview: 5+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2023-09-25 05:01 [PATCH v8 4/7] Row pattern recognition patch (executor). Tatsuo Ishii <[email protected]>
2024-04-13 08:36 Re: Parallel CREATE INDEX for BRIN indexes Andres Freund <[email protected]>
2024-04-13 09:19 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
2024-04-13 21:04 ` Re: Parallel CREATE INDEX for BRIN indexes Tomas Vondra <[email protected]>
2024-08-15 13:48 ` Re: Parallel CREATE INDEX for BRIN indexes Peter Eisentraut <[email protected]>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox