摘要:

mysql-innerJoin访问多表-优化器改变表访问顺序-分析

DDL准备:

表结构:

create table t1 (a int, b int) engine=innodb;
create table t2 (a int, b int) engine=innodb;
create table t3 (a int, b int) engine=innodb;
create table t4 (a int, b int) engine=innodb;
create table t5 (a int, b int) engine=innodb;

插入数据:

insert into t1 values (1, 3), (2, 3), (3, 4);
insert into t2 values (1, 2), (2, 4), (4, 5);
insert into t3 values (1, 2), (2, 3), (3, 4), (4, 5);
insert into t4 values (1, 3);
insert into t5 values (1, 2), (3, 4);

inner join查询:

    SELECt
        *
    FROM
        t1
    INNER JOIN t2 ON
        (t1.a = t2.a)
    INNER JOIN t3 ON
        (t1.a = t3.a)
    INNER JOIN t4 ON
        (t2.a = t4.a)
    INNER JOIN t5 ON
        (t1.a = t5.a);

left join查询:

    SELECt
        *
    FROM
        t1
    LEFT JOIN t2 ON
        (t1.a = t2.a)
    LEFT JOIN t3 ON
        (t1.a = t3.a)
    LEFT JOIN t4 ON
        (t1.a = t4.a)
    LEFT JOIN t5 ON
        (t1.a = t5.a);

核心函数:

greedy_search

static void greedy_search(JOIN *join, table_map remaining_tables, uint search_depth, uint prune_level)
{
  double record_count = 1.0;
  double read_time = 0.0;
  uint idx = join->const_tables;  // index into 'join->best_ref'
  uint best_idx;
  uint rem_size;  // cardinality of remaining_tables
  POSITION best_pos;
  JOIN_TAB *best_table;  // the next plan node to be added to the curr QEP

  DBUG_ENTER("greedy_search");

  
  rem_size = my_count_bits(remaining_tables);

  do
  {
    
    join->best_read = DBL_MAX;
    best_extension_by_limited_search(join, remaining_tables, idx, record_count, read_time, search_depth, prune_level);

    if (rem_size <= search_depth)
    {
      
      DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, join->tables, "optimal"););
      DBUG_VOID_RETURN;
    }

    
    best_pos = join->best_positions[idx];
    best_table = best_pos.table;
    
    join->positions[idx] = best_pos;

    
    best_idx = idx;
    JOIN_TAB *pos = join->best_ref[best_idx];
    while (pos && best_table != pos) pos = join->best_ref[++best_idx];
    DBUG_ASSERT((pos != NULL));  // should always find 'best_table'
    
    swap_variables(JOIN_TAB *, join->best_ref[idx], join->best_ref[best_idx]);

    
    record_count *= join->positions[idx].records_read;
    read_time += join->positions[idx].read_time;

    remaining_tables &= ~(best_table->table->map);
    --rem_size;
    ++idx;

    DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, idx, "extended"););
  } while (TRUE);
}

best_extension_by_limited_search

static void best_extension_by_limited_search(JOIN *join, table_map remaining_tables, uint idx, double record_count,
                                             double read_time, uint search_depth, uint prune_level)
{
  THD *thd = join->thd;
  if (thd->killed)  // Abort
    return;

  DBUG_ENTER("best_extension_by_limited_search");

  
  JOIN_TAB *s;
  double best_record_count = DBL_MAX;
  double best_read_time = DBL_MAX;

  DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, idx, "part_plan"););

  for (JOIN_TAB **pos = join->best_ref + idx; (s = *pos); pos++)
  {
    table_map real_table_bit = s->table->map;
    if ((remaining_tables & real_table_bit) && !(remaining_tables & s->dependent))
    {
      double current_record_count, current_read_time;

      
      best_access_path(join, s, thd, remaining_tables, idx, record_count, read_time);
      
      current_record_count = record_count * join->positions[idx].records_read;
      current_read_time = read_time + join->positions[idx].read_time;

      
      if ((current_read_time + current_record_count / (double)TIME_FOR_COMPARE) >= join->best_read)
      {
        DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, idx, "prune_by_cost"););
        continue;
      }

      
      if (prune_level == 1)
      {
        if (best_record_count > current_record_count || best_read_time > current_read_time ||
            idx == join->const_tables &&  // 's' is the first table in the QEP
                s->table == join->sort_by_table)
        {
          if (best_record_count >= current_record_count && best_read_time >= current_read_time &&
              
              (!(s->key_dependent & remaining_tables) || join->positions[idx].records_read < 2.0))
          {
            best_record_count = current_record_count;
            best_read_time = current_read_time;
          }
        }
        else
        {
          DBUG_EXECUTE("opt", print_plan(join, read_time, record_count, idx, "pruned_by_heuristic"););
          continue;
        }
      }

      if ((search_depth > 1) && (remaining_tables & ~real_table_bit))
      { 
        swap_variables(JOIN_TAB *, join->best_ref[idx], *pos);
        best_extension_by_limited_search(join, remaining_tables & ~real_table_bit, idx + 1, current_record_count,
                                         current_read_time, search_depth - 1, prune_level);
        if (thd->killed)
          DBUG_VOID_RETURN;
        swap_variables(JOIN_TAB *, join->best_ref[idx], *pos);
      }
      else
      { 
        current_read_time += current_record_count / (double)TIME_FOR_COMPARE;
        if (join->sort_by_table && join->sort_by_table != join->positions[join->const_tables].table->table)
          
          current_read_time += current_record_count;
        if ((search_depth == 1) || (current_read_time < join->best_read))
        {
          memcpy((gptr)join->best_positions, (gptr)join->positions, sizeof(POSITION) * (idx + 1));
          join->best_read = current_read_time - 0.001;
        }
        DBUG_EXECUTE("opt", print_plan(join, current_read_time, current_record_count, idx, "full_plan"););
      }
    }
  }
  DBUG_VOID_RETURN;
}

inner join改变表访问顺序分析:

调用堆栈:

(gdb) bt
#0  best_extension_by_limited_search (join=join@entry=0x7f6b9c00c250, remaining_tables=remaining_tables@entry=23, idx=idx@entry=1, record_count=record_count@entry=1, read_time=1, 
    search_depth=search_depth@entry=61, prune_level=prune_level@entry=1) at sql_select.cc:3696
#1  0x000000000056df71 in best_extension_by_limited_search (join=join@entry=0x7f6b9c00c250, remaining_tables=remaining_tables@entry=31, idx=idx@entry=0, record_count=record_count@entry=1, 
    read_time=read_time@entry=0, search_depth=search_depth@entry=62, prune_level=prune_level@entry=1) at sql_select.cc:3680
#2  0x000000000057c25e in greedy_search (prune_level=, search_depth=62, remaining_tables=31, join=0x7f6b9c00c250) at sql_select.cc:3459
#3  choose_plan (join_tables=, join=0x7f6b9c00c250) at sql_select.cc:3209
#4  make_join_statistics (join=join@entry=0x7f6b9c00c250, tables=, conds=0x7f6b9c002f18, keyuse_array=keyuse_array@entry=0x7f6b9c00d420) at sql_select.cc:1968
#5  0x000000000057f889 in JOIN::optimize (this=this@entry=0x7f6b9c00c250) at sql_select.cc:554
#6  0x000000000058343f in mysql_select (thd=thd@entry=0x17ff2a0, rref_pointer_array=rref_pointer_array@entry=0x17ff8c8, tables=0x7f6b9c00a480, wild_num=, fields=..., 
    conds=, og_num=0, order=0x0, group=0x0, having=0x0, proc_param=0x0, select_options=select_options@entry=2156153344, result=result@entry=0x7f6b9c001f60, unit=unit@entry=0x17ff320, 
    select_lex=select_lex@entry=0x17ff6a0) at sql_select.cc:1577
#7  0x0000000000583674 in handle_select (thd=thd@entry=0x17ff2a0, lex=lex@entry=0x17ff308, result=result@entry=0x7f6b9c001f60, setup_tables_done_option=setup_tables_done_option@entry=0)
    at sql_select.cc:186
#8  0x000000000054269d in mysql_execute_command (thd=thd@entry=0x17ff2a0) at sql_parse.cc:2298
#9  0x00000000005428d7 in mysql_parse (thd=thd@entry=0x17ff2a0, inBuf=, length=) at sql_parse.cc:5101
#10 0x00000000005435dc in dispatch_command (command=command@entry=COM_QUERY, thd=thd@entry=0x17ff2a0, 
    packet=packet@entry=0x181b131 "SELECTn        *n    FROMn        t1n    INNER JOIN t2 ONn        (t1.a = t2.a)n    INNER JOIN t3 ONn        (t1.a = t3.a)n    INNER JOIN t4 ONn        (t2.a = t4.a)n    INNER JOIN t5 ONn        (t1.a"..., packet_length=packet_length@entry=209) at sql_parse.cc:1579
#11 0x00000000005446f8 in do_command (thd=0x17ff2a0) at sql_parse.cc:1386
#12 0x00000000005451ea in handle_one_connection (arg=) at sql_parse.cc:1043
#13 0x00007f6bab9eeea5 in start_thread () from /lib64/libpthread.so.0
#14 0x00007f6baa8a2b0d in clone () from /lib64/libc.so.6

关键数据:

join->positions

(gdb) p join->positions
$56 = {{
    records_read = 1, 
    read_time = 1, 
    table = 0x7f6b9c00dbd8, 
    key = 0x0
  }, {
    records_read = 3, 
    read_time = 3, 
    table = 0x7f6b9c00d7a8, 
    key = 0x0
  }, {
    records_read = 4, 
    read_time = 9, 
    table = 0x7f6b9c00d9c0, 
    key = 0x0
  }, {
    records_read = 1, 
    read_time = 36, 
    table = 0x7f6b9c00dbd8, 
    key = 0x0
  }, {
    records_read = 2, 
    read_time = 36, 
    table = 0x7f6b9c00ddf0, 
    key = 0x0
  }, {

best_positions

(gdb) p join->best_positions
$57 = {{
    records_read = 3, 
    read_time = 1, 
    table = 0x7f6b9c00d590, 
    key = 0x0
  }, {
    records_read = 3, 
    read_time = 3, 
    table = 0x7f6b9c00d7a8, 
    key = 0x0
  }, {
    records_read = 4, 
    read_time = 9, 
    table = 0x7f6b9c00d9c0, 
    key = 0x0
  }, {
    records_read = 1, 
    read_time = 36, 
    table = 0x7f6b9c00dbd8, 
    key = 0x0
  }, {
    records_read = 2, 
    read_time = 36, 
    table = 0x7f6b9c00ddf0, 
    key = 0x0
  }, {