Sunday, February 17, 2013

When kill flag is checked for SELECT? Part II

In the previous part I've stopped at the moment when we entered JOIN:exec() - most checks for kill flag happen somewhere there, during query execution. We know the list of functions that checks this flag during query execution:

sub_select_cache()
evaluate_join_record()
flush_cached_records()
end_write()
end_update()
end_unique_update()
end_write_group()
remove_dup_with_compare()
remove_dup_with_hash_index()


but we do not know when exactly each of them is called. So, let me try to show what happens inside JOIN::exec (some code paths and checks are not considered for simplicity, we care about SELECT, but not EXPLAIN SELECT etc). I've included statements that change thread status and highlighted parts of code with the same thread status with different background colors and, as usual, functions that eventually may check kill flag are highlighted with bold:

JOIN::exec()
  thd_proc_info(thd, "executing");
  get_schema_tables_result()
  /* Create a tmp table if distinct or if the sort is too complicated */
  if (need_tmp)
  {
    thd_proc_info(thd, "Copying to tmp table");
    do_select()
    change_to_use_tpm_fileds()
    change_refs_to_tmp_fields()
    JOIN::make_simple_join()
    create_tmp_table()
    thd_proc_info(thd, "Creating sort index");
    create_sort_index()
    thd_proc_info(thd, "Copying to group table");
    JOIN::make_sum_func_list()
    setup_sum_funcs()
    do_select()
    end_read_record()
    change_to_use_tpm_fileds()
    if (curr_join->select_distinct && ! curr_join->group_list)
    {
      thd_proc_info(thd, "Removing duplicates");
      remove_duplicates()
    }
    calc_group_buffer()
    count_filed_types()
  } 
  /* let's ignore case of procedure entirely */
  /* simplification, few ifs ignored */
  make_group_fileds()
  init_items_ref_array()
  setup_copy_fields()
  JOIN::set_itmes_ref_array()
  JOIN::make_sum_func_list()
  prepare_sum_aggregators()
  setup_sum_funcs()
  if (curr_join->group_list || curr_join->order)
  {
     thd_proc_info(thd, "Sorting result");
     make_cond_for_table()
     create_sort_index()
  }
  send_result_set_metadata()
  thd_proc_info(thd, "Sending data");
  do_select()

As you can see, do_select() function may be called in different places and more than once if temporary table is used. Let's check what this function does:

do_select()
  /* Set up select_end */
  end_select=setup_end_select_func()
  if (join->tables)
  {
    join->join_tab[join->tables-1].next_select= end_select;
    join_tab=join->join_tab+join->const_tables;
  }
  ...
  sub_select()
  ...
  join->result->send_eof()

 So, basically do_select() determines  how to do next select step and then calls sub_select():
 
sub_select()
  if (end_of_records)
     return (*join_tab->next_select)(join,join_tab+1,end_of_records);
  ...
  rc= evaluate_join_record(join, join_tab, error);
  while (rc == NESTED_LOOP_OK)
  {
    error= info->read_record(info);
    rc= evaluate_join_record(join, join_tab, error);
  }
  if (rc == NESTED_LOOP_NO_MORE_ROWS &&
      join_tab->last_inner && !join_tab->found)
    rc= evaluate_null_complemented_join_record(join, join_tab);

Here we can call one of functions for the next select step or call evaluate_join_record() in a loop. evaluate_join_record() is one of the functions that checks kill flag before doing read work.

Most of other functions that check kill flag are called when we are done with nested loop join and already found a dataset for GROUP BY and ORDER BY processing (in a temporary table). This is how end_select function is determined:

/*
Rows produced by a join sweep may end up in a temporary table or be
sent to a client. Setup the function of the nested loop join algorithm
which handles final fully constructed and matched records.
*/

11382 Next_select_func setup_end_select_func(JOIN *join)
11383 {
11384  TABLE *table= join->tmp_table;
11385  TMP_TABLE_PARAM *tmp_tbl= &join->tmp_table_param;
11386  Next_select_func end_select;
11387
11388  /* Set up select_end */
11389  if (table)
11390  {
11391    if (table->group && tmp_tbl->sum_func_count &&
11392    !tmp_tbl->precomputed_group_by)
11393    {
11394      if (table->s->keys)
11395      {
11396        DBUG_PRINT("info",("Using end_update"));
11397        end_select=end_update;
11398      }
11399      else
11400      {
11401        DBUG_PRINT("info",("Using end_unique_update"));
11402        end_select=end_unique_update;
11403      }
11404    }
11405    else if (join->sort_and_group && !tmp_tbl->precomputed_group_by)
11406    {
11407      DBUG_PRINT("info",("Using end_write_group"));
11408      end_select=end_write_group;
11409    }
11410    else
11411    {
11412      DBUG_PRINT("info",("Using end_write"));
11413      end_select=end_write;
11414      if (tmp_tbl->precomputed_group_by)
11415      {
11416        /*
11417        A preceding call to create_tmp_table in the case when loose
11418        index scan is used guarantees that
11419        TMP_TABLE_PARAM::items_to_copy has enough space for the group
11420        by functions. It is OK here to use memcpy since we copy
11421        Item_sum pointers into an array of Item pointers.
11422        */
11423        memcpy(tmp_tbl->items_to_copy + tmp_tbl->func_count,
11424          join->sum_funcs,
11425          sizeof(Item*)*tmp_tbl->sum_func_count);
11426        tmp_tbl->items_to_copy[tmp_tbl->func_count+tmp_tbl->sum_func_count]= 0;
11427      }
11428    }
11429  }
11430  else
11431  {
11432    /*
11433    Choose method for presenting result to user. Use end_send_group
11434    if the query requires grouping (has a GROUP BY clause and/or one or
11435    more aggregate functions). Use end_send if the query should not
11436    be grouped.
11437    */
11438    if ((join->sort_and_group ||
11439      (join->procedure && join->procedure->flags & PROC_GROUP)) &&
11440      !tmp_tbl->precomputed_group_by)
11441      end_select= end_send_group;
11442    else
11443      end_select= end_send;
11444  }
11445  return end_select;
11446 } 

So, one of the functions that check for kill flag is used whenever we need to use temporary table to process GROUP BY and/or ORDER BY:

end_write()
end_update()
end_unique_update()
end_write_group()

Only 3 functions remain. Where sub_select_cache() is used (by the way, it calls sub_select() also, so may lead to more checks of kill flag in the process)?  It is used whenever you see "Using join buffer" in the EXPLAIN results for the query. This is determined at the optimization stage:

JOIN::optimize()
  make_join_readinfo()
...
 6868  for (i=join->const_tables ; i < join->tables ; i++)
 6869  {
...
 6875    tab->next_select=sub_select; /* normal select */
 6876
 6877    /*
 6878    Determine if the set is already ordered for ORDER BY, so it can
 6879    disable join cache because it will change the ordering of the results.
 6880    Code handles sort table that is at any location (not only first after
 6881    the const tables) despite the fact that it's currently prohibited.
 6882    We must disable join cache if the first non-const table alone is
 6883    ordered. If there is a temp table the ordering is done as a last
 6884    operation and doesn't prevent join cache usage.
 6885    */
...
 6896    switch (tab->type) {
...
 6915    case JT_ALL:
 6916    /*
 6917    If previous table use cache
 6918    If the incoming data set is already sorted don't use cache.
 6919    */
 6920    if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
 6921    tab->use_quick != 2 && !tab->first_inner && !ordered_set)
 6922    {
 6923      if ((options & SELECT_DESCRIBE) ||
 6924        !join_init_cache(join->thd,join->join_tab+join->const_tables,
 6925          i-join->const_tables))
 6926      {
 6927        tab[-1].next_select=sub_select_cache; /* Patch previous */
 6928      }
 6929    }
...

Read the manual for more details of join buffer usage. Basically it is used to reduce number of reads of inner tables in joins that are scanned entirely (see JT_ALL above).

Remaining two functions that check kill flag during query execution are called in remove_duplicates():

14327 static int
14328 remove_duplicates(JOIN *join, TABLE *entry,List<Item> &fields, Item *having)
14329 {
...
14360  entry->file->info(HA_STATUS_VARIABLE);
14361  if (entry->s->db_type() == heap_hton ||
14362      (!entry->s->blob_fields &&
14363       ((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->file->stats.records <
14364    thd->variables.sortbuff_size)))
14365    error=remove_dup_with_hash_index(join->thd, entry,
14366                     field_count, first_field,
14367                     reclength, having);
14368  else
14369    error=remove_dup_with_compare(join->thd, entry, first_field, offset,
14370                  having);
14371 
14372  free_blobs(first_field);
14373  DBUG_RETURN(error);
14374 }

The remove_duplicates() itself may be called in JOIN::exec() and it was highlighted in the beginning of this post.

Now the picture is almost complete, we know when kill flag is checked during query execution also. What I still miss is some nice text (or simple pseudo code that fits into one screen) for the manual to replace that oversimplified statement that we had started with. I have to think about this and present in the final Part III, so... to be continued.

No comments:

Post a Comment