Re: Inheritance planner CPU and memory usage change since 9.3.2

Robert Haas <robertmhaas@gmail.com> writes:
> Meanwhile, here is an updated patch.

I don't care for that patch too much: it seems a bit brute-force, and I'm
quite worried by the assumption that it's okay to destroy each child's
append_rel_list after processing the child.  That would fail if any of
the Vars/subexpressions in the lists get incorporated into the resulting
child Plan, which does not seem impossible.  (I think in many cases we'd
do a copyObject() when extracting an append_rel_list expression, but this
hardly seems guaranteed.)

I propose instead the attached patch, which operates by identifying which
of the append_rel_list entries actually contain subquery references, and
copying only those; the other ones are just linked into the child's
append_rel_list by reference, which is okay because they won't get
modified.

On my laptop, I get the following timings for your test queries from
unmodified HEAD (--cassert build):

# Q1: 41260.239 ms
# Q2: 45225.768 ms
# Q3: 43066.958 ms
# Q4: 193360.726 ms
# Q5: 40746.503 ms

and these with my patch:

# Q1: 1767.753 ms
# Q2: 3662.131 ms
# Q3: 814.293 ms
# Q4: 64468.914 ms
# Q5: 881.295 ms

which seems to be generally a better result.

> The extraordinarily planning time for query 4 is caused by a
> completely different problem: SearchCatCache eats up huge amounts of
> CPU; its callers are get_attavgwidth and get_typlen.  It's not clear
> to me why doubling the number of relations causes such an enormous
> explosion in calls to those functions; I would expect the number of
> calls to double, but presumably the actual increase is much more.

Actually, Q4 necessarily involves O(N^2) planning time, because for
each of N target relations you're considering a join to an N-member
inheritance tree.  A lot of those ultimately get thrown away by
constraint exclusion, but not before we've expended significant
cycles on them.  I do not think we are going to get much traction
on that --- even if we do something to knock off whatever the leading
term is, there'll still be more O(N^2) behavior right behind it.

            regards, tom lane

diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c
index 8afde2b7d5069707e346901f819bed888a2333ee..d7fee96ba01272efdf7231d5985ab688912bcf58 100644
*** a/src/backend/optimizer/plan/planner.c
--- b/src/backend/optimizer/plan/planner.c
*************** inheritance_planner(PlannerInfo *root)
*** 834,840 ****
  {
      Query       *parse = root->parse;
      int            parentRTindex = parse->resultRelation;
!     Bitmapset  *resultRTindexes = NULL;
      int            nominalRelation = -1;
      List       *final_rtable = NIL;
      int            save_rel_array_size = 0;
--- 834,842 ----
  {
      Query       *parse = root->parse;
      int            parentRTindex = parse->resultRelation;
!     Bitmapset  *resultRTindexes;
!     Bitmapset  *subqueryRTindexes;
!     Bitmapset  *modifiableARIindexes;
      int            nominalRelation = -1;
      List       *final_rtable = NIL;
      int            save_rel_array_size = 0;
*************** inheritance_planner(PlannerInfo *root)
*** 845,850 ****
--- 847,853 ----
      List       *returningLists = NIL;
      List       *rowMarks;
      ListCell   *lc;
+     Index        rti;

      Assert(parse->commandType != CMD_INSERT);

*************** inheritance_planner(PlannerInfo *root)
*** 867,874 ****
       * subqueries during planning, and so we must create copies of them too,
       * except where they are target relations, which will each only be used in
       * a single plan.
       */
!     resultRTindexes = bms_add_member(resultRTindexes, parentRTindex);
      foreach(lc, root->append_rel_list)
      {
          AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
--- 870,879 ----
       * subqueries during planning, and so we must create copies of them too,
       * except where they are target relations, which will each only be used in
       * a single plan.
+      *
+      * To begin with, we'll need a bitmapset of the target relation relids.
       */
!     resultRTindexes = bms_make_singleton(parentRTindex);
      foreach(lc, root->append_rel_list)
      {
          AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
*************** inheritance_planner(PlannerInfo *root)
*** 878,889 ****
                                               appinfo->child_relid);
      }

      foreach(lc, root->append_rel_list)
      {
          AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
          PlannerInfo subroot;
          Plan       *subplan;
!         Index        rti;

          /* append_rel_list contains all append rels; ignore others */
          if (appinfo->parent_relid != parentRTindex)
--- 883,937 ----
                                               appinfo->child_relid);
      }

+     /*
+      * Now, generate a bitmapset of the relids of the subquery RTEs, including
+      * security-barrier RTEs that will become subqueries, as just explained.
+      */
+     subqueryRTindexes = NULL;
+     rti = 1;
+     foreach(lc, parse->rtable)
+     {
+         RangeTblEntry *rte = (RangeTblEntry *) lfirst(lc);
+
+         if (rte->rtekind == RTE_SUBQUERY ||
+             (rte->securityQuals != NIL &&
+              !bms_is_member(rti, resultRTindexes)))
+             subqueryRTindexes = bms_add_member(subqueryRTindexes, rti);
+         rti++;
+     }
+
+     /*
+      * Next, we want to identify which AppendRelInfo items contain references
+      * to any of the aforesaid subquery RTEs.  These items will need to be
+      * copied and modified to adjust their subquery references; whereas the
+      * other ones need not be touched.  It's worth being tense over this
+      * because we can usually avoid processing most of the AppendRelInfo
+      * items, thereby saving O(N^2) space and time when the target is a large
+      * inheritance tree.  We can identify AppendRelInfo items by their
+      * child_relid, since that should be unique within the list.
+      */
+     modifiableARIindexes = NULL;
+     foreach(lc, root->append_rel_list)
+     {
+         AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
+
+         if (bms_is_member(appinfo->parent_relid, subqueryRTindexes) ||
+             bms_is_member(appinfo->child_relid, subqueryRTindexes) ||
+             bms_overlap(pull_varnos((Node *) appinfo->translated_vars),
+                         subqueryRTindexes))
+             modifiableARIindexes = bms_add_member(modifiableARIindexes,
+                                                   appinfo->child_relid);
+     }
+
+     /*
+      * And now we can get on with generating a plan for each child table.
+      */
      foreach(lc, root->append_rel_list)
      {
          AppendRelInfo *appinfo = (AppendRelInfo *) lfirst(lc);
          PlannerInfo subroot;
          Plan       *subplan;
!         ListCell   *lc2;

          /* append_rel_list contains all append rels; ignore others */
          if (appinfo->parent_relid != parentRTindex)
*************** inheritance_planner(PlannerInfo *root)
*** 917,925 ****
          /*
           * The append_rel_list likewise might contain references to subquery
           * RTEs (if any subqueries were flattenable UNION ALLs).  So prepare
!          * to apply ChangeVarNodes to that, too.
           */
!         subroot.append_rel_list = (List *) copyObject(root->append_rel_list);

          /*
           * Add placeholders to the child Query's rangetable list to fill the
--- 965,985 ----
          /*
           * The append_rel_list likewise might contain references to subquery
           * RTEs (if any subqueries were flattenable UNION ALLs).  So prepare
!          * to apply ChangeVarNodes to that, too.  As explained above, we only
!          * want to copy items that actually contain such references; the
!          * rest can just get linked into the subroot's append_rel_list.
           */
!         subroot.append_rel_list = NIL;
!         foreach(lc2, root->append_rel_list)
!         {
!             AppendRelInfo *appinfo2 = (AppendRelInfo *) lfirst(lc2);
!
!             if (bms_is_member(appinfo2->child_relid, modifiableARIindexes))
!                 appinfo2 = (AppendRelInfo *) copyObject(appinfo2);
!
!             subroot.append_rel_list = lappend(subroot.append_rel_list,
!                                               appinfo2);
!         }

          /*
           * Add placeholders to the child Query's rangetable list to fill the
*************** inheritance_planner(PlannerInfo *root)
*** 933,945 ****

          /*
           * If this isn't the first child Query, generate duplicates of all
!          * subquery RTEs, and adjust Var numbering to reference the
!          * duplicates. To simplify the loop logic, we scan the original rtable
!          * not the copy just made by adjust_appendrel_attrs; that should be OK
!          * since subquery RTEs couldn't contain any references to the target
!          * rel.
           */
!         if (final_rtable != NIL)
          {
              ListCell   *lr;

--- 993,1005 ----

          /*
           * If this isn't the first child Query, generate duplicates of all
!          * subquery (or subquery-to-be) RTEs, and adjust Var numbering to
!          * reference the duplicates.  To simplify the loop logic, we scan the
!          * original rtable not the copy just made by adjust_appendrel_attrs;
!          * that should be OK since subquery RTEs couldn't contain any
!          * references to the target rel.
           */
!         if (final_rtable != NIL && !bms_is_empty(subqueryRTindexes))
          {
              ListCell   *lr;

*************** inheritance_planner(PlannerInfo *root)
*** 948,961 ****
              {
                  RangeTblEntry *rte = (RangeTblEntry *) lfirst(lr);

!                 /*
!                  * Copy subquery RTEs and RTEs with security barrier quals
!                  * that will be turned into subqueries, except those that are
!                  * target relations.
!                  */
!                 if (rte->rtekind == RTE_SUBQUERY ||
!                     (rte->securityQuals != NIL &&
!                      !bms_is_member(rti, resultRTindexes)))
                  {
                      Index        newrti;

--- 1008,1014 ----
              {
                  RangeTblEntry *rte = (RangeTblEntry *) lfirst(lr);

!                 if (bms_is_member(rti, subqueryRTindexes))
                  {
                      Index        newrti;