Avoid recursion when processing simple lists of AND'ed or OR'ed clauses.

Since most of the system thinks AND and OR are N-argument expressions
anyway, let's have the grammar generate a representation of that form when
dealing with input like "x AND y AND z AND ...", rather than generating
a deeply-nested binary tree that just has to be flattened later by the
planner.  This avoids stack overflow in parse analysis when dealing with
queries having more than a few thousand such clauses; and in any case it
removes some rather unsightly inconsistencies, since some parts of parse
analysis were generating N-argument ANDs/ORs already.

It's still possible to get a stack overflow with weirdly parenthesized
input, such as "x AND (y AND (z AND ( ... )))", but such cases are not
mainstream usage.  The maximum depth of parenthesization is already
limited by Bison's stack in such cases, anyway, so that the limit is
probably fairly platform-independent.

Patch originally by Gurjeet Singh, heavily revised by me

3 files changed, 18 insertions, 16 deletions

diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c
index 776fe426c3e..79521942a4f 100644
--- a/src/backend/optimizer/prep/prepjointree.c
+++ b/src/backend/optimizer/prep/prepjointree.c
@@ -133,9 +133,9 @@ static Node *find_jointree_node_for_rel(Node *jtnode, int relid);
  * transformations if any are found.
  *
  * This routine has to run before preprocess_expression(), so the quals
- * clauses are not yet reduced to implicit-AND format.  That means we need
- * to recursively search through explicit AND clauses, which are
- * probably only binary ANDs.  We stop as soon as we hit a non-AND item.
+ * clauses are not yet reduced to implicit-AND format, and are not guaranteed
+ * to be AND/OR-flat either.  That means we need to recursively search through
+ * explicit AND clauses.  We stop as soon as we hit a non-AND item.
  */
 void
 pull_up_sublinks(PlannerInfo *root)
diff --git a/src/backend/optimizer/prep/prepqual.c b/src/backend/optimizer/prep/prepqual.c
index 2a24938d843..244e5dbc150 100644
--- a/src/backend/optimizer/prep/prepqual.c
+++ b/src/backend/optimizer/prep/prepqual.c
@@ -4,13 +4,12 @@
  *	  Routines for preprocessing qualification expressions
  *
  *
- * The parser regards AND and OR as purely binary operators, so a qual like
- *		(A = 1) OR (A = 2) OR (A = 3) ...
- * will produce a nested parsetree
- *		(OR (A = 1) (OR (A = 2) (OR (A = 3) ...)))
- * In reality, the optimizer and executor regard AND and OR as N-argument
- * operators, so this tree can be flattened to
- *		(OR (A = 1) (A = 2) (A = 3) ...)
+ * While the parser will produce flattened (N-argument) AND/OR trees from
+ * simple sequences of AND'ed or OR'ed clauses, there might be an AND clause
+ * directly underneath another AND, or OR underneath OR, if the input was
+ * oddly parenthesized.  Also, rule expansion and subquery flattening could
+ * produce such parsetrees.  The planner wants to flatten all such cases
+ * to ensure consistent optimization behavior.
  *
  * Formerly, this module was responsible for doing the initial flattening,
  * but now we leave it to eval_const_expressions to do that since it has to
diff --git a/src/backend/optimizer/util/clauses.c b/src/backend/optimizer/util/clauses.c
index 97dacaaac19..19b5cf7b612 100644
--- a/src/backend/optimizer/util/clauses.c
+++ b/src/backend/optimizer/util/clauses.c
@@ -3447,12 +3447,15 @@ simplify_or_arguments(List *args,
 	List	   *unprocessed_args;
 
 	/*
-	 * Since the parser considers OR to be a binary operator, long OR lists
-	 * become deeply nested expressions.  We must flatten these into long
-	 * argument lists of a single OR operator.  To avoid blowing out the stack
-	 * with recursion of eval_const_expressions, we resort to some tenseness
-	 * here: we keep a list of not-yet-processed inputs, and handle flattening
-	 * of nested ORs by prepending to the to-do list instead of recursing.
+	 * We want to ensure that any OR immediately beneath another OR gets
+	 * flattened into a single OR-list, so as to simplify later reasoning.
+	 *
+	 * To avoid stack overflow from recursion of eval_const_expressions, we
+	 * resort to some tenseness here: we keep a list of not-yet-processed
+	 * inputs, and handle flattening of nested ORs by prepending to the to-do
+	 * list instead of recursing.  Now that the parser generates N-argument
+	 * ORs from simple lists, this complexity is probably less necessary than
+	 * it once was, but we might as well keep the logic.
 	 */
 	unprocessed_args = list_copy(args);
 	while (unprocessed_args)