[关闭]
@Spongcer 2015-04-10T06:49:50.000000Z 字数 5417 阅读 1610

PostgreSQL-process_duplicate_ors

PG

  1. test=# EXPLAIN SELECT * FROM T1 WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1) ;
  2.                        QUERY PLAN
  3. ---------------------------------------------------------
  4.  Seq Scan on t1  (cost=0.00..45.40 rows=1 width=16)
  5.    Filter: ((a = 1) AND ((b = 1) OR (c = 1) OR (d = 1)))
  6. (2 行记录)
  9. test=#
  1. /*
  2.  * process_duplicate_ors
  3.  *    Given a list of exprs which are ORed together, try to apply
  4.  *    the inverse OR distributive law.
  5.  *
  6.  * Returns the resulting expression (could be an AND clause, an OR
  7.  * clause, or maybe even a single subexpression).
  8.  */
  10. /*
  11.  * 假设表T1有四列：A、B、C、D。
  12.  * 
  13.  * 这个函数处理这种情况，对于一个选择，SELECT * FROM TEST
  14.  * WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1);
  15.  * 
  16.  * 语句中的WHERE条件：
  17.  *      (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1)
  18.  * 可以改写为：
  19.  *      (A=1）AND （B=1 OR C=1 OR D=1)
  20.  * 这就是这个函数的主要功能。
  21.  *
  22.  * 这个函数的参数是一个list, 对于上述的WHERE条件，orlist的结构如下：
  23.  * orlist中有一个元素，是OR_EXPR类型的BoolExpr，BoolExpr中的结构如下：
  24.  * typedef struct BoolExpr
  25.  * {
  26.  *   Expr xpr; = 略
  27.  *   BoolExprType boolop; = OR_EXPR
  28.  *   List *args;    = OR中的3个条件，即(A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1)
  29.  *   bool plusFlag; = 略
  30.  * } BoolExpr;
  31.  *
  32.  * 下面分析函数的具体实现，大致的步骤为：
  33.  * 1）分析每个OR中的公共项， 2）提取公共项， 3）合并剩余项为AND。
  34.  */
  35. static Expr *
  36. process_duplicate_ors(List *orlist)
  37. {
  38.     List       *reference = NIL;
  39.     int         num_subclauses = 0;
  40.     List       *winners;
  41.     List       *neworlist;
  42.     ListCell   *temp;
  44.     if (orlist == NIL)
  45.         return NULL;            /* probably can't happen */
  47.     /* 如果只有一个。。。。，那就算了吧 */
  48.     if (list_length(orlist) == 1)       /* single-expression OR (can this
  49.                                          * happen?) */
  50.         return linitial(orlist);
  52.     /*
  53.      * Choose the shortest AND clause as the reference list --- obviously, any
  54.      * subclause not in this clause isn't in all the clauses. If we find a
  55.      * clause that's not an AND, we can treat it as a one-element AND clause,
  56.      * which necessarily wins as shortest.
  57.      */
  58.     /*
  59.      * “找最短”。
  60.      * 在WHERE语句中：
  61.      *      (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1)
  62.      * OR操作串联了3个子语句，找到其中最短的一个，因为如果有公共项，那么最短的那个也一定
  63.      * 包含公共项，那么通过找到最短的那个，在后面的操作里能减少 比较 的次数。
  64.      * 在上面的WHERE语句中，3个子语句的长度相同，按照如下执行过程，找到的应该是(A=1 AND B=1)，
  65.      * 即第一个。
  66.      */
  67.     foreach(temp, orlist)
  68.     {
  69.         Expr       *clause = (Expr *) lfirst(temp);
  71.         if (and_clause((Node *) clause))
  72.         {
  73.             List       *subclauses = ((BoolExpr *) clause)->args;
  74.             int         nclauses = list_length(subclauses);
  76.             /* 
  77.              * 这里判断子语句里的长度，比如对于(A=1 AND B=1)子语句，
  78.              * 他实际上是一个AND连接起来的两个 子子语句， 那么他的长度就是2。
  79.              *
  80.              * 通过nclauses记录最短的子语句，如果有更短的（nclauses < num_subclauses），
  81.              * 那么就替换成最短的。
  82.              */
  83.             if (reference == NIL || nclauses < num_subclauses)
  84.             {
  85.                 reference = subclauses;
  86.                 num_subclauses = nclauses;
  87.             }
  88.         }
  89.         else
  90.         {
  91.             /* 
  92.              * 还有一种情况， 就是可能子句不是一个AND语句，这样看上去不大符合规则，
  93.              * 那么把他看做一个整体，那这个就是最短元素。
  94.              * 
  95.              ******************************
  96.              * 如果代码执行到这里，那么只有两种情况：
  97.              * 一种是 ... WHERE (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1)。
  98.              * 一种是 ... WHERE ((A=1 OR C=1) AND B=1) OR (A=1 OR C=1).
  99.              * 如果是这两种情况，都可以做如下简化：
  100.              * 第一种情况简化为 A=1
  101.              * 第二种情况化简为 (A=1 OR C=1)
  102.              * 
  103.              * 第三种情况待补充...
  104.              */
  105.             reference = list_make1(clause);
  106.             break;
  107.         }
  108.     }
  110.     /*
  111.      * Just in case, eliminate any duplicates in the reference list.
  112.      */
  113.     /* 找到最短的， 存到List */
  114.     reference = list_union(NIL, reference);
  116.     /*
  117.      * Check each element of the reference list to see if it's in all the OR
  118.      * clauses.  Build a new list of winning clauses.
  119.      */
  120.     /*
  121.      * “找公共项”。
  122.      *
  123.      * NOTE:这时候就能体现“找最短”带来的优势，外层循环次数会少一些。
  124.      *
  125.      * 如果WHERE语句是：
  126.      *      (A=1 AND B=1) OR (A=1 AND C=1) OR (A=1 AND D=1)
  127.      * “找最短”中找到的一定是(A=1 AND B=1)。
  128.      * 则外层会有两次循环...（foreach(temp, reference)），两次循环的变量分别为
  129.      *          A=1 和 B=1。
  130.      * 内层有三次循环...（foreach(temp2, orlist)），三次循环的变量分别为
  131.      *          (A=1 AND B=1) 和 (A=1 AND C=1) 和 (A=1 AND D=1)
  132.      * 
  133.      * 示例如下：
  134.      * 假如现在外层循环第一次执行，即查找A=1的公共项，进而假如内层循环也是第一次执行，
  135.      * 即在(A=1 AND B=1)中查找是否存在A=1这个公共项，发现是存在的（list_member），
  136.      * 则依次判断内层循环的第二个子句...
  137.      *
  138.      * 如上例，具体来说，这些循环分别作的操作是：
  139.      *  外层第一次：
  140.      *      判断A=1是否在(A=1 AND B=1)，在，判断下一个
  141.      *      判断A=1是否在(A=1 AND C=1)，在，判断下一个
  142.      *      判断A=1是否在(A=1 AND D=1)，在，A=1是公共项，记录（winners = lappend...）
  143.      *  外层第二次：
  144.      *      判断B=1是否在(A=1 AND B=1)，在，判断下一个
  145.      *      判断B=1是否在(A=1 AND C=1)，不在，跳出循环，下一个不用判断了。
  146.      *      判断B=1是否在(A=1 AND D=1)，未执行，因为上一个不含公共项，就不可能提取了。
  147.      */
  148.     winners = NIL;
  149.     foreach(temp, reference)
  150.     {
  151.         Expr       *refclause = (Expr *) lfirst(temp);
  152.         bool        win = true;
  153.         ListCell   *temp2;
  155.         foreach(temp2, orlist)
  156.         {
  157.             Expr       *clause = (Expr *) lfirst(temp2);
  159.             if (and_clause((Node *) clause))
  160.             {
  161.                 if (!list_member(((BoolExpr *) clause)->args, refclause))
  162.                 {
  163.                     win = false;
  164.                     break;
  165.                 }
  166.             }
  167.             else
  168.             {
  169.                 if (!equal(refclause, clause))
  170.                 {
  171.                     win = false;
  172.                     break;
  173.                 }
  174.             }
  175.         }
  177.         if (win)
  178.             winners = lappend(winners, refclause);
  179.     }
  181.     /*
  182.      * If no winners, we can't transform the OR
  183.      */
  184.     if (winners == NIL)
  185.         return make_orclause(orlist);
  187.     /*
  188.      * Generate new OR list consisting of the remaining sub-clauses.
  189.      *
  190.      * If any clause degenerates to empty, then we have a situation like (A
  191.      * AND B) OR (A), which can be reduced to just A --- that is, the
  192.      * additional conditions in other arms of the OR are irrelevant.
  193.      *
  194.      * Note that because we use list_difference, any multiple occurrences of a
  195.      * winning clause in an AND sub-clause will be removed automatically.
  196.      */
  197.     /*
  198.      * “提取公共项”。
  199.      * 用list_difference删除公共项，实现细节不在赘述。
  200.      */
  201.     neworlist = NIL;
  202.     foreach(temp, orlist)
  203.     {
  204.         Expr       *clause = (Expr *) lfirst(temp);
  206.         if (and_clause((Node *) clause))
  207.         {
  208.             List       *subclauses = ((BoolExpr *) clause)->args;
  210.             /* 看这里...看这里..., 消除公共项 */
  211.             subclauses = list_difference(subclauses, winners);
  212.             if (subclauses != NIL)
  213.             {
  214.                 /* 消除后，剩余的拼接起来，拼接成：（B=1 OR C=1 OR D=1)*/
  215.                 if (list_length(subclauses) == 1)
  216.                     neworlist = lappend(neworlist, linitial(subclauses));
  217.                 else
  218.                     neworlist = lappend(neworlist, make_andclause(subclauses));
  219.             }
  220.             else
  221.             {
  222.                 /*
  223.                  * 这说明子语句中，有一个全部是公共项，也就是如下形式：
  224.                  *      ... WHERE (A=1 AND B=1) OR (A=1)
  225.                  *
  226.                  * 这时候公共项是A=1，第一个子句是(A=1 AND B=1)，第二个子句是（A=1),
  227.                  * 第二个子句经过list_difference，返回的结果是NULL。
  228.                  * 对于这种情况，实际上可以化简为：A=1，因为(A=1 AND B=1)一定满足A=1的情况。
  229.                  */
  230.                 neworlist = NIL;    /* degenerate case, see above */
  231.                 break;
  232.             }
  233.         }
  234.         else
  235.         {
  236.             if (!list_member(winners, clause))
  237.                 neworlist = lappend(neworlist, clause);
  238.             else
  239.             {
  240.                 neworlist = NIL;    /* degenerate case, see above */
  241.                 break;
  242.             }
  243.         }
  244.     }
  246.     /*
  247.      * Append reduced OR to the winners list, if it's not degenerate, handling
  248.      * the special case of one element correctly (can that really happen?).
  249.      * Also be careful to maintain AND/OR flatness in case we pulled up a
  250.      * sub-sub-OR-clause.
  251.      */
  252.     if (neworlist != NIL)
  253.     {
  254.         if (list_length(neworlist) == 1)
  255.             winners = lappend(winners, linitial(neworlist));
  256.         else
  257.             /*neworlist里面应该是（B=1 OR C=1 OR D=1)，所以用make_orclause */
  258.             winners = lappend(winners, make_orclause(pull_ors(neworlist)));
  259.     }
  261.     /*
  262.      * And return the constructed AND clause, again being wary of a single
  263.      * element and AND/OR flatness.
  264.      */
  265.     if (list_length(winners) == 1)
  266.         return (Expr *) linitial(winners);
  267.     else
  268.         /* 返回的形式是：(A=1）AND （B=1 OR C=1 OR D=1)，所以会用make_andclause */
  269.         return make_andclause(pull_ands(winners));
  270. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注