public inbox for [email protected]
help / color / mirror / Atom feed[PATCH v15 2/8] Row pattern recognition patch (parse/analysis).
3+ messages / 2 participants
[nested] [flat]
* [PATCH v15 2/8] Row pattern recognition patch (parse/analysis).
@ 2024-03-28 10:30 Tatsuo Ishii <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Tatsuo Ishii @ 2024-03-28 10:30 UTC (permalink / raw)
---
src/backend/parser/parse_agg.c | 7 +
src/backend/parser/parse_clause.c | 296 +++++++++++++++++++++++++++++-
src/backend/parser/parse_expr.c | 4 +
src/backend/parser/parse_func.c | 3 +
4 files changed, 309 insertions(+), 1 deletion(-)
diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c
index bee7d8346a..9bc22a836a 100644
--- a/src/backend/parser/parse_agg.c
+++ b/src/backend/parser/parse_agg.c
@@ -577,6 +577,10 @@ check_agglevels_and_constraints(ParseState *pstate, Node *expr)
errkind = true;
break;
+ case EXPR_KIND_RPR_DEFINE:
+ errkind = true;
+ break;
+
/*
* There is intentionally no default: case here, so that the
* compiler will warn if we add a new ParseExprKind without
@@ -967,6 +971,9 @@ transformWindowFuncCall(ParseState *pstate, WindowFunc *wfunc,
case EXPR_KIND_CYCLE_MARK:
errkind = true;
break;
+ case EXPR_KIND_RPR_DEFINE:
+ errkind = true;
+ break;
/*
* There is intentionally no default: case here, so that the
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index d2ac86777c..de2e5791e3 100644
--- a/src/backend/parser/parse_clause.c
+++ b/src/backend/parser/parse_clause.c
@@ -98,7 +98,14 @@ static WindowClause *findWindowClause(List *wclist, const char *name);
static Node *transformFrameOffset(ParseState *pstate, int frameOptions,
Oid rangeopfamily, Oid rangeopcintype, Oid *inRangeFunc,
Node *clause);
-
+static void transformRPR(ParseState *pstate, WindowClause *wc, WindowDef *windef,
+ List **targetlist);
+static List *transformDefineClause(ParseState *pstate, WindowClause *wc, WindowDef *windef,
+ List **targetlist);
+static void transformPatternClause(ParseState *pstate, WindowClause *wc,
+ WindowDef *windef);
+static List *transformMeasureClause(ParseState *pstate, WindowClause *wc,
+ WindowDef *windef);
/*
* transformFromClause -
@@ -2948,6 +2955,10 @@ transformWindowDefinitions(ParseState *pstate,
rangeopfamily, rangeopcintype,
&wc->endInRangeFunc,
windef->endOffset);
+
+ /* Process Row Pattern Recognition related clauses */
+ transformRPR(pstate, wc, windef, targetlist);
+
wc->runCondition = NIL;
wc->winref = winref;
@@ -3813,3 +3824,286 @@ transformFrameOffset(ParseState *pstate, int frameOptions,
return node;
}
+
+/*
+ * transformRPR
+ * Process Row Pattern Recognition related clauses
+ */
+static void
+transformRPR(ParseState *pstate, WindowClause *wc, WindowDef *windef,
+ List **targetlist)
+{
+ /*
+ * Window definition exists?
+ */
+ if (windef == NULL)
+ return;
+
+ /*
+ * Row Pattern Common Syntax clause exists?
+ */
+ if (windef->rpCommonSyntax == NULL)
+ return;
+
+ /* Check Frame option. Frame must start at current row */
+ if ((wc->frameOptions & FRAMEOPTION_START_CURRENT_ROW) == 0)
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("FRAME must start at current row when row patttern recognition is used")));
+
+ /* Transform AFTER MACH SKIP TO clause */
+ wc->rpSkipTo = windef->rpCommonSyntax->rpSkipTo;
+
+ /* Transform AFTER MACH SKIP TO variable */
+ wc->rpSkipVariable = windef->rpCommonSyntax->rpSkipVariable;
+
+ /* Transform SEEK or INITIAL clause */
+ wc->initial = windef->rpCommonSyntax->initial;
+
+ /* Transform DEFINE clause into list of TargetEntry's */
+ wc->defineClause = transformDefineClause(pstate, wc, windef, targetlist);
+
+ /* Check PATTERN clause and copy to patternClause */
+ transformPatternClause(pstate, wc, windef);
+
+ /* Transform MEASURE clause */
+ transformMeasureClause(pstate, wc, windef);
+}
+
+/*
+ * transformDefineClause Process DEFINE clause and transform ResTarget into
+ * list of TargetEntry.
+ *
+ * XXX we only support column reference in row pattern definition search
+ * condition, e.g. "price". <row pattern definition variable name>.<column
+ * reference> is not supported, e.g. "A.price".
+ */
+static List *
+transformDefineClause(ParseState *pstate, WindowClause *wc, WindowDef *windef,
+ List **targetlist)
+{
+ /* DEFINE variable name initials */
+ static char *defineVariableInitials = "abcdefghijklmnopqrstuvwxyz";
+
+ ListCell *lc,
+ *l;
+ ResTarget *restarget,
+ *r;
+ List *restargets;
+ List *defineClause;
+ char *name;
+ int initialLen;
+ int i;
+
+ /*
+ * If Row Definition Common Syntax exists, DEFINE clause must exist. (the
+ * raw parser should have already checked it.)
+ */
+ Assert(windef->rpCommonSyntax->rpDefs != NULL);
+
+ /*
+ * Check and add "A AS A IS TRUE" if pattern variable is missing in DEFINE
+ * per the SQL standard.
+ */
+ restargets = NIL;
+ foreach(lc, windef->rpCommonSyntax->rpPatterns)
+ {
+ A_Expr *a;
+ bool found = false;
+
+ if (!IsA(lfirst(lc), A_Expr))
+ ereport(ERROR,
+ errmsg("node type is not A_Expr"));
+
+ a = (A_Expr *) lfirst(lc);
+ name = strVal(a->lexpr);
+
+ foreach(l, windef->rpCommonSyntax->rpDefs)
+ {
+ restarget = (ResTarget *) lfirst(l);
+
+ if (!strcmp(restarget->name, name))
+ {
+ found = true;
+ break;
+ }
+ }
+
+ if (!found)
+ {
+ /*
+ * "name" is missing. So create "name AS name IS TRUE" ResTarget
+ * node and add it to the temporary list.
+ */
+ A_Const *n;
+
+ restarget = makeNode(ResTarget);
+ n = makeNode(A_Const);
+ n->val.boolval.type = T_Boolean;
+ n->val.boolval.boolval = true;
+ n->location = -1;
+ restarget->name = pstrdup(name);
+ restarget->indirection = NIL;
+ restarget->val = (Node *) n;
+ restarget->location = -1;
+ restargets = lappend((List *) restargets, restarget);
+ }
+ }
+
+ if (list_length(restargets) >= 1)
+ {
+ /* add missing DEFINEs */
+ windef->rpCommonSyntax->rpDefs =
+ list_concat(windef->rpCommonSyntax->rpDefs, restargets);
+ list_free(restargets);
+ }
+
+ /*
+ * Check for duplicate row pattern definition variables. The standard
+ * requires that no two row pattern definition variable names shall be
+ * equivalent.
+ */
+ restargets = NIL;
+ foreach(lc, windef->rpCommonSyntax->rpDefs)
+ {
+ restarget = (ResTarget *) lfirst(lc);
+ name = restarget->name;
+
+ /*
+ * Add DEFINE expression (Restarget->val) to the targetlist as a
+ * TargetEntry if it does not exist yet. Planner will add the column
+ * ref var node to the outer plan's target list later on. This makes
+ * DEFINE expression could access the outer tuple while evaluating
+ * PATTERN.
+ *
+ * XXX: adding whole expressions of DEFINE to the plan.targetlist is
+ * not so good, because it's not necessary to evalute the expression
+ * in the target list while running the plan. We should extract the
+ * var nodes only then add them to the plan.targetlist.
+ */
+ findTargetlistEntrySQL99(pstate, (Node *) restarget->val,
+ targetlist, EXPR_KIND_RPR_DEFINE);
+
+ /*
+ * Make sure that the row pattern definition search condition is a
+ * boolean expression.
+ */
+ transformWhereClause(pstate, restarget->val,
+ EXPR_KIND_RPR_DEFINE, "DEFINE");
+
+ foreach(l, restargets)
+ {
+ char *n;
+
+ r = (ResTarget *) lfirst(l);
+ n = r->name;
+
+ if (!strcmp(n, name))
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("row pattern definition variable name \"%s\" appears more than once in DEFINE clause",
+ name),
+ parser_errposition(pstate, exprLocation((Node *) r))));
+ }
+ restargets = lappend(restargets, restarget);
+ }
+ list_free(restargets);
+
+ /*
+ * Create list of row pattern DEFINE variable name's initial. We assign
+ * [a-z] to them (up to 26 variable names are allowed).
+ */
+ restargets = NIL;
+ i = 0;
+ initialLen = strlen(defineVariableInitials);
+
+ foreach(lc, windef->rpCommonSyntax->rpDefs)
+ {
+ char initial[2];
+
+ restarget = (ResTarget *) lfirst(lc);
+ name = restarget->name;
+
+ if (i >= initialLen)
+ {
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("number of row pattern definition variable names exceeds %d",
+ initialLen),
+ parser_errposition(pstate,
+ exprLocation((Node *) restarget))));
+ }
+ initial[0] = defineVariableInitials[i++];
+ initial[1] = '\0';
+ wc->defineInitial = lappend(wc->defineInitial,
+ makeString(pstrdup(initial)));
+ }
+
+ defineClause = transformTargetList(pstate, windef->rpCommonSyntax->rpDefs,
+ EXPR_KIND_RPR_DEFINE);
+
+ /* mark column origins */
+ markTargetListOrigins(pstate, defineClause);
+
+ /* mark all nodes in the DEFINE clause tree with collation information */
+ assign_expr_collations(pstate, (Node *) defineClause);
+
+ return defineClause;
+}
+
+/*
+ * transformPatternClause
+ * Process PATTERN clause and return PATTERN clause in the raw parse tree
+ */
+static void
+transformPatternClause(ParseState *pstate, WindowClause *wc,
+ WindowDef *windef)
+{
+ ListCell *lc;
+
+ /*
+ * Row Pattern Common Syntax clause exists?
+ */
+ if (windef->rpCommonSyntax == NULL)
+ return;
+
+ wc->patternVariable = NIL;
+ wc->patternRegexp = NIL;
+ foreach(lc, windef->rpCommonSyntax->rpPatterns)
+ {
+ A_Expr *a;
+ char *name;
+ char *regexp;
+
+ if (!IsA(lfirst(lc), A_Expr))
+ ereport(ERROR,
+ errmsg("node type is not A_Expr"));
+
+ a = (A_Expr *) lfirst(lc);
+ name = strVal(a->lexpr);
+
+ wc->patternVariable = lappend(wc->patternVariable, makeString(pstrdup(name)));
+ regexp = strVal(lfirst(list_head(a->name)));
+
+ wc->patternRegexp = lappend(wc->patternRegexp, makeString(pstrdup(regexp)));
+ }
+}
+
+/*
+ * transformMeasureClause
+ * Process MEASURE clause
+ * XXX MEASURE clause is not supported yet
+ */
+static List *
+transformMeasureClause(ParseState *pstate, WindowClause *wc,
+ WindowDef *windef)
+{
+ if (windef->rowPatternMeasures == NIL)
+ return NIL;
+
+ ereport(ERROR,
+ (errcode(ERRCODE_SYNTAX_ERROR),
+ errmsg("%s", "MEASURE clause is not supported yet"),
+ parser_errposition(pstate, exprLocation((Node *) windef->rowPatternMeasures))));
+ return NIL;
+}
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 73c83cea4a..8b0cc608bc 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -578,6 +578,7 @@ transformColumnRef(ParseState *pstate, ColumnRef *cref)
case EXPR_KIND_COPY_WHERE:
case EXPR_KIND_GENERATED_COLUMN:
case EXPR_KIND_CYCLE_MARK:
+ case EXPR_KIND_RPR_DEFINE:
/* okay */
break;
@@ -1817,6 +1818,7 @@ transformSubLink(ParseState *pstate, SubLink *sublink)
case EXPR_KIND_VALUES:
case EXPR_KIND_VALUES_SINGLE:
case EXPR_KIND_CYCLE_MARK:
+ case EXPR_KIND_RPR_DEFINE:
/* okay */
break;
case EXPR_KIND_CHECK_CONSTRAINT:
@@ -3197,6 +3199,8 @@ ParseExprKindName(ParseExprKind exprKind)
return "GENERATED AS";
case EXPR_KIND_CYCLE_MARK:
return "CYCLE";
+ case EXPR_KIND_RPR_DEFINE:
+ return "DEFINE";
/*
* There is intentionally no default: case here, so that the
diff --git a/src/backend/parser/parse_func.c b/src/backend/parser/parse_func.c
index 0cbc950c95..ad982a7c17 100644
--- a/src/backend/parser/parse_func.c
+++ b/src/backend/parser/parse_func.c
@@ -2657,6 +2657,9 @@ check_srf_call_placement(ParseState *pstate, Node *last_srf, int location)
case EXPR_KIND_CYCLE_MARK:
errkind = true;
break;
+ case EXPR_KIND_RPR_DEFINE:
+ errkind = true;
+ break;
/*
* There is intentionally no default: case here, so that the
--
2.25.1
----Next_Part(Thu_Mar_28_19_59_25_2024_076)--
Content-Type: Text/X-Patch; charset=us-ascii
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="v15-0003-Row-pattern-recognition-patch-rewriter.patch"
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands.
@ 2024-07-02 20:10 Joel Jacobson <[email protected]>
2024-07-02 20:13 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]>
0 siblings, 1 reply; 3+ messages in thread
From: Joel Jacobson @ 2024-07-02 20:10 UTC (permalink / raw)
To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers
On Tue, Jul 2, 2024, at 21:55, Joel Jacobson wrote:
> On Tue, Jul 2, 2024, at 20:53, Joel Jacobson wrote:
>> Trying to wrap my head around what could cause this.
I found the bug in the case 3 code,
and it turns out the same type of bug also exists in the case 2 code:
case 2:
newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
The problem here is that res_ndigits could become less than 4,
if rscale is low enough,
and then we would try to access a negative array index in var2digits.
Fix:
case 2:
if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
else
newdig = 0;
Another problem in the case 2 code:
if (res_ndigits - 3 < var2ndigits)
newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
Fix:
if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
New version attached that fixes both the case 2 and case 3 code.
Regards,
Joel
Attachments:
[application/octet-stream] v4-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch (4.3K, ../../[email protected]/2-v4-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch)
download | inline diff:
From a7d421d5fcd4f6b367f266c3b005c82abff03d7c Mon Sep 17 00:00:00 2001
From: Joel Jakobsson <[email protected]>
Date: Tue, 2 Jul 2024 17:54:25 +0200
Subject: [PATCH] numeric: Simplified fast-path computation for mul_var()
---
src/backend/utils/adt/numeric.c | 106 ++++++++++++++++++++++++++++++++
1 file changed, 106 insertions(+)
diff --git a/src/backend/utils/adt/numeric.c b/src/backend/utils/adt/numeric.c
index 5510a203b0..e3bc29b626 100644
--- a/src/backend/utils/adt/numeric.c
+++ b/src/backend/utils/adt/numeric.c
@@ -8747,6 +8747,112 @@ mul_var(const NumericVar *var1, const NumericVar *var2, NumericVar *result,
return;
}
+ /*
+ * Simplified fast-path computation, if var1 has just one or two digits.
+ * This is significantly faster, since it avoids allocating a separate
+ * digit array, making multiple passes over var2, and having separate
+ * carry-propagation passes.
+ */
+ if (var1ndigits <= 3)
+ {
+ NumericDigit *res_buf;
+
+ /* Allocate result digit array */
+ res_buf = digitbuf_alloc(res_ndigits);
+ res_buf[0] = 0; /* spare digit for later rounding */
+ res_digits = res_buf + 1;
+
+ /*
+ * Compute the result digits directly, in one pass, propagating the
+ * carry up as we go.
+ */
+ switch (var1ndigits)
+ {
+ case 1:
+ carry = 0;
+ for (i = res_ndigits - 3; i >= 0; i--)
+ {
+ newdig = (int) var1digits[0] * var2digits[i] + carry;
+ res_digits[i + 1] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ }
+ res_digits[0] = (NumericDigit) carry;
+ break;
+
+ case 2:
+ if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
+ newdig = (int) var1digits[1] * var2digits[res_ndigits - 4];
+ else
+ newdig = 0;
+ if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
+ newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
+ res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ for (i = res_ndigits - 4; i >= 1; i--)
+ {
+ newdig = (int) var1digits[0] * var2digits[i] +
+ (int) var1digits[1] * var2digits[i - 1] + carry;
+ res_digits[i + 1] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ }
+ newdig = (int) var1digits[0] * var2digits[0] + carry;
+ res_digits[1] = (NumericDigit) (newdig % NBASE);
+ res_digits[0] = (NumericDigit) (newdig / NBASE);
+ break;
+
+ case 3:
+ if (res_ndigits - 5 >= 0 && res_ndigits - 5 < var2ndigits)
+ newdig = (int) var1digits[2] * var2digits[res_ndigits - 5];
+ else
+ newdig = 0;
+ if (res_ndigits - 4 >= 0 && res_ndigits - 4 < var2ndigits)
+ newdig += (int) var1digits[1] * var2digits[res_ndigits - 4];
+ if (res_ndigits - 3 >= 0 && res_ndigits - 3 < var2ndigits)
+ newdig += (int) var1digits[0] * var2digits[res_ndigits - 3];
+ res_digits[res_ndigits - 2] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ for (i = res_ndigits - 4; i >= 2; i--)
+ {
+ newdig = carry;
+ if (i < var2ndigits)
+ newdig += (int) var1digits[0] * var2digits[i];
+ if (i - 1 >= 0 && i - 1 < var2ndigits)
+ newdig += (int) var1digits[1] * var2digits[i - 1];
+ if (i - 2 >= 0 && i - 2 < var2ndigits)
+ newdig += (int) var1digits[2] * var2digits[i - 2];
+ res_digits[i + 1] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ }
+ newdig = carry;
+ if (var2ndigits > 1)
+ newdig += (int) var1digits[0] * var2digits[1];
+ if (var2ndigits > 0)
+ newdig += (int) var1digits[1] * var2digits[0];
+ res_digits[2] = (NumericDigit) (newdig % NBASE);
+ carry = newdig / NBASE;
+ newdig = (int) var1digits[0] * var2digits[0] + carry;
+ res_digits[1] = (NumericDigit) (newdig % NBASE);
+ res_digits[0] = (NumericDigit) (newdig / NBASE);
+ break;
+ }
+
+ /* Store the product in result (minus extra rounding digit) */
+ digitbuf_free(result->buf);
+ result->ndigits = res_ndigits - 1;
+ result->buf = res_buf;
+ result->digits = res_digits;
+ result->weight = res_weight - 1;
+ result->sign = res_sign;
+
+ /* Round to target rscale (and set result->dscale) */
+ round_var(result, rscale);
+
+ /* Strip leading and trailing zeroes */
+ strip_var(result);
+
+ return;
+ }
+
/*
* We do the arithmetic in an array "dig[]" of signed int's. Since
* INT_MAX is noticeably larger than NBASE*NBASE, this gives us headroom
--
2.45.1
^ permalink raw reply [nested|flat] 3+ messages in thread
* Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands.
2024-07-02 20:10 Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]>
@ 2024-07-02 20:13 ` Joel Jacobson <[email protected]>
0 siblings, 0 replies; 3+ messages in thread
From: Joel Jacobson @ 2024-07-02 20:13 UTC (permalink / raw)
To: Dean Rasheed <[email protected]>; +Cc: Dagfinn Ilmari Mannsåker <[email protected]>; pgsql-hackers
On Tue, Jul 2, 2024, at 22:10, Joel Jacobson wrote:
> * v4-optimize-numeric-mul_var-small-var1-arbitrary-var2.patch
Instead of these boundary checks, maybe it would be cleaner to just
skip this optimization if there are too few res_ndigits?
/Joel
^ permalink raw reply [nested|flat] 3+ messages in thread
end of thread, other threads:[~2024-07-02 20:13 UTC | newest]
Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2024-03-28 10:30 [PATCH v15 2/8] Row pattern recognition patch (parse/analysis). Tatsuo Ishii <[email protected]>
2024-07-02 20:10 Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[email protected]>
2024-07-02 20:13 ` Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands. Joel Jacobson <[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