agora inbox for [email protected]help / color / mirror / Atom feed
[PATCH v33 1/2] Unique key 11+ messages / 3 participants [nested] [flat]
* [PATCH v33 1/2] Unique key @ 2019-07-09 10:44 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-07-09 10:44 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 17 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 373 insertions(+), 13 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..bd1ea53e5c 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + /* + * Fall out quickly if we are passed two identical lists. This mostly + * catches the case where both are NIL, but that's common enough to + * warrant the test. + */ + if (keys1 == keys2) + return true; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + { + found = true; + break; + } + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..984fca0696 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a006dbbe9c 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -940,6 +940,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +965,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1002,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1021,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1065,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1927,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1954,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1981,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2007,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2034,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2061,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2088,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..4e329f0fb5 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -1077,6 +1081,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1119,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1145,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..f75ff6f323 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --ezqb2fwnenb5aigz Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v33-0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH] Unique key @ 2019-07-09 10:44 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-07-09 10:44 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 17 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 373 insertions(+), 13 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index b0dcd02ff6..1ccd68d3aa 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1720,6 +1720,7 @@ _outPathInfo(StringInfo str, const Path *node) =09WRITE_FLOAT_FIELD(startup_cost, "%.2f"); =09WRITE_FLOAT_FIELD(total_cost, "%.2f"); =09WRITE_NODE_FIELD(pathkeys); +=09WRITE_NODE_FIELD(uniquekeys); } =20 /* @@ -2201,6 +2202,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *no= de) =09WRITE_NODE_FIELD(eq_classes); =09WRITE_BOOL_FIELD(ec_merging_done); =09WRITE_NODE_FIELD(canon_pathkeys); +=09WRITE_NODE_FIELD(canon_uniquekeys); =09WRITE_NODE_FIELD(left_join_clauses); =09WRITE_NODE_FIELD(right_join_clauses); =09WRITE_NODE_FIELD(full_join_clauses); @@ -2210,6 +2212,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *no= de) =09WRITE_NODE_FIELD(placeholder_list); =09WRITE_NODE_FIELD(fkey_list); =09WRITE_NODE_FIELD(query_pathkeys); +=09WRITE_NODE_FIELD(query_uniquekeys); =09WRITE_NODE_FIELD(group_pathkeys); =09WRITE_NODE_FIELD(window_pathkeys); =09WRITE_NODE_FIELD(distinct_pathkeys); @@ -2397,6 +2400,14 @@ _outPathKey(StringInfo str, const PathKey *node) =09WRITE_BOOL_FIELD(pk_nulls_first); } =20 +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ +=09WRITE_NODE_TYPE("UNIQUEKEY"); + +=09WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4083,6 +4094,9 @@ outNode(StringInfo str, const void *obj) =09=09=09case T_PathKey: =09=09=09=09_outPathKey(str, obj); =09=09=09=09break; +=09=09=09case T_UniqueKey: +=09=09=09=09_outUniqueKey(str, obj); +=09=09=09=09break; =09=09=09case T_PathTarget: =09=09=09=09_outPathTarget(str, obj); =09=09=09=09break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 4ecde6b421..435b32063c 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtabl= e) =09printf(")\n"); } =20 +/* + * print_uniquekeys - + *=09 uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ +=09ListCell *l; + +=09printf("("); +=09foreach(l, uniquekeys) +=09{ +=09=09UniqueKey *unique_key =3D (UniqueKey *) lfirst(l); +=09=09EquivalenceClass *eclass =3D (EquivalenceClass *) unique_key->eq_cla= use; +=09=09ListCell *k; +=09=09bool=09=09first =3D true; + +=09=09/* chase up */ +=09=09while (eclass->ec_merged) +=09=09=09eclass =3D eclass->ec_merged; + +=09=09printf("("); +=09=09foreach(k, eclass->ec_members) +=09=09{ +=09=09=09EquivalenceMember *mem =3D (EquivalenceMember *) lfirst(k); + +=09=09=09if (first) +=09=09=09=09first =3D false; +=09=09=09else +=09=09=09=09printf(", "); +=09=09=09print_expr((Node *) mem->em_expr, rtable); +=09=09} +=09=09printf(")"); +=09=09if (lnext(uniquekeys, l)) +=09=09=09printf(", "); +=09} +=09printf(")\n"); +} + /* * print_tl *=09 print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/pa= th/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS =3D \ =09joinpath.o \ =09joinrels.o \ =09pathkeys.o \ -=09tidpath.o +=09tidpath.o \ +=09uniquekey.o =20 include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/= path/allpaths.c index db3a68a51d..5fc9b81746 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent= ) =09=09print_pathkeys(path->pathkeys, root->parse->rtable); =09} =20 +=09if (path->uniquekeys) +=09{ +=09=09for (i =3D 0; i < indent; i++) +=09=09=09printf("\t"); +=09=09printf(" uniquekeys: "); +=09=09print_uniquekeys(path->uniquekeys, root->parse->rtable); +=09} + =09if (join) =09{ =09=09JoinPath *jp =3D (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/= path/indxpath.c index 37b257cd0e..88c1dd0f59 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *= index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09 EquivalenceClass *ec, EquivalenceMember *em, =09=09=09=09=09=09=09=09=09 void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); =20 =20 /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, =09List=09 *orderbyclausecols; =09List=09 *index_pathkeys; =09List=09 *useful_pathkeys; +=09List=09 *useful_uniquekeys =3D NIL; =09bool=09=09found_lower_saop_clause; =09bool=09=09pathkeys_possibly_useful; =09bool=09=09index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *re= l, =09if (index_clauses !=3D NIL || useful_pathkeys !=3D NIL || useful_predic= ate || =09=09index_only_scan) =09{ +=09=09if (has_useful_uniquekeys(root)) +=09=09=09useful_uniquekeys =3D get_uniquekeys_for_index(root, useful_pathk= eys); + =09=09ipath =3D create_index_path(root, index, =09=09=09=09=09=09=09=09 index_clauses, =09=09=09=09=09=09=09=09 orderbyclauses, =09=09=09=09=09=09=09=09 orderbyclausecols, =09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09 index_is_ordered ? =09=09=09=09=09=09=09=09 ForwardScanDirection : =09=09=09=09=09=09=09=09 NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09 orderbyclauses, =09=09=09=09=09=09=09=09=09 orderbyclausecols, =09=09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09=09 index_is_ordered ? =09=09=09=09=09=09=09=09=09 ForwardScanDirection : =09=09=09=09=09=09=09=09=09 NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *re= l, =09=09=09=09=09=09=09=09=09=09=09=09=09index_pathkeys); =09=09if (useful_pathkeys !=3D NIL) =09=09{ +=09=09=09if (has_useful_uniquekeys(root)) +=09=09=09=09useful_uniquekeys =3D get_uniquekeys_for_index(root, useful_pa= thkeys); + =09=09=09ipath =3D create_index_path(root, index, =09=09=09=09=09=09=09=09=09 index_clauses, =09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09=09 BackwardScanDirection, =09=09=09=09=09=09=09=09=09 index_only_scan, =09=09=09=09=09=09=09=09=09 outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09=09=09 BackwardScanDirection, =09=09=09=09=09=09=09=09=09=09 index_only_scan, =09=09=09=09=09=09=09=09=09=09 outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, =09return clause; } =20 +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ +=09ListCell *lc; + +=09if (pathkeys) +=09{ +=09=09List *uniquekeys =3D NIL; +=09=09foreach(lc, pathkeys) +=09=09{ +=09=09=09UniqueKey *unique_key; +=09=09=09PathKey *pk =3D (PathKey *) lfirst(lc); +=09=09=09EquivalenceClass *ec =3D (EquivalenceClass *) pk->pk_eclass; + +=09=09=09unique_key =3D makeNode(UniqueKey); +=09=09=09unique_key->eq_clause =3D ec; + +=09=09=09lappend(uniquekeys, unique_key); +=09=09} + +=09=09if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) +=09=09=09return uniquekeys; +=09} + +=09return NIL; +} =20 /*************************************************************************= *** *=09=09=09=09---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS=09---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/= path/pathkeys.c index 2f4fea241a..b0dc1bc22a 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" =20 =20 +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, =09=09=09=09=09=09=09=09=09=09=09 RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, =09return pk; } =20 +/* + * pathkey_is_unique + *=09 Checks if the new pathkey's equivalence class is the same as that = of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ +=09EquivalenceClass *new_ec =3D new_pathkey->pk_eclass; +=09ListCell *lc; + +=09/* If same EC already is already in the list, then not unique */ +=09foreach(lc, pathkeys) +=09{ +=09=09PathKey *old_pathkey =3D (PathKey *) lfirst(lc); + +=09=09if (new_ec =3D=3D old_pathkey->pk_eclass) +=09=09=09return false; +=09} + +=09return true; +} + /* * pathkey_is_redundant *=09 Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { =09EquivalenceClass *new_ec =3D new_pathkey->pk_eclass; -=09ListCell *lc; =20 =09/* Check for EC containing a constant --- unconditionally redundant */ =09if (EC_MUST_BE_REDUNDANT(new_ec)) =09=09return true; =20 -=09/* If same EC already used in list, then redundant */ -=09foreach(lc, pathkeys) -=09{ -=09=09PathKey *old_pathkey =3D (PathKey *) lfirst(lc); - -=09=09if (new_ec =3D=3D old_pathkey->pk_eclass) -=09=09=09return true; -=09} - -=09return false; +=09return !pathkey_is_unique(new_pathkey, pathkeys); } =20 /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, =09return pathkeys; } =20 +/* + * make_pathkeys_for_uniquekeyclauses + *=09=09Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, +=09=09=09=09=09=09=09 List *sortclauses, +=09=09=09=09=09=09=09 List *tlist) +{ +=09List=09 *pathkeys =3D NIL; +=09ListCell *l; + +=09foreach(l, sortclauses) +=09{ +=09=09SortGroupClause *sortcl =3D (SortGroupClause *) lfirst(l); +=09=09Expr=09 *sortkey; +=09=09PathKey *pathkey; + +=09=09sortkey =3D (Expr *) get_sortgroupclause_expr(sortcl, tlist); +=09=09Assert(OidIsValid(sortcl->sortop)); +=09=09pathkey =3D make_pathkey_from_sortop(root, +=09=09=09=09=09=09=09=09=09=09 sortkey, +=09=09=09=09=09=09=09=09=09=09 root->nullable_baserels, +=09=09=09=09=09=09=09=09=09=09 sortcl->sortop, +=09=09=09=09=09=09=09=09=09=09 sortcl->nulls_first, +=09=09=09=09=09=09=09=09=09=09 sortcl->tleSortGroupRef, +=09=09=09=09=09=09=09=09=09=09 true); + +=09=09if (pathkey_is_unique(pathkey, pathkeys)) +=09=09=09pathkeys =3D lappend(pathkeys, pathkey); +=09} + +=09return pathkeys; +} + /*************************************************************************= *** *=09=09PATHKEYS AND MERGECLAUSES *************************************************************************= ***/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer= /path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------= - + * + * uniquekey.c + *=09 Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + *=09 src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------= - + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceC= lass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ +=09List *result =3D NIL; +=09List *sortkeys; +=09ListCell *l; + +=09sortkeys =3D make_pathkeys_for_uniquekeys(root, +=09=09=09=09=09=09=09=09=09=09=09sortclauses, +=09=09=09=09=09=09=09=09=09=09=09root->processed_tlist); + +=09/* Create a uniquekey and add it to the list */ +=09foreach(l, sortkeys) +=09{ +=09=09PathKey *pathkey =3D (PathKey *) lfirst(l); +=09=09EquivalenceClass *ec =3D pathkey->pk_eclass; +=09=09UniqueKey *unique_key =3D make_canonical_uniquekey(root, ec); + +=09=09result =3D lappend(result, unique_key); +=09} + +=09return result; +} + +/* + * uniquekeys_contained_in + *=09 Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ +=09ListCell *key1, +=09=09=09 *key2; + +=09/* +=09 * Fall out quickly if we are passed two identical lists. This mostly +=09 * catches the case where both are NIL, but that's common enough to +=09 * warrant the test. +=09 */ +=09if (keys1 =3D=3D keys2) +=09=09return true; + +=09foreach(key2, keys2) +=09{ +=09=09bool found =3D false; +=09=09UniqueKey *uniquekey2 =3D (UniqueKey *) lfirst(key2); + +=09=09foreach(key1, keys1) +=09=09{ +=09=09=09UniqueKey *uniquekey1 =3D (UniqueKey *) lfirst(key1); + +=09=09=09if (uniquekey1->eq_clause =3D=3D uniquekey2->eq_clause) +=09=09=09{ +=09=09=09=09found =3D true; +=09=09=09=09break; +=09=09=09} +=09=09} + +=09=09if (!found) +=09=09=09return false; +=09} + +=09return true; +} + +/* + * has_useful_uniquekeys + *=09=09Detect whether the planner could have any uniquekeys that are + *=09=09useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ +=09if (root->query_uniquekeys !=3D NIL) +=09=09return true;=09/* there are some */ +=09return false;=09=09/* definitely useless */ +} + +/* + * make_canonical_uniquekey + *=09 Given the parameters for a UniqueKey, find any pre-existing matchin= g + *=09 uniquekey in the query's list of "canonical" uniquekeys. Make a ne= w + *=09 entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instea= d, + * equivclass.c will complain if a merge occurs after root->canon_uniqueke= ys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, +=09=09=09=09=09=09 EquivalenceClass *eclass) +{ +=09UniqueKey *uk; +=09ListCell *lc; +=09MemoryContext oldcontext; + +=09/* The passed eclass might be non-canonical, so chase up to the top */ +=09while (eclass->ec_merged) +=09=09eclass =3D eclass->ec_merged; + +=09foreach(lc, root->canon_uniquekeys) +=09{ +=09=09uk =3D (UniqueKey *) lfirst(lc); +=09=09if (eclass =3D=3D uk->eq_clause) +=09=09=09return uk; +=09} + +=09/* +=09 * Be sure canonical uniquekeys are allocated in the main planning cont= ext. +=09 * Not an issue in normal planning, but it is for GEQO. +=09 */ +=09oldcontext =3D MemoryContextSwitchTo(root->planner_cxt); + +=09uk =3D makeNode(UniqueKey); +=09uk->eq_clause =3D eclass; + +=09root->canon_uniquekeys =3D lappend(root->canon_uniquekeys, uk); + +=09MemoryContextSwitchTo(oldcontext); + +=09return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/p= lan/planagg.c index 974f6204ca..f6144b2267 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) =09=09=09=09=09=09=09=09=09 root->parse->targetList); =20 =09root->query_pathkeys =3D root->sort_pathkeys; +=09root->query_uniquekeys =3D NIL; } =20 /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/= plan/planmain.c index f0c1b52a2e..3ccde03ab7 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, =09root->join_rel_level =3D NULL; =09root->join_cur_level =3D 0; =09root->canon_pathkeys =3D NIL; +=09root->canon_uniquekeys =3D NIL; =09root->left_join_clauses =3D NIL; =09root->right_join_clauses =3D NIL; =09root->full_join_clauses =3D NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/p= lan/planner.c index 7fe11b59a0..8f03a20825 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3651,15 +3651,30 @@ standard_qp_callback(PlannerInfo *root, void *extra= ) =09 * much easier, since we know that the parser ensured that one is a =09 * superset of the other. =09 */ +=09root->query_uniquekeys =3D NIL; + =09if (root->group_pathkeys) +=09{ =09=09root->query_pathkeys =3D root->group_pathkeys; + +=09=09if (!root->parse->hasAggs) +=09=09=09root->query_uniquekeys =3D build_uniquekeys(root, qp_extra->group= Clause); +=09} =09else if (root->window_pathkeys) =09=09root->query_pathkeys =3D root->window_pathkeys; =09else if (list_length(root->distinct_pathkeys) > =09=09=09 list_length(root->sort_pathkeys)) +=09{ =09=09root->query_pathkeys =3D root->distinct_pathkeys; +=09=09root->query_uniquekeys =3D build_uniquekeys(root, parse->distinctCla= use); +=09} =09else if (root->sort_pathkeys) +=09{ =09=09root->query_pathkeys =3D root->sort_pathkeys; + +=09=09if (root->distinct_pathkeys) +=09=09=09root->query_uniquekeys =3D build_uniquekeys(root, parse->distinct= Clause); +=09} =09else =09=09root->query_pathkeys =3D NIL; } @@ -6216,7 +6231,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) =20 =09/* Estimate the cost of index scan */ =09indexScanPath =3D create_index_path(root, indexInfo, -=09=09=09=09=09=09=09=09=09 NIL, NIL, NIL, NIL, +=09=09=09=09=09=09=09=09=09 NIL, NIL, NIL, NIL, NIL, =09=09=09=09=09=09=09=09=09 ForwardScanDirection, false, =09=09=09=09=09=09=09=09=09 NULL, 1.0, false); =20 diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/= util/pathnode.c index 60c93ee7c5..ec02c468d0 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -940,6 +940,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D parallel_workers; =09pathnode->pathkeys =3D NIL;=09/* seqscan has unordered result */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_seqscan(pathnode, root, rel, pathnode->param_info); =20 @@ -964,6 +965,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *r= el, Relids required_outer =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* samplescan has unordered result */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_samplescan(pathnode, root, rel, pathnode->param_info); =20 @@ -1000,6 +1002,7 @@ create_index_path(PlannerInfo *root, =09=09=09=09 List *indexorderbys, =09=09=09=09 List *indexorderbycols, =09=09=09=09 List *pathkeys, +=09=09=09=09 List *uniquekeys, =09=09=09=09 ScanDirection indexscandir, =09=09=09=09 bool indexonly, =09=09=09=09 Relids required_outer, @@ -1018,6 +1021,7 @@ create_index_path(PlannerInfo *root, =09pathnode->path.parallel_safe =3D rel->consider_parallel; =09pathnode->path.parallel_workers =3D 0; =09pathnode->path.pathkeys =3D pathkeys; +=09pathnode->path.uniquekeys =3D uniquekeys; =20 =09pathnode->indexinfo =3D index; =09pathnode->indexclauses =3D indexclauses; @@ -1061,6 +1065,7 @@ create_bitmap_heap_path(PlannerInfo *root, =09pathnode->path.parallel_safe =3D rel->consider_parallel; =09pathnode->path.parallel_workers =3D parallel_degree; =09pathnode->path.pathkeys =3D NIL;=09/* always unordered */ +=09pathnode->path.uniquekeys =3D NIL; =20 =09pathnode->bitmapqual =3D bitmapqual; =20 @@ -1922,6 +1927,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInf= o *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D pathkeys; +=09pathnode->uniquekeys =3D NIL; =20 =09cost_functionscan(pathnode, root, rel, pathnode->param_info); =20 @@ -1948,6 +1954,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptIn= fo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); =20 @@ -1974,6 +1981,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo = *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_valuesscan(pathnode, root, rel, pathnode->param_info); =20 @@ -1999,6 +2007,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *re= l, Relids required_outer) =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* XXX for now, result is always unordere= d */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_ctescan(pathnode, root, rel, pathnode->param_info); =20 @@ -2025,6 +2034,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, Re= lOptInfo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); =20 @@ -2051,6 +2061,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo = *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_resultscan(pathnode, root, rel, pathnode->param_info); =20 @@ -2077,6 +2088,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptIn= fo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09/* Cost is the same as for a regular CTE scan */ =09cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index bce2d59b0d..cbb6ba2586 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag =09T_EquivalenceMember, =09T_PathKey, =09T_PathTarget, +=09T_UniqueKey, =09T_RestrictInfo, =09T_IndexClause, =09T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 23a06d718e..10ece6c875 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -267,6 +267,8 @@ struct PlannerInfo =20 =09List=09 *canon_pathkeys; /* list of "canonical" PathKeys */ =20 +=09List=09 *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + =09List=09 *left_join_clauses;=09/* list of RestrictInfos for mergejoina= ble =09=09=09=09=09=09=09=09=09 * outer join clauses w/nonnullable var on =09=09=09=09=09=09=09=09=09 * left */ @@ -295,6 +297,8 @@ struct PlannerInfo =20 =09List=09 *query_pathkeys; /* desired pathkeys for query_planner() */ =20 +=09List=09 *query_uniquekeys; /* unique keys used for the query */ + =09List=09 *group_pathkeys; /* groupClause pathkeys, if any */ =09List=09 *window_pathkeys;=09/* pathkeys of bottom window, if any */ =09List=09 *distinct_pathkeys;=09/* distinctClause pathkeys, if any */ @@ -1075,6 +1079,15 @@ typedef struct ParamPathInfo =09List=09 *ppi_clauses;=09/* join clauses available from outer rels */ } ParamPathInfo; =20 +/* + * UniqueKey + */ +typedef struct UniqueKey +{ +=09NodeTag=09=09type; + +=09EquivalenceClass *eq_clause;=09/* equivalence class */ +} UniqueKey; =20 /* * Type "Path" is used as-is for sequential-scan paths, as well as some ot= her @@ -1104,6 +1117,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1127,6 +1143,8 @@ typedef struct Path =20 =09List=09 *pathkeys;=09=09/* sort ordering of path's output */ =09/* pathkeys is a List of PathKey nodes; see above */ + +=09List=09 *uniquekeys;=09/* the unique keys, or NIL if none */ } Path; =20 /* Macro for extracting a path's parameterization relids; beware double ev= al */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index cbff56a724..f1a7112877 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); =20 diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathn= ode.h index a12af54971..37a946f857 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, =09=09=09=09=09=09=09=09=09List *indexorderbys, =09=09=09=09=09=09=09=09=09List *indexorderbycols, =09=09=09=09=09=09=09=09=09List *pathkeys, +=09=09=09=09=09=09=09=09=09List *uniquekeys, =09=09=09=09=09=09=09=09=09ScanDirection indexscandir, =09=09=09=09=09=09=09=09=09bool indexonly, =09=09=09=09=09=09=09=09=09Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index c6c34630c2..c79e47eeaf 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, =09=09=09=09=09=09=09=09=09=09 List *sortclauses, =09=09=09=09=09=09=09=09=09=09 List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, +=09=09=09=09=09=09=09=09=09=09 List *sortclauses, +=09=09=09=09=09=09=09=09=09=09 List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, =09=09=09=09=09=09=09=09=09=09=09RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *ro= ot, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09List *live_childrels); =20 +/* + * uniquekey.c + *=09 Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif=09=09=09=09=09=09=09/* PATHS_H */ --=20 2.21.0 --------------51513615E9A6AD19C4BF8178 Content-Type: text/x-patch; charset=UTF-8; name="v30_0002-Index-skip-scan.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="v30_0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v31 1/2] Unique key @ 2019-07-09 10:44 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-07-09 10:44 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 17 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 373 insertions(+), 13 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..bd1ea53e5c 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + /* + * Fall out quickly if we are passed two identical lists. This mostly + * catches the case where both are NIL, but that's common enough to + * warrant the test. + */ + if (keys1 == keys2) + return true; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + { + found = true; + break; + } + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..984fca0696 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a006dbbe9c 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -940,6 +940,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +965,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1002,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1021,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1065,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1927,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1954,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1981,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2007,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2034,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2061,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2088,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..4e329f0fb5 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -1077,6 +1081,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1119,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1145,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..f75ff6f323 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --cxnum6r77tfmznfe Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v31-0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v32 1/2] Unique key @ 2019-07-09 10:44 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-07-09 10:44 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 17 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 373 insertions(+), 13 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..bd1ea53e5c 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + /* + * Fall out quickly if we are passed two identical lists. This mostly + * catches the case where both are NIL, but that's common enough to + * warrant the test. + */ + if (keys1 == keys2) + return true; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + { + found = true; + break; + } + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..984fca0696 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a006dbbe9c 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -940,6 +940,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +965,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1002,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1021,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1065,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1927,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1954,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1981,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2007,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2034,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2061,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2088,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..4e329f0fb5 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -1077,6 +1081,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1119,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1145,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..f75ff6f323 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --f7z2si56qzkbcsr7 Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v32-0002-Index-skip-scan-visibility-check.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH 1/2] Unique key @ 2019-08-02 11:52 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-08-02 11:52 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 2 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/costsize.c | 5 + src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 72 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planner.c | 18 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/backend/optimizer/util/tlist.c | 1 - src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 2 +- src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 377 insertions(+), 15 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index e6ce8e2110..9a4f3e8e4b 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1720,6 +1720,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2201,6 +2202,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2210,6 +2212,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2397,6 +2400,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4073,6 +4084,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 4ecde6b421..62c9d4ef7a 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * unique_key an UniqueKey + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 6864a62132..8249a6b6db 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -13,6 +13,6 @@ top_builddir = ../../../.. include $(top_builddir)/src/Makefile.global OBJS = allpaths.o clausesel.o costsize.o equivclass.o indxpath.o \ - joinpath.o joinrels.o pathkeys.o tidpath.o + joinpath.o joinrels.o pathkeys.o tidpath.o uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index e9ee32b7f4..6f4c25f7dd 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3957,6 +3957,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c index 3a9a994733..2565dcf296 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -705,6 +705,11 @@ cost_index(IndexPath *path, PlannerInfo *root, double loop_count, path->path.parallel_aware = true; } + /* Consider cost based on unique key */ + if (path->path.uniquekeys) + { + } + /* * Now interpolate based on estimated index order correlation to get total * disk I/O cost for main table accesses. diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 5f339fdfde..4b90dd378a 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3369,6 +3381,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 2f4fea241a..0cba366c06 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,30 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Part of pathkey_is_redundant, that is reponsible for the case, when the + * new pathkey's equivalence class is the same as that of any existing + * member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +160,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1113,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + /* + * Fall out quickly if we are passed two identical lists. This mostly + * catches the case where both are NIL, but that's common enough to + * warrant the test. + */ + if (keys1 == keys2) + return true; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + { + found = true; + break; + } + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 8f51f59f8a..5ee9ee6595 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3656,15 +3656,31 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->canon_uniquekeys = NIL; + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6238,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index 0ac73984d2..ac0b937895 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -941,6 +941,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -965,6 +966,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1001,6 +1003,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1019,6 +1022,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1062,6 +1066,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1923,6 +1928,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1949,6 +1955,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1975,6 +1982,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -2000,6 +2008,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2026,6 +2035,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2052,6 +2062,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2078,6 +2089,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/backend/optimizer/util/tlist.c b/src/backend/optimizer/util/tlist.c index 7ccb10e4e1..618032e82c 100644 --- a/src/backend/optimizer/util/tlist.c +++ b/src/backend/optimizer/util/tlist.c @@ -427,7 +427,6 @@ get_sortgrouplist_exprs(List *sgClauses, List *targetList) return result; } - /***************************************************************************** * Functions to extract data from a list of SortGroupClauses * diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 4e2fb39105..a9b67c64f8 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index e3c579ee44..c1d6f33fc0 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -1077,6 +1081,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1119,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1145,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index cbff56a724..31e8f0686e 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -16,7 +16,6 @@ #include "executor/tuptable.h" - #define nodeDisplay(x) pprint(x) extern void print(const void *obj); @@ -28,6 +27,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index 182ffeef4b..374cac157b 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 7345137d1d..c7976d4a90 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -209,6 +209,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -235,4 +238,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --------------A6AA3F98E061114DE0DF40DC Content-Type: text/x-patch; name="v23_0002-Index-skip-scan.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="v23_0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH 1/2] Unique key @ 2019-11-11 13:49 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-11-11 13:49 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/costsize.c | 5 + src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 17 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 17 files changed, 378 insertions(+), 13 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index b0dcd02ff6..1ccd68d3aa 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1720,6 +1720,7 @@ _outPathInfo(StringInfo str, const Path *node) =09WRITE_FLOAT_FIELD(startup_cost, "%.2f"); =09WRITE_FLOAT_FIELD(total_cost, "%.2f"); =09WRITE_NODE_FIELD(pathkeys); +=09WRITE_NODE_FIELD(uniquekeys); } =20 /* @@ -2201,6 +2202,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *no= de) =09WRITE_NODE_FIELD(eq_classes); =09WRITE_BOOL_FIELD(ec_merging_done); =09WRITE_NODE_FIELD(canon_pathkeys); +=09WRITE_NODE_FIELD(canon_uniquekeys); =09WRITE_NODE_FIELD(left_join_clauses); =09WRITE_NODE_FIELD(right_join_clauses); =09WRITE_NODE_FIELD(full_join_clauses); @@ -2210,6 +2212,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *no= de) =09WRITE_NODE_FIELD(placeholder_list); =09WRITE_NODE_FIELD(fkey_list); =09WRITE_NODE_FIELD(query_pathkeys); +=09WRITE_NODE_FIELD(query_uniquekeys); =09WRITE_NODE_FIELD(group_pathkeys); =09WRITE_NODE_FIELD(window_pathkeys); =09WRITE_NODE_FIELD(distinct_pathkeys); @@ -2397,6 +2400,14 @@ _outPathKey(StringInfo str, const PathKey *node) =09WRITE_BOOL_FIELD(pk_nulls_first); } =20 +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ +=09WRITE_NODE_TYPE("UNIQUEKEY"); + +=09WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4083,6 +4094,9 @@ outNode(StringInfo str, const void *obj) =09=09=09case T_PathKey: =09=09=09=09_outPathKey(str, obj); =09=09=09=09break; +=09=09=09case T_UniqueKey: +=09=09=09=09_outUniqueKey(str, obj); +=09=09=09=09break; =09=09=09case T_PathTarget: =09=09=09=09_outPathTarget(str, obj); =09=09=09=09break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 4ecde6b421..62c9d4ef7a 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtabl= e) =09printf(")\n"); } =20 +/* + * print_uniquekeys - + *=09 unique_key an UniqueKey + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ +=09ListCell *l; + +=09printf("("); +=09foreach(l, uniquekeys) +=09{ +=09=09UniqueKey *unique_key =3D (UniqueKey *) lfirst(l); +=09=09EquivalenceClass *eclass =3D (EquivalenceClass *) unique_key->eq_cla= use; +=09=09ListCell *k; +=09=09bool=09=09first =3D true; + +=09=09/* chase up */ +=09=09while (eclass->ec_merged) +=09=09=09eclass =3D eclass->ec_merged; + +=09=09printf("("); +=09=09foreach(k, eclass->ec_members) +=09=09{ +=09=09=09EquivalenceMember *mem =3D (EquivalenceMember *) lfirst(k); + +=09=09=09if (first) +=09=09=09=09first =3D false; +=09=09=09else +=09=09=09=09printf(", "); +=09=09=09print_expr((Node *) mem->em_expr, rtable); +=09=09} +=09=09printf(")"); +=09=09if (lnext(uniquekeys, l)) +=09=09=09printf(", "); +=09} +=09printf(")\n"); +} + /* * print_tl *=09 print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/pa= th/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS =3D \ =09joinpath.o \ =09joinrels.o \ =09pathkeys.o \ -=09tidpath.o +=09tidpath.o \ +=09uniquekey.o =20 include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/= path/allpaths.c index db3a68a51d..5fc9b81746 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent= ) =09=09print_pathkeys(path->pathkeys, root->parse->rtable); =09} =20 +=09if (path->uniquekeys) +=09{ +=09=09for (i =3D 0; i < indent; i++) +=09=09=09printf("\t"); +=09=09printf(" uniquekeys: "); +=09=09print_uniquekeys(path->uniquekeys, root->parse->rtable); +=09} + =09if (join) =09{ =09=09JoinPath *jp =3D (JoinPath *) path; diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/= path/costsize.c index c5f6593485..0ec9a6db76 100644 --- a/src/backend/optimizer/path/costsize.c +++ b/src/backend/optimizer/path/costsize.c @@ -705,6 +705,11 @@ cost_index(IndexPath *path, PlannerInfo *root, double = loop_count, =09=09path->path.parallel_aware =3D true; =09} =20 +=09/* Consider cost based on unique key */ +=09if (path->path.uniquekeys) +=09{ +=09} + =09/* =09 * Now interpolate based on estimated index order correlation to get to= tal =09 * disk I/O cost for main table accesses. diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/= path/indxpath.c index 37b257cd0e..aa0da49119 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *= index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09 EquivalenceClass *ec, EquivalenceMember *em, =09=09=09=09=09=09=09=09=09 void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); =20 =20 /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, =09List=09 *orderbyclausecols; =09List=09 *index_pathkeys; =09List=09 *useful_pathkeys; +=09List=09 *useful_uniquekeys; =09bool=09=09found_lower_saop_clause; =09bool=09=09pathkeys_possibly_useful; =09bool=09=09index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *re= l, =09if (index_clauses !=3D NIL || useful_pathkeys !=3D NIL || useful_predic= ate || =09=09index_only_scan) =09{ +=09=09if (has_useful_uniquekeys(root)) +=09=09=09useful_uniquekeys =3D get_uniquekeys_for_index(root, useful_pathk= eys); + =09=09ipath =3D create_index_path(root, index, =09=09=09=09=09=09=09=09 index_clauses, =09=09=09=09=09=09=09=09 orderbyclauses, =09=09=09=09=09=09=09=09 orderbyclausecols, =09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09 index_is_ordered ? =09=09=09=09=09=09=09=09 ForwardScanDirection : =09=09=09=09=09=09=09=09 NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09 orderbyclauses, =09=09=09=09=09=09=09=09=09 orderbyclausecols, =09=09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09=09 index_is_ordered ? =09=09=09=09=09=09=09=09=09 ForwardScanDirection : =09=09=09=09=09=09=09=09=09 NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *re= l, =09=09=09=09=09=09=09=09=09=09=09=09=09index_pathkeys); =09=09if (useful_pathkeys !=3D NIL) =09=09{ +=09=09=09if (has_useful_uniquekeys(root)) +=09=09=09=09useful_uniquekeys =3D get_uniquekeys_for_index(root, useful_pa= thkeys); + =09=09=09ipath =3D create_index_path(root, index, =09=09=09=09=09=09=09=09=09 index_clauses, =09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09=09 BackwardScanDirection, =09=09=09=09=09=09=09=09=09 index_only_scan, =09=09=09=09=09=09=09=09=09 outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09=09 NIL, =09=09=09=09=09=09=09=09=09=09 useful_pathkeys, +=09=09=09=09=09=09=09=09=09=09 useful_uniquekeys, =09=09=09=09=09=09=09=09=09=09 BackwardScanDirection, =09=09=09=09=09=09=09=09=09=09 index_only_scan, =09=09=09=09=09=09=09=09=09=09 outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, =09return clause; } =20 +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ +=09ListCell *lc; + +=09if (pathkeys) +=09{ +=09=09List *uniquekeys =3D NIL; +=09=09foreach(lc, pathkeys) +=09=09{ +=09=09=09UniqueKey *unique_key; +=09=09=09PathKey *pk =3D (PathKey *) lfirst(lc); +=09=09=09EquivalenceClass *ec =3D (EquivalenceClass *) pk->pk_eclass; + +=09=09=09unique_key =3D makeNode(UniqueKey); +=09=09=09unique_key->eq_clause =3D ec; +=09=09=09 +=09=09=09lappend(uniquekeys, unique_key); +=09=09} + +=09=09if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) +=09=09=09return uniquekeys; +=09} + +=09return NIL; +} =20 /*************************************************************************= *** *=09=09=09=09---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS=09---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/= path/pathkeys.c index 2f4fea241a..b0dc1bc22a 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" =20 =20 +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, =09=09=09=09=09=09=09=09=09=09=09 RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, =09return pk; } =20 +/* + * pathkey_is_unique + *=09 Checks if the new pathkey's equivalence class is the same as that = of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ +=09EquivalenceClass *new_ec =3D new_pathkey->pk_eclass; +=09ListCell *lc; + +=09/* If same EC already is already in the list, then not unique */ +=09foreach(lc, pathkeys) +=09{ +=09=09PathKey *old_pathkey =3D (PathKey *) lfirst(lc); + +=09=09if (new_ec =3D=3D old_pathkey->pk_eclass) +=09=09=09return false; +=09} + +=09return true; +} + /* * pathkey_is_redundant *=09 Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { =09EquivalenceClass *new_ec =3D new_pathkey->pk_eclass; -=09ListCell *lc; =20 =09/* Check for EC containing a constant --- unconditionally redundant */ =09if (EC_MUST_BE_REDUNDANT(new_ec)) =09=09return true; =20 -=09/* If same EC already used in list, then redundant */ -=09foreach(lc, pathkeys) -=09{ -=09=09PathKey *old_pathkey =3D (PathKey *) lfirst(lc); - -=09=09if (new_ec =3D=3D old_pathkey->pk_eclass) -=09=09=09return true; -=09} - -=09return false; +=09return !pathkey_is_unique(new_pathkey, pathkeys); } =20 /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, =09return pathkeys; } =20 +/* + * make_pathkeys_for_uniquekeyclauses + *=09=09Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, +=09=09=09=09=09=09=09 List *sortclauses, +=09=09=09=09=09=09=09 List *tlist) +{ +=09List=09 *pathkeys =3D NIL; +=09ListCell *l; + +=09foreach(l, sortclauses) +=09{ +=09=09SortGroupClause *sortcl =3D (SortGroupClause *) lfirst(l); +=09=09Expr=09 *sortkey; +=09=09PathKey *pathkey; + +=09=09sortkey =3D (Expr *) get_sortgroupclause_expr(sortcl, tlist); +=09=09Assert(OidIsValid(sortcl->sortop)); +=09=09pathkey =3D make_pathkey_from_sortop(root, +=09=09=09=09=09=09=09=09=09=09 sortkey, +=09=09=09=09=09=09=09=09=09=09 root->nullable_baserels, +=09=09=09=09=09=09=09=09=09=09 sortcl->sortop, +=09=09=09=09=09=09=09=09=09=09 sortcl->nulls_first, +=09=09=09=09=09=09=09=09=09=09 sortcl->tleSortGroupRef, +=09=09=09=09=09=09=09=09=09=09 true); + +=09=09if (pathkey_is_unique(pathkey, pathkeys)) +=09=09=09pathkeys =3D lappend(pathkeys, pathkey); +=09} + +=09return pathkeys; +} + /*************************************************************************= *** *=09=09PATHKEYS AND MERGECLAUSES *************************************************************************= ***/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer= /path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------= - + * + * uniquekey.c + *=09 Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + *=09 src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------= - + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceC= lass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ +=09List *result =3D NIL; +=09List *sortkeys; +=09ListCell *l; + +=09sortkeys =3D make_pathkeys_for_uniquekeys(root, +=09=09=09=09=09=09=09=09=09=09=09sortclauses, +=09=09=09=09=09=09=09=09=09=09=09root->processed_tlist); + +=09/* Create a uniquekey and add it to the list */ +=09foreach(l, sortkeys) +=09{ +=09=09PathKey *pathkey =3D (PathKey *) lfirst(l); +=09=09EquivalenceClass *ec =3D pathkey->pk_eclass; +=09=09UniqueKey *unique_key =3D make_canonical_uniquekey(root, ec); + +=09=09result =3D lappend(result, unique_key); +=09} + +=09return result; +} + +/* + * uniquekeys_contained_in + *=09 Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ +=09ListCell *key1, +=09=09=09 *key2; + +=09/* +=09 * Fall out quickly if we are passed two identical lists. This mostly +=09 * catches the case where both are NIL, but that's common enough to +=09 * warrant the test. +=09 */ +=09if (keys1 =3D=3D keys2) +=09=09return true; + +=09foreach(key2, keys2) +=09{ +=09=09bool found =3D false; +=09=09UniqueKey *uniquekey2 =3D (UniqueKey *) lfirst(key2); + +=09=09foreach(key1, keys1) +=09=09{ +=09=09=09UniqueKey *uniquekey1 =3D (UniqueKey *) lfirst(key1); + +=09=09=09if (uniquekey1->eq_clause =3D=3D uniquekey2->eq_clause) +=09=09=09{ +=09=09=09=09found =3D true; +=09=09=09=09break; +=09=09=09} +=09=09} + +=09=09if (!found) +=09=09=09return false; +=09} + +=09return true; +} + +/* + * has_useful_uniquekeys + *=09=09Detect whether the planner could have any uniquekeys that are + *=09=09useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ +=09if (root->query_uniquekeys !=3D NIL) +=09=09return true;=09/* there are some */ +=09return false;=09=09/* definitely useless */ +} + +/* + * make_canonical_uniquekey + *=09 Given the parameters for a UniqueKey, find any pre-existing matchin= g + *=09 uniquekey in the query's list of "canonical" uniquekeys. Make a ne= w + *=09 entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instea= d, + * equivclass.c will complain if a merge occurs after root->canon_uniqueke= ys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, +=09=09=09=09=09=09 EquivalenceClass *eclass) +{ +=09UniqueKey *uk; +=09ListCell *lc; +=09MemoryContext oldcontext; + +=09/* The passed eclass might be non-canonical, so chase up to the top */ +=09while (eclass->ec_merged) +=09=09eclass =3D eclass->ec_merged; + +=09foreach(lc, root->canon_uniquekeys) +=09{ +=09=09uk =3D (UniqueKey *) lfirst(lc); +=09=09if (eclass =3D=3D uk->eq_clause) +=09=09=09return uk; +=09} + +=09/* +=09 * Be sure canonical uniquekeys are allocated in the main planning cont= ext. +=09 * Not an issue in normal planning, but it is for GEQO. +=09 */ +=09oldcontext =3D MemoryContextSwitchTo(root->planner_cxt); + +=09uk =3D makeNode(UniqueKey); +=09uk->eq_clause =3D eclass; + +=09root->canon_uniquekeys =3D lappend(root->canon_uniquekeys, uk); + +=09MemoryContextSwitchTo(oldcontext); + +=09return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/p= lan/planagg.c index 9381939c82..3d32f6dfd6 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -512,6 +512,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) =09=09=09=09=09=09=09=09=09 root->parse->targetList); =20 =09root->query_pathkeys =3D root->sort_pathkeys; +=09root->query_uniquekeys =3D NIL; } =20 /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/= plan/planmain.c index f0c1b52a2e..3ccde03ab7 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, =09root->join_rel_level =3D NULL; =09root->join_cur_level =3D 0; =09root->canon_pathkeys =3D NIL; +=09root->canon_uniquekeys =3D NIL; =09root->left_join_clauses =3D NIL; =09root->right_join_clauses =3D NIL; =09root->full_join_clauses =3D NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/p= lan/planner.c index 17c5f086fb..2507ec7d2a 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3652,15 +3652,30 @@ standard_qp_callback(PlannerInfo *root, void *extra= ) =09 * much easier, since we know that the parser ensured that one is a =09 * superset of the other. =09 */ +=09root->query_uniquekeys =3D NIL; + =09if (root->group_pathkeys) +=09{ =09=09root->query_pathkeys =3D root->group_pathkeys; + +=09=09if (!root->parse->hasAggs) +=09=09=09root->query_uniquekeys =3D build_uniquekeys(root, qp_extra->group= Clause); +=09} =09else if (root->window_pathkeys) =09=09root->query_pathkeys =3D root->window_pathkeys; =09else if (list_length(root->distinct_pathkeys) > =09=09=09 list_length(root->sort_pathkeys)) +=09{ =09=09root->query_pathkeys =3D root->distinct_pathkeys; +=09=09root->query_uniquekeys =3D build_uniquekeys(root, parse->distinctCla= use); +=09} =09else if (root->sort_pathkeys) +=09{ =09=09root->query_pathkeys =3D root->sort_pathkeys; + +=09=09if (root->distinct_pathkeys) +=09=09=09root->query_uniquekeys =3D build_uniquekeys(root, parse->distinct= Clause); +=09} =09else =09=09root->query_pathkeys =3D NIL; } @@ -6217,7 +6232,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) =20 =09/* Estimate the cost of index scan */ =09indexScanPath =3D create_index_path(root, indexInfo, -=09=09=09=09=09=09=09=09=09 NIL, NIL, NIL, NIL, +=09=09=09=09=09=09=09=09=09 NIL, NIL, NIL, NIL, NIL, =09=09=09=09=09=09=09=09=09 ForwardScanDirection, false, =09=09=09=09=09=09=09=09=09 NULL, 1.0, false); =20 diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/= util/pathnode.c index 34acb732ee..f268112386 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -941,6 +941,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D parallel_workers; =09pathnode->pathkeys =3D NIL;=09/* seqscan has unordered result */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_seqscan(pathnode, root, rel, pathnode->param_info); =20 @@ -965,6 +966,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *r= el, Relids required_outer =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* samplescan has unordered result */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_samplescan(pathnode, root, rel, pathnode->param_info); =20 @@ -1001,6 +1003,7 @@ create_index_path(PlannerInfo *root, =09=09=09=09 List *indexorderbys, =09=09=09=09 List *indexorderbycols, =09=09=09=09 List *pathkeys, +=09=09=09=09 List *uniquekeys, =09=09=09=09 ScanDirection indexscandir, =09=09=09=09 bool indexonly, =09=09=09=09 Relids required_outer, @@ -1019,6 +1022,7 @@ create_index_path(PlannerInfo *root, =09pathnode->path.parallel_safe =3D rel->consider_parallel; =09pathnode->path.parallel_workers =3D 0; =09pathnode->path.pathkeys =3D pathkeys; +=09pathnode->path.uniquekeys =3D uniquekeys; =20 =09pathnode->indexinfo =3D index; =09pathnode->indexclauses =3D indexclauses; @@ -1062,6 +1066,7 @@ create_bitmap_heap_path(PlannerInfo *root, =09pathnode->path.parallel_safe =3D rel->consider_parallel; =09pathnode->path.parallel_workers =3D parallel_degree; =09pathnode->path.pathkeys =3D NIL;=09/* always unordered */ +=09pathnode->path.uniquekeys =3D NIL; =20 =09pathnode->bitmapqual =3D bitmapqual; =20 @@ -1923,6 +1928,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInf= o *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D pathkeys; +=09pathnode->uniquekeys =3D NIL; =20 =09cost_functionscan(pathnode, root, rel, pathnode->param_info); =20 @@ -1949,6 +1955,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptIn= fo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); =20 @@ -1975,6 +1982,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo = *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_valuesscan(pathnode, root, rel, pathnode->param_info); =20 @@ -2000,6 +2008,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *re= l, Relids required_outer) =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* XXX for now, result is always unordere= d */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_ctescan(pathnode, root, rel, pathnode->param_info); =20 @@ -2026,6 +2035,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, Re= lOptInfo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); =20 @@ -2052,6 +2062,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo = *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09cost_resultscan(pathnode, root, rel, pathnode->param_info); =20 @@ -2078,6 +2089,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptIn= fo *rel, =09pathnode->parallel_safe =3D rel->consider_parallel; =09pathnode->parallel_workers =3D 0; =09pathnode->pathkeys =3D NIL;=09/* result is always unordered */ +=09pathnode->uniquekeys =3D NIL; =20 =09/* Cost is the same as for a regular CTE scan */ =09cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index bce2d59b0d..cbb6ba2586 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag =09T_EquivalenceMember, =09T_PathKey, =09T_PathTarget, +=09T_UniqueKey, =09T_RestrictInfo, =09T_IndexClause, =09T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 23a06d718e..6198c31cd4 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -267,6 +267,8 @@ struct PlannerInfo =20 =09List=09 *canon_pathkeys; /* list of "canonical" PathKeys */ =20 +=09List=09 *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + =09List=09 *left_join_clauses;=09/* list of RestrictInfos for mergejoina= ble =09=09=09=09=09=09=09=09=09 * outer join clauses w/nonnullable var on =09=09=09=09=09=09=09=09=09 * left */ @@ -295,6 +297,8 @@ struct PlannerInfo =20 =09List=09 *query_pathkeys; /* desired pathkeys for query_planner() */ =20 +=09List=09 *query_uniquekeys; /* */ + =09List=09 *group_pathkeys; /* groupClause pathkeys, if any */ =09List=09 *window_pathkeys;=09/* pathkeys of bottom window, if any */ =09List=09 *distinct_pathkeys;=09/* distinctClause pathkeys, if any */ @@ -1075,6 +1079,15 @@ typedef struct ParamPathInfo =09List=09 *ppi_clauses;=09/* join clauses available from outer rels */ } ParamPathInfo; =20 +/* + * UniqueKey + */ +typedef struct UniqueKey +{ +=09NodeTag=09=09type; + +=09EquivalenceClass *eq_clause;=09/* equivalence class */ +} UniqueKey; =20 /* * Type "Path" is used as-is for sequential-scan paths, as well as some ot= her @@ -1104,6 +1117,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1127,6 +1143,8 @@ typedef struct Path =20 =09List=09 *pathkeys;=09=09/* sort ordering of path's output */ =09/* pathkeys is a List of PathKey nodes; see above */ + +=09List=09 *uniquekeys;=09/* the unique keys, or NIL if none */ } Path; =20 /* Macro for extracting a path's parameterization relids; beware double ev= al */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index cbff56a724..f1a7112877 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); =20 diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathn= ode.h index a12af54971..37a946f857 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, =09=09=09=09=09=09=09=09=09List *indexorderbys, =09=09=09=09=09=09=09=09=09List *indexorderbycols, =09=09=09=09=09=09=09=09=09List *pathkeys, +=09=09=09=09=09=09=09=09=09List *uniquekeys, =09=09=09=09=09=09=09=09=09ScanDirection indexscandir, =09=09=09=09=09=09=09=09=09bool indexonly, =09=09=09=09=09=09=09=09=09Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index c6c34630c2..c79e47eeaf 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, =09=09=09=09=09=09=09=09=09=09 List *sortclauses, =09=09=09=09=09=09=09=09=09=09 List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, +=09=09=09=09=09=09=09=09=09=09 List *sortclauses, +=09=09=09=09=09=09=09=09=09=09 List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, =09=09=09=09=09=09=09=09=09=09=09RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *ro= ot, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, =09=09=09=09=09=09=09=09=09List *live_childrels); =20 +/* + * uniquekey.c + *=09 Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif=09=09=09=09=09=09=09/* PATHS_H */ --=20 2.21.0 --------------25BA7482CCCC3CA4CEC0D330 Content-Type: text/x-patch; charset=UTF-8; name="v29_0002-Index-skip-scan.patch" Content-Transfer-Encoding: quoted-printable Content-Disposition: attachment; filename="v29_0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH 1/2] Unique key @ 2019-11-15 14:46 jesperpedersen <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: jesperpedersen @ 2019-11-15 14:46 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 +++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++-- src/backend/optimizer/path/uniquekey.c | 147 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 17 ++- src/backend/optimizer/util/pathnode.c | 12 ++ src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 18 +++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 1 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 373 insertions(+), 13 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..34e7fafa84 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..13d4ebb98c --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,147 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + /* + * Fall out quickly if we are passed two identical lists. This mostly + * catches the case where both are NIL, but that's common enough to + * warrant the test. + */ + if (keys1 == keys2) + return true; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + { + found = true; + break; + } + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..984fca0696 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a006dbbe9c 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -940,6 +940,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +965,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1002,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1021,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1065,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1927,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1954,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1981,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2007,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2034,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2061,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2088,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..4e329f0fb5 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -1077,6 +1081,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1119,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1145,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..f75ff6f323 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -44,6 +44,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.1 --------------51B4E6A19513F7FD264CD0FF Content-Type: text/x-patch; charset=UTF-8; name="v31-0002-Index-skip-scan.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="v31-0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v33 1/2] Unique key @ 2020-03-24 16:04 Dmitrii Dolgov <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: Dmitrii Dolgov @ 2020-03-24 16:04 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 ++++++++ src/backend/optimizer/path/pathkeys.c | 71 +++++++++++-- src/backend/optimizer/path/uniquekey.c | 136 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 37 ++++++- src/backend/optimizer/util/pathnode.c | 46 +++++++-- src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 19 ++++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 2 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 408 insertions(+), 23 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..363f5349f1 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + uniquekeys = lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..c421401d0f --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,136 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + return true; + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..a7de8476d9 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); @@ -7107,6 +7122,26 @@ apply_scanjoin_target_to_paths(PlannerInfo *root, } } + foreach(lc, rel->unique_pathlist) + { + Path *subpath = (Path *) lfirst(lc); + + /* Shouldn't have any parameterized paths anymore */ + Assert(subpath->param_info == NULL); + + if (tlist_same_exprs) + subpath->pathtarget->sortgrouprefs = + scanjoin_target->sortgrouprefs; + else + { + Path *newpath; + + newpath = (Path *) create_projection_path(root, rel, subpath, + scanjoin_target); + lfirst(lc) = newpath; + } + } + /* * Now, if final scan/join target contains SRFs, insert ProjectSetPath(s) * atop each existing path. (Note that this function doesn't look at the diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a4dfafbb59 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -361,9 +361,9 @@ set_cheapest(RelOptInfo *parent_rel) } /* - * add_path + * add_path_to * Consider a potential implementation path for the specified parent rel, - * and add it to the rel's pathlist if it is worthy of consideration. + * and add it to the specified pathlist if it is worthy of consideration. * A path is worthy if it has a better sort order (better pathkeys) or * cheaper cost (on either dimension), or generates fewer rows, than any * existing path that has the same or superset parameterization rels. @@ -416,10 +416,10 @@ set_cheapest(RelOptInfo *parent_rel) * 'parent_rel' is the relation entry to which the path corresponds. * 'new_path' is a potential path for parent_rel. * - * Returns nothing, but modifies parent_rel->pathlist. + * Returns modified pathlist. */ -void -add_path(RelOptInfo *parent_rel, Path *new_path) +static List * +add_path_to(RelOptInfo *parent_rel, List *pathlist, Path *new_path) { bool accept_new = true; /* unless we find a superior old path */ int insert_at = 0; /* where to insert new item */ @@ -440,7 +440,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) * for more than one old path to be tossed out because new_path dominates * it. */ - foreach(p1, parent_rel->pathlist) + foreach(p1, pathlist) { Path *old_path = (Path *) lfirst(p1); bool remove_old = false; /* unless new proves superior */ @@ -584,8 +584,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) */ if (remove_old) { - parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist, - p1); + pathlist = foreach_delete_current(pathlist, p1); /* * Delete the data pointed-to by the deleted cell, if possible @@ -612,8 +611,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) if (accept_new) { /* Accept the new path: insert it at proper place in pathlist */ - parent_rel->pathlist = - list_insert_nth(parent_rel->pathlist, insert_at, new_path); + pathlist = list_insert_nth(pathlist, insert_at, new_path); } else { @@ -621,6 +619,15 @@ add_path(RelOptInfo *parent_rel, Path *new_path) if (!IsA(new_path, IndexPath)) pfree(new_path); } + + return pathlist; +} + +void +add_path(RelOptInfo *parent_rel, Path *new_path) +{ + parent_rel->pathlist = add_path_to(parent_rel, + parent_rel->pathlist, new_path); } /* @@ -915,6 +922,13 @@ add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, return true; } +void +add_unique_path(RelOptInfo *parent_rel, Path *new_path) +{ + parent_rel->unique_pathlist = add_path_to(parent_rel, + parent_rel->unique_pathlist, + new_path); +} /***************************************************************************** * PATH NODE CREATION ROUTINES @@ -940,6 +954,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +979,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1016,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1035,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1079,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1941,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1968,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1995,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2021,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2048,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2075,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2102,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..0de27f0ef3 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -657,6 +661,7 @@ typedef struct RelOptInfo List *pathlist; /* Path structures */ List *ppilist; /* ParamPathInfos used in pathlist */ List *partial_pathlist; /* partial Paths */ + List *unique_pathlist; /* unique Paths */ struct Path *cheapest_startup_path; struct Path *cheapest_total_path; struct Path *cheapest_unique_path; @@ -1077,6 +1082,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1120,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1146,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..fd25997af5 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -34,6 +34,7 @@ extern void add_partial_path(RelOptInfo *parent_rel, Path *new_path); extern bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys); +extern void add_unique_path(RelOptInfo *parent_rel, Path *new_path); extern Path *create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer, int parallel_workers); extern Path *create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, @@ -44,6 +45,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --y3rsfeqxxd2vddcp Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v33-0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v33 1/2] Unique key @ 2020-03-24 16:04 Dmitrii Dolgov <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: Dmitrii Dolgov @ 2020-03-24 16:04 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 ++++++ src/backend/nodes/print.c | 39 +++++++++++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 +++ src/backend/optimizer/path/indxpath.c | 41 ++++++++++++++++ src/backend/optimizer/path/pathkeys.c | 71 ++++++++++++++++++++++----- src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 37 +++++++++++++- src/backend/optimizer/util/pathnode.c | 46 +++++++++++++---- src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 19 +++++++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 2 + src/include/optimizer/paths.h | 11 +++++ 15 files changed, 272 insertions(+), 23 deletions(-) diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..363f5349f1 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + uniquekeys = lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..a7de8476d9 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); @@ -7107,6 +7122,26 @@ apply_scanjoin_target_to_paths(PlannerInfo *root, } } + foreach(lc, rel->unique_pathlist) + { + Path *subpath = (Path *) lfirst(lc); + + /* Shouldn't have any parameterized paths anymore */ + Assert(subpath->param_info == NULL); + + if (tlist_same_exprs) + subpath->pathtarget->sortgrouprefs = + scanjoin_target->sortgrouprefs; + else + { + Path *newpath; + + newpath = (Path *) create_projection_path(root, rel, subpath, + scanjoin_target); + lfirst(lc) = newpath; + } + } + /* * Now, if final scan/join target contains SRFs, insert ProjectSetPath(s) * atop each existing path. (Note that this function doesn't look at the diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a4dfafbb59 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -361,9 +361,9 @@ set_cheapest(RelOptInfo *parent_rel) } /* - * add_path + * add_path_to * Consider a potential implementation path for the specified parent rel, - * and add it to the rel's pathlist if it is worthy of consideration. + * and add it to the specified pathlist if it is worthy of consideration. * A path is worthy if it has a better sort order (better pathkeys) or * cheaper cost (on either dimension), or generates fewer rows, than any * existing path that has the same or superset parameterization rels. @@ -416,10 +416,10 @@ set_cheapest(RelOptInfo *parent_rel) * 'parent_rel' is the relation entry to which the path corresponds. * 'new_path' is a potential path for parent_rel. * - * Returns nothing, but modifies parent_rel->pathlist. + * Returns modified pathlist. */ -void -add_path(RelOptInfo *parent_rel, Path *new_path) +static List * +add_path_to(RelOptInfo *parent_rel, List *pathlist, Path *new_path) { bool accept_new = true; /* unless we find a superior old path */ int insert_at = 0; /* where to insert new item */ @@ -440,7 +440,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) * for more than one old path to be tossed out because new_path dominates * it. */ - foreach(p1, parent_rel->pathlist) + foreach(p1, pathlist) { Path *old_path = (Path *) lfirst(p1); bool remove_old = false; /* unless new proves superior */ @@ -584,8 +584,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) */ if (remove_old) { - parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist, - p1); + pathlist = foreach_delete_current(pathlist, p1); /* * Delete the data pointed-to by the deleted cell, if possible @@ -612,8 +611,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) if (accept_new) { /* Accept the new path: insert it at proper place in pathlist */ - parent_rel->pathlist = - list_insert_nth(parent_rel->pathlist, insert_at, new_path); + pathlist = list_insert_nth(pathlist, insert_at, new_path); } else { @@ -621,6 +619,15 @@ add_path(RelOptInfo *parent_rel, Path *new_path) if (!IsA(new_path, IndexPath)) pfree(new_path); } + + return pathlist; +} + +void +add_path(RelOptInfo *parent_rel, Path *new_path) +{ + parent_rel->pathlist = add_path_to(parent_rel, + parent_rel->pathlist, new_path); } /* @@ -915,6 +922,13 @@ add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, return true; } +void +add_unique_path(RelOptInfo *parent_rel, Path *new_path) +{ + parent_rel->unique_pathlist = add_path_to(parent_rel, + parent_rel->unique_pathlist, + new_path); +} /***************************************************************************** * PATH NODE CREATION ROUTINES @@ -940,6 +954,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +979,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1016,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1035,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1079,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1941,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1968,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1995,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2021,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2048,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2075,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2102,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..0de27f0ef3 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -657,6 +661,7 @@ typedef struct RelOptInfo List *pathlist; /* Path structures */ List *ppilist; /* ParamPathInfos used in pathlist */ List *partial_pathlist; /* partial Paths */ + List *unique_pathlist; /* unique Paths */ struct Path *cheapest_startup_path; struct Path *cheapest_total_path; struct Path *cheapest_unique_path; @@ -1077,6 +1082,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1120,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1146,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..fd25997af5 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -34,6 +34,7 @@ extern void add_partial_path(RelOptInfo *parent_rel, Path *new_path); extern bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys); +extern void add_unique_path(RelOptInfo *parent_rel, Path *new_path); extern Path *create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer, int parallel_workers); extern Path *create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, @@ -44,6 +45,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --qfje4fcsuvt2suqm Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v33-0002-Index-skip-scan.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v33 1/2] Unique key @ 2020-03-24 16:04 Dmitrii Dolgov <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: Dmitrii Dolgov @ 2020-03-24 16:04 UTC (permalink / raw) Design by David Rowley. Author: Jesper Pedersen --- src/backend/nodes/outfuncs.c | 14 +++ src/backend/nodes/print.c | 39 +++++++ src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/allpaths.c | 8 ++ src/backend/optimizer/path/indxpath.c | 41 ++++++++ src/backend/optimizer/path/pathkeys.c | 71 +++++++++++-- src/backend/optimizer/path/uniquekey.c | 136 +++++++++++++++++++++++++ src/backend/optimizer/plan/planagg.c | 1 + src/backend/optimizer/plan/planmain.c | 1 + src/backend/optimizer/plan/planner.c | 37 ++++++- src/backend/optimizer/util/pathnode.c | 46 +++++++-- src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 19 ++++ src/include/nodes/print.h | 1 + src/include/optimizer/pathnode.h | 2 + src/include/optimizer/paths.h | 11 ++ 16 files changed, 408 insertions(+), 23 deletions(-) create mode 100644 src/backend/optimizer/path/uniquekey.c diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index d76fae44b8..16083e7a7e 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -1723,6 +1723,7 @@ _outPathInfo(StringInfo str, const Path *node) WRITE_FLOAT_FIELD(startup_cost, "%.2f"); WRITE_FLOAT_FIELD(total_cost, "%.2f"); WRITE_NODE_FIELD(pathkeys); + WRITE_NODE_FIELD(uniquekeys); } /* @@ -2205,6 +2206,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(eq_classes); WRITE_BOOL_FIELD(ec_merging_done); WRITE_NODE_FIELD(canon_pathkeys); + WRITE_NODE_FIELD(canon_uniquekeys); WRITE_NODE_FIELD(left_join_clauses); WRITE_NODE_FIELD(right_join_clauses); WRITE_NODE_FIELD(full_join_clauses); @@ -2214,6 +2216,7 @@ _outPlannerInfo(StringInfo str, const PlannerInfo *node) WRITE_NODE_FIELD(placeholder_list); WRITE_NODE_FIELD(fkey_list); WRITE_NODE_FIELD(query_pathkeys); + WRITE_NODE_FIELD(query_uniquekeys); WRITE_NODE_FIELD(group_pathkeys); WRITE_NODE_FIELD(window_pathkeys); WRITE_NODE_FIELD(distinct_pathkeys); @@ -2401,6 +2404,14 @@ _outPathKey(StringInfo str, const PathKey *node) WRITE_BOOL_FIELD(pk_nulls_first); } +static void +_outUniqueKey(StringInfo str, const UniqueKey *node) +{ + WRITE_NODE_TYPE("UNIQUEKEY"); + + WRITE_NODE_FIELD(eq_clause); +} + static void _outPathTarget(StringInfo str, const PathTarget *node) { @@ -4092,6 +4103,9 @@ outNode(StringInfo str, const void *obj) case T_PathKey: _outPathKey(str, obj); break; + case T_UniqueKey: + _outUniqueKey(str, obj); + break; case T_PathTarget: _outPathTarget(str, obj); break; diff --git a/src/backend/nodes/print.c b/src/backend/nodes/print.c index 42476724d8..d286b34544 100644 --- a/src/backend/nodes/print.c +++ b/src/backend/nodes/print.c @@ -459,6 +459,45 @@ print_pathkeys(const List *pathkeys, const List *rtable) printf(")\n"); } +/* + * print_uniquekeys - + * uniquekeys list of UniqueKeys + */ +void +print_uniquekeys(const List *uniquekeys, const List *rtable) +{ + ListCell *l; + + printf("("); + foreach(l, uniquekeys) + { + UniqueKey *unique_key = (UniqueKey *) lfirst(l); + EquivalenceClass *eclass = (EquivalenceClass *) unique_key->eq_clause; + ListCell *k; + bool first = true; + + /* chase up */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + printf("("); + foreach(k, eclass->ec_members) + { + EquivalenceMember *mem = (EquivalenceMember *) lfirst(k); + + if (first) + first = false; + else + printf(", "); + print_expr((Node *) mem->em_expr, rtable); + } + printf(")"); + if (lnext(uniquekeys, l)) + printf(", "); + } + printf(")\n"); +} + /* * print_tl * print targetlist in a more legible way. diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..63cc1505d9 100644 --- a/src/backend/optimizer/path/Makefile +++ b/src/backend/optimizer/path/Makefile @@ -21,6 +21,7 @@ OBJS = \ joinpath.o \ joinrels.o \ pathkeys.o \ - tidpath.o + tidpath.o \ + uniquekey.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 8286d9cf34..bbc13e6141 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -3954,6 +3954,14 @@ print_path(PlannerInfo *root, Path *path, int indent) print_pathkeys(path->pathkeys, root->parse->rtable); } + if (path->uniquekeys) + { + for (i = 0; i < indent; i++) + printf("\t"); + printf(" uniquekeys: "); + print_uniquekeys(path->uniquekeys, root->parse->rtable); + } + if (join) { JoinPath *jp = (JoinPath *) path; diff --git a/src/backend/optimizer/path/indxpath.c b/src/backend/optimizer/path/indxpath.c index 2a50272da6..363f5349f1 100644 --- a/src/backend/optimizer/path/indxpath.c +++ b/src/backend/optimizer/path/indxpath.c @@ -189,6 +189,7 @@ static Expr *match_clause_to_ordering_op(IndexOptInfo *index, static bool ec_member_matches_indexcol(PlannerInfo *root, RelOptInfo *rel, EquivalenceClass *ec, EquivalenceMember *em, void *arg); +static List *get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys); /* @@ -874,6 +875,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, List *orderbyclausecols; List *index_pathkeys; List *useful_pathkeys; + List *useful_uniquekeys = NIL; bool found_lower_saop_clause; bool pathkeys_possibly_useful; bool index_is_ordered; @@ -1036,11 +1038,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, if (index_clauses != NIL || useful_pathkeys != NIL || useful_predicate || index_only_scan) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1063,6 +1069,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, orderbyclauses, orderbyclausecols, useful_pathkeys, + useful_uniquekeys, index_is_ordered ? ForwardScanDirection : NoMovementScanDirection, @@ -1093,11 +1100,15 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, index_pathkeys); if (useful_pathkeys != NIL) { + if (has_useful_uniquekeys(root)) + useful_uniquekeys = get_uniquekeys_for_index(root, useful_pathkeys); + ipath = create_index_path(root, index, index_clauses, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -1115,6 +1126,7 @@ build_index_paths(PlannerInfo *root, RelOptInfo *rel, NIL, NIL, useful_pathkeys, + useful_uniquekeys, BackwardScanDirection, index_only_scan, outer_relids, @@ -3365,6 +3377,35 @@ match_clause_to_ordering_op(IndexOptInfo *index, return clause; } +/* + * get_uniquekeys_for_index + */ +static List * +get_uniquekeys_for_index(PlannerInfo *root, List *pathkeys) +{ + ListCell *lc; + + if (pathkeys) + { + List *uniquekeys = NIL; + foreach(lc, pathkeys) + { + UniqueKey *unique_key; + PathKey *pk = (PathKey *) lfirst(lc); + EquivalenceClass *ec = (EquivalenceClass *) pk->pk_eclass; + + unique_key = makeNode(UniqueKey); + unique_key->eq_clause = ec; + + uniquekeys = lappend(uniquekeys, unique_key); + } + + if (uniquekeys_contained_in(root->canon_uniquekeys, uniquekeys)) + return uniquekeys; + } + + return NIL; +} /**************************************************************************** * ---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS ---- diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index 71b9d42c99..054df9a617 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -29,6 +29,7 @@ #include "utils/lsyscache.h" +static bool pathkey_is_unique(PathKey *new_pathkey, List *pathkeys); static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, @@ -96,6 +97,29 @@ make_canonical_pathkey(PlannerInfo *root, return pk; } +/* + * pathkey_is_unique + * Checks if the new pathkey's equivalence class is the same as that of + * any existing member of the pathkey list. + */ +static bool +pathkey_is_unique(PathKey *new_pathkey, List *pathkeys) +{ + EquivalenceClass *new_ec = new_pathkey->pk_eclass; + ListCell *lc; + + /* If same EC already is already in the list, then not unique */ + foreach(lc, pathkeys) + { + PathKey *old_pathkey = (PathKey *) lfirst(lc); + + if (new_ec == old_pathkey->pk_eclass) + return false; + } + + return true; +} + /* * pathkey_is_redundant * Is a pathkey redundant with one already in the given list? @@ -135,22 +159,12 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys) { EquivalenceClass *new_ec = new_pathkey->pk_eclass; - ListCell *lc; /* Check for EC containing a constant --- unconditionally redundant */ if (EC_MUST_BE_REDUNDANT(new_ec)) return true; - /* If same EC already used in list, then redundant */ - foreach(lc, pathkeys) - { - PathKey *old_pathkey = (PathKey *) lfirst(lc); - - if (new_ec == old_pathkey->pk_eclass) - return true; - } - - return false; + return !pathkey_is_unique(new_pathkey, pathkeys); } /* @@ -1098,6 +1112,41 @@ make_pathkeys_for_sortclauses(PlannerInfo *root, return pathkeys; } +/* + * make_pathkeys_for_uniquekeyclauses + * Generate a pathkeys list to be used for uniquekey clauses + */ +List * +make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist) +{ + List *pathkeys = NIL; + ListCell *l; + + foreach(l, sortclauses) + { + SortGroupClause *sortcl = (SortGroupClause *) lfirst(l); + Expr *sortkey; + PathKey *pathkey; + + sortkey = (Expr *) get_sortgroupclause_expr(sortcl, tlist); + Assert(OidIsValid(sortcl->sortop)); + pathkey = make_pathkey_from_sortop(root, + sortkey, + root->nullable_baserels, + sortcl->sortop, + sortcl->nulls_first, + sortcl->tleSortGroupRef, + true); + + if (pathkey_is_unique(pathkey, pathkeys)) + pathkeys = lappend(pathkeys, pathkey); + } + + return pathkeys; +} + /**************************************************************************** * PATHKEYS AND MERGECLAUSES ****************************************************************************/ diff --git a/src/backend/optimizer/path/uniquekey.c b/src/backend/optimizer/path/uniquekey.c new file mode 100644 index 0000000000..c421401d0f --- /dev/null +++ b/src/backend/optimizer/path/uniquekey.c @@ -0,0 +1,136 @@ +/*------------------------------------------------------------------------- + * + * uniquekey.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekey.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "nodes/pg_list.h" + +static UniqueKey *make_canonical_uniquekey(PlannerInfo *root, EquivalenceClass *eclass); + +/* + * Build a list of unique keys + */ +List* +build_uniquekeys(PlannerInfo *root, List *sortclauses) +{ + List *result = NIL; + List *sortkeys; + ListCell *l; + + sortkeys = make_pathkeys_for_uniquekeys(root, + sortclauses, + root->processed_tlist); + + /* Create a uniquekey and add it to the list */ + foreach(l, sortkeys) + { + PathKey *pathkey = (PathKey *) lfirst(l); + EquivalenceClass *ec = pathkey->pk_eclass; + UniqueKey *unique_key = make_canonical_uniquekey(root, ec); + + result = lappend(result, unique_key); + } + + return result; +} + +/* + * uniquekeys_contained_in + * Are the keys2 included in the keys1 superset + */ +bool +uniquekeys_contained_in(List *keys1, List *keys2) +{ + ListCell *key1, + *key2; + + foreach(key2, keys2) + { + bool found = false; + UniqueKey *uniquekey2 = (UniqueKey *) lfirst(key2); + + foreach(key1, keys1) + { + UniqueKey *uniquekey1 = (UniqueKey *) lfirst(key1); + + if (uniquekey1->eq_clause == uniquekey2->eq_clause) + return true; + } + + if (!found) + return false; + } + + return true; +} + +/* + * has_useful_uniquekeys + * Detect whether the planner could have any uniquekeys that are + * useful. + */ +bool +has_useful_uniquekeys(PlannerInfo *root) +{ + if (root->query_uniquekeys != NIL) + return true; /* there are some */ + return false; /* definitely useless */ +} + +/* + * make_canonical_uniquekey + * Given the parameters for a UniqueKey, find any pre-existing matching + * uniquekey in the query's list of "canonical" uniquekeys. Make a new + * entry if there's not one already. + * + * Note that this function must not be used until after we have completed + * merging EquivalenceClasses. (We don't try to enforce that here; instead, + * equivclass.c will complain if a merge occurs after root->canon_uniquekeys + * has become nonempty.) + */ +static UniqueKey * +make_canonical_uniquekey(PlannerInfo *root, + EquivalenceClass *eclass) +{ + UniqueKey *uk; + ListCell *lc; + MemoryContext oldcontext; + + /* The passed eclass might be non-canonical, so chase up to the top */ + while (eclass->ec_merged) + eclass = eclass->ec_merged; + + foreach(lc, root->canon_uniquekeys) + { + uk = (UniqueKey *) lfirst(lc); + if (eclass == uk->eq_clause) + return uk; + } + + /* + * Be sure canonical uniquekeys are allocated in the main planning context. + * Not an issue in normal planning, but it is for GEQO. + */ + oldcontext = MemoryContextSwitchTo(root->planner_cxt); + + uk = makeNode(UniqueKey); + uk->eq_clause = eclass; + + root->canon_uniquekeys = lappend(root->canon_uniquekeys, uk); + + MemoryContextSwitchTo(oldcontext); + + return uk; +} diff --git a/src/backend/optimizer/plan/planagg.c b/src/backend/optimizer/plan/planagg.c index 8634940efc..dd64775d8f 100644 --- a/src/backend/optimizer/plan/planagg.c +++ b/src/backend/optimizer/plan/planagg.c @@ -511,6 +511,7 @@ minmax_qp_callback(PlannerInfo *root, void *extra) root->parse->targetList); root->query_pathkeys = root->sort_pathkeys; + root->query_uniquekeys = NIL; } /* diff --git a/src/backend/optimizer/plan/planmain.c b/src/backend/optimizer/plan/planmain.c index 62dfc6d44a..3a372af91b 100644 --- a/src/backend/optimizer/plan/planmain.c +++ b/src/backend/optimizer/plan/planmain.c @@ -70,6 +70,7 @@ query_planner(PlannerInfo *root, root->join_rel_level = NULL; root->join_cur_level = 0; root->canon_pathkeys = NIL; + root->canon_uniquekeys = NIL; root->left_join_clauses = NIL; root->right_join_clauses = NIL; root->full_join_clauses = NIL; diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index d6f2153593..a7de8476d9 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -3657,15 +3657,30 @@ standard_qp_callback(PlannerInfo *root, void *extra) * much easier, since we know that the parser ensured that one is a * superset of the other. */ + root->query_uniquekeys = NIL; + if (root->group_pathkeys) + { root->query_pathkeys = root->group_pathkeys; + + if (!root->parse->hasAggs) + root->query_uniquekeys = build_uniquekeys(root, qp_extra->groupClause); + } else if (root->window_pathkeys) root->query_pathkeys = root->window_pathkeys; else if (list_length(root->distinct_pathkeys) > list_length(root->sort_pathkeys)) + { root->query_pathkeys = root->distinct_pathkeys; + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else if (root->sort_pathkeys) + { root->query_pathkeys = root->sort_pathkeys; + + if (root->distinct_pathkeys) + root->query_uniquekeys = build_uniquekeys(root, parse->distinctClause); + } else root->query_pathkeys = NIL; } @@ -6222,7 +6237,7 @@ plan_cluster_use_sort(Oid tableOid, Oid indexOid) /* Estimate the cost of index scan */ indexScanPath = create_index_path(root, indexInfo, - NIL, NIL, NIL, NIL, + NIL, NIL, NIL, NIL, NIL, ForwardScanDirection, false, NULL, 1.0, false); @@ -7107,6 +7122,26 @@ apply_scanjoin_target_to_paths(PlannerInfo *root, } } + foreach(lc, rel->unique_pathlist) + { + Path *subpath = (Path *) lfirst(lc); + + /* Shouldn't have any parameterized paths anymore */ + Assert(subpath->param_info == NULL); + + if (tlist_same_exprs) + subpath->pathtarget->sortgrouprefs = + scanjoin_target->sortgrouprefs; + else + { + Path *newpath; + + newpath = (Path *) create_projection_path(root, rel, subpath, + scanjoin_target); + lfirst(lc) = newpath; + } + } + /* * Now, if final scan/join target contains SRFs, insert ProjectSetPath(s) * atop each existing path. (Note that this function doesn't look at the diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c index e6d08aede5..a4dfafbb59 100644 --- a/src/backend/optimizer/util/pathnode.c +++ b/src/backend/optimizer/util/pathnode.c @@ -361,9 +361,9 @@ set_cheapest(RelOptInfo *parent_rel) } /* - * add_path + * add_path_to * Consider a potential implementation path for the specified parent rel, - * and add it to the rel's pathlist if it is worthy of consideration. + * and add it to the specified pathlist if it is worthy of consideration. * A path is worthy if it has a better sort order (better pathkeys) or * cheaper cost (on either dimension), or generates fewer rows, than any * existing path that has the same or superset parameterization rels. @@ -416,10 +416,10 @@ set_cheapest(RelOptInfo *parent_rel) * 'parent_rel' is the relation entry to which the path corresponds. * 'new_path' is a potential path for parent_rel. * - * Returns nothing, but modifies parent_rel->pathlist. + * Returns modified pathlist. */ -void -add_path(RelOptInfo *parent_rel, Path *new_path) +static List * +add_path_to(RelOptInfo *parent_rel, List *pathlist, Path *new_path) { bool accept_new = true; /* unless we find a superior old path */ int insert_at = 0; /* where to insert new item */ @@ -440,7 +440,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) * for more than one old path to be tossed out because new_path dominates * it. */ - foreach(p1, parent_rel->pathlist) + foreach(p1, pathlist) { Path *old_path = (Path *) lfirst(p1); bool remove_old = false; /* unless new proves superior */ @@ -584,8 +584,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) */ if (remove_old) { - parent_rel->pathlist = foreach_delete_current(parent_rel->pathlist, - p1); + pathlist = foreach_delete_current(pathlist, p1); /* * Delete the data pointed-to by the deleted cell, if possible @@ -612,8 +611,7 @@ add_path(RelOptInfo *parent_rel, Path *new_path) if (accept_new) { /* Accept the new path: insert it at proper place in pathlist */ - parent_rel->pathlist = - list_insert_nth(parent_rel->pathlist, insert_at, new_path); + pathlist = list_insert_nth(pathlist, insert_at, new_path); } else { @@ -621,6 +619,15 @@ add_path(RelOptInfo *parent_rel, Path *new_path) if (!IsA(new_path, IndexPath)) pfree(new_path); } + + return pathlist; +} + +void +add_path(RelOptInfo *parent_rel, Path *new_path) +{ + parent_rel->pathlist = add_path_to(parent_rel, + parent_rel->pathlist, new_path); } /* @@ -915,6 +922,13 @@ add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, return true; } +void +add_unique_path(RelOptInfo *parent_rel, Path *new_path) +{ + parent_rel->unique_pathlist = add_path_to(parent_rel, + parent_rel->unique_pathlist, + new_path); +} /***************************************************************************** * PATH NODE CREATION ROUTINES @@ -940,6 +954,7 @@ create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = parallel_workers; pathnode->pathkeys = NIL; /* seqscan has unordered result */ + pathnode->uniquekeys = NIL; cost_seqscan(pathnode, root, rel, pathnode->param_info); @@ -964,6 +979,7 @@ create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* samplescan has unordered result */ + pathnode->uniquekeys = NIL; cost_samplescan(pathnode, root, rel, pathnode->param_info); @@ -1000,6 +1016,7 @@ create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, @@ -1018,6 +1035,7 @@ create_index_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = 0; pathnode->path.pathkeys = pathkeys; + pathnode->path.uniquekeys = uniquekeys; pathnode->indexinfo = index; pathnode->indexclauses = indexclauses; @@ -1061,6 +1079,7 @@ create_bitmap_heap_path(PlannerInfo *root, pathnode->path.parallel_safe = rel->consider_parallel; pathnode->path.parallel_workers = parallel_degree; pathnode->path.pathkeys = NIL; /* always unordered */ + pathnode->path.uniquekeys = NIL; pathnode->bitmapqual = bitmapqual; @@ -1922,6 +1941,7 @@ create_functionscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = pathkeys; + pathnode->uniquekeys = NIL; cost_functionscan(pathnode, root, rel, pathnode->param_info); @@ -1948,6 +1968,7 @@ create_tablefuncscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_tablefuncscan(pathnode, root, rel, pathnode->param_info); @@ -1974,6 +1995,7 @@ create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_valuesscan(pathnode, root, rel, pathnode->param_info); @@ -1999,6 +2021,7 @@ create_ctescan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer) pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* XXX for now, result is always unordered */ + pathnode->uniquekeys = NIL; cost_ctescan(pathnode, root, rel, pathnode->param_info); @@ -2025,6 +2048,7 @@ create_namedtuplestorescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_namedtuplestorescan(pathnode, root, rel, pathnode->param_info); @@ -2051,6 +2075,7 @@ create_resultscan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; cost_resultscan(pathnode, root, rel, pathnode->param_info); @@ -2077,6 +2102,7 @@ create_worktablescan_path(PlannerInfo *root, RelOptInfo *rel, pathnode->parallel_safe = rel->consider_parallel; pathnode->parallel_workers = 0; pathnode->pathkeys = NIL; /* result is always unordered */ + pathnode->uniquekeys = NIL; /* Cost is the same as for a regular CTE scan */ cost_ctescan(pathnode, root, rel, pathnode->param_info); diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index baced7eec0..a1511b46ea 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -261,6 +261,7 @@ typedef enum NodeTag T_EquivalenceMember, T_PathKey, T_PathTarget, + T_UniqueKey, T_RestrictInfo, T_IndexClause, T_PlaceHolderVar, diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h index 3d3be197e0..0de27f0ef3 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -269,6 +269,8 @@ struct PlannerInfo List *canon_pathkeys; /* list of "canonical" PathKeys */ + List *canon_uniquekeys; /* list of "canonical" UniqueKeys */ + List *left_join_clauses; /* list of RestrictInfos for mergejoinable * outer join clauses w/nonnullable var on * left */ @@ -297,6 +299,8 @@ struct PlannerInfo List *query_pathkeys; /* desired pathkeys for query_planner() */ + List *query_uniquekeys; /* unique keys used for the query */ + List *group_pathkeys; /* groupClause pathkeys, if any */ List *window_pathkeys; /* pathkeys of bottom window, if any */ List *distinct_pathkeys; /* distinctClause pathkeys, if any */ @@ -657,6 +661,7 @@ typedef struct RelOptInfo List *pathlist; /* Path structures */ List *ppilist; /* ParamPathInfos used in pathlist */ List *partial_pathlist; /* partial Paths */ + List *unique_pathlist; /* unique Paths */ struct Path *cheapest_startup_path; struct Path *cheapest_total_path; struct Path *cheapest_unique_path; @@ -1077,6 +1082,15 @@ typedef struct ParamPathInfo List *ppi_clauses; /* join clauses available from outer rels */ } ParamPathInfo; +/* + * UniqueKey + */ +typedef struct UniqueKey +{ + NodeTag type; + + EquivalenceClass *eq_clause; /* equivalence class */ +} UniqueKey; /* * Type "Path" is used as-is for sequential-scan paths, as well as some other @@ -1106,6 +1120,9 @@ typedef struct ParamPathInfo * * "pathkeys" is a List of PathKey nodes (see above), describing the sort * ordering of the path's output rows. + * + * "uniquekeys", if not NIL, is a list of UniqueKey nodes (see above), + * describing the XXX. */ typedef struct Path { @@ -1129,6 +1146,8 @@ typedef struct Path List *pathkeys; /* sort ordering of path's output */ /* pathkeys is a List of PathKey nodes; see above */ + + List *uniquekeys; /* the unique keys, or NIL if none */ } Path; /* Macro for extracting a path's parameterization relids; beware double eval */ diff --git a/src/include/nodes/print.h b/src/include/nodes/print.h index 6126b491bf..006248bfb5 100644 --- a/src/include/nodes/print.h +++ b/src/include/nodes/print.h @@ -28,6 +28,7 @@ extern char *pretty_format_node_dump(const char *dump); extern void print_rt(const List *rtable); extern void print_expr(const Node *expr, const List *rtable); extern void print_pathkeys(const List *pathkeys, const List *rtable); +extern void print_uniquekeys(const List *uniquekeys, const List *rtable); extern void print_tl(const List *tlist, const List *rtable); extern void print_slot(TupleTableSlot *slot); diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h index e450fe112a..fd25997af5 100644 --- a/src/include/optimizer/pathnode.h +++ b/src/include/optimizer/pathnode.h @@ -34,6 +34,7 @@ extern void add_partial_path(RelOptInfo *parent_rel, Path *new_path); extern bool add_partial_path_precheck(RelOptInfo *parent_rel, Cost total_cost, List *pathkeys); +extern void add_unique_path(RelOptInfo *parent_rel, Path *new_path); extern Path *create_seqscan_path(PlannerInfo *root, RelOptInfo *rel, Relids required_outer, int parallel_workers); extern Path *create_samplescan_path(PlannerInfo *root, RelOptInfo *rel, @@ -44,6 +45,7 @@ extern IndexPath *create_index_path(PlannerInfo *root, List *indexorderbys, List *indexorderbycols, List *pathkeys, + List *uniquekeys, ScanDirection indexscandir, bool indexonly, Relids required_outer, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 9ab73bd20c..5b6be383b3 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -214,6 +214,9 @@ extern List *build_join_pathkeys(PlannerInfo *root, extern List *make_pathkeys_for_sortclauses(PlannerInfo *root, List *sortclauses, List *tlist); +extern List *make_pathkeys_for_uniquekeys(PlannerInfo *root, + List *sortclauses, + List *tlist); extern void initialize_mergeclause_eclasses(PlannerInfo *root, RestrictInfo *restrictinfo); extern void update_mergeclause_eclasses(PlannerInfo *root, @@ -240,4 +243,12 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekey.c + * Utilities for matching and building unique keys + */ +extern List *build_uniquekeys(PlannerInfo *root, List *sortclauses); +extern bool uniquekeys_contained_in(List *keys1, List *keys2); +extern bool has_useful_uniquekeys(PlannerInfo *root); + #endif /* PATHS_H */ -- 2.21.0 --t7fko7qta7zyrtxo Content-Type: text/x-diff; charset=us-ascii Content-Disposition: attachment; filename="v33-0002-Index-skip-scan-with-filtering.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
* [PATCH v3 2/7] Row pattern recognition patch (parse/analysis). @ 2023-07-26 10:49 Tatsuo Ishii <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: Tatsuo Ishii @ 2023-07-26 10:49 UTC (permalink / raw) --- src/backend/parser/parse_agg.c | 7 ++ src/backend/parser/parse_clause.c | 190 +++++++++++++++++++++++++++++- src/backend/parser/parse_expr.c | 4 + src/backend/parser/parse_func.c | 3 + 4 files changed, 203 insertions(+), 1 deletion(-) diff --git a/src/backend/parser/parse_agg.c b/src/backend/parser/parse_agg.c index 85cd47b7ae..aa7a1cee80 100644 --- a/src/backend/parser/parse_agg.c +++ b/src/backend/parser/parse_agg.c @@ -564,6 +564,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 @@ -953,6 +957,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 334b9b42bd..ea2decc579 100644 --- a/src/backend/parser/parse_clause.c +++ b/src/backend/parser/parse_clause.c @@ -100,7 +100,10 @@ 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); +static List *transformDefineClause(ParseState *pstate, WindowClause *wc, WindowDef *windef); +static void transformPatternClause(ParseState *pstate, WindowClause *wc, WindowDef *windef); +static List *transformMeasureClause(ParseState *pstate, WindowClause *wc, WindowDef *windef); /* * transformFromClause - @@ -2950,6 +2953,10 @@ transformWindowDefinitions(ParseState *pstate, rangeopfamily, rangeopcintype, &wc->endInRangeFunc, windef->endOffset); + + /* Process Row Pattern Recognition related clauses */ + transformRPR(pstate, wc, windef); + wc->runCondition = NIL; wc->winref = winref; @@ -3815,3 +3822,184 @@ transformFrameOffset(ParseState *pstate, int frameOptions, return node; } + +/* + * transformRPR + * Process Row Pattern Recognition related clauses + */ +static void +transformRPR(ParseState *pstate, WindowClause *wc, WindowDef *windef) +{ + /* Check Frame option. Frame must start at current row */ + + /* + * Window definition exists? + */ + if (windef == NULL) + return; + + /* + * Row Pattern Common Syntax clause exists? + */ + if (windef->rpCommonSyntax == NULL) + return; + + 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 SEEK or INITIAL clause */ + wc->initial = windef->rpCommonSyntax->initial; + + /* Transform DEFINE clause into list of TargetEntry's */ + wc->defineClause = transformDefineClause(pstate, wc, windef); + + /* 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) +{ + ListCell *lc; + ResTarget *restarget, *r; + List *restargets; + + + /* + * If Row Definition Common Syntax exists, DEFINE clause must exist. + * (the raw parser should have already checked it.) + */ + Assert(windef->rpCommonSyntax->rpDefs != NULL); + + /* + * 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) + { + char *name; + ListCell *l; + + restarget = (ResTarget *)lfirst(lc); + name = restarget->name; + + /* + * Make sure that 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); + + return transformTargetList(pstate, windef->rpCommonSyntax->rpDefs, + EXPR_KIND_RPR_DEFINE); +} + +/* + * transformPatternClause + * Process PATTERN clause and return PATTERN clause in the raw parse tree + */ +static void +transformPatternClause(ParseState *pstate, WindowClause *wc, WindowDef *windef) +{ + ListCell *lc, *l; + + /* + * Row Pattern Common Syntax clause exists? + */ + if (windef->rpCommonSyntax == NULL) + return; + + /* + * Primary row pattern variable names in PATTERN clause must appear in + * DEFINE clause as row pattern definition variable names. + */ + wc->patternVariable = NIL; + wc->patternRegexp = NIL; + foreach(lc, windef->rpCommonSyntax->rpPatterns) + { + A_Expr *a; + char *name; + char *regexp; + 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 = (ResTarget *)lfirst(l); + + if (!strcmp(restarget->name, name)) + { + found = true; + break; + } + } + + if (!found) + ereport(ERROR, + (errcode(ERRCODE_SYNTAX_ERROR), + errmsg("primary row pattern variable name \"%s\" does not appear in DEFINE clause", + name), + parser_errposition(pstate, exprLocation((Node *)a)))); + 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 + */ +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)))); +} diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c index fed8e4d089..8921b7ae01 100644 --- a/src/backend/parser/parse_expr.c +++ b/src/backend/parser/parse_expr.c @@ -557,6 +557,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; @@ -1770,6 +1771,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: @@ -3149,6 +3151,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 b3f0b6a137..2ff3699538 100644 --- a/src/backend/parser/parse_func.c +++ b/src/backend/parser/parse_func.c @@ -2656,6 +2656,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(Wed_Jul_26_21_21_34_2023_317)-- Content-Type: Text/X-Patch; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Disposition: inline; filename="v3-0003-Row-pattern-recognition-patch-planner.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
end of thread, other threads:[~2023-07-26 10:49 UTC | newest] Thread overview: 11+ messages (download: mbox mbox.gz follow: Atom feed) -- links below jump to the message on this page -- 2019-07-09 10:44 [PATCH v31 1/2] Unique key jesperpedersen <[email protected]> 2019-07-09 10:44 [PATCH v32 1/2] Unique key jesperpedersen <[email protected]> 2019-07-09 10:44 [PATCH v33 1/2] Unique key jesperpedersen <[email protected]> 2019-07-09 10:44 [PATCH] Unique key jesperpedersen <[email protected]> 2019-08-02 11:52 [PATCH 1/2] Unique key jesperpedersen <[email protected]> 2019-11-11 13:49 [PATCH 1/2] Unique key jesperpedersen <[email protected]> 2019-11-15 14:46 [PATCH 1/2] Unique key jesperpedersen <[email protected]> 2020-03-24 16:04 [PATCH v33 1/2] Unique key Dmitrii Dolgov <[email protected]> 2020-03-24 16:04 [PATCH v33 1/2] Unique key Dmitrii Dolgov <[email protected]> 2020-03-24 16:04 [PATCH v33 1/2] Unique key Dmitrii Dolgov <[email protected]> 2023-07-26 10:49 [PATCH v3 2/7] Row pattern recognition patch (parse/analysis). 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