agora inbox for [email protected]help / color / mirror / Atom feed
[PATCH v33 1/2] Unique key 11+ messages / 3 participants [nested] [flat]
* [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 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 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 v40 1/4] Refactor index_concurrently_create_copy() for use with REPACK (CONCURRENTLY). @ 2026-03-09 10:35 Antonin Houska <[email protected]> 0 siblings, 0 replies; 11+ messages in thread From: Antonin Houska @ 2026-03-09 10:35 UTC (permalink / raw) This patch moves the code to index_create_copy() and adds a "concurrently" parameter so it can be used by REPACK (CONCURRENTLY). With the CONCURRENTLY option, REPACK cannot simply swap the heap file and rebuild its indexes. Instead, it needs to build a separate set of indexes (including system catalog entries) *before* the actual swap, to reduce the time AccessExclusiveLock needs to be held for. --- src/backend/catalog/index.c | 54 +++++++++++++++++++++++--------- src/backend/commands/indexcmds.c | 6 ++-- src/backend/nodes/makefuncs.c | 9 +++--- src/include/catalog/index.h | 3 ++ src/include/nodes/makefuncs.h | 4 ++- 5 files changed, 54 insertions(+), 22 deletions(-) diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c index 5ee6389d39c..f8e6c3d804e 100644 --- a/src/backend/catalog/index.c +++ b/src/backend/catalog/index.c @@ -1288,15 +1288,32 @@ index_create(Relation heapRelation, /* * index_concurrently_create_copy * - * Create concurrently an index based on the definition of the one provided by - * caller. The index is inserted into catalogs and needs to be built later - * on. This is called during concurrent reindex processing. - * - * "tablespaceOid" is the tablespace to use for this index. + * Variant of index_create_copy(), called during concurrent reindex + * processing. */ Oid index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, Oid tablespaceOid, const char *newName) +{ + return index_create_copy(heapRelation, oldIndexId, tablespaceOid, newName, + true); +} + +/* + * index_create_copy + * + * Create an index based on the definition of the one provided by caller. The + * index is inserted into catalogs. If 'concurrently' is TRUE, it needs to be + * built later on, otherwise it's built immediately. + * + * "tablespaceOid" is the tablespace to use for this index. + * + * The actual implementation of index_concurrently_create_copy(), reusable for + * other purposes. + */ +Oid +index_create_copy(Relation heapRelation, Oid oldIndexId, Oid tablespaceOid, + const char *newName, bool concurrently) { Relation indexRelation; IndexInfo *oldInfo, @@ -1315,6 +1332,7 @@ index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, List *indexColNames = NIL; List *indexExprs = NIL; List *indexPreds = NIL; + int flags = 0; indexRelation = index_open(oldIndexId, RowExclusiveLock); @@ -1325,7 +1343,7 @@ index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, * Concurrent build of an index with exclusion constraints is not * supported. */ - if (oldInfo->ii_ExclusionOps != NULL) + if (oldInfo->ii_ExclusionOps != NULL && concurrently) ereport(ERROR, (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), errmsg("concurrent index creation for exclusion constraints is not supported"))); @@ -1381,9 +1399,7 @@ index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, } /* - * Build the index information for the new index. Note that rebuild of - * indexes with exclusion constraints is not supported, hence there is no - * need to fill all the ii_Exclusion* fields. + * Build the index information for the new index. */ newInfo = makeIndexInfo(oldInfo->ii_NumIndexAttrs, oldInfo->ii_NumIndexKeyAttrs, @@ -1392,10 +1408,13 @@ index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, indexPreds, oldInfo->ii_Unique, oldInfo->ii_NullsNotDistinct, - false, /* not ready for inserts */ - true, + !concurrently, /* isready */ + concurrently, /* concurrent */ indexRelation->rd_indam->amsummarizing, - oldInfo->ii_WithoutOverlaps); + oldInfo->ii_WithoutOverlaps, + oldInfo->ii_ExclusionOps, + oldInfo->ii_ExclusionProcs, + oldInfo->ii_ExclusionStrats); /* * Extract the list of column names and the column numbers for the new @@ -1433,6 +1452,9 @@ index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, stattargets[i].isnull = isnull; } + if (concurrently) + flags = INDEX_CREATE_SKIP_BUILD | INDEX_CREATE_CONCURRENT; + /* * Now create the new index. * @@ -1456,7 +1478,7 @@ index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, indcoloptions->values, stattargets, reloptionsDatum, - INDEX_CREATE_SKIP_BUILD | INDEX_CREATE_CONCURRENT, + flags, 0, true, /* allow table to be a system catalog? */ false, /* is_internal? */ @@ -2450,7 +2472,8 @@ BuildIndexInfo(Relation index) indexStruct->indisready, false, index->rd_indam->amsummarizing, - indexStruct->indisexclusion && indexStruct->indisunique); + indexStruct->indisexclusion && indexStruct->indisunique, + NULL, NULL, NULL); /* fill in attribute numbers */ for (i = 0; i < numAtts; i++) @@ -2510,7 +2533,8 @@ BuildDummyIndexInfo(Relation index) indexStruct->indisready, false, index->rd_indam->amsummarizing, - indexStruct->indisexclusion && indexStruct->indisunique); + indexStruct->indisexclusion && indexStruct->indisunique, + NULL, NULL, NULL); /* fill in attribute numbers */ for (i = 0; i < numAtts; i++) diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c index 635679cc1f2..34209bd1393 100644 --- a/src/backend/commands/indexcmds.c +++ b/src/backend/commands/indexcmds.c @@ -243,7 +243,8 @@ CheckIndexCompatible(Oid oldId, */ indexInfo = makeIndexInfo(numberOfAttributes, numberOfAttributes, accessMethodId, NIL, NIL, false, false, - false, false, amsummarizing, isWithoutOverlaps); + false, false, amsummarizing, isWithoutOverlaps, + NULL, NULL, NULL); typeIds = palloc_array(Oid, numberOfAttributes); collationIds = palloc_array(Oid, numberOfAttributes); opclassIds = palloc_array(Oid, numberOfAttributes); @@ -930,7 +931,8 @@ DefineIndex(ParseState *pstate, !concurrent, concurrent, amissummarizing, - stmt->iswithoutoverlaps); + stmt->iswithoutoverlaps, + NULL, NULL, NULL); typeIds = palloc_array(Oid, numberOfAttributes); collationIds = palloc_array(Oid, numberOfAttributes); diff --git a/src/backend/nodes/makefuncs.c b/src/backend/nodes/makefuncs.c index 2caec621d73..ca7e21e8349 100644 --- a/src/backend/nodes/makefuncs.c +++ b/src/backend/nodes/makefuncs.c @@ -834,7 +834,8 @@ IndexInfo * makeIndexInfo(int numattrs, int numkeyattrs, Oid amoid, List *expressions, List *predicates, bool unique, bool nulls_not_distinct, bool isready, bool concurrent, bool summarizing, - bool withoutoverlaps) + bool withoutoverlaps, Oid *exclusion_ops, Oid *exclusion_procs, + uint16 *exclusion_strats) { IndexInfo *n = makeNode(IndexInfo); @@ -863,9 +864,9 @@ makeIndexInfo(int numattrs, int numkeyattrs, Oid amoid, List *expressions, n->ii_PredicateState = NULL; /* exclusion constraints */ - n->ii_ExclusionOps = NULL; - n->ii_ExclusionProcs = NULL; - n->ii_ExclusionStrats = NULL; + n->ii_ExclusionOps = exclusion_ops; + n->ii_ExclusionProcs = exclusion_procs; + n->ii_ExclusionStrats = exclusion_strats; /* speculative inserts */ n->ii_UniqueOps = NULL; diff --git a/src/include/catalog/index.h b/src/include/catalog/index.h index b259c4141ed..3426087b445 100644 --- a/src/include/catalog/index.h +++ b/src/include/catalog/index.h @@ -99,6 +99,9 @@ extern Oid index_concurrently_create_copy(Relation heapRelation, Oid oldIndexId, Oid tablespaceOid, const char *newName); +extern Oid index_create_copy(Relation heapRelation, Oid oldIndexId, + Oid tablespaceOid, const char *newName, + bool concurrently); extern void index_concurrently_build(Oid heapRelationId, Oid indexRelationId); diff --git a/src/include/nodes/makefuncs.h b/src/include/nodes/makefuncs.h index 982ec25ae14..dcea148ae1a 100644 --- a/src/include/nodes/makefuncs.h +++ b/src/include/nodes/makefuncs.h @@ -99,7 +99,9 @@ extern IndexInfo *makeIndexInfo(int numattrs, int numkeyattrs, Oid amoid, List *expressions, List *predicates, bool unique, bool nulls_not_distinct, bool isready, bool concurrent, - bool summarizing, bool withoutoverlaps); + bool summarizing, bool withoutoverlaps, + Oid *exclusion_ops, Oid *exclusion_procs, + uint16 *exclusion_strats); extern Node *makeStringConst(char *str, int location); extern DefElem *makeDefElem(char *name, Node *arg, int location); -- 2.47.3 --k4rn5ob3nx2ufkij Content-Type: text/x-diff; charset=utf-8 Content-Disposition: attachment; filename="v40-0002-Add-CONCURRENTLY-option-to-REPACK-command.patch" ^ permalink raw reply [nested|flat] 11+ messages in thread
end of thread, other threads:[~2026-03-09 10:35 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 v33 1/2] Unique key jesperpedersen <[email protected]> 2019-07-09 10:44 [PATCH] Unique key jesperpedersen <[email protected]> 2019-07-09 10:44 [PATCH v32 1/2] 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]> 2026-03-09 10:35 [PATCH v40 1/4] Refactor index_concurrently_create_copy() for use with REPACK (CONCURRENTLY). Antonin Houska <[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