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,
--