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 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 http://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 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 Wed, Feb 26, 2014 at 10:21:03PM -0500, Tom Lane wrote: > Noah Misch 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 http://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 Thu, Feb 27, 2014 at 8:51 AM, Tom Lane wrote:
> Noah Misch 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
Re: [HACKERS] Avoiding deeply nested AND/OR trees in the parser
Noah Misch 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 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
