review: Non-recursive processing of AND/OR lists

diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 327557e..61a1cd9 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -40,8 +40,7 @@ bool		Transform_null_equals = false;
 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
 static Node *transformParamRef(ParseState *pstate, ParamRef *pref);
 static Node *transformAExprOp(ParseState *pstate, A_Expr *a);
-static Node *transformAExprAnd(ParseState *pstate, A_Expr *a);
-static Node *transformAExprOr(ParseState *pstate, A_Expr *a);
+static Node *transformAExprAndOr(ParseState *pstate, A_Expr *a);
 static Node *transformAExprNot(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a);
@@ -223,10 +222,10 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 						result = transformAExprOp(pstate, a);
 						break;
 					case AEXPR_AND:
-						result = transformAExprAnd(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_OR:
-						result = transformAExprOr(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_NOT:
 						result = transformAExprNot(pstate, a);
@@ -920,27 +916,72 @@ transformAExprOp(ParseState *pstate, A_Expr *a)
-static Node *
-transformAExprAnd(ParseState *pstate, A_Expr *a)
-{
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
-
-	lexpr = coerce_to_boolean(pstate, lexpr, "AND");
-	rexpr = coerce_to_boolean(pstate, rexpr, "AND");
-
-	return (Node *) makeBoolExpr(AND_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
-}
-
-static Node *
-transformAExprOr(ParseState *pstate, A_Expr *a)
-{
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
-
-	lexpr = coerce_to_boolean(pstate, lexpr, "OR");
-	rexpr = coerce_to_boolean(pstate, rexpr, "OR");
-
-	return (Node *) makeBoolExpr(OR_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
-}
+/*
+ * Transform the AND/OR trees non-recursively.
+ *
+ * The parser turns a list of consecutive AND expressions into a left-deep tree.
+ *
+ * a AND b AND c
+ *
+ *      AND
+ *     /  \
+ *   AND   c
+ *  /  \
+ * a    b
+ *
+ * For very long lists, it gets deep enough that processing it recursively causes
+ * check_stack_depth() to raise error and abort the query. Hence, it is necessary
+ * that we process these trees iteratively.
+ */
+static Node *
+transformAExprAndOr(ParseState *pstate, A_Expr *a)
+{
+	List		   *exprs = NIL;
+	List		   *pending = NIL;
+	Node		   *expr;
+	A_Expr		   *root = a;
+	A_Expr_Kind		root_kind = a->kind;
+	char		   *root_char = (root_kind == AEXPR_AND ? "AND" : "OR");
+	BoolExprType	root_bool_expr = (root_kind == AEXPR_AND ? AND_EXPR : OR_EXPR);
+
+	pending = lappend(pending, a);
+
+	while (list_length(pending) > 0)
+	{
+		Node *tmp;
+		a = (A_Expr*) linitial(pending);
+
+		pending = list_delete_first(pending);
+
+		/*
+		 * Follow the left links to walk the left-deep tree, and process all the
+		 * right branches.xi
+		 *
+		 * If a right branch is also the same kind of tree as the root, then
+		 * append it to the 'pending' list. The pending list is also processed
+		 * in this function call iteratively rather than recursing.  This allows
+		 * us to process even bushy trees, not just left-deep trees.
+		 */
+		tmp = (Node*)a;
+		do {
+			a = (A_Expr*) tmp;
+
+			if (IsA(a->rexpr, A_Expr) && ((A_Expr*)a->rexpr)->kind == root_kind)
+			{
+				pending = lappend(pending, a->rexpr);
+			}
+			else
+			{
+				expr = transformExprRecurse(pstate, a->rexpr);
+				expr = coerce_to_boolean(pstate, expr, root_char);
+				exprs = lcons(expr, exprs);
+			}
+
+			tmp = a->lexpr;
+		} while (IsA(tmp, A_Expr) && ((A_Expr*)tmp)->kind == root_kind);
+
+		/* Now process the last left expression */
+		expr = transformExprRecurse(pstate, a->lexpr);
+		expr = coerce_to_boolean(pstate, expr, root_char);
+		exprs = lcons(expr, exprs);
+	}
+
+	return (Node *) makeBoolExpr(root_bool_expr, exprs, root->location);
+}
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 57ae842..42f0ece 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -2092,7 +2092,7 @@ SELECT viewname, definition FROM pg_views WHERE schemaname <> 'information_schem
                                  |     int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail                                                                                                                                                     +
                                  |    FROM shoe rsh,                                                                                                                                                                                              +
                                  |     shoelace rsl                                                                                                                                                                                               +
-                                 |   WHERE (((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
+                                 |   WHERE ((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
  shoelace                        |  SELECT s.sl_name,                                                                                                                                                                                             +
                                  |     s.sl_avail,                                                                                                                                                                                                +
                                  |     s.sl_color,                                                                                                                                                                                                +

diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 327557e..61a1cd9 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -40,8 +40,7 @@ bool		Transform_null_equals = false;
 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
 static Node *transformParamRef(ParseState *pstate, ParamRef *pref);
 static Node *transformAExprOp(ParseState *pstate, A_Expr *a);
-static Node *transformAExprAnd(ParseState *pstate, A_Expr *a);
-static Node *transformAExprOr(ParseState *pstate, A_Expr *a);
+static Node *transformAExprAndOr(ParseState *pstate, A_Expr *a);
 static Node *transformAExprNot(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a);
@@ -223,10 +222,10 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 						result = transformAExprOp(pstate, a);
 						break;
 					case AEXPR_AND:
-						result = transformAExprAnd(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_OR:
-						result = transformAExprOr(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_NOT:
 						result = transformAExprNot(pstate, a);
@@ -920,27 +916,72 @@ transformAExprOp(ParseState *pstate, A_Expr *a)
-static Node *
-transformAExprAnd(ParseState *pstate, A_Expr *a)
-{
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
-
-	lexpr = coerce_to_boolean(pstate, lexpr, "AND");
-	rexpr = coerce_to_boolean(pstate, rexpr, "AND");
-
-	return (Node *) makeBoolExpr(AND_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
-}
-
-static Node *
-transformAExprOr(ParseState *pstate, A_Expr *a)
-{
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
-
-	lexpr = coerce_to_boolean(pstate, lexpr, "OR");
-	rexpr = coerce_to_boolean(pstate, rexpr, "OR");
-
-	return (Node *) makeBoolExpr(OR_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
-}
+/*
+ * Transform the AND/OR trees non-recursively.
+ *
+ * The parser turns a list of consecutive AND expressions into a left-deep tree.
+ *
+ * a AND b AND c
+ *
+ *      AND
+ *     /  \
+ *   AND   c
+ *  /  \
+ * a    b
+ *
+ * For very long lists, it gets deep enough that processing it recursively causes
+ * check_stack_depth() to raise error and abort the query. Hence, it is necessary
+ * that we process these trees iteratively.
+ */
+static Node *
+transformAExprAndOr(ParseState *pstate, A_Expr *a)
+{
+	List		   *exprs = NIL;
+	List		   *pending = NIL;
+	Node		   *expr;
+	A_Expr		   *root = a;
+	A_Expr_Kind		root_expr_kind = a->kind;
+	char		   *root_expr_name = (root_expr_kind == AEXPR_AND ? "AND" : "OR");
+	BoolExprType	root_bool_expr_type = (root_expr_kind == AEXPR_AND ? AND_EXPR : OR_EXPR);
+
+	pending = lappend(pending, a);
+
+	while (list_length(pending) > 0)
+	{
+		Node *tmp;
+		a = (A_Expr*) linitial(pending);
+
+		pending = list_delete_first(pending);
+
+		/*
+		 * Follow the left links to walk the left-deep tree, and process all the
+		 * right branches.
+		 *
+		 * If a right branch is also the same kind of tree as the root, then
+		 * append it to the 'pending' list. The pending list is also processed
+		 * in this function call iteratively rather than recursively.  This
+		 * allows us to process even bushy trees, not just left-deep trees.
+		 */
+		tmp = (Node*)a;
+		do {
+			a = (A_Expr*) tmp;
+
+			if (IsA(a->rexpr, A_Expr) && ((A_Expr*)a->rexpr)->kind == root_expr_kind)
+			{
+				pending = lappend(pending, a->rexpr);
+			}
+			else
+			{
+				expr = transformExprRecurse(pstate, a->rexpr);
+				expr = coerce_to_boolean(pstate, expr, root_expr_name);
+				exprs = lcons(expr, exprs);
+			}
+
+			tmp = a->lexpr;
+		} while (IsA(tmp, A_Expr) && ((A_Expr*)tmp)->kind == root_expr_kind);
+
+		/* Now process the last left expression */
+		expr = transformExprRecurse(pstate, a->lexpr);
+		expr = coerce_to_boolean(pstate, expr, root_expr_name);
+		exprs = lcons(expr, exprs);
+	}
+
+	return (Node *) makeBoolExpr(root_bool_expr_type, exprs, root->location);
+}
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 57ae842..42f0ece 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -2092,7 +2092,7 @@ SELECT viewname, definition FROM pg_views WHERE schemaname <> 'information_schem
                                  |     int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail                                                                                                                                                     +
                                  |    FROM shoe rsh,                                                                                                                                                                                              +
                                  |     shoelace rsl                                                                                                                                                                                               +
-                                 |   WHERE (((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
+                                 |   WHERE ((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
  shoelace                        |  SELECT s.sl_name,                                                                                                                                                                                             +
                                  |     s.sl_avail,                                                                                                                                                                                                +
                                  |     s.sl_color,                                                                                                                                                                                                +

diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 06f6512..5cbf577 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -40,8 +40,7 @@ bool		Transform_null_equals = false;
 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
 static Node *transformParamRef(ParseState *pstate, ParamRef *pref);
 static Node *transformAExprOp(ParseState *pstate, A_Expr *a);
-static Node *transformAExprAnd(ParseState *pstate, A_Expr *a);
-static Node *transformAExprOr(ParseState *pstate, A_Expr *a);
+static Node *transformAExprAndOr(ParseState *pstate, A_Expr *a);
 static Node *transformAExprNot(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a);
@@ -223,10 +222,10 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 						result = transformAExprOp(pstate, a);
 						break;
 					case AEXPR_AND:
-						result = transformAExprAnd(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_OR:
-						result = transformAExprOr(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_NOT:
 						result = transformAExprNot(pstate, a);
@@ -917,32 +916,85 @@ transformAExprOp(ParseState *pstate, A_Expr *a)
 	return result;
 }
 
+/*
+ * Transform the AND/OR trees non-recursively.
+ *
+ * The parser turns a list of consecutive AND expressions into a left-deep tree.
+ *
+ * a AND b AND c
+ *
+ *      AND
+ *     /  \
+ *   AND   c
+ *  /  \
+ * a    b
+ *
+ * For very long lists, it gets deep enough that processing it recursively causes
+ * check_stack_depth() to raise error and abort the query. Hence, it is necessary
+ * that we process these trees iteratively.
+ */
 static Node *
-transformAExprAnd(ParseState *pstate, A_Expr *a)
+transformAExprAndOr(ParseState *pstate, A_Expr *a)
 {
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
+	List		   *exprs = NIL;
+	List		   *pending = NIL;
+	Node		   *expr;
+	A_Expr		   *root = a;
+	A_Expr_Kind		root_expr_kind = a->kind;
+	char		   *root_expr_name = (root_expr_kind == AEXPR_AND ? "AND" : "OR");
+	BoolExprType	root_bool_expr_type = (root_expr_kind == AEXPR_AND ? AND_EXPR : OR_EXPR);
 
-	lexpr = coerce_to_boolean(pstate, lexpr, "AND");
-	rexpr = coerce_to_boolean(pstate, rexpr, "AND");
+	do {
+		Node *tmp;
 
-	return (Node *) makeBoolExpr(AND_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
-}
+		/*
+		 * Follow the left links to walk the left-deep tree, and process all the
+		 * right branches.
+		 *
+		 * If a right branch is also the same kind of tree as the root, then
+		 * append it to the 'pending' list. The pending list is also processed
+		 * in this function call iteratively rather than recursively.  This
+		 * allows us to process even bushy trees, not just left-deep trees.
+		 */
+		tmp = (Node*)a;
+		do {
+			a = (A_Expr*) tmp;
 
-static Node *
-transformAExprOr(ParseState *pstate, A_Expr *a)
-{
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
+			if (IsA(a->rexpr, A_Expr) && ((A_Expr*)a->rexpr)->kind == root_expr_kind)
+			{
+				pending = lappend(pending, a->rexpr);
+			}
+			else
+			{
+				expr = transformExprRecurse(pstate, a->rexpr);
+				expr = coerce_to_boolean(pstate, expr, root_expr_name);
+				exprs = lcons(expr, exprs);
+			}
 
-	lexpr = coerce_to_boolean(pstate, lexpr, "OR");
-	rexpr = coerce_to_boolean(pstate, rexpr, "OR");
+			tmp = a->lexpr;
+		} while (IsA(tmp, A_Expr) && ((A_Expr*)tmp)->kind == root_expr_kind);
 
-	return (Node *) makeBoolExpr(OR_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
+		/* Now process the last left expression */
+		expr = transformExprRecurse(pstate, a->lexpr);
+		expr = coerce_to_boolean(pstate, expr, root_expr_name);
+		exprs = lcons(expr, exprs);
+
+        /*
+		 * Now that we're done processing the edge of the left-deep tree, pop
+		 * the first element from the front of the pending list and process any
+		 * interesting nodes we found earlier.
+		 */
+		if (list_length(pending) > 0)
+		{
+			a = (A_Expr*) linitial(pending);
+			pending = list_delete_first(pending);
+		}
+		else
+			a = NULL;
+
+	} while(a != NULL);
+
+	return (Node *) makeBoolExpr(root_bool_expr_type, exprs, root->location);
 }
 
 static Node *
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 8f24c51..41bb098 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -2095,7 +2095,7 @@ SELECT viewname, definition FROM pg_views WHERE schemaname <> 'information_schem
                                  |     int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail                                                                                                                                                     +
                                  |    FROM shoe rsh,                                                                                                                                                                                              +
                                  |     shoelace rsl                                                                                                                                                                                               +
-                                 |   WHERE (((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
+                                 |   WHERE ((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
  shoelace                        |  SELECT s.sl_name,                                                                                                                                                                                             +
                                  |     s.sl_avail,                                                                                                                                                                                                +
                                  |     s.sl_color,                                                                                                                                                                                                +

diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 81c9338..eb35d70 100644
--- a/src/backend/parser/parse_expr.c
+++ b/src/backend/parser/parse_expr.c
@@ -41,8 +41,7 @@ bool		Transform_null_equals = false;
 static Node *transformExprRecurse(ParseState *pstate, Node *expr);
 static Node *transformParamRef(ParseState *pstate, ParamRef *pref);
 static Node *transformAExprOp(ParseState *pstate, A_Expr *a);
-static Node *transformAExprAnd(ParseState *pstate, A_Expr *a);
-static Node *transformAExprOr(ParseState *pstate, A_Expr *a);
+static Node *transformAExprAndOr(ParseState *pstate, A_Expr *a);
 static Node *transformAExprNot(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a);
 static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a);
@@ -224,10 +223,10 @@ transformExprRecurse(ParseState *pstate, Node *expr)
 						result = transformAExprOp(pstate, a);
 						break;
 					case AEXPR_AND:
-						result = transformAExprAnd(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_OR:
-						result = transformAExprOr(pstate, a);
+						result = transformAExprAndOr(pstate, a);
 						break;
 					case AEXPR_NOT:
 						result = transformAExprNot(pstate, a);
@@ -918,32 +917,102 @@ transformAExprOp(ParseState *pstate, A_Expr *a)
 	return result;
 }
 
+/*
+ * Transform the AND/OR trees non-recursively.
+ *
+ * The parser turns a list of consecutive AND expressions into a left-deep tree.
+ *
+ * a AND b AND c
+ *
+ *      AND
+ *     /  \
+ *   AND   c
+ *  /  \
+ * a    b
+ *
+ * For very long lists, it gets deep enough that processing it recursively causes
+ * check_stack_depth() to raise error and abort the query. Hence, it is necessary
+ * that we process these trees iteratively.
+ */
 static Node *
-transformAExprAnd(ParseState *pstate, A_Expr *a)
+transformAExprAndOr(ParseState *pstate, A_Expr *a)
 {
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
+#define PROCESS_BUSHY_TREES 1
+	List		   *exprs = NIL;
+#if PROCESS_BUSHY_TREES
+	List		   *pending = NIL;
+#endif
+	Node		   *expr;
+	A_Expr		   *root = a;
+	A_Expr_Kind		root_kind = a->kind;
+	char		   *root_name = (root_kind == AEXPR_AND ? "AND" : "OR");
+	BoolExprType	root_expr_type = (root_kind == AEXPR_AND ? AND_EXPR : OR_EXPR);
+
+	do {
+		Node *tmp;
 
-	lexpr = coerce_to_boolean(pstate, lexpr, "AND");
-	rexpr = coerce_to_boolean(pstate, rexpr, "AND");
+		/*
+		 * Follow the left links to walk the left-deep tree, and process all the
+		 * right branches. We traverse down the left branch as long as we find
+		 * an unbroken chain of node types that match the root node. Then we
+		 * stop and process the rest of the tree in normal recursive manner.
+#if PROCESS_BUSHY_TREES
+		 *
+		 * If a right branch is also the same kind of tree as the root, then
+		 * append it to the 'pending' list. The pending list is also processed
+		 * in this function call iteratively rather than recursively.  This
+		 * allows us to process bushy and even right-deep trees, not just
+		 * left-deep trees.
+#endif
+		 */
+		tmp = (Node*)a;
+		do {
+			a = (A_Expr*) tmp;
 
-	return (Node *) makeBoolExpr(AND_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
-}
+#if PROCESS_BUSHY_TREES
+			if (IsA(a->rexpr, A_Expr) && ((A_Expr*)a->rexpr)->kind == root_kind)
+			{
+				pending = lappend(pending, a->rexpr);
+			}
+			else
+#endif
+			{
+				expr = transformExprRecurse(pstate, a->rexpr);
+				expr = coerce_to_boolean(pstate, expr, root_name);
+				/*
+				 * Use lcons instead of lappend to retain the order of
+				 * processing of right branches close to the way it was in the
+				 * case of recursive processing.
+				 */
+				exprs = lcons(expr, exprs);
+			}
 
-static Node *
-transformAExprOr(ParseState *pstate, A_Expr *a)
-{
-	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
-	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
+			tmp = a->lexpr;
+		} while (IsA(tmp, A_Expr) && ((A_Expr*)tmp)->kind == root_kind);
 
-	lexpr = coerce_to_boolean(pstate, lexpr, "OR");
-	rexpr = coerce_to_boolean(pstate, rexpr, "OR");
+		/* Now process the node in left branch that broke our chain. */
+		expr = transformExprRecurse(pstate, a->lexpr);
+		expr = coerce_to_boolean(pstate, expr, root_name);
+		exprs = lcons(expr, exprs);
 
-	return (Node *) makeBoolExpr(OR_EXPR,
-								 list_make2(lexpr, rexpr),
-								 a->location);
+#if PROCESS_BUSHY_TREES
+		/*
+		 * Now that we're done processing the edge of the left-deep tree, pop
+		 * the first element from the front of the pending list and process any
+		 * interesting nodes we found earlier.
+		 */
+		if (list_length(pending) > 0)
+		{
+			a = (A_Expr*) linitial(pending);
+			pending = list_delete_first(pending);
+		}
+		else
+#endif
+			a = NULL;
+
+	} while(a != NULL);
+
+	return (Node *) makeBoolExpr(root_expr_type, exprs, root->location);
 }
 
 static Node *
@@ -2428,10 +2497,6 @@ make_row_comparison_op(ParseState *pstate, List *opname,
 	/*
 	 * For = and <> cases, we just combine the pairwise operators with AND or
 	 * OR respectively.
-	 *
-	 * Note: this is presently the only place where the parser generates
-	 * BoolExpr with more than two arguments.  Should be OK since the rest of
-	 * the system thinks BoolExpr is N-argument anyway.
 	 */
 	if (rctype == ROWCOMPARE_EQ)
 		return (Node *) makeBoolExpr(AND_EXPR, opexprs, location);
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 9cce60b..5b5c22b 100644
--- a/src/include/nodes/primnodes.h
+++ b/src/include/nodes/primnodes.h
@@ -458,12 +458,9 @@ typedef struct ScalarArrayOpExpr
  * BoolExpr - expression node for the basic Boolean operators AND, OR, NOT
  *
  * Notice the arguments are given as a List.  For NOT, of course the list
- * must always have exactly one element.  For AND and OR, the executor can
- * handle any number of arguments.	The parser generally treats AND and OR
- * as binary and so it typically only produces two-element lists, but the
- * optimizer will flatten trees of AND and OR nodes to produce longer lists
- * when possible.  There are also a few special cases where more arguments
- * can appear before optimization.
+ * must always have exactly one element.  For AND and OR, there are two or
+ * more arguments in the list. The optimizer and the executor are capable
+ * of processing these flat lists.
  */
 typedef enum BoolExprType
 {
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 6c51d0d..c3188a7 100644
--- a/src/test/regress/expected/rules.out
+++ b/src/test/regress/expected/rules.out
@@ -2117,7 +2117,7 @@ shoe_ready| SELECT rsh.shoename,
     int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail
    FROM shoe rsh,
     shoelace rsl
-  WHERE (((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
+  WHERE ((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
 shoelace| SELECT s.sl_name,
     s.sl_avail,
     s.sl_color,

diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c
index 1e48a7f..95f5dd2 100644
*** a/src/backend/nodes/nodeFuncs.c
--- b/src/backend/nodes/nodeFuncs.c
*************** raw_expression_tree_walker(Node *node,
*** 3047,3052 ****
--- 3047,3060 ----
  				/* operator name is deemed uninteresting */
  			}
  			break;
+ 		case T_BoolExpr:
+ 			{
+ 				BoolExpr   *expr = (BoolExpr *) node;
+ 
+ 				if (walker(expr->args, context))
+ 					return true;
+ 			}
+ 			break;
  		case T_ColumnRef:
  			/* we assume the fields contain nothing interesting */
  			break;
diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c
index 10e8139..cd4bce1 100644
*** a/src/backend/nodes/outfuncs.c
--- b/src/backend/nodes/outfuncs.c
*************** _outAExpr(StringInfo str, const A_Expr *
*** 2437,2451 ****
  			appendStringInfoChar(str, ' ');
  			WRITE_NODE_FIELD(name);
  			break;
- 		case AEXPR_AND:
- 			appendStringInfoString(str, " AND");
- 			break;
- 		case AEXPR_OR:
- 			appendStringInfoString(str, " OR");
- 			break;
- 		case AEXPR_NOT:
- 			appendStringInfoString(str, " NOT");
- 			break;
  		case AEXPR_OP_ANY:
  			appendStringInfoChar(str, ' ');
  			WRITE_NODE_FIELD(name);
--- 2437,2442 ----
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index 7b9895d..dd04b1a 100644
*** a/src/backend/parser/gram.y
--- b/src/backend/parser/gram.y
*************** static void insertSelectOptions(SelectSt
*** 151,156 ****
--- 151,159 ----
  static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg);
  static Node *doNegate(Node *n, int location);
  static void doNegateFloat(Value *v);
+ static Node *makeAndExpr(Node *lexpr, Node *rexpr, int location);
+ static Node *makeOrExpr(Node *lexpr, Node *rexpr, int location);
+ static Node *makeNotExpr(Node *expr, int location);
  static Node *makeAArrayExpr(List *elements, int location);
  static Node *makeXmlExpr(XmlExprOp op, char *name, List *named_args,
  						 List *args, int location);
*************** a_expr:		c_expr									{ $$ = $1; }
*** 10849,10859 ****
  				{ $$ = (Node *) makeA_Expr(AEXPR_OP, $2, $1, NULL, @2); }
  
  			| a_expr AND a_expr
! 				{ $$ = (Node *) makeA_Expr(AEXPR_AND, NIL, $1, $3, @2); }
  			| a_expr OR a_expr
! 				{ $$ = (Node *) makeA_Expr(AEXPR_OR, NIL, $1, $3, @2); }
  			| NOT a_expr
! 				{ $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, $2, @1); }
  
  			| a_expr LIKE a_expr
  				{ $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "~~", $1, $3, @2); }
--- 10852,10862 ----
  				{ $$ = (Node *) makeA_Expr(AEXPR_OP, $2, $1, NULL, @2); }
  
  			| a_expr AND a_expr
! 				{ $$ = makeAndExpr($1, $3, @2); }
  			| a_expr OR a_expr
! 				{ $$ = makeOrExpr($1, $3, @2); }
  			| NOT a_expr
! 				{ $$ = makeNotExpr($2, @1); }
  
  			| a_expr LIKE a_expr
  				{ $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, "~~", $1, $3, @2); }
*************** a_expr:		c_expr									{ $$ = $1; }
*** 11022,11032 ****
  				}
  			| a_expr IS NOT DISTINCT FROM a_expr		%prec IS
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL,
! 									(Node *) makeSimpleA_Expr(AEXPR_DISTINCT,
! 															  "=", $1, $6, @2),
! 											 @2);
! 
  				}
  			| a_expr IS OF '(' type_list ')'			%prec IS
  				{
--- 11025,11033 ----
  				}
  			| a_expr IS NOT DISTINCT FROM a_expr		%prec IS
  				{
! 					$$ = makeNotExpr((Node *) makeSimpleA_Expr(AEXPR_DISTINCT,
! 															   "=", $1, $6, @2),
! 									 @2);
  				}
  			| a_expr IS OF '(' type_list ')'			%prec IS
  				{
*************** a_expr:		c_expr									{ $$ = $1; }
*** 11044,11086 ****
  			 */
  			| a_expr BETWEEN opt_asymmetric b_expr AND b_expr		%prec BETWEEN
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_AND, NIL,
  						(Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2),
  						(Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2),
! 											 @2);
  				}
  			| a_expr NOT BETWEEN opt_asymmetric b_expr AND b_expr	%prec BETWEEN
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_OR, NIL,
  						(Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2),
  						(Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2),
! 											 @2);
  				}
  			| a_expr BETWEEN SYMMETRIC b_expr AND b_expr			%prec BETWEEN
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_OR, NIL,
! 						(Node *) makeA_Expr(AEXPR_AND, NIL,
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2),
! 											@2),
! 						(Node *) makeA_Expr(AEXPR_AND, NIL,
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $6, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $4, @2),
! 											@2),
! 											 @2);
  				}
  			| a_expr NOT BETWEEN SYMMETRIC b_expr AND b_expr		%prec BETWEEN
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_AND, NIL,
! 						(Node *) makeA_Expr(AEXPR_OR, NIL,
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2),
! 											@2),
! 						(Node *) makeA_Expr(AEXPR_OR, NIL,
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $7, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $5, @2),
! 											@2),
! 											 @2);
  				}
  			| a_expr IN_P in_expr
  				{
--- 11045,11087 ----
  			 */
  			| a_expr BETWEEN opt_asymmetric b_expr AND b_expr		%prec BETWEEN
  				{
! 					$$ = makeAndExpr(
  						(Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2),
  						(Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2),
! 									 @2);
  				}
  			| a_expr NOT BETWEEN opt_asymmetric b_expr AND b_expr	%prec BETWEEN
  				{
! 					$$ = makeOrExpr(
  						(Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2),
  						(Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2),
! 									@2);
  				}
  			| a_expr BETWEEN SYMMETRIC b_expr AND b_expr			%prec BETWEEN
  				{
! 					$$ = makeOrExpr(
! 						  makeAndExpr(
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2),
! 									  @2),
! 						  makeAndExpr(
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $6, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $4, @2),
! 									  @2),
! 									@2);
  				}
  			| a_expr NOT BETWEEN SYMMETRIC b_expr AND b_expr		%prec BETWEEN
  				{
! 					$$ = makeAndExpr(
! 						   makeOrExpr(
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2),
! 									  @2),
! 						   makeOrExpr(
  							(Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $7, @2),
  							(Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $5, @2),
! 									  @2),
! 									 @2);
  				}
  			| a_expr IN_P in_expr
  				{
*************** a_expr:		c_expr									{ $$ = $1; }
*** 11114,11120 ****
  						n->operName = list_make1(makeString("="));
  						n->location = @3;
  						/* Stick a NOT on top */
! 						$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, (Node *) n, @2);
  					}
  					else
  					{
--- 11115,11121 ----
  						n->operName = list_make1(makeString("="));
  						n->location = @3;
  						/* Stick a NOT on top */
! 						$$ = makeNotExpr((Node *) n, @2);
  					}
  					else
  					{
*************** a_expr:		c_expr									{ $$ = $1; }
*** 11162,11171 ****
  				}
  			| a_expr IS NOT DOCUMENT_P				%prec IS
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL,
! 											 makeXmlExpr(IS_DOCUMENT, NULL, NIL,
! 														 list_make1($1), @2),
! 											 @2);
  				}
  		;
  
--- 11163,11171 ----
  				}
  			| a_expr IS NOT DOCUMENT_P				%prec IS
  				{
! 					$$ = makeNotExpr(makeXmlExpr(IS_DOCUMENT, NULL, NIL,
! 												 list_make1($1), @2),
! 									 @2);
  				}
  		;
  
*************** b_expr:		c_expr
*** 11216,11223 ****
  				}
  			| b_expr IS NOT DISTINCT FROM b_expr	%prec IS
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL,
! 						NULL, (Node *) makeSimpleA_Expr(AEXPR_DISTINCT, "=", $1, $6, @2), @2);
  				}
  			| b_expr IS OF '(' type_list ')'		%prec IS
  				{
--- 11216,11224 ----
  				}
  			| b_expr IS NOT DISTINCT FROM b_expr	%prec IS
  				{
! 					$$ = makeNotExpr((Node *) makeSimpleA_Expr(AEXPR_DISTINCT,
! 															   "=", $1, $6, @2),
! 									 @2);
  				}
  			| b_expr IS OF '(' type_list ')'		%prec IS
  				{
*************** b_expr:		c_expr
*** 11234,11243 ****
  				}
  			| b_expr IS NOT DOCUMENT_P				%prec IS
  				{
! 					$$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL,
! 											 makeXmlExpr(IS_DOCUMENT, NULL, NIL,
! 														 list_make1($1), @2),
! 											 @2);
  				}
  		;
  
--- 11235,11243 ----
  				}
  			| b_expr IS NOT DOCUMENT_P				%prec IS
  				{
! 					$$ = makeNotExpr(makeXmlExpr(IS_DOCUMENT, NULL, NIL,
! 												 list_make1($1), @2),
! 									 @2);
  				}
  		;
  
*************** doNegateFloat(Value *v)
*** 13693,13698 ****
--- 13693,13738 ----
  }
  
  static Node *
+ makeAndExpr(Node *lexpr, Node *rexpr, int location)
+ {
+ 	/* Flatten "a AND b AND c ..." to a single BoolExpr on sight */
+ 	if (IsA(lexpr, BoolExpr))
+ 	{
+ 		BoolExpr *blexpr = (BoolExpr *) lexpr;
+ 
+ 		if (blexpr->boolop == AND_EXPR)
+ 		{
+ 			blexpr->args = lappend(blexpr->args, rexpr);
+ 			return (Node *) blexpr;
+ 		}
+ 	}
+ 	return (Node *) makeBoolExpr(AND_EXPR, list_make2(lexpr, rexpr), location);
+ }
+ 
+ static Node *
+ makeOrExpr(Node *lexpr, Node *rexpr, int location)
+ {
+ 	/* Flatten "a OR b OR c ..." to a single BoolExpr on sight */
+ 	if (IsA(lexpr, BoolExpr))
+ 	{
+ 		BoolExpr *blexpr = (BoolExpr *) lexpr;
+ 
+ 		if (blexpr->boolop == OR_EXPR)
+ 		{
+ 			blexpr->args = lappend(blexpr->args, rexpr);
+ 			return (Node *) blexpr;
+ 		}
+ 	}
+ 	return (Node *) makeBoolExpr(OR_EXPR, list_make2(lexpr, rexpr), location);
+ }
+ 
+ static Node *
+ makeNotExpr(Node *expr, int location)
+ {
+ 	return (Node *) makeBoolExpr(NOT_EXPR, list_make1(expr), location);
+ }
+ 
+ static Node *
  makeAArrayExpr(List *elements, int location)
  {
  	A_ArrayExpr *n = makeNode(A_ArrayExpr);
diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c
index aa704bb..a71f611 100644
*** a/src/backend/parser/parse_clause.c
--- b/src/backend/parser/parse_clause.c
*************** transformJoinUsingClause(ParseState *pst
*** 332,338 ****
  						 RangeTblEntry *leftRTE, RangeTblEntry *rightRTE,
  						 List *leftVars, List *rightVars)
  {
! 	Node	   *result = NULL;
  	ListCell   *lvars,
  			   *rvars;
  
--- 332,339 ----
  						 RangeTblEntry *leftRTE, RangeTblEntry *rightRTE,
  						 List *leftVars, List *rightVars)
  {
! 	Node	   *result;
! 	List	   *andargs = NIL;
  	ListCell   *lvars,
  			   *rvars;
  
*************** transformJoinUsingClause(ParseState *pst
*** 358,375 ****
  							 copyObject(lvar), copyObject(rvar),
  							 -1);
  
! 		/* And combine into an AND clause, if multiple join columns */
! 		if (result == NULL)
! 			result = (Node *) e;
! 		else
! 		{
! 			A_Expr	   *a;
! 
! 			a = makeA_Expr(AEXPR_AND, NIL, result, (Node *) e, -1);
! 			result = (Node *) a;
! 		}
  	}
  
  	/*
  	 * Since the references are already Vars, and are certainly from the input
  	 * relations, we don't have to go through the same pushups that
--- 359,374 ----
  							 copyObject(lvar), copyObject(rvar),
  							 -1);
  
! 		/* Prepare to combine into an AND clause, if multiple join columns */
! 		andargs = lappend(andargs, e);
  	}
  
+ 	/* Only need an AND if there's more than one join column */
+ 	if (list_length(andargs) == 1)
+ 		result = (Node *) linitial(andargs);
+ 	else
+ 		result = (Node *) makeBoolExpr(AND_EXPR, andargs, -1);
+ 
  	/*
  	 * Since the references are already Vars, and are certainly from the input
  	 * relations, we don't have to go through the same pushups that
diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c
index 81c9338..cb76133 100644
*** a/src/backend/parser/parse_expr.c
--- b/src/backend/parser/parse_expr.c
*************** bool		Transform_null_equals = false;
*** 41,55 ****
  static Node *transformExprRecurse(ParseState *pstate, Node *expr);
  static Node *transformParamRef(ParseState *pstate, ParamRef *pref);
  static Node *transformAExprOp(ParseState *pstate, A_Expr *a);
- static Node *transformAExprAnd(ParseState *pstate, A_Expr *a);
- static Node *transformAExprOr(ParseState *pstate, A_Expr *a);
- static Node *transformAExprNot(ParseState *pstate, A_Expr *a);
  static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a);
  static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a);
  static Node *transformAExprDistinct(ParseState *pstate, A_Expr *a);
  static Node *transformAExprNullIf(ParseState *pstate, A_Expr *a);
  static Node *transformAExprOf(ParseState *pstate, A_Expr *a);
  static Node *transformAExprIn(ParseState *pstate, A_Expr *a);
  static Node *transformFuncCall(ParseState *pstate, FuncCall *fn);
  static Node *transformCaseExpr(ParseState *pstate, CaseExpr *c);
  static Node *transformSubLink(ParseState *pstate, SubLink *sublink);
--- 41,53 ----
  static Node *transformExprRecurse(ParseState *pstate, Node *expr);
  static Node *transformParamRef(ParseState *pstate, ParamRef *pref);
  static Node *transformAExprOp(ParseState *pstate, A_Expr *a);
  static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a);
  static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a);
  static Node *transformAExprDistinct(ParseState *pstate, A_Expr *a);
  static Node *transformAExprNullIf(ParseState *pstate, A_Expr *a);
  static Node *transformAExprOf(ParseState *pstate, A_Expr *a);
  static Node *transformAExprIn(ParseState *pstate, A_Expr *a);
+ static Node *transformBoolExpr(ParseState *pstate, BoolExpr *a);
  static Node *transformFuncCall(ParseState *pstate, FuncCall *fn);
  static Node *transformCaseExpr(ParseState *pstate, CaseExpr *c);
  static Node *transformSubLink(ParseState *pstate, SubLink *sublink);
*************** transformExprRecurse(ParseState *pstate,
*** 223,237 ****
  					case AEXPR_OP:
  						result = transformAExprOp(pstate, a);
  						break;
- 					case AEXPR_AND:
- 						result = transformAExprAnd(pstate, a);
- 						break;
- 					case AEXPR_OR:
- 						result = transformAExprOr(pstate, a);
- 						break;
- 					case AEXPR_NOT:
- 						result = transformAExprNot(pstate, a);
- 						break;
  					case AEXPR_OP_ANY:
  						result = transformAExprOpAny(pstate, a);
  						break;
--- 221,226 ----
*************** transformExprRecurse(ParseState *pstate,
*** 258,263 ****
--- 247,256 ----
  				break;
  			}
  
+ 		case T_BoolExpr:
+ 			result = transformBoolExpr(pstate, (BoolExpr *) expr);
+ 			break;
+ 
  		case T_FuncCall:
  			result = transformFuncCall(pstate, (FuncCall *) expr);
  			break;
*************** transformExprRecurse(ParseState *pstate,
*** 337,343 ****
  		case T_DistinctExpr:
  		case T_NullIfExpr:
  		case T_ScalarArrayOpExpr:
- 		case T_BoolExpr:
  		case T_FieldSelect:
  		case T_FieldStore:
  		case T_RelabelType:
--- 330,335 ----
*************** transformAExprOp(ParseState *pstate, A_E
*** 919,964 ****
  }
  
  static Node *
- transformAExprAnd(ParseState *pstate, A_Expr *a)
- {
- 	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
- 	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
- 
- 	lexpr = coerce_to_boolean(pstate, lexpr, "AND");
- 	rexpr = coerce_to_boolean(pstate, rexpr, "AND");
- 
- 	return (Node *) makeBoolExpr(AND_EXPR,
- 								 list_make2(lexpr, rexpr),
- 								 a->location);
- }
- 
- static Node *
- transformAExprOr(ParseState *pstate, A_Expr *a)
- {
- 	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
- 	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
- 
- 	lexpr = coerce_to_boolean(pstate, lexpr, "OR");
- 	rexpr = coerce_to_boolean(pstate, rexpr, "OR");
- 
- 	return (Node *) makeBoolExpr(OR_EXPR,
- 								 list_make2(lexpr, rexpr),
- 								 a->location);
- }
- 
- static Node *
- transformAExprNot(ParseState *pstate, A_Expr *a)
- {
- 	Node	   *rexpr = transformExprRecurse(pstate, a->rexpr);
- 
- 	rexpr = coerce_to_boolean(pstate, rexpr, "NOT");
- 
- 	return (Node *) makeBoolExpr(NOT_EXPR,
- 								 list_make1(rexpr),
- 								 a->location);
- }
- 
- static Node *
  transformAExprOpAny(ParseState *pstate, A_Expr *a)
  {
  	Node	   *lexpr = transformExprRecurse(pstate, a->lexpr);
--- 911,916 ----
*************** transformAExprIn(ParseState *pstate, A_E
*** 1238,1243 ****
--- 1190,1231 ----
  }
  
  static Node *
+ transformBoolExpr(ParseState *pstate, BoolExpr *a)
+ {
+ 	List	   *args = NIL;
+ 	const char *opname;
+ 	ListCell   *lc;
+ 
+ 	switch (a->boolop)
+ 	{
+ 		case AND_EXPR:
+ 			opname = "AND";
+ 			break;
+ 		case OR_EXPR:
+ 			opname = "OR";
+ 			break;
+ 		case NOT_EXPR:
+ 			opname = "NOT";
+ 			break;
+ 		default:
+ 			elog(ERROR, "unrecognized boolop: %d", (int) a->boolop);
+ 			opname = NULL;		/* keep compiler quiet */
+ 			break;
+ 	}
+ 
+ 	foreach(lc, a->args)
+ 	{
+ 		Node	   *arg = (Node *) lfirst(lc);
+ 
+ 		arg = transformExprRecurse(pstate, arg);
+ 		arg = coerce_to_boolean(pstate, arg, opname);
+ 		args = lappend(args, arg);
+ 	}
+ 
+ 	return (Node *) makeBoolExpr(a->boolop, args, a->location);
+ }
+ 
+ static Node *
  transformFuncCall(ParseState *pstate, FuncCall *fn)
  {
  	List	   *targs;
*************** make_row_comparison_op(ParseState *pstat
*** 2428,2437 ****
  	/*
  	 * For = and <> cases, we just combine the pairwise operators with AND or
  	 * OR respectively.
- 	 *
- 	 * Note: this is presently the only place where the parser generates
- 	 * BoolExpr with more than two arguments.  Should be OK since the rest of
- 	 * the system thinks BoolExpr is N-argument anyway.
  	 */
  	if (rctype == ROWCOMPARE_EQ)
  		return (Node *) makeBoolExpr(AND_EXPR, opexprs, location);
--- 2416,2421 ----
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 18d4991..59916eb 100644
*** a/src/include/nodes/parsenodes.h
--- b/src/include/nodes/parsenodes.h
*************** typedef struct ParamRef
*** 225,233 ****
  typedef enum A_Expr_Kind
  {
  	AEXPR_OP,					/* normal operator */
- 	AEXPR_AND,					/* booleans - name field is unused */
- 	AEXPR_OR,
- 	AEXPR_NOT,
  	AEXPR_OP_ANY,				/* scalar op ANY (array) */
  	AEXPR_OP_ALL,				/* scalar op ALL (array) */
  	AEXPR_DISTINCT,				/* IS DISTINCT FROM - name must be "=" */
--- 225,230 ----
diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h
index 9cce60b..ed73109 100644
*** a/src/include/nodes/primnodes.h
--- b/src/include/nodes/primnodes.h
*************** typedef struct ScalarArrayOpExpr
*** 458,469 ****
   * BoolExpr - expression node for the basic Boolean operators AND, OR, NOT
   *
   * Notice the arguments are given as a List.  For NOT, of course the list
!  * must always have exactly one element.  For AND and OR, the executor can
!  * handle any number of arguments.	The parser generally treats AND and OR
!  * as binary and so it typically only produces two-element lists, but the
!  * optimizer will flatten trees of AND and OR nodes to produce longer lists
!  * when possible.  There are also a few special cases where more arguments
!  * can appear before optimization.
   */
  typedef enum BoolExprType
  {
--- 458,465 ----
   * BoolExpr - expression node for the basic Boolean operators AND, OR, NOT
   *
   * Notice the arguments are given as a List.  For NOT, of course the list
!  * must always have exactly one element.  For AND and OR, there can be two
!  * or more arguments.
   */
  typedef enum BoolExprType
  {
diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out
index 6c51d0d..c3188a7 100644
*** a/src/test/regress/expected/rules.out
--- b/src/test/regress/expected/rules.out
*************** shoe_ready| SELECT rsh.shoename,
*** 2117,2123 ****
      int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail
     FROM shoe rsh,
      shoelace rsl
!   WHERE (((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
  shoelace| SELECT s.sl_name,
      s.sl_avail,
      s.sl_color,
--- 2117,2123 ----
      int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail
     FROM shoe rsh,
      shoelace rsl
!   WHERE ((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm));
  shoelace| SELECT s.sl_name,
      s.sl_avail,
      s.sl_color,