public inbox for [email protected]help / color / mirror / Atom feed
Re: POC: GROUP BY optimization 2+ messages / 2 participants [nested] [flat]
* Re: POC: GROUP BY optimization @ 2022-02-01 09:48 Andrey V. Lepikhov <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Andrey V. Lepikhov @ 2022-02-01 09:48 UTC (permalink / raw) To: Tomas Vondra <[email protected]>; Teodor Sigaev <[email protected]>; +Cc: Tomas Vondra <[email protected]>; PostgreSQL Developers <[email protected]> > On 7/22/21 3:58 AM, Tomas Vondra wrote: > I've simplified the costing a bit, and the attached version actually > undoes all the "suspicious" plan changes in postgres_fdw. It changes one > new plan, but that seems somewhat reasonable, as it pushes sort to the > remote side. I tried to justify heap-sort part of the compute_cpu_sort_cost() routine and realized, that here we may have a mistake. After a week of efforts, I don't found any research papers on dependence of bounded heap-sort time compexity on number of duplicates. So, I suppose self-made formula, based on simple logical constructions: 1. We should base on initial formula: cost ~ N*LOG2(M), where M - output_tuples. 2. Realize, that full representation of this formula is: cost ~ N*LOG2(min{N,M}) 3. In the case of multicolumn, number of comparisons for each next column can be estimated by the same formula, but arranged to a number of tuples per group: comparisons ~ input * LOG2(min{input,M}) 4. Realize, that for the case, when M > input, we should change this formula a bit: comparisons ~ max{input,M} * LOG2(min{input,M}) Remember, that in our case M << tuples. So, general formula for bounded heap sort can be written as: cost ~ N * sum(max{n_i,M}/N * LOG2(min{n_i,M})), i=1,ncols where n_1 == N, n_i - number of tuples per group, estimated from previous iteration. In attachment - an implementation of this approach. -- regards, Andrey Lepikhov Postgres Professional diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 68a32740d7..2c3cce57aa 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -1872,6 +1872,15 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr) * * N * sum( Fk * log(Gk) ) * + * For bounded heap sort we haven't such a duplicates-related research. So invent + * it based on a simple logic (M - number of output tuples): + * For one column we can estimate number of comparisons as: + * N * log(min{N,M}) + * For the case of many columns we can natively estimate number of comparisons by + * the formula: + * sum(max{n_i,M} * log(min{N,M})), + * where n_0 == N, n_i - number of tuples per group, estimated on previous step. + * * Note: We also consider column width, not just the comparator cost. * * NOTE: some callers currently pass NIL for pathkeys because they @@ -1881,7 +1890,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr) static Cost compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, Cost comparison_cost, double tuples, double output_tuples, - bool heapSort) + bool bounded_sort) { Cost per_tuple_cost = 0.0; ListCell *lc; @@ -1907,7 +1916,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * of this function, but I'm not sure. I suggest we introduce some simple * constants for that, instead of magic values. */ - output_tuples = (heapSort) ? 2.0 * output_tuples : tuples; + output_tuples = (bounded_sort) ? 2.0 * output_tuples : tuples; per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples); /* add cost provided by caller */ @@ -1925,8 +1934,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, { PathKey *pathkey = (PathKey*) lfirst(lc); EquivalenceMember *em; - double nGroups, - correctedNGroups; + double nGroups; /* * We believe that equivalence members aren't very different, so, to @@ -2000,24 +2008,16 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, */ if (i >= nPresortedKeys) { - if (heapSort) - { - double heap_tuples; - - /* have to keep at least one group, and a multiple of group size */ - heap_tuples = Max(ceil(output_tuples / tuplesPerPrevGroup) * tuplesPerPrevGroup, - tuplesPerPrevGroup); - - /* so how many (whole) groups is that? */ - correctedNGroups = ceil(heap_tuples / tuplesPerPrevGroup); - } + /* + * Quick sort and 'top-N' sorting (bounded heap sort) algorithms + * have different formulas for time complexity estimation. + */ + if (bounded_sort) + per_tuple_cost += totalFuncCost * + (Max(tuplesPerPrevGroup, output_tuples) / tuples) * + LOG2(2.0 * Min(tuplesPerPrevGroup, output_tuples)); else - /* all groups in the input */ - correctedNGroups = nGroups; - - correctedNGroups = Max(1.0, ceil(correctedNGroups)); - - per_tuple_cost += totalFuncCost * LOG2(correctedNGroups); + per_tuple_cost += totalFuncCost * LOG2(nGroups); } i++; Attachments: [text/plain] bounded_heap_sort_fix.txt (3.1K, ../../[email protected]/2-bounded_heap_sort_fix.txt) download | inline diff: diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 68a32740d7..2c3cce57aa 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -1872,6 +1872,15 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr) * * N * sum( Fk * log(Gk) ) * + * For bounded heap sort we haven't such a duplicates-related research. So invent + * it based on a simple logic (M - number of output tuples): + * For one column we can estimate number of comparisons as: + * N * log(min{N,M}) + * For the case of many columns we can natively estimate number of comparisons by + * the formula: + * sum(max{n_i,M} * log(min{N,M})), + * where n_0 == N, n_i - number of tuples per group, estimated on previous step. + * * Note: We also consider column width, not just the comparator cost. * * NOTE: some callers currently pass NIL for pathkeys because they @@ -1881,7 +1890,7 @@ get_width_cost_multiplier(PlannerInfo *root, Expr *expr) static Cost compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, Cost comparison_cost, double tuples, double output_tuples, - bool heapSort) + bool bounded_sort) { Cost per_tuple_cost = 0.0; ListCell *lc; @@ -1907,7 +1916,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, * of this function, but I'm not sure. I suggest we introduce some simple * constants for that, instead of magic values. */ - output_tuples = (heapSort) ? 2.0 * output_tuples : tuples; + output_tuples = (bounded_sort) ? 2.0 * output_tuples : tuples; per_tuple_cost += 2.0 * cpu_operator_cost * LOG2(output_tuples); /* add cost provided by caller */ @@ -1925,8 +1934,7 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, { PathKey *pathkey = (PathKey*) lfirst(lc); EquivalenceMember *em; - double nGroups, - correctedNGroups; + double nGroups; /* * We believe that equivalence members aren't very different, so, to @@ -2000,24 +2008,16 @@ compute_cpu_sort_cost(PlannerInfo *root, List *pathkeys, int nPresortedKeys, */ if (i >= nPresortedKeys) { - if (heapSort) - { - double heap_tuples; - - /* have to keep at least one group, and a multiple of group size */ - heap_tuples = Max(ceil(output_tuples / tuplesPerPrevGroup) * tuplesPerPrevGroup, - tuplesPerPrevGroup); - - /* so how many (whole) groups is that? */ - correctedNGroups = ceil(heap_tuples / tuplesPerPrevGroup); - } + /* + * Quick sort and 'top-N' sorting (bounded heap sort) algorithms + * have different formulas for time complexity estimation. + */ + if (bounded_sort) + per_tuple_cost += totalFuncCost * + (Max(tuplesPerPrevGroup, output_tuples) / tuples) * + LOG2(2.0 * Min(tuplesPerPrevGroup, output_tuples)); else - /* all groups in the input */ - correctedNGroups = nGroups; - - correctedNGroups = Max(1.0, ceil(correctedNGroups)); - - per_tuple_cost += totalFuncCost * LOG2(correctedNGroups); + per_tuple_cost += totalFuncCost * LOG2(nGroups); } i++; ^ permalink raw reply [nested|flat] 2+ messages in thread
* [PATCH v25 1/9] Row pattern recognition patch for raw parser. @ 2024-12-21 06:19 Tatsuo Ishii <[email protected]> 0 siblings, 0 replies; 2+ messages in thread From: Tatsuo Ishii @ 2024-12-21 06:19 UTC (permalink / raw) --- src/backend/parser/gram.y | 221 ++++++++++++++++++++++++++++++-- src/include/nodes/parsenodes.h | 67 ++++++++++ src/include/parser/kwlist.h | 8 ++ src/include/parser/parse_node.h | 1 + 4 files changed, 286 insertions(+), 11 deletions(-) diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y index 67eb96396a..d21dc28955 100644 --- a/src/backend/parser/gram.y +++ b/src/backend/parser/gram.y @@ -664,6 +664,21 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); json_object_constructor_null_clause_opt json_array_constructor_null_clause_opt +%type <target> row_pattern_measure_item + row_pattern_definition +%type <node> opt_row_pattern_common_syntax + opt_row_pattern_skip_to + row_pattern_subset_item + row_pattern_term +%type <list> opt_row_pattern_measures + row_pattern_measure_list + row_pattern_definition_list + opt_row_pattern_subset_clause + row_pattern_subset_list + row_pattern_subset_rhs + row_pattern +%type <boolean> opt_row_pattern_initial_or_seek + first_or_last /* * Non-keyword token types. These are hard-wired into the "flex" lexer. @@ -707,7 +722,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); CURRENT_TIME CURRENT_TIMESTAMP CURRENT_USER CURSOR CYCLE DATA_P DATABASE DAY_P DEALLOCATE DEC DECIMAL_P DECLARE DEFAULT DEFAULTS - DEFERRABLE DEFERRED DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DEPTH DESC + DEFERRABLE DEFERRED DEFINE DEFINER DELETE_P DELIMITER DELIMITERS DEPENDS DEPTH DESC DETACH DICTIONARY DISABLE_P DISCARD DISTINCT DO DOCUMENT_P DOMAIN_P DOUBLE_P DROP @@ -723,7 +738,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); HANDLER HAVING HEADER_P HOLD HOUR_P IDENTITY_P IF_P ILIKE IMMEDIATE IMMUTABLE IMPLICIT_P IMPORT_P IN_P INCLUDE - INCLUDING INCREMENT INDENT INDEX INDEXES INHERIT INHERITS INITIALLY INLINE_P + INCLUDING INCREMENT INDENT INDEX INDEXES INHERIT INHERITS INITIAL INITIALLY INLINE_P INNER_P INOUT INPUT_P INSENSITIVE INSERT INSTEAD INT_P INTEGER INTERSECT INTERVAL INTO INVOKER IS ISNULL ISOLATION @@ -736,7 +751,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); LEADING LEAKPROOF LEAST LEFT LEVEL LIKE LIMIT LISTEN LOAD LOCAL LOCALTIME LOCALTIMESTAMP LOCATION LOCK_P LOCKED LOGGED - MAPPING MATCH MATCHED MATERIALIZED MAXVALUE MERGE MERGE_ACTION METHOD + MAPPING MATCH MATCHED MATERIALIZED MAXVALUE MEASURES MERGE MERGE_ACTION METHOD MINUTE_P MINVALUE MODE MONTH_P MOVE NAME_P NAMES NATIONAL NATURAL NCHAR NESTED NEW NEXT NFC NFD NFKC NFKD NO @@ -748,8 +763,9 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); ORDER ORDINALITY OTHERS OUT_P OUTER_P OVER OVERLAPS OVERLAY OVERRIDING OWNED OWNER - PARALLEL PARAMETER PARSER PARTIAL PARTITION PASSING PASSWORD PATH - PERIOD PLACING PLAN PLANS POLICY + PARALLEL PARAMETER PARSER PARTIAL PARTITION PASSING PASSWORD PAST + PATH PATTERN_P PERIOD PERMUTE PLACING PLAN PLANS POLICY + POSITION PRECEDING PRECISION PRESERVE PREPARE PREPARED PRIMARY PRIOR PRIVILEGES PROCEDURAL PROCEDURE PROCEDURES PROGRAM PUBLICATION @@ -760,12 +776,13 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); RESET RESTART RESTRICT RETURN RETURNING RETURNS REVOKE RIGHT ROLE ROLLBACK ROLLUP ROUTINE ROUTINES ROW ROWS RULE - SAVEPOINT SCALAR SCHEMA SCHEMAS SCROLL SEARCH SECOND_P SECURITY SELECT + SAVEPOINT SCALAR SCHEMA SCHEMAS SCROLL SEARCH SECOND_P SECURITY SEEK SELECT SEQUENCE SEQUENCES + SERIALIZABLE SERVER SESSION SESSION_USER SET SETS SETOF SHARE SHOW SIMILAR SIMPLE SKIP SMALLINT SNAPSHOT SOME SOURCE SQL_P STABLE STANDALONE_P START STATEMENT STATISTICS STDIN STDOUT STORAGE STORED STRICT_P STRING_P STRIP_P - SUBSCRIPTION SUBSTRING SUPPORT SYMMETRIC SYSID SYSTEM_P SYSTEM_USER + SUBSCRIPTION SUBSET SUBSTRING SUPPORT SYMMETRIC SYSID SYSTEM_P SYSTEM_USER TABLE TABLES TABLESAMPLE TABLESPACE TARGET TEMP TEMPLATE TEMPORARY TEXT_P THEN TIES TIME TIMESTAMP TO TRAILING TRANSACTION TRANSFORM @@ -874,6 +891,7 @@ static Node *makeRecursiveViewSelect(char *relname, List *aliases, Node *query); %nonassoc UNBOUNDED NESTED /* ideally would have same precedence as IDENT */ %nonassoc IDENT PARTITION RANGE ROWS GROUPS PRECEDING FOLLOWING CUBE ROLLUP SET KEYS OBJECT_P SCALAR VALUE_P WITH WITHOUT PATH + MEASURES AFTER INITIAL SEEK PATTERN_P %left Op OPERATOR /* multi-character ops and user-defined operators */ %left '+' '-' %left '*' '/' '%' @@ -16326,7 +16344,8 @@ over_clause: OVER window_specification ; window_specification: '(' opt_existing_window_name opt_partition_clause - opt_sort_clause opt_frame_clause ')' + opt_sort_clause opt_row_pattern_measures opt_frame_clause + opt_row_pattern_common_syntax ')' { WindowDef *n = makeNode(WindowDef); @@ -16334,10 +16353,12 @@ window_specification: '(' opt_existing_window_name opt_partition_clause n->refname = $2; n->partitionClause = $3; n->orderClause = $4; + n->rowPatternMeasures = $5; /* copy relevant fields of opt_frame_clause */ - n->frameOptions = $5->frameOptions; - n->startOffset = $5->startOffset; - n->endOffset = $5->endOffset; + n->frameOptions = $6->frameOptions; + n->startOffset = $6->startOffset; + n->endOffset = $6->endOffset; + n->rpCommonSyntax = (RPCommonSyntax *)$7; n->location = @1; $$ = n; } @@ -16361,6 +16382,31 @@ opt_partition_clause: PARTITION BY expr_list { $$ = $3; } | /*EMPTY*/ { $$ = NIL; } ; +/* + * ROW PATTERN_P MEASURES + */ +opt_row_pattern_measures: MEASURES row_pattern_measure_list { $$ = $2; } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_measure_list: + row_pattern_measure_item + { $$ = list_make1($1); } + | row_pattern_measure_list ',' row_pattern_measure_item + { $$ = lappend($1, $3); } + ; + +row_pattern_measure_item: + a_expr AS ColLabel + { + $$ = makeNode(ResTarget); + $$->name = $3; + $$->indirection = NIL; + $$->val = (Node *) $1; + $$->location = @1; + } + ; + /* * For frame clauses, we return a WindowDef, but only some fields are used: * frameOptions, startOffset, and endOffset. @@ -16520,6 +16566,143 @@ opt_window_exclusion_clause: | /*EMPTY*/ { $$ = 0; } ; +opt_row_pattern_common_syntax: +opt_row_pattern_skip_to opt_row_pattern_initial_or_seek + PATTERN_P '(' row_pattern ')' + opt_row_pattern_subset_clause + DEFINE row_pattern_definition_list + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ((RPCommonSyntax *)$1)->rpSkipTo; + n->rpSkipVariable = ((RPCommonSyntax *)$1)->rpSkipVariable; + n->initial = $2; + n->rpPatterns = $5; + n->rpSubsetClause = $7; + n->rpDefs = $9; + $$ = (Node *) n; + } + | /*EMPTY*/ { $$ = NULL; } + ; + +opt_row_pattern_skip_to: + AFTER MATCH SKIP TO NEXT ROW + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_NEXT_ROW; + n->rpSkipVariable = NULL; + $$ = (Node *) n; + } + | AFTER MATCH SKIP PAST LAST_P ROW + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_PAST_LAST_ROW; + n->rpSkipVariable = NULL; + $$ = (Node *) n; + } + | AFTER MATCH SKIP TO first_or_last ColId + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = $5? ST_FIRST_VARIABLE : ST_LAST_VARIABLE; + n->rpSkipVariable = $6; + $$ = (Node *) n; + } +/* + | AFTER MATCH SKIP TO LAST_P ColId %prec LAST_P + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_LAST_VARIABLE; + n->rpSkipVariable = $6; + $$ = n; + } + | AFTER MATCH SKIP TO ColId + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + n->rpSkipTo = ST_VARIABLE; + n->rpSkipVariable = $5; + $$ = n; + } +*/ + | /*EMPTY*/ + { + RPCommonSyntax *n = makeNode(RPCommonSyntax); + /* temporary set default to ST_NEXT_ROW */ + n->rpSkipTo = ST_PAST_LAST_ROW; + n->rpSkipVariable = NULL; + $$ = (Node *) n; + } + ; + +first_or_last: + FIRST_P { $$ = true; } + | LAST_P { $$ = false; } + ; + +opt_row_pattern_initial_or_seek: + INITIAL { $$ = true; } + | SEEK + { + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("SEEK is not supported"), + errhint("Use INITIAL."), + parser_errposition(@1))); + } + | /*EMPTY*/ { $$ = true; } + ; + +row_pattern: + row_pattern_term { $$ = list_make1($1); } + | row_pattern row_pattern_term { $$ = lappend($1, $2); } + ; + +row_pattern_term: + ColId { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "", (Node *)makeString($1), NULL, @1); } + | ColId '*' { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "*", (Node *)makeString($1), NULL, @1); } + | ColId '+' { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "+", (Node *)makeString($1), NULL, @1); } + | ColId '?' { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "?", (Node *)makeString($1), NULL, @1); } + ; + +opt_row_pattern_subset_clause: + SUBSET row_pattern_subset_list { $$ = $2; } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_subset_list: + row_pattern_subset_item { $$ = list_make1($1); } + | row_pattern_subset_list ',' row_pattern_subset_item { $$ = lappend($1, $3); } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_subset_item: ColId '=' '(' row_pattern_subset_rhs ')' + { + RPSubsetItem *n = makeNode(RPSubsetItem); + n->name = $1; + n->rhsVariable = $4; + $$ = (Node *) n; + } + ; + +row_pattern_subset_rhs: + ColId { $$ = list_make1(makeStringConst($1, @1)); } + | row_pattern_subset_rhs ',' ColId { $$ = lappend($1, makeStringConst($3, @1)); } + | /*EMPTY*/ { $$ = NIL; } + ; + +row_pattern_definition_list: + row_pattern_definition { $$ = list_make1($1); } + | row_pattern_definition_list ',' row_pattern_definition { $$ = lappend($1, $3); } + ; + +row_pattern_definition: + ColId AS a_expr + { + $$ = makeNode(ResTarget); + $$->name = $1; + $$->indirection = NIL; + $$->val = (Node *) $3; + $$->location = @1; + } + ; /* * Supporting nonterminals for expressions. @@ -17732,6 +17915,7 @@ unreserved_keyword: | INDEXES | INHERIT | INHERITS + | INITIAL | INLINE_P | INPUT_P | INSENSITIVE @@ -17760,6 +17944,7 @@ unreserved_keyword: | MATCHED | MATERIALIZED | MAXVALUE + | MEASURES | MERGE | METHOD | MINUTE_P @@ -17804,8 +17989,11 @@ unreserved_keyword: | PARTITION | PASSING | PASSWORD + | PAST | PATH + | PATTERN_P | PERIOD + | PERMUTE | PLAN | PLANS | POLICY @@ -17857,6 +18045,7 @@ unreserved_keyword: | SEARCH | SECOND_P | SECURITY + | SEEK | SEQUENCE | SEQUENCES | SERIALIZABLE @@ -17884,6 +18073,7 @@ unreserved_keyword: | STRING_P | STRIP_P | SUBSCRIPTION + | SUBSET | SUPPORT | SYSID | SYSTEM_P @@ -18078,6 +18268,7 @@ reserved_keyword: | CURRENT_USER | DEFAULT | DEFERRABLE + | DEFINE | DESC | DISTINCT | DO @@ -18241,6 +18432,7 @@ bare_label_keyword: | DEFAULTS | DEFERRABLE | DEFERRED + | DEFINE | DEFINER | DELETE_P | DELIMITER @@ -18318,6 +18510,7 @@ bare_label_keyword: | INDEXES | INHERIT | INHERITS + | INITIAL | INITIALLY | INLINE_P | INNER_P @@ -18372,6 +18565,7 @@ bare_label_keyword: | MATCHED | MATERIALIZED | MAXVALUE + | MEASURES | MERGE | MERGE_ACTION | METHOD @@ -18428,8 +18622,11 @@ bare_label_keyword: | PARTITION | PASSING | PASSWORD + | PAST | PATH + | PATTERN_P | PERIOD + | PERMUTE | PLACING | PLAN | PLANS @@ -18487,6 +18684,7 @@ bare_label_keyword: | SCROLL | SEARCH | SECURITY + | SEEK | SELECT | SEQUENCE | SEQUENCES @@ -18520,6 +18718,7 @@ bare_label_keyword: | STRING_P | STRIP_P | SUBSCRIPTION + | SUBSET | SUBSTRING | SUPPORT | SYMMETRIC diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h index 0f9462493e..defc62bf9b 100644 --- a/src/include/nodes/parsenodes.h +++ b/src/include/nodes/parsenodes.h @@ -552,6 +552,48 @@ typedef struct SortBy ParseLoc location; /* operator location, or -1 if none/unknown */ } SortBy; +/* + * AFTER MATCH row pattern skip to types in row pattern common syntax + */ +typedef enum RPSkipTo +{ + ST_NONE, /* AFTER MATCH omitted */ + ST_NEXT_ROW, /* SKIP TO NEXT ROW */ + ST_PAST_LAST_ROW, /* SKIP TO PAST LAST ROW */ + ST_FIRST_VARIABLE, /* SKIP TO FIRST variable name */ + ST_LAST_VARIABLE, /* SKIP TO LAST variable name */ + ST_VARIABLE /* SKIP TO variable name */ +} RPSkipTo; + +/* + * Row Pattern SUBSET clause item + */ +typedef struct RPSubsetItem +{ + NodeTag type; + char *name; /* Row Pattern SUBSET clause variable name */ + List *rhsVariable; /* Row Pattern SUBSET rhs variables (list of + * char *string) */ +} RPSubsetItem; + +/* + * RowPatternCommonSyntax - raw representation of row pattern common syntax + * + */ +typedef struct RPCommonSyntax +{ + NodeTag type; + RPSkipTo rpSkipTo; /* Row Pattern AFTER MATCH SKIP type */ + char *rpSkipVariable; /* Row Pattern Skip To variable name, if any */ + bool initial; /* true if <row pattern initial or seek> is + * initial */ + List *rpPatterns; /* PATTERN variables (list of A_Expr) */ + List *rpSubsetClause; /* row pattern subset clause (list of + * RPSubsetItem), if any */ + List *rpDefs; /* row pattern definitions clause (list of + * ResTarget) */ +} RPCommonSyntax; + /* * WindowDef - raw representation of WINDOW and OVER clauses * @@ -567,6 +609,9 @@ typedef struct WindowDef char *refname; /* referenced window name, if any */ List *partitionClause; /* PARTITION BY expression list */ List *orderClause; /* ORDER BY (list of SortBy) */ + List *rowPatternMeasures; /* row pattern measures (list of + * ResTarget) */ + RPCommonSyntax *rpCommonSyntax; /* row pattern common syntax */ int frameOptions; /* frame_clause options, see below */ Node *startOffset; /* expression for starting bound, if any */ Node *endOffset; /* expression for ending bound, if any */ @@ -1530,6 +1575,11 @@ typedef struct GroupingSet * the orderClause might or might not be copied (see copiedOrder); the framing * options are never copied, per spec. * + * "defineClause" is Row Pattern Recognition DEFINE clause (list of + * TargetEntry). TargetEntry.resname represents row pattern definition + * variable name. "patternVariable" and "patternRegexp" represents PATTERN + * clause. + * * The information relevant for the query jumbling is the partition clause * type and its bounds. */ @@ -1559,6 +1609,23 @@ typedef struct WindowClause Index winref; /* ID referenced by window functions */ /* did we copy orderClause from refname? */ bool copiedOrder pg_node_attr(query_jumble_ignore); + /* Row Pattern AFTER MACH SKIP clause */ + RPSkipTo rpSkipTo; /* Row Pattern Skip To type */ + char *rpSkipVariable; /* Row Pattern Skip To variable */ + bool initial; /* true if <row pattern initial or seek> is + * initial */ + /* Row Pattern DEFINE clause (list of TargetEntry) */ + List *defineClause; + /* Row Pattern DEFINE variable initial names (list of String) */ + List *defineInitial; + /* Row Pattern PATTERN variable name (list of String) */ + List *patternVariable; + + /* + * Row Pattern PATTERN regular expression quantifier ('+' or ''. list of + * String) + */ + List *patternRegexp; } WindowClause; /* diff --git a/src/include/parser/kwlist.h b/src/include/parser/kwlist.h index 899d64ad55..f52d797615 100644 --- a/src/include/parser/kwlist.h +++ b/src/include/parser/kwlist.h @@ -129,6 +129,7 @@ PG_KEYWORD("default", DEFAULT, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("defaults", DEFAULTS, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("deferrable", DEFERRABLE, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("deferred", DEFERRED, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("define", DEFINE, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("definer", DEFINER, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("delete", DELETE_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("delimiter", DELIMITER, UNRESERVED_KEYWORD, BARE_LABEL) @@ -215,6 +216,7 @@ PG_KEYWORD("index", INDEX, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("indexes", INDEXES, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inherit", INHERIT, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inherits", INHERITS, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("initial", INITIAL, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("initially", INITIALLY, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inline", INLINE_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("inner", INNER_P, TYPE_FUNC_NAME_KEYWORD, BARE_LABEL) @@ -273,6 +275,7 @@ PG_KEYWORD("match", MATCH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("matched", MATCHED, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("materialized", MATERIALIZED, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("maxvalue", MAXVALUE, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("measures", MEASURES, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("merge", MERGE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("merge_action", MERGE_ACTION, COL_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("method", METHOD, UNRESERVED_KEYWORD, BARE_LABEL) @@ -337,8 +340,11 @@ PG_KEYWORD("partial", PARTIAL, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("partition", PARTITION, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("passing", PASSING, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("password", PASSWORD, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("past", PAST, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("path", PATH, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("pattern", PATTERN_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("period", PERIOD, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("permute", PERMUTE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("placing", PLACING, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("plan", PLAN, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("plans", PLANS, UNRESERVED_KEYWORD, BARE_LABEL) @@ -399,6 +405,7 @@ PG_KEYWORD("scroll", SCROLL, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("search", SEARCH, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("second", SECOND_P, UNRESERVED_KEYWORD, AS_LABEL) PG_KEYWORD("security", SECURITY, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("seek", SEEK, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("select", SELECT, RESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("sequence", SEQUENCE, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("sequences", SEQUENCES, UNRESERVED_KEYWORD, BARE_LABEL) @@ -432,6 +439,7 @@ PG_KEYWORD("strict", STRICT_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("string", STRING_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("strip", STRIP_P, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("subscription", SUBSCRIPTION, UNRESERVED_KEYWORD, BARE_LABEL) +PG_KEYWORD("subset", SUBSET, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("substring", SUBSTRING, COL_NAME_KEYWORD, BARE_LABEL) PG_KEYWORD("support", SUPPORT, UNRESERVED_KEYWORD, BARE_LABEL) PG_KEYWORD("symmetric", SYMMETRIC, RESERVED_KEYWORD, BARE_LABEL) diff --git a/src/include/parser/parse_node.h b/src/include/parser/parse_node.h index 2375e95c10..737f8a9e0e 100644 --- a/src/include/parser/parse_node.h +++ b/src/include/parser/parse_node.h @@ -51,6 +51,7 @@ typedef enum ParseExprKind EXPR_KIND_WINDOW_FRAME_RANGE, /* window frame clause with RANGE */ EXPR_KIND_WINDOW_FRAME_ROWS, /* window frame clause with ROWS */ EXPR_KIND_WINDOW_FRAME_GROUPS, /* window frame clause with GROUPS */ + EXPR_KIND_RPR_DEFINE, /* DEFINE */ EXPR_KIND_SELECT_TARGET, /* SELECT target list item */ EXPR_KIND_INSERT_TARGET, /* INSERT target list item */ EXPR_KIND_UPDATE_SOURCE, /* UPDATE assignment source item */ -- 2.25.1 ----Next_Part(Sat_Dec_21_18_20_04_2024_526)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v25-0002-Row-pattern-recognition-patch-parse-analysis.patch" ^ permalink raw reply [nested|flat] 2+ messages in thread
end of thread, other threads:[~2024-12-21 06:19 UTC | newest] Thread overview: 2+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2022-02-01 09:48 Re: POC: GROUP BY optimization Andrey V. Lepikhov <[email protected]> 2024-12-21 06:19 [PATCH v25 1/9] Row pattern recognition patch for raw parser. Tatsuo Ishii <[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