Avoiding deeply nested AND/OR trees in the parser - Mailing list pgsql-hackers

Over in
http://www.postgresql.org/message-id/BAY176-W382A9DE827EBC8E602B7BBC5860@phx.gbl
there's a complaint about getting "stack depth limit exceeded" from a
query of the form

select count(*) from gui_die_summary where (x_coord, y_coord) in
((25,5),(41,13),(25,7),(28,3),(25,8),(34,7),(26,6),(21,10), ...);

when there's a few thousand pairs in the IN list.  The reason for this
is that transformAExprIn() generates a tree of nested OR expressions,
and then recursion in assign_collations_walker() runs out of stack space.
(If assign_collations_walker() hadn't failed, something else probably
would later, so it's wrong to blame that function in particular.)

I reproduced this problem in the regression database using generated
queries like so:

print "explain select * from tenk1 where (thousand, tenthous) in (\n";
for ($i = 0; $i < 10000; $i++) {
  print ",\n" if $i > 0;
  print "($i,$i)";
}
print ");\n";

On my machine, HEAD fails at about 9000 pairs with this test case.

While I commented in the pgsql-novice thread that there are better ways
to do this, it still seems like a limitation we probably ought to fix
if it's not too hard.  In the case of transformAExprIn, we could generate
an N-argument OR or AND node instead of a nest; this is already done
for example in make_row_comparison_op().  The attached quick-hack patch
does so, and I verified that the system could handle a million pairs
with this in place.  (It takes about 20 seconds and 20GB of memory to
plan such a case, so I still say it's a bad idea, but at least we can
do it.)  There is similar code in make_row_distinct_op(), which perhaps
ought to be fixed as well.

However, this isn't exactly the end of the story, because if you were to
dump out a view generated from a query like this, it would contain a long
chain of OR clauses, which would mean that reloading the view would put
you right back in stack overflow territory.  Really if we wanted to fix
this issue we'd need to hack up transformAExprAnd/transformAExprOr so that
they recognized nested ANDs/ORs and flattened them on the spot.  This
might not be a bad idea, but it's starting to look like more than a quick
hack patch.

Does this seem worth pursuing, or shall we leave it alone?

            regards, tom lane

diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 81c9338..9550bd1 100644
*** a/src/backend/parser/parse_expr.c
--- b/src/backend/parser/parse_expr.c
*************** transformAExprOf(ParseState *pstate, A_E
*** 1088,1094 ****
  static Node *
  transformAExprIn(ParseState *pstate, A_Expr *a)
  {
!     Node       *result = NULL;
      Node       *lexpr;
      List       *rexprs;
      List       *rvars;
--- 1088,1095 ----
  static Node *
  transformAExprIn(ParseState *pstate, A_Expr *a)
  {
!     Node       *result;
!     List       *cmpexprs = NIL;
      Node       *lexpr;
      List       *rexprs;
      List       *rvars;
*************** transformAExprIn(ParseState *pstate, A_E
*** 1166,1171 ****
--- 1167,1173 ----
               */
              List       *aexprs;
              ArrayExpr  *newa;
+             Node       *cmp;

              aexprs = NIL;
              foreach(l, rnonvars)
*************** transformAExprIn(ParseState *pstate, A_E
*** 1185,1196 ****
              newa->multidims = false;
              newa->location = -1;

!             result = (Node *) make_scalar_array_op(pstate,
!                                                    a->name,
!                                                    useOr,
!                                                    lexpr,
!                                                    (Node *) newa,
!                                                    a->location);

              /* Consider only the Vars (if any) in the loop below */
              rexprs = rvars;
--- 1187,1202 ----
              newa->multidims = false;
              newa->location = -1;

!             cmp = (Node *) make_scalar_array_op(pstate,
!                                                 a->name,
!                                                 useOr,
!                                                 lexpr,
!                                                 (Node *) newa,
!                                                 a->location);
!
!             /* cmp certainly yields boolean, no need to check it */
!
!             cmpexprs = lappend(cmpexprs, cmp);

              /* Consider only the Vars (if any) in the loop below */
              rexprs = rvars;
*************** transformAExprIn(ParseState *pstate, A_E
*** 1198,1204 ****
      }

      /*
!      * Must do it the hard way, ie, with a boolean expression tree.
       */
      foreach(l, rexprs)
      {
--- 1204,1210 ----
      }

      /*
!      * Any remaining righthand exprs need to be compared individually.
       */
      foreach(l, rexprs)
      {
*************** transformAExprIn(ParseState *pstate, A_E
*** 1226,1239 ****
          }

          cmp = coerce_to_boolean(pstate, cmp, "IN");
!         if (result == NULL)
!             result = cmp;
!         else
!             result = (Node *) makeBoolExpr(useOr ? OR_EXPR : AND_EXPR,
!                                            list_make2(result, cmp),
!                                            a->location);
      }

      return result;
  }

--- 1232,1253 ----
          }

          cmp = coerce_to_boolean(pstate, cmp, "IN");
!
!         cmpexprs = lappend(cmpexprs, cmp);
      }

+     /*
+      * If we have more than one comparison expression, AND or OR them together
+      */
+     if (cmpexprs == NIL)
+         result = NULL;            /* can this happen? is it right if so? */
+     else if (list_length(cmpexprs) == 1)
+         result = (Node *) linitial(cmpexprs);
+     else
+         result = (Node *) makeBoolExpr(useOr ? OR_EXPR : AND_EXPR,
+                                        cmpexprs,
+                                        a->location);
+
      return result;
  }