← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

Merged in latest plugin-slot-reorg.

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
#include <drizzled/sql_base.h>
107
108
#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
 
109
#include <drizzled/error.h>
 
110
#include <drizzled/cost_vect.h>
 
111
#include <drizzled/item/cmpfunc.h>
 
112
#include <drizzled/field/num.h>
 
113
#include <drizzled/check_stack_overrun.h>
 
114
 
 
115
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
 
116
 
 
117
#include <string>
 
118
#include <vector>
 
119
#include <algorithm>
 
120
 
 
121
using namespace std;
 
122
 
 
123
#define HA_END_SPACE_KEY 0
113
124
 
114
125
/*
115
126
  Convert double value to #rows. Currently this does floor(), and we
116
127
  might consider using round() instead.
117
128
*/
118
 
#define double2rows(x) ((ha_rows)(x))
 
129
static inline ha_rows double2rows(double x)
 
130
{
 
131
    return static_cast<ha_rows>(x);
 
132
}
 
133
 
 
134
extern "C" int refpos_order_cmp(void* arg, const void *a,const void *b)
 
135
{
 
136
  handler *file= (handler*)arg;
 
137
  return file->cmp_ref((const unsigned char*)a, (const unsigned char*)b);
 
138
}
119
139
 
120
140
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
121
141
 
124
144
class RANGE_OPT_PARAM;
125
145
/*
126
146
  A construction block of the SEL_ARG-graph.
127
 
  
128
 
  The following description only covers graphs of SEL_ARG objects with 
 
147
 
 
148
  The following description only covers graphs of SEL_ARG objects with
129
149
  sel_arg->type==KEY_RANGE:
130
150
 
131
151
  One SEL_ARG object represents an "elementary interval" in form
132
 
  
 
152
 
133
153
      min_value <=?  table.keypartX  <=? max_value
134
 
  
 
154
 
135
155
  The interval is a non-empty interval of any kind: with[out] minimum/maximum
136
156
  bound, [half]open/closed, single-point interval, etc.
137
157
 
138
158
  1. SEL_ARG GRAPH STRUCTURE
139
 
  
 
159
 
140
160
  SEL_ARG objects are linked together in a graph. The meaning of the graph
141
161
  is better demostrated by an example:
142
 
  
 
162
 
143
163
     tree->keys[i]
144
 
      | 
 
164
      |
145
165
      |             $              $
146
166
      |    part=1   $     part=2   $    part=3
147
167
      |             $              $
150
170
      |  +-------+  $   +-------+  $   +--------+
151
171
      |      |      $              $       |
152
172
      |      |      $              $   +--------+
153
 
      |      |      $              $   | kp3=12 | 
154
 
      |      |      $              $   +--------+ 
155
 
      |  +-------+  $              $   
156
 
      \->| kp1=2 |--$--------------$-+ 
 
173
      |      |      $              $   | kp3=12 |
 
174
      |      |      $              $   +--------+
 
175
      |  +-------+  $              $
 
176
      \->| kp1=2 |--$--------------$-+
157
177
         +-------+  $              $ |   +--------+
158
178
             |      $              $  ==>| kp3=11 |
159
179
         +-------+  $              $ |   +--------+
161
181
         +-------+  $              $     +--------+
162
182
             |      $              $     | kp3=14 |
163
183
            ...     $              $     +--------+
164
 
 
 
184
 
165
185
  The entire graph is partitioned into "interval lists".
166
186
 
167
187
  An interval list is a sequence of ordered disjoint intervals over the same
168
188
  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 
 
189
  all intervals in the list form an RB-tree, linked via left/right/parent
170
190
  pointers. The RB-tree root SEL_ARG object will be further called "root of the
171
191
  interval list".
172
 
  
173
 
    In the example pic, there are 4 interval lists: 
 
192
 
 
193
    In the example pic, there are 4 interval lists:
174
194
    "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
175
195
    The vertical lines represent SEL_ARG::next/prev pointers.
176
 
    
 
196
 
177
197
  In an interval list, each member X may have SEL_ARG::next_key_part pointer
178
198
  pointing to the root of another interval list Y. The pointed interval list
179
199
  must cover a key part with greater number (i.e. Y->part > X->part).
180
 
    
 
200
 
181
201
    In the example pic, the next_key_part pointers are represented by
182
202
    horisontal lines.
183
203
 
185
205
 
186
206
  It represents a condition in a special form (we don't have a name for it ATM)
187
207
  The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
188
 
  
 
208
 
189
209
  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 
 
210
   (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
 
211
   (kp1=2 AND (kp3=11 OR kp3=14)) OR
192
212
   (kp1=3 AND (kp3=11 OR kp3=14))
193
213
 
194
214
 
197
217
  Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
198
218
  Then walk the SEL_ARG graph and get a list of dijsoint ordered key
199
219
  intervals (i.e. intervals in form
200
 
  
 
220
 
201
221
   (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
202
222
 
203
223
  Those intervals can be used to access the index. The uses are in:
208
228
                            and create QUICK_RANGE_SELECT object that will
209
229
                            read records within these intervals.
210
230
 
211
 
  4. SPACE COMPLEXITY NOTES 
 
231
  4. SPACE COMPLEXITY NOTES
212
232
 
213
233
    SEL_ARG graph is a representation of an ordered disjoint sequence of
214
234
    intervals over the ordered set of index tuple values.
215
235
 
216
236
    For multi-part keys, one can construct a WHERE expression such that its
217
237
    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 
 
238
 
 
239
      (keypart1 IN (1,2, ..., n1)) AND
 
240
      (keypart2 IN (1,2, ..., n2)) AND
221
241
      (keypart3 IN (1,2, ..., n3))
222
 
    
 
242
 
223
243
    For this WHERE clause the list of intervals will have n1*n2*n3 intervals
224
244
    of form
225
 
     
 
245
 
226
246
      (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
227
 
    
 
247
 
228
248
    SEL_ARG graph structure aims to reduce the amount of required space by
229
249
    "sharing" the elementary intervals when possible (the pic at the
230
 
    beginning of this comment has examples of such sharing). The sharing may 
 
250
    beginning of this comment has examples of such sharing). The sharing may
231
251
    prevent combinatorial blowup:
232
252
 
233
253
      There are WHERE clauses that have combinatorial-size interval lists but
234
254
      will be represented by a compact SEL_ARG graph.
235
255
      Example:
236
 
        (keypartN IN (1,2, ..., n1)) AND 
 
256
        (keypartN IN (1,2, ..., n1)) AND
237
257
        ...
238
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
258
        (keypart2 IN (1,2, ..., n2)) AND
239
259
        (keypart1 IN (1,2, ..., n3))
240
260
 
241
261
    but not in all cases:
244
264
      representation but get_mm_tree() and its callees will construct a
245
265
      graph of combinatorial size.
246
266
      Example:
247
 
        (keypart1 IN (1,2, ..., n1)) AND 
248
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
267
        (keypart1 IN (1,2, ..., n1)) AND
 
268
        (keypart2 IN (1,2, ..., n2)) AND
249
269
        ...
250
270
        (keypartN IN (1,2, ..., n3))
251
271
 
255
275
        By induction: Let's take any interval on some keypart in the middle:
256
276
 
257
277
           kp15=c0
258
 
        
 
278
 
259
279
        Then let's AND it with this interval 'structure' from preceding and
260
280
        following keyparts:
261
281
 
262
282
          (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
263
 
        
 
283
 
264
284
        We will obtain this SEL_ARG graph:
265
 
 
 
285
 
266
286
             kp14     $      kp15      $      kp16
267
287
                      $                $
268
288
         +---------+  $   +---------+  $   +---------+
269
289
         | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
270
290
         +---------+  $   +---------+  $   +---------+
271
 
              |       $                $              
272
 
         +---------+  $   +---------+  $             
273
 
         | kp14=c2 |--$-->| kp15=c0 |  $             
274
 
         +---------+  $   +---------+  $             
 
291
              |       $                $
 
292
         +---------+  $   +---------+  $
 
293
         | kp14=c2 |--$-->| kp15=c0 |  $
 
294
         +---------+  $   +---------+  $
275
295
                      $                $
276
 
                      
 
296
 
277
297
       Note that we had to duplicate "kp15=c0" and there was no way to avoid
278
 
       that. 
 
298
       that.
279
299
       The induction step: AND the obtained expression with another "wrapping"
280
300
       expression like (*).
281
 
       When the process ends because of the limit on max. number of keyparts 
 
301
       When the process ends because of the limit on max. number of keyparts
282
302
       we'll have:
283
303
 
284
304
         WHERE clause length  is O(3*#max_keyparts)
298
318
  uint8_t min_flag,max_flag,maybe_flag;
299
319
  uint8_t part;                                 // Which key part
300
320
  uint8_t maybe_null;
301
 
  /* 
 
321
  /*
302
322
    Number of children of this element in the RB-tree, plus 1 for this
303
323
    element itself.
304
324
  */
319
339
  SEL_ARG *left,*right;   /* R-B tree children */
320
340
  SEL_ARG *next,*prev;    /* Links for bi-directional interval list */
321
341
  SEL_ARG *parent;        /* R-B tree parent */
322
 
  SEL_ARG *next_key_part; 
 
342
  SEL_ARG *next_key_part;
323
343
  enum leaf_color { BLACK,RED } color;
324
344
  enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
325
345
 
345
365
  inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
346
366
  inline void maybe_smaller() { maybe_flag=1; }
347
367
  /* Return true iff it's a single-point null interval */
348
 
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; } 
 
368
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
349
369
  inline int cmp_min_to_min(SEL_ARG* arg)
350
370
  {
351
371
    return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
372
392
    }
373
393
    else
374
394
    {
375
 
      new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
 
395
      new_min=arg->min_value; flag_min=arg->min_flag;
376
396
    }
377
397
    if (cmp_max_to_max(arg) <= 0)
378
398
    {
482
502
    uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
483
503
                                  range_key, *range_key_flag);
484
504
    *range_key_flag|= key_tree->min_flag;
485
 
    
 
505
 
486
506
    if (key_tree->next_key_part &&
487
507
        key_tree->next_key_part->part == key_tree->part+1 &&
488
508
        !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
556
576
 
557
577
    SYNOPSIS
558
578
      is_singlepoint()
559
 
    
 
579
 
560
580
    DESCRIPTION
561
581
      Check if this SEL_ARG object (not tree) represents a single-point
562
 
      interval, i.e. if it represents a "keypart = const" or 
 
582
      interval, i.e. if it represents a "keypart = const" or
563
583
      "keypart IS NULL".
564
584
 
565
585
    RETURN
569
589
 
570
590
  bool is_singlepoint()
571
591
  {
572
 
    /* 
573
 
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field) 
 
592
    /*
 
593
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
574
594
      flags, and the same for right edge.
575
595
    */
576
596
    if (min_flag || max_flag)
602
622
public:
603
623
  /*
604
624
    Starting an effort to document this field:
605
 
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) => 
 
625
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
606
626
       (type == SEL_TREE::IMPOSSIBLE)
607
627
  */
608
628
  enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
609
629
  SEL_TREE(enum Type type_arg) :type(type_arg) {}
610
630
  SEL_TREE() :type(KEY)
611
631
  {
612
 
    keys_map.clear_all();
 
632
    keys_map.reset();
613
633
    memset(keys, 0, sizeof(keys));
614
634
  }
615
635
  /*
623
643
 
624
644
  /*
625
645
    Possible ways to read rows using index_merge. The list is non-empty only
626
 
    if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
 
646
    if type==KEY. Currently can be non empty only if keys_map.none().
627
647
  */
628
 
  List<SEL_IMERGE> merges;
 
648
  vector<SEL_IMERGE*> merges;
629
649
 
630
650
  /* The members below are filled/used only after get_mm_tree is done */
631
651
  key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
639
659
class RANGE_OPT_PARAM
640
660
{
641
661
public:
642
 
  THD   *thd;   /* Current thread handle */
 
662
  Session       *session;   /* Current thread handle */
643
663
  Table *table; /* Table being analyzed */
644
664
  COND *cond;   /* Used inside get_mm_tree(). */
645
665
  table_map prev_tables;
656
676
    #keys elements are not empty)
657
677
  */
658
678
  uint32_t keys;
659
 
  
660
 
  /* 
 
679
 
 
680
  /*
661
681
    If true, the index descriptions describe real indexes (and it is ok to
662
682
    call field->optimize_range(real_keynr[...], ...).
663
683
    Otherwise index description describes fake indexes.
664
684
  */
665
685
  bool using_real_indexes;
666
 
  
 
686
 
667
687
  bool remove_jump_scans;
668
 
  
 
688
 
669
689
  /*
670
690
    used_key_no -> table_key_no translation table. Only makes sense if
671
691
    using_real_indexes==true
672
692
  */
673
693
  uint32_t real_keynr[MAX_KEY];
674
694
  /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
675
 
  uint32_t alloced_sel_args; 
 
695
  uint32_t alloced_sel_args;
676
696
  bool force_default_mrr;
677
697
};
678
698
 
689
709
  bool quick;                           // Don't calulate possible keys
690
710
 
691
711
  uint32_t fields_bitmap_size;
692
 
  MY_BITMAP needed_fields;    /* bitmask of fields needed by the query */
693
 
  MY_BITMAP tmp_covered_fields;
 
712
  MyBitmap needed_fields;    /* bitmask of fields needed by the query */
 
713
  MyBitmap tmp_covered_fields;
694
714
 
695
715
  key_map *needed_reg;        /* ptr to SQL_SELECT::needed_reg */
696
716
 
722
742
 
723
743
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
724
744
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
725
 
                                  SEL_ARG *tree, bool update_tbl_stats, 
 
745
                                  SEL_ARG *tree, bool update_tbl_stats,
726
746
                                  uint32_t *mrr_flags, uint32_t *bufsize,
727
747
                                  COST_VECT *cost);
728
748
                                  //bool update_tbl_stats);
732
752
*/
733
753
 
734
754
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
735
 
                                     SEL_ARG *key_tree, uint32_t mrr_flags, 
 
755
                                     SEL_ARG *key_tree, uint32_t mrr_flags,
736
756
                                     uint32_t mrr_buf_size, MEM_ROOT *alloc);
737
757
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
738
758
                                       bool index_read_must_be_used,
922
942
 
923
943
 
924
944
/*
925
 
  Perform AND operation on two index_merge lists and store result in *im1.
 
945
  Perform AND operation on two index_merge lists and store result in im1.
926
946
*/
927
947
 
928
 
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
 
948
inline void imerge_list_and_list(vector<SEL_IMERGE*> &im1, vector<SEL_IMERGE*> &im2)
929
949
{
930
 
  im1->concat(im2);
 
950
  im1.insert(im1.end(), im2.begin(), im2.end());
 
951
  im2.clear();
931
952
}
932
953
 
933
954
 
954
975
    other Error, both passed lists are unusable
955
976
*/
956
977
 
957
 
int imerge_list_or_list(RANGE_OPT_PARAM *param,
958
 
                        List<SEL_IMERGE> *im1,
959
 
                        List<SEL_IMERGE> *im2)
 
978
static int imerge_list_or_list(RANGE_OPT_PARAM *param,
 
979
                               vector<SEL_IMERGE*> &im1,
 
980
                               vector<SEL_IMERGE*> &im2)
960
981
{
961
 
  SEL_IMERGE *imerge= im1->head();
962
 
  im1->empty();
963
 
  im1->push_back(imerge);
 
982
  SEL_IMERGE *imerge= im1.front();
 
983
  im1.clear();
 
984
  im1.push_back(imerge);
964
985
 
965
 
  return imerge->or_sel_imerge_with_checks(param, im2->head());
 
986
  return imerge->or_sel_imerge_with_checks(param, im2.front());
966
987
}
967
988
 
968
989
 
970
991
  Perform OR operation on index_merge list and key tree.
971
992
 
972
993
  RETURN
973
 
    0     OK, result is stored in *im1.
974
 
    other Error
 
994
    false   OK, result is stored in im1.
 
995
    true    Error
975
996
*/
976
997
 
977
 
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
978
 
                        List<SEL_IMERGE> *im1,
979
 
                        SEL_TREE *tree)
 
998
static bool imerge_list_or_tree(RANGE_OPT_PARAM *param,
 
999
                                vector<SEL_IMERGE*> &im1,
 
1000
                                SEL_TREE *tree)
980
1001
{
981
 
  SEL_IMERGE *imerge;
982
 
  List_iterator<SEL_IMERGE> it(*im1);
983
 
  while ((imerge= it++))
 
1002
  vector<SEL_IMERGE*>::iterator imerge= im1.begin();
 
1003
 
 
1004
  while (imerge != im1.end())
984
1005
  {
985
 
    if (imerge->or_sel_tree_with_checks(param, tree))
986
 
      it.remove();
 
1006
    if ((*imerge)->or_sel_tree_with_checks(param, tree))
 
1007
      imerge= im1.erase( imerge );
 
1008
    else
 
1009
      ++imerge;
987
1010
  }
988
 
  return im1->is_empty();
 
1011
 
 
1012
  return im1.empty();
989
1013
}
990
1014
 
991
1015
 
1000
1024
           */
1001
1025
 
1002
1026
SQL_SELECT *make_select(Table *head, table_map const_tables,
1003
 
                        table_map read_tables, COND *conds,
 
1027
                        table_map read_tables, COND *conds,
1004
1028
                        bool allow_null_cond,
1005
1029
                        int *error)
1006
1030
{
1009
1033
  *error=0;
1010
1034
 
1011
1035
  if (!conds && !allow_null_cond)
1012
 
    return(0);
 
1036
    return 0;
1013
1037
  if (!(select= new SQL_SELECT))
1014
1038
  {
1015
1039
    *error= 1;                  // out of memory
1016
 
    return(0);          /* purecov: inspected */
 
1040
    return 0;
1017
1041
  }
1018
1042
  select->read_tables=read_tables;
1019
1043
  select->const_tables=const_tables;
1025
1049
    select->file= *head->sort.io_cache;
1026
1050
    select->records=(ha_rows) (select->file.end_of_file/
1027
1051
                               head->file->ref_length);
1028
 
    free(head->sort.io_cache);
 
1052
    delete head->sort.io_cache;
1029
1053
    head->sort.io_cache=0;
1030
1054
  }
1031
1055
  return(select);
1034
1058
 
1035
1059
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1036
1060
{
1037
 
  quick_keys.clear_all(); needed_reg.clear_all();
 
1061
  quick_keys.reset(); 
 
1062
  needed_reg.reset();
1038
1063
  my_b_clear(&file);
1039
1064
}
1040
1065
 
1058
1083
  cleanup();
1059
1084
}
1060
1085
 
 
1086
 
 
1087
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
 
1088
                             ha_rows limit)
 
1089
{
 
1090
  key_map tmp;
 
1091
  tmp.set();
 
1092
  return test_quick_select(session, tmp, 0, limit,
 
1093
                           force_quick_range, false) < 0;
 
1094
}
 
1095
 
 
1096
 
 
1097
bool SQL_SELECT::skip_record()
 
1098
{
 
1099
  return cond ? cond->val_int() == 0 : 0;
 
1100
}
 
1101
 
 
1102
 
1061
1103
QUICK_SELECT_I::QUICK_SELECT_I()
1062
1104
  :max_used_key_length(0),
1063
1105
   used_key_parts(0)
1064
1106
{}
1065
1107
 
1066
 
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, Table *table, uint32_t key_nr,
 
1108
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1067
1109
                                       bool no_alloc, MEM_ROOT *parent_alloc,
1068
1110
                                       bool *create_error)
1069
1111
  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1077
1119
  key_part_info= head->key_info[index].key_part;
1078
1120
  my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1079
1121
 
1080
 
  /* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1081
 
  mrr_buf_size= thd->variables.read_rnd_buff_size;
 
1122
  /* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
 
1123
  mrr_buf_size= session->variables.read_rnd_buff_size;
1082
1124
  mrr_buf_desc= NULL;
1083
1125
 
1084
1126
  if (!no_alloc && !parent_alloc)
1085
1127
  {
1086
1128
    // Allocates everything through the internal memroot
1087
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1088
 
    thd->mem_root= &alloc;
 
1129
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1130
    session->mem_root= &alloc;
1089
1131
  }
1090
1132
  else
1091
1133
    memset(&alloc, 0, sizeof(alloc));
1095
1137
  save_write_set= head->write_set;
1096
1138
 
1097
1139
  /* 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))))
 
1140
  if (! (bitmap= (my_bitmap_map*) malloc(head->s->column_bitmap_size)))
1100
1141
  {
1101
 
    column_bitmap.bitmap= 0;
 
1142
    column_bitmap.setBitmap(NULL);
1102
1143
    *create_error= 1;
1103
1144
  }
1104
1145
  else
1105
 
    bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1106
 
  return;
 
1146
  {
 
1147
    column_bitmap.init(bitmap, head->s->fields);
 
1148
  }
1107
1149
}
1108
1150
 
1109
1151
 
1127
1169
  if (!dont_free)
1128
1170
  {
1129
1171
    /* file is NULL for CPK scan on covering ROR-intersection */
1130
 
    if (file) 
 
1172
    if (file)
1131
1173
    {
1132
1174
      range_end();
1133
1175
      if (head->key_read)
1137
1179
      }
1138
1180
      if (free_file)
1139
1181
      {
1140
 
        file->ha_external_lock(current_thd, F_UNLCK);
 
1182
        file->ha_external_lock(current_session, F_UNLCK);
1141
1183
        file->close();
1142
1184
        delete file;
1143
1185
      }
1144
1186
    }
1145
1187
    delete_dynamic(&ranges); /* ranges are allocated in alloc */
1146
1188
    free_root(&alloc,MYF(0));
1147
 
    free((char*) column_bitmap.bitmap);
1148
1189
  }
1149
1190
  head->column_bitmaps_set(save_read_set, save_write_set);
 
1191
  assert(mrr_buf_desc == NULL);
1150
1192
  if (mrr_buf_desc)
1151
1193
    free(mrr_buf_desc);
1152
 
  return;
1153
1194
}
1154
1195
 
1155
1196
 
1156
 
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
 
1197
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1157
1198
                                                   Table *table)
1158
 
  :pk_quick_select(NULL), thd(thd_param)
 
1199
  :pk_quick_select(NULL), session(session_param)
1159
1200
{
1160
1201
  index= MAX_KEY;
1161
1202
  head= table;
1162
1203
  memset(&read_record, 0, sizeof(read_record));
1163
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1204
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1164
1205
  return;
1165
1206
}
1166
1207
 
1167
1208
int QUICK_INDEX_MERGE_SELECT::init()
1168
1209
{
1169
 
  return(0);
 
1210
  return 0;
1170
1211
}
1171
1212
 
1172
1213
int QUICK_INDEX_MERGE_SELECT::reset()
1203
1244
}
1204
1245
 
1205
1246
 
1206
 
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
 
1247
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1207
1248
                                                       Table *table,
1208
1249
                                                       bool retrieve_full_rows,
1209
1250
                                                       MEM_ROOT *parent_alloc)
1210
 
  : cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
 
1251
  : cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1211
1252
    scans_inited(false)
1212
1253
{
1213
1254
  index= MAX_KEY;
1214
1255
  head= table;
1215
1256
  record= head->record[0];
1216
1257
  if (!parent_alloc)
1217
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1258
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1218
1259
  else
1219
1260
    memset(&alloc, 0, sizeof(MEM_ROOT));
1220
1261
  last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1264
1305
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1265
1306
{
1266
1307
  handler *save_file= file, *org_file;
1267
 
  THD *thd;
 
1308
  Session *session;
1268
1309
 
1269
1310
  in_ror_merged_scan= 1;
1270
1311
  if (reuse_handler)
1271
1312
  {
1272
1313
    if (init() || reset())
1273
1314
    {
1274
 
      return(1);
 
1315
      return 0;
1275
1316
    }
1276
1317
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1277
1318
    goto end;
1281
1322
  if (free_file)
1282
1323
  {
1283
1324
    /* already have own 'handler' object. */
1284
 
    return(0);
 
1325
    return 0;
1285
1326
  }
1286
1327
 
1287
 
  thd= head->in_use;
1288
 
  if (!(file= head->file->clone(thd->mem_root)))
 
1328
  session= head->in_use;
 
1329
  if (!(file= head->file->clone(session->mem_root)))
1289
1330
  {
1290
 
    /* 
 
1331
    /*
1291
1332
      Manually set the error flag. Note: there seems to be quite a few
1292
1333
      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. 
 
1334
      sending no response to a query. ATM those are not real errors because
 
1335
      the storage engine calls in question happen to never fail with the
 
1336
      existing storage engines.
1296
1337
    */
1297
 
    my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
 
1338
    my_error(ER_OUT_OF_RESOURCES, MYF(0));
1298
1339
    /* Caller will free the memory */
1299
 
    goto failure;  /* purecov: inspected */
 
1340
    goto failure;
1300
1341
  }
1301
1342
 
1302
1343
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1303
1344
 
1304
 
  if (file->ha_external_lock(thd, F_RDLCK))
 
1345
  if (file->ha_external_lock(session, F_RDLCK))
1305
1346
    goto failure;
1306
1347
 
1307
1348
  if (init() || reset())
1308
1349
  {
1309
 
    file->ha_external_lock(thd, F_UNLCK);
 
1350
    file->ha_external_lock(session, F_UNLCK);
1310
1351
    file->close();
1311
1352
    goto failure;
1312
1353
  }
1330
1371
  }
1331
1372
  head->prepare_for_position();
1332
1373
  head->file= org_file;
1333
 
  bitmap_copy(&column_bitmap, head->read_set);
 
1374
  column_bitmap= *head->read_set;
1334
1375
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1335
1376
 
1336
 
  return(0);
 
1377
  return 0;
1337
1378
 
1338
1379
failure:
1339
1380
  head->column_bitmaps_set(save_read_set, save_write_set);
1340
1381
  delete file;
1341
1382
  file= save_file;
1342
 
  return(1);
 
1383
  return 0;
 
1384
}
 
1385
 
 
1386
 
 
1387
void QUICK_RANGE_SELECT::save_last_pos()
 
1388
{
 
1389
  file->position(record);
1343
1390
}
1344
1391
 
1345
1392
 
1368
1415
      selects.
1369
1416
    */
1370
1417
    if (quick->init_ror_merged_scan(true))
1371
 
      return(1);
 
1418
      return 0;
1372
1419
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1373
1420
  }
1374
1421
  while ((quick= quick_it++))
1375
1422
  {
1376
1423
    if (quick->init_ror_merged_scan(false))
1377
 
      return(1);
 
1424
      return 0;
1378
1425
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1379
1426
    /* All merged scans share the same record buffer in intersection. */
1380
1427
    quick->record= head->record[0];
1382
1429
 
1383
1430
  if (need_to_fetch_row && head->file->ha_rnd_init(1))
1384
1431
  {
1385
 
    return(1);
 
1432
    return 0;
1386
1433
  }
1387
 
  return(0);
 
1434
  return 0;
1388
1435
}
1389
1436
 
1390
1437
 
1400
1447
int QUICK_ROR_INTERSECT_SELECT::reset()
1401
1448
{
1402
1449
  if (!scans_inited && init_ror_merged_scan(true))
1403
 
    return(1);
 
1450
    return 0;
1404
1451
  scans_inited= true;
1405
1452
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1406
1453
  QUICK_RANGE_SELECT *quick;
1407
1454
  while ((quick= it++))
1408
1455
    quick->reset();
1409
 
  return(0);
 
1456
  return 0;
1410
1457
}
1411
1458
 
1412
1459
 
1442
1489
}
1443
1490
 
1444
1491
 
1445
 
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
 
1492
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1446
1493
                                               Table *table)
1447
 
  : thd(thd_param), scans_inited(false)
 
1494
  : session(session_param), scans_inited(false)
1448
1495
{
1449
1496
  index= MAX_KEY;
1450
1497
  head= table;
1451
1498
  rowid_length= table->file->ref_length;
1452
1499
  record= head->record[0];
1453
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1454
 
  thd_param->mem_root= &alloc;
 
1500
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1501
  session_param->mem_root= &alloc;
1455
1502
}
1456
1503
 
 
1504
/*
 
1505
 * Function object that is used as the comparison function
 
1506
 * for the priority queue in the QUICK_ROR_UNION_SELECT
 
1507
 * class.
 
1508
 */
 
1509
class compare_functor
 
1510
{
 
1511
  QUICK_ROR_UNION_SELECT *self;
 
1512
  public:
 
1513
  compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
 
1514
    : self(in_arg) { }
 
1515
  inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
 
1516
  {
 
1517
    int val= self->head->file->cmp_ref(i->last_rowid,
 
1518
                                       j->last_rowid);
 
1519
    return (val >= 0);
 
1520
  }
 
1521
};
1457
1522
 
1458
1523
/*
1459
1524
  Do post-constructor initialization.
1467
1532
 
1468
1533
int QUICK_ROR_UNION_SELECT::init()
1469
1534
{
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
 
 
 
1535
  queue= 
 
1536
    new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
1478
1537
  if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1479
 
    return(1);
 
1538
    return 0;
1480
1539
  prev_rowid= cur_rowid + head->file->ref_length;
1481
 
  return(0);
1482
 
}
1483
 
 
1484
 
 
1485
 
/*
1486
 
  Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1487
 
  queue.
1488
 
 
1489
 
  SYNPOSIS
1490
 
    QUICK_ROR_UNION_SELECT::queue_cmp()
1491
 
      arg   Pointer to QUICK_ROR_UNION_SELECT
1492
 
      val1  First merged select
1493
 
      val2  Second merged select
1494
 
*/
1495
 
 
1496
 
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1497
 
{
1498
 
  QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1499
 
  return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1500
 
                                   ((QUICK_SELECT_I*)val2)->last_rowid);
 
1540
  return 0;
1501
1541
}
1502
1542
 
1503
1543
 
1522
1562
    while ((quick= it++))
1523
1563
    {
1524
1564
      if (quick->init_ror_merged_scan(false))
1525
 
        return(1);
 
1565
        return 0;
1526
1566
    }
1527
1567
    scans_inited= true;
1528
1568
  }
1529
 
  queue_remove_all(&queue);
 
1569
  while (!queue->empty())
 
1570
    queue->pop();
1530
1571
  /*
1531
1572
    Initialize scans for merged quick selects and put all merged quick
1532
1573
    selects into the queue.
1535
1576
  while ((quick= it++))
1536
1577
  {
1537
1578
    if (quick->reset())
1538
 
      return(1);
 
1579
      return 0;
1539
1580
    if ((error= quick->get_next()))
1540
1581
    {
1541
1582
      if (error == HA_ERR_END_OF_FILE)
1543
1584
      return(error);
1544
1585
    }
1545
1586
    quick->save_last_pos();
1546
 
    queue_insert(&queue, (unsigned char*)quick);
 
1587
    queue->push(quick);
1547
1588
  }
1548
1589
 
1549
1590
  if (head->file->ha_rnd_init(1))
1550
1591
  {
1551
 
    return(1);
 
1592
    return 0;
1552
1593
  }
1553
1594
 
1554
 
  return(0);
 
1595
  return 0;
1555
1596
}
1556
1597
 
1557
1598
 
1563
1604
 
1564
1605
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1565
1606
{
1566
 
  delete_queue(&queue);
 
1607
  while (!queue->empty())
 
1608
    queue->pop();
 
1609
  delete queue;
1567
1610
  quick_selects.delete_elements();
1568
1611
  if (head->file->inited != handler::NONE)
1569
1612
    head->file->ha_rnd_end();
1623
1666
  left=right= &null_element;
1624
1667
}
1625
1668
 
1626
 
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, 
 
1669
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1627
1670
                        SEL_ARG **next_arg)
1628
1671
{
1629
1672
  SEL_ARG *tmp;
1759
1802
      limit  Number of records that will be retrieved
1760
1803
 
1761
1804
  DESCRIPTION
1762
 
    Find the best index that allows to retrieve first #limit records in the 
 
1805
    Find the best index that allows to retrieve first #limit records in the
1763
1806
    given order cheaper then one would retrieve them using full table scan.
1764
1807
 
1765
1808
  IMPLEMENTATION
1783
1826
  uint32_t idx;
1784
1827
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
1785
1828
  order_st *ord;
1786
 
  
 
1829
 
1787
1830
  for (ord= order; ord; ord= ord->next)
1788
1831
    if (!ord->asc)
1789
1832
      return MAX_KEY;
1790
1833
 
1791
1834
  for (idx= 0; idx < table->s->keys; idx++)
1792
1835
  {
1793
 
    if (!(table->keys_in_use_for_query.is_set(idx)))
 
1836
    if (!(table->keys_in_use_for_query.test(idx)))
1794
1837
      continue;
1795
1838
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
1796
1839
    uint32_t n_parts=  table->key_info[idx].key_parts;
1797
1840
    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 
 
1841
 
 
1842
    /*
 
1843
      The below check is sufficient considering we now have either BTREE
 
1844
      indexes (records are returned in order for any index prefix) or HASH
1802
1845
      indexes (records are not returned in order for any index prefix).
1803
1846
    */
1804
1847
    if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
1810
1853
           ((Item_field*)item)->field->eq(keyinfo[partno].field)))
1811
1854
        break;
1812
1855
    }
1813
 
    
 
1856
 
1814
1857
    if (!ord && table->key_info[idx].key_length < match_key_len)
1815
1858
    {
1816
 
      /* 
 
1859
      /*
1817
1860
        Ok, the ordering is compatible and this key is shorter then
1818
1861
        previous match (we want shorter keys as we'll have to read fewer
1819
1862
        index pages for the same number of records)
1825
1868
 
1826
1869
  if (match_key != MAX_KEY)
1827
1870
  {
1828
 
    /* 
1829
 
      Found an index that allows records to be retrieved in the requested 
 
1871
    /*
 
1872
      Found an index that allows records to be retrieved in the requested
1830
1873
      order. Now we'll check if using the index is cheaper then doing a table
1831
1874
      scan.
1832
1875
    */
1881
1924
 
1882
1925
  /* Table read plans are allocated on MEM_ROOT and are never deleted */
1883
1926
  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)))
 
1927
  { return (void*) alloc_root(mem_root, (uint32_t) size); }
 
1928
  static void operator delete(void *, size_t)
1887
1929
    { TRASH(ptr, size); }
1888
 
  static void operator delete(void *ptr __attribute__((unused)),
1889
 
                              MEM_ROOT *mem_root __attribute__((unused)))
 
1930
  static void operator delete(void *, MEM_ROOT *)
1890
1931
    { /* Never called */ }
1891
1932
  virtual ~TABLE_READ_PLAN() {}               /* Remove gcc warning */
1892
1933
 
1909
1950
public:
1910
1951
  SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1911
1952
  uint32_t     key_idx; /* key number in PARAM::key */
1912
 
  uint32_t     mrr_flags; 
 
1953
  uint32_t     mrr_flags;
1913
1954
  uint32_t     mrr_buf_size;
1914
1955
 
1915
1956
  TRP_RANGE(SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1917
1958
  {}
1918
1959
  virtual ~TRP_RANGE() {}                     /* Remove gcc warning */
1919
1960
 
1920
 
  QUICK_SELECT_I *make_quick(PARAM *param,
1921
 
                             bool retrieve_full_rows __attribute__((unused)),
1922
 
                             MEM_ROOT *parent_alloc)
 
1961
  QUICK_SELECT_I *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1923
1962
  {
1924
1963
    QUICK_RANGE_SELECT *quick;
1925
1964
    if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
1928
1967
      quick->records= records;
1929
1968
      quick->read_time= read_cost;
1930
1969
    }
1931
 
    return(quick);
 
1970
    return quick;
1932
1971
  }
1933
1972
};
1934
1973
 
1989
2028
 
1990
2029
 
1991
2030
/*
1992
 
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan. 
 
2031
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
1993
2032
*/
1994
2033
 
1995
2034
class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN
2056
2095
  Table *table= param->table;
2057
2096
  my_bitmap_map *tmp;
2058
2097
  uint32_t pk;
2059
 
  param->tmp_covered_fields.bitmap= 0;
 
2098
  param->tmp_covered_fields.setBitmap(0);
2060
2099
  param->fields_bitmap_size= table->s->column_bitmap_size;
2061
2100
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
2062
2101
                                  param->fields_bitmap_size)) ||
2063
 
      bitmap_init(&param->needed_fields, tmp, table->s->fields, false))
 
2102
      param->needed_fields.init(tmp, table->s->fields))
2064
2103
    return 1;
2065
2104
 
2066
 
  bitmap_copy(&param->needed_fields, table->read_set);
 
2105
  param->needed_fields= *table->read_set;
2067
2106
  bitmap_union(&param->needed_fields, table->write_set);
2068
2107
 
2069
2108
  pk= param->table->s->primary_key;
2074
2113
    KEY_PART_INFO *key_part_end= key_part +
2075
2114
                                 param->table->key_info[pk].key_parts;
2076
2115
    for (;key_part != key_part_end; ++key_part)
2077
 
      bitmap_clear_bit(&param->needed_fields, key_part->fieldnr-1);
 
2116
      param->needed_fields.clearBit(key_part->fieldnr-1);
2078
2117
  }
2079
2118
  return 0;
2080
2119
}
2085
2124
 
2086
2125
  SYNOPSIS
2087
2126
    SQL_SELECT::test_quick_select()
2088
 
      thd               Current thread
 
2127
      session               Current thread
2089
2128
      keys_to_use       Keys to use for range retrieval
2090
2129
      prev_tables       Tables assumed to be already read when the scan is
2091
2130
                        performed (but not read at the moment of this call)
2105
2144
 
2106
2145
  IMPLEMENTATION
2107
2146
    quick_condition_rows value is obtained as follows:
2108
 
      
 
2147
 
2109
2148
      It is a minimum of E(#output rows) for all considered table access
2110
2149
      methods (range and index_merge accesses over various indexes).
2111
 
    
 
2150
 
2112
2151
    The obtained value is not a true E(#rows that satisfy table condition)
2113
2152
    but rather a pessimistic estimate. To obtain a true E(#...) one would
2114
2153
    need to combine estimates of various access methods, taking into account
2115
2154
    correlations between sets of rows they will return.
2116
 
    
 
2155
 
2117
2156
    For example, if values of tbl.key1 and tbl.key2 are independent (a right
2118
2157
    assumption if we have no information about their correlation) then the
2119
2158
    correct estimate will be:
2120
 
    
2121
 
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) = 
 
2159
 
 
2160
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
2122
2161
      = E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)
2123
2162
 
2124
 
    which is smaller than 
2125
 
      
 
2163
    which is smaller than
 
2164
 
2126
2165
       MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))
2127
2166
 
2128
2167
    which is currently produced.
2129
2168
 
2130
2169
  TODO
2131
2170
   * 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 
 
2171
     estimate to true E(#rows that satisfy table condition).
 
2172
     (we can re-use some of E(#rows) calcuation code from index_merge/intersection
2134
2173
      for this)
2135
 
   
 
2174
 
2136
2175
   * Check if this function really needs to modify keys_to_use, and change the
2137
2176
     code to pass it by reference if it doesn't.
2138
2177
 
2146
2185
    1 if found usable ranges and quick select has been successfully created.
2147
2186
*/
2148
2187
 
2149
 
int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
 
2188
int SQL_SELECT::test_quick_select(Session *session, key_map keys_to_use,
2150
2189
                                  table_map prev_tables,
2151
 
                                  ha_rows limit, bool force_quick_range, 
 
2190
                                  ha_rows limit, bool force_quick_range,
2152
2191
                                  bool ordered_output)
2153
2192
{
2154
2193
  uint32_t idx;
2155
2194
  double scan_time;
2156
2195
  delete quick;
2157
2196
  quick=0;
2158
 
  needed_reg.clear_all();
2159
 
  quick_keys.clear_all();
2160
 
  if (keys_to_use.is_clear_all())
2161
 
    return(0);
 
2197
  needed_reg.reset();
 
2198
  quick_keys.reset();
 
2199
  if (keys_to_use.none())
 
2200
    return 0;
2162
2201
  records= head->file->stats.records;
2163
2202
  if (!records)
2164
 
    records++;                                  /* purecov: inspected */
 
2203
    records++;
2165
2204
  scan_time= (double) records / TIME_FOR_COMPARE + 1;
2166
2205
  read_time= (double) head->file->scan_time() + scan_time + 1.1;
2167
2206
  if (head->force_index)
2169
2208
  if (limit < records)
2170
2209
    read_time= (double) records + scan_time + 1; // Force to use index
2171
2210
  else if (read_time <= 2.0 && !force_quick_range)
2172
 
    return(0);                          /* No need for quick select */
 
2211
    return 0;                           /* No need for quick select */
2173
2212
 
2174
 
  keys_to_use.intersect(head->keys_in_use_for_query);
2175
 
  if (!keys_to_use.is_clear_all())
 
2213
  keys_to_use&= head->keys_in_use_for_query;
 
2214
  if (keys_to_use.any())
2176
2215
  {
2177
2216
    MEM_ROOT alloc;
2178
2217
    SEL_TREE *tree= NULL;
2180
2219
    KEY *key_info;
2181
2220
    PARAM param;
2182
2221
 
2183
 
    if (check_stack_overrun(thd, 2*STACK_MIN_SIZE, NULL))
2184
 
      return(0);                           // Fatal error flag is set
 
2222
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
 
2223
      return 0;                           // Fatal error flag is set
2185
2224
 
2186
2225
    /* set up parameter that is passed to all functions */
2187
 
    param.thd= thd;
 
2226
    param.session= session;
2188
2227
    param.baseflag= head->file->ha_table_flags();
2189
 
    param.prev_tables=prev_tables | const_tables;
2190
 
    param.read_tables=read_tables;
 
2228
    param.prev_tables= prev_tables | const_tables;
 
2229
    param.read_tables= read_tables;
2191
2230
    param.current_table= head->map;
2192
2231
    param.table=head;
2193
2232
    param.keys=0;
2194
2233
    param.mem_root= &alloc;
2195
 
    param.old_root= thd->mem_root;
 
2234
    param.old_root= session->mem_root;
2196
2235
    param.needed_reg= &needed_reg;
2197
2236
    param.imerge_cost_buff_size= 0;
2198
2237
    param.using_real_indexes= true;
2199
2238
    param.remove_jump_scans= true;
2200
2239
    param.force_default_mrr= ordered_output;
2201
2240
 
2202
 
    thd->no_errors=1;                           // Don't warn about NULL
2203
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
2241
    session->no_errors=1;                               // Don't warn about NULL
 
2242
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
2204
2243
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
2205
2244
                                                  sizeof(KEY_PART)*
2206
2245
                                                  head->s->key_parts)) ||
2207
2246
        fill_used_fields_bitmap(&param))
2208
2247
    {
2209
 
      thd->no_errors=0;
 
2248
      session->no_errors=0;
2210
2249
      free_root(&alloc,MYF(0));                 // Return memory & allocator
2211
 
      return(0);                                // Can't use range
 
2250
      return 0;                         // Can't use range
2212
2251
    }
2213
2252
    key_parts= param.key_parts;
2214
 
    thd->mem_root= &alloc;
 
2253
    session->mem_root= &alloc;
2215
2254
 
2216
2255
    /*
2217
2256
      Make an array with description of all key parts of all table keys.
2221
2260
    for (idx=0 ; idx < head->s->keys ; idx++, key_info++)
2222
2261
    {
2223
2262
      KEY_PART_INFO *key_part_info;
2224
 
      if (!keys_to_use.is_set(idx))
 
2263
      if (! keys_to_use.test(idx))
2225
2264
        continue;
2226
2265
 
2227
2266
      param.key[param.keys]=key_parts;
2228
2267
      key_part_info= key_info->key_part;
2229
 
      for (uint32_t part=0 ; part < key_info->key_parts ;
2230
 
           part++, key_parts++, key_part_info++)
 
2268
      for (uint32_t part=0;
 
2269
           part < key_info->key_parts;
 
2270
           part++, key_parts++, key_part_info++)
2231
2271
      {
2232
 
        key_parts->key=          param.keys;
2233
 
        key_parts->part=         part;
2234
 
        key_parts->length=       key_part_info->length;
2235
 
        key_parts->store_length= key_part_info->store_length;
2236
 
        key_parts->field=        key_part_info->field;
2237
 
        key_parts->null_bit=     key_part_info->null_bit;
2238
 
        key_parts->image_type =  Field::itRAW;
 
2272
        key_parts->key= param.keys;
 
2273
        key_parts->part= part;
 
2274
        key_parts->length= key_part_info->length;
 
2275
        key_parts->store_length= key_part_info->store_length;
 
2276
        key_parts->field= key_part_info->field;
 
2277
        key_parts->null_bit= key_part_info->null_bit;
2239
2278
        /* Only HA_PART_KEY_SEG is used */
2240
 
        key_parts->flag=         (uint8_t) key_part_info->key_part_flag;
 
2279
        key_parts->flag= (uint8_t) key_part_info->key_part_flag;
2241
2280
      }
2242
2281
      param.real_keynr[param.keys++]=idx;
2243
2282
    }
2245
2284
    param.alloced_sel_args= 0;
2246
2285
 
2247
2286
    /* Calculate cost of full index read for the shortest covering index */
2248
 
    if (!head->covering_keys.is_clear_all())
 
2287
    if (!head->covering_keys.none())
2249
2288
    {
2250
2289
      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, 
 
2290
      double key_read_time=
 
2291
        param.table->file->index_only_read_time(key_for_use,
2253
2292
                                                rows2double(records)) +
2254
2293
        (double) records / TIME_FOR_COMPARE;
2255
2294
      if (key_read_time < read_time)
2286
2325
    group_trp= get_best_group_min_max(&param, tree);
2287
2326
    if (group_trp)
2288
2327
    {
2289
 
      param.table->quick_condition_rows= cmin(group_trp->records,
 
2328
      param.table->quick_condition_rows= min(group_trp->records,
2290
2329
                                             head->file->stats.records);
2291
2330
      if (group_trp->read_cost < best_read_time)
2292
2331
      {
2301
2340
        It is possible to use a range-based quick select (but it might be
2302
2341
        slower than 'all' table scan).
2303
2342
      */
2304
 
      if (tree->merges.is_empty())
 
2343
      if (tree->merges.empty() == true)
2305
2344
      {
2306
2345
        TRP_RANGE         *range_trp;
2307
2346
        TRP_ROR_INTERSECT *rori_trp;
2320
2359
          objects are not allowed so don't use ROR-intersection for
2321
2360
          table deletes.
2322
2361
        */
2323
 
        if ((thd->lex->sql_command != SQLCOM_DELETE))
 
2362
        if ((session->lex->sql_command != SQLCOM_DELETE))
2324
2363
        {
2325
2364
          /*
2326
2365
            Get best non-covering ROR-intersection plan and prepare data for
2345
2384
      else
2346
2385
      {
2347
2386
        /* Try creating index_merge/ROR-union scan. */
2348
 
        SEL_IMERGE *imerge;
2349
2387
        TABLE_READ_PLAN *best_conj_trp= NULL, *new_conj_trp;
2350
 
        List_iterator_fast<SEL_IMERGE> it(tree->merges);
2351
 
        while ((imerge= it++))
 
2388
        vector<SEL_IMERGE*>::iterator imerge= tree->merges.begin();
 
2389
        while (imerge != tree->merges.end())
2352
2390
        {
2353
 
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
 
2391
          new_conj_trp= get_best_disjunct_quick(&param, *imerge, best_read_time);
2354
2392
          if (new_conj_trp)
2355
 
            set_if_smaller(param.table->quick_condition_rows, 
 
2393
            set_if_smaller(param.table->quick_condition_rows,
2356
2394
                           new_conj_trp->records);
 
2395
 
2357
2396
          if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
2358
2397
                                 best_conj_trp->read_cost))
2359
2398
            best_conj_trp= new_conj_trp;
 
2399
 
 
2400
          ++imerge;
2360
2401
        }
2361
2402
        if (best_conj_trp)
2362
2403
          best_trp= best_conj_trp;
2363
2404
      }
2364
2405
    }
2365
2406
 
2366
 
    thd->mem_root= param.old_root;
 
2407
    session->mem_root= param.old_root;
2367
2408
 
2368
2409
    /* If we got a read plan, create a quick select from it. */
2369
2410
    if (best_trp)
2378
2419
 
2379
2420
  free_mem:
2380
2421
    free_root(&alloc,MYF(0));                   // Return memory & allocator
2381
 
    thd->mem_root= param.old_root;
2382
 
    thd->no_errors=0;
 
2422
    session->mem_root= param.old_root;
 
2423
    session->no_errors=0;
2383
2424
  }
2384
2425
 
2385
2426
  /*
2481
2522
  if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
2482
2523
                                             sizeof(TRP_RANGE*)*
2483
2524
                                             n_child_scans)))
2484
 
    return(NULL);
 
2525
    return NULL;
2485
2526
  /*
2486
2527
    Collect best 'range' scan for each of disjuncts, and, while doing so,
2487
2528
    analyze possibility of ROR scans. Also calculate some values needed by
2526
2567
      Bail out if it is obvious that both index_merge and ROR-union will be
2527
2568
      more expensive
2528
2569
    */
2529
 
    return(NULL);
 
2570
    return NULL;
2530
2571
  }
2531
2572
  if (all_scans_rors)
2532
2573
  {
2545
2586
  /* Calculate cost(rowid_to_row_scan) */
2546
2587
  {
2547
2588
    COST_VECT sweep_cost;
2548
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2589
    JOIN *join= param->session->lex->select_lex.join;
2549
2590
    bool is_interrupted= test(join && join->tables == 1);
2550
2591
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
2551
2592
                        &sweep_cost);
2558
2599
  unique_calc_buff_size=
2559
2600
    Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
2560
2601
                                    param->table->file->ref_length,
2561
 
                                    param->thd->variables.sortbuff_size);
 
2602
                                    param->session->variables.sortbuff_size);
2562
2603
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
2563
2604
  {
2564
2605
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
2565
2606
                                                     unique_calc_buff_size)))
2566
 
      return(NULL);
 
2607
      return NULL;
2567
2608
    param->imerge_cost_buff_size= unique_calc_buff_size;
2568
2609
  }
2569
2610
 
2570
2611
  imerge_cost +=
2571
 
    Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records,
 
2612
    Unique::get_use_cost(param->imerge_cost_buff, (uint32_t)non_cpk_scan_records,
2572
2613
                         param->table->file->ref_length,
2573
 
                         param->thd->variables.sortbuff_size);
 
2614
                         param->session->variables.sortbuff_size);
2574
2615
  if (imerge_cost < read_time)
2575
2616
  {
2576
2617
    if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE))
2577
2618
    {
2578
2619
      imerge_trp->read_cost= imerge_cost;
2579
2620
      imerge_trp->records= non_cpk_scan_records + cpk_scan_records;
2580
 
      imerge_trp->records= cmin(imerge_trp->records,
 
2621
      imerge_trp->records= min(imerge_trp->records,
2581
2622
                               param->table->file->stats.records);
2582
2623
      imerge_trp->range_scans= range_scans;
2583
2624
      imerge_trp->range_scans_end= range_scans + n_child_scans;
2586
2627
  }
2587
2628
 
2588
2629
build_ror_index_merge:
2589
 
  if (!all_scans_ror_able || param->thd->lex->sql_command == SQLCOM_DELETE)
 
2630
  if (!all_scans_ror_able || param->session->lex->sql_command == SQLCOM_DELETE)
2590
2631
    return(imerge_trp);
2591
2632
 
2592
2633
  /* Ok, it is possible to build a ROR-union, try it. */
2661
2702
  double roru_total_cost;
2662
2703
  {
2663
2704
    COST_VECT sweep_cost;
2664
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2705
    JOIN *join= param->session->lex->select_lex.join;
2665
2706
    bool is_interrupted= test(join && join->tables == 1);
2666
2707
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
2667
2708
                        &sweep_cost);
2697
2738
  SEL_ARG   *sel_arg;
2698
2739
 
2699
2740
  /* Fields used in the query and covered by this ROR scan. */
2700
 
  MY_BITMAP covered_fields;
 
2741
  MyBitmap covered_fields;
2701
2742
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
2702
2743
  int       key_rec_length; /* length of key record (including rowid) */
2703
2744
 
2731
2772
{
2732
2773
  ROR_SCAN_INFO *ror_scan;
2733
2774
  my_bitmap_map *bitmap_buf;
 
2775
 
2734
2776
  uint32_t keynr;
2735
2777
 
2736
2778
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
2737
2779
                                             sizeof(ROR_SCAN_INFO))))
2738
 
    return(NULL);
 
2780
    return NULL;
2739
2781
 
2740
2782
  ror_scan->idx= idx;
2741
2783
  ror_scan->keynr= keynr= param->real_keynr[idx];
2746
2788
 
2747
2789
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
2748
2790
                                                param->fields_bitmap_size)))
2749
 
    return(NULL);
 
2791
    return NULL;
2750
2792
 
2751
 
  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);
 
2793
  if (ror_scan->covered_fields.init(bitmap_buf,
 
2794
                                    param->table->s->fields))
 
2795
    return NULL;
 
2796
  ror_scan->covered_fields.clearAll();
2755
2797
 
2756
2798
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2757
2799
  KEY_PART_INFO *key_part_end= key_part +
2758
2800
                               param->table->key_info[keynr].key_parts;
2759
2801
  for (;key_part != key_part_end; ++key_part)
2760
2802
  {
2761
 
    if (bitmap_is_set(&param->needed_fields, key_part->fieldnr-1))
2762
 
      bitmap_set_bit(&ror_scan->covered_fields, key_part->fieldnr-1);
 
2803
    if (param->needed_fields.isBitSet(key_part->fieldnr-1))
 
2804
      ror_scan->covered_fields.setBit(key_part->fieldnr-1);
2763
2805
  }
2764
2806
  double rows= rows2double(param->table->quick_rows[ror_scan->keynr]);
2765
2807
  ror_scan->index_read_cost=
2827
2869
typedef struct
2828
2870
{
2829
2871
  const PARAM *param;
2830
 
  MY_BITMAP covered_fields; /* union of fields covered by all scans */
 
2872
  MyBitmap covered_fields; /* union of fields covered by all scans */
2831
2873
  /*
2832
2874
    Fraction of table records that satisfies conditions of all scans.
2833
2875
    This is the number of full records that will be retrieved if a
2867
2909
  if (!(buf= (my_bitmap_map*) alloc_root(param->mem_root,
2868
2910
                                         param->fields_bitmap_size)))
2869
2911
    return NULL;
2870
 
  if (bitmap_init(&info->covered_fields, buf, param->table->s->fields,
2871
 
                  false))
 
2912
  if (info->covered_fields.init(buf, param->table->s->fields))
2872
2913
    return NULL;
2873
2914
  info->is_covering= false;
2874
2915
  info->index_scan_costs= 0.0;
2875
2916
  info->index_records= 0;
2876
2917
  info->out_rows= (double) param->table->file->stats.records;
2877
 
  bitmap_clear_all(&info->covered_fields);
 
2918
  info->covered_fields.clearAll();
2878
2919
  return info;
2879
2920
}
2880
2921
 
2881
 
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
 
2922
static void ror_intersect_cpy(ROR_INTERSECT_INFO *dst,
 
2923
                              const ROR_INTERSECT_INFO *src)
2882
2924
{
2883
2925
  dst->param= src->param;
2884
 
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap, 
2885
 
         no_bytes_in_map(&src->covered_fields));
 
2926
  dst->covered_fields= src->covered_fields;
2886
2927
  dst->out_rows= src->out_rows;
2887
2928
  dst->is_covering= src->is_covering;
2888
2929
  dst->index_records= src->index_records;
2896
2937
 
2897
2938
  SYNOPSIS
2898
2939
    ror_scan_selectivity()
2899
 
      info  ROR-interection 
 
2940
      info  ROR-interection
2900
2941
      scan  ROR scan
2901
 
      
 
2942
 
2902
2943
  NOTES
2903
2944
    Suppose we have a condition on several keys
2904
2945
    cond=k_11=c_11 AND k_12=c_12 AND ...  // parts of first key
2981
3022
    Selectivity of given ROR scan.
2982
3023
*/
2983
3024
 
2984
 
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info, 
 
3025
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
2985
3026
                                   const ROR_SCAN_INFO *scan)
2986
3027
{
2987
3028
  double selectivity_mult= 1.0;
2991
3032
  SEL_ARG *sel_arg, *tuple_arg= NULL;
2992
3033
  key_part_map keypart_map= 0;
2993
3034
  bool cur_covered;
2994
 
  bool prev_covered= test(bitmap_is_set(&info->covered_fields,
2995
 
                                        key_part->fieldnr-1));
 
3035
  bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
2996
3036
  key_range min_range;
2997
3037
  key_range max_range;
2998
3038
  min_range.key= key_val;
3004
3044
  for (sel_arg= scan->sel_arg; sel_arg;
3005
3045
       sel_arg= sel_arg->next_key_part)
3006
3046
  {
3007
 
    cur_covered= test(bitmap_is_set(&info->covered_fields,
3008
 
                                    key_part[sel_arg->part].fieldnr-1));
 
3047
    cur_covered= 
 
3048
      test(info->covered_fields.isBitSet(key_part[sel_arg->part].fieldnr-1));
3009
3049
    if (cur_covered != prev_covered)
3010
3050
    {
3011
3051
      /* create (part1val, ..., part{n-1}val) tuple. */
3083
3123
 
3084
3124
    E(rows_to_retrieve) = #rows_in_table * ror_scan_selectivity(null, scan1) *
3085
3125
                           ror_scan_selectivity({scan1}, scan2) * ... *
3086
 
                           ror_scan_selectivity({scan1,...}, scanN). 
 
3126
                           ror_scan_selectivity({scan1,...}, scanN).
3087
3127
  RETURN
3088
3128
    true   ROR scan added to ROR-intersection, cost updated.
3089
3129
    false  It doesn't make sense to add this ROR scan to this ROR-intersection.
3098
3138
  if (selectivity_mult == 1.0)
3099
3139
  {
3100
3140
    /* Don't add this scan if it doesn't improve selectivity. */
3101
 
    return(false);
 
3141
    return false;
3102
3142
  }
3103
 
  
 
3143
 
3104
3144
  info->out_rows *= selectivity_mult;
3105
 
  
 
3145
 
3106
3146
  if (is_cpk_scan)
3107
3147
  {
3108
3148
    /*
3109
 
      CPK scan is used to filter out rows. We apply filtering for 
 
3149
      CPK scan is used to filter out rows. We apply filtering for
3110
3150
      each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
3111
3151
      per check this gives us:
3112
3152
    */
3113
 
    info->index_scan_costs += rows2double(info->index_records) / 
 
3153
    info->index_scan_costs += rows2double(info->index_records) /
3114
3154
                              TIME_FOR_COMPARE_ROWID;
3115
3155
  }
3116
3156
  else
3129
3169
  if (!info->is_covering)
3130
3170
  {
3131
3171
    COST_VECT sweep_cost;
3132
 
    JOIN *join= info->param->thd->lex->select_lex.join;
 
3172
    JOIN *join= info->param->session->lex->select_lex.join;
3133
3173
    bool is_interrupted= test(join && join->tables == 1);
3134
3174
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
3135
3175
                        is_interrupted, &sweep_cost);
3136
3176
    info->total_cost += sweep_cost.total_cost();
3137
3177
  }
3138
 
  return(true);
 
3178
  return true;
3139
3179
}
3140
3180
 
3141
3181
 
3155
3195
 
3156
3196
  NOTES
3157
3197
    get_key_scans_params must be called before this function can be called.
3158
 
    
 
3198
 
3159
3199
    When this function is called by ROR-union construction algorithm it
3160
3200
    assumes it is building an uncovered ROR-intersection (and thus # of full
3161
3201
    records to be retrieved is wrong here). This is a hack.
3177
3217
        firstR= R - first(R);
3178
3218
        if (!selectivity(S + firstR < selectivity(S)))
3179
3219
          continue;
3180
 
          
 
3220
 
3181
3221
        S= S + first(R);
3182
3222
        if (cost(S) < min_cost)
3183
3223
        {
3212
3252
  double min_cost= DBL_MAX;
3213
3253
 
3214
3254
  if ((tree->n_ror_scans < 2) || !param->table->file->stats.records)
3215
 
    return(NULL);
 
3255
    return NULL;
3216
3256
 
3217
3257
  /*
3218
 
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of 
 
3258
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
3219
3259
    them. Also find and save clustered PK scan if there is one.
3220
3260
  */
3221
3261
  ROR_SCAN_INFO **cur_ror_scan;
3233
3273
  for (idx= 0, cur_ror_scan= tree->ror_scans; idx < param->keys; idx++)
3234
3274
  {
3235
3275
    ROR_SCAN_INFO *scan;
3236
 
    if (!tree->ror_scans_map.is_set(idx))
 
3276
    if (! tree->ror_scans_map.test(idx))
3237
3277
      continue;
3238
3278
    if (!(scan= make_ror_scan(param, idx, tree->keys[idx])))
3239
3279
      return NULL;
3271
3311
 
3272
3312
  /* Create and incrementally update ROR intersection. */
3273
3313
  ROR_INTERSECT_INFO *intersect, *intersect_best;
3274
 
  if (!(intersect= ror_intersect_init(param)) || 
 
3314
  if (!(intersect= ror_intersect_init(param)) ||
3275
3315
      !(intersect_best= ror_intersect_init(param)))
3276
3316
    return NULL;
3277
3317
 
3287
3327
      cur_ror_scan++;
3288
3328
      continue;
3289
3329
    }
3290
 
    
 
3330
 
3291
3331
    *(intersect_scans_end++)= *(cur_ror_scan++);
3292
3332
 
3293
3333
    if (intersect->total_cost < min_cost)
3301
3341
 
3302
3342
  if (intersect_scans_best == intersect_scans)
3303
3343
  {
3304
 
    return(NULL);
 
3344
    return NULL;
3305
3345
  }
3306
 
    
 
3346
 
3307
3347
  print_ror_scans_arr(param->table,
3308
3348
                                          "best ROR-intersection",
3309
3349
                                          intersect_scans,
3315
3355
 
3316
3356
  /*
3317
3357
    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 
 
3358
    Check if we should add a CPK scan. If the obtained ROR-intersection is
3319
3359
    covering, it doesn't make sense to add CPK scan.
3320
3360
  */
3321
3361
  if (cpk_scan && !intersect->is_covering)
3322
3362
  {
3323
 
    if (ror_intersect_add(intersect, cpk_scan, true) && 
 
3363
    if (ror_intersect_add(intersect, cpk_scan, true) &&
3324
3364
        (intersect->total_cost < min_cost))
3325
3365
    {
3326
3366
      cpk_scan_used= true;
3337
3377
    if (!(trp->first_scan=
3338
3378
           (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3339
3379
                                       sizeof(ROR_SCAN_INFO*)*best_num)))
3340
 
      return(NULL);
 
3380
      return NULL;
3341
3381
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
3342
3382
    trp->last_scan=  trp->first_scan + best_num;
3343
3383
    trp->is_covering= intersect_best->is_covering;
3408
3448
  /*I=set of all covering indexes */
3409
3449
  ror_scan_mark= tree->ror_scans;
3410
3450
 
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,
 
3451
  MyBitmap *covered_fields= &param->tmp_covered_fields;
 
3452
  if (! covered_fields->getBitmap())
 
3453
  {
 
3454
    my_bitmap_map *tmp_bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3414
3455
                                               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);
 
3456
    covered_fields->setBitmap(tmp_bitmap);
 
3457
  }
 
3458
  if (! covered_fields->getBitmap() ||
 
3459
      covered_fields->init(covered_fields->getBitmap(),
 
3460
                           param->table->s->fields))
 
3461
    return 0;
 
3462
  covered_fields->clearAll();
3420
3463
 
3421
3464
  double total_cost= 0.0f;
3422
3465
  ha_rows records=0;
3437
3480
    {
3438
3481
      bitmap_subtract(&(*scan)->covered_fields, covered_fields);
3439
3482
      (*scan)->used_fields_covered=
3440
 
        bitmap_bits_set(&(*scan)->covered_fields);
 
3483
        (*scan)->covered_fields.getBitsSet();
3441
3484
      (*scan)->first_uncovered_field=
3442
 
        bitmap_get_first(&(*scan)->covered_fields);
 
3485
        (*scan)->covered_fields.getFirst();
3443
3486
    }
3444
3487
 
3445
3488
    my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
3453
3496
    total_cost += (*ror_scan_mark)->index_read_cost;
3454
3497
    records += (*ror_scan_mark)->records;
3455
3498
    if (total_cost > read_time)
3456
 
      return(NULL);
 
3499
      return NULL;
3457
3500
    /* F=F-covered by first(I) */
3458
3501
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3459
3502
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
3460
3503
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3461
 
  
 
3504
 
3462
3505
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
3463
 
    return(NULL);
 
3506
    return NULL;
3464
3507
 
3465
3508
  /*
3466
3509
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
3476
3519
                (TIME_FOR_COMPARE_ROWID * M_LN2);
3477
3520
 
3478
3521
  if (total_cost > read_time)
3479
 
    return(NULL);
 
3522
    return NULL;
3480
3523
 
3481
3524
  TRP_ROR_INTERSECT *trp;
3482
3525
  if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
3485
3528
  if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3486
3529
                                                     sizeof(ROR_SCAN_INFO*)*
3487
3530
                                                     best_num)))
3488
 
    return(NULL);
 
3531
    return NULL;
3489
3532
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
3490
3533
  trp->last_scan=  trp->first_scan + best_num;
3491
3534
  trp->is_covering= true;
3492
3535
  trp->read_cost= total_cost;
3493
3536
  trp->records= records;
3494
3537
  trp->cpk_scan= NULL;
3495
 
  set_if_smaller(param->table->quick_condition_rows, records); 
 
3538
  set_if_smaller(param->table->quick_condition_rows, records);
3496
3539
 
3497
3540
  return(trp);
3498
3541
}
3509
3552
                               (except for clustered PK indexes)
3510
3553
      update_tbl_stats         true <=> update table->quick_* with information
3511
3554
                               about range scans we've evaluated.
3512
 
      read_time                Maximum cost. i.e. don't create read plans with 
 
3555
      read_time                Maximum cost. i.e. don't create read plans with
3513
3556
                               cost > read_time.
3514
3557
 
3515
3558
  DESCRIPTION
3516
 
    Find the best "range" table read plan for given SEL_TREE. 
3517
 
    The side effects are 
 
3559
    Find the best "range" table read plan for given SEL_TREE.
 
3560
    The side effects are
3518
3561
     - tree->ror_scans is updated to indicate which scans are ROR scans.
3519
3562
     - if update_tbl_stats=true then table->quick_* is updated with info
3520
3563
       about every possible range scan.
3525
3568
*/
3526
3569
 
3527
3570
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
3528
 
                                       bool index_read_must_be_used, 
 
3571
                                       bool index_read_must_be_used,
3529
3572
                                       bool update_tbl_stats,
3530
3573
                                       double read_time)
3531
3574
{
3540
3583
    is defined as "not null".
3541
3584
  */
3542
3585
  print_sel_tree(param, tree, &tree->keys_map, "tree scans");
3543
 
  tree->ror_scans_map.clear_all();
 
3586
  tree->ror_scans_map.reset();
3544
3587
  tree->n_ror_scans= 0;
3545
3588
  for (idx= 0,key=tree->keys, end=key+param->keys; key != end; key++,idx++)
3546
3589
  {
3553
3596
      uint32_t keynr= param->real_keynr[idx];
3554
3597
      if ((*key)->type == SEL_ARG::MAYBE_KEY ||
3555
3598
          (*key)->maybe_flag)
3556
 
        param->needed_reg->set_bit(keynr);
 
3599
        param->needed_reg->set(keynr);
3557
3600
 
3558
 
      bool read_index_only= index_read_must_be_used || 
3559
 
                            param->table->covering_keys.is_set(keynr);
 
3601
      bool read_index_only= index_read_must_be_used ||
 
3602
                            param->table->covering_keys.test(keynr);
3560
3603
 
3561
3604
      found_records= check_quick_select(param, idx, read_index_only, *key,
3562
3605
                                        update_tbl_stats, &mrr_flags,
3565
3608
      if ((found_records != HA_POS_ERROR) && param->is_ror_scan)
3566
3609
      {
3567
3610
        tree->n_ror_scans++;
3568
 
        tree->ror_scans_map.set_bit(idx);
 
3611
        tree->ror_scans_map.set(idx);
3569
3612
      }
3570
3613
      if (read_time > found_read_time && found_records != HA_POS_ERROR)
3571
3614
      {
3586
3629
                                                    best_mrr_flags)))
3587
3630
    {
3588
3631
      read_plan->records= best_records;
3589
 
      read_plan->is_ror= tree->ror_scans_map.is_set(idx);
 
3632
      read_plan->is_ror= tree->ror_scans_map.test(idx);
3590
3633
      read_plan->read_cost= read_time;
3591
3634
      read_plan->mrr_buf_size= best_buf_size;
3592
3635
    }
3596
3639
}
3597
3640
 
3598
3641
 
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)))
 
3642
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
3602
3643
{
3603
3644
  QUICK_INDEX_MERGE_SELECT *quick_imerge;
3604
3645
  QUICK_RANGE_SELECT *quick;
3605
3646
  /* index_merge always retrieves full rows, ignore retrieve_full_rows */
3606
 
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->thd, param->table)))
 
3647
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->session, param->table)))
3607
3648
    return NULL;
3608
3649
 
3609
3650
  quick_imerge->records= records;
3632
3673
  MEM_ROOT *alloc;
3633
3674
 
3634
3675
  if ((quick_intrsect=
3635
 
         new QUICK_ROR_INTERSECT_SELECT(param->thd, param->table,
 
3676
         new QUICK_ROR_INTERSECT_SELECT(param->session, param->table,
3636
3677
                                        (retrieve_full_rows? (!is_covering) :
3637
3678
                                         false),
3638
3679
                                        parent_alloc)))
3650
3691
          quick_intrsect->push_quick_back(quick))
3651
3692
      {
3652
3693
        delete quick_intrsect;
3653
 
        return(NULL);
 
3694
        return NULL;
3654
3695
      }
3655
3696
    }
3656
3697
    if (cpk_scan)
3661
3702
                                    0, alloc)))
3662
3703
      {
3663
3704
        delete quick_intrsect;
3664
 
        return(NULL);
 
3705
        return NULL;
3665
3706
      }
3666
 
      quick->file= NULL; 
 
3707
      quick->file= NULL;
3667
3708
      quick_intrsect->cpk_quick= quick;
3668
3709
    }
3669
3710
    quick_intrsect->records= records;
3673
3714
}
3674
3715
 
3675
3716
 
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)))
 
3717
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
3679
3718
{
3680
3719
  QUICK_ROR_UNION_SELECT *quick_roru;
3681
3720
  TABLE_READ_PLAN **scan;
3684
3723
    It is impossible to construct a ROR-union that will not retrieve full
3685
3724
    rows, ignore retrieve_full_rows parameter.
3686
3725
  */
3687
 
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->thd, param->table)))
 
3726
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->session, param->table)))
3688
3727
  {
3689
3728
    for (scan= first_ror; scan != last_ror; scan++)
3690
3729
    {
3691
3730
      if (!(quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||
3692
3731
          quick_roru->push_quick_back(quick))
3693
 
        return(NULL);
 
3732
        return NULL;
3694
3733
    }
3695
3734
    quick_roru->records= records;
3696
3735
    quick_roru->read_time= read_cost;
3701
3740
 
3702
3741
/*
3703
3742
  Build a SEL_TREE for <> or NOT BETWEEN predicate
3704
 
 
 
3743
 
3705
3744
  SYNOPSIS
3706
3745
    get_ne_mm_tree()
3707
3746
      param       PARAM from SQL_SELECT::test_quick_select
3711
3750
      gt_value    constant that field should be greaterr
3712
3751
      cmp_type    compare type for the field
3713
3752
 
3714
 
  RETURN 
 
3753
  RETURN
3715
3754
    #  Pointer to tree built tree
3716
3755
    0  on error
3717
3756
*/
3718
3757
 
3719
 
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3758
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3720
3759
                                Field *field,
3721
3760
                                Item *lt_value, Item *gt_value,
3722
3761
                                Item_result cmp_type)
3732
3771
  }
3733
3772
  return tree;
3734
3773
}
3735
 
   
 
3774
 
3736
3775
 
3737
3776
/*
3738
3777
  Build a SEL_TREE for a simple predicate
3739
 
 
 
3778
 
3740
3779
  SYNOPSIS
3741
3780
    get_func_mm_tree()
3742
3781
      param       PARAM from SQL_SELECT::test_quick_select
3745
3784
      value       constant in the predicate
3746
3785
      cmp_type    compare type for the field
3747
3786
      inv         true <> NOT cond_func is considered
3748
 
                  (makes sense only when cond_func is BETWEEN or IN) 
 
3787
                  (makes sense only when cond_func is BETWEEN or IN)
3749
3788
 
3750
 
  RETURN 
 
3789
  RETURN
3751
3790
    Pointer to the tree built tree
3752
3791
*/
3753
3792
 
3754
 
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3793
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3755
3794
                                  Field *field, Item *value,
3756
3795
                                  Item_result cmp_type, bool inv)
3757
3796
{
3805
3844
      so we check it here to avoid unnecessary work.
3806
3845
    */
3807
3846
    if (!func->arg_types_compatible)
3808
 
      break;     
 
3847
      break;
3809
3848
 
3810
3849
    if (inv)
3811
3850
    {
3813
3852
      {
3814
3853
        /*
3815
3854
          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 
 
3855
          where c{i} are constants. Our goal is to produce a SEL_TREE that
3817
3856
          represents intervals:
3818
 
          
 
3857
 
3819
3858
          ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ...    (*)
3820
 
          
 
3859
 
3821
3860
          where $MIN is either "-inf" or NULL.
3822
 
          
 
3861
 
3823
3862
          The most straightforward way to produce it is to convert NOT IN
3824
3863
          into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
3825
3864
          analyzer to build SEL_TREE from that. The problem is that the
3829
3868
 
3830
3869
          Another problem with big lists like (*) is that a big list is
3831
3870
          unlikely to produce a good "range" access, while considering that
3832
 
          range access will require expensive CPU calculations (and for 
 
3871
          range access will require expensive CPU calculations (and for
3833
3872
          MyISAM even index accesses). In short, big NOT IN lists are rarely
3834
3873
          worth analyzing.
3835
3874
 
3840
3879
        */
3841
3880
#define NOT_IN_IGNORE_THRESHOLD 1000
3842
3881
        MEM_ROOT *tmp_root= param->mem_root;
3843
 
        param->thd->mem_root= param->old_root;
3844
 
        /* 
 
3882
        param->session->mem_root= param->old_root;
 
3883
        /*
3845
3884
          Create one Item_type constant object. We'll need it as
3846
3885
          get_mm_parts only accepts constant values wrapped in Item_Type
3847
3886
          objects.
3848
3887
          We create the Item on param->mem_root which points to
3849
 
          per-statement mem_root (while thd->mem_root is currently pointing
 
3888
          per-statement mem_root (while session->mem_root is currently pointing
3850
3889
          to mem_root local to range optimizer).
3851
3890
        */
3852
3891
        Item *value_item= func->array->create_item();
3853
 
        param->thd->mem_root= tmp_root;
 
3892
        param->session->mem_root= tmp_root;
3854
3893
 
3855
3894
        if (func->array->count > NOT_IN_IGNORE_THRESHOLD || !value_item)
3856
3895
          break;
3857
3896
 
3858
3897
        /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
3859
3898
        uint32_t i=0;
3860
 
        do 
 
3899
        do
3861
3900
        {
3862
3901
          func->array->value_to_item(i, value_item);
3863
3902
          tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
3900
3939
                new_interval->min_flag= NEAR_MIN;
3901
3940
              }
3902
3941
            }
3903
 
            /* 
 
3942
            /*
3904
3943
              The following doesn't try to allocate memory so no need to
3905
3944
              check for NULL.
3906
3945
            */
3907
3946
            tree= tree_or(param, tree, tree2);
3908
3947
          }
3909
3948
        }
3910
 
        
 
3949
 
3911
3950
        if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
3912
3951
        {
3913
 
          /* 
3914
 
            Get the SEL_TREE for the last "c_last < X < +inf" interval 
 
3952
          /*
 
3953
            Get the SEL_TREE for the last "c_last < X < +inf" interval
3915
3954
            (value_item cotains c_last already)
3916
3955
          */
3917
3956
          tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
3930
3969
          for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3931
3970
               arg < end ; arg++)
3932
3971
          {
3933
 
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
 
3972
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
3934
3973
                                                        *arg, *arg, cmp_type));
3935
3974
          }
3936
3975
        }
3937
3976
      }
3938
3977
    }
3939
3978
    else
3940
 
    {    
 
3979
    {
3941
3980
      tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
3942
3981
                         func->arguments()[1], cmp_type);
3943
3982
      if (tree)
3946
3985
        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3947
3986
             arg < end ; arg++)
3948
3987
        {
3949
 
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 
 
3988
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3950
3989
                                                  Item_func::EQ_FUNC,
3951
3990
                                                  *arg, cmp_type));
3952
3991
        }
3954
3993
    }
3955
3994
    break;
3956
3995
  }
3957
 
  default: 
 
3996
  default:
3958
3997
  {
3959
 
    /* 
 
3998
    /*
3960
3999
       Here the function for the following predicates are processed:
3961
4000
       <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL.
3962
4001
       If the predicate is of the form (value op field) it is handled
3976
4015
 
3977
4016
/*
3978
4017
  Build conjunction of all SEL_TREEs for a simple predicate applying equalities
3979
 
 
 
4018
 
3980
4019
  SYNOPSIS
3981
4020
    get_full_func_mm_tree()
3982
4021
      param       PARAM from SQL_SELECT::test_quick_select
3984
4023
      field_item  field in the predicate
3985
4024
      value       constant in the predicate
3986
4025
                  (for BETWEEN it contains the number of the field argument,
3987
 
                   for IN it's always 0) 
 
4026
                   for IN it's always 0)
3988
4027
      inv         true <> NOT cond_func is considered
3989
4028
                  (makes sense only when cond_func is BETWEEN or IN)
3990
4029
 
3993
4032
    c is a constant, the function builds a conjunction of all SEL_TREES that can
3994
4033
    be obtained by the substitution of f for all different fields equal to f.
3995
4034
 
3996
 
  NOTES  
 
4035
  NOTES
3997
4036
    If the WHERE condition contains a predicate (fi op c),
3998
4037
    then not only SELL_TREE for this predicate is built, but
3999
4038
    the trees for the results of substitution of fi for
4000
4039
    each fj belonging to the same multiple equality as fi
4001
4040
    are built as well.
4002
 
    E.g. for WHERE t1.a=t2.a AND t2.a > 10 
 
4041
    E.g. for WHERE t1.a=t2.a AND t2.a > 10
4003
4042
    a SEL_TREE for t2.a > 10 will be built for quick select from t2
4004
 
    and   
 
4043
    and
4005
4044
    a SEL_TREE for t1.a > 10 will be built for quick select from t1.
4006
4045
 
4007
4046
    A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
4010
4049
    Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed
4011
4050
    differently. It is considered as a conjuction of two SARGable
4012
4051
    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) 
 
4052
    is called for each of them separately producing trees for
 
4053
       AND j (f1j <=c ) and AND j (f2j <= c)
4015
4054
    After this these two trees are united in one conjunctive tree.
4016
4055
    It's easy to see that the same tree is obtained for
4017
4056
       AND j,k (f1j <=c AND f2k<=c)
4018
 
    which is equivalent to 
 
4057
    which is equivalent to
4019
4058
       AND j,k (c BETWEEN f1j AND f2k).
4020
4059
    The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i)
4021
4060
    which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the
4022
4061
    function get_full_func_mm_tree is called for (f1i > c) and (f2i < c)
4023
4062
    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 
 
4063
    trees are united in one OR-tree. The expression
4025
4064
      (AND j (f1j > c) OR AND j (f2j < c)
4026
4065
    is equivalent to the expression
4027
 
      AND j,k (f1j > c OR f2k < c) 
4028
 
    which is just a translation of 
 
4066
      AND j,k (f1j > c OR f2k < c)
 
4067
    which is just a translation of
4029
4068
      AND j,k (c NOT BETWEEN f1j AND f2k)
4030
4069
 
4031
4070
    In the cases when one of the items f1, f2 is a constant c1 we do not create
4038
4077
    As to IN predicates only ones of the form (f IN (c1,...,cn)),
4039
4078
    where f1 is a field and c1,...,cn are constant, are considered as
4040
4079
    SARGable. We never try to narrow the index scan using predicates of
4041
 
    the form (c IN (c1,...,f,...,cn)). 
4042
 
      
4043
 
  RETURN 
 
4080
    the form (c IN (c1,...,f,...,cn)).
 
4081
 
 
4082
  RETURN
4044
4083
    Pointer to the tree representing the built conjunction of SEL_TREEs
4045
4084
*/
4046
4085
 
4047
4086
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
4048
4087
                                       Item_func *cond_func,
4049
 
                                       Item_field *field_item, Item *value, 
 
4088
                                       Item_field *field_item, Item *value,
4050
4089
                                       bool inv)
4051
4090
{
4052
4091
  SEL_TREE *tree= 0;
4061
4100
    if (arg != field_item)
4062
4101
      ref_tables|= arg->used_tables();
4063
4102
  }
 
4103
 
4064
4104
  Field *field= field_item->field;
 
4105
  field->setWriteSet();
 
4106
 
4065
4107
  Item_result cmp_type= field->cmp_type();
4066
4108
  if (!((ref_tables | field->table->map) & param_comp))
4067
4109
    ftree= get_func_mm_tree(param, cond_func, field, value, cmp_type, inv);
4073
4115
    while ((item= it++))
4074
4116
    {
4075
4117
      Field *f= item->field;
 
4118
      f->setWriteSet();
 
4119
 
4076
4120
      if (field->eq(f))
4077
4121
        continue;
4078
4122
      if (!((ref_tables | f->table->map) & param_comp))
4106
4150
      while ((item=li++))
4107
4151
      {
4108
4152
        SEL_TREE *new_tree=get_mm_tree(param,item);
4109
 
        if (param->thd->is_fatal_error || 
 
4153
        if (param->session->is_fatal_error ||
4110
4154
            param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
4111
 
          return(0);    // out of memory
 
4155
          return 0;     // out of memory
4112
4156
        tree=tree_and(param,tree,new_tree);
4113
4157
        if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4114
4158
          break;
4124
4168
        {
4125
4169
          SEL_TREE *new_tree=get_mm_tree(param,item);
4126
4170
          if (!new_tree)
4127
 
            return(0);  // out of memory
 
4171
            return 0;   // out of memory
4128
4172
          tree=tree_or(param,tree,new_tree);
4129
4173
          if (!tree || tree->type == SEL_TREE::ALWAYS)
4130
4174
            break;
4137
4181
  if (cond->const_item())
4138
4182
  {
4139
4183
    /*
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 
 
4184
      During the cond->val_int() evaluation we can come across a subselect
 
4185
      item which may allocate memory on the session->mem_root and assumes
 
4186
      all the memory allocated has the same life span as the subselect
4143
4187
      item itself. So we have to restore the thread's mem_root here.
4144
4188
    */
4145
4189
    MEM_ROOT *tmp_root= param->mem_root;
4146
 
    param->thd->mem_root= param->old_root;
 
4190
    param->session->mem_root= param->old_root;
4147
4191
    tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
4148
4192
                            new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
4149
 
    param->thd->mem_root= tmp_root;
 
4193
    param->session->mem_root= tmp_root;
4150
4194
    return(tree);
4151
4195
  }
4152
4196
 
4158
4202
    ref_tables= cond->used_tables();
4159
4203
    if ((ref_tables & param->current_table) ||
4160
4204
        (ref_tables & ~(param->prev_tables | param->read_tables)))
4161
 
      return(0);
 
4205
      return 0;
4162
4206
    return(new SEL_TREE(SEL_TREE::MAYBE));
4163
4207
  }
4164
4208
 
4167
4211
      cond_func->functype() == Item_func::IN_FUNC)
4168
4212
    inv= ((Item_func_opt_neg *) cond_func)->negated;
4169
4213
  else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
4170
 
    return(0);                         
 
4214
    return 0;
4171
4215
 
4172
4216
  param->cond= cond;
4173
4217
 
4188
4232
      if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
4189
4233
      {
4190
4234
        field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
4191
 
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func, 
 
4235
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
4192
4236
                                    field_item, (Item*)(intptr_t)i, inv);
4193
4237
        if (inv)
4194
4238
          tree= !tree ? tmp : tree_or(param, tree, tmp);
4195
 
        else 
 
4239
        else
4196
4240
          tree= tree_and(param, tree, tmp);
4197
4241
      }
4198
4242
      else if (inv)
4199
 
      { 
 
4243
      {
4200
4244
        tree= 0;
4201
4245
        break;
4202
4246
      }
4208
4252
  {
4209
4253
    Item_func_in *func=(Item_func_in*) cond_func;
4210
4254
    if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
4211
 
      return(0);
 
4255
      return 0;
4212
4256
    field_item= (Item_field*) (func->key_item()->real_item());
4213
4257
    ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
4214
4258
    break;
4215
4259
  }
4216
4260
  case Item_func::MULT_EQUAL_FUNC:
4217
4261
  {
4218
 
    Item_equal *item_equal= (Item_equal *) cond;    
 
4262
    Item_equal *item_equal= (Item_equal *) cond;
4219
4263
    if (!(value= item_equal->get_const()))
4220
 
      return(0);
 
4264
      return 0;
4221
4265
    Item_equal_iterator it(*item_equal);
4222
4266
    ref_tables= value->used_tables();
4223
4267
    while ((field_item= it++))
4224
4268
    {
4225
4269
      Field *field= field_item->field;
 
4270
      field->setWriteSet();
 
4271
 
4226
4272
      Item_result cmp_type= field->cmp_type();
4227
4273
      if (!((ref_tables | field->table->map) & param_comp))
4228
4274
      {
4231
4277
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
4232
4278
      }
4233
4279
    }
4234
 
    
 
4280
 
4235
4281
    return(ftree);
4236
4282
  }
4237
4283
  default:
4248
4294
      value= cond_func->arguments()[0];
4249
4295
    }
4250
4296
    else
4251
 
      return(0);
 
4297
      return 0;
4252
4298
    ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
4253
4299
  }
4254
4300
 
4259
4305
static SEL_TREE *
4260
4306
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4261
4307
             Item_func::Functype type,
4262
 
             Item *value,
4263
 
             Item_result cmp_type __attribute__((unused)))
 
4308
             Item *value, Item_result)
4264
4309
{
4265
4310
  if (field->table != param->table)
4266
 
    return(0);
 
4311
    return 0;
4267
4312
 
4268
4313
  KEY_PART *key_part = param->key_parts;
4269
4314
  KEY_PART *end = param->key_parts_end;
4270
4315
  SEL_TREE *tree=0;
4271
4316
  if (value &&
4272
4317
      value->used_tables() & ~(param->prev_tables | param->read_tables))
4273
 
    return(0);
 
4318
    return 0;
4274
4319
  for (; key_part != end ; key_part++)
4275
4320
  {
4276
4321
    if (field->eq(key_part->field))
4277
4322
    {
4278
4323
      SEL_ARG *sel_arg=0;
4279
4324
      if (!tree && !(tree=new SEL_TREE()))
4280
 
        return(0);                              // OOM
 
4325
        return 0;                               // OOM
4281
4326
      if (!value || !(value->used_tables() & ~param->read_tables))
4282
4327
      {
4283
4328
        sel_arg=get_mm_leaf(param,cond_func,
4294
4339
      {
4295
4340
        // This key may be used later
4296
4341
        if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4297
 
          return(0);                    // OOM
 
4342
          return 0;                     // OOM
4298
4343
      }
4299
4344
      sel_arg->part=(unsigned char) key_part->part;
4300
4345
      tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4301
 
      tree->keys_map.set_bit(key_part->key);
 
4346
      tree->keys_map.set(key_part->key);
4302
4347
    }
4303
4348
  }
4304
 
  
 
4349
 
4305
4350
  return(tree);
4306
4351
}
4307
4352
 
4310
4355
get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field,
4311
4356
            KEY_PART *key_part, Item_func::Functype type,Item *value)
4312
4357
{
4313
 
  uint32_t maybe_null=(uint) field->real_maybe_null();
 
4358
  uint32_t maybe_null=(uint32_t) field->real_maybe_null();
4314
4359
  bool optimize_range;
4315
4360
  SEL_ARG *tree= 0;
4316
4361
  MEM_ROOT *alloc= param->mem_root;
4317
4362
  unsigned char *str;
4318
 
  ulong orig_sql_mode;
4319
 
  int err;
 
4363
  int err= 0;
4320
4364
 
4321
4365
  /*
4322
4366
    We need to restore the runtime mem_root of the thread in this
4324
4368
    the argument can be any, e.g. a subselect. The subselect
4325
4369
    items, in turn, assume that all the memory allocated during
4326
4370
    the evaluation has the same life span as the item itself.
4327
 
    TODO: opt_range.cc should not reset thd->mem_root at all.
 
4371
    TODO: opt_range.cc should not reset session->mem_root at all.
4328
4372
  */
4329
 
  param->thd->mem_root= param->old_root;
 
4373
  param->session->mem_root= param->old_root;
4330
4374
  if (!value)                                   // IS NULL or IS NOT NULL
4331
4375
  {
4332
4376
    if (field->table->maybe_null)               // Can't use a key on this
4361
4405
  */
4362
4406
  if (field->result_type() == STRING_RESULT &&
4363
4407
      value->result_type() == STRING_RESULT &&
4364
 
      key_part->image_type == Field::itRAW &&
4365
4408
      ((Field_str*)field)->charset() != conf_func->compare_collation() &&
4366
4409
      !(conf_func->compare_collation()->state & MY_CS_BINSORT))
4367
4410
    goto end;
4433
4476
      max_str[0]= min_str[0]=0;
4434
4477
 
4435
4478
    field_length-= maybe_null;
 
4479
    int escape_code=
 
4480
      make_escape_code(field->charset(),
 
4481
                       ((Item_func_like*)(param->cond))->escape);
4436
4482
    like_error= my_like_range(field->charset(),
4437
4483
                              res->ptr(), res->length(),
4438
 
                              ((Item_func_like*)(param->cond))->escape,
 
4484
                              escape_code,
4439
4485
                              wild_one, wild_many,
4440
4486
                              field_length,
4441
4487
                              (char*) min_str+offset, (char*) max_str+offset,
4465
4511
      value->result_type() != STRING_RESULT &&
4466
4512
      field->cmp_type() != value->result_type())
4467
4513
    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);
 
4514
 
 
4515
  /*
 
4516
   * Some notes from Jay...
 
4517
   *
 
4518
   * OK, so previously, and in MySQL, what the optimizer does here is
 
4519
   * override the sql_mode variable to ignore out-of-range or bad date-
 
4520
   * time values.  It does this because the optimizer is populating the
 
4521
   * field variable with the incoming value from the comparison field, 
 
4522
   * and the value may exceed the bounds of a proper column type.
 
4523
   *
 
4524
   * For instance, assume the following:
 
4525
   *
 
4526
   * CREATE TABLE t1 (ts TIMESTAMP); 
 
4527
   * INSERT INTO t1 ('2009-03-04 00:00:00');
 
4528
   * CREATE TABLE t2 (dt1 DATETIME, dt2 DATETIME); 
 
4529
   * INSERT INT t2 ('2003-12-31 00:00:00','2999-12-31 00:00:00');
 
4530
   *
 
4531
   * If we issue this query:
 
4532
   *
 
4533
   * SELECT * FROM t1, t2 WHERE t1.ts BETWEEN t2.dt1 AND t2.dt2;
 
4534
   *
 
4535
   * We will come into bounds issues.  Field_timestamp::store() will be
 
4536
   * called with a datetime value of "2999-12-31 00:00:00" and will throw
 
4537
   * an error for out-of-bounds.  MySQL solves this via a hack with sql_mode
 
4538
   * but Drizzle always throws errors on bad data storage in a Field class.
 
4539
   *
 
4540
   * Therefore, to get around the problem of the Field class being used for
 
4541
   * "storage" here without actually storing anything...we must check to see 
 
4542
   * if the value being stored in a Field_timestamp here is out of range.  If
 
4543
   * it is, then we must convert to the highest Timestamp value (or lowest,
 
4544
   * depending on whether the datetime is before or after the epoch.
 
4545
   */
 
4546
  if (field->type() == DRIZZLE_TYPE_TIMESTAMP)
 
4547
  {
 
4548
    /* 
 
4549
     * The left-side of the range comparison is a timestamp field.  Therefore, 
 
4550
     * we must check to see if the value in the right-hand side is outside the
 
4551
     * range of the UNIX epoch, and cut to the epoch bounds if it is.
 
4552
     */
 
4553
    /* Datetime and date columns are Item::FIELD_ITEM ... and have a result type of STRING_RESULT */
 
4554
    if (value->real_item()->type() == Item::FIELD_ITEM
 
4555
        && value->result_type() == STRING_RESULT)
 
4556
    {
 
4557
      char buff[drizzled::DateTime::MAX_STRING_LENGTH];
 
4558
      String tmp(buff, sizeof(buff), &my_charset_bin);
 
4559
      String *res= value->val_str(&tmp);
 
4560
 
 
4561
      if (!res)
 
4562
        goto end;
 
4563
      else
 
4564
      {
 
4565
        /* 
 
4566
         * Create a datetime from the string and compare to fixed timestamp
 
4567
         * instances representing the epoch boundaries.
 
4568
         */
 
4569
        drizzled::DateTime value_datetime;
 
4570
 
 
4571
        if (! value_datetime.from_string(res->c_ptr(), (size_t) res->length()))
 
4572
          goto end;
 
4573
 
 
4574
        drizzled::Timestamp max_timestamp;
 
4575
        drizzled::Timestamp min_timestamp;
 
4576
 
 
4577
        (void) max_timestamp.from_time_t((time_t) INT32_MAX);
 
4578
        (void) min_timestamp.from_time_t((time_t) 0);
 
4579
 
 
4580
        /* We rely on Temporal class operator overloads to do our comparisons. */
 
4581
        if (value_datetime < min_timestamp)
 
4582
        {
 
4583
          /* 
 
4584
           * Datetime in right-hand side column is before UNIX epoch, so adjust to
 
4585
           * lower bound.
 
4586
           */
 
4587
          char new_value_buff[drizzled::DateTime::MAX_STRING_LENGTH];
 
4588
          int new_value_length;
 
4589
          String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
 
4590
 
 
4591
          new_value_length= min_timestamp.to_string(new_value_string.c_ptr(),
 
4592
                                    drizzled::DateTime::MAX_STRING_LENGTH);
 
4593
          assert((new_value_length+1) < drizzled::DateTime::MAX_STRING_LENGTH);
 
4594
          new_value_string.length(new_value_length);
 
4595
          err= value->save_str_value_in_field(field, &new_value_string);
 
4596
        }
 
4597
        else if (value_datetime > max_timestamp)
 
4598
        {
 
4599
          /*
 
4600
           * Datetime in right hand side column is after UNIX epoch, so adjust
 
4601
           * to the higher bound of the epoch.
 
4602
           */
 
4603
          char new_value_buff[drizzled::DateTime::MAX_STRING_LENGTH];
 
4604
          int new_value_length;
 
4605
          String new_value_string(new_value_buff, sizeof(new_value_buff), &my_charset_bin);
 
4606
 
 
4607
          new_value_length= max_timestamp.to_string(new_value_string.c_ptr(),
 
4608
                                        drizzled::DateTime::MAX_STRING_LENGTH);
 
4609
          assert((new_value_length+1) < drizzled::DateTime::MAX_STRING_LENGTH);
 
4610
          new_value_string.length(new_value_length);
 
4611
          err= value->save_str_value_in_field(field, &new_value_string);
 
4612
        }
 
4613
        else
 
4614
          err= value->save_in_field(field, 1);
 
4615
      }
 
4616
    }
 
4617
    else /* Not a datetime -> timestamp comparison */
 
4618
      err= value->save_in_field(field, 1);
 
4619
  }
 
4620
  else /* Not a timestamp comparison */
 
4621
    err= value->save_in_field(field, 1);
 
4622
 
4475
4623
  if (err > 0)
4476
4624
  {
4477
4625
    if (field->cmp_type() != value->result_type())
4491
4639
          for the cases like int_field > 999999999999999999999999 as well.
4492
4640
        */
4493
4641
        tree= 0;
4494
 
        if (err == 3 && field->type() == DRIZZLE_TYPE_NEWDATE &&
 
4642
        if (err == 3 && field->type() == DRIZZLE_TYPE_DATE &&
4495
4643
            (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC ||
4496
4644
             type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) )
4497
4645
        {
4500
4648
            but a non-zero time part was cut off.
4501
4649
 
4502
4650
            In MySQL's SQL dialect, DATE and DATETIME are compared as datetime
4503
 
            values. Index over a DATE column uses DATE comparison. Changing 
 
4651
            values. Index over a DATE column uses DATE comparison. Changing
4504
4652
            from one comparison to the other is possible:
4505
4653
 
4506
4654
            datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10'
4537
4685
  }
4538
4686
  else if (err < 0)
4539
4687
  {
4540
 
    field->table->in_use->variables.sql_mode= orig_sql_mode;
4541
4688
    /* This happens when we try to insert a NULL field in a not null column */
4542
4689
    tree= &null_element;                        // cmp with NULL is never true
4543
4690
    goto end;
4544
4691
  }
4545
 
  field->table->in_use->variables.sql_mode= orig_sql_mode;
4546
4692
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
4547
4693
  if (!str)
4548
4694
    goto end;
4549
4695
  if (maybe_null)
4550
4696
    *str= (unsigned char) field->is_real_null();        // Set to 1 if null
4551
 
  field->get_key_image(str+maybe_null, key_part->length,
4552
 
                       key_part->image_type);
 
4697
  field->get_key_image(str+maybe_null, key_part->length);
4553
4698
  if (!(tree= new (alloc) SEL_ARG(field, str, str)))
4554
4699
    goto end;                                   // out of memory
4555
4700
 
4612
4757
  }
4613
4758
 
4614
4759
end:
4615
 
  param->thd->mem_root= alloc;
 
4760
  param->session->mem_root= alloc;
4616
4761
  return(tree);
4617
4762
}
4618
4763
 
4692
4837
    return(tree1);
4693
4838
  }
4694
4839
  key_map  result_keys;
4695
 
  result_keys.clear_all();
4696
 
  
 
4840
  result_keys.reset();
 
4841
 
4697
4842
  /* Join the trees key per key */
4698
4843
  SEL_ARG **key1,**key2,**end;
4699
4844
  for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
4712
4857
        tree1->type= SEL_TREE::IMPOSSIBLE;
4713
4858
        return(tree1);
4714
4859
      }
4715
 
      result_keys.set_bit(key1 - tree1->keys);
 
4860
      result_keys.set(key1 - tree1->keys);
4716
4861
#ifdef EXTRA_DEBUG
4717
 
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
4862
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4718
4863
          (*key1)->test_use_count(*key1);
4719
4864
#endif
4720
4865
    }
4721
4866
  }
4722
4867
  tree1->keys_map= result_keys;
4723
4868
  /* dispose index_merge if there is a "range" option */
4724
 
  if (!result_keys.is_clear_all())
 
4869
  if (result_keys.any())
4725
4870
  {
4726
 
    tree1->merges.empty();
 
4871
    tree1->merges.clear();
4727
4872
    return(tree1);
4728
4873
  }
4729
4874
 
4730
4875
  /* ok, both trees are index_merge trees */
4731
 
  imerge_list_and_list(&tree1->merges, &tree2->merges);
 
4876
  imerge_list_and_list(tree1->merges, tree2->merges);
4732
4877
  return(tree1);
4733
4878
}
4734
4879
 
4739
4884
  using index_merge.
4740
4885
*/
4741
4886
 
4742
 
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, 
 
4887
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4743
4888
                           RANGE_OPT_PARAM* param)
4744
4889
{
4745
4890
  key_map common_keys= tree1->keys_map;
4746
 
  common_keys.intersect(tree2->keys_map);
 
4891
  common_keys&= tree2->keys_map;
4747
4892
 
4748
 
  if (common_keys.is_clear_all())
4749
 
    return(false);
 
4893
  if (common_keys.none())
 
4894
    return false;
4750
4895
 
4751
4896
  /* trees have a common key, check if they refer to same key part */
4752
4897
  SEL_ARG **key1,**key2;
4753
4898
  for (uint32_t key_no=0; key_no < param->keys; key_no++)
4754
4899
  {
4755
 
    if (common_keys.is_set(key_no))
 
4900
    if (common_keys.test(key_no))
4756
4901
    {
4757
4902
      key1= tree1->keys + key_no;
4758
4903
      key2= tree2->keys + key_no;
4759
4904
      if ((*key1)->part == (*key2)->part)
4760
4905
      {
4761
 
        return(true);
 
4906
        return true;
4762
4907
      }
4763
4908
    }
4764
4909
  }
4765
 
  return(false);
 
4910
  return false;
4766
4911
}
4767
4912
 
4768
4913
 
4771
4916
  SYNOPSIS
4772
4917
    param  Range analysis parameter
4773
4918
    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
4774
 
 
 
4919
 
4775
4920
  DESCRIPTION
4776
4921
    This function walks through tree->keys[] and removes the SEL_ARG* trees
4777
4922
    that are not "maybe" trees (*) and cannot be used to construct quick range
4783
4928
    tree->part != 0. (e.g. it could represent "keypart2 < const").
4784
4929
 
4785
4930
    WHY THIS FUNCTION IS NEEDED
4786
 
    
 
4931
 
4787
4932
    Normally we allow construction of SEL_TREE objects that have SEL_ARG
4788
4933
    trees that do not allow quick range select construction. For example for
4789
4934
    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4792
4937
                                               from this
4793
4938
    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4794
4939
                                   tree.
4795
 
    
 
4940
 
4796
4941
    There is an exception though: when we construct index_merge SEL_TREE,
4797
4942
    any SEL_ARG* tree that cannot be used to construct quick range select can
4798
4943
    be removed, because current range analysis code doesn't provide any way
4799
4944
    that tree could be later combined with another tree.
4800
4945
    Consider an example: we should not construct
4801
 
    st1 = SEL_TREE { 
4802
 
      merges = SEL_IMERGE { 
4803
 
                            SEL_TREE(t.key1part1 = 1), 
 
4946
    st1 = SEL_TREE {
 
4947
      merges = SEL_IMERGE {
 
4948
                            SEL_TREE(t.key1part1 = 1),
4804
4949
                            SEL_TREE(t.key2part2 = 2)   -- (*)
4805
 
                          } 
 
4950
                          }
4806
4951
                   };
4807
 
    because 
4808
 
     - (*) cannot be used to construct quick range select, 
4809
 
     - There is no execution path that would cause (*) to be converted to 
 
4952
    because
 
4953
     - (*) cannot be used to construct quick range select,
 
4954
     - There is no execution path that would cause (*) to be converted to
4810
4955
       a tree that could be used.
4811
4956
 
4812
4957
    The latter is easy to verify: first, notice that the only way to convert
4813
4958
    (*) into a usable tree is to call tree_and(something, (*)).
4814
4959
 
4815
4960
    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 
 
4961
    SEL_TREE that has the structure like st1 tree has, and conlcude that
4817
4962
    tree_and(something, (*)) will not be called.
4818
4963
 
4819
4964
  RETURN
4831
4976
      if (tree->keys[i]->part)
4832
4977
      {
4833
4978
        tree->keys[i]= NULL;
4834
 
        tree->keys_map.clear_bit(i);
 
4979
        tree->keys_map.reset(i);
4835
4980
      }
4836
4981
      else
4837
4982
        res= true;
4845
4990
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4846
4991
{
4847
4992
  if (!tree1 || !tree2)
4848
 
    return(0);
 
4993
    return 0;
4849
4994
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4850
4995
    return(tree2);
4851
4996
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4857
5002
 
4858
5003
  SEL_TREE *result= 0;
4859
5004
  key_map  result_keys;
4860
 
  result_keys.clear_all();
 
5005
  result_keys.reset();
4861
5006
  if (sel_trees_can_be_ored(tree1, tree2, param))
4862
5007
  {
4863
5008
    /* Join the trees key per key */
4869
5014
      if (*key1)
4870
5015
      {
4871
5016
        result=tree1;                           // Added to tree1
4872
 
        result_keys.set_bit(key1 - tree1->keys);
 
5017
        result_keys.set(key1 - tree1->keys);
4873
5018
#ifdef EXTRA_DEBUG
4874
 
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
5019
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4875
5020
          (*key1)->test_use_count(*key1);
4876
5021
#endif
4877
5022
      }
4882
5027
  else
4883
5028
  {
4884
5029
    /* ok, two trees have KEY type but cannot be used without index merge */
4885
 
    if (tree1->merges.is_empty() && tree2->merges.is_empty())
 
5030
    if ((tree1->merges.empty() == true) && (tree2->merges.empty() == true))
4886
5031
    {
4887
5032
      if (param->remove_jump_scans)
4888
5033
      {
4891
5036
        if (no_trees)
4892
5037
          return(new SEL_TREE(SEL_TREE::ALWAYS));
4893
5038
      }
4894
 
      SEL_IMERGE *merge;
4895
 
      /* both trees are "range" trees, produce new index merge structure */
4896
 
      if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
4897
 
          (result->merges.push_back(merge)) ||
4898
 
          (merge->or_sel_tree(param, tree1)) ||
4899
 
          (merge->or_sel_tree(param, tree2)))
 
5039
 
 
5040
      /* both trees are "range" trees, produce new index merge structure. */
 
5041
      result= new SEL_TREE();
 
5042
      SEL_IMERGE *merge= new SEL_IMERGE();
 
5043
      result->merges.push_back(merge);
 
5044
 
 
5045
      if( merge->or_sel_tree(param, tree1) || merge->or_sel_tree(param, tree2))
4900
5046
        result= NULL;
4901
5047
      else
4902
5048
        result->type= tree1->type;
4903
5049
    }
4904
 
    else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
 
5050
    else if ((tree1->merges.empty() == false) && (tree2->merges.empty() == false))
4905
5051
    {
4906
 
      if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
 
5052
      if (imerge_list_or_list(param, tree1->merges, tree2->merges))
4907
5053
        result= new SEL_TREE(SEL_TREE::ALWAYS);
4908
5054
      else
4909
5055
        result= tree1;
4911
5057
    else
4912
5058
    {
4913
5059
      /* one tree is index merge tree and another is range tree */
4914
 
      if (tree1->merges.is_empty())
 
5060
      if (tree1->merges.empty() == true)
4915
5061
        std::swap(tree1, tree2);
4916
 
      
 
5062
 
4917
5063
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
4918
5064
         return(new SEL_TREE(SEL_TREE::ALWAYS));
 
5065
 
4919
5066
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
4920
 
      if (imerge_list_or_tree(param, &tree1->merges, tree2))
 
5067
      if (imerge_list_or_tree(param, tree1->merges, tree2))
4921
5068
        result= new SEL_TREE(SEL_TREE::ALWAYS);
4922
5069
      else
4923
5070
        result= tree1;
4924
5071
    }
4925
5072
  }
4926
 
  return(result);
 
5073
  return result;
4927
5074
}
4928
5075
 
4929
5076
 
4930
5077
/* And key trees where key1->part < key2 -> part */
4931
5078
 
4932
5079
static SEL_ARG *
4933
 
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, 
 
5080
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4934
5081
             uint32_t clone_flag)
4935
5082
{
4936
5083
  SEL_ARG *next;
5030
5177
    }
5031
5178
    if (key1->type == SEL_ARG::MAYBE_KEY)
5032
5179
    {                                           // Both are maybe key
5033
 
      key1->next_key_part=key_and(param, key1->next_key_part, 
 
5180
      key1->next_key_part=key_and(param, key1->next_key_part,
5034
5181
                                  key2->next_key_part, clone_flag);
5035
5182
      if (key1->next_key_part &&
5036
5183
          key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5534
5681
  }
5535
5682
 
5536
5683
  if (root == &null_element)
5537
 
    return(0);                          // Maybe root later
 
5684
    return 0;                           // Maybe root later
5538
5685
  if (remove_color == BLACK)
5539
5686
    root=rb_delete_fixup(root,nod,fix_par);
 
5687
#ifdef EXTRA_DEBUG
5540
5688
  test_rb_tree(root,root->parent);
 
5689
#endif /* EXTRA_DEBUG */
5541
5690
 
5542
5691
  root->use_count=this->use_count;              // Fix root counters
5543
5692
  root->elements=this->elements-1;
5634
5783
    }
5635
5784
  }
5636
5785
  root->color=BLACK;
 
5786
#ifdef EXTRA_DEBUG
5637
5787
  test_rb_tree(root,root->parent);
 
5788
#endif /* EXTRA_DEBUG */
 
5789
 
5638
5790
  return root;
5639
5791
}
5640
5792
 
5729
5881
    return 0;                                   // Found end of tree
5730
5882
  if (element->parent != parent)
5731
5883
  {
5732
 
    sql_print_error("Wrong tree: Parent doesn't point at parent");
 
5884
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5733
5885
    return -1;
5734
5886
  }
5735
5887
  if (element->color == SEL_ARG::RED &&
5736
5888
      (element->left->color == SEL_ARG::RED ||
5737
5889
       element->right->color == SEL_ARG::RED))
5738
5890
  {
5739
 
    sql_print_error("Wrong tree: Found two red in a row");
 
5891
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5740
5892
    return -1;
5741
5893
  }
5742
5894
  if (element->left == element->right && element->left != &null_element)
5743
5895
  {                                             // Dummy test
5744
 
    sql_print_error("Wrong tree: Found right == left");
 
5896
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5745
5897
    return -1;
5746
5898
  }
5747
5899
  count_l=test_rb_tree(element->left,element);
5750
5902
  {
5751
5903
    if (count_l == count_r)
5752
5904
      return count_l+(element->color == SEL_ARG::BLACK);
5753
 
    sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
 
5905
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5754
5906
            count_l,count_r);
5755
5907
  }
5756
5908
  return -1;                                    // Error, no more warnings
5759
5911
 
5760
5912
/*
5761
5913
  Count how many times SEL_ARG graph "root" refers to its part "key"
5762
 
  
 
5914
 
5763
5915
  SYNOPSIS
5764
5916
    count_key_part_usage()
5765
5917
      root  An RB-Root node in a SEL_ARG graph.
5770
5922
    root->next->n
5771
5923
 
5772
5924
    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 
 
5925
    SEL_ARG::next_key_part) by
 
5926
     - intervals of RB-tree pointed by "root",
 
5927
     - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5776
5928
       intervals of RB-tree pointed by "root",
5777
5929
     - and so on.
5778
 
    
5779
 
    Here is an example (horizontal links represent next_key_part pointers, 
5780
 
    vertical links - next/prev prev pointers):  
5781
 
    
 
5930
 
 
5931
    Here is an example (horizontal links represent next_key_part pointers,
 
5932
    vertical links - next/prev prev pointers):
 
5933
 
5782
5934
         +----+               $
5783
5935
         |root|-----------------+
5784
5936
         +----+               $ |
5797
5949
          ...     +---+       $    |
5798
5950
                  |   |------------+
5799
5951
                  +---+       $
5800
 
  RETURN 
 
5952
  RETURN
5801
5953
    Number of links to "key" from nodes reachable from "root".
5802
5954
*/
5803
5955
 
5837
5989
  uint32_t e_count=0;
5838
5990
  if (this == root && use_count != 1)
5839
5991
  {
5840
 
    sql_print_information("Use_count: Wrong count %lu for root",use_count);
 
5992
    errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5841
5993
    return;
5842
5994
  }
5843
5995
  if (this->type != SEL_ARG::KEY_RANGE)
5850
6002
      ulong count=count_key_part_usage(root,pos->next_key_part);
5851
6003
      if (count > pos->next_key_part->use_count)
5852
6004
      {
5853
 
        sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
 
6005
        errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5854
6006
                              "should be %lu", (long unsigned int)pos,
5855
6007
                              pos->next_key_part->use_count, count);
5856
6008
        return;
5859
6011
    }
5860
6012
  }
5861
6013
  if (e_count != elements)
5862
 
    sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
 
6014
    errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5863
6015
                      e_count, elements, (long unsigned int) this);
5864
6016
}
5865
6017
 
5870
6022
 ****************************************************************************/
5871
6023
 
5872
6024
/* MRR range sequence, SEL_ARG* implementation: stack entry */
5873
 
typedef struct st_range_seq_entry 
 
6025
typedef struct st_range_seq_entry
5874
6026
{
5875
 
  /* 
 
6027
  /*
5876
6028
    Pointers in min and max keys. They point to right-after-end of key
5877
6029
    images. The 0-th entry has these pointing to key tuple start.
5878
6030
  */
5879
6031
  unsigned char *min_key, *max_key;
5880
 
  
5881
 
  /* 
 
6032
 
 
6033
  /*
5882
6034
    Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
5883
6035
    min_key_flag may have NULL_RANGE set.
5884
6036
  */
5885
6037
  uint32_t min_key_flag, max_key_flag;
5886
 
  
 
6038
 
5887
6039
  /* Number of key parts */
5888
6040
  uint32_t min_key_parts, max_key_parts;
5889
6041
  SEL_ARG *key_tree;
5899
6051
  uint32_t real_keyno; /* Number of the index in tables */
5900
6052
  PARAM *param;
5901
6053
  SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
5902
 
  
 
6054
 
5903
6055
  RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
5904
6056
  int i; /* Index of last used element in the above array */
5905
 
  
 
6057
 
5906
6058
  bool at_start; /* true <=> The traversal has just started */
5907
6059
} SEL_ARG_RANGE_SEQ;
5908
6060
 
5913
6065
  SYNOPSIS
5914
6066
    init()
5915
6067
      init_params  SEL_ARG tree traversal context
5916
 
      n_ranges     [ignored] The number of ranges obtained 
 
6068
      n_ranges     [ignored] The number of ranges obtained
5917
6069
      flags        [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
5918
6070
 
5919
6071
  RETURN
5920
6072
    Value of init_param
5921
6073
*/
5922
6074
 
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)))
 
6075
static range_seq_t sel_arg_range_seq_init(void *init_param, uint32_t, uint32_t)
5926
6076
{
5927
6077
  SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
5928
6078
  seq->at_start= true;
5943
6093
{
5944
6094
  RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
5945
6095
  RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
5946
 
  
 
6096
 
5947
6097
  cur->key_tree= key_tree;
5948
6098
  cur->min_key= prev->min_key;
5949
6099
  cur->max_key= prev->max_key;
5967
6117
 
5968
6118
/*
5969
6119
  Range sequence interface, SEL_ARG* implementation: get the next interval
5970
 
  
 
6120
 
5971
6121
  SYNOPSIS
5972
6122
    sel_arg_range_seq_next()
5973
6123
      rseq        Value returned from sel_arg_range_seq_init
5989
6139
*/
5990
6140
 
5991
6141
//psergey-merge-todo: support check_quick_keys:max_keypart
5992
 
uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
 
6142
static uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
5993
6143
{
5994
6144
  SEL_ARG *key_tree;
5995
6145
  SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
6002
6152
 
6003
6153
  key_tree= seq->stack[seq->i].key_tree;
6004
6154
  /* Ok, we're at some "full tuple" position in the tree */
6005
 
 
 
6155
 
6006
6156
  /* Step down if we can */
6007
6157
  if (key_tree->next && key_tree->next != &null_element)
6008
6158
  {
6039
6189
    Walk right-up while we can
6040
6190
  */
6041
6191
walk_right_n_up:
6042
 
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element && 
 
6192
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
6043
6193
         key_tree->next_key_part->part == key_tree->part + 1 &&
6044
6194
         key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6045
6195
  {
6054
6204
      {
6055
6205
        seq->param->is_ror_scan= false;
6056
6206
        if (!key_tree->min_flag)
6057
 
          cur->min_key_parts += 
 
6207
          cur->min_key_parts +=
6058
6208
            key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6059
6209
                                                   &cur->min_key,
6060
6210
                                                   &cur->min_key_flag);
6061
6211
        if (!key_tree->max_flag)
6062
 
          cur->max_key_parts += 
 
6212
          cur->max_key_parts +=
6063
6213
            key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6064
6214
                                                   &cur->max_key,
6065
6215
                                                   &cur->max_key_flag);
6066
6216
        break;
6067
6217
      }
6068
6218
    }
6069
 
  
 
6219
 
6070
6220
    /*
6071
6221
      Ok, current atomic interval is in form "t.field=const" and there is
6072
6222
      next_key_part interval. Step right, and walk up from there.
6084
6234
 
6085
6235
  /* Ok got a tuple */
6086
6236
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6087
 
  
 
6237
 
6088
6238
  range->ptr= (char*)(int)(key_tree->part);
6089
6239
  {
6090
6240
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
6091
 
    
 
6241
 
6092
6242
    range->start_key.key=    seq->param->min_key;
6093
6243
    range->start_key.length= cur->min_key - seq->param->min_key;
6094
6244
    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 : 
 
6245
    range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
6096
6246
                                                           HA_READ_KEY_EXACT);
6097
6247
 
6098
6248
    range->end_key.key=    seq->param->max_key;
6099
6249
    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 : 
 
6250
    range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
6101
6251
                                                         HA_READ_AFTER_KEY);
6102
6252
    range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
6103
6253
 
6104
6254
    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 &&
 
6255
        (uint32_t)key_tree->part+1 == seq->param->table->key_info[seq->real_keyno].key_parts &&
6106
6256
        (seq->param->table->key_info[seq->real_keyno].flags & (HA_NOSAME)) ==
6107
6257
        HA_NOSAME &&
6108
6258
        range->start_key.length == range->end_key.length &&
6109
6259
        !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
6110
6260
      range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
6111
 
      
 
6261
 
6112
6262
    if (seq->param->is_ror_scan)
6113
6263
    {
6114
6264
      /*
6128
6278
    }
6129
6279
  }
6130
6280
  seq->param->range_count++;
6131
 
  seq->param->max_key_part=cmax(seq->param->max_key_part,(uint)key_tree->part);
 
6281
  seq->param->max_key_part= max(seq->param->max_key_part,(uint32_t)key_tree->part);
6132
6282
  return 0;
6133
6283
}
6134
6284
 
6135
6285
 
6136
6286
/*
6137
 
  Calculate cost and E(#rows) for a given index and intervals tree 
 
6287
  Calculate cost and E(#rows) for a given index and intervals tree
6138
6288
 
6139
6289
  SYNOPSIS
6140
6290
    check_quick_select()
6162
6312
 
6163
6313
static
6164
6314
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
6165
 
                           SEL_ARG *tree, bool update_tbl_stats, 
 
6315
                           SEL_ARG *tree, bool update_tbl_stats,
6166
6316
                           uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
6167
6317
{
6168
6318
  SEL_ARG_RANGE_SEQ seq;
6170
6320
  handler *file= param->table->file;
6171
6321
  ha_rows rows;
6172
6322
  uint32_t keynr= param->real_keynr[idx];
6173
 
  
 
6323
 
6174
6324
  /* Handle cases when we don't have a valid non-empty list of range */
6175
6325
  if (!tree)
6176
6326
    return(HA_POS_ERROR);
6190
6340
  param->is_ror_scan= true;
6191
6341
  if (file->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)
6192
6342
    param->is_ror_scan= false;
6193
 
  
 
6343
 
6194
6344
  *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
6195
6345
  *mrr_flags|= HA_MRR_NO_ASSOCIATION;
6196
6346
 
6197
6347
  bool pk_is_clustered= file->primary_key_is_clustered();
6198
 
  if (index_only && 
 
6348
  if (index_only &&
6199
6349
      (file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&
6200
6350
      !(pk_is_clustered && keynr == param->table->s->primary_key))
6201
6351
     *mrr_flags |= HA_MRR_INDEX_ONLY;
6202
 
  
6203
 
  if (current_thd->lex->sql_command != SQLCOM_SELECT)
 
6352
 
 
6353
  if (current_session->lex->sql_command != SQLCOM_SELECT)
6204
6354
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6205
6355
 
6206
 
  *bufsize= param->thd->variables.read_rnd_buff_size;
 
6356
  *bufsize= param->session->variables.read_rnd_buff_size;
6207
6357
  rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,
6208
6358
                                          bufsize, mrr_flags, cost);
6209
6359
  if (rows != HA_POS_ERROR)
6211
6361
    param->table->quick_rows[keynr]=rows;
6212
6362
    if (update_tbl_stats)
6213
6363
    {
6214
 
      param->table->quick_keys.set_bit(keynr);
 
6364
      param->table->quick_keys.set(keynr);
6215
6365
      param->table->quick_key_parts[keynr]=param->max_key_part+1;
6216
6366
      param->table->quick_n_ranges[keynr]= param->range_count;
6217
6367
      param->table->quick_condition_rows=
6218
 
        cmin(param->table->quick_condition_rows, rows);
 
6368
        min(param->table->quick_condition_rows, rows);
6219
6369
    }
6220
6370
  }
6221
6371
  /* Figure out if the key scan is ROR (returns rows in ROWID order) or not */
6222
6372
  enum ha_key_alg key_alg= param->table->key_info[seq.real_keyno].algorithm;
6223
6373
  if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF))
6224
6374
  {
6225
 
    /* 
 
6375
    /*
6226
6376
      All scans are non-ROR scans for those index types.
6227
 
      TODO: Don't have this logic here, make table engines return 
 
6377
      TODO: Don't have this logic here, make table engines return
6228
6378
      appropriate flags instead.
6229
6379
    */
6230
6380
    param->is_ror_scan= false;
6263
6413
 
6264
6414
    where the index is defined on (key1_1, ..., key1_N [,a_1, ..., a_n])
6265
6415
 
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 
 
6416
    and the table has a clustered Primary Key defined as
 
6417
      PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
 
6418
 
 
6419
    i.e. the first key parts of it are identical to uncovered parts ot the
6270
6420
    key being scanned. This function assumes that the index flags do not
6271
6421
    include HA_KEY_SCAN_NOT_ROR flag (that is checked elsewhere).
6272
6422
 
6284
6434
  KEY_PART_INFO *key_part_end= (table_key->key_part +
6285
6435
                                table_key->key_parts);
6286
6436
  uint32_t pk_number;
6287
 
  
 
6437
 
6288
6438
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
6289
6439
  {
6290
6440
    uint16_t fieldnr= param->table->key_info[keynr].
6330
6480
  NOTES
6331
6481
    The caller must call QUICK_SELECT::init for returned quick select.
6332
6482
 
6333
 
    CAUTION! This function may change thd->mem_root to a MEM_ROOT which will be
 
6483
    CAUTION! This function may change session->mem_root to a MEM_ROOT which will be
6334
6484
    deallocated when the returned quick select is deleted.
6335
6485
 
6336
6486
  RETURN
6345
6495
  QUICK_RANGE_SELECT *quick;
6346
6496
  bool create_err= false;
6347
6497
 
6348
 
  quick=new QUICK_RANGE_SELECT(param->thd, param->table,
 
6498
  quick=new QUICK_RANGE_SELECT(param->session, param->table,
6349
6499
                               param->real_keynr[idx],
6350
6500
                               test(parent_alloc), NULL, &create_err);
6351
6501
 
6369
6519
                    param->table->key_info[param->real_keynr[idx]].key_parts);
6370
6520
    }
6371
6521
  }
6372
 
  return(quick);
 
6522
  return quick;
6373
6523
}
6374
6524
 
6375
6525
 
6403
6553
      key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6404
6554
  {                                               // const key as prefix
6405
6555
    if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
6406
 
         memcmp(min_key, max_key, (uint)(tmp_max_key - max_key))==0 &&
 
6556
         memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
6407
6557
         key_tree->min_flag==0 && key_tree->max_flag==0)
6408
6558
    {
6409
6559
      if (get_quick_keys(param,quick,key,key_tree->next_key_part,
6444
6594
  }
6445
6595
  if (flag == 0)
6446
6596
  {
6447
 
    uint32_t length= (uint) (tmp_min_key - param->min_key);
6448
 
    if (length == (uint) (tmp_max_key - param->max_key) &&
 
6597
    uint32_t length= (uint32_t) (tmp_min_key - param->min_key);
 
6598
    if (length == (uint32_t) (tmp_max_key - param->max_key) &&
6449
6599
        !memcmp(param->min_key,param->max_key,length))
6450
6600
    {
6451
6601
      KEY *table_key=quick->head->key_info+quick->index;
6456
6606
        if (!(table_key->flags & HA_NULL_PART_KEY) ||
6457
6607
            !null_part_in_key(key,
6458
6608
                              param->min_key,
6459
 
                              (uint) (tmp_min_key - param->min_key)))
 
6609
                              (uint32_t) (tmp_min_key - param->min_key)))
6460
6610
          flag|= UNIQUE_RANGE;
6461
6611
        else
6462
6612
          flag|= NULL_RANGE;
6466
6616
 
6467
6617
  /* Get range for retrieving rows in QUICK_SELECT::get_next */
6468
6618
  if (!(range= new QUICK_RANGE(param->min_key,
6469
 
                               (uint) (tmp_min_key - param->min_key),
 
6619
                               (uint32_t) (tmp_min_key - param->min_key),
6470
6620
                               min_part >=0 ? make_keypart_map(min_part) : 0,
6471
6621
                               param->max_key,
6472
 
                               (uint) (tmp_max_key - param->max_key),
 
6622
                               (uint32_t) (tmp_max_key - param->max_key),
6473
6623
                               max_part >=0 ? make_keypart_map(max_part) : 0,
6474
6624
                               flag)))
6475
6625
    return 1;                   // out of memory
6476
6626
 
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);
 
6627
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->min_length);
 
6628
  set_if_bigger(quick->max_used_key_length, (uint32_t)range->max_length);
 
6629
  set_if_bigger(quick->used_key_parts, (uint32_t) key_tree->part+1);
6480
6630
  if (insert_dynamic(&quick->ranges, (unsigned char*) &range))
6481
6631
    return 1;
6482
6632
 
6513
6663
  Return true if any part of the key is NULL
6514
6664
 
6515
6665
  SYNOPSIS
6516
 
    null_part_in_key()    
 
6666
    null_part_in_key()
6517
6667
      key_part  Array of key parts (index description)
6518
6668
      key       Key values tuple
6519
6669
      length    Length of key values tuple in bytes.
6536
6686
}
6537
6687
 
6538
6688
 
6539
 
bool QUICK_SELECT_I::is_keys_used(const MY_BITMAP *fields)
 
6689
bool QUICK_SELECT_I::is_keys_used(const MyBitmap *fields)
6540
6690
{
6541
6691
  return is_key_used(head, index, fields);
6542
6692
}
6543
6693
 
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)
 
6694
bool QUICK_INDEX_MERGE_SELECT::is_keys_used(const MyBitmap *fields)
 
6695
{
 
6696
  QUICK_RANGE_SELECT *quick;
 
6697
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6698
  while ((quick= it++))
 
6699
  {
 
6700
    if (is_key_used(head, quick->index, fields))
 
6701
      return 1;
 
6702
  }
 
6703
  return 0;
 
6704
}
 
6705
 
 
6706
bool QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MyBitmap *fields)
 
6707
{
 
6708
  QUICK_RANGE_SELECT *quick;
 
6709
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
 
6710
  while ((quick= it++))
 
6711
  {
 
6712
    if (is_key_used(head, quick->index, fields))
 
6713
      return 1;
 
6714
  }
 
6715
  return 0;
 
6716
}
 
6717
 
 
6718
bool QUICK_ROR_UNION_SELECT::is_keys_used(const MyBitmap *fields)
6569
6719
{
6570
6720
  QUICK_SELECT_I *quick;
6571
6721
  List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
6583
6733
 
6584
6734
  SYNOPSIS
6585
6735
    get_quick_select_for_ref()
6586
 
      thd      Thread handle
 
6736
      session      Thread handle
6587
6737
      table    Table to access
6588
6738
      ref      ref[_or_null] scan parameters
6589
6739
      records  Estimate of number of records (needed only to construct
6597
6747
    NULL on error.
6598
6748
*/
6599
6749
 
6600
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, Table *table,
6601
 
                                             TABLE_REF *ref, ha_rows records)
 
6750
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
 
6751
                                             table_reference_st *ref, ha_rows records)
6602
6752
{
6603
6753
  MEM_ROOT *old_root, *alloc;
6604
6754
  QUICK_RANGE_SELECT *quick;
6609
6759
  bool create_err= false;
6610
6760
  COST_VECT cost;
6611
6761
 
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);
 
6762
  old_root= session->mem_root;
 
6763
  /* The following call may change session->mem_root */
 
6764
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0, &create_err);
6615
6765
  /* save mem_root set by QUICK_RANGE_SELECT constructor */
6616
 
  alloc= thd->mem_root;
 
6766
  alloc= session->mem_root;
6617
6767
  /*
6618
 
    return back default mem_root (thd->mem_root) changed by
 
6768
    return back default mem_root (session->mem_root) changed by
6619
6769
    QUICK_RANGE_SELECT constructor
6620
6770
  */
6621
 
  thd->mem_root= old_root;
 
6771
  session->mem_root= old_root;
6622
6772
 
6623
6773
  if (!quick || create_err)
6624
6774
    return 0;                   /* no ranges found */
6626
6776
    goto err;
6627
6777
  quick->records= records;
6628
6778
 
6629
 
  if ((cp_buffer_from_ref(thd, ref) && thd->is_fatal_error) ||
 
6779
  if ((cp_buffer_from_ref(session, ref) && session->is_fatal_error) ||
6630
6780
      !(range= new(alloc) QUICK_RANGE()))
6631
6781
    goto err;                                   // out of memory
6632
6782
 
6635
6785
  range->min_keypart_map= range->max_keypart_map=
6636
6786
    make_prev_keypart_map(ref->key_parts);
6637
6787
  range->flag= ((ref->key_length == key_info->key_length &&
6638
 
                 key_info->flags == 0) ? EQ_RANGE : 0);
 
6788
                 (key_info->flags & HA_END_SPACE_KEY) == 0) ? EQ_RANGE : 0);
 
6789
 
6639
6790
 
6640
6791
  if (!(quick->key_parts=key_part=(KEY_PART *)
6641
6792
        alloc_root(&quick->alloc,sizeof(KEY_PART)*ref->key_parts)))
6676
6827
  }
6677
6828
 
6678
6829
  /* Call multi_range_read_info() to get the MRR flags and buffer size */
6679
 
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION | 
 
6830
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
6680
6831
                    (table->key_read ? HA_MRR_INDEX_ONLY : 0);
6681
 
  if (thd->lex->sql_command != SQLCOM_SELECT)
 
6832
  if (session->lex->sql_command != SQLCOM_SELECT)
6682
6833
    quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6683
6834
 
6684
 
  quick->mrr_buf_size= thd->variables.read_rnd_buff_size;
6685
 
  if (table->file->multi_range_read_info(quick->index, 1, (uint)records,
 
6835
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
 
6836
  if (table->file->multi_range_read_info(quick->index, 1, (uint32_t)records,
6686
6837
                                         &quick->mrr_buf_size,
6687
6838
                                         &quick->mrr_flags, &cost))
6688
6839
    goto err;
6695
6846
 
6696
6847
 
6697
6848
/*
6698
 
  Perform key scans for all used indexes (except CPK), get rowids and merge 
 
6849
  Perform key scans for all used indexes (except CPK), get rowids and merge
6699
6850
  them into an ordered non-recurrent sequence of rowids.
6700
 
  
 
6851
 
6701
6852
  The merge/duplicate removal is performed using Unique class. We put all
6702
6853
  rowids into Unique, get the sorted sequence and destroy the Unique.
6703
 
  
 
6854
 
6704
6855
  If table has a clustered primary key that covers all rows (true for bdb
6705
6856
  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 
 
6857
  then rows that will be retrieved by PK scan are not put into Unique and
6707
6858
  primary key scan is not performed here, it is performed later separately.
6708
6859
 
6709
6860
  RETURN
6725
6876
  cur_quick_it.rewind();
6726
6877
  cur_quick= cur_quick_it++;
6727
6878
  assert(cur_quick != 0);
6728
 
  
 
6879
 
6729
6880
  /*
6730
 
    We reuse the same instance of handler so we need to call both init and 
 
6881
    We reuse the same instance of handler so we need to call both init and
6731
6882
    reset here.
6732
6883
  */
6733
6884
  if (cur_quick->init() || cur_quick->reset())
6734
 
    return(1);
 
6885
    return 0;
6735
6886
 
6736
6887
  unique= new Unique(refpos_order_cmp, (void *)file,
6737
6888
                     file->ref_length,
6738
 
                     thd->variables.sortbuff_size);
 
6889
                     session->variables.sortbuff_size);
6739
6890
  if (!unique)
6740
 
    return(1);
 
6891
    return 0;
6741
6892
  for (;;)
6742
6893
  {
6743
6894
    while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6747
6898
      if (!cur_quick)
6748
6899
        break;
6749
6900
 
6750
 
      if (cur_quick->file->inited != handler::NONE) 
 
6901
      if (cur_quick->file->inited != handler::NONE)
6751
6902
        cur_quick->file->ha_index_end();
6752
6903
      if (cur_quick->init() || cur_quick->reset())
6753
 
        return(1);
 
6904
        return 0;
6754
6905
    }
6755
6906
 
6756
6907
    if (result)
6758
6909
      if (result != HA_ERR_END_OF_FILE)
6759
6910
      {
6760
6911
        cur_quick->range_end();
6761
 
        return(result);
 
6912
        return result;
6762
6913
      }
6763
6914
      break;
6764
6915
    }
6765
6916
 
6766
 
    if (thd->killed)
6767
 
      return(1);
 
6917
    if (session->killed)
 
6918
      return 0;
6768
6919
 
6769
6920
    /* skip row if it will be retrieved by clustered PK scan */
6770
6921
    if (pk_quick_select && pk_quick_select->row_in_ranges())
6773
6924
    cur_quick->file->position(cur_quick->record);
6774
6925
    result= unique->unique_add((char*)cur_quick->file->ref);
6775
6926
    if (result)
6776
 
      return(1);
 
6927
      return 0;
6777
6928
 
6778
6929
  }
6779
6930
 
6784
6935
  /* index_merge currently doesn't support "using index" at all */
6785
6936
  file->extra(HA_EXTRA_NO_KEYREAD);
6786
6937
  /* start table scan */
6787
 
  init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6788
 
  return(result);
 
6938
  init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
 
6939
  return result;
6789
6940
}
6790
6941
 
6791
6942
 
6815
6966
      doing_pk_scan= true;
6816
6967
      if ((result= pk_quick_select->init()) ||
6817
6968
          (result= pk_quick_select->reset()))
6818
 
        return(result);
 
6969
        return result;
6819
6970
      return(pk_quick_select->get_next());
6820
6971
    }
6821
6972
  }
6822
6973
 
6823
 
  return(result);
 
6974
  return result;
6824
6975
}
6825
6976
 
6826
6977
 
6939
7090
  {
6940
7091
    do
6941
7092
    {
6942
 
      if (!queue.elements)
 
7093
      if (queue->empty())
6943
7094
        return(HA_ERR_END_OF_FILE);
6944
7095
      /* Ok, we have a queue with >= 1 scans */
6945
7096
 
6946
 
      quick= (QUICK_SELECT_I*)queue_top(&queue);
 
7097
      quick= queue->top();
6947
7098
      memcpy(cur_rowid, quick->last_rowid, rowid_length);
6948
7099
 
6949
7100
      /* put into queue rowid from the same stream as top element */
6951
7102
      {
6952
7103
        if (error != HA_ERR_END_OF_FILE)
6953
7104
          return(error);
6954
 
        queue_remove(&queue, 0);
 
7105
        queue->pop();
6955
7106
      }
6956
7107
      else
6957
7108
      {
6958
7109
        quick->save_last_pos();
6959
 
        queue_replaced(&queue);
 
7110
        queue->pop();
 
7111
        queue->push(quick);
6960
7112
      }
6961
7113
 
6962
7114
      if (!have_prev_rowid)
6990
7142
 
6991
7143
  if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6992
7144
    return(error);
6993
 
 
 
7145
 
6994
7146
  /* Allocate buffer if we need one but haven't allocated it yet */
6995
7147
  if (mrr_buf_size && !mrr_buf_desc)
6996
7148
  {
7014
7166
 
7015
7167
  if (!mrr_buf_desc)
7016
7168
    empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7017
 
 
 
7169
 
7018
7170
  if (sorted)
7019
7171
     mrr_flags |= HA_MRR_SORTED;
7020
7172
  RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7021
7173
  error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7022
 
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc: 
 
7174
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc:
7023
7175
                                                              &empty_buf);
7024
7176
  return(error);
7025
7177
}
7027
7179
 
7028
7180
/*
7029
7181
  Range sequence interface implementation for array<QUICK_RANGE>: initialize
7030
 
  
 
7182
 
7031
7183
  SYNOPSIS
7032
7184
    quick_range_seq_init()
7033
7185
      init_param  Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
7034
7186
      n_ranges    Number of ranges in the sequence (ignored)
7035
 
      flags       MRR flags (currently not used) 
 
7187
      flags       MRR flags (currently not used)
7036
7188
 
7037
7189
  RETURN
7038
7190
    Opaque value to be passed to quick_range_seq_next
7039
7191
*/
7040
7192
 
7041
 
range_seq_t quick_range_seq_init(void *init_param,
7042
 
                                 uint32_t n_ranges __attribute__((unused)),
7043
 
                                 uint32_t flags __attribute__((unused)))
 
7193
range_seq_t quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7044
7194
{
7045
7195
  QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7046
7196
  quick->qr_traversal_ctx.first=  (QUICK_RANGE**)quick->ranges.buffer;
7053
7203
 
7054
7204
/*
7055
7205
  Range sequence interface implementation for array<QUICK_RANGE>: get next
7056
 
  
 
7206
 
7057
7207
  SYNOPSIS
7058
7208
    quick_range_seq_next()
7059
7209
      rseq        Value returned from quick_range_seq_init
7097
7247
 
7098
7248
 
7099
7249
/*
7100
 
  MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7101
 
 
7102
 
  SYNOPSIS
7103
 
    mrr_persistent_flag_storage()
7104
 
      seq  Range sequence being traversed
7105
 
      idx  Number of range
7106
 
 
7107
 
  DESCRIPTION
7108
 
    MRR/NDB implementation needs to store some bits for each range. This
7109
 
    function returns a reference to the "range_flag" associated with the
7110
 
    range number idx.
7111
 
 
7112
 
    This function should be removed when we get a proper MRR/NDB 
7113
 
    implementation.
7114
 
 
7115
 
  RETURN
7116
 
    Reference to range_flag associated with range number #idx
7117
 
*/
7118
 
 
7119
 
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7120
 
{
7121
 
  QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7122
 
  return ctx->first[idx]->flag;
7123
 
}
7124
 
 
7125
 
 
7126
 
/*
7127
 
  MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7128
 
 
7129
 
  SYNOPSIS
7130
 
    mrr_get_ptr_by_idx()
7131
 
      seq  Range sequence bening traversed
7132
 
      idx  Number of the range
7133
 
 
7134
 
  DESCRIPTION
7135
 
    An extension of MRR range sequence interface needed by NDB: return the
7136
 
    data associated with the given range.
7137
 
 
7138
 
    A proper MRR interface implementer is supposed to store and return
7139
 
    range-associated data. NDB stores number of the range instead. So this
7140
 
    is a helper function that translates range number to range associated
7141
 
    data.
7142
 
 
7143
 
    This function does nothing, as currrently there is only one user of the
7144
 
    MRR interface - the quick range select code, and this user doesn't need
7145
 
    to use range-associated data.
7146
 
 
7147
 
  RETURN
7148
 
    Reference to range-associated data
7149
 
*/
7150
 
 
7151
 
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7152
 
                          uint32_t idx __attribute__((unused)))
7153
 
{
7154
 
  static char *dummy;
7155
 
  return dummy;
7156
 
}
7157
 
 
7158
 
 
7159
 
/*
7160
7250
  Get next possible record using quick-struct.
7161
7251
 
7162
7252
  SYNOPSIS
7180
7270
      We don't need to signal the bitmap change as the bitmap is always the
7181
7271
      same for this head->file
7182
7272
    */
7183
 
    head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
 
7273
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
7184
7274
  }
7185
7275
 
7186
7276
  int result= file->multi_range_read_next(&dummy);
7188
7278
  if (in_ror_merged_scan)
7189
7279
  {
7190
7280
    /* Restore bitmaps set on entry */
7191
 
    head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
 
7281
    head->column_bitmaps_set(save_read_set, save_write_set);
7192
7282
  }
7193
 
  return(result);
 
7283
  return result;
7194
7284
}
7195
7285
 
7196
7286
 
7237
7327
      result= file->index_read_map(record, cur_prefix, keypart_map,
7238
7328
                                   HA_READ_AFTER_KEY);
7239
7329
      if (result || (file->compare_key(file->end_range) <= 0))
7240
 
        return(result);
 
7330
        return result;
7241
7331
    }
7242
7332
 
7243
7333
    uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7245
7335
    {
7246
7336
      /* Ranges have already been used up before. None is left for read. */
7247
7337
      last_range= 0;
7248
 
      return(HA_ERR_END_OF_FILE);
 
7338
      return HA_ERR_END_OF_FILE;
7249
7339
    }
7250
7340
    last_range= *(cur_range++);
7251
7341
 
7252
7342
    start_key.key=    (const unsigned char*) last_range->min_key;
7253
 
    start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
 
7343
    start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
7254
7344
    start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7255
7345
    start_key.flag=   ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7256
7346
                       (last_range->flag & EQ_RANGE) ?
7257
7347
                       HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7258
7348
    end_key.key=      (const unsigned char*) last_range->max_key;
7259
 
    end_key.length=   cmin(last_range->max_length, (uint16_t)prefix_length);
 
7349
    end_key.length=   min(last_range->max_length, (uint16_t)prefix_length);
7260
7350
    end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7261
7351
    /*
7262
7352
      We use READ_AFTER_KEY here because if we are reading on a key
7273
7363
      last_range= 0;                    // Stop searching
7274
7364
 
7275
7365
    if (result != HA_ERR_END_OF_FILE)
7276
 
      return(result);
 
7366
      return result;
7277
7367
    last_range= 0;                      // No matching rows; go to next range
7278
7368
  }
7279
7369
}
7329
7419
  for now, this seems to work right at least.
7330
7420
 */
7331
7421
 
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)))
 
7422
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7335
7423
 :QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7336
7424
{
7337
7425
  QUICK_RANGE *r;
7379
7467
      if (!result)
7380
7468
      {
7381
7469
        if (cmp_prev(*rev_it.ref()) == 0)
7382
 
          return(0);
 
7470
          return 0;
7383
7471
      }
7384
7472
      else if (result != HA_ERR_END_OF_FILE)
7385
 
        return(result);
 
7473
        return result;
7386
7474
    }
7387
7475
 
7388
7476
    if (!(last_range= rev_it++))
7389
 
      return(HA_ERR_END_OF_FILE);               // All ranges used
 
7477
      return HA_ERR_END_OF_FILE;                // All ranges used
7390
7478
 
7391
7479
    if (last_range->flag & NO_MAX_RANGE)        // Read last record
7392
7480
    {
7394
7482
      if ((local_error=file->index_last(record)))
7395
7483
        return(local_error);            // Empty table
7396
7484
      if (cmp_prev(last_range) == 0)
7397
 
        return(0);
 
7485
        return 0;
7398
7486
      last_range= 0;                            // No match; go to next range
7399
7487
      continue;
7400
7488
    }
7418
7506
    if (result)
7419
7507
    {
7420
7508
      if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7421
 
        return(result);
 
7509
        return result;
7422
7510
      last_range= 0;                            // Not found, to next range
7423
7511
      continue;
7424
7512
    }
7426
7514
    {
7427
7515
      if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7428
7516
        last_range= 0;                          // Stop searching
7429
 
      return(0);                                // Found key is in range
 
7517
      return 0;                         // Found key is in range
7430
7518
    }
7431
7519
    last_range= 0;                              // To next range
7432
7520
  }
7436
7524
/*
7437
7525
  Compare if found key is over max-value
7438
7526
  Returns 0 if key <= range->max_key
7439
 
  TODO: Figure out why can't this function be as simple as cmp_prev(). 
 
7527
  TODO: Figure out why can't this function be as simple as cmp_prev().
7440
7528
*/
7441
7529
 
7442
7530
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7686
7774
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7687
7775
                       KEY_PART_INFO *first_non_group_part,
7688
7776
                       KEY_PART_INFO *min_max_arg_part,
7689
 
                       KEY_PART_INFO *last_part, THD *thd,
 
7777
                       KEY_PART_INFO *last_part, Session *session,
7690
7778
                       unsigned char *key_infix, uint32_t *key_infix_len,
7691
7779
                       KEY_PART_INFO **first_non_infix_part);
7692
 
static bool
7693
 
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7694
 
                               Field::imagetype image_type);
 
7780
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7695
7781
 
7696
7782
static void
7697
7783
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7729
7815
        - NGA = QA - (GA union C) = {NG_1, ..., NG_m} - the ones not in
7730
7816
          GROUP BY and not referenced by MIN/MAX functions.
7731
7817
        with the following properties specified below.
7732
 
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not 
 
7818
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
7733
7819
        applicable.
7734
7820
 
7735
7821
    SA1. There is at most one attribute in SA referenced by any number of
7817
7903
    other field as in: "select min(a) from t1 group by a" ?
7818
7904
  - We assume that the general correctness of the GROUP-BY query was checked
7819
7905
    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 
 
7906
  - Lift the limitation in condition (B3), that is, make this access method
7821
7907
    applicable to ROLLUP queries.
7822
7908
 
7823
7909
  RETURN
7832
7918
static TRP_GROUP_MIN_MAX *
7833
7919
get_best_group_min_max(PARAM *param, SEL_TREE *tree)
7834
7920
{
7835
 
  THD *thd= param->thd;
7836
 
  JOIN *join= thd->lex->current_select->join;
 
7921
  Session *session= param->session;
 
7922
  JOIN *join= session->lex->current_select->join;
7837
7923
  Table *table= param->table;
7838
7924
  bool have_min= false;              /* true if there is a MIN function. */
7839
7925
  bool have_max= false;              /* true if there is a MAX function. */
7854
7940
 
7855
7941
  /* Perform few 'cheap' tests whether this access method is applicable. */
7856
7942
  if (!join)
7857
 
    return(NULL);        /* This is not a select statement. */
 
7943
    return NULL;        /* This is not a select statement. */
7858
7944
  if ((join->tables != 1) ||  /* The query must reference one table. */
7859
7945
      ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
7860
7946
       (!join->select_distinct)) ||
7861
7947
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
7862
 
    return(NULL);
 
7948
    return NULL;
7863
7949
  if (table->s->keys == 0)        /* There are no indexes to use. */
7864
 
    return(NULL);
 
7950
    return NULL;
7865
7951
 
7866
7952
  /* Analyze the query in more detail. */
7867
7953
  List_iterator<Item> select_items_it(join->fields_list);
7868
7954
 
7869
7955
  /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
7870
7956
  if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
7871
 
    return(NULL);
 
7957
    return NULL;
7872
7958
  if (join->sum_funcs[0])
7873
7959
  {
7874
7960
    Item_sum *min_max_item;
7880
7966
      else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
7881
7967
        have_max= true;
7882
7968
      else
7883
 
        return(NULL);
 
7969
        return NULL;
7884
7970
 
7885
7971
      /* The argument of MIN/MAX. */
7886
 
      Item *expr= min_max_item->args[0]->real_item();    
 
7972
      Item *expr= min_max_item->args[0]->real_item();
7887
7973
      if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */
7888
7974
      {
7889
7975
        if (! min_max_arg_item)
7890
7976
          min_max_arg_item= (Item_field*) expr;
7891
7977
        else if (! min_max_arg_item->eq(expr, 1))
7892
 
          return(NULL);
 
7978
          return NULL;
7893
7979
      }
7894
7980
      else
7895
 
        return(NULL);
 
7981
        return NULL;
7896
7982
    }
7897
7983
  }
7898
7984
 
7902
7988
    while ((item= select_items_it++))
7903
7989
    {
7904
7990
      if (item->type() != Item::FIELD_ITEM)
7905
 
        return(NULL);
 
7991
        return NULL;
7906
7992
    }
7907
7993
  }
7908
7994
 
7910
7996
  for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
7911
7997
  {
7912
7998
    if ((*tmp_group->item)->type() != Item::FIELD_ITEM)
7913
 
      return(NULL);
 
7999
      return NULL;
7914
8000
  }
7915
8001
 
7916
8002
  /*
7940
8026
  SEL_ARG *cur_index_tree= NULL;
7941
8027
  ha_rows cur_quick_prefix_records= 0;
7942
8028
  uint32_t cur_param_idx=MAX_KEY;
7943
 
  key_map cur_used_key_parts;
 
8029
  key_map used_key_parts_map;
 
8030
  uint32_t cur_key_infix_len= 0;
 
8031
  unsigned char cur_key_infix[MAX_KEY_LENGTH];
 
8032
  uint32_t cur_used_key_parts= 0;
7944
8033
  uint32_t pk= param->table->s->primary_key;
7945
8034
 
7946
8035
  for (uint32_t cur_index= 0 ; cur_index_info != cur_index_info_end ;
7947
8036
       cur_index_info++, cur_index++)
7948
8037
  {
7949
8038
    /* Check (B1) - if current index is covering. */
7950
 
    if (!table->covering_keys.is_set(cur_index))
 
8039
    if (!table->covering_keys.test(cur_index))
7951
8040
      goto next_index;
7952
8041
 
7953
8042
    /*
7970
8059
          If the field is used in the current query ensure that it's
7971
8060
          part of 'cur_index'
7972
8061
        */
7973
 
        if (bitmap_is_set(table->read_set, cur_field->field_index) &&
7974
 
            !cur_field->part_of_key_not_clustered.is_set(cur_index))
 
8062
        if ((cur_field->isReadSet()) &&
 
8063
            !cur_field->part_of_key_not_clustered.test(cur_index))
7975
8064
          goto next_index;                  // Field was not part of key
7976
8065
      }
7977
8066
    }
8015
8104
    else if (join->select_distinct)
8016
8105
    {
8017
8106
      select_items_it.rewind();
8018
 
      cur_used_key_parts.clear_all();
 
8107
      used_key_parts_map.reset();
8019
8108
      uint32_t max_key_part= 0;
8020
8109
      while ((item= select_items_it++))
8021
8110
      {
8026
8115
          Check if this attribute was already present in the select list.
8027
8116
          If it was present, then its corresponding key part was alredy used.
8028
8117
        */
8029
 
        if (cur_used_key_parts.is_set(key_part_nr))
 
8118
        if (used_key_parts_map.test(key_part_nr))
8030
8119
          continue;
8031
8120
        if (key_part_nr < 1 || key_part_nr > join->fields_list.elements)
8032
8121
          goto next_index;
8033
8122
        cur_part= cur_index_info->key_part + key_part_nr - 1;
8034
8123
        cur_group_prefix_len+= cur_part->store_length;
8035
 
        cur_used_key_parts.set_bit(key_part_nr);
 
8124
        used_key_parts_map.set(key_part_nr);
8036
8125
        ++cur_group_key_parts;
8037
 
        max_key_part= cmax(max_key_part,key_part_nr);
 
8126
        max_key_part= max(max_key_part,key_part_nr);
8038
8127
      }
8039
8128
      /*
8040
8129
        Check that used key parts forms a prefix of the index.
8042
8131
        all_parts have all bits set from 0 to (max_key_part-1).
8043
8132
        cur_parts have bits set for only used keyparts.
8044
8133
      */
8045
 
      uint64_t all_parts, cur_parts;
8046
 
      all_parts= (1<<max_key_part) - 1;
8047
 
      cur_parts= cur_used_key_parts.to_uint64_t() >> 1;
 
8134
      key_map all_parts, cur_parts;
 
8135
      for (uint32_t pos= 0; pos < max_key_part; pos++)
 
8136
        all_parts.set(pos);
 
8137
      cur_parts= used_key_parts_map >> 1;
8048
8138
      if (all_parts != cur_parts)
8049
8139
        goto next_index;
8050
8140
    }
8094
8184
                                                        &dummy);
8095
8185
        if (!get_constant_key_infix(cur_index_info, index_range_tree,
8096
8186
                                    first_non_group_part, min_max_arg_part,
8097
 
                                    last_part, thd, key_infix, &key_infix_len,
 
8187
                                    last_part, session, cur_key_infix, 
 
8188
                                    &cur_key_infix_len,
8098
8189
                                    &first_non_infix_part))
8099
8190
          goto next_index;
8100
8191
      }
8142
8233
                (min_max_arg_part && (min_max_arg_part < last_part));
8143
8234
      for (; cur_part != last_part; cur_part++)
8144
8235
      {
8145
 
        if (bitmap_is_set(table->read_set, cur_part->field->field_index))
 
8236
        if (cur_part->field->isReadSet())
8146
8237
          goto next_index;
8147
8238
      }
8148
8239
    }
8149
8240
 
8150
8241
    /* If we got to this point, cur_index_info passes the test. */
8151
 
    key_infix_parts= key_infix_len ?
 
8242
    key_infix_parts= cur_key_infix_len ?
8152
8243
                     (first_non_infix_part - first_non_group_part) : 0;
8153
 
    used_key_parts= cur_group_key_parts + key_infix_parts;
 
8244
    cur_used_key_parts= cur_group_key_parts + key_infix_parts;
8154
8245
 
8155
8246
    /* Compute the cost of using this index. */
8156
8247
    if (tree)
8162
8253
      COST_VECT dummy_cost;
8163
8254
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
8164
8255
      uint32_t mrr_bufsize=0;
8165
 
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx, 
8166
 
                                                   false /*don't care*/, 
 
8256
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
 
8257
                                                   false /*don't care*/,
8167
8258
                                                   cur_index_tree, true,
8168
8259
                                                   &mrr_flags, &mrr_bufsize,
8169
8260
                                                   &dummy_cost);
8170
8261
    }
8171
 
    cost_group_min_max(table, cur_index_info, used_key_parts,
 
8262
    cost_group_min_max(table, cur_index_info, cur_used_key_parts,
8172
8263
                       cur_group_key_parts, tree, cur_index_tree,
8173
8264
                       cur_quick_prefix_records, have_min, have_max,
8174
8265
                       &cur_read_cost, &cur_records);
8189
8280
      best_param_idx= cur_param_idx;
8190
8281
      group_key_parts= cur_group_key_parts;
8191
8282
      group_prefix_len= cur_group_prefix_len;
 
8283
      key_infix_len= cur_key_infix_len;
 
8284
      if (key_infix_len)
 
8285
        memcpy (key_infix, cur_key_infix, sizeof (key_infix));
 
8286
      used_key_parts= cur_used_key_parts;
8192
8287
    }
8193
8288
 
8194
8289
  next_index:
8195
8290
    cur_group_key_parts= 0;
8196
8291
    cur_group_prefix_len= 0;
 
8292
    cur_key_infix_len= 0;
8197
8293
  }
8198
8294
  if (!index_info) /* No usable index found. */
8199
 
    return(NULL);
 
8295
    return NULL;
8200
8296
 
8201
8297
  /* Check (SA3) for the where clause. */
8202
8298
  if (join->conds && min_max_arg_item &&
8203
 
      !check_group_min_max_predicates(join->conds, min_max_arg_item, Field::itRAW))
8204
 
    return(NULL);
 
8299
      ! check_group_min_max_predicates(join->conds, min_max_arg_item))
 
8300
    return NULL;
8205
8301
 
8206
8302
  /* The query passes all tests, so construct a new TRP object. */
8207
8303
  read_plan= new (param->mem_root)
8215
8311
  if (read_plan)
8216
8312
  {
8217
8313
    if (tree && read_plan->quick_prefix_records == 0)
8218
 
      return(NULL);
 
8314
      return NULL;
8219
8315
 
8220
8316
    read_plan->read_cost= best_read_cost;
8221
8317
    read_plan->records=   best_records;
8222
8318
  }
8223
8319
 
8224
 
  return(read_plan);
 
8320
  return read_plan;
8225
8321
}
8226
8322
 
8227
8323
 
8246
8342
    true  if cond passes the test
8247
8343
    false o/w
8248
8344
*/
8249
 
 
8250
 
static bool
8251
 
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
8252
 
                               Field::imagetype image_type)
 
8345
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item)
8253
8346
{
8254
8347
  assert(cond && min_max_arg_item);
8255
8348
 
8261
8354
    Item *and_or_arg;
8262
8355
    while ((and_or_arg= li++))
8263
8356
    {
8264
 
      if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,
8265
 
                                         image_type))
8266
 
        return(false);
 
8357
      if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item))
 
8358
        return false;
8267
8359
    }
8268
 
    return(true);
 
8360
    return true;
8269
8361
  }
8270
8362
 
8271
8363
  /*
8278
8370
    so.
8279
8371
  */
8280
8372
  if (cond_type == Item::SUBSELECT_ITEM)
8281
 
    return(false);
8282
 
  
 
8373
    return false;
 
8374
 
8283
8375
  /* We presume that at this point there are no other Items than functions. */
8284
8376
  assert(cond_type == Item::FUNC_ITEM);
8285
8377
 
8292
8384
    cur_arg= arguments[arg_idx]->real_item();
8293
8385
    if (cur_arg->type() == Item::FIELD_ITEM)
8294
8386
    {
8295
 
      if (min_max_arg_item->eq(cur_arg, 1)) 
 
8387
      if (min_max_arg_item->eq(cur_arg, 1))
8296
8388
      {
8297
8389
       /*
8298
8390
         If pred references the MIN/MAX argument, check whether pred is a range
8309
8401
            pred_type != Item_func::ISNOTNULL_FUNC &&
8310
8402
            pred_type != Item_func::EQ_FUNC        &&
8311
8403
            pred_type != Item_func::NE_FUNC)
8312
 
          return(false);
 
8404
          return false;
8313
8405
 
8314
8406
        /* Check that pred compares min_max_arg_item with a constant. */
8315
8407
        Item *args[3];
8317
8409
        bool inv;
8318
8410
        /* Test if this is a comparison of a field and a constant. */
8319
8411
        if (!simple_pred(pred, args, &inv))
8320
 
          return(false);
 
8412
          return false;
8321
8413
 
8322
8414
        /* Check for compatible string comparisons - similar to get_mm_leaf. */
8323
8415
        if (args[0] && args[1] && !args[2] && // this is a binary function
8326
8418
              Don't use an index when comparing strings of different collations.
8327
8419
            */
8328
8420
            ((args[1]->result_type() == STRING_RESULT &&
8329
 
              image_type == Field::itRAW &&
8330
8421
              ((Field_str*) min_max_arg_item->field)->charset() !=
8331
8422
              pred->compare_collation())
8332
8423
             ||
8336
8427
             */
8337
8428
             (args[1]->result_type() != STRING_RESULT &&
8338
8429
              min_max_arg_item->field->cmp_type() != args[1]->result_type())))
8339
 
          return(false);
 
8430
          return false;
8340
8431
      }
8341
8432
    }
8342
8433
    else if (cur_arg->type() == Item::FUNC_ITEM)
8343
8434
    {
8344
 
      if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,
8345
 
                                         image_type))
8346
 
        return(false);
 
8435
      if (! check_group_min_max_predicates(cur_arg, min_max_arg_item))
 
8436
        return false;
8347
8437
    }
8348
8438
    else if (cur_arg->const_item())
8349
8439
    {
8350
 
      return(true);
 
8440
      return true;
8351
8441
    }
8352
8442
    else
8353
 
      return(false);
 
8443
      return false;
8354
8444
  }
8355
8445
 
8356
 
  return(true);
 
8446
  return true;
8357
8447
}
8358
8448
 
8359
8449
 
8367
8457
    first_non_group_part   [in]  First index part after group attribute parts
8368
8458
    min_max_arg_part       [in]  The keypart of the MIN/MAX argument if any
8369
8459
    last_part              [in]  Last keypart of the index
8370
 
    thd                    [in]  Current thread
 
8460
    session                    [in]  Current thread
8371
8461
    key_infix              [out] Infix of constants to be used for index lookup
8372
8462
    key_infix_len          [out] Lenghth of the infix
8373
8463
    first_non_infix_part   [out] The first keypart after the infix (if any)
8374
 
    
 
8464
 
8375
8465
  DESCRIPTION
8376
8466
    Test conditions (NGA1, NGA2) from get_best_group_min_max(). Namely,
8377
8467
    for each keypart field NGF_i not in GROUP-BY, check that there is a
8389
8479
*/
8390
8480
 
8391
8481
static bool
8392
 
get_constant_key_infix(KEY *index_info __attribute__((unused)),
8393
 
                       SEL_ARG *index_range_tree,
 
8482
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
8394
8483
                       KEY_PART_INFO *first_non_group_part,
8395
8484
                       KEY_PART_INFO *min_max_arg_part,
8396
8485
                       KEY_PART_INFO *last_part,
8397
 
                       THD *thd __attribute__((unused)),
8398
 
                       unsigned char *key_infix, uint32_t *key_infix_len,
 
8486
                       Session *, unsigned char *key_infix, uint32_t *key_infix_len,
8399
8487
                       KEY_PART_INFO **first_non_infix_part)
8400
8488
{
8401
8489
  SEL_ARG       *cur_range;
8522
8610
    idx++;
8523
8611
  }
8524
8612
  *param_idx= idx;
8525
 
  return(range_tree->keys[idx]);
 
8613
  return range_tree->keys[idx];
8526
8614
}
8527
8615
 
8528
8616
 
8588
8676
 
8589
8677
void cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
8590
8678
                        uint32_t group_key_parts, SEL_TREE *range_tree,
8591
 
                        SEL_ARG *index_tree __attribute__((unused)),
8592
 
                        ha_rows quick_prefix_records,
 
8679
                        SEL_ARG *, ha_rows quick_prefix_records,
8593
8680
                        bool have_min, bool have_max,
8594
8681
                        double *read_cost, ha_rows *records)
8595
8682
{
8609
8696
  keys_per_block= (table->file->stats.block_size / 2 /
8610
8697
                   (index_info->key_length + table->file->ref_length)
8611
8698
                        + 1);
8612
 
  num_blocks= (uint)(table_records / keys_per_block) + 1;
 
8699
  num_blocks= (uint32_t)(table_records / keys_per_block) + 1;
8613
8700
 
8614
8701
  /* Compute the number of keys in a group. */
8615
8702
  keys_per_group= index_info->rec_per_key[group_key_parts - 1];
8616
8703
  if (keys_per_group == 0) /* If there is no statistics try to guess */
8617
8704
    /* 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;
 
8705
    keys_per_group= (uint32_t)(table_records / 10) + 1;
 
8706
  num_groups= (uint32_t)(table_records / keys_per_group) + 1;
8620
8707
 
8621
8708
  /* Apply the selectivity of the quick select for group prefixes. */
8622
8709
  if (range_tree && (quick_prefix_records != HA_POS_ERROR))
8623
8710
  {
8624
8711
    quick_prefix_selectivity= (double) quick_prefix_records /
8625
8712
                              (double) table_records;
8626
 
    num_groups= (uint) rint(num_groups * quick_prefix_selectivity);
8627
 
    set_if_bigger(num_groups, 1);
 
8713
    num_groups= (uint32_t) rint(num_groups * quick_prefix_selectivity);
 
8714
    set_if_bigger(num_groups, 1U);
8628
8715
  }
8629
8716
 
8630
8717
  if (used_key_parts > group_key_parts)
8639
8726
    {
8640
8727
      double blocks_per_group= (double) num_blocks / (double) num_groups;
8641
8728
      p_overlap= (blocks_per_group * (keys_per_subgroup - 1)) / keys_per_group;
8642
 
      p_overlap= cmin(p_overlap, 1.0);
 
8729
      p_overlap= min(p_overlap, 1.0);
8643
8730
    }
8644
 
    io_cost= (double) cmin(num_groups * (1 + p_overlap), (double)num_blocks);
 
8731
    io_cost= (double) min(num_groups * (1 + p_overlap), (double)num_blocks);
8645
8732
  }
8646
8733
  else
8647
8734
    io_cost= (keys_per_group > keys_per_block) ?
8658
8745
 
8659
8746
  *read_cost= io_cost + cpu_cost;
8660
8747
  *records= num_groups;
8661
 
  return;
8662
8748
}
8663
8749
 
8664
8750
 
8684
8770
*/
8685
8771
 
8686
8772
QUICK_SELECT_I *
8687
 
TRP_GROUP_MIN_MAX::make_quick(PARAM *param,
8688
 
                              bool retrieve_full_rows __attribute__((unused)),
8689
 
                              MEM_ROOT *parent_alloc)
 
8773
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
8690
8774
{
8691
8775
  QUICK_GROUP_MIN_MAX_SELECT *quick;
8692
8776
 
8693
8777
  quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table,
8694
 
                                        param->thd->lex->current_select->join,
 
8778
                                        param->session->lex->current_select->join,
8695
8779
                                        have_min, have_max, min_max_arg_part,
8696
8780
                                        group_prefix_len, group_key_parts,
8697
8781
                                        used_key_parts, index_info, index,
8698
8782
                                        read_cost, records, key_infix_len,
8699
8783
                                        key_infix, parent_alloc);
8700
8784
  if (!quick)
8701
 
    return(NULL);
 
8785
    return NULL;
8702
8786
 
8703
8787
  if (quick->init())
8704
8788
  {
8705
8789
    delete quick;
8706
 
    return(NULL);
 
8790
    return NULL;
8707
8791
  }
8708
8792
 
8709
8793
  if (range_tree)
8742
8826
        {
8743
8827
          delete quick;
8744
8828
          quick= NULL;
8745
 
          return(NULL);
 
8829
          return NULL;
8746
8830
        }
8747
8831
        min_max_range= min_max_range->next;
8748
8832
      }
8754
8838
  quick->update_key_stat();
8755
8839
  quick->adjust_prefix_ranges();
8756
8840
 
8757
 
  return(quick);
 
8841
  return quick;
8758
8842
}
8759
8843
 
8760
8844
 
8819
8903
  assert(!parent_alloc);
8820
8904
  if (!parent_alloc)
8821
8905
  {
8822
 
    init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8823
 
    join->thd->mem_root= &alloc;
 
8906
    init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
 
8907
    join->session->mem_root= &alloc;
8824
8908
  }
8825
8909
  else
8826
8910
    memset(&alloc, 0, sizeof(MEM_ROOT));  // ensure that it's not used
8832
8916
 
8833
8917
  SYNOPSIS
8834
8918
    QUICK_GROUP_MIN_MAX_SELECT::init()
8835
 
  
 
8919
 
8836
8920
  DESCRIPTION
8837
8921
    The method performs initialization that cannot be done in the constructor
8838
8922
    such as memory allocations that may fail. It allocates memory for the
8923
9007
 
8924
9008
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8925
9009
{
8926
 
  if (file->inited != handler::NONE) 
 
9010
  if (file->inited != handler::NONE)
8927
9011
    file->ha_index_end();
8928
9012
  if (min_max_arg_part)
8929
9013
    delete_dynamic(&min_max_ranges);
8931
9015
  delete min_functions_it;
8932
9016
  delete max_functions_it;
8933
9017
  delete quick_prefix_select;
8934
 
  return; 
8935
9018
}
8936
9019
 
8937
9020
 
8940
9023
 
8941
9024
  SYNOPSIS
8942
9025
    QUICK_GROUP_MIN_MAX_SELECT::add_range()
8943
 
    sel_range  Range object from which a 
 
9026
    sel_range  Range object from which a
8944
9027
 
8945
9028
  NOTES
8946
9029
    Construct a new QUICK_RANGE object from a SEL_ARG object, and
8994
9077
 
8995
9078
  NOTES
8996
9079
    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 
 
9080
    It defines a number of ranges of length x.
 
9081
    However when jumping through the prefixes we use only the the first
8999
9082
    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 
 
9083
    are more keyparts to follow the ones we are using we must make the
 
9084
    condition on the key inclusive (because x < "ab" means
9002
9085
    x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9003
9086
    To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9004
9087
*/
9108
9191
 
9109
9192
  file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9110
9193
  if ((result= file->ha_index_init(index,1)))
9111
 
    return(result);
 
9194
    return result;
9112
9195
  if (quick_prefix_select && quick_prefix_select->reset())
9113
 
    return(1);
 
9196
    return 0;
9114
9197
  result= file->index_last(record);
9115
9198
  if (result == HA_ERR_END_OF_FILE)
9116
 
    return(0);
 
9199
    return 0;
9117
9200
  /* Save the prefix of the last group. */
9118
9201
  key_copy(last_prefix, record, index_info, group_prefix_len);
9119
9202
 
9120
 
  return(0);
 
9203
  return 0;
9121
9204
}
9122
9205
 
9123
9206
 
9124
9207
 
9125
 
/* 
 
9208
/*
9126
9209
  Get the next key containing the MIN and/or MAX key for the next group.
9127
9210
 
9128
9211
  SYNOPSIS
9173
9256
                              group_prefix_len);
9174
9257
      assert(is_last_prefix <= 0);
9175
9258
    }
9176
 
    else 
 
9259
    else
9177
9260
    {
9178
9261
      if (result == HA_ERR_KEY_NOT_FOUND)
9179
9262
        continue;
9194
9277
      if (max_res == 0)
9195
9278
        update_max_result();
9196
9279
      /* 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)));
 
9280
      assert(((have_max && !have_min) ||
 
9281
                  (have_max && have_min && (max_res == 0))));
9199
9282
    }
9200
9283
    /*
9201
9284
      If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9224
9307
  else if (result == HA_ERR_KEY_NOT_FOUND)
9225
9308
    result= HA_ERR_END_OF_FILE;
9226
9309
 
9227
 
  return(result);
 
9310
  return result;
9228
9311
}
9229
9312
 
9230
9313
 
9259
9342
  if (min_max_ranges.elements > 0)
9260
9343
  {
9261
9344
    if ((result= next_min_in_range()))
9262
 
      return(result);
 
9345
      return result;
9263
9346
  }
9264
9347
  else
9265
9348
  {
9269
9352
      if ((result= file->index_read_map(record, group_prefix,
9270
9353
                                        make_prev_keypart_map(real_key_parts),
9271
9354
                                        HA_READ_KEY_EXACT)))
9272
 
        return(result);
 
9355
        return result;
9273
9356
    }
9274
9357
 
9275
9358
    /*
9310
9393
    If the MIN attribute is non-nullable, this->record already contains the
9311
9394
    MIN key in the group, so just return.
9312
9395
  */
9313
 
  return(result);
 
9396
  return result;
9314
9397
}
9315
9398
 
9316
9399
 
9317
 
/* 
 
9400
/*
9318
9401
  Retrieve the maximal key in the next group.
9319
9402
 
9320
9403
  SYNOPSIS
9341
9424
    result= file->index_read_map(record, group_prefix,
9342
9425
                                 make_prev_keypart_map(real_key_parts),
9343
9426
                                 HA_READ_PREFIX_LAST);
9344
 
  return(result);
 
9427
  return result;
9345
9428
}
9346
9429
 
9347
9430
 
9375
9458
    unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9376
9459
    if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9377
9460
                         make_prev_keypart_map(group_key_parts), cur_prefix)))
9378
 
      return(result);
 
9461
      return result;
9379
9462
    seen_first_key= true;
9380
9463
  }
9381
9464
  else
9384
9467
    {
9385
9468
      result= file->index_first(record);
9386
9469
      if (result)
9387
 
        return(result);
 
9470
        return result;
9388
9471
      seen_first_key= true;
9389
9472
    }
9390
9473
    else
9394
9477
                                   make_prev_keypart_map(group_key_parts),
9395
9478
                                   HA_READ_AFTER_KEY);
9396
9479
      if (result)
9397
 
        return(result);
 
9480
        return result;
9398
9481
    }
9399
9482
  }
9400
9483
 
9405
9488
    memcpy(group_prefix + group_prefix_len,
9406
9489
           key_infix, key_infix_len);
9407
9490
 
9408
 
  return(0);
 
9491
  return 0;
9409
9492
}
9410
9493
 
9411
9494
 
9437
9520
  QUICK_RANGE *cur_range;
9438
9521
  bool found_null= false;
9439
9522
  int result= HA_ERR_KEY_NOT_FOUND;
 
9523
  basic_string<unsigned char> max_key;
 
9524
 
 
9525
  max_key.reserve(real_prefix_len + min_max_arg_len);
9440
9526
 
9441
9527
  assert(min_max_ranges.elements > 0);
9442
9528
 
9510
9596
    if ( !(cur_range->flag & NO_MAX_RANGE) )
9511
9597
    {
9512
9598
      /* 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);
 
9599
      max_key.clear();
 
9600
      max_key.append(group_prefix, real_prefix_len);
 
9601
      max_key.append(cur_range->max_key, cur_range->max_length);
9517
9602
      /* Compare the found key with max_key. */
9518
 
      int cmp_res= key_cmp(index_info->key_part, max_key,
 
9603
      int cmp_res= key_cmp(index_info->key_part,
 
9604
                           max_key.data(),
9519
9605
                           real_prefix_len + min_max_arg_len);
9520
 
      if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
 
9606
      if (!(((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
 
9607
            (cmp_res <= 0)))
9521
9608
      {
9522
9609
        result= HA_ERR_KEY_NOT_FOUND;
9523
9610
        continue;
9568
9655
  key_part_map keypart_map;
9569
9656
  QUICK_RANGE *cur_range;
9570
9657
  int result;
 
9658
  basic_string<unsigned char> min_key;
 
9659
  min_key.reserve(real_prefix_len + min_max_arg_len);
9571
9660
 
9572
9661
  assert(min_max_ranges.elements > 0);
9573
9662
 
9627
9716
    if ( !(cur_range->flag & NO_MIN_RANGE) )
9628
9717
    {
9629
9718
      /* 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);
 
9719
      min_key.clear();
 
9720
      min_key.append(group_prefix, real_prefix_len);
 
9721
      min_key.append(cur_range->min_key, cur_range->min_length);
 
9722
 
9634
9723
      /* Compare the found key with min_key. */
9635
 
      int cmp_res= key_cmp(index_info->key_part, min_key,
 
9724
      int cmp_res= key_cmp(index_info->key_part,
 
9725
                           min_key.data(),
9636
9726
                           real_prefix_len + min_max_arg_len);
9637
 
      if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
 
9727
      if (!(((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9638
9728
            (cmp_res >= 0)))
9639
9729
        continue;
9640
9730
    }
9735
9825
  used_lengths->append(buf, length);
9736
9826
}
9737
9827
 
9738
 
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9739
 
                           const char *msg __attribute__((unused)))
 
9828
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9740
9829
{
9741
9830
  SEL_ARG **key,**end;
9742
9831
  int idx;
9748
9837
       key != end ;
9749
9838
       key++,idx++)
9750
9839
  {
9751
 
    if (tree_map->is_set(idx))
 
9840
    if (tree_map->test(idx))
9752
9841
    {
9753
9842
      uint32_t keynr= param->real_keynr[idx];
9754
9843
      if (tmp.length())
9758
9847
  }
9759
9848
  if (!tmp.length())
9760
9849
    tmp.append(STRING_WITH_LEN("(empty)"));
9761
 
 
9762
 
  return;
9763
9850
}
9764
9851
 
9765
9852
 
9766
9853
static void print_ror_scans_arr(Table *table,
9767
 
                                const char *msg __attribute__((unused)),
9768
 
                                struct st_ror_scan_info **start,
 
9854
                                const char *, struct st_ror_scan_info **start,
9769
9855
                                struct st_ror_scan_info **end)
9770
9856
{
9771
9857
  char buff[1024];
9779
9865
  }
9780
9866
  if (!tmp.length())
9781
9867
    tmp.append(STRING_WITH_LEN("(empty)"));
9782
 
  return;
9783
9868
}
9784
9869
 
9785
9870
/*****************************************************************************
9786
 
** Instantiate templates 
 
9871
** Instantiate templates
9787
9872
*****************************************************************************/
9788
9873
 
9789
9874
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION