← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/join.cc

  • Committer: Stewart Smith
  • Date: 2009-06-16 00:45:15 UTC
  • mto: (1119.2.6 merge)
  • mto: This revision was merged to the branch mainline in revision 1124.
  • Revision ID: stewart@flamingspork.com-20090616004515-bgr8e62psvn2820l
make snowman test not leave tables behind after running

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/join.cc
1
1
/* - mode: c; c-basic-offset: 2; indent-tabs-mode: nil; -*-
2
2
 *  vim:expandtab:shiftwidth=2:tabstop=2:smarttab:
3
3
 *
4
 
 *  Copyright (C) 2008-2009 Sun Microsystems, Inc.
 
4
 *  Copyright (C) 2008-2009 Sun Microsystems
5
5
 *
6
6
 *  This program is free software; you can redistribute it and/or modify
7
7
 *  it under the terms of the GNU General Public License as published by
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
 * @{
28
28
 */
29
29
 
30
 
#include "config.h"
31
 
 
32
 
#include <float.h>
33
 
#include <math.h>
34
 
 
 
30
#include "drizzled/server_includes.h"
 
31
#include "drizzled/table_map_iterator.h"
35
32
#include "drizzled/item/cache.h"
36
33
#include "drizzled/item/cmpfunc.h"
37
34
#include "drizzled/item/copy_string.h"
45
42
#include "drizzled/join_cache.h"
46
43
#include "drizzled/show.h"
47
44
#include "drizzled/field/blob.h"
48
 
#include "drizzled/optimizer/position.h"
49
 
#include "drizzled/optimizer/sargable_param.h"
50
 
#include "drizzled/optimizer/key_use.h"
51
 
#include "drizzled/optimizer/range.h"
52
 
#include "drizzled/optimizer/sum.h"
53
 
#include "drizzled/optimizer/explain_plan.h"
54
 
#include "drizzled/optimizer/access_method_factory.h"
55
 
#include "drizzled/optimizer/access_method.h"
56
 
#include "drizzled/records.h"
57
 
#include "drizzled/probes.h"
58
 
#include "drizzled/internal/my_bit.h"
59
 
#include "drizzled/internal/my_sys.h"
60
 
#include "drizzled/internal/iocache.h"
61
 
#include "drizzled/plugin/storage_engine.h"
62
 
 
63
 
#include <drizzled/debug.h>
 
45
#include "mysys/my_bit.h"
64
46
 
65
47
#include <algorithm>
66
48
 
67
49
using namespace std;
68
50
 
69
 
namespace drizzled
70
 
{
71
 
extern plugin::StorageEngine *heap_engine;
72
 
 
73
51
/** Declarations of static functions used in this source file. */
74
 
static bool make_group_fields(Join *main_join, Join *curr_join);
75
 
static void calc_group_buffer(Join *join, Order *group);
76
 
static bool alloc_group_fields(Join *join, Order *group);
77
 
static uint32_t cache_record_length(Join *join, uint32_t index);
78
 
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref);
79
 
static bool get_best_combination(Join *join);
80
 
static void set_position(Join *join,
81
 
                         uint32_t index,
82
 
                         JoinTable *table,
83
 
                         optimizer::KeyUse *key);
84
 
static bool choose_plan(Join *join,table_map join_tables);
85
 
static void best_access_path(Join *join, JoinTable *s,
 
52
static bool make_group_fields(JOIN *main_join, JOIN *curr_join);
 
53
static void calc_group_buffer(JOIN *join,order_st *group);
 
54
static bool alloc_group_fields(JOIN *join,order_st *group);
 
55
/*
 
56
  TODO: 'find_best' is here only temporarily until 'greedy_search' is
 
57
  tested and approved.
 
58
*/
 
59
static bool find_best(JOIN *join,table_map rest_tables,uint32_t index, double record_count,double read_time);
 
60
static uint32_t cache_record_length(JOIN *join, uint32_t index);
 
61
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref);
 
62
static bool get_best_combination(JOIN *join);
 
63
static void set_position(JOIN *join,uint32_t index,JoinTable *table,KeyUse *key);
 
64
static bool choose_plan(JOIN *join,table_map join_tables);
 
65
static void best_access_path(JOIN *join, JoinTable *s,
86
66
                             Session *session,
87
67
                             table_map remaining_tables,
88
68
                             uint32_t idx,
89
69
                             double record_count,
90
70
                             double read_time);
91
 
static void optimize_straight_join(Join *join, table_map join_tables);
92
 
static bool greedy_search(Join *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
93
 
static bool best_extension_by_limited_search(Join *join,
 
71
static void optimize_straight_join(JOIN *join, table_map join_tables);
 
72
static bool greedy_search(JOIN *join, table_map remaining_tables, uint32_t depth, uint32_t prune_level);
 
73
static bool best_extension_by_limited_search(JOIN *join,
94
74
                                             table_map remaining_tables,
95
75
                                             uint32_t idx,
96
76
                                             double record_count,
97
77
                                             double read_time,
98
78
                                             uint32_t depth,
99
79
                                             uint32_t prune_level);
100
 
static uint32_t determine_search_depth(Join* join);
101
 
static bool make_simple_join(Join *join,Table *tmp_table);
102
 
static void make_outerjoin_info(Join *join);
103
 
static bool make_join_select(Join *join, optimizer::SqlSelect *select,COND *item);
104
 
static bool make_join_readinfo(Join *join);
105
 
static void update_depend_map(Join *join);
106
 
static void update_depend_map(Join *join, Order *order);
107
 
static Order *remove_constants(Join *join,Order *first_order,COND *cond, bool change_list, bool *simple_order);
108
 
static int return_zero_rows(Join *join,
 
80
static uint32_t determine_search_depth(JOIN* join);
 
81
static bool make_simple_join(JOIN *join,Table *tmp_table);
 
82
static void make_outerjoin_info(JOIN *join);
 
83
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *item);
 
84
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after);
 
85
static void update_depend_map(JOIN *join);
 
86
static void update_depend_map(JOIN *join, order_st *order);
 
87
static order_st *remove_constants(JOIN *join,order_st *first_order,COND *cond, bool change_list, bool *simple_order);
 
88
static int return_zero_rows(JOIN *join,
109
89
                            select_result *res,
110
90
                            TableList *tables,
111
91
                            List<Item> &fields,
113
93
                            uint64_t select_options,
114
94
                            const char *info,
115
95
                            Item *having);
116
 
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top);
117
 
static int remove_duplicates(Join *join,Table *entry,List<Item> &fields, Item *having);
 
96
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top);
 
97
static int remove_duplicates(JOIN *join,Table *entry,List<Item> &fields, Item *having);
118
98
static int setup_without_group(Session *session, 
119
99
                               Item **ref_pointer_array,
120
100
                               TableList *tables,
122
102
                               List<Item> &fields,
123
103
                               List<Item> &all_fields,
124
104
                               COND **conds,
125
 
                               Order *order,
126
 
                               Order *group,
 
105
                               order_st *order,
 
106
                               order_st *group,
127
107
                               bool *hidden_group_fields);
128
 
static bool make_join_statistics(Join *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
 
108
static bool make_join_statistics(JOIN *join, TableList *leaves, COND *conds, DYNAMIC_ARRAY *keyuse);
129
109
static uint32_t build_bitmap_for_nested_joins(List<TableList> *join_list, uint32_t first_unused);
130
 
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables);
 
110
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables);
131
111
static void reset_nj_counters(List<TableList> *join_list);
132
 
static bool test_if_subpart(Order *a,Order *b);
 
112
static bool test_if_subpart(order_st *a,order_st *b);
133
113
static void restore_prev_nj_state(JoinTable *last);
 
114
static uint32_t make_join_orderinfo(JOIN *join);
134
115
static bool add_ref_to_table_cond(Session *session, JoinTable *join_tab);
135
116
static void free_blobs(Field **ptr); /* Rename this method...conflicts with another in global namespace... */
136
117
 
137
 
Join::Join(Session *session_arg, 
138
 
           List<Item> &fields_arg, 
139
 
           uint64_t select_options_arg,
140
 
           select_result *result_arg) :
141
 
  join_tab(NULL),
142
 
  best_ref(NULL),
143
 
  map2table(NULL),
144
 
  join_tab_save(NULL),
145
 
  table(NULL),
146
 
  all_tables(NULL),
147
 
  sort_by_table(NULL),
148
 
  tables(0),
149
 
  outer_tables(0),
150
 
  const_tables(0),
151
 
  send_group_parts(0),
152
 
  sort_and_group(false),
153
 
  first_record(false),
154
 
  full_join(false),
155
 
  group(false),
156
 
  no_field_update(false),
157
 
  do_send_rows(true),
158
 
  resume_nested_loop(false),
159
 
  no_const_tables(false),
160
 
  select_distinct(false),
161
 
  group_optimized_away(false),
162
 
  simple_order(false),
163
 
  simple_group(false),
164
 
  no_order(false),
165
 
  skip_sort_order(false),
166
 
  union_part(false),
167
 
  optimized(false),
168
 
  need_tmp(false),
169
 
  hidden_group_fields(false),
170
 
  const_table_map(0),
171
 
  found_const_table_map(0),
172
 
  outer_join(0),
173
 
  send_records(0),
174
 
  found_records(0),
175
 
  examined_rows(0),
176
 
  row_limit(0),
177
 
  select_limit(0),
178
 
  fetch_limit(HA_POS_ERROR),
179
 
  session(session_arg),
180
 
  fields_list(fields_arg), 
181
 
  join_list(NULL),
182
 
  unit(NULL),
183
 
  select_lex(NULL),
184
 
  select(NULL),
185
 
  exec_tmp_table1(NULL),
186
 
  exec_tmp_table2(NULL),
187
 
  sum_funcs(NULL),
188
 
  sum_funcs2(NULL),
189
 
  having(NULL),
190
 
  tmp_having(NULL),
191
 
  having_history(NULL),
192
 
  select_options(select_options_arg),
193
 
  result(result_arg),
194
 
  lock(session_arg->lock),
195
 
  tmp_join(NULL),
196
 
  all_fields(fields_arg),
197
 
  error(0),
198
 
  cond_equal(NULL),
199
 
  return_tab(NULL),
200
 
  ref_pointer_array(NULL),
201
 
  items0(NULL),
202
 
  items1(NULL),
203
 
  items2(NULL),
204
 
  items3(NULL),
205
 
  ref_pointer_array_size(0),
206
 
  zero_result_cause(NULL),
207
 
  sortorder(NULL),
208
 
  table_reexec(NULL),
209
 
  join_tab_reexec(NULL)
210
 
{
211
 
  select_distinct= test(select_options & SELECT_DISTINCT);
212
 
  if (&fields_list != &fields_arg) /* only copy if not same*/
213
 
    fields_list= fields_arg;
214
 
  memset(&keyuse, 0, sizeof(keyuse));
215
 
  tmp_table_param.init();
216
 
  tmp_table_param.end_write_records= HA_POS_ERROR;
217
 
  rollup.setState(Rollup::STATE_NONE);
218
 
}
219
 
 
220
 
  /** 
221
 
   * This method is currently only used when a subselect EXPLAIN is performed.
222
 
   * I pulled out the init() method and have simply reset the values to what
223
 
   * was previously in the init() method.  See the note about the hack in 
224
 
   * sql_union.cc...
225
 
   */
226
 
void Join::reset(Session *session_arg, 
227
 
                 List<Item> &fields_arg, 
228
 
                 uint64_t select_options_arg,
229
 
                 select_result *result_arg)
230
 
{
231
 
  join_tab= NULL;
232
 
  best_ref= NULL;
233
 
  map2table= NULL;
234
 
  join_tab_save= NULL;
235
 
  table= NULL;
236
 
  all_tables= NULL;
237
 
  sort_by_table= NULL;
238
 
  tables= 0;
239
 
  outer_tables= 0;
240
 
  const_tables= 0;
241
 
  send_group_parts= 0;
242
 
  sort_and_group= false;
243
 
  first_record= false;
244
 
  full_join= false;
245
 
  group= false;
246
 
  no_field_update= false;
247
 
  do_send_rows= true;
248
 
  resume_nested_loop= false;
249
 
  no_const_tables= false;
250
 
  select_distinct= false;
251
 
  group_optimized_away= false;
252
 
  simple_order= false;
253
 
  simple_group= false;
254
 
  no_order= false;
255
 
  skip_sort_order= false;
256
 
  union_part= false;
257
 
  optimized= false;
258
 
  need_tmp= false;
259
 
  hidden_group_fields= false;
260
 
  const_table_map= 0;
261
 
  found_const_table_map= 0;
262
 
  outer_join= 0;
263
 
  send_records= 0;
264
 
  found_records= 0;
265
 
  examined_rows= 0;
266
 
  row_limit= 0;
267
 
  select_limit= 0;
268
 
  fetch_limit= HA_POS_ERROR;
269
 
  session= session_arg;
270
 
  fields_list= fields_arg; 
271
 
  join_list= NULL;
272
 
  unit= NULL;
273
 
  select_lex= NULL;
274
 
  select= NULL;
275
 
  exec_tmp_table1= NULL;
276
 
  exec_tmp_table2= NULL;
277
 
  sum_funcs= NULL;
278
 
  sum_funcs2= NULL;
279
 
  having= NULL;
280
 
  tmp_having= NULL;
281
 
  having_history= NULL;
282
 
  select_options= select_options_arg;
283
 
  result= result_arg;
284
 
  lock= session_arg->lock;
285
 
  tmp_join= NULL;
286
 
  all_fields= fields_arg;
287
 
  error= 0;
288
 
  cond_equal= NULL;
289
 
  return_tab= NULL;
290
 
  ref_pointer_array= NULL;
291
 
  items0= NULL;
292
 
  items1= NULL;
293
 
  items2= NULL;
294
 
  items3= NULL;
295
 
  ref_pointer_array_size= 0;
296
 
  zero_result_cause= NULL;
297
 
  sortorder= NULL;
298
 
  table_reexec= NULL;
299
 
  join_tab_reexec= NULL;
300
 
  select_distinct= test(select_options & SELECT_DISTINCT);
301
 
  if (&fields_list != &fields_arg) /* only copy if not same*/
302
 
    fields_list= fields_arg;
303
 
  memset(&keyuse, 0, sizeof(keyuse));
304
 
  tmp_table_param.init();
305
 
  tmp_table_param.end_write_records= HA_POS_ERROR;
306
 
  rollup.setState(Rollup::STATE_NONE);
307
 
}
308
 
 
309
 
bool Join::is_top_level_join() const
310
 
{
311
 
  return (unit == &session->lex->unit && (unit->fake_select_lex == 0 ||
312
 
                                          select_lex == unit->fake_select_lex));
313
 
}
314
 
 
315
118
/**
316
119
  Prepare of whole select (including sub queries in future).
317
120
 
324
127
  @retval
325
128
    0   on success
326
129
*/
327
 
int Join::prepare(Item ***rref_pointer_array,
 
130
int JOIN::prepare(Item ***rref_pointer_array,
328
131
                  TableList *tables_init,
329
132
                  uint32_t wild_num,
330
133
                  COND *conds_init,
331
134
                  uint32_t og_num,
332
 
                  Order *order_init,
333
 
                  Order *group_init,
 
135
                  order_st *order_init,
 
136
                  order_st *group_init,
334
137
                  Item *having_init,
335
138
                  Select_Lex *select_lex_arg,
336
139
                  Select_Lex_Unit *unit_arg)
363
166
      setup_tables_and_check_access(session, &select_lex->context, join_list,
364
167
                                    tables_list, &select_lex->leaf_tables,
365
168
                                    false))
366
 
  {
367
169
      return(-1);
368
 
  }
369
170
 
370
171
  TableList *table_ptr;
371
172
  for (table_ptr= select_lex->leaf_tables;
372
173
       table_ptr;
373
174
       table_ptr= table_ptr->next_leaf)
374
 
  {
375
175
    tables++;
376
 
  }
377
 
 
378
176
 
379
177
  if (setup_wild(session, fields_list, &all_fields, wild_num) ||
380
178
      select_lex->setup_ref_array(session, og_num) ||
384
182
        select_lex->leaf_tables, fields_list,
385
183
        all_fields, &conds, order, group_list,
386
184
        &hidden_group_fields))
387
 
    return(-1);
 
185
    return(-1);       /* purecov: inspected */
388
186
 
389
187
  ref_pointer_array= *rref_pointer_array;
390
188
 
391
189
  if (having)
392
190
  {
393
191
    nesting_map save_allow_sum_func= session->lex->allow_sum_func;
394
 
    session->setWhere("having clause");
 
192
    session->where="having clause";
395
193
    session->lex->allow_sum_func|= 1 << select_lex_arg->nest_level;
396
194
    select_lex->having_fix_field= 1;
397
195
    bool having_fix_rc= (!having->fixed &&
399
197
        having->check_cols(1)));
400
198
    select_lex->having_fix_field= 0;
401
199
    if (having_fix_rc || session->is_error())
402
 
      return(-1);
 
200
      return(-1);       /* purecov: inspected */
403
201
    session->lex->allow_sum_func= save_allow_sum_func;
404
202
  }
405
203
 
416
214
        in_subs= (Item_in_subselect*)subselect;
417
215
 
418
216
      {
419
 
        bool do_materialize= true;
 
217
        bool do_materialize= !test(session->variables.optimizer_switch &
 
218
                                   OPTIMIZER_SWITCH_NO_MATERIALIZATION);
420
219
        /*
421
220
          Check if the subquery predicate can be executed via materialization.
422
221
          The required conditions are:
434
233
             (Subquery is non-correlated ||
435
234
              Subquery is correlated to any query outer to IN predicate ||
436
235
              (Subquery is correlated to the immediate outer query &&
437
 
               Subquery !contains {GROUP BY, ORDER BY [LIMIT],
 
236
               Subquery !contains {GROUP BY, order_st BY [LIMIT],
438
237
               aggregate functions) && subquery predicate is not under "NOT IN"))
439
238
          6. No execution method was already chosen (by a prepared statement).
440
239
 
470
269
 
471
270
  if (order)
472
271
  {
473
 
    Order *ord;
 
272
    order_st *ord;
474
273
    for (ord= order; ord; ord= ord->next)
475
274
    {
476
275
      Item *item= *ord->item;
515
314
  {
516
315
    /* Caclulate the number of groups */
517
316
    send_group_parts= 0;
518
 
    for (Order *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
 
317
    for (order_st *group_tmp= group_list ; group_tmp ; group_tmp= group_tmp->next)
519
318
      send_group_parts++;
520
319
  }
521
320
 
522
321
  if (error)
523
 
    return(-1);
 
322
    goto err;         /* purecov: inspected */
524
323
 
525
 
  /* 
526
 
   * The below will create the new table for
527
 
   * CREATE TABLE ... SELECT
528
 
   *
529
 
   * @see create_table_from_items() in drizzled/sql_insert.cc
530
 
   */
531
324
  if (result && result->prepare(fields_list, unit_arg))
532
 
    return(-1);
 
325
    goto err;         /* purecov: inspected */
533
326
 
534
327
  /* Init join struct */
535
328
  count_field_types(select_lex, &tmp_table_param, all_fields, 0);
541
334
  if (sum_func_count && !group_list && (func_count || field_count))
542
335
  {
543
336
    my_message(ER_WRONG_SUM_SELECT,ER(ER_WRONG_SUM_SELECT),MYF(0));
544
 
    return(-1);
 
337
    goto err;
545
338
  }
546
339
#endif
547
340
  if (select_lex->olap == ROLLUP_TYPE && rollup_init())
548
 
    return(-1);
549
 
 
 
341
    goto err;
550
342
  if (alloc_func_list())
551
 
    return(-1);
552
 
 
553
 
  return 0; // All OK
 
343
    goto err;
 
344
 
 
345
  return(0); // All OK
 
346
 
 
347
err:
 
348
  return(-1);       /* purecov: inspected */
554
349
}
555
350
 
556
351
/*
557
352
  Remove the predicates pushed down into the subquery
558
353
 
559
354
  SYNOPSIS
560
 
    Join::remove_subq_pushed_predicates()
 
355
    JOIN::remove_subq_pushed_predicates()
561
356
      where   IN  Must be NULL
562
357
              OUT The remaining WHERE condition, or NULL
563
358
 
582
377
    that is searched in a byte. But this requires homogenization of the return
583
378
    codes of all Field*::store() methods.
584
379
*/
585
 
void Join::remove_subq_pushed_predicates(Item **where)
 
380
void JOIN::remove_subq_pushed_predicates(Item **where)
586
381
{
587
382
  if (conds->type() == Item::FUNC_ITEM &&
588
383
      ((Item_func *)this->conds)->functype() == Item_func::EQ_FUNC &&
607
402
  @retval
608
403
    1   error
609
404
*/
610
 
int Join::optimize()
 
405
int JOIN::optimize()
611
406
{
612
407
  // to prevent double initialization on EXPLAIN
613
408
  if (optimized)
614
 
    return 0;
 
409
    return(0);
615
410
  optimized= 1;
616
411
 
617
412
  session->set_proc_info("optimizing");
677
472
    {           /* Impossible cond */
678
473
      zero_result_cause=  having_value == Item::COND_FALSE ?
679
474
                           "Impossible HAVING" : "Impossible WHERE";
680
 
      tables = 0;
681
 
      goto setup_subq_exit;
 
475
      error= 0;
 
476
      return(0);
682
477
    }
683
478
  }
684
479
 
687
482
  {
688
483
    int res;
689
484
    /*
690
 
      optimizer::sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
 
485
      opt_sum_query() returns HA_ERR_KEY_NOT_FOUND if no rows match
691
486
      to the WHERE conditions,
692
487
      or 1 if all items were resolved,
693
488
      or 0, or an error number HA_ERR_...
694
489
    */
695
 
    if ((res= optimizer::sum_query(select_lex->leaf_tables, all_fields, conds)))
 
490
    if ((res=opt_sum_query(select_lex->leaf_tables, all_fields, conds)))
696
491
    {
697
492
      if (res == HA_ERR_KEY_NOT_FOUND)
698
493
      {
699
494
        zero_result_cause= "No matching min/max row";
700
 
        tables = 0;
701
 
        goto setup_subq_exit;
 
495
        error=0;
 
496
        return(0);
702
497
      }
703
498
      if (res > 1)
704
499
      {
708
503
      if (res < 0)
709
504
      {
710
505
        zero_result_cause= "No matching min/max row";
711
 
        tables = 0;
712
 
        goto setup_subq_exit;
 
506
        error=0;
 
507
        return(0);
713
508
      }
714
509
      zero_result_cause= "Select tables optimized away";
715
510
      tables_list= 0;       // All tables resolved
716
 
      const_tables= tables;
717
511
      /*
718
512
        Extract all table-independent conditions and replace the WHERE
719
 
        clause with them. All other conditions were computed by optimizer::sum_query
 
513
        clause with them. All other conditions were computed by opt_sum_query
720
514
        and the MIN/MAX/COUNT function(s) have been replaced by constants,
721
515
        so there is no need to compute the whole WHERE clause again.
722
516
        Notice that make_cond_for_table() will always succeed to remove all
723
 
        computed conditions, because optimizer::sum_query() is applicable only to
 
517
        computed conditions, because opt_sum_query() is applicable only to
724
518
        conjunctions.
725
519
        Preserve conditions for EXPLAIN.
726
520
      */
729
523
        COND *table_independent_conds= make_cond_for_table(conds, PSEUDO_TABLE_BITS, 0, 0);
730
524
        conds= table_independent_conds;
731
525
      }
732
 
      goto setup_subq_exit;
733
526
    }
734
527
  }
735
528
  if (!tables_list)
762
555
       select_lex->master_unit() == &session->lex->unit)) // upper level SELECT
763
556
  {
764
557
    zero_result_cause= "no matching row in const table";
765
 
    goto setup_subq_exit;
 
558
    error= 0;
 
559
    return(0);
766
560
  }
767
561
  if (!(session->options & OPTION_BIG_SELECTS) &&
768
562
      best_read > (double) session->variables.max_join_size &&
769
563
      !(select_options & SELECT_DESCRIBE))
770
 
  {
 
564
  {           /* purecov: inspected */
771
565
    my_message(ER_TOO_BIG_SELECT, ER(ER_TOO_BIG_SELECT), MYF(0));
772
566
    error= -1;
773
567
    return 1;
774
568
  }
775
569
  if (const_tables && !(select_options & SELECT_NO_UNLOCK))
776
 
    session->unlockSomeTables(table, const_tables);
 
570
    mysql_unlock_some_tables(session, table, const_tables);
777
571
  if (!conds && outer_join)
778
572
  {
779
573
    /* Handle the case where we have an OUTER JOIN without a WHERE */
780
574
    conds=new Item_int((int64_t) 1,1);  // Always true
781
575
  }
782
 
  select= optimizer::make_select(*table, const_table_map,
783
 
                                 const_table_map, conds, 1, &error);
 
576
  select= make_select(*table, const_table_map,
 
577
                      const_table_map, conds, 1, &error);
784
578
  if (error)
785
 
  {
786
 
    error= -1;
 
579
  {           /* purecov: inspected */
 
580
    error= -1;          /* purecov: inspected */
787
581
    return 1;
788
582
  }
789
583
 
823
617
  {
824
618
    conds=new Item_int((int64_t) 0,1);  // Always false
825
619
  }
826
 
 
827
620
  if (make_join_select(this, select, conds))
828
621
  {
829
622
    zero_result_cause=
830
623
      "Impossible WHERE noticed after reading const tables";
831
 
    goto setup_subq_exit;
 
624
    return(0);        // error == 0
832
625
  }
833
626
 
834
627
  error= -1;          /* if goto err */
835
628
 
836
629
  /* Optimize distinct away if possible */
837
630
  {
838
 
    Order *org_order= order;
 
631
    order_st *org_order= order;
839
632
    order= remove_constants(this, order,conds,1, &simple_order);
840
633
    if (session->is_error())
841
634
    {
844
637
    }
845
638
 
846
639
    /*
847
 
      If we are using ORDER BY NULL or ORDER BY const_expression,
 
640
      If we are using order_st BY NULL or order_st BY const_expression,
848
641
      return result in any order (even if we are using a GROUP BY)
849
642
    */
850
643
    if (!order && org_order)
863
656
     The FROM clause must contain a single non-constant table.
864
657
  */
865
658
  if (tables - const_tables == 1 && (group_list || select_distinct) &&
866
 
      ! tmp_table_param.sum_func_count &&
867
 
      (! join_tab[const_tables].select ||
868
 
       ! join_tab[const_tables].select->quick ||
 
659
      !tmp_table_param.sum_func_count &&
 
660
      (!join_tab[const_tables].select ||
 
661
       !join_tab[const_tables].select->quick ||
869
662
       join_tab[const_tables].select->quick->get_type() !=
870
 
       optimizer::QuickSelectInterface::QS_TYPE_GROUP_MIN_MAX))
 
663
       QUICK_SELECT_I::QS_TYPE_GROUP_MIN_MAX))
871
664
  {
872
665
    if (group_list && list_contains_unique_index(join_tab[const_tables].table, find_field_in_order_list, (void *) group_list))
873
666
    {
875
668
        We have found that grouping can be removed since groups correspond to
876
669
        only one row anyway, but we still have to guarantee correct result
877
670
        order. The line below effectively rewrites the query from GROUP BY
878
 
        <fields> to ORDER BY <fields>. There are two exceptions:
 
671
        <fields> to order_st BY <fields>. There are two exceptions:
879
672
        - if skip_sort_order is set (see above), then we can simply skip
880
673
          GROUP BY;
881
 
        - we can only rewrite ORDER BY if the ORDER BY fields are 'compatible'
 
674
        - we can only rewrite order_st BY if the order_st BY fields are 'compatible'
882
675
          with the GROUP BY ones, i.e. either one is a prefix of another.
883
 
          We only check if the ORDER BY is a prefix of GROUP BY. In this case
 
676
          We only check if the order_st BY is a prefix of GROUP BY. In this case
884
677
          test_if_subpart() copies the ASC/DESC attributes from the original
885
 
          ORDER BY fields.
 
678
          order_st BY fields.
886
679
          If GROUP BY is a prefix of order_st BY, then it is safe to leave
887
680
          'order' as is.
888
681
       */
889
 
      if (! order || test_if_subpart(group_list, order))
 
682
      if (!order || test_if_subpart(group_list, order))
890
683
          order= skip_sort_order ? 0 : group_list;
891
684
      /*
892
685
        If we have an IGNORE INDEX FOR GROUP BY(fields) clause, this must be
907
700
  }
908
701
  if (group_list || tmp_table_param.sum_func_count)
909
702
  {
910
 
    if (! hidden_group_fields && rollup.getState() == Rollup::STATE_NONE)
 
703
    if (! hidden_group_fields && rollup.state == ROLLUP::STATE_NONE)
911
704
      select_distinct=0;
912
705
  }
913
706
  else if (select_distinct && tables - const_tables == 1)
921
714
      - We are scanning the whole table without LIMIT
922
715
        This can happen if:
923
716
        - We are using CALC_FOUND_ROWS
924
 
        - We are using an ORDER BY that can't be optimized away.
 
717
        - We are using an order_st BY that can't be optimized away.
925
718
 
926
719
      We don't want to use this optimization when we are using LIMIT
927
720
      because in this case we can just create a temporary table that
953
746
          {
954
747
            /*
955
748
              Force MySQL to read the table in sorted order to get result in
956
 
              ORDER BY order.
 
749
              order_st BY order.
957
750
            */
958
751
            tmp_table_param.quick_group=0;
959
752
          }
969
762
  }
970
763
  simple_group= 0;
971
764
  {
972
 
    Order *old_group_list;
 
765
    order_st *old_group_list;
973
766
    group_list= remove_constants(this, (old_group_list= group_list), conds,
974
 
                                 rollup.getState() == Rollup::STATE_NONE,
 
767
                                 rollup.state == ROLLUP::STATE_NONE,
975
768
                                 &simple_group);
976
769
    if (session->is_error())
977
770
    {
1010
803
    This has to be done if all tables are not already read (const tables)
1011
804
    and one of the following conditions holds:
1012
805
    - We are using DISTINCT (simple distinct's are already optimized away)
1013
 
    - We are using an ORDER BY or GROUP BY on fields not in the first table
1014
 
    - We are using different ORDER BY and GROUP BY orders
 
806
    - We are using an order_st BY or GROUP BY on fields not in the first table
 
807
    - We are using different order_st BY and GROUP BY orders
1015
808
    - The user wants us to buffer the result.
1016
809
  */
1017
810
  need_tmp= (const_tables != tables &&
1019
812
        (group_list && order) ||
1020
813
        test(select_options & OPTION_BUFFER_RESULT)));
1021
814
 
 
815
  uint32_t no_jbuf_after= make_join_orderinfo(this);
 
816
  uint64_t select_opts_for_readinfo=
 
817
    (select_options & (SELECT_DESCRIBE | SELECT_NO_JOIN_CACHE)) | (0);
 
818
 
1022
819
  // No cache for MATCH == 'Don't use join buffering when we use MATCH'.
1023
 
  if (make_join_readinfo(this))
 
820
  if (make_join_readinfo(this, select_opts_for_readinfo, no_jbuf_after))
1024
821
    return 1;
1025
822
 
1026
823
  /* Create all structures needed for materialized subquery execution. */
1027
824
  if (setup_subquery_materialization())
1028
825
    return 1;
1029
826
 
1030
 
  /* Cache constant expressions in WHERE, HAVING, ON clauses. */
1031
 
  cache_const_exprs();
1032
 
 
1033
827
  /*
1034
828
    is this simple IN subquery?
1035
829
  */
1047
841
        save_index_subquery_explain_info(join_tab, where);
1048
842
        join_tab[0].type= AM_UNIQUE_SUBQUERY;
1049
843
        error= 0;
1050
 
        return(unit->item->change_engine(new subselect_uniquesubquery_engine(session, join_tab, unit->item, where)));
 
844
        return(unit->item->
 
845
                    change_engine(new
 
846
                                  subselect_uniquesubquery_engine(session,
 
847
                                                                  join_tab,
 
848
                                                                  unit->item,
 
849
                                                                  where)));
1051
850
      }
1052
851
      else if (join_tab[0].type == AM_REF &&
1053
852
         join_tab[0].ref.items[0]->name == in_left_expr_name)
1056
855
        save_index_subquery_explain_info(join_tab, where);
1057
856
        join_tab[0].type= AM_INDEX_SUBQUERY;
1058
857
        error= 0;
1059
 
        return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, where, NULL, 0)));
 
858
        return(unit->item->
 
859
                    change_engine(new
 
860
                                  subselect_indexsubquery_engine(session,
 
861
                                                                 join_tab,
 
862
                                                                 unit->item,
 
863
                                                                 where,
 
864
                                                                 NULL,
 
865
                                                                 0)));
1060
866
      }
1061
867
    } 
1062
868
    else if (join_tab[0].type == AM_REF_OR_NULL &&
1067
873
      error= 0;
1068
874
      conds= remove_additional_cond(conds);
1069
875
      save_index_subquery_explain_info(join_tab, conds);
1070
 
      return(unit->item->change_engine(new subselect_indexsubquery_engine(session, join_tab, unit->item, conds, having, 1)));
 
876
      return(unit->item->
 
877
      change_engine(new subselect_indexsubquery_engine(session,
 
878
                   join_tab,
 
879
                   unit->item,
 
880
                   conds,
 
881
                                                                   having,
 
882
                   1)));
1071
883
    }
1072
884
 
1073
885
  }
1119
931
        Force using of tmp table if sorting by a SP or UDF function due to
1120
932
        their expensive and probably non-deterministic nature.
1121
933
      */
1122
 
      for (Order *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
 
934
      for (order_st *tmp_order= order; tmp_order ; tmp_order=tmp_order->next)
1123
935
      {
1124
936
        Item *item= *tmp_order->item;
1125
937
        if (item->is_expensive())
1163
975
 
1164
976
    tmp_table_param.hidden_field_count= (all_fields.elements -
1165
977
           fields_list.elements);
1166
 
    Order *tmp_group= (((not simple_group) or not (getDebug().test(debug::NO_KEY_GROUP))) ? group_list : (Order*) 0);
1167
 
 
 
978
    order_st *tmp_group= ((!simple_group && 
 
979
                           ! (test_flags.test(TEST_NO_KEY_GROUP))) ? group_list :
 
980
                                                                     (order_st*) 0);
1168
981
    /*
1169
982
      Pushing LIMIT to the temporary table creation is not applicable
1170
 
      when there is ORDER BY or GROUP BY or there is no GROUP BY, but
 
983
      when there is order_st BY or GROUP BY or there is no GROUP BY, but
1171
984
      there are aggregate functions, because in all these cases we need
1172
985
      all result rows.
1173
986
    */
1267
1080
      If this join belongs to an uncacheable subquery save
1268
1081
      the original join
1269
1082
    */
1270
 
    if (select_lex->uncacheable.any() && 
1271
 
        ! is_top_level_join() &&
 
1083
    if (select_lex->uncacheable && !is_top_level_join() &&
1272
1084
        init_save_join_tab())
1273
 
    {
1274
 
      return -1;
1275
 
    }
 
1085
      return(-1);                         /* purecov: inspected */
1276
1086
  }
1277
1087
 
1278
1088
  error= 0;
1279
 
  return 0;
1280
 
 
1281
 
setup_subq_exit:
1282
 
  /* Even with zero matching rows, subqueries in the HAVING clause
1283
 
     may need to be evaluated if there are aggregate functions in the query.
1284
 
  */
1285
 
  if (setup_subquery_materialization())
1286
 
    return 1;
1287
 
  error= 0;
1288
 
  return 0;
 
1089
  return(0);
1289
1090
}
1290
1091
 
1291
1092
/**
1292
1093
  Restore values in temporary join.
1293
1094
*/
1294
 
void Join::restore_tmp()
 
1095
void JOIN::restore_tmp()
1295
1096
{
1296
 
  memcpy(tmp_join, this, (size_t) sizeof(Join));
 
1097
  memcpy(tmp_join, this, (size_t) sizeof(JOIN));
1297
1098
}
1298
1099
 
1299
 
int Join::reinit()
 
1100
int JOIN::reinit()
1300
1101
{
1301
1102
  unit->offset_limit_cnt= (ha_rows)(select_lex->offset_limit ?
1302
1103
                                    select_lex->offset_limit->val_uint() :
1306
1107
 
1307
1108
  if (exec_tmp_table1)
1308
1109
  {
1309
 
    exec_tmp_table1->cursor->extra(HA_EXTRA_RESET_STATE);
1310
 
    exec_tmp_table1->cursor->ha_delete_all_rows();
 
1110
    exec_tmp_table1->file->extra(HA_EXTRA_RESET_STATE);
 
1111
    exec_tmp_table1->file->ha_delete_all_rows();
1311
1112
    exec_tmp_table1->free_io_cache();
1312
1113
    exec_tmp_table1->filesort_free_buffers();
1313
1114
  }
1314
1115
  if (exec_tmp_table2)
1315
1116
  {
1316
 
    exec_tmp_table2->cursor->extra(HA_EXTRA_RESET_STATE);
1317
 
    exec_tmp_table2->cursor->ha_delete_all_rows();
 
1117
    exec_tmp_table2->file->extra(HA_EXTRA_RESET_STATE);
 
1118
    exec_tmp_table2->file->ha_delete_all_rows();
1318
1119
    exec_tmp_table2->free_io_cache();
1319
1120
    exec_tmp_table2->filesort_free_buffers();
1320
1121
  }
1348
1149
   @retval 0      success.
1349
1150
   @retval 1      error occurred.
1350
1151
*/
1351
 
bool Join::init_save_join_tab()
 
1152
bool JOIN::init_save_join_tab()
1352
1153
{
1353
 
  if (!(tmp_join= (Join*)session->getMemRoot()->allocate(sizeof(Join))))
1354
 
    return 1;
1355
 
 
 
1154
  if (!(tmp_join= (JOIN*)session->alloc(sizeof(JOIN))))
 
1155
    return 1;                                  /* purecov: inspected */
1356
1156
  error= 0;              // Ensure that tmp_join.error= 0
1357
1157
  restore_tmp();
1358
 
 
1359
1158
  return 0;
1360
1159
}
1361
1160
 
1362
 
bool Join::save_join_tab()
 
1161
bool JOIN::save_join_tab()
1363
1162
{
1364
 
  if (! join_tab_save && select_lex->master_unit()->uncacheable.any())
 
1163
  if (!join_tab_save && select_lex->master_unit()->uncacheable)
1365
1164
  {
1366
 
    if (!(join_tab_save= (JoinTable*)session->getMemRoot()->duplicate((unsigned char*) join_tab,
 
1165
    if (!(join_tab_save= (JoinTable*)session->memdup((unsigned char*) join_tab,
1367
1166
            sizeof(JoinTable) * tables)))
1368
1167
      return 1;
1369
1168
  }
1381
1180
  @todo
1382
1181
    When can we have here session->net.report_error not zero?
1383
1182
*/
1384
 
void Join::exec()
 
1183
void JOIN::exec()
1385
1184
{
1386
1185
  List<Item> *columns_list= &fields_list;
1387
1186
  int      tmp_error;
1393
1192
  {                                           
1394
1193
    /* Only test of functions */
1395
1194
    if (select_options & SELECT_DESCRIBE)
1396
 
    {
1397
 
      optimizer::ExplainPlan planner(this, 
1398
 
                                     false,
1399
 
                                     false,
1400
 
                                     false,
1401
 
                                     (zero_result_cause ? zero_result_cause : "No tables used"));
1402
 
      planner.printPlan();
1403
 
    }
 
1195
      select_describe(this, false, false, false, (zero_result_cause?zero_result_cause:"No tables used"));
1404
1196
    else
1405
1197
    {
1406
1198
      result->send_fields(*columns_list);
1451
1243
    return;
1452
1244
  }
1453
1245
 
 
1246
  if ((this->select_lex->options & OPTION_SCHEMA_TABLE) && get_schema_tables_result(this, PROCESSED_BY_JOIN_EXEC))
 
1247
    return;
 
1248
 
1454
1249
  if (select_options & SELECT_DESCRIBE)
1455
1250
  {
1456
1251
    /*
1457
 
      Check if we managed to optimize ORDER BY away and don't use temporary
 
1252
      Check if we managed to optimize order_st BY away and don't use temporary
1458
1253
      table to resolve order_st BY: in that case, we only may need to do
1459
1254
      filesort for GROUP BY.
1460
1255
    */
1473
1268
      order= 0;
1474
1269
    }
1475
1270
    having= tmp_having;
1476
 
    optimizer::ExplainPlan planner(this,
1477
 
                                   need_tmp,
1478
 
                                   order != 0 && ! skip_sort_order,
1479
 
                                   select_distinct,
1480
 
                                   ! tables ? "No tables used" : NULL);
1481
 
    planner.printPlan();
 
1271
    select_describe(this, need_tmp, order != 0 && !skip_sort_order,  select_distinct, !tables ? "No tables used" : NULL);
1482
1272
    return;
1483
1273
  }
1484
1274
 
1485
 
  Join *curr_join= this;
 
1275
  JOIN *curr_join= this;
1486
1276
  List<Item> *curr_all_fields= &all_fields;
1487
1277
  List<Item> *curr_fields_list= &fields_list;
1488
1278
  Table *curr_tmp_table= 0;
1517
1307
      error= tmp_error;
1518
1308
      return;
1519
1309
    }
1520
 
    curr_tmp_table->cursor->info(HA_STATUS_VARIABLE);
 
1310
    curr_tmp_table->file->info(HA_STATUS_VARIABLE);
1521
1311
 
1522
1312
    if (curr_join->having)
1523
1313
      curr_join->having= curr_join->tmp_having= 0; // Allready done
1592
1382
                                                   - curr_join->tmp_fields_list1.elements;
1593
1383
 
1594
1384
      if (exec_tmp_table2)
1595
 
      {
1596
1385
        curr_tmp_table= exec_tmp_table2;
1597
 
      }
1598
1386
      else
1599
1387
      {
1600
1388
        /* group data to new table */
1602
1390
        /*
1603
1391
          If the access method is loose index scan then all MIN/MAX
1604
1392
          functions are precomputed, and should be treated as regular
1605
 
          functions. See extended comment in Join::exec.
 
1393
          functions. See extended comment in JOIN::exec.
1606
1394
        */
1607
1395
        if (curr_join->join_tab->is_using_loose_index_scan())
1608
1396
          curr_join->tmp_table_param.precomputed_group_by= true;
1611
1399
              exec_tmp_table2= create_tmp_table(session,
1612
1400
                                                &curr_join->tmp_table_param,
1613
1401
                                                *curr_all_fields,
1614
 
                                                (Order*) 0,
 
1402
                                                (order_st*) 0,
1615
1403
                                                curr_join->select_distinct &&
1616
1404
                                                !curr_join->group_list,
1617
1405
                                                1, curr_join->select_options,
1618
1406
                                                HA_POS_ERROR,
1619
1407
                                                (char *) "")))
1620
 
        {
1621
1408
          return;
1622
 
        }
1623
 
 
1624
1409
        curr_join->exec_tmp_table2= exec_tmp_table2;
1625
1410
      }
1626
1411
      if (curr_join->group_list)
1668
1453
        error= tmp_error;
1669
1454
        return;
1670
1455
      }
1671
 
      curr_join->join_tab->read_record.end_read_record();
 
1456
      end_read_record(&curr_join->join_tab->read_record);
1672
1457
      curr_join->const_tables= curr_join->tables; // Mark free for cleanup()
1673
1458
      curr_join->join_tab[0].table= 0;           // Table is freed
1674
1459
 
1765
1550
      if (sort_table_cond)
1766
1551
      {
1767
1552
        if (!curr_table->select)
1768
 
          if (!(curr_table->select= new optimizer::SqlSelect()))
 
1553
          if (!(curr_table->select= new SQL_SELECT))
1769
1554
            return;
1770
1555
        if (!curr_table->select->cond)
1771
1556
          curr_table->select->cond= sort_table_cond;
1879
1664
  Clean up join.
1880
1665
 
1881
1666
  @return
1882
 
    Return error that hold Join.
 
1667
    Return error that hold JOIN.
1883
1668
*/
1884
 
int Join::destroy()
 
1669
int JOIN::destroy()
1885
1670
{
1886
1671
  select_lex->join= 0;
1887
1672
 
1900
1685
  cond_equal= 0;
1901
1686
 
1902
1687
  cleanup(1);
1903
 
  exec_tmp_table1= NULL;
1904
 
  exec_tmp_table2= NULL;
 
1688
  if (exec_tmp_table1)
 
1689
    exec_tmp_table1->free_tmp_table(session);
 
1690
  if (exec_tmp_table2)
 
1691
    exec_tmp_table2->free_tmp_table(session);
1905
1692
  delete select;
1906
1693
  delete_dynamic(&keyuse);
1907
 
 
1908
1694
  return(error);
1909
1695
}
1910
1696
 
1917
1703
  - try to initialize all data structures needed for the materialized execution
1918
1704
    of the IN predicate,
1919
1705
  - if this fails, then perform the IN=>EXISTS transformation which was
1920
 
    previously blocked during Join::prepare.
 
1706
    previously blocked during JOIN::prepare.
1921
1707
 
1922
1708
  This method is part of the "code generation" query processing phase.
1923
1709
 
1930
1716
  @retval false     success.
1931
1717
  @retval true      error occurred.
1932
1718
*/
1933
 
bool Join::setup_subquery_materialization()
 
1719
bool JOIN::setup_subquery_materialization()
1934
1720
{
1935
1721
  for (Select_Lex_Unit *un= select_lex->first_inner_unit(); un;
1936
1722
       un= un->next_unit())
1952
1738
}
1953
1739
 
1954
1740
/**
1955
 
  Partially cleanup Join after it has executed: close index or rnd read
 
1741
  Partially cleanup JOIN after it has executed: close index or rnd read
1956
1742
  (table cursors), free quick selects.
1957
1743
 
1958
 
    This function is called in the end of execution of a Join, before the used
 
1744
    This function is called in the end of execution of a JOIN, before the used
1959
1745
    tables are unlocked and closed.
1960
1746
 
1961
1747
    For a join that is resolved using a temporary table, the first sweep is
1969
1755
    is called after all rows are sent, but before EOF packet is sent.
1970
1756
 
1971
1757
    For a simple SELECT with no subqueries this function performs a full
1972
 
    cleanup of the Join and calls unlockReadTables to free used base
 
1758
    cleanup of the JOIN and calls mysql_unlock_read_tables to free used base
1973
1759
    tables.
1974
1760
 
1975
 
    If a Join is executed for a subquery or if it has a subquery, we can't
 
1761
    If a JOIN is executed for a subquery or if it has a subquery, we can't
1976
1762
    do the full cleanup and need to do a partial cleanup only.
1977
 
    - If a Join is not the top level join, we must not unlock the tables
 
1763
    - If a JOIN is not the top level join, we must not unlock the tables
1978
1764
    because the outer select may not have been evaluated yet, and we
1979
1765
    can't unlock only selected tables of a query.
1980
 
    - Additionally, if this Join corresponds to a correlated subquery, we
 
1766
    - Additionally, if this JOIN corresponds to a correlated subquery, we
1981
1767
    should not free quick selects and join buffers because they will be
1982
1768
    needed for the next execution of the correlated subquery.
1983
 
    - However, if this is a Join for a [sub]select, which is not
 
1769
    - However, if this is a JOIN for a [sub]select, which is not
1984
1770
    a correlated subquery itself, but has subqueries, we can free it
1985
 
    fully and also free Joins of all its subqueries. The exception
 
1771
    fully and also free JOINs of all its subqueries. The exception
1986
1772
    is a subquery in SELECT list, e.g: @n
1987
1773
    SELECT a, (select cmax(b) from t1) group by c @n
1988
1774
    This subquery will not be evaluated at first sweep and its value will
1993
1779
  @todo
1994
1780
    Unlock tables even if the join isn't top level select in the tree
1995
1781
*/
1996
 
void Join::join_free()
 
1782
void JOIN::join_free()
1997
1783
{
1998
1784
  Select_Lex_Unit *tmp_unit;
1999
1785
  Select_Lex *sl;
2000
1786
  /*
2001
 
    Optimization: if not EXPLAIN and we are done with the Join,
 
1787
    Optimization: if not EXPLAIN and we are done with the JOIN,
2002
1788
    free all tables.
2003
1789
  */
2004
 
  bool full= (select_lex->uncacheable.none() && ! session->lex->describe);
 
1790
  bool full= (!select_lex->uncacheable && !session->lex->describe);
2005
1791
  bool can_unlock= full;
2006
1792
 
2007
1793
  cleanup(full);
2012
1798
    for (sl= tmp_unit->first_select(); sl; sl= sl->next_select())
2013
1799
    {
2014
1800
      Item_subselect *subselect= sl->master_unit()->item;
2015
 
      bool full_local= full && (!subselect || 
2016
 
                                (subselect->is_evaluated() &&
2017
 
                                !subselect->is_uncacheable()));
 
1801
      bool full_local= full && (!subselect || subselect->is_evaluated());
2018
1802
      /*
2019
1803
        If this join is evaluated, we can fully clean it up and clean up all
2020
1804
        its underlying joins even if they are correlated -- they will not be
2025
1809
        but all table cursors must be closed before the unlock.
2026
1810
      */
2027
1811
      sl->cleanup_all_joins(full_local);
2028
 
      /* Can't unlock if at least one Join is still needed */
 
1812
      /* Can't unlock if at least one JOIN is still needed */
2029
1813
      can_unlock= can_unlock && full_local;
2030
1814
    }
2031
1815
 
2043
1827
      TODO: unlock tables even if the join isn't top level select in the
2044
1828
      tree.
2045
1829
    */
2046
 
    session->unlockReadTables(lock);           // Don't free join->lock
 
1830
    mysql_unlock_read_tables(session, lock);           // Don't free join->lock
2047
1831
    lock= 0;
2048
1832
  }
2049
1833
 
2062
1846
    With subquery this function definitely will be called several times,
2063
1847
    but even for simple query it can be called several times.
2064
1848
*/
2065
 
void Join::cleanup(bool full)
 
1849
void JOIN::cleanup(bool full)
2066
1850
{
2067
1851
  if (table)
2068
1852
  {
 
1853
    JoinTable *tab,*end;
2069
1854
    /*
2070
1855
      Only a sorted table may be cached.  This sorted table is always the
2071
1856
      first non const table in join->table
2075
1860
      table[const_tables]->free_io_cache();
2076
1861
      table[const_tables]->filesort_free_buffers(full);
2077
1862
    }
2078
 
  }
2079
 
 
2080
 
  if (join_tab)
2081
 
  {
2082
 
    JoinTable *tab,*end;
2083
1863
 
2084
1864
    if (full)
2085
1865
    {
2092
1872
      for (tab= join_tab, end= tab+tables; tab != end; tab++)
2093
1873
      {
2094
1874
        if (tab->table)
2095
 
          tab->table->cursor->ha_index_or_rnd_end();
 
1875
          tab->table->file->ha_index_or_rnd_end();
2096
1876
      }
2097
1877
    }
2098
1878
  }
2099
 
 
2100
1879
  /*
2101
1880
    We are not using tables anymore
2102
1881
    Unlock all tables. We may be in an INSERT .... SELECT statement.
2112
1891
    */
2113
1892
    tmp_table_param.copy_funcs.empty();
2114
1893
    /*
2115
 
      If we have tmp_join and 'this' Join is not tmp_join and
 
1894
      If we have tmp_join and 'this' JOIN is not tmp_join and
2116
1895
      tmp_table_param.copy_field's  of them are equal then we have to remove
2117
1896
      pointer to  tmp_table_param.copy_field from tmp_join, because it qill
2118
1897
      be removed in tmp_table_param.cleanup().
2131
1910
}
2132
1911
 
2133
1912
/*
2134
 
  used only in Join::clear
 
1913
  used only in JOIN::clear
2135
1914
*/
2136
 
static void clear_tables(Join *join)
 
1915
static void clear_tables(JOIN *join)
2137
1916
{
2138
1917
  /*
2139
1918
    must clear only the non-const tables, as const tables
2140
1919
    are not re-calculated.
2141
1920
  */
2142
1921
  for (uint32_t i= join->const_tables; i < join->tables; i++)
2143
 
  {
2144
1922
    join->table[i]->mark_as_null_row();   // All fields are NULL
2145
 
  }
2146
1923
}
2147
1924
 
2148
1925
/**
2154
1931
  @retval
2155
1932
    1 Error
2156
1933
*/
2157
 
bool Join::alloc_func_list()
 
1934
bool JOIN::alloc_func_list()
2158
1935
{
2159
1936
  uint32_t func_count, group_parts;
2160
1937
 
2163
1940
    If we are using rollup, we need a copy of the summary functions for
2164
1941
    each level
2165
1942
  */
2166
 
  if (rollup.getState() != Rollup::STATE_NONE)
 
1943
  if (rollup.state != ROLLUP::STATE_NONE)
2167
1944
    func_count*= (send_group_parts+1);
2168
1945
 
2169
1946
  group_parts= send_group_parts;
2180
1957
    */
2181
1958
    if (order)
2182
1959
    {
2183
 
      Order *ord;
 
1960
      order_st *ord;
2184
1961
      for (ord= order; ord; ord= ord->next)
2185
1962
        group_parts++;
2186
1963
    }
2206
1983
  @retval
2207
1984
    1  error
2208
1985
*/
2209
 
bool Join::make_sum_func_list(List<Item> &field_list, 
 
1986
bool JOIN::make_sum_func_list(List<Item> &field_list, 
2210
1987
                              List<Item> &send_fields,
2211
1988
                              bool before_group_by, 
2212
1989
                              bool recompute)
2226
2003
         ((Item_sum *)item)->depended_from() == select_lex))
2227
2004
      *func++= (Item_sum*) item;
2228
2005
  }
2229
 
  if (before_group_by && rollup.getState() == Rollup::STATE_INITED)
 
2006
  if (before_group_by && rollup.state == ROLLUP::STATE_INITED)
2230
2007
  {
2231
 
    rollup.setState(Rollup::STATE_READY);
 
2008
    rollup.state= ROLLUP::STATE_READY;
2232
2009
    if (rollup_make_fields(field_list, send_fields, &func))
2233
 
      return true;     // Should never happen
 
2010
      return(true);     // Should never happen
2234
2011
  }
2235
 
  else if (rollup.getState() == Rollup::STATE_NONE)
 
2012
  else if (rollup.state == ROLLUP::STATE_NONE)
2236
2013
  {
2237
2014
    for (uint32_t i=0 ; i <= send_group_parts ;i++)
2238
2015
      sum_funcs_end[i]= func;
2239
2016
  }
2240
 
  else if (rollup.getState() == Rollup::STATE_READY)
 
2017
  else if (rollup.state == ROLLUP::STATE_READY)
2241
2018
    return(false);                         // Don't put end marker
2242
2019
  *func=0;          // End marker
2243
2020
  return(false);
2244
2021
}
2245
2022
 
2246
2023
/** Allocate memory needed for other rollup functions. */
2247
 
bool Join::rollup_init()
 
2024
bool JOIN::rollup_init()
2248
2025
{
 
2026
  uint32_t i,j;
2249
2027
  Item **ref_array;
2250
2028
 
2251
2029
  tmp_table_param.quick_group= 0; // Can't create groups in tmp table
2252
 
  rollup.setState(Rollup::STATE_INITED);
 
2030
  rollup.state= ROLLUP::STATE_INITED;
2253
2031
 
2254
2032
  /*
2255
2033
    Create pointers to the different sum function groups
2257
2035
  */
2258
2036
  tmp_table_param.group_parts= send_group_parts;
2259
2037
 
2260
 
  rollup.setNullItems((Item_null_result**) session->getMemRoot()->allocate((sizeof(Item*) +
2261
 
                                                                sizeof(Item**) +
2262
 
                                                                sizeof(List<Item>) +
2263
 
                                                                ref_pointer_array_size)
2264
 
                                                               * send_group_parts ));
2265
 
  if (! rollup.getNullItems())
2266
 
  {
 
2038
  if (!(rollup.null_items= (Item_null_result**) session->alloc((sizeof(Item*) +
 
2039
                                                sizeof(Item**) +
 
2040
                                                sizeof(List<Item>) +
 
2041
                        ref_pointer_array_size)
 
2042
                        * send_group_parts )))
2267
2043
    return 1;
2268
 
  }
2269
2044
 
2270
 
  rollup.setFields((List<Item>*) (rollup.getNullItems() + send_group_parts));
2271
 
  rollup.setRefPointerArrays((Item***) (rollup.getFields() + send_group_parts));
2272
 
  ref_array= (Item**) (rollup.getRefPointerArrays()+send_group_parts);
 
2045
  rollup.fields= (List<Item>*) (rollup.null_items + send_group_parts);
 
2046
  rollup.ref_pointer_arrays= (Item***) (rollup.fields + send_group_parts);
 
2047
  ref_array= (Item**) (rollup.ref_pointer_arrays+send_group_parts);
2273
2048
 
2274
2049
  /*
2275
2050
    Prepare space for field list for the different levels
2276
2051
    These will be filled up in rollup_make_fields()
2277
2052
  */
2278
 
  for (uint32_t i= 0 ; i < send_group_parts ; i++)
 
2053
  for (i= 0 ; i < send_group_parts ; i++)
2279
2054
  {
2280
 
    rollup.getNullItems()[i]= new (session->mem_root) Item_null_result();
2281
 
    List<Item> *rollup_fields= &rollup.getFields()[i];
 
2055
    rollup.null_items[i]= new (session->mem_root) Item_null_result();
 
2056
    List<Item> *rollup_fields= &rollup.fields[i];
2282
2057
    rollup_fields->empty();
2283
 
    rollup.getRefPointerArrays()[i]= ref_array;
 
2058
    rollup.ref_pointer_arrays[i]= ref_array;
2284
2059
    ref_array+= all_fields.elements;
2285
2060
  }
2286
 
 
2287
 
  for (uint32_t i= 0 ; i < send_group_parts; i++)
 
2061
  for (i= 0 ; i < send_group_parts; i++)
2288
2062
  {
2289
 
    for (uint32_t j= 0 ; j < fields_list.elements ; j++)
2290
 
    {
2291
 
      rollup.getFields()[i].push_back(rollup.getNullItems()[i]);
2292
 
    }
 
2063
    for (j=0 ; j < fields_list.elements ; j++)
 
2064
      rollup.fields[i].push_back(rollup.null_items[i]);
2293
2065
  }
2294
 
 
2295
2066
  List_iterator<Item> it(all_fields);
2296
2067
  Item *item;
2297
2068
  while ((item= it++))
2298
2069
  {
2299
 
    Order *group_tmp;
 
2070
    order_st *group_tmp;
2300
2071
    bool found_in_group= 0;
2301
2072
 
2302
2073
    for (group_tmp= group_list; group_tmp; group_tmp= group_tmp->next)
2325
2096
            return 1;
2326
2097
          new_item->fix_fields(session, (Item **) 0);
2327
2098
          session->change_item_tree(it.ref(), new_item);
2328
 
          for (Order *tmp= group_tmp; tmp; tmp= tmp->next)
 
2099
          for (order_st *tmp= group_tmp; tmp; tmp= tmp->next)
2329
2100
          {
2330
2101
            if (*tmp->item == item)
2331
2102
              session->change_item_tree(tmp->item, new_item);
2365
2136
  @retval
2366
2137
    1    on error
2367
2138
*/
2368
 
bool Join::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
 
2139
bool JOIN::rollup_make_fields(List<Item> &fields_arg, List<Item> &sel_fields, Item_sum ***func)
2369
2140
{
2370
2141
  List_iterator_fast<Item> it(fields_arg);
2371
2142
  Item *first_field= sel_fields.head();
2398
2169
    uint32_t pos= send_group_parts - level -1;
2399
2170
    bool real_fields= 0;
2400
2171
    Item *item;
2401
 
    List_iterator<Item> new_it(rollup.getFields()[pos]);
2402
 
    Item **ref_array_start= rollup.getRefPointerArrays()[pos];
2403
 
    Order *start_group;
 
2172
    List_iterator<Item> new_it(rollup.fields[pos]);
 
2173
    Item **ref_array_start= rollup.ref_pointer_arrays[pos];
 
2174
    order_st *start_group;
2404
2175
 
2405
2176
    /* Point to first hidden field */
2406
2177
    Item **ref_array= ref_array_start + fields_arg.elements-1;
2442
2213
      else
2443
2214
      {
2444
2215
        /* Check if this is something that is part of this group by */
2445
 
        Order *group_tmp;
 
2216
        order_st *group_tmp;
2446
2217
        for (group_tmp= start_group, i= pos ;
2447
2218
                  group_tmp ; group_tmp= group_tmp->next, i++)
2448
2219
        {
2495
2266
  @retval
2496
2267
    1   If send_data_failed()
2497
2268
*/
2498
 
int Join::rollup_send_data(uint32_t idx)
 
2269
int JOIN::rollup_send_data(uint32_t idx)
2499
2270
{
2500
 
  for (uint32_t i= send_group_parts ; i-- > idx ; )
 
2271
  uint32_t i;
 
2272
  for (i= send_group_parts ; i-- > idx ; )
2501
2273
  {
2502
2274
    /* Get reference pointers to sum functions in place */
2503
 
    memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i], ref_pointer_array_size);
2504
 
 
 
2275
    memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
 
2276
     ref_pointer_array_size);
2505
2277
    if ((!having || having->val_int()))
2506
2278
    {
2507
 
      if (send_records < unit->select_limit_cnt && do_send_rows && result->send_data(rollup.getFields()[i]))
2508
 
      {
2509
 
        return 1;
2510
 
      }
 
2279
      if (send_records < unit->select_limit_cnt && do_send_rows &&
 
2280
    result->send_data(rollup.fields[i]))
 
2281
  return 1;
2511
2282
      send_records++;
2512
2283
    }
2513
2284
  }
2514
2285
  /* Restore ref_pointer_array */
2515
2286
  set_items_ref_array(current_ref_pointer_array);
2516
 
 
2517
2287
  return 0;
2518
2288
}
2519
2289
 
2536
2306
  @retval
2537
2307
    1   if write_data_failed()
2538
2308
*/
2539
 
int Join::rollup_write_data(uint32_t idx, Table *table_arg)
 
2309
int JOIN::rollup_write_data(uint32_t idx, Table *table_arg)
2540
2310
{
2541
 
  for (uint32_t i= send_group_parts ; i-- > idx ; )
 
2311
  uint32_t i;
 
2312
  for (i= send_group_parts ; i-- > idx ; )
2542
2313
  {
2543
2314
    /* Get reference pointers to sum functions in place */
2544
 
    memcpy(ref_pointer_array, rollup.getRefPointerArrays()[i],
2545
 
           ref_pointer_array_size);
 
2315
    memcpy(ref_pointer_array, rollup.ref_pointer_arrays[i],
 
2316
     ref_pointer_array_size);
2546
2317
    if ((!having || having->val_int()))
2547
2318
    {
2548
2319
      int write_error;
2549
2320
      Item *item;
2550
 
      List_iterator_fast<Item> it(rollup.getFields()[i]);
 
2321
      List_iterator_fast<Item> it(rollup.fields[i]);
2551
2322
      while ((item= it++))
2552
2323
      {
2553
2324
        if (item->type() == Item::NULL_ITEM && item->is_result_field())
2554
2325
          item->save_in_result_field(1);
2555
2326
      }
2556
2327
      copy_sum_funcs(sum_funcs_end[i+1], sum_funcs_end[i]);
2557
 
      if ((write_error= table_arg->cursor->insertRecord(table_arg->getInsertRecord())))
 
2328
      if ((write_error= table_arg->file->ha_write_row(table_arg->record[0])))
2558
2329
      {
2559
 
        my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
2560
 
        return 1;
 
2330
  if (create_myisam_from_heap(session, table_arg,
 
2331
                                    tmp_table_param.start_recinfo,
 
2332
                                    &tmp_table_param.recinfo,
 
2333
                                    write_error, 0))
 
2334
    return 1;
2561
2335
      }
2562
2336
    }
2563
2337
  }
2564
2338
  /* Restore ref_pointer_array */
2565
2339
  set_items_ref_array(current_ref_pointer_array);
2566
 
 
2567
2340
  return 0;
2568
2341
}
2569
2342
 
2571
2344
  clear results if there are not rows found for group
2572
2345
  (end_send_group/end_write_group)
2573
2346
*/
2574
 
void Join::clear()
 
2347
void JOIN::clear()
2575
2348
{
2576
2349
  clear_tables(this);
2577
2350
  copy_fields(&tmp_table_param);
2585
2358
}
2586
2359
 
2587
2360
/**
2588
 
  change select_result object of Join.
 
2361
  change select_result object of JOIN.
2589
2362
 
2590
2363
  @param res    new select_result object
2591
2364
 
2594
2367
  @retval
2595
2368
    true    error
2596
2369
*/
2597
 
bool Join::change_result(select_result *res)
 
2370
bool JOIN::change_result(select_result *res)
2598
2371
{
2599
2372
  result= res;
2600
2373
  if (result->prepare(fields_list, select_lex->master_unit()))
2605
2378
}
2606
2379
 
2607
2380
/**
2608
 
  Cache constant expressions in WHERE, HAVING, ON conditions.
2609
 
*/
2610
 
 
2611
 
void Join::cache_const_exprs()
2612
 
{
2613
 
  bool cache_flag= false;
2614
 
  bool *analyzer_arg= &cache_flag;
2615
 
 
2616
 
  /* No need in cache if all tables are constant. */
2617
 
  if (const_tables == tables)
2618
 
    return;
2619
 
 
2620
 
  if (conds)
2621
 
    conds->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2622
 
                  &Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2623
 
  cache_flag= false;
2624
 
  if (having)
2625
 
    having->compile(&Item::cache_const_expr_analyzer, (unsigned char **)&analyzer_arg,
2626
 
                    &Item::cache_const_expr_transformer, (unsigned char *)&cache_flag);
2627
 
 
2628
 
  for (JoinTable *tab= join_tab + const_tables; tab < join_tab + tables ; tab++)
2629
 
  {
2630
 
    if (*tab->on_expr_ref)
2631
 
    {
2632
 
      cache_flag= false;
2633
 
      (*tab->on_expr_ref)->compile(&Item::cache_const_expr_analyzer,
2634
 
                                 (unsigned char **)&analyzer_arg,
2635
 
                                 &Item::cache_const_expr_transformer,
2636
 
                                 (unsigned char *)&cache_flag);
2637
 
    }
2638
 
  }
2639
 
}
2640
 
 
2641
 
/**
2642
2381
  @brief
2643
2382
  
2644
2383
  Process one record of the nested loop join.
2649
2388
  applicable to the partial record on hand and in case of success
2650
2389
  submit this record to the next level of the nested loop.
2651
2390
*/
2652
 
enum_nested_loop_state evaluate_join_record(Join *join, JoinTable *join_tab, int error)
 
2391
enum_nested_loop_state evaluate_join_record(JOIN *join, JoinTable *join_tab, int error)
2653
2392
{
2654
2393
  bool not_used_in_distinct= join_tab->not_used_in_distinct;
2655
2394
  ha_rows found_records= join->found_records;
2659
2398
    return NESTED_LOOP_ERROR;
2660
2399
  if (error < 0)
2661
2400
    return NESTED_LOOP_NO_MORE_ROWS;
2662
 
  if (join->session->getKilled())                       // Aborted by user
 
2401
  if (join->session->killed)                    // Aborted by user
2663
2402
  {
2664
2403
    join->session->send_kill_message();
2665
 
    return NESTED_LOOP_KILLED;
 
2404
    return NESTED_LOOP_KILLED;               /* purecov: inspected */
2666
2405
  }
2667
2406
  if (!select_cond || select_cond->val_int())
2668
2407
  {
2752
2491
        return NESTED_LOOP_NO_MORE_ROWS;
2753
2492
    }
2754
2493
    else
2755
 
      join_tab->read_record.cursor->unlock_row();
 
2494
      join_tab->read_record.file->unlock_row();
2756
2495
  }
2757
2496
  else
2758
2497
  {
2762
2501
    */
2763
2502
    join->examined_rows++;
2764
2503
    join->session->row_count++;
2765
 
    join_tab->read_record.cursor->unlock_row();
 
2504
    join_tab->read_record.file->unlock_row();
2766
2505
  }
2767
2506
  return NESTED_LOOP_OK;
2768
2507
}
2773
2512
    level of the nested loop. This function is used in case we have
2774
2513
    an OUTER join and no matching record was found.
2775
2514
*/
2776
 
enum_nested_loop_state evaluate_null_complemented_join_record(Join *join, JoinTable *join_tab)
 
2515
enum_nested_loop_state evaluate_null_complemented_join_record(JOIN *join, JoinTable *join_tab)
2777
2516
{
2778
2517
  /*
2779
2518
    The table join_tab is the first inner table of a outer join operation
2829
2568
  return (*join_tab->next_select)(join, join_tab+1, 0);
2830
2569
}
2831
2570
 
2832
 
enum_nested_loop_state flush_cached_records(Join *join, JoinTable *join_tab, bool skip_last)
 
2571
enum_nested_loop_state flush_cached_records(JOIN *join, JoinTable *join_tab, bool skip_last)
2833
2572
{
2834
2573
  enum_nested_loop_state rc= NESTED_LOOP_OK;
2835
2574
  int error;
2836
 
  ReadRecord *info;
 
2575
  READ_RECORD *info;
2837
2576
 
2838
2577
  join_tab->table->null_row= 0;
2839
2578
  if (!join_tab->cache.records)
2840
 
  {
2841
2579
    return NESTED_LOOP_OK;                      /* Nothing to do */
2842
 
  }
2843
 
 
2844
2580
  if (skip_last)
2845
 
  {
2846
 
    (void) join_tab->cache.store_record_in_cache(); // Must save this for later
2847
 
  }
2848
 
 
2849
 
 
 
2581
    (void) store_record_in_cache(&join_tab->cache); // Must save this for later
2850
2582
  if (join_tab->use_quick == 2)
2851
2583
  {
2852
2584
    if (join_tab->select->quick)
2858
2590
  /* read through all records */
2859
2591
  if ((error=join_init_read_record(join_tab)))
2860
2592
  {
2861
 
    join_tab->cache.reset_cache_write();
 
2593
    reset_cache_write(&join_tab->cache);
2862
2594
    return error < 0 ? NESTED_LOOP_NO_MORE_ROWS: NESTED_LOOP_ERROR;
2863
2595
  }
2864
2596
 
2871
2603
  info= &join_tab->read_record;
2872
2604
  do
2873
2605
  {
2874
 
    if (join->session->getKilled())
 
2606
    if (join->session->killed)
2875
2607
    {
2876
2608
      join->session->send_kill_message();
2877
 
      return NESTED_LOOP_KILLED;
 
2609
      return NESTED_LOOP_KILLED; // Aborted by user /* purecov: inspected */
2878
2610
    }
2879
 
    optimizer::SqlSelect *select= join_tab->select;
 
2611
    SQL_SELECT *select=join_tab->select;
2880
2612
    if (rc == NESTED_LOOP_OK &&
2881
2613
        (!join_tab->cache.select || !join_tab->cache.select->skip_record()))
2882
2614
    {
2883
2615
      uint32_t i;
2884
 
      join_tab->cache.reset_cache_read();
 
2616
      reset_cache_read(&join_tab->cache);
2885
2617
      for (i=(join_tab->cache.records- (skip_last ? 1 : 0)) ; i-- > 0 ;)
2886
2618
      {
2887
2619
              join_tab->readCachedRecord();
2892
2624
          rc= (join_tab->next_select)(join,join_tab+1,0);
2893
2625
          if (rc != NESTED_LOOP_OK && rc != NESTED_LOOP_NO_MORE_ROWS)
2894
2626
          {
2895
 
            join_tab->cache.reset_cache_write();
 
2627
            reset_cache_write(&join_tab->cache);
2896
2628
            return rc;
2897
2629
          }
2898
2630
 
2905
2637
 
2906
2638
  if (skip_last)
2907
2639
    join_tab->readCachedRecord();               // Restore current record
2908
 
  join_tab->cache.reset_cache_write();
 
2640
  reset_cache_write(&join_tab->cache);
2909
2641
  if (error > 0)                                // Fatal error
2910
 
    return NESTED_LOOP_ERROR;
 
2642
    return NESTED_LOOP_ERROR;                   /* purecov: inspected */
2911
2643
  for (JoinTable *tmp2=join->join_tab; tmp2 != join_tab ; tmp2++)
2912
2644
    tmp2->table->status=tmp2->status;
2913
2645
  return NESTED_LOOP_OK;
2937
2669
                               operation.
2938
2670
   All return values except NESTED_LOOP_OK abort the nested loop.
2939
2671
*****************************************************************************/
2940
 
enum_nested_loop_state end_send(Join *join, JoinTable *, bool end_of_records)
 
2672
enum_nested_loop_state end_send(JOIN *join, JoinTable *, bool end_of_records)
2941
2673
{
2942
2674
  if (! end_of_records)
2943
2675
  {
2948
2680
    if (join->do_send_rows)
2949
2681
      error=join->result->send_data(*join->fields);
2950
2682
    if (error)
2951
 
      return NESTED_LOOP_ERROR;
 
2683
      return NESTED_LOOP_ERROR; /* purecov: inspected */
2952
2684
    if (++join->send_records >= join->unit->select_limit_cnt && join->do_send_rows)
2953
2685
    {
2954
2686
      if (join->select_options & OPTION_FOUND_ROWS)
2957
2689
        if ((join->tables == 1) && !join->tmp_table && !join->sort_and_group
2958
2690
            && !join->send_group_parts && !join->having && !jt->select_cond &&
2959
2691
            !(jt->select && jt->select->quick) &&
2960
 
            (jt->table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
 
2692
            (jt->table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
2961
2693
                  (jt->ref.key < 0))
2962
2694
        {
2963
2695
          /* Join over all rows in table;  Return number of found rows */
2972
2704
          }
2973
2705
          else
2974
2706
          {
2975
 
            table->cursor->info(HA_STATUS_VARIABLE);
2976
 
            join->send_records= table->cursor->stats.records;
 
2707
            table->file->info(HA_STATUS_VARIABLE);
 
2708
            join->send_records= table->file->stats.records;
2977
2709
          }
2978
2710
        }
2979
2711
        else
2999
2731
  return NESTED_LOOP_OK;
3000
2732
}
3001
2733
 
3002
 
enum_nested_loop_state end_write(Join *join, JoinTable *, bool end_of_records)
 
2734
enum_nested_loop_state end_write(JOIN *join, JoinTable *, bool end_of_records)
3003
2735
{
3004
2736
  Table *table= join->tmp_table;
3005
2737
 
3006
 
  if (join->session->getKilled())                       // Aborted by user
 
2738
  if (join->session->killed)                    // Aborted by user
3007
2739
  {
3008
2740
    join->session->send_kill_message();
3009
 
    return NESTED_LOOP_KILLED;
 
2741
    return NESTED_LOOP_KILLED;             /* purecov: inspected */
3010
2742
  }
3011
2743
  if (!end_of_records)
3012
2744
  {
3013
2745
    copy_fields(&join->tmp_table_param);
3014
 
    if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3015
 
      return NESTED_LOOP_ERROR;
 
2746
    copy_funcs(join->tmp_table_param.items_to_copy);
3016
2747
    if (!join->having || join->having->val_int())
3017
2748
    {
3018
2749
      int error;
3019
2750
      join->found_records++;
3020
 
      if ((error=table->cursor->insertRecord(table->getInsertRecord())))
 
2751
      if ((error=table->file->ha_write_row(table->record[0])))
3021
2752
      {
3022
 
        if (!table->cursor->is_fatal_error(error, HA_CHECK_DUP))
3023
 
        {
3024
 
          return NESTED_LOOP_OK;
3025
 
        }
3026
 
 
3027
 
        my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
3028
 
        return NESTED_LOOP_ERROR;        // Table is_full error
 
2753
        if (!table->file->is_fatal_error(error, HA_CHECK_DUP))
 
2754
          goto end;
 
2755
        if (create_myisam_from_heap(join->session, table,
 
2756
                                          join->tmp_table_param.start_recinfo,
 
2757
                                          &join->tmp_table_param.recinfo,
 
2758
                  error, 1))
 
2759
          return NESTED_LOOP_ERROR;        // Not a table_is_full error
 
2760
        table->s->uniques= 0;                   // To ensure rows are the same
3029
2761
      }
3030
2762
      if (++join->send_records >= join->tmp_table_param.end_write_records && join->do_send_rows)
3031
2763
      {
3037
2769
      }
3038
2770
    }
3039
2771
  }
3040
 
 
 
2772
end:
3041
2773
  return NESTED_LOOP_OK;
3042
2774
}
3043
2775
 
3044
2776
/** Group by searching after group record and updating it if possible. */
3045
 
enum_nested_loop_state end_update(Join *join, JoinTable *, bool end_of_records)
 
2777
enum_nested_loop_state end_update(JOIN *join, JoinTable *, bool end_of_records)
3046
2778
{
3047
2779
  Table *table= join->tmp_table;
3048
 
  Order *group;
 
2780
  order_st *group;
3049
2781
  int   error;
3050
2782
 
3051
2783
  if (end_of_records)
3052
2784
    return NESTED_LOOP_OK;
3053
 
  if (join->session->getKilled())                       // Aborted by user
 
2785
  if (join->session->killed)                    // Aborted by user
3054
2786
  {
3055
2787
    join->session->send_kill_message();
3056
 
    return NESTED_LOOP_KILLED;
 
2788
    return NESTED_LOOP_KILLED;             /* purecov: inspected */
3057
2789
  }
3058
2790
 
3059
2791
  join->found_records++;
3067
2799
    if (item->maybe_null)
3068
2800
      group->buff[-1]= (char) group->field->is_null();
3069
2801
  }
3070
 
  if (!table->cursor->index_read_map(table->getUpdateRecord(),
 
2802
  if (!table->file->index_read_map(table->record[1],
3071
2803
                                   join->tmp_table_param.group_buff,
3072
2804
                                   HA_WHOLE_KEY,
3073
2805
                                   HA_READ_KEY_EXACT))
3074
2806
  {                                             /* Update old record */
3075
2807
    table->restoreRecord();
3076
2808
    update_tmptable_sum_func(join->sum_funcs,table);
3077
 
    if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
3078
 
                                          table->getInsertRecord())))
 
2809
    if ((error= table->file->ha_update_row(table->record[1],
 
2810
                                          table->record[0])))
3079
2811
    {
3080
 
      table->print_error(error,MYF(0));
3081
 
      return NESTED_LOOP_ERROR;
 
2812
      table->file->print_error(error,MYF(0));   /* purecov: inspected */
 
2813
      return NESTED_LOOP_ERROR;            /* purecov: inspected */
3082
2814
    }
3083
2815
    return NESTED_LOOP_OK;
3084
2816
  }
3088
2820
    We can't copy all data as the key may have different format
3089
2821
    as the row data (for example as with VARCHAR keys)
3090
2822
  */
3091
 
  KeyPartInfo *key_part;
 
2823
  KEY_PART_INFO *key_part;
3092
2824
  for (group=table->group,key_part=table->key_info[0].key_part;
3093
2825
       group ;
3094
2826
       group=group->next,key_part++)
3095
2827
  {
3096
2828
    if (key_part->null_bit)
3097
 
      memcpy(table->getInsertRecord()+key_part->offset, group->buff, 1);
 
2829
      memcpy(table->record[0]+key_part->offset, group->buff, 1);
3098
2830
  }
3099
2831
  init_tmptable_sum_functions(join->sum_funcs);
3100
 
  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3101
 
    return NESTED_LOOP_ERROR;
3102
 
  if ((error=table->cursor->insertRecord(table->getInsertRecord())))
 
2832
  copy_funcs(join->tmp_table_param.items_to_copy);
 
2833
  if ((error=table->file->ha_write_row(table->record[0])))
3103
2834
  {
3104
 
    my_error(ER_USE_SQL_BIG_RESULT, MYF(0));
3105
 
    return NESTED_LOOP_ERROR;        // Table is_full error
 
2835
    if (create_myisam_from_heap(join->session, table,
 
2836
                                join->tmp_table_param.start_recinfo,
 
2837
                                &join->tmp_table_param.recinfo,
 
2838
                                error, 0))
 
2839
      return NESTED_LOOP_ERROR;            // Not a table_is_full error
 
2840
    /* Change method to update rows */
 
2841
    table->file->ha_index_init(0, 0);
 
2842
    join->join_tab[join->tables-1].next_select= end_unique_update;
3106
2843
  }
3107
2844
  join->send_records++;
3108
2845
  return NESTED_LOOP_OK;
3109
2846
}
3110
2847
 
3111
2848
/** Like end_update, but this is done with unique constraints instead of keys.  */
3112
 
enum_nested_loop_state end_unique_update(Join *join, JoinTable *, bool end_of_records)
 
2849
enum_nested_loop_state end_unique_update(JOIN *join, JoinTable *, bool end_of_records)
3113
2850
{
3114
2851
  Table *table= join->tmp_table;
3115
2852
  int   error;
3116
2853
 
3117
2854
  if (end_of_records)
3118
2855
    return NESTED_LOOP_OK;
3119
 
  if (join->session->getKilled())                       // Aborted by user
 
2856
  if (join->session->killed)                    // Aborted by user
3120
2857
  {
3121
2858
    join->session->send_kill_message();
3122
 
    return NESTED_LOOP_KILLED;
 
2859
    return NESTED_LOOP_KILLED;             /* purecov: inspected */
3123
2860
  }
3124
2861
 
3125
2862
  init_tmptable_sum_functions(join->sum_funcs);
3126
2863
  copy_fields(&join->tmp_table_param);          // Groups are copied twice.
3127
 
  if (copy_funcs(join->tmp_table_param.items_to_copy, join->session))
3128
 
    return NESTED_LOOP_ERROR;
 
2864
  copy_funcs(join->tmp_table_param.items_to_copy);
3129
2865
 
3130
 
  if (!(error= table->cursor->insertRecord(table->getInsertRecord())))
 
2866
  if (!(error= table->file->ha_write_row(table->record[0])))
3131
2867
    join->send_records++;                       // New group
3132
2868
  else
3133
2869
  {
3134
 
    if ((int) table->get_dup_key(error) < 0)
 
2870
    if ((int) table->file->get_dup_key(error) < 0)
3135
2871
    {
3136
 
      table->print_error(error,MYF(0));
3137
 
      return NESTED_LOOP_ERROR;
 
2872
      table->file->print_error(error,MYF(0));   /* purecov: inspected */
 
2873
      return NESTED_LOOP_ERROR;            /* purecov: inspected */
3138
2874
    }
3139
 
    if (table->cursor->rnd_pos(table->getUpdateRecord(),table->cursor->dup_ref))
 
2875
    if (table->file->rnd_pos(table->record[1],table->file->dup_ref))
3140
2876
    {
3141
 
      table->print_error(error,MYF(0));
3142
 
      return NESTED_LOOP_ERROR;
 
2877
      table->file->print_error(error,MYF(0));   /* purecov: inspected */
 
2878
      return NESTED_LOOP_ERROR;            /* purecov: inspected */
3143
2879
    }
3144
2880
    table->restoreRecord();
3145
2881
    update_tmptable_sum_func(join->sum_funcs,table);
3146
 
    if ((error= table->cursor->updateRecord(table->getUpdateRecord(),
3147
 
                                          table->getInsertRecord())))
 
2882
    if ((error= table->file->ha_update_row(table->record[1],
 
2883
                                          table->record[0])))
3148
2884
    {
3149
 
      table->print_error(error,MYF(0));
3150
 
      return NESTED_LOOP_ERROR;
 
2885
      table->file->print_error(error,MYF(0));   /* purecov: inspected */
 
2886
      return NESTED_LOOP_ERROR;            /* purecov: inspected */
3151
2887
    }
3152
2888
  }
3153
2889
  return NESTED_LOOP_OK;
3165
2901
  @retval
3166
2902
    1   failed
3167
2903
*/
3168
 
static bool make_group_fields(Join *main_join, Join *curr_join)
 
2904
static bool make_group_fields(JOIN *main_join, JOIN *curr_join)
3169
2905
{
3170
2906
  if (main_join->group_fields_cache.elements)
3171
2907
  {
3184
2920
/**
3185
2921
  calc how big buffer we need for comparing group entries.
3186
2922
*/
3187
 
static void calc_group_buffer(Join *join, Order *group)
 
2923
static void calc_group_buffer(JOIN *join,order_st *group)
3188
2924
{
3189
2925
  uint32_t key_length=0, parts=0, null_parts=0;
3190
2926
 
3210
2946
      case REAL_RESULT:
3211
2947
        key_length+= sizeof(double);
3212
2948
        break;
3213
 
 
3214
2949
      case INT_RESULT:
3215
2950
        key_length+= sizeof(int64_t);
3216
2951
        break;
3217
 
 
3218
2952
      case DECIMAL_RESULT:
3219
 
        key_length+= class_decimal_get_binary_size(group_item->max_length -
 
2953
        key_length+= my_decimal_get_binary_size(group_item->max_length -
3220
2954
                                                (group_item->decimals ? 1 : 0),
3221
2955
                                                group_item->decimals);
3222
2956
        break;
3223
 
 
3224
2957
      case STRING_RESULT:
3225
 
        {
3226
 
          enum enum_field_types type= group_item->field_type();
 
2958
      {
 
2959
        enum enum_field_types type= group_item->field_type();
 
2960
        /*
 
2961
          As items represented as DATE/TIME fields in the group buffer
 
2962
          have STRING_RESULT result type, we increase the length
 
2963
          by 8 as maximum pack length of such fields.
 
2964
        */
 
2965
        if (type == DRIZZLE_TYPE_DATE ||
 
2966
            type == DRIZZLE_TYPE_DATETIME ||
 
2967
            type == DRIZZLE_TYPE_TIMESTAMP)
 
2968
        {
 
2969
          key_length+= 8;
 
2970
        }
 
2971
        else
 
2972
        {
3227
2973
          /*
3228
 
            As items represented as DATE/TIME fields in the group buffer
3229
 
            have STRING_RESULT result type, we increase the length
3230
 
            by 8 as maximum pack length of such fields.
 
2974
            Group strings are taken as varstrings and require an length field.
 
2975
            A field is not yet created by create_tmp_field()
 
2976
            and the sizes should match up.
3231
2977
          */
3232
 
          if (type == DRIZZLE_TYPE_DATE ||
3233
 
              type == DRIZZLE_TYPE_TIME ||
3234
 
              type == DRIZZLE_TYPE_DATETIME ||
3235
 
              type == DRIZZLE_TYPE_MICROTIME ||
3236
 
              type == DRIZZLE_TYPE_TIMESTAMP)
3237
 
          {
3238
 
            key_length+= 8;
3239
 
          }
3240
 
          else
3241
 
          {
3242
 
            /*
3243
 
              Group strings are taken as varstrings and require an length field.
3244
 
              A field is not yet created by create_tmp_field()
3245
 
              and the sizes should match up.
3246
 
            */
3247
 
            key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3248
 
          }
3249
 
 
3250
 
          break;
 
2978
          key_length+= group_item->max_length + HA_KEY_BLOB_LENGTH;
3251
2979
        }
3252
 
 
3253
 
      case ROW_RESULT:
 
2980
        break;
 
2981
      }
 
2982
      default:
3254
2983
        /* This case should never be choosen */
3255
2984
        assert(0);
3256
2985
        my_error(ER_OUT_OF_RESOURCES, MYF(ME_FATALERROR));
3257
2986
      }
3258
2987
    }
3259
 
 
3260
2988
    parts++;
3261
 
 
3262
2989
    if (group_item->maybe_null)
3263
2990
      null_parts++;
3264
2991
  }
3265
 
 
3266
2992
  join->tmp_table_param.group_length=key_length+null_parts;
3267
2993
  join->tmp_table_param.group_parts=parts;
3268
2994
  join->tmp_table_param.group_null_parts=null_parts;
3273
2999
 
3274
3000
  Groups are saved in reverse order for easyer check loop.
3275
3001
*/
3276
 
static bool alloc_group_fields(Join *join, Order *group)
 
3002
static bool alloc_group_fields(JOIN *join,order_st *group)
3277
3003
{
3278
3004
  if (group)
3279
3005
  {
3280
3006
    for (; group ; group=group->next)
3281
3007
    {
3282
 
      Cached_item *tmp= new_Cached_item(join->session, *group->item);
 
3008
      Cached_item *tmp=new_Cached_item(join->session, *group->item, false);
3283
3009
      if (!tmp || join->group_fields.push_front(tmp))
3284
3010
        return true;
3285
3011
    }
3288
3014
  return false;
3289
3015
}
3290
3016
 
3291
 
static uint32_t cache_record_length(Join *join,uint32_t idx)
 
3017
/**
 
3018
  @todo
 
3019
  - TODO: this function is here only temporarily until 'greedy_search' is
 
3020
  tested and accepted.
 
3021
 
 
3022
  RETURN VALUES
 
3023
    false       ok
 
3024
    true        Fatal error
 
3025
*/
 
3026
static bool find_best(JOIN *join,table_map rest_tables,uint32_t idx,double record_count, double read_time)
 
3027
{
 
3028
  Session *session= join->session;
 
3029
  Position partial_pos;
 
3030
  if (session->killed)
 
3031
  {
 
3032
    return true;
 
3033
  }
 
3034
 
 
3035
  if (! rest_tables)
 
3036
  {
 
3037
    read_time+= record_count/(double) TIME_FOR_COMPARE;
 
3038
    partial_pos= join->getPosFromPartialPlan(join->const_tables);
 
3039
    if (join->sort_by_table &&
 
3040
        join->sort_by_table !=
 
3041
        partial_pos.table->table)
 
3042
    {
 
3043
      read_time+= record_count;      // We have to make a temp table
 
3044
    }
 
3045
    if (read_time < join->best_read)
 
3046
    {
 
3047
      join->copyPartialPlanIntoOptimalPlan(idx);
 
3048
      join->best_read= read_time - 0.001;
 
3049
    }
 
3050
    return false;
 
3051
  }
 
3052
  if (read_time+record_count/(double) TIME_FOR_COMPARE >= join->best_read)
 
3053
  {
 
3054
    return false;          /* Found better before */
 
3055
  }
 
3056
 
 
3057
  JoinTable *s;
 
3058
  double best_record_count= DBL_MAX;
 
3059
  double best_read_time= DBL_MAX;
 
3060
  for (JoinTable **pos= join->best_ref+idx ; (s= *pos) ; pos++)
 
3061
  {
 
3062
    table_map real_table_bit= s->table->map;
 
3063
    if (idx)
 
3064
    {
 
3065
      partial_pos= join->getPosFromPartialPlan(idx - 1);
 
3066
    }
 
3067
    if ((rest_tables & real_table_bit) && !(rest_tables & s->dependent) &&
 
3068
        (! idx || ! check_interleaving_with_nj(partial_pos.table, s)))
 
3069
    {
 
3070
      double records, best;
 
3071
      best_access_path(join, s, session, rest_tables, idx, record_count,
 
3072
                       read_time);
 
3073
      partial_pos= join->getPosFromPartialPlan(idx);
 
3074
      records= partial_pos.records_read;
 
3075
      best= partial_pos.read_time;
 
3076
      /*
 
3077
         Go to the next level only if there hasn't been a better key on
 
3078
         this level! This will cut down the search for a lot simple cases!
 
3079
       */
 
3080
      double current_record_count= record_count * records;
 
3081
      double current_read_time= read_time + best;
 
3082
      if (best_record_count > current_record_count ||
 
3083
          best_read_time > current_read_time ||
 
3084
          (idx == join->const_tables && s->table == join->sort_by_table))
 
3085
      {
 
3086
        if (best_record_count >= current_record_count &&
 
3087
            best_read_time >= current_read_time &&
 
3088
            (! (s->key_dependent & rest_tables) || 
 
3089
             partial_pos.isConstTable()))
 
3090
        {
 
3091
          best_record_count= current_record_count;
 
3092
          best_read_time= current_read_time;
 
3093
        }
 
3094
        std::swap(join->best_ref[idx], *pos);
 
3095
        if (find_best(join,rest_tables & ~real_table_bit,idx+1,
 
3096
              current_record_count,current_read_time))
 
3097
        {
 
3098
          return true;
 
3099
        }
 
3100
        std::swap(join->best_ref[idx], *pos);
 
3101
      }
 
3102
      restore_prev_nj_state(s);
 
3103
      if (join->select_options & SELECT_STRAIGHT_JOIN)
 
3104
        break;        // Don't test all combinations
 
3105
    }
 
3106
  }
 
3107
  return false;
 
3108
}
 
3109
 
 
3110
static uint32_t cache_record_length(JOIN *join,uint32_t idx)
3292
3111
{
3293
3112
  uint32_t length=0;
3294
3113
  JoinTable **pos,**end;
3356
3175
  RETURN
3357
3176
    Expected number of row combinations
3358
3177
*/
3359
 
static double prev_record_reads(Join *join, uint32_t idx, table_map found_ref)
 
3178
static double prev_record_reads(JOIN *join, uint32_t idx, table_map found_ref)
3360
3179
{
3361
3180
  double found=1.0;
3362
 
  optimizer::Position *pos_end= join->getSpecificPosInPartialPlan(-1);
3363
 
  for (optimizer::Position *pos= join->getSpecificPosInPartialPlan(idx - 1); 
 
3181
  Position *pos_end= join->getSpecificPosInPartialPlan(-1);
 
3182
  for (Position *pos= join->getSpecificPosInPartialPlan(idx - 1); 
3364
3183
       pos != pos_end; 
3365
3184
       pos--)
3366
3185
  {
3367
 
    if (pos->examinePosition(found_ref))
 
3186
    if (pos->table->table->map & found_ref)
3368
3187
    {
3369
 
      found_ref|= pos->getRefDependMap();
 
3188
      found_ref|= pos->ref_depend_map;
3370
3189
      /*
3371
 
        For the case of "t1 LEFT Join t2 ON ..." where t2 is a const table
 
3190
        For the case of "t1 LEFT JOIN t2 ON ..." where t2 is a const table
3372
3191
        with no matching row we will get position[t2].records_read==0.
3373
3192
        Actually the size of output is one null-complemented row, therefore
3374
3193
        we will use value of 1 whenever we get records_read==0.
3383
3202
          is an inprecise estimate and adding 1 (or, in the worst case,
3384
3203
          #max_nested_outer_joins=64-1) will not make it any more precise.
3385
3204
      */
3386
 
      if (pos->getFanout() > DBL_EPSILON)
3387
 
        found*= pos->getFanout();
 
3205
      if (pos->records_read > DBL_EPSILON)
 
3206
        found*= pos->records_read;
3388
3207
    }
3389
3208
  }
3390
3209
  return found;
3393
3212
/**
3394
3213
  Set up join struct according to best position.
3395
3214
*/
3396
 
static bool get_best_combination(Join *join)
 
3215
static bool get_best_combination(JOIN *join)
3397
3216
{
3398
3217
  uint32_t i,tablenr;
3399
3218
  table_map used_tables;
3400
3219
  JoinTable *join_tab,*j;
3401
 
  optimizer::KeyUse *keyuse;
 
3220
  KeyUse *keyuse;
3402
3221
  uint32_t table_count;
3403
3222
  Session *session=join->session;
3404
 
  optimizer::Position cur_pos;
 
3223
  Position cur_pos;
3405
3224
 
3406
3225
  table_count=join->tables;
3407
3226
  if (!(join->join_tab=join_tab=
3408
 
  (JoinTable*) session->getMemRoot()->allocate(sizeof(JoinTable)*table_count)))
 
3227
  (JoinTable*) session->alloc(sizeof(JoinTable)*table_count)))
3409
3228
    return(true);
3410
3229
 
3411
 
  for (i= 0; i < table_count; i++)
3412
 
    new (join_tab+i) JoinTable();
3413
 
 
3414
3230
  join->full_join=0;
3415
3231
 
3416
3232
  used_tables= OUTER_REF_TABLE_BIT;   // Outer row is already read
3418
3234
  {
3419
3235
    Table *form;
3420
3236
    cur_pos= join->getPosFromOptimalPlan(tablenr);
3421
 
    *j= *cur_pos.getJoinTable();
 
3237
    *j= *cur_pos.table;
3422
3238
    form=join->table[tablenr]=j->table;
3423
3239
    used_tables|= form->map;
3424
3240
    form->reginfo.join_tab=j;
3425
3241
    if (!*j->on_expr_ref)
3426
 
      form->reginfo.not_exists_optimize=0;  // Only with LEFT Join
 
3242
      form->reginfo.not_exists_optimize=0;  // Only with LEFT JOIN
3427
3243
    if (j->type == AM_CONST)
3428
3244
      continue;         // Handled in make_join_stat..
3429
3245
 
3432
3248
 
3433
3249
    if (j->type == AM_SYSTEM)
3434
3250
      continue;
3435
 
    if (j->keys.none() || ! (keyuse= cur_pos.getKeyUse()))
 
3251
    if (j->keys.none() || !(keyuse= cur_pos.key))
3436
3252
    {
3437
3253
      j->type= AM_ALL;
3438
3254
      if (tablenr != join->const_tables)
3449
3265
}
3450
3266
 
3451
3267
/** Save const tables first as used tables. */
3452
 
static void set_position(Join *join,
3453
 
                         uint32_t idx,
3454
 
                         JoinTable *table,
3455
 
                         optimizer::KeyUse *key)
 
3268
static void set_position(JOIN *join,uint32_t idx,JoinTable *table,KeyUse *key)
3456
3269
{
3457
 
  optimizer::Position tmp_pos(1.0, /* This is a const table */
3458
 
                              0.0,
3459
 
                              table,
3460
 
                              key,
3461
 
                              0);
 
3270
  Position tmp_pos;
 
3271
  tmp_pos.table= table;
 
3272
  tmp_pos.key= key;
 
3273
  tmp_pos.records_read= 1.0;  /* This is a const table */
 
3274
  tmp_pos.ref_depend_map= 0;
3462
3275
  join->setPosInPartialPlan(idx, tmp_pos);
3463
3276
 
3464
3277
  /* Move the const table as down as possible in best_ref */
3486
3299
                      the query
3487
3300
  @param join_tables  set of the tables in the query
3488
3301
 
 
3302
  @todo
 
3303
    'MAX_TABLES+2' denotes the old implementation of find_best before
 
3304
    the greedy version. Will be removed when greedy_search is approved.
 
3305
 
3489
3306
  @retval
3490
3307
    false       ok
3491
3308
  @retval
3492
3309
    true        Fatal error
3493
3310
*/
3494
 
static bool choose_plan(Join *join, table_map join_tables)
 
3311
static bool choose_plan(JOIN *join, table_map join_tables)
3495
3312
{
3496
3313
  uint32_t search_depth= join->session->variables.optimizer_search_depth;
3497
3314
  uint32_t prune_level=  join->session->variables.optimizer_prune_level;
3507
3324
      Apply heuristic: pre-sort all access plans with respect to the number of
3508
3325
      records accessed.
3509
3326
  */
3510
 
  internal::my_qsort(join->best_ref + join->const_tables,
3511
 
                     join->tables - join->const_tables, sizeof(JoinTable*),
3512
 
                     straight_join ? join_tab_cmp_straight : join_tab_cmp);
 
3327
  my_qsort(join->best_ref + join->const_tables,
 
3328
           join->tables - join->const_tables, sizeof(JoinTable*),
 
3329
           straight_join ? join_tab_cmp_straight : join_tab_cmp);
3513
3330
  if (straight_join)
3514
3331
  {
3515
3332
    optimize_straight_join(join, join_tables);
3516
3333
  }
3517
3334
  else
3518
3335
  {
3519
 
    if (search_depth == 0)
3520
 
      /* Automatically determine a reasonable value for 'search_depth' */
3521
 
      search_depth= determine_search_depth(join);
3522
 
    if (greedy_search(join, join_tables, search_depth, prune_level))
3523
 
      return true;
 
3336
    if (search_depth == MAX_TABLES+2)
 
3337
    { /*
 
3338
        TODO: 'MAX_TABLES+2' denotes the old implementation of find_best before
 
3339
        the greedy version. Will be removed when greedy_search is approved.
 
3340
      */
 
3341
      join->best_read= DBL_MAX;
 
3342
      if (find_best(join, join_tables, join->const_tables, 1.0, 0.0))
 
3343
        return(true);
 
3344
    }
 
3345
    else
 
3346
    {
 
3347
      if (search_depth == 0)
 
3348
        /* Automatically determine a reasonable value for 'search_depth' */
 
3349
        search_depth= determine_search_depth(join);
 
3350
      if (greedy_search(join, join_tables, search_depth, prune_level))
 
3351
        return(true);
 
3352
    }
3524
3353
  }
3525
3354
 
3526
3355
  /*
3558
3387
  @return
3559
3388
    None
3560
3389
*/
3561
 
static void best_access_path(Join *join,
 
3390
static void best_access_path(JOIN *join,
3562
3391
                             JoinTable *s,
3563
3392
                             Session *session,
3564
3393
                             table_map remaining_tables,
3566
3395
                             double record_count,
3567
3396
                             double)
3568
3397
{
3569
 
  optimizer::KeyUse *best_key= NULL;
3570
 
  uint32_t best_max_key_part= 0;
 
3398
  KeyUse *best_key=         0;
 
3399
  uint32_t best_max_key_part=   0;
3571
3400
  bool found_constraint= 0;
3572
 
  double best= DBL_MAX;
3573
 
  double best_time= DBL_MAX;
3574
 
  double records= DBL_MAX;
 
3401
  double best=              DBL_MAX;
 
3402
  double best_time=         DBL_MAX;
 
3403
  double records=           DBL_MAX;
3575
3404
  table_map best_ref_depends_map= 0;
3576
3405
  double tmp;
3577
3406
  ha_rows rec;
3579
3408
  if (s->keyuse)
3580
3409
  {                                            /* Use key if possible */
3581
3410
    Table *table= s->table;
3582
 
    optimizer::KeyUse *keyuse= NULL;
3583
 
    optimizer::KeyUse *start_key= NULL;
 
3411
    KeyUse *keyuse,*start_key=0;
3584
3412
    double best_records= DBL_MAX;
3585
3413
    uint32_t max_key_part=0;
3586
3414
 
3587
3415
    /* Test how we can use keys */
3588
3416
    rec= s->records/MATCHING_ROWS_IN_OTHER_TABLE;  // Assumed records/key
3589
 
    for (keyuse= s->keyuse; keyuse->getTable() == table; )
 
3417
    for (keyuse=s->keyuse ; keyuse->table == table ;)
3590
3418
    {
3591
3419
      key_part_map found_part= 0;
3592
3420
      table_map found_ref= 0;
3593
 
      uint32_t key= keyuse->getKey();
3594
 
      KeyInfo *keyinfo= table->key_info + key;
 
3421
      uint32_t key= keyuse->key;
 
3422
      KEY *keyinfo= table->key_info+key;
3595
3423
      /* Bitmap of keyparts where the ref access is over 'keypart=const': */
3596
3424
      key_part_map const_part= 0;
3597
3425
      /* The or-null keypart in ref-or-null access: */
3602
3430
 
3603
3431
      do /* For each keypart */
3604
3432
      {
3605
 
        uint32_t keypart= keyuse->getKeypart();
 
3433
        uint32_t keypart= keyuse->keypart;
3606
3434
        table_map best_part_found_ref= 0;
3607
3435
        double best_prev_record_reads= DBL_MAX;
3608
3436
 
3613
3441
            if 1. expression doesn't refer to forward tables
3614
3442
               2. we won't get two ref-or-null's
3615
3443
          */
3616
 
          if (! (remaining_tables & keyuse->getUsedTables()) &&
3617
 
              ! (ref_or_null_part && (keyuse->getOptimizeFlags() &
3618
 
                                      KEY_OPTIMIZE_REF_OR_NULL)))
 
3444
          if (!(remaining_tables & keyuse->used_tables) &&
 
3445
              !(ref_or_null_part && (keyuse->optimize &
 
3446
                                     KEY_OPTIMIZE_REF_OR_NULL)))
3619
3447
          {
3620
 
            found_part|= keyuse->getKeypartMap();
3621
 
            if (! (keyuse->getUsedTables() & ~join->const_table_map))
3622
 
              const_part|= keyuse->getKeypartMap();
 
3448
            found_part|= keyuse->keypart_map;
 
3449
            if (!(keyuse->used_tables & ~join->const_table_map))
 
3450
              const_part|= keyuse->keypart_map;
3623
3451
 
3624
3452
            double tmp2= prev_record_reads(join, idx, (found_ref |
3625
 
                                                       keyuse->getUsedTables()));
 
3453
                                                      keyuse->used_tables));
3626
3454
            if (tmp2 < best_prev_record_reads)
3627
3455
            {
3628
 
              best_part_found_ref= keyuse->getUsedTables() & ~join->const_table_map;
 
3456
              best_part_found_ref= keyuse->used_tables & ~join->const_table_map;
3629
3457
              best_prev_record_reads= tmp2;
3630
3458
            }
3631
 
            if (rec > keyuse->getTableRows())
3632
 
              rec= keyuse->getTableRows();
 
3459
            if (rec > keyuse->ref_table_rows)
 
3460
              rec= keyuse->ref_table_rows;
3633
3461
      /*
3634
3462
        If there is one 'key_column IS NULL' expression, we can
3635
3463
        use this ref_or_null optimisation of this field
3636
3464
      */
3637
 
            if (keyuse->getOptimizeFlags() & KEY_OPTIMIZE_REF_OR_NULL)
3638
 
              ref_or_null_part|= keyuse->getKeypartMap();
 
3465
            if (keyuse->optimize & KEY_OPTIMIZE_REF_OR_NULL)
 
3466
              ref_or_null_part |= keyuse->keypart_map;
3639
3467
          }
3640
3468
 
3641
3469
          keyuse++;
3642
 
        } while (keyuse->getTable() == table && keyuse->getKey() == key &&
3643
 
                 keyuse->getKeypart() == keypart);
3644
 
        found_ref|= best_part_found_ref;
3645
 
      } while (keyuse->getTable() == table && keyuse->getKey() == key);
 
3470
        } while (keyuse->table == table && keyuse->key == key &&
 
3471
                 keyuse->keypart == keypart);
 
3472
  found_ref|= best_part_found_ref;
 
3473
      } while (keyuse->table == table && keyuse->key == key);
3646
3474
 
3647
3475
      /*
3648
3476
        Assume that that each key matches a proportional part of table.
3704
3532
                records=
3705
3533
                  ((double) s->records / (double) rec *
3706
3534
                   (1.0 +
3707
 
                    ((double) (table->getShare()->max_key_length-keyinfo->key_length) /
3708
 
                     (double) table->getShare()->max_key_length)));
 
3535
                    ((double) (table->s->max_key_length-keyinfo->key_length) /
 
3536
                     (double) table->s->max_key_length)));
3709
3537
                if (records < 2.0)
3710
3538
                  records=2.0;               /* Can't be as good as a unique */
3711
3539
              }
3733
3561
            if (table->covering_keys.test(key))
3734
3562
            {
3735
3563
              /* we can use only index tree */
3736
 
              tmp= record_count * table->cursor->index_only_read_time(key, tmp);
 
3564
              tmp= record_count * table->file->index_only_read_time(key, tmp);
3737
3565
            }
3738
3566
            else
3739
3567
              tmp= record_count * min(tmp,s->worst_seeks);
3747
3575
            Set tmp to (previous record count) * (records / combination)
3748
3576
          */
3749
3577
          if ((found_part & 1) &&
3750
 
              (!(table->index_flags(key) & HA_ONLY_WHOLE_INDEX) ||
3751
 
               found_part == PREV_BITS(uint, keyinfo->key_parts)))
 
3578
              (!(table->file->index_flags(key, 0, 0) & HA_ONLY_WHOLE_INDEX) ||
 
3579
               found_part == PREV_BITS(uint,keyinfo->key_parts)))
3752
3580
          {
3753
3581
            max_key_part= max_part_bit(found_part);
3754
3582
            /*
3827
3655
              else
3828
3656
              {
3829
3657
                /*
3830
 
                  Assume that the first key part matches 1% of the cursor
 
3658
                  Assume that the first key part matches 1% of the file
3831
3659
                  and that the whole key matches 10 (duplicates) or 1
3832
3660
                  (unique) records.
3833
3661
                  Assume also that more key matches proportionally more
3898
3726
            if (table->covering_keys.test(key))
3899
3727
            {
3900
3728
              /* we can use only index tree */
3901
 
              tmp= record_count * table->cursor->index_only_read_time(key, tmp);
 
3729
              tmp= record_count * table->file->index_only_read_time(key, tmp);
3902
3730
            }
3903
3731
            else
3904
3732
              tmp= record_count * min(tmp,s->worst_seeks);
3950
3778
        scan.
3951
3779
  */
3952
3780
  if ((records >= s->found_records || best > s->read_time) &&            // (1)
3953
 
      ! (s->quick && best_key && s->quick->index == best_key->getKey() &&      // (2)
3954
 
        best_max_key_part >= s->table->quick_key_parts[best_key->getKey()]) &&// (2)
3955
 
      ! ((s->table->cursor->getEngine()->check_flag(HTON_BIT_TABLE_SCAN_ON_INDEX)) &&   // (3)
3956
 
        ! s->table->covering_keys.none() && best_key && !s->quick) && // (3)
3957
 
      ! (s->table->force_index && best_key && !s->quick))                 // (4)
 
3781
      !(s->quick && best_key && s->quick->index == best_key->key &&      // (2)
 
3782
        best_max_key_part >= s->table->quick_key_parts[best_key->key]) &&// (2)
 
3783
      !((s->table->file->ha_table_flags() & HA_TABLE_SCAN_ON_INDEX) &&   // (3)
 
3784
        ! s->table->covering_keys.none() && best_key && !s->quick) &&// (3)
 
3785
      !(s->table->force_index && best_key && !s->quick))                 // (4)
3958
3786
  {                                             // Check full join
3959
3787
    ha_rows rnd_records= s->found_records;
3960
3788
    /*
3999
3827
    else
4000
3828
    {
4001
3829
      /* Estimate cost of reading table. */
4002
 
      tmp= s->table->cursor->scan_time();
 
3830
      tmp= s->table->file->scan_time();
4003
3831
      if (s->table->map & join->outer_join)     // Can't use join cache
4004
3832
      {
4005
3833
        /*
4050
3878
  }
4051
3879
 
4052
3880
  /* Update the cost information for the current partial plan */
4053
 
  optimizer::Position tmp_pos(records,
4054
 
                              best,
4055
 
                              s,
4056
 
                              best_key,
4057
 
                              best_ref_depends_map);
 
3881
  Position tmp_pos;
 
3882
  tmp_pos.records_read= records;
 
3883
  tmp_pos.read_time=    best;
 
3884
  tmp_pos.key=          best_key;
 
3885
  tmp_pos.table=        s;
 
3886
  tmp_pos.ref_depend_map= best_ref_depends_map;
4058
3887
  join->setPosInPartialPlan(idx, tmp_pos);
4059
3888
 
4060
3889
  if (!best_key &&
4088
3917
    Thus 'optimize_straight_join' can be used at any stage of the query
4089
3918
    optimization process to finalize a QEP as it is.
4090
3919
*/
4091
 
static void optimize_straight_join(Join *join, table_map join_tables)
 
3920
static void optimize_straight_join(JOIN *join, table_map join_tables)
4092
3921
{
4093
3922
  JoinTable *s;
4094
 
  optimizer::Position partial_pos;
 
3923
  Position partial_pos;
4095
3924
  uint32_t idx= join->const_tables;
4096
3925
  double    record_count= 1.0;
4097
3926
  double    read_time=    0.0;
4103
3932
                     record_count, read_time);
4104
3933
    /* compute the cost of the new plan extended with 's' */
4105
3934
    partial_pos= join->getPosFromPartialPlan(idx);
4106
 
    record_count*= partial_pos.getFanout();
4107
 
    read_time+=    partial_pos.getCost();
 
3935
    record_count*= partial_pos.records_read;
 
3936
    read_time+=    partial_pos.read_time;
4108
3937
    join_tables&= ~(s->table->map);
4109
3938
    ++idx;
4110
3939
  }
4112
3941
  read_time+= record_count / (double) TIME_FOR_COMPARE;
4113
3942
  partial_pos= join->getPosFromPartialPlan(join->const_tables);
4114
3943
  if (join->sort_by_table &&
4115
 
      partial_pos.hasTableForSorting(join->sort_by_table))
 
3944
      join->sort_by_table != partial_pos.table->table)
4116
3945
    read_time+= record_count;  // We have to make a temp table
4117
3946
  join->copyPartialPlanIntoOptimalPlan(idx);
4118
3947
  join->best_read= read_time;
4198
4027
  @retval
4199
4028
    true        Fatal error
4200
4029
*/
4201
 
static bool greedy_search(Join      *join,
 
4030
static bool greedy_search(JOIN      *join,
4202
4031
              table_map remaining_tables,
4203
4032
              uint32_t      search_depth,
4204
4033
              uint32_t      prune_level)
4208
4037
  uint32_t      idx= join->const_tables; // index into 'join->best_ref'
4209
4038
  uint32_t      best_idx;
4210
4039
  uint32_t      size_remain;    // cardinality of remaining_tables
4211
 
  optimizer::Position best_pos;
 
4040
  Position best_pos;
4212
4041
  JoinTable  *best_table; // the next plan node to be added to the curr QEP
4213
4042
 
4214
4043
  /* number of tables that remain to be optimized */
4215
 
  size_remain= internal::my_count_bits(remaining_tables);
 
4044
  size_remain= my_count_bits(remaining_tables);
4216
4045
 
4217
4046
  do {
4218
4047
    /* Find the extension of the current QEP with the lowest cost */
4232
4061
 
4233
4062
    /* select the first table in the optimal extension as most promising */
4234
4063
    best_pos= join->getPosFromOptimalPlan(idx);
4235
 
    best_table= best_pos.getJoinTable();
 
4064
    best_table= best_pos.table;
4236
4065
    /*
4237
4066
      Each subsequent loop of 'best_extension_by_limited_search' uses
4238
4067
      'join->positions' for cost estimates, therefore we have to update its
4240
4069
    */
4241
4070
    join->setPosInPartialPlan(idx, best_pos);
4242
4071
 
4243
 
    /*
4244
 
      We need to make best_extension_by_limited_search aware of the fact
4245
 
      that it's not starting from top level, but from a rather specific
4246
 
      position in the list of nested joins.
4247
 
    */
4248
 
    check_interleaving_with_nj (best_table);
4249
 
    
4250
 
      
4251
 
 
4252
4072
    /* find the position of 'best_table' in 'join->best_ref' */
4253
4073
    best_idx= idx;
4254
4074
    JoinTable *pos= join->best_ref[best_idx];
4259
4079
    std::swap(join->best_ref[idx], join->best_ref[best_idx]);
4260
4080
 
4261
4081
    /* compute the cost of the new plan extended with 'best_table' */
4262
 
    optimizer::Position partial_pos= join->getPosFromPartialPlan(idx);
4263
 
    record_count*= partial_pos.getFanout();
4264
 
    read_time+=    partial_pos.getCost();
 
4082
    Position partial_pos= join->getPosFromPartialPlan(idx);
 
4083
    record_count*= partial_pos.records_read;
 
4084
    read_time+=    partial_pos.read_time;
4265
4085
 
4266
4086
    remaining_tables&= ~(best_table->table->map);
4267
4087
    --size_remain;
4386
4206
  @retval
4387
4207
    true        Fatal error
4388
4208
*/
4389
 
static bool best_extension_by_limited_search(Join *join,
 
4209
static bool best_extension_by_limited_search(JOIN *join,
4390
4210
                                             table_map remaining_tables,
4391
4211
                                             uint32_t idx,
4392
4212
                                             double record_count,
4395
4215
                                             uint32_t prune_level)
4396
4216
{
4397
4217
  Session *session= join->session;
4398
 
  if (session->getKilled())  // Abort
 
4218
  if (session->killed)  // Abort
4399
4219
    return(true);
4400
4220
 
4401
4221
  /*
4405
4225
  JoinTable *s;
4406
4226
  double best_record_count= DBL_MAX;
4407
4227
  double best_read_time=    DBL_MAX;
4408
 
  optimizer::Position partial_pos;
 
4228
  Position partial_pos;
4409
4229
 
4410
4230
  for (JoinTable **pos= join->best_ref + idx ; (s= *pos) ; pos++)
4411
4231
  {
4412
4232
    table_map real_table_bit= s->table->map;
 
4233
    if (idx)
 
4234
    {
 
4235
      partial_pos= join->getPosFromPartialPlan(idx - 1);
 
4236
    }
4413
4237
    if ((remaining_tables & real_table_bit) &&
4414
 
        ! (remaining_tables & s->dependent) &&
4415
 
        (! idx || ! check_interleaving_with_nj(s)))
 
4238
        !(remaining_tables & s->dependent) &&
 
4239
        (!idx || !check_interleaving_with_nj(partial_pos.table, s)))
4416
4240
    {
4417
4241
      double current_record_count, current_read_time;
4418
4242
 
4428
4252
                       record_count, read_time);
4429
4253
      /* Compute the cost of extending the plan with 's' */
4430
4254
      partial_pos= join->getPosFromPartialPlan(idx);
4431
 
      current_record_count= record_count * partial_pos.getFanout();
4432
 
      current_read_time=    read_time + partial_pos.getCost();
 
4255
      current_record_count= record_count * partial_pos.records_read;
 
4256
      current_read_time=    read_time + partial_pos.read_time;
4433
4257
 
4434
4258
      /* Expand only partial plans with lower cost than the best QEP so far */
4435
4259
      if ((current_read_time +
4487
4311
        partial_pos= join->getPosFromPartialPlan(join->const_tables);
4488
4312
        current_read_time+= current_record_count / (double) TIME_FOR_COMPARE;
4489
4313
        if (join->sort_by_table &&
4490
 
            partial_pos.hasTableForSorting(join->sort_by_table))
 
4314
            join->sort_by_table !=
 
4315
            partial_pos.table->table)
4491
4316
          /* We have to make a temp table */
4492
4317
          current_read_time+= current_record_count;
4493
4318
        if ((search_depth == 1) || (current_read_time < join->best_read))
4533
4358
    exhaustiveness) of the depth-first search algorithm used by
4534
4359
    'greedy_search'.
4535
4360
*/
4536
 
static uint32_t determine_search_depth(Join *join)
 
4361
static uint32_t determine_search_depth(JOIN *join)
4537
4362
{
4538
4363
  uint32_t table_count=  join->tables - join->const_tables;
4539
4364
  uint32_t search_depth;
4552
4377
  return search_depth;
4553
4378
}
4554
4379
 
4555
 
static bool make_simple_join(Join *join,Table *tmp_table)
 
4380
static bool make_simple_join(JOIN *join,Table *tmp_table)
4556
4381
{
4557
4382
  Table **tableptr;
4558
4383
  JoinTable *join_tab;
4559
4384
 
4560
4385
  /*
4561
4386
    Reuse Table * and JoinTable if already allocated by a previous call
4562
 
    to this function through Join::exec (may happen for sub-queries).
 
4387
    to this function through JOIN::exec (may happen for sub-queries).
4563
4388
  */
4564
4389
  if (!join->table_reexec)
4565
4390
  {
4566
 
    if (!(join->table_reexec= (Table**) join->session->getMemRoot()->allocate(sizeof(Table*))))
4567
 
      return(true);
 
4391
    if (!(join->table_reexec= (Table**) join->session->alloc(sizeof(Table*))))
 
4392
      return(true);                        /* purecov: inspected */
4568
4393
    if (join->tmp_join)
4569
4394
      join->tmp_join->table_reexec= join->table_reexec;
4570
4395
  }
4571
4396
  if (!join->join_tab_reexec)
4572
4397
  {
4573
4398
    if (!(join->join_tab_reexec=
4574
 
          (JoinTable*) join->session->getMemRoot()->allocate(sizeof(JoinTable))))
4575
 
      return(true);
4576
 
    new (join->join_tab_reexec) JoinTable();
 
4399
          (JoinTable*) join->session->alloc(sizeof(JoinTable))))
 
4400
      return(true);                        /* purecov: inspected */
4577
4401
    if (join->tmp_join)
4578
4402
      join->tmp_join->join_tab_reexec= join->join_tab_reexec;
4579
4403
  }
4594
4418
  join->row_limit=join->unit->select_limit_cnt;
4595
4419
  join->do_send_rows = (join->row_limit) ? 1 : 0;
4596
4420
 
 
4421
  join_tab->cache.buff=0;                       /* No caching */
4597
4422
  join_tab->table=tmp_table;
4598
4423
  join_tab->select=0;
4599
4424
  join_tab->select_cond=0;
4609
4434
  join_tab->read_first_record= join_init_read_record;
4610
4435
  join_tab->join=join;
4611
4436
  join_tab->ref.key_parts= 0;
4612
 
  join_tab->read_record.init();
 
4437
  memset(&join_tab->read_record, 0, sizeof(join_tab->read_record));
4613
4438
  tmp_table->status=0;
4614
4439
  tmp_table->null_row=0;
4615
 
 
4616
 
  return false;
 
4440
  return(false);
4617
4441
}
4618
4442
 
4619
4443
/**
4657
4481
    This function can be called only after the execution plan
4658
4482
    has been chosen.
4659
4483
*/
4660
 
static void make_outerjoin_info(Join *join)
 
4484
static void make_outerjoin_info(JOIN *join)
4661
4485
{
4662
4486
  for (uint32_t i=join->const_tables ; i < join->tables ; i++)
4663
4487
  {
4664
4488
    JoinTable *tab=join->join_tab+i;
4665
4489
    Table *table=tab->table;
4666
4490
    TableList *tbl= table->pos_in_table_list;
4667
 
    TableList *embedding= tbl->getEmbedding();
 
4491
    TableList *embedding= tbl->embedding;
4668
4492
 
4669
4493
    if (tbl->outer_join)
4670
4494
    {
4677
4501
      tab->on_expr_ref= &tbl->on_expr;
4678
4502
      tab->cond_equal= tbl->cond_equal;
4679
4503
      if (embedding)
4680
 
        tab->first_upper= embedding->getNestedJoin()->first_nested;
 
4504
        tab->first_upper= embedding->nested_join->first_nested;
4681
4505
    }
4682
 
    for ( ; embedding ; embedding= embedding->getEmbedding())
 
4506
    for ( ; embedding ; embedding= embedding->embedding)
4683
4507
    {
4684
4508
      /* Ignore sj-nests: */
4685
4509
      if (!embedding->on_expr)
4686
4510
        continue;
4687
 
      NestedJoin *nested_join= embedding->getNestedJoin();
 
4511
      nested_join_st *nested_join= embedding->nested_join;
4688
4512
      if (!nested_join->counter_)
4689
4513
      {
4690
4514
        /*
4694
4518
        nested_join->first_nested= tab;
4695
4519
        tab->on_expr_ref= &embedding->on_expr;
4696
4520
        tab->cond_equal= tbl->cond_equal;
4697
 
        if (embedding->getEmbedding())
4698
 
          tab->first_upper= embedding->getEmbedding()->getNestedJoin()->first_nested;
 
4521
        if (embedding->embedding)
 
4522
          tab->first_upper= embedding->embedding->nested_join->first_nested;
4699
4523
      }
4700
4524
      if (!tab->first_inner)
4701
4525
        tab->first_inner= nested_join->first_nested;
4708
4532
  return;
4709
4533
}
4710
4534
 
4711
 
static bool make_join_select(Join *join,
4712
 
                             optimizer::SqlSelect *select,
4713
 
                             COND *cond)
 
4535
static bool make_join_select(JOIN *join,SQL_SELECT *select,COND *cond)
4714
4536
{
4715
4537
  Session *session= join->session;
4716
 
  optimizer::Position cur_pos;
 
4538
  Position cur_pos;
4717
4539
  if (select)
4718
4540
  {
4719
4541
    add_not_null_conds(join);
4793
4615
        tab->ref.key= -1;
4794
4616
        tab->ref.key_parts= 0;          // Don't use ref key.
4795
4617
        cur_pos= join->getPosFromOptimalPlan(i);
4796
 
        cur_pos.setFanout(rows2double(tab->quick->records));
 
4618
        cur_pos.records_read= rows2double(tab->quick->records);
4797
4619
        /*
4798
4620
           We will use join cache here : prevent sorting of the first
4799
4621
           table only and sort at the end.
4802
4624
          join->full_join= 1;
4803
4625
      }
4804
4626
 
4805
 
      if (join->full_join and not session->lex->current_select->is_cross and not cond)
4806
 
      {
4807
 
        my_error(ER_CARTESIAN_JOIN_ATTEMPTED, MYF(0));
4808
 
        return 1;
4809
 
      }
4810
 
 
4811
4627
      tmp= NULL;
4812
4628
      if (cond)
4813
4629
        tmp= make_cond_for_table(cond,used_tables,current_map, 0);
4837
4653
      if (tmp || !cond || tab->type == AM_REF || tab->type == AM_REF_OR_NULL ||
4838
4654
          tab->type == AM_EQ_REF)
4839
4655
      {
4840
 
        optimizer::SqlSelect *sel= tab->select= ((optimizer::SqlSelect*)
4841
 
            session->getMemRoot()->duplicate((unsigned char*) select,
 
4656
        SQL_SELECT *sel= tab->select= ((SQL_SELECT*)
 
4657
            session->memdup((unsigned char*) select,
4842
4658
              sizeof(*select)));
4843
4659
        if (! sel)
4844
4660
          return 1;                     // End of memory
4901
4717
          cur_pos= join->getPosFromOptimalPlan(i);
4902
4718
          if ((cond && (! ((tab->keys & tab->const_keys) == tab->keys) && i > 0)) ||
4903
4719
              (! tab->const_keys.none() && (i == join->const_tables) &&
4904
 
              (join->unit->select_limit_cnt < cur_pos.getFanout()) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
 
4720
              (join->unit->select_limit_cnt < cur_pos.records_read) && ((join->select_options & OPTION_FOUND_ROWS) == false)))
4905
4721
          {
4906
4722
            /* Join with outer join condition */
4907
4723
            COND *orig_cond= sel->cond;
4947
4763
            if (sel->quick)
4948
4764
            {
4949
4765
              cur_pos= join->getPosFromOptimalPlan(i);
4950
 
              cur_pos.setFanout(static_cast<double>(sel->quick->records));
 
4766
              cur_pos.records_read= (double)sel->quick->records;
4951
4767
            }
4952
4768
          }
4953
4769
          else
4975
4791
                                         current_map,
4976
4792
                                         current_map, 0)))
4977
4793
            {
4978
 
              tab->cache.select= (optimizer::SqlSelect*)
4979
 
                session->getMemRoot()->duplicate((unsigned char*) sel, sizeof(optimizer::SqlSelect));
 
4794
              tab->cache.select= (SQL_SELECT*)
 
4795
                session->memdup((unsigned char*) sel, sizeof(SQL_SELECT));
4980
4796
              tab->cache.select->cond= tmp;
4981
4797
              tab->cache.select->read_tables= join->const_table_map;
4982
4798
            }
5092
4908
    false - OK
5093
4909
    true  - Out of memory
5094
4910
*/
5095
 
static bool make_join_readinfo(Join *join)
 
4911
static bool make_join_readinfo(JOIN *join, uint64_t options, uint32_t no_jbuf_after)
5096
4912
{
5097
 
  bool sorted= true;
 
4913
  uint32_t i;
 
4914
  bool statistics= test(!(join->select_options & SELECT_DESCRIBE));
 
4915
  bool sorted= 1;
5098
4916
 
5099
 
  for (uint32_t i= join->const_tables ; i < join->tables ; i++)
 
4917
  for (i=join->const_tables ; i < join->tables ; i++)
5100
4918
  {
5101
4919
    JoinTable *tab=join->join_tab+i;
5102
4920
    Table *table=tab->table;
 
4921
    bool using_join_cache;
5103
4922
    tab->read_record.table= table;
5104
 
    tab->read_record.cursor= table->cursor;
 
4923
    tab->read_record.file=table->file;
5105
4924
    tab->next_select=sub_select;                /* normal select */
5106
4925
    /*
5107
4926
      TODO: don't always instruct first table's ref/range access method to
5108
4927
      produce sorted output.
5109
4928
    */
5110
4929
    tab->sorted= sorted;
5111
 
    sorted= false; // only first must be sorted
5112
 
 
 
4930
    sorted= 0;                                  // only first must be sorted
5113
4931
    if (tab->insideout_match_tab)
5114
4932
    {
5115
 
      if (! (tab->insideout_buf= (unsigned char*) join->session->getMemRoot()->allocate(tab->table->key_info
5116
 
                                                                       [tab->index].
5117
 
                                                                       key_length)))
 
4933
      if (!(tab->insideout_buf= (unsigned char*)join->session->alloc(tab->table->key_info
 
4934
                                                         [tab->index].
 
4935
                                                         key_length)))
5118
4936
        return true;
5119
4937
    }
5120
 
 
5121
 
    optimizer::AccessMethodFactory &factory= optimizer::AccessMethodFactory::singleton();
5122
 
    boost::shared_ptr<optimizer::AccessMethod> access_method(factory.createAccessMethod(tab->type));
5123
 
 
5124
 
    if (! access_method)
5125
 
    {
5126
 
      /**
5127
 
       * @todo
5128
 
       * Is abort() the correct thing to call here? I call this here because it was what was called in
5129
 
       * the default case for the switch statement that used to be here.
5130
 
       */
5131
 
      abort();
 
4938
    switch (tab->type) {
 
4939
    case AM_SYSTEM:                             // Only happens with left join
 
4940
      table->status=STATUS_NO_RECORD;
 
4941
      tab->read_first_record= join_read_system;
 
4942
      tab->read_record.read_record= join_no_more_records;
 
4943
      break;
 
4944
    case AM_CONST:                              // Only happens with left join
 
4945
      table->status=STATUS_NO_RECORD;
 
4946
      tab->read_first_record= join_read_const;
 
4947
      tab->read_record.read_record= join_no_more_records;
 
4948
      if (table->covering_keys.test(tab->ref.key) &&
 
4949
          !table->no_keyread)
 
4950
      {
 
4951
        table->key_read=1;
 
4952
        table->file->extra(HA_EXTRA_KEYREAD);
 
4953
      }
 
4954
      break;
 
4955
    case AM_EQ_REF:
 
4956
      table->status=STATUS_NO_RECORD;
 
4957
      if (tab->select)
 
4958
      {
 
4959
        delete tab->select->quick;
 
4960
        tab->select->quick=0;
 
4961
      }
 
4962
      delete tab->quick;
 
4963
      tab->quick=0;
 
4964
      tab->read_first_record= join_read_key;
 
4965
      tab->read_record.read_record= join_no_more_records;
 
4966
      if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
 
4967
      {
 
4968
        table->key_read=1;
 
4969
        table->file->extra(HA_EXTRA_KEYREAD);
 
4970
      }
 
4971
      break;
 
4972
    case AM_REF_OR_NULL:
 
4973
    case AM_REF:
 
4974
      table->status=STATUS_NO_RECORD;
 
4975
      if (tab->select)
 
4976
      {
 
4977
        delete tab->select->quick;
 
4978
        tab->select->quick=0;
 
4979
      }
 
4980
      delete tab->quick;
 
4981
      tab->quick=0;
 
4982
      if (table->covering_keys.test(tab->ref.key) && !table->no_keyread)
 
4983
      {
 
4984
        table->key_read=1;
 
4985
        table->file->extra(HA_EXTRA_KEYREAD);
 
4986
      }
 
4987
      if (tab->type == AM_REF)
 
4988
      {
 
4989
        tab->read_first_record= join_read_always_key;
 
4990
        tab->read_record.read_record= tab->insideout_match_tab?
 
4991
           join_read_next_same_diff : join_read_next_same;
 
4992
      }
 
4993
      else
 
4994
      {
 
4995
        tab->read_first_record= join_read_always_key_or_null;
 
4996
        tab->read_record.read_record= join_read_next_same_or_null;
 
4997
      }
 
4998
      break;
 
4999
    case AM_ALL:
 
5000
      /*
 
5001
        If previous table use cache
 
5002
        If the incoming data set is already sorted don't use cache.
 
5003
      */
 
5004
      table->status=STATUS_NO_RECORD;
 
5005
      using_join_cache= false;
 
5006
      if (i != join->const_tables && !(options & SELECT_NO_JOIN_CACHE) &&
 
5007
          tab->use_quick != 2 && !tab->first_inner && i <= no_jbuf_after &&
 
5008
          !tab->insideout_match_tab)
 
5009
      {
 
5010
        if ((options & SELECT_DESCRIBE) ||
 
5011
            !join_init_cache(join->session,join->join_tab+join->const_tables,
 
5012
                i-join->const_tables))
 
5013
        {
 
5014
                using_join_cache= true;
 
5015
          tab[-1].next_select=sub_select_cache; /* Patch previous */
 
5016
        }
 
5017
      }
 
5018
      /* These init changes read_record */
 
5019
      if (tab->use_quick == 2)
 
5020
      {
 
5021
        join->session->server_status|=SERVER_QUERY_NO_GOOD_INDEX_USED;
 
5022
        tab->read_first_record= join_init_quick_read_record;
 
5023
        if (statistics)
 
5024
          status_var_increment(join->session->status_var.select_range_check_count);
 
5025
      }
 
5026
      else
 
5027
      {
 
5028
        tab->read_first_record= join_init_read_record;
 
5029
        if (i == join->const_tables)
 
5030
        {
 
5031
          if (tab->select && tab->select->quick)
 
5032
          {
 
5033
            if (statistics)
 
5034
              status_var_increment(join->session->status_var.select_range_count);
 
5035
          }
 
5036
          else
 
5037
          {
 
5038
            join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
 
5039
            if (statistics)
 
5040
              status_var_increment(join->session->status_var.select_scan_count);
 
5041
          }
 
5042
        }
 
5043
        else
 
5044
        {
 
5045
          if (tab->select && tab->select->quick)
 
5046
          {
 
5047
            if (statistics)
 
5048
              status_var_increment(join->session->status_var.select_full_range_join_count);
 
5049
          }
 
5050
          else
 
5051
          {
 
5052
            join->session->server_status|=SERVER_QUERY_NO_INDEX_USED;
 
5053
            if (statistics)
 
5054
              status_var_increment(join->session->status_var.select_full_join_count);
 
5055
          }
 
5056
        }
 
5057
        if (!table->no_keyread)
 
5058
        {
 
5059
          if (tab->select && tab->select->quick &&
 
5060
                    tab->select->quick->index != MAX_KEY && //not index_merge
 
5061
              table->covering_keys.test(tab->select->quick->index))
 
5062
          {
 
5063
            table->key_read=1;
 
5064
            table->file->extra(HA_EXTRA_KEYREAD);
 
5065
          }
 
5066
          else if (!table->covering_keys.none() &&
 
5067
            !(tab->select && tab->select->quick))
 
5068
          {                                     // Only read index tree
 
5069
                  if (!tab->insideout_match_tab)
 
5070
                  {
 
5071
                    /*
 
5072
                      See bug #26447: "Using the clustered index for a table scan
 
5073
                      is always faster than using a secondary index".
 
5074
                    */
 
5075
                    if (table->s->primary_key != MAX_KEY &&
 
5076
                        table->file->primary_key_is_clustered())
 
5077
                      tab->index= table->s->primary_key;
 
5078
                    else
 
5079
                      tab->index= table->find_shortest_key(&table->covering_keys);
 
5080
                  }
 
5081
            tab->read_first_record= join_read_first;
 
5082
            tab->type= AM_NEXT;         // Read with index_first / index_next
 
5083
          }
 
5084
        }
 
5085
      }
 
5086
      break;
 
5087
    default:
 
5088
      break;                                    /* purecov: deadcode */
 
5089
    case AM_UNKNOWN:
 
5090
    case AM_MAYBE_REF:
 
5091
      abort();                                  /* purecov: deadcode */
5132
5092
    }
5133
 
 
5134
 
    access_method->getStats(table, tab);
5135
5093
  }
5136
 
 
5137
 
  join->join_tab[join->tables-1].next_select= NULL; /* Set by do_select */
5138
 
 
5139
 
  return false;
 
5094
  join->join_tab[join->tables-1].next_select=0; /* Set by do_select */
 
5095
  return(false);
5140
5096
}
5141
5097
 
5142
5098
/** Update the dependency map for the tables. */
5143
 
static void update_depend_map(Join *join)
 
5099
static void update_depend_map(JOIN *join)
5144
5100
{
5145
5101
  JoinTable *join_tab=join->join_tab, *end=join_tab+join->tables;
5146
5102
 
5163
5119
}
5164
5120
 
5165
5121
/** Update the dependency map for the sort order. */
5166
 
static void update_depend_map(Join *join, Order *order)
 
5122
static void update_depend_map(JOIN *join, order_st *order)
5167
5123
{
5168
5124
  for (; order ; order=order->next)
5169
5125
  {
5201
5157
  @return
5202
5158
    Returns new sort order
5203
5159
*/
5204
 
static Order *remove_constants(Join *join,Order *first_order, COND *cond, bool change_list, bool *simple_order)
 
5160
static order_st *remove_constants(JOIN *join,order_st *first_order, COND *cond, bool change_list, bool *simple_order)
5205
5161
{
5206
5162
  if (join->tables == join->const_tables)
5207
5163
    return change_list ? 0 : first_order;               // No need to sort
5208
5164
 
5209
 
  Order *order,**prev_ptr;
 
5165
  order_st *order,**prev_ptr;
5210
5166
  table_map first_table= join->join_tab[join->const_tables].table->map;
5211
5167
  table_map not_const_tables= ~join->const_table_map;
5212
5168
  table_map ref;
5261
5217
  return(first_order);
5262
5218
}
5263
5219
 
5264
 
static int return_zero_rows(Join *join,
 
5220
static int return_zero_rows(JOIN *join,
5265
5221
                            select_result *result,
5266
5222
                            TableList *tables,
5267
5223
                                        List<Item> &fields,
5272
5228
{
5273
5229
  if (select_options & SELECT_DESCRIBE)
5274
5230
  {
5275
 
    optimizer::ExplainPlan planner(join,
5276
 
                                   false,
5277
 
                                   false,
5278
 
                                   false,
5279
 
                                   info);
5280
 
    planner.printPlan();
5281
 
    return 0;
 
5231
    select_describe(join, false, false, false, info);
 
5232
    return(0);
5282
5233
  }
5283
5234
 
5284
5235
  join->join_free();
5427
5378
    - The new condition, if success
5428
5379
    - 0, otherwise
5429
5380
*/
5430
 
static COND *simplify_joins(Join *join, List<TableList> *join_list, COND *conds, bool top)
 
5381
static COND *simplify_joins(JOIN *join, List<TableList> *join_list, COND *conds, bool top)
5431
5382
{
5432
5383
  TableList *table;
5433
 
  NestedJoin *nested_join;
 
5384
  nested_join_st *nested_join;
5434
5385
  TableList *prev_table= 0;
5435
5386
  List_iterator<TableList> li(*join_list);
5436
5387
 
5443
5394
    table_map used_tables;
5444
5395
    table_map not_null_tables= (table_map) 0;
5445
5396
 
5446
 
    if ((nested_join= table->getNestedJoin()))
 
5397
    if ((nested_join= table->nested_join))
5447
5398
    {
5448
5399
      /*
5449
5400
         If the element of join_list is a nested join apply
5485
5436
        not_null_tables= conds->not_null_tables();
5486
5437
    }
5487
5438
 
5488
 
    if (table->getEmbedding())
 
5439
    if (table->embedding)
5489
5440
    {
5490
 
      table->getEmbedding()->getNestedJoin()->used_tables|= used_tables;
5491
 
      table->getEmbedding()->getNestedJoin()->not_null_tables|= not_null_tables;
 
5441
      table->embedding->nested_join->used_tables|= used_tables;
 
5442
      table->embedding->nested_join->not_null_tables|= not_null_tables;
5492
5443
    }
5493
5444
 
5494
5445
    if (!table->outer_join || (used_tables & not_null_tables))
5524
5475
    */
5525
5476
    if (table->on_expr)
5526
5477
    {
5527
 
      table->setDepTables(table->getDepTables() | table->on_expr->used_tables());
5528
 
      if (table->getEmbedding())
 
5478
      table->dep_tables|= table->on_expr->used_tables();
 
5479
      if (table->embedding)
5529
5480
      {
5530
 
        table->setDepTables(table->getDepTables() & ~table->getEmbedding()->getNestedJoin()->used_tables);
 
5481
        table->dep_tables&= ~table->embedding->nested_join->used_tables;
5531
5482
        /*
5532
5483
           Embedding table depends on tables used
5533
5484
           in embedded on expressions.
5534
5485
        */
5535
 
        table->getEmbedding()->setOnExprDepTables(table->getEmbedding()->getOnExprDepTables() & table->on_expr->used_tables());
 
5486
        table->embedding->on_expr_dep_tables|= table->on_expr->used_tables();
5536
5487
      }
5537
5488
      else
5538
 
        table->setDepTables(table->getDepTables() & ~table->table->map);
 
5489
        table->dep_tables&= ~table->table->map;
5539
5490
    }
5540
5491
 
5541
5492
    if (prev_table)
5542
5493
    {
5543
 
      //If this is straight join, set prev table to be dependent on all tables
5544
 
      //from this nested join, so that correct join order is selected.
5545
 
      if ((test(join->select_options & SELECT_STRAIGHT_JOIN)) ||
5546
 
          prev_table->straight)
5547
 
        prev_table->setDepTables(prev_table->getDepTables() | used_tables);
 
5494
      /* The order of tables is reverse: prev_table follows table */
 
5495
      if (prev_table->straight)
 
5496
        prev_table->dep_tables|= used_tables;
5548
5497
      if (prev_table->on_expr)
5549
5498
      {
5550
 
        prev_table->setDepTables(prev_table->getDepTables() | table->getOnExprDepTables());
5551
 
        table_map prev_used_tables= prev_table->getNestedJoin() ?
5552
 
                                    prev_table->getNestedJoin()->used_tables :
 
5499
        prev_table->dep_tables|= table->on_expr_dep_tables;
 
5500
        table_map prev_used_tables= prev_table->nested_join ?
 
5501
                                    prev_table->nested_join->used_tables :
5553
5502
                                    prev_table->table->map;
5554
5503
        /*
5555
5504
          If on expression contains only references to inner tables
5558
5507
          for them. Yet this is really a rare case.
5559
5508
              */
5560
5509
        if (!(prev_table->on_expr->used_tables() & ~prev_used_tables))
5561
 
          prev_table->setDepTables(prev_table->getDepTables() | used_tables);
 
5510
          prev_table->dep_tables|= used_tables;
5562
5511
      }
5563
5512
    }
5564
5513
    prev_table= table;
5571
5520
  li.rewind();
5572
5521
  while ((table= li++))
5573
5522
  {
5574
 
    nested_join= table->getNestedJoin();
 
5523
    nested_join= table->nested_join;
5575
5524
    if (nested_join && !table->on_expr)
5576
5525
    {
5577
5526
      TableList *tbl;
5578
5527
      List_iterator<TableList> it(nested_join->join_list);
5579
5528
      while ((tbl= it++))
5580
5529
      {
5581
 
        tbl->setEmbedding(table->getEmbedding());
5582
 
        tbl->setJoinList(table->getJoinList());
 
5530
        tbl->embedding= table->embedding;
 
5531
        tbl->join_list= table->join_list;
5583
5532
      }
5584
5533
      li.replace(nested_join->join_list);
5585
5534
    }
5587
5536
  return(conds);
5588
5537
}
5589
5538
 
5590
 
static int remove_duplicates(Join *join, Table *entry,List<Item> &fields, Item *having)
 
5539
static int remove_duplicates(JOIN *join, Table *entry,List<Item> &fields, Item *having)
5591
5540
{
5592
5541
  int error;
5593
5542
  uint32_t reclength,offset;
5611
5560
    join->unit->select_limit_cnt= 1;            // Only send first row
5612
5561
    return(0);
5613
5562
  }
5614
 
  Field **first_field=entry->getFields() + entry->getShare()->sizeFields() - field_count;
 
5563
  Field **first_field=entry->field+entry->s->fields - field_count;
5615
5564
  offset= (field_count ?
5616
 
           entry->getField(entry->getShare()->sizeFields() - field_count)->offset(entry->getInsertRecord()) : 0);
5617
 
  reclength= entry->getShare()->getRecordLength() - offset;
 
5565
           entry->field[entry->s->fields - field_count]->
 
5566
           offset(entry->record[0]) : 0);
 
5567
  reclength= entry->s->reclength-offset;
5618
5568
 
5619
5569
  entry->free_io_cache();                               // Safety
5620
 
  entry->cursor->info(HA_STATUS_VARIABLE);
5621
 
  if (entry->getShare()->db_type() == heap_engine ||
5622
 
      (!entry->getShare()->blob_fields &&
5623
 
       ((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->cursor->stats.records <
5624
 
        session->variables.sortbuff_size)))
5625
 
  {
 
5570
  entry->file->info(HA_STATUS_VARIABLE);
 
5571
  if (entry->s->db_type() == heap_engine ||
 
5572
      (!entry->s->blob_fields &&
 
5573
       ((ALIGN_SIZE(reclength) + HASH_OVERHEAD) * entry->file->stats.records <
 
5574
        session->variables.sortbuff_size)))
5626
5575
    error= remove_dup_with_hash_index(join->session, entry,
5627
 
                                      field_count, first_field,
5628
 
                                      reclength, having);
5629
 
  }
 
5576
                                     field_count, first_field,
 
5577
                                     reclength, having);
5630
5578
  else
5631
 
  {
5632
 
    error= remove_dup_with_compare(join->session, entry, first_field, offset, having);
5633
 
  }
 
5579
    error= remove_dup_with_compare(join->session, entry, first_field, offset,
 
5580
                                  having);
5634
5581
 
5635
5582
  free_blobs(first_field);
5636
 
 
5637
5583
  return(error);
5638
5584
}
5639
5585
 
5647
5593
                               List<Item> &fields,
5648
5594
                               List<Item> &all_fields,
5649
5595
                               COND **conds,
5650
 
                               Order *order,
5651
 
                               Order *group,
 
5596
                               order_st *order,
 
5597
                               order_st *group,
5652
5598
                               bool *hidden_group_fields)
5653
5599
{
5654
5600
  int res;
5675
5621
  @retval
5676
5622
    1   Fatal error
5677
5623
*/
5678
 
static bool make_join_statistics(Join *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
 
5624
static bool make_join_statistics(JOIN *join, TableList *tables, COND *conds, DYNAMIC_ARRAY *keyuse_array)
5679
5625
{
5680
5626
  int error;
5681
5627
  Table *table;
5682
 
  uint32_t i;
5683
 
  uint32_t table_count;
5684
 
  uint32_t const_count;
5685
 
  uint32_t key;
5686
 
  table_map found_const_table_map;
5687
 
  table_map all_table_map;
5688
 
  table_map found_ref;
5689
 
  table_map refs;
5690
 
  key_map const_ref;
5691
 
  key_map eq_part;
5692
 
  Table **table_vector= NULL;
5693
 
  JoinTable *stat= NULL;
5694
 
  JoinTable *stat_end= NULL;
5695
 
  JoinTable *s= NULL;
5696
 
  JoinTable **stat_ref= NULL;
5697
 
  optimizer::KeyUse *keyuse= NULL;
5698
 
  optimizer::KeyUse *start_keyuse= NULL;
5699
 
  table_map outer_join= 0;
5700
 
  vector<optimizer::SargableParam> sargables;
 
5628
  uint32_t i,table_count,const_count,key;
 
5629
  table_map found_const_table_map, all_table_map, found_ref, refs;
 
5630
  key_map const_ref, eq_part;
 
5631
  Table **table_vector;
 
5632
  JoinTable *stat,*stat_end,*s,**stat_ref;
 
5633
  KeyUse *keyuse,*start_keyuse;
 
5634
  table_map outer_join=0;
 
5635
  SARGABLE_PARAM *sargables= 0;
5701
5636
  JoinTable *stat_vector[MAX_TABLES+1];
5702
 
  optimizer::Position *partial_pos;
 
5637
  Position *partial_pos;
5703
5638
 
5704
 
  table_count= join->tables;
5705
 
  stat= (JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
5706
 
  stat_ref= (JoinTable**) join->session->getMemRoot()->allocate(sizeof(JoinTable*)*MAX_TABLES);
5707
 
  table_vector= (Table**) join->session->getMemRoot()->allocate(sizeof(Table*)*(table_count*2));
 
5639
  table_count=join->tables;
 
5640
  stat=(JoinTable*) join->session->calloc(sizeof(JoinTable)*table_count);
 
5641
  stat_ref=(JoinTable**) join->session->alloc(sizeof(JoinTable*)*MAX_TABLES);
 
5642
  table_vector=(Table**) join->session->alloc(sizeof(Table*)*(table_count*2));
5708
5643
  if (! stat || ! stat_ref || ! table_vector)
5709
 
    return 1;
 
5644
    return 1;                           // Eom /* purecov: inspected */
5710
5645
 
5711
5646
  join->best_ref=stat_vector;
5712
5647
 
5718
5653
       tables;
5719
5654
       s++, tables= tables->next_leaf, i++)
5720
5655
  {
5721
 
    TableList *embedding= tables->getEmbedding();
 
5656
    TableList *embedding= tables->embedding;
5722
5657
    stat_vector[i]=s;
5723
5658
    s->keys.reset();
5724
5659
    s->const_keys.reset();
5726
5661
    s->needed_reg.reset();
5727
5662
    table_vector[i]=s->table=table=tables->table;
5728
5663
    table->pos_in_table_list= tables;
5729
 
    assert(table->cursor);
5730
 
    error= table->cursor->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
 
5664
    error= table->file->info(HA_STATUS_VARIABLE | HA_STATUS_NO_LOCK);
5731
5665
    if (error)
5732
5666
    {
5733
 
        table->print_error(error, MYF(0));
 
5667
        table->file->print_error(error, MYF(0));
5734
5668
        return 1;
5735
5669
    }
5736
5670
    table->quick_keys.reset();
5737
5671
    table->reginfo.join_tab=s;
5738
5672
    table->reginfo.not_exists_optimize=0;
5739
5673
    memset(table->const_key_parts, 0,
5740
 
           sizeof(key_part_map)*table->getShare()->sizeKeys());
 
5674
           sizeof(key_part_map)*table->s->keys);
5741
5675
    all_table_map|= table->map;
5742
5676
    s->join=join;
5743
5677
    s->info=0;                                  // For describe
5744
5678
 
5745
 
    s->dependent= tables->getDepTables();
 
5679
    s->dependent= tables->dep_tables;
5746
5680
    s->key_dependent= 0;
5747
 
    table->quick_condition_rows= table->cursor->stats.records;
 
5681
    if (tables->schema_table)
 
5682
      table->file->stats.records= 2;
 
5683
    table->quick_condition_rows= table->file->stats.records;
5748
5684
 
5749
5685
    s->on_expr_ref= &tables->on_expr;
5750
5686
    if (*s->on_expr_ref)
5751
5687
    {
5752
5688
      /* s is the only inner table of an outer join */
5753
 
      if (!table->cursor->stats.records && !embedding)
 
5689
      if (!table->file->stats.records && !embedding)
5754
5690
      {                                         // Empty table
5755
5691
        s->dependent= 0;                        // Ignore LEFT JOIN depend.
5756
 
        set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
 
5692
        set_position(join,const_count++,s,(KeyUse*) 0);
5757
5693
        continue;
5758
5694
      }
5759
5695
      outer_join|= table->map;
5760
5696
      s->embedding_map.reset();
5761
 
      for (;embedding; embedding= embedding->getEmbedding())
5762
 
        s->embedding_map|= embedding->getNestedJoin()->nj_map;
 
5697
      for (;embedding; embedding= embedding->embedding)
 
5698
        s->embedding_map|= embedding->nested_join->nj_map;
5763
5699
      continue;
5764
5700
    }
5765
 
    if (embedding && !(false && ! embedding->getEmbedding()))
 
5701
    if (embedding && !(false && ! embedding->embedding))
5766
5702
    {
5767
5703
      /* s belongs to a nested join, maybe to several embedded joins */
5768
5704
      s->embedding_map.reset();
5769
5705
      do
5770
5706
      {
5771
 
        NestedJoin *nested_join= embedding->getNestedJoin();
 
5707
        nested_join_st *nested_join= embedding->nested_join;
5772
5708
        s->embedding_map|= nested_join->nj_map;
5773
 
        s->dependent|= embedding->getDepTables();
5774
 
        embedding= embedding->getEmbedding();
 
5709
        s->dependent|= embedding->dep_tables;
 
5710
        embedding= embedding->embedding;
5775
5711
        outer_join|= nested_join->used_tables;
5776
5712
      }
5777
5713
      while (embedding);
5778
5714
      continue;
5779
5715
    }
5780
 
    if ((table->cursor->stats.records <= 1) && !s->dependent &&
5781
 
              (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
 
5716
    if ((table->file->stats.records <= 1) && !s->dependent &&
 
5717
              (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) && 
5782
5718
        !join->no_const_tables)
5783
5719
    {
5784
 
      set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
 
5720
      set_position(join,const_count++,s,(KeyUse*) 0);
5785
5721
    }
5786
5722
  }
5787
5723
  stat_vector[i]=0;
5797
5733
       As we use bitmaps to represent the relation the complexity
5798
5734
       of the algorithm is O((number of tables)^2).
5799
5735
    */
5800
 
    for (i= 0; i < table_count; i++)
 
5736
    for (i= 0, s= stat ; i < table_count ; i++, s++)
5801
5737
    {
5802
 
      uint32_t j;
5803
 
      table= stat[i].table;
5804
 
 
5805
 
      if (!table->reginfo.join_tab->dependent)
5806
 
        continue;
5807
 
 
5808
 
      for (j= 0, s= stat; j < table_count; j++, s++)
 
5738
      for (uint32_t j= 0 ; j < table_count ; j++)
5809
5739
      {
 
5740
        table= stat[j].table;
5810
5741
        if (s->dependent & table->map)
5811
 
        {
5812
 
          table_map was_dependent= s->dependent;
5813
5742
          s->dependent |= table->reginfo.join_tab->dependent;
5814
 
          if (i > j && s->dependent != was_dependent)
5815
 
          {
5816
 
            i= j= 1;
5817
 
            break;
5818
 
          }
5819
 
        }
5820
5743
      }
 
5744
      if (s->dependent)
 
5745
        s->table->maybe_null= 1;
5821
5746
    }
5822
5747
    /* Catch illegal cross references for outer joins */
5823
5748
    for (i= 0, s= stat ; i < table_count ; i++, s++)
5828
5753
        my_message(ER_WRONG_OUTER_JOIN, ER(ER_WRONG_OUTER_JOIN), MYF(0));
5829
5754
        return 1;
5830
5755
      }
5831
 
      if (outer_join & s->table->map)
5832
 
        s->table->maybe_null= 1;
5833
 
 
5834
5756
      s->key_dependent= s->dependent;
5835
5757
    }
5836
5758
  }
5838
5760
  if (conds || outer_join)
5839
5761
    if (update_ref_and_keys(join->session, keyuse_array, stat, join->tables,
5840
5762
                            conds, join->cond_equal,
5841
 
                            ~outer_join, join->select_lex, sargables))
 
5763
                            ~outer_join, join->select_lex, &sargables))
5842
5764
      return 1;
5843
5765
 
5844
5766
  /* Read tables with 0 or 1 rows (system tables) */
5845
5767
  join->const_table_map= 0;
5846
5768
 
5847
 
  optimizer::Position *p_pos= join->getFirstPosInPartialPlan();
5848
 
  optimizer::Position *p_end= join->getSpecificPosInPartialPlan(const_count);
 
5769
  Position *p_pos= join->getFirstPosInPartialPlan();
 
5770
  Position *p_end= join->getSpecificPosInPartialPlan(const_count);
5849
5771
  while (p_pos < p_end)
5850
5772
  {
5851
5773
    int tmp;
5852
 
    s= p_pos->getJoinTable();
 
5774
    s= p_pos->table;
5853
5775
    s->type= AM_SYSTEM;
5854
5776
    join->const_table_map|=s->table->map;
5855
 
    if ((tmp= s->joinReadConstTable(p_pos)))
 
5777
    if ((tmp= join_read_const_table(s, p_pos)))
5856
5778
    {
5857
5779
      if (tmp > 0)
5858
5780
        return 1;                       // Fatal error
5875
5797
      set_position() will move all const_tables first in stat_vector
5876
5798
    */
5877
5799
 
5878
 
    for (JoinTable **pos= stat_vector+const_count; (s= *pos); pos++)
 
5800
    for (JoinTable **pos=stat_vector+const_count ; (s= *pos) ; pos++)
5879
5801
    {
5880
 
      table= s->table;
 
5802
      table=s->table;
5881
5803
 
5882
5804
      /*
5883
5805
        If equi-join condition by a key is null rejecting and after a
5896
5818
          TODO. Apply single row substitution to null complemented inner tables
5897
5819
          for nested outer join operations.
5898
5820
        */
5899
 
        while (keyuse->getTable() == table)
 
5821
        while (keyuse->table == table)
5900
5822
        {
5901
 
          if (! (keyuse->getVal()->used_tables() & ~join->const_table_map) &&
5902
 
              keyuse->getVal()->is_null() && keyuse->isNullRejected())
 
5823
          if (!(keyuse->val->used_tables() & ~join->const_table_map) &&
 
5824
              keyuse->val->is_null() && keyuse->null_rejecting)
5903
5825
          {
5904
5826
            s->type= AM_CONST;
5905
5827
            table->mark_as_null_row();
5906
5828
            found_const_table_map|= table->map;
5907
5829
            join->const_table_map|= table->map;
5908
 
            set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
 
5830
            set_position(join,const_count++,s,(KeyUse*) 0);
5909
5831
            goto more_const_tables_found;
5910
5832
           }
5911
5833
          keyuse++;
5917
5839
        // All dep. must be constants
5918
5840
        if (s->dependent & ~(found_const_table_map))
5919
5841
          continue;
5920
 
        if (table->cursor->stats.records <= 1L &&
5921
 
            (table->cursor->getEngine()->check_flag(HTON_BIT_STATS_RECORDS_IS_EXACT)) &&
5922
 
                  !table->pos_in_table_list->getEmbedding())
 
5842
        if (table->file->stats.records <= 1L &&
 
5843
            (table->file->ha_table_flags() & HA_STATS_RECORDS_IS_EXACT) &&
 
5844
                  !table->pos_in_table_list->embedding)
5923
5845
        {                                       // system table
5924
5846
          int tmp= 0;
5925
5847
          s->type= AM_SYSTEM;
5926
5848
          join->const_table_map|=table->map;
5927
 
          set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
 
5849
          set_position(join,const_count++,s,(KeyUse*) 0);
5928
5850
          partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5929
 
          if ((tmp= s->joinReadConstTable(partial_pos)))
 
5851
          if ((tmp= join_read_const_table(s, partial_pos)))
5930
5852
          {
5931
5853
            if (tmp > 0)
5932
5854
              return 1;                 // Fatal error
5940
5862
      if ((keyuse=s->keyuse))
5941
5863
      {
5942
5864
        s->type= AM_REF;
5943
 
        while (keyuse->getTable() == table)
 
5865
        while (keyuse->table == table)
5944
5866
        {
5945
 
          start_keyuse= keyuse;
5946
 
          key= keyuse->getKey();
 
5867
          start_keyuse=keyuse;
 
5868
          key=keyuse->key;
5947
5869
          s->keys.set(key);               // QQ: remove this ?
5948
5870
 
5949
 
          refs= 0;
5950
 
          const_ref.reset();
 
5871
          refs=0;
 
5872
                const_ref.reset();
5951
5873
          eq_part.reset();
5952
5874
          do
5953
5875
          {
5954
 
            if (keyuse->getVal()->type() != Item::NULL_ITEM && 
5955
 
                ! keyuse->getOptimizeFlags())
 
5876
            if (keyuse->val->type() != Item::NULL_ITEM && !keyuse->optimize)
5956
5877
            {
5957
 
              if (! ((~found_const_table_map) & keyuse->getUsedTables()))
5958
 
                const_ref.set(keyuse->getKeypart());
 
5878
              if (!((~found_const_table_map) & keyuse->used_tables))
 
5879
                const_ref.set(keyuse->keypart);
5959
5880
              else
5960
 
                refs|= keyuse->getUsedTables();
5961
 
              eq_part.set(keyuse->getKeypart());
 
5881
                refs|=keyuse->used_tables;
 
5882
              eq_part.set(keyuse->keypart);
5962
5883
            }
5963
5884
            keyuse++;
5964
 
          } while (keyuse->getTable() == table && keyuse->getKey() == key);
 
5885
          } while (keyuse->table == table && keyuse->key == key);
5965
5886
 
5966
5887
          if (is_keymap_prefix(eq_part, table->key_info[key].key_parts) &&
5967
 
              ! table->pos_in_table_list->getEmbedding())
 
5888
              !table->pos_in_table_list->embedding)
5968
5889
          {
5969
5890
            if ((table->key_info[key].flags & (HA_NOSAME)) == HA_NOSAME)
5970
5891
            {
5974
5895
                ref_changed = 1;
5975
5896
                s->type= AM_CONST;
5976
5897
                join->const_table_map|= table->map;
5977
 
                set_position(join, const_count++, s, start_keyuse);
 
5898
                set_position(join,const_count++,s,start_keyuse);
5978
5899
                if (create_ref_for_key(join, s, start_keyuse, found_const_table_map))
5979
5900
                  return 1;
5980
5901
                partial_pos= join->getSpecificPosInPartialPlan(const_count - 1);
5981
 
                if ((tmp=s->joinReadConstTable(partial_pos)))
 
5902
                if ((tmp=join_read_const_table(s, partial_pos)))
5982
5903
                {
5983
5904
                  if (tmp > 0)
5984
5905
                    return 1;                   // Fatal error
6002
5923
    Update info on indexes that can be used for search lookups as
6003
5924
    reading const tables may has added new sargable predicates.
6004
5925
  */
6005
 
  if (const_count && ! sargables.empty())
 
5926
  if (const_count && sargables)
6006
5927
  {
6007
 
    vector<optimizer::SargableParam>::iterator iter= sargables.begin();
6008
 
    while (iter != sargables.end())
 
5928
    for( ; sargables->field ; sargables++)
6009
5929
    {
6010
 
      Field *field= (*iter).getField();
6011
 
      JoinTable *join_tab= field->getTable()->reginfo.join_tab;
 
5930
      Field *field= sargables->field;
 
5931
      JoinTable *join_tab= field->table->reginfo.join_tab;
6012
5932
      key_map possible_keys= field->key_start;
6013
 
      possible_keys&= field->getTable()->keys_in_use_for_query;
6014
 
      bool is_const= true;
6015
 
      for (uint32_t j= 0; j < (*iter).getNumValues(); j++)
6016
 
        is_const&= (*iter).isConstItem(j);
 
5933
      possible_keys&= field->table->keys_in_use_for_query;
 
5934
      bool is_const= 1;
 
5935
      for (uint32_t j=0; j < sargables->num_values; j++)
 
5936
        is_const&= sargables->arg_value[j]->const_item();
6017
5937
      if (is_const)
6018
5938
        join_tab[0].const_keys|= possible_keys;
6019
 
      ++iter;
6020
5939
    }
6021
5940
  }
6022
5941
 
6031
5950
      continue;
6032
5951
    }
6033
5952
    /* Approximate found rows and time to read them */
6034
 
    s->found_records=s->records=s->table->cursor->stats.records;
6035
 
    s->read_time=(ha_rows) s->table->cursor->scan_time();
 
5953
    s->found_records=s->records=s->table->file->stats.records;
 
5954
    s->read_time=(ha_rows) s->table->file->scan_time();
6036
5955
 
6037
5956
    /*
6038
5957
      Set a max range of how many seeks we can expect when using keys
6051
5970
    add_group_and_distinct_keys(join, s);
6052
5971
 
6053
5972
    if (s->const_keys.any() &&
6054
 
        !s->table->pos_in_table_list->getEmbedding())
 
5973
        !s->table->pos_in_table_list->embedding)
6055
5974
    {
6056
5975
      ha_rows records;
6057
 
      optimizer::SqlSelect *select= NULL;
6058
 
      select= optimizer::make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
 
5976
      SQL_SELECT *select;
 
5977
      select= make_select(s->table, found_const_table_map, found_const_table_map, *s->on_expr_ref ? *s->on_expr_ref : conds, 1, &error);
6059
5978
      if (! select)
6060
5979
        return 1;
6061
5980
      records= get_quick_record_count(join->session, select, s->table, &s->const_keys, join->row_limit);
6062
5981
      s->quick=select->quick;
6063
5982
      s->needed_reg=select->needed_reg;
6064
5983
      select->quick=0;
6065
 
 
6066
5984
      if (records == 0 && s->table->reginfo.impossible_range)
6067
5985
      {
6068
5986
        /*
6072
5990
          caller to abort with a zero row result.
6073
5991
        */
6074
5992
        join->const_table_map|= s->table->map;
6075
 
        set_position(join, const_count++, s, (optimizer::KeyUse*) 0);
 
5993
        set_position(join,const_count++,s,(KeyUse*) 0);
6076
5994
        s->type= AM_CONST;
6077
5995
        if (*s->on_expr_ref)
6078
5996
        {
6102
6020
  if (join->const_tables != join->tables)
6103
6021
  {
6104
6022
    optimize_keyuse(join, keyuse_array);
6105
 
    // @note c_str() is not likely to be valid here if dtrace expects it to
6106
 
    // exist for any period of time.
6107
 
    DRIZZLE_QUERY_OPT_CHOOSE_PLAN_START(join->session->getQueryString()->c_str(), join->session->thread_id);
6108
 
    bool res= choose_plan(join, all_table_map & ~join->const_table_map);
6109
 
    DRIZZLE_QUERY_OPT_CHOOSE_PLAN_DONE(res ? 1 : 0);
6110
 
    if (res)
6111
 
      return true;
 
6023
    if (choose_plan(join, all_table_map & ~join->const_table_map))
 
6024
      return(true);
6112
6025
  }
6113
6026
  else
6114
6027
  {
6116
6029
    join->best_read= 1.0;
6117
6030
  }
6118
6031
  /* Generate an execution plan from the found optimal join order. */
6119
 
  return (join->session->getKilled() || get_best_combination(join));
 
6032
  return (join->session->killed || get_best_combination(join));
6120
6033
}
6121
6034
 
6122
6035
/**
6144
6057
  TableList *table;
6145
6058
  while ((table= li++))
6146
6059
  {
6147
 
    NestedJoin *nested_join;
6148
 
    if ((nested_join= table->getNestedJoin()))
 
6060
    nested_join_st *nested_join;
 
6061
    if ((nested_join= table->nested_join))
6149
6062
    {
6150
6063
      /*
6151
6064
        It is guaranteed by simplify_joins() function that a nested join
6176
6089
  Return table number if there is only one table in sort order
6177
6090
  and group and order is compatible, else return 0.
6178
6091
*/
6179
 
static Table *get_sort_by_table(Order *a, Order *b,TableList *tables)
 
6092
static Table *get_sort_by_table(order_st *a,order_st *b,TableList *tables)
6180
6093
{
6181
6094
  table_map map= (table_map) 0;
6182
6095
 
6201
6114
}
6202
6115
 
6203
6116
/**
6204
 
  Set NestedJoin::counter=0 in all nested joins in passed list.
 
6117
  Set nested_join_st::counter=0 in all nested joins in passed list.
6205
6118
 
6206
 
    Recursively set NestedJoin::counter=0 for all nested joins contained in
 
6119
    Recursively set nested_join_st::counter=0 for all nested joins contained in
6207
6120
    the passed join_list.
6208
6121
 
6209
6122
  @param join_list  List of nested joins to process. It may also contain base
6215
6128
  TableList *table;
6216
6129
  while ((table= li++))
6217
6130
  {
6218
 
    NestedJoin *nested_join;
6219
 
    if ((nested_join= table->getNestedJoin()))
 
6131
    nested_join_st *nested_join;
 
6132
    if ((nested_join= table->nested_join))
6220
6133
    {
6221
6134
      nested_join->counter_= 0;
6222
6135
      reset_nj_counters(&nested_join->join_list);
6231
6144
  If first parts has different direction, change it to second part
6232
6145
  (group is sorted like order)
6233
6146
*/
6234
 
static bool test_if_subpart(Order *a, Order *b)
 
6147
static bool test_if_subpart(order_st *a,order_st *b)
6235
6148
{
6236
6149
  for (; a && b; a=a->next,b=b->next)
6237
6150
  {
6246
6159
/**
6247
6160
  Nested joins perspective: Remove the last table from the join order.
6248
6161
 
6249
 
  The algorithm is the reciprocal of check_interleaving_with_nj(), hence
6250
 
  parent join nest nodes are updated only when the last table in its child
6251
 
  node is removed. The ASCII graphic below will clarify.
6252
 
 
6253
 
  %A table nesting such as <tt> t1 x [ ( t2 x t3 ) x ( t4 x t5 ) ] </tt>is
6254
 
  represented by the below join nest tree.
6255
 
 
6256
 
  @verbatim
6257
 
                     NJ1
6258
 
                  _/ /  \
6259
 
                _/  /    NJ2
6260
 
              _/   /     / \ 
6261
 
             /    /     /   \
6262
 
   t1 x [ (t2 x t3) x (t4 x t5) ]
6263
 
  @endverbatim
6264
 
 
6265
 
  At the point in time when check_interleaving_with_nj() adds the table t5 to
6266
 
  the query execution plan, QEP, it also directs the node named NJ2 to mark
6267
 
  the table as covered. NJ2 does so by incrementing its @c counter
6268
 
  member. Since all of NJ2's tables are now covered by the QEP, the algorithm
6269
 
  proceeds up the tree to NJ1, incrementing its counter as well. All join
6270
 
  nests are now completely covered by the QEP.
6271
 
 
6272
 
  restore_prev_nj_state() does the above in reverse. As seen above, the node
6273
 
  NJ1 contains the nodes t2, t3, and NJ2. Its counter being equal to 3 means
6274
 
  that the plan covers t2, t3, and NJ2, @e and that the sub-plan (t4 x t5)
6275
 
  completely covers NJ2. The removal of t5 from the partial plan will first
6276
 
  decrement NJ2's counter to 1. It will then detect that NJ2 went from being
6277
 
  completely to partially covered, and hence the algorithm must continue
6278
 
  upwards to NJ1 and decrement its counter to 2. %A subsequent removal of t4
6279
 
  will however not influence NJ1 since it did not un-cover the last table in
6280
 
  NJ2.
6281
 
 
6282
 
  SYNOPSIS
6283
 
    restore_prev_nj_state()
6284
 
      last  join table to remove, it is assumed to be the last in current 
6285
 
            partial join order.
6286
 
     
6287
 
  DESCRIPTION
6288
 
 
6289
6162
    Remove the last table from the partial join order and update the nested
6290
 
    joins counters and join->cur_embedding_map. It is ok to call this 
6291
 
    function for the first table in join order (for which 
 
6163
    joins counters and join->cur_embedding_map. It is ok to call this
 
6164
    function for the first table in join order (for which
6292
6165
    check_interleaving_with_nj has not been called)
6293
6166
 
6294
6167
  @param last  join table to remove, it is assumed to be the last in current
6295
6168
               partial join order.
6296
6169
*/
6297
 
 
6298
6170
static void restore_prev_nj_state(JoinTable *last)
6299
6171
{
6300
 
  TableList *last_emb= last->table->pos_in_table_list->getEmbedding();
6301
 
  Join *join= last->join;
6302
 
  for (;last_emb != NULL; last_emb= last_emb->getEmbedding())
6303
 
  {
6304
 
    NestedJoin *nest= last_emb->getNestedJoin();
6305
 
    
6306
 
    bool was_fully_covered= nest->is_fully_covered();
6307
 
    
6308
 
    if (--nest->counter_ == 0)
6309
 
      join->cur_embedding_map&= ~nest->nj_map;
6310
 
    
6311
 
    if (!was_fully_covered)
 
6172
  TableList *last_emb= last->table->pos_in_table_list->embedding;
 
6173
  JOIN *join= last->join;
 
6174
  while (last_emb)
 
6175
  {
 
6176
    if (last_emb->on_expr)
 
6177
    {
 
6178
      if (!(--last_emb->nested_join->counter_))
 
6179
        join->cur_embedding_map&= ~last_emb->nested_join->nj_map;
 
6180
      else if (last_emb->nested_join->join_list.elements-1 ==
 
6181
               last_emb->nested_join->counter_)
 
6182
        join->cur_embedding_map|= last_emb->nested_join->nj_map;
 
6183
      else
 
6184
        break;
 
6185
    }
 
6186
    last_emb= last_emb->embedding;
 
6187
  }
 
6188
}
 
6189
 
 
6190
/**
 
6191
  Determine if the set is already ordered for order_st BY, so it can
 
6192
  disable join cache because it will change the ordering of the results.
 
6193
  Code handles sort table that is at any location (not only first after
 
6194
  the const tables) despite the fact that it's currently prohibited.
 
6195
  We must disable join cache if the first non-const table alone is
 
6196
  ordered. If there is a temp table the ordering is done as a last
 
6197
  operation and doesn't prevent join cache usage.
 
6198
*/
 
6199
static uint32_t make_join_orderinfo(JOIN *join)
 
6200
{
 
6201
  uint32_t i;
 
6202
  if (join->need_tmp)
 
6203
    return join->tables;
 
6204
 
 
6205
  for (i=join->const_tables ; i < join->tables ; i++)
 
6206
  {
 
6207
    JoinTable *tab= join->join_tab+i;
 
6208
    Table *table= tab->table;
 
6209
    if ((table == join->sort_by_table &&
 
6210
        (!join->order || join->skip_sort_order)) ||
 
6211
        (join->sort_by_table == (Table *) 1 &&  i != join->const_tables))
 
6212
    {
6312
6213
      break;
6313
 
    
6314
 
    join->cur_embedding_map|= nest->nj_map;
 
6214
    }
6315
6215
  }
 
6216
  return i;
6316
6217
}
6317
6218
 
6318
6219
/**
6332
6233
 
6333
6234
  for (uint32_t i=0 ; i < join_tab->ref.key_parts ; i++)
6334
6235
  {
6335
 
    Field *field=table->getField(table->key_info[join_tab->ref.key].key_part[i].fieldnr - 1);
 
6236
    Field *field=table->field[table->key_info[join_tab->ref.key].key_part[i].
 
6237
                              fieldnr-1];
6336
6238
    Item *value=join_tab->ref.items[i];
6337
6239
    cond->add(new Item_func_equal(new Item_field(field), value));
6338
6240
  }
6346
6248
    error=(int) cond->add(join_tab->select->cond);
6347
6249
    join_tab->select_cond=join_tab->select->cond=cond;
6348
6250
  }
6349
 
  else if ((join_tab->select= optimizer::make_select(join_tab->table, 0, 0, cond, 0,
6350
 
                                                     &error)))
 
6251
  else if ((join_tab->select= make_select(join_tab->table, 0, 0, cond, 0,
 
6252
                                          &error)))
6351
6253
    join_tab->select_cond=cond;
6352
6254
 
6353
6255
  return(error ? true : false);
6365
6267
/**
6366
6268
  @} (end of group Query_Optimizer)
6367
6269
*/
6368
 
 
6369
 
} /* namespace drizzled */