← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

  • Committer: Brian Aker
  • Date: 2009-04-27 14:36:40 UTC
  • Revision ID: brian@gaz-20090427143640-f6zjmtt9vm55qgm2
Patch on show processlist from  davi@apache.org

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
#include <bitset>
 
118
 
 
119
using namespace std;
113
120
 
114
121
/*
115
122
  Convert double value to #rows. Currently this does floor(), and we
116
123
  might consider using round() instead.
117
124
*/
118
 
#define double2rows(x) ((ha_rows)(x))
 
125
static inline ha_rows double2rows(double x)
 
126
{
 
127
    return static_cast<ha_rows>(x);
 
128
}
119
129
 
120
130
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
121
131
 
124
134
class RANGE_OPT_PARAM;
125
135
/*
126
136
  A construction block of the SEL_ARG-graph.
127
 
  
128
 
  The following description only covers graphs of SEL_ARG objects with 
 
137
 
 
138
  The following description only covers graphs of SEL_ARG objects with
129
139
  sel_arg->type==KEY_RANGE:
130
140
 
131
141
  One SEL_ARG object represents an "elementary interval" in form
132
 
  
 
142
 
133
143
      min_value <=?  table.keypartX  <=? max_value
134
 
  
 
144
 
135
145
  The interval is a non-empty interval of any kind: with[out] minimum/maximum
136
146
  bound, [half]open/closed, single-point interval, etc.
137
147
 
138
148
  1. SEL_ARG GRAPH STRUCTURE
139
 
  
 
149
 
140
150
  SEL_ARG objects are linked together in a graph. The meaning of the graph
141
151
  is better demostrated by an example:
142
 
  
 
152
 
143
153
     tree->keys[i]
144
 
      | 
 
154
      |
145
155
      |             $              $
146
156
      |    part=1   $     part=2   $    part=3
147
157
      |             $              $
150
160
      |  +-------+  $   +-------+  $   +--------+
151
161
      |      |      $              $       |
152
162
      |      |      $              $   +--------+
153
 
      |      |      $              $   | kp3=12 | 
154
 
      |      |      $              $   +--------+ 
155
 
      |  +-------+  $              $   
156
 
      \->| kp1=2 |--$--------------$-+ 
 
163
      |      |      $              $   | kp3=12 |
 
164
      |      |      $              $   +--------+
 
165
      |  +-------+  $              $
 
166
      \->| kp1=2 |--$--------------$-+
157
167
         +-------+  $              $ |   +--------+
158
168
             |      $              $  ==>| kp3=11 |
159
169
         +-------+  $              $ |   +--------+
161
171
         +-------+  $              $     +--------+
162
172
             |      $              $     | kp3=14 |
163
173
            ...     $              $     +--------+
164
 
 
 
174
 
165
175
  The entire graph is partitioned into "interval lists".
166
176
 
167
177
  An interval list is a sequence of ordered disjoint intervals over the same
168
178
  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 
 
179
  all intervals in the list form an RB-tree, linked via left/right/parent
170
180
  pointers. The RB-tree root SEL_ARG object will be further called "root of the
171
181
  interval list".
172
 
  
173
 
    In the example pic, there are 4 interval lists: 
 
182
 
 
183
    In the example pic, there are 4 interval lists:
174
184
    "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
175
185
    The vertical lines represent SEL_ARG::next/prev pointers.
176
 
    
 
186
 
177
187
  In an interval list, each member X may have SEL_ARG::next_key_part pointer
178
188
  pointing to the root of another interval list Y. The pointed interval list
179
189
  must cover a key part with greater number (i.e. Y->part > X->part).
180
 
    
 
190
 
181
191
    In the example pic, the next_key_part pointers are represented by
182
192
    horisontal lines.
183
193
 
185
195
 
186
196
  It represents a condition in a special form (we don't have a name for it ATM)
187
197
  The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
188
 
  
 
198
 
189
199
  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 
 
200
   (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
 
201
   (kp1=2 AND (kp3=11 OR kp3=14)) OR
192
202
   (kp1=3 AND (kp3=11 OR kp3=14))
193
203
 
194
204
 
197
207
  Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
198
208
  Then walk the SEL_ARG graph and get a list of dijsoint ordered key
199
209
  intervals (i.e. intervals in form
200
 
  
 
210
 
201
211
   (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
202
212
 
203
213
  Those intervals can be used to access the index. The uses are in:
208
218
                            and create QUICK_RANGE_SELECT object that will
209
219
                            read records within these intervals.
210
220
 
211
 
  4. SPACE COMPLEXITY NOTES 
 
221
  4. SPACE COMPLEXITY NOTES
212
222
 
213
223
    SEL_ARG graph is a representation of an ordered disjoint sequence of
214
224
    intervals over the ordered set of index tuple values.
215
225
 
216
226
    For multi-part keys, one can construct a WHERE expression such that its
217
227
    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 
 
228
 
 
229
      (keypart1 IN (1,2, ..., n1)) AND
 
230
      (keypart2 IN (1,2, ..., n2)) AND
221
231
      (keypart3 IN (1,2, ..., n3))
222
 
    
 
232
 
223
233
    For this WHERE clause the list of intervals will have n1*n2*n3 intervals
224
234
    of form
225
 
     
 
235
 
226
236
      (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
227
 
    
 
237
 
228
238
    SEL_ARG graph structure aims to reduce the amount of required space by
229
239
    "sharing" the elementary intervals when possible (the pic at the
230
 
    beginning of this comment has examples of such sharing). The sharing may 
 
240
    beginning of this comment has examples of such sharing). The sharing may
231
241
    prevent combinatorial blowup:
232
242
 
233
243
      There are WHERE clauses that have combinatorial-size interval lists but
234
244
      will be represented by a compact SEL_ARG graph.
235
245
      Example:
236
 
        (keypartN IN (1,2, ..., n1)) AND 
 
246
        (keypartN IN (1,2, ..., n1)) AND
237
247
        ...
238
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
248
        (keypart2 IN (1,2, ..., n2)) AND
239
249
        (keypart1 IN (1,2, ..., n3))
240
250
 
241
251
    but not in all cases:
244
254
      representation but get_mm_tree() and its callees will construct a
245
255
      graph of combinatorial size.
246
256
      Example:
247
 
        (keypart1 IN (1,2, ..., n1)) AND 
248
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
257
        (keypart1 IN (1,2, ..., n1)) AND
 
258
        (keypart2 IN (1,2, ..., n2)) AND
249
259
        ...
250
260
        (keypartN IN (1,2, ..., n3))
251
261
 
255
265
        By induction: Let's take any interval on some keypart in the middle:
256
266
 
257
267
           kp15=c0
258
 
        
 
268
 
259
269
        Then let's AND it with this interval 'structure' from preceding and
260
270
        following keyparts:
261
271
 
262
272
          (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
263
 
        
 
273
 
264
274
        We will obtain this SEL_ARG graph:
265
 
 
 
275
 
266
276
             kp14     $      kp15      $      kp16
267
277
                      $                $
268
278
         +---------+  $   +---------+  $   +---------+
269
279
         | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
270
280
         +---------+  $   +---------+  $   +---------+
271
 
              |       $                $              
272
 
         +---------+  $   +---------+  $             
273
 
         | kp14=c2 |--$-->| kp15=c0 |  $             
274
 
         +---------+  $   +---------+  $             
 
281
              |       $                $
 
282
         +---------+  $   +---------+  $
 
283
         | kp14=c2 |--$-->| kp15=c0 |  $
 
284
         +---------+  $   +---------+  $
275
285
                      $                $
276
 
                      
 
286
 
277
287
       Note that we had to duplicate "kp15=c0" and there was no way to avoid
278
 
       that. 
 
288
       that.
279
289
       The induction step: AND the obtained expression with another "wrapping"
280
290
       expression like (*).
281
 
       When the process ends because of the limit on max. number of keyparts 
 
291
       When the process ends because of the limit on max. number of keyparts
282
292
       we'll have:
283
293
 
284
294
         WHERE clause length  is O(3*#max_keyparts)
298
308
  uint8_t min_flag,max_flag,maybe_flag;
299
309
  uint8_t part;                                 // Which key part
300
310
  uint8_t maybe_null;
301
 
  /* 
 
311
  /*
302
312
    Number of children of this element in the RB-tree, plus 1 for this
303
313
    element itself.
304
314
  */
319
329
  SEL_ARG *left,*right;   /* R-B tree children */
320
330
  SEL_ARG *next,*prev;    /* Links for bi-directional interval list */
321
331
  SEL_ARG *parent;        /* R-B tree parent */
322
 
  SEL_ARG *next_key_part; 
 
332
  SEL_ARG *next_key_part;
323
333
  enum leaf_color { BLACK,RED } color;
324
334
  enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
325
335
 
345
355
  inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
346
356
  inline void maybe_smaller() { maybe_flag=1; }
347
357
  /* Return true iff it's a single-point null interval */
348
 
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; } 
 
358
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
349
359
  inline int cmp_min_to_min(SEL_ARG* arg)
350
360
  {
351
361
    return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
482
492
    uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
483
493
                                  range_key, *range_key_flag);
484
494
    *range_key_flag|= key_tree->min_flag;
485
 
    
 
495
 
486
496
    if (key_tree->next_key_part &&
487
497
        key_tree->next_key_part->part == key_tree->part+1 &&
488
498
        !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
556
566
 
557
567
    SYNOPSIS
558
568
      is_singlepoint()
559
 
    
 
569
 
560
570
    DESCRIPTION
561
571
      Check if this SEL_ARG object (not tree) represents a single-point
562
 
      interval, i.e. if it represents a "keypart = const" or 
 
572
      interval, i.e. if it represents a "keypart = const" or
563
573
      "keypart IS NULL".
564
574
 
565
575
    RETURN
569
579
 
570
580
  bool is_singlepoint()
571
581
  {
572
 
    /* 
573
 
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field) 
 
582
    /*
 
583
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
574
584
      flags, and the same for right edge.
575
585
    */
576
586
    if (min_flag || max_flag)
602
612
public:
603
613
  /*
604
614
    Starting an effort to document this field:
605
 
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) => 
 
615
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
606
616
       (type == SEL_TREE::IMPOSSIBLE)
607
617
  */
608
618
  enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
639
649
class RANGE_OPT_PARAM
640
650
{
641
651
public:
642
 
  THD   *thd;   /* Current thread handle */
 
652
  Session       *session;   /* Current thread handle */
643
653
  Table *table; /* Table being analyzed */
644
654
  COND *cond;   /* Used inside get_mm_tree(). */
645
655
  table_map prev_tables;
656
666
    #keys elements are not empty)
657
667
  */
658
668
  uint32_t keys;
659
 
  
660
 
  /* 
 
669
 
 
670
  /*
661
671
    If true, the index descriptions describe real indexes (and it is ok to
662
672
    call field->optimize_range(real_keynr[...], ...).
663
673
    Otherwise index description describes fake indexes.
664
674
  */
665
675
  bool using_real_indexes;
666
 
  
 
676
 
667
677
  bool remove_jump_scans;
668
 
  
 
678
 
669
679
  /*
670
680
    used_key_no -> table_key_no translation table. Only makes sense if
671
681
    using_real_indexes==true
672
682
  */
673
683
  uint32_t real_keynr[MAX_KEY];
674
684
  /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
675
 
  uint32_t alloced_sel_args; 
 
685
  uint32_t alloced_sel_args;
676
686
  bool force_default_mrr;
677
687
};
678
688
 
689
699
  bool quick;                           // Don't calulate possible keys
690
700
 
691
701
  uint32_t fields_bitmap_size;
692
 
  MY_BITMAP needed_fields;    /* bitmask of fields needed by the query */
693
 
  MY_BITMAP tmp_covered_fields;
 
702
  bitset<MAX_FIELDS> needed_fields; /* bitmask of fields needed by the query */
 
703
  bitset<MAX_FIELDS> tmp_covered_fields;
694
704
 
695
705
  key_map *needed_reg;        /* ptr to SQL_SELECT::needed_reg */
696
706
 
722
732
 
723
733
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
724
734
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
725
 
                                  SEL_ARG *tree, bool update_tbl_stats, 
 
735
                                  SEL_ARG *tree, bool update_tbl_stats,
726
736
                                  uint32_t *mrr_flags, uint32_t *bufsize,
727
737
                                  COST_VECT *cost);
728
738
                                  //bool update_tbl_stats);
732
742
*/
733
743
 
734
744
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
735
 
                                     SEL_ARG *key_tree, uint32_t mrr_flags, 
 
745
                                     SEL_ARG *key_tree, uint32_t mrr_flags,
736
746
                                     uint32_t mrr_buf_size, MEM_ROOT *alloc);
737
747
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
738
748
                                       bool index_read_must_be_used,
1009
1019
  *error=0;
1010
1020
 
1011
1021
  if (!conds && !allow_null_cond)
1012
 
    return(0);
 
1022
    return 0;
1013
1023
  if (!(select= new SQL_SELECT))
1014
1024
  {
1015
1025
    *error= 1;                  // out of memory
1016
 
    return(0);          /* purecov: inspected */
 
1026
    return 0;           /* purecov: inspected */
1017
1027
  }
1018
1028
  select->read_tables=read_tables;
1019
1029
  select->const_tables=const_tables;
1025
1035
    select->file= *head->sort.io_cache;
1026
1036
    select->records=(ha_rows) (select->file.end_of_file/
1027
1037
                               head->file->ref_length);
1028
 
    free(head->sort.io_cache);
 
1038
    delete head->sort.io_cache;
1029
1039
    head->sort.io_cache=0;
1030
1040
  }
1031
1041
  return(select);
1058
1068
  cleanup();
1059
1069
}
1060
1070
 
 
1071
 
 
1072
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
 
1073
                             ha_rows limit)
 
1074
{
 
1075
  key_map tmp;
 
1076
  tmp.set_all();
 
1077
  return test_quick_select(session, tmp, 0, limit,
 
1078
                           force_quick_range, false) < 0;
 
1079
}
 
1080
 
 
1081
 
 
1082
bool SQL_SELECT::skip_record()
 
1083
{
 
1084
  return cond ? cond->val_int() == 0 : 0;
 
1085
}
 
1086
 
 
1087
 
1061
1088
QUICK_SELECT_I::QUICK_SELECT_I()
1062
1089
  :max_used_key_length(0),
1063
1090
   used_key_parts(0)
1064
1091
{}
1065
1092
 
1066
 
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, Table *table, uint32_t key_nr,
1067
 
                                       bool no_alloc, MEM_ROOT *parent_alloc,
1068
 
                                       bool *create_error)
 
1093
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
 
1094
                                       bool no_alloc, MEM_ROOT *parent_alloc)
1069
1095
  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1070
1096
{
1071
 
  my_bitmap_map *bitmap;
1072
 
 
1073
1097
  in_ror_merged_scan= 0;
1074
1098
  sorted= 0;
1075
1099
  index= key_nr;
1077
1101
  key_part_info= head->key_info[index].key_part;
1078
1102
  my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1079
1103
 
1080
 
  /* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1081
 
  mrr_buf_size= thd->variables.read_rnd_buff_size;
 
1104
  /* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
 
1105
  mrr_buf_size= session->variables.read_rnd_buff_size;
1082
1106
  mrr_buf_desc= NULL;
1083
1107
 
1084
1108
  if (!no_alloc && !parent_alloc)
1085
1109
  {
1086
1110
    // Allocates everything through the internal memroot
1087
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1088
 
    thd->mem_root= &alloc;
 
1111
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1112
    session->mem_root= &alloc;
1089
1113
  }
1090
1114
  else
1091
1115
    memset(&alloc, 0, sizeof(alloc));
1094
1118
  save_read_set= head->read_set;
1095
1119
  save_write_set= head->write_set;
1096
1120
 
1097
 
  /* 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))))
1100
 
  {
1101
 
    column_bitmap.bitmap= 0;
1102
 
    *create_error= 1;
1103
 
  }
1104
 
  else
1105
 
    bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1106
1121
  return;
1107
1122
}
1108
1123
 
1127
1142
  if (!dont_free)
1128
1143
  {
1129
1144
    /* file is NULL for CPK scan on covering ROR-intersection */
1130
 
    if (file) 
 
1145
    if (file)
1131
1146
    {
1132
1147
      range_end();
1133
1148
      if (head->key_read)
1137
1152
      }
1138
1153
      if (free_file)
1139
1154
      {
1140
 
        file->ha_external_lock(current_thd, F_UNLCK);
 
1155
        file->ha_external_lock(current_session, F_UNLCK);
1141
1156
        file->close();
1142
1157
        delete file;
1143
1158
      }
1144
1159
    }
1145
1160
    delete_dynamic(&ranges); /* ranges are allocated in alloc */
1146
1161
    free_root(&alloc,MYF(0));
1147
 
    free((char*) column_bitmap.bitmap);
1148
1162
  }
1149
1163
  head->column_bitmaps_set(save_read_set, save_write_set);
1150
1164
  if (mrr_buf_desc)
1153
1167
}
1154
1168
 
1155
1169
 
1156
 
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
 
1170
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1157
1171
                                                   Table *table)
1158
 
  :pk_quick_select(NULL), thd(thd_param)
 
1172
  :pk_quick_select(NULL), session(session_param)
1159
1173
{
1160
1174
  index= MAX_KEY;
1161
1175
  head= table;
1162
1176
  memset(&read_record, 0, sizeof(read_record));
1163
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1177
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1164
1178
  return;
1165
1179
}
1166
1180
 
1167
1181
int QUICK_INDEX_MERGE_SELECT::init()
1168
1182
{
1169
 
  return(0);
 
1183
  return 0;
1170
1184
}
1171
1185
 
1172
1186
int QUICK_INDEX_MERGE_SELECT::reset()
1203
1217
}
1204
1218
 
1205
1219
 
1206
 
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
 
1220
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1207
1221
                                                       Table *table,
1208
1222
                                                       bool retrieve_full_rows,
1209
1223
                                                       MEM_ROOT *parent_alloc)
1210
 
  : cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
 
1224
  : cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1211
1225
    scans_inited(false)
1212
1226
{
1213
1227
  index= MAX_KEY;
1214
1228
  head= table;
1215
1229
  record= head->record[0];
1216
1230
  if (!parent_alloc)
1217
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1231
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1218
1232
  else
1219
1233
    memset(&alloc, 0, sizeof(MEM_ROOT));
1220
1234
  last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1264
1278
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1265
1279
{
1266
1280
  handler *save_file= file, *org_file;
1267
 
  THD *thd;
 
1281
  Session *session;
1268
1282
 
1269
1283
  in_ror_merged_scan= 1;
1270
1284
  if (reuse_handler)
1271
1285
  {
1272
1286
    if (init() || reset())
1273
1287
    {
1274
 
      return(1);
 
1288
      return 0;
1275
1289
    }
1276
1290
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1277
1291
    goto end;
1281
1295
  if (free_file)
1282
1296
  {
1283
1297
    /* already have own 'handler' object. */
1284
 
    return(0);
 
1298
    return 0;
1285
1299
  }
1286
1300
 
1287
 
  thd= head->in_use;
1288
 
  if (!(file= head->file->clone(thd->mem_root)))
 
1301
  session= head->in_use;
 
1302
  if (!(file= head->file->clone(session->mem_root)))
1289
1303
  {
1290
 
    /* 
 
1304
    /*
1291
1305
      Manually set the error flag. Note: there seems to be quite a few
1292
1306
      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. 
 
1307
      sending no response to a query. ATM those are not real errors because
 
1308
      the storage engine calls in question happen to never fail with the
 
1309
      existing storage engines.
1296
1310
    */
1297
1311
    my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1298
1312
    /* Caller will free the memory */
1301
1315
 
1302
1316
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1303
1317
 
1304
 
  if (file->ha_external_lock(thd, F_RDLCK))
 
1318
  if (file->ha_external_lock(session, F_RDLCK))
1305
1319
    goto failure;
1306
1320
 
1307
1321
  if (init() || reset())
1308
1322
  {
1309
 
    file->ha_external_lock(thd, F_UNLCK);
 
1323
    file->ha_external_lock(session, F_UNLCK);
1310
1324
    file->close();
1311
1325
    goto failure;
1312
1326
  }
1330
1344
  }
1331
1345
  head->prepare_for_position();
1332
1346
  head->file= org_file;
1333
 
  bitmap_copy(&column_bitmap, head->read_set);
 
1347
  column_bitmap= *(head->read_set);
1334
1348
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1335
1349
 
1336
 
  return(0);
 
1350
  return 0;
1337
1351
 
1338
1352
failure:
1339
1353
  head->column_bitmaps_set(save_read_set, save_write_set);
1340
1354
  delete file;
1341
1355
  file= save_file;
1342
 
  return(1);
 
1356
  return 0;
 
1357
}
 
1358
 
 
1359
 
 
1360
void QUICK_RANGE_SELECT::save_last_pos()
 
1361
{
 
1362
  file->position(record);
1343
1363
}
1344
1364
 
1345
1365
 
1368
1388
      selects.
1369
1389
    */
1370
1390
    if (quick->init_ror_merged_scan(true))
1371
 
      return(1);
 
1391
      return 0;
1372
1392
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1373
1393
  }
1374
1394
  while ((quick= quick_it++))
1375
1395
  {
1376
1396
    if (quick->init_ror_merged_scan(false))
1377
 
      return(1);
 
1397
      return 0;
1378
1398
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1379
1399
    /* All merged scans share the same record buffer in intersection. */
1380
1400
    quick->record= head->record[0];
1382
1402
 
1383
1403
  if (need_to_fetch_row && head->file->ha_rnd_init(1))
1384
1404
  {
1385
 
    return(1);
 
1405
    return 0;
1386
1406
  }
1387
 
  return(0);
 
1407
  return 0;
1388
1408
}
1389
1409
 
1390
1410
 
1400
1420
int QUICK_ROR_INTERSECT_SELECT::reset()
1401
1421
{
1402
1422
  if (!scans_inited && init_ror_merged_scan(true))
1403
 
    return(1);
 
1423
    return 0;
1404
1424
  scans_inited= true;
1405
1425
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1406
1426
  QUICK_RANGE_SELECT *quick;
1407
1427
  while ((quick= it++))
1408
1428
    quick->reset();
1409
 
  return(0);
 
1429
  return 0;
1410
1430
}
1411
1431
 
1412
1432
 
1442
1462
}
1443
1463
 
1444
1464
 
1445
 
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
 
1465
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1446
1466
                                               Table *table)
1447
 
  : thd(thd_param), scans_inited(false)
 
1467
  : session(session_param), scans_inited(false)
1448
1468
{
1449
1469
  index= MAX_KEY;
1450
1470
  head= table;
1451
1471
  rowid_length= table->file->ref_length;
1452
1472
  record= head->record[0];
1453
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1454
 
  thd_param->mem_root= &alloc;
 
1473
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1474
  session_param->mem_root= &alloc;
1455
1475
}
1456
1476
 
 
1477
/*
 
1478
 * Function object that is used as the comparison function
 
1479
 * for the priority queue in the QUICK_ROR_UNION_SELECT
 
1480
 * class.
 
1481
 */
 
1482
class compare_functor
 
1483
{
 
1484
  QUICK_ROR_UNION_SELECT *self;
 
1485
  public:
 
1486
  compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
 
1487
    : self(in_arg) { }
 
1488
  inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
 
1489
  {
 
1490
    int val= self->head->file->cmp_ref(i->last_rowid,
 
1491
                                       j->last_rowid);
 
1492
    return (val >= 0);
 
1493
  }
 
1494
};
1457
1495
 
1458
1496
/*
1459
1497
  Do post-constructor initialization.
1467
1505
 
1468
1506
int QUICK_ROR_UNION_SELECT::init()
1469
1507
{
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
 
 
 
1508
  queue= 
 
1509
    new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
1478
1510
  if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1479
 
    return(1);
 
1511
    return 0;
1480
1512
  prev_rowid= cur_rowid + head->file->ref_length;
1481
 
  return(0);
 
1513
  return 0;
1482
1514
}
1483
1515
 
1484
1516
 
1493
1525
      val2  Second merged select
1494
1526
*/
1495
1527
 
1496
 
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
 
1528
int quick_ror_union_select_queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1497
1529
{
1498
1530
  QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1499
1531
  return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1522
1554
    while ((quick= it++))
1523
1555
    {
1524
1556
      if (quick->init_ror_merged_scan(false))
1525
 
        return(1);
 
1557
        return 0;
1526
1558
    }
1527
1559
    scans_inited= true;
1528
1560
  }
1529
 
  queue_remove_all(&queue);
 
1561
  while (!queue->empty())
 
1562
    queue->pop();
1530
1563
  /*
1531
1564
    Initialize scans for merged quick selects and put all merged quick
1532
1565
    selects into the queue.
1535
1568
  while ((quick= it++))
1536
1569
  {
1537
1570
    if (quick->reset())
1538
 
      return(1);
 
1571
      return 0;
1539
1572
    if ((error= quick->get_next()))
1540
1573
    {
1541
1574
      if (error == HA_ERR_END_OF_FILE)
1543
1576
      return(error);
1544
1577
    }
1545
1578
    quick->save_last_pos();
1546
 
    queue_insert(&queue, (unsigned char*)quick);
 
1579
    queue->push(quick);
1547
1580
  }
1548
1581
 
1549
1582
  if (head->file->ha_rnd_init(1))
1550
1583
  {
1551
 
    return(1);
 
1584
    return 0;
1552
1585
  }
1553
1586
 
1554
 
  return(0);
 
1587
  return 0;
1555
1588
}
1556
1589
 
1557
1590
 
1563
1596
 
1564
1597
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1565
1598
{
1566
 
  delete_queue(&queue);
 
1599
  while (!queue->empty())
 
1600
    queue->pop();
 
1601
  delete queue;
1567
1602
  quick_selects.delete_elements();
1568
1603
  if (head->file->inited != handler::NONE)
1569
1604
    head->file->ha_rnd_end();
1623
1658
  left=right= &null_element;
1624
1659
}
1625
1660
 
1626
 
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, 
 
1661
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1627
1662
                        SEL_ARG **next_arg)
1628
1663
{
1629
1664
  SEL_ARG *tmp;
1759
1794
      limit  Number of records that will be retrieved
1760
1795
 
1761
1796
  DESCRIPTION
1762
 
    Find the best index that allows to retrieve first #limit records in the 
 
1797
    Find the best index that allows to retrieve first #limit records in the
1763
1798
    given order cheaper then one would retrieve them using full table scan.
1764
1799
 
1765
1800
  IMPLEMENTATION
1783
1818
  uint32_t idx;
1784
1819
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
1785
1820
  order_st *ord;
1786
 
  
 
1821
 
1787
1822
  for (ord= order; ord; ord= ord->next)
1788
1823
    if (!ord->asc)
1789
1824
      return MAX_KEY;
1795
1830
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
1796
1831
    uint32_t n_parts=  table->key_info[idx].key_parts;
1797
1832
    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 
 
1833
 
 
1834
    /*
 
1835
      The below check is sufficient considering we now have either BTREE
 
1836
      indexes (records are returned in order for any index prefix) or HASH
1802
1837
      indexes (records are not returned in order for any index prefix).
1803
1838
    */
1804
1839
    if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
1810
1845
           ((Item_field*)item)->field->eq(keyinfo[partno].field)))
1811
1846
        break;
1812
1847
    }
1813
 
    
 
1848
 
1814
1849
    if (!ord && table->key_info[idx].key_length < match_key_len)
1815
1850
    {
1816
 
      /* 
 
1851
      /*
1817
1852
        Ok, the ordering is compatible and this key is shorter then
1818
1853
        previous match (we want shorter keys as we'll have to read fewer
1819
1854
        index pages for the same number of records)
1825
1860
 
1826
1861
  if (match_key != MAX_KEY)
1827
1862
  {
1828
 
    /* 
1829
 
      Found an index that allows records to be retrieved in the requested 
 
1863
    /*
 
1864
      Found an index that allows records to be retrieved in the requested
1830
1865
      order. Now we'll check if using the index is cheaper then doing a table
1831
1866
      scan.
1832
1867
    */
1881
1916
 
1882
1917
  /* Table read plans are allocated on MEM_ROOT and are never deleted */
1883
1918
  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)))
 
1919
  { return (void*) alloc_root(mem_root, (uint32_t) size); }
 
1920
  static void operator delete(void *, size_t)
1887
1921
    { TRASH(ptr, size); }
1888
 
  static void operator delete(void *ptr __attribute__((unused)),
1889
 
                              MEM_ROOT *mem_root __attribute__((unused)))
 
1922
  static void operator delete(void *, MEM_ROOT *)
1890
1923
    { /* Never called */ }
1891
1924
  virtual ~TABLE_READ_PLAN() {}               /* Remove gcc warning */
1892
1925
 
1909
1942
public:
1910
1943
  SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1911
1944
  uint32_t     key_idx; /* key number in PARAM::key */
1912
 
  uint32_t     mrr_flags; 
 
1945
  uint32_t     mrr_flags;
1913
1946
  uint32_t     mrr_buf_size;
1914
1947
 
1915
1948
  TRP_RANGE(SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1917
1950
  {}
1918
1951
  virtual ~TRP_RANGE() {}                     /* Remove gcc warning */
1919
1952
 
1920
 
  QUICK_SELECT_I *make_quick(PARAM *param,
1921
 
                             bool retrieve_full_rows __attribute__((unused)),
1922
 
                             MEM_ROOT *parent_alloc)
 
1953
  QUICK_SELECT_I *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1923
1954
  {
1924
1955
    QUICK_RANGE_SELECT *quick;
1925
1956
    if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
1928
1959
      quick->records= records;
1929
1960
      quick->read_time= read_cost;
1930
1961
    }
1931
 
    return(quick);
 
1962
    return quick;
1932
1963
  }
1933
1964
};
1934
1965
 
1989
2020
 
1990
2021
 
1991
2022
/*
1992
 
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan. 
 
2023
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
1993
2024
*/
1994
2025
 
1995
2026
class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN
2054
2085
static int fill_used_fields_bitmap(PARAM *param)
2055
2086
{
2056
2087
  Table *table= param->table;
2057
 
  my_bitmap_map *tmp;
2058
2088
  uint32_t pk;
2059
 
  param->tmp_covered_fields.bitmap= 0;
2060
2089
  param->fields_bitmap_size= table->s->column_bitmap_size;
2061
 
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
2062
 
                                  param->fields_bitmap_size)) ||
2063
 
      bitmap_init(&param->needed_fields, tmp, table->s->fields, false))
2064
 
    return 1;
2065
2090
 
2066
 
  bitmap_copy(&param->needed_fields, table->read_set);
2067
 
  bitmap_union(&param->needed_fields, table->write_set);
 
2091
  param->needed_fields = *(table->read_set);
 
2092
  param->needed_fields |= *(table->write_set);
2068
2093
 
2069
2094
  pk= param->table->s->primary_key;
2070
2095
  if (pk != MAX_KEY && param->table->file->primary_key_is_clustered())
2074
2099
    KEY_PART_INFO *key_part_end= key_part +
2075
2100
                                 param->table->key_info[pk].key_parts;
2076
2101
    for (;key_part != key_part_end; ++key_part)
2077
 
      bitmap_clear_bit(&param->needed_fields, key_part->fieldnr-1);
 
2102
      param->needed_fields.reset(key_part->fieldnr-1);
2078
2103
  }
2079
2104
  return 0;
2080
2105
}
2085
2110
 
2086
2111
  SYNOPSIS
2087
2112
    SQL_SELECT::test_quick_select()
2088
 
      thd               Current thread
 
2113
      session               Current thread
2089
2114
      keys_to_use       Keys to use for range retrieval
2090
2115
      prev_tables       Tables assumed to be already read when the scan is
2091
2116
                        performed (but not read at the moment of this call)
2105
2130
 
2106
2131
  IMPLEMENTATION
2107
2132
    quick_condition_rows value is obtained as follows:
2108
 
      
 
2133
 
2109
2134
      It is a minimum of E(#output rows) for all considered table access
2110
2135
      methods (range and index_merge accesses over various indexes).
2111
 
    
 
2136
 
2112
2137
    The obtained value is not a true E(#rows that satisfy table condition)
2113
2138
    but rather a pessimistic estimate. To obtain a true E(#...) one would
2114
2139
    need to combine estimates of various access methods, taking into account
2115
2140
    correlations between sets of rows they will return.
2116
 
    
 
2141
 
2117
2142
    For example, if values of tbl.key1 and tbl.key2 are independent (a right
2118
2143
    assumption if we have no information about their correlation) then the
2119
2144
    correct estimate will be:
2120
 
    
2121
 
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) = 
 
2145
 
 
2146
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
2122
2147
      = E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)
2123
2148
 
2124
 
    which is smaller than 
2125
 
      
 
2149
    which is smaller than
 
2150
 
2126
2151
       MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))
2127
2152
 
2128
2153
    which is currently produced.
2129
2154
 
2130
2155
  TODO
2131
2156
   * 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 
 
2157
     estimate to true E(#rows that satisfy table condition).
 
2158
     (we can re-use some of E(#rows) calcuation code from index_merge/intersection
2134
2159
      for this)
2135
 
   
 
2160
 
2136
2161
   * Check if this function really needs to modify keys_to_use, and change the
2137
2162
     code to pass it by reference if it doesn't.
2138
2163
 
2146
2171
    1 if found usable ranges and quick select has been successfully created.
2147
2172
*/
2148
2173
 
2149
 
int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
 
2174
int SQL_SELECT::test_quick_select(Session *session, key_map keys_to_use,
2150
2175
                                  table_map prev_tables,
2151
 
                                  ha_rows limit, bool force_quick_range, 
 
2176
                                  ha_rows limit, bool force_quick_range,
2152
2177
                                  bool ordered_output)
2153
2178
{
2154
2179
  uint32_t idx;
2158
2183
  needed_reg.clear_all();
2159
2184
  quick_keys.clear_all();
2160
2185
  if (keys_to_use.is_clear_all())
2161
 
    return(0);
 
2186
    return 0;
2162
2187
  records= head->file->stats.records;
2163
2188
  if (!records)
2164
2189
    records++;                                  /* purecov: inspected */
2169
2194
  if (limit < records)
2170
2195
    read_time= (double) records + scan_time + 1; // Force to use index
2171
2196
  else if (read_time <= 2.0 && !force_quick_range)
2172
 
    return(0);                          /* No need for quick select */
 
2197
    return 0;                           /* No need for quick select */
2173
2198
 
2174
2199
  keys_to_use.intersect(head->keys_in_use_for_query);
2175
2200
  if (!keys_to_use.is_clear_all())
2180
2205
    KEY *key_info;
2181
2206
    PARAM param;
2182
2207
 
2183
 
    if (check_stack_overrun(thd, 2*STACK_MIN_SIZE, NULL))
2184
 
      return(0);                           // Fatal error flag is set
 
2208
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
 
2209
      return 0;                           // Fatal error flag is set
2185
2210
 
2186
2211
    /* set up parameter that is passed to all functions */
2187
 
    param.thd= thd;
 
2212
    param.session= session;
2188
2213
    param.baseflag= head->file->ha_table_flags();
2189
2214
    param.prev_tables=prev_tables | const_tables;
2190
2215
    param.read_tables=read_tables;
2192
2217
    param.table=head;
2193
2218
    param.keys=0;
2194
2219
    param.mem_root= &alloc;
2195
 
    param.old_root= thd->mem_root;
 
2220
    param.old_root= session->mem_root;
2196
2221
    param.needed_reg= &needed_reg;
2197
2222
    param.imerge_cost_buff_size= 0;
2198
2223
    param.using_real_indexes= true;
2199
2224
    param.remove_jump_scans= true;
2200
2225
    param.force_default_mrr= ordered_output;
2201
2226
 
2202
 
    thd->no_errors=1;                           // Don't warn about NULL
2203
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
2227
    session->no_errors=1;                               // Don't warn about NULL
 
2228
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
2204
2229
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
2205
2230
                                                  sizeof(KEY_PART)*
2206
2231
                                                  head->s->key_parts)) ||
2207
2232
        fill_used_fields_bitmap(&param))
2208
2233
    {
2209
 
      thd->no_errors=0;
 
2234
      session->no_errors=0;
2210
2235
      free_root(&alloc,MYF(0));                 // Return memory & allocator
2211
 
      return(0);                                // Can't use range
 
2236
      return 0;                         // Can't use range
2212
2237
    }
2213
2238
    key_parts= param.key_parts;
2214
 
    thd->mem_root= &alloc;
 
2239
    session->mem_root= &alloc;
2215
2240
 
2216
2241
    /*
2217
2242
      Make an array with description of all key parts of all table keys.
2248
2273
    if (!head->covering_keys.is_clear_all())
2249
2274
    {
2250
2275
      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, 
 
2276
      double key_read_time=
 
2277
        param.table->file->index_only_read_time(key_for_use,
2253
2278
                                                rows2double(records)) +
2254
2279
        (double) records / TIME_FOR_COMPARE;
2255
2280
      if (key_read_time < read_time)
2320
2345
          objects are not allowed so don't use ROR-intersection for
2321
2346
          table deletes.
2322
2347
        */
2323
 
        if ((thd->lex->sql_command != SQLCOM_DELETE))
 
2348
        if ((session->lex->sql_command != SQLCOM_DELETE))
2324
2349
        {
2325
2350
          /*
2326
2351
            Get best non-covering ROR-intersection plan and prepare data for
2352
2377
        {
2353
2378
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
2354
2379
          if (new_conj_trp)
2355
 
            set_if_smaller(param.table->quick_condition_rows, 
 
2380
            set_if_smaller(param.table->quick_condition_rows,
2356
2381
                           new_conj_trp->records);
2357
2382
          if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
2358
2383
                                 best_conj_trp->read_cost))
2363
2388
      }
2364
2389
    }
2365
2390
 
2366
 
    thd->mem_root= param.old_root;
 
2391
    session->mem_root= param.old_root;
2367
2392
 
2368
2393
    /* If we got a read plan, create a quick select from it. */
2369
2394
    if (best_trp)
2378
2403
 
2379
2404
  free_mem:
2380
2405
    free_root(&alloc,MYF(0));                   // Return memory & allocator
2381
 
    thd->mem_root= param.old_root;
2382
 
    thd->no_errors=0;
 
2406
    session->mem_root= param.old_root;
 
2407
    session->no_errors=0;
2383
2408
  }
2384
2409
 
2385
2410
  /*
2481
2506
  if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
2482
2507
                                             sizeof(TRP_RANGE*)*
2483
2508
                                             n_child_scans)))
2484
 
    return(NULL);
 
2509
    return NULL;
2485
2510
  /*
2486
2511
    Collect best 'range' scan for each of disjuncts, and, while doing so,
2487
2512
    analyze possibility of ROR scans. Also calculate some values needed by
2526
2551
      Bail out if it is obvious that both index_merge and ROR-union will be
2527
2552
      more expensive
2528
2553
    */
2529
 
    return(NULL);
 
2554
    return NULL;
2530
2555
  }
2531
2556
  if (all_scans_rors)
2532
2557
  {
2545
2570
  /* Calculate cost(rowid_to_row_scan) */
2546
2571
  {
2547
2572
    COST_VECT sweep_cost;
2548
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2573
    JOIN *join= param->session->lex->select_lex.join;
2549
2574
    bool is_interrupted= test(join && join->tables == 1);
2550
2575
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
2551
2576
                        &sweep_cost);
2558
2583
  unique_calc_buff_size=
2559
2584
    Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
2560
2585
                                    param->table->file->ref_length,
2561
 
                                    param->thd->variables.sortbuff_size);
 
2586
                                    param->session->variables.sortbuff_size);
2562
2587
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
2563
2588
  {
2564
2589
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
2565
2590
                                                     unique_calc_buff_size)))
2566
 
      return(NULL);
 
2591
      return NULL;
2567
2592
    param->imerge_cost_buff_size= unique_calc_buff_size;
2568
2593
  }
2569
2594
 
2570
2595
  imerge_cost +=
2571
 
    Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records,
 
2596
    Unique::get_use_cost(param->imerge_cost_buff, (uint32_t)non_cpk_scan_records,
2572
2597
                         param->table->file->ref_length,
2573
 
                         param->thd->variables.sortbuff_size);
 
2598
                         param->session->variables.sortbuff_size);
2574
2599
  if (imerge_cost < read_time)
2575
2600
  {
2576
2601
    if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE))
2586
2611
  }
2587
2612
 
2588
2613
build_ror_index_merge:
2589
 
  if (!all_scans_ror_able || param->thd->lex->sql_command == SQLCOM_DELETE)
 
2614
  if (!all_scans_ror_able || param->session->lex->sql_command == SQLCOM_DELETE)
2590
2615
    return(imerge_trp);
2591
2616
 
2592
2617
  /* Ok, it is possible to build a ROR-union, try it. */
2661
2686
  double roru_total_cost;
2662
2687
  {
2663
2688
    COST_VECT sweep_cost;
2664
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2689
    JOIN *join= param->session->lex->select_lex.join;
2665
2690
    bool is_interrupted= test(join && join->tables == 1);
2666
2691
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
2667
2692
                        &sweep_cost);
2697
2722
  SEL_ARG   *sel_arg;
2698
2723
 
2699
2724
  /* Fields used in the query and covered by this ROR scan. */
2700
 
  MY_BITMAP covered_fields;
 
2725
  bitset<MAX_FIELDS> covered_fields;
2701
2726
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
2702
2727
  int       key_rec_length; /* length of key record (including rowid) */
2703
2728
 
2735
2760
 
2736
2761
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
2737
2762
                                             sizeof(ROR_SCAN_INFO))))
2738
 
    return(NULL);
 
2763
    return NULL;
2739
2764
 
2740
2765
  ror_scan->idx= idx;
2741
2766
  ror_scan->keynr= keynr= param->real_keynr[idx];
2746
2771
 
2747
2772
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
2748
2773
                                                param->fields_bitmap_size)))
2749
 
    return(NULL);
 
2774
    return NULL;
2750
2775
 
2751
 
  if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,
2752
 
                  param->table->s->fields, false))
2753
 
    return(NULL);
2754
 
  bitmap_clear_all(&ror_scan->covered_fields);
 
2776
  ror_scan->covered_fields.reset();
2755
2777
 
2756
2778
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2757
2779
  KEY_PART_INFO *key_part_end= key_part +
2758
2780
                               param->table->key_info[keynr].key_parts;
2759
2781
  for (;key_part != key_part_end; ++key_part)
2760
2782
  {
2761
 
    if (bitmap_is_set(&param->needed_fields, key_part->fieldnr-1))
2762
 
      bitmap_set_bit(&ror_scan->covered_fields, key_part->fieldnr-1);
 
2783
    if (param->needed_fields.test(key_part->fieldnr-1))
 
2784
      ror_scan->covered_fields.set(key_part->fieldnr-1);
2763
2785
  }
2764
2786
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
2765
2787
  ror_scan->index_read_cost=
2827
2849
typedef struct
2828
2850
{
2829
2851
  const PARAM *param;
2830
 
  MY_BITMAP covered_fields; /* union of fields covered by all scans */
 
2852
  bitset<MAX_FIELDS> covered_fields; /* union of fields covered by all scans */
2831
2853
  /*
2832
2854
    Fraction of table records that satisfies conditions of all scans.
2833
2855
    This is the number of full records that will be retrieved if a
2859
2881
ROR_INTERSECT_INFO* ror_intersect_init(const PARAM *param)
2860
2882
{
2861
2883
  ROR_INTERSECT_INFO *info;
2862
 
  my_bitmap_map* buf;
2863
2884
  if (!(info= (ROR_INTERSECT_INFO*)alloc_root(param->mem_root,
2864
2885
                                              sizeof(ROR_INTERSECT_INFO))))
2865
2886
    return NULL;
2866
2887
  info->param= param;
2867
 
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
2868
 
                                         param->fields_bitmap_size)))
2869
 
    return NULL;
2870
 
  if (bitmap_init(&info->covered_fields, buf, param->table->s->fields,
2871
 
                  false))
2872
 
    return NULL;
2873
2888
  info->is_covering= false;
2874
2889
  info->index_scan_costs= 0.0;
2875
2890
  info->index_records= 0;
2876
2891
  info->out_rows= (double) param->table->file->stats.records;
2877
 
  bitmap_clear_all(&info->covered_fields);
 
2892
  info->covered_fields.reset();
2878
2893
  return info;
2879
2894
}
2880
2895
 
2881
2896
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
2882
2897
{
2883
2898
  dst->param= src->param;
2884
 
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap, 
2885
 
         no_bytes_in_map(&src->covered_fields));
 
2899
  dst->covered_fields= src->covered_fields;
2886
2900
  dst->out_rows= src->out_rows;
2887
2901
  dst->is_covering= src->is_covering;
2888
2902
  dst->index_records= src->index_records;
2896
2910
 
2897
2911
  SYNOPSIS
2898
2912
    ror_scan_selectivity()
2899
 
      info  ROR-interection 
 
2913
      info  ROR-interection
2900
2914
      scan  ROR scan
2901
 
      
 
2915
 
2902
2916
  NOTES
2903
2917
    Suppose we have a condition on several keys
2904
2918
    cond=k_11=c_11 AND k_12=c_12 AND ...  // parts of first key
2981
2995
    Selectivity of given ROR scan.
2982
2996
*/
2983
2997
 
2984
 
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info, 
 
2998
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
2985
2999
                                   const ROR_SCAN_INFO *scan)
2986
3000
{
2987
3001
  double selectivity_mult= 1.0;
2991
3005
  SEL_ARG *sel_arg, *tuple_arg= NULL;
2992
3006
  key_part_map keypart_map= 0;
2993
3007
  bool cur_covered;
2994
 
  bool prev_covered= test(bitmap_is_set(&info->covered_fields,
2995
 
                                        key_part->fieldnr-1));
 
3008
  bool prev_covered= test(info->covered_fields.test(key_part->fieldnr-1));
2996
3009
  key_range min_range;
2997
3010
  key_range max_range;
2998
3011
  min_range.key= key_val;
3004
3017
  for (sel_arg= scan->sel_arg; sel_arg;
3005
3018
       sel_arg= sel_arg->next_key_part)
3006
3019
  {
3007
 
    cur_covered= test(bitmap_is_set(&info->covered_fields,
3008
 
                                    key_part[sel_arg->part].fieldnr-1));
 
3020
    cur_covered= test(info->covered_fields.test(key_part[sel_arg->part].fieldnr-1));
3009
3021
    if (cur_covered != prev_covered)
3010
3022
    {
3011
3023
      /* create (part1val, ..., part{n-1}val) tuple. */
3083
3095
 
3084
3096
    E(rows_to_retrieve) = #rows_in_table * ror_scan_selectivity(null, scan1) *
3085
3097
                           ror_scan_selectivity({scan1}, scan2) * ... *
3086
 
                           ror_scan_selectivity({scan1,...}, scanN). 
 
3098
                           ror_scan_selectivity({scan1,...}, scanN).
3087
3099
  RETURN
3088
3100
    true   ROR scan added to ROR-intersection, cost updated.
3089
3101
    false  It doesn't make sense to add this ROR scan to this ROR-intersection.
3098
3110
  if (selectivity_mult == 1.0)
3099
3111
  {
3100
3112
    /* Don't add this scan if it doesn't improve selectivity. */
3101
 
    return(false);
 
3113
    return false;
3102
3114
  }
3103
 
  
 
3115
 
3104
3116
  info->out_rows *= selectivity_mult;
3105
 
  
 
3117
 
3106
3118
  if (is_cpk_scan)
3107
3119
  {
3108
3120
    /*
3109
 
      CPK scan is used to filter out rows. We apply filtering for 
 
3121
      CPK scan is used to filter out rows. We apply filtering for
3110
3122
      each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
3111
3123
      per check this gives us:
3112
3124
    */
3113
 
    info->index_scan_costs += rows2double(info->index_records) / 
 
3125
    info->index_scan_costs += rows2double(info->index_records) /
3114
3126
                              TIME_FOR_COMPARE_ROWID;
3115
3127
  }
3116
3128
  else
3117
3129
  {
3118
3130
    info->index_records += info->param->table->quick_rows[ror_scan->keynr];
3119
3131
    info->index_scan_costs += ror_scan->index_read_cost;
3120
 
    bitmap_union(&info->covered_fields, &ror_scan->covered_fields);
3121
 
    if (!info->is_covering && bitmap_is_subset(&info->param->needed_fields,
3122
 
                                               &info->covered_fields))
 
3132
    info->covered_fields |= ror_scan->covered_fields;
 
3133
    if (! info->is_covering &&
 
3134
        ((info->covered_fields & info->param->needed_fields) == info->param->needed_fields))
3123
3135
    {
3124
3136
      info->is_covering= true;
3125
3137
    }
3129
3141
  if (!info->is_covering)
3130
3142
  {
3131
3143
    COST_VECT sweep_cost;
3132
 
    JOIN *join= info->param->thd->lex->select_lex.join;
 
3144
    JOIN *join= info->param->session->lex->select_lex.join;
3133
3145
    bool is_interrupted= test(join && join->tables == 1);
3134
3146
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
3135
3147
                        is_interrupted, &sweep_cost);
3136
3148
    info->total_cost += sweep_cost.total_cost();
3137
3149
  }
3138
 
  return(true);
 
3150
  return true;
3139
3151
}
3140
3152
 
3141
3153
 
3155
3167
 
3156
3168
  NOTES
3157
3169
    get_key_scans_params must be called before this function can be called.
3158
 
    
 
3170
 
3159
3171
    When this function is called by ROR-union construction algorithm it
3160
3172
    assumes it is building an uncovered ROR-intersection (and thus # of full
3161
3173
    records to be retrieved is wrong here). This is a hack.
3177
3189
        firstR= R - first(R);
3178
3190
        if (!selectivity(S + firstR < selectivity(S)))
3179
3191
          continue;
3180
 
          
 
3192
 
3181
3193
        S= S + first(R);
3182
3194
        if (cost(S) < min_cost)
3183
3195
        {
3212
3224
  double min_cost= DBL_MAX;
3213
3225
 
3214
3226
  if ((tree->n_ror_scans < 2) || !param->table->file->stats.records)
3215
 
    return(NULL);
 
3227
    return NULL;
3216
3228
 
3217
3229
  /*
3218
 
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of 
 
3230
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
3219
3231
    them. Also find and save clustered PK scan if there is one.
3220
3232
  */
3221
3233
  ROR_SCAN_INFO **cur_ror_scan;
3271
3283
 
3272
3284
  /* Create and incrementally update ROR intersection. */
3273
3285
  ROR_INTERSECT_INFO *intersect, *intersect_best;
3274
 
  if (!(intersect= ror_intersect_init(param)) || 
 
3286
  if (!(intersect= ror_intersect_init(param)) ||
3275
3287
      !(intersect_best= ror_intersect_init(param)))
3276
3288
    return NULL;
3277
3289
 
3287
3299
      cur_ror_scan++;
3288
3300
      continue;
3289
3301
    }
3290
 
    
 
3302
 
3291
3303
    *(intersect_scans_end++)= *(cur_ror_scan++);
3292
3304
 
3293
3305
    if (intersect->total_cost < min_cost)
3301
3313
 
3302
3314
  if (intersect_scans_best == intersect_scans)
3303
3315
  {
3304
 
    return(NULL);
 
3316
    return NULL;
3305
3317
  }
3306
 
    
 
3318
 
3307
3319
  print_ror_scans_arr(param->table,
3308
3320
                                          "best ROR-intersection",
3309
3321
                                          intersect_scans,
3315
3327
 
3316
3328
  /*
3317
3329
    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 
 
3330
    Check if we should add a CPK scan. If the obtained ROR-intersection is
3319
3331
    covering, it doesn't make sense to add CPK scan.
3320
3332
  */
3321
3333
  if (cpk_scan && !intersect->is_covering)
3322
3334
  {
3323
 
    if (ror_intersect_add(intersect, cpk_scan, true) && 
 
3335
    if (ror_intersect_add(intersect, cpk_scan, true) &&
3324
3336
        (intersect->total_cost < min_cost))
3325
3337
    {
3326
3338
      cpk_scan_used= true;
3337
3349
    if (!(trp->first_scan=
3338
3350
           (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3339
3351
                                       sizeof(ROR_SCAN_INFO*)*best_num)))
3340
 
      return(NULL);
 
3352
      return NULL;
3341
3353
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
3342
3354
    trp->last_scan=  trp->first_scan + best_num;
3343
3355
    trp->is_covering= intersect_best->is_covering;
3354
3366
  return(trp);
3355
3367
}
3356
3368
 
3357
 
 
3358
3369
/*
3359
3370
  Get best covering ROR-intersection.
3360
3371
  SYNOPSIS
3408
3419
  /*I=set of all covering indexes */
3409
3420
  ror_scan_mark= tree->ror_scans;
3410
3421
 
3411
 
  MY_BITMAP *covered_fields= &param->tmp_covered_fields;
3412
 
  if (!covered_fields->bitmap) 
3413
 
    covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3414
 
                                               param->fields_bitmap_size);
3415
 
  if (!covered_fields->bitmap ||
3416
 
      bitmap_init(covered_fields, covered_fields->bitmap,
3417
 
                  param->table->s->fields, false))
3418
 
    return(0);
3419
 
  bitmap_clear_all(covered_fields);
 
3422
  bitset<MAX_FIELDS> *covered_fields= &param->tmp_covered_fields;
 
3423
  covered_fields->reset();
3420
3424
 
3421
3425
  double total_cost= 0.0f;
3422
3426
  ha_rows records=0;
3435
3439
    */
3436
3440
    for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
3437
3441
    {
3438
 
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
3439
 
      (*scan)->used_fields_covered=
3440
 
        bitmap_bits_set(&(*scan)->covered_fields);
3441
 
      (*scan)->first_uncovered_field=
3442
 
        bitmap_get_first(&(*scan)->covered_fields);
 
3442
      /* subtract a bitset */
 
3443
      (*scan)->covered_fields &= covered_fields->flip();
 
3444
      covered_fields->flip();
 
3445
      (*scan)->used_fields_covered= (*scan)->covered_fields.count();
 
3446
      (*scan)->first_uncovered_field= getFirstBitPos((*scan)->covered_fields);
3443
3447
    }
3444
3448
 
3445
3449
    my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
3453
3457
    total_cost += (*ror_scan_mark)->index_read_cost;
3454
3458
    records += (*ror_scan_mark)->records;
3455
3459
    if (total_cost > read_time)
3456
 
      return(NULL);
 
3460
      return NULL;
3457
3461
    /* F=F-covered by first(I) */
3458
 
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3459
 
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
 
3462
    *covered_fields|= (*ror_scan_mark)->covered_fields;
 
3463
    /*
 
3464
     * Check whether the param->needed_fields bitset is a subset of
 
3465
     * the covered_fields bitset. If the param->needed_fields bitset
 
3466
     * is a subset of covered_fields, then set all_covered to 
 
3467
     * true; otherwise, set it to false.
 
3468
     */
 
3469
    all_covered= ((*covered_fields & param->needed_fields) == param->needed_fields);
3460
3470
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3461
 
  
 
3471
 
3462
3472
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
3463
 
    return(NULL);
 
3473
    return NULL;
3464
3474
 
3465
3475
  /*
3466
3476
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
3476
3486
                (TIME_FOR_COMPARE_ROWID * M_LN2);
3477
3487
 
3478
3488
  if (total_cost > read_time)
3479
 
    return(NULL);
 
3489
    return NULL;
3480
3490
 
3481
3491
  TRP_ROR_INTERSECT *trp;
3482
3492
  if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
3485
3495
  if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3486
3496
                                                     sizeof(ROR_SCAN_INFO*)*
3487
3497
                                                     best_num)))
3488
 
    return(NULL);
 
3498
    return NULL;
3489
3499
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
3490
3500
  trp->last_scan=  trp->first_scan + best_num;
3491
3501
  trp->is_covering= true;
3492
3502
  trp->read_cost= total_cost;
3493
3503
  trp->records= records;
3494
3504
  trp->cpk_scan= NULL;
3495
 
  set_if_smaller(param->table->quick_condition_rows, records); 
 
3505
  set_if_smaller(param->table->quick_condition_rows, records);
3496
3506
 
3497
3507
  return(trp);
3498
3508
}
3509
3519
                               (except for clustered PK indexes)
3510
3520
      update_tbl_stats         true <=> update table->quick_* with information
3511
3521
                               about range scans we've evaluated.
3512
 
      read_time                Maximum cost. i.e. don't create read plans with 
 
3522
      read_time                Maximum cost. i.e. don't create read plans with
3513
3523
                               cost > read_time.
3514
3524
 
3515
3525
  DESCRIPTION
3516
 
    Find the best "range" table read plan for given SEL_TREE. 
3517
 
    The side effects are 
 
3526
    Find the best "range" table read plan for given SEL_TREE.
 
3527
    The side effects are
3518
3528
     - tree->ror_scans is updated to indicate which scans are ROR scans.
3519
3529
     - if update_tbl_stats=true then table->quick_* is updated with info
3520
3530
       about every possible range scan.
3525
3535
*/
3526
3536
 
3527
3537
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
3528
 
                                       bool index_read_must_be_used, 
 
3538
                                       bool index_read_must_be_used,
3529
3539
                                       bool update_tbl_stats,
3530
3540
                                       double read_time)
3531
3541
{
3555
3565
          (*key)->maybe_flag)
3556
3566
        param->needed_reg->set_bit(keynr);
3557
3567
 
3558
 
      bool read_index_only= index_read_must_be_used || 
 
3568
      bool read_index_only= index_read_must_be_used ||
3559
3569
                            param->table->covering_keys.is_set(keynr);
3560
3570
 
3561
3571
      found_records= check_quick_select(param, idx, read_index_only, *key,
3596
3606
}
3597
3607
 
3598
3608
 
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)))
 
3609
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
3602
3610
{
3603
3611
  QUICK_INDEX_MERGE_SELECT *quick_imerge;
3604
3612
  QUICK_RANGE_SELECT *quick;
3605
3613
  /* index_merge always retrieves full rows, ignore retrieve_full_rows */
3606
 
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->thd, param->table)))
 
3614
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->session, param->table)))
3607
3615
    return NULL;
3608
3616
 
3609
3617
  quick_imerge->records= records;
3632
3640
  MEM_ROOT *alloc;
3633
3641
 
3634
3642
  if ((quick_intrsect=
3635
 
         new QUICK_ROR_INTERSECT_SELECT(param->thd, param->table,
 
3643
         new QUICK_ROR_INTERSECT_SELECT(param->session, param->table,
3636
3644
                                        (retrieve_full_rows? (!is_covering) :
3637
3645
                                         false),
3638
3646
                                        parent_alloc)))
3650
3658
          quick_intrsect->push_quick_back(quick))
3651
3659
      {
3652
3660
        delete quick_intrsect;
3653
 
        return(NULL);
 
3661
        return NULL;
3654
3662
      }
3655
3663
    }
3656
3664
    if (cpk_scan)
3661
3669
                                    0, alloc)))
3662
3670
      {
3663
3671
        delete quick_intrsect;
3664
 
        return(NULL);
 
3672
        return NULL;
3665
3673
      }
3666
 
      quick->file= NULL; 
 
3674
      quick->file= NULL;
3667
3675
      quick_intrsect->cpk_quick= quick;
3668
3676
    }
3669
3677
    quick_intrsect->records= records;
3673
3681
}
3674
3682
 
3675
3683
 
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)))
 
3684
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
3679
3685
{
3680
3686
  QUICK_ROR_UNION_SELECT *quick_roru;
3681
3687
  TABLE_READ_PLAN **scan;
3684
3690
    It is impossible to construct a ROR-union that will not retrieve full
3685
3691
    rows, ignore retrieve_full_rows parameter.
3686
3692
  */
3687
 
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->thd, param->table)))
 
3693
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->session, param->table)))
3688
3694
  {
3689
3695
    for (scan= first_ror; scan != last_ror; scan++)
3690
3696
    {
3691
3697
      if (!(quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||
3692
3698
          quick_roru->push_quick_back(quick))
3693
 
        return(NULL);
 
3699
        return NULL;
3694
3700
    }
3695
3701
    quick_roru->records= records;
3696
3702
    quick_roru->read_time= read_cost;
3701
3707
 
3702
3708
/*
3703
3709
  Build a SEL_TREE for <> or NOT BETWEEN predicate
3704
 
 
 
3710
 
3705
3711
  SYNOPSIS
3706
3712
    get_ne_mm_tree()
3707
3713
      param       PARAM from SQL_SELECT::test_quick_select
3711
3717
      gt_value    constant that field should be greaterr
3712
3718
      cmp_type    compare type for the field
3713
3719
 
3714
 
  RETURN 
 
3720
  RETURN
3715
3721
    #  Pointer to tree built tree
3716
3722
    0  on error
3717
3723
*/
3718
3724
 
3719
 
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3725
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3720
3726
                                Field *field,
3721
3727
                                Item *lt_value, Item *gt_value,
3722
3728
                                Item_result cmp_type)
3732
3738
  }
3733
3739
  return tree;
3734
3740
}
3735
 
   
 
3741
 
3736
3742
 
3737
3743
/*
3738
3744
  Build a SEL_TREE for a simple predicate
3739
 
 
 
3745
 
3740
3746
  SYNOPSIS
3741
3747
    get_func_mm_tree()
3742
3748
      param       PARAM from SQL_SELECT::test_quick_select
3745
3751
      value       constant in the predicate
3746
3752
      cmp_type    compare type for the field
3747
3753
      inv         true <> NOT cond_func is considered
3748
 
                  (makes sense only when cond_func is BETWEEN or IN) 
 
3754
                  (makes sense only when cond_func is BETWEEN or IN)
3749
3755
 
3750
 
  RETURN 
 
3756
  RETURN
3751
3757
    Pointer to the tree built tree
3752
3758
*/
3753
3759
 
3754
 
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3760
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3755
3761
                                  Field *field, Item *value,
3756
3762
                                  Item_result cmp_type, bool inv)
3757
3763
{
3805
3811
      so we check it here to avoid unnecessary work.
3806
3812
    */
3807
3813
    if (!func->arg_types_compatible)
3808
 
      break;     
 
3814
      break;
3809
3815
 
3810
3816
    if (inv)
3811
3817
    {
3813
3819
      {
3814
3820
        /*
3815
3821
          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 
 
3822
          where c{i} are constants. Our goal is to produce a SEL_TREE that
3817
3823
          represents intervals:
3818
 
          
 
3824
 
3819
3825
          ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ...    (*)
3820
 
          
 
3826
 
3821
3827
          where $MIN is either "-inf" or NULL.
3822
 
          
 
3828
 
3823
3829
          The most straightforward way to produce it is to convert NOT IN
3824
3830
          into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
3825
3831
          analyzer to build SEL_TREE from that. The problem is that the
3829
3835
 
3830
3836
          Another problem with big lists like (*) is that a big list is
3831
3837
          unlikely to produce a good "range" access, while considering that
3832
 
          range access will require expensive CPU calculations (and for 
 
3838
          range access will require expensive CPU calculations (and for
3833
3839
          MyISAM even index accesses). In short, big NOT IN lists are rarely
3834
3840
          worth analyzing.
3835
3841
 
3840
3846
        */
3841
3847
#define NOT_IN_IGNORE_THRESHOLD 1000
3842
3848
        MEM_ROOT *tmp_root= param->mem_root;
3843
 
        param->thd->mem_root= param->old_root;
3844
 
        /* 
 
3849
        param->session->mem_root= param->old_root;
 
3850
        /*
3845
3851
          Create one Item_type constant object. We'll need it as
3846
3852
          get_mm_parts only accepts constant values wrapped in Item_Type
3847
3853
          objects.
3848
3854
          We create the Item on param->mem_root which points to
3849
 
          per-statement mem_root (while thd->mem_root is currently pointing
 
3855
          per-statement mem_root (while session->mem_root is currently pointing
3850
3856
          to mem_root local to range optimizer).
3851
3857
        */
3852
3858
        Item *value_item= func->array->create_item();
3853
 
        param->thd->mem_root= tmp_root;
 
3859
        param->session->mem_root= tmp_root;
3854
3860
 
3855
3861
        if (func->array->count > NOT_IN_IGNORE_THRESHOLD || !value_item)
3856
3862
          break;
3857
3863
 
3858
3864
        /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
3859
3865
        uint32_t i=0;
3860
 
        do 
 
3866
        do
3861
3867
        {
3862
3868
          func->array->value_to_item(i, value_item);
3863
3869
          tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
3900
3906
                new_interval->min_flag= NEAR_MIN;
3901
3907
              }
3902
3908
            }
3903
 
            /* 
 
3909
            /*
3904
3910
              The following doesn't try to allocate memory so no need to
3905
3911
              check for NULL.
3906
3912
            */
3907
3913
            tree= tree_or(param, tree, tree2);
3908
3914
          }
3909
3915
        }
3910
 
        
 
3916
 
3911
3917
        if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
3912
3918
        {
3913
 
          /* 
3914
 
            Get the SEL_TREE for the last "c_last < X < +inf" interval 
 
3919
          /*
 
3920
            Get the SEL_TREE for the last "c_last < X < +inf" interval
3915
3921
            (value_item cotains c_last already)
3916
3922
          */
3917
3923
          tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
3930
3936
          for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3931
3937
               arg < end ; arg++)
3932
3938
          {
3933
 
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
 
3939
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
3934
3940
                                                        *arg, *arg, cmp_type));
3935
3941
          }
3936
3942
        }
3937
3943
      }
3938
3944
    }
3939
3945
    else
3940
 
    {    
 
3946
    {
3941
3947
      tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
3942
3948
                         func->arguments()[1], cmp_type);
3943
3949
      if (tree)
3946
3952
        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3947
3953
             arg < end ; arg++)
3948
3954
        {
3949
 
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 
 
3955
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3950
3956
                                                  Item_func::EQ_FUNC,
3951
3957
                                                  *arg, cmp_type));
3952
3958
        }
3954
3960
    }
3955
3961
    break;
3956
3962
  }
3957
 
  default: 
 
3963
  default:
3958
3964
  {
3959
 
    /* 
 
3965
    /*
3960
3966
       Here the function for the following predicates are processed:
3961
3967
       <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL.
3962
3968
       If the predicate is of the form (value op field) it is handled
3976
3982
 
3977
3983
/*
3978
3984
  Build conjunction of all SEL_TREEs for a simple predicate applying equalities
3979
 
 
 
3985
 
3980
3986
  SYNOPSIS
3981
3987
    get_full_func_mm_tree()
3982
3988
      param       PARAM from SQL_SELECT::test_quick_select
3984
3990
      field_item  field in the predicate
3985
3991
      value       constant in the predicate
3986
3992
                  (for BETWEEN it contains the number of the field argument,
3987
 
                   for IN it's always 0) 
 
3993
                   for IN it's always 0)
3988
3994
      inv         true <> NOT cond_func is considered
3989
3995
                  (makes sense only when cond_func is BETWEEN or IN)
3990
3996
 
3993
3999
    c is a constant, the function builds a conjunction of all SEL_TREES that can
3994
4000
    be obtained by the substitution of f for all different fields equal to f.
3995
4001
 
3996
 
  NOTES  
 
4002
  NOTES
3997
4003
    If the WHERE condition contains a predicate (fi op c),
3998
4004
    then not only SELL_TREE for this predicate is built, but
3999
4005
    the trees for the results of substitution of fi for
4000
4006
    each fj belonging to the same multiple equality as fi
4001
4007
    are built as well.
4002
 
    E.g. for WHERE t1.a=t2.a AND t2.a > 10 
 
4008
    E.g. for WHERE t1.a=t2.a AND t2.a > 10
4003
4009
    a SEL_TREE for t2.a > 10 will be built for quick select from t2
4004
 
    and   
 
4010
    and
4005
4011
    a SEL_TREE for t1.a > 10 will be built for quick select from t1.
4006
4012
 
4007
4013
    A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
4010
4016
    Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed
4011
4017
    differently. It is considered as a conjuction of two SARGable
4012
4018
    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) 
 
4019
    is called for each of them separately producing trees for
 
4020
       AND j (f1j <=c ) and AND j (f2j <= c)
4015
4021
    After this these two trees are united in one conjunctive tree.
4016
4022
    It's easy to see that the same tree is obtained for
4017
4023
       AND j,k (f1j <=c AND f2k<=c)
4018
 
    which is equivalent to 
 
4024
    which is equivalent to
4019
4025
       AND j,k (c BETWEEN f1j AND f2k).
4020
4026
    The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i)
4021
4027
    which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the
4022
4028
    function get_full_func_mm_tree is called for (f1i > c) and (f2i < c)
4023
4029
    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 
 
4030
    trees are united in one OR-tree. The expression
4025
4031
      (AND j (f1j > c) OR AND j (f2j < c)
4026
4032
    is equivalent to the expression
4027
 
      AND j,k (f1j > c OR f2k < c) 
4028
 
    which is just a translation of 
 
4033
      AND j,k (f1j > c OR f2k < c)
 
4034
    which is just a translation of
4029
4035
      AND j,k (c NOT BETWEEN f1j AND f2k)
4030
4036
 
4031
4037
    In the cases when one of the items f1, f2 is a constant c1 we do not create
4038
4044
    As to IN predicates only ones of the form (f IN (c1,...,cn)),
4039
4045
    where f1 is a field and c1,...,cn are constant, are considered as
4040
4046
    SARGable. We never try to narrow the index scan using predicates of
4041
 
    the form (c IN (c1,...,f,...,cn)). 
4042
 
      
4043
 
  RETURN 
 
4047
    the form (c IN (c1,...,f,...,cn)).
 
4048
 
 
4049
  RETURN
4044
4050
    Pointer to the tree representing the built conjunction of SEL_TREEs
4045
4051
*/
4046
4052
 
4047
4053
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
4048
4054
                                       Item_func *cond_func,
4049
 
                                       Item_field *field_item, Item *value, 
 
4055
                                       Item_field *field_item, Item *value,
4050
4056
                                       bool inv)
4051
4057
{
4052
4058
  SEL_TREE *tree= 0;
4106
4112
      while ((item=li++))
4107
4113
      {
4108
4114
        SEL_TREE *new_tree=get_mm_tree(param,item);
4109
 
        if (param->thd->is_fatal_error || 
 
4115
        if (param->session->is_fatal_error ||
4110
4116
            param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
4111
 
          return(0);    // out of memory
 
4117
          return 0;     // out of memory
4112
4118
        tree=tree_and(param,tree,new_tree);
4113
4119
        if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4114
4120
          break;
4124
4130
        {
4125
4131
          SEL_TREE *new_tree=get_mm_tree(param,item);
4126
4132
          if (!new_tree)
4127
 
            return(0);  // out of memory
 
4133
            return 0;   // out of memory
4128
4134
          tree=tree_or(param,tree,new_tree);
4129
4135
          if (!tree || tree->type == SEL_TREE::ALWAYS)
4130
4136
            break;
4137
4143
  if (cond->const_item())
4138
4144
  {
4139
4145
    /*
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 
 
4146
      During the cond->val_int() evaluation we can come across a subselect
 
4147
      item which may allocate memory on the session->mem_root and assumes
 
4148
      all the memory allocated has the same life span as the subselect
4143
4149
      item itself. So we have to restore the thread's mem_root here.
4144
4150
    */
4145
4151
    MEM_ROOT *tmp_root= param->mem_root;
4146
 
    param->thd->mem_root= param->old_root;
 
4152
    param->session->mem_root= param->old_root;
4147
4153
    tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
4148
4154
                            new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
4149
 
    param->thd->mem_root= tmp_root;
 
4155
    param->session->mem_root= tmp_root;
4150
4156
    return(tree);
4151
4157
  }
4152
4158
 
4158
4164
    ref_tables= cond->used_tables();
4159
4165
    if ((ref_tables & param->current_table) ||
4160
4166
        (ref_tables & ~(param->prev_tables | param->read_tables)))
4161
 
      return(0);
 
4167
      return 0;
4162
4168
    return(new SEL_TREE(SEL_TREE::MAYBE));
4163
4169
  }
4164
4170
 
4167
4173
      cond_func->functype() == Item_func::IN_FUNC)
4168
4174
    inv= ((Item_func_opt_neg *) cond_func)->negated;
4169
4175
  else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
4170
 
    return(0);                         
 
4176
    return 0;
4171
4177
 
4172
4178
  param->cond= cond;
4173
4179
 
4188
4194
      if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
4189
4195
      {
4190
4196
        field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
4191
 
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func, 
 
4197
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
4192
4198
                                    field_item, (Item*)(intptr_t)i, inv);
4193
4199
        if (inv)
4194
4200
          tree= !tree ? tmp : tree_or(param, tree, tmp);
4195
 
        else 
 
4201
        else
4196
4202
          tree= tree_and(param, tree, tmp);
4197
4203
      }
4198
4204
      else if (inv)
4199
 
      { 
 
4205
      {
4200
4206
        tree= 0;
4201
4207
        break;
4202
4208
      }
4208
4214
  {
4209
4215
    Item_func_in *func=(Item_func_in*) cond_func;
4210
4216
    if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
4211
 
      return(0);
 
4217
      return 0;
4212
4218
    field_item= (Item_field*) (func->key_item()->real_item());
4213
4219
    ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
4214
4220
    break;
4215
4221
  }
4216
4222
  case Item_func::MULT_EQUAL_FUNC:
4217
4223
  {
4218
 
    Item_equal *item_equal= (Item_equal *) cond;    
 
4224
    Item_equal *item_equal= (Item_equal *) cond;
4219
4225
    if (!(value= item_equal->get_const()))
4220
 
      return(0);
 
4226
      return 0;
4221
4227
    Item_equal_iterator it(*item_equal);
4222
4228
    ref_tables= value->used_tables();
4223
4229
    while ((field_item= it++))
4231
4237
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
4232
4238
      }
4233
4239
    }
4234
 
    
 
4240
 
4235
4241
    return(ftree);
4236
4242
  }
4237
4243
  default:
4248
4254
      value= cond_func->arguments()[0];
4249
4255
    }
4250
4256
    else
4251
 
      return(0);
 
4257
      return 0;
4252
4258
    ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
4253
4259
  }
4254
4260
 
4259
4265
static SEL_TREE *
4260
4266
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4261
4267
             Item_func::Functype type,
4262
 
             Item *value,
4263
 
             Item_result cmp_type __attribute__((unused)))
 
4268
             Item *value, Item_result)
4264
4269
{
4265
4270
  if (field->table != param->table)
4266
 
    return(0);
 
4271
    return 0;
4267
4272
 
4268
4273
  KEY_PART *key_part = param->key_parts;
4269
4274
  KEY_PART *end = param->key_parts_end;
4270
4275
  SEL_TREE *tree=0;
4271
4276
  if (value &&
4272
4277
      value->used_tables() & ~(param->prev_tables | param->read_tables))
4273
 
    return(0);
 
4278
    return 0;
4274
4279
  for (; key_part != end ; key_part++)
4275
4280
  {
4276
4281
    if (field->eq(key_part->field))
4277
4282
    {
4278
4283
      SEL_ARG *sel_arg=0;
4279
4284
      if (!tree && !(tree=new SEL_TREE()))
4280
 
        return(0);                              // OOM
 
4285
        return 0;                               // OOM
4281
4286
      if (!value || !(value->used_tables() & ~param->read_tables))
4282
4287
      {
4283
4288
        sel_arg=get_mm_leaf(param,cond_func,
4294
4299
      {
4295
4300
        // This key may be used later
4296
4301
        if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4297
 
          return(0);                    // OOM
 
4302
          return 0;                     // OOM
4298
4303
      }
4299
4304
      sel_arg->part=(unsigned char) key_part->part;
4300
4305
      tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4301
4306
      tree->keys_map.set_bit(key_part->key);
4302
4307
    }
4303
4308
  }
4304
 
  
 
4309
 
4305
4310
  return(tree);
4306
4311
}
4307
4312
 
4310
4315
get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field,
4311
4316
            KEY_PART *key_part, Item_func::Functype type,Item *value)
4312
4317
{
4313
 
  uint32_t maybe_null=(uint) field->real_maybe_null();
 
4318
  uint32_t maybe_null=(uint32_t) field->real_maybe_null();
4314
4319
  bool optimize_range;
4315
4320
  SEL_ARG *tree= 0;
4316
4321
  MEM_ROOT *alloc= param->mem_root;
4317
4322
  unsigned char *str;
4318
 
  ulong orig_sql_mode;
4319
 
  int err;
 
4323
  int err= 0;
4320
4324
 
4321
4325
  /*
4322
4326
    We need to restore the runtime mem_root of the thread in this
4324
4328
    the argument can be any, e.g. a subselect. The subselect
4325
4329
    items, in turn, assume that all the memory allocated during
4326
4330
    the evaluation has the same life span as the item itself.
4327
 
    TODO: opt_range.cc should not reset thd->mem_root at all.
 
4331
    TODO: opt_range.cc should not reset session->mem_root at all.
4328
4332
  */
4329
 
  param->thd->mem_root= param->old_root;
 
4333
  param->session->mem_root= param->old_root;
4330
4334
  if (!value)                                   // IS NULL or IS NOT NULL
4331
4335
  {
4332
4336
    if (field->table->maybe_null)               // Can't use a key on this
4465
4469
      value->result_type() != STRING_RESULT &&
4466
4470
      field->cmp_type() != value->result_type())
4467
4471
    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);
 
4472
 
 
4473
  /*
 
4474
   * Some notes from Jay...
 
4475
   *
 
4476
   * OK, so previously, and in MySQL, what the optimizer does here is
 
4477
   * override the sql_mode variable to ignore out-of-range or bad date-
 
4478
   * time values.  It does this because the optimizer is populating the
 
4479
   * field variable with the incoming value from the comparison field, 
 
4480
   * and the value may exceed the bounds of a proper column type.
 
4481
   *
 
4482
   * For instance, assume the following:
 
4483
   *
 
4484
   * CREATE TABLE t1 (ts TIMESTAMP); 
 
4485
   * INSERT INTO t1 ('2009-03-04 00:00:00');
 
4486
   * CREATE TABLE t2 (dt1 DATETIME, dt2 DATETIME); 
 
4487
   * INSERT INT t2 ('2003-12-31 00:00:00','2999-12-31 00:00:00');
 
4488
   *
 
4489
   * If we issue this query:
 
4490
   *
 
4491
   * SELECT * FROM t1, t2 WHERE t1.ts BETWEEN t2.dt1 AND t2.dt2;
 
4492
   *
 
4493
   * We will come into bounds issues.  Field_timestamp::store() will be
 
4494
   * called with a datetime value of "2999-12-31 00:00:00" and will throw
 
4495
   * an error for out-of-bounds.  MySQL solves this via a hack with sql_mode
 
4496
   * but Drizzle always throws errors on bad data storage in a Field class.
 
4497
   *
 
4498
   * Therefore, to get around the problem of the Field class being used for
 
4499
   * "storage" here without actually storing anything...we must check to see 
 
4500
   * if the value being stored in a Field_timestamp here is out of range.  If
 
4501
   * it is, then we must convert to the highest Timestamp value (or lowest,
 
4502
   * depending on whether the datetime is before or after the epoch.
 
4503
   */
 
4504
  if (field->type() == DRIZZLE_TYPE_TIMESTAMP)
 
4505
  {
 
4506
    /* 
 
4507
     * The left-side of the range comparison is a timestamp field.  Therefore, 
 
4508
     * we must check to see if the value in the right-hand side is outside the
 
4509
     * range of the UNIX epoch, and cut to the epoch bounds if it is.
 
4510
     */
 
4511
    /* Datetime and date columns are Item::FIELD_ITEM ... and have a result type of STRING_RESULT */
 
4512
    if (value->real_item()->type() == Item::FIELD_ITEM
 
4513
        && value->result_type() == STRING_RESULT)
 
4514
    {
 
4515
      char buff[MAX_DATETIME_FULL_WIDTH];
 
4516
      String tmp(buff, sizeof(buff), &my_charset_bin);
 
4517
      String *res= value->val_str(&tmp);
 
4518
 
 
4519
      if (!res)
 
4520
        goto end;
 
4521
      else
 
4522
      {
 
4523
        /* 
 
4524
         * Create a datetime from the string and compare to fixed timestamp
 
4525
         * instances representing the epoch boundaries.
 
4526
         */
 
4527
        drizzled::DateTime value_datetime;
 
4528
 
 
4529
        if (! value_datetime.from_string(res->c_ptr(), (size_t) res->length()))
 
4530
          goto end;
 
4531
 
 
4532
        drizzled::Timestamp max_timestamp;
 
4533
        drizzled::Timestamp min_timestamp;
 
4534
 
 
4535
        (void) max_timestamp.from_time_t((time_t) INT32_MAX);
 
4536
        (void) min_timestamp.from_time_t((time_t) 0);
 
4537
 
 
4538
        /* We rely on Temporal class operator overloads to do our comparisons. */
 
4539
        if (value_datetime < min_timestamp)
 
4540
        {
 
4541
          /* 
 
4542
           * Datetime in right-hand side column is before UNIX epoch, so adjust to
 
4543
           * lower bound.
 
4544
           */
 
4545
          char new_value_buff[MAX_DATETIME_FULL_WIDTH];
 
4546
          size_t new_value_length;
 
4547
          String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
 
4548
 
 
4549
          min_timestamp.to_string(new_value_string.c_ptr(), &new_value_length);
 
4550
          new_value_string.length(new_value_length);
 
4551
          err= value->save_str_value_in_field(field, &new_value_string);
 
4552
        }
 
4553
        else if (value_datetime > max_timestamp)
 
4554
        {
 
4555
          /*
 
4556
           * Datetime in right hand side column is after UNIX epoch, so adjust
 
4557
           * to the higher bound of the epoch.
 
4558
           */
 
4559
          char new_value_buff[MAX_DATETIME_FULL_WIDTH];
 
4560
          size_t new_value_length;
 
4561
          String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
 
4562
 
 
4563
          max_timestamp.to_string(new_value_string.c_ptr(), &new_value_length);
 
4564
          new_value_string.length(new_value_length);
 
4565
          err= value->save_str_value_in_field(field, &new_value_string);
 
4566
        }
 
4567
        else
 
4568
          err= value->save_in_field(field, 1);
 
4569
      }
 
4570
    }
 
4571
    else /* Not a datetime -> timestamp comparison */
 
4572
      err= value->save_in_field(field, 1);
 
4573
  }
 
4574
  else /* Not a timestamp comparison */
 
4575
    err= value->save_in_field(field, 1);
 
4576
 
4475
4577
  if (err > 0)
4476
4578
  {
4477
4579
    if (field->cmp_type() != value->result_type())
4491
4593
          for the cases like int_field > 999999999999999999999999 as well.
4492
4594
        */
4493
4595
        tree= 0;
4494
 
        if (err == 3 && field->type() == DRIZZLE_TYPE_NEWDATE &&
 
4596
        if (err == 3 && field->type() == DRIZZLE_TYPE_DATE &&
4495
4597
            (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC ||
4496
4598
             type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) )
4497
4599
        {
4500
4602
            but a non-zero time part was cut off.
4501
4603
 
4502
4604
            In MySQL's SQL dialect, DATE and DATETIME are compared as datetime
4503
 
            values. Index over a DATE column uses DATE comparison. Changing 
 
4605
            values. Index over a DATE column uses DATE comparison. Changing
4504
4606
            from one comparison to the other is possible:
4505
4607
 
4506
4608
            datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10'
4537
4639
  }
4538
4640
  else if (err < 0)
4539
4641
  {
4540
 
    field->table->in_use->variables.sql_mode= orig_sql_mode;
4541
4642
    /* This happens when we try to insert a NULL field in a not null column */
4542
4643
    tree= &null_element;                        // cmp with NULL is never true
4543
4644
    goto end;
4544
4645
  }
4545
 
  field->table->in_use->variables.sql_mode= orig_sql_mode;
4546
4646
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
4547
4647
  if (!str)
4548
4648
    goto end;
4612
4712
  }
4613
4713
 
4614
4714
end:
4615
 
  param->thd->mem_root= alloc;
 
4715
  param->session->mem_root= alloc;
4616
4716
  return(tree);
4617
4717
}
4618
4718
 
4693
4793
  }
4694
4794
  key_map  result_keys;
4695
4795
  result_keys.clear_all();
4696
 
  
 
4796
 
4697
4797
  /* Join the trees key per key */
4698
4798
  SEL_ARG **key1,**key2,**end;
4699
4799
  for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
4714
4814
      }
4715
4815
      result_keys.set_bit(key1 - tree1->keys);
4716
4816
#ifdef EXTRA_DEBUG
4717
 
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
4817
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4718
4818
          (*key1)->test_use_count(*key1);
4719
4819
#endif
4720
4820
    }
4739
4839
  using index_merge.
4740
4840
*/
4741
4841
 
4742
 
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, 
 
4842
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4743
4843
                           RANGE_OPT_PARAM* param)
4744
4844
{
4745
4845
  key_map common_keys= tree1->keys_map;
4746
4846
  common_keys.intersect(tree2->keys_map);
4747
4847
 
4748
4848
  if (common_keys.is_clear_all())
4749
 
    return(false);
 
4849
    return false;
4750
4850
 
4751
4851
  /* trees have a common key, check if they refer to same key part */
4752
4852
  SEL_ARG **key1,**key2;
4758
4858
      key2= tree2->keys + key_no;
4759
4859
      if ((*key1)->part == (*key2)->part)
4760
4860
      {
4761
 
        return(true);
 
4861
        return true;
4762
4862
      }
4763
4863
    }
4764
4864
  }
4765
 
  return(false);
 
4865
  return false;
4766
4866
}
4767
4867
 
4768
4868
 
4771
4871
  SYNOPSIS
4772
4872
    param  Range analysis parameter
4773
4873
    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
4774
 
 
 
4874
 
4775
4875
  DESCRIPTION
4776
4876
    This function walks through tree->keys[] and removes the SEL_ARG* trees
4777
4877
    that are not "maybe" trees (*) and cannot be used to construct quick range
4783
4883
    tree->part != 0. (e.g. it could represent "keypart2 < const").
4784
4884
 
4785
4885
    WHY THIS FUNCTION IS NEEDED
4786
 
    
 
4886
 
4787
4887
    Normally we allow construction of SEL_TREE objects that have SEL_ARG
4788
4888
    trees that do not allow quick range select construction. For example for
4789
4889
    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4792
4892
                                               from this
4793
4893
    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4794
4894
                                   tree.
4795
 
    
 
4895
 
4796
4896
    There is an exception though: when we construct index_merge SEL_TREE,
4797
4897
    any SEL_ARG* tree that cannot be used to construct quick range select can
4798
4898
    be removed, because current range analysis code doesn't provide any way
4799
4899
    that tree could be later combined with another tree.
4800
4900
    Consider an example: we should not construct
4801
 
    st1 = SEL_TREE { 
4802
 
      merges = SEL_IMERGE { 
4803
 
                            SEL_TREE(t.key1part1 = 1), 
 
4901
    st1 = SEL_TREE {
 
4902
      merges = SEL_IMERGE {
 
4903
                            SEL_TREE(t.key1part1 = 1),
4804
4904
                            SEL_TREE(t.key2part2 = 2)   -- (*)
4805
 
                          } 
 
4905
                          }
4806
4906
                   };
4807
 
    because 
4808
 
     - (*) cannot be used to construct quick range select, 
4809
 
     - There is no execution path that would cause (*) to be converted to 
 
4907
    because
 
4908
     - (*) cannot be used to construct quick range select,
 
4909
     - There is no execution path that would cause (*) to be converted to
4810
4910
       a tree that could be used.
4811
4911
 
4812
4912
    The latter is easy to verify: first, notice that the only way to convert
4813
4913
    (*) into a usable tree is to call tree_and(something, (*)).
4814
4914
 
4815
4915
    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 
 
4916
    SEL_TREE that has the structure like st1 tree has, and conlcude that
4817
4917
    tree_and(something, (*)) will not be called.
4818
4918
 
4819
4919
  RETURN
4845
4945
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4846
4946
{
4847
4947
  if (!tree1 || !tree2)
4848
 
    return(0);
 
4948
    return 0;
4849
4949
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4850
4950
    return(tree2);
4851
4951
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4871
4971
        result=tree1;                           // Added to tree1
4872
4972
        result_keys.set_bit(key1 - tree1->keys);
4873
4973
#ifdef EXTRA_DEBUG
4874
 
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
4974
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4875
4975
          (*key1)->test_use_count(*key1);
4876
4976
#endif
4877
4977
      }
4913
5013
      /* one tree is index merge tree and another is range tree */
4914
5014
      if (tree1->merges.is_empty())
4915
5015
        std::swap(tree1, tree2);
4916
 
      
 
5016
 
4917
5017
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
4918
5018
         return(new SEL_TREE(SEL_TREE::ALWAYS));
4919
5019
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
4923
5023
        result= tree1;
4924
5024
    }
4925
5025
  }
4926
 
  return(result);
 
5026
  return result;
4927
5027
}
4928
5028
 
4929
5029
 
4930
5030
/* And key trees where key1->part < key2 -> part */
4931
5031
 
4932
5032
static SEL_ARG *
4933
 
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, 
 
5033
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4934
5034
             uint32_t clone_flag)
4935
5035
{
4936
5036
  SEL_ARG *next;
5030
5130
    }
5031
5131
    if (key1->type == SEL_ARG::MAYBE_KEY)
5032
5132
    {                                           // Both are maybe key
5033
 
      key1->next_key_part=key_and(param, key1->next_key_part, 
 
5133
      key1->next_key_part=key_and(param, key1->next_key_part,
5034
5134
                                  key2->next_key_part, clone_flag);
5035
5135
      if (key1->next_key_part &&
5036
5136
          key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5534
5634
  }
5535
5635
 
5536
5636
  if (root == &null_element)
5537
 
    return(0);                          // Maybe root later
 
5637
    return 0;                           // Maybe root later
5538
5638
  if (remove_color == BLACK)
5539
5639
    root=rb_delete_fixup(root,nod,fix_par);
 
5640
#ifdef EXTRA_DEBUG
5540
5641
  test_rb_tree(root,root->parent);
 
5642
#endif /* EXTRA_DEBUG */
5541
5643
 
5542
5644
  root->use_count=this->use_count;              // Fix root counters
5543
5645
  root->elements=this->elements-1;
5634
5736
    }
5635
5737
  }
5636
5738
  root->color=BLACK;
 
5739
#ifdef EXTRA_DEBUG
5637
5740
  test_rb_tree(root,root->parent);
 
5741
#endif /* EXTRA_DEBUG */
 
5742
 
5638
5743
  return root;
5639
5744
}
5640
5745
 
5729
5834
    return 0;                                   // Found end of tree
5730
5835
  if (element->parent != parent)
5731
5836
  {
5732
 
    sql_print_error("Wrong tree: Parent doesn't point at parent");
 
5837
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5733
5838
    return -1;
5734
5839
  }
5735
5840
  if (element->color == SEL_ARG::RED &&
5736
5841
      (element->left->color == SEL_ARG::RED ||
5737
5842
       element->right->color == SEL_ARG::RED))
5738
5843
  {
5739
 
    sql_print_error("Wrong tree: Found two red in a row");
 
5844
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5740
5845
    return -1;
5741
5846
  }
5742
5847
  if (element->left == element->right && element->left != &null_element)
5743
5848
  {                                             // Dummy test
5744
 
    sql_print_error("Wrong tree: Found right == left");
 
5849
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5745
5850
    return -1;
5746
5851
  }
5747
5852
  count_l=test_rb_tree(element->left,element);
5750
5855
  {
5751
5856
    if (count_l == count_r)
5752
5857
      return count_l+(element->color == SEL_ARG::BLACK);
5753
 
    sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
 
5858
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5754
5859
            count_l,count_r);
5755
5860
  }
5756
5861
  return -1;                                    // Error, no more warnings
5759
5864
 
5760
5865
/*
5761
5866
  Count how many times SEL_ARG graph "root" refers to its part "key"
5762
 
  
 
5867
 
5763
5868
  SYNOPSIS
5764
5869
    count_key_part_usage()
5765
5870
      root  An RB-Root node in a SEL_ARG graph.
5770
5875
    root->next->n
5771
5876
 
5772
5877
    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 
 
5878
    SEL_ARG::next_key_part) by
 
5879
     - intervals of RB-tree pointed by "root",
 
5880
     - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5776
5881
       intervals of RB-tree pointed by "root",
5777
5882
     - and so on.
5778
 
    
5779
 
    Here is an example (horizontal links represent next_key_part pointers, 
5780
 
    vertical links - next/prev prev pointers):  
5781
 
    
 
5883
 
 
5884
    Here is an example (horizontal links represent next_key_part pointers,
 
5885
    vertical links - next/prev prev pointers):
 
5886
 
5782
5887
         +----+               $
5783
5888
         |root|-----------------+
5784
5889
         +----+               $ |
5797
5902
          ...     +---+       $    |
5798
5903
                  |   |------------+
5799
5904
                  +---+       $
5800
 
  RETURN 
 
5905
  RETURN
5801
5906
    Number of links to "key" from nodes reachable from "root".
5802
5907
*/
5803
5908
 
5837
5942
  uint32_t e_count=0;
5838
5943
  if (this == root && use_count != 1)
5839
5944
  {
5840
 
    sql_print_information("Use_count: Wrong count %lu for root",use_count);
 
5945
    errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5841
5946
    return;
5842
5947
  }
5843
5948
  if (this->type != SEL_ARG::KEY_RANGE)
5850
5955
      ulong count=count_key_part_usage(root,pos->next_key_part);
5851
5956
      if (count > pos->next_key_part->use_count)
5852
5957
      {
5853
 
        sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
 
5958
        errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5854
5959
                              "should be %lu", (long unsigned int)pos,
5855
5960
                              pos->next_key_part->use_count, count);
5856
5961
        return;
5859
5964
    }
5860
5965
  }
5861
5966
  if (e_count != elements)
5862
 
    sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
 
5967
    errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5863
5968
                      e_count, elements, (long unsigned int) this);
5864
5969
}
5865
5970
 
5870
5975
 ****************************************************************************/
5871
5976
 
5872
5977
/* MRR range sequence, SEL_ARG* implementation: stack entry */
5873
 
typedef struct st_range_seq_entry 
 
5978
typedef struct st_range_seq_entry
5874
5979
{
5875
 
  /* 
 
5980
  /*
5876
5981
    Pointers in min and max keys. They point to right-after-end of key
5877
5982
    images. The 0-th entry has these pointing to key tuple start.
5878
5983
  */
5879
5984
  unsigned char *min_key, *max_key;
5880
 
  
5881
 
  /* 
 
5985
 
 
5986
  /*
5882
5987
    Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
5883
5988
    min_key_flag may have NULL_RANGE set.
5884
5989
  */
5885
5990
  uint32_t min_key_flag, max_key_flag;
5886
 
  
 
5991
 
5887
5992
  /* Number of key parts */
5888
5993
  uint32_t min_key_parts, max_key_parts;
5889
5994
  SEL_ARG *key_tree;
5899
6004
  uint32_t real_keyno; /* Number of the index in tables */
5900
6005
  PARAM *param;
5901
6006
  SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
5902
 
  
 
6007
 
5903
6008
  RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
5904
6009
  int i; /* Index of last used element in the above array */
5905
 
  
 
6010
 
5906
6011
  bool at_start; /* true <=> The traversal has just started */
5907
6012
} SEL_ARG_RANGE_SEQ;
5908
6013
 
5913
6018
  SYNOPSIS
5914
6019
    init()
5915
6020
      init_params  SEL_ARG tree traversal context
5916
 
      n_ranges     [ignored] The number of ranges obtained 
 
6021
      n_ranges     [ignored] The number of ranges obtained
5917
6022
      flags        [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
5918
6023
 
5919
6024
  RETURN
5920
6025
    Value of init_param
5921
6026
*/
5922
6027
 
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)))
 
6028
range_seq_t sel_arg_range_seq_init(void *init_param, uint32_t, uint32_t)
5926
6029
{
5927
6030
  SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
5928
6031
  seq->at_start= true;
5943
6046
{
5944
6047
  RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
5945
6048
  RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
5946
 
  
 
6049
 
5947
6050
  cur->key_tree= key_tree;
5948
6051
  cur->min_key= prev->min_key;
5949
6052
  cur->max_key= prev->max_key;
5967
6070
 
5968
6071
/*
5969
6072
  Range sequence interface, SEL_ARG* implementation: get the next interval
5970
 
  
 
6073
 
5971
6074
  SYNOPSIS
5972
6075
    sel_arg_range_seq_next()
5973
6076
      rseq        Value returned from sel_arg_range_seq_init
6002
6105
 
6003
6106
  key_tree= seq->stack[seq->i].key_tree;
6004
6107
  /* Ok, we're at some "full tuple" position in the tree */
6005
 
 
 
6108
 
6006
6109
  /* Step down if we can */
6007
6110
  if (key_tree->next && key_tree->next != &null_element)
6008
6111
  {
6039
6142
    Walk right-up while we can
6040
6143
  */
6041
6144
walk_right_n_up:
6042
 
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element && 
 
6145
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
6043
6146
         key_tree->next_key_part->part == key_tree->part + 1 &&
6044
6147
         key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6045
6148
  {
6054
6157
      {
6055
6158
        seq->param->is_ror_scan= false;
6056
6159
        if (!key_tree->min_flag)
6057
 
          cur->min_key_parts += 
 
6160
          cur->min_key_parts +=
6058
6161
            key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6059
6162
                                                   &cur->min_key,
6060
6163
                                                   &cur->min_key_flag);
6061
6164
        if (!key_tree->max_flag)
6062
 
          cur->max_key_parts += 
 
6165
          cur->max_key_parts +=
6063
6166
            key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6064
6167
                                                   &cur->max_key,
6065
6168
                                                   &cur->max_key_flag);
6066
6169
        break;
6067
6170
      }
6068
6171
    }
6069
 
  
 
6172
 
6070
6173
    /*
6071
6174
      Ok, current atomic interval is in form "t.field=const" and there is
6072
6175
      next_key_part interval. Step right, and walk up from there.
6084
6187
 
6085
6188
  /* Ok got a tuple */
6086
6189
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6087
 
  
 
6190
 
6088
6191
  range->ptr= (char*)(int)(key_tree->part);
6089
6192
  {
6090
6193
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
6091
 
    
 
6194
 
6092
6195
    range->start_key.key=    seq->param->min_key;
6093
6196
    range->start_key.length= cur->min_key - seq->param->min_key;
6094
6197
    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 : 
 
6198
    range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
6096
6199
                                                           HA_READ_KEY_EXACT);
6097
6200
 
6098
6201
    range->end_key.key=    seq->param->max_key;
6099
6202
    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 : 
 
6203
    range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
6101
6204
                                                         HA_READ_AFTER_KEY);
6102
6205
    range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
6103
6206
 
6104
6207
    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 &&
 
6208
        (uint32_t)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts &&
6106
6209
        (seq->param->table->key_info[seq->real_keyno].flags & (HA_NOSAME)) ==
6107
6210
        HA_NOSAME &&
6108
6211
        range->start_key.length == range->end_key.length &&
6109
6212
        !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
6110
6213
      range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
6111
 
      
 
6214
 
6112
6215
    if (seq->param->is_ror_scan)
6113
6216
    {
6114
6217
      /*
6128
6231
    }
6129
6232
  }
6130
6233
  seq->param->range_count++;
6131
 
  seq->param->max_key_part=cmax(seq->param->max_key_part,(uint)key_tree->part);
 
6234
  seq->param->max_key_part=cmax(seq->param->max_key_part,(uint32_t)key_tree->part);
6132
6235
  return 0;
6133
6236
}
6134
6237
 
6135
6238
 
6136
6239
/*
6137
 
  Calculate cost and E(#rows) for a given index and intervals tree 
 
6240
  Calculate cost and E(#rows) for a given index and intervals tree
6138
6241
 
6139
6242
  SYNOPSIS
6140
6243
    check_quick_select()
6162
6265
 
6163
6266
static
6164
6267
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
6165
 
                           SEL_ARG *tree, bool update_tbl_stats, 
 
6268
                           SEL_ARG *tree, bool update_tbl_stats,
6166
6269
                           uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
6167
6270
{
6168
6271
  SEL_ARG_RANGE_SEQ seq;
6170
6273
  handler *file= param->table->file;
6171
6274
  ha_rows rows;
6172
6275
  uint32_t keynr= param->real_keynr[idx];
6173
 
  
 
6276
 
6174
6277
  /* Handle cases when we don't have a valid non-empty list of range */
6175
6278
  if (!tree)
6176
6279
    return(HA_POS_ERROR);
6190
6293
  param->is_ror_scan= true;
6191
6294
  if (file->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)
6192
6295
    param->is_ror_scan= false;
6193
 
  
 
6296
 
6194
6297
  *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
6195
6298
  *mrr_flags|= HA_MRR_NO_ASSOCIATION;
6196
6299
 
6197
6300
  bool pk_is_clustered= file->primary_key_is_clustered();
6198
 
  if (index_only && 
 
6301
  if (index_only &&
6199
6302
      (file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&
6200
6303
      !(pk_is_clustered && keynr == param->table->s->primary_key))
6201
6304
     *mrr_flags |= HA_MRR_INDEX_ONLY;
6202
 
  
6203
 
  if (current_thd->lex->sql_command != SQLCOM_SELECT)
 
6305
 
 
6306
  if (current_session->lex->sql_command != SQLCOM_SELECT)
6204
6307
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6205
6308
 
6206
 
  *bufsize= param->thd->variables.read_rnd_buff_size;
 
6309
  *bufsize= param->session->variables.read_rnd_buff_size;
6207
6310
  rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,
6208
6311
                                          bufsize, mrr_flags, cost);
6209
6312
  if (rows != HA_POS_ERROR)
6222
6325
  enum ha_key_alg key_alg= param->table->key_info[seq.real_keyno].algorithm;
6223
6326
  if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF))
6224
6327
  {
6225
 
    /* 
 
6328
    /*
6226
6329
      All scans are non-ROR scans for those index types.
6227
 
      TODO: Don't have this logic here, make table engines return 
 
6330
      TODO: Don't have this logic here, make table engines return
6228
6331
      appropriate flags instead.
6229
6332
    */
6230
6333
    param->is_ror_scan= false;
6263
6366
 
6264
6367
    where the index is defined on (key1_1, ..., key1_N [,a_1, ..., a_n])
6265
6368
 
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 
 
6369
    and the table has a clustered Primary Key defined as
 
6370
      PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
 
6371
 
 
6372
    i.e. the first key parts of it are identical to uncovered parts ot the
6270
6373
    key being scanned. This function assumes that the index flags do not
6271
6374
    include HA_KEY_SCAN_NOT_ROR flag (that is checked elsewhere).
6272
6375
 
6284
6387
  KEY_PART_INFO *key_part_end= (table_key->key_part +
6285
6388
                                table_key->key_parts);
6286
6389
  uint32_t pk_number;
6287
 
  
 
6390
 
6288
6391
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
6289
6392
  {
6290
6393
    uint16_t fieldnr= param->table->key_info[keynr].
6330
6433
  NOTES
6331
6434
    The caller must call QUICK_SELECT::init for returned quick select.
6332
6435
 
6333
 
    CAUTION! This function may change thd->mem_root to a MEM_ROOT which will be
 
6436
    CAUTION! This function may change session->mem_root to a MEM_ROOT which will be
6334
6437
    deallocated when the returned quick select is deleted.
6335
6438
 
6336
6439
  RETURN
6345
6448
  QUICK_RANGE_SELECT *quick;
6346
6449
  bool create_err= false;
6347
6450
 
6348
 
  quick=new QUICK_RANGE_SELECT(param->thd, param->table,
 
6451
  quick=new QUICK_RANGE_SELECT(param->session, param->table,
6349
6452
                               param->real_keynr[idx],
6350
 
                               test(parent_alloc), NULL, &create_err);
 
6453
                               test(parent_alloc), NULL);
6351
6454
 
6352
6455
  if (quick)
6353
6456
  {
6369
6472
                    param->table->key_info[param->real_keynr[idx]].key_parts);
6370
6473
    }
6371
6474
  }
6372
 
  return(quick);
 
6475
  return quick;
6373
6476
}
6374
6477
 
6375
6478
 
6403
6506
      key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6404
6507
  {                                               // const key as prefix
6405
6508
    if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
6406
 
         memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 &&
 
6509
         memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
6407
6510
         key_tree->min_flag==0 && key_tree->max_flag==0)
6408
6511
    {
6409
6512
      if (get_quick_keys(param,quick,key,key_tree->next_key_part,
6444
6547
  }
6445
6548
  if (flag == 0)
6446
6549
  {
6447
 
    uint32_t length= (uint) (tmp_min_key - param->min_key);
6448
 
    if (length == (uint) (tmp_max_key - param->max_key) &&
 
6550
    uint32_t length= (uint32_t) (tmp_min_key - param->min_key);
 
6551
    if (length == (uint32_t) (tmp_max_key - param->max_key) &&
6449
6552
        !memcmp(param->min_key,param->max_key,length))
6450
6553
    {
6451
6554
      KEY *table_key=quick->head->key_info+quick->index;
6456
6559
        if (!(table_key->flags & HA_NULL_PART_KEY) ||
6457
6560
            !null_part_in_key(key,
6458
6561
                              param->min_key,
6459
 
                              (uint) (tmp_min_key - param->min_key)))
 
6562
                              (uint32_t) (tmp_min_key - param->min_key)))
6460
6563
          flag|= UNIQUE_RANGE;
6461
6564
        else
6462
6565
          flag|= NULL_RANGE;
6466
6569
 
6467
6570
  /* Get range for retrieving rows in QUICK_SELECT::get_next */
6468
6571
  if (!(range= new QUICK_RANGE(param->min_key,
6469
 
                               (uint) (tmp_min_key - param->min_key),
 
6572
                               (uint32_t) (tmp_min_key - param->min_key),
6470
6573
                               min_part >=0 ? make_keypart_map(min_part) : 0,
6471
6574
                               param->max_key,
6472
 
                               (uint) (tmp_max_key - param->max_key),
 
6575
                               (uint32_t) (tmp_max_key - param->max_key),
6473
6576
                               max_part >=0 ? make_keypart_map(max_part) : 0,
6474
6577
                               flag)))
6475
6578
    return 1;                   // out of memory
6476
6579
 
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);
 
6580
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
 
6581
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
 
6582
  set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
6480
6583
  if (insert_dynamic(&quick->ranges, (unsigned char*) &range))
6481
6584
    return 1;
6482
6585
 
6513
6616
  Return true if any part of the key is NULL
6514
6617
 
6515
6618
  SYNOPSIS
6516
 
    null_part_in_key()    
 
6619
    null_part_in_key()
6517
6620
      key_part  Array of key parts (index description)
6518
6621
      key       Key values tuple
6519
6622
      length    Length of key values tuple in bytes.
6536
6639
}
6537
6640
 
6538
6641
 
6539
 
bool QUICK_SELECT_I::is_keys_used(const MY_BITMAP *fields)
 
6642
bool QUICK_SELECT_I::is_keys_used(const bitset<MAX_FIELDS> *fields)
6540
6643
{
6541
6644
  return is_key_used(head, index, fields);
6542
6645
}
6543
6646
 
6544
 
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MY_BITMAP *fields)
6545
 
{
6546
 
  QUICK_RANGE_SELECT *quick;
6547
 
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6548
 
  while ((quick= it++))
6549
 
  {
6550
 
    if (is_key_used(head, quick->index, fields))
6551
 
      return 1;
6552
 
  }
6553
 
  return 0;
6554
 
}
6555
 
 
6556
 
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MY_BITMAP *fields)
6557
 
{
6558
 
  QUICK_RANGE_SELECT *quick;
6559
 
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6560
 
  while ((quick= it++))
6561
 
  {
6562
 
    if (is_key_used(head, quick->index, fields))
6563
 
      return 1;
6564
 
  }
6565
 
  return 0;
6566
 
}
6567
 
 
6568
 
bool QUICK_ROR_UNION_SELECT::is_keys_used(const MY_BITMAP *fields)
 
6647
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
 
6648
{
 
6649
  QUICK_RANGE_SELECT *quick;
 
6650
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6651
  while ((quick= it++))
 
6652
  {
 
6653
    if (is_key_used(head, quick->index, fields))
 
6654
      return 1;
 
6655
  }
 
6656
  return 0;
 
6657
}
 
6658
 
 
6659
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
 
6660
{
 
6661
  QUICK_RANGE_SELECT *quick;
 
6662
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6663
  while ((quick= it++))
 
6664
  {
 
6665
    if (is_key_used(head, quick->index, fields))
 
6666
      return 1;
 
6667
  }
 
6668
  return 0;
 
6669
}
 
6670
 
 
6671
bool QUICK_ROR_UNION_SELECT::is_keys_used(const bitset<MAX_FIELDS> *fields)
6569
6672
{
6570
6673
  QUICK_SELECT_I *quick;
6571
6674
  List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
6583
6686
 
6584
6687
  SYNOPSIS
6585
6688
    get_quick_select_for_ref()
6586
 
      thd      Thread handle
 
6689
      session      Thread handle
6587
6690
      table    Table to access
6588
6691
      ref      ref[_or_null] scan parameters
6589
6692
      records  Estimate of number of records (needed only to construct
6597
6700
    NULL on error.
6598
6701
*/
6599
6702
 
6600
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, Table *table,
 
6703
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
6601
6704
                                             TABLE_REF *ref, ha_rows records)
6602
6705
{
6603
6706
  MEM_ROOT *old_root, *alloc;
6609
6712
  bool create_err= false;
6610
6713
  COST_VECT cost;
6611
6714
 
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);
 
6715
  old_root= session->mem_root;
 
6716
  /* The following call may change session->mem_root */
 
6717
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0);
6615
6718
  /* save mem_root set by QUICK_RANGE_SELECT constructor */
6616
 
  alloc= thd->mem_root;
 
6719
  alloc= session->mem_root;
6617
6720
  /*
6618
 
    return back default mem_root (thd->mem_root) changed by
 
6721
    return back default mem_root (session->mem_root) changed by
6619
6722
    QUICK_RANGE_SELECT constructor
6620
6723
  */
6621
 
  thd->mem_root= old_root;
 
6724
  session->mem_root= old_root;
6622
6725
 
6623
6726
  if (!quick || create_err)
6624
6727
    return 0;                   /* no ranges found */
6626
6729
    goto err;
6627
6730
  quick->records= records;
6628
6731
 
6629
 
  if ((cp_buffer_from_ref(thd, ref) && thd->is_fatal_error) ||
 
6732
  if ((cp_buffer_from_ref(session, ref) && session->is_fatal_error) ||
6630
6733
      !(range= new(alloc) QUICK_RANGE()))
6631
6734
    goto err;                                   // out of memory
6632
6735
 
6676
6779
  }
6677
6780
 
6678
6781
  /* Call multi_range_read_info() to get the MRR flags and buffer size */
6679
 
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION | 
 
6782
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
6680
6783
                    (table->key_read ? HA_MRR_INDEX_ONLY : 0);
6681
 
  if (thd->lex->sql_command != SQLCOM_SELECT)
 
6784
  if (session->lex->sql_command != SQLCOM_SELECT)
6682
6785
    quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6683
6786
 
6684
 
  quick->mrr_buf_size= thd->variables.read_rnd_buff_size;
6685
 
  if (table->file->multi_range_read_info(quick->index, 1, (uint)records,
 
6787
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
 
6788
  if (table->file->multi_range_read_info(quick->index, 1, (uint32_t)records,
6686
6789
                                         &quick->mrr_buf_size,
6687
6790
                                         &quick->mrr_flags, &cost))
6688
6791
    goto err;
6695
6798
 
6696
6799
 
6697
6800
/*
6698
 
  Perform key scans for all used indexes (except CPK), get rowids and merge 
 
6801
  Perform key scans for all used indexes (except CPK), get rowids and merge
6699
6802
  them into an ordered non-recurrent sequence of rowids.
6700
 
  
 
6803
 
6701
6804
  The merge/duplicate removal is performed using Unique class. We put all
6702
6805
  rowids into Unique, get the sorted sequence and destroy the Unique.
6703
 
  
 
6806
 
6704
6807
  If table has a clustered primary key that covers all rows (true for bdb
6705
6808
  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 
 
6809
  then rows that will be retrieved by PK scan are not put into Unique and
6707
6810
  primary key scan is not performed here, it is performed later separately.
6708
6811
 
6709
6812
  RETURN
6725
6828
  cur_quick_it.rewind();
6726
6829
  cur_quick= cur_quick_it++;
6727
6830
  assert(cur_quick != 0);
6728
 
  
 
6831
 
6729
6832
  /*
6730
 
    We reuse the same instance of handler so we need to call both init and 
 
6833
    We reuse the same instance of handler so we need to call both init and
6731
6834
    reset here.
6732
6835
  */
6733
6836
  if (cur_quick->init() || cur_quick->reset())
6734
 
    return(1);
 
6837
    return 0;
6735
6838
 
6736
6839
  unique= new Unique(refpos_order_cmp, (void *)file,
6737
6840
                     file->ref_length,
6738
 
                     thd->variables.sortbuff_size);
 
6841
                     session->variables.sortbuff_size);
6739
6842
  if (!unique)
6740
 
    return(1);
 
6843
    return 0;
6741
6844
  for (;;)
6742
6845
  {
6743
6846
    while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6747
6850
      if (!cur_quick)
6748
6851
        break;
6749
6852
 
6750
 
      if (cur_quick->file->inited != handler::NONE) 
 
6853
      if (cur_quick->file->inited != handler::NONE)
6751
6854
        cur_quick->file->ha_index_end();
6752
6855
      if (cur_quick->init() || cur_quick->reset())
6753
 
        return(1);
 
6856
        return 0;
6754
6857
    }
6755
6858
 
6756
6859
    if (result)
6758
6861
      if (result != HA_ERR_END_OF_FILE)
6759
6862
      {
6760
6863
        cur_quick->range_end();
6761
 
        return(result);
 
6864
        return result;
6762
6865
      }
6763
6866
      break;
6764
6867
    }
6765
6868
 
6766
 
    if (thd->killed)
6767
 
      return(1);
 
6869
    if (session->killed)
 
6870
      return 0;
6768
6871
 
6769
6872
    /* skip row if it will be retrieved by clustered PK scan */
6770
6873
    if (pk_quick_select && pk_quick_select->row_in_ranges())
6773
6876
    cur_quick->file->position(cur_quick->record);
6774
6877
    result= unique->unique_add((char*)cur_quick->file->ref);
6775
6878
    if (result)
6776
 
      return(1);
 
6879
      return 0;
6777
6880
 
6778
6881
  }
6779
6882
 
6784
6887
  /* index_merge currently doesn't support "using index" at all */
6785
6888
  file->extra(HA_EXTRA_NO_KEYREAD);
6786
6889
  /* start table scan */
6787
 
  init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6788
 
  return(result);
 
6890
  init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
 
6891
  return result;
6789
6892
}
6790
6893
 
6791
6894
 
6815
6918
      doing_pk_scan= true;
6816
6919
      if ((result= pk_quick_select->init()) ||
6817
6920
          (result= pk_quick_select->reset()))
6818
 
        return(result);
 
6921
        return result;
6819
6922
      return(pk_quick_select->get_next());
6820
6923
    }
6821
6924
  }
6822
6925
 
6823
 
  return(result);
 
6926
  return result;
6824
6927
}
6825
6928
 
6826
6929
 
6939
7042
  {
6940
7043
    do
6941
7044
    {
6942
 
      if (!queue.elements)
 
7045
      if (queue->empty())
6943
7046
        return(HA_ERR_END_OF_FILE);
6944
7047
      /* Ok, we have a queue with >= 1 scans */
6945
7048
 
6946
 
      quick= (QUICK_SELECT_I*)queue_top(&queue);
 
7049
      quick= queue->top();
6947
7050
      memcpy(cur_rowid, quick->last_rowid, rowid_length);
6948
7051
 
6949
7052
      /* put into queue rowid from the same stream as top element */
6951
7054
      {
6952
7055
        if (error != HA_ERR_END_OF_FILE)
6953
7056
          return(error);
6954
 
        queue_remove(&queue, 0);
 
7057
        queue->pop();
6955
7058
      }
6956
7059
      else
6957
7060
      {
6958
7061
        quick->save_last_pos();
6959
 
        queue_replaced(&queue);
 
7062
        queue->pop();
 
7063
        queue->push(quick);
6960
7064
      }
6961
7065
 
6962
7066
      if (!have_prev_rowid)
6990
7094
 
6991
7095
  if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6992
7096
    return(error);
6993
 
 
 
7097
 
6994
7098
  /* Allocate buffer if we need one but haven't allocated it yet */
6995
7099
  if (mrr_buf_size && !mrr_buf_desc)
6996
7100
  {
7014
7118
 
7015
7119
  if (!mrr_buf_desc)
7016
7120
    empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7017
 
 
 
7121
 
7018
7122
  if (sorted)
7019
7123
     mrr_flags |= HA_MRR_SORTED;
7020
7124
  RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7021
7125
  error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7022
 
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc: 
 
7126
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc:
7023
7127
                                                              &empty_buf);
7024
7128
  return(error);
7025
7129
}
7027
7131
 
7028
7132
/*
7029
7133
  Range sequence interface implementation for array<QUICK_RANGE>: initialize
7030
 
  
 
7134
 
7031
7135
  SYNOPSIS
7032
7136
    quick_range_seq_init()
7033
7137
      init_param  Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
7034
7138
      n_ranges    Number of ranges in the sequence (ignored)
7035
 
      flags       MRR flags (currently not used) 
 
7139
      flags       MRR flags (currently not used)
7036
7140
 
7037
7141
  RETURN
7038
7142
    Opaque value to be passed to quick_range_seq_next
7039
7143
*/
7040
7144
 
7041
 
range_seq_t quick_range_seq_init(void *init_param,
7042
 
                                 uint32_t n_ranges __attribute__((unused)),
7043
 
                                 uint32_t flags __attribute__((unused)))
 
7145
range_seq_t quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7044
7146
{
7045
7147
  QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7046
7148
  quick->qr_traversal_ctx.first=  (QUICK_RANGE**)quick->ranges.buffer;
7053
7155
 
7054
7156
/*
7055
7157
  Range sequence interface implementation for array<QUICK_RANGE>: get next
7056
 
  
 
7158
 
7057
7159
  SYNOPSIS
7058
7160
    quick_range_seq_next()
7059
7161
      rseq        Value returned from quick_range_seq_init
7109
7211
    function returns a reference to the "range_flag" associated with the
7110
7212
    range number idx.
7111
7213
 
7112
 
    This function should be removed when we get a proper MRR/NDB 
 
7214
    This function should be removed when we get a proper MRR/NDB
7113
7215
    implementation.
7114
7216
 
7115
7217
  RETURN
7148
7250
    Reference to range-associated data
7149
7251
*/
7150
7252
 
7151
 
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7152
 
                          uint32_t idx __attribute__((unused)))
 
7253
char* &mrr_get_ptr_by_idx(range_seq_t, uint32_t)
7153
7254
{
7154
7255
  static char *dummy;
7155
7256
  return dummy;
7190
7291
    /* Restore bitmaps set on entry */
7191
7292
    head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7192
7293
  }
7193
 
  return(result);
 
7294
  return result;
7194
7295
}
7195
7296
 
7196
7297
 
7237
7338
      result= file->index_read_map(record, cur_prefix, keypart_map,
7238
7339
                                   HA_READ_AFTER_KEY);
7239
7340
      if (result || (file->compare_key(file->end_range) <= 0))
7240
 
        return(result);
 
7341
        return result;
7241
7342
    }
7242
7343
 
7243
7344
    uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7245
7346
    {
7246
7347
      /* Ranges have already been used up before. None is left for read. */
7247
7348
      last_range= 0;
7248
 
      return(HA_ERR_END_OF_FILE);
 
7349
      return HA_ERR_END_OF_FILE;
7249
7350
    }
7250
7351
    last_range= *(cur_range++);
7251
7352
 
7273
7374
      last_range= 0;                    // Stop searching
7274
7375
 
7275
7376
    if (result != HA_ERR_END_OF_FILE)
7276
 
      return(result);
 
7377
      return result;
7277
7378
    last_range= 0;                      // No matching rows; go to next range
7278
7379
  }
7279
7380
}
7329
7430
  for now, this seems to work right at least.
7330
7431
 */
7331
7432
 
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)))
 
7433
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7335
7434
 :QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7336
7435
{
7337
7436
  QUICK_RANGE *r;
7379
7478
      if (!result)
7380
7479
      {
7381
7480
        if (cmp_prev(*rev_it.ref()) == 0)
7382
 
          return(0);
 
7481
          return 0;
7383
7482
      }
7384
7483
      else if (result != HA_ERR_END_OF_FILE)
7385
 
        return(result);
 
7484
        return result;
7386
7485
    }
7387
7486
 
7388
7487
    if (!(last_range= rev_it++))
7389
 
      return(HA_ERR_END_OF_FILE);               // All ranges used
 
7488
      return HA_ERR_END_OF_FILE;                // All ranges used
7390
7489
 
7391
7490
    if (last_range->flag & NO_MAX_RANGE)        // Read last record
7392
7491
    {
7394
7493
      if ((local_error=file->index_last(record)))
7395
7494
        return(local_error);            // Empty table
7396
7495
      if (cmp_prev(last_range) == 0)
7397
 
        return(0);
 
7496
        return 0;
7398
7497
      last_range= 0;                            // No match; go to next range
7399
7498
      continue;
7400
7499
    }
7418
7517
    if (result)
7419
7518
    {
7420
7519
      if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7421
 
        return(result);
 
7520
        return result;
7422
7521
      last_range= 0;                            // Not found, to next range
7423
7522
      continue;
7424
7523
    }
7426
7525
    {
7427
7526
      if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7428
7527
        last_range= 0;                          // Stop searching
7429
 
      return(0);                                // Found key is in range
 
7528
      return 0;                         // Found key is in range
7430
7529
    }
7431
7530
    last_range= 0;                              // To next range
7432
7531
  }
7436
7535
/*
7437
7536
  Compare if found key is over max-value
7438
7537
  Returns 0 if key <= range->max_key
7439
 
  TODO: Figure out why can't this function be as simple as cmp_prev(). 
 
7538
  TODO: Figure out why can't this function be as simple as cmp_prev().
7440
7539
*/
7441
7540
 
7442
7541
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7686
7785
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7687
7786
                       KEY_PART_INFO *first_non_group_part,
7688
7787
                       KEY_PART_INFO *min_max_arg_part,
7689
 
                       KEY_PART_INFO *last_part, THD *thd,
 
7788
                       KEY_PART_INFO *last_part, Session *session,
7690
7789
                       unsigned char *key_infix, uint32_t *key_infix_len,
7691
7790
                       KEY_PART_INFO **first_non_infix_part);
7692
7791
static bool
7729
7828
        - NGA = QA - (GA union C) = {NG_1, ..., NG_m} - the ones not in
7730
7829
          GROUP BY and not referenced by MIN/MAX functions.
7731
7830
        with the following properties specified below.
7732
 
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not 
 
7831
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
7733
7832
        applicable.
7734
7833
 
7735
7834
    SA1. There is at most one attribute in SA referenced by any number of
7817
7916
    other field as in: "select min(a) from t1 group by a" ?
7818
7917
  - We assume that the general correctness of the GROUP-BY query was checked
7819
7918
    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 
 
7919
  - Lift the limitation in condition (B3), that is, make this access method
7821
7920
    applicable to ROLLUP queries.
7822
7921
 
7823
7922
  RETURN
7832
7931
static TRP_GROUP_MIN_MAX *
7833
7932
get_best_group_min_max(PARAM *param, SEL_TREE *tree)
7834
7933
{
7835
 
  THD *thd= param->thd;
7836
 
  JOIN *join= thd->lex->current_select->join;
 
7934
  Session *session= param->session;
 
7935
  JOIN *join= session->lex->current_select->join;
7837
7936
  Table *table= param->table;
7838
7937
  bool have_min= false;              /* true if there is a MIN function. */
7839
7938
  bool have_max= false;              /* true if there is a MAX function. */
7854
7953
 
7855
7954
  /* Perform few 'cheap' tests whether this access method is applicable. */
7856
7955
  if (!join)
7857
 
    return(NULL);        /* This is not a select statement. */
 
7956
    return NULL;        /* This is not a select statement. */
7858
7957
  if ((join->tables != 1) ||  /* The query must reference one table. */
7859
7958
      ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
7860
7959
       (!join->select_distinct)) ||
7861
7960
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
7862
 
    return(NULL);
 
7961
    return NULL;
7863
7962
  if (table->s->keys == 0)        /* There are no indexes to use. */
7864
 
    return(NULL);
 
7963
    return NULL;
7865
7964
 
7866
7965
  /* Analyze the query in more detail. */
7867
7966
  List_iterator<Item> select_items_it(join->fields_list);
7868
7967
 
7869
7968
  /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
7870
7969
  if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
7871
 
    return(NULL);
 
7970
    return NULL;
7872
7971
  if (join->sum_funcs[0])
7873
7972
  {
7874
7973
    Item_sum *min_max_item;
7880
7979
      else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
7881
7980
        have_max= true;
7882
7981
      else
7883
 
        return(NULL);
 
7982
        return NULL;
7884
7983
 
7885
7984
      /* The argument of MIN/MAX. */
7886
 
      Item *expr= min_max_item->args[0]->real_item();    
 
7985
      Item *expr= min_max_item->args[0]->real_item();
7887
7986
      if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */
7888
7987
      {
7889
7988
        if (! min_max_arg_item)
7890
7989
          min_max_arg_item= (Item_field*) expr;
7891
7990
        else if (! min_max_arg_item->eq(expr, 1))
7892
 
          return(NULL);
 
7991
          return NULL;
7893
7992
      }
7894
7993
      else
7895
 
        return(NULL);
 
7994
        return NULL;
7896
7995
    }
7897
7996
  }
7898
7997
 
7902
8001
    while ((item= select_items_it++))
7903
8002
    {
7904
8003
      if (item->type() != Item::FIELD_ITEM)
7905
 
        return(NULL);
 
8004
        return NULL;
7906
8005
    }
7907
8006
  }
7908
8007
 
7910
8009
  for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
7911
8010
  {
7912
8011
    if ((*tmp_group->item)->type() != Item::FIELD_ITEM)
7913
 
      return(NULL);
 
8012
      return NULL;
7914
8013
  }
7915
8014
 
7916
8015
  /*
7970
8069
          If the field is used in the current query ensure that it's
7971
8070
          part of 'cur_index'
7972
8071
        */
7973
 
        if (bitmap_is_set(table->read_set, cur_field->field_index) &&
 
8072
        if (table->read_set->test(cur_field->field_index) &&
7974
8073
            !cur_field->part_of_key_not_clustered.is_set(cur_index))
7975
8074
          goto next_index;                  // Field was not part of key
7976
8075
      }
8094
8193
                                                        &dummy);
8095
8194
        if (!get_constant_key_infix(cur_index_info, index_range_tree,
8096
8195
                                    first_non_group_part, min_max_arg_part,
8097
 
                                    last_part, thd, key_infix, &key_infix_len,
 
8196
                                    last_part, session, key_infix, &key_infix_len,
8098
8197
                                    &first_non_infix_part))
8099
8198
          goto next_index;
8100
8199
      }
8142
8241
                (min_max_arg_part && (min_max_arg_part < last_part));
8143
8242
      for (; cur_part != last_part; cur_part++)
8144
8243
      {
8145
 
        if (bitmap_is_set(table->read_set, cur_part->field->field_index))
 
8244
        if (table->read_set->test(cur_part->field->field_index))
8146
8245
          goto next_index;
8147
8246
      }
8148
8247
    }
8162
8261
      COST_VECT dummy_cost;
8163
8262
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
8164
8263
      uint32_t mrr_bufsize=0;
8165
 
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx, 
8166
 
                                                   false /*don't care*/, 
 
8264
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
 
8265
                                                   false /*don't care*/,
8167
8266
                                                   cur_index_tree, true,
8168
8267
                                                   &mrr_flags, &mrr_bufsize,
8169
8268
                                                   &dummy_cost);
8196
8295
    cur_group_prefix_len= 0;
8197
8296
  }
8198
8297
  if (!index_info) /* No usable index found. */
8199
 
    return(NULL);
 
8298
    return NULL;
8200
8299
 
8201
8300
  /* Check (SA3) for the where clause. */
8202
8301
  if (join->conds && min_max_arg_item &&
8203
8302
      !check_group_min_max_predicates(join->conds, min_max_arg_item, Field::itRAW))
8204
 
    return(NULL);
 
8303
    return NULL;
8205
8304
 
8206
8305
  /* The query passes all tests, so construct a new TRP object. */
8207
8306
  read_plan= new (param->mem_root)
8215
8314
  if (read_plan)
8216
8315
  {
8217
8316
    if (tree && read_plan->quick_prefix_records == 0)
8218
 
      return(NULL);
 
8317
      return NULL;
8219
8318
 
8220
8319
    read_plan->read_cost= best_read_cost;
8221
8320
    read_plan->records=   best_records;
8222
8321
  }
8223
8322
 
8224
 
  return(read_plan);
 
8323
  return read_plan;
8225
8324
}
8226
8325
 
8227
8326
 
8263
8362
    {
8264
8363
      if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,
8265
8364
                                         image_type))
8266
 
        return(false);
 
8365
        return false;
8267
8366
    }
8268
 
    return(true);
 
8367
    return true;
8269
8368
  }
8270
8369
 
8271
8370
  /*
8278
8377
    so.
8279
8378
  */
8280
8379
  if (cond_type == Item::SUBSELECT_ITEM)
8281
 
    return(false);
8282
 
  
 
8380
    return false;
 
8381
 
8283
8382
  /* We presume that at this point there are no other Items than functions. */
8284
8383
  assert(cond_type == Item::FUNC_ITEM);
8285
8384
 
8292
8391
    cur_arg= arguments[arg_idx]->real_item();
8293
8392
    if (cur_arg->type() == Item::FIELD_ITEM)
8294
8393
    {
8295
 
      if (min_max_arg_item->eq(cur_arg, 1)) 
 
8394
      if (min_max_arg_item->eq(cur_arg, 1))
8296
8395
      {
8297
8396
       /*
8298
8397
         If pred references the MIN/MAX argument, check whether pred is a range
8309
8408
            pred_type != Item_func::ISNOTNULL_FUNC &&
8310
8409
            pred_type != Item_func::EQ_FUNC        &&
8311
8410
            pred_type != Item_func::NE_FUNC)
8312
 
          return(false);
 
8411
          return false;
8313
8412
 
8314
8413
        /* Check that pred compares min_max_arg_item with a constant. */
8315
8414
        Item *args[3];
8317
8416
        bool inv;
8318
8417
        /* Test if this is a comparison of a field and a constant. */
8319
8418
        if (!simple_pred(pred, args, &inv))
8320
 
          return(false);
 
8419
          return false;
8321
8420
 
8322
8421
        /* Check for compatible string comparisons - similar to get_mm_leaf. */
8323
8422
        if (args[0] && args[1] && !args[2] && // this is a binary function
8336
8435
             */
8337
8436
             (args[1]->result_type() != STRING_RESULT &&
8338
8437
              min_max_arg_item->field->cmp_type() != args[1]->result_type())))
8339
 
          return(false);
 
8438
          return false;
8340
8439
      }
8341
8440
    }
8342
8441
    else if (cur_arg->type() == Item::FUNC_ITEM)
8343
8442
    {
8344
8443
      if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,
8345
8444
                                         image_type))
8346
 
        return(false);
 
8445
        return false;
8347
8446
    }
8348
8447
    else if (cur_arg->const_item())
8349
8448
    {
8350
 
      return(true);
 
8449
      return true;
8351
8450
    }
8352
8451
    else
8353
 
      return(false);
 
8452
      return false;
8354
8453
  }
8355
8454
 
8356
 
  return(true);
 
8455
  return true;
8357
8456
}
8358
8457
 
8359
8458
 
8367
8466
    first_non_group_part   [in]  First index part after group attribute parts
8368
8467
    min_max_arg_part       [in]  The keypart of the MIN/MAX argument if any
8369
8468
    last_part              [in]  Last keypart of the index
8370
 
    thd                    [in]  Current thread
 
8469
    session                    [in]  Current thread
8371
8470
    key_infix              [out] Infix of constants to be used for index lookup
8372
8471
    key_infix_len          [out] Lenghth of the infix
8373
8472
    first_non_infix_part   [out] The first keypart after the infix (if any)
8374
 
    
 
8473
 
8375
8474
  DESCRIPTION
8376
8475
    Test conditions (NGA1, NGA2) from get_best_group_min_max(). Namely,
8377
8476
    for each keypart field NGF_i not in GROUP-BY, check that there is a
8389
8488
*/
8390
8489
 
8391
8490
static bool
8392
 
get_constant_key_infix(KEY *index_info __attribute__((unused)),
8393
 
                       SEL_ARG *index_range_tree,
 
8491
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
8394
8492
                       KEY_PART_INFO *first_non_group_part,
8395
8493
                       KEY_PART_INFO *min_max_arg_part,
8396
8494
                       KEY_PART_INFO *last_part,
8397
 
                       THD *thd __attribute__((unused)),
8398
 
                       unsigned char *key_infix, uint32_t *key_infix_len,
 
8495
                       Session *, unsigned char *key_infix, uint32_t *key_infix_len,
8399
8496
                       KEY_PART_INFO **first_non_infix_part)
8400
8497
{
8401
8498
  SEL_ARG       *cur_range;
8522
8619
    idx++;
8523
8620
  }
8524
8621
  *param_idx= idx;
8525
 
  return(range_tree->keys[idx]);
 
8622
  return range_tree->keys[idx];
8526
8623
}
8527
8624
 
8528
8625
 
8588
8685
 
8589
8686
void cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
8590
8687
                        uint32_t group_key_parts, SEL_TREE *range_tree,
8591
 
                        SEL_ARG *index_tree __attribute__((unused)),
8592
 
                        ha_rows quick_prefix_records,
 
8688
                        SEL_ARG *, ha_rows quick_prefix_records,
8593
8689
                        bool have_min, bool have_max,
8594
8690
                        double *read_cost, ha_rows *records)
8595
8691
{
8609
8705
  keys_per_block= (table->file->stats.block_size / 2 /
8610
8706
                   (index_info->key_length + table->file->ref_length)
8611
8707
                        + 1);
8612
 
  num_blocks= (uint)(table_records / keys_per_block) + 1;
 
8708
  num_blocks= (uint32_t)(table_records / keys_per_block) + 1;
8613
8709
 
8614
8710
  /* Compute the number of keys in a group. */
8615
8711
  keys_per_group= index_info->rec_per_key[group_key_parts - 1];
8616
8712
  if (keys_per_group == 0) /* If there is no statistics try to guess */
8617
8713
    /* 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;
 
8714
    keys_per_group= (uint32_t)(table_records / 10) + 1;
 
8715
  num_groups= (uint32_t)(table_records / keys_per_group) + 1;
8620
8716
 
8621
8717
  /* Apply the selectivity of the quick select for group prefixes. */
8622
8718
  if (range_tree && (quick_prefix_records != HA_POS_ERROR))
8623
8719
  {
8624
8720
    quick_prefix_selectivity= (double) quick_prefix_records /
8625
8721
                              (double) table_records;
8626
 
    num_groups= (uint) rint(num_groups * quick_prefix_selectivity);
8627
 
    set_if_bigger(num_groups, 1);
 
8722
    num_groups= (uint32_t) rint(num_groups * quick_prefix_selectivity);
 
8723
    set_if_bigger(num_groups, 1U);
8628
8724
  }
8629
8725
 
8630
8726
  if (used_key_parts > group_key_parts)
8658
8754
 
8659
8755
  *read_cost= io_cost + cpu_cost;
8660
8756
  *records= num_groups;
8661
 
  return;
8662
8757
}
8663
8758
 
8664
8759
 
8684
8779
*/
8685
8780
 
8686
8781
QUICK_SELECT_I *
8687
 
TRP_GROUP_MIN_MAX::make_quick(PARAM *param,
8688
 
                              bool retrieve_full_rows __attribute__((unused)),
8689
 
                              MEM_ROOT *parent_alloc)
 
8782
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
8690
8783
{
8691
8784
  QUICK_GROUP_MIN_MAX_SELECT *quick;
8692
8785
 
8693
8786
  quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table,
8694
 
                                        param->thd->lex->current_select->join,
 
8787
                                        param->session->lex->current_select->join,
8695
8788
                                        have_min, have_max, min_max_arg_part,
8696
8789
                                        group_prefix_len, group_key_parts,
8697
8790
                                        used_key_parts, index_info, index,
8698
8791
                                        read_cost, records, key_infix_len,
8699
8792
                                        key_infix, parent_alloc);
8700
8793
  if (!quick)
8701
 
    return(NULL);
 
8794
    return NULL;
8702
8795
 
8703
8796
  if (quick->init())
8704
8797
  {
8705
8798
    delete quick;
8706
 
    return(NULL);
 
8799
    return NULL;
8707
8800
  }
8708
8801
 
8709
8802
  if (range_tree)
8742
8835
        {
8743
8836
          delete quick;
8744
8837
          quick= NULL;
8745
 
          return(NULL);
 
8838
          return NULL;
8746
8839
        }
8747
8840
        min_max_range= min_max_range->next;
8748
8841
      }
8754
8847
  quick->update_key_stat();
8755
8848
  quick->adjust_prefix_ranges();
8756
8849
 
8757
 
  return(quick);
 
8850
  return quick;
8758
8851
}
8759
8852
 
8760
8853
 
8819
8912
  assert(!parent_alloc);
8820
8913
  if (!parent_alloc)
8821
8914
  {
8822
 
    init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8823
 
    join->thd->mem_root= &alloc;
 
8915
    init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
 
8916
    join->session->mem_root= &alloc;
8824
8917
  }
8825
8918
  else
8826
8919
    memset(&alloc, 0, sizeof(MEM_ROOT));  // ensure that it's not used
8832
8925
 
8833
8926
  SYNOPSIS
8834
8927
    QUICK_GROUP_MIN_MAX_SELECT::init()
8835
 
  
 
8928
 
8836
8929
  DESCRIPTION
8837
8930
    The method performs initialization that cannot be done in the constructor
8838
8931
    such as memory allocations that may fail. It allocates memory for the
8923
9016
 
8924
9017
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8925
9018
{
8926
 
  if (file->inited != handler::NONE) 
 
9019
  if (file->inited != handler::NONE)
8927
9020
    file->ha_index_end();
8928
9021
  if (min_max_arg_part)
8929
9022
    delete_dynamic(&min_max_ranges);
8931
9024
  delete min_functions_it;
8932
9025
  delete max_functions_it;
8933
9026
  delete quick_prefix_select;
8934
 
  return; 
8935
9027
}
8936
9028
 
8937
9029
 
8940
9032
 
8941
9033
  SYNOPSIS
8942
9034
    QUICK_GROUP_MIN_MAX_SELECT::add_range()
8943
 
    sel_range  Range object from which a 
 
9035
    sel_range  Range object from which a
8944
9036
 
8945
9037
  NOTES
8946
9038
    Construct a new QUICK_RANGE object from a SEL_ARG object, and
8994
9086
 
8995
9087
  NOTES
8996
9088
    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 
 
9089
    It defines a number of ranges of length x.
 
9090
    However when jumping through the prefixes we use only the the first
8999
9091
    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 
 
9092
    are more keyparts to follow the ones we are using we must make the
 
9093
    condition on the key inclusive (because x < "ab" means
9002
9094
    x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9003
9095
    To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9004
9096
*/
9108
9200
 
9109
9201
  file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9110
9202
  if ((result= file->ha_index_init(index,1)))
9111
 
    return(result);
 
9203
    return result;
9112
9204
  if (quick_prefix_select && quick_prefix_select->reset())
9113
 
    return(1);
 
9205
    return 0;
9114
9206
  result= file->index_last(record);
9115
9207
  if (result == HA_ERR_END_OF_FILE)
9116
 
    return(0);
 
9208
    return 0;
9117
9209
  /* Save the prefix of the last group. */
9118
9210
  key_copy(last_prefix, record, index_info, group_prefix_len);
9119
9211
 
9120
 
  return(0);
 
9212
  return 0;
9121
9213
}
9122
9214
 
9123
9215
 
9124
9216
 
9125
 
/* 
 
9217
/*
9126
9218
  Get the next key containing the MIN and/or MAX key for the next group.
9127
9219
 
9128
9220
  SYNOPSIS
9173
9265
                              group_prefix_len);
9174
9266
      assert(is_last_prefix <= 0);
9175
9267
    }
9176
 
    else 
 
9268
    else
9177
9269
    {
9178
9270
      if (result == HA_ERR_KEY_NOT_FOUND)
9179
9271
        continue;
9194
9286
      if (max_res == 0)
9195
9287
        update_max_result();
9196
9288
      /* 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)));
 
9289
      assert(((have_max && !have_min) ||
 
9290
                  (have_max && have_min && (max_res == 0))));
9199
9291
    }
9200
9292
    /*
9201
9293
      If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9224
9316
  else if (result == HA_ERR_KEY_NOT_FOUND)
9225
9317
    result= HA_ERR_END_OF_FILE;
9226
9318
 
9227
 
  return(result);
 
9319
  return result;
9228
9320
}
9229
9321
 
9230
9322
 
9259
9351
  if (min_max_ranges.elements > 0)
9260
9352
  {
9261
9353
    if ((result= next_min_in_range()))
9262
 
      return(result);
 
9354
      return result;
9263
9355
  }
9264
9356
  else
9265
9357
  {
9269
9361
      if ((result= file->index_read_map(record, group_prefix,
9270
9362
                                        make_prev_keypart_map(real_key_parts),
9271
9363
                                        HA_READ_KEY_EXACT)))
9272
 
        return(result);
 
9364
        return result;
9273
9365
    }
9274
9366
 
9275
9367
    /*
9310
9402
    If the MIN attribute is non-nullable, this->record already contains the
9311
9403
    MIN key in the group, so just return.
9312
9404
  */
9313
 
  return(result);
 
9405
  return result;
9314
9406
}
9315
9407
 
9316
9408
 
9317
 
/* 
 
9409
/*
9318
9410
  Retrieve the maximal key in the next group.
9319
9411
 
9320
9412
  SYNOPSIS
9341
9433
    result= file->index_read_map(record, group_prefix,
9342
9434
                                 make_prev_keypart_map(real_key_parts),
9343
9435
                                 HA_READ_PREFIX_LAST);
9344
 
  return(result);
 
9436
  return result;
9345
9437
}
9346
9438
 
9347
9439
 
9375
9467
    unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9376
9468
    if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9377
9469
                         make_prev_keypart_map(group_key_parts), cur_prefix)))
9378
 
      return(result);
 
9470
      return result;
9379
9471
    seen_first_key= true;
9380
9472
  }
9381
9473
  else
9384
9476
    {
9385
9477
      result= file->index_first(record);
9386
9478
      if (result)
9387
 
        return(result);
 
9479
        return result;
9388
9480
      seen_first_key= true;
9389
9481
    }
9390
9482
    else
9394
9486
                                   make_prev_keypart_map(group_key_parts),
9395
9487
                                   HA_READ_AFTER_KEY);
9396
9488
      if (result)
9397
 
        return(result);
 
9489
        return result;
9398
9490
    }
9399
9491
  }
9400
9492
 
9405
9497
    memcpy(group_prefix + group_prefix_len,
9406
9498
           key_infix, key_infix_len);
9407
9499
 
9408
 
  return(0);
 
9500
  return 0;
9409
9501
}
9410
9502
 
9411
9503
 
9437
9529
  QUICK_RANGE *cur_range;
9438
9530
  bool found_null= false;
9439
9531
  int result= HA_ERR_KEY_NOT_FOUND;
 
9532
  basic_string<unsigned char> max_key;
 
9533
 
 
9534
  max_key.reserve(real_prefix_len + min_max_arg_len);
9440
9535
 
9441
9536
  assert(min_max_ranges.elements > 0);
9442
9537
 
9510
9605
    if ( !(cur_range->flag & NO_MAX_RANGE) )
9511
9606
    {
9512
9607
      /* 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);
 
9608
      max_key.clear();
 
9609
      max_key.append(group_prefix, real_prefix_len);
 
9610
      max_key.append(cur_range->max_key, cur_range->max_length);
9517
9611
      /* Compare the found key with max_key. */
9518
 
      int cmp_res= key_cmp(index_info->key_part, max_key,
 
9612
      int cmp_res= key_cmp(index_info->key_part,
 
9613
                           max_key.data(),
9519
9614
                           real_prefix_len + min_max_arg_len);
9520
9615
      if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9521
9616
      {
9568
9663
  key_part_map keypart_map;
9569
9664
  QUICK_RANGE *cur_range;
9570
9665
  int result;
 
9666
  basic_string<unsigned char> min_key;
 
9667
  min_key.reserve(real_prefix_len + min_max_arg_len);
9571
9668
 
9572
9669
  assert(min_max_ranges.elements > 0);
9573
9670
 
9627
9724
    if ( !(cur_range->flag & NO_MIN_RANGE) )
9628
9725
    {
9629
9726
      /* 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);
 
9727
      min_key.clear();
 
9728
      min_key.append(group_prefix, real_prefix_len);
 
9729
      min_key.append(cur_range->min_key, cur_range->min_length);
 
9730
 
9634
9731
      /* Compare the found key with min_key. */
9635
 
      int cmp_res= key_cmp(index_info->key_part, min_key,
 
9732
      int cmp_res= key_cmp(index_info->key_part,
 
9733
                           min_key.data(),
9636
9734
                           real_prefix_len + min_max_arg_len);
9637
9735
      if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9638
9736
            (cmp_res >= 0)))
9735
9833
  used_lengths->append(buf, length);
9736
9834
}
9737
9835
 
9738
 
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9739
 
                           const char *msg __attribute__((unused)))
 
9836
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9740
9837
{
9741
9838
  SEL_ARG **key,**end;
9742
9839
  int idx;
9758
9855
  }
9759
9856
  if (!tmp.length())
9760
9857
    tmp.append(STRING_WITH_LEN("(empty)"));
9761
 
 
9762
 
  return;
9763
9858
}
9764
9859
 
9765
9860
 
9766
9861
static void print_ror_scans_arr(Table *table,
9767
 
                                const char *msg __attribute__((unused)),
9768
 
                                struct st_ror_scan_info **start,
 
9862
                                const char *, struct st_ror_scan_info **start,
9769
9863
                                struct st_ror_scan_info **end)
9770
9864
{
9771
9865
  char buff[1024];
9779
9873
  }
9780
9874
  if (!tmp.length())
9781
9875
    tmp.append(STRING_WITH_LEN("(empty)"));
9782
 
  return;
9783
9876
}
9784
9877
 
9785
9878
/*****************************************************************************
9786
 
** Instantiate templates 
 
9879
** Instantiate templates
9787
9880
*****************************************************************************/
9788
9881
 
9789
9882
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION