simplify_joins 外联接消除、嵌套消除

bool
SELECT_LEX::simplify_joins(THD *thd,
                           List *join_list, bool top,
                           bool in_sj, Item **cond, uint *changelog)
{
  /*
    Each type of change done by this function, or its recursive calls, is
    tracked in a bitmap:
  */
  enum change
  {
    NONE= 0,
    OUTER_JOIN_TO_INNER= 1 << 0,
    JOIN_COND_TO_WHERE= 1 << 1,
    PAREN_REMOVAL= 1 << 2, 
    SEMIJOIN= 1 << 3
  };
  uint changes= 0; // To keep track of changes.
  if (changelog == NULL) // This is the top call.
    changelog= &changes;


  TABLE_LIST *table;
  NESTED_JOIN *nested_join;
  TABLE_LIST *prev_table= 0;
  List_iterator li(*join_list);
  const bool straight_join= active_options() & SELECT_STRAIGHT_JOIN;
  DBUG_ENTER("simplify_joins");


  /* 
    Try to simplify join operations from join_list.
    The most outer join operation is checked for conversion first. 
  */
  while ((table= li++))
  {
    table_map used_tables;
    table_map not_null_tables= (table_map) 0;

    if ((nested_join= table->nested_join))
    {
// table 是个嵌套联接，如：tb3 join (tb1 left join tb2 on ... )  on ... ,table为(tb1 left join tb2 on ...)
// 消除table内部的外联接
      if (table->join_cond())
      {
        Item *join_cond= table->join_cond();
 
  // 试图通过table->join_cond的联接条件消除table内的外联接
        if (simplify_joins(thd, &nested_join->join_list,
                           false, in_sj || table->sj_cond(),
                           &join_cond, changelog))
          DBUG_RETURN(true);
// 至此，table 内的 tb1 left join tb2 on ... 被转换为：(tb1,tb2),原来tb2上的 join cond与table->join_cond合并
// table的嵌套并未消除
        if (join_cond != table->join_cond())
        {
          DBUG_ASSERT(join_cond);
          table->set_join_cond(join_cond);
        }
      }
      nested_join->used_tables= (table_map) 0;
      nested_join->not_null_tables=(table_map) 0;
     // 通过where cond或上一层的JOIN COND 消除table内的外联接，
      if (simplify_joins(thd, &nested_join->join_list, top,
                         in_sj || table->sj_cond(), cond, changelog))
        DBUG_RETURN(true);
      used_tables= nested_join->used_tables;
      not_null_tables= nested_join->not_null_tables;  
    }
    else
    {
      used_tables= table->map();
      if (*cond)
        not_null_tables= (*cond)->not_null_tables();
    }
      
    if (table->embedding)
    {
      table->embedding->nested_join->used_tables|= used_tables;
      table->embedding->nested_join->not_null_tables|= not_null_tables;
    }


    // table 为内表,或有合取谓词使table拒绝空值
    if (!table->outer_join || (used_tables & not_null_tables))
    {
        // table拒绝空值
      if (table->outer_join)
      {
        *changelog|= OUTER_JOIN_TO_INNER;
        table->outer_join= 0;
      }
  /* table 为非外联接内表（或外联接内表，但table拒绝空值）
   可将联接条件并入WHERE COND 或将联接条件并入上层的JOIN COND
   将进行如下转换：
   1、tb1 [inner/left] join tb2 on tb1.a=tb2.a where cond ==> tb1,tb2 where cond AND tb1.a=tb2.a
   或2、tb1 [inner/left] join tb2 on tb1.a=tb2.a left join tb3 on tb1.b=tb3.b ==> (tb1,tb2) left join tb3 on tb1.b=tb3.b AND tb1.a=tb2.a
*/
      if (table->join_cond())
      {
        *changelog|= JOIN_COND_TO_WHERE;
        /* Add join condition to the WHERE or upper-level join condition. */
        if (*cond)
        {
          Item_cond_and *new_cond=
            static_cast(and_conds(*cond, table->join_cond()));
          if (!new_cond)
            DBUG_RETURN(true);
          new_cond->top_level_item();
          /*
            It is always a new item as both the upper-level condition and a
            join condition existed
          */
          DBUG_ASSERT(!new_cond->fixed);
          if (new_cond->fix_fields(thd, NULL))
            DBUG_RETURN(true);

          /* If join condition has a pending rollback in THD::change_list */
          List_iterator lit(*new_cond->argument_list());
          Item *arg;
          while ((arg= lit++))
          {
            /*
              Check whether the arguments to AND need substitution替代
              of rollback location.
            */
            thd->replace_rollback_place(lit.ref());
          }
          *cond= new_cond;
        }
        else
        {
          *cond= table->join_cond();
          /* If join condition has a pending rollback in THD::change_list */
          thd->replace_rollback_place(cond);
        }
        table->set_join_cond(NULL);
      } // if (table->join_cond())
    }

    if (!top)
      continue;

    /* 
      Only inner tables of non-convertible outer joins remain with
      the join condition.
    */ 
    if (table->join_cond())
    {
      table->dep_tables|= table->join_cond()->used_tables();

      // At this point the joined tables always have an embedding join nest:
      DBUG_ASSERT(table->embedding);

      table->dep_tables&= ~table->embedding->nested_join->used_tables;

      // Embedding table depends on tables used in embedded join conditions. 
      table->embedding->on_expr_dep_tables|= table->join_cond()->used_tables();
    }

    if (prev_table)
    {
      /* The order of tables is reverse: prev_table follows table */
      if (prev_table->straight || straight_join)
        prev_table->dep_tables|= used_tables;
      if (prev_table->join_cond())
      {
        prev_table->dep_tables|= table->on_expr_dep_tables;
        table_map prev_used_tables= prev_table->nested_join ?
                           prev_table->nested_join->used_tables :
                           prev_table->map();
        /* 
          If join condition contains only references to inner tables
          we still make the inner tables dependent on the outer tables.
          It would be enough to set dependency only on one outer table
          for them. Yet this is really a rare case.
          Note:
          PSEUDO_TABLE_BITS mask should not be counted as it
          prevents update of inner table dependencies.
          For example it might happen if RAND()/COUNT(*) function
          is used in JOIN ON clause.
*/  
        if (!((prev_table->join_cond()->used_tables() & ~PSEUDO_TABLE_BITS) &
              ~prev_used_tables))
          prev_table->dep_tables|= used_tables;
      }
    }
    prev_table= table;
  }

  // 消除不必要的括号（嵌套）
  li.rewind();
  while ((table= li++))
  {
    nested_join= table->nested_join;
    if (table->sj_cond() && !in_sj)
    {
       /*
         If this is a semi-join that is not contained within another semi-join, 
         leave it intact (otherwise it is flattened)
       */
      *changelog|= SEMIJOIN;
    }
    else if (nested_join && !table->join_cond())
    {
      *changelog|= PAREN_REMOVAL;
      TABLE_LIST *tbl;
      List_iterator it(nested_join->join_list);
      while ((tbl= it++))
      {
        tbl->embedding= table->embedding;
        tbl->join_list= table->join_list;
        tbl->dep_tables|= table->dep_tables;
      }
      li.replace(nested_join->join_list);
    }
  }
.............
.............
.............
  DBUG_RETURN(false);
}