home *** CD-ROM | disk | FTP | other *** search
/ Chip 2001 January / Chip_2001-01_cd1.bin / tema / mysql / mysql-3.23.28g-win-source.exe / sql / sql_select.cpp < prev    next >
C/C++ Source or Header  |  2000-11-22  |  186KB  |  6,590 lines
  1. /* Copyright (C) 2000 MySQL AB & MySQL Finland AB & TCX DataKonsult AB
  2.  
  3.    This program is free software; you can redistribute it and/or modify
  4.    it under the terms of the GNU General Public License as published by
  5.    the Free Software Foundation; either version 2 of the License, or
  6.    (at your option) any later version.
  7.  
  8.    This program is distributed in the hope that it will be useful,
  9.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.    GNU General Public License for more details.
  12.  
  13.    You should have received a copy of the GNU General Public License
  14.    along with this program; if not, write to the Free Software
  15.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  16.  
  17.  
  18. /* mysql_select and join optimization */
  19.  
  20. #ifdef __GNUC__
  21. #pragma implementation                // gcc: Class implementation
  22. #endif
  23.  
  24. #include "mysql_priv.h"
  25. #include "sql_select.h"
  26.  
  27. #include "opt_ft.h"
  28.  
  29. #include <m_ctype.h>
  30. #include <hash.h>
  31. #include <ft_global.h>
  32. #include <assert.h>
  33.  
  34. const char *join_type_str[]={ "UNKNOWN","system","const","eq_ref","ref",
  35.                   "MAYBE_REF","ALL","range","index","fulltext" };
  36.  
  37. static bool make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
  38.                         DYNAMIC_ARRAY *keyuse,List<Item_func_match> &ftfuncs);
  39. static bool update_ref_and_keys(DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,
  40.                                 uint tables,COND *conds,table_map table_map,
  41.                                 List<Item_func_match> &ftfuncs);
  42. static int sort_keyuse(KEYUSE *a,KEYUSE *b);
  43. static void set_position(JOIN *join,uint index,JOIN_TAB *table,KEYUSE *key);
  44. static void find_best_combination(JOIN *join,table_map rest_tables);
  45. static void find_best(JOIN *join,table_map rest_tables,uint index,
  46.               double record_count,double read_time);
  47. static uint cache_record_length(JOIN *join,uint index);
  48. static double prev_record_reads(JOIN *join,table_map found_ref);
  49. static bool get_best_combination(JOIN *join);
  50. static store_key *get_store_key(KEYUSE *keyuse, table_map used_tables,
  51.                 KEY_PART_INFO *key_part, char *key_buff,
  52.                 uint maybe_null);
  53. static bool make_simple_join(JOIN *join,TABLE *tmp_table);
  54. static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
  55. static void make_join_readinfo(JOIN *join,uint options);
  56. static void join_free(JOIN *join);
  57. static bool only_eq_ref_tables(JOIN *join,ORDER *order,table_map tables);
  58. static void update_depend_map(JOIN *join);
  59. static void update_depend_map(JOIN *join, ORDER *order);
  60. static ORDER *remove_const(JOIN *join,ORDER *first_order,COND *cond,
  61.                bool *simple_order);
  62. static int return_zero_rows(select_result *res,TABLE_LIST *tables,
  63.                 List<Item> &fields, bool send_row,
  64.                 uint select_options, const char *info,
  65.                 Item *having, Procedure *proc);
  66. static COND *optimize_cond(COND *conds,Item::cond_result *cond_value);
  67. static COND *remove_eq_conds(COND *cond,Item::cond_result *cond_value);
  68. static bool const_expression_in_where(COND *conds,Item *item, Item **comp_item);
  69. static bool open_tmp_table(TABLE *table);
  70. static bool create_myisam_tmp_table(TABLE *table,TMP_TABLE_PARAM *param,
  71.                     uint options);
  72. static int do_select(JOIN *join,List<Item> *fields,TABLE *tmp_table,
  73.              Procedure *proc);
  74. static int sub_select_cache(JOIN *join,JOIN_TAB *join_tab,bool end_of_records);
  75. static int sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records);
  76. static int flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skipp_last);
  77. static int end_send(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
  78. static int end_send_group(JOIN *join, JOIN_TAB *join_tab,bool end_of_records);
  79. static int end_write(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
  80. static int end_update(JOIN *join, JOIN_TAB *join_tab, bool end_of_records);
  81. static int end_unique_update(JOIN *join,JOIN_TAB *join_tab,
  82.                  bool end_of_records);
  83. static int end_write_group(JOIN *join, JOIN_TAB *join_tab,
  84.                bool end_of_records);
  85. static int test_if_group_changed(List<Item_buff> &list);
  86. static int join_read_const_tables(JOIN *join);
  87. static int join_read_system(JOIN_TAB *tab);
  88. static int join_read_const(JOIN_TAB *tab);
  89. static int join_read_key(JOIN_TAB *tab);
  90. static int join_read_always_key(JOIN_TAB *tab);
  91. static int join_no_more_records(READ_RECORD *info);
  92. static int join_read_next(READ_RECORD *info);
  93. static int join_init_quick_read_record(JOIN_TAB *tab);
  94. static int test_if_quick_select(JOIN_TAB *tab);
  95. static int join_init_read_record(JOIN_TAB *tab);
  96. static int join_init_read_first_with_key(JOIN_TAB *tab);
  97. static int join_init_read_next_with_key(READ_RECORD *info);
  98. static int join_init_read_last_with_key(JOIN_TAB *tab);
  99. static int join_init_read_prev_with_key(READ_RECORD *info);
  100. static int join_ft_read_first(JOIN_TAB *tab);
  101. static int join_ft_read_next(READ_RECORD *info);
  102. static COND *make_cond_for_table(COND *cond,table_map table,
  103.                  table_map used_table);
  104. static Item* part_of_refkey(TABLE *form,Field *field);
  105. static uint find_shortest_key(TABLE *table, key_map usable_keys);
  106. static bool test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,
  107.                     ha_rows select_limit);
  108. static int create_sort_index(JOIN_TAB *tab,ORDER *order,ha_rows select_limit);
  109. static int remove_duplicates(JOIN *join,TABLE *entry,List<Item> &fields);
  110. static int remove_dup_with_compare(THD *thd, TABLE *entry, Field **field,
  111.                    ulong offset);
  112. static int remove_dup_with_hash_index(THD *thd, TABLE *table,
  113.                       uint field_count, Field **first_field,
  114.                       ulong key_length);
  115. static int join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count);
  116. static ulong used_blob_length(CACHE_FIELD **ptr);
  117. static bool store_record_in_cache(JOIN_CACHE *cache);
  118. static void reset_cache(JOIN_CACHE *cache);
  119. static void read_cached_record(JOIN_TAB *tab);
  120. static bool cmp_buffer_with_ref(JOIN_TAB *tab);
  121. static int setup_group(THD *thd,TABLE_LIST *tables,List<Item> &fields,
  122.                List<Item> &all_fields, ORDER *order, bool *hidden);
  123. static bool setup_new_fields(THD *thd,TABLE_LIST *tables,List<Item> &fields,
  124.                  List<Item> &all_fields,ORDER *new_order);
  125. static ORDER *create_distinct_group(ORDER *order, List<Item> &fields);
  126. static bool test_if_subpart(ORDER *a,ORDER *b);
  127. static TABLE *get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables);
  128. static void calc_group_buffer(JOIN *join,ORDER *group);
  129. static bool alloc_group_fields(JOIN *join,ORDER *group);
  130. static bool make_sum_func_list(JOIN *join,List<Item> &fields);
  131. static bool change_to_use_tmp_fields(List<Item> &func);
  132. static bool change_refs_to_tmp_fields(THD *thd, List<Item> &func);
  133. static void init_tmptable_sum_functions(Item_sum **func);
  134. static void update_tmptable_sum_func(Item_sum **func,TABLE *tmp_table);
  135. static void copy_sum_funcs(Item_sum **func_ptr);
  136. static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab);
  137. static void init_sum_functions(Item_sum **func);
  138. static bool update_sum_func(Item_sum **func);
  139. static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
  140.                 bool distinct);
  141. static void describe_info(const char *info);
  142.  
  143. /*****************************************************************************
  144. ** check fields, find best join, do the select and output fields.
  145. ** mysql_select assumes that all tables are allready opened
  146. *****************************************************************************/
  147.  
  148. int
  149. mysql_select(THD *thd,TABLE_LIST *tables,List<Item> &fields,COND *conds,
  150.              List<Item_func_match> &ftfuncs,
  151.          ORDER *order, ORDER *group,Item *having,ORDER *proc_param,
  152.          uint select_options,select_result *result)
  153. {
  154.   TABLE        *tmp_table;
  155.   int        error,tmp;
  156.   bool        need_tmp,hidden_group_fields;
  157.   bool        simple_order,simple_group,no_order;
  158.   Item::cond_result cond_value;
  159.   SQL_SELECT    *select;
  160.   DYNAMIC_ARRAY keyuse;
  161.   JOIN        join;
  162.   Procedure    *procedure;
  163.   List<Item>    all_fields(fields);
  164.   bool        select_distinct;
  165.   DBUG_ENTER("mysql_select");
  166.  
  167.   /* Check that all tables, fields, conds and order are ok */
  168.  
  169.   select_distinct=test(select_options & SELECT_DISTINCT);
  170.   tmp_table=0;
  171.   select=0;
  172.   no_order=0;
  173.   bzero((char*) &keyuse,sizeof(keyuse));
  174.   thd->proc_info="init";
  175.   thd->used_tables=0;                // Updated by setup_fields
  176.  
  177.   if (setup_fields(thd,tables,fields,1,&all_fields) ||
  178.       setup_conds(thd,tables,&conds) ||
  179.       setup_order(thd,tables,fields,all_fields,order) ||
  180.       setup_group(thd,tables,fields,all_fields,group,&hidden_group_fields) ||
  181.       setup_ftfuncs(thd,tables,ftfuncs))
  182.     DBUG_RETURN(-1);                /* purecov: inspected */
  183.  
  184.   if (having)
  185.   {
  186.     thd->where="having clause";
  187.     thd->allow_sum_func=1;
  188.     if (having->fix_fields(thd,tables) || thd->fatal_error)
  189.       DBUG_RETURN(-1);                /* purecov: inspected */
  190.     if (having->with_sum_func)
  191.       having->split_sum_func(all_fields);
  192.   }
  193.   /*
  194.     Check if one one uses a not constant column with group functions
  195.     and no GROUP BY.
  196.     TODO:  Add check of calculation of GROUP functions and fields:
  197.        SELECT COUNT(*)+table.col1 from table1;
  198.     */
  199.   join.table=0;
  200.   join.tables=0;
  201.   {
  202.     if (!group)
  203.     {
  204.       uint flag=0;
  205.       List_iterator<Item> it(fields);
  206.       Item *item;
  207.       while ((item= it++))
  208.       {
  209.     if (item->with_sum_func)
  210.       flag|=1;
  211.     else if (!item->const_item())
  212.       flag|=2;
  213.       }
  214.       if (flag == 3)
  215.       {
  216.     my_error(ER_MIX_OF_GROUP_FUNC_AND_FIELDS,MYF(0));
  217.     DBUG_RETURN(-1);
  218.       }
  219.     }
  220.     TABLE_LIST *table;
  221.     for (table=tables ; table ; table=table->next)
  222.       join.tables++;
  223.   }
  224.   procedure=setup_procedure(thd,proc_param,result,fields,&error);
  225.   if (error)
  226.     DBUG_RETURN(-1);                /* purecov: inspected */
  227.   if (procedure)
  228.   {
  229.     if (setup_new_fields(thd,tables,fields,all_fields,procedure->param_fields))
  230.     {                        /* purecov: inspected */
  231.       delete procedure;                /* purecov: inspected */
  232.       DBUG_RETURN(-1);                /* purecov: inspected */
  233.     }
  234.     if (procedure->group)
  235.     {
  236.       if (!test_if_subpart(procedure->group,group))
  237.       {                        /* purecov: inspected */
  238.     my_message(0,"Can't handle procedures with differents groups yet",
  239.            MYF(0));            /* purecov: inspected */
  240.     delete procedure;            /* purecov: inspected */
  241.     DBUG_RETURN(-1);            /* purecov: inspected */
  242.       }
  243.     }
  244. #ifdef NOT_NEEDED
  245.     else if (!group && procedure->flags & PROC_GROUP)
  246.     {
  247.       my_message(0,"Select must have a group with this procedure",MYF(0));
  248.       delete procedure;
  249.       DBUG_RETURN(-1);
  250.     }
  251. #endif
  252.     if (order && (procedure->flags & PROC_NO_SORT))
  253.     { /* purecov: inspected */
  254.       my_message(0,"Can't use order with this procedure",MYF(0)); /* purecov: inspected */
  255.       delete procedure; /* purecov: inspected */
  256.       DBUG_RETURN(-1); /* purecov: inspected */
  257.     }
  258.   }
  259.  
  260.   /* Init join struct */
  261.   join.thd=thd;
  262.   join.lock=thd->lock;
  263.   join.join_tab=0;
  264.   join.tmp_table_param.copy_field=0;
  265.   join.sum_funcs=0;
  266.   join.send_records=join.found_records=0;
  267.   join.tmp_table_param.end_write_records= HA_POS_ERROR;
  268.   join.first_record=join.sort_and_group=0;
  269.   join.select_options=select_options;
  270.   join.result=result;
  271.   count_field_types(&join.tmp_table_param,all_fields);
  272.   join.const_tables=0;
  273.   join.having=0;
  274.   join.group= group != 0;
  275.  
  276. #ifdef RESTRICTED_GROUP
  277.   if (join.sum_func_count && !group && (join.func_count || join.field_count))
  278.   {
  279.     my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT));
  280.     delete procedure;
  281.     DBUG_RETURN(-1);
  282.   }
  283. #endif
  284.   if (!procedure && result->prepare(fields))
  285.   {                        /* purecov: inspected */
  286.     DBUG_RETURN(-1);                /* purecov: inspected */
  287.   }
  288.  
  289. #ifdef HAVE_REF_TO_FIELDS            // Not done yet
  290.   /* Add HAVING to WHERE if possible */
  291.   if (having && !group && ! join.sum_func_count)
  292.   {
  293.     if (!conds)
  294.     {
  295.       conds=having;
  296.       having=0;
  297.     }
  298.     else if ((conds=new Item_cond_and(conds,having)))
  299.     {
  300.       conds->fix_fields(thd,tables);
  301.       conds->change_ref_to_fields(thd,tables);
  302.       having=0;
  303.     }
  304.   }
  305. #endif
  306.  
  307.   conds=optimize_cond(conds,&cond_value);
  308.   if (thd->fatal_error)                // Out of memory
  309.   {
  310.     delete procedure;
  311.     DBUG_RETURN(0);
  312.   }
  313.   if (cond_value == Item::COND_FALSE || !thd->select_limit)
  314.   {                    /* Impossible cond */
  315.     error=return_zero_rows(result, tables, fields,
  316.                join.tmp_table_param.sum_func_count != 0 && !group,
  317.                select_options,"Impossible WHERE",join.having,
  318.                procedure);
  319.     delete procedure;
  320.     DBUG_RETURN(error);
  321.   }
  322.  
  323.   /* Optimize count(*), min() and max() */
  324.   if (tables && join.tmp_table_param.sum_func_count && ! group)
  325.   {
  326.     int res;
  327.     if ((res=opt_sum_query(tables, all_fields, conds)))
  328.     {
  329.       if (res < 0)
  330.       {
  331.     error=return_zero_rows(result, tables, fields, !group,
  332.                    select_options,"No matching min/max row",
  333.                    join.having,procedure);
  334.     delete procedure;
  335.     DBUG_RETURN(error);
  336.       }
  337.       if (select_options & SELECT_DESCRIBE)
  338.       {
  339.     describe_info("Select tables optimized away");
  340.     delete procedure;
  341.     DBUG_RETURN(0);
  342.       }
  343.       tables=0;                    // All tables resolved
  344.     }
  345.   }
  346.   if (!tables)
  347.   {                        // Only test of functions
  348.     error=0;
  349.     if (select_options & SELECT_DESCRIBE)
  350.       describe_info("No tables used");
  351.     else
  352.     {
  353.       result->send_fields(fields,1);
  354.       if (!having || having->val_int())
  355.       {
  356.     if (result->send_data(fields))
  357.     {
  358.       result->send_error(0,NullS);        /* purecov: inspected */
  359.       error=1;
  360.     }
  361.     else
  362.       error=(int) result->send_eof();
  363.       }
  364.       else
  365.     error=(int) result->send_eof();
  366.     }
  367.     delete procedure;
  368.     DBUG_RETURN(0);
  369.   }
  370.  
  371.   error = -1;
  372.   join.sort_by_table=get_sort_by_table(order,group,tables);
  373.  
  374.   /* Calculate how to do the join */
  375.   thd->proc_info="statistics";
  376.   if (make_join_statistics(&join,tables,conds,&keyuse,ftfuncs) ||
  377.       thd->fatal_error)
  378.     goto err;
  379.   thd->proc_info="preparing";
  380.   if ((tmp=join_read_const_tables(&join)) > 0)
  381.     goto err;
  382.   if (tmp && !(select_options & SELECT_DESCRIBE))
  383.   {
  384.     error=return_zero_rows(result,tables,fields,
  385.                join.tmp_table_param.sum_func_count != 0 &&
  386.                !group,0,"",join.having,procedure);
  387.     goto err;
  388.   }
  389.   if (!(thd->options & OPTION_BIG_SELECTS) &&
  390.       join.best_read > (double) thd->max_join_size &&
  391.       !(select_options & SELECT_DESCRIBE))
  392.   {                        /* purecov: inspected */
  393.     result->send_error(ER_TOO_BIG_SELECT,ER(ER_TOO_BIG_SELECT)); /* purecov: inspected */
  394.     error= 1;                    /* purecov: inspected */
  395.     goto err;                    /* purecov: inspected */
  396.   }
  397.   if (join.const_tables && !thd->locked_tables)
  398.     mysql_unlock_some_tables(thd, join.table,join.const_tables);
  399.   if (!conds && join.outer_join)
  400.   {
  401.     /* Handle the case where we have an OUTER JOIN without a WHERE */
  402.     conds=new Item_int((longlong) 1,1);    // Always true
  403.   }
  404.   select=make_select(*join.table, join.const_table_map,
  405.              join.const_table_map,conds,&error);
  406.   if (error)
  407.   { /* purecov: inspected */
  408.     error= -1; /* purecov: inspected */
  409.     goto err; /* purecov: inspected */
  410.   }
  411.   if (make_join_select(&join,select,conds))
  412.   {
  413.     error=return_zero_rows(result,tables,fields,
  414.                join.tmp_table_param.sum_func_count != 0 && !group,
  415.                select_options,
  416.                "Impossible WHERE noticed after reading const tables",
  417.                join.having,procedure);
  418.     goto err;
  419.   }
  420.  
  421.   error= -1;                    /* if goto err */
  422.  
  423.   /* Optimize distinct away if possible */
  424.   order=remove_const(&join,order,conds,&simple_order);
  425.   if (group || join.tmp_table_param.sum_func_count)
  426.   {
  427.     if (! hidden_group_fields)
  428.       select_distinct=0;
  429.   }
  430.   else if (select_distinct && join.tables - join.const_tables == 1 &&
  431.        (order || thd->select_limit == HA_POS_ERROR))
  432.   {
  433.     if ((group=create_distinct_group(order,fields)))
  434.     {
  435.       select_distinct=0;
  436.       no_order= !order;
  437.       join.group=1;                // For end_write_group
  438.     }
  439.     else if (thd->fatal_error)            // End of memory
  440.       goto err;
  441.   }
  442.   group=remove_const(&join,group,conds,&simple_group);
  443.   if (!group && join.group)
  444.   {
  445.     order=0;                    // The output has only one row
  446.     simple_order=1;
  447.   }
  448.  
  449.   calc_group_buffer(&join,group);
  450.   join.send_group_parts=join.tmp_table_param.group_parts; /* Save org parts */
  451.   if (procedure && procedure->group)
  452.   {
  453.     group=procedure->group=remove_const(&join,procedure->group,conds,
  454.                     &simple_group);
  455.     calc_group_buffer(&join,group);
  456.   }
  457.  
  458.   if (test_if_subpart(group,order) ||
  459.       (!group && join.tmp_table_param.sum_func_count))
  460.     order=0;
  461.  
  462.   // Can't use sort on head table if using cache
  463.   if (join.full_join)
  464.   {
  465.     if (group)
  466.       simple_group=0;
  467.     if (order)
  468.       simple_order=0;
  469.   }
  470.  
  471.   need_tmp= (join.const_tables != join.tables &&
  472.          ((select_distinct || !simple_order || !simple_group) ||
  473.           (group && order) ||
  474.           test(select_options & OPTION_BUFFER_RESULT)));
  475.  
  476.   make_join_readinfo(&join,
  477.              (select_options & SELECT_DESCRIBE) | SELECT_USE_CACHE);
  478.   DBUG_EXECUTE("info",TEST_join(&join););
  479.   /*
  480.     Because filesort always does a full table scan or a quick range scan
  481.     we must add the removed reference to the select for the table.
  482.     We only need to do this when we have a simple_order or simple_group
  483.     as in other cases the join is done before the sort.
  484.     */
  485.   if ((order || group) && join.join_tab[join.const_tables].type != JT_ALL &&
  486.       join.join_tab[join.const_tables].type != JT_FT &&
  487.       (order && simple_order || group && simple_group))
  488.   {
  489.     if (add_ref_to_table_cond(thd,&join.join_tab[join.const_tables]))
  490.       goto err;
  491.   }
  492.  
  493.   if (!(select_options & SELECT_BIG_RESULT) &&
  494.       ((group && join.const_tables != join.tables &&
  495.     !test_if_skip_sort_order(&join.join_tab[join.const_tables], group,
  496.                  HA_POS_ERROR)) ||
  497.        select_distinct) &&
  498.       join.tmp_table_param.quick_group && !procedure)
  499.   {
  500.     need_tmp=1; simple_order=simple_group=0;    // Force tmp table without sort
  501.   }
  502.  
  503.   if (select_options & SELECT_DESCRIBE)
  504.   {
  505.     if (!order && !no_order)
  506.       order=group;
  507.     if (order &&
  508.     (join.const_tables == join.tables ||
  509.      test_if_skip_sort_order(&join.join_tab[join.const_tables], order,
  510.                  (having || group ||
  511.                   join.const_tables != join.tables - 1) ?
  512.                  HA_POS_ERROR : thd->select_limit)))
  513.       order=0;
  514.     select_describe(&join,need_tmp,
  515.             (order != 0 &&
  516.              (!need_tmp || order != group || simple_group)),
  517.             select_distinct);
  518.     error=0;
  519.     goto err;
  520.   }
  521.  
  522.   /* Perform FULLTEXT search before all regular searches */
  523.   if (ftfuncs.elements)
  524.   {
  525.     List_iterator<Item_func_match> li(ftfuncs);
  526.     Item_func_match *ifm;
  527.     DBUG_PRINT("info",("Performing FULLTEXT search"));
  528.     thd->proc_info="FULLTEXT searching";
  529.  
  530.     while ((ifm=li++))
  531.     {
  532.       ifm->init_search(test(order));
  533.     }
  534.   }
  535.   /* Create a tmp table if distinct or if the sort is too complicated */
  536.   if (need_tmp)
  537.   {
  538.     DBUG_PRINT("info",("Creating tmp table"));
  539.     thd->proc_info="Creating tmp table";
  540.  
  541.     if (!(tmp_table =
  542.       create_tmp_table(thd,&join.tmp_table_param,all_fields,
  543.                ((!simple_group && !procedure &&
  544.                  !(test_flags & TEST_NO_KEY_GROUP)) ?
  545.                 group : (ORDER*) 0),
  546.                group ? 0 : select_distinct,
  547.                group && simple_group,
  548.                order == 0,
  549.                join.select_options)))
  550.       goto err;                    /* purecov: inspected */
  551.  
  552.     if (having && (join.sort_and_group || (tmp_table->distinct && !group)))
  553.       join.having=having;
  554.  
  555.     /* if group or order on first table, sort first */
  556.     if (group && simple_group)
  557.     {
  558.       DBUG_PRINT("info",("Sorting for group"));
  559.       thd->proc_info="Sorting for group";
  560.       if (create_sort_index(&join.join_tab[join.const_tables],group,
  561.                 HA_POS_ERROR) ||
  562.       make_sum_func_list(&join,all_fields) ||
  563.       alloc_group_fields(&join,group))
  564.     goto err;
  565.       group=0;
  566.     }
  567.     else
  568.     {
  569.       if (make_sum_func_list(&join,all_fields))
  570.     goto err;
  571.       if (!group && ! tmp_table->distinct && order && simple_order)
  572.       {
  573.     DBUG_PRINT("info",("Sorting for order"));
  574.     thd->proc_info="Sorting for order";
  575.     if (create_sort_index(&join.join_tab[join.const_tables],order,
  576.                   HA_POS_ERROR))
  577.       goto err;                /* purecov: inspected */
  578.     order=0;
  579.       }
  580.     }
  581.  
  582.     /*
  583.       Optimize distinct when used on some of the tables
  584.       SELECT DISTINCT t1.a FROM t1,t2 WHERE t1.b=t2.b
  585.       In this case we can stop scanning t2 when we have found one t1.a
  586.     */
  587.  
  588.     if (tmp_table->distinct)
  589.     {
  590.       table_map used_tables= thd->used_tables;
  591.       JOIN_TAB *join_tab=join.join_tab+join.tables-1;
  592.       do
  593.       {
  594.     if (used_tables & join_tab->table->map)
  595.       break;
  596.     join_tab->not_used_in_distinct=1;
  597.       } while (join_tab-- != join.join_tab);
  598.     }
  599.  
  600.     /* Copy data to the temporary table */
  601.     thd->proc_info="Copying to tmp table";
  602.     if (do_select(&join,(List<Item> *) 0,tmp_table,0))
  603.       goto err;                    /* purecov: inspected */
  604.     if (join.having)
  605.       join.having=having=0;            // Allready done
  606.  
  607.     /* Change sum_fields reference to calculated fields in tmp_table */
  608.     if (join.sort_and_group || tmp_table->group)
  609.     {
  610.       if (change_to_use_tmp_fields(all_fields))
  611.     goto err;
  612.       join.tmp_table_param.field_count+=join.tmp_table_param.sum_func_count+
  613.     join.tmp_table_param.func_count;
  614.       join.tmp_table_param.sum_func_count=join.tmp_table_param.func_count=0;
  615.     }
  616.     else
  617.     {
  618.       if (change_refs_to_tmp_fields(thd,all_fields))
  619.     goto err;
  620.       join.tmp_table_param.field_count+=join.tmp_table_param.func_count;
  621.       join.tmp_table_param.func_count=0;
  622.     }
  623.     if (procedure)
  624.       procedure->update_refs();
  625.     if (tmp_table->group)
  626.     {                        // Already grouped
  627.       if (!order && !no_order)
  628.     order=group;                /* order by group */
  629.       group=0;
  630.     }
  631.  
  632.     /*
  633.     ** If we have different sort & group then we must sort the data by group
  634.     ** and copy it to another tmp table
  635.     */
  636.  
  637.     if (group && (!test_if_subpart(group,order) || select_distinct))
  638.     {                    /* Must copy to another table */
  639.       TABLE *tmp_table2;
  640.       DBUG_PRINT("info",("Creating group table"));
  641.  
  642.       /* Free first data from old join */
  643.       join_free(&join);
  644.       if (make_simple_join(&join,tmp_table))
  645.     goto err;
  646.       calc_group_buffer(&join,group);
  647.       count_field_types(&join.tmp_table_param,all_fields);
  648.  
  649.       /* group data to new table */
  650.       if (!(tmp_table2 = create_tmp_table(thd,&join.tmp_table_param,all_fields,
  651.                       (ORDER*) 0, 0 , 1, 0,
  652.                       join.select_options)))
  653.     goto err;                /* purecov: inspected */
  654.       if (group)
  655.       {
  656.     thd->proc_info="Creating sort index";
  657.     if (create_sort_index(join.join_tab,group,HA_POS_ERROR) ||
  658.         alloc_group_fields(&join,group))
  659.     {
  660.       free_tmp_table(thd,tmp_table2); /* purecov: inspected */
  661.       goto err;                /* purecov: inspected */
  662.     }
  663.     group=0;
  664.       }
  665.       thd->proc_info="Copying to group table";
  666.       if (make_sum_func_list(&join,all_fields) ||
  667.       do_select(&join,(List<Item> *) 0,tmp_table2,0))
  668.       {
  669.     free_tmp_table(thd,tmp_table2);
  670.     goto err;                /* purecov: inspected */
  671.       }
  672.       end_read_record(&join.join_tab->read_record);
  673.       free_tmp_table(thd,tmp_table);
  674.       join.const_tables=join.tables;        // Mark free for join_free()
  675.       tmp_table=tmp_table2;
  676.       join.join_tab[0].table=0;            // Table is freed
  677.  
  678.       if (change_to_use_tmp_fields(all_fields)) // No sum funcs anymore
  679.     goto err;
  680.       join.tmp_table_param.field_count+=join.tmp_table_param.sum_func_count;
  681.       join.tmp_table_param.sum_func_count=0;
  682.     }
  683.  
  684.     if (tmp_table->distinct)
  685.       select_distinct=0;            /* Each row is uniq */
  686.  
  687.     join_free(&join);                /* Free quick selects */
  688.     if (select_distinct && ! group)
  689.     {
  690.       thd->proc_info="Removing duplicates";
  691.       if (remove_duplicates(&join,tmp_table,fields))
  692.     goto err; /* purecov: inspected */
  693.       select_distinct=0;
  694.     }
  695.     tmp_table->reginfo.lock_type=TL_UNLOCK;
  696.     if (make_simple_join(&join,tmp_table))
  697.       goto err;
  698.     calc_group_buffer(&join,group);
  699.     count_field_types(&join.tmp_table_param,all_fields);
  700.   }
  701.   if (procedure)
  702.   {
  703.     if (procedure->change_columns(fields) ||
  704.     result->prepare(fields))
  705.       goto err;
  706.     count_field_types(&join.tmp_table_param,all_fields);
  707.   }
  708.   if (join.group || join.tmp_table_param.sum_func_count ||
  709.       (procedure && (procedure->flags & PROC_GROUP)))
  710.   {
  711.     alloc_group_fields(&join,group);
  712.     setup_copy_fields(&join.tmp_table_param,all_fields);
  713.     if (make_sum_func_list(&join,all_fields) || thd->fatal_error)
  714.       goto err; /* purecov: inspected */
  715.   }
  716.   if (group || order)
  717.   {
  718.     DBUG_PRINT("info",("Sorting for send_fields"));
  719.     thd->proc_info="Sorting result";
  720.     /* If we have already done the group, add HAVING to sorted table */
  721.     if (having && ! group && ! join.sort_and_group)
  722.     {
  723.       having->update_used_tables();    // Some tables may have been const
  724.       JOIN_TAB *table=&join.join_tab[join.const_tables];
  725.       table_map used_tables= join.const_table_map | table->table->map;
  726.  
  727.       Item* sort_table_cond=make_cond_for_table(having,used_tables,used_tables);
  728.       if (sort_table_cond)
  729.       {
  730.     if (!table->select)
  731.       if (!(table->select=new SQL_SELECT))
  732.         goto err;
  733.     if (!table->select->cond)
  734.       table->select->cond=sort_table_cond;
  735.     else                    // This should never happen
  736.       if (!(table->select->cond=new Item_cond_and(table->select->cond,
  737.                               sort_table_cond)))
  738.         goto err;
  739.     table->select_cond=table->select->cond;
  740.     DBUG_EXECUTE("where",print_where(table->select->cond,
  741.                      "select and having"););
  742.     having=make_cond_for_table(having,~ (table_map) 0,~used_tables);
  743.     DBUG_EXECUTE("where",print_where(conds,"having after sort"););
  744.       }
  745.     }
  746.     if (create_sort_index(&join.join_tab[join.const_tables],
  747.               group ? group : order,
  748.               (having || group ||
  749.                join.const_tables != join.tables - 1) ?
  750.               HA_POS_ERROR : thd->select_limit))
  751.       goto err; /* purecov: inspected */
  752.   }
  753.   join.having=having;                // Actually a parameter
  754.   thd->proc_info="Sending data";
  755.   error=do_select(&join,&fields,NULL,procedure);
  756.  
  757. err:
  758.   thd->proc_info="end";
  759.   join.lock=0;                    // It's faster to unlock later
  760.   join_free(&join);
  761.   thd->proc_info="end2";            // QQ
  762.   if (tmp_table)
  763.     free_tmp_table(thd,tmp_table);
  764.   thd->proc_info="end3";            // QQ
  765.   delete select;
  766.   delete_dynamic(&keyuse);
  767.   delete procedure;
  768.   thd->proc_info="end4";            // QQ
  769.   DBUG_RETURN(error);
  770. }
  771.  
  772. /*****************************************************************************
  773. **    Create JOIN_TABS, make a guess about the table types,
  774. **    Approximate how many records will be used in each table
  775. *****************************************************************************/
  776.  
  777. static ha_rows get_quick_record_count(SQL_SELECT *select,TABLE *table,
  778.                       key_map keys)
  779. {
  780.   int error;
  781.   DBUG_ENTER("get_quick_record_count");
  782.   if (select)
  783.   {
  784.     select->head=table;
  785.     table->reginfo.impossible_range=0;
  786.     if ((error=select->test_quick_select(keys,(table_map) 0,HA_POS_ERROR))
  787.     == 1)
  788.       DBUG_RETURN(select->quick->records);
  789.     if (error == -1)
  790.     {
  791.       table->reginfo.impossible_range=1;
  792.       DBUG_RETURN(0);
  793.     }
  794.     DBUG_PRINT("warning",("Couldn't use record count on const keypart"));
  795.   }
  796.   DBUG_RETURN(HA_POS_ERROR);            /* This shouldn't happend */
  797. }
  798.  
  799.  
  800. static bool
  801. make_join_statistics(JOIN *join,TABLE_LIST *tables,COND *conds,
  802.              DYNAMIC_ARRAY *keyuse_array,
  803.              List<Item_func_match> &ftfuncs)
  804. {
  805.   int error;
  806.   uint i,table_count,const_count,found_ref,refs,key,const_ref,eq_part;
  807.   table_map const_table_map,all_table_map;
  808.   TABLE **table_vector;
  809.   JOIN_TAB *stat,*stat_end,*s,**stat_ref;
  810.   SQL_SELECT *select;
  811.   KEYUSE *keyuse,*start_keyuse;
  812.   table_map outer_join=0;
  813.   JOIN_TAB *stat_vector[MAX_TABLES+1];
  814.   DBUG_ENTER("make_join_statistics");
  815.  
  816.   table_count=join->tables;
  817.   stat=(JOIN_TAB*) join->thd->calloc(sizeof(JOIN_TAB)*table_count);
  818.   stat_ref=(JOIN_TAB**) join->thd->alloc(sizeof(JOIN_TAB*)*MAX_TABLES);
  819.   table_vector=(TABLE**) join->thd->alloc(sizeof(TABLE**)*(table_count*2));
  820.   if (!stat || !stat_ref || !table_vector)
  821.     DBUG_RETURN(1);                // Eom /* purecov: inspected */
  822.   select=0;
  823.  
  824.   join->best_ref=stat_vector;
  825.  
  826.   stat_end=stat+table_count;
  827.   const_table_map=all_table_map=0;
  828.   const_count=0;
  829.  
  830.   for (s=stat,i=0 ; tables ; s++,tables=tables->next,i++)
  831.   {
  832.     TABLE *table;
  833.     stat_vector[i]=s;
  834.     table_vector[i]=s->table=table=tables->table;
  835.     table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);// record count
  836.     table->quick_keys=0;
  837.     table->reginfo.join_tab=s;
  838.     table->reginfo.not_exists_optimize=0;
  839.     bzero((char*) table->const_key_parts, sizeof(key_part_map)*table->keys);
  840.     all_table_map|= table->map;
  841.     if ((s->on_expr=tables->on_expr))
  842.     {
  843.       // table->maybe_null=table->outer_join=1;    // Mark for send fields
  844.       if (!table->file->records)
  845.       {                        // Empty table
  846.     s->key_dependent=s->dependent=0;
  847.     s->type=JT_SYSTEM;
  848.     const_table_map|=table->map;
  849.     set_position(join,const_count++,s,(KEYUSE*) 0);
  850.     continue;
  851.       }
  852.       s->key_dependent=s->dependent=
  853.     s->on_expr->used_tables() & ~(table->map);
  854.       if (table->outer_join & JOIN_TYPE_LEFT)
  855.     s->dependent|=stat_vector[i-1]->dependent | table_vector[i-1]->map;
  856.       if (tables->outer_join & JOIN_TYPE_RIGHT)
  857.     s->dependent|=tables->next->table->map;
  858.       outer_join|=table->map;
  859.       continue;
  860.     }
  861.     if (tables->straight)            // We don't have to move this
  862.       s->dependent= table_vector[i-1]->map | stat_vector[i-1]->dependent;
  863.     else
  864.       s->dependent=(table_map) 0;
  865.     s->key_dependent=(table_map) 0;
  866.     if ((table->system || table->file->records <= 1L) && ! s->dependent)
  867.     {
  868.       s->type=JT_SYSTEM;
  869.       const_table_map|=table->map;
  870.       set_position(join,const_count++,s,(KEYUSE*) 0);
  871.     }
  872.   }
  873.   stat_vector[i]=0;
  874.   join->outer_join=outer_join;
  875.  
  876.   /*
  877.   ** If outer join: Re-arrange tables in stat_vector so that outer join
  878.   ** tables are after all tables it is dependent of.
  879.   ** For example: SELECT * from A LEFT JOIN B ON B.c=C.c, C WHERE A.C=C.C
  880.   ** Will shift table B after table C.
  881.   */
  882.   if (outer_join)
  883.   {
  884.     table_map used_tables=0L;
  885.     for (i=0 ; i < join->tables-1 ; i++)
  886.     {
  887.       if (stat_vector[i]->dependent & ~used_tables)
  888.       {
  889.     JOIN_TAB *save= stat_vector[i];
  890.     uint j;
  891.     for (j=i+1;
  892.          j < join->tables && stat_vector[j]->dependent & ~used_tables;
  893.          j++)
  894.     {
  895.       JOIN_TAB *tmp=stat_vector[j];        // Move element up
  896.       stat_vector[j]=save;
  897.       save=tmp;
  898.     }
  899.     if (j == join->tables)
  900.     {
  901.       join->tables=0;            // Don't use join->table
  902.       my_error(ER_WRONG_OUTER_JOIN,MYF(0));
  903.       DBUG_RETURN(1);
  904.     }
  905.     stat_vector[i]=stat_vector[j];
  906.     stat_vector[j]=save;
  907.       }
  908.       used_tables|= stat_vector[i]->table->map;
  909.     }
  910.   }
  911.  
  912.   if (conds || outer_join)
  913.     if (update_ref_and_keys(keyuse_array,stat,join->tables,
  914.                             conds,~outer_join,ftfuncs))
  915.       DBUG_RETURN(1);
  916.  
  917.   /* loop until no more const tables are found */
  918.   do
  919.   {
  920.     found_ref=0;
  921.     for (JOIN_TAB **pos=stat_vector+const_count; (s= *pos) ; pos++)
  922.     {
  923.       if (s->dependent)                // If dependent on some table
  924.       {
  925.     if (s->dependent & ~(const_table_map)) // All dep. must be constants
  926.       continue;
  927.     if (s->table->file->records <= 1L)
  928.     {                    // system table
  929.       s->type=JT_SYSTEM;
  930.       const_table_map|=s->table->map;
  931.       set_position(join,const_count++,s,(KEYUSE*) 0);
  932.       continue;
  933.     }
  934.       }
  935.       /* check if table can be read by key or table only uses const refs */
  936.       if ((keyuse=s->keyuse))
  937.       {
  938.     TABLE *table=s->table;
  939.     s->type= JT_REF;
  940.     while (keyuse->table == table)
  941.     {
  942.       start_keyuse=keyuse;
  943.       key=keyuse->key;
  944.       s->keys|= (key_map) 1 << key;        // QQ: remove this ?
  945.  
  946.       refs=const_ref=eq_part=0;
  947.       do
  948.       {
  949.         if (keyuse->val->type() != Item::NULL_ITEM)
  950.         {
  951.           if (!((~const_table_map) & keyuse->used_tables))
  952.         const_ref|= (key_map) 1 << keyuse->keypart;
  953.           else
  954.         refs|=keyuse->used_tables;
  955.           eq_part|= (uint) 1 << keyuse->keypart;
  956.         }
  957.         keyuse++;
  958.       } while (keyuse->table == table && keyuse->key == key);
  959.  
  960.       if (eq_part == PREV_BITS(uint,table->key_info[key].key_parts) &&
  961.           (table->key_info[key].flags & HA_NOSAME))
  962.       {
  963.         if (const_ref == eq_part)
  964.         {                    // Found everything for ref.
  965.           s->type=JT_CONST;
  966.           const_table_map|=table->map;
  967.           set_position(join,const_count++,s,start_keyuse);
  968.           break;
  969.         }
  970.         else
  971.           found_ref|= refs;        // Table is const if all refs are const
  972.       }
  973.     }
  974.       }
  975.     }
  976.   } while (const_table_map & found_ref);
  977.  
  978.   /* Calc how many (possible) matched records in each table */
  979.  
  980.   for (s=stat ; s < stat_end ; s++)
  981.   {
  982.     if (s->type == JT_SYSTEM || s->type == JT_CONST)
  983.     {
  984.       /* Only one matching row */
  985.       s->found_records=s->records=s->read_time=1; s->worst_seeks=1.0;
  986.       continue;
  987.     }
  988.     /* Approximate found rows and time to read them */
  989.     s->found_records=s->records=s->table->file->records;
  990.     s->read_time=(ha_rows) s->table->file->scan_time();
  991.  
  992.     /* Set a max range of how many seeks we can expect when using keys */
  993.     s->worst_seeks= (double) (s->read_time*2);
  994.     if (s->worst_seeks < 2.0)            // Fix for small tables
  995.       s->worst_seeks=2.0;
  996.  
  997.     /* if (s->type == JT_EQ_REF)
  998.       continue; */
  999.     if (s->const_keys)
  1000.     {
  1001.       ha_rows records;
  1002.       if (!select)
  1003.     select=make_select(s->table,const_table_map,
  1004.                0,
  1005.                and_conds(conds,s->on_expr),&error);
  1006.       records=get_quick_record_count(select,s->table, s->const_keys);
  1007.       s->quick=select->quick;
  1008.       s->needed_reg=select->needed_reg;
  1009.       select->quick=0;
  1010.       select->read_tables=const_table_map;
  1011.       if (records != HA_POS_ERROR)
  1012.       {
  1013.     s->found_records=records;
  1014.     s->read_time= (ha_rows) (s->quick ? s->quick->read_time : 0.0);
  1015.       }
  1016.     }
  1017.   }
  1018.   delete select;
  1019.  
  1020.   /* Find best combination and return it */
  1021.   join->join_tab=stat;
  1022.   join->map2table=stat_ref;
  1023.   join->table= join->all_tables=table_vector;
  1024.   join->const_tables=const_count;
  1025.   join->const_table_map=const_table_map;
  1026.  
  1027.   if (join->const_tables != join->tables)
  1028.     find_best_combination(join,all_table_map & ~const_table_map);
  1029.   else
  1030.   {
  1031.     memcpy((gptr) join->best_positions,(gptr) join->positions,
  1032.        sizeof(POSITION)*join->const_tables);
  1033.     join->best_read=1.0;
  1034.   }
  1035.   DBUG_RETURN(get_best_combination(join));
  1036. }
  1037.  
  1038.  
  1039. /*****************************************************************************
  1040. **    check with keys are used and with tables references with tables
  1041. **    updates in stat:
  1042. **      keys         Bitmap of all used keys
  1043. **      const_keys Bitmap of all keys with may be used with quick_select
  1044. **      keyuse     Pointer to possible keys
  1045. *****************************************************************************/
  1046.  
  1047. typedef struct key_field_t {        // Used when finding key fields
  1048.   Field        *field;
  1049.   Item        *val;            // May be empty if diff constant
  1050.   uint        level,const_level;    // QQ: Remove const_level
  1051.   bool        eq_func;
  1052.   bool        exists_optimize;
  1053. } KEY_FIELD;
  1054.  
  1055.  
  1056. /* merge new key definitions to old ones, remove those not used in both */
  1057.  
  1058. static KEY_FIELD *
  1059. merge_key_fields(KEY_FIELD *start,KEY_FIELD *new_fields,KEY_FIELD *end,
  1060.          uint and_level)
  1061. {
  1062.   if (start == new_fields)
  1063.     return start;                // Impossible or
  1064.   if (new_fields == end)
  1065.     return start;                // No new fields, skipp all
  1066.  
  1067.   KEY_FIELD *first_free=new_fields;
  1068.  
  1069.   /* Mark all found fields in old array */
  1070.   for (; new_fields != end ; new_fields++)
  1071.   {
  1072.     for (KEY_FIELD *old=start ; old != first_free ; old++)
  1073.     {
  1074.       if (old->field == new_fields->field)
  1075.       {
  1076.     if (new_fields->val->used_tables())
  1077.     {
  1078.       if (old->val->eq(new_fields->val))
  1079.       {
  1080.         old->level=old->const_level=and_level;
  1081.         old->exists_optimize&=new_fields->exists_optimize;
  1082.       }
  1083.     }
  1084.     else if (old->val->eq(new_fields->val) && old->eq_func &&
  1085.          new_fields->eq_func)
  1086.     {
  1087.       old->level=old->const_level=and_level;
  1088.       old->exists_optimize&=new_fields->exists_optimize;
  1089.     }
  1090.     else                    // Impossible; remove it
  1091.     {
  1092.       if (old == --first_free)        // If last item
  1093.         break;
  1094.       *old= *first_free;            // Remove old value
  1095.       old--;                // Retry this value
  1096.     }
  1097.       }
  1098.     }
  1099.   }
  1100.   /* Remove all not used items */
  1101.   for (KEY_FIELD *old=start ; old != first_free ;)
  1102.   {
  1103.     if (old->level != and_level && old->const_level != and_level)
  1104.     {                        // Not used in all levels
  1105.       if (old == --first_free)
  1106.     break;
  1107.       *old= *first_free;            // Remove old value
  1108.       continue;
  1109.     }
  1110.     old++;
  1111.   }
  1112.   return first_free;
  1113. }
  1114.  
  1115.  
  1116. static void
  1117. add_key_field(KEY_FIELD **key_fields,uint and_level,
  1118.           Field *field,bool eq_func,Item *value,
  1119.           table_map usable_tables)
  1120. {
  1121.   bool exists_optimize=0;
  1122.   if (!(field->flags & PART_KEY_FLAG))
  1123.   {
  1124.     // Don't remove column IS NULL on a LEFT JOIN table
  1125.     if (!eq_func || !value || value->type() != Item::NULL_ITEM ||
  1126.     !field->table->maybe_null || field->null_ptr)
  1127.       return;                    // Not a key. Skipp it
  1128.     exists_optimize=1;
  1129.   }
  1130.   else
  1131.   {
  1132.     table_map used_tables=0;
  1133.     if (value && (used_tables=value->used_tables()) &
  1134.     (field->table->map | RAND_TABLE_BIT))
  1135.       return;
  1136.     if (!(usable_tables & field->table->map))
  1137.     {
  1138.       if (!eq_func || !value || value->type() != Item::NULL_ITEM ||
  1139.       !field->table->maybe_null || field->null_ptr)
  1140.     return;                    // Can't use left join optimize
  1141.       exists_optimize=1;
  1142.     }
  1143.     else
  1144.     {
  1145.       JOIN_TAB *stat=field->table->reginfo.join_tab;
  1146.       stat[0].keys|=field->key_start;        // Add possible keys
  1147.  
  1148.       if (!value)
  1149.       {                        // Probably BETWEEN or IN
  1150.     stat[0].const_keys |= field->key_start;
  1151.     return;                    // Can't be used as eq key
  1152.       }
  1153.  
  1154.       /* Save the following cases:
  1155.      Field op constant
  1156.      Field LIKE constant where constant doesn't start with a wildcard
  1157.      Field = field2 where field2 is in a different table
  1158.      Field op formula
  1159.      Field IS NULL
  1160.      Field IS NOT NULL
  1161.       */
  1162.       stat[0].key_dependent|=used_tables;
  1163.       if (value->const_item())
  1164.     stat[0].const_keys |= field->key_start;
  1165.  
  1166.       /* We can't always use indexes when comparing a string index to a
  1167.      number. cmp_type() is checked to allow compare of dates to numbers */
  1168.       if (!eq_func ||
  1169.       field->result_type() == STRING_RESULT &&
  1170.       value->result_type() != STRING_RESULT &&
  1171.       field->cmp_type() != value->result_type())
  1172.     return;
  1173.     }
  1174.   }
  1175.   /* Store possible eq field */
  1176.   (*key_fields)->field=field;
  1177.   (*key_fields)->eq_func=eq_func;
  1178.   (*key_fields)->val=value;
  1179.   (*key_fields)->level=(*key_fields)->const_level=and_level;
  1180.   (*key_fields)->exists_optimize=exists_optimize;
  1181.   (*key_fields)++;
  1182. }
  1183.  
  1184.  
  1185. static void
  1186. add_key_fields(JOIN_TAB *stat,KEY_FIELD **key_fields,uint *and_level,
  1187.            COND *cond, table_map usable_tables)
  1188. {
  1189.   if (cond->type() == Item_func::COND_ITEM)
  1190.   {
  1191.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  1192.     KEY_FIELD *org_key_fields= *key_fields;
  1193.  
  1194.     if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
  1195.     {
  1196.       Item *item;
  1197.       while ((item=li++))
  1198.     add_key_fields(stat,key_fields,and_level,item,usable_tables);
  1199.       for (; org_key_fields != *key_fields ; org_key_fields++)
  1200.       {
  1201.     if (org_key_fields->const_level == org_key_fields->level)
  1202.       org_key_fields->const_level=org_key_fields->level= *and_level;
  1203.     else
  1204.       org_key_fields->const_level= *and_level;
  1205.       }
  1206.     }
  1207.     else
  1208.     {
  1209.       (*and_level)++;
  1210.       add_key_fields(stat,key_fields,and_level,li++,usable_tables);
  1211.       Item *item;
  1212.       while ((item=li++))
  1213.       {
  1214.     KEY_FIELD *start_key_fields= *key_fields;
  1215.     (*and_level)++;
  1216.     add_key_fields(stat,key_fields,and_level,item,usable_tables);
  1217.     *key_fields=merge_key_fields(org_key_fields,start_key_fields,
  1218.                      *key_fields,++(*and_level));
  1219.       }
  1220.     }
  1221.     return;
  1222.   }
  1223.   /* If item is of type 'field op field/constant' add it to key_fields */
  1224.  
  1225.   if (cond->type() != Item::FUNC_ITEM)
  1226.     return;
  1227.   Item_func *cond_func= (Item_func*) cond;
  1228.   switch (cond_func->select_optimize()) {
  1229.   case Item_func::OPTIMIZE_NONE:
  1230.     break;
  1231.   case Item_func::OPTIMIZE_KEY:
  1232.     if (cond_func->key_item()->type() == Item::FIELD_ITEM)
  1233.       add_key_field(key_fields,*and_level,
  1234.             ((Item_field*) (cond_func->key_item()))->field,
  1235.             0,(Item*) 0,usable_tables);
  1236.     break;
  1237.   case Item_func::OPTIMIZE_OP:
  1238.   {
  1239.     bool equal_func=(cond_func->functype() == Item_func::EQ_FUNC ||
  1240.              cond_func->functype() == Item_func::EQUAL_FUNC);
  1241.  
  1242.     if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  1243.     {
  1244.       add_key_field(key_fields,*and_level,
  1245.             ((Item_field*) (cond_func->arguments()[0]))->field,
  1246.             equal_func,
  1247.             (cond_func->arguments()[1]),usable_tables);
  1248.     }
  1249.     if (cond_func->arguments()[1]->type() == Item::FIELD_ITEM &&
  1250.     cond_func->functype() != Item_func::LIKE_FUNC)
  1251.     {
  1252.       add_key_field(key_fields,*and_level,
  1253.             ((Item_field*) (cond_func->arguments()[1]))->field,
  1254.             equal_func,
  1255.             (cond_func->arguments()[0]),usable_tables);
  1256.     }
  1257.     break;
  1258.   }
  1259.   case Item_func::OPTIMIZE_NULL:
  1260.     /* column_name IS [NOT] NULL */
  1261.     if (cond_func->arguments()[0]->type() == Item::FIELD_ITEM)
  1262.     {
  1263.       add_key_field(key_fields,*and_level,
  1264.             ((Item_field*) (cond_func->arguments()[0]))->field,
  1265.             cond_func->functype() == Item_func::ISNULL_FUNC,
  1266.             new Item_null, usable_tables);
  1267.     }
  1268.     break;
  1269.   }
  1270.   return;
  1271. }
  1272.  
  1273. /*
  1274. ** Add all keys with uses 'field' for some keypart
  1275. ** If field->and_level != and_level then only mark key_part as const_part
  1276. */
  1277.  
  1278. static uint
  1279. max_part_bit(key_map bits)
  1280. {
  1281.   uint found;
  1282.   for (found=0; bits & 1 ; found++,bits>>=1) ;
  1283.   return found;
  1284. }
  1285.  
  1286.  
  1287. static void
  1288. add_key_part(DYNAMIC_ARRAY *keyuse_array,KEY_FIELD *key_field)
  1289. {
  1290.   Field *field=key_field->field;
  1291.   TABLE *form= field->table;
  1292.   KEYUSE keyuse;
  1293.  
  1294.   if (key_field->eq_func && !key_field->exists_optimize)
  1295.   {
  1296.     for (uint key=0 ; key < form->keys ; key++)
  1297.     {
  1298.       if (!(form->keys_in_use_for_query & (((key_map) 1) << key)))
  1299.     continue;
  1300.       if (form->key_info[key].flags & HA_FULLTEXT)
  1301.     continue;    // ToDo: ft-keys in non-ft queries.   SerG
  1302.  
  1303.       uint key_parts= (uint) form->key_info[key].key_parts;
  1304.       for (uint part=0 ; part <  key_parts ; part++)
  1305.       {
  1306.     if (field->eq(form->key_info[key].key_part[part].field))
  1307.     {
  1308.       keyuse.table= field->table;
  1309.       keyuse.val =  key_field->val;
  1310.       keyuse.key =  key;
  1311.       keyuse.keypart=part;
  1312.       keyuse.used_tables=key_field->val->used_tables();
  1313.       VOID(insert_dynamic(keyuse_array,(gptr) &keyuse));
  1314.     }
  1315.       }
  1316.     }
  1317.   }
  1318.   /* Mark that we can optimize LEFT JOIN */
  1319.   if (key_field->val->type() == Item::NULL_ITEM &&
  1320.       !key_field->field->real_maybe_null())
  1321.     key_field->field->table->reginfo.not_exists_optimize=1;
  1322. }
  1323.  
  1324. static void
  1325. add_ft_keys(DYNAMIC_ARRAY *keyuse_array,
  1326.             JOIN_TAB *stat,COND *cond,table_map usable_tables)
  1327. {
  1328.   Item_func_match *cond_func=NULL;
  1329.  
  1330.   if (cond->type() == Item::FUNC_ITEM)
  1331.   {
  1332.     Item_func *func=(Item_func *)cond,
  1333.               *arg0=(Item_func *)(func->arguments()[0]),
  1334.               *arg1=(Item_func *)(func->arguments()[1]);
  1335.  
  1336.     if (func->functype() == Item_func::FT_FUNC)
  1337.       cond_func=(Item_func_match *)cond;
  1338.     else if ((func->functype() == Item_func::GE_FUNC ||
  1339.               func->functype() == Item_func::GT_FUNC)  &&
  1340.               arg0->type() == Item::FUNC_ITEM          &&
  1341.               arg0->functype() == Item_func::FT_FUNC   &&
  1342.               arg1->const_item() && arg1->val()>=0)
  1343.       cond_func=(Item_func_match *)arg0;
  1344.     else if ((func->functype() == Item_func::LE_FUNC ||
  1345.               func->functype() == Item_func::LT_FUNC)  &&
  1346.               arg1->type() == Item::FUNC_ITEM          &&
  1347.               arg1->functype() == Item_func::FT_FUNC   &&
  1348.               arg0->const_item() && arg0->val()>=0)
  1349.       cond_func=(Item_func_match *)arg1;
  1350.   }
  1351.   else if (cond->type() == Item::COND_ITEM)
  1352.   {
  1353.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  1354.  
  1355.     if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
  1356.     {
  1357.       Item *item;
  1358.       /* I'm too lazy to implement proper recursive descent here,
  1359.          and anyway, nobody will use such a stupid queries
  1360.          that will require it :-)
  1361.          May be later...
  1362.        */
  1363.       while ((item=li++))
  1364.         if (item->type() == Item::FUNC_ITEM &&
  1365.             ((Item_func *)item)->functype() == Item_func::FT_FUNC)
  1366.         {
  1367.           cond_func=(Item_func_match *)item;
  1368.           break;
  1369.         }
  1370.     }
  1371.   }
  1372.  
  1373.   if(!cond_func)
  1374.     return;
  1375.  
  1376.   KEYUSE keyuse;
  1377.  
  1378.   keyuse.table= cond_func->table;
  1379.   keyuse.val =  cond_func;
  1380.   keyuse.key =  cond_func->key;
  1381. #define FT_KEYPART   (MAX_REF_PARTS+10)
  1382.   keyuse.keypart=FT_KEYPART;
  1383.   keyuse.used_tables=cond_func->key_item()->used_tables();
  1384.   VOID(insert_dynamic(keyuse_array,(gptr) &keyuse));
  1385. }
  1386.  
  1387. static int
  1388. sort_keyuse(KEYUSE *a,KEYUSE *b)
  1389. {
  1390.   if (a->table->tablenr != b->table->tablenr)
  1391.     return (int) (a->table->tablenr - b->table->tablenr);
  1392.   if (a->key != b->key)
  1393.     return (int) (a->key - b->key);
  1394.   if (a->keypart != b->keypart)
  1395.     return (int) (a->keypart - b->keypart);
  1396.   return test(a->used_tables) - test(b->used_tables);    // Place const first
  1397. }
  1398.  
  1399.  
  1400. /*
  1401. ** Update keyuse array with all possible keys we can use to fetch rows
  1402. ** join_tab is a array in tablenr_order
  1403. ** stat is a reference array in 'prefered' order.
  1404. */
  1405.  
  1406. static bool
  1407. update_ref_and_keys(DYNAMIC_ARRAY *keyuse,JOIN_TAB *join_tab,uint tables,
  1408.         COND *cond, table_map normal_tables,List<Item_func_match> &ftfuncs)
  1409. {
  1410.   uint    and_level,i,found_eq_constant;
  1411.  
  1412.   {
  1413.     KEY_FIELD *key_fields,*end;
  1414.  
  1415.     if (!(key_fields=(KEY_FIELD*)
  1416.       my_malloc(sizeof(key_fields[0])*
  1417.             (current_thd->cond_count+1)*2,MYF(0))))
  1418.       return TRUE; /* purecov: inspected */
  1419.     and_level=0; end=key_fields;
  1420.     if (cond)
  1421.       add_key_fields(join_tab,&end,&and_level,cond,normal_tables);
  1422.     for (i=0 ; i < tables ; i++)
  1423.     {
  1424.       if (join_tab[i].on_expr)
  1425.       {
  1426.     add_key_fields(join_tab,&end,&and_level,join_tab[i].on_expr,
  1427.                join_tab[i].table->map);
  1428.       }
  1429.     }
  1430.     if (init_dynamic_array(keyuse,sizeof(KEYUSE),20,64))
  1431.     {
  1432.       my_free((gptr) key_fields,MYF(0));
  1433.       return TRUE;
  1434.     }
  1435.     /* fill keyuse with found key parts */
  1436.     for (KEY_FIELD *field=key_fields ; field != end ; field++)
  1437.       add_key_part(keyuse,field);
  1438.     my_free((gptr) key_fields,MYF(0));
  1439.   }
  1440.  
  1441.   if (ftfuncs.elements)
  1442.   {
  1443.     add_ft_keys(keyuse,join_tab,cond,normal_tables);
  1444.   }
  1445.  
  1446.   /*
  1447.   ** remove ref if there is a keypart which is a ref and a const.
  1448.   ** remove keyparts without previous keyparts.
  1449.   ** Special treatment for ft-keys. SerG.
  1450.   */
  1451.   if (keyuse->elements)
  1452.   {
  1453.     KEYUSE end,*prev,*save_pos,*use;
  1454.  
  1455.     qsort(keyuse->buffer,keyuse->elements,sizeof(KEYUSE),
  1456.       (qsort_cmp) sort_keyuse);
  1457.  
  1458.     bzero((char*) &end,sizeof(end));        /* Add for easy testing */
  1459.     VOID(insert_dynamic(keyuse,(gptr) &end));
  1460.  
  1461.     use=save_pos=dynamic_element(keyuse,0,KEYUSE*);
  1462.     prev=&end;
  1463.     found_eq_constant=0;
  1464.     for (i=0 ; i < keyuse->elements-1 ; i++,use++)
  1465.     {
  1466.       if (!use->used_tables)
  1467.     use->table->const_key_parts[use->key] |=
  1468.       (key_part_map) 1 << use->keypart;
  1469.       if (use->keypart != FT_KEYPART)
  1470.       {
  1471.     if (use->key == prev->key && use->table == prev->table)
  1472.     {
  1473.       if (prev->keypart+1 < use->keypart ||
  1474.           prev->keypart == use->keypart && found_eq_constant)
  1475.         continue;                /* remove */
  1476.     }
  1477.     else if (use->keypart != 0)        // First found must be 0
  1478.       continue;
  1479.       }
  1480.  
  1481.       *save_pos= *use;
  1482.       prev=use;
  1483.       found_eq_constant= !use->used_tables;
  1484.       /* Save ptr to first use */
  1485.       if (!use->table->reginfo.join_tab->keyuse)
  1486.     use->table->reginfo.join_tab->keyuse=save_pos;
  1487.       use->table->reginfo.join_tab->checked_keys|= (key_map) 1 << use->key;
  1488.       save_pos++;
  1489.     }
  1490.     i=(uint) (save_pos-(KEYUSE*) keyuse->buffer);
  1491.     VOID(set_dynamic(keyuse,(gptr) &end,i));
  1492.     keyuse->elements=i;
  1493.   }
  1494.   return FALSE;
  1495. }
  1496.  
  1497.  
  1498. /*****************************************************************************
  1499. **    Go through all combinations of not marked tables and find the one
  1500. **    which uses least records
  1501. *****************************************************************************/
  1502.  
  1503. /* Save const tables first as used tables */
  1504.  
  1505. static void
  1506. set_position(JOIN *join,uint idx,JOIN_TAB *table,KEYUSE *key)
  1507. {
  1508.   join->positions[idx].table= table;
  1509.   join->positions[idx].key=key;
  1510.   join->positions[idx].records_read=1.0;    /* This is a const table */
  1511.  
  1512.   /* Move the const table as down as possible in best_ref */
  1513.   JOIN_TAB **pos=join->best_ref+idx+1;
  1514.   JOIN_TAB *next=join->best_ref[idx];
  1515.   for ( ;next != table ; pos++)
  1516.   {
  1517.     JOIN_TAB *tmp=pos[0];
  1518.     pos[0]=next;
  1519.     next=tmp;
  1520.   }
  1521.   join->best_ref[idx]=table;
  1522. }
  1523.  
  1524.  
  1525. static void
  1526. find_best_combination(JOIN *join, table_map rest_tables)
  1527. {
  1528.   DBUG_ENTER("find_best_combination");
  1529.   join->best_read=DBL_MAX;
  1530.   find_best(join,rest_tables, join->const_tables,1.0,0.0);
  1531.   DBUG_VOID_RETURN;
  1532. }
  1533.  
  1534.  
  1535. static void
  1536. find_best(JOIN *join,table_map rest_tables,uint idx,double record_count,
  1537.       double read_time)
  1538. {
  1539.   ulong rec;
  1540.   double tmp;
  1541.  
  1542.   if (!rest_tables)
  1543.   {
  1544.     DBUG_PRINT("best",("read_time: %g  record_count: %g",read_time,
  1545.                record_count));
  1546.  
  1547.     read_time+=record_count/(double) TIME_FOR_COMPARE;
  1548.     if (join->sort_by_table &&
  1549.     join->sort_by_table != join->positions[join->const_tables].table->table)
  1550.       read_time+=record_count;            // We have to make a temp table
  1551.     if (read_time < join->best_read)
  1552.     {
  1553.       memcpy((gptr) join->best_positions,(gptr) join->positions,
  1554.          sizeof(POSITION)*idx);
  1555.       join->best_read=read_time;
  1556.     }
  1557.     return;
  1558.   }
  1559.   if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
  1560.     return;                    /* Found better before */
  1561.  
  1562.   JOIN_TAB *s;
  1563.   double best_record_count=DBL_MAX,best_read_time=DBL_MAX;
  1564.   for (JOIN_TAB **pos=join->best_ref+idx ; (s=*pos) ; pos++)
  1565.   {
  1566.     table_map real_table_bit=s->table->map;
  1567.     if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent))
  1568.     {
  1569.       double best,best_time,records;
  1570.       best=best_time=records=DBL_MAX;
  1571.       KEYUSE *best_key=0;
  1572.       uint best_max_key_part=0;
  1573.  
  1574.       if (s->keyuse)
  1575.       {                        /* Use key if possible */
  1576.     TABLE *table=s->table;
  1577.     KEYUSE *keyuse,*start_key=0;
  1578.     double best_records=DBL_MAX;
  1579.     uint max_key_part=0;
  1580.  
  1581.     /* Test how we can use keys */
  1582.     rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE;  /* Assumed records/key */
  1583.     for (keyuse=s->keyuse ; keyuse->table == table ;)
  1584.     {
  1585.       key_map found_part=0;
  1586.       table_map found_ref=0;
  1587.       uint key=keyuse->key;
  1588.       KEY *keyinfo=table->key_info+key;
  1589.           bool ft_key=(keyuse->keypart == FT_KEYPART);
  1590.  
  1591.       start_key=keyuse;
  1592.       do
  1593.       {
  1594.             uint keypart=keyuse->keypart;
  1595.         do
  1596.         {
  1597.               if (!ft_key)
  1598.               {
  1599.         table_map map;
  1600.         if (!(rest_tables & keyuse->used_tables))
  1601.         {
  1602.           found_part|= (key_part_map) 1 << keypart;
  1603.           found_ref|= keyuse->used_tables;
  1604.         }
  1605.         /*
  1606.         ** If we find a ref, assume this table matches a proportional
  1607.         ** part of this table.
  1608.         ** For example 100 records matching a table with 5000 records
  1609.         ** gives 5000/100 = 50 records per key
  1610.         ** Constant tables are ignored and to avoid bad matches,
  1611.         ** we don't make rec less than 100.
  1612.         */
  1613.         if (keyuse->used_tables &
  1614.             (map=(keyuse->used_tables & ~join->const_table_map)))
  1615.         {
  1616.           uint tablenr;
  1617.           for (tablenr=0 ; ! (map & 1) ; map>>=1, tablenr++) ;
  1618.           if (map == 1)            // Only one table
  1619.           {
  1620.             TABLE *tmp_table=join->all_tables[tablenr];
  1621.             if (rec > tmp_table->file->records && rec > 100)
  1622.               rec=max(tmp_table->file->records,100);
  1623.           }
  1624.         }
  1625.               }
  1626.           keyuse++;
  1627.         } while (keyuse->table == table && keyuse->key == key &&
  1628.              keyuse->keypart == keypart);
  1629.       } while (keyuse->table == table && keyuse->key == key);
  1630.  
  1631.       /*
  1632.       ** Assume that that each key matches a proportional part of table.
  1633.       */
  1634.           if (!found_part && !ft_key)
  1635.         continue;                // Nothing usable found
  1636.       if (rec == 0)
  1637.         rec=1L;                // Fix for small tables
  1638.  
  1639.           /*
  1640.           ** ft-keys require special treatment
  1641.           */
  1642.           if (ft_key)
  1643.           {
  1644.             /*
  1645.             ** Really, there should be records=0.0 (yes!)
  1646.             ** but 1.0 would be probably safer
  1647.             */
  1648.             tmp=prev_record_reads(join,found_ref);
  1649.             records=1.0;
  1650.           }
  1651.           else
  1652.           {
  1653.       /*
  1654.       ** Check if we found full key
  1655.       */
  1656.       if (found_part == PREV_BITS(uint,keyinfo->key_parts))
  1657.       {                /* use eq key */
  1658.         max_key_part= (uint) ~0;
  1659.         if ((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) == HA_NOSAME)
  1660.         {
  1661.           tmp=prev_record_reads(join,found_ref);
  1662.           records=1.0;
  1663.         }
  1664.         else
  1665.         {
  1666.           if (!found_ref)
  1667.           {                    // We found a const key
  1668.         if (table->quick_keys & ((key_map) 1 << key))
  1669.           records= (double) table->quick_rows[key];
  1670.         else
  1671.           records= (double) s->records/rec; // quick_range couldn't use key!
  1672.           }
  1673.           else
  1674.           {
  1675.         if (!(records=keyinfo->rec_per_key[keyinfo->key_parts-1]))
  1676.         {                // Prefere longer keys
  1677.           records=
  1678.             ((double) s->records / (double) rec *
  1679.              (1.0 +
  1680.               ((double) (table->max_key_length-keyinfo->key_length) /
  1681.                (double) table->max_key_length)));
  1682.           if (records < 2.0)
  1683.             records=2.0;        // Can't be as good as a unique
  1684.         }
  1685.           }
  1686.           if (table->used_keys & ((key_map) 1 << key))
  1687.           {
  1688.         /* we can use only index tree */
  1689.         uint keys_per_block= table->file->block_size/2/
  1690.           keyinfo->key_length+1;
  1691.         tmp=(record_count*(records+keys_per_block-1)/
  1692.              keys_per_block);
  1693.           }
  1694.           else
  1695.         tmp=record_count*min(records,s->worst_seeks);
  1696.         }
  1697.       }
  1698.       else
  1699.       {
  1700.         /*
  1701.         ** Use as much key-parts as possible and a uniq key is better
  1702.         ** than a not unique key
  1703.         ** Set tmp to (previous record count) * (records / combination)
  1704.         */
  1705.         if ((found_part & 1) &&
  1706.         !(table->file->option_flag() & HA_ONLY_WHOLE_INDEX))
  1707.         {
  1708.           max_key_part=max_part_bit(found_part);
  1709.           /* Check if quick_range could determinate how many rows we
  1710.          will match */
  1711.  
  1712.           if (table->quick_keys & ((key_map) 1 << key) &&
  1713.           table->quick_key_parts[key] <= max_key_part)
  1714.         tmp=records= (double) table->quick_rows[key];
  1715.           else
  1716.           {
  1717.         /* Check if we have statistic about the distribution */
  1718.         if ((records=keyinfo->rec_per_key[max_key_part-1]))
  1719.           tmp=records;
  1720.         else
  1721.         {
  1722.           /*
  1723.           ** Assume that the first key part matches 1% of the file
  1724.           ** and that the hole key matches 10 (dupplicates) or 1
  1725.           ** (unique) records.
  1726.           ** Assume also that more key matches proportionally more
  1727.           ** records
  1728.           ** This gives the formula:
  1729.           ** records= (x * (b-a) + a*c-b)/(c-1)
  1730.           **
  1731.           ** b = records matched by whole key
  1732.           ** a = records matched by first key part (10% of all records?)
  1733.           ** c = number of key parts in key
  1734.           ** x = used key parts (1 <= x <= c)
  1735.           */
  1736.           double rec_per_key;
  1737.           if (!(rec_per_key=(double)
  1738.             keyinfo->rec_per_key[keyinfo->key_parts-1]))
  1739.             rec_per_key=(double) s->records/rec+1;
  1740.  
  1741.           if (!s->records)
  1742.             tmp=0;
  1743.           else if (rec_per_key/(double) s->records >= 0.01)
  1744.             tmp=rec_per_key;
  1745.           else
  1746.           {
  1747.             double a=s->records*0.01;
  1748.             tmp=(max_key_part * (rec_per_key - a) +
  1749.              a*keyinfo->key_parts - rec_per_key)/
  1750.               (keyinfo->key_parts-1);
  1751.             set_if_bigger(tmp,1.0);
  1752.           }
  1753.           records=(ulong) tmp;
  1754.         }
  1755.           }
  1756.           if (table->used_keys & ((key_map) 1 << key))
  1757.           {
  1758.         /* we can use only index tree */
  1759.         uint keys_per_block= table->file->block_size/2/
  1760.           keyinfo->key_length+1;
  1761.         tmp=record_count*(tmp+keys_per_block-1)/keys_per_block;
  1762.           }
  1763.           else
  1764.         tmp=record_count*min(tmp,s->worst_seeks);
  1765.         }
  1766.         else
  1767.           tmp=best_time;            // Do nothing
  1768.       }
  1769.           } /* not ft_key */
  1770.       if (tmp < best_time - records/(double) TIME_FOR_COMPARE)
  1771.       {
  1772.         best_time=tmp + records/(double) TIME_FOR_COMPARE;
  1773.         best=tmp;
  1774.         best_records=records;
  1775.         best_key=start_key;
  1776.         best_max_key_part=max_key_part;
  1777.       }
  1778.     }
  1779.     records=best_records;
  1780.       }
  1781.  
  1782.       /*
  1783.     Don't test table scan if it can't be better.
  1784.     Prefer key lookup if we would use the same key for scanning.
  1785.       */
  1786.       if ((records >= s->found_records || best > s->read_time) &&
  1787.       !(s->quick && best_key && s->quick->index == best_key->key &&
  1788.         best_max_key_part >= s->table->quick_key_parts[best_key->key]))
  1789.       {                        // Check full join
  1790.     if (s->on_expr)
  1791.     {
  1792.       tmp=s->found_records;            // Can't use read cache
  1793.     }
  1794.     else
  1795.     {
  1796.       tmp=(double) s->read_time;
  1797.       /* Calculate time to read through cache */
  1798.       tmp*=(1.0+floor((double) cache_record_length(join,idx)*
  1799.               record_count/(double) join_buff_size));
  1800.     }
  1801.     if (best == DBL_MAX ||
  1802.         (tmp  + record_count/(double) TIME_FOR_COMPARE*s->found_records <
  1803.          best + record_count/(double) TIME_FOR_COMPARE*records))
  1804.     {
  1805.       /*
  1806.         If the table has a range (s->quick is set) make_join_select()
  1807.         will ensure that this will be used
  1808.       */
  1809.       best=tmp;
  1810.       records=s->found_records;
  1811.       best_key=0;
  1812.     }
  1813.       }
  1814.       join->positions[idx].records_read=(double) records;
  1815.       join->positions[idx].key=best_key;
  1816.       join->positions[idx].table= s;
  1817.       if (!best_key && idx == join->const_tables &&
  1818.       s->table == join->sort_by_table)
  1819.     join->sort_by_table= (TABLE*) 1;    // Must use temporary table
  1820.  
  1821.      /*
  1822.     Go to the next level only if there hasn't been a better key on
  1823.     this level! This will cut down the search for a lot simple cases!
  1824.        */
  1825.       double current_record_count=record_count*records;
  1826.       double current_read_time=read_time+best;
  1827.       if (best_record_count > current_record_count ||
  1828.       best_read_time > current_read_time ||
  1829.       idx == join->const_tables && s->table == join->sort_by_table)
  1830.       {
  1831.     if (best_record_count >= current_record_count &&
  1832.         best_read_time >= current_read_time &&
  1833.         (!(s->key_dependent & rest_tables) || records < 2.0))
  1834.     {
  1835.       best_record_count=current_record_count;
  1836.       best_read_time=current_read_time;
  1837.     }
  1838.     swap(JOIN_TAB*,join->best_ref[idx],*pos);
  1839.     find_best(join,rest_tables & ~real_table_bit,idx+1,
  1840.           current_record_count,current_read_time);
  1841.     swap(JOIN_TAB*,join->best_ref[idx],*pos);
  1842.       }
  1843.       if (join->select_options & SELECT_STRAIGHT_JOIN)
  1844.     break;                // Don't test all combinations
  1845.     }
  1846.   }
  1847. }
  1848.  
  1849.  
  1850. /*
  1851. ** Find how much space the prevous read not const tables takes in cache
  1852. */
  1853.  
  1854. static uint
  1855. cache_record_length(JOIN *join,uint idx)
  1856. {
  1857.   uint length;
  1858.   JOIN_TAB **pos,**end;
  1859.   THD *thd=current_thd;
  1860.  
  1861.   length=0;
  1862.   for (pos=join->best_ref+join->const_tables,end=join->best_ref+idx ;
  1863.        pos != end ;
  1864.        pos++)
  1865.   {
  1866.     JOIN_TAB *join_tab= *pos;
  1867.     if (!join_tab->used_fieldlength)
  1868.     {                    /* Not calced yet */
  1869.       uint null_fields,blobs,fields,rec_length;
  1870.       null_fields=blobs=fields=rec_length=0;
  1871.  
  1872.       Field **f_ptr,*field;
  1873.       for (f_ptr=join_tab->table->field ; (field= *f_ptr) ; f_ptr++)
  1874.       {
  1875.     if (field->query_id == thd->query_id)
  1876.     {
  1877.       uint flags=field->flags;
  1878.       fields++;
  1879.       rec_length+=field->pack_length();
  1880.       if (flags & BLOB_FLAG)
  1881.         blobs++;
  1882.       if (!(flags & NOT_NULL_FLAG))
  1883.         null_fields++;
  1884.     }
  1885.       }
  1886.       if (null_fields)
  1887.     rec_length+=(join_tab->table->null_fields+7)/8;
  1888.       if (join_tab->table->maybe_null)
  1889.     rec_length+=sizeof(my_bool);
  1890.       if (blobs)
  1891.       {
  1892.     uint blob_length=(uint) (join_tab->table->file->mean_rec_length-
  1893.                  (join_tab->table->reclength- rec_length));
  1894.     rec_length+=(uint) max(4,blob_length);
  1895.       }
  1896.       join_tab->used_fields=fields;
  1897.       join_tab->used_fieldlength=rec_length;
  1898.       join_tab->used_blobs=blobs;
  1899.     }
  1900.     length+=join_tab->used_fieldlength;
  1901.   }
  1902.   return length;
  1903. }
  1904.  
  1905.  
  1906. static double
  1907. prev_record_reads(JOIN *join,table_map found_ref)
  1908. {
  1909.   double found=1.0;
  1910.  
  1911.   for (POSITION *pos=join->positions ; found_ref ; pos++)
  1912.   {
  1913.     if (pos->table->table->map & found_ref)
  1914.     {
  1915.       found_ref&= ~pos->table->table->map;
  1916.       found*=pos->records_read;
  1917.     }
  1918.   }
  1919.   return found;
  1920. }
  1921.  
  1922.  
  1923. /*****************************************************************************
  1924. **    Set up join struct according to best position.
  1925. *****************************************************************************/
  1926.  
  1927. static bool
  1928. get_best_combination(JOIN *join)
  1929. {
  1930.   uint i,key,tablenr;
  1931.   table_map used_tables;
  1932.   TABLE *table;
  1933.   JOIN_TAB *join_tab,*j;
  1934.   KEYUSE *keyuse;
  1935.   KEY *keyinfo;
  1936.   uint table_count;
  1937.   String *ft_tmp=0;
  1938.   char tmp1[FT_QUERY_MAXLEN];
  1939.   String tmp2(tmp1,sizeof(tmp1));
  1940.  
  1941.   table_count=join->tables;
  1942.   if (!(join->join_tab=join_tab=
  1943.     (JOIN_TAB*) join->thd->alloc(sizeof(JOIN_TAB)*table_count)))
  1944.     return TRUE;
  1945.  
  1946.   join->const_tables=0;                /* for checking */
  1947.   join->const_table_map=0;
  1948.   join->full_join=0;
  1949.  
  1950.   used_tables=0;
  1951.   for (j=join_tab, tablenr=0 ; tablenr < table_count ; tablenr++,j++)
  1952.   {
  1953.     TABLE *form;
  1954.     *j= *join->best_positions[tablenr].table;
  1955.     form=join->table[tablenr]=j->table;
  1956.     j->ref.key = -1;
  1957.     j->ref.key_parts=0;
  1958.     j->info=0;                    // For describe
  1959.     used_tables|= form->map;
  1960.     form->reginfo.join_tab=j;
  1961.     if (!j->on_expr)
  1962.       form->reginfo.not_exists_optimize=0;    // Only with LEFT JOIN
  1963.  
  1964.     if (j->type == JT_SYSTEM)
  1965.     {
  1966.       j->table->const_table=1;
  1967.       if (join->const_tables == tablenr)
  1968.       {
  1969.     join->const_tables++;
  1970.     join->const_table_map|=form->map;
  1971.       }
  1972.       continue;
  1973.     }
  1974.     if (!j->keys || !(keyuse= join->best_positions[tablenr].key))
  1975.     {
  1976.       j->type=JT_ALL;
  1977.       if (tablenr != join->const_tables)
  1978.     join->full_join=1;
  1979.     }
  1980.     else
  1981.     {
  1982.       uint keyparts,length;
  1983.       bool ftkey=(keyuse->keypart == FT_KEYPART);
  1984.       /*
  1985.       ** Use best key from find_best
  1986.       */
  1987.       table=j->table;
  1988.       key=keyuse->key;
  1989.  
  1990.       keyinfo=table->key_info+key;
  1991.       if (ftkey)
  1992.       {
  1993.         Item_func_match *ifm=(Item_func_match *)keyuse->val;
  1994.  
  1995.         ft_tmp=ifm->key_item()->val_str(&tmp2);
  1996.         length=ft_tmp->length();
  1997.         keyparts=1;
  1998.         ifm->join_key=1;
  1999.       }
  2000.       else
  2001.       {
  2002.         keyparts=length=0;
  2003.         do
  2004.         {
  2005.           if (!((~used_tables) & keyuse->used_tables))
  2006.           {
  2007.             if (keyparts == keyuse->keypart)
  2008.             {
  2009.               keyparts++;
  2010.               length+=keyinfo->key_part[keyuse->keypart].length +
  2011.                 test(keyinfo->key_part[keyuse->keypart].null_bit);
  2012.             }
  2013.           }
  2014.           keyuse++;
  2015.         } while (keyuse->table == table && keyuse->key == key);
  2016.       } /* not ftkey */
  2017.  
  2018.       /* set up fieldref */
  2019.       keyinfo=table->key_info+key;
  2020.       j->ref.key_parts=keyparts;
  2021.       j->ref.key_length=length;
  2022.       j->ref.key=(int) key;
  2023.       if (!(j->ref.key_buff= (byte*) sql_calloc(ALIGN_SIZE(length)*2)) ||
  2024.       !(j->ref.key_copy= (store_key**) sql_alloc((sizeof(store_key*) *
  2025.                               (keyparts+1)))) ||
  2026.       !(j->ref.items=    (Item**) sql_alloc(sizeof(Item*)*keyparts)))
  2027.       {
  2028.     return TRUE;
  2029.       }
  2030.       j->ref.key_buff2=j->ref.key_buff+ALIGN_SIZE(length);
  2031.       j->ref.key_err=1;
  2032.       keyuse=join->best_positions[tablenr].key;
  2033.  
  2034.       store_key **ref_key=j->ref.key_copy;
  2035.       byte *key_buff=j->ref.key_buff;
  2036.       if (ftkey)
  2037.       {
  2038.         j->ref.items[0]=((Item_func*)(keyuse->val))->key_item();
  2039.         if (!keyuse->used_tables)
  2040.         {
  2041.           // AFAIK key_buff is zeroed...
  2042.       // We don't need to free ft_tmp as the buffer will be freed atom.
  2043.           memcpy((gptr)key_buff, (gptr) ft_tmp->ptr(), ft_tmp->length());
  2044.         }
  2045.         else
  2046.     {
  2047.           return TRUE; // not supported yet. SerG
  2048.     }
  2049.         j->type=JT_FT;
  2050.       }
  2051.       else
  2052.       {
  2053.     THD *thd=current_thd;
  2054.     for (i=0 ; i < keyparts ; keyuse++,i++)
  2055.     {
  2056.       while (keyuse->keypart != i ||
  2057.          ((~used_tables) & keyuse->used_tables))
  2058.         keyuse++;                /* Skipp other parts */
  2059.  
  2060.       uint maybe_null= test(keyinfo->key_part[i].null_bit);
  2061.       j->ref.items[i]=keyuse->val;        // Save for cond removal
  2062.       if (!keyuse->used_tables &&
  2063.           !(join->select_options & SELECT_DESCRIBE))
  2064.       {                    // Compare against constant
  2065.         store_key_item *tmp=new store_key_item(keyinfo->key_part[i].field,
  2066.                            (char*)key_buff +
  2067.                            maybe_null,
  2068.                            maybe_null ?
  2069.                            (char*) key_buff : 0,
  2070.                            keyinfo->key_part[i].length,
  2071.                            keyuse->val);
  2072.         if (thd->fatal_error)
  2073.         {
  2074.           return TRUE;
  2075.         }
  2076.         tmp->copy();
  2077.       }
  2078.       else
  2079.         *ref_key++= get_store_key(keyuse,join->const_table_map,
  2080.                       &keyinfo->key_part[i],
  2081.                       (char*) key_buff,maybe_null);
  2082.       key_buff+=keyinfo->key_part[i].store_length;
  2083.     }
  2084.       } /* not ftkey */
  2085.       *ref_key=0;                // end_marker
  2086.       if (j->type == JT_FT)  /* no-op */;
  2087.       else if (j->type == JT_CONST)
  2088.       {
  2089.     j->table->const_table=1;
  2090.     if (join->const_tables == tablenr)
  2091.     {
  2092.       join->const_tables++;
  2093.       join->const_table_map|=form->map;
  2094.     }
  2095.       }
  2096.       else if (((keyinfo->flags & (HA_NOSAME | HA_NULL_PART_KEY)) != HA_NOSAME) ||
  2097.            keyparts != keyinfo->key_parts)
  2098.     j->type=JT_REF;                /* Must read with repeat */
  2099.       else if (ref_key == j->ref.key_copy)
  2100.       {                        /* Should never be reached */
  2101.     j->type=JT_CONST;            /* purecov: deadcode */
  2102.     if (join->const_tables == tablenr)
  2103.     {
  2104.       join->const_tables++;            /* purecov: deadcode */
  2105.       join->const_table_map|=form->map;
  2106.     }
  2107.       }
  2108.       else
  2109.     j->type=JT_EQ_REF;
  2110.     }
  2111.   }
  2112.  
  2113.   for (i=0 ; i < table_count ; i++)
  2114.     join->map2table[join->join_tab[i].table->tablenr]=join->join_tab+i;
  2115.   update_depend_map(join);
  2116.   return 0;
  2117. }
  2118.  
  2119.  
  2120. static store_key *
  2121. get_store_key(KEYUSE *keyuse, table_map used_tables, KEY_PART_INFO *key_part,
  2122.           char *key_buff, uint maybe_null)
  2123. {
  2124.   if (!((~used_tables) & keyuse->used_tables))        // if const item
  2125.   {
  2126.     return new store_key_const_item(key_part->field,
  2127.                     key_buff + maybe_null,
  2128.                     maybe_null ? key_buff : 0,
  2129.                     key_part->length,
  2130.                     keyuse->val);
  2131.   }
  2132.   else if (keyuse->val->type() == Item::FIELD_ITEM)
  2133.     return new store_key_field(key_part->field,
  2134.                    key_buff + maybe_null,
  2135.                    maybe_null ? key_buff : 0,
  2136.                    key_part->length,
  2137.                    ((Item_field*) keyuse->val)->field,
  2138.                    keyuse->val->full_name());
  2139.   return new store_key_item(key_part->field,
  2140.                 key_buff + maybe_null,
  2141.                 maybe_null ? key_buff : 0,
  2142.                 key_part->length,
  2143.                 keyuse->val);
  2144. }
  2145.  
  2146. /*
  2147. ** This function is only called for const items on fields which are keys
  2148. ** returns 1 if there was some conversion made when the field was stored.
  2149. */
  2150.  
  2151. bool
  2152. store_val_in_field(Field *field,Item *item)
  2153. {
  2154.   THD *thd=current_thd;
  2155.   ulong cuted_fields=thd->cuted_fields;
  2156.   thd->count_cuted_fields=1;
  2157.   item->save_in_field(field);
  2158.   thd->count_cuted_fields=0;
  2159.   return cuted_fields != thd->cuted_fields;
  2160. }
  2161.  
  2162.  
  2163. static bool
  2164. make_simple_join(JOIN *join,TABLE *tmp_table)
  2165. {
  2166.   TABLE **tableptr;
  2167.   JOIN_TAB *join_tab;
  2168.  
  2169.   if (!(tableptr=(TABLE**) join->thd->alloc(sizeof(TABLE*))) ||
  2170.       !(join_tab=(JOIN_TAB*) join->thd->alloc(sizeof(JOIN_TAB))))
  2171.     return TRUE;
  2172.   join->join_tab=join_tab;
  2173.   join->table=tableptr; tableptr[0]=tmp_table;
  2174.   join->tables=1;
  2175.   join->const_tables=0;
  2176.   join->const_table_map=0;
  2177.   join->tmp_table_param.copy_field_count=join->tmp_table_param.field_count=
  2178.     join->tmp_table_param.sum_func_count= join->tmp_table_param.func_count=0;
  2179.   join->tmp_table_param.copy_field=0;
  2180.   join->first_record=join->sort_and_group=0;
  2181.   join->sum_funcs=0;
  2182.   join->send_records=(ha_rows) 0;
  2183.   join->group=0;
  2184.  
  2185.   join_tab->cache.buff=0;            /* No cacheing */
  2186.   join_tab->table=tmp_table;
  2187.   join_tab->select=0;
  2188.   join_tab->select_cond=0;
  2189.   join_tab->quick=0;
  2190.   join_tab->type= JT_ALL;            /* Map through all records */
  2191.   join_tab->keys= (uint) ~0;            /* test everything in quick */
  2192.   join_tab->info=0;
  2193.   join_tab->on_expr=0;
  2194.   join_tab->ref.key = -1;
  2195.   join_tab->not_used_in_distinct=0;
  2196.   join_tab->read_first_record= join_init_read_record;
  2197.   bzero((char*) &join_tab->read_record,sizeof(join_tab->read_record));
  2198.   tmp_table->status=0;
  2199.   tmp_table->null_row=0;
  2200.   return FALSE;
  2201. }
  2202.  
  2203.  
  2204. static bool
  2205. make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
  2206. {
  2207.   DBUG_ENTER("make_join_select");
  2208.   if (select)
  2209.   {
  2210.     table_map used_tables;
  2211.     if (join->tables > 1)
  2212.       cond->update_used_tables();        // Tablenr may have changed
  2213.     {                        // Check const tables
  2214.       COND *const_cond=
  2215.     make_cond_for_table(cond,join->const_table_map,(table_map) 0);
  2216.       DBUG_EXECUTE("where",print_where(const_cond,"constants"););
  2217.       if (const_cond && !const_cond->val_int())
  2218.     DBUG_RETURN(1);                // Impossible const condition
  2219.     }
  2220.     used_tables=(select->const_tables=join->const_table_map) | RAND_TABLE_BIT;
  2221.     for (uint i=join->const_tables ; i < join->tables ; i++)
  2222.     {
  2223.       JOIN_TAB *tab=join->join_tab+i;
  2224.       table_map current_map= tab->table->map;
  2225.       used_tables|=current_map;
  2226.       COND *tmp=make_cond_for_table(cond,used_tables,current_map);
  2227.       if (!tmp && tab->quick)
  2228.       {                        // Outer join
  2229.     /*
  2230.       Hack to handle the case where we only refer to a table
  2231.       in the ON part of an OUTER JOIN.
  2232.     */
  2233.     tmp=new Item_int((longlong) 1,1);    // Always true
  2234.       }
  2235.       if (tmp)
  2236.       {
  2237.     DBUG_EXECUTE("where",print_where(tmp,tab->table->table_name););
  2238.     SQL_SELECT *sel=tab->select=(SQL_SELECT*)
  2239.       sql_memdup((gptr) select, sizeof(SQL_SELECT));
  2240.     if (!sel)
  2241.       DBUG_RETURN(1);            // End of memory
  2242.     tab->select_cond=sel->cond=tmp;
  2243.     sel->head=tab->table;
  2244.     if (tab->quick)
  2245.     {
  2246.       /* Use quick key read if it's a constant and it's not used
  2247.          with key reading */
  2248.       if (tab->needed_reg == 0 && tab->type != JT_EQ_REF &&
  2249.           (tab->type != JT_REF ||
  2250.            (uint) tab->ref.key == tab->quick->index))
  2251.       {
  2252.         sel->quick=tab->quick;        // Use value from get_quick_...
  2253.         sel->quick_keys=0;
  2254.         sel->needed_reg=0;
  2255.       }
  2256.       else
  2257.       {
  2258.         delete tab->quick;
  2259.       }
  2260.       tab->quick=0;
  2261.     }
  2262.     uint ref_key=(uint) sel->head->reginfo.join_tab->ref.key+1;
  2263.     if (i == join->const_tables && ref_key)
  2264.     {
  2265.       if (tab->const_keys && tab->table->reginfo.impossible_range)
  2266.         DBUG_RETURN(1);
  2267.     }
  2268.     else if (tab->type == JT_ALL)
  2269.     {
  2270.       if (tab->const_keys &&
  2271.           tab->table->reginfo.impossible_range)
  2272.         DBUG_RETURN(1);                // Impossible range
  2273.       /*
  2274.         We plan to scan all rows.
  2275.         Check again if we should use an index.
  2276.         We could have used an column from a previous table in
  2277.         the index if we are using limit and this is the first table
  2278.       */
  2279.  
  2280.       if ((tab->keys & ~ tab->const_keys && i > 0) ||
  2281.           tab->const_keys && i == join->const_tables &&
  2282.           join->thd->select_limit < join->best_positions[i].records_read)
  2283.       {
  2284.         /* Join with outer join condition */
  2285.         COND *orig_cond=sel->cond;
  2286.         sel->cond=and_conds(sel->cond,tab->on_expr);
  2287.         if (sel->test_quick_select(tab->keys,
  2288.                        used_tables & ~ current_map,
  2289.                        join->thd->select_limit) < 0)
  2290.           DBUG_RETURN(1);                // Impossible range
  2291.         sel->cond=orig_cond;
  2292.       }
  2293.       else
  2294.       {
  2295.         sel->needed_reg=tab->needed_reg;
  2296.         sel->quick_keys=0;
  2297.       }
  2298.       if ((sel->quick_keys | sel->needed_reg) & ~tab->checked_keys)
  2299.       {
  2300.         tab->keys=sel->quick_keys | sel->needed_reg;
  2301.         tab->use_quick= (sel->needed_reg &&
  2302.                  (!select->quick_keys ||
  2303.                   (select->quick &&
  2304.                    (select->quick->records >= 100L)))) ?
  2305.           2 : 1;
  2306.         sel->read_tables= used_tables;
  2307.       }
  2308.       if (i != join->const_tables && tab->use_quick != 2)
  2309.       {                    /* Read with cache */
  2310.         if ((tmp=make_cond_for_table(cond,
  2311.                      join->const_table_map |
  2312.                      current_map,
  2313.                      current_map)))
  2314.         {
  2315.           DBUG_EXECUTE("where",print_where(tmp,"cache"););
  2316.           tab->cache.select=(SQL_SELECT*) sql_memdup((gptr) sel,
  2317.                             sizeof(SQL_SELECT));
  2318.           tab->cache.select->cond=tmp;
  2319.           tab->cache.select->read_tables=join->const_table_map;
  2320.         }
  2321.       }
  2322.     }
  2323.     if (tab->type == JT_REF && sel->quick &&
  2324.         tab->ref.key_length < sel->quick->max_used_key_length)
  2325.     {
  2326.       /* Range uses longer key;  Use this instead of ref on key */
  2327.       tab->type=JT_ALL;
  2328.       tab->use_quick=1;
  2329.       tab->ref.key_parts=0;        // Don't use ref key.
  2330.       join->best_positions[i].records_read=sel->quick->records;
  2331.     }
  2332.       }
  2333.     }
  2334.   }
  2335.   DBUG_RETURN(0);
  2336. }
  2337.  
  2338.  
  2339. static void
  2340. make_join_readinfo(JOIN *join,uint options)
  2341. {
  2342.   uint i;
  2343.   DBUG_ENTER("make_join_readinfo");
  2344.  
  2345.   for (i=join->const_tables ; i < join->tables ; i++)
  2346.   {
  2347.     JOIN_TAB *tab=join->join_tab+i;
  2348.     TABLE *table=tab->table;
  2349.     tab->read_record.table= table;
  2350.     tab->read_record.file=table->file;
  2351.     tab->next_select=sub_select;        /* normal select */
  2352.     switch (tab->type) {
  2353.     case JT_SYSTEM:                // Only happens with left join
  2354.       table->status=STATUS_NO_RECORD;
  2355.       tab->read_first_record= join_read_system;
  2356.       tab->read_record.read_record= join_no_more_records;
  2357.       break;
  2358.     case JT_CONST:                // Only happens with left join
  2359.       table->status=STATUS_NO_RECORD;
  2360.       tab->read_first_record= join_read_const;
  2361.       tab->read_record.read_record= join_no_more_records;
  2362.       break;
  2363.     case JT_EQ_REF:
  2364.       table->status=STATUS_NO_RECORD;
  2365.       if (tab->select)
  2366.       {
  2367.     delete tab->select->quick;
  2368.     tab->select->quick=0;
  2369.       }
  2370.       delete tab->quick;
  2371.       tab->quick=0;
  2372.       table->file->index_init(tab->ref.key);
  2373.       tab->read_first_record= join_read_key;
  2374.       tab->read_record.read_record= join_no_more_records;
  2375.       if (table->used_keys & ((key_map) 1 << tab->ref.key))
  2376.       {
  2377.     table->key_read=1;
  2378.     table->file->extra(HA_EXTRA_KEYREAD);
  2379.       }
  2380.       break;
  2381.     case JT_REF:
  2382.       table->status=STATUS_NO_RECORD;
  2383.       if (tab->select)
  2384.       {
  2385.     delete tab->select->quick;
  2386.     tab->select->quick=0;
  2387.       }
  2388.       delete tab->quick;
  2389.       tab->quick=0;
  2390.       table->file->index_init(tab->ref.key);
  2391.       tab->read_first_record= join_read_always_key;
  2392.       tab->read_record.read_record= join_read_next;
  2393.       if (table->used_keys & ((key_map) 1 << tab->ref.key))
  2394.       {
  2395.     table->key_read=1;
  2396.     table->file->extra(HA_EXTRA_KEYREAD);
  2397.       }
  2398.       break;
  2399.     case JT_FT:
  2400.       table->status=STATUS_NO_RECORD;
  2401.       table->file->index_init(tab->ref.key);
  2402.       tab->read_first_record= join_ft_read_first;
  2403.       tab->read_record.read_record= join_ft_read_next;
  2404.       break;
  2405.     case JT_ALL:
  2406.       /*
  2407.       ** if previous table use cache
  2408.       */
  2409.       table->status=STATUS_NO_RECORD;
  2410.       if (i != join->const_tables && (options & SELECT_USE_CACHE) &&
  2411.       tab->use_quick != 2 && !tab->on_expr)
  2412.       {
  2413.     if ((options & SELECT_DESCRIBE) ||
  2414.         !join_init_cache(join->thd,join->join_tab+join->const_tables,
  2415.                  i-join->const_tables))
  2416.     {
  2417.       tab[-1].next_select=sub_select_cache; /* Patch previous */
  2418.     }
  2419.       }
  2420.       /* These init changes read_record */
  2421.       if (tab->use_quick == 2)
  2422.       {
  2423.     join->thd->lex.options|=OPTION_NO_GOOD_INDEX_USED;
  2424.     tab->read_first_record= join_init_quick_read_record;
  2425.     statistic_increment(select_range_check_count, &LOCK_status);
  2426.       }
  2427.       else
  2428.       {
  2429.     tab->read_first_record= join_init_read_record;
  2430.     if (i == join->const_tables)
  2431.     {
  2432.       if (tab->select && tab->select->quick)
  2433.       {
  2434.         statistic_increment(select_range_count, &LOCK_status);
  2435.       }
  2436.       else
  2437.       {
  2438.         join->thd->lex.options|=OPTION_NO_INDEX_USED;
  2439.         statistic_increment(select_scan_count, &LOCK_status);
  2440.       }
  2441.     }
  2442.     else
  2443.     {
  2444.       if (tab->select && tab->select->quick)
  2445.       {
  2446.         statistic_increment(select_full_range_join_count, &LOCK_status);
  2447.       }
  2448.       else
  2449.       {
  2450.         join->thd->lex.options|=OPTION_NO_INDEX_USED;
  2451.         statistic_increment(select_full_join_count, &LOCK_status);
  2452.       }
  2453.     }
  2454.     if (tab->select && tab->select->quick &&
  2455.         table->used_keys & ((key_map) 1 << tab->select->quick->index))
  2456.     {
  2457.       table->key_read=1;
  2458.       table->file->extra(HA_EXTRA_KEYREAD);
  2459.     }
  2460.     else if (table->used_keys && ! (tab->select && tab->select->quick))
  2461.     {                    // Only read index tree
  2462.       tab->index=find_shortest_key(table, table->used_keys);
  2463.       tab->read_first_record= join_init_read_first_with_key;
  2464.       tab->type=JT_NEXT;        // Read with index_first / index_next
  2465.     }
  2466.       }
  2467.       break;
  2468.     default:
  2469.       DBUG_PRINT("error",("Table type %d found",tab->type)); /* purecov: deadcode */
  2470.       break;                    /* purecov: deadcode */
  2471.     case JT_UNKNOWN:
  2472.     case JT_MAYBE_REF:
  2473.       abort();                    /* purecov: deadcode */
  2474.     }
  2475.   }
  2476.   join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
  2477.   DBUG_VOID_RETURN;
  2478. }
  2479.  
  2480.  
  2481. static void
  2482. join_free(JOIN *join)
  2483. {
  2484.   JOIN_TAB *tab,*end;
  2485.  
  2486.   if (join->table)
  2487.   {
  2488.     /*
  2489.       Only a sorted table may be cached.  This sorted table is always the
  2490.       first non const table in join->table
  2491.     */
  2492.     if (join->tables > join->const_tables) // Test for not-const tables
  2493.       free_io_cache(join->table[join->const_tables]);
  2494.     for (tab=join->join_tab,end=tab+join->tables ; tab != end ; tab++)
  2495.     {
  2496.       delete tab->select;
  2497.       delete tab->quick;
  2498.       x_free(tab->cache.buff);
  2499.       end_read_record(&tab->read_record);
  2500.       if (tab->table)
  2501.       {
  2502.     if (tab->table->key_read)
  2503.     {
  2504.       tab->table->key_read=0;
  2505.       tab->table->file->extra(HA_EXTRA_NO_KEYREAD);
  2506.     }
  2507.     tab->table->file->index_end();
  2508.       }
  2509.     }
  2510.     join->table=0;
  2511.   }
  2512.   // We are not using tables anymore
  2513.   // Unlock all tables. We may be in an INSERT .... SELECT statement.
  2514.   if (join->lock && join->thd->lock)
  2515.   {
  2516.     mysql_unlock_read_tables(join->thd, join->lock);// Don't free join->lock
  2517.     join->lock=0;
  2518.   }
  2519.   join->group_fields.delete_elements();
  2520.   join->tmp_table_param.copy_funcs.delete_elements();
  2521.   delete [] join->tmp_table_param.copy_field;
  2522.   join->tmp_table_param.copy_field=0;
  2523. }
  2524.  
  2525.  
  2526. /*****************************************************************************
  2527. ** Remove the following expressions from ORDER BY and GROUP BY:
  2528. ** Constant expressions
  2529. ** Expression that only uses tables that are of type EQ_REF and the reference
  2530. ** is in the ORDER list or if all refereed tables are of the above type.
  2531. **
  2532. ** In the following, the X field can be removed:
  2533. ** SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t1.a,t2.X
  2534. ** SELECT * FROM t1,t2,t3 WHERE t1.a=t2.a AND t2.b=t3.b ORDER BY t1.a,t3.X
  2535. **
  2536. ** These can't be optimized:
  2537. ** SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.X,t1.a
  2538. ** SELECT * FROM t1,t2 WHERE t1.a=t2.a AND t1.b=t2.b ORDER BY t1.a,t2.c
  2539. ** SELECT * FROM t1,t2 WHERE t1.a=t2.a ORDER BY t2.b,t1.a
  2540. *****************************************************************************/
  2541.  
  2542. static bool
  2543. eq_ref_table(JOIN *join, ORDER *start_order, JOIN_TAB *tab)
  2544. {
  2545.   if (tab->cached_eq_ref_table)            // If cached
  2546.     return tab->eq_ref_table;
  2547.   tab->cached_eq_ref_table=1;
  2548.   if (tab->type == JT_CONST)            // We can skip const tables
  2549.     return (tab->eq_ref_table=1);        /* purecov: inspected */
  2550.   if (tab->type != JT_EQ_REF)
  2551.     return (tab->eq_ref_table=0);        // We must use this
  2552.   Item **ref_item=tab->ref.items;
  2553.   Item **end=ref_item+tab->ref.key_parts;
  2554.   uint found=0;
  2555.   table_map map=tab->table->map;
  2556.  
  2557.   for (; ref_item != end ; ref_item++)
  2558.   {
  2559.     if (! (*ref_item)->const_item())
  2560.     {                        // Not a const ref
  2561.       ORDER *order;
  2562.       for (order=start_order ; order ; order=order->next)
  2563.       {
  2564.     if ((*ref_item)->eq(order->item[0]))
  2565.       break;
  2566.       }
  2567.       if (order)
  2568.       {
  2569.     found++;
  2570.     dbug_assert(!(order->used & map));
  2571.     order->used|=map;
  2572.     continue;                // Used in ORDER BY
  2573.       }
  2574.       if (!only_eq_ref_tables(join,start_order, (*ref_item)->used_tables()))
  2575.     return (tab->eq_ref_table=0);
  2576.     }
  2577.   }
  2578.   /* Check that there was no reference to table before sort order */
  2579.   for ( ; found && start_order ; start_order=start_order->next)
  2580.   {
  2581.     if (start_order->used & map)
  2582.     {
  2583.       found--;
  2584.       continue;
  2585.     }
  2586.     if (start_order->depend_map & map)
  2587.       return (tab->eq_ref_table=0);
  2588.   }
  2589.   return tab->eq_ref_table=1;
  2590. }
  2591.  
  2592.  
  2593. static bool
  2594. only_eq_ref_tables(JOIN *join,ORDER *order,table_map tables)
  2595. {
  2596.   if (specialflag &  SPECIAL_SAFE_MODE)
  2597.     return 0;                    // skip this optimize /* purecov: inspected */
  2598.   for (JOIN_TAB **tab=join->map2table ; tables ; tab++, tables>>=1)
  2599.   {
  2600.     if (tables & 1 && !eq_ref_table(join, order, *tab))
  2601.       return 0;
  2602.   }
  2603.   return 1;
  2604. }
  2605.  
  2606.  
  2607. /* Update the dependency map for the tables */
  2608.  
  2609. static void update_depend_map(JOIN *join)
  2610. {
  2611.   JOIN_TAB *join_tab=join->join_tab, *end=join_tab+join->tables;
  2612.  
  2613.   for ( ; join_tab != end ; join_tab++)
  2614.   {
  2615.     TABLE_REF *ref= &join_tab->ref;
  2616.     table_map depend_map=0;
  2617.     Item **item=ref->items;
  2618.     uint i;
  2619.     for (i=0 ; i < ref->key_parts ; i++,item++)
  2620.       depend_map|=(*item)->used_tables();
  2621.     ref->depend_map=depend_map;
  2622.     for (JOIN_TAB *join_tab2=join->join_tab;
  2623.      depend_map ;
  2624.      join_tab2++,depend_map>>=1 )
  2625.     {
  2626.       if (depend_map & 1)
  2627.     ref->depend_map|=join_tab2->ref.depend_map;
  2628.     }
  2629.   }
  2630. }
  2631.  
  2632.  
  2633. /* Update the dependency map for the sort order */
  2634.  
  2635. static void update_depend_map(JOIN *join, ORDER *order)
  2636. {
  2637.   for ( ; order ; order=order->next)
  2638.   {
  2639.     table_map depend_map;
  2640.     order->item[0]->update_used_tables();
  2641.     order->depend_map=depend_map=order->item[0]->used_tables();
  2642.     if (!(order->depend_map & RAND_TABLE_BIT))    // Not item_sum() or RAND()
  2643.     {
  2644.       for (JOIN_TAB *join_tab=join->join_tab;
  2645.        depend_map ;
  2646.        join_tab++, depend_map>>=1)
  2647.       {
  2648.     if (depend_map & 1)
  2649.       order->depend_map|=join_tab->ref.depend_map;
  2650.       }
  2651.     }
  2652.   }
  2653. }
  2654.  
  2655.  
  2656. /*
  2657. **  simple_order is set to 1 if sort_order only uses fields from head table
  2658. **  and the head table is not a LEFT JOIN table
  2659. */
  2660.  
  2661. static ORDER *
  2662. remove_const(JOIN *join,ORDER *first_order, COND *cond, bool *simple_order)
  2663. {
  2664.   if (join->tables == join->const_tables)
  2665.     return 0;                    // No need to sort
  2666.   DBUG_ENTER("remove_const");
  2667.   ORDER *order,**prev_ptr;
  2668.   table_map first_table= join->join_tab[join->const_tables].table->map;
  2669.   table_map not_const_tables= ~join->const_table_map;
  2670.   table_map ref;
  2671.   prev_ptr= &first_order;
  2672.   *simple_order= join->join_tab[join->const_tables].on_expr ? 0 : 1;
  2673.  
  2674.   /* NOTE: A variable of not_const_tables ^ first_table; breaks gcc 2.7 */
  2675.  
  2676.   update_depend_map(join, first_order);
  2677.   for (order=first_order; order ; order=order->next)
  2678.   {
  2679.     table_map order_tables=order->item[0]->used_tables();
  2680.     if (order->item[0]->with_sum_func)
  2681.       *simple_order=0;                // Must do a temp table to sort
  2682.     else if (!(order_tables & not_const_tables))
  2683.     {
  2684.       DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
  2685.       continue;                    // skipp const item
  2686.     }
  2687.     else
  2688.     {
  2689.       if (order_tables & RAND_TABLE_BIT)
  2690.     *simple_order=0;
  2691.       else
  2692.       {
  2693.     Item *comp_item=0;
  2694.     if (cond && const_expression_in_where(cond,order->item[0], &comp_item))
  2695.     {
  2696.       DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
  2697.       continue;
  2698.     }
  2699.     if ((ref=order_tables & (not_const_tables ^ first_table)))
  2700.     {
  2701.       if (only_eq_ref_tables(join,first_order,ref))
  2702.       {
  2703.         DBUG_PRINT("info",("removing: %s", order->item[0]->full_name()));
  2704.         continue;
  2705.       }
  2706.       *simple_order=0;            // Must do a temp table to sort
  2707.     }
  2708.       }
  2709.     }
  2710.     *prev_ptr= order;                // use this entry
  2711.     prev_ptr= &order->next;
  2712.   }
  2713.   *prev_ptr=0;
  2714.   if (!first_order)                // Nothing to sort/group
  2715.     *simple_order=1;
  2716.   DBUG_PRINT("exit",("simple_order: %d",(int) *simple_order));
  2717.   DBUG_RETURN(first_order);
  2718. }
  2719.  
  2720. static int
  2721. return_zero_rows(select_result *result,TABLE_LIST *tables,List<Item> &fields,
  2722.          bool send_row, uint select_options,const char *info,
  2723.          Item *having, Procedure *procedure)
  2724. {
  2725.   DBUG_ENTER("return_zero_rows");
  2726.  
  2727.   if (select_options & SELECT_DESCRIBE)
  2728.   {
  2729.     describe_info(info);
  2730.     DBUG_RETURN(0);
  2731.   }
  2732.   if (procedure)
  2733.   {
  2734.     if (result->prepare(fields))        // This hasn't been done yet
  2735.       DBUG_RETURN(-1);
  2736.   }
  2737.   if (send_row)
  2738.   {
  2739.     for (TABLE_LIST *table=tables; table ; table=table->next)
  2740.       mark_as_null_row(table->table);        // All fields are NULL
  2741.     if (having && having->val_int() == 0)
  2742.       send_row=0;
  2743.   }
  2744.   if (!tables || !(result->send_fields(fields,1)))
  2745.   {
  2746.     if (send_row)
  2747.       result->send_data(fields);
  2748.     if (tables)                    // Not from do_select()
  2749.       result->send_eof();            // Should be safe
  2750.   }
  2751.   DBUG_RETURN(0);
  2752. }
  2753.  
  2754.  
  2755. static void clear_tables(JOIN *join)
  2756. {
  2757.   for (uint i=0 ; i < join->tables ; i++)
  2758.     mark_as_null_row(join->table[i]);        // All fields are NULL
  2759. }
  2760.  
  2761. /*****************************************************************************
  2762. ** Make som simple condition optimization:
  2763. ** If there is a test 'field = const' change all refs to 'field' to 'const'
  2764. ** Remove all dummy tests 'item = item', 'const op const'.
  2765. ** Remove all 'item is NULL', when item can never be null!
  2766. ** item->marker should be 0 for all items on entry
  2767. ** Return in cond_value FALSE if condition is impossible (1 = 2)
  2768. *****************************************************************************/
  2769.  
  2770. class COND_CMP :public ilink {
  2771. public:
  2772.   static void *operator new(size_t size) {return (void*) sql_alloc((uint) size); }
  2773.   static void operator delete(void *ptr __attribute__((unused)),
  2774.                   size_t size __attribute__((unused))) {} /*lint -e715 */
  2775.  
  2776.   Item *and_level;
  2777.   Item_func *cmp_func;
  2778.   COND_CMP(Item *a,Item_func *b) :and_level(a),cmp_func(b) {}
  2779. };
  2780.  
  2781. #ifdef __GNUC__
  2782. template class I_List<COND_CMP>;
  2783. template class I_List_iterator<COND_CMP>;
  2784. template class List<Item_func_match>;
  2785. template class List_iterator<Item_func_match>;
  2786. #endif
  2787.  
  2788. /*
  2789. ** change field = field to field = const for each found field = const in the
  2790. ** and_level
  2791. */
  2792.  
  2793. static void
  2794. change_cond_ref_to_const(I_List<COND_CMP> *save_list,Item *and_father,
  2795.              Item *cond, Item *field, Item *value)
  2796. {
  2797.   if (cond->type() == Item::COND_ITEM)
  2798.   {
  2799.     bool and_level= ((Item_cond*) cond)->functype() ==
  2800.       Item_func::COND_AND_FUNC;
  2801.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  2802.     Item *item;
  2803.     while ((item=li++))
  2804.       change_cond_ref_to_const(save_list,and_level ? cond : item, item,
  2805.                    field, value);
  2806.     return;
  2807.   }
  2808.   if (cond->eq_cmp_result() == Item::COND_OK)
  2809.     return;                    // Not a boolean function
  2810.  
  2811.   Item_bool_func2 *func=  (Item_bool_func2*) cond;
  2812.   Item *left_item=  func->arguments()[0];
  2813.   Item *right_item= func->arguments()[1];
  2814.   Item_func::Functype functype=  func->functype();
  2815.  
  2816.   if (right_item->eq(field) && left_item != value)
  2817.   {
  2818.     Item *tmp=value->new_item();
  2819.     if (tmp)
  2820.     {
  2821.       func->arguments()[1] = tmp;
  2822.       func->update_used_tables();
  2823.       if ((functype == Item_func::EQ_FUNC || functype == Item_func::EQUAL_FUNC)
  2824.       && and_father != cond && !left_item->const_item())
  2825.       {
  2826.     cond->marker=1;
  2827.     COND_CMP *tmp2;
  2828.     if ((tmp2=new COND_CMP(and_father,func)))
  2829.       save_list->push_back(tmp2);
  2830.       }
  2831.       func->set_cmp_func(item_cmp_type(func->arguments()[0]->result_type(),
  2832.                        func->arguments()[1]->result_type()));
  2833.     }
  2834.   }
  2835.   else if (left_item->eq(field) && right_item != value)
  2836.   {
  2837.     Item *tmp=value->new_item();
  2838.     if (tmp)
  2839.     {
  2840.       func->arguments()[0] = value = tmp;
  2841.       func->update_used_tables();
  2842.       if ((functype == Item_func::EQ_FUNC || functype == Item_func::EQUAL_FUNC)
  2843.       && and_father != cond && !right_item->const_item())
  2844.       {
  2845.     func->arguments()[0] = func->arguments()[1]; // For easy check
  2846.     func->arguments()[1] = value;
  2847.     cond->marker=1;
  2848.     COND_CMP *tmp2;
  2849.     if ((tmp2=new COND_CMP(and_father,func)))
  2850.       save_list->push_back(tmp2);
  2851.       }
  2852.       func->set_cmp_func(item_cmp_type(func->arguments()[0]->result_type(),
  2853.                        func->arguments()[1]->result_type()));
  2854.     }
  2855.   }
  2856. }
  2857.  
  2858.  
  2859. static void
  2860. propagate_cond_constants(I_List<COND_CMP> *save_list,COND *and_level,
  2861.              COND *cond)
  2862. {
  2863.   if (cond->type() == Item::COND_ITEM)
  2864.   {
  2865.     bool and_level= ((Item_cond*) cond)->functype() ==
  2866.       Item_func::COND_AND_FUNC;
  2867.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  2868.     Item *item;
  2869.     I_List<COND_CMP> save;
  2870.     while ((item=li++))
  2871.     {
  2872.       propagate_cond_constants(&save,and_level ? cond : item, item);
  2873.     }
  2874.     if (and_level)
  2875.     {                        // Handle other found items
  2876.       I_List_iterator<COND_CMP> cond_itr(save);
  2877.       COND_CMP *cond_cmp;
  2878.       while ((cond_cmp=cond_itr++))
  2879.     if (!cond_cmp->cmp_func->arguments()[0]->const_item())
  2880.       change_cond_ref_to_const(&save,cond_cmp->and_level,
  2881.                    cond_cmp->and_level,
  2882.                    cond_cmp->cmp_func->arguments()[0],
  2883.                    cond_cmp->cmp_func->arguments()[1]);
  2884.     }
  2885.   }
  2886.   else if (and_level != cond && !cond->marker)        // In a AND group
  2887.   {
  2888.     if (cond->type() == Item::FUNC_ITEM &&
  2889.     (((Item_func*) cond)->functype() == Item_func::EQ_FUNC ||
  2890.      ((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC))
  2891.     {
  2892.       Item_func_eq *func=(Item_func_eq*) cond;
  2893.       bool left_const= func->arguments()[0]->const_item();
  2894.       bool right_const=func->arguments()[1]->const_item();
  2895.       if (!(left_const && right_const))
  2896.       {
  2897.     if (right_const)
  2898.     {
  2899.       func->arguments()[1]=resolve_const_item(func->arguments()[1],
  2900.                           func->arguments()[0]);
  2901.       func->update_used_tables();
  2902.       change_cond_ref_to_const(save_list,and_level,and_level,
  2903.                    func->arguments()[0],
  2904.                    func->arguments()[1]);
  2905.     }
  2906.     else if (left_const)
  2907.     {
  2908.       func->arguments()[0]=resolve_const_item(func->arguments()[0],
  2909.                           func->arguments()[1]);
  2910.       func->update_used_tables();
  2911.       change_cond_ref_to_const(save_list,and_level,and_level,
  2912.                    func->arguments()[1],
  2913.                    func->arguments()[0]);
  2914.     }
  2915.       }
  2916.     }
  2917.   }
  2918. }
  2919.  
  2920.  
  2921. static COND *
  2922. optimize_cond(COND *conds,Item::cond_result *cond_value)
  2923. {
  2924.   if (!conds)
  2925.   {
  2926.     *cond_value= Item::COND_TRUE;
  2927.     return conds;
  2928.   }
  2929.   /* change field = field to field = const for each found field = const */
  2930.   DBUG_EXECUTE("where",print_where(conds,"original"););
  2931.   propagate_cond_constants((I_List<COND_CMP> *) 0,conds,conds);
  2932.   /*
  2933.   ** Remove all instances of item == item
  2934.   ** Remove all and-levels where CONST item != CONST item
  2935.   */
  2936.   DBUG_EXECUTE("where",print_where(conds,"after const change"););
  2937.   conds=remove_eq_conds(conds,cond_value) ;
  2938.   DBUG_EXECUTE("info",print_where(conds,"after remove"););
  2939.   return conds;
  2940. }
  2941.  
  2942.  
  2943. /*
  2944. ** remove const and eq items. Return new item, or NULL if no condition
  2945. ** cond_value is set to according:
  2946. ** COND_OK    query is possible (field = constant)
  2947. ** COND_TRUE  always true    ( 1 = 1 )
  2948. ** COND_FALSE always false    ( 1 = 2 )
  2949. */
  2950.  
  2951. static COND *
  2952. remove_eq_conds(COND *cond,Item::cond_result *cond_value)
  2953. {
  2954.   if (cond->type() == Item::COND_ITEM)
  2955.   {
  2956.     bool and_level= ((Item_cond*) cond)->functype()
  2957.       == Item_func::COND_AND_FUNC;
  2958.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  2959.     Item::cond_result tmp_cond_value;
  2960.  
  2961.     *cond_value=Item::COND_UNDEF;
  2962.     Item *item;
  2963.     while ((item=li++))
  2964.     {
  2965.       Item *new_item=remove_eq_conds(item,&tmp_cond_value);
  2966.       if (!new_item)
  2967.       {
  2968. #ifdef DELETE_ITEMS
  2969.     delete item;                // This may be shared
  2970. #endif
  2971.     li.remove();
  2972.       }
  2973.       else if (item != new_item)
  2974.       {
  2975. #ifdef DELETE_ITEMS
  2976.     delete item;                // This may be shared
  2977. #endif
  2978.     VOID(li.replace(new_item));
  2979.       }
  2980.       if (*cond_value == Item::COND_UNDEF)
  2981.     *cond_value=tmp_cond_value;
  2982.       switch (tmp_cond_value) {
  2983.       case Item::COND_OK:            // Not TRUE or FALSE
  2984.     if (and_level || *cond_value == Item::COND_FALSE)
  2985.       *cond_value=tmp_cond_value;
  2986.     break;
  2987.       case Item::COND_FALSE:
  2988.     if (and_level)
  2989.     {
  2990.       *cond_value=tmp_cond_value;
  2991.       return (COND*) 0;            // Always false
  2992.     }
  2993.     break;
  2994.       case Item::COND_TRUE:
  2995.     if (!and_level)
  2996.     {
  2997.       *cond_value= tmp_cond_value;
  2998.       return (COND*) 0;            // Always true
  2999.     }
  3000.     break;
  3001.       case Item::COND_UNDEF:            // Impossible
  3002.     break; /* purecov: deadcode */
  3003.       }
  3004.     }
  3005.     if (!((Item_cond*) cond)->argument_list()->elements ||
  3006.     *cond_value != Item::COND_OK)
  3007.       return (COND*) 0;
  3008.     if (((Item_cond*) cond)->argument_list()->elements == 1)
  3009.     {                        // Remove list
  3010.       item= ((Item_cond*) cond)->argument_list()->head();
  3011.       ((Item_cond*) cond)->argument_list()->empty();
  3012.       return item;
  3013.     }
  3014.   }
  3015.   else if (cond->type() == Item::FUNC_ITEM &&
  3016.        ((Item_func*) cond)->functype() == Item_func::ISNULL_FUNC)
  3017.   {
  3018.     /*
  3019.     ** Handles this special case for some ODBC applications:
  3020.     ** The are requesting the row that was just updated with a auto_increment
  3021.     ** value with this construct:
  3022.     **
  3023.     ** SELECT * from table_name where auto_increment_column IS NULL
  3024.     ** This will be changed to:
  3025.     ** SELECT * from table_name where auto_increment_column = LAST_INSERT_ID
  3026.     */
  3027.  
  3028.     Item_func_isnull *func=(Item_func_isnull*) cond;
  3029.     Item **args= func->arguments();
  3030.     THD *thd=current_thd;
  3031.     if (args[0]->type() == Item::FIELD_ITEM)
  3032.     {
  3033.       Field *field=((Item_field*) args[0])->field;
  3034.       if (field->flags & AUTO_INCREMENT_FLAG && !field->table->maybe_null &&
  3035.       (thd->options & OPTION_AUTO_IS_NULL) &&
  3036.       thd->insert_id())
  3037.       {
  3038.     COND *new_cond;
  3039.     if ((new_cond= new Item_func_eq(args[0],
  3040.                     new Item_int("last_insert_id()",
  3041.                              thd->insert_id(),
  3042.                              21))))
  3043.     {
  3044.       cond=new_cond;
  3045.       cond->fix_fields(thd,0);
  3046.     }
  3047.     thd->insert_id(0);        // Clear for next request
  3048.       }
  3049.       /* fix to replace 'NULL' dates with '0' (shreeve@uci.edu) */
  3050.       else if (((field->type() == FIELD_TYPE_DATE) ||
  3051.         (field->type() == FIELD_TYPE_DATETIME)) &&
  3052.         (field->flags & NOT_NULL_FLAG))
  3053.       {
  3054.     COND *new_cond;
  3055.     if ((new_cond= new Item_func_eq(args[0],new Item_int("0", 0, 2))))
  3056.     {
  3057.       cond=new_cond;
  3058.       cond->fix_fields(thd,0);
  3059.     }
  3060.       }
  3061.     }
  3062.   }
  3063.   else if (cond->const_item())
  3064.   {
  3065.     *cond_value= eval_const_cond(cond) ? Item::COND_TRUE : Item::COND_FALSE;
  3066.     return (COND*) 0;
  3067.   }
  3068.   else if ((*cond_value= cond->eq_cmp_result()) != Item::COND_OK)
  3069.   {                        // boolan compare function
  3070.     Item *left_item=    ((Item_func*) cond)->arguments()[0];
  3071.     Item *right_item= ((Item_func*) cond)->arguments()[1];
  3072.     if (left_item->eq(right_item))
  3073.     {
  3074.       if (!left_item->maybe_null ||
  3075.       ((Item_func*) cond)->functype() == Item_func::EQUAL_FUNC)
  3076.     return (COND*) 0;            // Compare of identical items
  3077.     }
  3078.   }
  3079.   *cond_value=Item::COND_OK;
  3080.   return cond;                /* Point at next and level */
  3081. }
  3082.  
  3083. /*
  3084. ** Return 1 if the item is a const value in all the WHERE clause
  3085. */
  3086.  
  3087. static bool
  3088. const_expression_in_where(COND *cond, Item *comp_item, Item **const_item)
  3089. {
  3090.   if (cond->type() == Item::COND_ITEM)
  3091.   {
  3092.     bool and_level= (((Item_cond*) cond)->functype()
  3093.              == Item_func::COND_AND_FUNC);
  3094.     List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  3095.     Item *item;
  3096.     while ((item=li++))
  3097.     {
  3098.       bool res=const_expression_in_where(item, comp_item, const_item);
  3099.       if (res)                    // Is a const value
  3100.       {
  3101.     if (and_level)
  3102.       return 1;
  3103.       }
  3104.       else if (!and_level)
  3105.     return 0;
  3106.     }
  3107.     return and_level ? 0 : 1;
  3108.   }
  3109.   else if (cond->eq_cmp_result() != Item::COND_OK)
  3110.   {                        // boolan compare function
  3111.     Item_func* func= (Item_func*) cond;
  3112.     if (func->functype() != Item_func::EQUAL_FUNC &&
  3113.     func->functype() != Item_func::EQ_FUNC)
  3114.       return 0;
  3115.     Item *left_item=    ((Item_func*) cond)->arguments()[0];
  3116.     Item *right_item= ((Item_func*) cond)->arguments()[1];
  3117.     if (left_item->eq(comp_item))
  3118.     {
  3119.       if (right_item->const_item())
  3120.       {
  3121.     if (*const_item)
  3122.       return right_item->eq(*const_item);
  3123.     *const_item=right_item;
  3124.     return 1;
  3125.       }
  3126.     }
  3127.     else if (right_item->eq(comp_item))
  3128.     {
  3129.       if (left_item->const_item())
  3130.       {
  3131.     if (*const_item)
  3132.       return left_item->eq(*const_item);
  3133.     *const_item=left_item;
  3134.     return 1;
  3135.       }
  3136.     }
  3137.   }
  3138.   return 0;
  3139. }
  3140.  
  3141.  
  3142. /****************************************************************************
  3143. **    Create a temp table according to a field list.
  3144. **    Set distinct if duplicates could be removed
  3145. **    Given fields field pointers are changed to point at tmp_table
  3146. **    for send_fields
  3147. ****************************************************************************/
  3148.  
  3149. Field *create_tmp_field(TABLE *table,Item *item, Item::Type type,
  3150.             Item_result_field ***copy_func, Field **from_field,
  3151.             bool group, bool modify_item)
  3152. {
  3153.   switch (type) {
  3154.   case Item::SUM_FUNC_ITEM:
  3155.   {
  3156.     Item_sum *item_sum=(Item_sum*) item;
  3157.     bool maybe_null=item_sum->maybe_null;
  3158.     switch (item_sum->sum_func()) {
  3159.     case Item_sum::AVG_FUNC:            /* Place for sum & count */
  3160.       if (group)
  3161.     return new Field_string(sizeof(double)+sizeof(longlong),
  3162.                 maybe_null, item->name,table,1);
  3163.       else
  3164.     return new Field_double(item_sum->max_length,maybe_null,
  3165.                 item->name, table, item_sum->decimals);
  3166.     case Item_sum::STD_FUNC:            /* Place for sum & count */
  3167.       if (group)
  3168.     return    new Field_string(sizeof(double)*2+sizeof(longlong),
  3169.                  maybe_null, item->name,table,1);
  3170.       else
  3171.     return new Field_double(item_sum->max_length, maybe_null,
  3172.                 item->name,table,item_sum->decimals);
  3173.     case Item_sum::UNIQUE_USERS_FUNC:
  3174.       return new Field_long(9,maybe_null,item->name,table,1);
  3175.     default:
  3176.       switch (item_sum->result_type()) {
  3177.       case REAL_RESULT:
  3178.     return new Field_double(item_sum->max_length,maybe_null,
  3179.                 item->name,table,item_sum->decimals);
  3180.       case INT_RESULT:
  3181.     return new Field_longlong(item_sum->max_length,maybe_null,
  3182.                   item->name,table);
  3183.       case STRING_RESULT:
  3184.     if (item_sum->max_length > 255)
  3185.       return  new Field_blob(item_sum->max_length,maybe_null,
  3186.                  item->name,table,item->binary);
  3187.     return    new Field_string(item_sum->max_length,maybe_null,
  3188.                  item->name,table,item->binary);
  3189.       }
  3190.     }
  3191.     current_thd->fatal_error=1;
  3192.     return 0;                    // Error
  3193.   }
  3194.   case Item::FIELD_ITEM:
  3195.   {
  3196.     Field *org_field=((Item_field*) item)->field,*new_field;
  3197.  
  3198.     *from_field=org_field;
  3199.     if ((new_field= org_field->new_field(table))) // Should always be true
  3200.     {
  3201.       if (modify_item)
  3202.     ((Item_field*) item)->result_field= new_field;
  3203.       else
  3204.     new_field->field_name=item->name;
  3205.       if (org_field->maybe_null())
  3206.     new_field->flags&= ~NOT_NULL_FLAG;    // Because of outer join
  3207.     }
  3208.     return new_field;
  3209.   }
  3210.   case Item::PROC_ITEM:
  3211.   case Item::FUNC_ITEM:
  3212.   case Item::COND_ITEM:
  3213.   case Item::FIELD_AVG_ITEM:
  3214.   case Item::FIELD_STD_ITEM:
  3215.     /* The following can only happen with 'CREATE TABLE ... SELECT' */
  3216.   case Item::INT_ITEM:
  3217.   case Item::REAL_ITEM:
  3218.   case Item::STRING_ITEM:
  3219.   case Item::REF_ITEM:
  3220.   case Item::NULL_ITEM:
  3221.   {
  3222.     bool maybe_null=item->maybe_null;
  3223.     Field *new_field;
  3224.     LINT_INIT(new_field);
  3225.  
  3226.     switch (item->result_type()) {
  3227.     case REAL_RESULT:
  3228.       new_field=new Field_double(item->max_length,maybe_null,
  3229.                  item->name,table,item->decimals);
  3230.       break;
  3231.     case INT_RESULT:
  3232.       new_field=new Field_longlong(item->max_length,maybe_null,
  3233.                    item->name,table);
  3234.       break;
  3235.     case STRING_RESULT:
  3236.       if (item->max_length > 255)
  3237.     new_field=  new Field_blob(item->max_length,maybe_null,
  3238.                    item->name,table,item->binary);
  3239.       else
  3240.     new_field= new Field_string(item->max_length,maybe_null,
  3241.                     item->name,table,item->binary);
  3242.       break;
  3243.     }
  3244.     if (copy_func)
  3245.       *((*copy_func)++) = (Item_result_field*) item; // Save for copy_funcs
  3246.     if (modify_item)
  3247.       ((Item_result_field*) item)->result_field=new_field;
  3248.     return new_field;
  3249.   }
  3250.   default:                    // Dosen't have to be stored
  3251.     return 0;
  3252.   }
  3253. }
  3254.  
  3255.  
  3256. TABLE *
  3257. create_tmp_table(THD *thd,TMP_TABLE_PARAM *param,List<Item> &fields,
  3258.          ORDER *group, bool distinct, bool save_sum_fields,
  3259.          bool allow_distinct_limit, uint select_options)
  3260. {
  3261.   TABLE *table;
  3262.   uint    i,field_count,reclength,null_count,null_pack_length,
  3263.     blob_count,group_null_items;
  3264.   bool    using_unique_constraint=0;
  3265.   char    *tmpname,path[FN_REFLEN];
  3266.   byte    *pos,*group_buff;
  3267.   uchar *null_flags;
  3268.   Field **reg_field,**from_field;
  3269.   Copy_field *copy=0;
  3270.   KEY *keyinfo;
  3271.   KEY_PART_INFO *key_part_info;
  3272.   Item_result_field **copy_func;
  3273.   MI_COLUMNDEF *recinfo;
  3274.   DBUG_ENTER("create_tmp_table");
  3275.   DBUG_PRINT("enter",("distinct: %d  save_sum_fields: %d  allow_distinct_limit: %d  group: %d",
  3276.               (int) distinct, (int) save_sum_fields,
  3277.               (int) allow_distinct_limit,test(group)));
  3278.  
  3279.   statistic_increment(created_tmp_tables, &LOCK_status);
  3280.   sprintf(path,"%s%s%lx_%lx_%x",mysql_tmpdir,tmp_file_prefix,current_pid,
  3281.       thd->thread_id, thd->tmp_table++);
  3282.   if (group)
  3283.   {
  3284.     if (!param->quick_group)
  3285.       group=0;                    // Can't use group key
  3286.     else for (ORDER *tmp=group ; tmp ; tmp=tmp->next)
  3287.       (*tmp->item)->marker=4;            // Store null in key
  3288.     if (param->group_length >= MAX_BLOB_WIDTH)
  3289.       using_unique_constraint=1;
  3290.   }
  3291.  
  3292.   field_count=param->field_count+param->func_count+param->sum_func_count;
  3293.   if (!my_multi_malloc(MYF(MY_WME),
  3294.                &table,sizeof(*table),
  3295.                ®_field,sizeof(Field*)*(field_count+1),
  3296.                &from_field,sizeof(Field*)*field_count,
  3297.                ©_func,sizeof(*copy_func)*(param->func_count+1),
  3298.                ¶m->keyinfo,sizeof(*param->keyinfo),
  3299.                &key_part_info,
  3300.                sizeof(*key_part_info)*(param->group_parts+1),
  3301.                ¶m->start_recinfo,
  3302.                sizeof(*param->recinfo)*(field_count*2+4),
  3303.                &tmpname,(uint) strlen(path)+1,
  3304.                &group_buff,group && ! using_unique_constraint ?
  3305.                param->group_length : 0,
  3306.                NullS))
  3307.   {
  3308.     DBUG_RETURN(NULL); /* purecov: inspected */
  3309.   }
  3310.   if (!(param->copy_field=copy=new Copy_field[field_count]))
  3311.   {
  3312.     my_free((gptr) table,MYF(0)); /* purecov: inspected */
  3313.     DBUG_RETURN(NULL); /* purecov: inspected */
  3314.   }
  3315.   param->funcs=copy_func;
  3316.   strmov(tmpname,path);
  3317.   /* make table according to fields */
  3318.  
  3319.   bzero((char*) table,sizeof(*table));
  3320.   bzero((char*) reg_field,sizeof(Field*)*(field_count+1));
  3321.   bzero((char*) from_field,sizeof(Field*)*field_count);
  3322.   table->field=reg_field;
  3323.   table->real_name=table->path=tmpname;
  3324.   table->table_name=base_name(tmpname);
  3325.   table->reginfo.lock_type=TL_WRITE;    /* Will be updated */
  3326.   table->db_stat=HA_OPEN_KEYFILE+HA_OPEN_RNDFILE;
  3327.   table->blob_ptr_size=mi_portable_sizeof_char_ptr;
  3328.   table->map=1;
  3329.   table->tmp_table=1;
  3330.   table->db_low_byte_first=1;            // True for HEAP and MyISAM
  3331.  
  3332.   /* Calculate with type of fields we will need in heap table */
  3333.  
  3334.   reclength=blob_count=null_count=group_null_items=0;
  3335.  
  3336.   List_iterator<Item> li(fields);
  3337.   Item *item;
  3338.   Field **tmp_from_field=from_field;
  3339.   while ((item=li++))
  3340.   {
  3341.     Item::Type type=item->type();
  3342.     if (item->with_sum_func && type != Item::SUM_FUNC_ITEM ||
  3343.     item->const_item())
  3344.       continue;
  3345.     if (type == Item::SUM_FUNC_ITEM && !group && !save_sum_fields)
  3346.     {                        /* Can't calc group yet */
  3347.       ((Item_sum*) item)->result_field=0;
  3348.       for (i=0 ; i < ((Item_sum*) item)->arg_count ; i++)
  3349.       {
  3350.     Item *arg= ((Item_sum*) item)->args[i];
  3351.     if (!arg->const_item())
  3352.     {
  3353.       Field *new_field=
  3354.         create_tmp_field(table,arg,arg->type(),©_func,tmp_from_field,
  3355.                  group != 0,1);
  3356.       if (!new_field)
  3357.         goto err;                    // Should be OOM
  3358.       tmp_from_field++;
  3359.       *(reg_field++)= new_field;
  3360.       reclength+=new_field->pack_length();
  3361.       if (!(new_field->flags & NOT_NULL_FLAG))
  3362.         null_count++;
  3363.       if (new_field->flags & BLOB_FLAG)
  3364.         blob_count++;
  3365.       ((Item_sum*) item)->args[i]= new Item_field(new_field);
  3366.     }
  3367.       }
  3368.     }
  3369.     else
  3370.     {
  3371.       Field *new_field=create_tmp_field(table,item,type,©_func,
  3372.                     tmp_from_field, group != 0,1);
  3373.       if (!new_field)
  3374.       {
  3375.     if (thd->fatal_error)
  3376.       goto err;                // Got OOM
  3377.     continue;                // Some kindf of const item
  3378.       }
  3379.       if (type == Item::SUM_FUNC_ITEM)
  3380.     ((Item_sum *) item)->result_field= new_field;
  3381.       tmp_from_field++;
  3382.       reclength+=new_field->pack_length();
  3383.       if (!(new_field->flags & NOT_NULL_FLAG))
  3384.     null_count++;
  3385.       if (new_field->flags & BLOB_FLAG)
  3386.     blob_count++;
  3387.       if (item->marker == 4 && item->maybe_null)
  3388.       {
  3389.     group_null_items++;
  3390.     new_field->flags|= GROUP_FLAG;
  3391.       }
  3392.       *(reg_field++) =new_field;
  3393.     }
  3394.   }
  3395.   field_count= (uint) (reg_field - table->field);
  3396.  
  3397.   /* If result table is small; use a heap */
  3398.   if (blob_count || using_unique_constraint ||
  3399.       (select_options & (OPTION_BIG_TABLES | SELECT_SMALL_RESULT)) ==
  3400.       OPTION_BIG_TABLES)
  3401.   {
  3402.     table->file=get_new_handler(table,table->db_type=DB_TYPE_MYISAM);
  3403.     if (group &&
  3404.     (param->group_parts > table->file->max_key_parts() ||
  3405.      param->group_length > table->file->max_key_length()))
  3406.       using_unique_constraint=1;
  3407.   }
  3408.   else
  3409.   {
  3410.     table->file=get_new_handler(table,table->db_type=DB_TYPE_HEAP);
  3411.   }
  3412.  
  3413.   if (!using_unique_constraint)
  3414.     reclength+= group_null_items;    // null flag is stored separately
  3415.  
  3416.   table->blob_fields=blob_count;
  3417.   if (blob_count == 0)
  3418.     null_count++;                // For delete link
  3419.   reclength+=(null_pack_length=(null_count+7)/8);
  3420.   if (!reclength)
  3421.     reclength=1;                // Dummy select
  3422.  
  3423.   table->fields=field_count;
  3424.   table->reclength=reclength;
  3425.   {
  3426.     uint alloc_length=ALIGN_SIZE(reclength+MI_UNIQUE_HASH_LENGTH+1);
  3427.     table->rec_buff_length=alloc_length;
  3428.     if (!(table->record[0]= (byte *) my_malloc(alloc_length*3, MYF(MY_WME))))
  3429.       goto err;
  3430.     table->record[1]= table->record[0]+alloc_length;
  3431.     table->record[2]= table->record[1]+alloc_length;
  3432.   }
  3433.   copy_func[0]=0;                // End marker
  3434.  
  3435.   recinfo=param->start_recinfo;
  3436.   null_flags=(uchar*) table->record[0];
  3437.   pos=table->record[0]+ null_pack_length;
  3438.   if (null_pack_length)
  3439.   {
  3440.     bzero((byte*) recinfo,sizeof(*recinfo));
  3441.     recinfo->type=FIELD_NORMAL;
  3442.     recinfo->length=null_pack_length;
  3443.     recinfo++;
  3444.     bfill(null_flags,null_pack_length,255);    // Set null fields
  3445.   }
  3446.   null_count= (blob_count == 0) ? 1 : 0;
  3447.   for (i=0,reg_field=table->field; i < field_count; i++,reg_field++,recinfo++)
  3448.   {
  3449.     Field *field= *reg_field;
  3450.     uint length;
  3451.     bzero((byte*) recinfo,sizeof(*recinfo));
  3452.  
  3453.     if (!(field->flags & NOT_NULL_FLAG))
  3454.     {
  3455.       if (field->flags & GROUP_FLAG && !using_unique_constraint)
  3456.       {
  3457.     *pos++=0;                // Null is stored here
  3458.     recinfo->length=1;
  3459.     recinfo->type=FIELD_NORMAL;
  3460.     recinfo++;
  3461.     bzero((byte*) recinfo,sizeof(*recinfo));
  3462.       }
  3463.       else
  3464.       {
  3465.     recinfo->null_bit= 1 << (null_count & 7);
  3466.     recinfo->null_pos= null_count/8;
  3467.       }
  3468.       field->move_field((char*) pos,null_flags+null_count/8,
  3469.             1 << (null_count & 7));
  3470.       null_count++;
  3471.     }
  3472.     else
  3473.       field->move_field((char*) pos,(uchar*) 0,0);
  3474.     field->reset();
  3475.     if (from_field[i])
  3476.     {                        /* Not a table Item */
  3477.       copy->set(field,from_field[i],save_sum_fields);
  3478.       copy++;
  3479.     }
  3480.     length=field->pack_length();
  3481.     pos+= length;
  3482.  
  3483.     /* Make entry for create table */
  3484.     recinfo->length=length;
  3485.     if (field->flags & BLOB_FLAG)
  3486.       recinfo->type= (int) FIELD_BLOB;
  3487.     else if (!field->zero_pack() &&
  3488.          (field->type() == FIELD_TYPE_STRING ||
  3489.           field->type() == FIELD_TYPE_VAR_STRING) &&
  3490.          length >= 10 && blob_count)
  3491.       recinfo->type=FIELD_SKIPP_ENDSPACE;
  3492.     else
  3493.       recinfo->type=FIELD_NORMAL;
  3494.   }
  3495.  
  3496.   param->copy_field_count=(uint) (copy - param->copy_field);
  3497.   param->recinfo=recinfo;
  3498.   store_record(table,2);            // Make empty default record
  3499.  
  3500.   table->max_rows=(((table->db_type == DB_TYPE_HEAP) ?
  3501.             min(tmp_table_size, max_heap_table_size) : tmp_table_size)/
  3502.            table->reclength);
  3503.   set_if_bigger(table->max_rows,1);        // For dummy start options
  3504.   keyinfo=param->keyinfo;
  3505.  
  3506.   if (group)
  3507.   {
  3508.     DBUG_PRINT("info",("Creating group key in temporary table"));
  3509.     table->group=group;                /* Table is grouped by key */
  3510.     param->group_buff=group_buff;
  3511.     table->keys=1;
  3512.     table->uniques= test(using_unique_constraint);
  3513.     table->key_info=keyinfo;
  3514.     keyinfo->key_part=key_part_info;
  3515.     keyinfo->flags=HA_NOSAME;
  3516.     keyinfo->usable_key_parts=keyinfo->key_parts= param->group_parts;
  3517.     keyinfo->key_length=0;
  3518.     keyinfo->rec_per_key=0;
  3519.     for (; group ; group=group->next,key_part_info++)
  3520.     {
  3521.       Field *field=(*group->item)->tmp_table_field();
  3522.       bool maybe_null=(*group->item)->maybe_null;
  3523.       key_part_info->field=  field;
  3524.       key_part_info->offset= field->offset();
  3525.       key_part_info->length= (uint16) field->pack_length();
  3526.       key_part_info->type=   (uint8) field->key_type();
  3527.       key_part_info->key_type =
  3528.     ((ha_base_keytype) key_part_info->type == HA_KEYTYPE_TEXT ||
  3529.      (ha_base_keytype) key_part_info->type == HA_KEYTYPE_VARTEXT) ?
  3530.     0 : FIELDFLAG_BINARY;
  3531.       if (!using_unique_constraint)
  3532.       {
  3533.     group->buff=(char*) group_buff;
  3534.     if (!(group->field=field->new_field(table)))
  3535.       goto err; /* purecov: inspected */
  3536.     if (maybe_null)
  3537.     {
  3538.       /*
  3539.         To be able to group on NULL, we move the null bit to be
  3540.          just before the column and extend the key to cover the null bit
  3541.       */
  3542.       *group_buff= 0;            // Init null byte
  3543.       key_part_info->offset--;
  3544.       key_part_info->length++;
  3545.       group->field->move_field((char*) group_buff+1, (uchar*) group_buff,
  3546.                    1);
  3547.     }
  3548.     else
  3549.       group->field->move_field((char*) group_buff);
  3550.     group_buff+= key_part_info->length;
  3551.       }
  3552.       keyinfo->key_length+=  key_part_info->length;
  3553.     }
  3554.   }
  3555.  
  3556.   if (distinct && !group)
  3557.   {
  3558.     /* Create an unique key or an unique constraint over all columns */
  3559.     keyinfo->key_parts=field_count+ test(null_count);
  3560.     if (distinct && allow_distinct_limit)
  3561.     {
  3562.       set_if_smaller(table->max_rows,thd->select_limit);
  3563.       param->end_write_records=thd->select_limit;
  3564.     }
  3565.     else
  3566.       param->end_write_records= HA_POS_ERROR;
  3567.     table->distinct=1;
  3568.     table->keys=1;
  3569.     if (blob_count)
  3570.     {
  3571.       using_unique_constraint=1;
  3572.       table->uniques=1;
  3573.     }
  3574.     if (!(key_part_info= (KEY_PART_INFO*)
  3575.       sql_calloc((keyinfo->key_parts)*sizeof(KEY_PART_INFO))))
  3576.       goto err;
  3577.     table->key_info=keyinfo;
  3578.     keyinfo->key_part=key_part_info;
  3579.     keyinfo->flags=HA_NOSAME;
  3580.     keyinfo->key_length=(uint16) reclength;
  3581.     keyinfo->name=(char*) "tmp";
  3582.     if (null_count)
  3583.     {
  3584.       key_part_info->offset=0;
  3585.       key_part_info->length=(null_count+7)/8;
  3586.       key_part_info->field=new Field_string((char*) table->record[0],
  3587.                         (uint32) key_part_info->length,
  3588.                         (uchar*) 0,
  3589.                         (uint) 0,
  3590.                         Field::NONE,
  3591.                         NullS, table, (bool) 1);
  3592.       key_part_info->key_type=FIELDFLAG_BINARY;
  3593.       key_part_info->type=    HA_KEYTYPE_BINARY;
  3594.       key_part_info++;
  3595.     }
  3596.     for (i=0,reg_field=table->field; i < field_count;
  3597.      i++, reg_field++, key_part_info++)
  3598.     {
  3599.       key_part_info->field=    *reg_field;
  3600.       key_part_info->offset=   (*reg_field)->offset();
  3601.       key_part_info->length=   (uint16) (*reg_field)->pack_length();
  3602.       key_part_info->type=     (uint8) (*reg_field)->key_type();
  3603.       key_part_info->key_type =
  3604.     ((ha_base_keytype) key_part_info->type == HA_KEYTYPE_TEXT ||
  3605.      (ha_base_keytype) key_part_info->type == HA_KEYTYPE_VARTEXT) ?
  3606.     0 : FIELDFLAG_BINARY;
  3607.     }
  3608.   }
  3609.   if (thd->fatal_error)                // If end of memory
  3610.     goto err;                     /* purecov: inspected */
  3611.   table->db_record_offset=1;
  3612.   if (table->db_type == DB_TYPE_MYISAM)
  3613.   {
  3614.     if (create_myisam_tmp_table(table,param,select_options))
  3615.       goto err;
  3616.   }
  3617.   if (!open_tmp_table(table))
  3618.     DBUG_RETURN(table);
  3619.  
  3620.  err:
  3621.   free_tmp_table(thd,table);            /* purecov: inspected */
  3622.   DBUG_RETURN(NULL);                /* purecov: inspected */
  3623. }
  3624.  
  3625.  
  3626. static bool open_tmp_table(TABLE *table)
  3627. {
  3628.   int error;
  3629.   if ((error=table->file->ha_open(table->real_name,O_RDWR,HA_OPEN_TMP_TABLE)))
  3630.   {
  3631.     table->file->print_error(error,MYF(0)); /* purecov: inspected */
  3632.     table->db_stat=0;
  3633.     return(1);
  3634.   }
  3635.   /* VOID(ha_lock(table,F_WRLCK)); */        /* Single thread table */
  3636.   (void) table->file->extra(HA_EXTRA_NO_READCHECK);    /* Not needed */
  3637.   (void) table->file->extra(HA_EXTRA_QUICK);        /* Faster */
  3638.   return(0);
  3639. }
  3640.  
  3641.  
  3642. static bool create_myisam_tmp_table(TABLE *table,TMP_TABLE_PARAM *param,
  3643.                     uint options)
  3644. {
  3645.   int error;
  3646.   MI_KEYDEF keydef;
  3647.   MI_UNIQUEDEF uniquedef;
  3648.   KEY *keyinfo=param->keyinfo;
  3649.  
  3650.   DBUG_ENTER("create_myisam_tmp_table");
  3651.   if (table->keys)
  3652.   {                        // Get keys for ni_create
  3653.     bool using_unique_constraint=0;
  3654.     MI_KEYSEG *seg= (MI_KEYSEG*) sql_calloc(sizeof(*seg) *
  3655.                         keyinfo->key_parts);
  3656.     if (!seg)
  3657.       goto err;
  3658.  
  3659.     if (keyinfo->key_length >= table->file->max_key_length() ||
  3660.     keyinfo->key_parts > table->file->max_key_parts() ||
  3661.     table->uniques)
  3662.     {
  3663.       /* Can't create a key; Make a unique constraint instead of a key */
  3664.       table->keys=0;
  3665.       table->uniques=1;
  3666.       using_unique_constraint=1;
  3667.       bzero((char*) &uniquedef,sizeof(uniquedef));
  3668.       uniquedef.keysegs=keyinfo->key_parts;
  3669.       uniquedef.seg=seg;
  3670.       uniquedef.null_are_equal=1;
  3671.  
  3672.       /* Create extra column for hash value */
  3673.       bzero((byte*) param->recinfo,sizeof(*param->recinfo));
  3674.       param->recinfo->type= FIELD_CHECK;
  3675.       param->recinfo->length=MI_UNIQUE_HASH_LENGTH;
  3676.       param->recinfo++;
  3677.       table->reclength+=MI_UNIQUE_HASH_LENGTH;
  3678.     }
  3679.     else
  3680.     {
  3681.       /* Create an unique key */
  3682.       bzero((char*) &keydef,sizeof(keydef));
  3683.       keydef.flag=HA_NOSAME | HA_BINARY_PACK_KEY | HA_PACK_KEY;
  3684.       keydef.keysegs=  keyinfo->key_parts;
  3685.       keydef.seg= seg;
  3686.     }
  3687.     for (uint i=0; i < keyinfo->key_parts ; i++,seg++)
  3688.     {
  3689.       Field *field=keyinfo->key_part[i].field;
  3690.       seg->flag=0;
  3691.       seg->language=MY_CHARSET_CURRENT;
  3692.       seg->length=keyinfo->key_part[i].length;
  3693.       seg->start=keyinfo->key_part[i].offset;
  3694.       if (field->flags & BLOB_FLAG)
  3695.       {
  3696.     seg->type=
  3697.     ((keyinfo->key_part[i].key_type & FIELDFLAG_BINARY) ?
  3698.      HA_KEYTYPE_VARBINARY : HA_KEYTYPE_VARTEXT);
  3699.     seg->bit_start=seg->length - table->blob_ptr_size;
  3700.     seg->flag= HA_BLOB_PART;
  3701.     seg->length=0;            // Whole blob in unique constraint
  3702.       }
  3703.       else
  3704.       {
  3705.     seg->type=
  3706.       ((keyinfo->key_part[i].key_type & FIELDFLAG_BINARY) ?
  3707.        HA_KEYTYPE_BINARY : HA_KEYTYPE_TEXT);
  3708.     if (!(field->flags & ZEROFILL_FLAG) &&
  3709.         (field->type() == FIELD_TYPE_STRING ||
  3710.          field->type() == FIELD_TYPE_VAR_STRING) &&
  3711.         keyinfo->key_part[i].length > 4)
  3712.       seg->flag|=HA_SPACE_PACK;
  3713.       }
  3714.       if (using_unique_constraint &&
  3715.       !(field->flags & NOT_NULL_FLAG))
  3716.       {
  3717.     seg->null_bit= field->null_bit;
  3718.     seg->null_pos= (uint) (field->null_ptr - (uchar*) table->record[0]);
  3719.       }
  3720.     }
  3721.   }
  3722.   MI_CREATE_INFO create_info;
  3723.   bzero((char*) &create_info,sizeof(create_info));
  3724.   if ((options & (OPTION_BIG_TABLES | SELECT_SMALL_RESULT)) ==
  3725.       OPTION_BIG_TABLES)
  3726.     create_info.data_file_length= ~(ulonglong) 0;
  3727.  
  3728.   if ((error=mi_create(table->real_name,table->keys,&keydef,
  3729.                (uint) (param->recinfo-param->start_recinfo),
  3730.                param->start_recinfo,
  3731.                table->uniques, &uniquedef,
  3732.                &create_info,
  3733.                HA_CREATE_TMP_TABLE)))
  3734.   {
  3735.     table->file->print_error(error,MYF(0));    /* purecov: inspected */
  3736.     table->db_stat=0;
  3737.     goto err;
  3738.   }
  3739.   statistic_increment(created_tmp_disk_tables, &LOCK_status);
  3740.   table->db_record_offset=1;
  3741.   DBUG_RETURN(0);
  3742.  err:
  3743.   DBUG_RETURN(1);
  3744. }
  3745.  
  3746.  
  3747. void
  3748. free_tmp_table(THD *thd, TABLE *entry)
  3749. {
  3750.   const char *save_proc_info;
  3751.   DBUG_ENTER("free_tmp_table");
  3752.   DBUG_PRINT("enter",("table: %s",entry->table_name));
  3753.  
  3754.   save_proc_info=thd->proc_info;
  3755.   thd->proc_info="removing tmp table";
  3756.   if (entry->db_stat && entry->file)
  3757.   {
  3758.     (void) entry->file->close();
  3759.     delete entry->file;
  3760.   }
  3761.   if (!(test_flags & TEST_KEEP_TMP_TABLES) || entry->db_type == DB_TYPE_HEAP)
  3762.     (void) ha_delete_table(entry->db_type,entry->real_name);
  3763.   /* free blobs */
  3764.   for (Field **ptr=entry->field ; *ptr ; ptr++)
  3765.     delete *ptr;
  3766.   my_free((gptr) entry->record[0],MYF(0));
  3767.   free_io_cache(entry);
  3768.   my_free((gptr) entry,MYF(0));
  3769.   thd->proc_info=save_proc_info;
  3770.  
  3771.   DBUG_VOID_RETURN;
  3772. }
  3773.  
  3774. /*
  3775. * If a HEAP table gets full, create a MyISAM table and copy all rows to this
  3776. */
  3777.  
  3778. bool create_myisam_from_heap(TABLE *table, TMP_TABLE_PARAM *param, int error,
  3779.                  bool ignore_last_dupp_key_error)
  3780. {
  3781.   TABLE new_table;
  3782.   const char *save_proc_info;
  3783.   THD *thd=current_thd;
  3784.   int write_err;
  3785.   DBUG_ENTER("create_myisam_from_heap");
  3786.  
  3787.   if (table->db_type != DB_TYPE_HEAP || error != HA_ERR_RECORD_FILE_FULL)
  3788.   {
  3789.     table->file->print_error(error,MYF(0));
  3790.     DBUG_RETURN(1);
  3791.   }
  3792.   new_table= *table;
  3793.   new_table.db_type=DB_TYPE_MYISAM;
  3794.   if (!(new_table.file=get_new_handler(&new_table,DB_TYPE_MYISAM)))
  3795.     DBUG_RETURN(1);                // End of memory
  3796.  
  3797.   save_proc_info=thd->proc_info;
  3798.   thd->proc_info="converting HEAP to MyISAM";
  3799.  
  3800.   if (create_myisam_tmp_table(&new_table,param,
  3801.                   thd->lex.options | thd->options))
  3802.     goto err2;
  3803.   if (open_tmp_table(&new_table))
  3804.     goto err1;
  3805.   table->file->index_end();
  3806.   table->file->rnd_init();
  3807.   /* copy all old rows */
  3808.   while (!table->file->rnd_next(new_table.record[1]))
  3809.   {
  3810.     if ((write_err=new_table.file->write_row(new_table.record[1])))
  3811.       goto err;
  3812.   }
  3813.   /* copy row that filled HEAP table */
  3814.   if ((write_err=new_table.file->write_row(table->record[0])))
  3815.   {
  3816.     if (write_err != HA_ERR_FOUND_DUPP_KEY &&
  3817.     write_err != HA_ERR_FOUND_DUPP_UNIQUE || !ignore_last_dupp_key_error)
  3818.     goto err;
  3819.   }
  3820.  
  3821.   /* remove heap table and change to use myisam table */
  3822.   (void) table->file->rnd_end();
  3823.   (void) table->file->close();
  3824.   (void) table->file->delete_table(table->real_name);
  3825.   delete table->file;
  3826.   table->file=0;
  3827.   *table =new_table;
  3828.   table->file->change_table_ptr(table);
  3829.  
  3830.   thd->proc_info=save_proc_info;
  3831.   DBUG_RETURN(0);
  3832.  
  3833.  err:
  3834.   DBUG_PRINT("error",("Got error: %d",write_err));
  3835.   table->file->print_error(error,MYF(0));    // Give table is full error
  3836.   (void) table->file->rnd_end();
  3837.   (void) new_table.file->close();
  3838.  err1:
  3839.   new_table.file->delete_table(new_table.real_name);
  3840.   delete new_table.file;
  3841.  err2:
  3842.   thd->proc_info=save_proc_info;
  3843.   DBUG_RETURN(1);
  3844. }
  3845.  
  3846.  
  3847. /*****************************************************************************
  3848. **    Make a join of all tables and write it on socket or to table
  3849. *****************************************************************************/
  3850.  
  3851. static int
  3852. do_select(JOIN *join,List<Item> *fields,TABLE *table,Procedure *procedure)
  3853. {
  3854.   int error;
  3855.   JOIN_TAB *join_tab;
  3856.   int (*end_select)(JOIN *, struct st_join_table *,bool);
  3857.   DBUG_ENTER("do_select");
  3858.  
  3859.   join->procedure=procedure;
  3860.   /*
  3861.   ** Tell the client how many fields there are in a row
  3862.   */
  3863.   if (!table)
  3864.     join->result->send_fields(*fields,1);
  3865.   else
  3866.   {
  3867.     VOID(table->file->extra(HA_EXTRA_WRITE_CACHE));
  3868.     empty_record(table);
  3869.   }
  3870.   join->tmp_table=table;            /* Save for easy recursion */
  3871.   join->fields= fields;
  3872.  
  3873.   /* Set up select_end */
  3874.   if (table)
  3875.   {
  3876.     if (table->group && join->tmp_table_param.sum_func_count)
  3877.     {
  3878.       DBUG_PRINT("info",("Using end_update"));
  3879.       if (table->keys)
  3880.       {
  3881.     end_select=end_update;
  3882.     table->file->index_init(0);
  3883.       }
  3884.       else
  3885.     end_select=end_unique_update;
  3886.     }
  3887.     else if (join->sort_and_group)
  3888.     {
  3889.       DBUG_PRINT("info",("Using end_write_group"));
  3890.       end_select=end_write_group;
  3891.     }
  3892.     else
  3893.     {
  3894.       DBUG_PRINT("info",("Using end_write"));
  3895.       end_select=end_write;
  3896.     }
  3897.   }
  3898.   else
  3899.   {
  3900.     if (join->sort_and_group || (join->procedure &&
  3901.                  join->procedure->flags & PROC_GROUP))
  3902.       end_select=end_send_group;
  3903.     else
  3904.       end_select=end_send;
  3905.   }
  3906.   join->join_tab[join->tables-1].next_select=end_select;
  3907.  
  3908.   join_tab=join->join_tab+join->const_tables;
  3909.   join->send_records=0;
  3910.   if (join->tables == join->const_tables)
  3911.   {
  3912.     if (!(error=(*end_select)(join,join_tab,0)) || error == -3)
  3913.       error=(*end_select)(join,join_tab,1);
  3914.   }
  3915.   else
  3916.   {
  3917.     error=sub_select(join,join_tab,0);
  3918.     if (error >= 0)
  3919.       error=sub_select(join,join_tab,1);
  3920.     if (error == -3)
  3921.       error=0;                    /* select_limit used */
  3922.   }
  3923.   if (!table)                    /* If sending data to client */
  3924.   {
  3925.     if (error < 0)
  3926.       join->result->send_error(0,NullS);    /* purecov: inspected */
  3927.     else
  3928.     {
  3929.       join_free(join);                // Unlock all cursors
  3930.       if (join->result->send_eof())
  3931.     error= -1;
  3932.     }
  3933.   }
  3934.   else if (error < 0)
  3935.     join->result->send_error(0,NullS); /* purecov: inspected */
  3936.  
  3937.   if (error >= 0)
  3938.   {
  3939.     DBUG_PRINT("info",("%ld records output",join->send_records));
  3940.   }
  3941.   if (table)
  3942.   {
  3943.     int old_error=error,tmp;
  3944.     if ((tmp=table->file->extra(HA_EXTRA_NO_CACHE)))
  3945.     {
  3946.       my_errno=tmp;
  3947.       error= -1;
  3948.     }
  3949.     if (table->file->index_end())
  3950.     {
  3951.       my_errno=tmp;
  3952.       error= -1;
  3953.     }
  3954.     if (error != old_error)
  3955.       table->file->print_error(my_errno,MYF(0));
  3956.   }
  3957.   DBUG_RETURN(error < 0);
  3958. }
  3959.  
  3960.  
  3961. static int
  3962. sub_select_cache(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
  3963. {
  3964.   int error;
  3965.  
  3966.   if (end_of_records)
  3967.   {
  3968.     if ((error=flush_cached_records(join,join_tab,FALSE)) < 0)
  3969.       return error; /* purecov: inspected */
  3970.     return sub_select(join,join_tab,end_of_records);
  3971.   }
  3972.   if (join->thd->killed)        // If aborted by user
  3973.   {
  3974.     my_error(ER_SERVER_SHUTDOWN,MYF(0)); /* purecov: inspected */
  3975.     return -2;                 /* purecov: inspected */
  3976.   }
  3977.   if (join_tab->use_quick != 2 || test_if_quick_select(join_tab) <= 0)
  3978.   {
  3979.     if (!store_record_in_cache(&join_tab->cache))
  3980.       return 0;                    // There is more room in cache
  3981.     return flush_cached_records(join,join_tab,FALSE);
  3982.   }
  3983.   if ((error=flush_cached_records(join,join_tab,TRUE)) < 0)
  3984.     return error; /* purecov: inspected */
  3985.   return sub_select(join,join_tab,end_of_records); /* Use ordinary select */
  3986. }
  3987.  
  3988.  
  3989. static int
  3990. sub_select(JOIN *join,JOIN_TAB *join_tab,bool end_of_records)
  3991. {
  3992.  
  3993.   join_tab->table->null_row=0;
  3994.   if (end_of_records)
  3995.     return (*join_tab->next_select)(join,join_tab+1,end_of_records);
  3996.  
  3997.   /* Cache variables for faster loop */
  3998.   int error;
  3999.   bool found=0;
  4000.   COND *on_expr=join_tab->on_expr, *select_cond=join_tab->select_cond;
  4001.   int  (*next_select)(JOIN *,struct st_join_table *,bool)=
  4002.     join_tab->next_select;
  4003.  
  4004.   if (!(error=(*join_tab->read_first_record)(join_tab)))
  4005.   {
  4006.     bool not_exists_optimize= join_tab->table->reginfo.not_exists_optimize;
  4007.     bool not_used_in_distinct=join_tab->not_used_in_distinct;
  4008.     ha_rows found_records=join->found_records;
  4009.     READ_RECORD *info= &join_tab->read_record;
  4010.  
  4011.     do
  4012.     {
  4013.       if (join->thd->killed)            // Aborted by user
  4014.       {
  4015.     my_error(ER_SERVER_SHUTDOWN,MYF(0));    /* purecov: inspected */
  4016.     return -2;                /* purecov: inspected */
  4017.       }
  4018.       if (!on_expr || on_expr->val_int())
  4019.       {
  4020.     found=1;
  4021.     if (not_exists_optimize)
  4022.       break;            // Searching after not null columns
  4023.     if (!select_cond || select_cond->val_int())
  4024.     {
  4025.       if ((error=(*next_select)(join,join_tab+1,0)) < 0)
  4026.         return error;
  4027.       if (not_used_in_distinct && found_records != join->found_records)
  4028.         return 0;
  4029.     }
  4030.       }
  4031.     } while (!(error=info->read_record(info)));
  4032.     if (error > 0)                // Fatal error
  4033.       return -1;
  4034.   }
  4035.   else if (error > 0)
  4036.     return -1;
  4037.  
  4038.   if (!found && on_expr)
  4039.   {                        // OUTER JOIN
  4040.     restore_record(join_tab->table,2);        // Make empty record
  4041.     mark_as_null_row(join_tab->table);        // For group by without error
  4042.     if (!select_cond || select_cond->val_int())
  4043.     {
  4044.       if ((error=(*next_select)(join,join_tab+1,0)) < 0)
  4045.     return error;                /* purecov: inspected */
  4046.     }
  4047.   }
  4048.   return 0;
  4049. }
  4050.  
  4051.  
  4052. static int
  4053. flush_cached_records(JOIN *join,JOIN_TAB *join_tab,bool skipp_last)
  4054. {
  4055.   int error;
  4056.   READ_RECORD *info;
  4057.  
  4058.   if (!join_tab->cache.records)
  4059.     return 0;                /* Nothing to do */
  4060.   if (skipp_last)
  4061.     (void) store_record_in_cache(&join_tab->cache); // Must save this for later
  4062.   if (join_tab->use_quick == 2)
  4063.   {
  4064.     if (join_tab->select->quick)
  4065.     {                    /* Used quick select last. reset it */
  4066.       delete join_tab->select->quick;
  4067.       join_tab->select->quick=0;
  4068.     }
  4069.   }
  4070.  /* read through all records */
  4071.   if ((error=join_init_read_record(join_tab)))
  4072.   {
  4073.     reset_cache(&join_tab->cache);
  4074.     join_tab->cache.records=0; join_tab->cache.ptr_record= (uint) ~0;
  4075.     return -error;            /* No records or error */
  4076.   }
  4077.  
  4078.   for (JOIN_TAB *tmp=join->join_tab; tmp != join_tab ; tmp++)
  4079.   {
  4080.     tmp->status=tmp->table->status;
  4081.     tmp->table->status=0;
  4082.   }
  4083.  
  4084.   info= &join_tab->read_record;
  4085.   do
  4086.   {
  4087.     if (join->thd->killed)
  4088.     {
  4089.       my_error(ER_SERVER_SHUTDOWN,MYF(0)); /* purecov: inspected */
  4090.       return -2;                // Aborted by user /* purecov: inspected */
  4091.     }
  4092.     SQL_SELECT *select=join_tab->select;
  4093.     if (!error && (!join_tab->cache.select ||
  4094.            !join_tab->cache.select->skipp_record()))
  4095.     {
  4096.       uint i;
  4097.       reset_cache(&join_tab->cache);
  4098.       for (i=(join_tab->cache.records- (skipp_last ? 1 : 0)) ; i-- > 0 ;)
  4099.       {
  4100.     read_cached_record(join_tab);
  4101.     if (!select || !select->skipp_record())
  4102.       if ((error=(join_tab->next_select)(join,join_tab+1,0)) < 0)
  4103.         return error; /* purecov: inspected */
  4104.       }
  4105.     }
  4106.   } while (!(error=info->read_record(info)));
  4107.  
  4108.   if (skipp_last)
  4109.     read_cached_record(join_tab);        // Restore current record
  4110.   reset_cache(&join_tab->cache);
  4111.   join_tab->cache.records=0; join_tab->cache.ptr_record= (uint) ~0;
  4112.   if (error > 0)                // Fatal error
  4113.     return -1;                    /* purecov: inspected */
  4114.   for (JOIN_TAB *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
  4115.     tmp2->table->status=tmp2->status;
  4116.   return 0;
  4117. }
  4118.  
  4119.  
  4120. /*****************************************************************************
  4121. ** The different ways to read a record
  4122. ** Returns -1 if row was not found, 0 if row was found and 1 on errors
  4123. *****************************************************************************/
  4124.  
  4125. static int
  4126. join_read_const_tables(JOIN *join)
  4127. {
  4128.   uint i;
  4129.   int error;
  4130.   DBUG_ENTER("join_read_const_tables");
  4131.   for (i=0 ; i < join->const_tables ; i++)
  4132.   {
  4133.     TABLE *form=join->table[i];
  4134.     form->null_row=0;
  4135.     form->status=STATUS_NO_RECORD;
  4136.  
  4137.     if (join->join_tab[i].type == JT_SYSTEM)
  4138.     {
  4139.       if ((error=join_read_system(join->join_tab+i)))
  4140.       {                        // Info for DESCRIBE
  4141.     join->join_tab[i].info="const row not found";
  4142.     join->best_positions[i].records_read=0.0;
  4143.     if (!form->outer_join || error > 0)
  4144.       DBUG_RETURN(error);
  4145.       }
  4146.     }
  4147.     else
  4148.     {
  4149.       if ((error=join_read_const(join->join_tab+i)))
  4150.       {
  4151.     join->join_tab[i].info="unique row not found";
  4152.     join->best_positions[i].records_read=0.0;
  4153.     if (!form->outer_join || error > 0)
  4154.       DBUG_RETURN(error);
  4155.       }
  4156.     }
  4157.     if (join->join_tab[i].on_expr && !form->null_row)
  4158.     {
  4159.       if ((form->null_row= test(join->join_tab[i].on_expr->val_int() == 0)))
  4160.     empty_record(form);
  4161.     }
  4162.     if (!form->null_row)
  4163.       form->maybe_null=0;
  4164.   }
  4165.   DBUG_RETURN(0);
  4166. }
  4167.  
  4168.  
  4169. static int
  4170. join_read_system(JOIN_TAB *tab)
  4171. {
  4172.   TABLE *table= tab->table;
  4173.   int error;
  4174.   if (table->status & STATUS_GARBAGE)        // If first read
  4175.   {
  4176.     if ((error=table->file->rnd_first(table->record[0])))
  4177.     {
  4178.       if (error != HA_ERR_END_OF_FILE)
  4179.       {
  4180.     table->file->print_error(error,MYF(0));
  4181.     return 1;
  4182.       }
  4183.       table->null_row=1;            // This is ok.
  4184.       empty_record(table);            // Make empty record
  4185.       return -1;
  4186.     }
  4187.     store_record(table,1);
  4188.   }
  4189.   else if (!table->status)            // Only happens with left join
  4190.     restore_record(table,1);            // restore old record
  4191.   table->null_row=0;
  4192.   return table->status ? -1 : 0;
  4193. }
  4194.  
  4195.  
  4196. static int
  4197. join_read_const(JOIN_TAB *tab)
  4198. {
  4199.   int error;
  4200.   TABLE *table= tab->table;
  4201.   if (table->status & STATUS_GARBAGE)        // If first read
  4202.   {
  4203.     if (cp_buffer_from_ref(&tab->ref))
  4204.       error=HA_ERR_KEY_NOT_FOUND;
  4205.     else
  4206.     {
  4207.       error=table->file->index_read_idx(table->record[0],tab->ref.key,
  4208.                     (byte*) tab->ref.key_buff,
  4209.                     tab->ref.key_length,HA_READ_KEY_EXACT);
  4210.     }
  4211.     if (error)
  4212.     {
  4213.       table->null_row=1;
  4214.       empty_record(table);
  4215.       if (error != HA_ERR_KEY_NOT_FOUND)
  4216.       {
  4217.     sql_print_error("read_const: Got error %d when reading table %s",
  4218.             error, table->path);
  4219.     table->file->print_error(error,MYF(0));
  4220.     return 1;
  4221.       }
  4222.       return -1;
  4223.     }
  4224.     store_record(table,1);
  4225.   }
  4226.   else if (!table->status)            // Only happens with left join
  4227.     restore_record(table,1);            // restore old record
  4228.   table->null_row=0;
  4229.   return table->status ? -1 : 0;
  4230. }
  4231.  
  4232.  
  4233. static int
  4234. join_read_key(JOIN_TAB *tab)
  4235. {
  4236.   int error;
  4237.   TABLE *table= tab->table;
  4238.  
  4239.   if (cmp_buffer_with_ref(tab) ||
  4240.       (table->status & (STATUS_GARBAGE | STATUS_NO_PARENT | STATUS_NULL_ROW)))
  4241.   {
  4242.     if (tab->ref.key_err)
  4243.     {
  4244.       table->status=STATUS_NOT_FOUND;
  4245.       return -1;
  4246.     }
  4247.     error=table->file->index_read(table->record[0],
  4248.                   tab->ref.key_buff,
  4249.                   tab->ref.key_length,HA_READ_KEY_EXACT);
  4250.     if (error && error != HA_ERR_KEY_NOT_FOUND)
  4251.     {
  4252.       sql_print_error("read_key: Got error %d when reading table '%s'",error,
  4253.               table->path);
  4254.       table->file->print_error(error,MYF(0));
  4255.       return 1;
  4256.     }
  4257.   }
  4258.   table->null_row=0;
  4259.   return table->status ? -1 : 0;
  4260. }
  4261.  
  4262.  
  4263. static int
  4264. join_read_always_key(JOIN_TAB *tab)
  4265. {
  4266.   int error;
  4267.   TABLE *table= tab->table;
  4268.  
  4269.   if (cp_buffer_from_ref(&tab->ref))
  4270.     return -1;
  4271.   if ((error=table->file->index_read(table->record[0],
  4272.                      tab->ref.key_buff,
  4273.                      tab->ref.key_length,HA_READ_KEY_EXACT)))
  4274.   {
  4275.     if (error != HA_ERR_KEY_NOT_FOUND)
  4276.     {
  4277.       sql_print_error("read_const: Got error %d when reading table %s",error,
  4278.               table->path);
  4279.       table->file->print_error(error,MYF(0));
  4280.       return 1;
  4281.     }
  4282.     return -1; /* purecov: inspected */
  4283.   }
  4284.   return 0;
  4285. }
  4286.  
  4287.  
  4288.     /* ARGSUSED */
  4289. static int
  4290. join_no_more_records(READ_RECORD *info __attribute__((unused)))
  4291. {
  4292.   return -1;
  4293. }
  4294.  
  4295.  
  4296. static int
  4297. join_read_next(READ_RECORD *info)
  4298. {
  4299.   int error;
  4300.   TABLE *table= info->table;
  4301.   JOIN_TAB *tab=table->reginfo.join_tab;
  4302.  
  4303.   if ((error=table->file->index_next_same(table->record[0],
  4304.                       tab->ref.key_buff,
  4305.                       tab->ref.key_length)))
  4306.   {
  4307.     if (error != HA_ERR_END_OF_FILE)
  4308.     {
  4309.       sql_print_error("read_next: Got error %d when reading table %s",error,
  4310.               table->path);
  4311.       table->file->print_error(error,MYF(0));
  4312.       return 1;
  4313.     }
  4314.     table->status= STATUS_GARBAGE;
  4315.     return -1;
  4316.   }
  4317.   return 0;
  4318. }
  4319.  
  4320.  
  4321. static int
  4322. join_init_quick_read_record(JOIN_TAB *tab)
  4323. {
  4324.   if (test_if_quick_select(tab) == -1)
  4325.     return -1;                    /* No possible records */
  4326.   return join_init_read_record(tab);
  4327. }
  4328.  
  4329.  
  4330. static int
  4331. test_if_quick_select(JOIN_TAB *tab)
  4332. {
  4333.   delete tab->select->quick;
  4334.   tab->select->quick=0;
  4335.   return tab->select->test_quick_select(tab->keys,(table_map) 0,HA_POS_ERROR);
  4336. }
  4337.  
  4338.  
  4339. static int
  4340. join_init_read_record(JOIN_TAB *tab)
  4341. {
  4342.   if (tab->select && tab->select->quick)
  4343.     tab->select->quick->reset();
  4344.   init_read_record(&tab->read_record,current_thd, tab->table, tab->select,1,1);
  4345.   return (*tab->read_record.read_record)(&tab->read_record);
  4346. }
  4347.  
  4348. static int
  4349. join_init_read_first_with_key(JOIN_TAB *tab)
  4350. {
  4351.   int error;
  4352.   TABLE *table=tab->table;
  4353.   if (!table->key_read && (table->used_keys & ((key_map) 1 << tab->index)))
  4354.   {
  4355.     table->key_read=1;
  4356.     table->file->extra(HA_EXTRA_KEYREAD);
  4357.   }
  4358.   tab->table->status=0;
  4359.   tab->read_record.read_record=join_init_read_next_with_key;
  4360.   tab->read_record.table=table;
  4361.   tab->read_record.file=table->file;
  4362.   tab->read_record.index=tab->index;
  4363.   tab->read_record.record=table->record[0];
  4364.   tab->table->file->index_init(tab->index);
  4365.   error=tab->table->file->index_first(tab->table->record[0]);
  4366.   if (error)
  4367.   {
  4368.     if (error != HA_ERR_KEY_NOT_FOUND && error != HA_ERR_END_OF_FILE)
  4369.     {
  4370.       sql_print_error("read_first_with_key: Got error %d when reading table",error);
  4371.       table->file->print_error(error,MYF(0));
  4372.       return 1;
  4373.     }
  4374.     return -1;
  4375.   }
  4376.   return 0;
  4377. }
  4378.  
  4379. static int
  4380. join_init_read_next_with_key(READ_RECORD *info)
  4381. {
  4382.   int error=info->file->index_next(info->record);
  4383.   if (error)
  4384.   {
  4385.     if (error != HA_ERR_END_OF_FILE)
  4386.     {
  4387.       sql_print_error("read_next_with_key: Got error %d when reading table %s",
  4388.               error, info->table->path);
  4389.       info->file->print_error(error,MYF(0));
  4390.       return 1;
  4391.     }
  4392.     return -1;
  4393.   }
  4394.   return 0;
  4395. }
  4396.  
  4397. static int
  4398. join_init_read_last_with_key(JOIN_TAB *tab)
  4399. {
  4400.   TABLE *table=tab->table;
  4401.   int error;
  4402.   if (!table->key_read && (table->used_keys & ((key_map) 1 << tab->index)))
  4403.   {
  4404.     table->key_read=1;
  4405.     table->file->extra(HA_EXTRA_KEYREAD);
  4406.   }
  4407.   tab->table->status=0;
  4408.   tab->read_record.read_record=join_init_read_prev_with_key;
  4409.   tab->read_record.table=table;
  4410.   tab->read_record.file=table->file;
  4411.   tab->read_record.index=tab->index;
  4412.   tab->read_record.record=table->record[0];
  4413.   tab->table->file->index_init(tab->index);
  4414.   error=tab->table->file->index_last(tab->table->record[0]);
  4415.   if (error)
  4416.   {
  4417.     if (error != HA_ERR_END_OF_FILE)
  4418.     {
  4419.       sql_print_error("read_first_with_key: Got error %d when reading table",
  4420.               error, table->path);
  4421.       table->file->print_error(error,MYF(0));
  4422.       return 1;
  4423.     }
  4424.     return -1;
  4425.   }
  4426.   return 0;
  4427. }
  4428.  
  4429. static int
  4430. join_init_read_prev_with_key(READ_RECORD *info)
  4431. {
  4432.   int error=info->file->index_prev(info->record);
  4433.   if (error)
  4434.   {
  4435.     if (error != HA_ERR_END_OF_FILE)
  4436.     {
  4437.       sql_print_error("read_prev_with_key: Got error %d when reading table: %s",
  4438.               error,info->table->path);
  4439.       info->file->print_error(error,MYF(0));
  4440.       return 1;
  4441.     }
  4442.     return -1;
  4443.   }
  4444.   return 0;
  4445. }
  4446.  
  4447. static int
  4448. join_ft_read_first(JOIN_TAB *tab)
  4449. {
  4450.   int error;
  4451.   TABLE *table= tab->table;
  4452.  
  4453. #if 0
  4454.   if (cp_buffer_from_ref(&tab->ref))       // as ft-key doesn't use store_key's
  4455.     return -1;                             // see also FT_SELECT::init()
  4456. #endif
  4457.   table->file->ft_init();
  4458.  
  4459.   error=table->file->ft_read(table->record[0]);
  4460.   if (error)
  4461.   {
  4462.     if (error != HA_ERR_END_OF_FILE)
  4463.     {
  4464.       sql_print_error("ft_read_first: Got error %d when reading table %s",
  4465.                       error, table->path);
  4466.       table->file->print_error(error,MYF(0));
  4467.       return 1;
  4468.     }
  4469.     return -1;
  4470.   }
  4471.   return 0;
  4472. }
  4473.  
  4474. static int
  4475. join_ft_read_next(READ_RECORD *info)
  4476. {
  4477.   int error=info->file->ft_read(info->table->record[0]);
  4478.   if (error)
  4479.   {
  4480.     if (error != HA_ERR_END_OF_FILE)
  4481.     {
  4482.       sql_print_error("ft_read_next: Got error %d when reading table %s",
  4483.                       error, info->table->path);
  4484.       info->file->print_error(error,MYF(0));
  4485.       return 1;
  4486.     }
  4487.     return -1;
  4488.   }
  4489.   return 0;
  4490. }
  4491.  
  4492.  
  4493. /*****************************************************************************
  4494. ** The different end of select functions
  4495. ** These functions returns < 0 when end is reached, 0 on ok and > 0 if a
  4496. ** fatal error (like table corruption) was detected
  4497. *****************************************************************************/
  4498.  
  4499.     /* ARGSUSED */
  4500. static int
  4501. end_send(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
  4502.      bool end_of_records)
  4503. {
  4504.   DBUG_ENTER("end_send");
  4505.   if (!end_of_records)
  4506.   {
  4507.     int error;
  4508.     if (join->having && join->having->val_int() == 0)
  4509.       DBUG_RETURN(0);                // Didn't match having
  4510.     if (join->procedure)
  4511.       error=join->procedure->send_row(*join->fields);
  4512.     else
  4513.       error=join->result->send_data(*join->fields);
  4514.     if (error)
  4515.       DBUG_RETURN(-1); /* purecov: inspected */
  4516.     if (++join->send_records >= join->thd->select_limit)
  4517.       DBUG_RETURN(-3);                // Abort nicely
  4518.   }
  4519.   else
  4520.   {
  4521.     if (join->procedure && join->procedure->end_of_records())
  4522.       DBUG_RETURN(-1);
  4523.   }
  4524.   DBUG_RETURN(0);
  4525. }
  4526.  
  4527.  
  4528.     /* ARGSUSED */
  4529. static int
  4530. end_send_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
  4531.            bool end_of_records)
  4532. {
  4533.   int idx= -1;
  4534.   DBUG_ENTER("end_send_group");
  4535.  
  4536.   if (!join->first_record || end_of_records ||
  4537.       (idx=test_if_group_changed(join->group_fields)) >= 0)
  4538.   {
  4539.     if (join->first_record || (end_of_records && !join->group))
  4540.     {
  4541.       if (join->procedure)
  4542.     join->procedure->end_group();
  4543.       if (idx < (int) join->send_group_parts)
  4544.       {
  4545.     int error;
  4546.     if (join->procedure)
  4547.     {
  4548.       if (join->having && join->having->val_int() == 0)
  4549.         error= -1;                // Didn't satisfy having
  4550.       else
  4551.         error=join->procedure->send_row(*join->fields) ? 1 : 0;
  4552.       if (end_of_records && join->procedure->end_of_records())
  4553.         error= 1;                // Fatal error
  4554.     }
  4555.     else
  4556.     {
  4557.       if (!join->first_record)
  4558.         clear_tables(join);
  4559.       if (join->having && join->having->val_int() == 0)
  4560.         error= -1;                // Didn't satisfy having
  4561.       else
  4562.         error=join->result->send_data(*join->fields) ? 1 : 0;
  4563.     }
  4564.     if (error > 0)
  4565.       DBUG_RETURN(-1);            /* purecov: inspected */
  4566.     if (end_of_records)
  4567.       DBUG_RETURN(0);
  4568.     if (!error && ++join->send_records >= join->thd->select_limit)
  4569.       DBUG_RETURN(-3);            /* Abort nicely */
  4570.       }
  4571.     }
  4572.     else
  4573.     {
  4574.       if (end_of_records)
  4575.     DBUG_RETURN(0);
  4576.       join->first_record=1;
  4577.       VOID(test_if_group_changed(join->group_fields));
  4578.     }
  4579.     if (idx < (int) join->send_group_parts)
  4580.     {
  4581.       copy_fields(&join->tmp_table_param);
  4582.       init_sum_functions(join->sum_funcs);
  4583.       if (join->procedure)
  4584.     join->procedure->add();
  4585.       DBUG_RETURN(0);
  4586.     }
  4587.   }
  4588.   if (update_sum_func(join->sum_funcs))
  4589.     DBUG_RETURN(-1);
  4590.   if (join->procedure)
  4591.     join->procedure->add();
  4592.   DBUG_RETURN(0);
  4593. }
  4594.  
  4595.  
  4596.     /* ARGSUSED */
  4597. static int
  4598. end_write(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
  4599.       bool end_of_records)
  4600. {
  4601.   TABLE *table=join->tmp_table;
  4602.   int error;
  4603.   DBUG_ENTER("end_write");
  4604.  
  4605.   if (join->thd->killed)            // Aborted by user
  4606.   {
  4607.     my_error(ER_SERVER_SHUTDOWN,MYF(0));    /* purecov: inspected */
  4608.     DBUG_RETURN(-2);                /* purecov: inspected */
  4609.   }
  4610.   if (!end_of_records)
  4611.   {
  4612.     copy_fields(&join->tmp_table_param);
  4613.     copy_funcs(join->tmp_table_param.funcs);
  4614.  
  4615.     if (!table->uniques)            // If not unique handling
  4616.     {
  4617.       /* Copy null values from group to row */
  4618.       ORDER   *group;
  4619.       for (group=table->group ; group ; group=group->next)
  4620.       {
  4621.     Item *item= *group->item;
  4622.     if (item->maybe_null)
  4623.     {
  4624.       Field *field=item->tmp_table_field();
  4625.       field->ptr[-1]= (byte) (field->is_null() ? 0 : 1);
  4626.     }
  4627.       }
  4628.     }
  4629.     if (!join->having || join->having->val_int())
  4630.     {
  4631.       join->found_records++;
  4632.       if ((error=table->file->write_row(table->record[0])))
  4633.       {
  4634.     if (error == HA_ERR_FOUND_DUPP_KEY ||
  4635.         error == HA_ERR_FOUND_DUPP_UNIQUE)
  4636.       goto end;
  4637.     if (create_myisam_from_heap(table, &join->tmp_table_param, error,1))
  4638.       DBUG_RETURN(1);            // Not a table_is_full error
  4639.     table->uniques=0;            // To ensure rows are the same
  4640.     if (++join->send_records >= join->tmp_table_param.end_write_records)
  4641.       DBUG_RETURN(-3);
  4642.       }
  4643.     }
  4644.   }
  4645. end:
  4646.   DBUG_RETURN(0);
  4647. }
  4648.  
  4649. /* Group by searching after group record and updating it if possible */
  4650. /* ARGSUSED */
  4651.  
  4652. static int
  4653. end_update(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
  4654.        bool end_of_records)
  4655. {
  4656.   TABLE *table=join->tmp_table;
  4657.   ORDER   *group;
  4658.   int      error;
  4659.   DBUG_ENTER("end_update");
  4660.  
  4661.   if (end_of_records)
  4662.     DBUG_RETURN(0);
  4663.   if (join->thd->killed)            // Aborted by user
  4664.   {
  4665.     my_error(ER_SERVER_SHUTDOWN,MYF(0));    /* purecov: inspected */
  4666.     DBUG_RETURN(-2);                /* purecov: inspected */
  4667.   }
  4668.  
  4669.   join->found_records++;
  4670.   copy_fields(&join->tmp_table_param);        // Groups are copied twice.
  4671.   /* Make a key of group index */
  4672.   for (group=table->group ; group ; group=group->next)
  4673.   {
  4674.     Item *item= *group->item;
  4675.     item->save_org_in_field(group->field);
  4676.     if (item->maybe_null)
  4677.       group->buff[0]=item->null_value ? 0: 1;    // Save reversed value
  4678.   }
  4679.   // table->file->index_init(0);
  4680.   if (!table->file->index_read(table->record[1],
  4681.                    join->tmp_table_param.group_buff,0,
  4682.                    HA_READ_KEY_EXACT))
  4683.   {                        /* Update old record */
  4684.     restore_record(table,1);
  4685.     update_tmptable_sum_func(join->sum_funcs,table);
  4686.     if ((error=table->file->update_row(table->record[1],
  4687.                        table->record[0])))
  4688.     {
  4689.       table->file->print_error(error,MYF(0));    /* purecov: inspected */
  4690.       DBUG_RETURN(-1);                /* purecov: inspected */
  4691.     }
  4692.     DBUG_RETURN(0);
  4693.   }
  4694.  
  4695.   /* The null bits are already set */
  4696.   KEY_PART_INFO *key_part;
  4697.   for (group=table->group,key_part=table->key_info[0].key_part;
  4698.        group ;
  4699.        group=group->next,key_part++)
  4700.     memcpy(table->record[0]+key_part->offset, group->buff, key_part->length);
  4701.  
  4702.   init_tmptable_sum_functions(join->sum_funcs);
  4703.   copy_funcs(join->tmp_table_param.funcs);
  4704.   if ((error=table->file->write_row(table->record[0])))
  4705.   {
  4706.     if (create_myisam_from_heap(table, &join->tmp_table_param, error, 0))
  4707.       DBUG_RETURN(-1);                // Not a table_is_full error
  4708.     /* Change method to update rows */
  4709.     table->file->index_init(0);
  4710.     join->join_tab[join->tables-1].next_select=end_unique_update;
  4711.   }
  4712.   join->send_records++;
  4713.   DBUG_RETURN(0);
  4714. }
  4715.  
  4716. /* Like end_update, but this is done with unique constraints instead of keys */
  4717.  
  4718. static int
  4719. end_unique_update(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
  4720.           bool end_of_records)
  4721. {
  4722.   TABLE *table=join->tmp_table;
  4723.   int      error;
  4724.   DBUG_ENTER("end_unique_update");
  4725.  
  4726.   if (end_of_records)
  4727.     DBUG_RETURN(0);
  4728.   if (join->thd->killed)            // Aborted by user
  4729.   {
  4730.     my_error(ER_SERVER_SHUTDOWN,MYF(0));    /* purecov: inspected */
  4731.     DBUG_RETURN(-2);                /* purecov: inspected */
  4732.   }
  4733.  
  4734.   init_tmptable_sum_functions(join->sum_funcs);
  4735.   copy_fields(&join->tmp_table_param);        // Groups are copied twice.
  4736.   copy_funcs(join->tmp_table_param.funcs);
  4737.  
  4738.   if (!(error=table->file->write_row(table->record[0])))
  4739.     join->send_records++;            // New group
  4740.   else
  4741.   {
  4742.     if ((int) table->file->get_dup_key(error) < 0)
  4743.     {
  4744.       table->file->print_error(error,MYF(0));    /* purecov: inspected */
  4745.       DBUG_RETURN(-1);                /* purecov: inspected */
  4746.     }
  4747.     if (table->file->rnd_pos(table->record[1],table->file->dupp_ref))
  4748.     {
  4749.       table->file->print_error(error,MYF(0));    /* purecov: inspected */
  4750.       DBUG_RETURN(-1);                /* purecov: inspected */
  4751.     }
  4752.     restore_record(table,1);
  4753.     update_tmptable_sum_func(join->sum_funcs,table);
  4754.     if ((error=table->file->update_row(table->record[1],
  4755.                        table->record[0])))
  4756.     {
  4757.       table->file->print_error(error,MYF(0));    /* purecov: inspected */
  4758.       DBUG_RETURN(-1);                /* purecov: inspected */
  4759.     }
  4760.   }
  4761.   DBUG_RETURN(0);
  4762. }
  4763.  
  4764.  
  4765.     /* ARGSUSED */
  4766. static int
  4767. end_write_group(JOIN *join, JOIN_TAB *join_tab __attribute__((unused)),
  4768.         bool end_of_records)
  4769. {
  4770.   TABLE *table=join->tmp_table;
  4771.   int      error;
  4772.   int      idx= -1;
  4773.   DBUG_ENTER("end_write_group");
  4774.  
  4775.   if (join->thd->killed)
  4776.   {                        // Aborted by user
  4777.     my_error(ER_SERVER_SHUTDOWN,MYF(0));    /* purecov: inspected */
  4778.     DBUG_RETURN(-2);                /* purecov: inspected */
  4779.   }
  4780.   if (!join->first_record || end_of_records ||
  4781.       (idx=test_if_group_changed(join->group_fields)) >= 0)
  4782.   {
  4783.     if (join->first_record || (end_of_records && !join->group))
  4784.     {
  4785.       if (join->procedure)
  4786.     join->procedure->end_group();
  4787.       if (idx < (int) join->send_group_parts)
  4788.       {
  4789.     if (!join->first_record)
  4790.       clear_tables(join);
  4791.     copy_sum_funcs(join->sum_funcs);
  4792.     if (!join->having || join->having->val_int())
  4793.     {
  4794.       if ((error=table->file->write_row(table->record[0])))
  4795.       {
  4796.         if (create_myisam_from_heap(table, &join->tmp_table_param,
  4797.                     error, 0))
  4798.           DBUG_RETURN(1);            // Not a table_is_full error
  4799.       }
  4800.       else
  4801.         join->send_records++;
  4802.     }
  4803.     if (end_of_records)
  4804.       DBUG_RETURN(0);
  4805.       }
  4806.     }
  4807.     else
  4808.     {
  4809.       join->first_record=1;
  4810.       VOID(test_if_group_changed(join->group_fields));
  4811.     }
  4812.     if (idx < (int) join->send_group_parts)
  4813.     {
  4814.       copy_fields(&join->tmp_table_param);
  4815.       copy_funcs(join->tmp_table_param.funcs);
  4816.       init_sum_functions(join->sum_funcs);
  4817.       if (join->procedure)
  4818.     join->procedure->add();
  4819.       DBUG_RETURN(0);
  4820.     }
  4821.   }
  4822.   if (update_sum_func(join->sum_funcs))
  4823.     DBUG_RETURN(-1);
  4824.   if (join->procedure)
  4825.     join->procedure->add();
  4826.   DBUG_RETURN(0);
  4827. }
  4828.  
  4829.  
  4830. /*****************************************************************************
  4831. ** Remove calculation with tables that aren't yet read. Remove also tests
  4832. ** against fields that are read through key.
  4833. ** We can't remove tests that are made against columns which are stored
  4834. ** in sorted order.
  4835. *****************************************************************************/
  4836.  
  4837. /* Return 1 if right_item is used removable reference key on left_item */
  4838.  
  4839. static bool test_if_ref(Item_field *left_item,Item *right_item)
  4840. {
  4841.   Field *field=left_item->field;
  4842.   if (!field->table->const_table)        // No need to change const test
  4843.   {
  4844.     Item *ref_item=part_of_refkey(field->table,field);
  4845.     if (ref_item && ref_item->eq(right_item))
  4846.     {
  4847.       if (right_item->type() == Item::FIELD_ITEM)
  4848.     return field->eq_def(((Item_field *) right_item)->field);
  4849.       if (right_item->const_item())
  4850.       {
  4851.     // We can remove binary fields and numerical fields except float,
  4852.     // as float comparison isn't 100 % secure
  4853.     if (field->binary() &&
  4854.         (field->type() != FIELD_TYPE_FLOAT || field->decimals() == 0))
  4855.     {
  4856.       return !store_val_in_field(field,right_item);
  4857.     }
  4858.       }
  4859.     }
  4860.   }
  4861.   return 0;                    // keep test
  4862. }
  4863.  
  4864.  
  4865. static COND *
  4866. make_cond_for_table(COND *cond,table_map tables,table_map used_table)
  4867. {
  4868.   if (used_table && !(cond->used_tables() & used_table))
  4869.     return (COND*) 0;                // Already checked
  4870.   if (cond->type() == Item::COND_ITEM)
  4871.   {
  4872.     if (((Item_cond*) cond)->functype() == Item_func::COND_AND_FUNC)
  4873.     {
  4874.       Item_cond_and *new_cond=new Item_cond_and;
  4875.       if (!new_cond)
  4876.     return (COND*) 0;            // OOM /* purecov: inspected */
  4877.       List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  4878.       Item *item;
  4879.       while ((item=li++))
  4880.       {
  4881.     Item *fix=make_cond_for_table(item,tables,used_table);
  4882.     if (fix)
  4883.       new_cond->argument_list()->push_back(fix);
  4884.       }
  4885.       switch (new_cond->argument_list()->elements) {
  4886.       case 0:
  4887.     return (COND*) 0;            // Always true
  4888.       case 1:
  4889.     return new_cond->argument_list()->head();
  4890.       default:
  4891.     new_cond->used_tables_cache=((Item_cond*) cond)->used_tables_cache &
  4892.       tables;
  4893.     return new_cond;
  4894.       }
  4895.     }
  4896.     else
  4897.     {                        // Or list
  4898.       Item_cond_or *new_cond=new Item_cond_or;
  4899.       if (!new_cond)
  4900.     return (COND*) 0;            // OOM /* purecov: inspected */
  4901.       List_iterator<Item> li(*((Item_cond*) cond)->argument_list());
  4902.       Item *item;
  4903.       while ((item=li++))
  4904.       {
  4905.     Item *fix=make_cond_for_table(item,tables,0L);
  4906.     if (!fix)
  4907.       return (COND*) 0;            // Always true
  4908.     new_cond->argument_list()->push_back(fix);
  4909.       }
  4910.       new_cond->used_tables_cache=((Item_cond_or*) cond)->used_tables_cache;
  4911.       return new_cond;
  4912.     }
  4913.   }
  4914.  
  4915.   /*
  4916.   ** Because the following test takes a while and it can be done
  4917.   ** table_count times, we mark each item that we have examined with the result
  4918.   ** of the test
  4919.   */
  4920.  
  4921.   if (cond->marker == 3 || (cond->used_tables() & ~tables))
  4922.     return (COND*) 0;                // Can't check this yet
  4923.   if (cond->marker == 2 || cond->eq_cmp_result() == Item::COND_OK)
  4924.     return cond;                // Not boolean op
  4925.  
  4926.   if (((Item_func*) cond)->functype() == Item_func::EQ_FUNC)
  4927.   {
  4928.     Item *left_item=    ((Item_func*) cond)->arguments()[0];
  4929.     Item *right_item= ((Item_func*) cond)->arguments()[1];
  4930.     if (left_item->type() == Item::FIELD_ITEM &&
  4931.     test_if_ref((Item_field*) left_item,right_item))
  4932.     {
  4933.       cond->marker=3;            // Checked when read
  4934.       return (COND*) 0;
  4935.     }
  4936.     if (right_item->type() == Item::FIELD_ITEM &&
  4937.     test_if_ref((Item_field*) right_item,left_item))
  4938.     {
  4939.       cond->marker=3;            // Checked when read
  4940.       return (COND*) 0;
  4941.     }
  4942.   }
  4943.   cond->marker=2;
  4944.   return cond;
  4945. }
  4946.  
  4947. static Item *
  4948. part_of_refkey(TABLE *table,Field *field)
  4949. {
  4950.   uint ref_parts=table->reginfo.join_tab->ref.key_parts;
  4951.   if (ref_parts)
  4952.   {
  4953.     KEY_PART_INFO *key_part=
  4954.       table->key_info[table->reginfo.join_tab->ref.key].key_part;
  4955.  
  4956.     for (uint part=0 ; part < ref_parts ; part++,key_part++)
  4957.       if (field->eq(key_part->field) &&
  4958.       !(key_part->key_part_flag & HA_PART_KEY))
  4959.     return table->reginfo.join_tab->ref.items[part];
  4960.   }
  4961.   return (Item*) 0;
  4962. }
  4963.  
  4964.  
  4965. /*****************************************************************************
  4966. ** Test if one can use the key to resolve ORDER BY
  4967. ** Returns: 1 if key is ok.
  4968. **        0 if key can't be used
  4969. **        -1 if reverse key can be used
  4970. *****************************************************************************/
  4971.  
  4972. static int test_if_order_by_key(ORDER *order, TABLE *table, uint idx)
  4973. {
  4974.   KEY_PART_INFO *key_part,*key_part_end;
  4975.   key_part=table->key_info[idx].key_part;
  4976.   key_part_end=key_part+table->key_info[idx].key_parts;
  4977.   key_part_map const_key_parts=table->const_key_parts[idx];
  4978.   int reverse=0;
  4979.  
  4980.   for (; order ; order=order->next, const_key_parts>>=1)
  4981.   {
  4982.     Field *field=((Item_field*) (*order->item))->field;
  4983.     int flag;
  4984.  
  4985.     /*
  4986.       Skip key parts that are constants in the WHERE clause.
  4987.       These are already skipped in the ORDER BY by const_expression_in_where()
  4988.     */
  4989.     while (const_key_parts & 1)
  4990.     {
  4991.       key_part++; const_key_parts>>=1;
  4992.     }
  4993.     if (key_part == key_part_end || key_part->field != field)
  4994.       return 0;
  4995.  
  4996.     /* set flag to 1 if we can use read-next on key, else to -1 */
  4997.     flag=(order->asc == !(key_part->key_part_flag & HA_REVERSE_SORT))
  4998.       ? 1 : -1;
  4999.     if (reverse && flag != reverse)
  5000.       return 0;
  5001.     reverse=flag;                // Remember if reverse
  5002.     key_part++;
  5003.   }
  5004.   return reverse;
  5005. }
  5006.  
  5007. static uint find_shortest_key(TABLE *table, key_map usable_keys)
  5008. {
  5009.   uint min_length= (uint) ~0;
  5010.   uint best= MAX_KEY;
  5011.   for (uint nr=0; usable_keys ; usable_keys>>=1, nr++)
  5012.   {
  5013.     if (usable_keys & 1)
  5014.     {
  5015.       if (table->key_info[nr].key_length < min_length)
  5016.       {
  5017.     min_length=table->key_info[nr].key_length;
  5018.     best=nr;
  5019.       }
  5020.     }
  5021.   }
  5022.   return best;
  5023. }
  5024.  
  5025.  
  5026. /*****************************************************************************
  5027. ** If not selecting by given key, create a index how records should be read
  5028. ** return: 0  ok
  5029. **      -1 some fatal error
  5030. **       1  no records
  5031. *****************************************************************************/
  5032.  
  5033. /* Return 1 if we don't have to do file sorting */
  5034.  
  5035. static bool
  5036. test_if_skip_sort_order(JOIN_TAB *tab,ORDER *order,ha_rows select_limit)
  5037. {
  5038.   int ref_key;
  5039.   TABLE *table=tab->table;
  5040.   SQL_SELECT *select=tab->select;
  5041.   key_map usable_keys;
  5042.   DBUG_ENTER("test_if_skip_sort_order");
  5043.  
  5044.   /* Check which keys can be used to resolve ORDER BY */
  5045.   usable_keys= ~(key_map) 0;
  5046.   for (ORDER *tmp_order=order; tmp_order ; tmp_order=tmp_order->next)
  5047.   {
  5048.     if ((*tmp_order->item)->type() != Item::FIELD_ITEM)
  5049.     {
  5050.       usable_keys=0;
  5051.       break;
  5052.     }
  5053.     usable_keys&=((Item_field*) (*tmp_order->item))->field->part_of_key;
  5054.   }
  5055.  
  5056.   ref_key= -1;
  5057.   if (tab->ref.key >= 0)            // Constant range in WHERE
  5058.     ref_key=tab->ref.key;
  5059.   else if (select && select->quick)        // Range found by opt_range
  5060.     ref_key=select->quick->index;
  5061.  
  5062.   if (ref_key >= 0)
  5063.   {
  5064.     /* Check if we get the rows in requested sorted order by using the key */
  5065.     if ((usable_keys & ((key_map) 1 << ref_key)) &&
  5066.     test_if_order_by_key(order,table,ref_key) == 1)
  5067.       DBUG_RETURN(1);            /* No need to sort */
  5068.   }
  5069.   else
  5070.   {
  5071.     /* check if we can use a key to resolve the group */
  5072.     /* Tables using JT_NEXT are handled here */
  5073.     uint nr;
  5074.     key_map keys=usable_keys;
  5075.  
  5076.     /*
  5077.       If not used with LIMIT, only use keys if the whole query can be
  5078.       resolved with a key;  This is because filesort() is usually faster than
  5079.       retrieving all rows through an index.
  5080.     */
  5081.     if (select_limit >= table->file->records)
  5082.       keys&= table->used_keys;
  5083.  
  5084.     for (nr=0; keys ; keys>>=1, nr++)
  5085.     {
  5086.       if (keys & 1)
  5087.       {
  5088.     int flag;
  5089.     if ((flag=test_if_order_by_key(order,table,nr)))
  5090.     {
  5091.       tab->index=nr;
  5092.       tab->read_first_record=  (flag > 0 ? join_init_read_first_with_key:
  5093.                     join_init_read_last_with_key);
  5094.       tab->type=JT_NEXT;    // Read with index_first(), index_next()
  5095.       DBUG_RETURN(1);
  5096.     }
  5097.       }
  5098.     }
  5099.   }
  5100.   DBUG_RETURN(0);                // Can't use index.
  5101. }
  5102.  
  5103. static int
  5104. create_sort_index(JOIN_TAB *tab,ORDER *order,ha_rows select_limit)
  5105. {
  5106.   SORT_FIELD *sortorder;
  5107.   uint length;
  5108.   TABLE *table=tab->table;
  5109.   SQL_SELECT *select=tab->select;
  5110.   DBUG_ENTER("create_sort_index");
  5111.  
  5112.   if (test_if_skip_sort_order(tab,order,select_limit))
  5113.     DBUG_RETURN(0);
  5114.   if (!(sortorder=make_unireg_sortorder(order,&length)))
  5115.     goto err;                /* purecov: inspected */
  5116.   /* It's not fatal if the following alloc fails */
  5117.   table->io_cache=(IO_CACHE*) my_malloc(sizeof(IO_CACHE),
  5118.                     MYF(MY_WME | MY_ZEROFILL));
  5119.   table->status=0;                // May be wrong if quick_select
  5120.  
  5121.   // If table has a range, move it to select
  5122.   if (select && !select->quick && tab->ref.key >= 0)
  5123.   {
  5124.     if (tab->quick)
  5125.     {
  5126.       select->quick=tab->quick;
  5127.       tab->quick=0;
  5128.       /* We can only use 'Only index' if quick key is same as ref_key */
  5129.       if (table->key_read && (uint) tab->ref.key != select->quick->index)
  5130.       {
  5131.     table->key_read=0;
  5132.     table->file->extra(HA_EXTRA_NO_KEYREAD);
  5133.       }
  5134.     }
  5135.     else
  5136.     {
  5137.       /*
  5138.     We have a ref on a const;  Change this to a range that filesort
  5139.     can use.
  5140.       */
  5141.       if (!(select->quick=get_ft_or_quick_select_for_ref(table, tab)))
  5142.     goto err;
  5143.     }
  5144.   }
  5145.   table->found_records=filesort(&table,sortorder,length,
  5146.                 select, 0L, select_limit);
  5147.   delete select;                // filesort did select
  5148.   tab->select=0;
  5149.   tab->select_cond=0;
  5150.   tab->type=JT_ALL;                // Read with normal read_record
  5151.   tab->read_first_record= join_init_read_record;
  5152.   if (table->key_read)                // Restore if we used indexes
  5153.   {
  5154.     table->key_read=0;
  5155.     table->file->extra(HA_EXTRA_NO_KEYREAD);
  5156.   }
  5157.   DBUG_RETURN(table->found_records == HA_POS_ERROR);
  5158. err:
  5159.   DBUG_RETURN(-1);
  5160. }
  5161.  
  5162.  
  5163. /*****************************************************************************
  5164. ** Remove duplicates from tmp table
  5165. ** This should be recoded to add a uniuqe index to the table and remove
  5166. ** dupplicates
  5167. ** Table is a locked single thread table
  5168. ** fields is the number of fields to check (from the end)
  5169. *****************************************************************************/
  5170.  
  5171. static bool compare_record(TABLE *table, Field **ptr)
  5172. {
  5173.   for (; *ptr ; ptr++)
  5174.   {
  5175.     if ((*ptr)->cmp_offset(table->rec_buff_length))
  5176.       return 1;
  5177.   }
  5178.   return 0;
  5179. }
  5180.  
  5181. static bool copy_blobs(Field **ptr)
  5182. {
  5183.   for (; *ptr ; ptr++)
  5184.   {
  5185.     if ((*ptr)->flags & BLOB_FLAG)
  5186.       if (((Field_blob *) (*ptr))->copy())
  5187.     return 1;                // Error
  5188.   }
  5189.   return 0;
  5190. }
  5191.  
  5192. static void free_blobs(Field **ptr)
  5193. {
  5194.   for (; *ptr ; ptr++)
  5195.   {
  5196.     if ((*ptr)->flags & BLOB_FLAG)
  5197.       ((Field_blob *) (*ptr))->free();
  5198.   }
  5199. }
  5200.  
  5201.  
  5202. static int
  5203. remove_duplicates(JOIN *join, TABLE *entry,List<Item> &fields)
  5204. {
  5205.   int error;
  5206.   ulong reclength,offset;
  5207.   uint field_count;
  5208.   DBUG_ENTER("remove_duplicates");
  5209.  
  5210.   entry->reginfo.lock_type=TL_WRITE;
  5211.   entry->file->extra(HA_EXTRA_NO_READCHECK);
  5212.  
  5213.   /* Calculate how many saved fields there is in list */
  5214.   field_count=0;
  5215.   List_iterator<Item> it(fields);
  5216.   Item *item;
  5217.   while ((item=it++))
  5218.     if (item->tmp_table_field())
  5219.       field_count++;
  5220.  
  5221.   if (!field_count)
  5222.   {                        // only const items
  5223.     join->thd->select_limit=1;            // Only send first row
  5224.     DBUG_RETURN(0);
  5225.   }
  5226.   Field **first_field=entry->field+entry->fields - field_count;
  5227.   offset=entry->field[entry->fields - field_count]->offset();
  5228.   reclength=entry->reclength-offset;
  5229.  
  5230.   free_io_cache(entry);                // Safety
  5231.   entry->file->info(HA_STATUS_VARIABLE);
  5232.   if (entry->db_type == DB_TYPE_HEAP ||
  5233.       (!entry->blob_fields &&
  5234.        ((ALIGN_SIZE(reclength) +sizeof(HASH_LINK)) * entry->file->records <
  5235.     sortbuff_size)))
  5236.     error=remove_dup_with_hash_index(join->thd, entry,
  5237.                      field_count, first_field,
  5238.                      reclength);
  5239.   else
  5240.     error=remove_dup_with_compare(join->thd, entry, first_field, offset);
  5241.  
  5242.   free_blobs(first_field);
  5243.   DBUG_RETURN(error);
  5244. }
  5245.  
  5246.  
  5247. static int remove_dup_with_compare(THD *thd, TABLE *table, Field **first_field,
  5248.                    ulong offset)
  5249. {
  5250.   handler *file=table->file;
  5251.   char *org_record,*new_record;
  5252.   int error;
  5253.   ulong reclength=table->reclength-offset;
  5254.   DBUG_ENTER("remove_dup_with_compare");
  5255.  
  5256.   org_record=(char*) table->record[0]+offset;
  5257.   new_record=(char*) table->record[1]+offset;
  5258.  
  5259.   file->rnd_init();
  5260.   error=file->rnd_next(table->record[0]);
  5261.   for (;;)
  5262.   {
  5263.     if (thd->killed)
  5264.     {
  5265.       my_error(ER_SERVER_SHUTDOWN,MYF(0));
  5266.       error=0;
  5267.       goto err;
  5268.     }
  5269.     if (error)
  5270.     {
  5271.       if (error == HA_ERR_RECORD_DELETED)
  5272.     continue;
  5273.       if (error == HA_ERR_END_OF_FILE)
  5274.     break;
  5275.       goto err;
  5276.     }
  5277.     if (copy_blobs(first_field))
  5278.     {
  5279.       my_error(ER_OUT_OF_SORTMEMORY,MYF(0));
  5280.       error=0;
  5281.       goto err;
  5282.     }
  5283.     memcpy(new_record,org_record,reclength);
  5284.  
  5285.     /* Read through rest of file and mark duplicated rows deleted */
  5286.     bool found=0;
  5287.     for (;;)
  5288.     {
  5289.       if ((error=file->rnd_next(table->record[0])))
  5290.       {
  5291.     if (error == HA_ERR_RECORD_DELETED)
  5292.       continue;
  5293.     if (error == HA_ERR_END_OF_FILE)
  5294.       break;
  5295.     goto err;
  5296.       }
  5297.       if (compare_record(table, first_field) == 0)
  5298.       {
  5299.     if ((error=file->delete_row(table->record[0])))
  5300.       goto err;
  5301.       }
  5302.       else if (!found)
  5303.       {
  5304.     found=1;
  5305.     file->position(table->record[0]);    // Remember position
  5306.       }
  5307.     }
  5308.     if (!found)
  5309.       break;                    // End of file
  5310.     /* Restart search on next row */
  5311.     error=file->restart_rnd_next(table->record[0],file->ref);
  5312.   }
  5313.  
  5314.   file->extra(HA_EXTRA_NO_CACHE);
  5315.   DBUG_RETURN(0);
  5316. err:
  5317.   file->extra(HA_EXTRA_NO_CACHE);
  5318.   if (error)
  5319.     file->print_error(error,MYF(0));
  5320.   DBUG_RETURN(1);
  5321. }
  5322.  
  5323.  
  5324. /*
  5325.   Generate a hash index for each row to quickly find duplicate rows
  5326.   Note that this will not work on tables with blobs!
  5327. */
  5328.  
  5329. static int remove_dup_with_hash_index(THD *thd, TABLE *table,
  5330.                       uint field_count,
  5331.                       Field **first_field,
  5332.                       ulong key_length)
  5333. {
  5334.   byte *key_buffer, *key_pos, *record=table->record[0];
  5335.   int error;
  5336.   handler *file=table->file;
  5337.   ulong extra_length=ALIGN_SIZE(key_length)-key_length;
  5338.   uint *field_lengths,*field_length;
  5339.   HASH hash;
  5340.   DBUG_ENTER("remove_dup_with_hash_index");
  5341.  
  5342.   if (!my_multi_malloc(MYF(MY_WME),
  5343.                &key_buffer,
  5344.                (uint) ((key_length + extra_length) *
  5345.                    (long) file->records),
  5346.                &field_lengths,
  5347.                (uint) (field_count*sizeof(*field_lengths)),
  5348.                NullS))
  5349.     DBUG_RETURN(1);
  5350.   if (hash_init(&hash, (uint) file->records, 0, key_length,
  5351.         (hash_get_key) 0, 0, 0))
  5352.   {
  5353.     my_free((char*) key_buffer,MYF(0));
  5354.     DBUG_RETURN(1);
  5355.   }
  5356.   {
  5357.     Field **ptr;
  5358.     for (ptr= first_field, field_length=field_lengths ; *ptr ; ptr++)
  5359.       (*field_length++)= (*ptr)->pack_length();
  5360.   }
  5361.  
  5362.   file->rnd_init();
  5363.   key_pos=key_buffer;
  5364.   for (;;)
  5365.   {
  5366.     if (thd->killed)
  5367.     {
  5368.       my_error(ER_SERVER_SHUTDOWN,MYF(0));
  5369.       error=0;
  5370.       goto err;
  5371.     }
  5372.     if ((error=file->rnd_next(record)))
  5373.     {
  5374.       if (error == HA_ERR_RECORD_DELETED)
  5375.     continue;
  5376.       if (error == HA_ERR_END_OF_FILE)
  5377.     break;
  5378.       goto err;
  5379.     }
  5380.  
  5381.     /* copy fields to key buffer */
  5382.     field_length=field_lengths;
  5383.     for (Field **ptr= first_field ; *ptr ; ptr++)
  5384.     {
  5385.       (*ptr)->sort_string((char*) key_pos,*field_length);
  5386.       key_pos+= *field_length++;
  5387.     }
  5388.     /* Check if it exists before */
  5389.     if (hash_search(&hash,key_pos-key_length,key_length))
  5390.     {
  5391.       /* Duplicated found ; Remove the row */
  5392.       if ((error=file->delete_row(record)))
  5393.     goto err;
  5394.     }
  5395.     (void) hash_insert(&hash, key_pos-key_length);
  5396.     key_pos+=extra_length;
  5397.   }
  5398.   my_free((char*) key_buffer,MYF(0));
  5399.   hash_free(&hash);
  5400.   file->extra(HA_EXTRA_NO_CACHE);
  5401.   (void) file->rnd_end();
  5402.   DBUG_RETURN(0);
  5403.  
  5404. err:
  5405.   my_free((char*) key_buffer,MYF(0));
  5406.   hash_free(&hash);
  5407.   file->extra(HA_EXTRA_NO_CACHE);
  5408.   (void) file->rnd_end();
  5409.   if (error)
  5410.     file->print_error(error,MYF(0));
  5411.   DBUG_RETURN(1);
  5412. }
  5413.  
  5414.  
  5415. SORT_FIELD *make_unireg_sortorder(ORDER *order, uint *length)
  5416. {
  5417.   uint count;
  5418.   SORT_FIELD *sort,*pos;
  5419.   DBUG_ENTER("make_unireg_sortorder");
  5420.  
  5421.   count=0;
  5422.   for (ORDER *tmp = order; tmp; tmp=tmp->next)
  5423.     count++;
  5424.   pos=sort=(SORT_FIELD*) sql_alloc(sizeof(SORT_FIELD)*(count+1));
  5425.   if (!pos)
  5426.     return 0;
  5427.  
  5428.   for (;order;order=order->next,pos++)
  5429.   {
  5430.     pos->field=0; pos->item=0;
  5431.     if (order->item[0]->type() == Item::FIELD_ITEM)
  5432.       pos->field= ((Item_field*) (*order->item))->field;
  5433.     else if (order->item[0]->type() == Item::SUM_FUNC_ITEM &&
  5434.          !order->item[0]->const_item())
  5435.       pos->field= ((Item_sum*) order->item[0])->tmp_table_field();
  5436.     else if (order->item[0]->type() == Item::COPY_STR_ITEM)
  5437.     {                        // Blob patch
  5438.       pos->item= ((Item_copy_string*) (*order->item))->item;
  5439.     }
  5440.     else
  5441.       pos->item= *order->item;
  5442.     pos->reverse=! order->asc;
  5443.   }
  5444.   *length=count;
  5445.   DBUG_RETURN(sort);
  5446. }
  5447.  
  5448.  
  5449. /*****************************************************************************
  5450. **    Fill join cache with packed records
  5451. **    Records are stored in tab->cache.buffer and last record in
  5452. **    last record is stored with pointers to blobs to support very big
  5453. **    records
  5454. ******************************************************************************/
  5455.  
  5456. static int
  5457. join_init_cache(THD *thd,JOIN_TAB *tables,uint table_count)
  5458. {
  5459.   reg1 uint i;
  5460.   uint length,blobs,size;
  5461.   CACHE_FIELD *copy,**blob_ptr;
  5462.   JOIN_CACHE  *cache;
  5463.   DBUG_ENTER("join_init_cache");
  5464.  
  5465.   cache= &tables[table_count].cache;
  5466.   cache->fields=blobs=0;
  5467.  
  5468.   for (i=0 ; i < table_count ; i++)
  5469.   {
  5470.     cache->fields+=tables[i].used_fields;
  5471.     blobs+=tables[i].used_blobs;
  5472.   }
  5473.   if (!(cache->field=(CACHE_FIELD*)
  5474.     sql_alloc(sizeof(CACHE_FIELD)*(cache->fields+table_count*2)+(blobs+1)*
  5475.           sizeof(CACHE_FIELD*))))
  5476.   {
  5477.     my_free((gptr) cache->buff,MYF(0));        /* purecov: inspected */
  5478.     cache->buff=0;                /* purecov: inspected */
  5479.     DBUG_RETURN(1);                /* purecov: inspected */
  5480.   }
  5481.   copy=cache->field;
  5482.   blob_ptr=cache->blob_ptr=(CACHE_FIELD**)
  5483.     (cache->field+cache->fields+table_count*2);
  5484.  
  5485.   length=0;
  5486.   for (i=0 ; i < table_count ; i++)
  5487.   {
  5488.     uint null_fields=0,used_fields;
  5489.  
  5490.     Field **f_ptr,*field;
  5491.     for (f_ptr=tables[i].table->field,used_fields=tables[i].used_fields ;
  5492.      used_fields ;
  5493.      f_ptr++)
  5494.     {
  5495.       field= *f_ptr;
  5496.       if (field->query_id == thd->query_id)
  5497.       {
  5498.     used_fields--;
  5499.     length+=field->fill_cache_field(copy);
  5500.     if (copy->blob_field)
  5501.       (*blob_ptr++)=copy;
  5502.     if (field->maybe_null())
  5503.       null_fields++;
  5504.     copy++;
  5505.       }
  5506.     }
  5507.     /* Copy null bits from table */
  5508.     if (null_fields && tables[i].table->null_fields)
  5509.     {                        /* must copy null bits */
  5510.       copy->str=(char*) tables[i].table->null_flags;
  5511.       copy->length=(tables[i].table->null_fields+7)/8;
  5512.       copy->strip=0;
  5513.       copy->blob_field=0;
  5514.       length+=copy->length;
  5515.       copy++;
  5516.       cache->fields++;
  5517.     }
  5518.     /* If outer join table, copy null_row flag */
  5519.     if (tables[i].table->maybe_null)
  5520.     {
  5521.       copy->str= (char*) &tables[i].table->null_row;
  5522.       copy->length=sizeof(tables[i].table->null_row);
  5523.       copy->strip=0;
  5524.       copy->blob_field=0;
  5525.       length+=copy->length;
  5526.       copy++;
  5527.       cache->fields++;
  5528.     }
  5529.   }
  5530.  
  5531.   cache->records=0; cache->ptr_record= (uint) ~0;
  5532.   cache->length=length+blobs*sizeof(char*);
  5533.   cache->blobs=blobs;
  5534.   *blob_ptr=0;                    /* End sequentel */
  5535.   size=max(join_buff_size,cache->length);
  5536.   if (!(cache->buff=(uchar*) my_malloc(size,MYF(0))))
  5537.     DBUG_RETURN(1);                /* Don't use cache */ /* purecov: inspected */
  5538.   cache->end=cache->buff+size;
  5539.   reset_cache(cache);
  5540.   DBUG_RETURN(0);
  5541. }
  5542.  
  5543.  
  5544. static ulong
  5545. used_blob_length(CACHE_FIELD **ptr)
  5546. {
  5547.   uint length,blob_length;
  5548.   for (length=0 ; *ptr ; ptr++)
  5549.   {
  5550.     (*ptr)->blob_length=blob_length=(*ptr)->blob_field->get_length();
  5551.     length+=blob_length;
  5552.     (*ptr)->blob_field->get_ptr(&(*ptr)->str);
  5553.   }
  5554.   return length;
  5555. }
  5556.  
  5557.  
  5558. static bool
  5559. store_record_in_cache(JOIN_CACHE *cache)
  5560. {
  5561.   ulong length;
  5562.   uchar *pos;
  5563.   CACHE_FIELD *copy,*end_field;
  5564.   bool last_record;
  5565.  
  5566.   pos=cache->pos;
  5567.   end_field=cache->field+cache->fields;
  5568.  
  5569.   length=cache->length;
  5570.   if (cache->blobs)
  5571.     length+=used_blob_length(cache->blob_ptr);
  5572.   if ((last_record=(length+cache->length > (uint) (cache->end - pos))))
  5573.     cache->ptr_record=cache->records;
  5574.  
  5575.   /*
  5576.   ** There is room in cache. Put record there
  5577.   */
  5578.   cache->records++;
  5579.   for (copy=cache->field ; copy < end_field; copy++)
  5580.   {
  5581.     if (copy->blob_field)
  5582.     {
  5583.       if (last_record)
  5584.       {
  5585.     copy->blob_field->get_image((char*) pos,copy->length+sizeof(char*));
  5586.     pos+=copy->length+sizeof(char*);
  5587.       }
  5588.       else
  5589.       {
  5590.     copy->blob_field->get_image((char*) pos,copy->length); // blob length
  5591.     memcpy(pos+copy->length,copy->str,copy->blob_length);  // Blob data
  5592.     pos+=copy->length+copy->blob_length;
  5593.       }
  5594.     }
  5595.     else
  5596.     {
  5597.       if (copy->strip)
  5598.       {
  5599.     char *str,*end;
  5600.     for (str=copy->str,end= str+copy->length;
  5601.          end > str && end[-1] == ' ' ;
  5602.          end--) ;
  5603.     length=(uint) (end-str);
  5604.     memcpy(pos+1,str,length);
  5605.     *pos=(uchar) length;
  5606.     pos+=length+1;
  5607.       }
  5608.       else
  5609.       {
  5610.     memcpy(pos,copy->str,copy->length);
  5611.     pos+=copy->length;
  5612.       }
  5613.     }
  5614.   }
  5615.   cache->pos=pos;
  5616.   return last_record || (uint) (cache->end -pos) < cache->length;
  5617. }
  5618.  
  5619.  
  5620. static void
  5621. reset_cache(JOIN_CACHE *cache)
  5622. {
  5623.   cache->record_nr=0;
  5624.   cache->pos=cache->buff;
  5625. }
  5626.  
  5627.  
  5628. static void
  5629. read_cached_record(JOIN_TAB *tab)
  5630. {
  5631.   uchar *pos;
  5632.   uint length;
  5633.   bool last_record;
  5634.   CACHE_FIELD *copy,*end_field;
  5635.  
  5636.   last_record=tab->cache.record_nr++ == tab->cache.ptr_record;
  5637.   pos=tab->cache.pos;
  5638.  
  5639.   for (copy=tab->cache.field,end_field=copy+tab->cache.fields ;
  5640.        copy < end_field;
  5641.        copy++)
  5642.   {
  5643.     if (copy->blob_field)
  5644.     {
  5645.       if (last_record)
  5646.       {
  5647.     copy->blob_field->set_image((char*) pos,copy->length+sizeof(char*));
  5648.     pos+=copy->length+sizeof(char*);
  5649.       }
  5650.       else
  5651.       {
  5652.     copy->blob_field->set_ptr((char*) pos,(char*) pos+copy->length);
  5653.     pos+=copy->length+copy->blob_field->get_length();
  5654.       }
  5655.     }
  5656.     else
  5657.     {
  5658.       if (copy->strip)
  5659.       {
  5660.     memcpy(copy->str,pos+1,length=(uint) *pos);
  5661.     memset(copy->str+length,' ',copy->length-length);
  5662.     pos+=1+length;
  5663.       }
  5664.       else
  5665.       {
  5666.     memcpy(copy->str,pos,copy->length);
  5667.     pos+=copy->length;
  5668.       }
  5669.     }
  5670.   }
  5671.   tab->cache.pos=pos;
  5672.   return;
  5673. }
  5674.  
  5675.  
  5676. static bool
  5677. cmp_buffer_with_ref(JOIN_TAB *tab)
  5678. {
  5679.   bool diff;
  5680.   if (!(diff=tab->ref.key_err))
  5681.   {
  5682.     memcpy(tab->ref.key_buff2, tab->ref.key_buff, tab->ref.key_length);
  5683.   }
  5684.   if ((tab->ref.key_err=cp_buffer_from_ref(&tab->ref)) || diff)
  5685.     return 1;
  5686.   return memcmp(tab->ref.key_buff2, tab->ref.key_buff, tab->ref.key_length)
  5687.     != 0;
  5688. }
  5689.  
  5690.  
  5691. bool
  5692. cp_buffer_from_ref(TABLE_REF *ref)
  5693. {
  5694.   for (store_key **copy=ref->key_copy ; *copy ; copy++)
  5695.     if ((*copy)->copy())
  5696.       return 1;                    // Something went wrong
  5697.   return 0;
  5698. }
  5699.  
  5700.  
  5701. /*****************************************************************************
  5702. ** Group and order functions
  5703. *****************************************************************************/
  5704.  
  5705. /*
  5706. ** Find order/group item in requested columns and change the item to point at
  5707. ** it. If item doesn't exists, add it first in the field list
  5708. ** Return 0 if ok.
  5709. */
  5710.  
  5711. static int
  5712. find_order_in_list(THD *thd,TABLE_LIST *tables,ORDER *order,List<Item> &fields,
  5713.            List<Item> &all_fields)
  5714. {
  5715.   if ((*order->item)->type() == Item::INT_ITEM)
  5716.   {                        /* Order by position */
  5717.     Item *item=0;
  5718.     List_iterator<Item> li(fields);
  5719.  
  5720.     for (uint count= (uint) ((Item_int*) (*order->item))->value ;
  5721.      count-- && (item=li++) ;) ;
  5722.     if (!item)
  5723.     {
  5724.       my_printf_error(ER_BAD_FIELD_ERROR,ER(ER_BAD_FIELD_ERROR),
  5725.               MYF(0),(*order->item)->full_name(),
  5726.            thd->where);
  5727.       return 1;
  5728.     }
  5729.     order->item=li.ref();
  5730.     order->in_field_list=1;
  5731.     return 0;
  5732.   }
  5733.   const char *save_where=thd->where;
  5734.   thd->where=0;                    // No error if not found
  5735.   Item **item=find_item_in_list(*order->item,fields);
  5736.   thd->where=save_where;
  5737.   if (item)
  5738.   {
  5739.     order->item=item;                // use it
  5740.     order->in_field_list=1;
  5741.     return 0;
  5742.   }
  5743.   order->in_field_list=0;
  5744.   if ((*order->item)->fix_fields(thd,tables) || thd->fatal_error)
  5745.     return 1;                    // Wrong field
  5746.   all_fields.push_front(*order->item);        // Add new field to field list
  5747.   order->item=(Item**) all_fields.head_ref();
  5748.   return 0;
  5749. }
  5750.  
  5751.  
  5752. /*
  5753. ** Change order to point at item in select list. If item isn't a number
  5754. ** and doesn't exits in the select list, add it the the field list.
  5755. */
  5756.  
  5757. int setup_order(THD *thd,TABLE_LIST *tables,List<Item> &fields,
  5758.          List<Item> &all_fields, ORDER *order)
  5759. {
  5760.   thd->where="order clause";
  5761.   for (; order; order=order->next)
  5762.   {
  5763.     if (find_order_in_list(thd,tables,order,fields,all_fields))
  5764.       return 1;
  5765.   }
  5766.   return 0;
  5767. }
  5768.  
  5769.  
  5770. static int
  5771. setup_group(THD *thd,TABLE_LIST *tables,List<Item> &fields,
  5772.         List<Item> &all_fields, ORDER *order, bool *hidden_group_fields)
  5773. {
  5774.   *hidden_group_fields=0;
  5775.   if (!order)
  5776.     return 0;                /* Everything is ok */
  5777.  
  5778.   if (thd->options & OPTION_ANSI_MODE)
  5779.   {
  5780.     Item *item;
  5781.     List_iterator<Item> li(fields);
  5782.     while ((item=li++))
  5783.       item->marker=0;            /* Marker that field is not used */
  5784.   }
  5785.   uint org_fields=all_fields.elements;
  5786.  
  5787.   thd->where="group statement";
  5788.   for ( ; order; order=order->next)
  5789.   {
  5790.     if (find_order_in_list(thd,tables,order,fields,all_fields))
  5791.       return 1;
  5792.     (*order->item)->marker=1;        /* Mark found */
  5793.     if ((*order->item)->with_sum_func)
  5794.     {
  5795.       my_printf_error(ER_WRONG_GROUP_FIELD, ER(ER_WRONG_GROUP_FIELD),MYF(0),
  5796.               (*order->item)->full_name());
  5797.       return 1;
  5798.     }
  5799.   }
  5800.   if (thd->options & OPTION_ANSI_MODE)
  5801.   {
  5802.     /* Don't allow one to use fields that is not used in GROUP BY */
  5803.     Item *item;
  5804.     List_iterator<Item> li(fields);
  5805.  
  5806.     while ((item=li++))
  5807.     {
  5808.       if (item->type() != Item::SUM_FUNC_ITEM && !item->marker)
  5809.       {
  5810.     my_printf_error(ER_WRONG_FIELD_WITH_GROUP,
  5811.             ER(ER_WRONG_FIELD_WITH_GROUP),
  5812.             MYF(0),item->full_name());
  5813.     return 1;
  5814.       }
  5815.     }
  5816.   }
  5817.   if (org_fields != all_fields.elements)
  5818.     *hidden_group_fields=1;            // group fields is not used
  5819.   return 0;
  5820. }
  5821.  
  5822. /*
  5823. ** Add fields with aren't used at start of field list. Return FALSE if ok
  5824. */
  5825.  
  5826. static bool
  5827. setup_new_fields(THD *thd,TABLE_LIST *tables,List<Item> &fields,
  5828.          List<Item> &all_fields, ORDER *new_field)
  5829. {
  5830.   Item      **item;
  5831.   DBUG_ENTER("setup_new_fields");
  5832.  
  5833.   thd->set_query_id=1;                // Not really needed, but...
  5834.   thd->where=0;                    // Don't give error
  5835.   for ( ; new_field ; new_field=new_field->next)
  5836.   {
  5837.     if ((item=find_item_in_list(*new_field->item,fields)))
  5838.       new_field->item=item;            /* Change to shared Item */
  5839.     else
  5840.     {
  5841.       thd->where="procedure list";
  5842.       if ((*new_field->item)->fix_fields(thd,tables))
  5843.     DBUG_RETURN(1); /* purecov: inspected */
  5844.       thd->where=0;
  5845.       all_fields.push_front(*new_field->item);
  5846.       new_field->item=all_fields.head_ref();
  5847.     }
  5848.   }
  5849.   DBUG_RETURN(0);
  5850. }
  5851.  
  5852. /*
  5853. ** Create a group by that consist of all non const fields. Try to use
  5854. ** the fields in the order given by 'order' to allow one to optimize
  5855. ** away 'order by'.
  5856. */
  5857.  
  5858. static ORDER *
  5859. create_distinct_group(ORDER *order_list,List<Item> &fields)
  5860. {
  5861.   List_iterator<Item> li(fields);
  5862.   Item *item;
  5863.   ORDER *order,*group,**prev;
  5864.  
  5865.   while ((item=li++))
  5866.     item->marker=0;            /* Marker that field is not used */
  5867.  
  5868.   prev= &group;  group=0;
  5869.   for (order=order_list ; order; order=order->next)
  5870.   {
  5871.     if (order->in_field_list)
  5872.     {
  5873.       ORDER *ord=(ORDER*) sql_memdup(order,sizeof(ORDER));
  5874.       if (!ord)
  5875.     return 0;
  5876.       *prev=ord;
  5877.       prev= &ord->next;
  5878.       (*ord->item)->marker=1;
  5879.     }
  5880.   }
  5881.  
  5882.   li.rewind();
  5883.   while ((item=li++))
  5884.   {
  5885.     if (item->const_item() || item->with_sum_func)
  5886.       continue;
  5887.     if (!item->marker)
  5888.     {
  5889.       ORDER *ord=(ORDER*) sql_calloc(sizeof(ORDER));
  5890.       if (!ord)
  5891.     return 0;
  5892.       ord->item=li.ref();
  5893.       ord->asc=1;
  5894.       *prev=ord;
  5895.       prev= &ord->next;
  5896.     }
  5897.   }
  5898.   *prev=0;
  5899.   return group;
  5900. }
  5901.  
  5902.  
  5903. /*****************************************************************************
  5904. ** Update join with count of the different type of fields
  5905. *****************************************************************************/
  5906.  
  5907. void
  5908. count_field_types(TMP_TABLE_PARAM *param, List<Item> &fields)
  5909. {
  5910.   List_iterator<Item> li(fields);
  5911.   Item *field;
  5912.  
  5913.   param->field_count=param->sum_func_count=
  5914.     param->func_count=0;
  5915.   param->quick_group=1;
  5916.   while ((field=li++))
  5917.   {
  5918.     Item::Type type=field->type();
  5919.     if (type == Item::FIELD_ITEM)
  5920.       param->field_count++;
  5921.     else if (type == Item::SUM_FUNC_ITEM)
  5922.     {
  5923.       if (! field->const_item())
  5924.       {
  5925.     Item_sum *sum_item=(Item_sum*) field;
  5926.     if (!sum_item->quick_group)
  5927.       param->quick_group=0;            // UDF SUM function
  5928.     param->sum_func_count++;
  5929.  
  5930.     for (uint i=0 ; i < sum_item->arg_count ; i++)
  5931.     {
  5932.       if (sum_item->args[0]->type() == Item::FIELD_ITEM)
  5933.         param->field_count++;
  5934.       else
  5935.         param->func_count++;
  5936.     }
  5937.       }
  5938.     }
  5939.     else
  5940.       param->func_count++;
  5941.   }
  5942. }
  5943.  
  5944.  
  5945. /*
  5946.   Return 1 if second is a subpart of first argument
  5947.   If first parts has different direction, change it to second part
  5948.   (group is sorted like order)
  5949. */
  5950.  
  5951. static bool
  5952. test_if_subpart(ORDER *a,ORDER *b)
  5953. {
  5954.   for (; a && b; a=a->next,b=b->next)
  5955.   {
  5956.     if ((*a->item)->eq(*b->item))
  5957.       a->asc=b->asc;
  5958.     else
  5959.       return 0;
  5960.   }
  5961.   return test(!b);
  5962. }
  5963.  
  5964. /*
  5965.   Return table number if there is only one table in sort order
  5966.   and group and order is compatible
  5967.   else return 0;
  5968. */
  5969.  
  5970. static TABLE *
  5971. get_sort_by_table(ORDER *a,ORDER *b,TABLE_LIST *tables)
  5972. {
  5973.   table_map map= (table_map) 0;
  5974.   DBUG_ENTER("get_sort_by_table");
  5975.  
  5976.   if (!a)
  5977.     a=b;                    // Only one need to be given
  5978.   else if (!b)
  5979.     b=a;
  5980.  
  5981.   for (; a && b; a=a->next,b=b->next)
  5982.   {
  5983.     if (!(*a->item)->eq(*b->item))
  5984.       DBUG_RETURN(0);
  5985.     map|=a->item[0]->used_tables();
  5986.   }
  5987.   if (!map || (map & RAND_TABLE_BIT))
  5988.     DBUG_RETURN(0);
  5989.  
  5990.   for ( ; !(map & tables->table->map) ; tables=tables->next) ;
  5991.   if (map != tables->table->map)
  5992.     DBUG_RETURN(0);                // More than one table
  5993.   DBUG_PRINT("exit",("sort by table: %d",tables->table->tablenr));
  5994.   DBUG_RETURN(tables->table);
  5995. }
  5996.  
  5997.  
  5998.     /* calc how big buffer we need for comparing group entries */
  5999.  
  6000. static void
  6001. calc_group_buffer(JOIN *join,ORDER *group)
  6002. {
  6003.   uint key_length=0,parts=0;
  6004.   if (group)
  6005.     join->group= 1;
  6006.   for (; group ; group=group->next)
  6007.   {
  6008.     Field *field=(*group->item)->tmp_table_field();
  6009.     if (field)
  6010.     {
  6011.       if (field->type() == FIELD_TYPE_BLOB)
  6012.     key_length+=MAX_BLOB_WIDTH;        // Can't be used as a key
  6013.       else
  6014.     key_length+=field->pack_length();
  6015.     }
  6016.     else if ((*group->item)->result_type() == REAL_RESULT)
  6017.       key_length+=sizeof(double);
  6018.     else if ((*group->item)->result_type() == INT_RESULT)
  6019.       key_length+=sizeof(longlong);
  6020.     else
  6021.       key_length+=(*group->item)->max_length;
  6022.     parts++;
  6023.     if ((*group->item)->maybe_null)
  6024.       key_length++;
  6025.   }
  6026.   join->tmp_table_param.group_length=key_length;
  6027.   join->tmp_table_param.group_parts=parts;
  6028. }
  6029.  
  6030.  
  6031. /*
  6032. ** Get a list of buffers for saveing last group
  6033. ** Groups are saved in reverse order for easyer check loop
  6034. */
  6035.  
  6036. static bool
  6037. alloc_group_fields(JOIN *join,ORDER *group)
  6038. {
  6039.   if (group)
  6040.   {
  6041.     for (; group ; group=group->next)
  6042.     {
  6043.       Item_buff *tmp=new_Item_buff(*group->item);
  6044.       if (!tmp || join->group_fields.push_front(tmp))
  6045.     return TRUE;
  6046.     }
  6047.   }
  6048.   join->sort_and_group=1;            /* Mark for do_select */
  6049.   return FALSE;
  6050. }
  6051.  
  6052.  
  6053. static int
  6054. test_if_group_changed(List<Item_buff> &list)
  6055. {
  6056.   List_iterator<Item_buff> li(list);
  6057.   int idx= -1,i;
  6058.   Item_buff *buff;
  6059.  
  6060.   for (i=(int) list.elements-1 ; (buff=li++) ; i--)
  6061.   {
  6062.     if (buff->cmp())
  6063.       idx=i;
  6064.   }
  6065.   return idx;
  6066. }
  6067.  
  6068.  
  6069.  
  6070. /*
  6071. ** Setup copy_fields to save fields at start of new group
  6072. ** Only FIELD_ITEM:s and FUNC_ITEM:s needs to be saved between groups.
  6073. ** Change old item_field to use a new field with points at saved fieldvalue
  6074. ** This function is only called before use of send_fields
  6075. */
  6076.  
  6077. bool
  6078. setup_copy_fields(TMP_TABLE_PARAM *param,List<Item> &fields)
  6079. {
  6080.   Item *pos;
  6081.   List_iterator<Item> li(fields);
  6082.   Copy_field *copy;
  6083.   DBUG_ENTER("setup_copy_fields");
  6084.  
  6085.   if (!(copy=param->copy_field= new Copy_field[param->field_count]))
  6086.     goto err;
  6087.  
  6088.   param->copy_funcs.empty();
  6089.   while ((pos=li++))
  6090.   {
  6091.     if (pos->type() == Item::FIELD_ITEM)
  6092.     {
  6093.       Item_field *item=(Item_field*) pos;
  6094.       if (item->field->flags & BLOB_FLAG)
  6095.       {
  6096.     if (!(pos=new Item_copy_string(pos)))
  6097.       goto err;
  6098.     VOID(li.replace(pos));
  6099.     if (param->copy_funcs.push_back(pos))
  6100.       goto err;
  6101.     continue;
  6102.       }
  6103.  
  6104.       /* set up save buffer and change result_field to point at saved value */
  6105.       Field *field= item->field;
  6106.       item->result_field=field->new_field(field->table);
  6107.       char *tmp=(char*) sql_alloc(field->pack_length()+1);
  6108.       if (!tmp)
  6109.     goto err;
  6110.       copy->set(tmp, item->result_field);
  6111.       item->result_field->move_field(copy->to_ptr,copy->to_null_ptr,1);
  6112.       copy++;
  6113.     }
  6114.     else if ((pos->type() == Item::FUNC_ITEM ||
  6115.           pos->type() == Item::COND_ITEM) &&
  6116.          !pos->with_sum_func)
  6117.     {                        // Save for send fields
  6118.       /* TODO:
  6119.      In most cases this result will be sent to the user.
  6120.      This should be changed to use copy_int or copy_real depending
  6121.      on how the value is to be used: In some cases this may be an
  6122.      argument in a group function, like: IF(ISNULL(col),0,COUNT(*))
  6123.       */
  6124.       if (!(pos=new Item_copy_string(pos)))
  6125.     goto err;
  6126.       VOID(li.replace(pos));
  6127.       if (param->copy_funcs.push_back(pos))
  6128.     goto err;
  6129.     }
  6130.   }
  6131.   param->copy_field_count= (uint) (copy - param->copy_field);
  6132.   DBUG_RETURN(0);
  6133.  
  6134.  err:
  6135.   delete [] param->copy_field;
  6136.   param->copy_field=0;
  6137.   DBUG_RETURN(TRUE);
  6138. }
  6139.  
  6140.  
  6141. /*
  6142. ** Copy fields and null values between two tables
  6143. */
  6144.  
  6145. void
  6146. copy_fields(TMP_TABLE_PARAM *param)
  6147. {
  6148.   Copy_field *ptr=param->copy_field;
  6149.   Copy_field *end=ptr+param->copy_field_count;
  6150.  
  6151.   for ( ; ptr != end; ptr++)
  6152.     (*ptr->do_copy)(ptr);
  6153.  
  6154.   List_iterator<Item> it(param->copy_funcs);
  6155.   Item_copy_string *item;
  6156.   while ((item = (Item_copy_string*) it++))
  6157.   {
  6158.     item->copy();
  6159.   }
  6160. }
  6161.  
  6162.  
  6163. /*****************************************************************************
  6164. ** Make an array of pointer to sum_functions to speed up sum_func calculation
  6165. *****************************************************************************/
  6166.  
  6167. static bool
  6168. make_sum_func_list(JOIN *join,List<Item> &fields)
  6169. {
  6170.   DBUG_ENTER("make_sum_func_list");
  6171.   Item_sum **func =
  6172.     (Item_sum**) sql_alloc(sizeof(Item_sum*)*
  6173.                (join->tmp_table_param.sum_func_count+1));
  6174.   if (!func)
  6175.     DBUG_RETURN(TRUE);
  6176.   List_iterator<Item> it(fields);
  6177.   join->sum_funcs=func;
  6178.  
  6179.   Item *field;
  6180.   while ((field=it++))
  6181.   {
  6182.     if (field->type() == Item::SUM_FUNC_ITEM && !field->const_item())
  6183.     {
  6184.       *func++=(Item_sum*) field;
  6185.       /* let COUNT(DISTINCT) create the temporary table */
  6186.       if (((Item_sum*) field)->setup(join->thd))
  6187.     DBUG_RETURN(TRUE);
  6188.     }
  6189.   }
  6190.   *func=0;                    // End marker
  6191.   DBUG_RETURN(FALSE);
  6192. }
  6193.  
  6194.  
  6195. /*
  6196. ** Change all funcs and sum_funcs to fields in tmp table
  6197. */
  6198.  
  6199. static bool
  6200. change_to_use_tmp_fields(List<Item> &items)
  6201. {
  6202.   List_iterator<Item> it(items);
  6203.   Item *item_field,*item;
  6204.  
  6205.   while ((item=it++))
  6206.   {
  6207.     Field *field;
  6208.     if (item->with_sum_func && item->type() != Item::SUM_FUNC_ITEM)
  6209.       continue;
  6210.     if (item->type() == Item::FIELD_ITEM)
  6211.     {
  6212.       ((Item_field*) item)->field=
  6213.     ((Item_field*) item)->result_field;
  6214.     }
  6215.     else if ((field=item->tmp_table_field()))
  6216.     {
  6217.       if (item->type() == Item::SUM_FUNC_ITEM && field->table->group)
  6218.     item_field=((Item_sum*) item)->result_item(field);
  6219.       else
  6220.     item_field=(Item*) new Item_field(field);
  6221.       if (!item_field)
  6222.     return TRUE;                // Fatal error
  6223.       item_field->name=item->name;        /*lint -e613 */
  6224. #ifndef DBUG_OFF
  6225.       if (_db_on_ && !item_field->name)
  6226.       {
  6227.     char buff[256];
  6228.     String str(buff,sizeof(buff));
  6229.     str.length(0);
  6230.     item->print(&str);
  6231.     item_field->name=sql_strmake(str.ptr(),str.length());
  6232.       }
  6233. #endif
  6234. #ifdef DELETE_ITEMS
  6235.       delete it.replace(item_field);        /*lint -e613 */
  6236. #else
  6237.       (void) it.replace(item_field);        /*lint -e613 */
  6238. #endif
  6239.     }
  6240.   }
  6241.   return FALSE;
  6242. }
  6243.  
  6244.  
  6245. /*
  6246. ** Change all sum_func refs to fields to point at fields in tmp table
  6247. ** Change all funcs to be fields in tmp table
  6248. */
  6249.  
  6250. static bool
  6251. change_refs_to_tmp_fields(THD *thd,List<Item> &items)
  6252. {
  6253.   List_iterator<Item> it(items);
  6254.   Item *item;
  6255.  
  6256.   while ((item= it++))
  6257.   {
  6258.     if (item->type() == Item::SUM_FUNC_ITEM)
  6259.     {
  6260.       if (!item->const_item())
  6261.       {
  6262.     Item_sum *sum_item= (Item_sum*) item;
  6263.     if (sum_item->result_field)        // If not a const sum func
  6264.     {
  6265.       Field *result_field=sum_item->result_field;
  6266.       for (uint i=0 ; i < sum_item->arg_count ; i++)
  6267.       {
  6268.         Item *arg= sum_item->args[i];
  6269.         if (!arg->const_item())
  6270.         {
  6271.           if (arg->type() == Item::FIELD_ITEM)
  6272.         ((Item_field*) arg)->field= result_field++;
  6273.           else
  6274.         sum_item->args[i]= new Item_field(result_field++);
  6275.         }
  6276.       }
  6277.     }
  6278.       }
  6279.     }
  6280.     else if (item->with_sum_func)
  6281.       continue;
  6282.     else if ((item->type() == Item::FUNC_ITEM ||
  6283.           item->type() == Item::COND_ITEM) &&
  6284.          !item->const_item())
  6285.     {                        /* All funcs are stored */
  6286. #ifdef DELETE_ITEMS
  6287.       delete it.replace(new Item_field(((Item_func*) item)->result_field));
  6288. #else
  6289.       (void) it.replace(new Item_field(((Item_func*) item)->result_field));
  6290. #endif
  6291.     }
  6292.     else if (item->type() == Item::FIELD_ITEM)    /* Change refs */
  6293.     {
  6294.       ((Item_field*)item)->field=((Item_field*) item)->result_field;
  6295.     }
  6296.   }
  6297.   return thd->fatal_error;
  6298. }
  6299.  
  6300.  
  6301.  
  6302. /******************************************************************************
  6303. ** code for calculating functions
  6304. ******************************************************************************/
  6305.  
  6306. static void
  6307. init_tmptable_sum_functions(Item_sum **func_ptr)
  6308. {
  6309.   Item_sum *func;
  6310.   while ((func= *(func_ptr++)))
  6311.     func->reset_field();
  6312. }
  6313.  
  6314.  
  6315.     /* Update record 0 in tmp_table from record 1 */
  6316.  
  6317. static void
  6318. update_tmptable_sum_func(Item_sum **func_ptr,
  6319.              TABLE *tmp_table __attribute__((unused)))
  6320. {
  6321.   Item_sum *func;
  6322.   while ((func= *(func_ptr++)))
  6323.     func->update_field(0);
  6324. }
  6325.  
  6326.  
  6327.     /* Copy result of sum functions to record in tmp_table */
  6328.  
  6329. static void
  6330. copy_sum_funcs(Item_sum **func_ptr)
  6331. {
  6332.   Item_sum *func;
  6333.   for (; (func = *func_ptr) ; func_ptr++)
  6334.     (void) func->save_in_field(func->result_field);
  6335.   return;
  6336. }
  6337.  
  6338.  
  6339. static void
  6340. init_sum_functions(Item_sum **func_ptr)
  6341. {
  6342.   Item_sum *func;
  6343.   for (; (func= (Item_sum*) *func_ptr) ; func_ptr++)
  6344.     func->reset();
  6345. }
  6346.  
  6347.  
  6348. static bool
  6349. update_sum_func(Item_sum **func_ptr)
  6350. {
  6351.   Item_sum *func;
  6352.   for (; (func= (Item_sum*) *func_ptr) ; func_ptr++)
  6353.     if (func->add())
  6354.       return 1;
  6355.   return 0;
  6356. }
  6357.  
  6358.     /* Copy result of functions to record in tmp_table */
  6359.  
  6360. void
  6361. copy_funcs(Item_result_field **func_ptr)
  6362. {
  6363.   Item_result_field *func;
  6364.   for (; (func = *func_ptr) ; func_ptr++)
  6365.     (void) func->save_in_field(func->result_field);
  6366.   return;
  6367. }
  6368.  
  6369.  
  6370. /*****************************************************************************
  6371. ** Create a condition for a const reference and add this to the
  6372. ** currenct select for the table
  6373. *****************************************************************************/
  6374.  
  6375. static bool add_ref_to_table_cond(THD *thd, JOIN_TAB *join_tab)
  6376. {
  6377.   DBUG_ENTER("add_ref_to_table_cond");
  6378.   if (!join_tab->ref.key_parts)
  6379.     DBUG_RETURN(FALSE);
  6380.  
  6381.   Item_cond_and *cond=new Item_cond_and();
  6382.   TABLE *table=join_tab->table;
  6383.   int error;
  6384.   if (!cond)
  6385.     DBUG_RETURN(TRUE);
  6386.  
  6387.   for (uint i=0 ; i < join_tab->ref.key_parts ; i++)
  6388.   {
  6389.     Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].fieldnr-1];
  6390.     Item *value=join_tab->ref.items[i];
  6391.     cond->add(new Item_func_equal(new Item_field(field),value));
  6392.   }
  6393.   if (thd->fatal_error)
  6394.     DBUG_RETURN(TRUE);
  6395.  
  6396.   /*
  6397.     Here we pass 0 as the first argument to fix_fields that don't need
  6398.     to do any stack checking (This is already done in the initial fix_fields).
  6399.   */
  6400.   cond->fix_fields((THD *) 0,(TABLE_LIST *) 0);
  6401.   if (join_tab->select)
  6402.   {
  6403.     error=(int) cond->add(join_tab->select->cond);
  6404.     join_tab->select_cond=join_tab->select->cond=cond;
  6405.   }
  6406.   else if ((join_tab->select=make_select(join_tab->table, 0, 0, cond,&error)))
  6407.     join_tab->select_cond=cond;
  6408.  
  6409.   DBUG_RETURN(error ? TRUE : FALSE);
  6410. }
  6411.  
  6412. /****************************************************************************
  6413. ** Send a description about what how the select will be done to stdout
  6414. ****************************************************************************/
  6415.  
  6416. static void select_describe(JOIN *join, bool need_tmp_table, bool need_order,
  6417.                 bool distinct)
  6418. {
  6419.   List<Item> field_list;
  6420.   Item *item;
  6421.   THD *thd=join->thd;
  6422.   DBUG_ENTER("select_describe");
  6423.  
  6424.   field_list.push_back(new Item_empty_string("table",NAME_LEN));
  6425.   field_list.push_back(new Item_empty_string("type",10));
  6426.   field_list.push_back(item=new Item_empty_string("possible_keys",
  6427.                           NAME_LEN*MAX_KEY));
  6428.   item->maybe_null=1;
  6429.   field_list.push_back(item=new Item_empty_string("key",NAME_LEN));
  6430.   item->maybe_null=1;
  6431.   field_list.push_back(item=new Item_int("key_len",0,3));
  6432.   item->maybe_null=1;
  6433.   field_list.push_back(item=new Item_empty_string("ref",
  6434.                           NAME_LEN*MAX_REF_PARTS));
  6435.   item->maybe_null=1;
  6436.   field_list.push_back(new Item_real("rows",0.0,0,10));
  6437.   field_list.push_back(new Item_empty_string("Extra",255));
  6438.   if (send_fields(thd,field_list,1))
  6439.     return; /* purecov: inspected */
  6440.  
  6441.   char buff[512],*buff_ptr;
  6442.   String tmp(buff,sizeof(buff)),*packet= &thd->packet;
  6443.   table_map used_tables=0;
  6444.   for (uint i=0 ; i < join->tables ; i++)
  6445.   {
  6446.     JOIN_TAB *tab=join->join_tab+i;
  6447.     TABLE *table=tab->table;
  6448.  
  6449.     if (tab->type == JT_ALL && tab->select && tab->select->quick)
  6450.       tab->type= JT_RANGE;
  6451.     packet->length(0);
  6452.     net_store_data(packet,table->table_name);
  6453.     net_store_data(packet,join_type_str[tab->type]);
  6454.     tmp.length(0);
  6455.     key_map bits;
  6456.     uint j;
  6457.     for (j=0,bits=tab->keys ; bits ; j++,bits>>=1)
  6458.     {
  6459.       if (bits & 1)
  6460.       {
  6461.     if (tmp.length())
  6462.       tmp.append(',');
  6463.     tmp.append(table->key_info[j].name);
  6464.       }
  6465.     }
  6466.     if (tmp.length())
  6467.       net_store_data(packet,tmp.ptr(),tmp.length());
  6468.     else
  6469.       net_store_null(packet);
  6470.     if (tab->ref.key_parts)
  6471.     {
  6472.       net_store_data(packet,table->key_info[tab->ref.key].name);
  6473.       net_store_data(packet,(uint32) tab->ref.key_length);
  6474.       tmp.length(0);
  6475.       for (store_key **ref=tab->ref.key_copy ; *ref ; ref++)
  6476.       {
  6477.     if (tmp.length())
  6478.       tmp.append(',');
  6479.     tmp.append((*ref)->name());
  6480.       }
  6481.       net_store_data(packet,tmp.ptr(),tmp.length());
  6482.     }
  6483.     else if (tab->type == JT_NEXT)
  6484.     {
  6485.       net_store_data(packet,table->key_info[tab->index].name);
  6486.       net_store_data(packet,(uint32) table->key_info[tab->index].key_length);
  6487.       net_store_null(packet);
  6488.     }
  6489.     else if (tab->select && tab->select->quick)
  6490.     {
  6491.       net_store_data(packet,table->key_info[tab->select->quick->index].name);;
  6492.       net_store_data(packet,(uint32) tab->select->quick->max_used_key_length);
  6493.       net_store_null(packet);
  6494.     }
  6495.     else
  6496.     {
  6497.       net_store_null(packet);
  6498.       net_store_null(packet);
  6499.       net_store_null(packet);
  6500.     }
  6501.     sprintf(buff,"%.0f",join->best_positions[i].records_read);
  6502.     net_store_data(packet,buff);
  6503.     my_bool key_read=table->key_read;
  6504.     if (tab->type == JT_NEXT &&
  6505.     ((table->used_keys & ((key_map) 1 << tab->index))))
  6506.       key_read=1;
  6507.  
  6508.     buff_ptr=buff;
  6509.     if (tab->info)
  6510.       net_store_data(packet,tab->info);
  6511.     else if (tab->select)
  6512.     {
  6513.       if (tab->use_quick == 2)
  6514.       {
  6515.     sprintf(buff_ptr,"range checked for each record (index map: %u)",
  6516.         tab->keys);
  6517.     buff_ptr=strend(buff_ptr);
  6518.       }
  6519.       else
  6520.     buff_ptr=strmov(buff_ptr,"where used");
  6521.     }
  6522.     if (key_read)
  6523.     {
  6524.       if (buff != buff_ptr)
  6525.       {
  6526.     buff_ptr[0]=';' ; buff_ptr[1]=' '; buff_ptr+=2;
  6527.       }
  6528.       buff_ptr=strmov(buff_ptr,"Using index");
  6529.     }
  6530.     if (table->reginfo.not_exists_optimize)
  6531.     {
  6532.       if (buff != buff_ptr)
  6533.       {
  6534.     buff_ptr[0]=';' ; buff_ptr[1]=' '; buff_ptr+=2;
  6535.       }
  6536.       buff_ptr=strmov(buff_ptr,"Not exists");
  6537.     }
  6538.     if (need_tmp_table)
  6539.     {
  6540.       need_tmp_table=0;
  6541.       if (buff != buff_ptr)
  6542.       {
  6543.     buff_ptr[0]=';' ; buff_ptr[1]=' '; buff_ptr+=2;
  6544.       }
  6545.       buff_ptr=strmov(buff_ptr,"Using temporary");
  6546.     }
  6547.     if (need_order)
  6548.     {
  6549.       need_order=0;
  6550.       if (buff != buff_ptr)
  6551.       {
  6552.     buff_ptr[0]=';' ; buff_ptr[1]=' '; buff_ptr+=2;
  6553.       }
  6554.       buff_ptr=strmov(buff_ptr,"Using filesort");
  6555.     }
  6556.     if (distinct & test_all_bits(used_tables,thd->used_tables))
  6557.     {
  6558.       if (buff != buff_ptr)
  6559.       {
  6560.     buff_ptr[0]=';' ; buff_ptr[1]=' '; buff_ptr+=2;
  6561.       }
  6562.       buff_ptr=strmov(buff_ptr,"Distinct");
  6563.     }
  6564.     net_store_data(packet,buff,(uint) (buff_ptr - buff));
  6565.     if (my_net_write(&thd->net,(char*) packet->ptr(),packet->length()))
  6566.       DBUG_VOID_RETURN;                /* purecov: inspected */
  6567.  
  6568.     // For next iteration
  6569.     used_tables|=table->map;
  6570.   }
  6571.   send_eof(&thd->net);
  6572.   DBUG_VOID_RETURN;
  6573. }
  6574.  
  6575.  
  6576. static void describe_info(const char *info)
  6577. {
  6578.   List<Item> field_list;
  6579.   THD *thd=current_thd;
  6580.   String *packet= &thd->packet;
  6581.  
  6582.   field_list.push_back(new Item_empty_string("Comment",80));
  6583.   if (send_fields(thd,field_list,1))
  6584.     return; /* purecov: inspected */
  6585.   packet->length(0);
  6586.   net_store_data(packet,info);
  6587.   if (!my_net_write(&thd->net,(char*) packet->ptr(),packet->length()))
  6588.     send_eof(&thd->net);
  6589. }
  6590.