From db5f1f0d1749e5657297b846a77ba12d6b38fcd7 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?=E4=B8=80=E6=8C=83?= Date: Sun, 3 May 2020 22:51:57 +0800 Subject: [PATCH v35 2/6] Introuduce RelOptInfo.uniquekeys attribute --- src/backend/nodes/list.c | 31 + src/backend/nodes/makefuncs.c | 21 + src/backend/optimizer/path/Makefile | 3 +- src/backend/optimizer/path/README.uniquekey | 71 ++ src/backend/optimizer/path/allpaths.c | 7 + src/backend/optimizer/path/joinrels.c | 2 + src/backend/optimizer/path/pathkeys.c | 3 +- src/backend/optimizer/path/uniquekeys.c | 1135 +++++++++++++++++++ src/backend/optimizer/plan/planner.c | 10 +- src/backend/optimizer/prep/prepunion.c | 2 + src/include/nodes/makefuncs.h | 3 + src/include/nodes/nodes.h | 1 + src/include/nodes/pathnodes.h | 26 + src/include/nodes/pg_list.h | 2 + src/include/optimizer/optimizer.h | 2 + src/include/optimizer/paths.h | 35 + 16 files changed, 1349 insertions(+), 5 deletions(-) create mode 100644 src/backend/optimizer/path/README.uniquekey create mode 100644 src/backend/optimizer/path/uniquekeys.c diff --git a/src/backend/nodes/list.c b/src/backend/nodes/list.c index 80fa8c84e4..aa47eaed36 100644 --- a/src/backend/nodes/list.c +++ b/src/backend/nodes/list.c @@ -687,6 +687,37 @@ list_member_oid(const List *list, Oid datum) return false; } +/* + * Return true iff there is an equal member in target for every + * member in members + */ +bool +list_is_subset(const List *members, const List *target) +{ + const ListCell *lc1, *lc2; + + Assert(IsPointerList(members)); + Assert(IsPointerList(target)); + check_list_invariants(members); + check_list_invariants(target); + + foreach(lc1, members) + { + bool found = false; + foreach(lc2, target) + { + if (equal(lfirst(lc1), lfirst(lc2))) + { + found = true; + break; + } + } + if (!found) + return false; + } + return true; +} + /* * Delete the n'th cell (counting from 0) in list. * diff --git a/src/backend/nodes/makefuncs.c b/src/backend/nodes/makefuncs.c index b442b5a29e..3155e5c372 100644 --- a/src/backend/nodes/makefuncs.c +++ b/src/backend/nodes/makefuncs.c @@ -812,3 +812,24 @@ makeVacuumRelation(RangeVar *relation, Oid oid, List *va_cols) v->va_cols = va_cols; return v; } + + +/* + * makeUniqueKey + */ +UniqueKey* +makeUniqueKey(List *exprs, bool multi_nullvals, bool onerow) +{ + UniqueKey * ukey = makeNode(UniqueKey); + if (onerow) + { + Assert(exprs == NIL); + Assert(!multi_nullvals); + } + else + Assert(exprs != NIL); + ukey->exprs = exprs; + ukey->multi_nullvals = multi_nullvals; + ukey->onerow = onerow; + return ukey; +} diff --git a/src/backend/optimizer/path/Makefile b/src/backend/optimizer/path/Makefile index 1e199ff66f..7b9820c25f 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 \ + uniquekeys.o include $(top_srcdir)/src/backend/common.mk diff --git a/src/backend/optimizer/path/README.uniquekey b/src/backend/optimizer/path/README.uniquekey new file mode 100644 index 0000000000..dc0d6490f2 --- /dev/null +++ b/src/backend/optimizer/path/README.uniquekey @@ -0,0 +1,71 @@ +1. What is UniqueKey? +We can think UniqueKey is a set of exprs for a RelOptInfo, which we are insure +that doesn't yields same result among all the rows. The simplest UniqueKey +format is primary key. + +However we define the UnqiueKey as below. + +typedef struct UniqueKey +{ + NodeTag type; + List *exprs; + bool multi_nullvals; + bool onerow; +} UniqueKey; + +mutli_nuvals is used to track if the exprs allows multi nullvals. For a unique +index without its column marked as not null, it allows mulit_nullvals. + +onerow is also a kind of UniqueKey which means the RelOptInfo will have 1 row at +most. it has a stronger semantic than others. like SELECT uk FROM t; uk is +normal unique key and may have different values. +SELECT colx FROM t WHERE uk = const. colx is unique AND we have only 1 value. This +field can used for innerrel_is_unique. and also be used as an optimization for +this case. We don't need to maintain multi UniqueKey, we just maintain one with +onerow = true and exprs = NIL. + +onerow is set to true only for 2 cases right now. 1) SELECT .. FROM t WHERE uk = +1; 2). SELECT aggref(xx) from t; // Without group by. + +The UniqueKey can be used at the following cases at least: +1. remove_useless_joins. +2. reduce_semianti_joins +3. remove distinct node if distinct clause is unique. +4. remove aggnode if group by clause is unique. +5. Aggregation Push Down without 2 phase aggregation if the join can't + duplicated the aggregated rows. (work in progress feature) + + +2. How is it maintained? + +We have a set of populate_xxx_unqiuekeys functions to maintain the uniquekey on +various cases. xxx includes baserel, joinrel, partitionedrel, distinctrel, +groupedrel, unionrel. and we also need to convert the uniquekey from subquery +to outer relation, which is what convert_subquery_uniquekeys does. + +The most error-prone part is joinrel, we simplified the rules like below: +1. If the relation's UniqueKey can't be duplicated after join, then is will be + still valid for the join rel. The function we used here is + innerrel_keeps_unique. The basic idea is innerrel.any_col = outer.uk. + +2. If the UnqiueKey can't keep valid via the rule 1, the combination of the + UniqueKey from both sides are valid for sure. We can prove this as: if the + unique exprs from rel1 is duplicated by rel2, the duplicated rows must + contains different unique exprs from rel2. + + +More considerations about onerow: +1. If relation with one row and it can't be duplicated, it is still possible + contains mulit_nullvas after outer join. +2. If the either UniqueKey can be duplicated after join, the can get one row + only when both side is one row AND there is no outer join. +3. Whenever the onerow UniqueKey is not a valid any more, we need to convert one + row UniqueKey to normal unique key since we don't store exprs for one-row + relation. get_exprs_from_uniquekeys will be used here. + + +More considerations about multi_nullvals after join: +1. If the original UnqiueKey has multi_nullvals, the final UniqueKey will have + mulit_nullvals in any case. +2. If a unique key doesn't allow mulit_nullvals, after some outer join, it + allows some outer join. diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index d984da25d7..c3d21f0520 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -786,6 +786,9 @@ set_plain_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* Consider TID scans */ create_tidscan_paths(root, rel); + + /* Set UniqueKeys for this relation */ + populate_baserel_uniquekeys(root, rel, rel->indexlist); } /* @@ -1276,6 +1279,8 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, /* Add paths to the append relation. */ add_paths_to_append_rel(root, rel, live_childrels); + if (IS_PARTITIONED_REL(rel)) + populate_partitionedrel_uniquekeys(root, rel, live_childrels); } @@ -2349,6 +2354,8 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, pathkeys, required_outer)); } + convert_subquery_uniquekeys(root, rel, sub_final_rel); + /* If outer rel allows parallelism, do same for partial paths. */ if (rel->consider_parallel && bms_is_empty(required_outer)) { diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 2d343cd293..b9163ee8ff 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -924,6 +924,8 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, /* Apply partitionwise join technique, if possible. */ try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist); + + populate_joinrel_uniquekeys(root, joinrel, rel1, rel2, restrictlist, sjinfo->jointype); } diff --git a/src/backend/optimizer/path/pathkeys.c b/src/backend/optimizer/path/pathkeys.c index ce9bf87e9b..7e596d4194 100644 --- a/src/backend/optimizer/path/pathkeys.c +++ b/src/backend/optimizer/path/pathkeys.c @@ -33,7 +33,6 @@ static bool pathkey_is_redundant(PathKey *new_pathkey, List *pathkeys); static bool matches_boolean_partition_clause(RestrictInfo *rinfo, RelOptInfo *partrel, int partkeycol); -static Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle); static bool right_merge_direction(PlannerInfo *root, PathKey *pathkey); @@ -1035,7 +1034,7 @@ convert_subquery_pathkeys(PlannerInfo *root, RelOptInfo *rel, * We need this to ensure that we don't return pathkeys describing values * that are unavailable above the level of the subquery scan. */ -static Var * +Var * find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle) { ListCell *lc; diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.c new file mode 100644 index 0000000000..957af61819 --- /dev/null +++ b/src/backend/optimizer/path/uniquekeys.c @@ -0,0 +1,1135 @@ +/*------------------------------------------------------------------------- + * + * uniquekeys.c + * Utilities for matching and building unique keys + * + * Portions Copyright (c) 2020, PostgreSQL Global Development Group + * + * IDENTIFICATION + * src/backend/optimizer/path/uniquekeys.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "nodes/makefuncs.h" +#include "nodes/nodeFuncs.h" +#include "optimizer/pathnode.h" +#include "optimizer/paths.h" +#include "optimizer/optimizer.h" +#include "optimizer/tlist.h" +#include "rewrite/rewriteManip.h" + + +static List *gather_mergeable_baserestrictlist(RelOptInfo *rel); +static List *gather_mergeable_joinclauses(RelOptInfo *joinrel, + RelOptInfo *rel1, + RelOptInfo *rel2, + List *restirctlist, + JoinType jointype); +static bool match_index_to_baserestrictinfo(IndexOptInfo *unique_ind, + List *restrictlist); + +/* + * This struct is used to help populate_joinrel_uniquekeys. + * + * added_to_joinrel is true if a uniquekey (from outerrel or innerrel) + * has been added to joinrel. + * useful is true if the exprs of the uniquekey still appears in joinrel. + */ +typedef struct UniqueKeyContextData +{ + UniqueKey *uniquekey; + bool added_to_joinrel; + bool useful; +} *UniqueKeyContext; + +static List *initililze_uniquecontext_for_joinrel(RelOptInfo *inputrel); +static bool innerrel_keeps_unique(PlannerInfo *root, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist, + bool reverse); +static List *get_exprs_from_uniquekey(RelOptInfo *joinrel, + RelOptInfo *rel1, + UniqueKey *ukey); +static bool clause_sides_match_join(RestrictInfo *rinfo, + Relids outerrelids, + Relids innerrelids); +static void add_uniquekey_from_index(RelOptInfo *rel, + IndexOptInfo *unique_index); +static void add_uniquekey_for_onerow(RelOptInfo *rel); +static bool add_combined_uniquekey(RelOptInfo *joinrel, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + UniqueKey *outer_ukey, + UniqueKey *inner_ukey, + JoinType jointype); + +/* Used for unique indexes checking for partitioned table */ +static bool index_constains_partkey(RelOptInfo *partrel, IndexOptInfo *ind); +static IndexOptInfo *simple_copy_indexinfo_to_parent(RelOptInfo *parentrel, + IndexOptInfo *from); +static bool simple_indexinfo_equal(IndexOptInfo *ind1, IndexOptInfo *ind2); +static void adjust_partition_unique_indexlist(RelOptInfo *parentrel, + RelOptInfo *childrel, + List **global_unique_index); + +/* Helper function for grouped relation and distinct relation. */ +static void add_uniquekey_from_sortgroups(PlannerInfo *root, + RelOptInfo *rel, + List *sortgroups); + +/* + * populate_baserel_uniquekeys + * Populate 'baserel' uniquekeys list by looking at the rel's unique index + * add baserestrictinfo + */ +void +populate_baserel_uniquekeys(PlannerInfo *root, + RelOptInfo *baserel, + List *indexlist) +{ + ListCell *lc; + List *restrictlist; + bool return_one_row = false; + List *matched_uniq_indexes = NIL; + + Assert(baserel->rtekind == RTE_RELATION); + + if (root->parse->hasTargetSRFs) + return; + + if (baserel->reloptkind == RELOPT_OTHER_MEMBER_REL) + /* + * Set UniqueKey on member rel is useless, we have to recompute it at + * upper level, see populate_partitionedrel_uniquekeys for reference + */ + return; + + restrictlist = gather_mergeable_baserestrictlist(baserel); + + foreach(lc, indexlist) + { + IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc); + if (!ind->unique || !ind->immediate || + (ind->indpred != NIL && !ind->predOK)) + continue; + + if (match_index_to_baserestrictinfo(ind, restrictlist)) + { + return_one_row = true; + break; + } + + if (ind->indexprs != NIL) + /* XXX: ignore index on expression so far */ + continue; + matched_uniq_indexes = lappend(matched_uniq_indexes, ind); + } + + if (return_one_row) + { + add_uniquekey_for_onerow(baserel); + } + else + { + foreach(lc, matched_uniq_indexes) + add_uniquekey_from_index(baserel, lfirst_node(IndexOptInfo, lc)); + } +} + + +/* + * populate_partitioned_rel_uniquekeys + * The unique index can only be used for UniqueKey based on: + * 1). It must include partition key. + * 2). It exists in all the related. partitions. + */ +void +populate_partitionedrel_uniquekeys(PlannerInfo *root, + RelOptInfo *rel, + List *childrels) +{ + ListCell *lc; + List *global_uniq_indexlist = NIL; + RelOptInfo *childrel; + bool is_first = true; + + Assert(IS_PARTITIONED_REL(rel)); + + if (root->parse->hasTargetSRFs) + return; + + if (childrels == NIL) + return; + + childrel = linitial_node(RelOptInfo, childrels); + foreach(lc, childrel->indexlist) + { + IndexOptInfo *ind = lfirst(lc); + IndexOptInfo *modified_index; + if (!ind->unique || !ind->immediate || + (ind->indpred != NIL && !ind->predOK)) + continue; + + modified_index = simple_copy_indexinfo_to_parent(rel, ind); + /* + * If the unique index doesn't contain partkey, then it is unique + * on this partition only, so it is useless for us. + */ + if (!index_constains_partkey(rel, modified_index)) + continue; + global_uniq_indexlist = lappend(global_uniq_indexlist, modified_index); + } + + /* Fast path */ + if (global_uniq_indexlist == NIL) + return; + + foreach(lc, childrels) + { + RelOptInfo *child = lfirst(lc); + if (is_first) + { + is_first = false; + continue; + } + adjust_partition_unique_indexlist(rel, child, &global_uniq_indexlist); + } + + /* Now we have a list of unique index which are exactly same on all childrels, + * Set the UniqueKey just like it is non-partition table + */ + populate_baserel_uniquekeys(root, rel, global_uniq_indexlist); +} + + +/* + * populate_distinctrel_uniquekeys + */ +void +populate_distinctrel_uniquekeys(PlannerInfo *root, + RelOptInfo *inputrel, + RelOptInfo *distinctrel) +{ + /* The unique key before the distinct is still valid. */ + distinctrel->uniquekeys = list_copy(inputrel->uniquekeys); + add_uniquekey_from_sortgroups(root, distinctrel, root->parse->distinctClause); +} + +/* + * populate_grouprel_uniquekeys + */ +void +populate_grouprel_uniquekeys(PlannerInfo *root, + RelOptInfo *grouprel) +{ + Query *parse = root->parse; + + if (parse->hasTargetSRFs) + return; + + if (parse->groupingSets) + return; + + /* A Normal group by without grouping set. */ + if (parse->groupClause) + add_uniquekey_from_sortgroups(root, + grouprel, + root->parse->groupClause); + else + /* It has aggregation but without a group by, so only one row returned */ + add_uniquekey_for_onerow(grouprel); +} + +/* + * simple_copy_uniquekeys + * Using a function for the one-line code makes us easy to check where we simply + * copied the uniquekey. + */ +void +simple_copy_uniquekeys(RelOptInfo *oldrel, + RelOptInfo *newrel) +{ + newrel->uniquekeys = oldrel->uniquekeys; +} + +/* + * populate_unionrel_uniquekeys + */ +void +populate_unionrel_uniquekeys(PlannerInfo *root, + RelOptInfo *unionrel) +{ + ListCell *lc; + List *exprs = NIL; + + Assert(unionrel->uniquekeys == NIL); + + foreach(lc, unionrel->reltarget->exprs) + { + exprs = lappend(exprs, lfirst(lc)); + } + + if (exprs == NIL) + /* SQL: select union select; is valid, we need to handle it here. */ + return; + unionrel->uniquekeys = lappend(unionrel->uniquekeys, + makeUniqueKey(exprs, + false, /* allows_multinull */ + false /* onerow */)); +} + +/* + * populate_joinrel_uniquekeys + * + * populate uniquekeys for joinrel. We will check each relation to see if it's + * UniqueKey is still valid via innerrel_keeps_unique, if so, we add it to + * joinrel. The multi_nullvals field will be changed from false to true + * for some outer join cases and one-row UniqueKey needs to be converted to nomarl + * UniqueKey for the same case as well. + + * For the uniquekey in either baserel which can't be unique after join, we still + * check to see if combination of UniqueKeys from both side is still useful for us. + * if yes, we add it to joinrel as well. + */ +void +populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel, + RelOptInfo *outerrel, RelOptInfo *innerrel, + List *restrictlist, JoinType jointype) +{ + ListCell *lc, *lc2; + List *clause_list = NIL; + List *outerrel_ukey_ctx; + List *innerrel_ukey_ctx; + bool inner_onerow, outer_onerow; + + if (root->parse->hasTargetSRFs) + return; + + /* Care about the outerrel relation only for SEMI/ANTI join */ + if (jointype == JOIN_SEMI || jointype == JOIN_ANTI) + { + foreach(lc, outerrel->uniquekeys) + { + UniqueKey *uniquekey = lfirst_node(UniqueKey, lc); + if (list_is_subset(uniquekey->exprs, joinrel->reltarget->exprs)) + joinrel->uniquekeys = lappend(joinrel->uniquekeys, uniquekey); + } + return; + } + + Assert(jointype == JOIN_LEFT || jointype == JOIN_FULL || jointype == JOIN_INNER); + + /* Fast path */ + if (innerrel->uniquekeys == NIL || outerrel->uniquekeys == NIL) + return; + + inner_onerow = relation_is_onerow(innerrel); + outer_onerow = relation_is_onerow(outerrel); + + outerrel_ukey_ctx = initililze_uniquecontext_for_joinrel(outerrel); + innerrel_ukey_ctx = initililze_uniquecontext_for_joinrel(innerrel); + + clause_list = gather_mergeable_joinclauses(joinrel, outerrel, innerrel, + restrictlist, jointype); + + if (innerrel_keeps_unique(root, innerrel, outerrel, clause_list, true /* reverse */)) + { + foreach(lc, outerrel_ukey_ctx) + { + UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc); + + if (!list_is_subset(ctx->uniquekey->exprs, joinrel->reltarget->exprs)) + { + ctx->useful = false; + continue; + } + + /* Outer relation has one row, and the unique key is not duplicated after join, + * the joinrel will still has one row unless the jointype == JOIN_FULL. + */ + if (outer_onerow && jointype != JOIN_FULL) + { + add_uniquekey_for_onerow(joinrel); + return; + } + else if (outer_onerow) + { + /* Full join case, the onerow becomes multi rows and multi_nullvals changes + * to true. We also need to set the exprs correctly since it is not one-row + * any more. + */ + ListCell *lc2; + foreach(lc2, get_exprs_from_uniquekey(joinrel, outerrel, NULL)) + { + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + makeUniqueKey(lfirst(lc2), + true, /* multi_nullvals */ + false /* onerow */)); + } + } + else + { + if (!ctx->uniquekey->multi_nullvals && jointype == JOIN_FULL) + /* Change multi_nullvals to true due to the full join. */ + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + makeUniqueKey(ctx->uniquekey->exprs, + true, + ctx->uniquekey->onerow)); + else + /* Just reuse it */ + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + ctx->uniquekey); + } + ctx->added_to_joinrel = true; + } + } + + if (innerrel_keeps_unique(root, outerrel, innerrel, clause_list, false)) + { + foreach(lc, innerrel_ukey_ctx) + { + UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc); + + if (!list_is_subset(ctx->uniquekey->exprs, joinrel->reltarget->exprs)) + { + ctx->useful = false; + continue; + } + + /* + * Inner relation has one row, and the unique key is not duplicated after join, + * the joinrel will still has one row unless the jointype not in + * (JOIN_FULL, JOIN_LEFT) + */ + if (inner_onerow && jointype != JOIN_FULL && jointype != JOIN_LEFT) + { + add_uniquekey_for_onerow(joinrel); + return; + } + else if (inner_onerow) + { + /* Full join or left outer join case, the inner one row becomes to multi rows + * and multi_nullvals becomes to true. We also need to set the exprs correctly + * since it is not one-row any more. + */ + ListCell *lc2; + foreach(lc2, get_exprs_from_uniquekey(joinrel, innerrel, NULL)) + { + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + makeUniqueKey(lfirst(lc2), + true, /* multi_nullvals */ + false /* onerow */)); + } + } + else + { + if (!ctx->uniquekey->multi_nullvals && + (jointype == JOIN_FULL || jointype == JOIN_LEFT)) + /* Need to change multi_nullvals to true due to the outer join. */ + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + makeUniqueKey(ctx->uniquekey->exprs, + true, + ctx->uniquekey->onerow)); + else + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + ctx->uniquekey); + + } + ctx->added_to_joinrel = true; + } + } + + /* The combination of the UniqueKey from both sides is unique as well regardless + * of join type, but no bother to add it if its subset has been added to joinrel + * already or it is not useful for the joinrel. + */ + foreach(lc, outerrel_ukey_ctx) + { + UniqueKeyContext ctx1 = (UniqueKeyContext) lfirst(lc); + if (ctx1->added_to_joinrel || !ctx1->useful) + continue; + foreach(lc2, innerrel_ukey_ctx) + { + UniqueKeyContext ctx2 = (UniqueKeyContext) lfirst(lc2); + if (ctx2->added_to_joinrel || !ctx2->useful) + continue; + if (add_combined_uniquekey(joinrel, outerrel, innerrel, + ctx1->uniquekey, ctx2->uniquekey, + jointype)) + /* If we set a onerow UniqueKey to joinrel, we don't need other. */ + return; + } + } +} + + +/* + * convert_subquery_uniquekeys + * + * Covert the UniqueKey in subquery to outer relation. + */ +void convert_subquery_uniquekeys(PlannerInfo *root, + RelOptInfo *currel, + RelOptInfo *sub_final_rel) +{ + ListCell *lc; + + if (sub_final_rel->uniquekeys == NIL) + return; + + if (relation_is_onerow(sub_final_rel)) + { + add_uniquekey_for_onerow(currel); + return; + } + + Assert(currel->subroot != NULL); + + foreach(lc, sub_final_rel->uniquekeys) + { + UniqueKey *ukey = lfirst_node(UniqueKey, lc); + ListCell *lc; + List *exprs = NIL; + bool ukey_useful = true; + + /* One row case is handled above */ + Assert(ukey->exprs != NIL); + foreach(lc, ukey->exprs) + { + Var *var; + TargetEntry *tle = tlist_member(lfirst(lc), + currel->subroot->processed_tlist); + if (tle == NULL) + { + ukey_useful = false; + break; + } + var = find_var_for_subquery_tle(currel, tle); + if (var == NULL) + { + ukey_useful = false; + break; + } + exprs = lappend(exprs, var); + } + + if (ukey_useful) + currel->uniquekeys = lappend(currel->uniquekeys, + makeUniqueKey(exprs, + ukey->multi_nullvals, + ukey->onerow)); + } +} + +/* + * innerrel_keeps_unique + * + * Check if Unique key of the innerrel is valid after join. innerrel's UniqueKey + * will be still valid if innerrel's any-column mergeop outrerel's uniquekey + * exists in clause_list. + * + * Note: the clause_list must be a list of mergeable restrictinfo already. + */ +static bool +innerrel_keeps_unique(PlannerInfo *root, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *clause_list, + bool reverse) +{ + ListCell *lc, *lc2, *lc3; + + if (outerrel->uniquekeys == NIL || innerrel->uniquekeys == NIL) + return false; + + /* Check if there is outerrel's uniquekey in mergeable clause. */ + foreach(lc, outerrel->uniquekeys) + { + List *outer_uq_exprs = lfirst_node(UniqueKey, lc)->exprs; + bool clauselist_matchs_all_exprs = true; + foreach(lc2, outer_uq_exprs) + { + Node *outer_uq_expr = lfirst(lc2); + bool find_uq_expr_in_clauselist = false; + foreach(lc3, clause_list) + { + RestrictInfo *rinfo = lfirst_node(RestrictInfo, lc3); + Node *outer_expr; + if (reverse) + outer_expr = rinfo->outer_is_left ? get_rightop(rinfo->clause) : get_leftop(rinfo->clause); + else + outer_expr = rinfo->outer_is_left ? get_leftop(rinfo->clause) : get_rightop(rinfo->clause); + if (equal(outer_expr, outer_uq_expr)) + { + find_uq_expr_in_clauselist = true; + break; + } + } + if (!find_uq_expr_in_clauselist) + { + /* No need to check the next exprs in the current uniquekey */ + clauselist_matchs_all_exprs = false; + break; + } + } + + if (clauselist_matchs_all_exprs) + return true; + } + return false; +} + + +/* + * relation_is_onerow + * Check if it is a one-row relation by checking UniqueKey. + */ +bool +relation_is_onerow(RelOptInfo *rel) +{ + UniqueKey *ukey; + if (rel->uniquekeys == NIL) + return false; + ukey = linitial_node(UniqueKey, rel->uniquekeys); + if (ukey->onerow) + { + /* Some helpful tiny check for UniqueKey. */ + + /* 1. We will only store one UniqueKey for this rel. */ + Assert(list_length(rel->uniquekeys) == 1); + /* 2. multi_nullvals must be false. */ + Assert(!ukey->multi_nullvals); + /* 3. exprs must be NIL. */ + Assert(ukey->exprs == NIL); + + } + return ukey->onerow; +} + +/* + * relation_has_uniquekeys_for + * Returns true if we have proofs that 'rel' cannot return multiple rows with + * the same values in each of 'exprs'. Otherwise returns false. + */ +bool +relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel, + List *exprs, bool allow_multinulls) +{ + ListCell *lc; + + /* For UniqueKey->onerow case, the uniquekey->exprs is empty as well + * so we can't rely on list_is_subset to handle this special cases + */ + if (exprs == NIL) + return false; + + foreach(lc, rel->uniquekeys) + { + UniqueKey *ukey = lfirst_node(UniqueKey, lc); + if (ukey->multi_nullvals && !allow_multinulls) + continue; + if (list_is_subset(ukey->exprs, exprs)) + return true; + } + return false; +} + + +/* + * Examine the rel's restriction clauses for usable var = const clauses + */ +static List* +gather_mergeable_baserestrictlist(RelOptInfo *rel) +{ + List *restrictlist = NIL; + ListCell *lc; + foreach(lc, rel->baserestrictinfo) + { + RestrictInfo *restrictinfo = (RestrictInfo *) lfirst(lc); + + /* + * Note: can_join won't be set for a restriction clause, but + * mergeopfamilies will be if it has a mergejoinable operator and + * doesn't contain volatile functions. + */ + if (restrictinfo->mergeopfamilies == NIL) + continue; /* not mergejoinable */ + + /* + * The clause certainly doesn't refer to anything but the given rel. + * If either side is pseudoconstant then we can use it. + */ + if (bms_is_empty(restrictinfo->left_relids)) + { + /* righthand side is inner */ + restrictinfo->outer_is_left = true; + } + else if (bms_is_empty(restrictinfo->right_relids)) + { + /* lefthand side is inner */ + restrictinfo->outer_is_left = false; + } + else + continue; + + /* OK, add to list */ + restrictlist = lappend(restrictlist, restrictinfo); + } + return restrictlist; +} + + +/* + * gather_mergeable_joinclauses + */ +static List* +gather_mergeable_joinclauses(RelOptInfo *joinrel, + RelOptInfo *outerrel, + RelOptInfo *innerrel, + List *restrictlist, + JoinType jointype) +{ + List *clause_list = NIL; + ListCell *lc; + foreach(lc, restrictlist) + { + RestrictInfo *restrictinfo = (RestrictInfo *)lfirst(lc); + if (IS_OUTER_JOIN(jointype) && + RINFO_IS_PUSHED_DOWN(restrictinfo, joinrel->relids)) + continue; + + /* Ignore if it's not a mergejoinable clause */ + if (!restrictinfo->can_join || + restrictinfo->mergeopfamilies == NIL) + continue; /* not mergejoinable */ + + /* + * Check if clause has the form "outer op inner" or "inner op outer", + * and if so mark which side is inner. + */ + if (!clause_sides_match_join(restrictinfo, outerrel->relids, innerrel->relids)) + continue; /* no good for these input relations. */ + + /* OK, add to list */ + clause_list = lappend(clause_list, restrictinfo); + } + return clause_list; +} + + +/* + * Return true if uk = Const in the restrictlist + */ +static bool +match_index_to_baserestrictinfo(IndexOptInfo *unique_ind, List *restrictlist) +{ + int c = 0; + + /* A fast path to avoid the 2 loop scan. */ + if (list_length(restrictlist) < unique_ind->ncolumns) + return false; + + for(c = 0; c < unique_ind->ncolumns; c++) + { + ListCell *lc; + bool found_in_restrictinfo = false; + foreach(lc, restrictlist) + { + RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); + Node *rexpr; + + /* + * The condition's equality operator must be a member of the + * index opfamily, else it is not asserting the right kind of + * equality behavior for this index. We check this first + * since it's probably cheaper than match_index_to_operand(). + */ + if (!list_member_oid(rinfo->mergeopfamilies, unique_ind->opfamily[c])) + continue; + + /* + * XXX at some point we may need to check collations here too. + * For the moment we assume all collations reduce to the same + * notion of equality. + */ + + /* OK, see if the condition operand matches the index key */ + if (rinfo->outer_is_left) + rexpr = get_rightop(rinfo->clause); + else + rexpr = get_leftop(rinfo->clause); + + if (match_index_to_operand(rexpr, c, unique_ind)) + { + found_in_restrictinfo = true; + break; + } + } + if (!found_in_restrictinfo) + return false; + } + return true; +} + +/* + * add_uniquekey_from_index + * We only add the Index Vars whose expr exists in rel->reltarget + */ +static void +add_uniquekey_from_index(RelOptInfo *rel, IndexOptInfo *unique_index) +{ + int pos; + List *exprs = NIL; + bool multi_nullvals = false; + + /* Fast path. + * Check if the indexed columns are used in this relation, if not return fast. + */ + for(pos = 0; pos < unique_index->ncolumns; pos++) + { + int attno = unique_index->indexkeys[pos]; + if (bms_is_empty(rel->attr_needed[attno - rel->min_attr])) + /* The indexed column is not needed in this relation. */ + return; + if (!bms_is_member(attno - FirstLowInvalidHeapAttributeNumber, + rel->notnullattrs)) + multi_nullvals = true; + } + + exprs = get_tlist_exprs(unique_index->indextlist, true); + rel->uniquekeys = lappend(rel->uniquekeys, + makeUniqueKey(exprs, + multi_nullvals, + false)); +} + + +/* + * add_uniquekey_for_onerow + * If we are sure that the relation only returns one row, then all the columns + * are unique. However we don't need to create UniqueKey for every column, we + * just set UniqueKey->onerow to true is OK and leave the exprs = NIL. + */ +void +add_uniquekey_for_onerow(RelOptInfo *rel) +{ + rel->uniquekeys = list_make1(makeUniqueKey(NIL, /* No need to set exprs */ + false, /* onerow can't have multi_nullvals */ + true)); + +} + +/* + * initililze_uniquecontext_for_joinrel + * Return a List of UniqueKeyContext for an inputrel + */ +static List * +initililze_uniquecontext_for_joinrel(RelOptInfo *inputrel) +{ + List *res = NIL; + ListCell *lc; + foreach(lc, inputrel->uniquekeys) + { + UniqueKeyContext context; + context = palloc(sizeof(struct UniqueKeyContextData)); + context->uniquekey = lfirst_node(UniqueKey, lc); + context->added_to_joinrel = false; + context->useful = true; + res = lappend(res, context); + } + return res; +} + +/* + * clause_sides_match_join + * Determine whether a join clause is of the right form to use in this join. + * + * We already know that the clause is a binary opclause referencing only the + * rels in the current join. The point here is to check whether it has the + * form "outerrel_expr op innerrel_expr" or "innerrel_expr op outerrel_expr", + * rather than mixing outer and inner vars on either side. If it matches, + * we set the transient flag outer_is_left to identify which side is which. + */ +static bool +clause_sides_match_join(RestrictInfo *rinfo, Relids outerrelids, + Relids innerrelids) +{ + if (bms_is_subset(rinfo->left_relids, outerrelids) && + bms_is_subset(rinfo->right_relids, innerrelids)) + { + /* lefthand side is outer */ + rinfo->outer_is_left = true; + return true; + } + else if (bms_is_subset(rinfo->left_relids, innerrelids) && + bms_is_subset(rinfo->right_relids, outerrelids)) + { + /* righthand side is outer */ + rinfo->outer_is_left = false; + return true; + } + return false; /* no good for these input relations */ +} + +/* + * get_exprs_from_uniquekey + * Unify the way of get List of exprs from a one-row UniqueKey or + * normal UniqueKey. Return a List of exprs. + * + * rel1: The relation which you want to get the exprs. + * ukey: The UniqueKey you want to get the exprs. + */ +static List * +get_exprs_from_uniquekey(RelOptInfo *joinrel, RelOptInfo *rel1, UniqueKey *ukey) +{ + ListCell *lc; + bool onerow = rel1 != NULL && relation_is_onerow(rel1); + + List *res = NIL; + Assert(onerow || ukey); + if (onerow) + { + /* Only cares about the exprs still exist in joinrel */ + foreach(lc, joinrel->reltarget->exprs) + { + Bitmapset *relids = pull_varnos(lfirst(lc)); + if (bms_is_subset(relids, rel1->relids)) + { + res = lappend(res, list_make1(lfirst(lc))); + } + } + } + else + { + res = list_make1(ukey->exprs); + } + return res; +} + +/* + * Partitioned table Unique Keys. + * The partition table unique key is maintained as: + * 1. The index must be unique as usual. + * 2. The index must contains partition key. + * 3. The index must exist on all the child rel. see simple_indexinfo_equal for + * how we compare it. + */ + +/* index_constains_partkey + * return true if the index contains the partiton key. + */ +static bool +index_constains_partkey(RelOptInfo *partrel, IndexOptInfo *ind) +{ + ListCell *lc; + int i; + Assert(IS_PARTITIONED_REL(partrel)); + + for(i = 0; i < partrel->part_scheme->partnatts; i++) + { + Node *part_expr = linitial(partrel->partexprs[i]); + bool found_in_index = false; + foreach(lc, ind->indextlist) + { + Expr *index_expr = lfirst_node(TargetEntry, lc)->expr; + if (equal(index_expr, part_expr)) + { + found_in_index = true; + break; + } + } + if (!found_in_index) + return false; + } + return true; +} + +/* + * simple_indexinfo_equal + * + * Used to check if the 2 index is same as each other. The index here + * is COPIED from childrel and did some tiny changes(see + * simple_copy_indexinfo_to_parent) + */ +static bool +simple_indexinfo_equal(IndexOptInfo *ind1, IndexOptInfo *ind2) +{ + Size oid_cmp_len = sizeof(Oid) * ind1->ncolumns; + return ind1->ncolumns == ind2->ncolumns && + ind1->unique == ind2->unique && + memcmp(ind1->indexkeys, ind2->indexkeys, sizeof(int) * ind1->ncolumns) == 0 && + memcmp(ind1->opfamily, ind2->opfamily, oid_cmp_len) == 0 && + memcmp(ind1->opcintype, ind2->opcintype, oid_cmp_len) == 0 && + memcmp(ind1->sortopfamily, ind2->sortopfamily, oid_cmp_len) == 0 && + equal(ind1->indextlist, ind2->indextlist); +} + + +/* + * The below macros are used for simple_copy_indexinfo_to_parent which is so + * customized that I don't want to put it to copyfuncs.c. So copy it here. + */ +#define COPY_POINTER_FIELD(fldname, sz) \ + do { \ + Size _size = (sz); \ + newnode->fldname = palloc(_size); \ + memcpy(newnode->fldname, from->fldname, _size); \ + } while (0) + +#define COPY_NODE_FIELD(fldname) \ + (newnode->fldname = copyObjectImpl(from->fldname)) + +#define COPY_SCALAR_FIELD(fldname) \ + (newnode->fldname = from->fldname) + + +/* + * simple_copy_indexinfo_to_parent (from partition) + * Copy the IndexInfo from child relation to parent relation with some modification, + * which is used to test: + * 1. If the same index exists in all the childrels. + * 2. If the parentrel->reltarget/basicrestrict info matches this index. + */ +static IndexOptInfo * +simple_copy_indexinfo_to_parent(RelOptInfo *parentrel, + IndexOptInfo *from) +{ + IndexOptInfo *newnode = makeNode(IndexOptInfo); + + COPY_SCALAR_FIELD(ncolumns); + COPY_SCALAR_FIELD(nkeycolumns); + COPY_SCALAR_FIELD(unique); + COPY_SCALAR_FIELD(immediate); + /* We just need to know if it is NIL or not */ + COPY_SCALAR_FIELD(indpred); + COPY_SCALAR_FIELD(predOK); + COPY_POINTER_FIELD(indexkeys, from->ncolumns * sizeof(int)); + COPY_POINTER_FIELD(indexcollations, from->ncolumns * sizeof(Oid)); + COPY_POINTER_FIELD(opfamily, from->ncolumns * sizeof(Oid)); + COPY_POINTER_FIELD(opcintype, from->ncolumns * sizeof(Oid)); + COPY_POINTER_FIELD(sortopfamily, from->ncolumns * sizeof(Oid)); + COPY_NODE_FIELD(indextlist); + + /* + * Change relid from partition relid to parent relid so that the later + * index match work. + */ + ChangeVarNodes((Node*) newnode->indextlist, + from->rel->relid, + parentrel->relid, 0); + newnode->rel = parentrel; + return newnode; +} + +/* + * adjust_partition_unique_indexlist + * + * global_unique_indexes: At the beginning, it contains the copy & modified + * unique index from the first partition. And then check if each index in it still + * exists in the following partitions. If no, remove it. at last, it has an + * index list which exists in all the partitions. + */ +static void +adjust_partition_unique_indexlist(RelOptInfo *parentrel, + RelOptInfo *childrel, + List **global_unique_indexes) +{ + ListCell *lc, *lc2; + foreach(lc, *global_unique_indexes) + { + IndexOptInfo *g_ind = lfirst_node(IndexOptInfo, lc); + bool found_in_child = false; + + foreach(lc2, childrel->indexlist) + { + IndexOptInfo *p_ind = lfirst_node(IndexOptInfo, lc2); + IndexOptInfo *p_ind_copy; + if (!p_ind->unique || !p_ind->immediate || + (p_ind->indpred != NIL && !p_ind->predOK)) + continue; + p_ind_copy = simple_copy_indexinfo_to_parent(parentrel, p_ind); + if (simple_indexinfo_equal(p_ind_copy, g_ind)) + { + found_in_child = true; + break; + } + } + + if (!found_in_child) + /* There is no same index on other childrel, remove it */ + *global_unique_indexes = foreach_delete_current(*global_unique_indexes, lc); + } +} + +/* Helper function for groupres/distinctrel */ +static void +add_uniquekey_from_sortgroups(PlannerInfo *root, RelOptInfo *rel, List *sortgroups) +{ + Query *parse = root->parse; + List *exprs; + + /* XXX: If there are some vars which is not in current levelsup, the semantic is + * imprecise, should we avoid it? levelsup = 1 is just a demo, maybe we need to + * check every level other than 0, if so, we need write another pull_var_walker. + */ + List *upper_vars = pull_vars_of_level((Node*)sortgroups, 1); + + if (upper_vars != NIL) + return; + + exprs = get_sortgrouplist_exprs(sortgroups, parse->targetList); + rel->uniquekeys = lappend(rel->uniquekeys, + makeUniqueKey(exprs, + false, /* sortgroupclause can't be multi_nullvals */ + false)); + +} + + +/* + * add_combined_uniquekey + * The combination of both UniqueKeys is a valid UniqueKey for joinrel no matter + * the jointype. + * Note: This function is called when either single side of the UniqueKeys is not + * valid any more after join. + */ +bool +add_combined_uniquekey(RelOptInfo *joinrel, + RelOptInfo *outer_rel, + RelOptInfo *inner_rel, + UniqueKey *outer_ukey, + UniqueKey *inner_ukey, + JoinType jointype) +{ + + ListCell *lc1, *lc2; + + /* Either side has multi_nullvals, the combined UniqueKey has multi_nullvals */ + bool multi_nullvals = outer_ukey->multi_nullvals || inner_ukey->multi_nullvals; + + /* If we have outer join, it implies we will have mutli_nullvals */ + multi_nullvals = multi_nullvals || IS_OUTER_JOIN(jointype); + + /* The only case we can get onerow joinrel after join */ + if (outer_ukey->onerow && inner_ukey->onerow && jointype == JOIN_INNER) + { + add_uniquekey_for_onerow(joinrel); + return true; + } + + foreach(lc1, get_exprs_from_uniquekey(joinrel, outer_rel, outer_ukey)) + { + foreach(lc2, get_exprs_from_uniquekey(joinrel, inner_rel, inner_ukey)) + { + List *exprs = list_concat_copy(lfirst_node(List, lc1), lfirst_node(List, lc2)); + joinrel->uniquekeys = lappend(joinrel->uniquekeys, + makeUniqueKey(exprs, + multi_nullvals, + false)); + } + } + return false; +} diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 357850624c..370903ef5e 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -2389,6 +2389,8 @@ grouping_planner(PlannerInfo *root, bool inheritance_update, add_path(final_rel, path); } + simple_copy_uniquekeys(current_rel, final_rel); + /* * Generate partial paths for final_rel, too, if outer query levels might * be able to make use of them. @@ -3899,6 +3901,8 @@ create_grouping_paths(PlannerInfo *root, } set_cheapest(grouped_rel); + + populate_grouprel_uniquekeys(root, grouped_rel); return grouped_rel; } @@ -4616,7 +4620,7 @@ create_window_paths(PlannerInfo *root, /* Now choose the best path(s) */ set_cheapest(window_rel); - + simple_copy_uniquekeys(input_rel, window_rel); return window_rel; } @@ -4912,7 +4916,7 @@ create_distinct_paths(PlannerInfo *root, /* Now choose the best path(s) */ set_cheapest(distinct_rel); - + populate_distinctrel_uniquekeys(root, input_rel, distinct_rel); return distinct_rel; } @@ -5173,6 +5177,8 @@ create_ordered_paths(PlannerInfo *root, */ Assert(ordered_rel->pathlist != NIL); + simple_copy_uniquekeys(input_rel, ordered_rel); + return ordered_rel; } diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c index 951aed80e7..e94e92937c 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -689,6 +689,8 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root, /* Undo effects of possibly forcing tuple_fraction to 0 */ root->tuple_fraction = save_fraction; + /* Add the UniqueKeys */ + populate_unionrel_uniquekeys(root, result_rel); return result_rel; } diff --git a/src/include/nodes/makefuncs.h b/src/include/nodes/makefuncs.h index 31d9aedeeb..33f6ddc948 100644 --- a/src/include/nodes/makefuncs.h +++ b/src/include/nodes/makefuncs.h @@ -16,6 +16,7 @@ #include "nodes/execnodes.h" #include "nodes/parsenodes.h" +#include "nodes/pathnodes.h" extern A_Expr *makeA_Expr(A_Expr_Kind kind, List *name, @@ -105,4 +106,6 @@ extern GroupingSet *makeGroupingSet(GroupingSetKind kind, List *content, int loc extern VacuumRelation *makeVacuumRelation(RangeVar *relation, Oid oid, List *va_cols); +extern UniqueKey* makeUniqueKey(List *exprs, bool multi_nullvals, bool onerow); + #endif /* MAKEFUNC_H */ diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h index 381d84b4e4..41110ed888 100644 --- a/src/include/nodes/nodes.h +++ b/src/include/nodes/nodes.h @@ -264,6 +264,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 9e3ebd488a..675956f06d 100644 --- a/src/include/nodes/pathnodes.h +++ b/src/include/nodes/pathnodes.h @@ -730,6 +730,7 @@ typedef struct RelOptInfo QualCost baserestrictcost; /* cost of evaluating the above */ Index baserestrict_min_security; /* min security_level found in * baserestrictinfo */ + List *uniquekeys; /* List of UniqueKey */ List *joininfo; /* RestrictInfo structures for join clauses * involving this rel */ bool has_eclass_joins; /* T means joininfo is incomplete */ @@ -1047,6 +1048,31 @@ typedef struct PathKey } PathKey; +/* + * UniqueKey + * + * Represents the unique properties held by a RelOptInfo. + * + * exprs is a list of exprs which is unique on current RelOptInfo. + * multi_nullvals: true means multi null values may exists in these exprs, so the + * uniqueness is not guaranteed in this case. This field is necessary for + * remove_useless_join & reduce_unique_semijoins where we don't mind these + * duplicated NULL values. It is set to true for 2 cases. One is a unique key + * from a unique index but the related column is nullable. The other one is for + * outer join. see populate_joinrel_uniquekeys for detail. + * onerow means the related relation return 1 row only. Like filter with unique + * index, aggregate without group node, join 2 1-row relations. An optimization + * is if the onerow is set to true, we will set not record every expr as a UniqueKey, + * we store exprs as a NIL instead. + */ +typedef struct UniqueKey +{ + NodeTag type; + List *exprs; + bool multi_nullvals; + bool onerow; +} UniqueKey; + /* * PathTarget * diff --git a/src/include/nodes/pg_list.h b/src/include/nodes/pg_list.h index 14ea2766ad..621f54a9f8 100644 --- a/src/include/nodes/pg_list.h +++ b/src/include/nodes/pg_list.h @@ -528,6 +528,8 @@ extern bool list_member_ptr(const List *list, const void *datum); extern bool list_member_int(const List *list, int datum); extern bool list_member_oid(const List *list, Oid datum); +extern bool list_is_subset(const List *members, const List *target); + extern List *list_delete(List *list, void *datum); extern List *list_delete_ptr(List *list, void *datum); extern List *list_delete_int(List *list, int datum); diff --git a/src/include/optimizer/optimizer.h b/src/include/optimizer/optimizer.h index 3e4171056e..9445141263 100644 --- a/src/include/optimizer/optimizer.h +++ b/src/include/optimizer/optimizer.h @@ -23,6 +23,7 @@ #define OPTIMIZER_H #include "nodes/parsenodes.h" +#include "nodes/pathnodes.h" /* * We don't want to include nodes/pathnodes.h here, because non-planner @@ -156,6 +157,7 @@ extern TargetEntry *get_sortgroupref_tle(Index sortref, List *targetList); extern TargetEntry *get_sortgroupclause_tle(SortGroupClause *sgClause, List *targetList); +extern Var *find_var_for_subquery_tle(RelOptInfo *rel, TargetEntry *tle); extern Node *get_sortgroupclause_expr(SortGroupClause *sgClause, List *targetList); extern List *get_sortgrouplist_exprs(List *sgClauses, diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h index 10b6e81079..651e48acbb 100644 --- a/src/include/optimizer/paths.h +++ b/src/include/optimizer/paths.h @@ -241,4 +241,39 @@ extern PathKey *make_canonical_pathkey(PlannerInfo *root, extern void add_paths_to_append_rel(PlannerInfo *root, RelOptInfo *rel, List *live_childrels); +/* + * uniquekeys.c + * Utilities for matching and building unique keys + */ +extern void populate_baserel_uniquekeys(PlannerInfo *root, + RelOptInfo *baserel, + List* unique_index_list); +extern void populate_partitionedrel_uniquekeys(PlannerInfo *root, + RelOptInfo *rel, + List *childrels); +extern void populate_distinctrel_uniquekeys(PlannerInfo *root, + RelOptInfo *inputrel, + RelOptInfo *distinctrel); +extern void populate_grouprel_uniquekeys(PlannerInfo *root, + RelOptInfo *grouprel); +extern void populate_unionrel_uniquekeys(PlannerInfo *root, + RelOptInfo *unionrel); +extern void simple_copy_uniquekeys(RelOptInfo *oldrel, + RelOptInfo *newrel); +extern void convert_subquery_uniquekeys(PlannerInfo *root, + RelOptInfo *currel, + RelOptInfo *sub_final_rel); +extern void populate_joinrel_uniquekeys(PlannerInfo *root, + RelOptInfo *joinrel, + RelOptInfo *rel1, + RelOptInfo *rel2, + List *restrictlist, + JoinType jointype); + +extern bool relation_has_uniquekeys_for(PlannerInfo *root, + RelOptInfo *rel, + List *exprs, + bool allow_multinulls); +extern bool relation_is_onerow(RelOptInfo *rel); + #endif /* PATHS_H */ -- 2.21.0