agora inbox for [email protected]
help / color / mirror / Atom feedFrom: Tomas Vondra <[email protected]>
Subject: [PATCH 04/10] review
Date: Tue, 16 Mar 2021 19:26:40 +0100
---
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"
view thread (53+ messages) latest in thread
reply
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: [email protected]
Cc: [email protected]
Subject: Re: [PATCH 04/10] review
In-Reply-To: <no-message-id-1880318@localhost>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox