From: Tomas Vondra Date: Tue, 16 Mar 2021 19:26:40 +0100 Subject: [PATCH 04/10] review --- src/backend/nodes/copyfuncs.c | 4 + src/backend/nodes/makefuncs.c | 1 - src/backend/nodes/outfuncs.c | 1 + src/backend/nodes/readfuncs.c | 2 + src/backend/optimizer/path/README.uniquekey | 285 +++--- src/backend/optimizer/path/allpaths.c | 10 +- src/backend/optimizer/path/joinrels.c | 7 + src/backend/optimizer/path/uniquekeys.c | 906 ++++++++++++++------ src/backend/optimizer/plan/planner.c | 10 + src/backend/optimizer/prep/prepunion.c | 1 + src/backend/optimizer/util/inherit.c | 1 + 11 files changed, 863 insertions(+), 365 deletions(-) diff --git a/src/backend/nodes/copyfuncs.c b/src/backend/nodes/copyfuncs.c index 75c1c5e824..9d832ddc03 100644 --- a/src/backend/nodes/copyfuncs.c +++ b/src/backend/nodes/copyfuncs.c @@ -2296,6 +2296,9 @@ _copyPathKey(const PathKey *from) return newnode; } +/* + * _copyUniqueKey + */ static UniqueKey * _copyUniqueKey(const UniqueKey *from) { @@ -2306,6 +2309,7 @@ _copyUniqueKey(const UniqueKey *from) return newnode; } + /* * _copyRestrictInfo */ diff --git a/src/backend/nodes/makefuncs.c b/src/backend/nodes/makefuncs.c index 40415d0f5b..e156c9cdf8 100644 --- a/src/backend/nodes/makefuncs.c +++ b/src/backend/nodes/makefuncs.c @@ -816,7 +816,6 @@ makeVacuumRelation(RangeVar *relation, Oid oid, List *va_cols) return v; } - /* * makeUniqueKey */ diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 44154cde6a..13905e6037 100644 --- a/src/backend/nodes/outfuncs.c +++ b/src/backend/nodes/outfuncs.c @@ -2460,6 +2460,7 @@ static void _outUniqueKey(StringInfo str, const UniqueKey *node) { WRITE_NODE_TYPE("UNIQUEKEY"); + WRITE_NODE_FIELD(exprs); WRITE_BOOL_FIELD(multi_nullvals); } diff --git a/src/backend/nodes/readfuncs.c b/src/backend/nodes/readfuncs.c index b3e212bf1c..8830c8df99 100644 --- a/src/backend/nodes/readfuncs.c +++ b/src/backend/nodes/readfuncs.c @@ -496,8 +496,10 @@ static UniqueKey * _readUniqueKey(void) { READ_LOCALS(UniqueKey); + READ_NODE_FIELD(exprs); READ_BOOL_FIELD(multi_nullvals); + READ_DONE(); } diff --git a/src/backend/optimizer/path/README.uniquekey b/src/backend/optimizer/path/README.uniquekey index 5eac761995..31cdb5ed65 100644 --- a/src/backend/optimizer/path/README.uniquekey +++ b/src/backend/optimizer/path/README.uniquekey @@ -1,131 +1,208 @@ -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. +review comments: +XXX Maybe move this to src/backend/optimizer/README.uniquekey? +XXX multi_nullvals name seems a bit weird +XXX no info about populate_distinctrel_uniquekeys, populate_grouprel_uniquekeys, populate_unionrel_uniquekeys +----- +src/backend/optimizer/path/README.uniquekey + +UniqueKey +========= + +UniqueKey is a set of exprs for a RelOptInfo, which are known to have unique +values on all the rows in the relation. A trivial example is a primary key +defined on a relation - each attributes of the constraint is a unique key. + +We can use this knowledge to perform optimization in a number of places. Some +of the optimizations are fairly obvious, others are less so: + +1. remove DISTINCT node if the clause is unique +2. remove aggregation if group by clause is unique +3. remove_useless_joins +4. reduce_semianti_joins +5. Index Skip Scan (WIP) +6. Aggregation Push-Down without 2-phase aggregation if the join can't + duplicate the aggregated rows. (WIP) + -However we define the UnqiueKey as below. +UniqueKey struct +---------------- -typedef struct UniqueKey -{ +A UnqiueKey is represented by the following struct: + + typedef struct UniqueKey + { NodeTag type; List *exprs; bool multi_nullvals; -} UniqueKey; - -exprs is a list of exprs which is unique on current RelOptInfo. exprs = NIL -is a special case of UniqueKey, which means there is only one row in that -relation.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. this logic is handled specially in add_uniquekey_for_onerow -function. - -multi_nullvals: true means multi null values may exist 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. - - -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. Index Skip Scan (WIP) -6. 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. - -1. The first part is about baserel. We handled 3 cases. suppose we have Unique -Index on (a, b). - -1. SELECT a, b FROM t. UniqueKey (a, b) -2. SELECT a FROM t WHERE b = 1; UniqueKey (a) -3. SELECT .. FROM t WHERE a = 1 AND b = 1; UniqueKey (NIL). onerow case, every - column is Unique. - -2. The next part is joinrel, this part is most error-prone, 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: + } UniqueKey; + +exprs is a list of exprs which are know to be unique on current RelOptInfo. + +exprs = NIL is a special case, meaning there is only one row in the relation. +This has has a stronger semantic than others. Consider for example + + SELECT uk FROM t + +where 'uk' is a unique key. This guarantees uniqueness, but there may be mamy +rows in the relation. On the other hand, consider this query + + SELECT colx FROM t WHERE uk = const + +In this case we know there's only a single matching row (thanks to a condition +on the unique key), which in turn guarantees uniqueness of the colx value, even +if there is no constraint on the column itself. + +This knowledge is used in innerrel_is_unique, and is handled as a special case +in add_uniquekey_for_onerow. + + +The multi_nullvals field tracks whether the expressions may contain multiple +NULL values. This can happen for example when the unique key is derived from +a unique index with nullable columns, or because of outer joins (which may add +NULL values to a known-unique list - see populate_joinrel_uniquekeys). + +In this case uniqueness is not guaranteed, but we can still use the information +in places places where NULL values are harmless - when removing useless joins, +reducing semijoins, and so on. + + +How is it maintained? +--------------------- + +Deducing the unique keys depends on the type of the relation - for each case +there's a separate "populate" function: + + +populate_baserel_uniquekeys +--------------------------- + +There are three cases, all assuming there's a unique index (e.g. on (a,b)): + +1. SELECT a, b FROM t => UniqueKey (a, b) +2. SELECT a FROM t WHERE b = 1 => UniqueKey (a) +3. SELECT .. FROM t WHERE a = 1 AND b = 1; => UniqueKey (NIL) + +The last query is the "one row" case, in which case every column is Unique. + + +populate_joinrel_uniquekeys +--------------------------- + +For joins, deducing the unique keys may be fairly complex and error-prone. +We've simplified the rules like this: + +1. If the UniqueKey on an input relation can't be duplicated by the join, then +it will be valid for the join rel. A typical example is a join like this: + + inner_rel.any_col = outer_rel.unique_key + +The function used to detect this is innerrel_keeps_unique. + +2. Any combination of unique keys on each side of the join is a unique key +for the join relation. This can be proved by contradiction - assume we have +unique key on either side of the join - uk1 and uk2. If the values in uk1 get +duplicated by the join with uk2 (by matching the row to multiple rows), the +duplicated rows must have different values in the uk2. + +We can also leverage information about the "one row" case: + +1. If one of the input relations is known to have a single row, and the join +can't duplicate the row (e.g. semi/anti join), we can keep the unique keys. +It may however contain multi_nullvals after an outer join. + +XXX Not sure I understand the original logic/wording :-( + +2. If either UniqueKey can be duplicated after a join, there can be only one +row only when both sides are "one row" AND there is no outer join. + +XXX Why the restriction on not allowing outer joins? + +3. Whenever the one row UniqueKey is not a valid any more, we need to convert +UniqueKey to normal unique key since we don't store exprs for one-row relation. +This is done by get_exprs_from_uniquekeys. + +The join case needs to be careful about multi_nullvals too: + 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. +mulit_nullvals in any case too. + +2. If the original unique key doesn't allow multi_nullvals, the unique key for +the join relation may allow multi_nullvals after an outer join. + + +subqueries +---------- + +It's necessary to "translate" unique keys between a subquery and the outer rels, +which is what convert_subquery_uniquekeys does. This does almost exactly what +convert_subquery_pathkeys does for pathkeys. It keeps only unique keys matching +Vars in the outer relation. The relationship between outerrel.Var and +subquery.exprs is built from outerel->subroot->processed_tlist. -3. When we comes to subquery, we need to convert_subquery_unqiuekeys just like -convert_subquery_pathkeys. Only the UniqueKey insides subquery is referenced as -a Var in outer relation will be reused. The relationship between the outerrel.Var -and subquery.exprs is built with outerel->subroot->processed_tlist. +set-returning functions +------------------------ +As for the SRF functions, it will break the uniqueness of uniquekey, However it +is handled in adjust_paths_for_srfs, which happens after the query_planner. So +we will maintain the UniqueKey until there and reset it to NIL at that place. -4. As for the SRF functions, it will break the uniqueness of uniquekey, However it -is handled in adjust_paths_for_srfs, which happens after the query_planner. so -we will maintain the UniqueKey until there and reset it to NIL at that -places. This can't help on distinct/group by elimination cases but probably help -in some other cases, like reduce_unqiue_semijoins/remove_useless_joins and it is -semantic correctly. +This can't help on distinct/group by elimination cases but probably help in some +other cases, like reduce_unqiue_semijoins/remove_useless_joins and it is correct. -5. As for inherit table, we first main the UnqiueKey on childrel as well. But for -partitioned table we need to maintain 2 different kinds of -UnqiueKey. 1). UniqueKey on the parent relation 2). UniqueKey on child -relation for partition wise query. +populate_partitionedrel_uniquekeys +---------------------------------- + +As for inherit table, we first build the UnqiueKey on childrel as well. But for +partitioned table we need to maintain two different kinds of UniqueKey: + +1) UniqueKey on the parent relation + +2) UniqueKey on child + +This is needed because a unique key from the partition may not be be unique key +on the partitioned table. + Example: -CREATE TABLE p (a int not null, b int not null) partition by list (a); + +CREATE TABLE p (a INT NOT NULL, b INT NOT NULL) PARTITION BY LIST (a); + CREATE TABLE p0 partition of p for values in (1); CREATE TABLE p1 partition of p for values in (2); -create unique index p0_b on p0(b); -create unique index p1_b on p1(b); +CREATE UNIQUE INDEX p0_b ON p0(b); +CREATE UNIQUE INDEX p1_b ON p1(b); -Now b is only unique on partition level, so the distinct can't be removed on -the following cases. SELECT DISTINCT b FROM p; +SELECT DISTINCT b FROM p; -Another example is SELECT DISTINCT a, b FROM p WHERE a = 1; Since only one -partition is chosen, the UniqueKey on child relation is same as the UniqueKey on -parent relation. +Now "b" is only unique on partition level, but the two partitions may contain +duplicate values for the "b" column (with different values in "a"). That means +the DISTINCT clause can't be removed. -Another usage of UniqueKey on partition level is it be helpful for -partition-wise join. +Now consider: -As for the UniqueKey on parent table level, it comes with 2 different ways, -1). the UniqueKey is also derived in UniqueKey index, but the index must be same -in all the related children relations and the unique index must contains -Partition Key in it. Example: +SELECT DISTINCT a, b FROM p WHERE a = 1 + +In this case, the optimizer eliminates all partitions except for one, so that +the UniqueKey is valid for the parent relation too. + +UniqueKey at a partition level is useful for partition-wise join too. + +XXX Explain why is it useful? + +A UniqueKey from a partition can be transferred to the parent relation, in two +cases. A trivial case is if there's a single child relation (e.g. thanks to +partition elimination). In that case all unique keys on the child relation are +automatically valid for the parent relation. If there are multiple relations, +the unique key must be defived from an index present in all partitions, and the +index has to include the partition key. + +Example: CREATE UNIQUE INDEX p_ab ON p(a, b); -- where a is the partition key. -- Query SELECT a, b FROM p; the (a, b) is a UniqueKey of p. -2). If the parent relation has only one childrel, the UniqueKey on childrel is - the UniqueKey on parent as well. diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 66bf6f19f7..a801707eaa 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -581,7 +581,8 @@ set_plain_rel_size(PlannerInfo *root, RelOptInfo *rel, RangeTblEntry *rte) /* * Now that we've marked which partial indexes are suitable, we can now - * build the relation's unique keys. + * build the relation's unique keys. We need to do it in this order, + * so that we don't deduce unique keys from inapplicable partial indexes. */ populate_baserel_uniquekeys(root, rel, rel->indexlist); @@ -1305,6 +1306,12 @@ set_append_rel_pathlist(PlannerInfo *root, RelOptInfo *rel, /* Add paths to the append relation. */ add_paths_to_append_rel(root, rel, live_childrels); + + /* + * XXX Maybe move the check into populate populate_partitionedrel_uniquekeys? + * XXX What if it's append rel (but not partitioned one), but there's only one + * child relation? We could still deduce unique keys, no? + */ if (IS_PARTITIONED_REL(rel)) populate_partitionedrel_uniquekeys(root, rel, live_childrels); } @@ -2314,6 +2321,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel, pathkeys, required_outer)); } + /* Convert subpath's unique keys to outer representation */ convert_subquery_uniquekeys(root, rel, sub_final_rel); /* If outer rel allows parallelism, do same for partial paths. */ diff --git a/src/backend/optimizer/path/joinrels.c b/src/backend/optimizer/path/joinrels.c index 7271f044ec..eefba449d6 100644 --- a/src/backend/optimizer/path/joinrels.c +++ b/src/backend/optimizer/path/joinrels.c @@ -925,6 +925,13 @@ populate_joinrel_with_paths(PlannerInfo *root, RelOptInfo *rel1, /* Apply partitionwise join technique, if possible. */ try_partitionwise_join(root, rel1, rel2, joinrel, sjinfo, restrictlist); + /* + * Determine which of the unique keys from input relations are applicable + * for the join result. + * + * XXX We do this after trying the partitionwise join, because that may allow + * using additional unique keys. + */ populate_joinrel_uniquekeys(root, joinrel, rel1, rel2, restrictlist, sjinfo->jointype); } diff --git a/src/backend/optimizer/path/uniquekeys.c b/src/backend/optimizer/path/uniquekeys.c index 77ed2b2eff..114e8334f5 100644 --- a/src/backend/optimizer/path/uniquekeys.c +++ b/src/backend/optimizer/path/uniquekeys.c @@ -36,7 +36,7 @@ typedef struct UniqueKeyContextData bool useful; } *UniqueKeyContext; -static List *initililze_uniquecontext_for_joinrel(RelOptInfo *inputrel); +static List *initialize_uniquecontext_for_joinrel(RelOptInfo *inputrel); static bool innerrel_keeps_unique(PlannerInfo *root, RelOptInfo *outerrel, RelOptInfo *innerrel, @@ -80,8 +80,20 @@ static void add_uniquekey_from_sortgroups(PlannerInfo *root, /* * populate_baserel_uniquekeys - * Populate 'baserel' uniquekeys list by looking at the rel's unique index - * and baserestrictinfo + * Build list of unique keys for the base relation. + * + * Inspects unique indexes defined on the relation and determines what + * unique keys are valid. Partial indexes are considered too, if the + * predicate is valid. + * + * This also inspects baserestrictinfo, because we need to determine + * which opclass families are interesting when inspecting indexes. If we + * have a unique index and distinct clause with a mismatching opclasses, + * we should not use that. + * + * XXX Why does this look at baserestrictinfo? + * + * XXX What about collations? */ void populate_baserel_uniquekeys(PlannerInfo *root, @@ -99,22 +111,48 @@ populate_baserel_uniquekeys(PlannerInfo *root, Assert(baserel->rtekind == RTE_RELATION); + if (!indexlist) + return; + + /* + * Determine which unique indexes to use to build the unique keys. + * We have to skip partial with predicates not matched by the query, + * and unique indexes that are not immediately enforced. + * + * XXX Do we actually skip indexes that are not immediate? + * XXX What about hypothetical indexes? + */ foreach(lc, indexlist) { IndexOptInfo *ind = (IndexOptInfo *) lfirst(lc); + if (!ind->unique || !ind->immediate || (ind->indpred != NIL && !ind->predOK)) continue; + matched_uniq_indexes = lappend(matched_uniq_indexes, ind); } + /* If there are not applicable unique indexes, we're done. */ if (matched_uniq_indexes == NIL) return; - /* Check which attrs is used in baserel->reltarget */ - pull_varattnos((Node *)baserel->reltarget->exprs, baserel->relid, &used_attrs); + /* + * Determine which attrs are referenced in baserel->reltarget. To use the + * unique key info, we need all the columns - a unique index on (a,b) may + * not be unique on (a). If a column is missing in reltarget, the nodes + * above can't possibly use it, and we can just ignore any matching index. + */ + pull_varattnos((Node *) baserel->reltarget->exprs, baserel->relid, &used_attrs); - /* Check which attrno is used at a mergeable const filter */ + /* + * Check which attrno is used at a mergeable const filter + * + * XXX This is not lookint att attrno at all, maybe obsolete comment? + * + * Seems the primary purpose of this is determining which opclass + * families to use when matching unique indexes in the next loop? + */ foreach(lc, baserel->baserestrictinfo) { RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc); @@ -122,6 +160,10 @@ populate_baserel_uniquekeys(PlannerInfo *root, if (rinfo->mergeopfamilies == NIL) continue; + /* + * XXX What if bms_is_empty is true for both left_relids/right_relids? + * Or what if it's false in both cases? + */ if (bms_is_empty(rinfo->left_relids)) { const_exprs = lappend(const_exprs, get_rightop(rinfo->clause)); @@ -136,40 +178,69 @@ populate_baserel_uniquekeys(PlannerInfo *root, expr_opfamilies = lappend(expr_opfamilies, rinfo->mergeopfamilies); } + /* + * Now try to match unique indexes to attributes in reltarget, and to + * merge operator families. The index may be on the right attributes, + * but if it's not matching the opfamily it's useless. + * + * XXX Can we have multiple baserestrictinfo for the same attribute, + * with different opfamilies? Probably not. + */ foreach(lc, matched_uniq_indexes) { - bool multi_nullvals, useful; - List *exprs = get_exprs_from_uniqueindex(lfirst_node(IndexOptInfo, lc), - const_exprs, - expr_opfamilies, - used_attrs, - &useful, - &multi_nullvals); - if (useful) + bool multi_nullvals, + useful; + + IndexOptInfo *index_info = (IndexOptInfo *) lfirst_node(IndexOptInfo, lc); + + List *exprs = get_exprs_from_uniqueindex(index_info, + const_exprs, + expr_opfamilies, + used_attrs, + &useful, + &multi_nullvals); + + if (!useful) + continue; + + /* + * All the columns in Unique Index matched with a restrictinfo, so + * that we know there's just a one row in the result. If we find + * such index, we're done - we discard all other unique keys and + * keep just this special one. In principle, this is a stronger + * guarantee, because all subsets of one row are still unique. + * + * XXX Is it correct to just return? Doesn't that prevent some + * optimizations that might be possible with the other keys? + */ + if (exprs == NIL) { - if (exprs == NIL) - { - /* All the columns in Unique Index matched with a restrictinfo */ - add_uniquekey_for_onerow(baserel); - return; - } - baserel->uniquekeys = lappend(baserel->uniquekeys, - makeUniqueKey(exprs, multi_nullvals)); + /* discards all previous uniquekeys */ + add_uniquekey_for_onerow(baserel); + return; } + + baserel->uniquekeys = lappend(baserel->uniquekeys, + makeUniqueKey(exprs, multi_nullvals)); } } /* * populate_partitionedrel_uniquekeys - * The UniqueKey on partitionrel comes from 2 cases: - * 1). Only one partition is involved in this query, the unique key can be - * copied to parent rel from childrel. - * 2). There are some unique index which includes partition key and exists - * in all the related partitions. - * We never mind rule 2 if we hit rule 1. + * Determine unique keys for a partitioned relation. + * + * Inspects unique keys for all partitions and derives unique keys that + * are valid for the whole partitioned table. There are two basic cases: + * + * 1) There's only one remaining partition (thanks to pruning all other + * partitions). In this case all the unique keys from the partition are + * trivially valid for the partitioned table. + * + * 2) All the partitions have the same unique index (on the same set of + * columns), and the index includes the partition key. This ensures the + * combination of values is unique for the whole partitioned table. */ - void populate_partitionedrel_uniquekeys(PlannerInfo *root, RelOptInfo *rel, @@ -180,110 +251,181 @@ populate_partitionedrel_uniquekeys(PlannerInfo *root, RelOptInfo *childrel; bool is_first = true; + /* XXX What about append rels? At least for the one-child case? */ Assert(IS_PARTITIONED_REL(rel)); + /* if there are no child relations, we're done. */ if (childrels == NIL) return; /* - * If there is only one partition used in this query, the UniqueKey in childrel is - * still valid in parent level, but we need convert the format from child expr to - * parent expr. + * If there is only one partition used in this query, the UniqueKey for + * a child relation is still valid for the parent level. We need to + * convert the format from child expr to parent expr. */ if (list_length(childrels) == 1) { - /* Check for Rule 1 */ RelOptInfo *childrel = linitial_node(RelOptInfo, childrels); ListCell *lc; + Assert(childrel->reloptkind == RELOPT_OTHER_MEMBER_REL); + + /* If the partition has a single row, so does the parent. */ if (relation_is_onerow(childrel)) { add_uniquekey_for_onerow(rel); return; } + /* + * Inspect the unique keys one by one, try reusing them for the + * parent relation. + * + * FIXME This needs more work to handle expressions and not just + * simple Vars. + */ foreach(lc, childrel->uniquekeys) { + ListCell *lc2; + List *parent_exprs = NIL; + bool can_reuse = true; + UniqueKey *ukey = lfirst_node(UniqueKey, lc); AppendRelInfo *appinfo = find_appinfo_by_child(root, childrel->relid); - List *parent_exprs = NIL; - bool can_reuse = true; - ListCell *lc2; + + /* + * XXX Not sure what exactly we do here. Surely we deal with + * expressions at child/parent level elsewhere? Can't we just + * copy the code from there? + */ foreach(lc2, ukey->exprs) { - Var *var = (Var *)lfirst(lc2); + Var *var = (Var *) lfirst(lc2); + /* - * If the expr comes from a expression, it is hard to build the expression - * in parent so ignore that case for now. + * XXX For now this only supports simple Var expressions, + * so if there's a more complex expression we'll not copy + * the unique key to the parent. */ if(!IsA(var, Var)) { can_reuse = false; break; } + /* Convert it to parent var */ - parent_exprs = lappend(parent_exprs, find_parent_var(appinfo, var)); + parent_exprs = lappend(parent_exprs, + find_parent_var(appinfo, var)); } - if (can_reuse) - rel->uniquekeys = lappend(rel->uniquekeys, - makeUniqueKey(parent_exprs, - ukey->multi_nullvals)); + + /* ignore unique keys with complex expressions */ + if (!can_reuse) + continue; + + rel->uniquekeys = lappend(rel->uniquekeys, + makeUniqueKey(parent_exprs, + ukey->multi_nullvals)); } + + return; } - else + + /* + * A parent with multiple child relations. We only care about indexes that + * are in all child relations, so we loop through indexes on the first one + * and check that they exist in the other child relations too. + */ + + childrel = linitial_node(RelOptInfo, childrels); + foreach(lc, childrel->indexlist) { - /* Check for rule 2 */ - 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; + IndexOptInfo *ind = lfirst(lc); + IndexOptInfo *modified_index; - /* - * During simple_copy_indexinfo_to_parent, we need to convert var from - * child var to parent var, index on expression is too complex to handle. - * so ignore it for now. - */ - if (ind->indexprs != NIL) - continue; + /* + * Ignore indexes that are not unique, immediately enforced. Partial + * indexes with mismatched predicate are useless too. + */ + if (!ind->unique || !ind->immediate || + (ind->indpred != NIL && !ind->predOK)) + continue; - modified_index = simple_copy_indexinfo_to_parent(root, 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; + /* + * During simple_copy_indexinfo_to_parent, we need to convert var from + * child var to parent var, index on expression is too complex to handle. + * so ignore it for now. + * + * FIXME We should support indexes on expressions. + */ + if (ind->indexprs != NIL) + continue; - global_uniq_indexlist = lappend(global_uniq_indexlist, modified_index); - } + /* + * Adopt the index definition for the parent. + * + * XXX This seems rather weird. We're constructing "artificial" index + * for the partitioned table (kinda like a global index). Can't we + * just have some simpler struct representing it? + */ + modified_index = simple_copy_indexinfo_to_parent(root, rel, ind); + + /* + * If the unique index doesn't contain partkey, then it is unique + * on this partition only, so it is useless for us. + * + * XXX Can't we do this check before simple_copy_indexinfo_to_parent? + */ + if (!index_constains_partkey(rel, modified_index)) + continue; - if (global_uniq_indexlist != NIL) + global_uniq_indexlist = lappend(global_uniq_indexlist, modified_index); + } + + /* if there are no applicable unique indexes, we're done */ + if (!global_uniq_indexlist) + return; + + /* + * We iterate over the child relations first, and inspect the unique + * indexes for each hild, because this way we can stop early if we + * happen to eliminate all the unique indexes. + */ + foreach(lc, childrels) + { + RelOptInfo *child = lfirst(lc); + + /* skip the first index, which is where we got the list from */ + if (is_first) { - foreach(lc, childrels) - { - RelOptInfo *child = lfirst(lc); - if (is_first) - { - is_first = false; - continue; - } - adjust_partition_unique_indexlist(root, 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); + is_first = false; + continue; } + + /* match the unique keys to indexes on this child */ + adjust_partition_unique_indexlist(root, rel, child, &global_uniq_indexlist); + + /* + * If we have eliminated all unique indexes, no point in looking at + * the remaining child relations. + */ + if (!global_uniq_indexlist) + break; } + + /* Now we have a list of unique index which are exactly same on all child + * relations. Set the UniqueKey just like it is non-partition table. + */ + populate_baserel_uniquekeys(root, rel, global_uniq_indexlist); } /* * populate_distinctrel_uniquekeys + * Update unique keys for relation produced by DISTINCT. + * + * We can keep all unique keys from the input relations, because DISTINCT + * can only remove rows - it can't duplicate them. Also, the DISTINCT clause + * itself is a unique key, so add that. */ void populate_distinctrel_uniquekeys(PlannerInfo *root, @@ -292,11 +434,13 @@ populate_distinctrel_uniquekeys(PlannerInfo *root, { /* 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, @@ -305,54 +449,76 @@ populate_grouprel_uniquekeys(PlannerInfo *root, { Query *parse = root->parse; - bool input_ukey_added = false; ListCell *lc; + /* + * XXX Is this actually valid, before checking fro grouping sets? + * The grouping sets may produce duplicate row even with just a single + * input row, I think. + */ if (relation_is_onerow(inputrel)) { add_uniquekey_for_onerow(grouprel); return; } + + /* + * Bail out if there are grouping sets. + * + * XXX Could we maybe inspect the grouping sets and determine if this + * generates distinct combinations? In some cases that's clearly not + * the case (rollup, cube), but for some simple cases it might. + */ if (parse->groupingSets) return; - /* A Normal group by without grouping set. */ - if (parse->groupClause) + /* It has aggregation but without a group by, so only one row returned */ + if (!parse->groupClause) + add_uniquekey_for_onerow(grouprel); + + /* + * A regular group by, without grouping sets. + * + * Obviously, the whole group clause determines a unique key. But if + * there are smaller unique keys on the input rel, we prefer those + * because those are more flexible. If (a,b) is unique, (a,b,c) is + * unique too. Only when there are no such smaller unique keys, we + * add the unique key derived from the group clause. + */ + foreach(lc, inputrel->uniquekeys) { + UniqueKey *ukey = lfirst_node(UniqueKey, lc); + /* - * Current even the groupby clause is Unique already, but if query has aggref - * We have to create grouprel still. To keep the UnqiueKey short, we will check - * the UniqueKey of input_rel still valid, if so we reuse it. + * Ignore unique keys on the input that are not subset of the + * group clause. We can't use incomplete unique keys. */ - foreach(lc, inputrel->uniquekeys) - { - UniqueKey *ukey = lfirst_node(UniqueKey, lc); - if (list_is_subset(ukey->exprs, grouprel->reltarget->exprs)) - { - grouprel->uniquekeys = lappend(grouprel->uniquekeys, - ukey); - input_ukey_added = true; - } - } - if (!input_ukey_added) - /* - * group by clause must be a super-set of grouprel->reltarget->exprs except the - * aggregation expr, so if such exprs is unique already, no bother to generate - * new uniquekey for group by exprs. - */ - add_uniquekey_from_sortgroups(root, - grouprel, - root->parse->groupClause); + if (!list_is_subset(ukey->exprs, grouprel->reltarget->exprs)) + continue; + + grouprel->uniquekeys = lappend(grouprel->uniquekeys, ukey); } - else - /* It has aggregation but without a group by, so only one row returned */ - add_uniquekey_for_onerow(grouprel); + + /* + * Group clause must be a super-set of of grouprel->reltarget->exprs, + * except for the aggregation expressions. So if we found a smaller + * unique key on the input relation, don't bother adding a unique key + * for the group clause. + */ + if (!grouprel->uniquekeys) + add_uniquekey_from_sortgroups(root, + grouprel, + root->parse->groupClause); } /* * simple_copy_uniquekeys - * Using a function for the one-line code makes us easy to check where we simply - * copied the uniquekey. + * Copy yhe unique keys between relations. + * + * Using a function for the one-line code makes us easy to check where we + * simply copied the uniquekey. + * + * XXX Seems like an overkill, not sure what's the purpose? */ void simple_copy_uniquekeys(RelOptInfo *oldrel, @@ -362,24 +528,27 @@ simple_copy_uniquekeys(RelOptInfo *oldrel, } /* - * populate_unionrel_uniquekeys + * populate_unionrel_uniquekeys + * Determine unique keys for UNION relation. + * + * XXX Does this need to care about UNION vs. UNION ALL? At least in the + * one-row code path? */ void populate_unionrel_uniquekeys(PlannerInfo *root, - RelOptInfo *unionrel) + RelOptInfo *unionrel) { - ListCell *lc; - List *exprs = NIL; + ListCell *lc; + List *exprs = NIL; Assert(unionrel->uniquekeys == NIL); + /* XXX Why are we copying the expressions? */ foreach(lc, unionrel->reltarget->exprs) - { exprs = lappend(exprs, lfirst(lc)); - } + /* SQL: select union select; is valid, we need to handle it here. */ if (exprs == NIL) - /* SQL: select union select; is valid, we need to handle it here. */ add_uniquekey_for_onerow(unionrel); else unionrel->uniquekeys = lappend(unionrel->uniquekeys, @@ -389,6 +558,7 @@ populate_unionrel_uniquekeys(PlannerInfo *root, /* * populate_joinrel_uniquekeys + * Determine unique keys for a join relation. * * populate uniquekeys for joinrel. We will check each relation to see if its * UniqueKey is still valid via innerrel_keeps_unique, if so, we add it to @@ -404,70 +574,99 @@ 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; - bool mergejoin_allowed; - - /* Care about the outerrel relation only for SEMI/ANTI join */ + ListCell *lc, + *lc2; + List *clause_list = NIL; + List *outerrel_ukey_ctx; + List *innerrel_ukey_ctx; + bool inner_onerow, + outer_onerow; + bool mergejoin_allowed; + + /* For SEMI/ANTI join, we care only about the outerrel unique keys. */ if (jointype == JOIN_SEMI || jointype == JOIN_ANTI) { foreach(lc, outerrel->uniquekeys) { UniqueKey *uniquekey = lfirst_node(UniqueKey, lc); + + /* Keep the unique key if it's included in the joinrel. */ if (list_is_subset(uniquekey->exprs, joinrel->reltarget->exprs)) joinrel->uniquekeys = lappend(joinrel->uniquekeys, uniquekey); } + return; } + /* XXX What about JOIN_RIGHT? */ Assert(jointype == JOIN_LEFT || jointype == JOIN_FULL || jointype == JOIN_INNER); - /* Fast path */ + /* + * For regular joins, we need to combine unique keys from both sides + * of the join, to get a new unique key for the join relation. So if + * either side does not have a unique key, bail out. + */ if (innerrel->uniquekeys == NIL || outerrel->uniquekeys == NIL) return; + /* XXX maybe move to the if blocks? Not needed outside. */ 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); + outerrel_ukey_ctx = initialize_uniquecontext_for_joinrel(outerrel); + innerrel_ukey_ctx = initialize_uniquecontext_for_joinrel(innerrel); - clause_list = select_mergejoin_clauses(root, joinrel, outerrel, innerrel, + clause_list = select_mergejoin_clauses(root, + joinrel, outerrel, innerrel, restrictlist, jointype, &mergejoin_allowed); - if (innerrel_keeps_unique(root, innerrel, outerrel, clause_list, true /* reverse */)) + /* + * XXX Seems a bit weird that it's called innerrel_keeps_unique but we + * seem to use it in both directions. Or what's the "reverse" for? The + * "reverse" name is not particularly descriptive. + */ + if (innerrel_keeps_unique(root, innerrel, outerrel, clause_list, true)) { - bool outer_impact = jointype == JOIN_FULL; + bool outer_impact = (jointype == JOIN_FULL); + + /* Inspect unique keys on the outer relation. */ foreach(lc, outerrel_ukey_ctx) { UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc); + /* + * If the output of the join does not include all the parts of the + * unique key, it's useless, so mark it accordingly and ignore it. + */ 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. + /* + * When the outer relation has one row, and the unique key is not + * duplicated after join, so the joinrel will still have just one + * row unless the jointype == JOIN_FULL. In that case we're done, + * it's the strictest unique key possible. + * + * If it's one-row with a JOIN_FULL, it might produce multiple + * rows with NULLs, so set multi_nullvals. We also need to set + * the exprs correctly since it can't be NIL any more. + * + * For other cases (not one-row relation), we just reuse the + * unique key, but we may need to tweak the multi_nullvals. */ if (outer_onerow && !outer_impact) { add_uniquekey_for_onerow(joinrel); return; } - else if (outer_onerow) + else if (outer_onerow) /* one-row and FULL join */ { - /* - * The onerow outerrel becomes multi rows and multi_nullvals - * will be changed to true. We also need to set the exprs correctly since it - * can't be NIL any more. - */ ListCell *lc2; + foreach(lc2, get_exprs_from_uniquekey(root, joinrel, outerrel, NULL)) { joinrel->uniquekeys = lappend(joinrel->uniquekeys, @@ -485,18 +684,38 @@ populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel, joinrel->uniquekeys = lappend(joinrel->uniquekeys, ctx->uniquekey); } + + /* + * Mark the unique key as added, so that we can ignore it later + * when combining unique keys from both sides of the join. + */ ctx->added_to_joinrel = true; } } + /* + * XXX Seems this actually checks if "outerrel keeps unique" so the name + * is misleading. Of maybe it's the previous block, not sure. + * + * XXX So why does this consider JOIN_FULL and JOIN_LEFT, while the previous + * block only cares about JOIN_FULL? + * + * XXX This is almost exact copy of the previous block, so maybe make it + * a separate function and just call it twice? + */ if (innerrel_keeps_unique(root, outerrel, innerrel, clause_list, false)) { - bool outer_impact = jointype == JOIN_FULL || jointype == JOIN_LEFT;; + bool outer_impact = (jointype == JOIN_FULL || jointype == JOIN_LEFT); + /* Inspect unique keys on the inner relation. */ foreach(lc, innerrel_ukey_ctx) { UniqueKeyContext ctx = (UniqueKeyContext)lfirst(lc); + /* + * If the output of the join does not include all the parts of the + * unique key, it's useless, so mark it accordingly and ignore it. + */ if (!list_is_subset(ctx->uniquekey->exprs, joinrel->reltarget->exprs)) { ctx->useful = false; @@ -529,29 +748,52 @@ populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel, ctx->uniquekey); } + + /* + * Mark the unique key as added, so that we can ignore it later + * when combining unique keys from both sides of the join. + */ 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. + * XXX What if either of the previous two conditions did not match? In + * that case we haven't updated the useful flag, and maybe the unique + * key is not useful, but we don't know, right? So we should not be + * using it in the next loop. Or maybe we should evaluate the flag + * before the loops. + */ + + /* + * The combination of the UniqueKey from both sides is unique as well, + * regardless of the join type. But don't bother to add it if its + * subset has been added to joinrel already or when it's not useful for + * the joinrel. + * + * XXX Maybe we should have a flag that both sides have useful keys? + * Or maybe the loops are short/cheap? */ foreach(lc, outerrel_ukey_ctx) { UniqueKeyContext ctx1 = (UniqueKeyContext) lfirst(lc); + + /* when not useful or already added to the joinrel, skip it */ if (ctx1->added_to_joinrel || !ctx1->useful) continue; + foreach(lc2, innerrel_ukey_ctx) { UniqueKeyContext ctx2 = (UniqueKeyContext) lfirst(lc2); + + /* when not useful or already added to the joinrel, skip it */ if (ctx2->added_to_joinrel || !ctx2->useful) continue; + + /* If we add a onerow UniqueKey, we don't need another key. */ if (add_combined_uniquekey(root, joinrel, outerrel, innerrel, ctx1->uniquekey, ctx2->uniquekey, jointype)) - /* If we set a onerow UniqueKey to joinrel, we don't need other. */ return; } } @@ -560,8 +802,9 @@ populate_joinrel_uniquekeys(PlannerInfo *root, RelOptInfo *joinrel, /* * convert_subquery_uniquekeys + * Covert the UniqueKey in subquery to outer relation. * - * Covert the UniqueKey in subquery to outer relation. + * XXX Explain what exactly does the conversion do? */ void convert_subquery_uniquekeys(PlannerInfo *root, RelOptInfo *currel, @@ -618,12 +861,14 @@ void convert_subquery_uniquekeys(PlannerInfo *root, /* * innerrel_keeps_unique + * Check if Unique key on the innerrel is valid after join. * - * 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. + * 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. + * + * XXX Misleading name? We seem to use it for "outerrel_keeps_unique" too. */ static bool innerrel_keeps_unique(PlannerInfo *root, @@ -634,26 +879,32 @@ innerrel_keeps_unique(PlannerInfo *root, { ListCell *lc, *lc2, *lc3; + /* XXX probably not needed, duplicate with the check in the caller + * (populate_joinrel_uniquekeys). But it's cheap. */ 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; + 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; @@ -677,22 +928,37 @@ innerrel_keeps_unique(PlannerInfo *root, /* * relation_is_onerow - * Check if it is a one-row relation by checking UniqueKey. + * Check if it is a one-row relation by checking UniqueKey. + * + * The one-row is a special case - there has to be just a single unique key, + * with no expressions. */ bool relation_is_onerow(RelOptInfo *rel) { UniqueKey *ukey; - if (rel->uniquekeys == NIL) + + /* there has to be exactly one unique key */ + if (list_length(rel->uniquekeys) != 1) return false; + ukey = linitial_node(UniqueKey, rel->uniquekeys); - return ukey->exprs == NIL && list_length(rel->uniquekeys) == 1; + + /* the unique key must have no expressions */ + return (ukey->exprs == NIL); } /* * 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. + * Determines if the relation has unique key for a list of expressions. + * + * Returns true iff we can prove that the relation cannot return multiple rows + * with the same values in the provided expression. + * + * allow_multinulls determines whether we allow multiple NULL values or not. + * + * The special "one-row" unique key is considered incompatible with all + * possible expressions. */ bool relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel, @@ -710,20 +976,39 @@ relation_has_uniquekeys_for(PlannerInfo *root, RelOptInfo *rel, 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; } /* * get_exprs_from_uniqueindex + * Return a list of expressions from a unique index. + * + * Provided with a list of expressions and opclass families, we try to match + * it to the index. If useful, we produce a list of index expressions (subset + * of the list we provided). + * + * We simply walk through the index expressions, and for each expression we + * check three things: * - * Return a list of exprs which is unique. set useful to false if this - * unique index is not useful for us. + * 1) If there's a matching (expr = Const) clause, we can simply ignore the + * expressions. Unique index on (a,b,c) guarantees uniqueness on (a,b) when + * there's condition (c=1). + * + * 2) Check that the index expression is present in the relation we're + * dealing with. If not, the unique key would be useless anyway, and the + * index can't produce unique key. + * + * XXX Shouldn't it be enough to return NULL when the index is not useful? + * The extra flag seems a bit unnecessary. */ static List * get_exprs_from_uniqueindex(IndexOptInfo *unique_index, @@ -743,18 +1028,19 @@ get_exprs_from_uniqueindex(IndexOptInfo *unique_index, indexpr_item = list_head(unique_index->indexprs); for(c = 0; c < unique_index->ncolumns; c++) { - int attr = unique_index->indexkeys[c]; - Expr *expr; - bool matched_const = false; - ListCell *lc1, *lc2; + int attr = unique_index->indexkeys[c]; + Expr *expr; + bool matched_const = false; + ListCell *lc1, *lc2; - if(attr > 0) + if (attr > 0) { + /* regular attribute, just use the expression from index tlist */ expr = list_nth_node(TargetEntry, unique_index->indextlist, c)->expr; } else if (attr == 0) { - /* Expression index */ + /* expression from the index */ expr = lfirst(indexpr_item); indexpr_item = lnext(unique_index->indexprs, indexpr_item); } @@ -764,29 +1050,43 @@ get_exprs_from_uniqueindex(IndexOptInfo *unique_index, Assert(false); } + /* should have a valid expression now */ + Assert(expr); + /* - * Check index_col = Const case with regarding to opfamily checking - * If we can remove the index_col from the final UniqueKey->exprs. + * Check if there's (index_col = Const) condition, and that it's using + * a compatible opfamily. If yes, we can remove the index_col from the + * final UniqueKey->exprs, because the value is constant (so removing + * it can't introduce duplicities). */ forboth(lc1, const_exprs, lc2, const_expr_opfamilies) { - if (list_member_oid((List *)lfirst(lc2), unique_index->opfamily[c]) - && match_index_to_operand((Node *) lfirst(lc1), c, unique_index)) + List *opfamilies = (List *) lfirst(lc2); + Node *cexpr = (Node *) lfirst(lc1); + + if (list_member_oid(opfamilies, unique_index->opfamily[c]) && + match_index_to_operand(cexpr, c, unique_index)) { matched_const = true; break; } } + /* it's constant, so ignore the expression */ if (matched_const) continue; - /* Check if the indexed expr is used in rel */ + /* + * Check if the indexed expr is used in rel. We do this after the + * (col = Const) check, because nn expression may be in a a restrict + * clause and not in the reltarget. So we don't want to rule out an + * index unnecessarily. + */ if (attr > 0) { /* - * Normal Indexed column, if the col is not used, then the index is useless - * for uniquekey. + * Normal indexed column, if the col is not used, then the index + * is useless for uniquekey. */ attr -= FirstLowInvalidHeapAttributeNumber; @@ -806,67 +1106,85 @@ get_exprs_from_uniqueindex(IndexOptInfo *unique_index, /* check not null property. */ if (attr == 0) { - /* We never know if a expression yields null or not */ + /* We never know if an expression yields null or not */ *multi_nullvals = true; } - else if (!bms_is_member(attr, unique_index->rel->notnullattrs) - && !bms_is_member(0 - FirstLowInvalidHeapAttributeNumber, - unique_index->rel->notnullattrs)) + else if (!bms_is_member(attr, unique_index->rel->notnullattrs) && + !bms_is_member(0 - FirstLowInvalidHeapAttributeNumber, + unique_index->rel->notnullattrs)) { *multi_nullvals = true; } exprs = lappend(exprs, expr); } + return exprs; } /* * 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 exprs = NIL and overwrites all the other UniqueKey on this RelOptInfo - * since this one has strongest semantics. + * Create a special unique key signifying that the rel has one row. + * + * If we are sure that the relation only returns one row (it might return + * no rows, but we still consider that unique), then all the columns are + * trivially unique. + * + * However we don't need to create UniqueKey with every column, we just + * set exprs = NIL, because that's easier to identify. We don't want to + * add unnecessary unique keys (such that we already have a unique key + * for a subset of the expressions), and with (exprs == NIL) we can just + * assume we have one unique key for each column in the rel. + * + * We discard all other unique keys, since it has the strongest semantics. */ void add_uniquekey_for_onerow(RelOptInfo *rel) { /* - * We overwrite the previous UniqueKey on purpose since this one has the - * strongest semantic. + * We overwrite the previous UniqueKey on purpose since this one has + * the strongest semantic (all other unique keys are implied by it). */ rel->uniquekeys = list_make1(makeUniqueKey(NIL, false)); } /* - * initililze_uniquecontext_for_joinrel - * Return a List of UniqueKeyContext for an inputrel + * initialize_uniquecontext_for_joinrel + * Return a List of UniqueKeyContext for an inputrel. */ static List * -initililze_uniquecontext_for_joinrel(RelOptInfo *inputrel) +initialize_uniquecontext_for_joinrel(RelOptInfo *inputrel) { - List *res = NIL; - ListCell *lc; - foreach(lc, inputrel->uniquekeys) + 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; } - /* * get_exprs_from_uniquekey - * Unify the way of get List of exprs from a one-row UniqueKey or - * normal UniqueKey. for the onerow case, every expr in rel1 is a valid - * UniqueKey. Return a List of exprs. + * Extract expressions that are part of a unique key. + * + * The meaning of the result is a bit different in regular and one-row cases. + * For the regular case, the list of expressions form a single unique key, + * i.e. the combination of values is unique. + * + * For the one-row case, each individual expression is known to be unique + * (simply because in a single row everything is unique). * * rel1: The relation which you want to get the exprs. * ukey: The UniqueKey you want to get the exprs. @@ -875,27 +1193,29 @@ static List * get_exprs_from_uniquekey(PlannerInfo *root, RelOptInfo *joinrel, RelOptInfo *rel1, UniqueKey *ukey) { - ListCell *lc; - bool onerow = rel1 != NULL && relation_is_onerow(rel1); + ListCell *lc; + List *res = NIL; + bool onerow = (rel1 != NULL) && relation_is_onerow(rel1); - List *res = NIL; + /* We require at least one of those to be true. */ Assert(onerow || ukey); - if (onerow) - { - /* Only cares about the exprs still exist in joinrel */ - foreach(lc, joinrel->reltarget->exprs) - { - Bitmapset *relids = pull_varnos(root, lfirst(lc)); - if (bms_is_subset(relids, rel1->relids)) - { - res = lappend(res, list_make1(lfirst(lc))); - } - } - } - else + + /* if not a one-row unique key, just return the key's expressions */ + if (!onerow) + return list_make1(ukey->exprs); + + /* + * If it's a one-row relation, we simply extract the expressions that + * still exist in the reltarget. + */ + foreach(lc, joinrel->reltarget->exprs) { - res = list_make1(ukey->exprs); + Bitmapset *relids = pull_varnos(root, lfirst(lc)); + + if (bms_is_subset(relids, rel1->relids)) + res = lappend(res, list_make1(lfirst(lc))); } + return res; } @@ -910,55 +1230,67 @@ get_exprs_from_uniquekey(PlannerInfo *root, RelOptInfo *joinrel, /* * index_constains_partkey - * return true if the index contains the partiton key. + * Determines if the index includes a partition key. + * + * XXX Surely we already have a code doing this already? E.g. when creating + * a unique index on a partitioned table we define that. */ static bool -index_constains_partkey(RelOptInfo *partrel, IndexOptInfo *ind) +index_constains_partkey(RelOptInfo *partrel, IndexOptInfo *ind) { ListCell *lc; int i; + Assert(IS_PARTITIONED_REL(partrel)); Assert(partrel->part_scheme->partnatts > 0); for(i = 0; i < partrel->part_scheme->partnatts; i++) { - Node *part_expr = linitial(partrel->partexprs[i]); - bool found_in_index = false; + Node *part_expr = linitial(partrel->partexprs[i]); + bool found_in_index = false; + foreach(lc, ind->indextlist) { - Expr *index_expr = lfirst_node(TargetEntry, lc)->expr; + 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 + * Compare two indexes to determine if they are the same. + * + * We need to do this because simple_copy_indexinfo_to_parent does change + * some elements. So this is not exactly the same as calling 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) + * XXX I wonder if we could simply use equal(), somehow? In fact, we should + * probably build something much simpler than IndexOptInfo, just enough to + * do the checks. */ 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(get_tlist_exprs(ind1->indextlist, true), - get_tlist_exprs(ind2->indextlist, true)); + 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(get_tlist_exprs(ind1->indextlist, true), + get_tlist_exprs(ind2->indextlist, true)))); } @@ -981,11 +1313,21 @@ simple_indexinfo_equal(IndexOptInfo *ind1, IndexOptInfo *ind2) /* - * 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. + * simple_copy_indexinfo_to_parent + * Copy index info from child to parent, with necessary tweaks. + * + * We use this copy to check: + * + * 1. If the same/matching index exists in all the childrels. * 2. If the parentrel->reltarget/basicrestrict info matches this index. + * + * XXX IMHO we should probably build something much simpler than a full + * IndexOptInfo copy, just enough to do the checks. + * + * XXX The fact that we copy so much data seems wrong, and having to + * define macros from copyfuncs.c seems like a very suspicious thing. + * One reason is that IndeOptInfo is fairly large struct, especially + * with all the fields, and we allocate it very often. */ static IndexOptInfo * simple_copy_indexinfo_to_parent(PlannerInfo *root, @@ -1027,20 +1369,24 @@ simple_copy_indexinfo_to_parent(PlannerInfo *root, /* * adjust_partition_unique_indexlist + * Checks and eliminates indexes that do not exist on the child relation. * - * 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. + * Walks the list of unique indexes, and eliminates those that don't match + * the child relation (i.e. where a matching child index does not exist). + * This is used to iteratively filter the list of candidate unique keys. + * + * After processing all child relations, the list contains only indexes that + * exist in all the child relations. */ static void adjust_partition_unique_indexlist(PlannerInfo *root, RelOptInfo *parentrel, RelOptInfo *childrel, - List **global_unique_indexes) + List **indexes) { ListCell *lc, *lc2; - foreach(lc, *global_unique_indexes) + + foreach(lc, *indexes) { IndexOptInfo *g_ind = lfirst_node(IndexOptInfo, lc); bool found_in_child = false; @@ -1049,23 +1395,45 @@ adjust_partition_unique_indexlist(PlannerInfo *root, { 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)) + + /* + * Ignore child indexes that can't possibly match (not unique or + * immediate, etc.) + * + * XXX We do these checks in many places, so maybe turn it into + * a reusable macro? + */ + if ((!p_ind->unique) || (!p_ind->immediate) || + (p_ind->indpred != NIL) && (!p_ind->predOK)) continue; + + /* + * XXX This seems possibly quite expensive. Imagine there are many + * child relations, with a bunch of unique indexes each. Then this + * generates a copy for each unique index in each child relation, + * something like O(N^2/2) copies. + */ p_ind_copy = simple_copy_indexinfo_to_parent(root, parentrel, p_ind); + + /* Found a matching index for the child relation, we're done. */ if (simple_indexinfo_equal(p_ind_copy, g_ind)) { found_in_child = true; break; } } + + /* No matching index in the child, so remove it from the list. */ if (!found_in_child) - /* The index doesn't exist in childrel, remove it from global_unique_indexes */ - *global_unique_indexes = foreach_delete_current(*global_unique_indexes, lc); + *indexes = foreach_delete_current(*indexes, lc); } } -/* Helper function for groupres/distinctrel */ +/* + * Helper function for groupres/distinctrel + * + * FIXME Not sure about this. + */ static void add_uniquekey_from_sortgroups(PlannerInfo *root, RelOptInfo *rel, List *sortgroups) { @@ -1073,27 +1441,32 @@ add_uniquekey_from_sortgroups(PlannerInfo *root, RelOptInfo *rel, List *sortgrou List *exprs; /* - * XXX: If there are some vars which is not in current levelsup, the semantic is - * imprecise, should we avoid it or not? levelsup = 1 is just a demo, maybe we need to - * check every level other than 0, if so, looks we have to write another - * pull_var_walker. + * XXX: If there are some vars which are not in the current levelsup, the + * semantic is imprecise, should we avoid it or not? levelsup = 1 is just + * a demo, maybe we need to check every level other than 0, if so, looks + * we have to write another pull_var_walker. */ List *upper_vars = pull_vars_of_level((Node*)sortgroups, 1); if (upper_vars != NIL) return; + /* sortgroupclause can't be multi_nullvals */ exprs = get_sortgrouplist_exprs(sortgroups, parse->targetList); rel->uniquekeys = lappend(rel->uniquekeys, - makeUniqueKey(exprs, - false /* sortgroupclause can't be multi_nullvals */)); + makeUniqueKey(exprs, false)); } /* * add_combined_uniquekey - * The combination of both UniqueKeys is a valid UniqueKey for joinrel no matter - * the jointype. + * Add a unique key for a join, combined from keys on inner/outer side. + * + * The combination of both UniqueKeys is a valid UniqueKey for joinrel no + * matter what's the exact jointype. + * + * Returns true if the unique key is "one-row" variant, so that the caller + * can stop considering further combinations. */ bool add_combined_uniquekey(PlannerInfo *root, @@ -1104,32 +1477,47 @@ add_combined_uniquekey(PlannerInfo *root, UniqueKey *inner_ukey, JoinType jointype) { + bool multi_nullvals; + ListCell *lc1, *lc2; - ListCell *lc1, *lc2; - - /* Either side has multi_nullvals or we have outer join, - * the combined UniqueKey has multi_nullvals */ - bool multi_nullvals = outer_ukey->multi_nullvals || + /* + * If either side has multi_nullvals, or we are dealing with an outer join, + * the combined UniqueKey has multi_nullvals too. + */ + multi_nullvals = outer_ukey->multi_nullvals || inner_ukey->multi_nullvals || IS_OUTER_JOIN(jointype); /* The only case we can get onerow joinrel after join */ - if (relation_is_onerow(outer_rel) - && relation_is_onerow(inner_rel) - && jointype == JOIN_INNER) + if (relation_is_onerow(outer_rel) && + relation_is_onerow(inner_rel) && + jointype == JOIN_INNER) { add_uniquekey_for_onerow(joinrel); return true; } + /* + * XXX Isn't this wrong? Why is it combining expressions that are part + * of the two unique keys? Imagine we have outer unique key on (a1, a2) + * and inner outer key on (b1, b2). Then this adds four unique keys + * for the join (a1,b1), (a1,b2), (a2,b1) and (a2,b2). Shouldn't it + * just add (a1,a2,b1,b2)? + */ foreach(lc1, get_exprs_from_uniquekey(root, joinrel, outer_rel, outer_ukey)) { + /* + * XXX This calls get_exprs_from_uniquekey repeatedly for each outer + * loop. Maybe we should calculate it just once before the loop. + */ foreach(lc2, get_exprs_from_uniquekey(root, 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)); } } + return false; } diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 8d8e493f5c..f29b65c07b 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -2387,6 +2387,7 @@ grouping_planner(PlannerInfo *root, bool inheritance_update, add_path(final_rel, path); } + /* XXX comment? can we simply just copy the unique keys to the final relation? */ simple_copy_uniquekeys(current_rel, final_rel); /* @@ -3902,7 +3903,9 @@ create_grouping_paths(PlannerInfo *root, set_cheapest(grouped_rel); + /* XXX does this apply to grouping sets too? */ populate_grouprel_uniquekeys(root, grouped_rel, input_rel); + return grouped_rel; } @@ -4625,7 +4628,10 @@ create_window_paths(PlannerInfo *root, /* Now choose the best path(s) */ set_cheapest(window_rel); + + /* XXX comment? */ simple_copy_uniquekeys(input_rel, window_rel); + return window_rel; } @@ -4939,7 +4945,10 @@ create_distinct_paths(PlannerInfo *root, /* Now choose the best path(s) */ set_cheapest(distinct_rel); + + /* XXX comment */ populate_distinctrel_uniquekeys(root, input_rel, distinct_rel); + return distinct_rel; } @@ -5200,6 +5209,7 @@ create_ordered_paths(PlannerInfo *root, */ Assert(ordered_rel->pathlist != NIL); + /* XXX comment */ 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 b7626545bf..72a3f3c598 100644 --- a/src/backend/optimizer/prep/prepunion.c +++ b/src/backend/optimizer/prep/prepunion.c @@ -691,6 +691,7 @@ generate_union_paths(SetOperationStmt *op, PlannerInfo *root, /* Add the UniqueKeys */ populate_unionrel_uniquekeys(root, result_rel); + return result_rel; } diff --git a/src/backend/optimizer/util/inherit.c b/src/backend/optimizer/util/inherit.c index 3eec1f4d74..c9829c5fc4 100644 --- a/src/backend/optimizer/util/inherit.c +++ b/src/backend/optimizer/util/inherit.c @@ -755,6 +755,7 @@ apply_child_basequals(PlannerInfo *root, RelOptInfo *parentrel, pseudoconstant, rinfo->security_level, NULL, NULL, NULL); + /* XXX This is a bit weird, doing this outside make_restrictinfo */ child_rinfo->mergeopfamilies = rinfo->mergeopfamilies; childquals = lappend(childquals, child_rinfo); /* track minimum security level among child quals */ -- 2.30.2 --------------F495F6B18672582269F00FF9 Content-Type: text/x-patch; charset=UTF-8; name="0005-Extend-UniqueKeys-20210317.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="0005-Extend-UniqueKeys-20210317.patch"