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.

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.

On 05/25/2013 09:56 AM, Gurjeet Singh 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.

***15,000***? I'd say that someone has an application design issue.

Fixing the stack overflow is a good thing, but that query is never going
to return ...

--
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

Josh Berkus <josh(at)agliodbs(dot)com> writes:
> ***15,000***? I'd say that someone has an application design issue.
> Fixing the stack overflow is a good thing, but that query is never going
> to return ...

Yeah, the parser's stack consumption seems like only the tip of the
iceberg here.

I find it hard to visualize a use-case for so many AND'ed conditions
anyway. I could believe a lot of OR'd conditions, but very likely it
would be a list that could and should be converted to an IN condition.

regards, tom lane

This situation falls from a problem that we noticed a mighty long time ago
in Slony, where the set of XIDs outstanding gets very large, and, attendant
to that, the set of "action id" values by which tuples are being filtered,
gets correspondingly large.

It happens when there is a long pause in application of replication data,
and is commonly the consequence of setting up replication on a very large
data table that takes a long time for the initial data copy.

At the time, Neil Conway observed this query breakage with a query that was
roughly 640K in size, from whence fell jokes to the effect, "who would ever
need a query larger than 640K?"

The resolution that I introduced at the time was to write a little parser
that would recognize sequences of adjacent values and merge them into
"BETWEEN A and B" clauses, which would bring the query size back to a
reasonable size.

In Slony 2.1, the issue re-emerged because the ordering of the "action id"
values was lost; the query had previously been implicitly forcing them into
order; we had to add an "ORDER BY" clause, to make the "compressor" work
again.
http://git.postgresql.org/gitweb/?p=slony1-engine.git;a=blobdiff;f=src/slon/remote_worker.c;h=b1f48043f8e25b4a74a392b0dbceeae8f3e18c27;hp=7fbf67c16f97cb7c3f209cf3be903ea52c4490a9;hb=c4ac435308a78a2db63bf267d401d842c169e87d;hpb=d4612aab78bac5a9836e3e2425c403878f7091c8

Joking about "640K" aside, it doesn't seem reasonable to expect a truly
enormous query as is generated by the broken forms of this logic to turn
out happily. I'd rather fix Slony (as done in the above patch).

On Sun, May 26, 2013 at 11:46 AM, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> Josh Berkus <josh(at)agliodbs(dot)com> writes:
> > ***15,000***? I'd say that someone has an application design issue.
> > Fixing the stack overflow is a good thing, but that query is never going
> > to return ...
>

Just for the record, it does finish in 5 sec on my laptop. But yes, point
taken.

>
> Yeah, the parser's stack consumption seems like only the tip of the
> iceberg here.
>

True. After getting past the parser, the bigger lists consume exponentially
longer times around process_equivalence(). And BTW, a backend stuck in that
stack does not respond to pg_cancel/terminate_backend()! Should there be a
CHECK_FOR_INTERRUPT() in process_equivalence(), perhaps invoked only every
N calls of that function.

>
> I find it hard to visualize a use-case for so many AND'ed conditions
> anyway. I could believe a lot of OR'd conditions, but very likely it
> would be a list that could and should be converted to an IN condition.
>

As noted earlier, this was seen in real-world, at a customer setup,
generated by Slony, a highly regarded community project. Also, the patch
addresses the stack limit for long OR clauses as well.

Anytime such conditions are generated programmatically, there's always a
possibility that the programmer underestimated the amount of data they are
generating the query for; just like it happened in Slony's case I quoted.

Slony has compress_actionseq() function to scan a list of numbers, and
generate a smallest possible WHERE clause. If it sees consecutive numbers
that form a range, it turns that range into a BETWEEN clause, and the
numbers that don't seem to be in a range are added to the where clause as
'AND col <> n1 AND col <> n2 ...'. It's quite likely that it generates such
long lists because it wrongly assumes that the input list is ordered, or at
least mostly ordered.

Agreed that that function can/should be fixed to do a better job of sorting
these numbers before scanning, and also using the NOT IN construct. But the
point remains that Postgres should be capable of handling this simple
construct efficiently.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

My last email was written before reading this. A few episodes of 24
occurred between writing and sending that email.

Added slony1-hackers, but didn't remove pgsql-hackers. Feel free to exclude
pgsql lists, as this branch of conversation seems to be more Slony related
than Postgres.

On Sun, May 26, 2013 at 10:59 PM, Christopher Browne <cbbrowne(at)gmail(dot)com>wrote:

>
> In Slony 2.1, the issue re-emerged because the ordering of the "action id"
> values was lost; the query had previously been implicitly forcing them into
> order; we had to add an "ORDER BY" clause, to make the "compressor" work
> again.
>
> http://git.postgresql.org/gitweb/?p=slony1-engine.git;a=blobdiff;f=src/slon/remote_worker.c;h=b1f48043f8e25b4a74a392b0dbceeae8f3e18c27;hp=7fbf67c16f97cb7c3f209cf3be903ea52c4490a9;hb=c4ac435308a78a2db63bf267d401d842c169e87d;hpb=d4612aab78bac5a9836e3e2425c403878f7091c8
>
>
Commit log says it was fixed between 2.1.2, but from the Slony logs at the
time, the version in use was 2.1.2. So

> Joking about "640K" aside, it doesn't seem reasonable to expect a truly
> enormous query as is generated by the broken forms of this logic to turn
> out happily. I'd rather fix Slony (as done in the above patch).
>

Yes, by all means, fix the application, but that doesn't preclude the
argument that the database should be a bit more smarter and efficient,
especially if it is easy to do.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On Mon, May 27, 2013 at 1:42 AM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:

>
>
>> Joking about "640K" aside, it doesn't seem reasonable to expect a truly
>> enormous query as is generated by the broken forms of this logic to turn
>> out happily. I'd rather fix Slony (as done in the above patch).
>>
>
> Yes, by all means, fix the application, but that doesn't preclude the
> argument that the database should be a bit more smarter and efficient,
> especially if it is easy to do.

Agreed, it seems like a fine idea to have the database support such
queries, as this eases coping with applications that might be more
difficult to get fixed. (I can't see too many users generating such
enormous queries by hand! :-))
--
When confronted by a difficult problem, solve it by reducing it to the
question, "How would the Lone Ranger handle this?"

On Mon, May 27, 2013 at 10:32 AM, Christopher Browne <cbbrowne(at)gmail(dot)com>wrote:

> On Mon, May 27, 2013 at 1:42 AM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:
>
>>
>>
>>> Joking about "640K" aside, it doesn't seem reasonable to expect a truly
>>> enormous query as is generated by the broken forms of this logic to turn
>>> out happily. I'd rather fix Slony (as done in the above patch).
>>>
>>
>> Yes, by all means, fix the application, but that doesn't preclude the
>> argument that the database should be a bit more smarter and efficient,
>> especially if it is easy to do.
>
>
> Agreed, it seems like a fine idea to have the database support such
> queries, as this eases coping with applications that might be more
> difficult to get fixed.
>

Seeing no more objections to it, I am going to add this patch to the
commitfest. Attached is updated patch against latest master; it's the same
as the previous version, except that that the patch now includes a fix for
the failing test case as well.

Best regards,
--
Gurjeet Singh

http://gurjeet.singh.im/

EnterpriseDB Inc.

On 6 June 2013 16:13, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:
> On Mon, May 27, 2013 at 10:32 AM, Christopher Browne <cbbrowne(at)gmail(dot)com>
> wrote:
>>
>> On Mon, May 27, 2013 at 1:42 AM, Gurjeet Singh <gurjeet(at)singh(dot)im> wrote:
>>>
>>>
>>>>
>>>> Joking about "640K" aside, it doesn't seem reasonable to expect a truly
>>>> enormous query as is generated by the broken forms of this logic to turn out
>>>> happily. I'd rather fix Slony (as done in the above patch).
>>>
>>>
>>> Yes, by all means, fix the application, but that doesn't preclude the
>>> argument that the database should be a bit more smarter and efficient,
>>> especially if it is easy to do.
>>
>>
>> Agreed, it seems like a fine idea to have the database support such
>> queries, as this eases coping with applications that might be more difficult
>> to get fixed.
>
>
> Seeing no more objections to it, I am going to add this patch to the
> commitfest. Attached is updated patch against latest master; it's the same
> as the previous version, except that that the patch now includes a fix for
> the failing test case as well.

I'm amazed such lisp-isms still exist, but hey.

This patch seems good, but it begs the question as to whether the
representation is the best one for later use.

When we consider expression cost we need to sort all peer expressions
at same level. Doing that on a left deep tree seems like hard work, so
shouldn't we be starting with a more bushy tree to make the sorting
happen more easily?

There's a few related transforms as well, such as I'd suggest we make
IN() lists and ORd conditions identical in both directions so that
expression proofs work more comprehensively.

--
Simon Riggs http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

On Mon, May 27, 2013 at 5:59 AM, Christopher Browne <cbbrowne(at)gmail(dot)com> wrote:
> This situation falls from a problem that we noticed a mighty long time ago
> in Slony, where the set of XIDs outstanding gets very large, and, attendant
> to that, the set of "action id" values by which tuples are being filtered,
> gets correspondingly large.
>
> It happens when there is a long pause in application of replication data,
> and is commonly the consequence of setting up replication on a very large
> data table that takes a long time for the initial data copy.
>
> At the time, Neil Conway observed this query breakage with a query that was
> roughly 640K in size, from whence fell jokes to the effect, "who would ever
> need a query larger than 640K?"
>
> The resolution that I introduced at the time was to write a little parser
> that would recognize sequences of adjacent values and merge them into
> "BETWEEN A and B" clauses, which would bring the query size back to a
> reasonable size.

PgQ uses simpler optimization to keep IN list size down -
it aggressively enlarges the main xid range and later processes
rows with txid_is_visible_in_snapshot():

https://github.com/markokr/skytools/blob/master/sql/pgq/functions/pgq.batch_event_sql.sql

IOW - it assumes the open-xid distribution is not uniformly random.

This additional optimization was ignored when pgq long-tx
approach was first imported to slony:

http://lists.slony.info/pipermail/slony1-general/2007-July/006238.html

I guess the reason was to have minimal patch.
You might want to play with that now.

--
marko