Re: Performance issue in foreign-key-aware join estimation

David Rowley <david.rowley@2ndquadrant.com> writes:
> Attaching the original patch again so the commitfest bot gets off my
> back about the other one not applying.

Pushed that one.  I'm interested by the "POC" patch, but I agree
that it'd take some research to show that it isn't a net negative
for simple queries.  It sounds like you're not really interested
in pursuing that right now?

Anyway, I rebased the POC patch up to HEAD, just in case anyone
still wants to play with it.

            regards, tom lane

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 65302fe..2ffa00c 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2351,6 +2351,7 @@ _outEquivalenceClass(StringInfo str, const EquivalenceClass *node)
     WRITE_NODE_FIELD(ec_sources);
     WRITE_NODE_FIELD(ec_derives);
     WRITE_BITMAPSET_FIELD(ec_relids);
+    WRITE_BITMAPSET_FIELD(ec_allrelids);
     WRITE_BOOL_FIELD(ec_has_const);
     WRITE_BOOL_FIELD(ec_has_volatile);
     WRITE_BOOL_FIELD(ec_below_outer_join);
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 0debac7..c5888b8 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -216,6 +216,8 @@ make_one_rel(PlannerInfo *root, List *joinlist)
     }
     root->total_table_pages = total_pages;

+    root->eq_index = create_eclass_index(root, EQUIVALANCE_IDX_MULTI_MEMBER);
+
     /*
      * Generate access paths for each base rel.
      */
@@ -226,6 +228,9 @@ make_one_rel(PlannerInfo *root, List *joinlist)
      */
     rel = make_rel_from_joinlist(root, joinlist);

+    free_eclass_index(root->eq_index);
+    root->eq_index = NULL;
+
     /*
      * The result should join all and only the query's base rels.
      */
diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 61b5b11..570b42f 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -358,6 +358,7 @@ process_equivalence(PlannerInfo *root,
         ec1->ec_sources = list_concat(ec1->ec_sources, ec2->ec_sources);
         ec1->ec_derives = list_concat(ec1->ec_derives, ec2->ec_derives);
         ec1->ec_relids = bms_join(ec1->ec_relids, ec2->ec_relids);
+        ec1->ec_allrelids = bms_join(ec1->ec_allrelids, ec2->ec_allrelids);
         ec1->ec_has_const |= ec2->ec_has_const;
         /* can't need to set has_volatile */
         ec1->ec_below_outer_join |= ec2->ec_below_outer_join;
@@ -372,6 +373,7 @@ process_equivalence(PlannerInfo *root,
         ec2->ec_sources = NIL;
         ec2->ec_derives = NIL;
         ec2->ec_relids = NULL;
+        ec2->ec_allrelids = NULL;
         ec1->ec_sources = lappend(ec1->ec_sources, restrictinfo);
         ec1->ec_below_outer_join |= below_outer_join;
         ec1->ec_min_security = Min(ec1->ec_min_security,
@@ -432,6 +434,7 @@ process_equivalence(PlannerInfo *root,
         ec->ec_sources = list_make1(restrictinfo);
         ec->ec_derives = NIL;
         ec->ec_relids = NULL;
+        ec->ec_allrelids = NULL;
         ec->ec_has_const = false;
         ec->ec_has_volatile = false;
         ec->ec_below_outer_join = below_outer_join;
@@ -572,6 +575,7 @@ add_eq_member(EquivalenceClass *ec, Expr *expr, Relids relids,
     {
         ec->ec_relids = bms_add_members(ec->ec_relids, relids);
     }
+    ec->ec_allrelids = bms_add_members(ec->ec_allrelids, relids);
     ec->ec_members = lappend(ec->ec_members, em);

     return em;
@@ -708,6 +712,7 @@ get_eclass_for_sort_expr(PlannerInfo *root,
     newec->ec_sources = NIL;
     newec->ec_derives = NIL;
     newec->ec_relids = NULL;
+    newec->ec_allrelids = NULL;
     newec->ec_has_const = false;
     newec->ec_has_volatile = contain_volatile_functions((Node *) expr);
     newec->ec_below_outer_join = false;
@@ -1114,6 +1119,60 @@ generate_join_implied_equalities_for_ecs(PlannerInfo *root,
         nominal_join_relids = join_relids;
     }

+    if (root->eq_index != NULL)
+    {
+        Bitmapset  *inner_ecs = NULL;
+        Bitmapset  *join_ecs = NULL;
+        Bitmapset  *matching_ecs;
+        int            i;
+
+        Assert((root->eq_index->ei_flags & EQUIVALANCE_IDX_MULTI_MEMBER));
+
+        i = -1;
+        while ((i = bms_next_member(inner_relids, i)) > 0)
+            inner_ecs = bms_add_members(inner_ecs, root->eq_index->ei_index[i]);
+
+        i = -1;
+        while ((i = bms_next_member(join_relids, i)) > 0)
+            join_ecs = bms_add_members(join_ecs, root->eq_index->ei_index[i]);
+
+        /* Determine all eclasses in common between inner rels and join rels */
+        matching_ecs = bms_int_members(inner_ecs, join_ecs);
+
+        i = -1;
+        while ((i = bms_next_member(matching_ecs, i)) >= 0)
+        {
+            EquivalenceClass *ec = root->eq_index->ei_classes[i];
+            List       *sublist = NIL;
+
+            /* ECs containing consts do not need any further enforcement */
+            if (ec->ec_has_const)
+                continue;
+
+            /* Ensure the class contains members for any of nominal_join_relids */
+            Assert(bms_overlap(ec->ec_relids, nominal_join_relids));
+
+            if (!ec->ec_broken)
+                sublist = generate_join_implied_equalities_normal(root,
+                                                                  ec,
+                                                                  join_relids,
+                                                                  outer_relids,
+                                                                  inner_relids);
+
+            /* Recover if we failed to generate required derived clauses */
+            if (ec->ec_broken)
+                sublist = generate_join_implied_equalities_broken(root,
+                                                                  ec,
+                                                                  nominal_join_relids,
+                                                                  outer_relids,
+                                                                  nominal_inner_relids,
+                                                                  inner_rel);
+
+            result = list_concat(result, sublist);
+        }
+        return result;
+    }
+
     foreach(lc, eclasses)
     {
         EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc);
@@ -2026,6 +2085,8 @@ exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2)
  * we ignore that fine point here.)  This is much like exprs_known_equal,
  * except that we insist on the comparison operator matching the eclass, so
  * that the result is definite not approximate.
+ *
+ * An eq_index without volatile classes must already exist on 'root'.
  */
 EquivalenceClass *
 match_eclasses_to_foreign_key_col(PlannerInfo *root,
@@ -2038,31 +2099,35 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
     AttrNumber    var2attno = fkinfo->confkey[colno];
     Oid            eqop = fkinfo->conpfeqop[colno];
     List       *opfamilies = NIL;    /* compute only if needed */
-    ListCell   *lc1;
+    EquivalenceClassIndex *eq_index;
+    Bitmapset  *matching_ecs;
+    int            i;

-    foreach(lc1, root->eq_classes)
+    Assert(root->eq_index != NULL);
+    Assert((root->eq_index->ei_flags & EQUIVALANCE_IDX_NON_VOLATILE) != 0);
+
+    eq_index = root->eq_index;
+
+    /* Determine which eclasses contain members for both of the relations */
+    matching_ecs = bms_intersect(eq_index->ei_index[var1varno],
+                                 eq_index->ei_index[var2varno]);
+
+    i = -1;
+    while ((i = bms_next_member(matching_ecs, i)) >= 0)
     {
-        EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
+        EquivalenceClass *ec = eq_index->ei_classes[i];
         bool        item1member = false;
         bool        item2member = false;
-        ListCell   *lc2;
+        ListCell   *lc;

-        /* Never match to a volatile EC */
-        if (ec->ec_has_volatile)
-            continue;
-        /* Note: it seems okay to match to "broken" eclasses here */
+        /* the eclass index shouldn't have indexed these */
+        Assert(!ec->ec_has_volatile);

-        /*
-         * If eclass visibly doesn't have members for both rels, there's no
-         * need to grovel through the members.
-         */
-        if (!bms_is_member(var1varno, ec->ec_relids) ||
-            !bms_is_member(var2varno, ec->ec_relids))
-            continue;
+        /* Note: it seems okay to match to "broken" eclasses here */

-        foreach(lc2, ec->ec_members)
+        foreach(lc, ec->ec_members)
         {
-            EquivalenceMember *em = (EquivalenceMember *) lfirst(lc2);
+            EquivalenceMember *em = (EquivalenceMember *) lfirst(lc);
             Var           *var;

             if (em->em_is_child)
@@ -2238,6 +2303,106 @@ generate_implied_equalities_for_column(PlannerInfo *root,
     else
         parent_relids = NULL;    /* not used, but keep compiler quiet */

+    if (root->eq_index != NULL)
+    {
+        Bitmapset       *matched_ecs = NULL;
+        int                i;
+
+        Assert((root->eq_index->ei_flags & EQUIVALANCE_IDX_MULTI_MEMBER));
+
+        i = -1;
+        while ((i = bms_next_member(rel->relids, i)) > 0)
+            matched_ecs = bms_add_members(matched_ecs, root->eq_index->ei_index[i]);
+
+        i = -1;
+        while ((i = bms_next_member(matched_ecs, i)) >= 0)
+        {
+            EquivalenceClass *cur_ec = root->eq_index->ei_classes[i];
+            EquivalenceMember *cur_em;
+            ListCell   *lc2;
+
+            /* Won't generate joinclauses if const */
+            if (cur_ec->ec_has_const)
+                continue;
+
+            /*
+             * Scan members, looking for a match to the target column.  Note that
+             * child EC members are considered, but only when they belong to the
+             * target relation.  (Unlike regular members, the same expression
+             * could be a child member of more than one EC.  Therefore, it's
+             * potentially order-dependent which EC a child relation's target
+             * column gets matched to.  This is annoying but it only happens in
+             * corner cases, so for now we live with just reporting the first
+             * match.  See also get_eclass_for_sort_expr.)
+             */
+            cur_em = NULL;
+            foreach(lc2, cur_ec->ec_members)
+            {
+                cur_em = (EquivalenceMember *) lfirst(lc2);
+                if (bms_equal(cur_em->em_relids, rel->relids) &&
+                    callback(root, rel, cur_ec, cur_em, callback_arg))
+                    break;
+                cur_em = NULL;
+            }
+
+            if (!cur_em)
+                continue;
+
+            /*
+             * Found our match.  Scan the other EC members and attempt to generate
+             * joinclauses.
+             */
+            foreach(lc2, cur_ec->ec_members)
+            {
+                EquivalenceMember *other_em = (EquivalenceMember *) lfirst(lc2);
+                Oid            eq_op;
+                RestrictInfo *rinfo;
+
+                if (other_em->em_is_child)
+                    continue;        /* ignore children here */
+
+                /* Make sure it'll be a join to a different rel */
+                if (other_em == cur_em ||
+                    bms_overlap(other_em->em_relids, rel->relids))
+                    continue;
+
+                /* Forget it if caller doesn't want joins to this rel */
+                if (bms_overlap(other_em->em_relids, prohibited_rels))
+                    continue;
+
+                /*
+                 * Also, if this is a child rel, avoid generating a useless join
+                 * to its parent rel(s).
+                 */
+                if (is_child_rel &&
+                    bms_overlap(parent_relids, other_em->em_relids))
+                    continue;
+
+                eq_op = select_equality_operator(cur_ec,
+                                                 cur_em->em_datatype,
+                                                 other_em->em_datatype);
+                if (!OidIsValid(eq_op))
+                    continue;
+
+                /* set parent_ec to mark as redundant with other joinclauses */
+                rinfo = create_join_clause(root, cur_ec, eq_op,
+                                           cur_em, other_em,
+                                           cur_ec);
+
+                result = lappend(result, rinfo);
+            }
+
+            /*
+             * If somehow we failed to create any join clauses, we might as well
+             * keep scanning the ECs for another match.  But if we did make any,
+             * we're done, because we don't want to return non-redundant clauses.
+             */
+            if (result)
+                break;
+        }
+        return result;
+    }
+
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *cur_ec = (EquivalenceClass *) lfirst(lc1);
@@ -2354,6 +2519,23 @@ have_relevant_eclass_joinclause(PlannerInfo *root,
 {
     ListCell   *lc1;

+    if (root->eq_index != NULL)
+    {
+        Bitmapset *rel1_ecs = NULL;
+        Bitmapset *rel2_ecs = NULL;
+
+        int i = -1;
+        while ((i = bms_next_member(rel1->relids, i)) > 0)
+            rel1_ecs = bms_add_members(rel1_ecs, root->eq_index->ei_index[i]);
+
+        i = -1;
+        while ((i = bms_next_member(rel2->relids, i)) > 0)
+            rel2_ecs = bms_add_members(rel2_ecs, root->eq_index->ei_index[i]);
+
+        /* return true if there are any eclasses in common between the two relations */
+        return bms_overlap(rel1_ecs, rel2_ecs);
+    }
+
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
@@ -2407,6 +2589,28 @@ has_relevant_eclass_joinclause(PlannerInfo *root, RelOptInfo *rel1)
 {
     ListCell   *lc1;

+    if (root->eq_index != NULL)
+    {
+        Bitmapset       *matched_ecs = NULL;
+        int                i;
+
+        Assert((root->eq_index->ei_flags & EQUIVALANCE_IDX_MULTI_MEMBER));
+
+        i = -1;
+        while ((i = bms_next_member(rel1->relids, i)) > 0)
+            matched_ecs = bms_add_members(matched_ecs, root->eq_index->ei_index[i]);
+
+        i = -1;
+
+        while ((i = bms_next_member(matched_ecs, i)) >= 0)
+        {
+            EquivalenceClass *ec = root->eq_index->ei_classes[i];
+            if (!bms_is_subset(ec->ec_relids, rel1->relids))
+                return true;
+        }
+        return false;
+    }
+
     foreach(lc1, root->eq_classes)
     {
         EquivalenceClass *ec = (EquivalenceClass *) lfirst(lc1);
@@ -2556,3 +2760,76 @@ is_redundant_with_indexclauses(RestrictInfo *rinfo, List *indexclauses)

     return false;
 }
+
+EquivalenceClassIndex *
+create_eclass_index(PlannerInfo *root, int flags)
+{
+    EquivalenceClassIndex *ec_index = makeNode(EquivalenceClassIndex);
+    EquivalenceClass      **ei_classes;
+    Bitmapset              **ei_index;
+    ListCell *lc;
+    int i;
+
+    ec_index->ei_classes = ei_classes = palloc(sizeof(EquivalenceClass *) *
+        list_length(root->eq_classes));
+    ec_index->ei_index = ei_index = palloc0(sizeof(Bitmapset *) *
+        root->simple_rel_array_size);
+    ec_index->ei_flags = flags;
+
+    /*
+     * Index the eclass list so that we can quickly identify eclasses
+     * belonging to a given relation.  First we build an array to store
+     * each eclass, this allows us to quickly lookup the eclass by array
+     * index.  We then build an index using a Bitmapset for each relation to
+     * mark which eclass array element contains a member for that relation.
+     */
+    i = 0;
+    foreach(lc, root->eq_classes)
+        ei_classes[i++] = lfirst(lc);
+
+    /*
+     * We could build the indexes in the loop above, but looping backwards
+     * allows the Bitmapset to be allocated to its final size on the first
+     * allocation.  Doing this forward could cause small incremental
+     * allocations which can be slower.
+     */
+    for (i--; i >= 0; i--)
+    {
+        int relid = -1;
+
+        while ((relid = bms_next_member(ei_classes[i]->ec_allrelids, relid)) > 0)
+        {
+            EquivalenceClass  *ec = ei_classes[i];
+
+            /* Don't index classes with a const if flags mention not to. */
+            if (ec->ec_has_const && (flags & EQUIVALANCE_IDX_NON_CONST) != 0)
+                continue;
+
+            /* Skip volatile classes when not required in the index */
+            if (ec->ec_has_volatile &&
+                (flags & EQUIVALANCE_IDX_NON_VOLATILE) != 0)
+                continue;
+
+            if (list_length(ec->ec_members) <= 1 &&
+                (flags & EQUIVALANCE_IDX_MULTI_MEMBER) != 0)
+                continue;
+
+            Assert(relid < root->simple_rel_array_size);
+
+            /* mark this eclass as having a member for relid */
+            ei_index[relid] = bms_add_member(ei_index[relid], i);
+        }
+    }
+
+    return ec_index;
+}
+
+void
+free_eclass_index(EquivalenceClassIndex *eci)
+{
+    Assert(IsA(eci, EquivalenceClassIndex));
+
+    pfree(eci->ei_classes);
+    pfree(eci->ei_index);
+}
+
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index 2afc3f1..a3bb646 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2433,6 +2433,9 @@ match_foreign_keys_to_quals(PlannerInfo *root)
     List       *newlist = NIL;
     ListCell   *lc;

+
+    root->eq_index = create_eclass_index(root, EQUIVALANCE_IDX_NON_VOLATILE);
+
     foreach(lc, root->fkey_list)
     {
         ForeignKeyOptInfo *fkinfo = (ForeignKeyOptInfo *) lfirst(lc);
@@ -2578,6 +2581,10 @@ match_foreign_keys_to_quals(PlannerInfo *root)
     }
     /* Replace fkey_list, thereby discarding any useless entries */
     root->fkey_list = newlist;
+
+    /* clean up the eclass index */
+    free_eclass_index(root->eq_index);
+    root->eq_index = NULL;
 }


diff --git a/src/include/nodes/nodes.h b/src/include/nodes/nodes.h
index f938925..736a1db 100644
--- a/src/include/nodes/nodes.h
+++ b/src/include/nodes/nodes.h
@@ -259,6 +259,7 @@ typedef enum NodeTag
     /* these aren't subclasses of Path: */
     T_EquivalenceClass,
     T_EquivalenceMember,
+    T_EquivalenceClassIndex,
     T_PathKey,
     T_PathTarget,
     T_RestrictInfo,
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index a008ae0..f50f98c 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -263,6 +263,8 @@ struct PlannerInfo

     List       *eq_classes;        /* list of active EquivalenceClasses */

+    struct EquivalenceClassIndex *eq_index;    /* Temporary eclass index */
+
     List       *canon_pathkeys; /* list of "canonical" PathKeys */

     List       *left_join_clauses;    /* list of RestrictInfos for mergejoinable
@@ -923,6 +925,7 @@ typedef struct EquivalenceClass
     List       *ec_derives;        /* list of derived RestrictInfos */
     Relids        ec_relids;        /* all relids appearing in ec_members, except
                                  * for child members (see below) */
+    Relids        ec_allrelids;    /* all relids, including child members */
     bool        ec_has_const;    /* any pseudoconstants in ec_members? */
     bool        ec_has_volatile;    /* the (sole) member is a volatile expr */
     bool        ec_below_outer_join;    /* equivalence applies below an OJ */
@@ -933,6 +936,22 @@ typedef struct EquivalenceClass
     struct EquivalenceClass *ec_merged; /* set if merged into another EC */
 } EquivalenceClass;

+typedef struct EquivalenceClassIndex
+{
+    NodeTag        type;
+
+    EquivalenceClass      **ei_classes;    /* an array of EquivalenceClasses */
+    Bitmapset              **ei_index; /* an array, indexed by relid contining
+                                       * a bitmapset of each ei_classes item
+                                       * which has a member belonging to this
+                                       * relation */
+    int                        ei_flags;
+} EquivalenceClassIndex;
+
+#define EQUIVALANCE_IDX_NON_CONST        1
+#define EQUIVALANCE_IDX_NON_VOLATILE    2
+#define EQUIVALANCE_IDX_MULTI_MEMBER    4
+
 /*
  * If an EC contains a const and isn't below-outer-join, any PathKey depending
  * on it must be redundant, since there's only one possible value of the key.
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 040335a..7c81239 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -169,6 +169,9 @@ extern bool eclass_useful_for_merging(PlannerInfo *root,
 extern bool is_redundant_derived_clause(RestrictInfo *rinfo, List *clauselist);
 extern bool is_redundant_with_indexclauses(RestrictInfo *rinfo,
                                List *indexclauses);
+extern EquivalenceClassIndex *create_eclass_index(PlannerInfo *root,
+                    int flags);
+extern void free_eclass_index(EquivalenceClassIndex *eci);

 /*
  * pathkeys.c