← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

  • Committer: Monty Taylor
  • Date: 2009-03-24 17:44:41 UTC
  • mto: (960.5.2 mordred)
  • mto: This revision was merged to the branch mainline in revision 964.
  • Revision ID: mordred@inaugust.com-20090324174441-nmsq0gwjlgf7f0mt
Changed handlerton to StorageEngine.

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/opt_range.cc
25
25
/*
26
26
  This file contains:
27
27
 
28
 
  RangeAnalysisModule  
29
 
    A module that accepts a condition, index (or partitioning) description, 
30
 
    and builds lists of intervals (in index/partitioning space), such that 
31
 
    all possible records that match the condition are contained within the 
 
28
  RangeAnalysisModule
 
29
    A module that accepts a condition, index (or partitioning) description,
 
30
    and builds lists of intervals (in index/partitioning space), such that
 
31
    all possible records that match the condition are contained within the
32
32
    intervals.
33
33
    The entry point for the range analysis module is get_mm_tree() function.
34
 
    
 
34
 
35
35
    The lists are returned in form of complicated structure of interlinked
36
36
    SEL_TREE/SEL_IMERGE/SEL_ARG objects.
37
 
    See quick_range_seq_next, find_used_partitions for examples of how to walk 
 
37
    See quick_range_seq_next, find_used_partitions for examples of how to walk
38
38
    this structure.
39
39
    All direct "users" of this module are located within this file, too.
40
40
 
46
46
    The module has single entry point - prune_partitions() function.
47
47
 
48
48
 
49
 
  Range/index_merge/groupby-minmax optimizer module  
50
 
    A module that accepts a table, condition, and returns 
 
49
  Range/index_merge/groupby-minmax optimizer module
 
50
    A module that accepts a table, condition, and returns
51
51
     - a QUICK_*_SELECT object that can be used to retrieve rows that match
52
 
       the specified condition, or a "no records will match the condition" 
 
52
       the specified condition, or a "no records will match the condition"
53
53
       statement.
54
54
 
55
55
    The module entry points are
64
64
  ~~~~~~~~~~~~~~
65
65
  The code in this file (and elsewhere) makes operations on key value tuples.
66
66
  Those tuples are stored in the following format:
67
 
  
 
67
 
68
68
  The tuple is a sequence of key part values. The length of key part value
69
69
  depends only on its type (and not depends on the what value is stored)
70
 
  
 
70
 
71
71
    KeyTuple: keypart1-data, keypart2-data, ...
72
 
  
 
72
 
73
73
  The value of each keypart is stored in the following format:
74
 
  
 
74
 
75
75
    keypart_data: [isnull_byte] keypart-value-bytes
76
76
 
77
77
  If a keypart may have a NULL value (key_part->field->real_maybe_null() can
78
 
  be used to check this), then the first byte is a NULL indicator with the 
 
78
  be used to check this), then the first byte is a NULL indicator with the
79
79
  following valid values:
80
80
    1  - keypart has NULL value.
81
81
    0  - keypart has non-NULL value.
86
86
 
87
87
  keypart-value-bytes holds the value. Its format depends on the field type.
88
88
  The length of keypart-value-bytes may or may not depend on the value being
89
 
  stored. The default is that length is static and equal to 
 
89
  stored. The default is that length is static and equal to
90
90
  KEY_PART_INFO::length.
91
 
  
92
 
  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the 
 
91
 
 
92
  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
93
93
  value:
94
 
  
 
94
 
95
95
     keypart-value-bytes: value_length value_bytes
96
96
 
97
97
  The value_length part itself occupies HA_KEY_BLOB_LENGTH=2 bytes.
99
99
  See key_copy() and key_restore() for code to move data between index tuple
100
100
  and table record
101
101
 
102
 
  CAUTION: the above description is only sergefp's understanding of the 
 
102
  CAUTION: the above description is only sergefp's understanding of the
103
103
           subject and may omit some details.
104
104
*/
105
105
 
106
106
#include <drizzled/server_includes.h>
107
107
#include <drizzled/sql_select.h>
108
 
 
109
 
#ifndef EXTRA_DEBUG
110
 
#define test_rb_tree(A,B) {}
111
 
#define test_use_count(A) {}
112
 
#endif
 
108
#include <drizzled/error.h>
 
109
#include <drizzled/cost_vect.h>
 
110
#include <drizzled/item/cmpfunc.h>
 
111
#include <drizzled/field/num.h>
 
112
#include <drizzled/check_stack_overrun.h>
 
113
 
 
114
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
 
115
 
 
116
#include <string>
 
117
 
 
118
using namespace std;
113
119
 
114
120
/*
115
121
  Convert double value to #rows. Currently this does floor(), and we
116
122
  might consider using round() instead.
117
123
*/
118
 
#define double2rows(x) ((ha_rows)(x))
 
124
static inline ha_rows double2rows(double x)
 
125
{
 
126
    return static_cast<ha_rows>(x);
 
127
}
119
128
 
120
129
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
121
130
 
124
133
class RANGE_OPT_PARAM;
125
134
/*
126
135
  A construction block of the SEL_ARG-graph.
127
 
  
128
 
  The following description only covers graphs of SEL_ARG objects with 
 
136
 
 
137
  The following description only covers graphs of SEL_ARG objects with
129
138
  sel_arg->type==KEY_RANGE:
130
139
 
131
140
  One SEL_ARG object represents an "elementary interval" in form
132
 
  
 
141
 
133
142
      min_value <=?  table.keypartX  <=? max_value
134
 
  
 
143
 
135
144
  The interval is a non-empty interval of any kind: with[out] minimum/maximum
136
145
  bound, [half]open/closed, single-point interval, etc.
137
146
 
138
147
  1. SEL_ARG GRAPH STRUCTURE
139
 
  
 
148
 
140
149
  SEL_ARG objects are linked together in a graph. The meaning of the graph
141
150
  is better demostrated by an example:
142
 
  
 
151
 
143
152
     tree->keys[i]
144
 
      | 
 
153
      |
145
154
      |             $              $
146
155
      |    part=1   $     part=2   $    part=3
147
156
      |             $              $
150
159
      |  +-------+  $   +-------+  $   +--------+
151
160
      |      |      $              $       |
152
161
      |      |      $              $   +--------+
153
 
      |      |      $              $   | kp3=12 | 
154
 
      |      |      $              $   +--------+ 
155
 
      |  +-------+  $              $   
156
 
      \->| kp1=2 |--$--------------$-+ 
 
162
      |      |      $              $   | kp3=12 |
 
163
      |      |      $              $   +--------+
 
164
      |  +-------+  $              $
 
165
      \->| kp1=2 |--$--------------$-+
157
166
         +-------+  $              $ |   +--------+
158
167
             |      $              $  ==>| kp3=11 |
159
168
         +-------+  $              $ |   +--------+
161
170
         +-------+  $              $     +--------+
162
171
             |      $              $     | kp3=14 |
163
172
            ...     $              $     +--------+
164
 
 
 
173
 
165
174
  The entire graph is partitioned into "interval lists".
166
175
 
167
176
  An interval list is a sequence of ordered disjoint intervals over the same
168
177
  key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
169
 
  all intervals in the list form an RB-tree, linked via left/right/parent 
 
178
  all intervals in the list form an RB-tree, linked via left/right/parent
170
179
  pointers. The RB-tree root SEL_ARG object will be further called "root of the
171
180
  interval list".
172
 
  
173
 
    In the example pic, there are 4 interval lists: 
 
181
 
 
182
    In the example pic, there are 4 interval lists:
174
183
    "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
175
184
    The vertical lines represent SEL_ARG::next/prev pointers.
176
 
    
 
185
 
177
186
  In an interval list, each member X may have SEL_ARG::next_key_part pointer
178
187
  pointing to the root of another interval list Y. The pointed interval list
179
188
  must cover a key part with greater number (i.e. Y->part > X->part).
180
 
    
 
189
 
181
190
    In the example pic, the next_key_part pointers are represented by
182
191
    horisontal lines.
183
192
 
185
194
 
186
195
  It represents a condition in a special form (we don't have a name for it ATM)
187
196
  The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
188
 
  
 
197
 
189
198
  For example, the picture represents the condition in form:
190
 
   (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR 
191
 
   (kp1=2 AND (kp3=11 OR kp3=14)) OR 
 
199
   (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
 
200
   (kp1=2 AND (kp3=11 OR kp3=14)) OR
192
201
   (kp1=3 AND (kp3=11 OR kp3=14))
193
202
 
194
203
 
197
206
  Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
198
207
  Then walk the SEL_ARG graph and get a list of dijsoint ordered key
199
208
  intervals (i.e. intervals in form
200
 
  
 
209
 
201
210
   (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
202
211
 
203
212
  Those intervals can be used to access the index. The uses are in:
208
217
                            and create QUICK_RANGE_SELECT object that will
209
218
                            read records within these intervals.
210
219
 
211
 
  4. SPACE COMPLEXITY NOTES 
 
220
  4. SPACE COMPLEXITY NOTES
212
221
 
213
222
    SEL_ARG graph is a representation of an ordered disjoint sequence of
214
223
    intervals over the ordered set of index tuple values.
215
224
 
216
225
    For multi-part keys, one can construct a WHERE expression such that its
217
226
    list of intervals will be of combinatorial size. Here is an example:
218
 
     
219
 
      (keypart1 IN (1,2, ..., n1)) AND 
220
 
      (keypart2 IN (1,2, ..., n2)) AND 
 
227
 
 
228
      (keypart1 IN (1,2, ..., n1)) AND
 
229
      (keypart2 IN (1,2, ..., n2)) AND
221
230
      (keypart3 IN (1,2, ..., n3))
222
 
    
 
231
 
223
232
    For this WHERE clause the list of intervals will have n1*n2*n3 intervals
224
233
    of form
225
 
     
 
234
 
226
235
      (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
227
 
    
 
236
 
228
237
    SEL_ARG graph structure aims to reduce the amount of required space by
229
238
    "sharing" the elementary intervals when possible (the pic at the
230
 
    beginning of this comment has examples of such sharing). The sharing may 
 
239
    beginning of this comment has examples of such sharing). The sharing may
231
240
    prevent combinatorial blowup:
232
241
 
233
242
      There are WHERE clauses that have combinatorial-size interval lists but
234
243
      will be represented by a compact SEL_ARG graph.
235
244
      Example:
236
 
        (keypartN IN (1,2, ..., n1)) AND 
 
245
        (keypartN IN (1,2, ..., n1)) AND
237
246
        ...
238
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
247
        (keypart2 IN (1,2, ..., n2)) AND
239
248
        (keypart1 IN (1,2, ..., n3))
240
249
 
241
250
    but not in all cases:
244
253
      representation but get_mm_tree() and its callees will construct a
245
254
      graph of combinatorial size.
246
255
      Example:
247
 
        (keypart1 IN (1,2, ..., n1)) AND 
248
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
256
        (keypart1 IN (1,2, ..., n1)) AND
 
257
        (keypart2 IN (1,2, ..., n2)) AND
249
258
        ...
250
259
        (keypartN IN (1,2, ..., n3))
251
260
 
255
264
        By induction: Let's take any interval on some keypart in the middle:
256
265
 
257
266
           kp15=c0
258
 
        
 
267
 
259
268
        Then let's AND it with this interval 'structure' from preceding and
260
269
        following keyparts:
261
270
 
262
271
          (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
263
 
        
 
272
 
264
273
        We will obtain this SEL_ARG graph:
265
 
 
 
274
 
266
275
             kp14     $      kp15      $      kp16
267
276
                      $                $
268
277
         +---------+  $   +---------+  $   +---------+
269
278
         | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
270
279
         +---------+  $   +---------+  $   +---------+
271
 
              |       $                $              
272
 
         +---------+  $   +---------+  $             
273
 
         | kp14=c2 |--$-->| kp15=c0 |  $             
274
 
         +---------+  $   +---------+  $             
 
280
              |       $                $
 
281
         +---------+  $   +---------+  $
 
282
         | kp14=c2 |--$-->| kp15=c0 |  $
 
283
         +---------+  $   +---------+  $
275
284
                      $                $
276
 
                      
 
285
 
277
286
       Note that we had to duplicate "kp15=c0" and there was no way to avoid
278
 
       that. 
 
287
       that.
279
288
       The induction step: AND the obtained expression with another "wrapping"
280
289
       expression like (*).
281
 
       When the process ends because of the limit on max. number of keyparts 
 
290
       When the process ends because of the limit on max. number of keyparts
282
291
       we'll have:
283
292
 
284
293
         WHERE clause length  is O(3*#max_keyparts)
298
307
  uint8_t min_flag,max_flag,maybe_flag;
299
308
  uint8_t part;                                 // Which key part
300
309
  uint8_t maybe_null;
301
 
  /* 
 
310
  /*
302
311
    Number of children of this element in the RB-tree, plus 1 for this
303
312
    element itself.
304
313
  */
319
328
  SEL_ARG *left,*right;   /* R-B tree children */
320
329
  SEL_ARG *next,*prev;    /* Links for bi-directional interval list */
321
330
  SEL_ARG *parent;        /* R-B tree parent */
322
 
  SEL_ARG *next_key_part; 
 
331
  SEL_ARG *next_key_part;
323
332
  enum leaf_color { BLACK,RED } color;
324
333
  enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
325
334
 
345
354
  inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
346
355
  inline void maybe_smaller() { maybe_flag=1; }
347
356
  /* Return true iff it's a single-point null interval */
348
 
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; } 
 
357
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
349
358
  inline int cmp_min_to_min(SEL_ARG* arg)
350
359
  {
351
360
    return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
482
491
    uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
483
492
                                  range_key, *range_key_flag);
484
493
    *range_key_flag|= key_tree->min_flag;
485
 
    
 
494
 
486
495
    if (key_tree->next_key_part &&
487
496
        key_tree->next_key_part->part == key_tree->part+1 &&
488
497
        !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
556
565
 
557
566
    SYNOPSIS
558
567
      is_singlepoint()
559
 
    
 
568
 
560
569
    DESCRIPTION
561
570
      Check if this SEL_ARG object (not tree) represents a single-point
562
 
      interval, i.e. if it represents a "keypart = const" or 
 
571
      interval, i.e. if it represents a "keypart = const" or
563
572
      "keypart IS NULL".
564
573
 
565
574
    RETURN
569
578
 
570
579
  bool is_singlepoint()
571
580
  {
572
 
    /* 
573
 
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field) 
 
581
    /*
 
582
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
574
583
      flags, and the same for right edge.
575
584
    */
576
585
    if (min_flag || max_flag)
602
611
public:
603
612
  /*
604
613
    Starting an effort to document this field:
605
 
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) => 
 
614
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
606
615
       (type == SEL_TREE::IMPOSSIBLE)
607
616
  */
608
617
  enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
639
648
class RANGE_OPT_PARAM
640
649
{
641
650
public:
642
 
  THD   *thd;   /* Current thread handle */
 
651
  Session       *session;   /* Current thread handle */
643
652
  Table *table; /* Table being analyzed */
644
653
  COND *cond;   /* Used inside get_mm_tree(). */
645
654
  table_map prev_tables;
656
665
    #keys elements are not empty)
657
666
  */
658
667
  uint32_t keys;
659
 
  
660
 
  /* 
 
668
 
 
669
  /*
661
670
    If true, the index descriptions describe real indexes (and it is ok to
662
671
    call field->optimize_range(real_keynr[...], ...).
663
672
    Otherwise index description describes fake indexes.
664
673
  */
665
674
  bool using_real_indexes;
666
 
  
 
675
 
667
676
  bool remove_jump_scans;
668
 
  
 
677
 
669
678
  /*
670
679
    used_key_no -> table_key_no translation table. Only makes sense if
671
680
    using_real_indexes==true
672
681
  */
673
682
  uint32_t real_keynr[MAX_KEY];
674
683
  /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
675
 
  uint32_t alloced_sel_args; 
 
684
  uint32_t alloced_sel_args;
676
685
  bool force_default_mrr;
677
686
};
678
687
 
722
731
 
723
732
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
724
733
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
725
 
                                  SEL_ARG *tree, bool update_tbl_stats, 
 
734
                                  SEL_ARG *tree, bool update_tbl_stats,
726
735
                                  uint32_t *mrr_flags, uint32_t *bufsize,
727
736
                                  COST_VECT *cost);
728
737
                                  //bool update_tbl_stats);
732
741
*/
733
742
 
734
743
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
735
 
                                     SEL_ARG *key_tree, uint32_t mrr_flags, 
 
744
                                     SEL_ARG *key_tree, uint32_t mrr_flags,
736
745
                                     uint32_t mrr_buf_size, MEM_ROOT *alloc);
737
746
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
738
747
                                       bool index_read_must_be_used,
1009
1018
  *error=0;
1010
1019
 
1011
1020
  if (!conds && !allow_null_cond)
1012
 
    return(0);
 
1021
    return 0;
1013
1022
  if (!(select= new SQL_SELECT))
1014
1023
  {
1015
1024
    *error= 1;                  // out of memory
1016
 
    return(0);          /* purecov: inspected */
 
1025
    return 0;           /* purecov: inspected */
1017
1026
  }
1018
1027
  select->read_tables=read_tables;
1019
1028
  select->const_tables=const_tables;
1025
1034
    select->file= *head->sort.io_cache;
1026
1035
    select->records=(ha_rows) (select->file.end_of_file/
1027
1036
                               head->file->ref_length);
1028
 
    free(head->sort.io_cache);
 
1037
    delete head->sort.io_cache;
1029
1038
    head->sort.io_cache=0;
1030
1039
  }
1031
1040
  return(select);
1058
1067
  cleanup();
1059
1068
}
1060
1069
 
 
1070
 
 
1071
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
 
1072
                             ha_rows limit)
 
1073
{
 
1074
  key_map tmp;
 
1075
  tmp.set_all();
 
1076
  return test_quick_select(session, tmp, 0, limit,
 
1077
                           force_quick_range, false) < 0;
 
1078
}
 
1079
 
 
1080
 
 
1081
bool SQL_SELECT::skip_record()
 
1082
{
 
1083
  return cond ? cond->val_int() == 0 : 0;
 
1084
}
 
1085
 
 
1086
 
1061
1087
QUICK_SELECT_I::QUICK_SELECT_I()
1062
1088
  :max_used_key_length(0),
1063
1089
   used_key_parts(0)
1064
1090
{}
1065
1091
 
1066
 
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, Table *table, uint32_t key_nr,
 
1092
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1067
1093
                                       bool no_alloc, MEM_ROOT *parent_alloc,
1068
1094
                                       bool *create_error)
1069
1095
  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1077
1103
  key_part_info= head->key_info[index].key_part;
1078
1104
  my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1079
1105
 
1080
 
  /* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1081
 
  mrr_buf_size= thd->variables.read_rnd_buff_size;
 
1106
  /* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
 
1107
  mrr_buf_size= session->variables.read_rnd_buff_size;
1082
1108
  mrr_buf_desc= NULL;
1083
1109
 
1084
1110
  if (!no_alloc && !parent_alloc)
1085
1111
  {
1086
1112
    // Allocates everything through the internal memroot
1087
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1088
 
    thd->mem_root= &alloc;
 
1113
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1114
    session->mem_root= &alloc;
1089
1115
  }
1090
1116
  else
1091
1117
    memset(&alloc, 0, sizeof(alloc));
1095
1121
  save_write_set= head->write_set;
1096
1122
 
1097
1123
  /* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1098
 
  if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1099
 
                                           MYF(MY_WME))))
 
1124
  if (!(bitmap= (my_bitmap_map*) malloc(head->s->column_bitmap_size)))
1100
1125
  {
1101
1126
    column_bitmap.bitmap= 0;
1102
1127
    *create_error= 1;
1127
1152
  if (!dont_free)
1128
1153
  {
1129
1154
    /* file is NULL for CPK scan on covering ROR-intersection */
1130
 
    if (file) 
 
1155
    if (file)
1131
1156
    {
1132
1157
      range_end();
1133
1158
      if (head->key_read)
1137
1162
      }
1138
1163
      if (free_file)
1139
1164
      {
1140
 
        file->ha_external_lock(current_thd, F_UNLCK);
 
1165
        file->ha_external_lock(current_session, F_UNLCK);
1141
1166
        file->close();
1142
1167
        delete file;
1143
1168
      }
1153
1178
}
1154
1179
 
1155
1180
 
1156
 
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
 
1181
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1157
1182
                                                   Table *table)
1158
 
  :pk_quick_select(NULL), thd(thd_param)
 
1183
  :pk_quick_select(NULL), session(session_param)
1159
1184
{
1160
1185
  index= MAX_KEY;
1161
1186
  head= table;
1162
1187
  memset(&read_record, 0, sizeof(read_record));
1163
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1188
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1164
1189
  return;
1165
1190
}
1166
1191
 
1167
1192
int QUICK_INDEX_MERGE_SELECT::init()
1168
1193
{
1169
 
  return(0);
 
1194
  return 0;
1170
1195
}
1171
1196
 
1172
1197
int QUICK_INDEX_MERGE_SELECT::reset()
1203
1228
}
1204
1229
 
1205
1230
 
1206
 
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
 
1231
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1207
1232
                                                       Table *table,
1208
1233
                                                       bool retrieve_full_rows,
1209
1234
                                                       MEM_ROOT *parent_alloc)
1210
 
  : cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
 
1235
  : cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1211
1236
    scans_inited(false)
1212
1237
{
1213
1238
  index= MAX_KEY;
1214
1239
  head= table;
1215
1240
  record= head->record[0];
1216
1241
  if (!parent_alloc)
1217
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1242
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1218
1243
  else
1219
1244
    memset(&alloc, 0, sizeof(MEM_ROOT));
1220
1245
  last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1264
1289
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1265
1290
{
1266
1291
  handler *save_file= file, *org_file;
1267
 
  THD *thd;
 
1292
  Session *session;
1268
1293
 
1269
1294
  in_ror_merged_scan= 1;
1270
1295
  if (reuse_handler)
1271
1296
  {
1272
1297
    if (init() || reset())
1273
1298
    {
1274
 
      return(1);
 
1299
      return 0;
1275
1300
    }
1276
1301
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1277
1302
    goto end;
1281
1306
  if (free_file)
1282
1307
  {
1283
1308
    /* already have own 'handler' object. */
1284
 
    return(0);
 
1309
    return 0;
1285
1310
  }
1286
1311
 
1287
 
  thd= head->in_use;
1288
 
  if (!(file= head->file->clone(thd->mem_root)))
 
1312
  session= head->in_use;
 
1313
  if (!(file= head->file->clone(session->mem_root)))
1289
1314
  {
1290
 
    /* 
 
1315
    /*
1291
1316
      Manually set the error flag. Note: there seems to be quite a few
1292
1317
      places where a failure could cause the server to "hang" the client by
1293
 
      sending no response to a query. ATM those are not real errors because 
1294
 
      the storage engine calls in question happen to never fail with the 
1295
 
      existing storage engines. 
 
1318
      sending no response to a query. ATM those are not real errors because
 
1319
      the storage engine calls in question happen to never fail with the
 
1320
      existing storage engines.
1296
1321
    */
1297
1322
    my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1298
1323
    /* Caller will free the memory */
1301
1326
 
1302
1327
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1303
1328
 
1304
 
  if (file->ha_external_lock(thd, F_RDLCK))
 
1329
  if (file->ha_external_lock(session, F_RDLCK))
1305
1330
    goto failure;
1306
1331
 
1307
1332
  if (init() || reset())
1308
1333
  {
1309
 
    file->ha_external_lock(thd, F_UNLCK);
 
1334
    file->ha_external_lock(session, F_UNLCK);
1310
1335
    file->close();
1311
1336
    goto failure;
1312
1337
  }
1333
1358
  bitmap_copy(&column_bitmap, head->read_set);
1334
1359
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1335
1360
 
1336
 
  return(0);
 
1361
  return 0;
1337
1362
 
1338
1363
failure:
1339
1364
  head->column_bitmaps_set(save_read_set, save_write_set);
1340
1365
  delete file;
1341
1366
  file= save_file;
1342
 
  return(1);
 
1367
  return 0;
 
1368
}
 
1369
 
 
1370
 
 
1371
void QUICK_RANGE_SELECT::save_last_pos()
 
1372
{
 
1373
  file->position(record);
1343
1374
}
1344
1375
 
1345
1376
 
1368
1399
      selects.
1369
1400
    */
1370
1401
    if (quick->init_ror_merged_scan(true))
1371
 
      return(1);
 
1402
      return 0;
1372
1403
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1373
1404
  }
1374
1405
  while ((quick= quick_it++))
1375
1406
  {
1376
1407
    if (quick->init_ror_merged_scan(false))
1377
 
      return(1);
 
1408
      return 0;
1378
1409
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1379
1410
    /* All merged scans share the same record buffer in intersection. */
1380
1411
    quick->record= head->record[0];
1382
1413
 
1383
1414
  if (need_to_fetch_row && head->file->ha_rnd_init(1))
1384
1415
  {
1385
 
    return(1);
 
1416
    return 0;
1386
1417
  }
1387
 
  return(0);
 
1418
  return 0;
1388
1419
}
1389
1420
 
1390
1421
 
1400
1431
int QUICK_ROR_INTERSECT_SELECT::reset()
1401
1432
{
1402
1433
  if (!scans_inited && init_ror_merged_scan(true))
1403
 
    return(1);
 
1434
    return 0;
1404
1435
  scans_inited= true;
1405
1436
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1406
1437
  QUICK_RANGE_SELECT *quick;
1407
1438
  while ((quick= it++))
1408
1439
    quick->reset();
1409
 
  return(0);
 
1440
  return 0;
1410
1441
}
1411
1442
 
1412
1443
 
1442
1473
}
1443
1474
 
1444
1475
 
1445
 
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
 
1476
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1446
1477
                                               Table *table)
1447
 
  : thd(thd_param), scans_inited(false)
 
1478
  : session(session_param), scans_inited(false)
1448
1479
{
1449
1480
  index= MAX_KEY;
1450
1481
  head= table;
1451
1482
  rowid_length= table->file->ref_length;
1452
1483
  record= head->record[0];
1453
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1454
 
  thd_param->mem_root= &alloc;
 
1484
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1485
  session_param->mem_root= &alloc;
1455
1486
}
1456
1487
 
 
1488
/*
 
1489
 * Function object that is used as the comparison function
 
1490
 * for the priority queue in the QUICK_ROR_UNION_SELECT
 
1491
 * class.
 
1492
 */
 
1493
class compare_functor
 
1494
{
 
1495
  QUICK_ROR_UNION_SELECT *self;
 
1496
  public:
 
1497
  compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
 
1498
    : self(in_arg) { }
 
1499
  inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
 
1500
  {
 
1501
    int val= self->head->file->cmp_ref(i->last_rowid,
 
1502
                                       j->last_rowid);
 
1503
    return (val >= 0);
 
1504
  }
 
1505
};
1457
1506
 
1458
1507
/*
1459
1508
  Do post-constructor initialization.
1467
1516
 
1468
1517
int QUICK_ROR_UNION_SELECT::init()
1469
1518
{
1470
 
  if (init_queue(&queue, quick_selects.elements, 0,
1471
 
                 false , QUICK_ROR_UNION_SELECT::queue_cmp,
1472
 
                 (void*) this))
1473
 
  {
1474
 
    memset(&queue, 0, sizeof(QUEUE));
1475
 
    return(1);
1476
 
  }
1477
 
 
 
1519
  queue= 
 
1520
    new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
1478
1521
  if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1479
 
    return(1);
 
1522
    return 0;
1480
1523
  prev_rowid= cur_rowid + head->file->ref_length;
1481
 
  return(0);
 
1524
  return 0;
1482
1525
}
1483
1526
 
1484
1527
 
1493
1536
      val2  Second merged select
1494
1537
*/
1495
1538
 
1496
 
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
 
1539
int quick_ror_union_select_queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1497
1540
{
1498
1541
  QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1499
1542
  return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1522
1565
    while ((quick= it++))
1523
1566
    {
1524
1567
      if (quick->init_ror_merged_scan(false))
1525
 
        return(1);
 
1568
        return 0;
1526
1569
    }
1527
1570
    scans_inited= true;
1528
1571
  }
1529
 
  queue_remove_all(&queue);
 
1572
  while (!queue->empty())
 
1573
    queue->pop();
1530
1574
  /*
1531
1575
    Initialize scans for merged quick selects and put all merged quick
1532
1576
    selects into the queue.
1535
1579
  while ((quick= it++))
1536
1580
  {
1537
1581
    if (quick->reset())
1538
 
      return(1);
 
1582
      return 0;
1539
1583
    if ((error= quick->get_next()))
1540
1584
    {
1541
1585
      if (error == HA_ERR_END_OF_FILE)
1543
1587
      return(error);
1544
1588
    }
1545
1589
    quick->save_last_pos();
1546
 
    queue_insert(&queue, (unsigned char*)quick);
 
1590
    queue->push(quick);
1547
1591
  }
1548
1592
 
1549
1593
  if (head->file->ha_rnd_init(1))
1550
1594
  {
1551
 
    return(1);
 
1595
    return 0;
1552
1596
  }
1553
1597
 
1554
 
  return(0);
 
1598
  return 0;
1555
1599
}
1556
1600
 
1557
1601
 
1563
1607
 
1564
1608
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1565
1609
{
1566
 
  delete_queue(&queue);
 
1610
  while (!queue->empty())
 
1611
    queue->pop();
 
1612
  delete queue;
1567
1613
  quick_selects.delete_elements();
1568
1614
  if (head->file->inited != handler::NONE)
1569
1615
    head->file->ha_rnd_end();
1623
1669
  left=right= &null_element;
1624
1670
}
1625
1671
 
1626
 
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, 
 
1672
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1627
1673
                        SEL_ARG **next_arg)
1628
1674
{
1629
1675
  SEL_ARG *tmp;
1759
1805
      limit  Number of records that will be retrieved
1760
1806
 
1761
1807
  DESCRIPTION
1762
 
    Find the best index that allows to retrieve first #limit records in the 
 
1808
    Find the best index that allows to retrieve first #limit records in the
1763
1809
    given order cheaper then one would retrieve them using full table scan.
1764
1810
 
1765
1811
  IMPLEMENTATION
1783
1829
  uint32_t idx;
1784
1830
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
1785
1831
  order_st *ord;
1786
 
  
 
1832
 
1787
1833
  for (ord= order; ord; ord= ord->next)
1788
1834
    if (!ord->asc)
1789
1835
      return MAX_KEY;
1795
1841
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
1796
1842
    uint32_t n_parts=  table->key_info[idx].key_parts;
1797
1843
    uint32_t partno= 0;
1798
 
    
1799
 
    /* 
1800
 
      The below check is sufficient considering we now have either BTREE 
1801
 
      indexes (records are returned in order for any index prefix) or HASH 
 
1844
 
 
1845
    /*
 
1846
      The below check is sufficient considering we now have either BTREE
 
1847
      indexes (records are returned in order for any index prefix) or HASH
1802
1848
      indexes (records are not returned in order for any index prefix).
1803
1849
    */
1804
1850
    if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
1810
1856
           ((Item_field*)item)->field->eq(keyinfo[partno].field)))
1811
1857
        break;
1812
1858
    }
1813
 
    
 
1859
 
1814
1860
    if (!ord && table->key_info[idx].key_length < match_key_len)
1815
1861
    {
1816
 
      /* 
 
1862
      /*
1817
1863
        Ok, the ordering is compatible and this key is shorter then
1818
1864
        previous match (we want shorter keys as we'll have to read fewer
1819
1865
        index pages for the same number of records)
1825
1871
 
1826
1872
  if (match_key != MAX_KEY)
1827
1873
  {
1828
 
    /* 
1829
 
      Found an index that allows records to be retrieved in the requested 
 
1874
    /*
 
1875
      Found an index that allows records to be retrieved in the requested
1830
1876
      order. Now we'll check if using the index is cheaper then doing a table
1831
1877
      scan.
1832
1878
    */
1881
1927
 
1882
1928
  /* Table read plans are allocated on MEM_ROOT and are never deleted */
1883
1929
  static void *operator new(size_t size, MEM_ROOT *mem_root)
1884
 
  { return (void*) alloc_root(mem_root, (uint) size); }
1885
 
  static void operator delete(void *ptr __attribute__((unused)),
1886
 
                              size_t size __attribute__((unused)))
 
1930
  { return (void*) alloc_root(mem_root, (uint32_t) size); }
 
1931
  static void operator delete(void *, size_t)
1887
1932
    { TRASH(ptr, size); }
1888
 
  static void operator delete(void *ptr __attribute__((unused)),
1889
 
                              MEM_ROOT *mem_root __attribute__((unused)))
 
1933
  static void operator delete(void *, MEM_ROOT *)
1890
1934
    { /* Never called */ }
1891
1935
  virtual ~TABLE_READ_PLAN() {}               /* Remove gcc warning */
1892
1936
 
1909
1953
public:
1910
1954
  SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1911
1955
  uint32_t     key_idx; /* key number in PARAM::key */
1912
 
  uint32_t     mrr_flags; 
 
1956
  uint32_t     mrr_flags;
1913
1957
  uint32_t     mrr_buf_size;
1914
1958
 
1915
1959
  TRP_RANGE(SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1917
1961
  {}
1918
1962
  virtual ~TRP_RANGE() {}                     /* Remove gcc warning */
1919
1963
 
1920
 
  QUICK_SELECT_I *make_quick(PARAM *param,
1921
 
                             bool retrieve_full_rows __attribute__((unused)),
1922
 
                             MEM_ROOT *parent_alloc)
 
1964
  QUICK_SELECT_I *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1923
1965
  {
1924
1966
    QUICK_RANGE_SELECT *quick;
1925
1967
    if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
1928
1970
      quick->records= records;
1929
1971
      quick->read_time= read_cost;
1930
1972
    }
1931
 
    return(quick);
 
1973
    return quick;
1932
1974
  }
1933
1975
};
1934
1976
 
1989
2031
 
1990
2032
 
1991
2033
/*
1992
 
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan. 
 
2034
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
1993
2035
*/
1994
2036
 
1995
2037
class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN
2085
2127
 
2086
2128
  SYNOPSIS
2087
2129
    SQL_SELECT::test_quick_select()
2088
 
      thd               Current thread
 
2130
      session               Current thread
2089
2131
      keys_to_use       Keys to use for range retrieval
2090
2132
      prev_tables       Tables assumed to be already read when the scan is
2091
2133
                        performed (but not read at the moment of this call)
2105
2147
 
2106
2148
  IMPLEMENTATION
2107
2149
    quick_condition_rows value is obtained as follows:
2108
 
      
 
2150
 
2109
2151
      It is a minimum of E(#output rows) for all considered table access
2110
2152
      methods (range and index_merge accesses over various indexes).
2111
 
    
 
2153
 
2112
2154
    The obtained value is not a true E(#rows that satisfy table condition)
2113
2155
    but rather a pessimistic estimate. To obtain a true E(#...) one would
2114
2156
    need to combine estimates of various access methods, taking into account
2115
2157
    correlations between sets of rows they will return.
2116
 
    
 
2158
 
2117
2159
    For example, if values of tbl.key1 and tbl.key2 are independent (a right
2118
2160
    assumption if we have no information about their correlation) then the
2119
2161
    correct estimate will be:
2120
 
    
2121
 
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) = 
 
2162
 
 
2163
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
2122
2164
      = E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)
2123
2165
 
2124
 
    which is smaller than 
2125
 
      
 
2166
    which is smaller than
 
2167
 
2126
2168
       MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))
2127
2169
 
2128
2170
    which is currently produced.
2129
2171
 
2130
2172
  TODO
2131
2173
   * Change the value returned in quick_condition_rows from a pessimistic
2132
 
     estimate to true E(#rows that satisfy table condition). 
2133
 
     (we can re-use some of E(#rows) calcuation code from index_merge/intersection 
 
2174
     estimate to true E(#rows that satisfy table condition).
 
2175
     (we can re-use some of E(#rows) calcuation code from index_merge/intersection
2134
2176
      for this)
2135
 
   
 
2177
 
2136
2178
   * Check if this function really needs to modify keys_to_use, and change the
2137
2179
     code to pass it by reference if it doesn't.
2138
2180
 
2146
2188
    1 if found usable ranges and quick select has been successfully created.
2147
2189
*/
2148
2190
 
2149
 
int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
 
2191
int SQL_SELECT::test_quick_select(Session *session, key_map keys_to_use,
2150
2192
                                  table_map prev_tables,
2151
 
                                  ha_rows limit, bool force_quick_range, 
 
2193
                                  ha_rows limit, bool force_quick_range,
2152
2194
                                  bool ordered_output)
2153
2195
{
2154
2196
  uint32_t idx;
2158
2200
  needed_reg.clear_all();
2159
2201
  quick_keys.clear_all();
2160
2202
  if (keys_to_use.is_clear_all())
2161
 
    return(0);
 
2203
    return 0;
2162
2204
  records= head->file->stats.records;
2163
2205
  if (!records)
2164
2206
    records++;                                  /* purecov: inspected */
2169
2211
  if (limit < records)
2170
2212
    read_time= (double) records + scan_time + 1; // Force to use index
2171
2213
  else if (read_time <= 2.0 && !force_quick_range)
2172
 
    return(0);                          /* No need for quick select */
 
2214
    return 0;                           /* No need for quick select */
2173
2215
 
2174
2216
  keys_to_use.intersect(head->keys_in_use_for_query);
2175
2217
  if (!keys_to_use.is_clear_all())
2180
2222
    KEY *key_info;
2181
2223
    PARAM param;
2182
2224
 
2183
 
    if (check_stack_overrun(thd, 2*STACK_MIN_SIZE, NULL))
2184
 
      return(0);                           // Fatal error flag is set
 
2225
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
 
2226
      return 0;                           // Fatal error flag is set
2185
2227
 
2186
2228
    /* set up parameter that is passed to all functions */
2187
 
    param.thd= thd;
 
2229
    param.session= session;
2188
2230
    param.baseflag= head->file->ha_table_flags();
2189
2231
    param.prev_tables=prev_tables | const_tables;
2190
2232
    param.read_tables=read_tables;
2192
2234
    param.table=head;
2193
2235
    param.keys=0;
2194
2236
    param.mem_root= &alloc;
2195
 
    param.old_root= thd->mem_root;
 
2237
    param.old_root= session->mem_root;
2196
2238
    param.needed_reg= &needed_reg;
2197
2239
    param.imerge_cost_buff_size= 0;
2198
2240
    param.using_real_indexes= true;
2199
2241
    param.remove_jump_scans= true;
2200
2242
    param.force_default_mrr= ordered_output;
2201
2243
 
2202
 
    thd->no_errors=1;                           // Don't warn about NULL
2203
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
2244
    session->no_errors=1;                               // Don't warn about NULL
 
2245
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
2204
2246
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
2205
2247
                                                  sizeof(KEY_PART)*
2206
2248
                                                  head->s->key_parts)) ||
2207
2249
        fill_used_fields_bitmap(&param))
2208
2250
    {
2209
 
      thd->no_errors=0;
 
2251
      session->no_errors=0;
2210
2252
      free_root(&alloc,MYF(0));                 // Return memory & allocator
2211
 
      return(0);                                // Can't use range
 
2253
      return 0;                         // Can't use range
2212
2254
    }
2213
2255
    key_parts= param.key_parts;
2214
 
    thd->mem_root= &alloc;
 
2256
    session->mem_root= &alloc;
2215
2257
 
2216
2258
    /*
2217
2259
      Make an array with description of all key parts of all table keys.
2248
2290
    if (!head->covering_keys.is_clear_all())
2249
2291
    {
2250
2292
      int key_for_use= head->find_shortest_key(&head->covering_keys);
2251
 
      double key_read_time= 
2252
 
        param.table->file->index_only_read_time(key_for_use, 
 
2293
      double key_read_time=
 
2294
        param.table->file->index_only_read_time(key_for_use,
2253
2295
                                                rows2double(records)) +
2254
2296
        (double) records / TIME_FOR_COMPARE;
2255
2297
      if (key_read_time < read_time)
2320
2362
          objects are not allowed so don't use ROR-intersection for
2321
2363
          table deletes.
2322
2364
        */
2323
 
        if ((thd->lex->sql_command != SQLCOM_DELETE))
 
2365
        if ((session->lex->sql_command != SQLCOM_DELETE))
2324
2366
        {
2325
2367
          /*
2326
2368
            Get best non-covering ROR-intersection plan and prepare data for
2352
2394
        {
2353
2395
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
2354
2396
          if (new_conj_trp)
2355
 
            set_if_smaller(param.table->quick_condition_rows, 
 
2397
            set_if_smaller(param.table->quick_condition_rows,
2356
2398
                           new_conj_trp->records);
2357
2399
          if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
2358
2400
                                 best_conj_trp->read_cost))
2363
2405
      }
2364
2406
    }
2365
2407
 
2366
 
    thd->mem_root= param.old_root;
 
2408
    session->mem_root= param.old_root;
2367
2409
 
2368
2410
    /* If we got a read plan, create a quick select from it. */
2369
2411
    if (best_trp)
2378
2420
 
2379
2421
  free_mem:
2380
2422
    free_root(&alloc,MYF(0));                   // Return memory & allocator
2381
 
    thd->mem_root= param.old_root;
2382
 
    thd->no_errors=0;
 
2423
    session->mem_root= param.old_root;
 
2424
    session->no_errors=0;
2383
2425
  }
2384
2426
 
2385
2427
  /*
2481
2523
  if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
2482
2524
                                             sizeof(TRP_RANGE*)*
2483
2525
                                             n_child_scans)))
2484
 
    return(NULL);
 
2526
    return NULL;
2485
2527
  /*
2486
2528
    Collect best 'range' scan for each of disjuncts, and, while doing so,
2487
2529
    analyze possibility of ROR scans. Also calculate some values needed by
2526
2568
      Bail out if it is obvious that both index_merge and ROR-union will be
2527
2569
      more expensive
2528
2570
    */
2529
 
    return(NULL);
 
2571
    return NULL;
2530
2572
  }
2531
2573
  if (all_scans_rors)
2532
2574
  {
2545
2587
  /* Calculate cost(rowid_to_row_scan) */
2546
2588
  {
2547
2589
    COST_VECT sweep_cost;
2548
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2590
    JOIN *join= param->session->lex->select_lex.join;
2549
2591
    bool is_interrupted= test(join && join->tables == 1);
2550
2592
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
2551
2593
                        &sweep_cost);
2558
2600
  unique_calc_buff_size=
2559
2601
    Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
2560
2602
                                    param->table->file->ref_length,
2561
 
                                    param->thd->variables.sortbuff_size);
 
2603
                                    param->session->variables.sortbuff_size);
2562
2604
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
2563
2605
  {
2564
2606
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
2565
2607
                                                     unique_calc_buff_size)))
2566
 
      return(NULL);
 
2608
      return NULL;
2567
2609
    param->imerge_cost_buff_size= unique_calc_buff_size;
2568
2610
  }
2569
2611
 
2570
2612
  imerge_cost +=
2571
 
    Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records,
 
2613
    Unique::get_use_cost(param->imerge_cost_buff, (uint32_t)non_cpk_scan_records,
2572
2614
                         param->table->file->ref_length,
2573
 
                         param->thd->variables.sortbuff_size);
 
2615
                         param->session->variables.sortbuff_size);
2574
2616
  if (imerge_cost < read_time)
2575
2617
  {
2576
2618
    if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE))
2586
2628
  }
2587
2629
 
2588
2630
build_ror_index_merge:
2589
 
  if (!all_scans_ror_able || param->thd->lex->sql_command == SQLCOM_DELETE)
 
2631
  if (!all_scans_ror_able || param->session->lex->sql_command == SQLCOM_DELETE)
2590
2632
    return(imerge_trp);
2591
2633
 
2592
2634
  /* Ok, it is possible to build a ROR-union, try it. */
2661
2703
  double roru_total_cost;
2662
2704
  {
2663
2705
    COST_VECT sweep_cost;
2664
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2706
    JOIN *join= param->session->lex->select_lex.join;
2665
2707
    bool is_interrupted= test(join && join->tables == 1);
2666
2708
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
2667
2709
                        &sweep_cost);
2735
2777
 
2736
2778
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
2737
2779
                                             sizeof(ROR_SCAN_INFO))))
2738
 
    return(NULL);
 
2780
    return NULL;
2739
2781
 
2740
2782
  ror_scan->idx= idx;
2741
2783
  ror_scan->keynr= keynr= param->real_keynr[idx];
2746
2788
 
2747
2789
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
2748
2790
                                                param->fields_bitmap_size)))
2749
 
    return(NULL);
 
2791
    return NULL;
2750
2792
 
2751
2793
  if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,
2752
2794
                  param->table->s->fields, false))
2753
 
    return(NULL);
 
2795
    return NULL;
2754
2796
  bitmap_clear_all(&ror_scan->covered_fields);
2755
2797
 
2756
2798
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2881
2923
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
2882
2924
{
2883
2925
  dst->param= src->param;
2884
 
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap, 
 
2926
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
2885
2927
         no_bytes_in_map(&src->covered_fields));
2886
2928
  dst->out_rows= src->out_rows;
2887
2929
  dst->is_covering= src->is_covering;
2896
2938
 
2897
2939
  SYNOPSIS
2898
2940
    ror_scan_selectivity()
2899
 
      info  ROR-interection 
 
2941
      info  ROR-interection
2900
2942
      scan  ROR scan
2901
 
      
 
2943
 
2902
2944
  NOTES
2903
2945
    Suppose we have a condition on several keys
2904
2946
    cond=k_11=c_11 AND k_12=c_12 AND ...  // parts of first key
2981
3023
    Selectivity of given ROR scan.
2982
3024
*/
2983
3025
 
2984
 
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info, 
 
3026
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
2985
3027
                                   const ROR_SCAN_INFO *scan)
2986
3028
{
2987
3029
  double selectivity_mult= 1.0;
3083
3125
 
3084
3126
    E(rows_to_retrieve) = #rows_in_table * ror_scan_selectivity(null, scan1) *
3085
3127
                           ror_scan_selectivity({scan1}, scan2) * ... *
3086
 
                           ror_scan_selectivity({scan1,...}, scanN). 
 
3128
                           ror_scan_selectivity({scan1,...}, scanN).
3087
3129
  RETURN
3088
3130
    true   ROR scan added to ROR-intersection, cost updated.
3089
3131
    false  It doesn't make sense to add this ROR scan to this ROR-intersection.
3098
3140
  if (selectivity_mult == 1.0)
3099
3141
  {
3100
3142
    /* Don't add this scan if it doesn't improve selectivity. */
3101
 
    return(false);
 
3143
    return false;
3102
3144
  }
3103
 
  
 
3145
 
3104
3146
  info->out_rows *= selectivity_mult;
3105
 
  
 
3147
 
3106
3148
  if (is_cpk_scan)
3107
3149
  {
3108
3150
    /*
3109
 
      CPK scan is used to filter out rows. We apply filtering for 
 
3151
      CPK scan is used to filter out rows. We apply filtering for
3110
3152
      each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
3111
3153
      per check this gives us:
3112
3154
    */
3113
 
    info->index_scan_costs += rows2double(info->index_records) / 
 
3155
    info->index_scan_costs += rows2double(info->index_records) /
3114
3156
                              TIME_FOR_COMPARE_ROWID;
3115
3157
  }
3116
3158
  else
3129
3171
  if (!info->is_covering)
3130
3172
  {
3131
3173
    COST_VECT sweep_cost;
3132
 
    JOIN *join= info->param->thd->lex->select_lex.join;
 
3174
    JOIN *join= info->param->session->lex->select_lex.join;
3133
3175
    bool is_interrupted= test(join && join->tables == 1);
3134
3176
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
3135
3177
                        is_interrupted, &sweep_cost);
3136
3178
    info->total_cost += sweep_cost.total_cost();
3137
3179
  }
3138
 
  return(true);
 
3180
  return true;
3139
3181
}
3140
3182
 
3141
3183
 
3155
3197
 
3156
3198
  NOTES
3157
3199
    get_key_scans_params must be called before this function can be called.
3158
 
    
 
3200
 
3159
3201
    When this function is called by ROR-union construction algorithm it
3160
3202
    assumes it is building an uncovered ROR-intersection (and thus # of full
3161
3203
    records to be retrieved is wrong here). This is a hack.
3177
3219
        firstR= R - first(R);
3178
3220
        if (!selectivity(S + firstR < selectivity(S)))
3179
3221
          continue;
3180
 
          
 
3222
 
3181
3223
        S= S + first(R);
3182
3224
        if (cost(S) < min_cost)
3183
3225
        {
3212
3254
  double min_cost= DBL_MAX;
3213
3255
 
3214
3256
  if ((tree->n_ror_scans < 2) || !param->table->file->stats.records)
3215
 
    return(NULL);
 
3257
    return NULL;
3216
3258
 
3217
3259
  /*
3218
 
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of 
 
3260
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
3219
3261
    them. Also find and save clustered PK scan if there is one.
3220
3262
  */
3221
3263
  ROR_SCAN_INFO **cur_ror_scan;
3271
3313
 
3272
3314
  /* Create and incrementally update ROR intersection. */
3273
3315
  ROR_INTERSECT_INFO *intersect, *intersect_best;
3274
 
  if (!(intersect= ror_intersect_init(param)) || 
 
3316
  if (!(intersect= ror_intersect_init(param)) ||
3275
3317
      !(intersect_best= ror_intersect_init(param)))
3276
3318
    return NULL;
3277
3319
 
3287
3329
      cur_ror_scan++;
3288
3330
      continue;
3289
3331
    }
3290
 
    
 
3332
 
3291
3333
    *(intersect_scans_end++)= *(cur_ror_scan++);
3292
3334
 
3293
3335
    if (intersect->total_cost < min_cost)
3301
3343
 
3302
3344
  if (intersect_scans_best == intersect_scans)
3303
3345
  {
3304
 
    return(NULL);
 
3346
    return NULL;
3305
3347
  }
3306
 
    
 
3348
 
3307
3349
  print_ror_scans_arr(param->table,
3308
3350
                                          "best ROR-intersection",
3309
3351
                                          intersect_scans,
3315
3357
 
3316
3358
  /*
3317
3359
    Ok, found the best ROR-intersection of non-CPK key scans.
3318
 
    Check if we should add a CPK scan. If the obtained ROR-intersection is 
 
3360
    Check if we should add a CPK scan. If the obtained ROR-intersection is
3319
3361
    covering, it doesn't make sense to add CPK scan.
3320
3362
  */
3321
3363
  if (cpk_scan && !intersect->is_covering)
3322
3364
  {
3323
 
    if (ror_intersect_add(intersect, cpk_scan, true) && 
 
3365
    if (ror_intersect_add(intersect, cpk_scan, true) &&
3324
3366
        (intersect->total_cost < min_cost))
3325
3367
    {
3326
3368
      cpk_scan_used= true;
3337
3379
    if (!(trp->first_scan=
3338
3380
           (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3339
3381
                                       sizeof(ROR_SCAN_INFO*)*best_num)))
3340
 
      return(NULL);
 
3382
      return NULL;
3341
3383
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
3342
3384
    trp->last_scan=  trp->first_scan + best_num;
3343
3385
    trp->is_covering= intersect_best->is_covering;
3409
3451
  ror_scan_mark= tree->ror_scans;
3410
3452
 
3411
3453
  MY_BITMAP *covered_fields= &param->tmp_covered_fields;
3412
 
  if (!covered_fields->bitmap) 
 
3454
  if (!covered_fields->bitmap)
3413
3455
    covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3414
3456
                                               param->fields_bitmap_size);
3415
3457
  if (!covered_fields->bitmap ||
3416
3458
      bitmap_init(covered_fields, covered_fields->bitmap,
3417
3459
                  param->table->s->fields, false))
3418
 
    return(0);
 
3460
    return 0;
3419
3461
  bitmap_clear_all(covered_fields);
3420
3462
 
3421
3463
  double total_cost= 0.0f;
3453
3495
    total_cost += (*ror_scan_mark)->index_read_cost;
3454
3496
    records += (*ror_scan_mark)->records;
3455
3497
    if (total_cost > read_time)
3456
 
      return(NULL);
 
3498
      return NULL;
3457
3499
    /* F=F-covered by first(I) */
3458
3500
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3459
3501
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
3460
3502
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3461
 
  
 
3503
 
3462
3504
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
3463
 
    return(NULL);
 
3505
    return NULL;
3464
3506
 
3465
3507
  /*
3466
3508
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
3476
3518
                (TIME_FOR_COMPARE_ROWID * M_LN2);
3477
3519
 
3478
3520
  if (total_cost > read_time)
3479
 
    return(NULL);
 
3521
    return NULL;
3480
3522
 
3481
3523
  TRP_ROR_INTERSECT *trp;
3482
3524
  if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
3485
3527
  if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3486
3528
                                                     sizeof(ROR_SCAN_INFO*)*
3487
3529
                                                     best_num)))
3488
 
    return(NULL);
 
3530
    return NULL;
3489
3531
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
3490
3532
  trp->last_scan=  trp->first_scan + best_num;
3491
3533
  trp->is_covering= true;
3492
3534
  trp->read_cost= total_cost;
3493
3535
  trp->records= records;
3494
3536
  trp->cpk_scan= NULL;
3495
 
  set_if_smaller(param->table->quick_condition_rows, records); 
 
3537
  set_if_smaller(param->table->quick_condition_rows, records);
3496
3538
 
3497
3539
  return(trp);
3498
3540
}
3509
3551
                               (except for clustered PK indexes)
3510
3552
      update_tbl_stats         true <=> update table->quick_* with information
3511
3553
                               about range scans we've evaluated.
3512
 
      read_time                Maximum cost. i.e. don't create read plans with 
 
3554
      read_time                Maximum cost. i.e. don't create read plans with
3513
3555
                               cost > read_time.
3514
3556
 
3515
3557
  DESCRIPTION
3516
 
    Find the best "range" table read plan for given SEL_TREE. 
3517
 
    The side effects are 
 
3558
    Find the best "range" table read plan for given SEL_TREE.
 
3559
    The side effects are
3518
3560
     - tree->ror_scans is updated to indicate which scans are ROR scans.
3519
3561
     - if update_tbl_stats=true then table->quick_* is updated with info
3520
3562
       about every possible range scan.
3525
3567
*/
3526
3568
 
3527
3569
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
3528
 
                                       bool index_read_must_be_used, 
 
3570
                                       bool index_read_must_be_used,
3529
3571
                                       bool update_tbl_stats,
3530
3572
                                       double read_time)
3531
3573
{
3555
3597
          (*key)->maybe_flag)
3556
3598
        param->needed_reg->set_bit(keynr);
3557
3599
 
3558
 
      bool read_index_only= index_read_must_be_used || 
 
3600
      bool read_index_only= index_read_must_be_used ||
3559
3601
                            param->table->covering_keys.is_set(keynr);
3560
3602
 
3561
3603
      found_records= check_quick_select(param, idx, read_index_only, *key,
3596
3638
}
3597
3639
 
3598
3640
 
3599
 
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param,
3600
 
                                            bool retrieve_full_rows __attribute__((unused)),
3601
 
                                            MEM_ROOT *parent_alloc __attribute__((unused)))
 
3641
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
3602
3642
{
3603
3643
  QUICK_INDEX_MERGE_SELECT *quick_imerge;
3604
3644
  QUICK_RANGE_SELECT *quick;
3605
3645
  /* index_merge always retrieves full rows, ignore retrieve_full_rows */
3606
 
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->thd, param->table)))
 
3646
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->session, param->table)))
3607
3647
    return NULL;
3608
3648
 
3609
3649
  quick_imerge->records= records;
3632
3672
  MEM_ROOT *alloc;
3633
3673
 
3634
3674
  if ((quick_intrsect=
3635
 
         new QUICK_ROR_INTERSECT_SELECT(param->thd, param->table,
 
3675
         new QUICK_ROR_INTERSECT_SELECT(param->session, param->table,
3636
3676
                                        (retrieve_full_rows? (!is_covering) :
3637
3677
                                         false),
3638
3678
                                        parent_alloc)))
3650
3690
          quick_intrsect->push_quick_back(quick))
3651
3691
      {
3652
3692
        delete quick_intrsect;
3653
 
        return(NULL);
 
3693
        return NULL;
3654
3694
      }
3655
3695
    }
3656
3696
    if (cpk_scan)
3661
3701
                                    0, alloc)))
3662
3702
      {
3663
3703
        delete quick_intrsect;
3664
 
        return(NULL);
 
3704
        return NULL;
3665
3705
      }
3666
 
      quick->file= NULL; 
 
3706
      quick->file= NULL;
3667
3707
      quick_intrsect->cpk_quick= quick;
3668
3708
    }
3669
3709
    quick_intrsect->records= records;
3673
3713
}
3674
3714
 
3675
3715
 
3676
 
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param,
3677
 
                                          bool retrieve_full_rows __attribute__((unused)),
3678
 
                                          MEM_ROOT *parent_alloc __attribute__((unused)))
 
3716
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
3679
3717
{
3680
3718
  QUICK_ROR_UNION_SELECT *quick_roru;
3681
3719
  TABLE_READ_PLAN **scan;
3684
3722
    It is impossible to construct a ROR-union that will not retrieve full
3685
3723
    rows, ignore retrieve_full_rows parameter.
3686
3724
  */
3687
 
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->thd, param->table)))
 
3725
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->session, param->table)))
3688
3726
  {
3689
3727
    for (scan= first_ror; scan != last_ror; scan++)
3690
3728
    {
3691
3729
      if (!(quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||
3692
3730
          quick_roru->push_quick_back(quick))
3693
 
        return(NULL);
 
3731
        return NULL;
3694
3732
    }
3695
3733
    quick_roru->records= records;
3696
3734
    quick_roru->read_time= read_cost;
3701
3739
 
3702
3740
/*
3703
3741
  Build a SEL_TREE for <> or NOT BETWEEN predicate
3704
 
 
 
3742
 
3705
3743
  SYNOPSIS
3706
3744
    get_ne_mm_tree()
3707
3745
      param       PARAM from SQL_SELECT::test_quick_select
3711
3749
      gt_value    constant that field should be greaterr
3712
3750
      cmp_type    compare type for the field
3713
3751
 
3714
 
  RETURN 
 
3752
  RETURN
3715
3753
    #  Pointer to tree built tree
3716
3754
    0  on error
3717
3755
*/
3718
3756
 
3719
 
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3757
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3720
3758
                                Field *field,
3721
3759
                                Item *lt_value, Item *gt_value,
3722
3760
                                Item_result cmp_type)
3732
3770
  }
3733
3771
  return tree;
3734
3772
}
3735
 
   
 
3773
 
3736
3774
 
3737
3775
/*
3738
3776
  Build a SEL_TREE for a simple predicate
3739
 
 
 
3777
 
3740
3778
  SYNOPSIS
3741
3779
    get_func_mm_tree()
3742
3780
      param       PARAM from SQL_SELECT::test_quick_select
3745
3783
      value       constant in the predicate
3746
3784
      cmp_type    compare type for the field
3747
3785
      inv         true <> NOT cond_func is considered
3748
 
                  (makes sense only when cond_func is BETWEEN or IN) 
 
3786
                  (makes sense only when cond_func is BETWEEN or IN)
3749
3787
 
3750
 
  RETURN 
 
3788
  RETURN
3751
3789
    Pointer to the tree built tree
3752
3790
*/
3753
3791
 
3754
 
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3792
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3755
3793
                                  Field *field, Item *value,
3756
3794
                                  Item_result cmp_type, bool inv)
3757
3795
{
3805
3843
      so we check it here to avoid unnecessary work.
3806
3844
    */
3807
3845
    if (!func->arg_types_compatible)
3808
 
      break;     
 
3846
      break;
3809
3847
 
3810
3848
    if (inv)
3811
3849
    {
3813
3851
      {
3814
3852
        /*
3815
3853
          We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
3816
 
          where c{i} are constants. Our goal is to produce a SEL_TREE that 
 
3854
          where c{i} are constants. Our goal is to produce a SEL_TREE that
3817
3855
          represents intervals:
3818
 
          
 
3856
 
3819
3857
          ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ...    (*)
3820
 
          
 
3858
 
3821
3859
          where $MIN is either "-inf" or NULL.
3822
 
          
 
3860
 
3823
3861
          The most straightforward way to produce it is to convert NOT IN
3824
3862
          into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
3825
3863
          analyzer to build SEL_TREE from that. The problem is that the
3829
3867
 
3830
3868
          Another problem with big lists like (*) is that a big list is
3831
3869
          unlikely to produce a good "range" access, while considering that
3832
 
          range access will require expensive CPU calculations (and for 
 
3870
          range access will require expensive CPU calculations (and for
3833
3871
          MyISAM even index accesses). In short, big NOT IN lists are rarely
3834
3872
          worth analyzing.
3835
3873
 
3840
3878
        */
3841
3879
#define NOT_IN_IGNORE_THRESHOLD 1000
3842
3880
        MEM_ROOT *tmp_root= param->mem_root;
3843
 
        param->thd->mem_root= param->old_root;
3844
 
        /* 
 
3881
        param->session->mem_root= param->old_root;
 
3882
        /*
3845
3883
          Create one Item_type constant object. We'll need it as
3846
3884
          get_mm_parts only accepts constant values wrapped in Item_Type
3847
3885
          objects.
3848
3886
          We create the Item on param->mem_root which points to
3849
 
          per-statement mem_root (while thd->mem_root is currently pointing
 
3887
          per-statement mem_root (while session->mem_root is currently pointing
3850
3888
          to mem_root local to range optimizer).
3851
3889
        */
3852
3890
        Item *value_item= func->array->create_item();
3853
 
        param->thd->mem_root= tmp_root;
 
3891
        param->session->mem_root= tmp_root;
3854
3892
 
3855
3893
        if (func->array->count > NOT_IN_IGNORE_THRESHOLD || !value_item)
3856
3894
          break;
3857
3895
 
3858
3896
        /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
3859
3897
        uint32_t i=0;
3860
 
        do 
 
3898
        do
3861
3899
        {
3862
3900
          func->array->value_to_item(i, value_item);
3863
3901
          tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
3900
3938
                new_interval->min_flag= NEAR_MIN;
3901
3939
              }
3902
3940
            }
3903
 
            /* 
 
3941
            /*
3904
3942
              The following doesn't try to allocate memory so no need to
3905
3943
              check for NULL.
3906
3944
            */
3907
3945
            tree= tree_or(param, tree, tree2);
3908
3946
          }
3909
3947
        }
3910
 
        
 
3948
 
3911
3949
        if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
3912
3950
        {
3913
 
          /* 
3914
 
            Get the SEL_TREE for the last "c_last < X < +inf" interval 
 
3951
          /*
 
3952
            Get the SEL_TREE for the last "c_last < X < +inf" interval
3915
3953
            (value_item cotains c_last already)
3916
3954
          */
3917
3955
          tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
3930
3968
          for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3931
3969
               arg < end ; arg++)
3932
3970
          {
3933
 
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
 
3971
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
3934
3972
                                                        *arg, *arg, cmp_type));
3935
3973
          }
3936
3974
        }
3937
3975
      }
3938
3976
    }
3939
3977
    else
3940
 
    {    
 
3978
    {
3941
3979
      tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
3942
3980
                         func->arguments()[1], cmp_type);
3943
3981
      if (tree)
3946
3984
        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3947
3985
             arg < end ; arg++)
3948
3986
        {
3949
 
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 
 
3987
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3950
3988
                                                  Item_func::EQ_FUNC,
3951
3989
                                                  *arg, cmp_type));
3952
3990
        }
3954
3992
    }
3955
3993
    break;
3956
3994
  }
3957
 
  default: 
 
3995
  default:
3958
3996
  {
3959
 
    /* 
 
3997
    /*
3960
3998
       Here the function for the following predicates are processed:
3961
3999
       <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL.
3962
4000
       If the predicate is of the form (value op field) it is handled
3976
4014
 
3977
4015
/*
3978
4016
  Build conjunction of all SEL_TREEs for a simple predicate applying equalities
3979
 
 
 
4017
 
3980
4018
  SYNOPSIS
3981
4019
    get_full_func_mm_tree()
3982
4020
      param       PARAM from SQL_SELECT::test_quick_select
3984
4022
      field_item  field in the predicate
3985
4023
      value       constant in the predicate
3986
4024
                  (for BETWEEN it contains the number of the field argument,
3987
 
                   for IN it's always 0) 
 
4025
                   for IN it's always 0)
3988
4026
      inv         true <> NOT cond_func is considered
3989
4027
                  (makes sense only when cond_func is BETWEEN or IN)
3990
4028
 
3993
4031
    c is a constant, the function builds a conjunction of all SEL_TREES that can
3994
4032
    be obtained by the substitution of f for all different fields equal to f.
3995
4033
 
3996
 
  NOTES  
 
4034
  NOTES
3997
4035
    If the WHERE condition contains a predicate (fi op c),
3998
4036
    then not only SELL_TREE for this predicate is built, but
3999
4037
    the trees for the results of substitution of fi for
4000
4038
    each fj belonging to the same multiple equality as fi
4001
4039
    are built as well.
4002
 
    E.g. for WHERE t1.a=t2.a AND t2.a > 10 
 
4040
    E.g. for WHERE t1.a=t2.a AND t2.a > 10
4003
4041
    a SEL_TREE for t2.a > 10 will be built for quick select from t2
4004
 
    and   
 
4042
    and
4005
4043
    a SEL_TREE for t1.a > 10 will be built for quick select from t1.
4006
4044
 
4007
4045
    A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
4010
4048
    Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed
4011
4049
    differently. It is considered as a conjuction of two SARGable
4012
4050
    predicates (f1i <= c) and (f2i <=c) and the function get_full_func_mm_tree
4013
 
    is called for each of them separately producing trees for 
4014
 
       AND j (f1j <=c ) and AND j (f2j <= c) 
 
4051
    is called for each of them separately producing trees for
 
4052
       AND j (f1j <=c ) and AND j (f2j <= c)
4015
4053
    After this these two trees are united in one conjunctive tree.
4016
4054
    It's easy to see that the same tree is obtained for
4017
4055
       AND j,k (f1j <=c AND f2k<=c)
4018
 
    which is equivalent to 
 
4056
    which is equivalent to
4019
4057
       AND j,k (c BETWEEN f1j AND f2k).
4020
4058
    The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i)
4021
4059
    which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the
4022
4060
    function get_full_func_mm_tree is called for (f1i > c) and (f2i < c)
4023
4061
    producing trees for AND j (f1j > c) and AND j (f2j < c). Then this two
4024
 
    trees are united in one OR-tree. The expression 
 
4062
    trees are united in one OR-tree. The expression
4025
4063
      (AND j (f1j > c) OR AND j (f2j < c)
4026
4064
    is equivalent to the expression
4027
 
      AND j,k (f1j > c OR f2k < c) 
4028
 
    which is just a translation of 
 
4065
      AND j,k (f1j > c OR f2k < c)
 
4066
    which is just a translation of
4029
4067
      AND j,k (c NOT BETWEEN f1j AND f2k)
4030
4068
 
4031
4069
    In the cases when one of the items f1, f2 is a constant c1 we do not create
4038
4076
    As to IN predicates only ones of the form (f IN (c1,...,cn)),
4039
4077
    where f1 is a field and c1,...,cn are constant, are considered as
4040
4078
    SARGable. We never try to narrow the index scan using predicates of
4041
 
    the form (c IN (c1,...,f,...,cn)). 
4042
 
      
4043
 
  RETURN 
 
4079
    the form (c IN (c1,...,f,...,cn)).
 
4080
 
 
4081
  RETURN
4044
4082
    Pointer to the tree representing the built conjunction of SEL_TREEs
4045
4083
*/
4046
4084
 
4047
4085
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
4048
4086
                                       Item_func *cond_func,
4049
 
                                       Item_field *field_item, Item *value, 
 
4087
                                       Item_field *field_item, Item *value,
4050
4088
                                       bool inv)
4051
4089
{
4052
4090
  SEL_TREE *tree= 0;
4106
4144
      while ((item=li++))
4107
4145
      {
4108
4146
        SEL_TREE *new_tree=get_mm_tree(param,item);
4109
 
        if (param->thd->is_fatal_error || 
 
4147
        if (param->session->is_fatal_error ||
4110
4148
            param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
4111
 
          return(0);    // out of memory
 
4149
          return 0;     // out of memory
4112
4150
        tree=tree_and(param,tree,new_tree);
4113
4151
        if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4114
4152
          break;
4124
4162
        {
4125
4163
          SEL_TREE *new_tree=get_mm_tree(param,item);
4126
4164
          if (!new_tree)
4127
 
            return(0);  // out of memory
 
4165
            return 0;   // out of memory
4128
4166
          tree=tree_or(param,tree,new_tree);
4129
4167
          if (!tree || tree->type == SEL_TREE::ALWAYS)
4130
4168
            break;
4137
4175
  if (cond->const_item())
4138
4176
  {
4139
4177
    /*
4140
 
      During the cond->val_int() evaluation we can come across a subselect 
4141
 
      item which may allocate memory on the thd->mem_root and assumes 
4142
 
      all the memory allocated has the same life span as the subselect 
 
4178
      During the cond->val_int() evaluation we can come across a subselect
 
4179
      item which may allocate memory on the session->mem_root and assumes
 
4180
      all the memory allocated has the same life span as the subselect
4143
4181
      item itself. So we have to restore the thread's mem_root here.
4144
4182
    */
4145
4183
    MEM_ROOT *tmp_root= param->mem_root;
4146
 
    param->thd->mem_root= param->old_root;
 
4184
    param->session->mem_root= param->old_root;
4147
4185
    tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
4148
4186
                            new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
4149
 
    param->thd->mem_root= tmp_root;
 
4187
    param->session->mem_root= tmp_root;
4150
4188
    return(tree);
4151
4189
  }
4152
4190
 
4158
4196
    ref_tables= cond->used_tables();
4159
4197
    if ((ref_tables & param->current_table) ||
4160
4198
        (ref_tables & ~(param->prev_tables | param->read_tables)))
4161
 
      return(0);
 
4199
      return 0;
4162
4200
    return(new SEL_TREE(SEL_TREE::MAYBE));
4163
4201
  }
4164
4202
 
4167
4205
      cond_func->functype() == Item_func::IN_FUNC)
4168
4206
    inv= ((Item_func_opt_neg *) cond_func)->negated;
4169
4207
  else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
4170
 
    return(0);                         
 
4208
    return 0;
4171
4209
 
4172
4210
  param->cond= cond;
4173
4211
 
4188
4226
      if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
4189
4227
      {
4190
4228
        field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
4191
 
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func, 
 
4229
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
4192
4230
                                    field_item, (Item*)(intptr_t)i, inv);
4193
4231
        if (inv)
4194
4232
          tree= !tree ? tmp : tree_or(param, tree, tmp);
4195
 
        else 
 
4233
        else
4196
4234
          tree= tree_and(param, tree, tmp);
4197
4235
      }
4198
4236
      else if (inv)
4199
 
      { 
 
4237
      {
4200
4238
        tree= 0;
4201
4239
        break;
4202
4240
      }
4208
4246
  {
4209
4247
    Item_func_in *func=(Item_func_in*) cond_func;
4210
4248
    if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
4211
 
      return(0);
 
4249
      return 0;
4212
4250
    field_item= (Item_field*) (func->key_item()->real_item());
4213
4251
    ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
4214
4252
    break;
4215
4253
  }
4216
4254
  case Item_func::MULT_EQUAL_FUNC:
4217
4255
  {
4218
 
    Item_equal *item_equal= (Item_equal *) cond;    
 
4256
    Item_equal *item_equal= (Item_equal *) cond;
4219
4257
    if (!(value= item_equal->get_const()))
4220
 
      return(0);
 
4258
      return 0;
4221
4259
    Item_equal_iterator it(*item_equal);
4222
4260
    ref_tables= value->used_tables();
4223
4261
    while ((field_item= it++))
4231
4269
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
4232
4270
      }
4233
4271
    }
4234
 
    
 
4272
 
4235
4273
    return(ftree);
4236
4274
  }
4237
4275
  default:
4248
4286
      value= cond_func->arguments()[0];
4249
4287
    }
4250
4288
    else
4251
 
      return(0);
 
4289
      return 0;
4252
4290
    ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
4253
4291
  }
4254
4292
 
4259
4297
static SEL_TREE *
4260
4298
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4261
4299
             Item_func::Functype type,
4262
 
             Item *value,
4263
 
             Item_result cmp_type __attribute__((unused)))
 
4300
             Item *value, Item_result)
4264
4301
{
4265
4302
  if (field->table != param->table)
4266
 
    return(0);
 
4303
    return 0;
4267
4304
 
4268
4305
  KEY_PART *key_part = param->key_parts;
4269
4306
  KEY_PART *end = param->key_parts_end;
4270
4307
  SEL_TREE *tree=0;
4271
4308
  if (value &&
4272
4309
      value->used_tables() & ~(param->prev_tables | param->read_tables))
4273
 
    return(0);
 
4310
    return 0;
4274
4311
  for (; key_part != end ; key_part++)
4275
4312
  {
4276
4313
    if (field->eq(key_part->field))
4277
4314
    {
4278
4315
      SEL_ARG *sel_arg=0;
4279
4316
      if (!tree && !(tree=new SEL_TREE()))
4280
 
        return(0);                              // OOM
 
4317
        return 0;                               // OOM
4281
4318
      if (!value || !(value->used_tables() & ~param->read_tables))
4282
4319
      {
4283
4320
        sel_arg=get_mm_leaf(param,cond_func,
4294
4331
      {
4295
4332
        // This key may be used later
4296
4333
        if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4297
 
          return(0);                    // OOM
 
4334
          return 0;                     // OOM
4298
4335
      }
4299
4336
      sel_arg->part=(unsigned char) key_part->part;
4300
4337
      tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4301
4338
      tree->keys_map.set_bit(key_part->key);
4302
4339
    }
4303
4340
  }
4304
 
  
 
4341
 
4305
4342
  return(tree);
4306
4343
}
4307
4344
 
4310
4347
get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field,
4311
4348
            KEY_PART *key_part, Item_func::Functype type,Item *value)
4312
4349
{
4313
 
  uint32_t maybe_null=(uint) field->real_maybe_null();
 
4350
  uint32_t maybe_null=(uint32_t) field->real_maybe_null();
4314
4351
  bool optimize_range;
4315
4352
  SEL_ARG *tree= 0;
4316
4353
  MEM_ROOT *alloc= param->mem_root;
4317
4354
  unsigned char *str;
4318
 
  ulong orig_sql_mode;
4319
 
  int err;
 
4355
  int err= 0;
4320
4356
 
4321
4357
  /*
4322
4358
    We need to restore the runtime mem_root of the thread in this
4324
4360
    the argument can be any, e.g. a subselect. The subselect
4325
4361
    items, in turn, assume that all the memory allocated during
4326
4362
    the evaluation has the same life span as the item itself.
4327
 
    TODO: opt_range.cc should not reset thd->mem_root at all.
 
4363
    TODO: opt_range.cc should not reset session->mem_root at all.
4328
4364
  */
4329
 
  param->thd->mem_root= param->old_root;
 
4365
  param->session->mem_root= param->old_root;
4330
4366
  if (!value)                                   // IS NULL or IS NOT NULL
4331
4367
  {
4332
4368
    if (field->table->maybe_null)               // Can't use a key on this
4465
4501
      value->result_type() != STRING_RESULT &&
4466
4502
      field->cmp_type() != value->result_type())
4467
4503
    goto end;
4468
 
  /* For comparison purposes allow invalid dates like 2000-01-32 */
4469
 
  orig_sql_mode= field->table->in_use->variables.sql_mode;
4470
 
  if (value->real_item()->type() == Item::STRING_ITEM &&
4471
 
      (field->type() == DRIZZLE_TYPE_NEWDATE ||
4472
 
       field->type() == DRIZZLE_TYPE_DATETIME))
4473
 
    field->table->in_use->variables.sql_mode|= MODE_INVALID_DATES;
4474
 
  err= value->save_in_field_no_warnings(field, 1);
 
4504
 
 
4505
  /*
 
4506
   * Some notes from Jay...
 
4507
   *
 
4508
   * OK, so previously, and in MySQL, what the optimizer does here is
 
4509
   * override the sql_mode variable to ignore out-of-range or bad date-
 
4510
   * time values.  It does this because the optimizer is populating the
 
4511
   * field variable with the incoming value from the comparison field, 
 
4512
   * and the value may exceed the bounds of a proper column type.
 
4513
   *
 
4514
   * For instance, assume the following:
 
4515
   *
 
4516
   * CREATE TABLE t1 (ts TIMESTAMP); 
 
4517
   * INSERT INTO t1 ('2009-03-04 00:00:00');
 
4518
   * CREATE TABLE t2 (dt1 DATETIME, dt2 DATETIME); 
 
4519
   * INSERT INT t2 ('2003-12-31 00:00:00','2999-12-31 00:00:00');
 
4520
   *
 
4521
   * If we issue this query:
 
4522
   *
 
4523
   * SELECT * FROM t1, t2 WHERE t1.ts BETWEEN t2.dt1 AND t2.dt2;
 
4524
   *
 
4525
   * We will come into bounds issues.  Field_timestamp::store() will be
 
4526
   * called with a datetime value of "2999-12-31 00:00:00" and will throw
 
4527
   * an error for out-of-bounds.  MySQL solves this via a hack with sql_mode
 
4528
   * but Drizzle always throws errors on bad data storage in a Field class.
 
4529
   *
 
4530
   * Therefore, to get around the problem of the Field class being used for
 
4531
   * "storage" here without actually storing anything...we must check to see 
 
4532
   * if the value being stored in a Field_timestamp here is out of range.  If
 
4533
   * it is, then we must convert to the highest Timestamp value (or lowest,
 
4534
   * depending on whether the datetime is before or after the epoch.
 
4535
   */
 
4536
  if (field->type() == DRIZZLE_TYPE_TIMESTAMP)
 
4537
  {
 
4538
    /* 
 
4539
     * The left-side of the range comparison is a timestamp field.  Therefore, 
 
4540
     * we must check to see if the value in the right-hand side is outside the
 
4541
     * range of the UNIX epoch, and cut to the epoch bounds if it is.
 
4542
     */
 
4543
    /* Datetime and date columns are Item::FIELD_ITEM ... and have a result type of STRING_RESULT */
 
4544
    if (value->real_item()->type() == Item::FIELD_ITEM
 
4545
        && value->result_type() == STRING_RESULT)
 
4546
    {
 
4547
      char buff[MAX_DATETIME_FULL_WIDTH];
 
4548
      String tmp(buff, sizeof(buff), &my_charset_bin);
 
4549
      String *res= value->val_str(&tmp);
 
4550
 
 
4551
      if (!res)
 
4552
        goto end;
 
4553
      else
 
4554
      {
 
4555
        /* 
 
4556
         * Create a datetime from the string and compare to fixed timestamp
 
4557
         * instances representing the epoch boundaries.
 
4558
         */
 
4559
        drizzled::DateTime value_datetime;
 
4560
 
 
4561
        if (! value_datetime.from_string(res->c_ptr(), (size_t) res->length()))
 
4562
          goto end;
 
4563
 
 
4564
        drizzled::Timestamp max_timestamp;
 
4565
        drizzled::Timestamp min_timestamp;
 
4566
 
 
4567
        (void) max_timestamp.from_time_t((time_t) INT32_MAX);
 
4568
        (void) min_timestamp.from_time_t((time_t) 0);
 
4569
 
 
4570
        /* We rely on Temporal class operator overloads to do our comparisons. */
 
4571
        if (value_datetime < min_timestamp)
 
4572
        {
 
4573
          /* 
 
4574
           * Datetime in right-hand side column is before UNIX epoch, so adjust to
 
4575
           * lower bound.
 
4576
           */
 
4577
          char new_value_buff[MAX_DATETIME_FULL_WIDTH];
 
4578
          size_t new_value_length;
 
4579
          String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
 
4580
 
 
4581
          min_timestamp.to_string(new_value_string.c_ptr(), &new_value_length);
 
4582
          new_value_string.length(new_value_length);
 
4583
          err= value->save_str_value_in_field(field, &new_value_string);
 
4584
        }
 
4585
        else if (value_datetime > max_timestamp)
 
4586
        {
 
4587
          /*
 
4588
           * Datetime in right hand side column is after UNIX epoch, so adjust
 
4589
           * to the higher bound of the epoch.
 
4590
           */
 
4591
          char new_value_buff[MAX_DATETIME_FULL_WIDTH];
 
4592
          size_t new_value_length;
 
4593
          String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
 
4594
 
 
4595
          max_timestamp.to_string(new_value_string.c_ptr(), &new_value_length);
 
4596
          new_value_string.length(new_value_length);
 
4597
          err= value->save_str_value_in_field(field, &new_value_string);
 
4598
        }
 
4599
        else
 
4600
          err= value->save_in_field(field, 1);
 
4601
      }
 
4602
    }
 
4603
    else /* Not a datetime -> timestamp comparison */
 
4604
      err= value->save_in_field(field, 1);
 
4605
  }
 
4606
  else /* Not a timestamp comparison */
 
4607
    err= value->save_in_field(field, 1);
 
4608
 
4475
4609
  if (err > 0)
4476
4610
  {
4477
4611
    if (field->cmp_type() != value->result_type())
4491
4625
          for the cases like int_field > 999999999999999999999999 as well.
4492
4626
        */
4493
4627
        tree= 0;
4494
 
        if (err == 3 && field->type() == DRIZZLE_TYPE_NEWDATE &&
 
4628
        if (err == 3 && field->type() == DRIZZLE_TYPE_DATE &&
4495
4629
            (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC ||
4496
4630
             type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) )
4497
4631
        {
4500
4634
            but a non-zero time part was cut off.
4501
4635
 
4502
4636
            In MySQL's SQL dialect, DATE and DATETIME are compared as datetime
4503
 
            values. Index over a DATE column uses DATE comparison. Changing 
 
4637
            values. Index over a DATE column uses DATE comparison. Changing
4504
4638
            from one comparison to the other is possible:
4505
4639
 
4506
4640
            datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10'
4537
4671
  }
4538
4672
  else if (err < 0)
4539
4673
  {
4540
 
    field->table->in_use->variables.sql_mode= orig_sql_mode;
4541
4674
    /* This happens when we try to insert a NULL field in a not null column */
4542
4675
    tree= &null_element;                        // cmp with NULL is never true
4543
4676
    goto end;
4544
4677
  }
4545
 
  field->table->in_use->variables.sql_mode= orig_sql_mode;
4546
4678
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
4547
4679
  if (!str)
4548
4680
    goto end;
4612
4744
  }
4613
4745
 
4614
4746
end:
4615
 
  param->thd->mem_root= alloc;
 
4747
  param->session->mem_root= alloc;
4616
4748
  return(tree);
4617
4749
}
4618
4750
 
4693
4825
  }
4694
4826
  key_map  result_keys;
4695
4827
  result_keys.clear_all();
4696
 
  
 
4828
 
4697
4829
  /* Join the trees key per key */
4698
4830
  SEL_ARG **key1,**key2,**end;
4699
4831
  for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
4714
4846
      }
4715
4847
      result_keys.set_bit(key1 - tree1->keys);
4716
4848
#ifdef EXTRA_DEBUG
4717
 
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
4849
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4718
4850
          (*key1)->test_use_count(*key1);
4719
4851
#endif
4720
4852
    }
4739
4871
  using index_merge.
4740
4872
*/
4741
4873
 
4742
 
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, 
 
4874
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4743
4875
                           RANGE_OPT_PARAM* param)
4744
4876
{
4745
4877
  key_map common_keys= tree1->keys_map;
4746
4878
  common_keys.intersect(tree2->keys_map);
4747
4879
 
4748
4880
  if (common_keys.is_clear_all())
4749
 
    return(false);
 
4881
    return false;
4750
4882
 
4751
4883
  /* trees have a common key, check if they refer to same key part */
4752
4884
  SEL_ARG **key1,**key2;
4758
4890
      key2= tree2->keys + key_no;
4759
4891
      if ((*key1)->part == (*key2)->part)
4760
4892
      {
4761
 
        return(true);
 
4893
        return true;
4762
4894
      }
4763
4895
    }
4764
4896
  }
4765
 
  return(false);
 
4897
  return false;
4766
4898
}
4767
4899
 
4768
4900
 
4771
4903
  SYNOPSIS
4772
4904
    param  Range analysis parameter
4773
4905
    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
4774
 
 
 
4906
 
4775
4907
  DESCRIPTION
4776
4908
    This function walks through tree->keys[] and removes the SEL_ARG* trees
4777
4909
    that are not "maybe" trees (*) and cannot be used to construct quick range
4783
4915
    tree->part != 0. (e.g. it could represent "keypart2 < const").
4784
4916
 
4785
4917
    WHY THIS FUNCTION IS NEEDED
4786
 
    
 
4918
 
4787
4919
    Normally we allow construction of SEL_TREE objects that have SEL_ARG
4788
4920
    trees that do not allow quick range select construction. For example for
4789
4921
    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4792
4924
                                               from this
4793
4925
    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4794
4926
                                   tree.
4795
 
    
 
4927
 
4796
4928
    There is an exception though: when we construct index_merge SEL_TREE,
4797
4929
    any SEL_ARG* tree that cannot be used to construct quick range select can
4798
4930
    be removed, because current range analysis code doesn't provide any way
4799
4931
    that tree could be later combined with another tree.
4800
4932
    Consider an example: we should not construct
4801
 
    st1 = SEL_TREE { 
4802
 
      merges = SEL_IMERGE { 
4803
 
                            SEL_TREE(t.key1part1 = 1), 
 
4933
    st1 = SEL_TREE {
 
4934
      merges = SEL_IMERGE {
 
4935
                            SEL_TREE(t.key1part1 = 1),
4804
4936
                            SEL_TREE(t.key2part2 = 2)   -- (*)
4805
 
                          } 
 
4937
                          }
4806
4938
                   };
4807
 
    because 
4808
 
     - (*) cannot be used to construct quick range select, 
4809
 
     - There is no execution path that would cause (*) to be converted to 
 
4939
    because
 
4940
     - (*) cannot be used to construct quick range select,
 
4941
     - There is no execution path that would cause (*) to be converted to
4810
4942
       a tree that could be used.
4811
4943
 
4812
4944
    The latter is easy to verify: first, notice that the only way to convert
4813
4945
    (*) into a usable tree is to call tree_and(something, (*)).
4814
4946
 
4815
4947
    Second look at what tree_and/tree_or function would do when passed a
4816
 
    SEL_TREE that has the structure like st1 tree has, and conlcude that 
 
4948
    SEL_TREE that has the structure like st1 tree has, and conlcude that
4817
4949
    tree_and(something, (*)) will not be called.
4818
4950
 
4819
4951
  RETURN
4845
4977
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4846
4978
{
4847
4979
  if (!tree1 || !tree2)
4848
 
    return(0);
 
4980
    return 0;
4849
4981
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4850
4982
    return(tree2);
4851
4983
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4871
5003
        result=tree1;                           // Added to tree1
4872
5004
        result_keys.set_bit(key1 - tree1->keys);
4873
5005
#ifdef EXTRA_DEBUG
4874
 
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
5006
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4875
5007
          (*key1)->test_use_count(*key1);
4876
5008
#endif
4877
5009
      }
4913
5045
      /* one tree is index merge tree and another is range tree */
4914
5046
      if (tree1->merges.is_empty())
4915
5047
        std::swap(tree1, tree2);
4916
 
      
 
5048
 
4917
5049
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
4918
5050
         return(new SEL_TREE(SEL_TREE::ALWAYS));
4919
5051
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
4923
5055
        result= tree1;
4924
5056
    }
4925
5057
  }
4926
 
  return(result);
 
5058
  return result;
4927
5059
}
4928
5060
 
4929
5061
 
4930
5062
/* And key trees where key1->part < key2 -> part */
4931
5063
 
4932
5064
static SEL_ARG *
4933
 
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, 
 
5065
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4934
5066
             uint32_t clone_flag)
4935
5067
{
4936
5068
  SEL_ARG *next;
5030
5162
    }
5031
5163
    if (key1->type == SEL_ARG::MAYBE_KEY)
5032
5164
    {                                           // Both are maybe key
5033
 
      key1->next_key_part=key_and(param, key1->next_key_part, 
 
5165
      key1->next_key_part=key_and(param, key1->next_key_part,
5034
5166
                                  key2->next_key_part, clone_flag);
5035
5167
      if (key1->next_key_part &&
5036
5168
          key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5534
5666
  }
5535
5667
 
5536
5668
  if (root == &null_element)
5537
 
    return(0);                          // Maybe root later
 
5669
    return 0;                           // Maybe root later
5538
5670
  if (remove_color == BLACK)
5539
5671
    root=rb_delete_fixup(root,nod,fix_par);
 
5672
#ifdef EXTRA_DEBUG
5540
5673
  test_rb_tree(root,root->parent);
 
5674
#endif /* EXTRA_DEBUG */
5541
5675
 
5542
5676
  root->use_count=this->use_count;              // Fix root counters
5543
5677
  root->elements=this->elements-1;
5634
5768
    }
5635
5769
  }
5636
5770
  root->color=BLACK;
 
5771
#ifdef EXTRA_DEBUG
5637
5772
  test_rb_tree(root,root->parent);
 
5773
#endif /* EXTRA_DEBUG */
 
5774
 
5638
5775
  return root;
5639
5776
}
5640
5777
 
5729
5866
    return 0;                                   // Found end of tree
5730
5867
  if (element->parent != parent)
5731
5868
  {
5732
 
    sql_print_error("Wrong tree: Parent doesn't point at parent");
 
5869
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5733
5870
    return -1;
5734
5871
  }
5735
5872
  if (element->color == SEL_ARG::RED &&
5736
5873
      (element->left->color == SEL_ARG::RED ||
5737
5874
       element->right->color == SEL_ARG::RED))
5738
5875
  {
5739
 
    sql_print_error("Wrong tree: Found two red in a row");
 
5876
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5740
5877
    return -1;
5741
5878
  }
5742
5879
  if (element->left == element->right && element->left != &null_element)
5743
5880
  {                                             // Dummy test
5744
 
    sql_print_error("Wrong tree: Found right == left");
 
5881
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5745
5882
    return -1;
5746
5883
  }
5747
5884
  count_l=test_rb_tree(element->left,element);
5750
5887
  {
5751
5888
    if (count_l == count_r)
5752
5889
      return count_l+(element->color == SEL_ARG::BLACK);
5753
 
    sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
 
5890
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5754
5891
            count_l,count_r);
5755
5892
  }
5756
5893
  return -1;                                    // Error, no more warnings
5759
5896
 
5760
5897
/*
5761
5898
  Count how many times SEL_ARG graph "root" refers to its part "key"
5762
 
  
 
5899
 
5763
5900
  SYNOPSIS
5764
5901
    count_key_part_usage()
5765
5902
      root  An RB-Root node in a SEL_ARG graph.
5770
5907
    root->next->n
5771
5908
 
5772
5909
    This function counts how many times the node "key" is referred (via
5773
 
    SEL_ARG::next_key_part) by 
5774
 
     - intervals of RB-tree pointed by "root", 
5775
 
     - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from 
 
5910
    SEL_ARG::next_key_part) by
 
5911
     - intervals of RB-tree pointed by "root",
 
5912
     - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5776
5913
       intervals of RB-tree pointed by "root",
5777
5914
     - and so on.
5778
 
    
5779
 
    Here is an example (horizontal links represent next_key_part pointers, 
5780
 
    vertical links - next/prev prev pointers):  
5781
 
    
 
5915
 
 
5916
    Here is an example (horizontal links represent next_key_part pointers,
 
5917
    vertical links - next/prev prev pointers):
 
5918
 
5782
5919
         +----+               $
5783
5920
         |root|-----------------+
5784
5921
         +----+               $ |
5797
5934
          ...     +---+       $    |
5798
5935
                  |   |------------+
5799
5936
                  +---+       $
5800
 
  RETURN 
 
5937
  RETURN
5801
5938
    Number of links to "key" from nodes reachable from "root".
5802
5939
*/
5803
5940
 
5837
5974
  uint32_t e_count=0;
5838
5975
  if (this == root && use_count != 1)
5839
5976
  {
5840
 
    sql_print_information("Use_count: Wrong count %lu for root",use_count);
 
5977
    errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5841
5978
    return;
5842
5979
  }
5843
5980
  if (this->type != SEL_ARG::KEY_RANGE)
5850
5987
      ulong count=count_key_part_usage(root,pos->next_key_part);
5851
5988
      if (count > pos->next_key_part->use_count)
5852
5989
      {
5853
 
        sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
 
5990
        errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5854
5991
                              "should be %lu", (long unsigned int)pos,
5855
5992
                              pos->next_key_part->use_count, count);
5856
5993
        return;
5859
5996
    }
5860
5997
  }
5861
5998
  if (e_count != elements)
5862
 
    sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
 
5999
    errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5863
6000
                      e_count, elements, (long unsigned int) this);
5864
6001
}
5865
6002
 
5870
6007
 ****************************************************************************/
5871
6008
 
5872
6009
/* MRR range sequence, SEL_ARG* implementation: stack entry */
5873
 
typedef struct st_range_seq_entry 
 
6010
typedef struct st_range_seq_entry
5874
6011
{
5875
 
  /* 
 
6012
  /*
5876
6013
    Pointers in min and max keys. They point to right-after-end of key
5877
6014
    images. The 0-th entry has these pointing to key tuple start.
5878
6015
  */
5879
6016
  unsigned char *min_key, *max_key;
5880
 
  
5881
 
  /* 
 
6017
 
 
6018
  /*
5882
6019
    Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
5883
6020
    min_key_flag may have NULL_RANGE set.
5884
6021
  */
5885
6022
  uint32_t min_key_flag, max_key_flag;
5886
 
  
 
6023
 
5887
6024
  /* Number of key parts */
5888
6025
  uint32_t min_key_parts, max_key_parts;
5889
6026
  SEL_ARG *key_tree;
5899
6036
  uint32_t real_keyno; /* Number of the index in tables */
5900
6037
  PARAM *param;
5901
6038
  SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
5902
 
  
 
6039
 
5903
6040
  RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
5904
6041
  int i; /* Index of last used element in the above array */
5905
 
  
 
6042
 
5906
6043
  bool at_start; /* true <=> The traversal has just started */
5907
6044
} SEL_ARG_RANGE_SEQ;
5908
6045
 
5913
6050
  SYNOPSIS
5914
6051
    init()
5915
6052
      init_params  SEL_ARG tree traversal context
5916
 
      n_ranges     [ignored] The number of ranges obtained 
 
6053
      n_ranges     [ignored] The number of ranges obtained
5917
6054
      flags        [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
5918
6055
 
5919
6056
  RETURN
5920
6057
    Value of init_param
5921
6058
*/
5922
6059
 
5923
 
range_seq_t sel_arg_range_seq_init(void *init_param,
5924
 
                                   uint32_t n_ranges __attribute__((unused)),
5925
 
                                   uint32_t flags __attribute__((unused)))
 
6060
range_seq_t sel_arg_range_seq_init(void *init_param, uint32_t, uint32_t)
5926
6061
{
5927
6062
  SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
5928
6063
  seq->at_start= true;
5943
6078
{
5944
6079
  RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
5945
6080
  RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
5946
 
  
 
6081
 
5947
6082
  cur->key_tree= key_tree;
5948
6083
  cur->min_key= prev->min_key;
5949
6084
  cur->max_key= prev->max_key;
5967
6102
 
5968
6103
/*
5969
6104
  Range sequence interface, SEL_ARG* implementation: get the next interval
5970
 
  
 
6105
 
5971
6106
  SYNOPSIS
5972
6107
    sel_arg_range_seq_next()
5973
6108
      rseq        Value returned from sel_arg_range_seq_init
6002
6137
 
6003
6138
  key_tree= seq->stack[seq->i].key_tree;
6004
6139
  /* Ok, we're at some "full tuple" position in the tree */
6005
 
 
 
6140
 
6006
6141
  /* Step down if we can */
6007
6142
  if (key_tree->next && key_tree->next != &null_element)
6008
6143
  {
6039
6174
    Walk right-up while we can
6040
6175
  */
6041
6176
walk_right_n_up:
6042
 
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element && 
 
6177
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
6043
6178
         key_tree->next_key_part->part == key_tree->part + 1 &&
6044
6179
         key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6045
6180
  {
6054
6189
      {
6055
6190
        seq->param->is_ror_scan= false;
6056
6191
        if (!key_tree->min_flag)
6057
 
          cur->min_key_parts += 
 
6192
          cur->min_key_parts +=
6058
6193
            key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6059
6194
                                                   &cur->min_key,
6060
6195
                                                   &cur->min_key_flag);
6061
6196
        if (!key_tree->max_flag)
6062
 
          cur->max_key_parts += 
 
6197
          cur->max_key_parts +=
6063
6198
            key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6064
6199
                                                   &cur->max_key,
6065
6200
                                                   &cur->max_key_flag);
6066
6201
        break;
6067
6202
      }
6068
6203
    }
6069
 
  
 
6204
 
6070
6205
    /*
6071
6206
      Ok, current atomic interval is in form "t.field=const" and there is
6072
6207
      next_key_part interval. Step right, and walk up from there.
6084
6219
 
6085
6220
  /* Ok got a tuple */
6086
6221
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6087
 
  
 
6222
 
6088
6223
  range->ptr= (char*)(int)(key_tree->part);
6089
6224
  {
6090
6225
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
6091
 
    
 
6226
 
6092
6227
    range->start_key.key=    seq->param->min_key;
6093
6228
    range->start_key.length= cur->min_key - seq->param->min_key;
6094
6229
    range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
6095
 
    range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY : 
 
6230
    range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
6096
6231
                                                           HA_READ_KEY_EXACT);
6097
6232
 
6098
6233
    range->end_key.key=    seq->param->max_key;
6099
6234
    range->end_key.length= cur->max_key - seq->param->max_key;
6100
 
    range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY : 
 
6235
    range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
6101
6236
                                                         HA_READ_AFTER_KEY);
6102
6237
    range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
6103
6238
 
6104
6239
    if (!(cur->min_key_flag & ~NULL_RANGE) && !cur->max_key_flag &&
6105
 
        (uint)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts &&
 
6240
        (uint32_t)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts &&
6106
6241
        (seq->param->table->key_info[seq->real_keyno].flags & (HA_NOSAME)) ==
6107
6242
        HA_NOSAME &&
6108
6243
        range->start_key.length == range->end_key.length &&
6109
6244
        !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
6110
6245
      range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
6111
 
      
 
6246
 
6112
6247
    if (seq->param->is_ror_scan)
6113
6248
    {
6114
6249
      /*
6128
6263
    }
6129
6264
  }
6130
6265
  seq->param->range_count++;
6131
 
  seq->param->max_key_part=cmax(seq->param->max_key_part,(uint)key_tree->part);
 
6266
  seq->param->max_key_part=cmax(seq->param->max_key_part,(uint32_t)key_tree->part);
6132
6267
  return 0;
6133
6268
}
6134
6269
 
6135
6270
 
6136
6271
/*
6137
 
  Calculate cost and E(#rows) for a given index and intervals tree 
 
6272
  Calculate cost and E(#rows) for a given index and intervals tree
6138
6273
 
6139
6274
  SYNOPSIS
6140
6275
    check_quick_select()
6162
6297
 
6163
6298
static
6164
6299
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
6165
 
                           SEL_ARG *tree, bool update_tbl_stats, 
 
6300
                           SEL_ARG *tree, bool update_tbl_stats,
6166
6301
                           uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
6167
6302
{
6168
6303
  SEL_ARG_RANGE_SEQ seq;
6170
6305
  handler *file= param->table->file;
6171
6306
  ha_rows rows;
6172
6307
  uint32_t keynr= param->real_keynr[idx];
6173
 
  
 
6308
 
6174
6309
  /* Handle cases when we don't have a valid non-empty list of range */
6175
6310
  if (!tree)
6176
6311
    return(HA_POS_ERROR);
6190
6325
  param->is_ror_scan= true;
6191
6326
  if (file->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)
6192
6327
    param->is_ror_scan= false;
6193
 
  
 
6328
 
6194
6329
  *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
6195
6330
  *mrr_flags|= HA_MRR_NO_ASSOCIATION;
6196
6331
 
6197
6332
  bool pk_is_clustered= file->primary_key_is_clustered();
6198
 
  if (index_only && 
 
6333
  if (index_only &&
6199
6334
      (file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&
6200
6335
      !(pk_is_clustered && keynr == param->table->s->primary_key))
6201
6336
     *mrr_flags |= HA_MRR_INDEX_ONLY;
6202
 
  
6203
 
  if (current_thd->lex->sql_command != SQLCOM_SELECT)
 
6337
 
 
6338
  if (current_session->lex->sql_command != SQLCOM_SELECT)
6204
6339
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6205
6340
 
6206
 
  *bufsize= param->thd->variables.read_rnd_buff_size;
 
6341
  *bufsize= param->session->variables.read_rnd_buff_size;
6207
6342
  rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,
6208
6343
                                          bufsize, mrr_flags, cost);
6209
6344
  if (rows != HA_POS_ERROR)
6222
6357
  enum ha_key_alg key_alg= param->table->key_info[seq.real_keyno].algorithm;
6223
6358
  if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF))
6224
6359
  {
6225
 
    /* 
 
6360
    /*
6226
6361
      All scans are non-ROR scans for those index types.
6227
 
      TODO: Don't have this logic here, make table engines return 
 
6362
      TODO: Don't have this logic here, make table engines return
6228
6363
      appropriate flags instead.
6229
6364
    */
6230
6365
    param->is_ror_scan= false;
6263
6398
 
6264
6399
    where the index is defined on (key1_1, ..., key1_N [,a_1, ..., a_n])
6265
6400
 
6266
 
    and the table has a clustered Primary Key defined as 
6267
 
      PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k) 
6268
 
    
6269
 
    i.e. the first key parts of it are identical to uncovered parts ot the 
 
6401
    and the table has a clustered Primary Key defined as
 
6402
      PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
 
6403
 
 
6404
    i.e. the first key parts of it are identical to uncovered parts ot the
6270
6405
    key being scanned. This function assumes that the index flags do not
6271
6406
    include HA_KEY_SCAN_NOT_ROR flag (that is checked elsewhere).
6272
6407
 
6284
6419
  KEY_PART_INFO *key_part_end= (table_key->key_part +
6285
6420
                                table_key->key_parts);
6286
6421
  uint32_t pk_number;
6287
 
  
 
6422
 
6288
6423
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
6289
6424
  {
6290
6425
    uint16_t fieldnr= param->table->key_info[keynr].
6330
6465
  NOTES
6331
6466
    The caller must call QUICK_SELECT::init for returned quick select.
6332
6467
 
6333
 
    CAUTION! This function may change thd->mem_root to a MEM_ROOT which will be
 
6468
    CAUTION! This function may change session->mem_root to a MEM_ROOT which will be
6334
6469
    deallocated when the returned quick select is deleted.
6335
6470
 
6336
6471
  RETURN
6345
6480
  QUICK_RANGE_SELECT *quick;
6346
6481
  bool create_err= false;
6347
6482
 
6348
 
  quick=new QUICK_RANGE_SELECT(param->thd, param->table,
 
6483
  quick=new QUICK_RANGE_SELECT(param->session, param->table,
6349
6484
                               param->real_keynr[idx],
6350
6485
                               test(parent_alloc), NULL, &create_err);
6351
6486
 
6369
6504
                    param->table->key_info[param->real_keynr[idx]].key_parts);
6370
6505
    }
6371
6506
  }
6372
 
  return(quick);
 
6507
  return quick;
6373
6508
}
6374
6509
 
6375
6510
 
6403
6538
      key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6404
6539
  {                                               // const key as prefix
6405
6540
    if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
6406
 
         memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 &&
 
6541
         memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
6407
6542
         key_tree->min_flag==0 && key_tree->max_flag==0)
6408
6543
    {
6409
6544
      if (get_quick_keys(param,quick,key,key_tree->next_key_part,
6444
6579
  }
6445
6580
  if (flag == 0)
6446
6581
  {
6447
 
    uint32_t length= (uint) (tmp_min_key - param->min_key);
6448
 
    if (length == (uint) (tmp_max_key - param->max_key) &&
 
6582
    uint32_t length= (uint32_t) (tmp_min_key - param->min_key);
 
6583
    if (length == (uint32_t) (tmp_max_key - param->max_key) &&
6449
6584
        !memcmp(param->min_key,param->max_key,length))
6450
6585
    {
6451
6586
      KEY *table_key=quick->head->key_info+quick->index;
6456
6591
        if (!(table_key->flags & HA_NULL_PART_KEY) ||
6457
6592
            !null_part_in_key(key,
6458
6593
                              param->min_key,
6459
 
                              (uint) (tmp_min_key - param->min_key)))
 
6594
                              (uint32_t) (tmp_min_key - param->min_key)))
6460
6595
          flag|= UNIQUE_RANGE;
6461
6596
        else
6462
6597
          flag|= NULL_RANGE;
6466
6601
 
6467
6602
  /* Get range for retrieving rows in QUICK_SELECT::get_next */
6468
6603
  if (!(range= new QUICK_RANGE(param->min_key,
6469
 
                               (uint) (tmp_min_key - param->min_key),
 
6604
                               (uint32_t) (tmp_min_key - param->min_key),
6470
6605
                               min_part >=0 ? make_keypart_map(min_part) : 0,
6471
6606
                               param->max_key,
6472
 
                               (uint) (tmp_max_key - param->max_key),
 
6607
                               (uint32_t) (tmp_max_key - param->max_key),
6473
6608
                               max_part >=0 ? make_keypart_map(max_part) : 0,
6474
6609
                               flag)))
6475
6610
    return 1;                   // out of memory
6476
6611
 
6477
 
  set_if_bigger(quick->max_used_key_length, range->min_length);
6478
 
  set_if_bigger(quick->max_used_key_length, range->max_length);
6479
 
  set_if_bigger(quick->used_key_parts, (uint) key_tree->part+1);
 
6612
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
 
6613
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
 
6614
  set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
6480
6615
  if (insert_dynamic(&quick->ranges, (unsigned char*) &range))
6481
6616
    return 1;
6482
6617
 
6513
6648
  Return true if any part of the key is NULL
6514
6649
 
6515
6650
  SYNOPSIS
6516
 
    null_part_in_key()    
 
6651
    null_part_in_key()
6517
6652
      key_part  Array of key parts (index description)
6518
6653
      key       Key values tuple
6519
6654
      length    Length of key values tuple in bytes.
6583
6718
 
6584
6719
  SYNOPSIS
6585
6720
    get_quick_select_for_ref()
6586
 
      thd      Thread handle
 
6721
      session      Thread handle
6587
6722
      table    Table to access
6588
6723
      ref      ref[_or_null] scan parameters
6589
6724
      records  Estimate of number of records (needed only to construct
6597
6732
    NULL on error.
6598
6733
*/
6599
6734
 
6600
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, Table *table,
 
6735
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
6601
6736
                                             TABLE_REF *ref, ha_rows records)
6602
6737
{
6603
6738
  MEM_ROOT *old_root, *alloc;
6609
6744
  bool create_err= false;
6610
6745
  COST_VECT cost;
6611
6746
 
6612
 
  old_root= thd->mem_root;
6613
 
  /* The following call may change thd->mem_root */
6614
 
  quick= new QUICK_RANGE_SELECT(thd, table, ref->key, 0, 0, &create_err);
 
6747
  old_root= session->mem_root;
 
6748
  /* The following call may change session->mem_root */
 
6749
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0, &create_err);
6615
6750
  /* save mem_root set by QUICK_RANGE_SELECT constructor */
6616
 
  alloc= thd->mem_root;
 
6751
  alloc= session->mem_root;
6617
6752
  /*
6618
 
    return back default mem_root (thd->mem_root) changed by
 
6753
    return back default mem_root (session->mem_root) changed by
6619
6754
    QUICK_RANGE_SELECT constructor
6620
6755
  */
6621
 
  thd->mem_root= old_root;
 
6756
  session->mem_root= old_root;
6622
6757
 
6623
6758
  if (!quick || create_err)
6624
6759
    return 0;                   /* no ranges found */
6626
6761
    goto err;
6627
6762
  quick->records= records;
6628
6763
 
6629
 
  if ((cp_buffer_from_ref(thd, ref) && thd->is_fatal_error) ||
 
6764
  if ((cp_buffer_from_ref(session, ref) && session->is_fatal_error) ||
6630
6765
      !(range= new(alloc) QUICK_RANGE()))
6631
6766
    goto err;                                   // out of memory
6632
6767
 
6676
6811
  }
6677
6812
 
6678
6813
  /* Call multi_range_read_info() to get the MRR flags and buffer size */
6679
 
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION | 
 
6814
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
6680
6815
                    (table->key_read ? HA_MRR_INDEX_ONLY : 0);
6681
 
  if (thd->lex->sql_command != SQLCOM_SELECT)
 
6816
  if (session->lex->sql_command != SQLCOM_SELECT)
6682
6817
    quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6683
6818
 
6684
 
  quick->mrr_buf_size= thd->variables.read_rnd_buff_size;
6685
 
  if (table->file->multi_range_read_info(quick->index, 1, (uint)records,
 
6819
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
 
6820
  if (table->file->multi_range_read_info(quick->index, 1, (uint32_t)records,
6686
6821
                                         &quick->mrr_buf_size,
6687
6822
                                         &quick->mrr_flags, &cost))
6688
6823
    goto err;
6695
6830
 
6696
6831
 
6697
6832
/*
6698
 
  Perform key scans for all used indexes (except CPK), get rowids and merge 
 
6833
  Perform key scans for all used indexes (except CPK), get rowids and merge
6699
6834
  them into an ordered non-recurrent sequence of rowids.
6700
 
  
 
6835
 
6701
6836
  The merge/duplicate removal is performed using Unique class. We put all
6702
6837
  rowids into Unique, get the sorted sequence and destroy the Unique.
6703
 
  
 
6838
 
6704
6839
  If table has a clustered primary key that covers all rows (true for bdb
6705
6840
  and innodb currently) and one of the index_merge scans is a scan on PK,
6706
 
  then rows that will be retrieved by PK scan are not put into Unique and 
 
6841
  then rows that will be retrieved by PK scan are not put into Unique and
6707
6842
  primary key scan is not performed here, it is performed later separately.
6708
6843
 
6709
6844
  RETURN
6725
6860
  cur_quick_it.rewind();
6726
6861
  cur_quick= cur_quick_it++;
6727
6862
  assert(cur_quick != 0);
6728
 
  
 
6863
 
6729
6864
  /*
6730
 
    We reuse the same instance of handler so we need to call both init and 
 
6865
    We reuse the same instance of handler so we need to call both init and
6731
6866
    reset here.
6732
6867
  */
6733
6868
  if (cur_quick->init() || cur_quick->reset())
6734
 
    return(1);
 
6869
    return 0;
6735
6870
 
6736
6871
  unique= new Unique(refpos_order_cmp, (void *)file,
6737
6872
                     file->ref_length,
6738
 
                     thd->variables.sortbuff_size);
 
6873
                     session->variables.sortbuff_size);
6739
6874
  if (!unique)
6740
 
    return(1);
 
6875
    return 0;
6741
6876
  for (;;)
6742
6877
  {
6743
6878
    while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6747
6882
      if (!cur_quick)
6748
6883
        break;
6749
6884
 
6750
 
      if (cur_quick->file->inited != handler::NONE) 
 
6885
      if (cur_quick->file->inited != handler::NONE)
6751
6886
        cur_quick->file->ha_index_end();
6752
6887
      if (cur_quick->init() || cur_quick->reset())
6753
 
        return(1);
 
6888
        return 0;
6754
6889
    }
6755
6890
 
6756
6891
    if (result)
6758
6893
      if (result != HA_ERR_END_OF_FILE)
6759
6894
      {
6760
6895
        cur_quick->range_end();
6761
 
        return(result);
 
6896
        return result;
6762
6897
      }
6763
6898
      break;
6764
6899
    }
6765
6900
 
6766
 
    if (thd->killed)
6767
 
      return(1);
 
6901
    if (session->killed)
 
6902
      return 0;
6768
6903
 
6769
6904
    /* skip row if it will be retrieved by clustered PK scan */
6770
6905
    if (pk_quick_select && pk_quick_select->row_in_ranges())
6773
6908
    cur_quick->file->position(cur_quick->record);
6774
6909
    result= unique->unique_add((char*)cur_quick->file->ref);
6775
6910
    if (result)
6776
 
      return(1);
 
6911
      return 0;
6777
6912
 
6778
6913
  }
6779
6914
 
6784
6919
  /* index_merge currently doesn't support "using index" at all */
6785
6920
  file->extra(HA_EXTRA_NO_KEYREAD);
6786
6921
  /* start table scan */
6787
 
  init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6788
 
  return(result);
 
6922
  init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
 
6923
  return result;
6789
6924
}
6790
6925
 
6791
6926
 
6815
6950
      doing_pk_scan= true;
6816
6951
      if ((result= pk_quick_select->init()) ||
6817
6952
          (result= pk_quick_select->reset()))
6818
 
        return(result);
 
6953
        return result;
6819
6954
      return(pk_quick_select->get_next());
6820
6955
    }
6821
6956
  }
6822
6957
 
6823
 
  return(result);
 
6958
  return result;
6824
6959
}
6825
6960
 
6826
6961
 
6939
7074
  {
6940
7075
    do
6941
7076
    {
6942
 
      if (!queue.elements)
 
7077
      if (queue->empty())
6943
7078
        return(HA_ERR_END_OF_FILE);
6944
7079
      /* Ok, we have a queue with >= 1 scans */
6945
7080
 
6946
 
      quick= (QUICK_SELECT_I*)queue_top(&queue);
 
7081
      quick= queue->top();
6947
7082
      memcpy(cur_rowid, quick->last_rowid, rowid_length);
6948
7083
 
6949
7084
      /* put into queue rowid from the same stream as top element */
6951
7086
      {
6952
7087
        if (error != HA_ERR_END_OF_FILE)
6953
7088
          return(error);
6954
 
        queue_remove(&queue, 0);
 
7089
        queue->pop();
6955
7090
      }
6956
7091
      else
6957
7092
      {
6958
7093
        quick->save_last_pos();
6959
 
        queue_replaced(&queue);
 
7094
        queue->pop();
 
7095
        queue->push(quick);
6960
7096
      }
6961
7097
 
6962
7098
      if (!have_prev_rowid)
6990
7126
 
6991
7127
  if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6992
7128
    return(error);
6993
 
 
 
7129
 
6994
7130
  /* Allocate buffer if we need one but haven't allocated it yet */
6995
7131
  if (mrr_buf_size && !mrr_buf_desc)
6996
7132
  {
7014
7150
 
7015
7151
  if (!mrr_buf_desc)
7016
7152
    empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7017
 
 
 
7153
 
7018
7154
  if (sorted)
7019
7155
     mrr_flags |= HA_MRR_SORTED;
7020
7156
  RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7021
7157
  error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7022
 
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc: 
 
7158
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc:
7023
7159
                                                              &empty_buf);
7024
7160
  return(error);
7025
7161
}
7027
7163
 
7028
7164
/*
7029
7165
  Range sequence interface implementation for array<QUICK_RANGE>: initialize
7030
 
  
 
7166
 
7031
7167
  SYNOPSIS
7032
7168
    quick_range_seq_init()
7033
7169
      init_param  Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
7034
7170
      n_ranges    Number of ranges in the sequence (ignored)
7035
 
      flags       MRR flags (currently not used) 
 
7171
      flags       MRR flags (currently not used)
7036
7172
 
7037
7173
  RETURN
7038
7174
    Opaque value to be passed to quick_range_seq_next
7039
7175
*/
7040
7176
 
7041
 
range_seq_t quick_range_seq_init(void *init_param,
7042
 
                                 uint32_t n_ranges __attribute__((unused)),
7043
 
                                 uint32_t flags __attribute__((unused)))
 
7177
range_seq_t quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7044
7178
{
7045
7179
  QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7046
7180
  quick->qr_traversal_ctx.first=  (QUICK_RANGE**)quick->ranges.buffer;
7053
7187
 
7054
7188
/*
7055
7189
  Range sequence interface implementation for array<QUICK_RANGE>: get next
7056
 
  
 
7190
 
7057
7191
  SYNOPSIS
7058
7192
    quick_range_seq_next()
7059
7193
      rseq        Value returned from quick_range_seq_init
7109
7243
    function returns a reference to the "range_flag" associated with the
7110
7244
    range number idx.
7111
7245
 
7112
 
    This function should be removed when we get a proper MRR/NDB 
 
7246
    This function should be removed when we get a proper MRR/NDB
7113
7247
    implementation.
7114
7248
 
7115
7249
  RETURN
7148
7282
    Reference to range-associated data
7149
7283
*/
7150
7284
 
7151
 
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7152
 
                          uint32_t idx __attribute__((unused)))
 
7285
char* &mrr_get_ptr_by_idx(range_seq_t, uint32_t)
7153
7286
{
7154
7287
  static char *dummy;
7155
7288
  return dummy;
7190
7323
    /* Restore bitmaps set on entry */
7191
7324
    head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7192
7325
  }
7193
 
  return(result);
 
7326
  return result;
7194
7327
}
7195
7328
 
7196
7329
 
7237
7370
      result= file->index_read_map(record, cur_prefix, keypart_map,
7238
7371
                                   HA_READ_AFTER_KEY);
7239
7372
      if (result || (file->compare_key(file->end_range) <= 0))
7240
 
        return(result);
 
7373
        return result;
7241
7374
    }
7242
7375
 
7243
7376
    uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7245
7378
    {
7246
7379
      /* Ranges have already been used up before. None is left for read. */
7247
7380
      last_range= 0;
7248
 
      return(HA_ERR_END_OF_FILE);
 
7381
      return HA_ERR_END_OF_FILE;
7249
7382
    }
7250
7383
    last_range= *(cur_range++);
7251
7384
 
7273
7406
      last_range= 0;                    // Stop searching
7274
7407
 
7275
7408
    if (result != HA_ERR_END_OF_FILE)
7276
 
      return(result);
 
7409
      return result;
7277
7410
    last_range= 0;                      // No matching rows; go to next range
7278
7411
  }
7279
7412
}
7329
7462
  for now, this seems to work right at least.
7330
7463
 */
7331
7464
 
7332
 
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7333
 
                                     uint32_t used_key_parts_arg __attribute__((unused)),
7334
 
                                     bool *create_err __attribute__((unused)))
 
7465
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7335
7466
 :QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7336
7467
{
7337
7468
  QUICK_RANGE *r;
7379
7510
      if (!result)
7380
7511
      {
7381
7512
        if (cmp_prev(*rev_it.ref()) == 0)
7382
 
          return(0);
 
7513
          return 0;
7383
7514
      }
7384
7515
      else if (result != HA_ERR_END_OF_FILE)
7385
 
        return(result);
 
7516
        return result;
7386
7517
    }
7387
7518
 
7388
7519
    if (!(last_range= rev_it++))
7389
 
      return(HA_ERR_END_OF_FILE);               // All ranges used
 
7520
      return HA_ERR_END_OF_FILE;                // All ranges used
7390
7521
 
7391
7522
    if (last_range->flag & NO_MAX_RANGE)        // Read last record
7392
7523
    {
7394
7525
      if ((local_error=file->index_last(record)))
7395
7526
        return(local_error);            // Empty table
7396
7527
      if (cmp_prev(last_range) == 0)
7397
 
        return(0);
 
7528
        return 0;
7398
7529
      last_range= 0;                            // No match; go to next range
7399
7530
      continue;
7400
7531
    }
7418
7549
    if (result)
7419
7550
    {
7420
7551
      if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7421
 
        return(result);
 
7552
        return result;
7422
7553
      last_range= 0;                            // Not found, to next range
7423
7554
      continue;
7424
7555
    }
7426
7557
    {
7427
7558
      if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7428
7559
        last_range= 0;                          // Stop searching
7429
 
      return(0);                                // Found key is in range
 
7560
      return 0;                         // Found key is in range
7430
7561
    }
7431
7562
    last_range= 0;                              // To next range
7432
7563
  }
7436
7567
/*
7437
7568
  Compare if found key is over max-value
7438
7569
  Returns 0 if key <= range->max_key
7439
 
  TODO: Figure out why can't this function be as simple as cmp_prev(). 
 
7570
  TODO: Figure out why can't this function be as simple as cmp_prev().
7440
7571
*/
7441
7572
 
7442
7573
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7686
7817
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7687
7818
                       KEY_PART_INFO *first_non_group_part,
7688
7819
                       KEY_PART_INFO *min_max_arg_part,
7689
 
                       KEY_PART_INFO *last_part, THD *thd,
 
7820
                       KEY_PART_INFO *last_part, Session *session,
7690
7821
                       unsigned char *key_infix, uint32_t *key_infix_len,
7691
7822
                       KEY_PART_INFO **first_non_infix_part);
7692
7823
static bool
7729
7860
        - NGA = QA - (GA union C) = {NG_1, ..., NG_m} - the ones not in
7730
7861
          GROUP BY and not referenced by MIN/MAX functions.
7731
7862
        with the following properties specified below.
7732
 
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not 
 
7863
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
7733
7864
        applicable.
7734
7865
 
7735
7866
    SA1. There is at most one attribute in SA referenced by any number of
7817
7948
    other field as in: "select min(a) from t1 group by a" ?
7818
7949
  - We assume that the general correctness of the GROUP-BY query was checked
7819
7950
    before this point. Is this correct, or do we have to check it completely?
7820
 
  - Lift the limitation in condition (B3), that is, make this access method 
 
7951
  - Lift the limitation in condition (B3), that is, make this access method
7821
7952
    applicable to ROLLUP queries.
7822
7953
 
7823
7954
  RETURN
7832
7963
static TRP_GROUP_MIN_MAX *
7833
7964
get_best_group_min_max(PARAM *param, SEL_TREE *tree)
7834
7965
{
7835
 
  THD *thd= param->thd;
7836
 
  JOIN *join= thd->lex->current_select->join;
 
7966
  Session *session= param->session;
 
7967
  JOIN *join= session->lex->current_select->join;
7837
7968
  Table *table= param->table;
7838
7969
  bool have_min= false;              /* true if there is a MIN function. */
7839
7970
  bool have_max= false;              /* true if there is a MAX function. */
7854
7985
 
7855
7986
  /* Perform few 'cheap' tests whether this access method is applicable. */
7856
7987
  if (!join)
7857
 
    return(NULL);        /* This is not a select statement. */
 
7988
    return NULL;        /* This is not a select statement. */
7858
7989
  if ((join->tables != 1) ||  /* The query must reference one table. */
7859
7990
      ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
7860
7991
       (!join->select_distinct)) ||
7861
7992
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
7862
 
    return(NULL);
 
7993
    return NULL;
7863
7994
  if (table->s->keys == 0)        /* There are no indexes to use. */
7864
 
    return(NULL);
 
7995
    return NULL;
7865
7996
 
7866
7997
  /* Analyze the query in more detail. */
7867
7998
  List_iterator<Item> select_items_it(join->fields_list);
7868
7999
 
7869
8000
  /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
7870
8001
  if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
7871
 
    return(NULL);
 
8002
    return NULL;
7872
8003
  if (join->sum_funcs[0])
7873
8004
  {
7874
8005
    Item_sum *min_max_item;
7880
8011
      else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
7881
8012
        have_max= true;
7882
8013
      else
7883
 
        return(NULL);
 
8014
        return NULL;
7884
8015
 
7885
8016
      /* The argument of MIN/MAX. */
7886
 
      Item *expr= min_max_item->args[0]->real_item();    
 
8017
      Item *expr= min_max_item->args[0]->real_item();
7887
8018
      if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */
7888
8019
      {
7889
8020
        if (! min_max_arg_item)
7890
8021
          min_max_arg_item= (Item_field*) expr;
7891
8022
        else if (! min_max_arg_item->eq(expr, 1))
7892
 
          return(NULL);
 
8023
          return NULL;
7893
8024
      }
7894
8025
      else
7895
 
        return(NULL);
 
8026
        return NULL;
7896
8027
    }
7897
8028
  }
7898
8029
 
7902
8033
    while ((item= select_items_it++))
7903
8034
    {
7904
8035
      if (item->type() != Item::FIELD_ITEM)
7905
 
        return(NULL);
 
8036
        return NULL;
7906
8037
    }
7907
8038
  }
7908
8039
 
7910
8041
  for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
7911
8042
  {
7912
8043
    if ((*tmp_group->item)->type() != Item::FIELD_ITEM)
7913
 
      return(NULL);
 
8044
      return NULL;
7914
8045
  }
7915
8046
 
7916
8047
  /*
8094
8225
                                                        &dummy);
8095
8226
        if (!get_constant_key_infix(cur_index_info, index_range_tree,
8096
8227
                                    first_non_group_part, min_max_arg_part,
8097
 
                                    last_part, thd, key_infix, &key_infix_len,
 
8228
                                    last_part, session, key_infix, &key_infix_len,
8098
8229
                                    &first_non_infix_part))
8099
8230
          goto next_index;
8100
8231
      }
8162
8293
      COST_VECT dummy_cost;
8163
8294
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
8164
8295
      uint32_t mrr_bufsize=0;
8165
 
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx, 
8166
 
                                                   false /*don't care*/, 
 
8296
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
 
8297
                                                   false /*don't care*/,
8167
8298
                                                   cur_index_tree, true,
8168
8299
                                                   &mrr_flags, &mrr_bufsize,
8169
8300
                                                   &dummy_cost);
8196
8327
    cur_group_prefix_len= 0;
8197
8328
  }
8198
8329
  if (!index_info) /* No usable index found. */
8199
 
    return(NULL);
 
8330
    return NULL;
8200
8331
 
8201
8332
  /* Check (SA3) for the where clause. */
8202
8333
  if (join->conds && min_max_arg_item &&
8203
8334
      !check_group_min_max_predicates(join->conds, min_max_arg_item, Field::itRAW))
8204
 
    return(NULL);
 
8335
    return NULL;
8205
8336
 
8206
8337
  /* The query passes all tests, so construct a new TRP object. */
8207
8338
  read_plan= new (param->mem_root)
8215
8346
  if (read_plan)
8216
8347
  {
8217
8348
    if (tree && read_plan->quick_prefix_records == 0)
8218
 
      return(NULL);
 
8349
      return NULL;
8219
8350
 
8220
8351
    read_plan->read_cost= best_read_cost;
8221
8352
    read_plan->records=   best_records;
8222
8353
  }
8223
8354
 
8224
 
  return(read_plan);
 
8355
  return read_plan;
8225
8356
}
8226
8357
 
8227
8358
 
8263
8394
    {
8264
8395
      if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,
8265
8396
                                         image_type))
8266
 
        return(false);
 
8397
        return false;
8267
8398
    }
8268
 
    return(true);
 
8399
    return true;
8269
8400
  }
8270
8401
 
8271
8402
  /*
8278
8409
    so.
8279
8410
  */
8280
8411
  if (cond_type == Item::SUBSELECT_ITEM)
8281
 
    return(false);
8282
 
  
 
8412
    return false;
 
8413
 
8283
8414
  /* We presume that at this point there are no other Items than functions. */
8284
8415
  assert(cond_type == Item::FUNC_ITEM);
8285
8416
 
8292
8423
    cur_arg= arguments[arg_idx]->real_item();
8293
8424
    if (cur_arg->type() == Item::FIELD_ITEM)
8294
8425
    {
8295
 
      if (min_max_arg_item->eq(cur_arg, 1)) 
 
8426
      if (min_max_arg_item->eq(cur_arg, 1))
8296
8427
      {
8297
8428
       /*
8298
8429
         If pred references the MIN/MAX argument, check whether pred is a range
8309
8440
            pred_type != Item_func::ISNOTNULL_FUNC &&
8310
8441
            pred_type != Item_func::EQ_FUNC        &&
8311
8442
            pred_type != Item_func::NE_FUNC)
8312
 
          return(false);
 
8443
          return false;
8313
8444
 
8314
8445
        /* Check that pred compares min_max_arg_item with a constant. */
8315
8446
        Item *args[3];
8317
8448
        bool inv;
8318
8449
        /* Test if this is a comparison of a field and a constant. */
8319
8450
        if (!simple_pred(pred, args, &inv))
8320
 
          return(false);
 
8451
          return false;
8321
8452
 
8322
8453
        /* Check for compatible string comparisons - similar to get_mm_leaf. */
8323
8454
        if (args[0] && args[1] && !args[2] && // this is a binary function
8336
8467
             */
8337
8468
             (args[1]->result_type() != STRING_RESULT &&
8338
8469
              min_max_arg_item->field->cmp_type() != args[1]->result_type())))
8339
 
          return(false);
 
8470
          return false;
8340
8471
      }
8341
8472
    }
8342
8473
    else if (cur_arg->type() == Item::FUNC_ITEM)
8343
8474
    {
8344
8475
      if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,
8345
8476
                                         image_type))
8346
 
        return(false);
 
8477
        return false;
8347
8478
    }
8348
8479
    else if (cur_arg->const_item())
8349
8480
    {
8350
 
      return(true);
 
8481
      return true;
8351
8482
    }
8352
8483
    else
8353
 
      return(false);
 
8484
      return false;
8354
8485
  }
8355
8486
 
8356
 
  return(true);
 
8487
  return true;
8357
8488
}
8358
8489
 
8359
8490
 
8367
8498
    first_non_group_part   [in]  First index part after group attribute parts
8368
8499
    min_max_arg_part       [in]  The keypart of the MIN/MAX argument if any
8369
8500
    last_part              [in]  Last keypart of the index
8370
 
    thd                    [in]  Current thread
 
8501
    session                    [in]  Current thread
8371
8502
    key_infix              [out] Infix of constants to be used for index lookup
8372
8503
    key_infix_len          [out] Lenghth of the infix
8373
8504
    first_non_infix_part   [out] The first keypart after the infix (if any)
8374
 
    
 
8505
 
8375
8506
  DESCRIPTION
8376
8507
    Test conditions (NGA1, NGA2) from get_best_group_min_max(). Namely,
8377
8508
    for each keypart field NGF_i not in GROUP-BY, check that there is a
8389
8520
*/
8390
8521
 
8391
8522
static bool
8392
 
get_constant_key_infix(KEY *index_info __attribute__((unused)),
8393
 
                       SEL_ARG *index_range_tree,
 
8523
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
8394
8524
                       KEY_PART_INFO *first_non_group_part,
8395
8525
                       KEY_PART_INFO *min_max_arg_part,
8396
8526
                       KEY_PART_INFO *last_part,
8397
 
                       THD *thd __attribute__((unused)),
8398
 
                       unsigned char *key_infix, uint32_t *key_infix_len,
 
8527
                       Session *, unsigned char *key_infix, uint32_t *key_infix_len,
8399
8528
                       KEY_PART_INFO **first_non_infix_part)
8400
8529
{
8401
8530
  SEL_ARG       *cur_range;
8522
8651
    idx++;
8523
8652
  }
8524
8653
  *param_idx= idx;
8525
 
  return(range_tree->keys[idx]);
 
8654
  return range_tree->keys[idx];
8526
8655
}
8527
8656
 
8528
8657
 
8588
8717
 
8589
8718
void cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
8590
8719
                        uint32_t group_key_parts, SEL_TREE *range_tree,
8591
 
                        SEL_ARG *index_tree __attribute__((unused)),
8592
 
                        ha_rows quick_prefix_records,
 
8720
                        SEL_ARG *, ha_rows quick_prefix_records,
8593
8721
                        bool have_min, bool have_max,
8594
8722
                        double *read_cost, ha_rows *records)
8595
8723
{
8609
8737
  keys_per_block= (table->file->stats.block_size / 2 /
8610
8738
                   (index_info->key_length + table->file->ref_length)
8611
8739
                        + 1);
8612
 
  num_blocks= (uint)(table_records / keys_per_block) + 1;
 
8740
  num_blocks= (uint32_t)(table_records / keys_per_block) + 1;
8613
8741
 
8614
8742
  /* Compute the number of keys in a group. */
8615
8743
  keys_per_group= index_info->rec_per_key[group_key_parts - 1];
8616
8744
  if (keys_per_group == 0) /* If there is no statistics try to guess */
8617
8745
    /* each group contains 10% of all records */
8618
 
    keys_per_group= (uint)(table_records / 10) + 1;
8619
 
  num_groups= (uint)(table_records / keys_per_group) + 1;
 
8746
    keys_per_group= (uint32_t)(table_records / 10) + 1;
 
8747
  num_groups= (uint32_t)(table_records / keys_per_group) + 1;
8620
8748
 
8621
8749
  /* Apply the selectivity of the quick select for group prefixes. */
8622
8750
  if (range_tree && (quick_prefix_records != HA_POS_ERROR))
8623
8751
  {
8624
8752
    quick_prefix_selectivity= (double) quick_prefix_records /
8625
8753
                              (double) table_records;
8626
 
    num_groups= (uint) rint(num_groups * quick_prefix_selectivity);
8627
 
    set_if_bigger(num_groups, 1);
 
8754
    num_groups= (uint32_t) rint(num_groups * quick_prefix_selectivity);
 
8755
    set_if_bigger(num_groups, 1U);
8628
8756
  }
8629
8757
 
8630
8758
  if (used_key_parts > group_key_parts)
8658
8786
 
8659
8787
  *read_cost= io_cost + cpu_cost;
8660
8788
  *records= num_groups;
8661
 
  return;
8662
8789
}
8663
8790
 
8664
8791
 
8684
8811
*/
8685
8812
 
8686
8813
QUICK_SELECT_I *
8687
 
TRP_GROUP_MIN_MAX::make_quick(PARAM *param,
8688
 
                              bool retrieve_full_rows __attribute__((unused)),
8689
 
                              MEM_ROOT *parent_alloc)
 
8814
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
8690
8815
{
8691
8816
  QUICK_GROUP_MIN_MAX_SELECT *quick;
8692
8817
 
8693
8818
  quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table,
8694
 
                                        param->thd->lex->current_select->join,
 
8819
                                        param->session->lex->current_select->join,
8695
8820
                                        have_min, have_max, min_max_arg_part,
8696
8821
                                        group_prefix_len, group_key_parts,
8697
8822
                                        used_key_parts, index_info, index,
8698
8823
                                        read_cost, records, key_infix_len,
8699
8824
                                        key_infix, parent_alloc);
8700
8825
  if (!quick)
8701
 
    return(NULL);
 
8826
    return NULL;
8702
8827
 
8703
8828
  if (quick->init())
8704
8829
  {
8705
8830
    delete quick;
8706
 
    return(NULL);
 
8831
    return NULL;
8707
8832
  }
8708
8833
 
8709
8834
  if (range_tree)
8742
8867
        {
8743
8868
          delete quick;
8744
8869
          quick= NULL;
8745
 
          return(NULL);
 
8870
          return NULL;
8746
8871
        }
8747
8872
        min_max_range= min_max_range->next;
8748
8873
      }
8754
8879
  quick->update_key_stat();
8755
8880
  quick->adjust_prefix_ranges();
8756
8881
 
8757
 
  return(quick);
 
8882
  return quick;
8758
8883
}
8759
8884
 
8760
8885
 
8819
8944
  assert(!parent_alloc);
8820
8945
  if (!parent_alloc)
8821
8946
  {
8822
 
    init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8823
 
    join->thd->mem_root= &alloc;
 
8947
    init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
 
8948
    join->session->mem_root= &alloc;
8824
8949
  }
8825
8950
  else
8826
8951
    memset(&alloc, 0, sizeof(MEM_ROOT));  // ensure that it's not used
8832
8957
 
8833
8958
  SYNOPSIS
8834
8959
    QUICK_GROUP_MIN_MAX_SELECT::init()
8835
 
  
 
8960
 
8836
8961
  DESCRIPTION
8837
8962
    The method performs initialization that cannot be done in the constructor
8838
8963
    such as memory allocations that may fail. It allocates memory for the
8923
9048
 
8924
9049
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8925
9050
{
8926
 
  if (file->inited != handler::NONE) 
 
9051
  if (file->inited != handler::NONE)
8927
9052
    file->ha_index_end();
8928
9053
  if (min_max_arg_part)
8929
9054
    delete_dynamic(&min_max_ranges);
8931
9056
  delete min_functions_it;
8932
9057
  delete max_functions_it;
8933
9058
  delete quick_prefix_select;
8934
 
  return; 
8935
9059
}
8936
9060
 
8937
9061
 
8940
9064
 
8941
9065
  SYNOPSIS
8942
9066
    QUICK_GROUP_MIN_MAX_SELECT::add_range()
8943
 
    sel_range  Range object from which a 
 
9067
    sel_range  Range object from which a
8944
9068
 
8945
9069
  NOTES
8946
9070
    Construct a new QUICK_RANGE object from a SEL_ARG object, and
8994
9118
 
8995
9119
  NOTES
8996
9120
    quick_prefix_select is made over the conditions on the whole key.
8997
 
    It defines a number of ranges of length x. 
8998
 
    However when jumping through the prefixes we use only the the first 
 
9121
    It defines a number of ranges of length x.
 
9122
    However when jumping through the prefixes we use only the the first
8999
9123
    few most significant keyparts in the range key. However if there
9000
 
    are more keyparts to follow the ones we are using we must make the 
9001
 
    condition on the key inclusive (because x < "ab" means 
 
9124
    are more keyparts to follow the ones we are using we must make the
 
9125
    condition on the key inclusive (because x < "ab" means
9002
9126
    x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9003
9127
    To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9004
9128
*/
9108
9232
 
9109
9233
  file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9110
9234
  if ((result= file->ha_index_init(index,1)))
9111
 
    return(result);
 
9235
    return result;
9112
9236
  if (quick_prefix_select && quick_prefix_select->reset())
9113
 
    return(1);
 
9237
    return 0;
9114
9238
  result= file->index_last(record);
9115
9239
  if (result == HA_ERR_END_OF_FILE)
9116
 
    return(0);
 
9240
    return 0;
9117
9241
  /* Save the prefix of the last group. */
9118
9242
  key_copy(last_prefix, record, index_info, group_prefix_len);
9119
9243
 
9120
 
  return(0);
 
9244
  return 0;
9121
9245
}
9122
9246
 
9123
9247
 
9124
9248
 
9125
 
/* 
 
9249
/*
9126
9250
  Get the next key containing the MIN and/or MAX key for the next group.
9127
9251
 
9128
9252
  SYNOPSIS
9173
9297
                              group_prefix_len);
9174
9298
      assert(is_last_prefix <= 0);
9175
9299
    }
9176
 
    else 
 
9300
    else
9177
9301
    {
9178
9302
      if (result == HA_ERR_KEY_NOT_FOUND)
9179
9303
        continue;
9194
9318
      if (max_res == 0)
9195
9319
        update_max_result();
9196
9320
      /* If a MIN was found, a MAX must have been found as well. */
9197
 
      assert((have_max && !have_min) ||
9198
 
                  (have_max && have_min && (max_res == 0)));
 
9321
      assert(((have_max && !have_min) ||
 
9322
                  (have_max && have_min && (max_res == 0))));
9199
9323
    }
9200
9324
    /*
9201
9325
      If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9224
9348
  else if (result == HA_ERR_KEY_NOT_FOUND)
9225
9349
    result= HA_ERR_END_OF_FILE;
9226
9350
 
9227
 
  return(result);
 
9351
  return result;
9228
9352
}
9229
9353
 
9230
9354
 
9259
9383
  if (min_max_ranges.elements > 0)
9260
9384
  {
9261
9385
    if ((result= next_min_in_range()))
9262
 
      return(result);
 
9386
      return result;
9263
9387
  }
9264
9388
  else
9265
9389
  {
9269
9393
      if ((result= file->index_read_map(record, group_prefix,
9270
9394
                                        make_prev_keypart_map(real_key_parts),
9271
9395
                                        HA_READ_KEY_EXACT)))
9272
 
        return(result);
 
9396
        return result;
9273
9397
    }
9274
9398
 
9275
9399
    /*
9310
9434
    If the MIN attribute is non-nullable, this->record already contains the
9311
9435
    MIN key in the group, so just return.
9312
9436
  */
9313
 
  return(result);
 
9437
  return result;
9314
9438
}
9315
9439
 
9316
9440
 
9317
 
/* 
 
9441
/*
9318
9442
  Retrieve the maximal key in the next group.
9319
9443
 
9320
9444
  SYNOPSIS
9341
9465
    result= file->index_read_map(record, group_prefix,
9342
9466
                                 make_prev_keypart_map(real_key_parts),
9343
9467
                                 HA_READ_PREFIX_LAST);
9344
 
  return(result);
 
9468
  return result;
9345
9469
}
9346
9470
 
9347
9471
 
9375
9499
    unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9376
9500
    if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9377
9501
                         make_prev_keypart_map(group_key_parts), cur_prefix)))
9378
 
      return(result);
 
9502
      return result;
9379
9503
    seen_first_key= true;
9380
9504
  }
9381
9505
  else
9384
9508
    {
9385
9509
      result= file->index_first(record);
9386
9510
      if (result)
9387
 
        return(result);
 
9511
        return result;
9388
9512
      seen_first_key= true;
9389
9513
    }
9390
9514
    else
9394
9518
                                   make_prev_keypart_map(group_key_parts),
9395
9519
                                   HA_READ_AFTER_KEY);
9396
9520
      if (result)
9397
 
        return(result);
 
9521
        return result;
9398
9522
    }
9399
9523
  }
9400
9524
 
9405
9529
    memcpy(group_prefix + group_prefix_len,
9406
9530
           key_infix, key_infix_len);
9407
9531
 
9408
 
  return(0);
 
9532
  return 0;
9409
9533
}
9410
9534
 
9411
9535
 
9437
9561
  QUICK_RANGE *cur_range;
9438
9562
  bool found_null= false;
9439
9563
  int result= HA_ERR_KEY_NOT_FOUND;
 
9564
  basic_string<unsigned char> max_key;
 
9565
 
 
9566
  max_key.reserve(real_prefix_len + min_max_arg_len);
9440
9567
 
9441
9568
  assert(min_max_ranges.elements > 0);
9442
9569
 
9510
9637
    if ( !(cur_range->flag & NO_MAX_RANGE) )
9511
9638
    {
9512
9639
      /* Compose the MAX key for the range. */
9513
 
      unsigned char *max_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9514
 
      memcpy(max_key, group_prefix, real_prefix_len);
9515
 
      memcpy(max_key + real_prefix_len, cur_range->max_key,
9516
 
             cur_range->max_length);
 
9640
      max_key.clear();
 
9641
      max_key.append(group_prefix, real_prefix_len);
 
9642
      max_key.append(cur_range->max_key, cur_range->max_length);
9517
9643
      /* Compare the found key with max_key. */
9518
 
      int cmp_res= key_cmp(index_info->key_part, max_key,
 
9644
      int cmp_res= key_cmp(index_info->key_part,
 
9645
                           max_key.data(),
9519
9646
                           real_prefix_len + min_max_arg_len);
9520
9647
      if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9521
9648
      {
9568
9695
  key_part_map keypart_map;
9569
9696
  QUICK_RANGE *cur_range;
9570
9697
  int result;
 
9698
  basic_string<unsigned char> min_key;
 
9699
  min_key.reserve(real_prefix_len + min_max_arg_len);
9571
9700
 
9572
9701
  assert(min_max_ranges.elements > 0);
9573
9702
 
9627
9756
    if ( !(cur_range->flag & NO_MIN_RANGE) )
9628
9757
    {
9629
9758
      /* Compose the MIN key for the range. */
9630
 
      unsigned char *min_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9631
 
      memcpy(min_key, group_prefix, real_prefix_len);
9632
 
      memcpy(min_key + real_prefix_len, cur_range->min_key,
9633
 
             cur_range->min_length);
 
9759
      min_key.clear();
 
9760
      min_key.append(group_prefix, real_prefix_len);
 
9761
      min_key.append(cur_range->min_key, cur_range->min_length);
 
9762
 
9634
9763
      /* Compare the found key with min_key. */
9635
 
      int cmp_res= key_cmp(index_info->key_part, min_key,
 
9764
      int cmp_res= key_cmp(index_info->key_part,
 
9765
                           min_key.data(),
9636
9766
                           real_prefix_len + min_max_arg_len);
9637
9767
      if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9638
9768
            (cmp_res >= 0)))
9735
9865
  used_lengths->append(buf, length);
9736
9866
}
9737
9867
 
9738
 
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9739
 
                           const char *msg __attribute__((unused)))
 
9868
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9740
9869
{
9741
9870
  SEL_ARG **key,**end;
9742
9871
  int idx;
9758
9887
  }
9759
9888
  if (!tmp.length())
9760
9889
    tmp.append(STRING_WITH_LEN("(empty)"));
9761
 
 
9762
 
  return;
9763
9890
}
9764
9891
 
9765
9892
 
9766
9893
static void print_ror_scans_arr(Table *table,
9767
 
                                const char *msg __attribute__((unused)),
9768
 
                                struct st_ror_scan_info **start,
 
9894
                                const char *, struct st_ror_scan_info **start,
9769
9895
                                struct st_ror_scan_info **end)
9770
9896
{
9771
9897
  char buff[1024];
9779
9905
  }
9780
9906
  if (!tmp.length())
9781
9907
    tmp.append(STRING_WITH_LEN("(empty)"));
9782
 
  return;
9783
9908
}
9784
9909
 
9785
9910
/*****************************************************************************
9786
 
** Instantiate templates 
 
9911
** Instantiate templates
9787
9912
*****************************************************************************/
9788
9913
 
9789
9914
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION