Costing elided SubqueryScans more nearly correctly - Mailing list pgsql-hackers

In [1] I complained about how SubqueryScans that get deleted from
a plan tree by setrefs.c nonetheless contribute cost increments
that might cause the planner to make odd choices.  That turned
out not to be the proximate cause of that particular issue, but
it still seems like it might be a good idea to do something about
it.  Here's a little patch to improve matters.

It turns out to be hard to predict perfectly whether setrefs.c will
remove a SubqueryScan, because createplan.c plays some games with
moving tlist evaluations around and/or inserting "physical"
(i.e. trivial) tlists, which can falsify any earlier estimate of
whether a SubqueryScan is trivial.  I'm not especially interested in
redesigning those mechanisms, so the best we can hope for is an
approximate determination.  (Those same behaviors also make a lot of
other path cost estimates a bit incorrect, so it doesn't seem like
we need to feel too awful about not getting SubqueryScan perfect.)

Given that ground rule, however, it's not very hard to determine
whether a SubqueryScanPath looks like it will be trivial and change
its costing accordingly.  The attached draft patch does that.

I instrumented the code in setrefs.c, and found that during the
core regression tests this patch estimates correctly in 2103
places while guessing wrongly in 54, so that seems like a pretty
good step forward.

Perhaps I overcomplicated matters by making the callers responsible
for determining triviality of the paths' targets.  We could just
make cost_subqueryscan check that for itself (using logic similar
to what I wrote in set_subquery_pathlist), but that'd result in
duplicative calculations anytime we make more than one Path for a
subquery.  On the other hand, said calculations wouldn't be that
expensive, so perhaps a more localized patch would be better.

I also notice that setrefs.c can elide Append and MergeAppend nodes
too in some cases, but AFAICS costing of those node types doesn't
take that into account.

Anyway, I'll stick this in the queue for v16.

            regards, tom lane

[1] https://www.postgresql.org/message-id/328872.1651247595%40sss.pgh.pa.us

diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index d84f66a81b..08f4d125e1 100644
--- a/src/backend/optimizer/path/allpaths.c
+++ b/src/backend/optimizer/path/allpaths.c
@@ -2439,6 +2439,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
 {
     Query       *parse = root->parse;
     Query       *subquery = rte->subquery;
+    bool        trivial_pathtarget;
     Relids        required_outer;
     pushdown_safety_info safetyInfo;
     double        tuple_fraction;
@@ -2597,6 +2598,36 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
      */
     set_subquery_size_estimates(root, rel);

+    /*
+     * Also detect whether the reltarget is trivial, so that we can pass that
+     * info to cost_subqueryscan (rather than re-deriving it multiple times).
+     * It's trivial if it fetches all the subplan output columns in order.
+     */
+    if (list_length(rel->reltarget->exprs) != list_length(subquery->targetList))
+        trivial_pathtarget = false;
+    else
+    {
+        trivial_pathtarget = true;
+        foreach(lc, rel->reltarget->exprs)
+        {
+            Node       *node = (Node *) lfirst(lc);
+            Var           *var;
+
+            if (!IsA(node, Var))
+            {
+                trivial_pathtarget = false;
+                break;
+            }
+            var = (Var *) node;
+            if (var->varno != rti ||
+                var->varattno != foreach_current_index(lc) + 1)
+            {
+                trivial_pathtarget = false;
+                break;
+            }
+        }
+    }
+
     /*
      * For each Path that subquery_planner produced, make a SubqueryScanPath
      * in the outer query.
@@ -2615,6 +2646,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
         /* Generate outer path using this subpath */
         add_path(rel, (Path *)
                  create_subqueryscan_path(root, rel, subpath,
+                                          trivial_pathtarget,
                                           pathkeys, required_outer));
     }

@@ -2640,6 +2672,7 @@ set_subquery_pathlist(PlannerInfo *root, RelOptInfo *rel,
             /* Generate outer path using this subpath */
             add_partial_path(rel, (Path *)
                              create_subqueryscan_path(root, rel, subpath,
+                                                      trivial_pathtarget,
                                                       pathkeys,
                                                       required_outer));
         }
diff --git a/src/backend/optimizer/path/costsize.c b/src/backend/optimizer/path/costsize.c
index 6673d271c2..efb58f083a 100644
--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -1388,10 +1388,12 @@ cost_tidrangescan(Path *path, PlannerInfo *root,
  *
  * 'baserel' is the relation to be scanned
  * 'param_info' is the ParamPathInfo if this is a parameterized path, else NULL
+ * 'trivial_pathtarget' is true if the pathtarget is believed to be trivial.
  */
 void
 cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root,
-                  RelOptInfo *baserel, ParamPathInfo *param_info)
+                  RelOptInfo *baserel, ParamPathInfo *param_info,
+                  bool trivial_pathtarget)
 {
     Cost        startup_cost;
     Cost        run_cost;
@@ -1431,6 +1433,22 @@ cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root,
     path->path.startup_cost = path->subpath->startup_cost;
     path->path.total_cost = path->subpath->total_cost;

+    /*
+     * However, if there are no relevant restriction clauses and the
+     * pathtarget is trivial, then we expect that setrefs.c will optimize away
+     * the SubqueryScan plan node altogether, so we should just make its cost
+     * and rowcount equal to the input path's.
+     *
+     * Note: there are some edge cases where createplan.c will apply a
+     * different targetlist to the SubqueryScan node, thus falsifying our
+     * current estimate of whether the target is trivial, and making the cost
+     * estimate (though not the rowcount) wrong.  It does not seem worth the
+     * extra complication to try to account for that exactly, especially since
+     * that behavior falsifies other cost estimates as well.
+     */
+    if (qpquals == NIL && trivial_pathtarget)
+        return;
+
     get_restriction_qual_cost(root, baserel, param_info, &qpqual_cost);

     startup_cost = qpqual_cost.startup;
diff --git a/src/backend/optimizer/prep/prepunion.c b/src/backend/optimizer/prep/prepunion.c
index f004fad1d9..2214920dea 100644
--- a/src/backend/optimizer/prep/prepunion.c
+++ b/src/backend/optimizer/prep/prepunion.c
@@ -78,7 +78,8 @@ static List *generate_setop_tlist(List *colTypes, List *colCollations,
                                   Index varno,
                                   bool hack_constants,
                                   List *input_tlist,
-                                  List *refnames_tlist);
+                                  List *refnames_tlist,
+                                  bool *trivial_tlist);
 static List *generate_append_tlist(List *colTypes, List *colCollations,
                                    bool flag,
                                    List *input_tlists,
@@ -226,6 +227,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
         Path       *subpath;
         Path       *path;
         List       *tlist;
+        bool        trivial_tlist;

         Assert(subquery != NULL);

@@ -254,7 +256,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
                                      rtr->rtindex,
                                      true,
                                      subroot->processed_tlist,
-                                     refnames_tlist);
+                                     refnames_tlist,
+                                     &trivial_tlist);
         rel->reltarget = create_pathtarget(root, tlist);

         /* Return the fully-fledged tlist to caller, too */
@@ -291,6 +294,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
          * soon too, likely.)
          */
         path = (Path *) create_subqueryscan_path(root, rel, subpath,
+                                                 trivial_tlist,
                                                  NIL, NULL);

         add_path(rel, path);
@@ -309,6 +313,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
             partial_subpath = linitial(final_rel->partial_pathlist);
             partial_path = (Path *)
                 create_subqueryscan_path(root, rel, partial_subpath,
+                                         trivial_tlist,
                                          NIL, NULL);
             add_partial_path(rel, partial_path);
         }
@@ -376,6 +381,7 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
             !tlist_same_collations(*pTargetList, colCollations, junkOK))
         {
             PathTarget *target;
+            bool        trivial_tlist;
             ListCell   *lc;

             *pTargetList = generate_setop_tlist(colTypes, colCollations,
@@ -383,7 +389,8 @@ recurse_set_operations(Node *setOp, PlannerInfo *root,
                                                 0,
                                                 false,
                                                 *pTargetList,
-                                                refnames_tlist);
+                                                refnames_tlist,
+                                                &trivial_tlist);
             target = create_pathtarget(root, *pTargetList);

             /* Apply projection to each path */
@@ -1117,6 +1124,7 @@ choose_hashed_setop(PlannerInfo *root, List *groupClauses,
  * hack_constants: true to copy up constants (see comments in code)
  * input_tlist: targetlist of this node's input node
  * refnames_tlist: targetlist to take column names from
+ * trivial_tlist: output parameter, set to true if targetlist is trivial
  */
 static List *
 generate_setop_tlist(List *colTypes, List *colCollations,
@@ -1124,7 +1132,8 @@ generate_setop_tlist(List *colTypes, List *colCollations,
                      Index varno,
                      bool hack_constants,
                      List *input_tlist,
-                     List *refnames_tlist)
+                     List *refnames_tlist,
+                     bool *trivial_tlist)
 {
     List       *tlist = NIL;
     int            resno = 1;
@@ -1135,6 +1144,8 @@ generate_setop_tlist(List *colTypes, List *colCollations,
     TargetEntry *tle;
     Node       *expr;

+    *trivial_tlist = true;        /* until proven differently */
+
     forfour(ctlc, colTypes, cclc, colCollations,
             itlc, input_tlist, rtlc, refnames_tlist)
     {
@@ -1160,6 +1171,9 @@ generate_setop_tlist(List *colTypes, List *colCollations,
          * this only at the first level of subquery-scan plans; we don't want
          * phony constants appearing in the output tlists of upper-level
          * nodes!
+         *
+         * Note that copying a constant doesn't in itself require us to mark
+         * the tlist nontrivial; see trivial_subqueryscan() in setrefs.c.
          */
         if (hack_constants && inputtle->expr && IsA(inputtle->expr, Const))
             expr = (Node *) inputtle->expr;
@@ -1185,6 +1199,7 @@ generate_setop_tlist(List *colTypes, List *colCollations,
                                          expr,
                                          colType,
                                          "UNION/INTERSECT/EXCEPT");
+            *trivial_tlist = false; /* the coercion makes it not trivial */
         }

         /*
@@ -1199,9 +1214,12 @@ generate_setop_tlist(List *colTypes, List *colCollations,
          * will reach the executor without any further processing.
          */
         if (exprCollation(expr) != colColl)
+        {
             expr = applyRelabelType(expr,
                                     exprType(expr), exprTypmod(expr), colColl,
                                     COERCE_IMPLICIT_CAST, -1, false);
+            *trivial_tlist = false; /* the relabel makes it not trivial */
+        }

         tle = makeTargetEntry((Expr *) expr,
                               (AttrNumber) resno++,
@@ -1234,6 +1252,7 @@ generate_setop_tlist(List *colTypes, List *colCollations,
                               pstrdup("flag"),
                               true);
         tlist = lappend(tlist, tle);
+        *trivial_tlist = false; /* the extra entry makes it not trivial */
     }

     return tlist;
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index e2a3c110ce..00ebf34093 100644
--- a/src/backend/optimizer/util/pathnode.c
+++ b/src/backend/optimizer/util/pathnode.c
@@ -1986,9 +1986,15 @@ create_gather_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
  * create_subqueryscan_path
  *      Creates a path corresponding to a scan of a subquery,
  *      returning the pathnode.
+ *
+ * Caller must pass trivial_pathtarget = true if it believes rel->reltarget to
+ * be trivial, ie just a fetch of all the subquery output columns in order.
+ * While we could determine that here, the caller can usually do it more
+ * efficiently (or at least amortize it over multiple calls).
  */
 SubqueryScanPath *
 create_subqueryscan_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
+                         bool trivial_pathtarget,
                          List *pathkeys, Relids required_outer)
 {
     SubqueryScanPath *pathnode = makeNode(SubqueryScanPath);
@@ -2005,7 +2011,8 @@ create_subqueryscan_path(PlannerInfo *root, RelOptInfo *rel, Path *subpath,
     pathnode->path.pathkeys = pathkeys;
     pathnode->subpath = subpath;

-    cost_subqueryscan(pathnode, root, rel, pathnode->path.param_info);
+    cost_subqueryscan(pathnode, root, rel, pathnode->path.param_info,
+                      trivial_pathtarget);

     return pathnode;
 }
@@ -3903,10 +3910,23 @@ reparameterize_path(PlannerInfo *root, Path *path,
         case T_SubqueryScan:
             {
                 SubqueryScanPath *spath = (SubqueryScanPath *) path;
+                Path       *subpath = spath->subpath;
+                bool        trivial_pathtarget;
+
+                /*
+                 * If existing node has zero extra cost, we must have decided
+                 * its target is trivial.  (The converse is not true, because
+                 * it might have a trivial target but quals to enforce; but in
+                 * that case the new node will too, so it doesn't matter
+                 * whether we get the right answer here.)
+                 */
+                trivial_pathtarget =
+                    (subpath->total_cost == spath->path.total_cost);

                 return (Path *) create_subqueryscan_path(root,
                                                          rel,
-                                                         spath->subpath,
+                                                         subpath,
+                                                         trivial_pathtarget,
                                                          spath->path.pathkeys,
                                                          required_outer);
             }
diff --git a/src/include/optimizer/cost.h b/src/include/optimizer/cost.h
index dc7fc17411..9e91da7114 100644
--- a/src/include/optimizer/cost.h
+++ b/src/include/optimizer/cost.h
@@ -91,7 +91,8 @@ extern void cost_tidrangescan(Path *path, PlannerInfo *root,
                               RelOptInfo *baserel, List *tidrangequals,
                               ParamPathInfo *param_info);
 extern void cost_subqueryscan(SubqueryScanPath *path, PlannerInfo *root,
-                              RelOptInfo *baserel, ParamPathInfo *param_info);
+                              RelOptInfo *baserel, ParamPathInfo *param_info,
+                              bool trivial_pathtarget);
 extern void cost_functionscan(Path *path, PlannerInfo *root,
                               RelOptInfo *baserel, ParamPathInfo *param_info);
 extern void cost_valuesscan(Path *path, PlannerInfo *root,
diff --git a/src/include/optimizer/pathnode.h b/src/include/optimizer/pathnode.h
index d2d46b15df..376eec8444 100644
--- a/src/include/optimizer/pathnode.h
+++ b/src/include/optimizer/pathnode.h
@@ -103,8 +103,11 @@ extern GatherMergePath *create_gather_merge_path(PlannerInfo *root,
                                                  Relids required_outer,
                                                  double *rows);
 extern SubqueryScanPath *create_subqueryscan_path(PlannerInfo *root,
-                                                  RelOptInfo *rel, Path *subpath,
-                                                  List *pathkeys, Relids required_outer);
+                                                  RelOptInfo *rel,
+                                                  Path *subpath,
+                                                  bool trivial_pathtarget,
+                                                  List *pathkeys,
+                                                  Relids required_outer);
 extern Path *create_functionscan_path(PlannerInfo *root, RelOptInfo *rel,
                                       List *pathkeys, Relids required_outer);
 extern Path *create_valuesscan_path(PlannerInfo *root, RelOptInfo *rel,
diff --git a/src/test/regress/expected/create_view.out b/src/test/regress/expected/create_view.out
index 32385bbb0e..9d4f9011a8 100644
--- a/src/test/regress/expected/create_view.out
+++ b/src/test/regress/expected/create_view.out
@@ -1976,18 +1976,18 @@ select * from tt24v;
 ------------------------------------------------------------------------------------------
  Hash Join
    Output: (cte.r).column2, ((ROW("*VALUES*".column1, "*VALUES*".column2))).column2
-   Hash Cond: (((ROW("*VALUES*".column1, "*VALUES*".column2))).column1 = (cte.r).column1)
+   Hash Cond: ((cte.r).column1 = ((ROW("*VALUES*".column1, "*VALUES*".column2))).column1)
    CTE cte
      ->  Values Scan on "*VALUES*_1"
            Output: ROW("*VALUES*_1".column1, "*VALUES*_1".column2)
-   ->  Limit
-         Output: (ROW("*VALUES*".column1, "*VALUES*".column2))
-         ->  Values Scan on "*VALUES*"
-               Output: ROW("*VALUES*".column1, "*VALUES*".column2)
-   ->  Hash
+   ->  CTE Scan on cte
          Output: cte.r
-         ->  CTE Scan on cte
-               Output: cte.r
+   ->  Hash
+         Output: (ROW("*VALUES*".column1, "*VALUES*".column2))
+         ->  Limit
+               Output: (ROW("*VALUES*".column1, "*VALUES*".column2))
+               ->  Values Scan on "*VALUES*"
+                     Output: ROW("*VALUES*".column1, "*VALUES*".column2)
 (14 rows)

 explain (verbose, costs off)
diff --git a/src/test/regress/expected/join.out b/src/test/regress/expected/join.out
index bf1a2db2cf..4c25743200 100644
--- a/src/test/regress/expected/join.out
+++ b/src/test/regress/expected/join.out
@@ -5180,11 +5180,11 @@ explain (costs off)
    Sort Key: a.q1, a.q2, x.q1, x.q2, (a.q1)
    ->  Nested Loop
          ->  Seq Scan on int8_tbl a
-         ->  Hash Right Join
-               Hash Cond: ((a.q1) = x.q2)
-               ->  Seq Scan on int4_tbl y
+         ->  Hash Left Join
+               Hash Cond: (x.q2 = (a.q1))
+               ->  Seq Scan on int8_tbl x
                ->  Hash
-                     ->  Seq Scan on int8_tbl x
+                     ->  Seq Scan on int4_tbl y
 (9 rows)

 select * from int8_tbl a,