diff-v29-v30.txt
text/plain
Filename: diff-v29-v30.txt
Type: text/plain
Part: 0
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 51b16d4f168..0395cee9a7c 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -3114,7 +3114,7 @@ add_child_rel_equivalences(PlannerInfo *root,
/*
* We save the knowledge that 'child_em' can be translated
* using 'child_rel'. This knowledge is useful for
- * add_transformed_child_version() to find child members from
+ * iterate_child_rel_equivalences() to find child members from
* the given Relids.
*/
cur_em->em_child_relids = bms_add_member(cur_em->em_child_relids,
@@ -3209,6 +3209,7 @@ add_child_join_rel_equivalences(PlannerInfo *root,
Expr *child_expr;
Relids new_relids;
EquivalenceMember *child_em;
+ int j;
if (parent_joinrel->reloptkind == RELOPT_JOINREL)
{
@@ -3248,12 +3249,39 @@ add_child_join_rel_equivalences(PlannerInfo *root,
/*
* We save the knowledge that 'child_em' can be translated
* using 'child_joinrel'. This knowledge is useful for
- * add_transformed_child_version() to find child members from
+ * iterate_child_rel_equivalences() to find child members from
* the given Relids.
*/
cur_em->em_child_joinrel_relids =
bms_add_member(cur_em->em_child_joinrel_relids,
child_joinrel->join_rel_list_index);
+
+ /*
+ * Update the corresponding inverted indexes.
+ */
+ j = -1;
+ while ((j = bms_next_member(child_joinrel->relids, j)) >= 0)
+ {
+ EquivalenceClassIndexes *indexes =
+ &root->eclass_indexes_array[j];
+
+ /*
+ * We do not need to update the inverted index of the top
+ * parent relations. This is because EquivalenceMembers
+ * that have only such parent relations as em_relids are
+ * already present in the ec_members, and so cannot be
+ * candidates for additional iteration by
+ * iterate_child_rel_equivalences(). Since the function
+ * needs EquivalenceMembers whose em_relids has child
+ * relations, skipping the update of this inverted index
+ * allows for faster iteration.
+ */
+ if (root->top_parent_relid_array[j] == -1)
+ continue;
+ indexes->joinrel_indexes =
+ bms_add_member(indexes->joinrel_indexes,
+ child_joinrel->join_rel_list_index);
+ }
}
}
}
@@ -3316,7 +3344,7 @@ add_setop_child_rel_equivalences(PlannerInfo *root, RelOptInfo *child_rel,
/*
* We save the knowledge that 'child_em' can be translated using
* 'child_rel'. This knowledge is useful for
- * add_transformed_child_version() to find child members from the
+ * iterate_child_rel_equivalences() to find child members from the
* given Relids.
*/
parent_em->em_child_relids =
@@ -3449,8 +3477,10 @@ add_transformed_child_version(EquivalenceChildMemberIterator *it,
/*
* iterate_child_rel_equivalences
- * Add transformed EquivalenceMembers referencing child rels in the given
- * child_relids to the iterator.
+ * Add child EquivalenceMembers whose em_relids is a subset of the given
+ * 'child_relids' to the iterator. Note that this function may add false
+ * positives, so callers must check that the members that this function adds
+ * satisfy the desired condition.
*
* The transformation is done in add_transformed_child_version().
*/
@@ -3461,9 +3491,6 @@ iterate_child_rel_equivalences(EquivalenceChildMemberIterator *it,
EquivalenceMember *parent_em,
Relids child_relids)
{
- int i;
- Relids matching_relids;
-
/* The given EquivalenceMember should be parent */
Assert(!parent_em->em_is_child);
@@ -3473,46 +3500,111 @@ iterate_child_rel_equivalences(EquivalenceChildMemberIterator *it,
* is done in add_child_rel_equivalences() and
* add_child_join_rel_equivalences(). To retrieve child EquivalenceMembers
* of some parent, we need to know which RelOptInfos have such child
- * members. This information is stored in indexes named em_child_relids
- * and em_child_joinrel_relids.
+ * members. We can know this information using indexes named
+ * EquivalenceMember->em_child_relids,
+ * EquivalenceMember->em_child_joinrel_relids, and
+ * EquivalenceClassIndexes->joinrel_indexes.
+ *
+ * We use an inverted index mechanism to quickly iterate over the members
+ * whose em_relids is a subset of the given 'child_relids'. The inverted
+ * indexes store RelOptInfo indices that have EquivalenceMembers
+ * mentioning them. Taking the union of these indexes allows to find which
+ * RelOptInfos have the EquivalenceMember we are looking for. With this
+ * method, the em_relids of the newly iterated ones overlap the given
+ * 'child_relids', but may not be subsets, so the caller must check that
+ * they satisfy the desired condition.
*
- * This function iterates over the child EquivalenceMembers that reference
- * the given 'child_relids'. To do this, we first intersect 'child_relids'
- * with these indexes. The result contains Relids of RelOptInfos that have
- * child EquivalenceMembers we want to retrieve. Then we get the child
- * members from the RelOptInfos using add_transformed_child_version().
+ * The above comments are about joinrels, and for simple rels, this
+ * mechanism is simpler. It is sufficient to simply add the child
+ * EquivalenceMembers of RelOptInfo to the iterator.
*
- * We need to do these steps for each of the two indexes.
+ * We need to perform these steps for each of the two types of relations.
*/
/*
* First, we translate simple rels.
*/
- matching_relids = bms_intersect(parent_em->em_child_relids,
- child_relids);
- i = -1;
- while ((i = bms_next_member(matching_relids, i)) >= 0)
+ if (!bms_is_empty(parent_em->em_child_relids))
{
- /* Add transformed child version for this child rel */
- RelOptInfo *child_rel = root->simple_rel_array[i];
+ Relids matching_relids;
+ int i;
+
+ /* Step 1: Get simple rels' Relids that have wanted EMs. */
+ matching_relids = bms_intersect(parent_em->em_child_relids,
+ child_relids);
- Assert(child_rel != NULL);
- add_transformed_child_version(it, root, ec, parent_em, child_rel);
+ /* Step 2: Fetch wanted EMs. */
+ i = -1;
+ while ((i = bms_next_member(matching_relids, i)) >= 0)
+ {
+ RelOptInfo *child_rel = root->simple_rel_array[i];
+
+ Assert(child_rel != NULL);
+ add_transformed_child_version(it, root, ec, parent_em, child_rel);
+ }
+ bms_free(matching_relids);
}
- bms_free(matching_relids);
/*
* Next, we try to translate join rels.
*/
- i = -1;
- while ((i = bms_next_member(parent_em->em_child_joinrel_relids, i)) >= 0)
+ if (!bms_is_empty(parent_em->em_child_joinrel_relids))
{
- /* Add transformed child version for this child join rel */
- RelOptInfo *child_joinrel =
- list_nth_node(RelOptInfo, root->join_rel_list, i);
+ Bitmapset *matching_indexes;
+ int i;
+
+ /* Step 1: Get join rels' indices that have wanted EMs. */
+ i = -1;
+ matching_indexes = NULL;
+ while ((i = bms_next_member(child_relids, i)) >= 0)
+ {
+ EquivalenceClassIndexes *indexes = &root->eclass_indexes_array[i];
+
+ matching_indexes =
+ bms_add_members(matching_indexes, indexes->joinrel_indexes);
+ }
+ matching_indexes = bms_int_members(matching_indexes,
+ parent_em->em_child_joinrel_relids);
- Assert(child_joinrel != NULL);
- add_transformed_child_version(it, root, ec, parent_em, child_joinrel);
+ /* Step 2: Fetch wanted EMs. */
+ i = -1;
+ while ((i = bms_next_member(matching_indexes, i)) >= 0)
+ {
+ RelOptInfo *child_joinrel =
+ list_nth_node(RelOptInfo, root->join_rel_list, i);
+
+ Assert(child_joinrel != NULL);
+
+ /*
+ * If this joinrel's Relids is not a subset of the given one, then
+ * the child EquivalenceMembers it holds should never be a subset
+ * either.
+ */
+ if (bms_is_subset(child_joinrel->relids, child_relids))
+ add_transformed_child_version(it, root, ec, parent_em, child_joinrel);
+#ifdef USE_ASSERT_CHECKING
+ else
+ {
+ /*
+ * Verify that the above comment is correct.
+ *
+ * NOTE: We may remove this assertion after the beta process.
+ */
+
+ ListCell *lc;
+
+ foreach(lc, child_joinrel->eclass_child_members)
+ {
+ EquivalenceMember *child_em = lfirst_node(EquivalenceMember, lc);
+
+ if (child_em->em_parent != parent_em)
+ continue;
+ Assert(!bms_is_subset(child_em->em_relids, child_relids));
+ }
+ }
+#endif
+ }
+ bms_free(matching_indexes);
}
}
@@ -4040,11 +4132,12 @@ eclass_rinfo_iterator_next(RestrictInfoIterator *iter)
++(iter->index);
bitnum = iter->index % BITS_PER_BITMAPWORD;
mask = (~(bitmapword) 0) << bitnum;
+ w = iter->last_word & mask;
/*
* Do we need to consume a new word?
*/
- if (bitnum == 0 || (iter->last_word & mask) == 0)
+ if (bitnum == 0 || w == 0)
{
/*
* Yes, we need a new word.
@@ -4114,8 +4207,7 @@ eclass_rinfo_iterator_next(RestrictInfoIterator *iter)
if (word != 0)
{
/* Yes, we find new ones. */
- iter->last_word = word;
- mask = (~(bitmapword) 0);
+ w = iter->last_word = word;
break;
}
/* No, we need to consume more word */
@@ -4123,9 +4215,8 @@ eclass_rinfo_iterator_next(RestrictInfoIterator *iter)
}
/*
- * Here, 'iter->last_word' must have a new member. We get it.
+ * Here, 'iter->last_word' or 'w' must have a new member. We get it.
*/
- w = iter->last_word & mask;
Assert(w != 0);
iter->index =
iter->wordnum * BITS_PER_BITMAPWORD + bmw_rightmost_one_pos(w);
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 35af63bb399..cef24c10459 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -1590,11 +1590,15 @@ typedef struct
* EquivalenceClassIndexes
*
* As mentioned in the EquivalenceClass comment, we introduce a
- * bitmapset-based indexing mechanism for faster lookups of RestrictInfo. This
- * struct exists for each relation and holds the corresponding indexes.
+ * bitmapset-based indexing mechanism for faster lookups of child
+ * EquivalenceMembers and RestrictInfos. This struct exists for each relation
+ * and holds the corresponding indexes.
*/
typedef struct EquivalenceClassIndexes
{
+ Bitmapset *joinrel_indexes; /* Indexes in PlannerInfo's join_rel_list
+ * list for RelOptInfos that mention this
+ * relation */
Bitmapset *source_indexes; /* Indexes in PlannerInfo's eq_sources list
* for RestrictInfos that mention this
* relation */