Re: review: Non-recursive processing of AND/OR lists - Mailing list pgsql-hackers
From | Tom Lane |
---|---|
Subject | Re: review: Non-recursive processing of AND/OR lists |
Date | |
Msg-id | 16332.1398392477@sss.pgh.pa.us Whole thread Raw |
In response to | Re: review: Non-recursive processing of AND/OR lists (Gurjeet Singh <gurjeet@singh.im>) |
Responses |
Re: review: Non-recursive processing of AND/OR lists
|
List | pgsql-hackers |
Gurjeet Singh <gurjeet@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 *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2), ! @2); } | a_expr NOT BETWEEN opt_asymmetric b_expr AND b_expr %prec BETWEEN { ! $$ = (Node *) makeA_Expr(AEXPR_OR, NIL, (Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2), ! @2); } | a_expr BETWEEN SYMMETRIC b_expr AND b_expr %prec BETWEEN { ! $$ = (Node *) makeA_Expr(AEXPR_OR, NIL, ! (Node *) makeA_Expr(AEXPR_AND, NIL, (Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2), ! @2), ! (Node *) makeA_Expr(AEXPR_AND, NIL, (Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $6, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $4, @2), ! @2), ! @2); } | a_expr NOT BETWEEN SYMMETRIC b_expr AND b_expr %prec BETWEEN { ! $$ = (Node *) makeA_Expr(AEXPR_AND, NIL, ! (Node *) makeA_Expr(AEXPR_OR, NIL, (Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2), ! @2), ! (Node *) makeA_Expr(AEXPR_OR, NIL, (Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $7, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $5, @2), ! @2), ! @2); } | a_expr IN_P in_expr { --- 11045,11087 ---- */ | a_expr BETWEEN opt_asymmetric b_expr AND b_expr %prec BETWEEN { ! $$ = makeAndExpr( (Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2), ! @2); } | a_expr NOT BETWEEN opt_asymmetric b_expr AND b_expr %prec BETWEEN { ! $$ = makeOrExpr( (Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2), ! @2); } | a_expr BETWEEN SYMMETRIC b_expr AND b_expr %prec BETWEEN { ! $$ = makeOrExpr( ! makeAndExpr( (Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $4, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $6, @2), ! @2), ! makeAndExpr( (Node *) makeSimpleA_Expr(AEXPR_OP, ">=", $1, $6, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, "<=", $1, $4, @2), ! @2), ! @2); } | a_expr NOT BETWEEN SYMMETRIC b_expr AND b_expr %prec BETWEEN { ! $$ = makeAndExpr( ! makeOrExpr( (Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $5, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $7, @2), ! @2), ! makeOrExpr( (Node *) makeSimpleA_Expr(AEXPR_OP, "<", $1, $7, @2), (Node *) makeSimpleA_Expr(AEXPR_OP, ">", $1, $5, @2), ! @2), ! @2); } | a_expr IN_P in_expr { *************** a_expr: c_expr { $$ = $1; } *** 11114,11120 **** n->operName = list_make1(makeString("=")); n->location = @3; /* Stick a NOT on top */ ! $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, (Node *) n, @2); } else { --- 11115,11121 ---- n->operName = list_make1(makeString("=")); n->location = @3; /* Stick a NOT on top */ ! $$ = makeNotExpr((Node *) n, @2); } else { *************** a_expr: c_expr { $$ = $1; } *** 11162,11171 **** } | a_expr IS NOT DOCUMENT_P %prec IS { ! $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, ! makeXmlExpr(IS_DOCUMENT, NULL, NIL, ! list_make1($1), @2), ! @2); } ; --- 11163,11171 ---- } | a_expr IS NOT DOCUMENT_P %prec IS { ! $$ = makeNotExpr(makeXmlExpr(IS_DOCUMENT, NULL, NIL, ! list_make1($1), @2), ! @2); } ; *************** b_expr: c_expr *** 11216,11223 **** } | b_expr IS NOT DISTINCT FROM b_expr %prec IS { ! $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, ! NULL, (Node *) makeSimpleA_Expr(AEXPR_DISTINCT, "=", $1, $6, @2), @2); } | b_expr IS OF '(' type_list ')' %prec IS { --- 11216,11224 ---- } | b_expr IS NOT DISTINCT FROM b_expr %prec IS { ! $$ = makeNotExpr((Node *) makeSimpleA_Expr(AEXPR_DISTINCT, ! "=", $1, $6, @2), ! @2); } | b_expr IS OF '(' type_list ')' %prec IS { *************** b_expr: c_expr *** 11234,11243 **** } | b_expr IS NOT DOCUMENT_P %prec IS { ! $$ = (Node *) makeA_Expr(AEXPR_NOT, NIL, NULL, ! makeXmlExpr(IS_DOCUMENT, NULL, NIL, ! list_make1($1), @2), ! @2); } ; --- 11235,11243 ---- } | b_expr IS NOT DOCUMENT_P %prec IS { ! $$ = makeNotExpr(makeXmlExpr(IS_DOCUMENT, NULL, NIL, ! list_make1($1), @2), ! @2); } ; *************** doNegateFloat(Value *v) *** 13693,13698 **** --- 13693,13738 ---- } static Node * + makeAndExpr(Node *lexpr, Node *rexpr, int location) + { + /* Flatten "a AND b AND c ..." to a single BoolExpr on sight */ + if (IsA(lexpr, BoolExpr)) + { + BoolExpr *blexpr = (BoolExpr *) lexpr; + + if (blexpr->boolop == AND_EXPR) + { + blexpr->args = lappend(blexpr->args, rexpr); + return (Node *) blexpr; + } + } + return (Node *) makeBoolExpr(AND_EXPR, list_make2(lexpr, rexpr), location); + } + + static Node * + makeOrExpr(Node *lexpr, Node *rexpr, int location) + { + /* Flatten "a OR b OR c ..." to a single BoolExpr on sight */ + if (IsA(lexpr, BoolExpr)) + { + BoolExpr *blexpr = (BoolExpr *) lexpr; + + if (blexpr->boolop == OR_EXPR) + { + blexpr->args = lappend(blexpr->args, rexpr); + return (Node *) blexpr; + } + } + return (Node *) makeBoolExpr(OR_EXPR, list_make2(lexpr, rexpr), location); + } + + static Node * + makeNotExpr(Node *expr, int location) + { + return (Node *) makeBoolExpr(NOT_EXPR, list_make1(expr), location); + } + + static Node * makeAArrayExpr(List *elements, int location) { A_ArrayExpr *n = makeNode(A_ArrayExpr); diff --git a/src/backend/parser/parse_clause.c b/src/backend/parser/parse_clause.c index aa704bb..a71f611 100644 *** a/src/backend/parser/parse_clause.c --- b/src/backend/parser/parse_clause.c *************** transformJoinUsingClause(ParseState *pst *** 332,338 **** RangeTblEntry *leftRTE, RangeTblEntry *rightRTE, List *leftVars, List *rightVars) { ! Node *result = NULL; ListCell *lvars, *rvars; --- 332,339 ---- RangeTblEntry *leftRTE, RangeTblEntry *rightRTE, List *leftVars, List *rightVars) { ! Node *result; ! List *andargs = NIL; ListCell *lvars, *rvars; *************** transformJoinUsingClause(ParseState *pst *** 358,375 **** copyObject(lvar), copyObject(rvar), -1); ! /* And combine into an AND clause, if multiple join columns */ ! if (result == NULL) ! result = (Node *) e; ! else ! { ! A_Expr *a; ! ! a = makeA_Expr(AEXPR_AND, NIL, result, (Node *) e, -1); ! result = (Node *) a; ! } } /* * Since the references are already Vars, and are certainly from the input * relations, we don't have to go through the same pushups that --- 359,374 ---- copyObject(lvar), copyObject(rvar), -1); ! /* Prepare to combine into an AND clause, if multiple join columns */ ! andargs = lappend(andargs, e); } + /* Only need an AND if there's more than one join column */ + if (list_length(andargs) == 1) + result = (Node *) linitial(andargs); + else + result = (Node *) makeBoolExpr(AND_EXPR, andargs, -1); + /* * Since the references are already Vars, and are certainly from the input * relations, we don't have to go through the same pushups that diff --git a/src/backend/parser/parse_expr.c b/src/backend/parser/parse_expr.c index 81c9338..cb76133 100644 *** a/src/backend/parser/parse_expr.c --- b/src/backend/parser/parse_expr.c *************** bool Transform_null_equals = false; *** 41,55 **** 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 *transformAExprNot(ParseState *pstate, A_Expr *a); static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a); static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a); static Node *transformAExprDistinct(ParseState *pstate, A_Expr *a); static Node *transformAExprNullIf(ParseState *pstate, A_Expr *a); static Node *transformAExprOf(ParseState *pstate, A_Expr *a); static Node *transformAExprIn(ParseState *pstate, A_Expr *a); static Node *transformFuncCall(ParseState *pstate, FuncCall *fn); static Node *transformCaseExpr(ParseState *pstate, CaseExpr *c); static Node *transformSubLink(ParseState *pstate, SubLink *sublink); --- 41,53 ---- static Node *transformExprRecurse(ParseState *pstate, Node *expr); static Node *transformParamRef(ParseState *pstate, ParamRef *pref); static Node *transformAExprOp(ParseState *pstate, A_Expr *a); static Node *transformAExprOpAny(ParseState *pstate, A_Expr *a); static Node *transformAExprOpAll(ParseState *pstate, A_Expr *a); static Node *transformAExprDistinct(ParseState *pstate, A_Expr *a); static Node *transformAExprNullIf(ParseState *pstate, A_Expr *a); static Node *transformAExprOf(ParseState *pstate, A_Expr *a); static Node *transformAExprIn(ParseState *pstate, A_Expr *a); + static Node *transformBoolExpr(ParseState *pstate, BoolExpr *a); static Node *transformFuncCall(ParseState *pstate, FuncCall *fn); static Node *transformCaseExpr(ParseState *pstate, CaseExpr *c); static Node *transformSubLink(ParseState *pstate, SubLink *sublink); *************** transformExprRecurse(ParseState *pstate, *** 223,237 **** case AEXPR_OP: result = transformAExprOp(pstate, a); break; - case AEXPR_AND: - result = transformAExprAnd(pstate, a); - break; - case AEXPR_OR: - result = transformAExprOr(pstate, a); - break; - case AEXPR_NOT: - result = transformAExprNot(pstate, a); - break; case AEXPR_OP_ANY: result = transformAExprOpAny(pstate, a); break; --- 221,226 ---- *************** transformExprRecurse(ParseState *pstate, *** 258,263 **** --- 247,256 ---- break; } + case T_BoolExpr: + result = transformBoolExpr(pstate, (BoolExpr *) expr); + break; + case T_FuncCall: result = transformFuncCall(pstate, (FuncCall *) expr); break; *************** transformExprRecurse(ParseState *pstate, *** 337,343 **** case T_DistinctExpr: case T_NullIfExpr: case T_ScalarArrayOpExpr: - case T_BoolExpr: case T_FieldSelect: case T_FieldStore: case T_RelabelType: --- 330,335 ---- *************** transformAExprOp(ParseState *pstate, A_E *** 919,964 **** } static Node * - transformAExprAnd(ParseState *pstate, A_Expr *a) - { - Node *lexpr = transformExprRecurse(pstate, a->lexpr); - Node *rexpr = transformExprRecurse(pstate, a->rexpr); - - lexpr = coerce_to_boolean(pstate, lexpr, "AND"); - rexpr = coerce_to_boolean(pstate, rexpr, "AND"); - - return (Node *) makeBoolExpr(AND_EXPR, - list_make2(lexpr, rexpr), - a->location); - } - - static Node * - transformAExprOr(ParseState *pstate, A_Expr *a) - { - Node *lexpr = transformExprRecurse(pstate, a->lexpr); - Node *rexpr = transformExprRecurse(pstate, a->rexpr); - - lexpr = coerce_to_boolean(pstate, lexpr, "OR"); - rexpr = coerce_to_boolean(pstate, rexpr, "OR"); - - return (Node *) makeBoolExpr(OR_EXPR, - list_make2(lexpr, rexpr), - a->location); - } - - static Node * - transformAExprNot(ParseState *pstate, A_Expr *a) - { - Node *rexpr = transformExprRecurse(pstate, a->rexpr); - - rexpr = coerce_to_boolean(pstate, rexpr, "NOT"); - - return (Node *) makeBoolExpr(NOT_EXPR, - list_make1(rexpr), - a->location); - } - - static Node * transformAExprOpAny(ParseState *pstate, A_Expr *a) { Node *lexpr = transformExprRecurse(pstate, a->lexpr); --- 911,916 ---- *************** transformAExprIn(ParseState *pstate, A_E *** 1238,1243 **** --- 1190,1231 ---- } static Node * + transformBoolExpr(ParseState *pstate, BoolExpr *a) + { + List *args = NIL; + const char *opname; + ListCell *lc; + + switch (a->boolop) + { + case AND_EXPR: + opname = "AND"; + break; + case OR_EXPR: + opname = "OR"; + break; + case NOT_EXPR: + opname = "NOT"; + break; + default: + elog(ERROR, "unrecognized boolop: %d", (int) a->boolop); + opname = NULL; /* keep compiler quiet */ + break; + } + + foreach(lc, a->args) + { + Node *arg = (Node *) lfirst(lc); + + arg = transformExprRecurse(pstate, arg); + arg = coerce_to_boolean(pstate, arg, opname); + args = lappend(args, arg); + } + + return (Node *) makeBoolExpr(a->boolop, args, a->location); + } + + static Node * transformFuncCall(ParseState *pstate, FuncCall *fn) { List *targs; *************** make_row_comparison_op(ParseState *pstat *** 2428,2437 **** /* * For = and <> cases, we just combine the pairwise operators with AND or * OR respectively. - * - * Note: this is presently the only place where the parser generates - * BoolExpr with more than two arguments. Should be OK since the rest of - * the system thinks BoolExpr is N-argument anyway. */ if (rctype == ROWCOMPARE_EQ) return (Node *) makeBoolExpr(AND_EXPR, opexprs, location); --- 2416,2421 ---- diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h index 18d4991..59916eb 100644 *** a/src/include/nodes/parsenodes.h --- b/src/include/nodes/parsenodes.h *************** typedef struct ParamRef *** 225,233 **** typedef enum A_Expr_Kind { AEXPR_OP, /* normal operator */ - AEXPR_AND, /* booleans - name field is unused */ - AEXPR_OR, - AEXPR_NOT, AEXPR_OP_ANY, /* scalar op ANY (array) */ AEXPR_OP_ALL, /* scalar op ALL (array) */ AEXPR_DISTINCT, /* IS DISTINCT FROM - name must be "=" */ --- 225,230 ---- diff --git a/src/include/nodes/primnodes.h b/src/include/nodes/primnodes.h index 9cce60b..ed73109 100644 *** a/src/include/nodes/primnodes.h --- b/src/include/nodes/primnodes.h *************** typedef struct ScalarArrayOpExpr *** 458,469 **** * BoolExpr - expression node for the basic Boolean operators AND, OR, NOT * * Notice the arguments are given as a List. For NOT, of course the list ! * must always have exactly one element. For AND and OR, the executor can ! * handle any number of arguments. The parser generally treats AND and OR ! * as binary and so it typically only produces two-element lists, but the ! * optimizer will flatten trees of AND and OR nodes to produce longer lists ! * when possible. There are also a few special cases where more arguments ! * can appear before optimization. */ typedef enum BoolExprType { --- 458,465 ---- * BoolExpr - expression node for the basic Boolean operators AND, OR, NOT * * Notice the arguments are given as a List. For NOT, of course the list ! * must always have exactly one element. For AND and OR, there can be two ! * or more arguments. */ typedef enum BoolExprType { diff --git a/src/test/regress/expected/rules.out b/src/test/regress/expected/rules.out index 6c51d0d..c3188a7 100644 *** a/src/test/regress/expected/rules.out --- b/src/test/regress/expected/rules.out *************** shoe_ready| SELECT rsh.shoename, *** 2117,2123 **** int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail FROM shoe rsh, shoelace rsl ! WHERE (((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm)) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm)); shoelace| SELECT s.sl_name, s.sl_avail, s.sl_color, --- 2117,2123 ---- int4smaller(rsh.sh_avail, rsl.sl_avail) AS total_avail FROM shoe rsh, shoelace rsl ! WHERE ((rsl.sl_color = rsh.slcolor) AND (rsl.sl_len_cm >= rsh.slminlen_cm) AND (rsl.sl_len_cm <= rsh.slmaxlen_cm)); shoelace| SELECT s.sl_name, s.sl_avail, s.sl_color,
pgsql-hackers by date: