Thread: Patch to fix FK-related selectivity estimates with constants

Patch to fix FK-related selectivity estimates with constants

From
Tom Lane
Date:
Over in the thread at [1] it's discussed how our code for making
selectivity estimates using knowledge about FOREIGN KEY constraints
is busted in the face of EquivalenceClasses including constants.

That is, if fktab(a,b) is a 2-column FK reference to pktab(a,b)
and we have a query like

    ... where fktab.a = pktab.a and fktab.b = pktab.b

then we understand that any given fktab row can match at most one
pktab row (and this estimate is often a lot better than we'd get
from assuming that the a and b conditions are independent).

However, if the query is like

    ... where fktab.a = pktab.a and fktab.b = pktab.b
              and fktab.a = 1

then this suddenly breaks down and we go back to non-FK-aware
estimates.  The reason is that get_foreign_key_join_selectivity()
is looking for join clauses that equate the two sides of the FK
constraint ... and in this example, it will not see any such
join clause for column "a".  That's because equivclass.c decided
to replace the given clauses with "fktab.a = 1 and pktab.a = 1",
which can be enforced at the scan level, leaving nothing to be
done for column "a" at the join level.

We can fix that by detecting which EquivalenceClasses are marked
"ec_has_const", since that's the property that dictates whether
equivclass.c uses this strategy.  However, that's only a partial
fix; if you try it, you soon find that the selectivity estimates
are still off.  The reason is that because the two "a = 1" conditions
are already factored into the size estimates for the join input
relations, we're essentially double-counting the "fktab.a = 1"
condition's selectivity if we use the existing FK selectivity
estimation rule.  If we treated the constant condition as only
relevant to the PK side, then the FK selectivity rule could work
normally.  But we don't want to drop the ability to enforce the
restriction at the scan level.  So what we have to do is cancel
the FK side's condition's selectivity out of the FK selectivity.

Attached is a patch series that attacks it that way.  For ease of
review I split it into two steps:

0001 refactors process_implied_equality() so that it can pass
back the new RestrictInfo to its callers in equivclass.c.
I think this is a good change on its own merits, because it means
that when generating a derived equality, we don't have to use
initialize_mergeclause_eclasses() to set up the new RestrictInfo's
left_ec and right_ec pointers.  The equivclass.c caller knows
perfectly darn well which EquivalenceClass the two sides of the
clause belong to, so it can just assign that value, saving a couple
of potentially-not-cheap get_eclass_for_sort_expr() searches.
This does require process_implied_equality() to duplicate some of
the steps in distribute_qual_to_rels(), but on the other hand we
get to remove some complexity from distribute_qual_to_rels() because
it no longer has to deal with any is_deduced cases.  Anyway, the
end goal of this step is that we can save away all the generated
"x = const" clauses in the EC's ec_derives list.  0001 doesn't
do anything with that information, but ...

0002 actually fixes the bug.  Dealing with the first part of the
problem just requires counting how many of the ECs we matched to
an FK constraint are ec_has_const.  To deal with the second part,
we dig out the scan-level "x = const" clause that the EC generated
for the FK column and see what selectivity it has got.  This beats
other ways of reconstructing the scan-clause selectivity because
(at least in all normal cases) that selectivity would have been
cached in the RestrictInfo.  Thus we not only save cycles but can be
sure we are cancelling out exactly the right amount of selectivity.

I would not propose back-patching this, but it seems OK for HEAD.
Thoughts?

            regards, tom lane

[1]
https://www.postgresql.org/message-id/flat/AM6PR02MB5287A0ADD936C1FA80973E72AB190%40AM6PR02MB5287.eurprd02.prod.outlook.com

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 690b753369..26c98198b5 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -840,10 +840,8 @@ find_em_expr_for_rel(EquivalenceClass *ec, RelOptInfo *rel)
  * scanning of the quals and before Path construction begins.
  *
  * We make no attempt to avoid generating duplicate RestrictInfos here: we
- * don't search ec_sources for matches, nor put the created RestrictInfos
- * into ec_derives.  Doing so would require some slightly ugly changes in
- * initsplan.c's API, and there's no real advantage, because the clauses
- * generated here can't duplicate anything we will generate for joins anyway.
+ * don't search ec_sources or ec_derives for matches.  It doesn't really
+ * seem worth the trouble to do so.
  */
 void
 generate_base_implied_equalities(PlannerInfo *root)
@@ -969,6 +967,7 @@ generate_base_implied_equalities_const(PlannerInfo *root,
     {
         EquivalenceMember *cur_em = (EquivalenceMember *) lfirst(lc);
         Oid            eq_op;
+        RestrictInfo *rinfo;

         Assert(!cur_em->em_is_child);    /* no children yet */
         if (cur_em == const_em)
@@ -982,14 +981,31 @@ generate_base_implied_equalities_const(PlannerInfo *root,
             ec->ec_broken = true;
             break;
         }
-        process_implied_equality(root, eq_op, ec->ec_collation,
-                                 cur_em->em_expr, const_em->em_expr,
-                                 bms_copy(ec->ec_relids),
-                                 bms_union(cur_em->em_nullable_relids,
-                                           const_em->em_nullable_relids),
-                                 ec->ec_min_security,
-                                 ec->ec_below_outer_join,
-                                 cur_em->em_is_const);
+        rinfo = process_implied_equality(root, eq_op, ec->ec_collation,
+                                         cur_em->em_expr, const_em->em_expr,
+                                         bms_copy(ec->ec_relids),
+                                         bms_union(cur_em->em_nullable_relids,
+                                                   const_em->em_nullable_relids),
+                                         ec->ec_min_security,
+                                         ec->ec_below_outer_join,
+                                         cur_em->em_is_const);
+
+        /*
+         * If the clause didn't degenerate to a constant, fill in the correct
+         * markings for a mergejoinable clause, and save it in ec_derives. (We
+         * will not re-use such clauses directly, but selectivity estimation
+         * may consult the list later.  Note that this use of ec_derives does
+         * not overlap with its use for join clauses, since we never generate
+         * join clauses from an ec_has_const eclass.)
+         */
+        if (rinfo && rinfo->mergeopfamilies)
+        {
+            /* it's not redundant, so don't set parent_ec */
+            rinfo->left_ec = rinfo->right_ec = ec;
+            rinfo->left_em = cur_em;
+            rinfo->right_em = const_em;
+            ec->ec_derives = lappend(ec->ec_derives, rinfo);
+        }
     }
 }

@@ -1028,6 +1044,7 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
         {
             EquivalenceMember *prev_em = prev_ems[relid];
             Oid            eq_op;
+            RestrictInfo *rinfo;

             eq_op = select_equality_operator(ec,
                                              prev_em->em_datatype,
@@ -1038,14 +1055,29 @@ generate_base_implied_equalities_no_const(PlannerInfo *root,
                 ec->ec_broken = true;
                 break;
             }
-            process_implied_equality(root, eq_op, ec->ec_collation,
-                                     prev_em->em_expr, cur_em->em_expr,
-                                     bms_copy(ec->ec_relids),
-                                     bms_union(prev_em->em_nullable_relids,
-                                               cur_em->em_nullable_relids),
-                                     ec->ec_min_security,
-                                     ec->ec_below_outer_join,
-                                     false);
+            rinfo = process_implied_equality(root, eq_op, ec->ec_collation,
+                                             prev_em->em_expr, cur_em->em_expr,
+                                             bms_copy(ec->ec_relids),
+                                             bms_union(prev_em->em_nullable_relids,
+                                                       cur_em->em_nullable_relids),
+                                             ec->ec_min_security,
+                                             ec->ec_below_outer_join,
+                                             false);
+
+            /*
+             * If the clause didn't degenerate to a constant, fill in the
+             * correct markings for a mergejoinable clause.  We don't put it
+             * in ec_derives however; we don't currently need to re-find such
+             * clauses, and we don't want to clutter that list with non-join
+             * clauses.
+             */
+            if (rinfo && rinfo->mergeopfamilies)
+            {
+                /* it's not redundant, so don't set parent_ec */
+                rinfo->left_ec = rinfo->right_ec = ec;
+                rinfo->left_em = prev_em;
+                rinfo->right_em = cur_em;
+            }
         }
         prev_ems[relid] = cur_em;
     }
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index e978b491f6..d64b32d4ba 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -62,14 +62,12 @@ static SpecialJoinInfo *make_outerjoininfo(PlannerInfo *root,
                                            JoinType jointype, List *clause);
 static void compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause);
 static void distribute_qual_to_rels(PlannerInfo *root, Node *clause,
-                                    bool is_deduced,
                                     bool below_outer_join,
                                     JoinType jointype,
                                     Index security_level,
                                     Relids qualscope,
                                     Relids ojscope,
                                     Relids outerjoin_nonnullable,
-                                    Relids deduced_nullable_relids,
                                     List **postponed_qual_list);
 static bool check_outerjoin_delay(PlannerInfo *root, Relids *relids_p,
                                   Relids *nullable_relids_p, bool is_pushed_down);
@@ -815,9 +813,9 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,

             if (bms_is_subset(pq->relids, *qualscope))
                 distribute_qual_to_rels(root, pq->qual,
-                                        false, below_outer_join, JOIN_INNER,
+                                        below_outer_join, JOIN_INNER,
                                         root->qual_security_level,
-                                        *qualscope, NULL, NULL, NULL,
+                                        *qualscope, NULL, NULL,
                                         NULL);
             else
                 *postponed_qual_list = lappend(*postponed_qual_list, pq);
@@ -831,9 +829,9 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
             Node       *qual = (Node *) lfirst(l);

             distribute_qual_to_rels(root, qual,
-                                    false, below_outer_join, JOIN_INNER,
+                                    below_outer_join, JOIN_INNER,
                                     root->qual_security_level,
-                                    *qualscope, NULL, NULL, NULL,
+                                    *qualscope, NULL, NULL,
                                     postponed_qual_list);
         }
     }
@@ -1008,10 +1006,10 @@ deconstruct_recurse(PlannerInfo *root, Node *jtnode, bool below_outer_join,
             Node       *qual = (Node *) lfirst(l);

             distribute_qual_to_rels(root, qual,
-                                    false, below_outer_join, j->jointype,
+                                    below_outer_join, j->jointype,
                                     root->qual_security_level,
                                     *qualscope,
-                                    ojscope, nonnullable_rels, NULL,
+                                    ojscope, nonnullable_rels,
                                     postponed_qual_list);
         }

@@ -1110,14 +1108,12 @@ process_security_barrier_quals(PlannerInfo *root,
              * than being pushed up to top of tree, which we don't want.
              */
             distribute_qual_to_rels(root, qual,
-                                    false,
                                     below_outer_join,
                                     JOIN_INNER,
                                     security_level,
                                     qualscope,
                                     qualscope,
                                     NULL,
-                                    NULL,
                                     NULL);
         }
         security_level++;
@@ -1581,7 +1577,6 @@ compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause)
  *      as belonging to a higher join level, just add it to postponed_qual_list.
  *
  * 'clause': the qual clause to be distributed
- * 'is_deduced': true if the qual came from implied-equality deduction
  * 'below_outer_join': true if the qual is from a JOIN/ON that is below the
  *        nullable side of a higher-level outer join
  * 'jointype': type of join the qual is from (JOIN_INNER for a WHERE clause)
@@ -1593,8 +1588,6 @@ compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause)
  *        baserels appearing on the outer (nonnullable) side of the join
  *        (for FULL JOIN this includes both sides of the join, and must in fact
  *        equal qualscope)
- * 'deduced_nullable_relids': if is_deduced is true, the nullable relids to
- *        impute to the clause; otherwise NULL
  * 'postponed_qual_list': list of PostponedQual structs, which we can add
  *        this qual to if it turns out to belong to a higher join level.
  *        Can be NULL if caller knows postponement is impossible.
@@ -1603,23 +1596,17 @@ compute_semijoin_info(SpecialJoinInfo *sjinfo, List *clause)
  * 'ojscope' is needed if we decide to force the qual up to the outer-join
  * level, which will be ojscope not necessarily qualscope.
  *
- * In normal use (when is_deduced is false), at the time this is called,
- * root->join_info_list must contain entries for all and only those special
- * joins that are syntactically below this qual.  But when is_deduced is true,
- * we are adding new deduced clauses after completion of deconstruct_jointree,
- * so it cannot be assumed that root->join_info_list has anything to do with
- * qual placement.
+ * At the time this is called, root->join_info_list must contain entries for
+ * all and only those special joins that are syntactically below this qual.
  */
 static void
 distribute_qual_to_rels(PlannerInfo *root, Node *clause,
-                        bool is_deduced,
                         bool below_outer_join,
                         JoinType jointype,
                         Index security_level,
                         Relids qualscope,
                         Relids ojscope,
                         Relids outerjoin_nonnullable,
-                        Relids deduced_nullable_relids,
                         List **postponed_qual_list)
 {
     Relids        relids;
@@ -1653,7 +1640,6 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,

         Assert(root->hasLateralRTEs);    /* shouldn't happen otherwise */
         Assert(jointype == JOIN_INNER); /* mustn't postpone past outer join */
-        Assert(!is_deduced);    /* shouldn't be deduced, either */
         pq->qual = clause;
         pq->relids = relids;
         *postponed_qual_list = lappend(*postponed_qual_list, pq);
@@ -1754,24 +1740,7 @@ distribute_qual_to_rels(PlannerInfo *root, Node *clause,
      * This seems like another reason why it should perhaps be rethought.
      *----------
      */
-    if (is_deduced)
-    {
-        /*
-         * If the qual came from implied-equality deduction, it should not be
-         * outerjoin-delayed, else deducer blew it.  But we can't check this
-         * because the join_info_list may now contain OJs above where the qual
-         * belongs.  For the same reason, we must rely on caller to supply the
-         * correct nullable_relids set.
-         */
-        Assert(!ojscope);
-        is_pushed_down = true;
-        outerjoin_delayed = false;
-        nullable_relids = deduced_nullable_relids;
-        /* Don't feed it back for more deductions */
-        maybe_equivalence = false;
-        maybe_outer_join = false;
-    }
-    else if (bms_overlap(relids, outerjoin_nonnullable))
+    if (bms_overlap(relids, outerjoin_nonnullable))
     {
         /*
          * The qual is attached to an outer join and mentions (some of the)
@@ -2277,14 +2246,18 @@ distribute_restrictinfo_to_rels(PlannerInfo *root,
  * can produce constant TRUE or constant FALSE.  (Otherwise it's not,
  * because the expressions went through eval_const_expressions already.)
  *
+ * Returns the generated RestrictInfo, if any.  The result will be NULL
+ * if both_const is true and we successfully reduced the clause to
+ * constant TRUE.
+ *
  * Note: this function will copy item1 and item2, but it is caller's
  * responsibility to make sure that the Relids parameters are fresh copies
  * not shared with other uses.
  *
- * This is currently used only when an EquivalenceClass is found to
- * contain pseudoconstants.  See path/pathkeys.c for more details.
+ * Note: we do not do initialize_mergeclause_eclasses() here.  It is
+ * caller's responsibility that left_ec/right_ec be set as necessary.
  */
-void
+RestrictInfo *
 process_implied_equality(PlannerInfo *root,
                          Oid opno,
                          Oid collation,
@@ -2296,24 +2269,27 @@ process_implied_equality(PlannerInfo *root,
                          bool below_outer_join,
                          bool both_const)
 {
-    Expr       *clause;
+    RestrictInfo *restrictinfo;
+    Node       *clause;
+    Relids        relids;
+    bool        pseudoconstant = false;

     /*
      * Build the new clause.  Copy to ensure it shares no substructure with
      * original (this is necessary in case there are subselects in there...)
      */
-    clause = make_opclause(opno,
-                           BOOLOID, /* opresulttype */
-                           false,    /* opretset */
-                           copyObject(item1),
-                           copyObject(item2),
-                           InvalidOid,
-                           collation);
+    clause = (Node *) make_opclause(opno,
+                                    BOOLOID,    /* opresulttype */
+                                    false,    /* opretset */
+                                    copyObject(item1),
+                                    copyObject(item2),
+                                    InvalidOid,
+                                    collation);

     /* If both constant, try to reduce to a boolean constant. */
     if (both_const)
     {
-        clause = (Expr *) eval_const_expressions(root, (Node *) clause);
+        clause = eval_const_expressions(root, clause);

         /* If we produced const TRUE, just drop the clause */
         if (clause && IsA(clause, Const))
@@ -2322,25 +2298,106 @@ process_implied_equality(PlannerInfo *root,

             Assert(cclause->consttype == BOOLOID);
             if (!cclause->constisnull && DatumGetBool(cclause->constvalue))
-                return;
+                return NULL;
+        }
+    }
+
+    /*
+     * The rest of this is a very cut-down version of distribute_qual_to_rels.
+     * We can skip most of the work therein, but there are a couple of special
+     * cases we still have to handle.
+     *
+     * Retrieve all relids mentioned within the possibly-simplified clause.
+     */
+    relids = pull_varnos(clause);
+    Assert(bms_is_subset(relids, qualscope));
+
+    /*
+     * If the clause is variable-free, our normal heuristic for pushing it
+     * down to just the mentioned rels doesn't work, because there are none.
+     * Apply at the given qualscope, or at the top of tree if it's nonvolatile
+     * (which it very likely is, but we'll check, just to be sure).
+     */
+    if (bms_is_empty(relids))
+    {
+        /* eval at original syntactic level */
+        relids = bms_copy(qualscope);
+        if (!contain_volatile_functions(clause))
+        {
+            /* mark as gating qual */
+            pseudoconstant = true;
+            /* tell createplan.c to check for gating quals */
+            root->hasPseudoConstantQuals = true;
+            /* if not below outer join, push it to top of tree */
+            if (!below_outer_join)
+            {
+                relids =
+                    get_relids_in_jointree((Node *) root->parse->jointree,
+                                           false);
+            }
         }
     }

+    /*
+     * Build the RestrictInfo node itself.
+     */
+    restrictinfo = make_restrictinfo((Expr *) clause,
+                                     true,    /* is_pushed_down */
+                                     false, /* outerjoin_delayed */
+                                     pseudoconstant,
+                                     security_level,
+                                     relids,
+                                     NULL,    /* outer_relids */
+                                     nullable_relids);
+
+    /*
+     * If it's a join clause, add vars used in the clause to targetlists of
+     * their relations, so that they will be emitted by the plan nodes that
+     * scan those relations (else they won't be available at the join node!).
+     *
+     * Typically, we'd have already done this when the component expressions
+     * were first seen by distribute_qual_to_rels; but it is possible that
+     * some of the Vars could have missed having that done because they only
+     * appeared in single-relation clauses originally.  So do it here for
+     * safety.
+     */
+    if (bms_membership(relids) == BMS_MULTIPLE)
+    {
+        List       *vars = pull_var_clause(clause,
+                                           PVC_RECURSE_AGGREGATES |
+                                           PVC_RECURSE_WINDOWFUNCS |
+                                           PVC_INCLUDE_PLACEHOLDERS);
+
+        add_vars_to_targetlist(root, vars, relids, false);
+        list_free(vars);
+    }
+
+    /*
+     * Check mergejoinability.  This will usually succeed, since the op came
+     * from an EquivalenceClass; but we could have reduced the original clause
+     * to a constant.
+     */
+    check_mergejoinable(restrictinfo);
+
+    /*
+     * Note we don't do initialize_mergeclause_eclasses(); the caller can
+     * handle that much more cheaply than we can.  It's okay to call
+     * distribute_restrictinfo_to_rels() before that happens.
+     */
+
     /*
      * Push the new clause into all the appropriate restrictinfo lists.
      */
-    distribute_qual_to_rels(root, (Node *) clause,
-                            true, below_outer_join, JOIN_INNER,
-                            security_level,
-                            qualscope, NULL, NULL, nullable_relids,
-                            NULL);
+    distribute_restrictinfo_to_rels(root, restrictinfo);
+
+    return restrictinfo;
 }

 /*
  * build_implied_join_equality --- build a RestrictInfo for a derived equality
  *
  * This overlaps the functionality of process_implied_equality(), but we
- * must return the RestrictInfo, not push it into the joininfo tree.
+ * must not push the RestrictInfo into the joininfo tree.
  *
  * Note: this function will copy item1 and item2, but it is caller's
  * responsibility to make sure that the Relids parameters are fresh copies
diff --git a/src/include/optimizer/planmain.h b/src/include/optimizer/planmain.h
index f3cefe67b8..81c4a7e560 100644
--- a/src/include/optimizer/planmain.h
+++ b/src/include/optimizer/planmain.h
@@ -77,16 +77,16 @@ extern void create_lateral_join_info(PlannerInfo *root);
 extern List *deconstruct_jointree(PlannerInfo *root);
 extern void distribute_restrictinfo_to_rels(PlannerInfo *root,
                                             RestrictInfo *restrictinfo);
-extern void process_implied_equality(PlannerInfo *root,
-                                     Oid opno,
-                                     Oid collation,
-                                     Expr *item1,
-                                     Expr *item2,
-                                     Relids qualscope,
-                                     Relids nullable_relids,
-                                     Index security_level,
-                                     bool below_outer_join,
-                                     bool both_const);
+extern RestrictInfo *process_implied_equality(PlannerInfo *root,
+                                              Oid opno,
+                                              Oid collation,
+                                              Expr *item1,
+                                              Expr *item2,
+                                              Relids qualscope,
+                                              Relids nullable_relids,
+                                              Index security_level,
+                                              bool below_outer_join,
+                                              bool both_const);
 extern RestrictInfo *build_implied_join_equality(Oid opno,
                                                  Oid collation,
                                                  Expr *item1,
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 08a049232e..530328af43 100644
--- a/src/backend/nodes/outfuncs.c
+++ b/src/backend/nodes/outfuncs.c
@@ -2352,6 +2352,7 @@ _outForeignKeyOptInfo(StringInfo str, const ForeignKeyOptInfo *node)
     WRITE_ATTRNUMBER_ARRAY(confkey, node->nkeys);
     WRITE_OID_ARRAY(conpfeqop, node->nkeys);
     WRITE_INT_FIELD(nmatched_ec);
+    WRITE_INT_FIELD(nconst_ec);
     WRITE_INT_FIELD(nmatched_rcols);
     WRITE_INT_FIELD(nmatched_ri);
     /* for compactness, just print the number of matches per column: */
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 733f7ea543..9f6507eacb 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -5066,9 +5066,16 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
          * remove back into the worklist.
          *
          * Since the matching clauses are known not outerjoin-delayed, they
-         * should certainly have appeared in the initial joinclause list.  If
-         * we didn't find them, they must have been matched to, and removed
-         * by, some other FK in a previous iteration of this loop.  (A likely
+         * would normally have appeared in the initial joinclause list.  If we
+         * didn't find them, there are two possibilities:
+         *
+         * 1. If the FK match is based on an EC that is ec_has_const, it won't
+         * have generated any join clauses at all.  We discount such ECs while
+         * checking to see if we have "all" the clauses.  (Below, we'll adjust
+         * the selectivity estimate for this case.)
+         *
+         * 2. The clauses were matched to some other FK in a previous
+         * iteration of this loop, and thus removed from worklist.  (A likely
          * case is that two FKs are matched to the same EC; there will be only
          * one EC-derived clause in the initial list, so the first FK will
          * consume it.)  Applying both FKs' selectivity independently risks
@@ -5079,7 +5086,7 @@ get_foreign_key_join_selectivity(PlannerInfo *root,
          * but for now, just punt, since this is a fairly uncommon situation.
          */
         if (list_length(removedlist) !=
-            (fkinfo->nmatched_ec + fkinfo->nmatched_ri))
+            (fkinfo->nmatched_ec - fkinfo->nconst_ec + fkinfo->nmatched_ri))
         {
             worklist = list_concat(worklist, removedlist);
             continue;
@@ -5138,9 +5145,48 @@ get_foreign_key_join_selectivity(PlannerInfo *root,

             fkselec *= 1.0 / ref_tuples;
         }
+
+        /*
+         * If any of the FK columns participated in ec_has_const ECs, then
+         * equivclass.c will have generated "var = const" restrictions for
+         * each side of the join, thus reducing the sizes of both input
+         * relations.  Taking the fkselec at face value would amount to
+         * double-counting the selectivity of the constant restriction for the
+         * referencing Var.  Hence, look for the restriction clause(s) that
+         * were applied to the referencing Var(s), and divide out their
+         * selectivity to correct for this.
+         */
+        if (fkinfo->nconst_ec > 0)
+        {
+            for (int i = 0; i < fkinfo->nkeys; i++)
+            {
+                EquivalenceClass *ec = fkinfo->eclass[i];
+
+                if (ec && ec->ec_has_const)
+                {
+                    EquivalenceMember *em = fkinfo->fk_eclass_member[i];
+                    RestrictInfo *rinfo = find_derived_clause_for_ec_member(ec,
+                                                                            em);
+
+                    if (rinfo)
+                    {
+                        Selectivity s0;
+
+                        s0 = clause_selectivity(root,
+                                                (Node *) rinfo,
+                                                0,
+                                                jointype,
+                                                sjinfo);
+                        if (s0 > 0)
+                            fkselec /= s0;
+                    }
+                }
+            }
+        }
     }

     *restrictlist = worklist;
+    CLAMP_PROBABILITY(fkselec);
     return fkselec;
 }

diff --git a/src/backend/optimizer/path/equivclass.c b/src/backend/optimizer/path/equivclass.c
index 26c98198b5..a21b3b4756 100644
--- a/src/backend/optimizer/path/equivclass.c
+++ b/src/backend/optimizer/path/equivclass.c
@@ -2183,6 +2183,10 @@ 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.
+ *
+ * On success, we also set fkinfo->eclass[colno] to the matching eclass,
+ * and set fkinfo->fk_eclass_member[colno] to the eclass member for the
+ * referencing Var.
  */
 EquivalenceClass *
 match_eclasses_to_foreign_key_col(PlannerInfo *root,
@@ -2212,8 +2216,8 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
     {
         EquivalenceClass *ec = (EquivalenceClass *) list_nth(root->eq_classes,
                                                              i);
-        bool        item1member = false;
-        bool        item2member = false;
+        EquivalenceMember *item1_em = NULL;
+        EquivalenceMember *item2_em = NULL;
         ListCell   *lc2;

         /* Never match to a volatile EC */
@@ -2238,12 +2242,12 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,

             /* Match? */
             if (var->varno == var1varno && var->varattno == var1attno)
-                item1member = true;
+                item1_em = em;
             else if (var->varno == var2varno && var->varattno == var2attno)
-                item2member = true;
+                item2_em = em;

             /* Have we found both PK and FK column in this EC? */
-            if (item1member && item2member)
+            if (item1_em && item2_em)
             {
                 /*
                  * Succeed if eqop matches EC's opfamilies.  We could test
@@ -2253,7 +2257,11 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
                 if (opfamilies == NIL)    /* compute if we didn't already */
                     opfamilies = get_mergejoin_opfamilies(eqop);
                 if (equal(opfamilies, ec->ec_opfamilies))
+                {
+                    fkinfo->eclass[colno] = ec;
+                    fkinfo->fk_eclass_member[colno] = item2_em;
                     return ec;
+                }
                 /* Otherwise, done with this EC, move on to the next */
                 break;
             }
@@ -2262,6 +2270,37 @@ match_eclasses_to_foreign_key_col(PlannerInfo *root,
     return NULL;
 }

+/*
+ * find_derived_clause_for_ec_member
+ *      Search for a previously-derived clause mentioning the given EM.
+ *
+ * The eclass should be an ec_has_const EC, of which the EM is a non-const
+ * member.  This should ensure there is just one derived clause mentioning
+ * the EM (and equating it to a constant).
+ * Returns NULL if no such clause can be found.
+ */
+RestrictInfo *
+find_derived_clause_for_ec_member(EquivalenceClass *ec,
+                                  EquivalenceMember *em)
+{
+    ListCell   *lc;
+
+    Assert(ec->ec_has_const);
+    Assert(!em->em_is_const);
+    foreach(lc, ec->ec_derives)
+    {
+        RestrictInfo *rinfo = (RestrictInfo *) lfirst(lc);
+
+        /*
+         * generate_base_implied_equalities_const will have put non-const
+         * members on the left side of derived clauses.
+         */
+        if (rinfo->left_em == em)
+            return rinfo;
+    }
+    return NULL;
+}
+

 /*
  * add_child_rel_equivalences
diff --git a/src/backend/optimizer/plan/initsplan.c b/src/backend/optimizer/plan/initsplan.c
index d64b32d4ba..aae5df09f9 100644
--- a/src/backend/optimizer/plan/initsplan.c
+++ b/src/backend/optimizer/plan/initsplan.c
@@ -2512,18 +2512,19 @@ match_foreign_keys_to_quals(PlannerInfo *root)
          */
         for (colno = 0; colno < fkinfo->nkeys; colno++)
         {
+            EquivalenceClass *ec;
             AttrNumber    con_attno,
                         ref_attno;
             Oid            fpeqop;
             ListCell   *lc2;

-            fkinfo->eclass[colno] = match_eclasses_to_foreign_key_col(root,
-                                                                      fkinfo,
-                                                                      colno);
+            ec = match_eclasses_to_foreign_key_col(root, fkinfo, colno);
             /* Don't bother looking for loose quals if we got an EC match */
-            if (fkinfo->eclass[colno] != NULL)
+            if (ec != NULL)
             {
                 fkinfo->nmatched_ec++;
+                if (ec->ec_has_const)
+                    fkinfo->nconst_ec++;
                 continue;
             }

diff --git a/src/backend/optimizer/util/plancat.c b/src/backend/optimizer/util/plancat.c
index f9d0d67aa7..4f0da51c26 100644
--- a/src/backend/optimizer/util/plancat.c
+++ b/src/backend/optimizer/util/plancat.c
@@ -567,9 +567,11 @@ get_relation_foreign_keys(PlannerInfo *root, RelOptInfo *rel,
             memcpy(info->conpfeqop, cachedfk->conpfeqop, sizeof(info->conpfeqop));
             /* zero out fields to be filled by match_foreign_keys_to_quals */
             info->nmatched_ec = 0;
+            info->nconst_ec = 0;
             info->nmatched_rcols = 0;
             info->nmatched_ri = 0;
             memset(info->eclass, 0, sizeof(info->eclass));
+            memset(info->fk_eclass_member, 0, sizeof(info->fk_eclass_member));
             memset(info->rinfos, 0, sizeof(info->rinfos));

             root->fkey_list = lappend(root->fkey_list, info);
diff --git a/src/include/nodes/pathnodes.h b/src/include/nodes/pathnodes.h
index 3dd16b9ad5..45cbf6045a 100644
--- a/src/include/nodes/pathnodes.h
+++ b/src/include/nodes/pathnodes.h
@@ -889,10 +889,13 @@ typedef struct ForeignKeyOptInfo

     /* Derived info about whether FK's equality conditions match the query: */
     int            nmatched_ec;    /* # of FK cols matched by ECs */
+    int            nconst_ec;        /* # of these ECs that are ec_has_const */
     int            nmatched_rcols; /* # of FK cols matched by non-EC rinfos */
     int            nmatched_ri;    /* total # of non-EC rinfos matched to FK */
     /* Pointer to eclass matching each column's condition, if there is one */
     struct EquivalenceClass *eclass[INDEX_MAX_KEYS];
+    /* Pointer to eclass member for the referencing Var, if there is one */
+    struct EquivalenceMember *fk_eclass_member[INDEX_MAX_KEYS];
     /* List of non-EC RestrictInfos matching each column's condition */
     List       *rinfos[INDEX_MAX_KEYS];
 } ForeignKeyOptInfo;
diff --git a/src/include/optimizer/paths.h b/src/include/optimizer/paths.h
index 10b6e81079..2134227ebc 100644
--- a/src/include/optimizer/paths.h
+++ b/src/include/optimizer/paths.h
@@ -149,6 +149,8 @@ extern bool exprs_known_equal(PlannerInfo *root, Node *item1, Node *item2);
 extern EquivalenceClass *match_eclasses_to_foreign_key_col(PlannerInfo *root,
                                                            ForeignKeyOptInfo *fkinfo,
                                                            int colno);
+extern RestrictInfo *find_derived_clause_for_ec_member(EquivalenceClass *ec,
+                                                       EquivalenceMember *em);
 extern void add_child_rel_equivalences(PlannerInfo *root,
                                        AppendRelInfo *appinfo,
                                        RelOptInfo *parent_rel,

Re: Patch to fix FK-related selectivity estimates with constants

From
Tom Lane
Date:
I wrote:
> Over in the thread at [1] it's discussed how our code for making
> selectivity estimates using knowledge about FOREIGN KEY constraints
> is busted in the face of EquivalenceClasses including constants.
> ...
> Attached is a patch series that attacks it that way.

I'd failed to generate a test case I liked yesterday, but perhaps
the attached will do.  (While the new code is exercised in the
core regression tests already, it doesn't produce any visible
plan changes.)  I'm a little nervous about whether the plan
shape will be stable in the buildfarm, but it works for me on
both 64-bit and 32-bit machines, so probably it's OK.

            regards, tom lane

diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index a46b1573bd..6c9a5e26dd 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5843,6 +5843,56 @@ select t1.b, ss.phv from join_ut1 t1 left join lateral
 drop table join_pt1;
 drop table join_ut1;
 --
+-- test estimation behavior with multi-column foreign key and constant qual
+--
+begin;
+create table fkest (x integer, x10 integer, x10b integer, x100 integer);
+insert into fkest select x, x/10, x/10, x/100 from generate_series(1,1000) x;
+create unique index on fkest(x, x10, x100);
+analyze fkest;
+explain (costs off)
+select * from fkest f1
+  join fkest f2 on (f1.x = f2.x and f1.x10 = f2.x10b and f1.x100 = f2.x100)
+  join fkest f3 on f1.x = f3.x
+  where f1.x100 = 2;
+                        QUERY PLAN
+-----------------------------------------------------------
+ Nested Loop
+   ->  Hash Join
+         Hash Cond: ((f2.x = f1.x) AND (f2.x10b = f1.x10))
+         ->  Seq Scan on fkest f2
+               Filter: (x100 = 2)
+         ->  Hash
+               ->  Seq Scan on fkest f1
+                     Filter: (x100 = 2)
+   ->  Index Scan using fkest_x_x10_x100_idx on fkest f3
+         Index Cond: (x = f1.x)
+(10 rows)
+
+alter table fkest add constraint fk
+  foreign key (x, x10b, x100) references fkest (x, x10, x100);
+explain (costs off)
+select * from fkest f1
+  join fkest f2 on (f1.x = f2.x and f1.x10 = f2.x10b and f1.x100 = f2.x100)
+  join fkest f3 on f1.x = f3.x
+  where f1.x100 = 2;
+                     QUERY PLAN
+-----------------------------------------------------
+ Hash Join
+   Hash Cond: ((f2.x = f1.x) AND (f2.x10b = f1.x10))
+   ->  Hash Join
+         Hash Cond: (f3.x = f2.x)
+         ->  Seq Scan on fkest f3
+         ->  Hash
+               ->  Seq Scan on fkest f2
+                     Filter: (x100 = 2)
+   ->  Hash
+         ->  Seq Scan on fkest f1
+               Filter: (x100 = 2)
+(11 rows)
+
+rollback;
+--
 -- test that foreign key join estimation performs sanely for outer joins
 --
 begin;
diff --git a/src/test/regress/sql/join.sql b/src/test/regress/sql/join.sql
index 1403e0ffe7..dd60d6a1f3 100644
--- a/src/test/regress/sql/join.sql
+++ b/src/test/regress/sql/join.sql
@@ -1975,6 +1975,35 @@ select t1.b, ss.phv from join_ut1 t1 left join lateral

 drop table join_pt1;
 drop table join_ut1;
+
+--
+-- test estimation behavior with multi-column foreign key and constant qual
+--
+
+begin;
+
+create table fkest (x integer, x10 integer, x10b integer, x100 integer);
+insert into fkest select x, x/10, x/10, x/100 from generate_series(1,1000) x;
+create unique index on fkest(x, x10, x100);
+analyze fkest;
+
+explain (costs off)
+select * from fkest f1
+  join fkest f2 on (f1.x = f2.x and f1.x10 = f2.x10b and f1.x100 = f2.x100)
+  join fkest f3 on f1.x = f3.x
+  where f1.x100 = 2;
+
+alter table fkest add constraint fk
+  foreign key (x, x10b, x100) references fkest (x, x10, x100);
+
+explain (costs off)
+select * from fkest f1
+  join fkest f2 on (f1.x = f2.x and f1.x10 = f2.x10b and f1.x100 = f2.x100)
+  join fkest f3 on f1.x = f3.x
+  where f1.x100 = 2;
+
+rollback;
+
 --
 -- test that foreign key join estimation performs sanely for outer joins
 --

Re: Patch to fix FK-related selectivity estimates with constants

From
Tomas Vondra
Date:
On Tue, Oct 27, 2020 at 01:58:56PM -0400, Tom Lane wrote:
>I wrote:
>> Over in the thread at [1] it's discussed how our code for making
>> selectivity estimates using knowledge about FOREIGN KEY constraints
>> is busted in the face of EquivalenceClasses including constants.
>> ...
>> Attached is a patch series that attacks it that way.
>

The patch sems fine to me, thanks for investigating and fixing this.

Two minor comments:

I find it a bit strange that generate_base_implied_equalities_const adds
the rinfo to ec_derives, while generate_base_implied_equalities_no_const
does not. I understand it's correct as we don't lookup the non-const
clauses, and we want to keep the list as short as possible, but it seems
like a bit surprising/unexpected difference in behavior.

I think casting the 'clause' to (Node*) in process_implied_equality is
unnecessary - it was probably needed when it was declared as Expr* but
the patch changes that.


As for the backpatching, I don't feel very strongly about it. It's
clearly a bug/thinko in the code, and I don't see any obvious risks in
backpatching it (no ABI breaks etc.). OTOH multi-column foreign keys are
not very common, and the query pattern seems rather unusual too, so the
risk is pretty low I guess. We certainly did not get many reports, so.


>I'd failed to generate a test case I liked yesterday, but perhaps
>the attached will do.  (While the new code is exercised in the
>core regression tests already, it doesn't produce any visible
>plan changes.)  I'm a little nervous about whether the plan
>shape will be stable in the buildfarm, but it works for me on
>both 64-bit and 32-bit machines, so probably it's OK.
>

Works fine on raspberry pi 4 (i.e. armv7l, 32-bit arm) too.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services 



Re: Patch to fix FK-related selectivity estimates with constants

From
Tom Lane
Date:
Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> On Tue, Oct 27, 2020 at 01:58:56PM -0400, Tom Lane wrote:
>>> Attached is a patch series that attacks it that way.

> The patch sems fine to me, thanks for investigating and fixing this.

Thanks for looking at it!

> I find it a bit strange that generate_base_implied_equalities_const adds
> the rinfo to ec_derives, while generate_base_implied_equalities_no_const
> does not. I understand it's correct as we don't lookup the non-const
> clauses, and we want to keep the list as short as possible, but it seems
> like a bit surprising/unexpected difference in behavior.

Yeah, perhaps.  I considered replacing ec_derives with two lists, one
for base-level derived clauses and one for join-level derived clauses,
but it didn't really seem worth the trouble.  This is something we
could change later if a need arises to be able to look back at non-const
base-level derived clauses.

> I think casting the 'clause' to (Node*) in process_implied_equality is
> unnecessary - it was probably needed when it was declared as Expr* but
> the patch changes that.

Hm, thought I got rid of the unnecessary casts ... I'll look again.

> As for the backpatching, I don't feel very strongly about it. It's
> clearly a bug/thinko in the code, and I don't see any obvious risks in
> backpatching it (no ABI breaks etc.).

I had two concerns about possible extension breakage from a back-patch:

* Changing the set of fields in ForeignKeyOptInfo is an ABI break.
We could minimize the risk by adding the new fields at the end in
the back branches, but it still wouldn't be zero-risk.

* Changing the expectation about whether process_implied_equality()
will fill left_ec/right_ec is an API break.  It's somewhat doubtful
whether there exist any callers outside equivclass.c, but again it's
not zero risk.

The other issue, entirely unrelated to code hazards, is whether this
is too big a change in planner behavior to be back-patched.  We've
often felt that destabilizing stable-branch plan choices is something
to be avoided.

Not to mention the whole issue of whether this patch has any bugs of
its own.

So on the whole I wouldn't want to back-patch, or at least not do so
very far.  Maybe there's an argument that v13 is still new enough to
deflect the concern about plan stability.

            regards, tom lane



Re: Patch to fix FK-related selectivity estimates with constants

From
Tomas Vondra
Date:
On Tue, Oct 27, 2020 at 09:27:06PM -0400, Tom Lane wrote:
>Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>> On Tue, Oct 27, 2020 at 01:58:56PM -0400, Tom Lane wrote:
>>>> Attached is a patch series that attacks it that way.
>
>> The patch sems fine to me, thanks for investigating and fixing this.
>
>Thanks for looking at it!
>
>> I find it a bit strange that generate_base_implied_equalities_const adds
>> the rinfo to ec_derives, while generate_base_implied_equalities_no_const
>> does not. I understand it's correct as we don't lookup the non-const
>> clauses, and we want to keep the list as short as possible, but it seems
>> like a bit surprising/unexpected difference in behavior.
>
>Yeah, perhaps.  I considered replacing ec_derives with two lists, one
>for base-level derived clauses and one for join-level derived clauses,
>but it didn't really seem worth the trouble.  This is something we
>could change later if a need arises to be able to look back at non-const
>base-level derived clauses.
>
>> I think casting the 'clause' to (Node*) in process_implied_equality is
>> unnecessary - it was probably needed when it was declared as Expr* but
>> the patch changes that.
>
>Hm, thought I got rid of the unnecessary casts ... I'll look again.
>

Apologies, the casts are fine. I got it mixed up somehow.

>> As for the backpatching, I don't feel very strongly about it. It's
>> clearly a bug/thinko in the code, and I don't see any obvious risks in
>> backpatching it (no ABI breaks etc.).
>
>I had two concerns about possible extension breakage from a back-patch:
>
>* Changing the set of fields in ForeignKeyOptInfo is an ABI break.
>We could minimize the risk by adding the new fields at the end in
>the back branches, but it still wouldn't be zero-risk.
>
>* Changing the expectation about whether process_implied_equality()
>will fill left_ec/right_ec is an API break.  It's somewhat doubtful
>whether there exist any callers outside equivclass.c, but again it's
>not zero risk.
>
>The other issue, entirely unrelated to code hazards, is whether this
>is too big a change in planner behavior to be back-patched.  We've
>often felt that destabilizing stable-branch plan choices is something
>to be avoided.
>
>Not to mention the whole issue of whether this patch has any bugs of
>its own.
>
>So on the whole I wouldn't want to back-patch, or at least not do so
>very far.  Maybe there's an argument that v13 is still new enough to
>deflect the concern about plan stability.
>

OK, understood.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services 



Re: Patch to fix FK-related selectivity estimates with constants

From
Tom Lane
Date:
Alvaro Herrera <alvherre@alvh.no-ip.org> writes:
> On 2020-Oct-27, Tom Lane wrote:
>> * Changing the set of fields in ForeignKeyOptInfo is an ABI break.
>> We could minimize the risk by adding the new fields at the end in
>> the back branches, but it still wouldn't be zero-risk.

> It'd be useful to be able to qualify this sort of risk more objectively.

Agreed.

> I think if a struct is used as a function argument somewhere or arrays
> of the struct are formed, then it's certain that changing that struct's
> size is going to cause problems.

I grasp the point about arrays, but not sure how it's a problem for
function arguments per se?  Or were you thinking of functions that
take a struct as pass-by-value not pass-by-reference?

The way I've generally thought about this is that new fields added to the
end of a Node struct are only likely to be a hazard if extension code
creates new instances of that Node type.  If it does, it's certainly
problematic, first because makeNode() will allocate the wrong amount of
storage (ABI issue) and second because the extension won't know it needs
to fill the new fields (API issue).  However if we don't expect that that
will happen, then it's probably going to be OK.  Code that just inspects
Nodes made by the core code won't be broken, as long as we don't change
the semantics of the existing fields.  We don't ever pass Node structs by
value, and we don't make arrays of them either, so the actual size of the
struct isn't much of an ABI issue.

As you say, we can also search to see if there seem to be any extensions
using the struct in question.  I don't have a huge amount of faith in
that, because I think there are lots of proprietary/custom extensions
that aren't visible on the net.  But on the other hand, the users
of such extensions probably wouldn't have much trouble rebuilding them
for a new version, if they did get bit.  It's the widely distributed
extensions that might have users not capable of dealing with that.

            regards, tom lane