Re: Processing long AND/OR lists

On Sat, May 25, 2013 at 9:56 AM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:

> 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().
>

As suspected, the problem was that a JOIN's USING clause processing cooks
up its own join conditions, and those were the ones that couldn't cope with
the changed order of output.

Fixing that order of arguments of the BoolExpr also fixed all the JOIN
related diffs. Now `make check` passes except for this benign diff.

| 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));

That's expected, since for cases like these, the patch converts what used
to be a tree of 2-argument BoolExprs into a single BoolExpr with many
arguments.

--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.