Re: nested loop semijoin estimates - Mailing list pgsql-hackers

Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
> On 05/30/15 23:16, Tom Lane wrote:
>> Attached is a draft patch for that.  It fixes the problem for me:

> Seems to be working OK, but I still do get a Bitmap Heap Scan there (but
> more about that later).

Attached is an incremental patch (on top of the previous one) to allow
startup cost of parameterized paths to be considered when the relation
is the RHS of a semi or anti join.  It seems reasonably clean except
for one thing: logically, we perhaps should remove the checks on
path->param_info from the last half of compare_path_costs_fuzzily(),
so as to increase the symmetry between parameterized paths and
unparameterized ones.  However, when I did that, I got changes in some
of the regression test plans, and they didn't seem to be for the better.
So I left that alone.  As-is, this patch doesn't seem to affect the
results for any existing regression tests.

> Do you plan to push that into 9.5, or 9.6? I assume it's a behavior
> change so that no back-patching, right?

Mumble.  It's definitely a planner bug fix, and I believe that the effects
are narrowly constrained to cases where significantly better plans are
possible.  So personally I'd be willing to back-patch it.  But others
might see that differently, especially since it's been like this for a
long time and we only have one field complaint.

            regards, tom lane

diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 4775acf..87304ba 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outRelOptInfo(StringInfo str, const Rel
*** 1844,1849 ****
--- 1844,1850 ----
      WRITE_FLOAT_FIELD(rows, "%.0f");
      WRITE_INT_FIELD(width);
      WRITE_BOOL_FIELD(consider_startup);
+     WRITE_BOOL_FIELD(consider_param_startup);
      WRITE_NODE_FIELD(reltargetlist);
      WRITE_NODE_FIELD(pathlist);
      WRITE_NODE_FIELD(ppilist);
diff --git a/src/backend/optimizer/README b/src/backend/optimizer/README
index d51fd57..d1349aa 100644
*** a/src/backend/optimizer/README
--- b/src/backend/optimizer/README
*************** a nestloop that provides parameters to t
*** 795,801 ****
  do not ignore merge joins entirely, joinpath.c does not fully explore the
  space of potential merge joins with parameterized inputs.  Also, add_path
  treats parameterized paths as having no pathkeys, so that they compete
! only on total cost and rowcount; they don't get preference for producing a
  special sort order.  This creates additional bias against merge joins,
  since we might discard a path that could have been useful for performing
  a merge without an explicit sort step.  Since a parameterized path must
--- 795,801 ----
  do not ignore merge joins entirely, joinpath.c does not fully explore the
  space of potential merge joins with parameterized inputs.  Also, add_path
  treats parameterized paths as having no pathkeys, so that they compete
! only on cost and rowcount; they don't get preference for producing a
  special sort order.  This creates additional bias against merge joins,
  since we might discard a path that could have been useful for performing
  a merge without an explicit sort step.  Since a parameterized path must
*************** uninteresting, these choices do not affe
*** 804,809 ****
--- 804,817 ----
  output order of a query --- they only make it harder to use a merge join
  at a lower level.  The savings in planning work justifies that.

+ Similarly, parameterized paths do not normally get preference in add_path
+ for having cheap startup cost; that's seldom of much value when on the
+ inside of a nestloop, so it seems not worth keeping extra paths solely for
+ that.  An exception occurs for parameterized paths for the RHS relation of
+ a SEMI or ANTI join: in those cases, we can stop the inner scan after the
+ first match, so that it's primarily startup not total cost that we care
+ about.
+

  LATERAL subqueries
  ------------------
diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c
index 4e6d90d..0b83189 100644
*** a/src/backend/optimizer/path/allpaths.c
--- b/src/backend/optimizer/path/allpaths.c
*************** set_rel_pathlist_hook_type set_rel_pathl
*** 61,66 ****
--- 61,67 ----
  join_search_hook_type join_search_hook = NULL;


+ static void set_base_rel_consider_startup(PlannerInfo *root);
  static void set_base_rel_sizes(PlannerInfo *root);
  static void set_base_rel_pathlists(PlannerInfo *root);
  static void set_rel_size(PlannerInfo *root, RelOptInfo *rel,
*************** make_one_rel(PlannerInfo *root, List *jo
*** 152,157 ****
--- 153,161 ----
          root->all_baserels = bms_add_member(root->all_baserels, brel->relid);
      }

+     /* Mark base rels as to whether we care about fast-start plans */
+     set_base_rel_consider_startup(root);
+
      /*
       * Generate access paths for the base rels.
       */
*************** make_one_rel(PlannerInfo *root, List *jo
*** 172,177 ****
--- 176,224 ----
  }

  /*
+  * set_base_rel_consider_startup
+  *      Set the consider_[param_]startup flags for each base-relation entry.
+  *
+  * For the moment, we only deal with consider_param_startup here; because the
+  * logic for consider_startup is pretty trivial and is the same for every base
+  * relation, we just let build_simple_rel() initialize that flag correctly to
+  * start with.  If that logic ever gets more complicated it would probably
+  * be better to move it here.
+  */
+ static void
+ set_base_rel_consider_startup(PlannerInfo *root)
+ {
+     /*
+      * Since parameterized paths can only be used on the inside of a nestloop
+      * join plan, there is usually little value in considering fast-start
+      * plans for them.  However, for relations that are on the RHS of a SEMI
+      * or ANTI join, a fast-start plan can be useful because we're only going
+      * to care about fetching one tuple anyway.
+      *
+      * To minimize growth of planning time, we currently restrict this to
+      * cases where the RHS is a single base relation, not a join; there is no
+      * provision for consider_param_startup to get set at all on joinrels.
+      * Also we don't worry about appendrels.  costsize.c's costing rules for
+      * nestloop semi/antijoins don't consider such cases either.
+      */
+     ListCell   *lc;
+
+     foreach(lc, root->join_info_list)
+     {
+         SpecialJoinInfo *sjinfo = (SpecialJoinInfo *) lfirst(lc);
+         int            varno;
+
+         if ((sjinfo->jointype == JOIN_SEMI || sjinfo->jointype == JOIN_ANTI) &&
+             bms_get_singleton_member(sjinfo->syn_righthand, &varno))
+         {
+             RelOptInfo *rel = find_base_rel(root, varno);
+
+             rel->consider_param_startup = true;
+         }
+     }
+ }
+
+ /*
   * set_base_rel_sizes
   *      Set the size estimates (rows and widths) for each base-relation entry.
   *
diff --git a/src/backend/optimizer/util/pathnode.c b/src/backend/optimizer/util/pathnode.c
index 7f7aa24..2afd59a 100644
*** a/src/backend/optimizer/util/pathnode.c
--- b/src/backend/optimizer/util/pathnode.c
*************** compare_fractional_path_costs(Path *path
*** 138,156 ****
   * total cost, we just say that their costs are "different", since neither
   * dominates the other across the whole performance spectrum.
   *
!  * If consider_startup is false, then we don't care about keeping paths with
!  * good startup cost, so we'll never return COSTS_DIFFERENT.
!  *
!  * This function also includes special hacks to support a policy enforced
!  * by its sole caller, add_path(): paths that have any parameterization
!  * cannot win comparisons on the grounds of having cheaper startup cost,
!  * since we deem only total cost to be of interest for a parameterized path.
!  * (Unparameterized paths are more common, so we check for this case last.)
   */
  static PathCostComparison
! compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor,
!                            bool consider_startup)
  {
      /*
       * Check total cost first since it's more likely to be different; many
       * paths have zero startup cost.
--- 138,154 ----
   * total cost, we just say that their costs are "different", since neither
   * dominates the other across the whole performance spectrum.
   *
!  * This function also enforces a policy rule that paths for which the relevant
!  * one of parent->consider_startup and parent->consider_param_startup is false
!  * cannot win comparisons on the grounds of good startup cost, so we never
!  * return COSTS_DIFFERENT when that is true for the total-cost loser.
   */
  static PathCostComparison
! compare_path_costs_fuzzily(Path *path1, Path *path2, double fuzz_factor)
  {
+ #define CONSIDER_PATH_STARTUP_COST(p)  \
+     ((p)->param_info == NULL ? (p)->parent->consider_startup : (p)->parent->consider_param_startup)
+
      /*
       * Check total cost first since it's more likely to be different; many
       * paths have zero startup cost.
*************** compare_path_costs_fuzzily(Path *path1,
*** 158,166 ****
      if (path1->total_cost > path2->total_cost * fuzz_factor)
      {
          /* path1 fuzzily worse on total cost */
!         if (consider_startup &&
!             path2->startup_cost > path1->startup_cost * fuzz_factor &&
!             path1->param_info == NULL)
          {
              /* ... but path2 fuzzily worse on startup, so DIFFERENT */
              return COSTS_DIFFERENT;
--- 156,163 ----
      if (path1->total_cost > path2->total_cost * fuzz_factor)
      {
          /* path1 fuzzily worse on total cost */
!         if (CONSIDER_PATH_STARTUP_COST(path1) &&
!             path2->startup_cost > path1->startup_cost * fuzz_factor)
          {
              /* ... but path2 fuzzily worse on startup, so DIFFERENT */
              return COSTS_DIFFERENT;
*************** compare_path_costs_fuzzily(Path *path1,
*** 171,179 ****
      if (path2->total_cost > path1->total_cost * fuzz_factor)
      {
          /* path2 fuzzily worse on total cost */
!         if (consider_startup &&
!             path1->startup_cost > path2->startup_cost * fuzz_factor &&
!             path2->param_info == NULL)
          {
              /* ... but path1 fuzzily worse on startup, so DIFFERENT */
              return COSTS_DIFFERENT;
--- 168,175 ----
      if (path2->total_cost > path1->total_cost * fuzz_factor)
      {
          /* path2 fuzzily worse on total cost */
!         if (CONSIDER_PATH_STARTUP_COST(path2) &&
!             path1->startup_cost > path2->startup_cost * fuzz_factor)
          {
              /* ... but path1 fuzzily worse on startup, so DIFFERENT */
              return COSTS_DIFFERENT;
*************** compare_path_costs_fuzzily(Path *path1,
*** 181,188 ****
          /* else path1 dominates */
          return COSTS_BETTER1;
      }
!     /* fuzzily the same on total cost */
!     /* (so we may as well compare startup cost, even if !consider_startup) */
      if (path1->startup_cost > path2->startup_cost * fuzz_factor &&
          path2->param_info == NULL)
      {
--- 177,189 ----
          /* else path1 dominates */
          return COSTS_BETTER1;
      }
!
!     /*
!      * Fuzzily the same on total cost (so we might as well compare startup
!      * cost, even when that would otherwise be uninteresting; but
!      * parameterized paths aren't allowed to win this way, we'd rather move on
!      * to other comparison heuristics)
!      */
      if (path1->startup_cost > path2->startup_cost * fuzz_factor &&
          path2->param_info == NULL)
      {
*************** compare_path_costs_fuzzily(Path *path1,
*** 197,202 ****
--- 198,205 ----
      }
      /* fuzzily the same on both costs */
      return COSTS_EQUAL;
+
+ #undef CONSIDER_PATH_STARTUP_COST
  }

  /*
*************** compare_path_costs_fuzzily(Path *path1,
*** 212,222 ****
   *
   * The cheapest_parameterized_paths list collects all parameterized paths
   * that have survived the add_path() tournament for this relation.  (Since
!  * add_path ignores pathkeys and startup cost for a parameterized path,
!  * these will be paths that have best total cost or best row count for their
!  * parameterization.)  cheapest_parameterized_paths always includes the
!  * cheapest-total unparameterized path, too, if there is one; the users of
!  * that list find it more convenient if that's included.
   *
   * This is normally called only after we've finished constructing the path
   * list for the rel node.
--- 215,225 ----
   *
   * The cheapest_parameterized_paths list collects all parameterized paths
   * that have survived the add_path() tournament for this relation.  (Since
!  * add_path ignores pathkeys for a parameterized path, these will be paths
!  * that have best cost or best row count for their parameterization.)
!  * cheapest_parameterized_paths always includes the cheapest-total
!  * unparameterized path, too, if there is one; the users of that list find
!  * it more convenient if that's included.
   *
   * This is normally called only after we've finished constructing the path
   * list for the rel node.
*************** set_cheapest(RelOptInfo *parent_rel)
*** 361,374 ****
   *      cases do arise, so we make the full set of checks anyway.
   *
   *      There are two policy decisions embedded in this function, along with
!  *      its sibling add_path_precheck: we treat all parameterized paths as
!  *      having NIL pathkeys, and we ignore their startup costs, so that they
!  *      compete only on parameterization, total cost and rowcount.  This is to
!  *      reduce the number of parameterized paths that are kept.  See discussion
!  *      in src/backend/optimizer/README.
   *
!  *      Another policy that is enforced here is that we only consider cheap
!  *      startup cost to be interesting if parent_rel->consider_startup is true.
   *
   *      The pathlist is kept sorted by total_cost, with cheaper paths
   *      at the front.  Within this routine, that's simply a speed hack:
--- 364,378 ----
   *      cases do arise, so we make the full set of checks anyway.
   *
   *      There are two policy decisions embedded in this function, along with
!  *      its sibling add_path_precheck.  First, we treat all parameterized paths
!  *      as having NIL pathkeys, so that they cannot win comparisons on the
!  *      basis of sort order.  This is to reduce the number of parameterized
!  *      paths that are kept; see discussion in src/backend/optimizer/README.
   *
!  *      Second, we only consider cheap startup cost to be interesting if
!  *      parent_rel->consider_startup is true for an unparameterized path, or
!  *      parent_rel->consider_param_startup is true for a parameterized one.
!  *      Again, this allows discarding useless paths sooner.
   *
   *      The pathlist is kept sorted by total_cost, with cheaper paths
   *      at the front.  Within this routine, that's simply a speed hack:
*************** add_path(RelOptInfo *parent_rel, Path *n
*** 433,440 ****
           * Do a fuzzy cost comparison with 1% fuzziness limit.  (XXX does this
           * percentage need to be user-configurable?)
           */
!         costcmp = compare_path_costs_fuzzily(new_path, old_path, 1.01,
!                                              parent_rel->consider_startup);

          /*
           * If the two paths compare differently for startup and total cost,
--- 437,443 ----
           * Do a fuzzy cost comparison with 1% fuzziness limit.  (XXX does this
           * percentage need to be user-configurable?)
           */
!         costcmp = compare_path_costs_fuzzily(new_path, old_path, 1.01);

          /*
           * If the two paths compare differently for startup and total cost,
*************** add_path(RelOptInfo *parent_rel, Path *n
*** 501,508 ****
                                      accept_new = false; /* old dominates new */
                                  else if (compare_path_costs_fuzzily(new_path,
                                                                      old_path,
!                                                                 1.0000000001,
!                                                                     parent_rel->consider_startup) == COSTS_BETTER1)
                                      remove_old = true;    /* new dominates old */
                                  else
                                      accept_new = false; /* old equals or
--- 504,510 ----
                                      accept_new = false; /* old dominates new */
                                  else if (compare_path_costs_fuzzily(new_path,
                                                                      old_path,
!                                               1.0000000001) == COSTS_BETTER1)
                                      remove_old = true;    /* new dominates old */
                                  else
                                      accept_new = false; /* old equals or
*************** add_path_precheck(RelOptInfo *parent_rel
*** 622,632 ****
--- 624,638 ----
                    List *pathkeys, Relids required_outer)
  {
      List       *new_path_pathkeys;
+     bool        consider_startup;
      ListCell   *p1;

      /* Pretend parameterized paths have no pathkeys, per add_path policy */
      new_path_pathkeys = required_outer ? NIL : pathkeys;

+     /* Decide whether new path's startup cost is interesting */
+     consider_startup = required_outer ? parent_rel->consider_param_startup : parent_rel->consider_startup;
+
      foreach(p1, parent_rel->pathlist)
      {
          Path       *old_path = (Path *) lfirst(p1);
*************** add_path_precheck(RelOptInfo *parent_rel
*** 644,651 ****
           */
          if (total_cost >= old_path->total_cost)
          {
!             /* can win on startup cost only if unparameterized */
!             if (startup_cost >= old_path->startup_cost || required_outer)
              {
                  /* new path does not win on cost, so check pathkeys... */
                  List       *old_path_pathkeys;
--- 650,657 ----
           */
          if (total_cost >= old_path->total_cost)
          {
!             /* new path can win on startup cost only if consider_startup */
!             if (startup_cost >= old_path->startup_cost || !consider_startup)
              {
                  /* new path does not win on cost, so check pathkeys... */
                  List       *old_path_pathkeys;
diff --git a/src/backend/optimizer/util/relnode.c b/src/backend/optimizer/util/relnode.c
index 1d635cd..be2ef3b 100644
*** a/src/backend/optimizer/util/relnode.c
--- b/src/backend/optimizer/util/relnode.c
*************** build_simple_rel(PlannerInfo *root, int
*** 101,106 ****
--- 101,107 ----
      rel->width = 0;
      /* cheap startup cost is interesting iff not all tuples to be retrieved */
      rel->consider_startup = (root->tuple_fraction > 0);
+     rel->consider_param_startup = false;        /* might get changed later */
      rel->reltargetlist = NIL;
      rel->pathlist = NIL;
      rel->ppilist = NIL;
*************** build_join_rel(PlannerInfo *root,
*** 361,366 ****
--- 362,368 ----
      joinrel->width = 0;
      /* cheap startup cost is interesting iff not all tuples to be retrieved */
      joinrel->consider_startup = (root->tuple_fraction > 0);
+     joinrel->consider_param_startup = false;
      joinrel->reltargetlist = NIL;
      joinrel->pathlist = NIL;
      joinrel->ppilist = NIL;
diff --git a/src/include/nodes/relation.h b/src/include/nodes/relation.h
index 706b6d1..33b0874 100644
*** a/src/include/nodes/relation.h
--- b/src/include/nodes/relation.h
*************** typedef struct PlannerInfo
*** 321,328 ****
   *               clauses have been applied (ie, output rows of a plan for it)
   *        width - avg. number of bytes per tuple in the relation after the
   *                appropriate projections have been done (ie, output width)
!  *        consider_startup - true if there is any value in keeping paths for
   *                           this rel on the basis of having cheap startup cost
   *        reltargetlist - List of Var and PlaceHolderVar nodes for the values
   *                        we need to output from this relation.
   *                        List is in no particular order, but all rels of an
--- 321,329 ----
   *               clauses have been applied (ie, output rows of a plan for it)
   *        width - avg. number of bytes per tuple in the relation after the
   *                appropriate projections have been done (ie, output width)
!  *        consider_startup - true if there is any value in keeping plain paths for
   *                           this rel on the basis of having cheap startup cost
+  *        consider_param_startup - the same for parameterized paths
   *        reltargetlist - List of Var and PlaceHolderVar nodes for the values
   *                        we need to output from this relation.
   *                        List is in no particular order, but all rels of an
*************** typedef struct RelOptInfo
*** 437,442 ****
--- 438,444 ----

      /* per-relation planner control flags */
      bool        consider_startup;        /* keep cheap-startup-cost paths? */
+     bool        consider_param_startup; /* ditto, for parameterized paths? */

      /* materialization information */
      List       *reltargetlist;    /* Vars to be output by scan of relation */