← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/join.cc

  • Committer: Siddharth Prakash Singh
  • Date: 2010-03-26 17:24:57 UTC
  • mto: This revision was merged to the branch mainline in revision 1425.
  • Revision ID: spsneo@spsneo-laptop-20100326172457-vni09y22ktvvefmn
some more sprintf --> snprintf

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/join.cc
21
21
/**
22
22
 * @file
23
23
 *
24
 
 * Implementation of the Join class
 
24
 * Implementation of the JOIN class
25
25
 * 
26
26
 * @defgroup Query_Optimizer  Query Optimizer
27
27
 * @{
51
51
#include "drizzled/optimizer/range.h"
52
52
#include "drizzled/optimizer/sum.h"
53
53
#include "drizzled/optimizer/explain_plan.h"
54
 
#include "drizzled/optimizer/access_method_factory.h"
55
 
#include "drizzled/optimizer/access_method.h"
56
54
#include "drizzled/records.h"
57
55
#include "drizzled/probes.h"
58
56
#include "drizzled/internal/my_bit.h"
70
68
extern std::bitset<12> test_flags;
71
69
 
72
70
/** Declarations of static functions used in this source file. */
73
 
static bool make_group_fields(Join *main_join, Join *curr_join);
74
 
static void calc_group_buffer(Join *join, Order *group);
75
 
static bool alloc_group_fields(Join *join, Order *group);
76
 
static uint32_t cache_record_length(Join *join, uint32_t index);
77
 
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);
78
 
static bool get_best_combination(Join *join);
79
 
static void set_position(Join *join,
 
71
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
 
72
static void calc_group_buffer(JOIN *join,order_st *group);
 
73
static bool alloc_group_fields(JOIN *join,order_st *group);
 
74
static uint32_t cache_record_length(JOIN *join, uint32_t index);
 
75
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
 
76
static bool get_best_combination(JOIN *join);
 
77
static void set_position(JOIN *join,
80
78
                         uint32_t index,
81
79
                         JoinTable *table,
82
80
                         optimizer::KeyUse *key);
83
 
static bool choose_plan(Join *join,table_map join_tables);
84
 
static void best_access_path(Join *join, JoinTable *s,
 
81
static bool choose_plan(JOIN *join,table_map join_tables);
 
82
static void best_access_path(JOIN *join, JoinTable *s,
85
83
                             Session *session,
86
84
                             table_map remaining_tables,
87
85
                             uint32_t idx,
88
86
                             double record_count,
89
87
                             double read_time);
90
 
static void optimize_straight_join(Join *join, table_map join_tables);
91
 
static bool greedy_search(Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
92
 
static bool best_extension_by_limited_search(Join *join,
 
88
static void optimize_straight_join(JOIN *join, table_map join_tables);
 
89
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
 
90
static bool best_extension_by_limited_search(JOIN *join,
93
91
                                             table_map remaining_tables,
94
92
                                             uint32_t idx,
95
93
                                             double record_count,
96
94
                                             double read_time,
97
95
                                             uint32_t depth,
98
96
                                             uint32_t prune_level);
99
 
static uint32_t determine_search_depth(Join* join);
100
 
static bool make_simple_join(Join *join,Table *tmp_table);
101
 
static void make_outerjoin_info(Join *join);
102
 
static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);
103
 
static bool make_join_readinfo(Join *join);
104
 
static void update_depend_map(Join *join);
105
 
static void update_depend_map(Join *join, Order *order);
106
 
static Order *remove_constants(Join *join,Order *first_order,COND *cond, bool change_list, bool *simple_order);
107
 
static int return_zero_rows(Join *join,
 
97
static uint32_t determine_search_depth(JOIN* join);
 
98
static bool make_simple_join(JOIN *join,Table *tmp_table);
 
99
static void make_outerjoin_info(JOIN *join);
 
100
static bool make_join_select(JOIN *join, optimizer::SqlSelect *select,COND *item);
 
101
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
 
102
static void update_depend_map(JOIN *join);
 
103
static void update_depend_map(JOIN *join, order_st *order);
 
104
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
 
105
static int return_zero_rows(JOIN *join,
108
106
                            select_result *res,
109
107
                            TableList *tables,
110
108
                            List<Item> &fields,
112
110
                            uint64_t select_options,
113
111
                            const char *info,
114
112
                            Item *having);
115
 
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);
116
 
static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);
 
113
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
 
114
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
117
115
static int setup_without_group(Session *session, 
118
116
                               Item **ref_pointer_array,
119
117
                               TableList *tables,
121
119
                               List<Item> &fields,
122
120
                               List<Item> &all_fields,
123
121
                               COND **conds,
124
 
                               Order *order,
125
 
                               Order *group,
 
122
                               order_st *order,
 
123
                               order_st *group,
126
124
                               bool *hidden_group_fields);
127
 
static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
 
125
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
128
126
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
129
 
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables);
 
127
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
130
128
static void reset_nj_counters(List<TableList> *join_list);
131
 
static bool test_if_subpart(Order *a,Order *b);
 
129
static bool test_if_subpart(order_st *a,order_st *b);
132
130
static void restore_prev_nj_state(JoinTable *last);
 
131
static uint32_t make_join_orderinfo(JOIN *join);
133
132
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
134
133
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
135
134
 
145
144
  @retval
146
145
    0   on success
147
146
*/
148
 
int Join::prepare(Item ***rref_pointer_array,
 
147
int JOIN::prepare(Item ***rref_pointer_array,
149
148
                  TableList *tables_init,
150
149
                  uint32_t wild_num,
151
150
                  COND *conds_init,
152
151
                  uint32_t og_num,
153
 
                  Order *order_init,
154
 
                  Order *group_init,
 
152
                  order_st *order_init,
 
153
                  order_st *group_init,
155
154
                  Item *having_init,
156
155
                  Select_Lex *select_lex_arg,
157
156
                  Select_Lex_Unit *unit_arg)
184
183
      setup_tables_and_check_access(session, &select_lex->context, join_list,
185
184
                                    tables_list, &select_lex->leaf_tables,
186
185
                                    false))
187
 
  {
188
186
      return(-1);
189
 
  }
190
187
 
191
188
  TableList *table_ptr;
192
189
  for (table_ptr= select_lex->leaf_tables;
193
190
       table_ptr;
194
191
       table_ptr= table_ptr->next_leaf)
195
 
  {
196
192
    tables++;
197
 
  }
198
 
 
199
193
 
200
194
  if (setup_wild(session, fields_list, &all_fields, wild_num) ||
201
195
      select_lex->setup_ref_array(session, og_num) ||
291
285
 
292
286
  if (order)
293
287
  {
294
 
    Order *ord;
 
288
    order_st *ord;
295
289
    for (ord= order; ord; ord= ord->next)
296
290
    {
297
291
      Item *item= *ord->item;
336
330
  {
337
331
    /* Caclulate the number of groups */
338
332
    send_group_parts= 0;
339
 
    for (Order *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
 
333
    for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
340
334
      send_group_parts++;
341
335
  }
342
336
 
343
337
  if (error)
344
 
    return(-1);
 
338
    goto err;
345
339
 
346
340
  /* 
347
341
   * The below will create the new table for
350
344
   * @see create_table_from_items() in drizzled/sql_insert.cc
351
345
   */
352
346
  if (result && result->prepare(fields_list, unit_arg))
353
 
    return(-1);
 
347
    goto err;
354
348
 
355
349
  /* Init join struct */
356
350
  count_field_types(select_lex, &tmp_table_param, all_fields, 0);
362
356
  if (sum_func_count && !group_list && (func_count || field_count))
363
357
  {
364
358
    my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
365
 
    return(-1);
 
359
    goto err;
366
360
  }
367
361
#endif
368
362
  if (select_lex->olap == ROLLUP_TYPE && rollup_init())
369
 
    return(-1);
370
 
 
 
363
    goto err;
371
364
  if (alloc_func_list())
372
 
    return(-1);
373
 
 
374
 
  return 0; // All OK
 
365
    goto err;
 
366
 
 
367
  return(0); // All OK
 
368
 
 
369
err:
 
370
  return(-1);
375
371
}
376
372
 
377
373
/*
378
374
  Remove the predicates pushed down into the subquery
379
375
 
380
376
  SYNOPSIS
381
 
    Join::remove_subq_pushed_predicates()
 
377
    JOIN::remove_subq_pushed_predicates()
382
378
      where   IN  Must be NULL
383
379
              OUT The remaining WHERE condition, or NULL
384
380
 
403
399
    that is searched in a byte. But this requires homogenization of the return
404
400
    codes of all Field*::store() methods.
405
401
*/
406
 
void Join::remove_subq_pushed_predicates(Item **where)
 
402
void JOIN::remove_subq_pushed_predicates(Item **where)
407
403
{
408
404
  if (conds->type() == Item::FUNC_ITEM &&
409
405
      ((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
428
424
  @retval
429
425
    1   error
430
426
*/
431
 
int Join::optimize()
 
427
int JOIN::optimize()
432
428
{
433
429
  // to prevent double initialization on EXPLAIN
434
430
  if (optimized)
498
494
    {           /* Impossible cond */
499
495
      zero_result_cause=  having_value == Item::COND_FALSE ?
500
496
                           "Impossible HAVING" : "Impossible WHERE";
501
 
      tables = 0;
502
 
      goto setup_subq_exit;
 
497
      error= 0;
 
498
      return(0);
503
499
    }
504
500
  }
505
501
 
518
514
      if (res == HA_ERR_KEY_NOT_FOUND)
519
515
      {
520
516
        zero_result_cause= "No matching min/max row";
521
 
        tables = 0;
522
 
        goto setup_subq_exit;
 
517
        error=0;
 
518
        return(0);
523
519
      }
524
520
      if (res > 1)
525
521
      {
529
525
      if (res < 0)
530
526
      {
531
527
        zero_result_cause= "No matching min/max row";
532
 
        tables = 0;
533
 
        goto setup_subq_exit;
 
528
        error=0;
 
529
        return(0);
534
530
      }
535
531
      zero_result_cause= "Select tables optimized away";
536
532
      tables_list= 0;       // All tables resolved
537
 
      const_tables= tables;
538
533
      /*
539
534
        Extract all table-independent conditions and replace the WHERE
540
535
        clause with them. All other conditions were computed by optimizer::sum_query
550
545
        COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
551
546
        conds= table_independent_conds;
552
547
      }
553
 
      goto setup_subq_exit;
554
548
    }
555
549
  }
556
550
  if (!tables_list)
583
577
       select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
584
578
  {
585
579
    zero_result_cause= "no matching row in const table";
586
 
    goto setup_subq_exit;
 
580
    error= 0;
 
581
    return(0);
587
582
  }
588
583
  if (!(session->options & OPTION_BIG_SELECTS) &&
589
584
      best_read > (double) session->variables.max_join_size &&
594
589
    return 1;
595
590
  }
596
591
  if (const_tables && !(select_options & SELECT_NO_UNLOCK))
597
 
    session->unlockSomeTables(table, const_tables);
 
592
    mysql_unlock_some_tables(session, table, const_tables);
598
593
  if (!conds && outer_join)
599
594
  {
600
595
    /* Handle the case where we have an OUTER JOIN without a WHERE */
649
644
  {
650
645
    zero_result_cause=
651
646
      "Impossible WHERE noticed after reading const tables";
652
 
    goto setup_subq_exit;
 
647
    return(0);        // error == 0
653
648
  }
654
649
 
655
650
  error= -1;          /* if goto err */
656
651
 
657
652
  /* Optimize distinct away if possible */
658
653
  {
659
 
    Order *org_order= order;
 
654
    order_st *org_order= order;
660
655
    order= remove_constants(this, order,conds,1, &simple_order);
661
656
    if (session->is_error())
662
657
    {
790
785
  }
791
786
  simple_group= 0;
792
787
  {
793
 
    Order *old_group_list;
 
788
    order_st *old_group_list;
794
789
    group_list= remove_constants(this, (old_group_list= group_list), conds,
795
790
                                 rollup.state == ROLLUP::STATE_NONE,
796
791
                                 &simple_group);
840
835
        (group_list && order) ||
841
836
        test(select_options & OPTION_BUFFER_RESULT)));
842
837
 
 
838
  uint32_t no_jbuf_after= make_join_orderinfo(this);
 
839
  uint64_t select_opts_for_readinfo=
 
840
    (select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
 
841
 
843
842
  // No cache for MATCH == 'Don't use join buffering when we use MATCH'.
844
 
  if (make_join_readinfo(this))
 
843
  if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
845
844
    return 1;
846
845
 
847
846
  /* Create all structures needed for materialized subquery execution. */
868
867
        save_index_subquery_explain_info(join_tab, where);
869
868
        join_tab[0].type= AM_UNIQUE_SUBQUERY;
870
869
        error= 0;
871
 
        return(unit->item->change_engine(new subselect_uniquesubquery_engine(session, join_tab, unit->item, where)));
 
870
        return(unit->item->
 
871
                    change_engine(new
 
872
                                  subselect_uniquesubquery_engine(session,
 
873
                                                                  join_tab,
 
874
                                                                  unit->item,
 
875
                                                                  where)));
872
876
      }
873
877
      else if (join_tab[0].type == AM_REF &&
874
878
         join_tab[0].ref.items[0]->name == in_left_expr_name)
877
881
        save_index_subquery_explain_info(join_tab, where);
878
882
        join_tab[0].type= AM_INDEX_SUBQUERY;
879
883
        error= 0;
880
 
        return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, where, NULL, 0)));
 
884
        return(unit->item->
 
885
                    change_engine(new
 
886
                                  subselect_indexsubquery_engine(session,
 
887
                                                                 join_tab,
 
888
                                                                 unit->item,
 
889
                                                                 where,
 
890
                                                                 NULL,
 
891
                                                                 0)));
881
892
      }
882
893
    } 
883
894
    else if (join_tab[0].type == AM_REF_OR_NULL &&
888
899
      error= 0;
889
900
      conds= remove_additional_cond(conds);
890
901
      save_index_subquery_explain_info(join_tab, conds);
891
 
      return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, conds, having, 1)));
 
902
      return(unit->item->
 
903
      change_engine(new subselect_indexsubquery_engine(session,
 
904
                   join_tab,
 
905
                   unit->item,
 
906
                   conds,
 
907
                                                                   having,
 
908
                   1)));
892
909
    }
893
910
 
894
911
  }
940
957
        Force using of tmp table if sorting by a SP or UDF function due to
941
958
        their expensive and probably non-deterministic nature.
942
959
      */
943
 
      for (Order *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
 
960
      for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
944
961
      {
945
962
        Item *item= *tmp_order->item;
946
963
        if (item->is_expensive())
984
1001
 
985
1002
    tmp_table_param.hidden_field_count= (all_fields.elements -
986
1003
           fields_list.elements);
987
 
    Order *tmp_group= ((!simple_group &&
 
1004
    order_st *tmp_group= ((!simple_group && 
988
1005
                           ! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
989
 
                                                                     (Order*) 0);
 
1006
                                                                     (order_st*) 0);
990
1007
    /*
991
1008
      Pushing LIMIT to the temporary table creation is not applicable
992
1009
      when there is ORDER BY or GROUP BY or there is no GROUP BY, but
1089
1106
      If this join belongs to an uncacheable subquery save
1090
1107
      the original join
1091
1108
    */
1092
 
    if (select_lex->uncacheable.any() && 
1093
 
        ! is_top_level_join() &&
 
1109
    if (select_lex->uncacheable && !is_top_level_join() &&
1094
1110
        init_save_join_tab())
1095
 
    {
1096
 
      return -1;
1097
 
    }
 
1111
      return(-1);
1098
1112
  }
1099
1113
 
1100
1114
  error= 0;
1101
 
  return 0;
1102
 
 
1103
 
setup_subq_exit:
1104
 
  /* Even with zero matching rows, subqueries in the HAVING clause
1105
 
     may need to be evaluated if there are aggregate functions in the query.
1106
 
  */
1107
 
  if (setup_subquery_materialization())
1108
 
    return 1;
1109
 
  error= 0;
1110
 
  return 0;
 
1115
  return(0);
1111
1116
}
1112
1117
 
1113
1118
/**
1114
1119
  Restore values in temporary join.
1115
1120
*/
1116
 
void Join::restore_tmp()
 
1121
void JOIN::restore_tmp()
1117
1122
{
1118
 
  memcpy(tmp_join, this, (size_t) sizeof(Join));
 
1123
  memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1119
1124
}
1120
1125
 
1121
 
int Join::reinit()
 
1126
int JOIN::reinit()
1122
1127
{
1123
1128
  unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1124
1129
                                    select_lex->offset_limit->val_uint() :
1170
1175
   @retval 0      success.
1171
1176
   @retval 1      error occurred.
1172
1177
*/
1173
 
bool Join::init_save_join_tab()
 
1178
bool JOIN::init_save_join_tab()
1174
1179
{
1175
 
  if (!(tmp_join= (Join*)session->alloc(sizeof(Join))))
 
1180
  if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
1176
1181
    return 1;
1177
 
 
1178
1182
  error= 0;              // Ensure that tmp_join.error= 0
1179
1183
  restore_tmp();
1180
 
 
1181
1184
  return 0;
1182
1185
}
1183
1186
 
1184
 
bool Join::save_join_tab()
 
1187
bool JOIN::save_join_tab()
1185
1188
{
1186
 
  if (! join_tab_save && select_lex->master_unit()->uncacheable.any())
 
1189
  if (!join_tab_save && select_lex->master_unit()->uncacheable)
1187
1190
  {
1188
1191
    if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1189
1192
            sizeof(JoinTable) * tables)))
1203
1206
  @todo
1204
1207
    When can we have here session->net.report_error not zero?
1205
1208
*/
1206
 
void Join::exec()
 
1209
void JOIN::exec()
1207
1210
{
1208
1211
  List<Item> *columns_list= &fields_list;
1209
1212
  int      tmp_error;
1304
1307
    return;
1305
1308
  }
1306
1309
 
1307
 
  Join *curr_join= this;
 
1310
  JOIN *curr_join= this;
1308
1311
  List<Item> *curr_all_fields= &all_fields;
1309
1312
  List<Item> *curr_fields_list= &fields_list;
1310
1313
  Table *curr_tmp_table= 0;
1414
1417
                                                   - curr_join->tmp_fields_list1.elements;
1415
1418
 
1416
1419
      if (exec_tmp_table2)
1417
 
      {
1418
1420
        curr_tmp_table= exec_tmp_table2;
1419
 
      }
1420
1421
      else
1421
1422
      {
1422
1423
        /* group data to new table */
1424
1425
        /*
1425
1426
          If the access method is loose index scan then all MIN/MAX
1426
1427
          functions are precomputed, and should be treated as regular
1427
 
          functions. See extended comment in Join::exec.
 
1428
          functions. See extended comment in JOIN::exec.
1428
1429
        */
1429
1430
        if (curr_join->join_tab->is_using_loose_index_scan())
1430
1431
          curr_join->tmp_table_param.precomputed_group_by= true;
1433
1434
              exec_tmp_table2= create_tmp_table(session,
1434
1435
                                                &curr_join->tmp_table_param,
1435
1436
                                                *curr_all_fields,
1436
 
                                                (Order*) 0,
 
1437
                                                (order_st*) 0,
1437
1438
                                                curr_join->select_distinct &&
1438
1439
                                                !curr_join->group_list,
1439
1440
                                                1, curr_join->select_options,
1440
1441
                                                HA_POS_ERROR,
1441
1442
                                                (char *) "")))
1442
 
        {
1443
1443
          return;
1444
 
        }
1445
 
 
1446
1444
        curr_join->exec_tmp_table2= exec_tmp_table2;
1447
1445
      }
1448
1446
      if (curr_join->group_list)
1490
1488
        error= tmp_error;
1491
1489
        return;
1492
1490
      }
1493
 
      curr_join->join_tab->read_record.end_read_record();
 
1491
      end_read_record(&curr_join->join_tab->read_record);
1494
1492
      curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1495
1493
      curr_join->join_tab[0].table= 0;           // Table is freed
1496
1494
 
1701
1699
  Clean up join.
1702
1700
 
1703
1701
  @return
1704
 
    Return error that hold Join.
 
1702
    Return error that hold JOIN.
1705
1703
*/
1706
 
int Join::destroy()
 
1704
int JOIN::destroy()
1707
1705
{
1708
1706
  select_lex->join= 0;
1709
1707
 
1722
1720
  cond_equal= 0;
1723
1721
 
1724
1722
  cleanup(1);
1725
 
  exec_tmp_table1= NULL;
1726
 
  exec_tmp_table2= NULL;
 
1723
  if (exec_tmp_table1)
 
1724
    exec_tmp_table1->free_tmp_table(session);
 
1725
  if (exec_tmp_table2)
 
1726
    exec_tmp_table2->free_tmp_table(session);
1727
1727
  delete select;
1728
1728
  delete_dynamic(&keyuse);
1729
 
 
1730
1729
  return(error);
1731
1730
}
1732
1731
 
1739
1738
  - try to initialize all data structures needed for the materialized execution
1740
1739
    of the IN predicate,
1741
1740
  - if this fails, then perform the IN=>EXISTS transformation which was
1742
 
    previously blocked during Join::prepare.
 
1741
    previously blocked during JOIN::prepare.
1743
1742
 
1744
1743
  This method is part of the "code generation" query processing phase.
1745
1744
 
1752
1751
  @retval false     success.
1753
1752
  @retval true      error occurred.
1754
1753
*/
1755
 
bool Join::setup_subquery_materialization()
 
1754
bool JOIN::setup_subquery_materialization()
1756
1755
{
1757
1756
  for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1758
1757
       un= un->next_unit())
1774
1773
}
1775
1774
 
1776
1775
/**
1777
 
  Partially cleanup Join after it has executed: close index or rnd read
 
1776
  Partially cleanup JOIN after it has executed: close index or rnd read
1778
1777
  (table cursors), free quick selects.
1779
1778
 
1780
 
    This function is called in the end of execution of a Join, before the used
 
1779
    This function is called in the end of execution of a JOIN, before the used
1781
1780
    tables are unlocked and closed.
1782
1781
 
1783
1782
    For a join that is resolved using a temporary table, the first sweep is
1791
1790
    is called after all rows are sent, but before EOF packet is sent.
1792
1791
 
1793
1792
    For a simple SELECT with no subqueries this function performs a full
1794
 
    cleanup of the Join and calls unlockReadTables to free used base
 
1793
    cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1795
1794
    tables.
1796
1795
 
1797
 
    If a Join is executed for a subquery or if it has a subquery, we can't
 
1796
    If a JOIN is executed for a subquery or if it has a subquery, we can't
1798
1797
    do the full cleanup and need to do a partial cleanup only.
1799
 
    - If a Join is not the top level join, we must not unlock the tables
 
1798
    - If a JOIN is not the top level join, we must not unlock the tables
1800
1799
    because the outer select may not have been evaluated yet, and we
1801
1800
    can't unlock only selected tables of a query.
1802
 
    - Additionally, if this Join corresponds to a correlated subquery, we
 
1801
    - Additionally, if this JOIN corresponds to a correlated subquery, we
1803
1802
    should not free quick selects and join buffers because they will be
1804
1803
    needed for the next execution of the correlated subquery.
1805
 
    - However, if this is a Join for a [sub]select, which is not
 
1804
    - However, if this is a JOIN for a [sub]select, which is not
1806
1805
    a correlated subquery itself, but has subqueries, we can free it
1807
 
    fully and also free Joins of all its subqueries. The exception
 
1806
    fully and also free JOINs of all its subqueries. The exception
1808
1807
    is a subquery in SELECT list, e.g: @n
1809
1808
    SELECT a, (select cmax(b) from t1) group by c @n
1810
1809
    This subquery will not be evaluated at first sweep and its value will
1815
1814
  @todo
1816
1815
    Unlock tables even if the join isn't top level select in the tree
1817
1816
*/
1818
 
void Join::join_free()
 
1817
void JOIN::join_free()
1819
1818
{
1820
1819
  Select_Lex_Unit *tmp_unit;
1821
1820
  Select_Lex *sl;
1822
1821
  /*
1823
 
    Optimization: if not EXPLAIN and we are done with the Join,
 
1822
    Optimization: if not EXPLAIN and we are done with the JOIN,
1824
1823
    free all tables.
1825
1824
  */
1826
 
  bool full= (select_lex->uncacheable.none() && ! session->lex->describe);
 
1825
  bool full= (!select_lex->uncacheable && !session->lex->describe);
1827
1826
  bool can_unlock= full;
1828
1827
 
1829
1828
  cleanup(full);
1845
1844
        but all table cursors must be closed before the unlock.
1846
1845
      */
1847
1846
      sl->cleanup_all_joins(full_local);
1848
 
      /* Can't unlock if at least one Join is still needed */
 
1847
      /* Can't unlock if at least one JOIN is still needed */
1849
1848
      can_unlock= can_unlock && full_local;
1850
1849
    }
1851
1850
 
1863
1862
      TODO: unlock tables even if the join isn't top level select in the
1864
1863
      tree.
1865
1864
    */
1866
 
    session->unlockReadTables(lock);           // Don't free join->lock
 
1865
    mysql_unlock_read_tables(session, lock);           // Don't free join->lock
1867
1866
    lock= 0;
1868
1867
  }
1869
1868
 
1882
1881
    With subquery this function definitely will be called several times,
1883
1882
    but even for simple query it can be called several times.
1884
1883
*/
1885
 
void Join::cleanup(bool full)
 
1884
void JOIN::cleanup(bool full)
1886
1885
{
1887
1886
  if (table)
1888
1887
  {
1927
1926
    */
1928
1927
    tmp_table_param.copy_funcs.empty();
1929
1928
    /*
1930
 
      If we have tmp_join and 'this' Join is not tmp_join and
 
1929
      If we have tmp_join and 'this' JOIN is not tmp_join and
1931
1930
      tmp_table_param.copy_field's  of them are equal then we have to remove
1932
1931
      pointer to  tmp_table_param.copy_field from tmp_join, because it qill
1933
1932
      be removed in tmp_table_param.cleanup().
1946
1945
}
1947
1946
 
1948
1947
/*
1949
 
  used only in Join::clear
 
1948
  used only in JOIN::clear
1950
1949
*/
1951
 
static void clear_tables(Join *join)
 
1950
static void clear_tables(JOIN *join)
1952
1951
{
1953
1952
  /*
1954
1953
    must clear only the non-const tables, as const tables
1967
1966
  @retval
1968
1967
    1 Error
1969
1968
*/
1970
 
bool Join::alloc_func_list()
 
1969
bool JOIN::alloc_func_list()
1971
1970
{
1972
1971
  uint32_t func_count, group_parts;
1973
1972
 
1993
1992
    */
1994
1993
    if (order)
1995
1994
    {
1996
 
      Order *ord;
 
1995
      order_st *ord;
1997
1996
      for (ord= order; ord; ord= ord->next)
1998
1997
        group_parts++;
1999
1998
    }
2019
2018
  @retval
2020
2019
    1  error
2021
2020
*/
2022
 
bool Join::make_sum_func_list(List<Item> &field_list, 
 
2021
bool JOIN::make_sum_func_list(List<Item> &field_list, 
2023
2022
                              List<Item> &send_fields,
2024
2023
                              bool before_group_by, 
2025
2024
                              bool recompute)
2057
2056
}
2058
2057
 
2059
2058
/** Allocate memory needed for other rollup functions. */
2060
 
bool Join::rollup_init()
 
2059
bool JOIN::rollup_init()
2061
2060
{
2062
2061
  uint32_t i,j;
2063
2062
  Item **ref_array;
2103
2102
  Item *item;
2104
2103
  while ((item= it++))
2105
2104
  {
2106
 
    Order *group_tmp;
 
2105
    order_st *group_tmp;
2107
2106
    bool found_in_group= 0;
2108
2107
 
2109
2108
    for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2132
2131
            return 1;
2133
2132
          new_item->fix_fields(session, (Item **) 0);
2134
2133
          session->change_item_tree(it.ref(), new_item);
2135
 
          for (Order *tmp= group_tmp; tmp; tmp= tmp->next)
 
2134
          for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2136
2135
          {
2137
2136
            if (*tmp->item == item)
2138
2137
              session->change_item_tree(tmp->item, new_item);
2172
2171
  @retval
2173
2172
    1    on error
2174
2173
*/
2175
 
bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
 
2174
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2176
2175
{
2177
2176
  List_iterator_fast<Item> it(fields_arg);
2178
2177
  Item *first_field= sel_fields.head();
2207
2206
    Item *item;
2208
2207
    List_iterator<Item> new_it(rollup.fields[pos]);
2209
2208
    Item **ref_array_start= rollup.ref_pointer_arrays[pos];
2210
 
    Order *start_group;
 
2209
    order_st *start_group;
2211
2210
 
2212
2211
    /* Point to first hidden field */
2213
2212
    Item **ref_array= ref_array_start + fields_arg.elements-1;
2249
2248
      else
2250
2249
      {
2251
2250
        /* Check if this is something that is part of this group by */
2252
 
        Order *group_tmp;
 
2251
        order_st *group_tmp;
2253
2252
        for (group_tmp= start_group, i= pos ;
2254
2253
                  group_tmp ; group_tmp= group_tmp->next, i++)
2255
2254
        {
2302
2301
  @retval
2303
2302
    1   If send_data_failed()
2304
2303
*/
2305
 
int Join::rollup_send_data(uint32_t idx)
 
2304
int JOIN::rollup_send_data(uint32_t idx)
2306
2305
{
2307
2306
  uint32_t i;
2308
2307
  for (i= send_group_parts ; i-- > idx ; )
2342
2341
  @retval
2343
2342
    1   if write_data_failed()
2344
2343
*/
2345
 
int Join::rollup_write_data(uint32_t idx, Table *table_arg)
 
2344
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2346
2345
{
2347
2346
  uint32_t i;
2348
2347
  for (i= send_group_parts ; i-- > idx ; )
2349
2348
  {
2350
2349
    /* Get reference pointers to sum functions in place */
2351
2350
    memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
2352
 
           ref_pointer_array_size);
 
2351
     ref_pointer_array_size);
2353
2352
    if ((!having || having->val_int()))
2354
2353
    {
2355
2354
      int write_error;
2361
2360
          item->save_in_result_field(1);
2362
2361
      }
2363
2362
      copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2364
 
      if ((write_error= table_arg->cursor->insertRecord(table_arg->getInsertRecord())))
 
2363
      if ((write_error= table_arg->cursor->ha_write_row(table_arg->record[0])))
2365
2364
      {
2366
 
        my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2367
 
        return 1;
 
2365
  if (create_myisam_from_heap(session, table_arg,
 
2366
                                    tmp_table_param.start_recinfo,
 
2367
                                    &tmp_table_param.recinfo,
 
2368
                                    write_error, 0))
 
2369
    return 1;
2368
2370
      }
2369
2371
    }
2370
2372
  }
2377
2379
  clear results if there are not rows found for group
2378
2380
  (end_send_group/end_write_group)
2379
2381
*/
2380
 
void Join::clear()
 
2382
void JOIN::clear()
2381
2383
{
2382
2384
  clear_tables(this);
2383
2385
  copy_fields(&tmp_table_param);
2391
2393
}
2392
2394
 
2393
2395
/**
2394
 
  change select_result object of Join.
 
2396
  change select_result object of JOIN.
2395
2397
 
2396
2398
  @param res    new select_result object
2397
2399
 
2400
2402
  @retval
2401
2403
    true    error
2402
2404
*/
2403
 
bool Join::change_result(select_result *res)
 
2405
bool JOIN::change_result(select_result *res)
2404
2406
{
2405
2407
  result= res;
2406
2408
  if (result->prepare(fields_list, select_lex->master_unit()))
2414
2416
  Cache constant expressions in WHERE, HAVING, ON conditions.
2415
2417
*/
2416
2418
 
2417
 
void Join::cache_const_exprs()
 
2419
void JOIN::cache_const_exprs()
2418
2420
{
2419
2421
  bool cache_flag= false;
2420
2422
  bool *analyzer_arg= &cache_flag;
2455
2457
  applicable to the partial record on hand and in case of success
2456
2458
  submit this record to the next level of the nested loop.
2457
2459
*/
2458
 
enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)
 
2460
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2459
2461
{
2460
2462
  bool not_used_in_distinct= join_tab->not_used_in_distinct;
2461
2463
  ha_rows found_records= join->found_records;
2465
2467
    return NESTED_LOOP_ERROR;
2466
2468
  if (error < 0)
2467
2469
    return NESTED_LOOP_NO_MORE_ROWS;
2468
 
  if (join->session->getKilled())                       // Aborted by user
 
2470
  if (join->session->killed)                    // Aborted by user
2469
2471
  {
2470
2472
    join->session->send_kill_message();
2471
2473
    return NESTED_LOOP_KILLED;
2579
2581
    level of the nested loop. This function is used in case we have
2580
2582
    an OUTER join and no matching record was found.
2581
2583
*/
2582
 
enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)
 
2584
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2583
2585
{
2584
2586
  /*
2585
2587
    The table join_tab is the first inner table of a outer join operation
2635
2637
  return (*join_tab->next_select)(join, join_tab+1, 0);
2636
2638
}
2637
2639
 
2638
 
enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
 
2640
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2639
2641
{
2640
2642
  enum_nested_loop_state rc= NESTED_LOOP_OK;
2641
2643
  int error;
2642
 
  ReadRecord *info;
 
2644
  READ_RECORD *info;
2643
2645
 
2644
2646
  join_tab->table->null_row= 0;
2645
2647
  if (!join_tab->cache.records)
2646
 
  {
2647
2648
    return NESTED_LOOP_OK;                      /* Nothing to do */
2648
 
  }
2649
 
 
2650
2649
  if (skip_last)
2651
 
  {
2652
 
    (void) join_tab->cache.store_record_in_cache(); // Must save this for later
2653
 
  }
2654
 
 
2655
 
 
 
2650
    (void) store_record_in_cache(&join_tab->cache); // Must save this for later
2656
2651
  if (join_tab->use_quick == 2)
2657
2652
  {
2658
2653
    if (join_tab->select->quick)
2664
2659
  /* read through all records */
2665
2660
  if ((error=join_init_read_record(join_tab)))
2666
2661
  {
2667
 
    join_tab->cache.reset_cache_write();
 
2662
    reset_cache_write(&join_tab->cache);
2668
2663
    return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2669
2664
  }
2670
2665
 
2677
2672
  info= &join_tab->read_record;
2678
2673
  do
2679
2674
  {
2680
 
    if (join->session->getKilled())
 
2675
    if (join->session->killed)
2681
2676
    {
2682
2677
      join->session->send_kill_message();
2683
2678
      return NESTED_LOOP_KILLED;
2687
2682
        (!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2688
2683
    {
2689
2684
      uint32_t i;
2690
 
      join_tab->cache.reset_cache_read();
 
2685
      reset_cache_read(&join_tab->cache);
2691
2686
      for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2692
2687
      {
2693
2688
              join_tab->readCachedRecord();
2698
2693
          rc= (join_tab->next_select)(join,join_tab+1,0);
2699
2694
          if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2700
2695
          {
2701
 
            join_tab->cache.reset_cache_write();
 
2696
            reset_cache_write(&join_tab->cache);
2702
2697
            return rc;
2703
2698
          }
2704
2699
 
2711
2706
 
2712
2707
  if (skip_last)
2713
2708
    join_tab->readCachedRecord();               // Restore current record
2714
 
  join_tab->cache.reset_cache_write();
 
2709
  reset_cache_write(&join_tab->cache);
2715
2710
  if (error > 0)                                // Fatal error
2716
2711
    return NESTED_LOOP_ERROR;
2717
2712
  for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2743
2738
                               operation.
2744
2739
   All return values except NESTED_LOOP_OK abort the nested loop.
2745
2740
*****************************************************************************/
2746
 
enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
 
2741
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2747
2742
{
2748
2743
  if (! end_of_records)
2749
2744
  {
2805
2800
  return NESTED_LOOP_OK;
2806
2801
}
2807
2802
 
2808
 
enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
 
2803
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
2809
2804
{
2810
2805
  Table *table= join->tmp_table;
2811
2806
 
2812
 
  if (join->session->getKilled())                       // Aborted by user
 
2807
  if (join->session->killed)                    // Aborted by user
2813
2808
  {
2814
2809
    join->session->send_kill_message();
2815
2810
    return NESTED_LOOP_KILLED;
2817
2812
  if (!end_of_records)
2818
2813
  {
2819
2814
    copy_fields(&join->tmp_table_param);
2820
 
    if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2821
 
      return NESTED_LOOP_ERROR;
 
2815
    copy_funcs(join->tmp_table_param.items_to_copy);
2822
2816
    if (!join->having || join->having->val_int())
2823
2817
    {
2824
2818
      int error;
2825
2819
      join->found_records++;
2826
 
      if ((error=table->cursor->insertRecord(table->getInsertRecord())))
 
2820
      if ((error=table->cursor->ha_write_row(table->record[0])))
2827
2821
      {
2828
2822
        if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
2829
 
        {
2830
 
          return NESTED_LOOP_OK;
2831
 
        }
2832
 
 
2833
 
        my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2834
 
        return NESTED_LOOP_ERROR;        // Table is_full error
 
2823
          goto end;
 
2824
        if (create_myisam_from_heap(join->session, table,
 
2825
                                          join->tmp_table_param.start_recinfo,
 
2826
                                          &join->tmp_table_param.recinfo,
 
2827
                  error, 1))
 
2828
          return NESTED_LOOP_ERROR;        // Not a table_is_full error
 
2829
        table->s->uniques= 0;                   // To ensure rows are the same
2835
2830
      }
2836
2831
      if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
2837
2832
      {
2843
2838
      }
2844
2839
    }
2845
2840
  }
2846
 
 
 
2841
end:
2847
2842
  return NESTED_LOOP_OK;
2848
2843
}
2849
2844
 
2850
2845
/** Group by searching after group record and updating it if possible. */
2851
 
enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
 
2846
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
2852
2847
{
2853
2848
  Table *table= join->tmp_table;
2854
 
  Order *group;
 
2849
  order_st *group;
2855
2850
  int   error;
2856
2851
 
2857
2852
  if (end_of_records)
2858
2853
    return NESTED_LOOP_OK;
2859
 
  if (join->session->getKilled())                       // Aborted by user
 
2854
  if (join->session->killed)                    // Aborted by user
2860
2855
  {
2861
2856
    join->session->send_kill_message();
2862
2857
    return NESTED_LOOP_KILLED;
2873
2868
    if (item->maybe_null)
2874
2869
      group->buff[-1]= (char) group->field->is_null();
2875
2870
  }
2876
 
  if (!table->cursor->index_read_map(table->getUpdateRecord(),
 
2871
  if (!table->cursor->index_read_map(table->record[1],
2877
2872
                                   join->tmp_table_param.group_buff,
2878
2873
                                   HA_WHOLE_KEY,
2879
2874
                                   HA_READ_KEY_EXACT))
2880
2875
  {                                             /* Update old record */
2881
2876
    table->restoreRecord();
2882
2877
    update_tmptable_sum_func(join->sum_funcs,table);
2883
 
    if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
2884
 
                                          table->getInsertRecord())))
 
2878
    if ((error= table->cursor->ha_update_row(table->record[1],
 
2879
                                          table->record[0])))
2885
2880
    {
2886
2881
      table->print_error(error,MYF(0));
2887
2882
      return NESTED_LOOP_ERROR;
2894
2889
    We can't copy all data as the key may have different format
2895
2890
    as the row data (for example as with VARCHAR keys)
2896
2891
  */
2897
 
  KeyPartInfo *key_part;
 
2892
  KEY_PART_INFO *key_part;
2898
2893
  for (group=table->group,key_part=table->key_info[0].key_part;
2899
2894
       group ;
2900
2895
       group=group->next,key_part++)
2901
2896
  {
2902
2897
    if (key_part->null_bit)
2903
 
      memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
 
2898
      memcpy(table->record[0]+key_part->offset, group->buff, 1);
2904
2899
  }
2905
2900
  init_tmptable_sum_functions(join->sum_funcs);
2906
 
  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2907
 
    return NESTED_LOOP_ERROR;
2908
 
  if ((error=table->cursor->insertRecord(table->getInsertRecord())))
 
2901
  copy_funcs(join->tmp_table_param.items_to_copy);
 
2902
  if ((error=table->cursor->ha_write_row(table->record[0])))
2909
2903
  {
2910
 
    my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2911
 
    return NESTED_LOOP_ERROR;        // Table is_full error
 
2904
    if (create_myisam_from_heap(join->session, table,
 
2905
                                join->tmp_table_param.start_recinfo,
 
2906
                                &join->tmp_table_param.recinfo,
 
2907
                                error, 0))
 
2908
      return NESTED_LOOP_ERROR;            // Not a table_is_full error
 
2909
    /* Change method to update rows */
 
2910
    table->cursor->ha_index_init(0, 0);
 
2911
    join->join_tab[join->tables-1].next_select= end_unique_update;
2912
2912
  }
2913
2913
  join->send_records++;
2914
2914
  return NESTED_LOOP_OK;
2915
2915
}
2916
2916
 
2917
2917
/** Like end_update, but this is done with unique constraints instead of keys.  */
2918
 
enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)
 
2918
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
2919
2919
{
2920
2920
  Table *table= join->tmp_table;
2921
2921
  int   error;
2922
2922
 
2923
2923
  if (end_of_records)
2924
2924
    return NESTED_LOOP_OK;
2925
 
  if (join->session->getKilled())                       // Aborted by user
 
2925
  if (join->session->killed)                    // Aborted by user
2926
2926
  {
2927
2927
    join->session->send_kill_message();
2928
2928
    return NESTED_LOOP_KILLED;
2930
2930
 
2931
2931
  init_tmptable_sum_functions(join->sum_funcs);
2932
2932
  copy_fields(&join->tmp_table_param);          // Groups are copied twice.
2933
 
  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
2934
 
    return NESTED_LOOP_ERROR;
 
2933
  copy_funcs(join->tmp_table_param.items_to_copy);
2935
2934
 
2936
 
  if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
 
2935
  if (!(error= table->cursor->ha_write_row(table->record[0])))
2937
2936
    join->send_records++;                       // New group
2938
2937
  else
2939
2938
  {
2942
2941
      table->print_error(error,MYF(0));
2943
2942
      return NESTED_LOOP_ERROR;
2944
2943
    }
2945
 
    if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
 
2944
    if (table->cursor->rnd_pos(table->record[1],table->cursor->dup_ref))
2946
2945
    {
2947
2946
      table->print_error(error,MYF(0));
2948
2947
      return NESTED_LOOP_ERROR;
2949
2948
    }
2950
2949
    table->restoreRecord();
2951
2950
    update_tmptable_sum_func(join->sum_funcs,table);
2952
 
    if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
2953
 
                                          table->getInsertRecord())))
 
2951
    if ((error= table->cursor->ha_update_row(table->record[1],
 
2952
                                          table->record[0])))
2954
2953
    {
2955
2954
      table->print_error(error,MYF(0));
2956
2955
      return NESTED_LOOP_ERROR;
2971
2970
  @retval
2972
2971
    1   failed
2973
2972
*/
2974
 
static bool make_group_fields(Join *main_join, Join *curr_join)
 
2973
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
2975
2974
{
2976
2975
  if (main_join->group_fields_cache.elements)
2977
2976
  {
2990
2989
/**
2991
2990
  calc how big buffer we need for comparing group entries.
2992
2991
*/
2993
 
static void calc_group_buffer(Join *join, Order *group)
 
2992
static void calc_group_buffer(JOIN *join,order_st *group)
2994
2993
{
2995
2994
  uint32_t key_length=0, parts=0, null_parts=0;
2996
2995
 
3016
3015
      case REAL_RESULT:
3017
3016
        key_length+= sizeof(double);
3018
3017
        break;
3019
 
 
3020
3018
      case INT_RESULT:
3021
3019
        key_length+= sizeof(int64_t);
3022
3020
        break;
3023
 
 
3024
3021
      case DECIMAL_RESULT:
3025
3022
        key_length+= my_decimal_get_binary_size(group_item->max_length -
3026
3023
                                                (group_item->decimals ? 1 : 0),
3027
3024
                                                group_item->decimals);
3028
3025
        break;
3029
 
 
3030
3026
      case STRING_RESULT:
3031
 
        {
3032
 
          enum enum_field_types type= group_item->field_type();
 
3027
      {
 
3028
        enum enum_field_types type= group_item->field_type();
 
3029
        /*
 
3030
          As items represented as DATE/TIME fields in the group buffer
 
3031
          have STRING_RESULT result type, we increase the length
 
3032
          by 8 as maximum pack length of such fields.
 
3033
        */
 
3034
        if (type == DRIZZLE_TYPE_DATE ||
 
3035
            type == DRIZZLE_TYPE_DATETIME ||
 
3036
            type == DRIZZLE_TYPE_TIMESTAMP)
 
3037
        {
 
3038
          key_length+= 8;
 
3039
        }
 
3040
        else
 
3041
        {
3033
3042
          /*
3034
 
            As items represented as DATE/TIME fields in the group buffer
3035
 
            have STRING_RESULT result type, we increase the length
3036
 
            by 8 as maximum pack length of such fields.
 
3043
            Group strings are taken as varstrings and require an length field.
 
3044
            A field is not yet created by create_tmp_field()
 
3045
            and the sizes should match up.
3037
3046
          */
3038
 
          if (type == DRIZZLE_TYPE_DATE ||
3039
 
              type == DRIZZLE_TYPE_DATETIME ||
3040
 
              type == DRIZZLE_TYPE_TIMESTAMP)
3041
 
          {
3042
 
            key_length+= 8;
3043
 
          }
3044
 
          else
3045
 
          {
3046
 
            /*
3047
 
              Group strings are taken as varstrings and require an length field.
3048
 
              A field is not yet created by create_tmp_field()
3049
 
              and the sizes should match up.
3050
 
            */
3051
 
            key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3052
 
          }
3053
 
          break;
 
3047
          key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3054
3048
        }
3055
 
 
3056
 
      case ROW_RESULT:
 
3049
        break;
 
3050
      }
 
3051
      default:
3057
3052
        /* This case should never be choosen */
3058
3053
        assert(0);
3059
3054
        my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3060
3055
      }
3061
3056
    }
3062
 
 
3063
3057
    parts++;
3064
 
 
3065
3058
    if (group_item->maybe_null)
3066
3059
      null_parts++;
3067
3060
  }
3068
 
 
3069
3061
  join->tmp_table_param.group_length=key_length+null_parts;
3070
3062
  join->tmp_table_param.group_parts=parts;
3071
3063
  join->tmp_table_param.group_null_parts=null_parts;
3076
3068
 
3077
3069
  Groups are saved in reverse order for easyer check loop.
3078
3070
*/
3079
 
static bool alloc_group_fields(Join *join, Order *group)
 
3071
static bool alloc_group_fields(JOIN *join,order_st *group)
3080
3072
{
3081
3073
  if (group)
3082
3074
  {
3091
3083
  return false;
3092
3084
}
3093
3085
 
3094
 
static uint32_t cache_record_length(Join *join,uint32_t idx)
 
3086
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3095
3087
{
3096
3088
  uint32_t length=0;
3097
3089
  JoinTable **pos,**end;
3159
3151
  RETURN
3160
3152
    Expected number of row combinations
3161
3153
*/
3162
 
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)
 
3154
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3163
3155
{
3164
3156
  double found=1.0;
3165
3157
  optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3171
3163
    {
3172
3164
      found_ref|= pos->getRefDependMap();
3173
3165
      /*
3174
 
        For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table
 
3166
        For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3175
3167
        with no matching row we will get position[t2].records_read==0.
3176
3168
        Actually the size of output is one null-complemented row, therefore
3177
3169
        we will use value of 1 whenever we get records_read==0.
3196
3188
/**
3197
3189
  Set up join struct according to best position.
3198
3190
*/
3199
 
static bool get_best_combination(Join *join)
 
3191
static bool get_best_combination(JOIN *join)
3200
3192
{
3201
3193
  uint32_t i,tablenr;
3202
3194
  table_map used_tables;
3223
3215
    used_tables|= form->map;
3224
3216
    form->reginfo.join_tab=j;
3225
3217
    if (!*j->on_expr_ref)
3226
 
      form->reginfo.not_exists_optimize=0;  // Only with LEFT Join
 
3218
      form->reginfo.not_exists_optimize=0;  // Only with LEFT JOIN
3227
3219
    if (j->type == AM_CONST)
3228
3220
      continue;         // Handled in make_join_stat..
3229
3221
 
3249
3241
}
3250
3242
 
3251
3243
/** Save const tables first as used tables. */
3252
 
static void set_position(Join *join,
 
3244
static void set_position(JOIN *join,
3253
3245
                         uint32_t idx,
3254
3246
                         JoinTable *table,
3255
3247
                         optimizer::KeyUse *key)
3291
3283
  @retval
3292
3284
    true        Fatal error
3293
3285
*/
3294
 
static bool choose_plan(Join *join, table_map join_tables)
 
3286
static bool choose_plan(JOIN *join, table_map join_tables)
3295
3287
{
3296
3288
  uint32_t search_depth= join->session->variables.optimizer_search_depth;
3297
3289
  uint32_t prune_level=  join->session->variables.optimizer_prune_level;
3358
3350
  @return
3359
3351
    None
3360
3352
*/
3361
 
static void best_access_path(Join *join,
 
3353
static void best_access_path(JOIN *join,
3362
3354
                             JoinTable *s,
3363
3355
                             Session *session,
3364
3356
                             table_map remaining_tables,
3391
3383
      key_part_map found_part= 0;
3392
3384
      table_map found_ref= 0;
3393
3385
      uint32_t key= keyuse->getKey();
3394
 
      KeyInfo *keyinfo= table->key_info + key;
 
3386
      KEY *keyinfo= table->key_info + key;
3395
3387
      /* Bitmap of keyparts where the ref access is over 'keypart=const': */
3396
3388
      key_part_map const_part= 0;
3397
3389
      /* The or-null keypart in ref-or-null access: */
3504
3496
                records=
3505
3497
                  ((double) s->records / (double) rec *
3506
3498
                   (1.0 +
3507
 
                    ((double) (table->getShare()->max_key_length-keyinfo->key_length) /
3508
 
                     (double) table->getShare()->max_key_length)));
 
3499
                    ((double) (table->s->max_key_length-keyinfo->key_length) /
 
3500
                     (double) table->s->max_key_length)));
3509
3501
                if (records < 2.0)
3510
3502
                  records=2.0;               /* Can't be as good as a unique */
3511
3503
              }
3888
3880
    Thus 'optimize_straight_join' can be used at any stage of the query
3889
3881
    optimization process to finalize a QEP as it is.
3890
3882
*/
3891
 
static void optimize_straight_join(Join *join, table_map join_tables)
 
3883
static void optimize_straight_join(JOIN *join, table_map join_tables)
3892
3884
{
3893
3885
  JoinTable *s;
3894
3886
  optimizer::Position partial_pos;
3998
3990
  @retval
3999
3991
    true        Fatal error
4000
3992
*/
4001
 
static bool greedy_search(Join      *join,
 
3993
static bool greedy_search(JOIN      *join,
4002
3994
              table_map remaining_tables,
4003
3995
              uint32_t      search_depth,
4004
3996
              uint32_t      prune_level)
4040
4032
    */
4041
4033
    join->setPosInPartialPlan(idx, best_pos);
4042
4034
 
4043
 
    /*
4044
 
      We need to make best_extension_by_limited_search aware of the fact
4045
 
      that it's not starting from top level, but from a rather specific
4046
 
      position in the list of nested joins.
4047
 
    */
4048
 
    check_interleaving_with_nj (best_table);
4049
 
    
4050
 
      
4051
 
 
4052
4035
    /* find the position of 'best_table' in 'join->best_ref' */
4053
4036
    best_idx= idx;
4054
4037
    JoinTable *pos= join->best_ref[best_idx];
4186
4169
  @retval
4187
4170
    true        Fatal error
4188
4171
*/
4189
 
static bool best_extension_by_limited_search(Join *join,
 
4172
static bool best_extension_by_limited_search(JOIN *join,
4190
4173
                                             table_map remaining_tables,
4191
4174
                                             uint32_t idx,
4192
4175
                                             double record_count,
4195
4178
                                             uint32_t prune_level)
4196
4179
{
4197
4180
  Session *session= join->session;
4198
 
  if (session->getKilled())  // Abort
 
4181
  if (session->killed)  // Abort
4199
4182
    return(true);
4200
4183
 
4201
4184
  /*
4210
4193
  for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4211
4194
  {
4212
4195
    table_map real_table_bit= s->table->map;
 
4196
    if (idx)
 
4197
    {
 
4198
      partial_pos= join->getPosFromPartialPlan(idx - 1);
 
4199
    }
4213
4200
    if ((remaining_tables & real_table_bit) &&
4214
4201
        ! (remaining_tables & s->dependent) &&
4215
 
        (! idx || ! check_interleaving_with_nj(s)))
 
4202
        (! idx || ! check_interleaving_with_nj(partial_pos.getJoinTable(), s)))
4216
4203
    {
4217
4204
      double current_record_count, current_read_time;
4218
4205
 
4333
4320
    exhaustiveness) of the depth-first search algorithm used by
4334
4321
    'greedy_search'.
4335
4322
*/
4336
 
static uint32_t determine_search_depth(Join *join)
 
4323
static uint32_t determine_search_depth(JOIN *join)
4337
4324
{
4338
4325
  uint32_t table_count=  join->tables - join->const_tables;
4339
4326
  uint32_t search_depth;
4352
4339
  return search_depth;
4353
4340
}
4354
4341
 
4355
 
static bool make_simple_join(Join *join,Table *tmp_table)
 
4342
static bool make_simple_join(JOIN *join,Table *tmp_table)
4356
4343
{
4357
4344
  Table **tableptr;
4358
4345
  JoinTable *join_tab;
4359
4346
 
4360
4347
  /*
4361
4348
    Reuse Table * and JoinTable if already allocated by a previous call
4362
 
    to this function through Join::exec (may happen for sub-queries).
 
4349
    to this function through JOIN::exec (may happen for sub-queries).
4363
4350
  */
4364
4351
  if (!join->table_reexec)
4365
4352
  {
4409
4396
  join_tab->read_first_record= join_init_read_record;
4410
4397
  join_tab->join=join;
4411
4398
  join_tab->ref.key_parts= 0;
4412
 
  join_tab->read_record.init();
 
4399
  memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4413
4400
  tmp_table->status=0;
4414
4401
  tmp_table->null_row=0;
4415
 
 
4416
 
  return false;
 
4402
  return(false);
4417
4403
}
4418
4404
 
4419
4405
/**
4457
4443
    This function can be called only after the execution plan
4458
4444
    has been chosen.
4459
4445
*/
4460
 
static void make_outerjoin_info(Join *join)
 
4446
static void make_outerjoin_info(JOIN *join)
4461
4447
{
4462
4448
  for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4463
4449
  {
4464
4450
    JoinTable *tab=join->join_tab+i;
4465
4451
    Table *table=tab->table;
4466
4452
    TableList *tbl= table->pos_in_table_list;
4467
 
    TableList *embedding= tbl->getEmbedding();
 
4453
    TableList *embedding= tbl->embedding;
4468
4454
 
4469
4455
    if (tbl->outer_join)
4470
4456
    {
4477
4463
      tab->on_expr_ref= &tbl->on_expr;
4478
4464
      tab->cond_equal= tbl->cond_equal;
4479
4465
      if (embedding)
4480
 
        tab->first_upper= embedding->getNestedJoin()->first_nested;
 
4466
        tab->first_upper= embedding->nested_join->first_nested;
4481
4467
    }
4482
 
    for ( ; embedding ; embedding= embedding->getEmbedding())
 
4468
    for ( ; embedding ; embedding= embedding->embedding)
4483
4469
    {
4484
4470
      /* Ignore sj-nests: */
4485
4471
      if (!embedding->on_expr)
4486
4472
        continue;
4487
 
      nested_join_st *nested_join= embedding->getNestedJoin();
 
4473
      nested_join_st *nested_join= embedding->nested_join;
4488
4474
      if (!nested_join->counter_)
4489
4475
      {
4490
4476
        /*
4494
4480
        nested_join->first_nested= tab;
4495
4481
        tab->on_expr_ref= &embedding->on_expr;
4496
4482
        tab->cond_equal= tbl->cond_equal;
4497
 
        if (embedding->getEmbedding())
4498
 
          tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;
 
4483
        if (embedding->embedding)
 
4484
          tab->first_upper= embedding->embedding->nested_join->first_nested;
4499
4485
      }
4500
4486
      if (!tab->first_inner)
4501
4487
        tab->first_inner= nested_join->first_nested;
4508
4494
  return;
4509
4495
}
4510
4496
 
4511
 
static bool make_join_select(Join *join,
 
4497
static bool make_join_select(JOIN *join,
4512
4498
                             optimizer::SqlSelect *select,
4513
4499
                             COND *cond)
4514
4500
{
4886
4872
    false - OK
4887
4873
    true  - Out of memory
4888
4874
*/
4889
 
static bool make_join_readinfo(Join *join)
 
4875
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
4890
4876
{
4891
 
  bool sorted= true;
 
4877
  uint32_t i;
 
4878
  bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
 
4879
  bool sorted= 1;
4892
4880
 
4893
 
  for (uint32_t i= join->const_tables ; i < join->tables ; i++)
 
4881
  for (i=join->const_tables ; i < join->tables ; i++)
4894
4882
  {
4895
4883
    JoinTable *tab=join->join_tab+i;
4896
4884
    Table *table=tab->table;
 
4885
    bool using_join_cache;
4897
4886
    tab->read_record.table= table;
4898
4887
    tab->read_record.cursor= table->cursor;
4899
4888
    tab->next_select=sub_select;                /* normal select */
4902
4891
      produce sorted output.
4903
4892
    */
4904
4893
    tab->sorted= sorted;
4905
 
    sorted= false; // only first must be sorted
4906
 
 
 
4894
    sorted= 0;                                  // only first must be sorted
4907
4895
    if (tab->insideout_match_tab)
4908
4896
    {
4909
 
      if (! (tab->insideout_buf= (unsigned char*) join->session->alloc(tab->table->key_info
4910
 
                                                                       [tab->index].
4911
 
                                                                       key_length)))
 
4897
      if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
 
4898
                                                         [tab->index].
 
4899
                                                         key_length)))
4912
4900
        return true;
4913
4901
    }
4914
 
 
4915
 
    optimizer::AccessMethodFactory &factory= optimizer::AccessMethodFactory::singleton();
4916
 
    boost::shared_ptr<optimizer::AccessMethod> access_method(factory.createAccessMethod(tab->type));
4917
 
 
4918
 
    if (! access_method)
4919
 
    {
4920
 
      /**
4921
 
       * @todo
4922
 
       * Is abort() the correct thing to call here? I call this here because it was what was called in
4923
 
       * the default case for the switch statement that used to be here.
4924
 
       */
 
4902
    switch (tab->type) {
 
4903
    case AM_SYSTEM:                             // Only happens with left join
 
4904
      table->status=STATUS_NO_RECORD;
 
4905
      tab->read_first_record= join_read_system;
 
4906
      tab->read_record.read_record= join_no_more_records;
 
4907
      break;
 
4908
    case AM_CONST:                              // Only happens with left join
 
4909
      table->status=STATUS_NO_RECORD;
 
4910
      tab->read_first_record= join_read_const;
 
4911
      tab->read_record.read_record= join_no_more_records;
 
4912
      if (table->covering_keys.test(tab->ref.key) &&
 
4913
          !table->no_keyread)
 
4914
      {
 
4915
        table->key_read=1;
 
4916
        table->cursor->extra(HA_EXTRA_KEYREAD);
 
4917
      }
 
4918
      break;
 
4919
    case AM_EQ_REF:
 
4920
      table->status=STATUS_NO_RECORD;
 
4921
      if (tab->select)
 
4922
      {
 
4923
        delete tab->select->quick;
 
4924
        tab->select->quick=0;
 
4925
      }
 
4926
      delete tab->quick;
 
4927
      tab->quick=0;
 
4928
      tab->read_first_record= join_read_key;
 
4929
      tab->read_record.read_record= join_no_more_records;
 
4930
      if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
 
4931
      {
 
4932
        table->key_read=1;
 
4933
        table->cursor->extra(HA_EXTRA_KEYREAD);
 
4934
      }
 
4935
      break;
 
4936
    case AM_REF_OR_NULL:
 
4937
    case AM_REF:
 
4938
      table->status=STATUS_NO_RECORD;
 
4939
      if (tab->select)
 
4940
      {
 
4941
        delete tab->select->quick;
 
4942
        tab->select->quick=0;
 
4943
      }
 
4944
      delete tab->quick;
 
4945
      tab->quick=0;
 
4946
      if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
 
4947
      {
 
4948
        table->key_read=1;
 
4949
        table->cursor->extra(HA_EXTRA_KEYREAD);
 
4950
      }
 
4951
      if (tab->type == AM_REF)
 
4952
      {
 
4953
        tab->read_first_record= join_read_always_key;
 
4954
        tab->read_record.read_record= tab->insideout_match_tab?
 
4955
           join_read_next_same_diff : join_read_next_same;
 
4956
      }
 
4957
      else
 
4958
      {
 
4959
        tab->read_first_record= join_read_always_key_or_null;
 
4960
        tab->read_record.read_record= join_read_next_same_or_null;
 
4961
      }
 
4962
      break;
 
4963
    case AM_ALL:
 
4964
      /*
 
4965
        If previous table use cache
 
4966
        If the incoming data set is already sorted don't use cache.
 
4967
      */
 
4968
      table->status=STATUS_NO_RECORD;
 
4969
      using_join_cache= false;
 
4970
      if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
 
4971
          tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
 
4972
          !tab->insideout_match_tab)
 
4973
      {
 
4974
        if ((options & SELECT_DESCRIBE) ||
 
4975
            !join_init_cache(join->session,join->join_tab+join->const_tables,
 
4976
                i-join->const_tables))
 
4977
        {
 
4978
                using_join_cache= true;
 
4979
          tab[-1].next_select=sub_select_cache; /* Patch previous */
 
4980
        }
 
4981
      }
 
4982
      /* These init changes read_record */
 
4983
      if (tab->use_quick == 2)
 
4984
      {
 
4985
        join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
 
4986
        tab->read_first_record= join_init_quick_read_record;
 
4987
        if (statistics)
 
4988
          status_var_increment(join->session->status_var.select_range_check_count);
 
4989
      }
 
4990
      else
 
4991
      {
 
4992
        tab->read_first_record= join_init_read_record;
 
4993
        if (i == join->const_tables)
 
4994
        {
 
4995
          if (tab->select && tab->select->quick)
 
4996
          {
 
4997
            if (statistics)
 
4998
              status_var_increment(join->session->status_var.select_range_count);
 
4999
          }
 
5000
          else
 
5001
          {
 
5002
            join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
 
5003
            if (statistics)
 
5004
              status_var_increment(join->session->status_var.select_scan_count);
 
5005
          }
 
5006
        }
 
5007
        else
 
5008
        {
 
5009
          if (tab->select && tab->select->quick)
 
5010
          {
 
5011
            if (statistics)
 
5012
              status_var_increment(join->session->status_var.select_full_range_join_count);
 
5013
          }
 
5014
          else
 
5015
          {
 
5016
            join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
 
5017
            if (statistics)
 
5018
              status_var_increment(join->session->status_var.select_full_join_count);
 
5019
          }
 
5020
        }
 
5021
        if (!table->no_keyread)
 
5022
        {
 
5023
          if (tab->select && tab->select->quick &&
 
5024
                    tab->select->quick->index != MAX_KEY && //not index_merge
 
5025
              table->covering_keys.test(tab->select->quick->index))
 
5026
          {
 
5027
            table->key_read=1;
 
5028
            table->cursor->extra(HA_EXTRA_KEYREAD);
 
5029
          }
 
5030
          else if (!table->covering_keys.none() &&
 
5031
            !(tab->select && tab->select->quick))
 
5032
          {                                     // Only read index tree
 
5033
                  if (!tab->insideout_match_tab)
 
5034
                  {
 
5035
                    /*
 
5036
                      See bug #26447: "Using the clustered index for a table scan
 
5037
                      is always faster than using a secondary index".
 
5038
                    */
 
5039
                    if (table->s->primary_key != MAX_KEY &&
 
5040
                        table->cursor->primary_key_is_clustered())
 
5041
                      tab->index= table->s->primary_key;
 
5042
                    else
 
5043
                      tab->index= table->find_shortest_key(&table->covering_keys);
 
5044
                  }
 
5045
            tab->read_first_record= join_read_first;
 
5046
            tab->type= AM_NEXT;         // Read with index_first / index_next
 
5047
          }
 
5048
        }
 
5049
      }
 
5050
      break;
 
5051
    default:
 
5052
      break;
 
5053
    case AM_UNKNOWN:
 
5054
    case AM_MAYBE_REF:
4925
5055
      abort();
4926
5056
    }
4927
 
 
4928
 
    access_method->getStats(table, tab);
4929
5057
  }
4930
 
 
4931
 
  join->join_tab[join->tables-1].next_select= NULL; /* Set by do_select */
4932
 
 
4933
 
  return false;
 
5058
  join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
 
5059
  return(false);
4934
5060
}
4935
5061
 
4936
5062
/** Update the dependency map for the tables. */
4937
 
static void update_depend_map(Join *join)
 
5063
static void update_depend_map(JOIN *join)
4938
5064
{
4939
5065
  JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
4940
5066
 
4957
5083
}
4958
5084
 
4959
5085
/** Update the dependency map for the sort order. */
4960
 
static void update_depend_map(Join *join, Order *order)
 
5086
static void update_depend_map(JOIN *join, order_st *order)
4961
5087
{
4962
5088
  for (; order ; order=order->next)
4963
5089
  {
4995
5121
  @return
4996
5122
    Returns new sort order
4997
5123
*/
4998
 
static Order *remove_constants(Join *join,Order *first_order, COND *cond, bool change_list, bool *simple_order)
 
5124
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
4999
5125
{
5000
5126
  if (join->tables == join->const_tables)
5001
5127
    return change_list ? 0 : first_order;               // No need to sort
5002
5128
 
5003
 
  Order *order,**prev_ptr;
 
5129
  order_st *order,**prev_ptr;
5004
5130
  table_map first_table= join->join_tab[join->const_tables].table->map;
5005
5131
  table_map not_const_tables= ~join->const_table_map;
5006
5132
  table_map ref;
5055
5181
  return(first_order);
5056
5182
}
5057
5183
 
5058
 
static int return_zero_rows(Join *join,
 
5184
static int return_zero_rows(JOIN *join,
5059
5185
                            select_result *result,
5060
5186
                            TableList *tables,
5061
5187
                                        List<Item> &fields,
5221
5347
    - The new condition, if success
5222
5348
    - 0, otherwise
5223
5349
*/
5224
 
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)
 
5350
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5225
5351
{
5226
5352
  TableList *table;
5227
5353
  nested_join_st *nested_join;
5237
5363
    table_map used_tables;
5238
5364
    table_map not_null_tables= (table_map) 0;
5239
5365
 
5240
 
    if ((nested_join= table->getNestedJoin()))
 
5366
    if ((nested_join= table->nested_join))
5241
5367
    {
5242
5368
      /*
5243
5369
         If the element of join_list is a nested join apply
5279
5405
        not_null_tables= conds->not_null_tables();
5280
5406
    }
5281
5407
 
5282
 
    if (table->getEmbedding())
 
5408
    if (table->embedding)
5283
5409
    {
5284
 
      table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;
5285
 
      table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;
 
5410
      table->embedding->nested_join->used_tables|= used_tables;
 
5411
      table->embedding->nested_join->not_null_tables|= not_null_tables;
5286
5412
    }
5287
5413
 
5288
5414
    if (!table->outer_join || (used_tables & not_null_tables))
5318
5444
    */
5319
5445
    if (table->on_expr)
5320
5446
    {
5321
 
      table->setDepTables(table->getDepTables() | table->on_expr->used_tables());
5322
 
      if (table->getEmbedding())
 
5447
      table->dep_tables|= table->on_expr->used_tables();
 
5448
      if (table->embedding)
5323
5449
      {
5324
 
        table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);
 
5450
        table->dep_tables&= ~table->embedding->nested_join->used_tables;
5325
5451
        /*
5326
5452
           Embedding table depends on tables used
5327
5453
           in embedded on expressions.
5328
5454
        */
5329
 
        table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());
 
5455
        table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5330
5456
      }
5331
5457
      else
5332
 
        table->setDepTables(table->getDepTables() & ~table->table->map);
 
5458
        table->dep_tables&= ~table->table->map;
5333
5459
    }
5334
5460
 
5335
5461
    if (prev_table)
5336
5462
    {
5337
 
      //If this is straight join, set prev table to be dependent on all tables
5338
 
      //from this nested join, so that correct join order is selected.
5339
 
      if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||
5340
 
          prev_table->straight)
5341
 
        prev_table->setDepTables(prev_table->getDepTables() | used_tables);
 
5463
      /* The order of tables is reverse: prev_table follows table */
 
5464
      if (prev_table->straight)
 
5465
        prev_table->dep_tables|= used_tables;
5342
5466
      if (prev_table->on_expr)
5343
5467
      {
5344
 
        prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());
5345
 
        table_map prev_used_tables= prev_table->getNestedJoin() ?
5346
 
                                    prev_table->getNestedJoin()->used_tables :
 
5468
        prev_table->dep_tables|= table->on_expr_dep_tables;
 
5469
        table_map prev_used_tables= prev_table->nested_join ?
 
5470
                                    prev_table->nested_join->used_tables :
5347
5471
                                    prev_table->table->map;
5348
5472
        /*
5349
5473
          If on expression contains only references to inner tables
5352
5476
          for them. Yet this is really a rare case.
5353
5477
              */
5354
5478
        if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5355
 
          prev_table->setDepTables(prev_table->getDepTables() | used_tables);
 
5479
          prev_table->dep_tables|= used_tables;
5356
5480
      }
5357
5481
    }
5358
5482
    prev_table= table;
5365
5489
  li.rewind();
5366
5490
  while ((table= li++))
5367
5491
  {
5368
 
    nested_join= table->getNestedJoin();
 
5492
    nested_join= table->nested_join;
5369
5493
    if (nested_join && !table->on_expr)
5370
5494
    {
5371
5495
      TableList *tbl;
5372
5496
      List_iterator<TableList> it(nested_join->join_list);
5373
5497
      while ((tbl= it++))
5374
5498
      {
5375
 
        tbl->setEmbedding(table->getEmbedding());
5376
 
        tbl->setJoinList(table->getJoinList());
 
5499
        tbl->embedding= table->embedding;
 
5500
        tbl->join_list= table->join_list;
5377
5501
      }
5378
5502
      li.replace(nested_join->join_list);
5379
5503
    }
5381
5505
  return(conds);
5382
5506
}
5383
5507
 
5384
 
static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)
 
5508
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5385
5509
{
5386
5510
  int error;
5387
5511
  uint32_t reclength,offset;
5405
5529
    join->unit->select_limit_cnt= 1;            // Only send first row
5406
5530
    return(0);
5407
5531
  }
5408
 
  Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;
 
5532
  Field **first_field=entry->field+entry->s->fields - field_count;
5409
5533
  offset= (field_count ?
5410
 
           entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0);
5411
 
  reclength= entry->getShare()->getRecordLength() - offset;
 
5534
           entry->field[entry->s->fields - field_count]->
 
5535
           offset(entry->record[0]) : 0);
 
5536
  reclength= entry->s->reclength-offset;
5412
5537
 
5413
5538
  entry->free_io_cache();                               // Safety
5414
5539
  entry->cursor->info(HA_STATUS_VARIABLE);
5415
 
  if (entry->getShare()->db_type() == heap_engine ||
5416
 
      (!entry->getShare()->blob_fields &&
 
5540
  if (entry->s->db_type() == heap_engine ||
 
5541
      (!entry->s->blob_fields &&
5417
5542
       ((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5418
 
        session->variables.sortbuff_size)))
5419
 
  {
 
5543
        session->variables.sortbuff_size)))
5420
5544
    error= remove_dup_with_hash_index(join->session, entry,
5421
 
                                      field_count, first_field,
5422
 
                                      reclength, having);
5423
 
  }
 
5545
                                     field_count, first_field,
 
5546
                                     reclength, having);
5424
5547
  else
5425
 
  {
5426
 
    error= remove_dup_with_compare(join->session, entry, first_field, offset, having);
5427
 
  }
 
5548
    error= remove_dup_with_compare(join->session, entry, first_field, offset,
 
5549
                                  having);
5428
5550
 
5429
5551
  free_blobs(first_field);
5430
 
 
5431
5552
  return(error);
5432
5553
}
5433
5554
 
5441
5562
                               List<Item> &fields,
5442
5563
                               List<Item> &all_fields,
5443
5564
                               COND **conds,
5444
 
                               Order *order,
5445
 
                               Order *group,
 
5565
                               order_st *order,
 
5566
                               order_st *group,
5446
5567
                               bool *hidden_group_fields)
5447
5568
{
5448
5569
  int res;
5469
5590
  @retval
5470
5591
    1   Fatal error
5471
5592
*/
5472
 
static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
 
5593
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5473
5594
{
5474
5595
  int error;
5475
5596
  Table *table;
5512
5633
       tables;
5513
5634
       s++, tables= tables->next_leaf, i++)
5514
5635
  {
5515
 
    TableList *embedding= tables->getEmbedding();
 
5636
    TableList *embedding= tables->embedding;
5516
5637
    stat_vector[i]=s;
5517
5638
    s->keys.reset();
5518
5639
    s->const_keys.reset();
5520
5641
    s->needed_reg.reset();
5521
5642
    table_vector[i]=s->table=table=tables->table;
5522
5643
    table->pos_in_table_list= tables;
5523
 
    assert(table->cursor);
5524
5644
    error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5525
5645
    if (error)
5526
5646
    {
5531
5651
    table->reginfo.join_tab=s;
5532
5652
    table->reginfo.not_exists_optimize=0;
5533
5653
    memset(table->const_key_parts, 0,
5534
 
           sizeof(key_part_map)*table->getShare()->sizeKeys());
 
5654
           sizeof(key_part_map)*table->s->keys);
5535
5655
    all_table_map|= table->map;
5536
5656
    s->join=join;
5537
5657
    s->info=0;                                  // For describe
5538
5658
 
5539
 
    s->dependent= tables->getDepTables();
 
5659
    s->dependent= tables->dep_tables;
5540
5660
    s->key_dependent= 0;
5541
5661
    table->quick_condition_rows= table->cursor->stats.records;
5542
5662
 
5552
5672
      }
5553
5673
      outer_join|= table->map;
5554
5674
      s->embedding_map.reset();
5555
 
      for (;embedding; embedding= embedding->getEmbedding())
5556
 
        s->embedding_map|= embedding->getNestedJoin()->nj_map;
 
5675
      for (;embedding; embedding= embedding->embedding)
 
5676
        s->embedding_map|= embedding->nested_join->nj_map;
5557
5677
      continue;
5558
5678
    }
5559
 
    if (embedding && !(false && ! embedding->getEmbedding()))
 
5679
    if (embedding && !(false && ! embedding->embedding))
5560
5680
    {
5561
5681
      /* s belongs to a nested join, maybe to several embedded joins */
5562
5682
      s->embedding_map.reset();
5563
5683
      do
5564
5684
      {
5565
 
        nested_join_st *nested_join= embedding->getNestedJoin();
 
5685
        nested_join_st *nested_join= embedding->nested_join;
5566
5686
        s->embedding_map|= nested_join->nj_map;
5567
 
        s->dependent|= embedding->getDepTables();
5568
 
        embedding= embedding->getEmbedding();
 
5687
        s->dependent|= embedding->dep_tables;
 
5688
        embedding= embedding->embedding;
5569
5689
        outer_join|= nested_join->used_tables;
5570
5690
      }
5571
5691
      while (embedding);
5699
5819
          continue;
5700
5820
        if (table->cursor->stats.records <= 1L &&
5701
5821
            (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5702
 
                  !table->pos_in_table_list->getEmbedding())
 
5822
                  !table->pos_in_table_list->embedding)
5703
5823
        {                                       // system table
5704
5824
          int tmp= 0;
5705
5825
          s->type= AM_SYSTEM;
5744
5864
          } while (keyuse->getTable() == table && keyuse->getKey() == key);
5745
5865
 
5746
5866
          if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5747
 
              ! table->pos_in_table_list->getEmbedding())
 
5867
              ! table->pos_in_table_list->embedding)
5748
5868
          {
5749
5869
            if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5750
5870
            {
5788
5908
    while (iter != sargables.end())
5789
5909
    {
5790
5910
      Field *field= (*iter).getField();
5791
 
      JoinTable *join_tab= field->getTable()->reginfo.join_tab;
 
5911
      JoinTable *join_tab= field->table->reginfo.join_tab;
5792
5912
      key_map possible_keys= field->key_start;
5793
 
      possible_keys&= field->getTable()->keys_in_use_for_query;
 
5913
      possible_keys&= field->table->keys_in_use_for_query;
5794
5914
      bool is_const= true;
5795
5915
      for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
5796
5916
        is_const&= (*iter).isConstItem(j);
5831
5951
    add_group_and_distinct_keys(join, s);
5832
5952
 
5833
5953
    if (s->const_keys.any() &&
5834
 
        !s->table->pos_in_table_list->getEmbedding())
 
5954
        !s->table->pos_in_table_list->embedding)
5835
5955
    {
5836
5956
      ha_rows records;
5837
5957
      optimizer::SqlSelect *select= NULL;
5881
6001
  if (join->const_tables != join->tables)
5882
6002
  {
5883
6003
    optimize_keyuse(join, keyuse_array);
5884
 
    // @note c_str() is not likely to be valid here if dtrace expects it to
5885
 
    // exist for any period of time.
5886
 
    DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);
 
6004
    DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->query.c_str(), join->session->thread_id);
5887
6005
    bool res= choose_plan(join, all_table_map & ~join->const_table_map);
5888
6006
    DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
5889
6007
    if (res)
5895
6013
    join->best_read= 1.0;
5896
6014
  }
5897
6015
  /* Generate an execution plan from the found optimal join order. */
5898
 
  return (join->session->getKilled() || get_best_combination(join));
 
6016
  return (join->session->killed || get_best_combination(join));
5899
6017
}
5900
6018
 
5901
6019
/**
5924
6042
  while ((table= li++))
5925
6043
  {
5926
6044
    nested_join_st *nested_join;
5927
 
    if ((nested_join= table->getNestedJoin()))
 
6045
    if ((nested_join= table->nested_join))
5928
6046
    {
5929
6047
      /*
5930
6048
        It is guaranteed by simplify_joins() function that a nested join
5955
6073
  Return table number if there is only one table in sort order
5956
6074
  and group and order is compatible, else return 0.
5957
6075
*/
5958
 
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables)
 
6076
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
5959
6077
{
5960
6078
  table_map map= (table_map) 0;
5961
6079
 
5995
6113
  while ((table= li++))
5996
6114
  {
5997
6115
    nested_join_st *nested_join;
5998
 
    if ((nested_join= table->getNestedJoin()))
 
6116
    if ((nested_join= table->nested_join))
5999
6117
    {
6000
6118
      nested_join->counter_= 0;
6001
6119
      reset_nj_counters(&nested_join->join_list);
6010
6128
  If first parts has different direction, change it to second part
6011
6129
  (group is sorted like order)
6012
6130
*/
6013
 
static bool test_if_subpart(Order *a, Order *b)
 
6131
static bool test_if_subpart(order_st *a,order_st *b)
6014
6132
{
6015
6133
  for (; a && b; a=a->next,b=b->next)
6016
6134
  {
6025
6143
/**
6026
6144
  Nested joins perspective: Remove the last table from the join order.
6027
6145
 
6028
 
  The algorithm is the reciprocal of check_interleaving_with_nj(), hence
6029
 
  parent join nest nodes are updated only when the last table in its child
6030
 
  node is removed. The ASCII graphic below will clarify.
6031
 
 
6032
 
  %A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
6033
 
  represented by the below join nest tree.
6034
 
 
6035
 
  @verbatim
6036
 
                     NJ1
6037
 
                  _/ /  \
6038
 
                _/  /    NJ2
6039
 
              _/   /     / \ 
6040
 
             /    /     /   \
6041
 
   t1 x [ (t2 x t3) x (t4 x t5) ]
6042
 
  @endverbatim
6043
 
 
6044
 
  At the point in time when check_interleaving_with_nj() adds the table t5 to
6045
 
  the query execution plan, QEP, it also directs the node named NJ2 to mark
6046
 
  the table as covered. NJ2 does so by incrementing its @c counter
6047
 
  member. Since all of NJ2's tables are now covered by the QEP, the algorithm
6048
 
  proceeds up the tree to NJ1, incrementing its counter as well. All join
6049
 
  nests are now completely covered by the QEP.
6050
 
 
6051
 
  restore_prev_nj_state() does the above in reverse. As seen above, the node
6052
 
  NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
6053
 
  that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
6054
 
  completely covers NJ2. The removal of t5 from the partial plan will first
6055
 
  decrement NJ2's counter to 1. It will then detect that NJ2 went from being
6056
 
  completely to partially covered, and hence the algorithm must continue
6057
 
  upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
6058
 
  will however not influence NJ1 since it did not un-cover the last table in
6059
 
  NJ2.
6060
 
 
6061
 
  SYNOPSIS
6062
 
    restore_prev_nj_state()
6063
 
      last  join table to remove, it is assumed to be the last in current 
6064
 
            partial join order.
6065
 
     
6066
 
  DESCRIPTION
6067
 
 
6068
6146
    Remove the last table from the partial join order and update the nested
6069
 
    joins counters and join->cur_embedding_map. It is ok to call this 
6070
 
    function for the first table in join order (for which 
 
6147
    joins counters and join->cur_embedding_map. It is ok to call this
 
6148
    function for the first table in join order (for which
6071
6149
    check_interleaving_with_nj has not been called)
6072
6150
 
6073
6151
  @param last  join table to remove, it is assumed to be the last in current
6074
6152
               partial join order.
6075
6153
*/
6076
 
 
6077
6154
static void restore_prev_nj_state(JoinTable *last)
6078
6155
{
6079
 
  TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6080
 
  Join *join= last->join;
6081
 
  for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6082
 
  {
6083
 
    nested_join_st *nest= last_emb->getNestedJoin();
6084
 
    
6085
 
    bool was_fully_covered= nest->is_fully_covered();
6086
 
    
6087
 
    if (--nest->counter_ == 0)
6088
 
      join->cur_embedding_map&= ~nest->nj_map;
6089
 
    
6090
 
    if (!was_fully_covered)
 
6156
  TableList *last_emb= last->table->pos_in_table_list->embedding;
 
6157
  JOIN *join= last->join;
 
6158
  while (last_emb)
 
6159
  {
 
6160
    if (last_emb->on_expr)
 
6161
    {
 
6162
      if (!(--last_emb->nested_join->counter_))
 
6163
        join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
 
6164
      else if (last_emb->nested_join->join_list.elements-1 ==
 
6165
               last_emb->nested_join->counter_)
 
6166
        join->cur_embedding_map|= last_emb->nested_join->nj_map;
 
6167
      else
 
6168
        break;
 
6169
    }
 
6170
    last_emb= last_emb->embedding;
 
6171
  }
 
6172
}
 
6173
 
 
6174
/**
 
6175
  Determine if the set is already ordered for order_st BY, so it can
 
6176
  disable join cache because it will change the ordering of the results.
 
6177
  Code handles sort table that is at any location (not only first after
 
6178
  the const tables) despite the fact that it's currently prohibited.
 
6179
  We must disable join cache if the first non-const table alone is
 
6180
  ordered. If there is a temp table the ordering is done as a last
 
6181
  operation and doesn't prevent join cache usage.
 
6182
*/
 
6183
static uint32_t make_join_orderinfo(JOIN *join)
 
6184
{
 
6185
  uint32_t i;
 
6186
  if (join->need_tmp)
 
6187
    return join->tables;
 
6188
 
 
6189
  for (i=join->const_tables ; i < join->tables ; i++)
 
6190
  {
 
6191
    JoinTable *tab= join->join_tab+i;
 
6192
    Table *table= tab->table;
 
6193
    if ((table == join->sort_by_table &&
 
6194
        (!join->order || join->skip_sort_order)) ||
 
6195
        (join->sort_by_table == (Table *) 1 &&  i != join->const_tables))
 
6196
    {
6091
6197
      break;
6092
 
    
6093
 
    join->cur_embedding_map|= nest->nj_map;
 
6198
    }
6094
6199
  }
 
6200
  return i;
6095
6201
}
6096
6202
 
6097
6203
/**
6111
6217
 
6112
6218
  for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6113
6219
  {
6114
 
    Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
 
6220
    Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
 
6221
                              fieldnr-1];
6115
6222
    Item *value=join_tab->ref.items[i];
6116
6223
    cond->add(new Item_func_equal(new Item_field(field), value));
6117
6224
  }