PostgreSQL source code interpretation (33)-query statement # 18 (query optimization-expression preprocessing # 3)
Args, refclause)) {win = false; break }} else// is this predicate equivalent to a single conditional expression? {if (! equal (refclause, clause)) {win = false; break } if (win) / / found the common predicate winners = lappend (winners, refclause); / / added to the result} / * * If no winners, we can't transform the OR * / if (winners = = NIL) return make_orclause (orlist) / / if found, return / * * Generate new OR list consisting of the remaining sub-clauses as is. * * found and generated new conditions * * If any clause degenerates to empty, then we have a situation like (A * AND B) OR (A), which can be reduced to just A-that is, the * additional conditions in other arms of the OR are irrelevant. * Note that because we use list_difference, any multiple occurrences of a * winning clause in an AND sub-clause will be removed automatically. * / neworlist = NIL; foreach (temp, orlist) / / traversing the OR linked list {Expr * clause = (Expr *) lfirst (temp); if (and_clause ((Node *) clause)) / / AND statement {List * subclauses = ((BoolExpr *) clause)-> args;// gets the conditional statement parameter subclauses = list_difference (subclauses, winners) / / remove the same part if (subclauses! = NIL) / / successfully, and generate a new AND statement {if (list_length (subclauses) = = 1) neworlist = lappend (neworlist, linitial (subclauses)); else neworlist = lappend (neworlist, make_andclause (subclauses)) } else {neworlist = NIL; / * degenerate case, see above * / break }} else// is not an AND statement {if (! list_member (winners, clause)) / / a single conditional statement, directly add conditional neworlist = lappend (neworlist, clause); else// OR statement? The public part has proposed to return directly without adding other conditions / / according to the absorption law, X AND (X OR B) is equivalent to X {neworlist = NIL; / * degenerate case, see above * / break. } / * * Append reduced OR to the winners list, if it's not degenerate, handling * the special case of one element correctly (can that really happen?) * Also be careful to maintain AND/OR flatness in case we pulled up a * sub-sub-OR-clause. * / if (neworlist! = NIL) / / newly generated linked list {if (list_length (neworlist) = = 1) winners = lappend (winners, linitial (neworlist)); else winners = lappend (winners, make_orclause (pull_ors (neworlist); / / flattening OR} / * * And return the constructed AND clause, again being wary of a single * element and AND/OR flatness. * / / return result if (list_length (winners) = = 1) return (Expr *) linitial (winners); else return make_andclause (pull_ands (winners)); / / flattening AND}
Pull_ors
/ * * pull_ors * Recursively flatten nested OR clauses into a single or-clause list. * * Input is the arglist of an OR clause. * Returns the rebuilt arglist (note original list structure is not touched). * / static List * pull_ors (List * orlist) {List * out_list = NIL; ListCell * arg; foreach (arg, orlist) {Node * subexpr = (Node *) lfirst (arg); / * Note: we can destructively concat the subexpression's arglist * because we know the recursive invocation of pull_ors will have * built a new arglist not shared with any other expr. Otherwise we'd * need a list_copy here. * / if (or_clause (subexpr)) out_list = list_concat (out_list, pull_ors (BoolExpr *) subexpr)-> args)); / / Recursive flattening else out_list = lappend (out_list, subexpr);} return out_list;}
Pull_ands
/ * * pull_ands * Recursively flatten nested AND clauses into a single and-clause list. * * Input is the arglist of an AND clause. * Returns the rebuilt arglist (note original list structure is not touched). * / static List * pull_ands (List * andlist) {List * out_list = NIL; ListCell * arg; foreach (arg, andlist) {Node * subexpr = (Node *) lfirst (arg); / * Note: we can destructively concat the subexpression's arglist * because we know the recursive invocation of pull_ands will have * built a new arglist not shared with any other expr. Otherwise we'd * need a list_copy here. * / if (and_clause (subexpr)) out_list = list_concat (out_list, pull_ands (BoolExpr *) subexpr)-> args)); / / Recursive flattening else out_list = lappend (out_list, subexpr);} return out_list;} IV. Tracking analysis
Test script:
Select * from t_dwxx where (FALSE OR dwbh = '1001') AND ((dwbh =' 1001' AND dwbh = '1002') OR (dwbh =' 1001' AND dwbh = '1003'))
This statement is normalized to the following SQL statement:
Select * from t_dwxx where dwbh=' 1001' AND (dwbh='1002' OR dwbh='1003');-- execution plan testdb=# explain verbose select * from t_dwxx where (FALSE OR dwbh=' 1001') AND ((dwbh=' 1001' AND dwbh='1002') OR (dwbh=' 1001' AND dwbh='1003')) QUERY PLAN -Seq Scan on public.t_dwxx (cost=0.00..12.80 rows=1 width=474) Output: dwmc Dwbh, dwdz Filter: ((t_dwxx.dwbh):: text = '1001'::text) AND (t_dwxx.dwbh):: text =' 1002'::text) OR ((t_dwxx.dwbh):: text = '1003'::text) (3 rows)
Gdb tracking:
(gdb) b find_duplicate_orsBreakpoint 1 at 0x7811b4: file prepqual.c, line 418. (gdb) cContinuing.Breakpoint 1, find_duplicate_ors (qual=0x2727528, is_check=false) at prepqual.c:418418 if (or_clause ((Node *) qual)) # input parameters, the BoolExpr#args linked list has two elements, one is (FALSE OR dwbh = '1001') # the other is ((dwbh = '1001' AND dwbh =' 1002') OR (dwbh = '1001' AND dwbh =' 1003')) (gdb) p * (BoolExpr *) qual$2 = {xpr = {type = T_BoolExpr}, boolop = AND_EXPR, args = 0x2726c88, location =-1} (gdb) p * ((BoolExpr *) qual)-> args$3 = {type = T_List, length = 2, head = 0x2726c68 Tail = 0x2727508}... # enter AND branch 462else if (and_clause ((Node *) qual)). # get the first element of the linked list 470 Expr * arg = (Expr *) lfirst (temp) # re-entering find_duplicate_ors#FALSE OR dwbh='1001' has previously been simplified to dwbh='1001', so return Breakpoint 1, find_duplicate_ors (qual=0x2726bc8, is_check=false) at prepqual.c:418418 if (or_clause ((Node *) qual)) (gdb) n462 else if (and_clause ((Node *) qual)) (gdb) # 515 return qual directly here (gdb) n516} (gdb) 475 if (arg & & IsA (arg, Const))... 497 andlist = lappend (andlist, arg); (gdb) n468 foreach (temp, (BoolExpr *) qual)-> args) (gdb) n470 Expr * arg = (Expr *) lfirst (temp); (gdb) 472 arg = find_duplicate_ors (arg, is_check) The next element of the # linked list, namely # ((dwbh = '1001' AND dwbh =' 1002') OR (dwbh = '1001' AND dwbh =' 1003')) # consists of two BoolExpr (gdb) p * (BoolExpr *) arg$23 = {xpr = {type = T_BoolExpr}, boolop = OR_EXPR, args = 0x27270d8, location =-1} (gdb) p * ((BoolExpr *) arg)-> args$24 = {type = T_List, length = 2, head = 0x27270b8 Tail = 0x27274b8} (gdb) p * (Node *) ((BoolExpr *) arg)-> args- > head- > data.ptr_value$25 = {type = T_BoolExpr} (gdb) p * (Node *) ((BoolExpr *) arg)-> args- > head- > next- > data.ptr_value$26 = {type = T_BoolExpr}.. # arg on the left and right sides of args is finished with 424 foreach (temp, ((BoolExpr *) qual)-> args) (gdb) 457 orlist = pull_ors (orlist) ... # enter process_duplicate_ors460 return process_duplicate_ors (orlist); (gdb) stepprocess_duplicate_ors (orlist=0x2727858) at prepqual.c:529529 List * reference = NIL;...# to get the linked list of the least predicates (gdb) p * reference$36 = {type = T_List, length = 2, head = 0x27278a8, tail = 0x27278f8}. # get the common predicate winner! That is, dwbh = '1001' (gdb) p * winners$40 = {type = T_List, length = 1, head = 0x2727918, tail = 0x2727918}... (gdb) canonicalize_qual (qual=0x2727528, is_check=false) at prepqual.c:309309 return newqual; (gdb) p * newqual$43 = {type = T_BoolExpr} (gdb) p * (BoolExpr *) newqual$45 = {xpr = {type = T_BoolExpr}, boolop = AND_EXPR, args = 0x2727c18, location =-1} # DONE! 5. Summary
1. The mathematical basis of optimization: Boolean algebra and related laws.
2. The process of expression normalization: the processing logic of expression flattening and common predicate extraction.
VI. Reference materials
Boolean algebra
Prepqual.c
