Re: [HACKERS] review: Non-recursive processing of AND/OR lists
Thanks! On Mon, Jun 16, 2014 at 3:58 PM, Tom Lane t...@sss.pgh.pa.us wrote: I wrote: Gurjeet Singh gurj...@singh.im writes: I tried to eliminate the 'pending' list, but I don't see a way around it. We need temporary storage somewhere to store the branches encountered on the right; in recursion case the call stack was serving that purpose. I still think we should fix this in the grammar, rather than introducing complicated logic to try to get rid of the recursion later. For example, as attached. I went looking for (and found) some additional obsoleted comments, and convinced myself that ruleutils.c is okay as-is, and pushed this. regards, tom lane -- Gurjeet Singh http://gurjeet.singh.im/ EDB 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] review: Non-recursive processing of AND/OR lists
I wrote: Gurjeet Singh gurj...@singh.im writes: I tried to eliminate the 'pending' list, but I don't see a way around it. We need temporary storage somewhere to store the branches encountered on the right; in recursion case the call stack was serving that purpose. I still think we should fix this in the grammar, rather than introducing complicated logic to try to get rid of the recursion later. For example, as attached. I went looking for (and found) some additional obsoleted comments, and convinced myself that ruleutils.c is okay as-is, and pushed this. 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] review: Non-recursive processing of AND/OR lists
On Thu, Jul 18, 2013 at 1:54 PM, Gurjeet Singh gurj...@singh.im wrote: On Thu, Jul 18, 2013 at 10:19 AM, Tom Lane t...@sss.pgh.pa.us wrote: Because simpler code is less likely to have bugs and is easier to maintain. I agree with that point, but one should also remember Polya's Inventor's Paradox: the more general problem may be easier to solve. That is, if done right, code that fully flattens an AND tree might actually be simpler than code that does just a subset of the transformation. The current patch fails to meet this expectation, The current patch does completely flatten any type of tree (left/right-deep or bushy) without recursing, and right-deep and bushy tree processing is what Robert is recommending to defer to recursive processing. Maybe I haven't considered a case where it doesn't flatten the tree; do you have an example in mind. but maybe you just haven't thought about it the right way. I tried to eliminate the 'pending' list, but I don't see a way around it. We need temporary storage somewhere to store the branches encountered on the right; in recursion case the call stack was serving that purpose. My concerns about this patch have little to do with that, though, and much more to do with the likelihood that it breaks some other piece of code that is expecting AND/OR to be strictly binary operators, which is what they've always been in parsetrees that haven't reached the planner. It doesn't appear to me that you've done any research on that point whatsoever No, I haven't, and I might not be able to research it for a few more weeks. There are about 30 files (including optimizer and executor) that match case-insensitive search for BoolExpr, and I scanned those for the usage of the member 'args'. All the instances where BoolExpr.args is being accessed, it's being treated as a null-terminated list. There's one exception that I could find, and it was in context of NOT expression: not_clause() in clauses.c. you have not even updated the comment for BoolExpr (in primnodes.h) that this patch falsifies. I will fix that. I think this line in that comment already covers the fact that in some special cases a BoolExpr may have more than 2 arguments. There are also a few special cases where more arguments can appear before optimization. I have updated the comment nevertheless, and removed another comment in parse_expr.c that claimed to be the only place where a BoolExpr with more than 2 args is generated. I have isolated the code for right-deep and bushy tree processing via the macro PROCESS_BUSHY_TREES. Also, I have shortened some variable names while retaining their meaning. Please find the updated patch attached (based on master). Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EDB www.EnterpriseDB.com http://www.enterprisedb.com diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c index 81c9338..eb35d70 100644 --- a/src/backend/parser/parse_expr.c +++ b/src/backend/parser/parse_expr.c @@ -41,8 +41,7 @@ bool Transform_null_equals = false; static Node *transformExprRecurse(ParseState *pstate, Node *expr); static Node *transformParamRef(ParseState *pstate, ParamRef *pref); static Node *transformAExprOp(ParseState *pstate, A_Expr *a); -static Node *transformAExprAnd(ParseState *pstate, A_Expr *a); -static Node *transformAExprOr(ParseState *pstate, A_Expr *a); +static Node *transformAExprAndOr(ParseState *pstate, A_Expr *a); static Node *transformAExprNot(ParseState *pstate, A_Expr *a); static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a); static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a); @@ -224,10 +223,10 @@ transformExprRecurse(ParseState *pstate, Node *expr) result = transformAExprOp(pstate, a); break; case AEXPR_AND: - result = transformAExprAnd(pstate, a); + result = transformAExprAndOr(pstate, a); break; case AEXPR_OR: - result = transformAExprOr(pstate, a); + result = transformAExprAndOr(pstate, a); break; case AEXPR_NOT: result = transformAExprNot(pstate, a); @@ -918,32 +917,102 @@ transformAExprOp(ParseState *pstate, A_Expr *a) return result; } +/* + * Transform the AND/OR trees non-recursively. + * + * The parser turns a list of consecutive AND expressions into a left-deep tree. + * + * a AND b AND c + * + * AND + * / \ + * AND c + * / \ + * ab + * + * For very long lists, it gets deep enough that processing it recursively causes + * check_stack_depth() to raise error and abort the query. Hence, it is necessary + * that we process these trees iteratively. + */ static Node * -transformAExprAnd(ParseState *pstate, A_Expr *a) +transformAExprAndOr(ParseState *pstate, A_Expr *a) { - Node *lexpr = transformExprRecurse(pstate, a-lexpr); - Node *rexpr = transformExprRecurse(pstate, a-rexpr); +#define PROCESS_BUSHY_TREES 1 + List *exprs = NIL; +#if PROCESS_BUSHY_TREES +
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
Gurjeet Singh gurj...@singh.im writes: I tried to eliminate the 'pending' list, but I don't see a way around it. We need temporary storage somewhere to store the branches encountered on the right; in recursion case the call stack was serving that purpose. I still think we should fix this in the grammar, rather than introducing complicated logic to try to get rid of the recursion later. For example, as attached. The existing A_Expr representation of raw AND/OR nodes isn't conducive to this, but it's not that hard to change it. The attached patch chooses to use BoolExpr as both the raw and transformed representation of AND/OR/NOT; we could alternatively invent some new raw-parsetree node type, but I don't see any advantage in that. I continue to think that more thought is needed about downstream processing. For instance, at least the comment at the head of prepqual.c is wrong now, and it's worth wondering whether the planner still needs to worry about AND/OR flattening at all. (It probably does, to deal with view-flattening cases for example; but it's worth considering whether anything could be saved if we stopped doing that.) regards, tom lane diff --git a/src/backend/nodes/nodeFuncs.c b/src/backend/nodes/nodeFuncs.c index 1e48a7f..95f5dd2 100644 *** a/src/backend/nodes/nodeFuncs.c --- b/src/backend/nodes/nodeFuncs.c *** raw_expression_tree_walker(Node *node, *** 3047,3052 --- 3047,3060 /* operator name is deemed uninteresting */ } break; + case T_BoolExpr: + { + BoolExpr *expr = (BoolExpr *) node; + + if (walker(expr-args, context)) + return true; + } + break; case T_ColumnRef: /* we assume the fields contain nothing interesting */ break; diff --git a/src/backend/nodes/outfuncs.c b/src/backend/nodes/outfuncs.c index 10e8139..cd4bce1 100644 *** a/src/backend/nodes/outfuncs.c --- b/src/backend/nodes/outfuncs.c *** _outAExpr(StringInfo str, const A_Expr * *** 2437,2451 appendStringInfoChar(str, ' '); WRITE_NODE_FIELD(name); break; - case AEXPR_AND: - appendStringInfoString(str, AND); - break; - case AEXPR_OR: - appendStringInfoString(str, OR); - break; - case AEXPR_NOT: - appendStringInfoString(str, NOT); - break; case AEXPR_OP_ANY: appendStringInfoChar(str, ' '); WRITE_NODE_FIELD(name); --- 2437,2442 diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y index 7b9895d..dd04b1a 100644 *** a/src/backend/parser/gram.y --- b/src/backend/parser/gram.y *** static void insertSelectOptions(SelectSt *** 151,156 --- 151,159 static Node *makeSetOp(SetOperation op, bool all, Node *larg, Node *rarg); static Node *doNegate(Node *n, int location); static void doNegateFloat(Value *v); + static Node *makeAndExpr(Node *lexpr, Node *rexpr, int location); + static Node *makeOrExpr(Node *lexpr, Node *rexpr, int location); + static Node *makeNotExpr(Node *expr, int location); static Node *makeAArrayExpr(List *elements, int location); static Node *makeXmlExpr(XmlExprOp op, char *name, List *named_args, List *args, int location); *** a_expr: c_expr { $$ = $1; } *** 10849,10859 { $$ = (Node *) makeA_Expr(AEXPR_OP, $2, $1, NULL, @2); } | a_expr AND a_expr ! { $$ = (Node *) makeA_Expr(AEXPR_AND, NIL, $1, $3, @2); } | a_expr OR a_expr ! { $$ = (Node *) makeA_Expr(AEXPR_OR, NIL, $1, $3, @2); } | NOT a_expr ! { $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, $2, @1); } | a_expr LIKE a_expr { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, ~~, $1, $3, @2); } --- 10852,10862 { $$ = (Node *) makeA_Expr(AEXPR_OP, $2, $1, NULL, @2); } | a_expr AND a_expr ! { $$ = makeAndExpr($1, $3, @2); } | a_expr OR a_expr ! { $$ = makeOrExpr($1, $3, @2); } | NOT a_expr ! { $$ = makeNotExpr($2, @1); } | a_expr LIKE a_expr { $$ = (Node *) makeSimpleA_Expr(AEXPR_OP, ~~, $1, $3, @2); } *** a_expr: c_expr { $$ = $1; } *** 11022,11032 } | a_expr IS NOT DISTINCT FROM a_expr %prec IS { ! $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, ! (Node *) makeSimpleA_Expr(AEXPR_DISTINCT, ! =, $1, $6, @2), ! @2); ! } | a_expr IS OF '(' type_list ')' %prec IS { --- 11025,11033 } | a_expr IS NOT DISTINCT FROM a_expr %prec IS { ! $$ = makeNotExpr((Node *) makeSimpleA_Expr(AEXPR_DISTINCT, ! =, $1, $6, @2), ! @2); } | a_expr IS OF '(' type_list ')' %prec IS { *** a_expr: c_expr { $$ = $1; } *** 11044,11086 */ | a_expr BETWEEN opt_asymmetric b_expr AND b_expr %prec BETWEEN { ! $$ = (Node *) makeA_Expr(AEXPR_AND, NIL, (Node *) makeSimpleA_Expr(AEXPR_OP, =, $1, $4, @2), (Node *)
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
On Wed, Jul 17, 2013 at 2:03 PM, Gurjeet Singh gurj...@singh.im wrote: In v6 of the patch, I have deferred the 'pending' list initialization to until we actually hit a candidate right-branch. So in the common case the pending list will never be populated, and if we find a bushy or right-deep tree (for some reason an ORM/tool may choose to build AND/OR lists that may end being right-deep when in Postgres), then the pending list will be used to process them iteratively. Does that alleviate your concern about 'pending' list management causing an overhead. Agreed that bushy/right-deep trees are a remote corner case, but we are addressing a remote corner case in the first place (insanely long AND lists) and why not handle another remote corner case right now if it doesn't cause an overhead for common case. Because simpler code is less likely to have bugs and is easier to maintain. It's worth noting that the change you're proposing is in fact user-visible, as demonstrated by the fact that you had to update the regression test output: - | 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)); Now, I think that change is actually an improvement, because here's what that WHERE clause looked like when it was entered: WHERE rsl.sl_color = rsh.slcolor AND rsl.sl_len_cm = rsh.slminlen_cm AND rsl.sl_len_cm = rsh.slmaxlen_cm; But flattening a = 1 AND (b = 1 AND c = 1 AND d = 1) AND e = 1 to a flat list doesn't have any of the same advantages. At the end of the day, this is a judgement call, and I'm giving you mine. If somebody else wants to weigh in, that's fine. I can't think of anything that would actually be outright broken under your proposed approach, but my personal feeling is that it's better to only add the amount of code that we know is needed to solve the problem actually observed in practice, and no more. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- 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] review: Non-recursive processing of AND/OR lists
Robert Haas robertmh...@gmail.com writes: On Wed, Jul 17, 2013 at 2:03 PM, Gurjeet Singh gurj...@singh.im wrote: Agreed that bushy/right-deep trees are a remote corner case, but we are addressing a remote corner case in the first place (insanely long AND lists) and why not handle another remote corner case right now if it doesn't cause an overhead for common case. Because simpler code is less likely to have bugs and is easier to maintain. I agree with that point, but one should also remember Polya's Inventor's Paradox: the more general problem may be easier to solve. That is, if done right, code that fully flattens an AND tree might actually be simpler than code that does just a subset of the transformation. The current patch fails to meet this expectation, but maybe you just haven't thought about it the right way. My concerns about this patch have little to do with that, though, and much more to do with the likelihood that it breaks some other piece of code that is expecting AND/OR to be strictly binary operators, which is what they've always been in parsetrees that haven't reached the planner. It doesn't appear to me that you've done any research on that point whatsoever --- you have not even updated the comment for BoolExpr (in primnodes.h) that this patch falsifies. It's worth noting that the change you're proposing is in fact user-visible, as demonstrated by the fact that you had to update the regression test output: The point to worry about here is whether rule dump and reload is still safe. In particular, the logic in ruleutils.c for deciding whether it's safe to omit parentheses has only really been thought about/tested for the binary AND/OR case. Although that code can dump N-way AND/OR because it's also used to print post-planner expression trees in EXPLAIN, that case has never been held to the standard of is the parser guaranteed to interpret this expression the same as before?. Perhaps it's fine, but has anyone looked at that issue? 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] review: Non-recursive processing of AND/OR lists
On Thu, Jul 18, 2013 at 10:19 AM, Tom Lane t...@sss.pgh.pa.us wrote: Because simpler code is less likely to have bugs and is easier to maintain. I agree with that point, but one should also remember Polya's Inventor's Paradox: the more general problem may be easier to solve. That is, if done right, code that fully flattens an AND tree might actually be simpler than code that does just a subset of the transformation. The current patch fails to meet this expectation, The current patch does completely flatten any type of tree (left/right-deep or bushy) without recursing, and right-deep and bushy tree processing is what Robert is recommending to defer to recursive processing. Maybe I haven't considered a case where it doesn't flatten the tree; do you have an example in mind. but maybe you just haven't thought about it the right way. My concerns about this patch have little to do with that, though, and much more to do with the likelihood that it breaks some other piece of code that is expecting AND/OR to be strictly binary operators, which is what they've always been in parsetrees that haven't reached the planner. It doesn't appear to me that you've done any research on that point whatsoever No, I haven't, and I might not be able to research it for a few more weeks. you have not even updated the comment for BoolExpr (in primnodes.h) that this patch falsifies. I will fix that. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
On Tue, Jul 16, 2013 at 4:04 PM, Pavel Stehule pavel.steh...@gmail.comwrote: I did a some performance tests of v5 and v6 version and there v5 is little bit faster than v6, and v6 has significantly higher stddev Thanks Pavel. The difference in average seems negligible, but stddev is interesting because v6 does less work than v5 in common cases and in the test that I had shared. The current commitfest (2013-06) is marked as 'In Progress', so is it okay to just mark the patch as 'Ready for Committer' or should I move it to the next commitfest (2013-09). What's the procedure of moving a patch to the next commitfest? Do I make a fresh submission there with a link to current submission, or is the move doable somehow in the application itself. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
On Wed, Jul 17, 2013 at 8:21 AM, Gurjeet Singh gurj...@singh.im wrote: What's the procedure of moving a patch to the next commitfest? Never mind, I see an email from Josh B. regarding this on my corporate account. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
On 07/17/2013 05:21 AM, Gurjeet Singh wrote: On Tue, Jul 16, 2013 at 4:04 PM, Pavel Stehule pavel.steh...@gmail.comwrote: I did a some performance tests of v5 and v6 version and there v5 is little bit faster than v6, and v6 has significantly higher stddev Thanks Pavel. The difference in average seems negligible, but stddev is interesting because v6 does less work than v5 in common cases and in the test that I had shared. The current commitfest (2013-06) is marked as 'In Progress', so is it okay to just mark the patch as 'Ready for Committer' or should I move it to the next commitfest (2013-09). If this is actually ready for committer, I'll mark it as such. -- Josh Berkus PostgreSQL Experts Inc. http://pgexperts.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] review: Non-recursive processing of AND/OR lists
On Mon, Jul 15, 2013 at 12:45 AM, Gurjeet Singh gurj...@singh.im wrote: Agreed that there's overhead in allocating list items, but is it more overhead than pushing functions on the call stack? Not sure, so I leave it to others who understand such things better than I do. If you think that a palloc can ever be cheaper that pushing a frame on the callstack, you're wrong. palloc is not some kind of an atomic primitive. It's implemented by the AllocSetAlloc function, and you're going to have to push that function on the call stack, too, in order to run it. My main point here is that if the user writes a = 1 and b = 1 and c = 1 and d = 1, they're not going to end up with a bushy tree. They're going to end up with a tree that's only deep in one direction (left, I guess) and that's the case we might want to consider optimizing. To obtain a bushy tree, they're going to have to write a = 1 and (b = 1 and c = 1) and d = 1, or something like that, and I don't see why we should stress out about that case. It will be rare in practice. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- 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] review: Non-recursive processing of AND/OR lists
On Wed, Jul 17, 2013 at 1:25 PM, Robert Haas robertmh...@gmail.com wrote: On Mon, Jul 15, 2013 at 12:45 AM, Gurjeet Singh gurj...@singh.im wrote: Agreed that there's overhead in allocating list items, but is it more overhead than pushing functions on the call stack? Not sure, so I leave it to others who understand such things better than I do. If you think that a palloc can ever be cheaper that pushing a frame on the callstack, you're wrong. palloc is not some kind of an atomic primitive. It's implemented by the AllocSetAlloc function, and you're going to have to push that function on the call stack, too, in order to run it. Agreed. I take my objection back. Even if AllocSetAlloc() reuses memory that was pfree'd earlier, it'll still be at least as expensive as recursing. My main point here is that if the user writes a = 1 and b = 1 and c = 1 and d = 1, they're not going to end up with a bushy tree. They're going to end up with a tree that's only deep in one direction (left, I guess) and that's the case we might want to consider optimizing. To obtain a bushy tree, they're going to have to write a = 1 and (b = 1 and c = 1) and d = 1, or something like that, and I don't see why we should stress out about that case. It will be rare in practice. In v6 of the patch, I have deferred the 'pending' list initialization to until we actually hit a candidate right-branch. So in the common case the pending list will never be populated, and if we find a bushy or right-deep tree (for some reason an ORM/tool may choose to build AND/OR lists that may end being right-deep when in Postgres), then the pending list will be used to process them iteratively. Does that alleviate your concern about 'pending' list management causing an overhead. Agreed that bushy/right-deep trees are a remote corner case, but we are addressing a remote corner case in the first place (insanely long AND lists) and why not handle another remote corner case right now if it doesn't cause an overhead for common case. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
Hello 2013/7/15 Gurjeet Singh gurj...@singh.im: On Sun, Jul 14, 2013 at 8:27 PM, Robert Haas robertmh...@gmail.com wrote: On Wed, Jul 10, 2013 at 9:02 PM, Josh Berkus j...@agliodbs.com wrote: I think it's a waste of code to try to handle bushy trees. A list is not a particularly efficient representation of the pending list; this will probably be slower than recusing in the common case. I'd suggest keeping the logic to handle left-deep trees, which I find rather elegant, but ditching the pending list. Somehow I find it hard to believe that recursing would be more efficient than processing the items right there. The recursion is not direct either; transformExprRecurse() is going to call this function again, but after a few more switch-case comparisons. Agreed that there's overhead in allocating list items, but is it more overhead than pushing functions on the call stack? Not sure, so I leave it to others who understand such things better than I do. If by common-case you mean a list of just one logical AND/OR operator, then I agree that creating and destroying a list may incur overhead that is relatively very expensive. To that end, I have altered the patch, attached, to not build a pending list until we encounter a node with root_expr_kind in a right branch. We're getting bushy-tree processing with very little extra code, but if you deem it not worthwhile or adding complexity, please feel free to rip it out. Is there going to be further discussion of this patch, or do I return it? Considering it's not been updated, nor my comments responded to, in almost two weeks, I think we return it at this point. Sorry, I didn't notice that this patch was put back in 'Waiting on Author' state. I did a some performance tests of v5 and v6 version and there v5 is little bit faster than v6, and v6 has significantly higher stddev but I am not sure, if my test is correct - I tested a speed of EXPLAIN statement - result was forwarded to /dev/null Result of this test is probably related to tested pattern of expressions - in this case expr or expr or expr or expr or expr ... 10 000 exprs (ms) v | avg | stddev ---+-+ 5 | 1839.14 | 13.68 6 | 1871.77 | 48.02 ==v5 profile== 209064 43.5354 postgres equal 207849 43.2824 postgres process_equivalence 37453 7.7992 postgres datumIsEqual 3178 0.6618 postgres SearchCatCache 2350 0.4894 postgres AllocSetAlloc ==v6 profile== 193251 45.3998 postgres process_equivalence 178183 41.8599 postgres equal 30430 7.1488 postgres datumIsEqual 2819 0.6623 postgres SearchCatCache 1951 0.4583 postgres AllocSetAlloc I found so 9.4 planner is about 1% slower (for test that sent by Gurjeet), that than 9.2 planner, but it is not related to this patch v6 is clean and all regression tests was passed Regards Pavel Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc. -- 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] review: Non-recursive processing of AND/OR lists
On Wed, Jul 10, 2013 at 9:02 PM, Josh Berkus j...@agliodbs.com wrote: I think it's a waste of code to try to handle bushy trees. A list is not a particularly efficient representation of the pending list; this will probably be slower than recusing in the common case. I'd suggest keeping the logic to handle left-deep trees, which I find rather elegant, but ditching the pending list. Is there going to be further discussion of this patch, or do I return it? Considering it's not been updated, nor my comments responded to, in almost two weeks, I think we return it at this point. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- 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] review: Non-recursive processing of AND/OR lists
On Sun, Jul 14, 2013 at 8:27 PM, Robert Haas robertmh...@gmail.com wrote: On Wed, Jul 10, 2013 at 9:02 PM, Josh Berkus j...@agliodbs.com wrote: I think it's a waste of code to try to handle bushy trees. A list is not a particularly efficient representation of the pending list; this will probably be slower than recusing in the common case. I'd suggest keeping the logic to handle left-deep trees, which I find rather elegant, but ditching the pending list. Somehow I find it hard to believe that recursing would be more efficient than processing the items right there. The recursion is not direct either; transformExprRecurse() is going to call this function again, but after a few more switch-case comparisons. Agreed that there's overhead in allocating list items, but is it more overhead than pushing functions on the call stack? Not sure, so I leave it to others who understand such things better than I do. If by common-case you mean a list of just one logical AND/OR operator, then I agree that creating and destroying a list may incur overhead that is relatively very expensive. To that end, I have altered the patch, attached, to not build a pending list until we encounter a node with root_expr_kind in a right branch. We're getting bushy-tree processing with very little extra code, but if you deem it not worthwhile or adding complexity, please feel free to rip it out. Is there going to be further discussion of this patch, or do I return it? Considering it's not been updated, nor my comments responded to, in almost two weeks, I think we return it at this point. Sorry, I didn't notice that this patch was put back in 'Waiting on Author' state. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc. non_recursive_and_or_transformation_v6.patch Description: Binary data -- 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] review: Non-recursive processing of AND/OR lists
I think it's a waste of code to try to handle bushy trees. A list is not a particularly efficient representation of the pending list; this will probably be slower than recusing in the common case. I'd suggest keeping the logic to handle left-deep trees, which I find rather elegant, but ditching the pending list. Is there going to be further discussion of this patch, or do I return it? -- Josh Berkus PostgreSQL Experts Inc. http://pgexperts.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] review: Non-recursive processing of AND/OR lists
On Sun, Jun 30, 2013 at 1:08 PM, Pavel Stehule pavel.steh...@gmail.com wrote: 2013/6/30 Gurjeet Singh gurj...@singh.im: On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule pavel.steh...@gmail.com wrote: 2013/6/30 Gurjeet Singh gurj...@singh.im: On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule pavel.steh...@gmail.com wrote: How about naming those 3 variables as follows: root_expr_kind root_expr_name root_bool_expr_type +1 Thanks. Attached is the patch with that change. I'll update the commitfest entry with a link to this email. ok I chechecked it - patched without warnings, all tests passed It is ready for commit I think it's a waste of code to try to handle bushy trees. A list is not a particularly efficient representation of the pending list; this will probably be slower than recusing in the common case. I'd suggest keeping the logic to handle left-deep trees, which I find rather elegant, but ditching the pending list. -- Robert Haas EnterpriseDB: http://www.enterprisedb.com The Enterprise PostgreSQL Company -- 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] review: Non-recursive processing of AND/OR lists
On Tue, Jun 18, 2013 at 3:01 PM, Pavel Stehule pavel.steh...@gmail.comwrote: related to https://commitfest.postgresql.org/action/patch_view?id=1130 http://www.postgresql.org/message-id/cabwtf4v9rsjibwe+87pk83mmm7acdrg7sz08rq-4qyme8jv...@mail.gmail.com * motivation: remove recursive procession of AND/OR list (hangs with 10062 and more subexpressions) * patch is short, clean and respect postgresql source code requirements * patch was applied cleanly without warnings * all regression tests was passed * I successfully evaluated expression with 10 subexpressions * there is no significant slowdown possible improvements a = (A_Expr*) list_nth(pending, 0); a = (A_Expr*) linitial(pending); I made that change, hesitantly. The comments above definition of linitial() macro describe the confusion that API causes. I wanted to avoid that confusion for new code, so I used the newer API which makes the intention quite clear. But looking at that code closely, list_nth() causes at least 2 function calls, and that's pretty heavy compared to the linitiali() macro. not well comment should be -- If the right branch is also an SAME condition, append it to the I moved that comment above the outer bock, so that the intention of the whole do-while code block is described in one place. I don't see any other issues, so after fixing comments this patch is ready for commit Thanks for the review Pavel. Attached is the updated patch, v4. It has the above edits, and a few code improvements, like not repeating the (root_kind == AEPR_AND ? .. : ..) ternary expression. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc. non_recursive_and_or_transformation_v4.patch Description: Binary data -- 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] review: Non-recursive processing of AND/OR lists
Hello just one small notices I dislike a name root_bool_expr, because, there is not a expression, but expression type. Can you use root_bool_expr_type instead? It is little bit longer, but more correct. Same not best name is root_char, maybe root_bool_op_name or root_expr_type and root_op_name ??? Have no other comments Regards Pavel 2013/6/30 Gurjeet Singh gurj...@singh.im: On Tue, Jun 18, 2013 at 3:01 PM, Pavel Stehule pavel.steh...@gmail.com wrote: related to https://commitfest.postgresql.org/action/patch_view?id=1130 http://www.postgresql.org/message-id/cabwtf4v9rsjibwe+87pk83mmm7acdrg7sz08rq-4qyme8jv...@mail.gmail.com * motivation: remove recursive procession of AND/OR list (hangs with 10062 and more subexpressions) * patch is short, clean and respect postgresql source code requirements * patch was applied cleanly without warnings * all regression tests was passed * I successfully evaluated expression with 10 subexpressions * there is no significant slowdown possible improvements a = (A_Expr*) list_nth(pending, 0); a = (A_Expr*) linitial(pending); I made that change, hesitantly. The comments above definition of linitial() macro describe the confusion that API causes. I wanted to avoid that confusion for new code, so I used the newer API which makes the intention quite clear. But looking at that code closely, list_nth() causes at least 2 function calls, and that's pretty heavy compared to the linitiali() macro. not well comment should be -- If the right branch is also an SAME condition, append it to the I moved that comment above the outer bock, so that the intention of the whole do-while code block is described in one place. I don't see any other issues, so after fixing comments this patch is ready for commit Thanks for the review Pavel. Attached is the updated patch, v4. It has the above edits, and a few code improvements, like not repeating the (root_kind == AEPR_AND ? .. : ..) ternary expression. Best regards, -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc. -- 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] review: Non-recursive processing of AND/OR lists
On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule pavel.steh...@gmail.comwrote: Hello just one small notices I dislike a name root_bool_expr, because, there is not a expression, but expression type. Can you use root_bool_expr_type instead? It is little bit longer, but more correct. Same not best name is root_char, maybe root_bool_op_name or root_expr_type and root_op_name ??? How about naming those 3 variables as follows: root_expr_kind root_expr_name root_bool_expr_type -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
2013/6/30 Gurjeet Singh gurj...@singh.im: On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule pavel.steh...@gmail.com wrote: Hello just one small notices I dislike a name root_bool_expr, because, there is not a expression, but expression type. Can you use root_bool_expr_type instead? It is little bit longer, but more correct. Same not best name is root_char, maybe root_bool_op_name or root_expr_type and root_op_name ??? How about naming those 3 variables as follows: root_expr_kind root_expr_name root_bool_expr_type +1 Pavel -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc. -- 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] review: Non-recursive processing of AND/OR lists
On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule pavel.steh...@gmail.comwrote: 2013/6/30 Gurjeet Singh gurj...@singh.im: On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule pavel.steh...@gmail.com wrote: How about naming those 3 variables as follows: root_expr_kind root_expr_name root_bool_expr_type +1 Thanks. Attached is the patch with that change. I'll update the commitfest entry with a link to this email. -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.
Re: [HACKERS] review: Non-recursive processing of AND/OR lists
2013/6/30 Gurjeet Singh gurj...@singh.im: On Sun, Jun 30, 2013 at 11:46 AM, Pavel Stehule pavel.steh...@gmail.com wrote: 2013/6/30 Gurjeet Singh gurj...@singh.im: On Sun, Jun 30, 2013 at 11:13 AM, Pavel Stehule pavel.steh...@gmail.com wrote: How about naming those 3 variables as follows: root_expr_kind root_expr_name root_bool_expr_type +1 Thanks. Attached is the patch with that change. I'll update the commitfest entry with a link to this email. ok I chechecked it - patched without warnings, all tests passed It is ready for commit Regards Pavel -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc. -- 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] review: Non-recursive processing of AND/OR lists
Thanks for the review Pavel. On Tue, Jun 18, 2013 at 3:01 PM, Pavel Stehule pavel.steh...@gmail.comwrote: Hello related to https://commitfest.postgresql.org/action/patch_view?id=1130 http://www.postgresql.org/message-id/cabwtf4v9rsjibwe+87pk83mmm7acdrg7sz08rq-4qyme8jv...@mail.gmail.com * motivation: remove recursive procession of AND/OR list (hangs with 10062 and more subexpressions) * patch is short, clean and respect postgresql source code requirements * patch was applied cleanly without warnings * all regression tests was passed * I successfully evaluated expression with 10 subexpressions * there is no significant slowdown possible improvements a = (A_Expr*) list_nth(pending, 0); a = (A_Expr*) linitial(pending); not well comment should be -- If the right branch is also an SAME condition, append it to the + /* +* If the right branch is also an AND condition, append it to the +* pending list, to be processed later. This allows us to walk even +* bushy trees, not just left-deep trees. +*/ + if (IsA(a-rexpr, A_Expr) ((A_Expr*)a-rexpr)-kind == root_kind) + { + pending = lappend(pending, a-rexpr); + } + else + { + expr = transformExprRecurse(pstate, a-rexpr); + expr = coerce_to_boolean(pstate, expr, root_kind == AEXPR_AND ? AND : OR); + exprs = lcons(expr, exprs); + } I don't see any other issues, so after fixing comments this patch is ready for commit Regards Pavel Stehule -- Gurjeet Singh http://gurjeet.singh.im/ EnterpriseDB Inc.