Processing long AND/OR lists

When Postgres encounters a long list of AND/OR chains, it errors out at
check_stack_depth() after a limit of few thousand. At around 10,000
elements, the recursion at assign_expr_collations() causes the error. But
at a little higher element count, around 15,000, the recursion check errors
out a little earlier, in the stack around transformAExprAnd(). The test
queries were generated using the attached test.sh script.

This is not a synthetic test. Recently I saw a report where Slony generated
a huge list of 'log_actionseq <> nnn and log_actionseq <> nnn and ...' for
a SYNC event, and that SYNC event could not complete due to this error.
Granted that Slony can be fixed by making it generate the condition as
'log_actionseq not in (nnn, nnn)' which is processed non-recursively, but
IMHO Postgres should be capable of handling this trivial construct, however
long it may be (of course, limited by memory).

To that end, I wrote the attached patch, and although I seem to be playing
by the rules, `make check` fails. Some diffs look benign, but others not so
much.

AIUI, a BoolExpr is perfectly capable of holding multiple expressions as a
list. And since SQL standard does not say anything about short-circuit
evaluation, the evaluation order of these expressions should not affect the
results. So clearly turning a tree of booleans expressions into a list is
not so subtle a change. I suspect that this patch is messing up the join
conditions.

I see two ways to fix it:
1) Fix the order of expressions in BoolExpr such that the order of
evaluation remains unchanged compared to before the patch.
I expect this to take care of the benign diffs. But I doubt this will
address the other diffs.

2) Construct a tree same as done before the patch, but do it
non-recursively.
This is I guess the right thing to do, but then we'll have to make
similar tree-traversal changes in other places, for eg. in BoolExpr walking
in expression_tree_walker() or maybe just the stack below
assign_expr_collations().

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.