Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
On Wed, Feb 26, 2014 at 10:21:03PM -0500, Tom Lane wrote: Noah Misch n...@leadboat.com writes: On Tue, Feb 25, 2014 at 01:15:09PM -0500, Tom Lane wrote: Really if we wanted to fix this issue we'd need to hack up transformAExprAnd/transformAExprOr so that they recognized nested ANDs/ORs and flattened them on the spot. This might not be a bad idea, but it's starting to look like more than a quick hack patch. Reminds me of this work: http://www.postgresql.org/message-id/flat/CABwTF4XJKN1smMjHv_O-QzTpokqSjHBouMWVw-E8kyb2bC=_...@mail.gmail.com http://www.postgresql.org/message-id/flat/cafj8prdd9qtyoy0cbpoodr-hfj1xambuxwoxazg0kyvtvau...@mail.gmail.com Oh, I'd forgotten about that thread. I never particularly liked the patch as presented: like Robert, I thought it far too complicated. My inclination would just be to tweak the parser enough so that a simple list of ANDs or ORs (ie, a left-deep raw parse tree) gets flattened. The most likely bet for making that happen in an uncomplicated way would be to alter gram.y's processing: if we had the productions for AND/OR notice whether their left inputs were already AND/OR clauses, they could extend the argument lists instead of building nested clauses. The reason the proposed patch is so complicated is it's trying to avoid recursing while handling a fundamentally recursive data structure, and that's just the hard way to do it. We do need to look at whether there are any implications for ruleutils and other places, though. Where are we on this? Is it being kept for 9.5? -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
Bruce Momjian br...@momjian.us writes: On Wed, Feb 26, 2014 at 10:21:03PM -0500, Tom Lane wrote: Oh, I'd forgotten about that thread. I never particularly liked the patch as presented: like Robert, I thought it far too complicated. My inclination would just be to tweak the parser enough so that a simple list of ANDs or ORs (ie, a left-deep raw parse tree) gets flattened. The most likely bet for making that happen in an uncomplicated way would be to alter gram.y's processing: if we had the productions for AND/OR notice whether their left inputs were already AND/OR clauses, they could extend the argument lists instead of building nested clauses. The reason the proposed patch is so complicated is it's trying to avoid recursing while handling a fundamentally recursive data structure, and that's just the hard way to do it. We do need to look at whether there are any implications for ruleutils and other places, though. Where are we on this? Is it being kept for 9.5? I think we rejected the patch-as-presented, and no one's bothered to create a new one, which suggests that the problem isn't all that important ... I suspect the gram.y change I suggest above would be about a ten-line patch. What makes it less than completely trivial is the need to chase down all the downstream implications, such as whether ruleutils would need any work, and whether anything else is expecting parser output to contain only binary clauses. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
On Sat, Apr 19, 2014 at 05:50:17PM -0400, Tom Lane wrote: Bruce Momjian br...@momjian.us writes: On Wed, Feb 26, 2014 at 10:21:03PM -0500, Tom Lane wrote: Oh, I'd forgotten about that thread. I never particularly liked the patch as presented: like Robert, I thought it far too complicated. My inclination would just be to tweak the parser enough so that a simple list of ANDs or ORs (ie, a left-deep raw parse tree) gets flattened. The most likely bet for making that happen in an uncomplicated way would be to alter gram.y's processing: if we had the productions for AND/OR notice whether their left inputs were already AND/OR clauses, they could extend the argument lists instead of building nested clauses. The reason the proposed patch is so complicated is it's trying to avoid recursing while handling a fundamentally recursive data structure, and that's just the hard way to do it. We do need to look at whether there are any implications for ruleutils and other places, though. Where are we on this? Is it being kept for 9.5? I think we rejected the patch-as-presented, and no one's bothered to create a new one, which suggests that the problem isn't all that important ... I suspect the gram.y change I suggest above would be about a ten-line patch. What makes it less than completely trivial is the need to chase down all the downstream implications, such as whether ruleutils would need any work, and whether anything else is expecting parser output to contain only binary clauses. OK, thanks for the feedback. -- Bruce Momjian br...@momjian.ushttp://momjian.us EnterpriseDB http://enterprisedb.com + Everyone has their own god. + -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
On Tue, Feb 25, 2014 at 01:15:09PM -0500, Tom Lane wrote: Over in http://www.postgresql.org/message-id/bay176-w382a9de827ebc8e602b7bbc5...@phx.gbl there's a complaint about getting stack depth limit exceeded from a query of the form select count(*) from gui_die_summary where (x_coord, y_coord) in ((25,5),(41,13),(25,7),(28,3),(25,8),(34,7),(26,6),(21,10), ...); when there's a few thousand pairs in the IN list. The reason for this is that transformAExprIn() generates a tree of nested OR expressions, and then recursion in assign_collations_walker() runs out of stack space. Really if we wanted to fix this issue we'd need to hack up transformAExprAnd/transformAExprOr so that they recognized nested ANDs/ORs and flattened them on the spot. This might not be a bad idea, but it's starting to look like more than a quick hack patch. Reminds me of this work: http://www.postgresql.org/message-id/flat/CABwTF4XJKN1smMjHv_O-QzTpokqSjHBouMWVw-E8kyb2bC=_...@mail.gmail.com http://www.postgresql.org/message-id/flat/cafj8prdd9qtyoy0cbpoodr-hfj1xambuxwoxazg0kyvtvau...@mail.gmail.com Does this seem worth pursuing, or shall we leave it alone? +1 for fixing. Extrapolating from your figure of 20s and 20 GiB for a million coordinate pairs, we'd have tolerable performance at 2 pairs instead of just failing as we do today. That's a nice win all by itself. -- Noah Misch EnterpriseDB http://www.enterprisedb.com -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
Noah Misch n...@leadboat.com writes: On Tue, Feb 25, 2014 at 01:15:09PM -0500, Tom Lane wrote: Really if we wanted to fix this issue we'd need to hack up transformAExprAnd/transformAExprOr so that they recognized nested ANDs/ORs and flattened them on the spot. This might not be a bad idea, but it's starting to look like more than a quick hack patch. Reminds me of this work: http://www.postgresql.org/message-id/flat/CABwTF4XJKN1smMjHv_O-QzTpokqSjHBouMWVw-E8kyb2bC=_...@mail.gmail.com http://www.postgresql.org/message-id/flat/cafj8prdd9qtyoy0cbpoodr-hfj1xambuxwoxazg0kyvtvau...@mail.gmail.com Oh, I'd forgotten about that thread. I never particularly liked the patch as presented: like Robert, I thought it far too complicated. My inclination would just be to tweak the parser enough so that a simple list of ANDs or ORs (ie, a left-deep raw parse tree) gets flattened. The most likely bet for making that happen in an uncomplicated way would be to alter gram.y's processing: if we had the productions for AND/OR notice whether their left inputs were already AND/OR clauses, they could extend the argument lists instead of building nested clauses. The reason the proposed patch is so complicated is it's trying to avoid recursing while handling a fundamentally recursive data structure, and that's just the hard way to do it. We do need to look at whether there are any implications for ruleutils and other places, though. regards, tom lane -- Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org) To make changes to your subscription: http://www.postgresql.org/mailpref/pgsql-hackers
Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
On Thu, Feb 27, 2014 at 8:51 AM, Tom Lane t...@sss.pgh.pa.us wrote:
Noah Misch n...@leadboat.com writes:
On Tue, Feb 25, 2014 at 01:15:09PM -0500, Tom Lane wrote:
Really if we wanted to fix
this issue we'd need to hack up transformAExprAnd/transformAExprOr so
that
they recognized nested ANDs/ORs and flattened them on the spot. This
might not be a bad idea, but it's starting to look like more than a
quick
hack patch.
Reminds me of this work:
http://www.postgresql.org/message-id/flat/CABwTF4XJKN1smMjHv_O-QzTpokqSjHBouMWVw-E8kyb2bC=_...@mail.gmail.com
http://www.postgresql.org/message-id/flat/cafj8prdd9qtyoy0cbpoodr-hfj1xambuxwoxazg0kyvtvau...@mail.gmail.com
Oh, I'd forgotten about that thread. I never particularly liked the patch
as presented: like Robert, I thought it far too complicated. My
inclination would just be to tweak the parser enough so that a simple list
of ANDs or ORs (ie, a left-deep raw parse tree) gets flattened.
The most likely bet for making that happen in an uncomplicated way would
be to alter gram.y's processing: if we had the productions for AND/OR
notice whether their left inputs were already AND/OR clauses, they could
extend the argument lists instead of building nested clauses. The reason
the proposed patch is so complicated is it's trying to avoid recursing
while handling a fundamentally recursive data structure, and that's just
the hard way to do it.
We do need to look at whether there are any implications for ruleutils
and other places, though.
ruleutils should be fine. See code below in ruleutils.c
6615 case AND_EXPR:
6616 if (!PRETTY_PAREN(context))
6617 appendStringInfoChar(buf, '(');
6618 get_rule_expr_paren(first_arg, context,
6619 false, node);
6620 while (arg)
6621 {
6622 appendStringInfoString(buf, AND );
6623 get_rule_expr_paren((Node *) lfirst(arg),
context,
6624 false, node);
6625 arg = lnext(arg);
6626 }
6627 if (!PRETTY_PAREN(context))
6628 appendStringInfoChar(buf, ')');
6629 break;
Similar code exists for OR_EXPR.
Within the planner, I have seen the quals are always implicitly ANDed
lists, where all ANDs are put into a single list. May be same with OR.
As a side note, the code blocks for AND_EXPR and OR_EXPR are almost same
except words AND and OR. So there is some chance to get rid of some
code duplication here.
regards, tom lane
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
--
Best Wishes,
Ashutosh Bapat
EnterpriseDB Corporation
The Postgres Database Company
