← Back to branch summary

~drizzle-trunk/drizzle/development

« back to all changes in this revision

Viewing changes to drizzled/opt_range.cc

  • Committer: Stewart Smith
  • Date: 2009-01-12 05:43:13 UTC
  • mto: (784.1.4 for-brian)
  • mto: This revision was merged to the branch mainline in revision 785.
  • Revision ID: stewart@flamingspork.com-20090112054313-edk6kpf4l6kpz4j7
fix archive_basic for drizzle

Show diffs side-by-side

added added

removed removed

Lines of Context:
drizzled/opt_range.cc
25
25
/*
26
26
  This file contains:
27
27
 
28
 
  RangeAnalysisModule  
29
 
    A module that accepts a condition, index (or partitioning) description, 
30
 
    and builds lists of intervals (in index/partitioning space), such that 
31
 
    all possible records that match the condition are contained within the 
 
28
  RangeAnalysisModule
 
29
    A module that accepts a condition, index (or partitioning) description,
 
30
    and builds lists of intervals (in index/partitioning space), such that
 
31
    all possible records that match the condition are contained within the
32
32
    intervals.
33
33
    The entry point for the range analysis module is get_mm_tree() function.
34
 
    
 
34
 
35
35
    The lists are returned in form of complicated structure of interlinked
36
36
    SEL_TREE/SEL_IMERGE/SEL_ARG objects.
37
 
    See quick_range_seq_next, find_used_partitions for examples of how to walk 
 
37
    See quick_range_seq_next, find_used_partitions for examples of how to walk
38
38
    this structure.
39
39
    All direct "users" of this module are located within this file, too.
40
40
 
46
46
    The module has single entry point - prune_partitions() function.
47
47
 
48
48
 
49
 
  Range/index_merge/groupby-minmax optimizer module  
50
 
    A module that accepts a table, condition, and returns 
 
49
  Range/index_merge/groupby-minmax optimizer module
 
50
    A module that accepts a table, condition, and returns
51
51
     - a QUICK_*_SELECT object that can be used to retrieve rows that match
52
 
       the specified condition, or a "no records will match the condition" 
 
52
       the specified condition, or a "no records will match the condition"
53
53
       statement.
54
54
 
55
55
    The module entry points are
64
64
  ~~~~~~~~~~~~~~
65
65
  The code in this file (and elsewhere) makes operations on key value tuples.
66
66
  Those tuples are stored in the following format:
67
 
  
 
67
 
68
68
  The tuple is a sequence of key part values. The length of key part value
69
69
  depends only on its type (and not depends on the what value is stored)
70
 
  
 
70
 
71
71
    KeyTuple: keypart1-data, keypart2-data, ...
72
 
  
 
72
 
73
73
  The value of each keypart is stored in the following format:
74
 
  
 
74
 
75
75
    keypart_data: [isnull_byte] keypart-value-bytes
76
76
 
77
77
  If a keypart may have a NULL value (key_part->field->real_maybe_null() can
78
 
  be used to check this), then the first byte is a NULL indicator with the 
 
78
  be used to check this), then the first byte is a NULL indicator with the
79
79
  following valid values:
80
80
    1  - keypart has NULL value.
81
81
    0  - keypart has non-NULL value.
86
86
 
87
87
  keypart-value-bytes holds the value. Its format depends on the field type.
88
88
  The length of keypart-value-bytes may or may not depend on the value being
89
 
  stored. The default is that length is static and equal to 
 
89
  stored. The default is that length is static and equal to
90
90
  KEY_PART_INFO::length.
91
 
  
92
 
  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the 
 
91
 
 
92
  Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
93
93
  value:
94
 
  
 
94
 
95
95
     keypart-value-bytes: value_length value_bytes
96
96
 
97
97
  The value_length part itself occupies HA_KEY_BLOB_LENGTH=2 bytes.
99
99
  See key_copy() and key_restore() for code to move data between index tuple
100
100
  and table record
101
101
 
102
 
  CAUTION: the above description is only sergefp's understanding of the 
 
102
  CAUTION: the above description is only sergefp's understanding of the
103
103
           subject and may omit some details.
104
104
*/
105
105
 
106
106
#include <drizzled/server_includes.h>
107
107
#include <drizzled/sql_select.h>
108
 
 
109
 
#ifndef EXTRA_DEBUG
110
 
#define test_rb_tree(A,B) {}
111
 
#define test_use_count(A) {}
 
108
#include <drizzled/error.h>
 
109
#include <drizzled/cost_vect.h>
 
110
#include <drizzled/item/cmpfunc.h>
 
111
#include <drizzled/field/num.h>
 
112
#include <drizzled/check_stack_overrun.h>
 
113
 
 
114
#include <string>
 
115
#include CMATH_H
 
116
 
 
117
using namespace std;
 
118
#if defined(CMATH_NAMESPACE)
 
119
using namespace CMATH_NAMESPACE;
112
120
#endif
113
121
 
114
122
/*
117
125
*/
118
126
#define double2rows(x) ((ha_rows)(x))
119
127
 
120
 
static int sel_cmp(Field *f,uchar *a,uchar *b,uint8_t a_flag,uint8_t b_flag);
 
128
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
121
129
 
122
 
static uchar is_null_string[2]= {1,0};
 
130
static unsigned char is_null_string[2]= {1,0};
123
131
 
124
132
class RANGE_OPT_PARAM;
125
133
/*
126
134
  A construction block of the SEL_ARG-graph.
127
 
  
128
 
  The following description only covers graphs of SEL_ARG objects with 
 
135
 
 
136
  The following description only covers graphs of SEL_ARG objects with
129
137
  sel_arg->type==KEY_RANGE:
130
138
 
131
139
  One SEL_ARG object represents an "elementary interval" in form
132
 
  
 
140
 
133
141
      min_value <=?  table.keypartX  <=? max_value
134
 
  
 
142
 
135
143
  The interval is a non-empty interval of any kind: with[out] minimum/maximum
136
144
  bound, [half]open/closed, single-point interval, etc.
137
145
 
138
146
  1. SEL_ARG GRAPH STRUCTURE
139
 
  
 
147
 
140
148
  SEL_ARG objects are linked together in a graph. The meaning of the graph
141
149
  is better demostrated by an example:
142
 
  
 
150
 
143
151
     tree->keys[i]
144
 
      | 
 
152
      |
145
153
      |             $              $
146
154
      |    part=1   $     part=2   $    part=3
147
155
      |             $              $
150
158
      |  +-------+  $   +-------+  $   +--------+
151
159
      |      |      $              $       |
152
160
      |      |      $              $   +--------+
153
 
      |      |      $              $   | kp3=12 | 
154
 
      |      |      $              $   +--------+ 
155
 
      |  +-------+  $              $   
156
 
      \->| kp1=2 |--$--------------$-+ 
 
161
      |      |      $              $   | kp3=12 |
 
162
      |      |      $              $   +--------+
 
163
      |  +-------+  $              $
 
164
      \->| kp1=2 |--$--------------$-+
157
165
         +-------+  $              $ |   +--------+
158
166
             |      $              $  ==>| kp3=11 |
159
167
         +-------+  $              $ |   +--------+
161
169
         +-------+  $              $     +--------+
162
170
             |      $              $     | kp3=14 |
163
171
            ...     $              $     +--------+
164
 
 
 
172
 
165
173
  The entire graph is partitioned into "interval lists".
166
174
 
167
175
  An interval list is a sequence of ordered disjoint intervals over the same
168
176
  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 
 
177
  all intervals in the list form an RB-tree, linked via left/right/parent
170
178
  pointers. The RB-tree root SEL_ARG object will be further called "root of the
171
179
  interval list".
172
 
  
173
 
    In the example pic, there are 4 interval lists: 
 
180
 
 
181
    In the example pic, there are 4 interval lists:
174
182
    "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
175
183
    The vertical lines represent SEL_ARG::next/prev pointers.
176
 
    
 
184
 
177
185
  In an interval list, each member X may have SEL_ARG::next_key_part pointer
178
186
  pointing to the root of another interval list Y. The pointed interval list
179
187
  must cover a key part with greater number (i.e. Y->part > X->part).
180
 
    
 
188
 
181
189
    In the example pic, the next_key_part pointers are represented by
182
190
    horisontal lines.
183
191
 
185
193
 
186
194
  It represents a condition in a special form (we don't have a name for it ATM)
187
195
  The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
188
 
  
 
196
 
189
197
  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 
 
198
   (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
 
199
   (kp1=2 AND (kp3=11 OR kp3=14)) OR
192
200
   (kp1=3 AND (kp3=11 OR kp3=14))
193
201
 
194
202
 
197
205
  Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
198
206
  Then walk the SEL_ARG graph and get a list of dijsoint ordered key
199
207
  intervals (i.e. intervals in form
200
 
  
 
208
 
201
209
   (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
202
210
 
203
211
  Those intervals can be used to access the index. The uses are in:
208
216
                            and create QUICK_RANGE_SELECT object that will
209
217
                            read records within these intervals.
210
218
 
211
 
  4. SPACE COMPLEXITY NOTES 
 
219
  4. SPACE COMPLEXITY NOTES
212
220
 
213
221
    SEL_ARG graph is a representation of an ordered disjoint sequence of
214
222
    intervals over the ordered set of index tuple values.
215
223
 
216
224
    For multi-part keys, one can construct a WHERE expression such that its
217
225
    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 
 
226
 
 
227
      (keypart1 IN (1,2, ..., n1)) AND
 
228
      (keypart2 IN (1,2, ..., n2)) AND
221
229
      (keypart3 IN (1,2, ..., n3))
222
 
    
 
230
 
223
231
    For this WHERE clause the list of intervals will have n1*n2*n3 intervals
224
232
    of form
225
 
     
 
233
 
226
234
      (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
227
 
    
 
235
 
228
236
    SEL_ARG graph structure aims to reduce the amount of required space by
229
237
    "sharing" the elementary intervals when possible (the pic at the
230
 
    beginning of this comment has examples of such sharing). The sharing may 
 
238
    beginning of this comment has examples of such sharing). The sharing may
231
239
    prevent combinatorial blowup:
232
240
 
233
241
      There are WHERE clauses that have combinatorial-size interval lists but
234
242
      will be represented by a compact SEL_ARG graph.
235
243
      Example:
236
 
        (keypartN IN (1,2, ..., n1)) AND 
 
244
        (keypartN IN (1,2, ..., n1)) AND
237
245
        ...
238
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
246
        (keypart2 IN (1,2, ..., n2)) AND
239
247
        (keypart1 IN (1,2, ..., n3))
240
248
 
241
249
    but not in all cases:
244
252
      representation but get_mm_tree() and its callees will construct a
245
253
      graph of combinatorial size.
246
254
      Example:
247
 
        (keypart1 IN (1,2, ..., n1)) AND 
248
 
        (keypart2 IN (1,2, ..., n2)) AND 
 
255
        (keypart1 IN (1,2, ..., n1)) AND
 
256
        (keypart2 IN (1,2, ..., n2)) AND
249
257
        ...
250
258
        (keypartN IN (1,2, ..., n3))
251
259
 
255
263
        By induction: Let's take any interval on some keypart in the middle:
256
264
 
257
265
           kp15=c0
258
 
        
 
266
 
259
267
        Then let's AND it with this interval 'structure' from preceding and
260
268
        following keyparts:
261
269
 
262
270
          (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
263
 
        
 
271
 
264
272
        We will obtain this SEL_ARG graph:
265
 
 
 
273
 
266
274
             kp14     $      kp15      $      kp16
267
275
                      $                $
268
276
         +---------+  $   +---------+  $   +---------+
269
277
         | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
270
278
         +---------+  $   +---------+  $   +---------+
271
 
              |       $                $              
272
 
         +---------+  $   +---------+  $             
273
 
         | kp14=c2 |--$-->| kp15=c0 |  $             
274
 
         +---------+  $   +---------+  $             
 
279
              |       $                $
 
280
         +---------+  $   +---------+  $
 
281
         | kp14=c2 |--$-->| kp15=c0 |  $
 
282
         +---------+  $   +---------+  $
275
283
                      $                $
276
 
                      
 
284
 
277
285
       Note that we had to duplicate "kp15=c0" and there was no way to avoid
278
 
       that. 
 
286
       that.
279
287
       The induction step: AND the obtained expression with another "wrapping"
280
288
       expression like (*).
281
 
       When the process ends because of the limit on max. number of keyparts 
 
289
       When the process ends because of the limit on max. number of keyparts
282
290
       we'll have:
283
291
 
284
292
         WHERE clause length  is O(3*#max_keyparts)
298
306
  uint8_t min_flag,max_flag,maybe_flag;
299
307
  uint8_t part;                                 // Which key part
300
308
  uint8_t maybe_null;
301
 
  /* 
 
309
  /*
302
310
    Number of children of this element in the RB-tree, plus 1 for this
303
311
    element itself.
304
312
  */
311
319
  ulong use_count;
312
320
 
313
321
  Field *field;
314
 
  uchar *min_value,*max_value;                  // Pointer to range
 
322
  unsigned char *min_value,*max_value;                  // Pointer to range
315
323
 
316
324
  /*
317
325
    eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
319
327
  SEL_ARG *left,*right;   /* R-B tree children */
320
328
  SEL_ARG *next,*prev;    /* Links for bi-directional interval list */
321
329
  SEL_ARG *parent;        /* R-B tree parent */
322
 
  SEL_ARG *next_key_part; 
 
330
  SEL_ARG *next_key_part;
323
331
  enum leaf_color { BLACK,RED } color;
324
332
  enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
325
333
 
327
335
 
328
336
  SEL_ARG() {}
329
337
  SEL_ARG(SEL_ARG &);
330
 
  SEL_ARG(Field *,const uchar *, const uchar *);
331
 
  SEL_ARG(Field *field, uint8_t part, uchar *min_value, uchar *max_value,
 
338
  SEL_ARG(Field *,const unsigned char *, const unsigned char *);
 
339
  SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
332
340
          uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
333
341
  SEL_ARG(enum Type type_arg)
334
342
    :min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
345
353
  inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
346
354
  inline void maybe_smaller() { maybe_flag=1; }
347
355
  /* Return true iff it's a single-point null interval */
348
 
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; } 
 
356
  inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
349
357
  inline int cmp_min_to_min(SEL_ARG* arg)
350
358
  {
351
359
    return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
364
372
  }
365
373
  SEL_ARG *clone_and(SEL_ARG* arg)
366
374
  {                                             // Get overlapping range
367
 
    uchar *new_min,*new_max;
 
375
    unsigned char *new_min,*new_max;
368
376
    uint8_t flag_min,flag_max;
369
377
    if (cmp_min_to_min(arg) >= 0)
370
378
    {
438
446
    min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
439
447
  }
440
448
  /* returns a number of keypart values (0 or 1) appended to the key buffer */
441
 
  int store_min(uint length, uchar **min_key,uint min_key_flag)
 
449
  int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
442
450
  {
443
451
    /* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
444
452
    if ((!(min_flag & NO_MIN_RANGE) &&
457
465
    return 0;
458
466
  }
459
467
  /* returns a number of keypart values (0 or 1) appended to the key buffer */
460
 
  int store_max(uint length, uchar **max_key, uint max_key_flag)
 
468
  int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
461
469
  {
462
470
    if (!(max_flag & NO_MAX_RANGE) &&
463
471
        !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
476
484
  }
477
485
 
478
486
  /* returns a number of keypart values appended to the key buffer */
479
 
  int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
 
487
  int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
480
488
  {
481
489
    SEL_ARG *key_tree= first();
482
 
    uint res= key_tree->store_min(key[key_tree->part].store_length,
 
490
    uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
483
491
                                  range_key, *range_key_flag);
484
492
    *range_key_flag|= key_tree->min_flag;
485
 
    
 
493
 
486
494
    if (key_tree->next_key_part &&
487
495
        key_tree->next_key_part->part == key_tree->part+1 &&
488
496
        !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
493
501
  }
494
502
 
495
503
  /* returns a number of keypart values appended to the key buffer */
496
 
  int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
 
504
  int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
497
505
  {
498
506
    SEL_ARG *key_tree= last();
499
 
    uint res=key_tree->store_max(key[key_tree->part].store_length,
 
507
    uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
500
508
                                 range_key, *range_key_flag);
501
509
    (*range_key_flag)|= key_tree->max_flag;
502
510
    if (key_tree->next_key_part &&
556
564
 
557
565
    SYNOPSIS
558
566
      is_singlepoint()
559
 
    
 
567
 
560
568
    DESCRIPTION
561
569
      Check if this SEL_ARG object (not tree) represents a single-point
562
 
      interval, i.e. if it represents a "keypart = const" or 
 
570
      interval, i.e. if it represents a "keypart = const" or
563
571
      "keypart IS NULL".
564
572
 
565
573
    RETURN
569
577
 
570
578
  bool is_singlepoint()
571
579
  {
572
 
    /* 
573
 
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field) 
 
580
    /*
 
581
      Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
574
582
      flags, and the same for right edge.
575
583
    */
576
584
    if (min_flag || max_flag)
577
585
      return false;
578
 
    uchar *min_val= min_value;
579
 
    uchar *max_val= max_value;
 
586
    unsigned char *min_val= min_value;
 
587
    unsigned char *max_val= max_value;
580
588
 
581
589
    if (maybe_null)
582
590
    {
602
610
public:
603
611
  /*
604
612
    Starting an effort to document this field:
605
 
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) => 
 
613
    (for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
606
614
       (type == SEL_TREE::IMPOSSIBLE)
607
615
  */
608
616
  enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
629
637
 
630
638
  /* The members below are filled/used only after get_mm_tree is done */
631
639
  key_map ror_scans_map;   /* bitmask of ROR scan-able elements in keys */
632
 
  uint    n_ror_scans;     /* number of set bits in ror_scans_map */
 
640
  uint32_t    n_ror_scans;     /* number of set bits in ror_scans_map */
633
641
 
634
642
  struct st_ror_scan_info **ror_scans;     /* list of ROR key scans */
635
643
  struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
639
647
class RANGE_OPT_PARAM
640
648
{
641
649
public:
642
 
  THD   *thd;   /* Current thread handle */
643
 
  TABLE *table; /* Table being analyzed */
 
650
  Session       *session;   /* Current thread handle */
 
651
  Table *table; /* Table being analyzed */
644
652
  COND *cond;   /* Used inside get_mm_tree(). */
645
653
  table_map prev_tables;
646
654
  table_map read_tables;
655
663
    Number of indexes used in range analysis (In SEL_TREE::keys only first
656
664
    #keys elements are not empty)
657
665
  */
658
 
  uint keys;
659
 
  
660
 
  /* 
 
666
  uint32_t keys;
 
667
 
 
668
  /*
661
669
    If true, the index descriptions describe real indexes (and it is ok to
662
670
    call field->optimize_range(real_keynr[...], ...).
663
671
    Otherwise index description describes fake indexes.
664
672
  */
665
673
  bool using_real_indexes;
666
 
  
 
674
 
667
675
  bool remove_jump_scans;
668
 
  
 
676
 
669
677
  /*
670
678
    used_key_no -> table_key_no translation table. Only makes sense if
671
679
    using_real_indexes==true
672
680
  */
673
 
  uint real_keynr[MAX_KEY];
 
681
  uint32_t real_keynr[MAX_KEY];
674
682
  /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
675
 
  uint alloced_sel_args; 
 
683
  uint32_t alloced_sel_args;
676
684
  bool force_default_mrr;
677
685
};
678
686
 
681
689
public:
682
690
  KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
683
691
  int64_t baseflag;
684
 
  uint max_key_part;
 
692
  uint32_t max_key_part;
685
693
  /* Number of ranges in the last checked tree->key */
686
 
  uint range_count;
687
 
  uchar min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
 
694
  uint32_t range_count;
 
695
  unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
688
696
    max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
689
697
  bool quick;                           // Don't calulate possible keys
690
698
 
691
 
  uint fields_bitmap_size;
 
699
  uint32_t fields_bitmap_size;
692
700
  MY_BITMAP needed_fields;    /* bitmask of fields needed by the query */
693
701
  MY_BITMAP tmp_covered_fields;
694
702
 
695
703
  key_map *needed_reg;        /* ptr to SQL_SELECT::needed_reg */
696
704
 
697
 
  uint *imerge_cost_buff;     /* buffer for index_merge cost estimates */
698
 
  uint imerge_cost_buff_size; /* size of the buffer */
 
705
  uint32_t *imerge_cost_buff;     /* buffer for index_merge cost estimates */
 
706
  uint32_t imerge_cost_buff_size; /* size of the buffer */
699
707
 
700
708
  /* true if last checked tree->key can be used for ROR-scan */
701
709
  bool is_ror_scan;
702
710
  /* Number of ranges in the last checked tree->key */
703
 
  uint n_ranges;
 
711
  uint32_t n_ranges;
704
712
};
705
713
 
706
714
class TABLE_READ_PLAN;
720
728
                            Item_func::Functype type,Item *value);
721
729
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
722
730
 
723
 
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8_t nparts);
724
 
static ha_rows check_quick_select(PARAM *param, uint idx, bool index_only,
725
 
                                  SEL_ARG *tree, bool update_tbl_stats, 
726
 
                                  uint *mrr_flags, uint *bufsize,
 
731
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
 
732
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
 
733
                                  SEL_ARG *tree, bool update_tbl_stats,
 
734
                                  uint32_t *mrr_flags, uint32_t *bufsize,
727
735
                                  COST_VECT *cost);
728
736
                                  //bool update_tbl_stats);
729
 
/*static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
730
 
                                uchar *min_key, uint min_key_flag, int,
731
 
                                uchar *max_key, uint max_key_flag, int);
 
737
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
 
738
                                unsigned char *min_key, uint32_t min_key_flag, int,
 
739
                                unsigned char *max_key, uint32_t max_key_flag, int);
732
740
*/
733
741
 
734
 
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint index,
735
 
                                     SEL_ARG *key_tree, uint mrr_flags, 
736
 
                                     uint mrr_buf_size, MEM_ROOT *alloc);
 
742
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
 
743
                                     SEL_ARG *key_tree, uint32_t mrr_flags,
 
744
                                     uint32_t mrr_buf_size, MEM_ROOT *alloc);
737
745
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
738
746
                                       bool index_read_must_be_used,
739
747
                                       bool update_tbl_stats,
754
762
 
755
763
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
756
764
                           const char *msg);
757
 
static void print_ror_scans_arr(TABLE *table, const char *msg,
 
765
static void print_ror_scans_arr(Table *table, const char *msg,
758
766
                                struct st_ror_scan_info **start,
759
767
                                struct st_ror_scan_info **end);
760
768
 
763
771
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
764
772
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
765
773
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
766
 
                        uint clone_flag);
 
774
                        uint32_t clone_flag);
767
775
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
768
776
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
769
 
                    SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
770
 
                    uchar *max_key,uint max_key_flag);
 
777
                    SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
 
778
                    unsigned char *max_key,uint32_t max_key_flag);
771
779
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
772
780
 
773
781
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
774
 
static bool null_part_in_key(KEY_PART *key_part, const uchar *key,
775
 
                             uint length);
 
782
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
 
783
                             uint32_t length);
776
784
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
777
785
 
778
786
 
828
836
  if (trees_next == trees_end)
829
837
  {
830
838
    const int realloc_ratio= 2;         /* Double size for next round */
831
 
    uint old_elements= (trees_end - trees);
832
 
    uint old_size= sizeof(SEL_TREE**) * old_elements;
833
 
    uint new_size= old_size * realloc_ratio;
 
839
    uint32_t old_elements= (trees_end - trees);
 
840
    uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
 
841
    uint32_t new_size= old_size * realloc_ratio;
834
842
    SEL_TREE **new_trees;
835
843
    if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
836
844
      return -1;
999
1007
           1 = Got some error (out of memory?)
1000
1008
           */
1001
1009
 
1002
 
SQL_SELECT *make_select(TABLE *head, table_map const_tables,
 
1010
SQL_SELECT *make_select(Table *head, table_map const_tables,
1003
1011
                        table_map read_tables, COND *conds,
1004
1012
                        bool allow_null_cond,
1005
1013
                        int *error)
1009
1017
  *error=0;
1010
1018
 
1011
1019
  if (!conds && !allow_null_cond)
1012
 
    return(0);
 
1020
    return 0;
1013
1021
  if (!(select= new SQL_SELECT))
1014
1022
  {
1015
1023
    *error= 1;                  // out of memory
1016
 
    return(0);          /* purecov: inspected */
 
1024
    return 0;           /* purecov: inspected */
1017
1025
  }
1018
1026
  select->read_tables=read_tables;
1019
1027
  select->const_tables=const_tables;
1025
1033
    select->file= *head->sort.io_cache;
1026
1034
    select->records=(ha_rows) (select->file.end_of_file/
1027
1035
                               head->file->ref_length);
1028
 
    my_free(head->sort.io_cache, MYF(0));
 
1036
    delete head->sort.io_cache;
1029
1037
    head->sort.io_cache=0;
1030
1038
  }
1031
1039
  return(select);
1058
1066
  cleanup();
1059
1067
}
1060
1068
 
 
1069
 
 
1070
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
 
1071
                             ha_rows limit)
 
1072
{
 
1073
  key_map tmp;
 
1074
  tmp.set_all();
 
1075
  return test_quick_select(session, tmp, 0, limit,
 
1076
                           force_quick_range, false) < 0;
 
1077
}
 
1078
 
 
1079
 
 
1080
bool SQL_SELECT::skip_record()
 
1081
{
 
1082
  return cond ? cond->val_int() == 0 : 0;
 
1083
}
 
1084
 
 
1085
 
1061
1086
QUICK_SELECT_I::QUICK_SELECT_I()
1062
1087
  :max_used_key_length(0),
1063
1088
   used_key_parts(0)
1064
1089
{}
1065
1090
 
1066
 
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, TABLE *table, uint key_nr,
 
1091
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1067
1092
                                       bool no_alloc, MEM_ROOT *parent_alloc,
1068
1093
                                       bool *create_error)
1069
1094
  :free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1077
1102
  key_part_info= head->key_info[index].key_part;
1078
1103
  my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1079
1104
 
1080
 
  /* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1081
 
  mrr_buf_size= thd->variables.read_rnd_buff_size;
 
1105
  /* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
 
1106
  mrr_buf_size= session->variables.read_rnd_buff_size;
1082
1107
  mrr_buf_desc= NULL;
1083
1108
 
1084
1109
  if (!no_alloc && !parent_alloc)
1085
1110
  {
1086
1111
    // Allocates everything through the internal memroot
1087
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1088
 
    thd->mem_root= &alloc;
 
1112
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1113
    session->mem_root= &alloc;
1089
1114
  }
1090
1115
  else
1091
1116
    memset(&alloc, 0, sizeof(alloc));
1095
1120
  save_write_set= head->write_set;
1096
1121
 
1097
1122
  /* 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))))
 
1123
  if (!(bitmap= (my_bitmap_map*) malloc(head->s->column_bitmap_size)))
1100
1124
  {
1101
1125
    column_bitmap.bitmap= 0;
1102
1126
    *create_error= 1;
1127
1151
  if (!dont_free)
1128
1152
  {
1129
1153
    /* file is NULL for CPK scan on covering ROR-intersection */
1130
 
    if (file) 
 
1154
    if (file)
1131
1155
    {
1132
1156
      range_end();
1133
1157
      if (head->key_read)
1137
1161
      }
1138
1162
      if (free_file)
1139
1163
      {
1140
 
        file->ha_external_lock(current_thd, F_UNLCK);
 
1164
        file->ha_external_lock(current_session, F_UNLCK);
1141
1165
        file->close();
1142
1166
        delete file;
1143
1167
      }
1144
1168
    }
1145
1169
    delete_dynamic(&ranges); /* ranges are allocated in alloc */
1146
1170
    free_root(&alloc,MYF(0));
1147
 
    my_free((char*) column_bitmap.bitmap, MYF(MY_ALLOW_ZERO_PTR));
 
1171
    free((char*) column_bitmap.bitmap);
1148
1172
  }
1149
1173
  head->column_bitmaps_set(save_read_set, save_write_set);
1150
 
  x_free(mrr_buf_desc);
 
1174
  if (mrr_buf_desc)
 
1175
    free(mrr_buf_desc);
1151
1176
  return;
1152
1177
}
1153
1178
 
1154
1179
 
1155
 
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1156
 
                                                   TABLE *table)
1157
 
  :pk_quick_select(NULL), thd(thd_param)
 
1180
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
 
1181
                                                   Table *table)
 
1182
  :pk_quick_select(NULL), session(session_param)
1158
1183
{
1159
1184
  index= MAX_KEY;
1160
1185
  head= table;
1161
1186
  memset(&read_record, 0, sizeof(read_record));
1162
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1187
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1163
1188
  return;
1164
1189
}
1165
1190
 
1166
1191
int QUICK_INDEX_MERGE_SELECT::init()
1167
1192
{
1168
 
  return(0);
 
1193
  return 0;
1169
1194
}
1170
1195
 
1171
1196
int QUICK_INDEX_MERGE_SELECT::reset()
1202
1227
}
1203
1228
 
1204
1229
 
1205
 
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1206
 
                                                       TABLE *table,
 
1230
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
 
1231
                                                       Table *table,
1207
1232
                                                       bool retrieve_full_rows,
1208
1233
                                                       MEM_ROOT *parent_alloc)
1209
 
  : cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
 
1234
  : cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1210
1235
    scans_inited(false)
1211
1236
{
1212
1237
  index= MAX_KEY;
1213
1238
  head= table;
1214
1239
  record= head->record[0];
1215
1240
  if (!parent_alloc)
1216
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
1241
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1217
1242
  else
1218
1243
    memset(&alloc, 0, sizeof(MEM_ROOT));
1219
 
  last_rowid= (uchar*) alloc_root(parent_alloc? parent_alloc : &alloc,
 
1244
  last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1220
1245
                                  head->file->ref_length);
1221
1246
}
1222
1247
 
1263
1288
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1264
1289
{
1265
1290
  handler *save_file= file, *org_file;
1266
 
  THD *thd;
 
1291
  Session *session;
1267
1292
 
1268
1293
  in_ror_merged_scan= 1;
1269
1294
  if (reuse_handler)
1270
1295
  {
1271
1296
    if (init() || reset())
1272
1297
    {
1273
 
      return(1);
 
1298
      return 0;
1274
1299
    }
1275
1300
    head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1276
1301
    goto end;
1280
1305
  if (free_file)
1281
1306
  {
1282
1307
    /* already have own 'handler' object. */
1283
 
    return(0);
 
1308
    return 0;
1284
1309
  }
1285
1310
 
1286
 
  thd= head->in_use;
1287
 
  if (!(file= head->file->clone(thd->mem_root)))
 
1311
  session= head->in_use;
 
1312
  if (!(file= head->file->clone(session->mem_root)))
1288
1313
  {
1289
 
    /* 
 
1314
    /*
1290
1315
      Manually set the error flag. Note: there seems to be quite a few
1291
1316
      places where a failure could cause the server to "hang" the client by
1292
 
      sending no response to a query. ATM those are not real errors because 
1293
 
      the storage engine calls in question happen to never fail with the 
1294
 
      existing storage engines. 
 
1317
      sending no response to a query. ATM those are not real errors because
 
1318
      the storage engine calls in question happen to never fail with the
 
1319
      existing storage engines.
1295
1320
    */
1296
1321
    my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1297
1322
    /* Caller will free the memory */
1300
1325
 
1301
1326
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1302
1327
 
1303
 
  if (file->ha_external_lock(thd, F_RDLCK))
 
1328
  if (file->ha_external_lock(session, F_RDLCK))
1304
1329
    goto failure;
1305
1330
 
1306
1331
  if (init() || reset())
1307
1332
  {
1308
 
    file->ha_external_lock(thd, F_UNLCK);
 
1333
    file->ha_external_lock(session, F_UNLCK);
1309
1334
    file->close();
1310
1335
    goto failure;
1311
1336
  }
1332
1357
  bitmap_copy(&column_bitmap, head->read_set);
1333
1358
  head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1334
1359
 
1335
 
  return(0);
 
1360
  return 0;
1336
1361
 
1337
1362
failure:
1338
1363
  head->column_bitmaps_set(save_read_set, save_write_set);
1339
1364
  delete file;
1340
1365
  file= save_file;
1341
 
  return(1);
 
1366
  return 0;
 
1367
}
 
1368
 
 
1369
 
 
1370
void QUICK_RANGE_SELECT::save_last_pos()
 
1371
{
 
1372
  file->position(record);
1342
1373
}
1343
1374
 
1344
1375
 
1367
1398
      selects.
1368
1399
    */
1369
1400
    if (quick->init_ror_merged_scan(true))
1370
 
      return(1);
 
1401
      return 0;
1371
1402
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1372
1403
  }
1373
1404
  while ((quick= quick_it++))
1374
1405
  {
1375
1406
    if (quick->init_ror_merged_scan(false))
1376
 
      return(1);
 
1407
      return 0;
1377
1408
    quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1378
1409
    /* All merged scans share the same record buffer in intersection. */
1379
1410
    quick->record= head->record[0];
1381
1412
 
1382
1413
  if (need_to_fetch_row && head->file->ha_rnd_init(1))
1383
1414
  {
1384
 
    return(1);
 
1415
    return 0;
1385
1416
  }
1386
 
  return(0);
 
1417
  return 0;
1387
1418
}
1388
1419
 
1389
1420
 
1399
1430
int QUICK_ROR_INTERSECT_SELECT::reset()
1400
1431
{
1401
1432
  if (!scans_inited && init_ror_merged_scan(true))
1402
 
    return(1);
 
1433
    return 0;
1403
1434
  scans_inited= true;
1404
1435
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1405
1436
  QUICK_RANGE_SELECT *quick;
1406
1437
  while ((quick= it++))
1407
1438
    quick->reset();
1408
 
  return(0);
 
1439
  return 0;
1409
1440
}
1410
1441
 
1411
1442
 
1441
1472
}
1442
1473
 
1443
1474
 
1444
 
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1445
 
                                               TABLE *table)
1446
 
  : thd(thd_param), scans_inited(false)
 
1475
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
 
1476
                                               Table *table)
 
1477
  : session(session_param), scans_inited(false)
1447
1478
{
1448
1479
  index= MAX_KEY;
1449
1480
  head= table;
1450
1481
  rowid_length= table->file->ref_length;
1451
1482
  record= head->record[0];
1452
 
  init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1453
 
  thd_param->mem_root= &alloc;
 
1483
  init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
 
1484
  session_param->mem_root= &alloc;
1454
1485
}
1455
1486
 
1456
1487
 
1471
1502
                 (void*) this))
1472
1503
  {
1473
1504
    memset(&queue, 0, sizeof(QUEUE));
1474
 
    return(1);
 
1505
    return 0;
1475
1506
  }
1476
1507
 
1477
 
  if (!(cur_rowid= (uchar*) alloc_root(&alloc, 2*head->file->ref_length)))
1478
 
    return(1);
 
1508
  if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
 
1509
    return 0;
1479
1510
  prev_rowid= cur_rowid + head->file->ref_length;
1480
 
  return(0);
 
1511
  return 0;
1481
1512
}
1482
1513
 
1483
1514
 
1492
1523
      val2  Second merged select
1493
1524
*/
1494
1525
 
1495
 
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, uchar *val1, uchar *val2)
 
1526
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1496
1527
{
1497
1528
  QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1498
1529
  return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1521
1552
    while ((quick= it++))
1522
1553
    {
1523
1554
      if (quick->init_ror_merged_scan(false))
1524
 
        return(1);
 
1555
        return 0;
1525
1556
    }
1526
1557
    scans_inited= true;
1527
1558
  }
1534
1565
  while ((quick= it++))
1535
1566
  {
1536
1567
    if (quick->reset())
1537
 
      return(1);
 
1568
      return 0;
1538
1569
    if ((error= quick->get_next()))
1539
1570
    {
1540
1571
      if (error == HA_ERR_END_OF_FILE)
1542
1573
      return(error);
1543
1574
    }
1544
1575
    quick->save_last_pos();
1545
 
    queue_insert(&queue, (uchar*)quick);
 
1576
    queue_insert(&queue, (unsigned char*)quick);
1546
1577
  }
1547
1578
 
1548
1579
  if (head->file->ha_rnd_init(1))
1549
1580
  {
1550
 
    return(1);
 
1581
    return 0;
1551
1582
  }
1552
1583
 
1553
 
  return(0);
 
1584
  return 0;
1554
1585
}
1555
1586
 
1556
1587
 
1601
1632
  use_count=0; elements=1;
1602
1633
}
1603
1634
 
1604
 
SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg,
1605
 
                 const uchar *max_value_arg)
 
1635
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
 
1636
                 const unsigned char *max_value_arg)
1606
1637
  :min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1607
 
   elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
1608
 
   max_value((uchar*) max_value_arg), next(0),prev(0),
 
1638
   elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
 
1639
   max_value((unsigned char*) max_value_arg), next(0),prev(0),
1609
1640
   next_key_part(0),color(BLACK),type(KEY_RANGE)
1610
1641
{
1611
1642
  left=right= &null_element;
1612
1643
}
1613
1644
 
1614
1645
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1615
 
                 uchar *min_value_, uchar *max_value_,
 
1646
                 unsigned char *min_value_, unsigned char *max_value_,
1616
1647
                 uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1617
1648
  :min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1618
1649
   part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1622
1653
  left=right= &null_element;
1623
1654
}
1624
1655
 
1625
 
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, 
 
1656
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1626
1657
                        SEL_ARG **next_arg)
1627
1658
{
1628
1659
  SEL_ARG *tmp;
1690
1721
  Returns -2 or 2 if the ranges where 'joined' like  < 2 and >= 2
1691
1722
*/
1692
1723
 
1693
 
static int sel_cmp(Field *field, uchar *a, uchar *b, uint8_t a_flag,
 
1724
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1694
1725
                   uint8_t b_flag)
1695
1726
{
1696
1727
  int cmp;
1758
1789
      limit  Number of records that will be retrieved
1759
1790
 
1760
1791
  DESCRIPTION
1761
 
    Find the best index that allows to retrieve first #limit records in the 
 
1792
    Find the best index that allows to retrieve first #limit records in the
1762
1793
    given order cheaper then one would retrieve them using full table scan.
1763
1794
 
1764
1795
  IMPLEMENTATION
1777
1808
    MAX_KEY if no such index was found.
1778
1809
*/
1779
1810
 
1780
 
uint get_index_for_order(TABLE *table, ORDER *order, ha_rows limit)
 
1811
uint32_t get_index_for_order(Table *table, order_st *order, ha_rows limit)
1781
1812
{
1782
 
  uint idx;
1783
 
  uint match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
1784
 
  ORDER *ord;
1785
 
  
 
1813
  uint32_t idx;
 
1814
  uint32_t match_key= MAX_KEY, match_key_len= MAX_KEY_LENGTH + 1;
 
1815
  order_st *ord;
 
1816
 
1786
1817
  for (ord= order; ord; ord= ord->next)
1787
1818
    if (!ord->asc)
1788
1819
      return MAX_KEY;
1792
1823
    if (!(table->keys_in_use_for_query.is_set(idx)))
1793
1824
      continue;
1794
1825
    KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
1795
 
    uint n_parts=  table->key_info[idx].key_parts;
1796
 
    uint partno= 0;
1797
 
    
1798
 
    /* 
1799
 
      The below check is sufficient considering we now have either BTREE 
1800
 
      indexes (records are returned in order for any index prefix) or HASH 
 
1826
    uint32_t n_parts=  table->key_info[idx].key_parts;
 
1827
    uint32_t partno= 0;
 
1828
 
 
1829
    /*
 
1830
      The below check is sufficient considering we now have either BTREE
 
1831
      indexes (records are returned in order for any index prefix) or HASH
1801
1832
      indexes (records are not returned in order for any index prefix).
1802
1833
    */
1803
1834
    if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
1809
1840
           ((Item_field*)item)->field->eq(keyinfo[partno].field)))
1810
1841
        break;
1811
1842
    }
1812
 
    
 
1843
 
1813
1844
    if (!ord && table->key_info[idx].key_length < match_key_len)
1814
1845
    {
1815
 
      /* 
 
1846
      /*
1816
1847
        Ok, the ordering is compatible and this key is shorter then
1817
1848
        previous match (we want shorter keys as we'll have to read fewer
1818
1849
        index pages for the same number of records)
1824
1855
 
1825
1856
  if (match_key != MAX_KEY)
1826
1857
  {
1827
 
    /* 
1828
 
      Found an index that allows records to be retrieved in the requested 
 
1858
    /*
 
1859
      Found an index that allows records to be retrieved in the requested
1829
1860
      order. Now we'll check if using the index is cheaper then doing a table
1830
1861
      scan.
1831
1862
    */
1881
1912
  /* Table read plans are allocated on MEM_ROOT and are never deleted */
1882
1913
  static void *operator new(size_t size, MEM_ROOT *mem_root)
1883
1914
  { return (void*) alloc_root(mem_root, (uint) size); }
1884
 
  static void operator delete(void *ptr __attribute__((unused)),
1885
 
                              size_t size __attribute__((unused)))
 
1915
  static void operator delete(void *, size_t)
1886
1916
    { TRASH(ptr, size); }
1887
 
  static void operator delete(void *ptr __attribute__((unused)),
1888
 
                              MEM_ROOT *mem_root __attribute__((unused)))
 
1917
  static void operator delete(void *, MEM_ROOT *)
1889
1918
    { /* Never called */ }
1890
1919
  virtual ~TABLE_READ_PLAN() {}               /* Remove gcc warning */
1891
1920
 
1907
1936
{
1908
1937
public:
1909
1938
  SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1910
 
  uint     key_idx; /* key number in PARAM::key */
1911
 
  uint     mrr_flags; 
1912
 
  uint     mrr_buf_size;
 
1939
  uint32_t     key_idx; /* key number in PARAM::key */
 
1940
  uint32_t     mrr_flags;
 
1941
  uint32_t     mrr_buf_size;
1913
1942
 
1914
 
  TRP_RANGE(SEL_ARG *key_arg, uint idx_arg, uint mrr_flags_arg)
 
1943
  TRP_RANGE(SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1915
1944
   : key(key_arg), key_idx(idx_arg), mrr_flags(mrr_flags_arg)
1916
1945
  {}
1917
1946
  virtual ~TRP_RANGE() {}                     /* Remove gcc warning */
1918
1947
 
1919
 
  QUICK_SELECT_I *make_quick(PARAM *param,
1920
 
                             bool retrieve_full_rows __attribute__((unused)),
1921
 
                             MEM_ROOT *parent_alloc)
 
1948
  QUICK_SELECT_I *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1922
1949
  {
1923
1950
    QUICK_RANGE_SELECT *quick;
1924
1951
    if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
1927
1954
      quick->records= records;
1928
1955
      quick->read_time= read_cost;
1929
1956
    }
1930
 
    return(quick);
 
1957
    return quick;
1931
1958
  }
1932
1959
};
1933
1960
 
1988
2015
 
1989
2016
 
1990
2017
/*
1991
 
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan. 
 
2018
  Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
1992
2019
*/
1993
2020
 
1994
2021
class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN
1996
2023
private:
1997
2024
  bool have_min, have_max;
1998
2025
  KEY_PART_INFO *min_max_arg_part;
1999
 
  uint group_prefix_len;
2000
 
  uint used_key_parts;
2001
 
  uint group_key_parts;
 
2026
  uint32_t group_prefix_len;
 
2027
  uint32_t used_key_parts;
 
2028
  uint32_t group_key_parts;
2002
2029
  KEY *index_info;
2003
 
  uint index;
2004
 
  uint key_infix_len;
2005
 
  uchar key_infix[MAX_KEY_LENGTH];
 
2030
  uint32_t index;
 
2031
  uint32_t key_infix_len;
 
2032
  unsigned char key_infix[MAX_KEY_LENGTH];
2006
2033
  SEL_TREE *range_tree; /* Represents all range predicates in the query. */
2007
2034
  SEL_ARG  *index_tree; /* The SEL_ARG sub-tree corresponding to index_info. */
2008
 
  uint param_idx; /* Index of used key in param->key. */
 
2035
  uint32_t param_idx; /* Index of used key in param->key. */
2009
2036
  /* Number of records selected by the ranges in index_tree. */
2010
2037
public:
2011
2038
  ha_rows quick_prefix_records;
2012
2039
public:
2013
2040
  TRP_GROUP_MIN_MAX(bool have_min_arg, bool have_max_arg,
2014
2041
                    KEY_PART_INFO *min_max_arg_part_arg,
2015
 
                    uint group_prefix_len_arg, uint used_key_parts_arg,
2016
 
                    uint group_key_parts_arg, KEY *index_info_arg,
2017
 
                    uint index_arg, uint key_infix_len_arg,
2018
 
                    uchar *key_infix_arg,
 
2042
                    uint32_t group_prefix_len_arg, uint32_t used_key_parts_arg,
 
2043
                    uint32_t group_key_parts_arg, KEY *index_info_arg,
 
2044
                    uint32_t index_arg, uint32_t key_infix_len_arg,
 
2045
                    unsigned char *key_infix_arg,
2019
2046
                    SEL_TREE *tree_arg, SEL_ARG *index_tree_arg,
2020
 
                    uint param_idx_arg, ha_rows quick_prefix_records_arg)
 
2047
                    uint32_t param_idx_arg, ha_rows quick_prefix_records_arg)
2021
2048
  : have_min(have_min_arg), have_max(have_max_arg),
2022
2049
    min_max_arg_part(min_max_arg_part_arg),
2023
2050
    group_prefix_len(group_prefix_len_arg), used_key_parts(used_key_parts_arg),
2052
2079
 
2053
2080
static int fill_used_fields_bitmap(PARAM *param)
2054
2081
{
2055
 
  TABLE *table= param->table;
 
2082
  Table *table= param->table;
2056
2083
  my_bitmap_map *tmp;
2057
 
  uint pk;
 
2084
  uint32_t pk;
2058
2085
  param->tmp_covered_fields.bitmap= 0;
2059
2086
  param->fields_bitmap_size= table->s->column_bitmap_size;
2060
2087
  if (!(tmp= (my_bitmap_map*) alloc_root(param->mem_root,
2084
2111
 
2085
2112
  SYNOPSIS
2086
2113
    SQL_SELECT::test_quick_select()
2087
 
      thd               Current thread
 
2114
      session               Current thread
2088
2115
      keys_to_use       Keys to use for range retrieval
2089
2116
      prev_tables       Tables assumed to be already read when the scan is
2090
2117
                        performed (but not read at the moment of this call)
2104
2131
 
2105
2132
  IMPLEMENTATION
2106
2133
    quick_condition_rows value is obtained as follows:
2107
 
      
 
2134
 
2108
2135
      It is a minimum of E(#output rows) for all considered table access
2109
2136
      methods (range and index_merge accesses over various indexes).
2110
 
    
 
2137
 
2111
2138
    The obtained value is not a true E(#rows that satisfy table condition)
2112
2139
    but rather a pessimistic estimate. To obtain a true E(#...) one would
2113
2140
    need to combine estimates of various access methods, taking into account
2114
2141
    correlations between sets of rows they will return.
2115
 
    
 
2142
 
2116
2143
    For example, if values of tbl.key1 and tbl.key2 are independent (a right
2117
2144
    assumption if we have no information about their correlation) then the
2118
2145
    correct estimate will be:
2119
 
    
2120
 
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) = 
 
2146
 
 
2147
      E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
2121
2148
      = E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)
2122
2149
 
2123
 
    which is smaller than 
2124
 
      
 
2150
    which is smaller than
 
2151
 
2125
2152
       MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))
2126
2153
 
2127
2154
    which is currently produced.
2128
2155
 
2129
2156
  TODO
2130
2157
   * Change the value returned in quick_condition_rows from a pessimistic
2131
 
     estimate to true E(#rows that satisfy table condition). 
2132
 
     (we can re-use some of E(#rows) calcuation code from index_merge/intersection 
 
2158
     estimate to true E(#rows that satisfy table condition).
 
2159
     (we can re-use some of E(#rows) calcuation code from index_merge/intersection
2133
2160
      for this)
2134
 
   
 
2161
 
2135
2162
   * Check if this function really needs to modify keys_to_use, and change the
2136
2163
     code to pass it by reference if it doesn't.
2137
2164
 
2145
2172
    1 if found usable ranges and quick select has been successfully created.
2146
2173
*/
2147
2174
 
2148
 
int SQL_SELECT::test_quick_select(THD *thd, key_map keys_to_use,
 
2175
int SQL_SELECT::test_quick_select(Session *session, key_map keys_to_use,
2149
2176
                                  table_map prev_tables,
2150
 
                                  ha_rows limit, bool force_quick_range, 
 
2177
                                  ha_rows limit, bool force_quick_range,
2151
2178
                                  bool ordered_output)
2152
2179
{
2153
 
  uint idx;
 
2180
  uint32_t idx;
2154
2181
  double scan_time;
2155
2182
  delete quick;
2156
2183
  quick=0;
2157
2184
  needed_reg.clear_all();
2158
2185
  quick_keys.clear_all();
2159
2186
  if (keys_to_use.is_clear_all())
2160
 
    return(0);
 
2187
    return 0;
2161
2188
  records= head->file->stats.records;
2162
2189
  if (!records)
2163
2190
    records++;                                  /* purecov: inspected */
2168
2195
  if (limit < records)
2169
2196
    read_time= (double) records + scan_time + 1; // Force to use index
2170
2197
  else if (read_time <= 2.0 && !force_quick_range)
2171
 
    return(0);                          /* No need for quick select */
 
2198
    return 0;                           /* No need for quick select */
2172
2199
 
2173
2200
  keys_to_use.intersect(head->keys_in_use_for_query);
2174
2201
  if (!keys_to_use.is_clear_all())
2179
2206
    KEY *key_info;
2180
2207
    PARAM param;
2181
2208
 
2182
 
    if (check_stack_overrun(thd, 2*STACK_MIN_SIZE, NULL))
2183
 
      return(0);                           // Fatal error flag is set
 
2209
    if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
 
2210
      return 0;                           // Fatal error flag is set
2184
2211
 
2185
2212
    /* set up parameter that is passed to all functions */
2186
 
    param.thd= thd;
 
2213
    param.session= session;
2187
2214
    param.baseflag= head->file->ha_table_flags();
2188
2215
    param.prev_tables=prev_tables | const_tables;
2189
2216
    param.read_tables=read_tables;
2191
2218
    param.table=head;
2192
2219
    param.keys=0;
2193
2220
    param.mem_root= &alloc;
2194
 
    param.old_root= thd->mem_root;
 
2221
    param.old_root= session->mem_root;
2195
2222
    param.needed_reg= &needed_reg;
2196
2223
    param.imerge_cost_buff_size= 0;
2197
2224
    param.using_real_indexes= true;
2198
2225
    param.remove_jump_scans= true;
2199
2226
    param.force_default_mrr= ordered_output;
2200
2227
 
2201
 
    thd->no_errors=1;                           // Don't warn about NULL
2202
 
    init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
 
2228
    session->no_errors=1;                               // Don't warn about NULL
 
2229
    init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
2203
2230
    if (!(param.key_parts= (KEY_PART*) alloc_root(&alloc,
2204
2231
                                                  sizeof(KEY_PART)*
2205
2232
                                                  head->s->key_parts)) ||
2206
2233
        fill_used_fields_bitmap(&param))
2207
2234
    {
2208
 
      thd->no_errors=0;
 
2235
      session->no_errors=0;
2209
2236
      free_root(&alloc,MYF(0));                 // Return memory & allocator
2210
 
      return(0);                                // Can't use range
 
2237
      return 0;                         // Can't use range
2211
2238
    }
2212
2239
    key_parts= param.key_parts;
2213
 
    thd->mem_root= &alloc;
 
2240
    session->mem_root= &alloc;
2214
2241
 
2215
2242
    /*
2216
2243
      Make an array with description of all key parts of all table keys.
2225
2252
 
2226
2253
      param.key[param.keys]=key_parts;
2227
2254
      key_part_info= key_info->key_part;
2228
 
      for (uint part=0 ; part < key_info->key_parts ;
 
2255
      for (uint32_t part=0 ; part < key_info->key_parts ;
2229
2256
           part++, key_parts++, key_part_info++)
2230
2257
      {
2231
2258
        key_parts->key=          param.keys;
2246
2273
    /* Calculate cost of full index read for the shortest covering index */
2247
2274
    if (!head->covering_keys.is_clear_all())
2248
2275
    {
2249
 
      int key_for_use= find_shortest_key(head, &head->covering_keys);
2250
 
      double key_read_time= 
2251
 
        param.table->file->index_only_read_time(key_for_use, 
 
2276
      int key_for_use= head->find_shortest_key(&head->covering_keys);
 
2277
      double key_read_time=
 
2278
        param.table->file->index_only_read_time(key_for_use,
2252
2279
                                                rows2double(records)) +
2253
2280
        (double) records / TIME_FOR_COMPARE;
2254
2281
      if (key_read_time < read_time)
2285
2312
    group_trp= get_best_group_min_max(&param, tree);
2286
2313
    if (group_trp)
2287
2314
    {
2288
 
      param.table->quick_condition_rows= min(group_trp->records,
 
2315
      param.table->quick_condition_rows= cmin(group_trp->records,
2289
2316
                                             head->file->stats.records);
2290
2317
      if (group_trp->read_cost < best_read_time)
2291
2318
      {
2319
2346
          objects are not allowed so don't use ROR-intersection for
2320
2347
          table deletes.
2321
2348
        */
2322
 
        if ((thd->lex->sql_command != SQLCOM_DELETE))
 
2349
        if ((session->lex->sql_command != SQLCOM_DELETE))
2323
2350
        {
2324
2351
          /*
2325
2352
            Get best non-covering ROR-intersection plan and prepare data for
2351
2378
        {
2352
2379
          new_conj_trp= get_best_disjunct_quick(&param, imerge, best_read_time);
2353
2380
          if (new_conj_trp)
2354
 
            set_if_smaller(param.table->quick_condition_rows, 
 
2381
            set_if_smaller(param.table->quick_condition_rows,
2355
2382
                           new_conj_trp->records);
2356
2383
          if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
2357
2384
                                 best_conj_trp->read_cost))
2362
2389
      }
2363
2390
    }
2364
2391
 
2365
 
    thd->mem_root= param.old_root;
 
2392
    session->mem_root= param.old_root;
2366
2393
 
2367
2394
    /* If we got a read plan, create a quick select from it. */
2368
2395
    if (best_trp)
2377
2404
 
2378
2405
  free_mem:
2379
2406
    free_root(&alloc,MYF(0));                   // Return memory & allocator
2380
 
    thd->mem_root= param.old_root;
2381
 
    thd->no_errors=0;
 
2407
    session->mem_root= param.old_root;
 
2408
    session->no_errors=0;
2382
2409
  }
2383
2410
 
2384
2411
  /*
2459
2486
{
2460
2487
  SEL_TREE **ptree;
2461
2488
  TRP_INDEX_MERGE *imerge_trp= NULL;
2462
 
  uint n_child_scans= imerge->trees_next - imerge->trees;
 
2489
  uint32_t n_child_scans= imerge->trees_next - imerge->trees;
2463
2490
  TRP_RANGE **range_scans;
2464
2491
  TRP_RANGE **cur_child;
2465
2492
  TRP_RANGE **cpk_scan= NULL;
2470
2497
  bool pk_is_clustered= param->table->file->primary_key_is_clustered();
2471
2498
  bool all_scans_ror_able= true;
2472
2499
  bool all_scans_rors= true;
2473
 
  uint unique_calc_buff_size;
 
2500
  uint32_t unique_calc_buff_size;
2474
2501
  TABLE_READ_PLAN **roru_read_plans;
2475
2502
  TABLE_READ_PLAN **cur_roru_plan;
2476
2503
  double roru_index_costs;
2480
2507
  if (!(range_scans= (TRP_RANGE**)alloc_root(param->mem_root,
2481
2508
                                             sizeof(TRP_RANGE*)*
2482
2509
                                             n_child_scans)))
2483
 
    return(NULL);
 
2510
    return NULL;
2484
2511
  /*
2485
2512
    Collect best 'range' scan for each of disjuncts, and, while doing so,
2486
2513
    analyze possibility of ROR scans. Also calculate some values needed by
2525
2552
      Bail out if it is obvious that both index_merge and ROR-union will be
2526
2553
      more expensive
2527
2554
    */
2528
 
    return(NULL);
 
2555
    return NULL;
2529
2556
  }
2530
2557
  if (all_scans_rors)
2531
2558
  {
2544
2571
  /* Calculate cost(rowid_to_row_scan) */
2545
2572
  {
2546
2573
    COST_VECT sweep_cost;
2547
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2574
    JOIN *join= param->session->lex->select_lex.join;
2548
2575
    bool is_interrupted= test(join && join->tables == 1);
2549
2576
    get_sweep_read_cost(param->table, non_cpk_scan_records, is_interrupted,
2550
2577
                        &sweep_cost);
2557
2584
  unique_calc_buff_size=
2558
2585
    Unique::get_cost_calc_buff_size((ulong)non_cpk_scan_records,
2559
2586
                                    param->table->file->ref_length,
2560
 
                                    param->thd->variables.sortbuff_size);
 
2587
                                    param->session->variables.sortbuff_size);
2561
2588
  if (param->imerge_cost_buff_size < unique_calc_buff_size)
2562
2589
  {
2563
2590
    if (!(param->imerge_cost_buff= (uint*)alloc_root(param->mem_root,
2564
2591
                                                     unique_calc_buff_size)))
2565
 
      return(NULL);
 
2592
      return NULL;
2566
2593
    param->imerge_cost_buff_size= unique_calc_buff_size;
2567
2594
  }
2568
2595
 
2569
2596
  imerge_cost +=
2570
2597
    Unique::get_use_cost(param->imerge_cost_buff, (uint)non_cpk_scan_records,
2571
2598
                         param->table->file->ref_length,
2572
 
                         param->thd->variables.sortbuff_size);
 
2599
                         param->session->variables.sortbuff_size);
2573
2600
  if (imerge_cost < read_time)
2574
2601
  {
2575
2602
    if ((imerge_trp= new (param->mem_root)TRP_INDEX_MERGE))
2576
2603
    {
2577
2604
      imerge_trp->read_cost= imerge_cost;
2578
2605
      imerge_trp->records= non_cpk_scan_records + cpk_scan_records;
2579
 
      imerge_trp->records= min(imerge_trp->records,
 
2606
      imerge_trp->records= cmin(imerge_trp->records,
2580
2607
                               param->table->file->stats.records);
2581
2608
      imerge_trp->range_scans= range_scans;
2582
2609
      imerge_trp->range_scans_end= range_scans + n_child_scans;
2585
2612
  }
2586
2613
 
2587
2614
build_ror_index_merge:
2588
 
  if (!all_scans_ror_able || param->thd->lex->sql_command == SQLCOM_DELETE)
 
2615
  if (!all_scans_ror_able || param->session->lex->sql_command == SQLCOM_DELETE)
2589
2616
    return(imerge_trp);
2590
2617
 
2591
2618
  /* Ok, it is possible to build a ROR-union, try it. */
2660
2687
  double roru_total_cost;
2661
2688
  {
2662
2689
    COST_VECT sweep_cost;
2663
 
    JOIN *join= param->thd->lex->select_lex.join;
 
2690
    JOIN *join= param->session->lex->select_lex.join;
2664
2691
    bool is_interrupted= test(join && join->tables == 1);
2665
2692
    get_sweep_read_cost(param->table, roru_total_records, is_interrupted,
2666
2693
                        &sweep_cost);
2688
2715
 
2689
2716
typedef struct st_ror_scan_info
2690
2717
{
2691
 
  uint      idx;      /* # of used key in param->keys */
2692
 
  uint      keynr;    /* # of used key in table */
 
2718
  uint32_t      idx;      /* # of used key in param->keys */
 
2719
  uint32_t      keynr;    /* # of used key in table */
2693
2720
  ha_rows   records;  /* estimate of # records this scan will return */
2694
2721
 
2695
2722
  /* Set of intervals over key fields that will be used for row retrieval. */
2697
2724
 
2698
2725
  /* Fields used in the query and covered by this ROR scan. */
2699
2726
  MY_BITMAP covered_fields;
2700
 
  uint      used_fields_covered; /* # of set bits in covered_fields */
 
2727
  uint32_t      used_fields_covered; /* # of set bits in covered_fields */
2701
2728
  int       key_rec_length; /* length of key record (including rowid) */
2702
2729
 
2703
2730
  /*
2705
2732
    (assuming there is no need to access full table records)
2706
2733
  */
2707
2734
  double    index_read_cost;
2708
 
  uint      first_uncovered_field; /* first unused bit in covered_fields */
2709
 
  uint      key_components; /* # of parts in the key */
 
2735
  uint32_t      first_uncovered_field; /* first unused bit in covered_fields */
 
2736
  uint32_t      key_components; /* # of parts in the key */
2710
2737
} ROR_SCAN_INFO;
2711
2738
 
2712
2739
 
2730
2757
{
2731
2758
  ROR_SCAN_INFO *ror_scan;
2732
2759
  my_bitmap_map *bitmap_buf;
2733
 
  uint keynr;
 
2760
  uint32_t keynr;
2734
2761
 
2735
2762
  if (!(ror_scan= (ROR_SCAN_INFO*)alloc_root(param->mem_root,
2736
2763
                                             sizeof(ROR_SCAN_INFO))))
2737
 
    return(NULL);
 
2764
    return NULL;
2738
2765
 
2739
2766
  ror_scan->idx= idx;
2740
2767
  ror_scan->keynr= keynr= param->real_keynr[idx];
2745
2772
 
2746
2773
  if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
2747
2774
                                                param->fields_bitmap_size)))
2748
 
    return(NULL);
 
2775
    return NULL;
2749
2776
 
2750
2777
  if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,
2751
2778
                  param->table->s->fields, false))
2752
 
    return(NULL);
 
2779
    return NULL;
2753
2780
  bitmap_clear_all(&ror_scan->covered_fields);
2754
2781
 
2755
2782
  KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2880
2907
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
2881
2908
{
2882
2909
  dst->param= src->param;
2883
 
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap, 
 
2910
  memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
2884
2911
         no_bytes_in_map(&src->covered_fields));
2885
2912
  dst->out_rows= src->out_rows;
2886
2913
  dst->is_covering= src->is_covering;
2895
2922
 
2896
2923
  SYNOPSIS
2897
2924
    ror_scan_selectivity()
2898
 
      info  ROR-interection 
 
2925
      info  ROR-interection
2899
2926
      scan  ROR scan
2900
 
      
 
2927
 
2901
2928
  NOTES
2902
2929
    Suppose we have a condition on several keys
2903
2930
    cond=k_11=c_11 AND k_12=c_12 AND ...  // parts of first key
2980
3007
    Selectivity of given ROR scan.
2981
3008
*/
2982
3009
 
2983
 
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info, 
 
3010
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
2984
3011
                                   const ROR_SCAN_INFO *scan)
2985
3012
{
2986
3013
  double selectivity_mult= 1.0;
2987
3014
  KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part;
2988
 
  uchar key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
2989
 
  uchar *key_ptr= key_val;
 
3015
  unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
 
3016
  unsigned char *key_ptr= key_val;
2990
3017
  SEL_ARG *sel_arg, *tuple_arg= NULL;
2991
3018
  key_part_map keypart_map= 0;
2992
3019
  bool cur_covered;
3082
3109
 
3083
3110
    E(rows_to_retrieve) = #rows_in_table * ror_scan_selectivity(null, scan1) *
3084
3111
                           ror_scan_selectivity({scan1}, scan2) * ... *
3085
 
                           ror_scan_selectivity({scan1,...}, scanN). 
 
3112
                           ror_scan_selectivity({scan1,...}, scanN).
3086
3113
  RETURN
3087
3114
    true   ROR scan added to ROR-intersection, cost updated.
3088
3115
    false  It doesn't make sense to add this ROR scan to this ROR-intersection.
3097
3124
  if (selectivity_mult == 1.0)
3098
3125
  {
3099
3126
    /* Don't add this scan if it doesn't improve selectivity. */
3100
 
    return(false);
 
3127
    return false;
3101
3128
  }
3102
 
  
 
3129
 
3103
3130
  info->out_rows *= selectivity_mult;
3104
 
  
 
3131
 
3105
3132
  if (is_cpk_scan)
3106
3133
  {
3107
3134
    /*
3108
 
      CPK scan is used to filter out rows. We apply filtering for 
 
3135
      CPK scan is used to filter out rows. We apply filtering for
3109
3136
      each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
3110
3137
      per check this gives us:
3111
3138
    */
3112
 
    info->index_scan_costs += rows2double(info->index_records) / 
 
3139
    info->index_scan_costs += rows2double(info->index_records) /
3113
3140
                              TIME_FOR_COMPARE_ROWID;
3114
3141
  }
3115
3142
  else
3128
3155
  if (!info->is_covering)
3129
3156
  {
3130
3157
    COST_VECT sweep_cost;
3131
 
    JOIN *join= info->param->thd->lex->select_lex.join;
 
3158
    JOIN *join= info->param->session->lex->select_lex.join;
3132
3159
    bool is_interrupted= test(join && join->tables == 1);
3133
3160
    get_sweep_read_cost(info->param->table, double2rows(info->out_rows),
3134
3161
                        is_interrupted, &sweep_cost);
3135
3162
    info->total_cost += sweep_cost.total_cost();
3136
3163
  }
3137
 
  return(true);
 
3164
  return true;
3138
3165
}
3139
3166
 
3140
3167
 
3154
3181
 
3155
3182
  NOTES
3156
3183
    get_key_scans_params must be called before this function can be called.
3157
 
    
 
3184
 
3158
3185
    When this function is called by ROR-union construction algorithm it
3159
3186
    assumes it is building an uncovered ROR-intersection (and thus # of full
3160
3187
    records to be retrieved is wrong here). This is a hack.
3176
3203
        firstR= R - first(R);
3177
3204
        if (!selectivity(S + firstR < selectivity(S)))
3178
3205
          continue;
3179
 
          
 
3206
 
3180
3207
        S= S + first(R);
3181
3208
        if (cost(S) < min_cost)
3182
3209
        {
3207
3234
                                          double read_time,
3208
3235
                                          bool *are_all_covering)
3209
3236
{
3210
 
  uint idx;
 
3237
  uint32_t idx;
3211
3238
  double min_cost= DBL_MAX;
3212
3239
 
3213
3240
  if ((tree->n_ror_scans < 2) || !param->table->file->stats.records)
3214
 
    return(NULL);
 
3241
    return NULL;
3215
3242
 
3216
3243
  /*
3217
 
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of 
 
3244
    Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
3218
3245
    them. Also find and save clustered PK scan if there is one.
3219
3246
  */
3220
3247
  ROR_SCAN_INFO **cur_ror_scan;
3221
3248
  ROR_SCAN_INFO *cpk_scan= NULL;
3222
 
  uint cpk_no;
 
3249
  uint32_t cpk_no;
3223
3250
  bool cpk_scan_used= false;
3224
3251
 
3225
3252
  if (!(tree->ror_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3270
3297
 
3271
3298
  /* Create and incrementally update ROR intersection. */
3272
3299
  ROR_INTERSECT_INFO *intersect, *intersect_best;
3273
 
  if (!(intersect= ror_intersect_init(param)) || 
 
3300
  if (!(intersect= ror_intersect_init(param)) ||
3274
3301
      !(intersect_best= ror_intersect_init(param)))
3275
3302
    return NULL;
3276
3303
 
3286
3313
      cur_ror_scan++;
3287
3314
      continue;
3288
3315
    }
3289
 
    
 
3316
 
3290
3317
    *(intersect_scans_end++)= *(cur_ror_scan++);
3291
3318
 
3292
3319
    if (intersect->total_cost < min_cost)
3300
3327
 
3301
3328
  if (intersect_scans_best == intersect_scans)
3302
3329
  {
3303
 
    return(NULL);
 
3330
    return NULL;
3304
3331
  }
3305
 
    
 
3332
 
3306
3333
  print_ror_scans_arr(param->table,
3307
3334
                                          "best ROR-intersection",
3308
3335
                                          intersect_scans,
3309
3336
                                          intersect_scans_best);
3310
3337
 
3311
3338
  *are_all_covering= intersect->is_covering;
3312
 
  uint best_num= intersect_scans_best - intersect_scans;
 
3339
  uint32_t best_num= intersect_scans_best - intersect_scans;
3313
3340
  ror_intersect_cpy(intersect, intersect_best);
3314
3341
 
3315
3342
  /*
3316
3343
    Ok, found the best ROR-intersection of non-CPK key scans.
3317
 
    Check if we should add a CPK scan. If the obtained ROR-intersection is 
 
3344
    Check if we should add a CPK scan. If the obtained ROR-intersection is
3318
3345
    covering, it doesn't make sense to add CPK scan.
3319
3346
  */
3320
3347
  if (cpk_scan && !intersect->is_covering)
3321
3348
  {
3322
 
    if (ror_intersect_add(intersect, cpk_scan, true) && 
 
3349
    if (ror_intersect_add(intersect, cpk_scan, true) &&
3323
3350
        (intersect->total_cost < min_cost))
3324
3351
    {
3325
3352
      cpk_scan_used= true;
3336
3363
    if (!(trp->first_scan=
3337
3364
           (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3338
3365
                                       sizeof(ROR_SCAN_INFO*)*best_num)))
3339
 
      return(NULL);
 
3366
      return NULL;
3340
3367
    memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
3341
3368
    trp->last_scan=  trp->first_scan + best_num;
3342
3369
    trp->is_covering= intersect_best->is_covering;
3408
3435
  ror_scan_mark= tree->ror_scans;
3409
3436
 
3410
3437
  MY_BITMAP *covered_fields= &param->tmp_covered_fields;
3411
 
  if (!covered_fields->bitmap) 
 
3438
  if (!covered_fields->bitmap)
3412
3439
    covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3413
3440
                                               param->fields_bitmap_size);
3414
3441
  if (!covered_fields->bitmap ||
3415
3442
      bitmap_init(covered_fields, covered_fields->bitmap,
3416
3443
                  param->table->s->fields, false))
3417
 
    return(0);
 
3444
    return 0;
3418
3445
  bitmap_clear_all(covered_fields);
3419
3446
 
3420
3447
  double total_cost= 0.0f;
3452
3479
    total_cost += (*ror_scan_mark)->index_read_cost;
3453
3480
    records += (*ror_scan_mark)->records;
3454
3481
    if (total_cost > read_time)
3455
 
      return(NULL);
 
3482
      return NULL;
3456
3483
    /* F=F-covered by first(I) */
3457
3484
    bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3458
3485
    all_covered= bitmap_is_subset(&param->needed_fields, covered_fields);
3459
3486
  } while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3460
 
  
 
3487
 
3461
3488
  if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
3462
 
    return(NULL);
 
3489
    return NULL;
3463
3490
 
3464
3491
  /*
3465
3492
    Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
3475
3502
                (TIME_FOR_COMPARE_ROWID * M_LN2);
3476
3503
 
3477
3504
  if (total_cost > read_time)
3478
 
    return(NULL);
 
3505
    return NULL;
3479
3506
 
3480
3507
  TRP_ROR_INTERSECT *trp;
3481
3508
  if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
3482
3509
    return(trp);
3483
 
  uint best_num= (ror_scan_mark - tree->ror_scans);
 
3510
  uint32_t best_num= (ror_scan_mark - tree->ror_scans);
3484
3511
  if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3485
3512
                                                     sizeof(ROR_SCAN_INFO*)*
3486
3513
                                                     best_num)))
3487
 
    return(NULL);
 
3514
    return NULL;
3488
3515
  memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
3489
3516
  trp->last_scan=  trp->first_scan + best_num;
3490
3517
  trp->is_covering= true;
3491
3518
  trp->read_cost= total_cost;
3492
3519
  trp->records= records;
3493
3520
  trp->cpk_scan= NULL;
3494
 
  set_if_smaller(param->table->quick_condition_rows, records); 
 
3521
  set_if_smaller(param->table->quick_condition_rows, records);
3495
3522
 
3496
3523
  return(trp);
3497
3524
}
3508
3535
                               (except for clustered PK indexes)
3509
3536
      update_tbl_stats         true <=> update table->quick_* with information
3510
3537
                               about range scans we've evaluated.
3511
 
      read_time                Maximum cost. i.e. don't create read plans with 
 
3538
      read_time                Maximum cost. i.e. don't create read plans with
3512
3539
                               cost > read_time.
3513
3540
 
3514
3541
  DESCRIPTION
3515
 
    Find the best "range" table read plan for given SEL_TREE. 
3516
 
    The side effects are 
 
3542
    Find the best "range" table read plan for given SEL_TREE.
 
3543
    The side effects are
3517
3544
     - tree->ror_scans is updated to indicate which scans are ROR scans.
3518
3545
     - if update_tbl_stats=true then table->quick_* is updated with info
3519
3546
       about every possible range scan.
3524
3551
*/
3525
3552
 
3526
3553
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
3527
 
                                       bool index_read_must_be_used, 
 
3554
                                       bool index_read_must_be_used,
3528
3555
                                       bool update_tbl_stats,
3529
3556
                                       double read_time)
3530
3557
{
3531
 
  uint idx;
 
3558
  uint32_t idx;
3532
3559
  SEL_ARG **key,**end, **key_to_read= NULL;
3533
3560
  ha_rows best_records= 0;
3534
 
  uint    best_mrr_flags= 0, best_buf_size= 0;
 
3561
  uint32_t    best_mrr_flags= 0, best_buf_size= 0;
3535
3562
  TRP_RANGE* read_plan= NULL;
3536
3563
  /*
3537
3564
    Note that there may be trees that have type SEL_TREE::KEY but contain no
3548
3575
      ha_rows found_records;
3549
3576
      COST_VECT cost;
3550
3577
      double found_read_time;
3551
 
      uint mrr_flags, buf_size;
3552
 
      uint keynr= param->real_keynr[idx];
 
3578
      uint32_t mrr_flags, buf_size;
 
3579
      uint32_t keynr= param->real_keynr[idx];
3553
3580
      if ((*key)->type == SEL_ARG::MAYBE_KEY ||
3554
3581
          (*key)->maybe_flag)
3555
3582
        param->needed_reg->set_bit(keynr);
3556
3583
 
3557
 
      bool read_index_only= index_read_must_be_used || 
 
3584
      bool read_index_only= index_read_must_be_used ||
3558
3585
                            param->table->covering_keys.is_set(keynr);
3559
3586
 
3560
3587
      found_records= check_quick_select(param, idx, read_index_only, *key,
3595
3622
}
3596
3623
 
3597
3624
 
3598
 
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param,
3599
 
                                            bool retrieve_full_rows __attribute__((unused)),
3600
 
                                            MEM_ROOT *parent_alloc __attribute__((unused)))
 
3625
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
3601
3626
{
3602
3627
  QUICK_INDEX_MERGE_SELECT *quick_imerge;
3603
3628
  QUICK_RANGE_SELECT *quick;
3604
3629
  /* index_merge always retrieves full rows, ignore retrieve_full_rows */
3605
 
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->thd, param->table)))
 
3630
  if (!(quick_imerge= new QUICK_INDEX_MERGE_SELECT(param->session, param->table)))
3606
3631
    return NULL;
3607
3632
 
3608
3633
  quick_imerge->records= records;
3631
3656
  MEM_ROOT *alloc;
3632
3657
 
3633
3658
  if ((quick_intrsect=
3634
 
         new QUICK_ROR_INTERSECT_SELECT(param->thd, param->table,
 
3659
         new QUICK_ROR_INTERSECT_SELECT(param->session, param->table,
3635
3660
                                        (retrieve_full_rows? (!is_covering) :
3636
3661
                                         false),
3637
3662
                                        parent_alloc)))
3649
3674
          quick_intrsect->push_quick_back(quick))
3650
3675
      {
3651
3676
        delete quick_intrsect;
3652
 
        return(NULL);
 
3677
        return NULL;
3653
3678
      }
3654
3679
    }
3655
3680
    if (cpk_scan)
3660
3685
                                    0, alloc)))
3661
3686
      {
3662
3687
        delete quick_intrsect;
3663
 
        return(NULL);
 
3688
        return NULL;
3664
3689
      }
3665
 
      quick->file= NULL; 
 
3690
      quick->file= NULL;
3666
3691
      quick_intrsect->cpk_quick= quick;
3667
3692
    }
3668
3693
    quick_intrsect->records= records;
3672
3697
}
3673
3698
 
3674
3699
 
3675
 
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param,
3676
 
                                          bool retrieve_full_rows __attribute__((unused)),
3677
 
                                          MEM_ROOT *parent_alloc __attribute__((unused)))
 
3700
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
3678
3701
{
3679
3702
  QUICK_ROR_UNION_SELECT *quick_roru;
3680
3703
  TABLE_READ_PLAN **scan;
3683
3706
    It is impossible to construct a ROR-union that will not retrieve full
3684
3707
    rows, ignore retrieve_full_rows parameter.
3685
3708
  */
3686
 
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->thd, param->table)))
 
3709
  if ((quick_roru= new QUICK_ROR_UNION_SELECT(param->session, param->table)))
3687
3710
  {
3688
3711
    for (scan= first_ror; scan != last_ror; scan++)
3689
3712
    {
3690
3713
      if (!(quick= (*scan)->make_quick(param, false, &quick_roru->alloc)) ||
3691
3714
          quick_roru->push_quick_back(quick))
3692
 
        return(NULL);
 
3715
        return NULL;
3693
3716
    }
3694
3717
    quick_roru->records= records;
3695
3718
    quick_roru->read_time= read_cost;
3700
3723
 
3701
3724
/*
3702
3725
  Build a SEL_TREE for <> or NOT BETWEEN predicate
3703
 
 
 
3726
 
3704
3727
  SYNOPSIS
3705
3728
    get_ne_mm_tree()
3706
3729
      param       PARAM from SQL_SELECT::test_quick_select
3710
3733
      gt_value    constant that field should be greaterr
3711
3734
      cmp_type    compare type for the field
3712
3735
 
3713
 
  RETURN 
 
3736
  RETURN
3714
3737
    #  Pointer to tree built tree
3715
3738
    0  on error
3716
3739
*/
3717
3740
 
3718
 
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3741
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3719
3742
                                Field *field,
3720
3743
                                Item *lt_value, Item *gt_value,
3721
3744
                                Item_result cmp_type)
3731
3754
  }
3732
3755
  return tree;
3733
3756
}
3734
 
   
 
3757
 
3735
3758
 
3736
3759
/*
3737
3760
  Build a SEL_TREE for a simple predicate
3738
 
 
 
3761
 
3739
3762
  SYNOPSIS
3740
3763
    get_func_mm_tree()
3741
3764
      param       PARAM from SQL_SELECT::test_quick_select
3744
3767
      value       constant in the predicate
3745
3768
      cmp_type    compare type for the field
3746
3769
      inv         true <> NOT cond_func is considered
3747
 
                  (makes sense only when cond_func is BETWEEN or IN) 
 
3770
                  (makes sense only when cond_func is BETWEEN or IN)
3748
3771
 
3749
 
  RETURN 
 
3772
  RETURN
3750
3773
    Pointer to the tree built tree
3751
3774
*/
3752
3775
 
3753
 
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func, 
 
3776
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3754
3777
                                  Field *field, Item *value,
3755
3778
                                  Item_result cmp_type, bool inv)
3756
3779
{
3804
3827
      so we check it here to avoid unnecessary work.
3805
3828
    */
3806
3829
    if (!func->arg_types_compatible)
3807
 
      break;     
 
3830
      break;
3808
3831
 
3809
3832
    if (inv)
3810
3833
    {
3812
3835
      {
3813
3836
        /*
3814
3837
          We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
3815
 
          where c{i} are constants. Our goal is to produce a SEL_TREE that 
 
3838
          where c{i} are constants. Our goal is to produce a SEL_TREE that
3816
3839
          represents intervals:
3817
 
          
 
3840
 
3818
3841
          ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ...    (*)
3819
 
          
 
3842
 
3820
3843
          where $MIN is either "-inf" or NULL.
3821
 
          
 
3844
 
3822
3845
          The most straightforward way to produce it is to convert NOT IN
3823
3846
          into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
3824
3847
          analyzer to build SEL_TREE from that. The problem is that the
3828
3851
 
3829
3852
          Another problem with big lists like (*) is that a big list is
3830
3853
          unlikely to produce a good "range" access, while considering that
3831
 
          range access will require expensive CPU calculations (and for 
 
3854
          range access will require expensive CPU calculations (and for
3832
3855
          MyISAM even index accesses). In short, big NOT IN lists are rarely
3833
3856
          worth analyzing.
3834
3857
 
3839
3862
        */
3840
3863
#define NOT_IN_IGNORE_THRESHOLD 1000
3841
3864
        MEM_ROOT *tmp_root= param->mem_root;
3842
 
        param->thd->mem_root= param->old_root;
3843
 
        /* 
 
3865
        param->session->mem_root= param->old_root;
 
3866
        /*
3844
3867
          Create one Item_type constant object. We'll need it as
3845
3868
          get_mm_parts only accepts constant values wrapped in Item_Type
3846
3869
          objects.
3847
3870
          We create the Item on param->mem_root which points to
3848
 
          per-statement mem_root (while thd->mem_root is currently pointing
 
3871
          per-statement mem_root (while session->mem_root is currently pointing
3849
3872
          to mem_root local to range optimizer).
3850
3873
        */
3851
3874
        Item *value_item= func->array->create_item();
3852
 
        param->thd->mem_root= tmp_root;
 
3875
        param->session->mem_root= tmp_root;
3853
3876
 
3854
3877
        if (func->array->count > NOT_IN_IGNORE_THRESHOLD || !value_item)
3855
3878
          break;
3856
3879
 
3857
3880
        /* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.  */
3858
 
        uint i=0;
3859
 
        do 
 
3881
        uint32_t i=0;
 
3882
        do
3860
3883
        {
3861
3884
          func->array->value_to_item(i, value_item);
3862
3885
          tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
3888
3911
            }
3889
3912
 
3890
3913
            /* Change all intervals to be "c_{i-1} < X < c_i" */
3891
 
            for (uint idx= 0; idx < param->keys; idx++)
 
3914
            for (uint32_t idx= 0; idx < param->keys; idx++)
3892
3915
            {
3893
3916
              SEL_ARG *new_interval, *last_val;
3894
3917
              if (((new_interval= tree2->keys[idx])) &&
3899
3922
                new_interval->min_flag= NEAR_MIN;
3900
3923
              }
3901
3924
            }
3902
 
            /* 
 
3925
            /*
3903
3926
              The following doesn't try to allocate memory so no need to
3904
3927
              check for NULL.
3905
3928
            */
3906
3929
            tree= tree_or(param, tree, tree2);
3907
3930
          }
3908
3931
        }
3909
 
        
 
3932
 
3910
3933
        if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
3911
3934
        {
3912
 
          /* 
3913
 
            Get the SEL_TREE for the last "c_last < X < +inf" interval 
 
3935
          /*
 
3936
            Get the SEL_TREE for the last "c_last < X < +inf" interval
3914
3937
            (value_item cotains c_last already)
3915
3938
          */
3916
3939
          tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
3929
3952
          for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3930
3953
               arg < end ; arg++)
3931
3954
          {
3932
 
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field, 
 
3955
            tree=  tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
3933
3956
                                                        *arg, *arg, cmp_type));
3934
3957
          }
3935
3958
        }
3936
3959
      }
3937
3960
    }
3938
3961
    else
3939
 
    {    
 
3962
    {
3940
3963
      tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
3941
3964
                         func->arguments()[1], cmp_type);
3942
3965
      if (tree)
3945
3968
        for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3946
3969
             arg < end ; arg++)
3947
3970
        {
3948
 
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field, 
 
3971
          tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3949
3972
                                                  Item_func::EQ_FUNC,
3950
3973
                                                  *arg, cmp_type));
3951
3974
        }
3953
3976
    }
3954
3977
    break;
3955
3978
  }
3956
 
  default: 
 
3979
  default:
3957
3980
  {
3958
 
    /* 
 
3981
    /*
3959
3982
       Here the function for the following predicates are processed:
3960
3983
       <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL.
3961
3984
       If the predicate is of the form (value op field) it is handled
3975
3998
 
3976
3999
/*
3977
4000
  Build conjunction of all SEL_TREEs for a simple predicate applying equalities
3978
 
 
 
4001
 
3979
4002
  SYNOPSIS
3980
4003
    get_full_func_mm_tree()
3981
4004
      param       PARAM from SQL_SELECT::test_quick_select
3983
4006
      field_item  field in the predicate
3984
4007
      value       constant in the predicate
3985
4008
                  (for BETWEEN it contains the number of the field argument,
3986
 
                   for IN it's always 0) 
 
4009
                   for IN it's always 0)
3987
4010
      inv         true <> NOT cond_func is considered
3988
4011
                  (makes sense only when cond_func is BETWEEN or IN)
3989
4012
 
3992
4015
    c is a constant, the function builds a conjunction of all SEL_TREES that can
3993
4016
    be obtained by the substitution of f for all different fields equal to f.
3994
4017
 
3995
 
  NOTES  
 
4018
  NOTES
3996
4019
    If the WHERE condition contains a predicate (fi op c),
3997
4020
    then not only SELL_TREE for this predicate is built, but
3998
4021
    the trees for the results of substitution of fi for
3999
4022
    each fj belonging to the same multiple equality as fi
4000
4023
    are built as well.
4001
 
    E.g. for WHERE t1.a=t2.a AND t2.a > 10 
 
4024
    E.g. for WHERE t1.a=t2.a AND t2.a > 10
4002
4025
    a SEL_TREE for t2.a > 10 will be built for quick select from t2
4003
 
    and   
 
4026
    and
4004
4027
    a SEL_TREE for t1.a > 10 will be built for quick select from t1.
4005
4028
 
4006
4029
    A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
4009
4032
    Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed
4010
4033
    differently. It is considered as a conjuction of two SARGable
4011
4034
    predicates (f1i <= c) and (f2i <=c) and the function get_full_func_mm_tree
4012
 
    is called for each of them separately producing trees for 
4013
 
       AND j (f1j <=c ) and AND j (f2j <= c) 
 
4035
    is called for each of them separately producing trees for
 
4036
       AND j (f1j <=c ) and AND j (f2j <= c)
4014
4037
    After this these two trees are united in one conjunctive tree.
4015
4038
    It's easy to see that the same tree is obtained for
4016
4039
       AND j,k (f1j <=c AND f2k<=c)
4017
 
    which is equivalent to 
 
4040
    which is equivalent to
4018
4041
       AND j,k (c BETWEEN f1j AND f2k).
4019
4042
    The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i)
4020
4043
    which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the
4021
4044
    function get_full_func_mm_tree is called for (f1i > c) and (f2i < c)
4022
4045
    producing trees for AND j (f1j > c) and AND j (f2j < c). Then this two
4023
 
    trees are united in one OR-tree. The expression 
 
4046
    trees are united in one OR-tree. The expression
4024
4047
      (AND j (f1j > c) OR AND j (f2j < c)
4025
4048
    is equivalent to the expression
4026
 
      AND j,k (f1j > c OR f2k < c) 
4027
 
    which is just a translation of 
 
4049
      AND j,k (f1j > c OR f2k < c)
 
4050
    which is just a translation of
4028
4051
      AND j,k (c NOT BETWEEN f1j AND f2k)
4029
4052
 
4030
4053
    In the cases when one of the items f1, f2 is a constant c1 we do not create
4037
4060
    As to IN predicates only ones of the form (f IN (c1,...,cn)),
4038
4061
    where f1 is a field and c1,...,cn are constant, are considered as
4039
4062
    SARGable. We never try to narrow the index scan using predicates of
4040
 
    the form (c IN (c1,...,f,...,cn)). 
4041
 
      
4042
 
  RETURN 
 
4063
    the form (c IN (c1,...,f,...,cn)).
 
4064
 
 
4065
  RETURN
4043
4066
    Pointer to the tree representing the built conjunction of SEL_TREEs
4044
4067
*/
4045
4068
 
4046
4069
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
4047
4070
                                       Item_func *cond_func,
4048
 
                                       Item_field *field_item, Item *value, 
 
4071
                                       Item_field *field_item, Item *value,
4049
4072
                                       bool inv)
4050
4073
{
4051
4074
  SEL_TREE *tree= 0;
4054
4077
  table_map param_comp= ~(param->prev_tables | param->read_tables |
4055
4078
                          param->current_table);
4056
4079
 
4057
 
  for (uint i= 0; i < cond_func->arg_count; i++)
 
4080
  for (uint32_t i= 0; i < cond_func->arg_count; i++)
4058
4081
  {
4059
4082
    Item *arg= cond_func->arguments()[i]->real_item();
4060
4083
    if (arg != field_item)
4105
4128
      while ((item=li++))
4106
4129
      {
4107
4130
        SEL_TREE *new_tree=get_mm_tree(param,item);
4108
 
        if (param->thd->is_fatal_error || 
 
4131
        if (param->session->is_fatal_error ||
4109
4132
            param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
4110
 
          return(0);    // out of memory
 
4133
          return 0;     // out of memory
4111
4134
        tree=tree_and(param,tree,new_tree);
4112
4135
        if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4113
4136
          break;
4123
4146
        {
4124
4147
          SEL_TREE *new_tree=get_mm_tree(param,item);
4125
4148
          if (!new_tree)
4126
 
            return(0);  // out of memory
 
4149
            return 0;   // out of memory
4127
4150
          tree=tree_or(param,tree,new_tree);
4128
4151
          if (!tree || tree->type == SEL_TREE::ALWAYS)
4129
4152
            break;
4136
4159
  if (cond->const_item())
4137
4160
  {
4138
4161
    /*
4139
 
      During the cond->val_int() evaluation we can come across a subselect 
4140
 
      item which may allocate memory on the thd->mem_root and assumes 
4141
 
      all the memory allocated has the same life span as the subselect 
 
4162
      During the cond->val_int() evaluation we can come across a subselect
 
4163
      item which may allocate memory on the session->mem_root and assumes
 
4164
      all the memory allocated has the same life span as the subselect
4142
4165
      item itself. So we have to restore the thread's mem_root here.
4143
4166
    */
4144
4167
    MEM_ROOT *tmp_root= param->mem_root;
4145
 
    param->thd->mem_root= param->old_root;
 
4168
    param->session->mem_root= param->old_root;
4146
4169
    tree= cond->val_int() ? new(tmp_root) SEL_TREE(SEL_TREE::ALWAYS) :
4147
4170
                            new(tmp_root) SEL_TREE(SEL_TREE::IMPOSSIBLE);
4148
 
    param->thd->mem_root= tmp_root;
 
4171
    param->session->mem_root= tmp_root;
4149
4172
    return(tree);
4150
4173
  }
4151
4174
 
4157
4180
    ref_tables= cond->used_tables();
4158
4181
    if ((ref_tables & param->current_table) ||
4159
4182
        (ref_tables & ~(param->prev_tables | param->read_tables)))
4160
 
      return(0);
 
4183
      return 0;
4161
4184
    return(new SEL_TREE(SEL_TREE::MAYBE));
4162
4185
  }
4163
4186
 
4166
4189
      cond_func->functype() == Item_func::IN_FUNC)
4167
4190
    inv= ((Item_func_opt_neg *) cond_func)->negated;
4168
4191
  else if (cond_func->select_optimize() == Item_func::OPTIMIZE_NONE)
4169
 
    return(0);                         
 
4192
    return 0;
4170
4193
 
4171
4194
  param->cond= cond;
4172
4195
 
4182
4205
      Concerning the code below see the NOTES section in
4183
4206
      the comments for the function get_full_func_mm_tree()
4184
4207
    */
4185
 
    for (uint i= 1 ; i < cond_func->arg_count ; i++)
 
4208
    for (uint32_t i= 1 ; i < cond_func->arg_count ; i++)
4186
4209
    {
4187
4210
      if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
4188
4211
      {
4189
4212
        field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
4190
 
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func, 
 
4213
        SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
4191
4214
                                    field_item, (Item*)(intptr_t)i, inv);
4192
4215
        if (inv)
4193
4216
          tree= !tree ? tmp : tree_or(param, tree, tmp);
4194
 
        else 
 
4217
        else
4195
4218
          tree= tree_and(param, tree, tmp);
4196
4219
      }
4197
4220
      else if (inv)
4198
 
      { 
 
4221
      {
4199
4222
        tree= 0;
4200
4223
        break;
4201
4224
      }
4207
4230
  {
4208
4231
    Item_func_in *func=(Item_func_in*) cond_func;
4209
4232
    if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
4210
 
      return(0);
 
4233
      return 0;
4211
4234
    field_item= (Item_field*) (func->key_item()->real_item());
4212
4235
    ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
4213
4236
    break;
4214
4237
  }
4215
4238
  case Item_func::MULT_EQUAL_FUNC:
4216
4239
  {
4217
 
    Item_equal *item_equal= (Item_equal *) cond;    
 
4240
    Item_equal *item_equal= (Item_equal *) cond;
4218
4241
    if (!(value= item_equal->get_const()))
4219
 
      return(0);
 
4242
      return 0;
4220
4243
    Item_equal_iterator it(*item_equal);
4221
4244
    ref_tables= value->used_tables();
4222
4245
    while ((field_item= it++))
4230
4253
        ftree= !ftree ? tree : tree_and(param, ftree, tree);
4231
4254
      }
4232
4255
    }
4233
 
    
 
4256
 
4234
4257
    return(ftree);
4235
4258
  }
4236
4259
  default:
4247
4270
      value= cond_func->arguments()[0];
4248
4271
    }
4249
4272
    else
4250
 
      return(0);
 
4273
      return 0;
4251
4274
    ftree= get_full_func_mm_tree(param, cond_func, field_item, value, inv);
4252
4275
  }
4253
4276
 
4258
4281
static SEL_TREE *
4259
4282
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4260
4283
             Item_func::Functype type,
4261
 
             Item *value,
4262
 
             Item_result cmp_type __attribute__((unused)))
 
4284
             Item *value, Item_result)
4263
4285
{
4264
4286
  if (field->table != param->table)
4265
 
    return(0);
 
4287
    return 0;
4266
4288
 
4267
4289
  KEY_PART *key_part = param->key_parts;
4268
4290
  KEY_PART *end = param->key_parts_end;
4269
4291
  SEL_TREE *tree=0;
4270
4292
  if (value &&
4271
4293
      value->used_tables() & ~(param->prev_tables | param->read_tables))
4272
 
    return(0);
 
4294
    return 0;
4273
4295
  for (; key_part != end ; key_part++)
4274
4296
  {
4275
4297
    if (field->eq(key_part->field))
4276
4298
    {
4277
4299
      SEL_ARG *sel_arg=0;
4278
4300
      if (!tree && !(tree=new SEL_TREE()))
4279
 
        return(0);                              // OOM
 
4301
        return 0;                               // OOM
4280
4302
      if (!value || !(value->used_tables() & ~param->read_tables))
4281
4303
      {
4282
4304
        sel_arg=get_mm_leaf(param,cond_func,
4293
4315
      {
4294
4316
        // This key may be used later
4295
4317
        if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4296
 
          return(0);                    // OOM
 
4318
          return 0;                     // OOM
4297
4319
      }
4298
 
      sel_arg->part=(uchar) key_part->part;
 
4320
      sel_arg->part=(unsigned char) key_part->part;
4299
4321
      tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4300
4322
      tree->keys_map.set_bit(key_part->key);
4301
4323
    }
4302
4324
  }
4303
 
  
 
4325
 
4304
4326
  return(tree);
4305
4327
}
4306
4328
 
4309
4331
get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field,
4310
4332
            KEY_PART *key_part, Item_func::Functype type,Item *value)
4311
4333
{
4312
 
  uint maybe_null=(uint) field->real_maybe_null();
 
4334
  uint32_t maybe_null=(uint) field->real_maybe_null();
4313
4335
  bool optimize_range;
4314
4336
  SEL_ARG *tree= 0;
4315
4337
  MEM_ROOT *alloc= param->mem_root;
4316
 
  uchar *str;
 
4338
  unsigned char *str;
4317
4339
  ulong orig_sql_mode;
4318
4340
  int err;
4319
4341
 
4323
4345
    the argument can be any, e.g. a subselect. The subselect
4324
4346
    items, in turn, assume that all the memory allocated during
4325
4347
    the evaluation has the same life span as the item itself.
4326
 
    TODO: opt_range.cc should not reset thd->mem_root at all.
 
4348
    TODO: opt_range.cc should not reset session->mem_root at all.
4327
4349
  */
4328
 
  param->thd->mem_root= param->old_root;
 
4350
  param->session->mem_root= param->old_root;
4329
4351
  if (!value)                                   // IS NULL or IS NOT NULL
4330
4352
  {
4331
4353
    if (field->table->maybe_null)               // Can't use a key on this
4375
4397
  {
4376
4398
    bool like_error;
4377
4399
    char buff1[MAX_FIELD_WIDTH];
4378
 
    uchar *min_str,*max_str;
 
4400
    unsigned char *min_str,*max_str;
4379
4401
    String tmp(buff1,sizeof(buff1),value->collation.collation),*res;
4380
4402
    size_t length, offset, min_length, max_length;
4381
 
    uint field_length= field->pack_length()+maybe_null;
 
4403
    uint32_t field_length= field->pack_length()+maybe_null;
4382
4404
 
4383
4405
    if (!optimize_range)
4384
4406
      goto end;
4424
4446
        field_length= length;
4425
4447
    }
4426
4448
    length+=offset;
4427
 
    if (!(min_str= (uchar*) alloc_root(alloc, length*2)))
 
4449
    if (!(min_str= (unsigned char*) alloc_root(alloc, length*2)))
4428
4450
      goto end;
4429
4451
 
4430
4452
    max_str=min_str+length;
4467
4489
  /* For comparison purposes allow invalid dates like 2000-01-32 */
4468
4490
  orig_sql_mode= field->table->in_use->variables.sql_mode;
4469
4491
  if (value->real_item()->type() == Item::STRING_ITEM &&
4470
 
      (field->type() == DRIZZLE_TYPE_NEWDATE ||
 
4492
      (field->type() == DRIZZLE_TYPE_DATE ||
4471
4493
       field->type() == DRIZZLE_TYPE_DATETIME))
4472
4494
    field->table->in_use->variables.sql_mode|= MODE_INVALID_DATES;
4473
4495
  err= value->save_in_field_no_warnings(field, 1);
4490
4512
          for the cases like int_field > 999999999999999999999999 as well.
4491
4513
        */
4492
4514
        tree= 0;
4493
 
        if (err == 3 && field->type() == DRIZZLE_TYPE_NEWDATE &&
 
4515
        if (err == 3 && field->type() == DRIZZLE_TYPE_DATE &&
4494
4516
            (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC ||
4495
4517
             type == Item_func::LT_FUNC || type == Item_func::LE_FUNC) )
4496
4518
        {
4499
4521
            but a non-zero time part was cut off.
4500
4522
 
4501
4523
            In MySQL's SQL dialect, DATE and DATETIME are compared as datetime
4502
 
            values. Index over a DATE column uses DATE comparison. Changing 
 
4524
            values. Index over a DATE column uses DATE comparison. Changing
4503
4525
            from one comparison to the other is possible:
4504
4526
 
4505
4527
            datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10'
4542
4564
    goto end;
4543
4565
  }
4544
4566
  field->table->in_use->variables.sql_mode= orig_sql_mode;
4545
 
  str= (uchar*) alloc_root(alloc, key_part->store_length+1);
 
4567
  str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
4546
4568
  if (!str)
4547
4569
    goto end;
4548
4570
  if (maybe_null)
4549
 
    *str= (uchar) field->is_real_null();        // Set to 1 if null
 
4571
    *str= (unsigned char) field->is_real_null();        // Set to 1 if null
4550
4572
  field->get_key_image(str+maybe_null, key_part->length,
4551
4573
                       key_part->image_type);
4552
4574
  if (!(tree= new (alloc) SEL_ARG(field, str, str)))
4611
4633
  }
4612
4634
 
4613
4635
end:
4614
 
  param->thd->mem_root= alloc;
 
4636
  param->session->mem_root= alloc;
4615
4637
  return(tree);
4616
4638
}
4617
4639
 
4692
4714
  }
4693
4715
  key_map  result_keys;
4694
4716
  result_keys.clear_all();
4695
 
  
 
4717
 
4696
4718
  /* Join the trees key per key */
4697
4719
  SEL_ARG **key1,**key2,**end;
4698
4720
  for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
4699
4721
       key1 != end ; key1++,key2++)
4700
4722
  {
4701
 
    uint flag=0;
 
4723
    uint32_t flag=0;
4702
4724
    if (*key1 || *key2)
4703
4725
    {
4704
4726
      if (*key1 && !(*key1)->simple_key())
4713
4735
      }
4714
4736
      result_keys.set_bit(key1 - tree1->keys);
4715
4737
#ifdef EXTRA_DEBUG
4716
 
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
4738
        if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4717
4739
          (*key1)->test_use_count(*key1);
4718
4740
#endif
4719
4741
    }
4738
4760
  using index_merge.
4739
4761
*/
4740
4762
 
4741
 
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, 
 
4763
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4742
4764
                           RANGE_OPT_PARAM* param)
4743
4765
{
4744
4766
  key_map common_keys= tree1->keys_map;
4745
4767
  common_keys.intersect(tree2->keys_map);
4746
4768
 
4747
4769
  if (common_keys.is_clear_all())
4748
 
    return(false);
 
4770
    return false;
4749
4771
 
4750
4772
  /* trees have a common key, check if they refer to same key part */
4751
4773
  SEL_ARG **key1,**key2;
4752
 
  for (uint key_no=0; key_no < param->keys; key_no++)
 
4774
  for (uint32_t key_no=0; key_no < param->keys; key_no++)
4753
4775
  {
4754
4776
    if (common_keys.is_set(key_no))
4755
4777
    {
4757
4779
      key2= tree2->keys + key_no;
4758
4780
      if ((*key1)->part == (*key2)->part)
4759
4781
      {
4760
 
        return(true);
 
4782
        return true;
4761
4783
      }
4762
4784
    }
4763
4785
  }
4764
 
  return(false);
 
4786
  return false;
4765
4787
}
4766
4788
 
4767
4789
 
4770
4792
  SYNOPSIS
4771
4793
    param  Range analysis parameter
4772
4794
    tree   Tree to be processed, tree->type is KEY or KEY_SMALLER
4773
 
 
 
4795
 
4774
4796
  DESCRIPTION
4775
4797
    This function walks through tree->keys[] and removes the SEL_ARG* trees
4776
4798
    that are not "maybe" trees (*) and cannot be used to construct quick range
4782
4804
    tree->part != 0. (e.g. it could represent "keypart2 < const").
4783
4805
 
4784
4806
    WHY THIS FUNCTION IS NEEDED
4785
 
    
 
4807
 
4786
4808
    Normally we allow construction of SEL_TREE objects that have SEL_ARG
4787
4809
    trees that do not allow quick range select construction. For example for
4788
4810
    " keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4791
4813
                                               from this
4792
4814
    call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4793
4815
                                   tree.
4794
 
    
 
4816
 
4795
4817
    There is an exception though: when we construct index_merge SEL_TREE,
4796
4818
    any SEL_ARG* tree that cannot be used to construct quick range select can
4797
4819
    be removed, because current range analysis code doesn't provide any way
4798
4820
    that tree could be later combined with another tree.
4799
4821
    Consider an example: we should not construct
4800
 
    st1 = SEL_TREE { 
4801
 
      merges = SEL_IMERGE { 
4802
 
                            SEL_TREE(t.key1part1 = 1), 
 
4822
    st1 = SEL_TREE {
 
4823
      merges = SEL_IMERGE {
 
4824
                            SEL_TREE(t.key1part1 = 1),
4803
4825
                            SEL_TREE(t.key2part2 = 2)   -- (*)
4804
 
                          } 
 
4826
                          }
4805
4827
                   };
4806
 
    because 
4807
 
     - (*) cannot be used to construct quick range select, 
4808
 
     - There is no execution path that would cause (*) to be converted to 
 
4828
    because
 
4829
     - (*) cannot be used to construct quick range select,
 
4830
     - There is no execution path that would cause (*) to be converted to
4809
4831
       a tree that could be used.
4810
4832
 
4811
4833
    The latter is easy to verify: first, notice that the only way to convert
4812
4834
    (*) into a usable tree is to call tree_and(something, (*)).
4813
4835
 
4814
4836
    Second look at what tree_and/tree_or function would do when passed a
4815
 
    SEL_TREE that has the structure like st1 tree has, and conlcude that 
 
4837
    SEL_TREE that has the structure like st1 tree has, and conlcude that
4816
4838
    tree_and(something, (*)) will not be called.
4817
4839
 
4818
4840
  RETURN
4823
4845
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree)
4824
4846
{
4825
4847
  bool res= false;
4826
 
  for (uint i=0; i < param->keys; i++)
 
4848
  for (uint32_t i=0; i < param->keys; i++)
4827
4849
  {
4828
4850
    if (tree->keys[i])
4829
4851
    {
4844
4866
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4845
4867
{
4846
4868
  if (!tree1 || !tree2)
4847
 
    return(0);
 
4869
    return 0;
4848
4870
  if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4849
4871
    return(tree2);
4850
4872
  if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4870
4892
        result=tree1;                           // Added to tree1
4871
4893
        result_keys.set_bit(key1 - tree1->keys);
4872
4894
#ifdef EXTRA_DEBUG
4873
 
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS) 
 
4895
        if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4874
4896
          (*key1)->test_use_count(*key1);
4875
4897
#endif
4876
4898
      }
4911
4933
    {
4912
4934
      /* one tree is index merge tree and another is range tree */
4913
4935
      if (tree1->merges.is_empty())
4914
 
        swap_variables(SEL_TREE*, tree1, tree2);
4915
 
      
 
4936
        std::swap(tree1, tree2);
 
4937
 
4916
4938
      if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
4917
4939
         return(new SEL_TREE(SEL_TREE::ALWAYS));
4918
4940
      /* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
4922
4944
        result= tree1;
4923
4945
    }
4924
4946
  }
4925
 
  return(result);
 
4947
  return result;
4926
4948
}
4927
4949
 
4928
4950
 
4929
4951
/* And key trees where key1->part < key2 -> part */
4930
4952
 
4931
4953
static SEL_ARG *
4932
 
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, 
4933
 
             uint clone_flag)
 
4954
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
 
4955
             uint32_t clone_flag)
4934
4956
{
4935
4957
  SEL_ARG *next;
4936
4958
  ulong use_count=key1->use_count;
4987
5009
*/
4988
5010
 
4989
5011
static SEL_ARG *
4990
 
key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint clone_flag)
 
5012
key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint32_t clone_flag)
4991
5013
{
4992
5014
  if (!key1)
4993
5015
    return key2;
4997
5019
  {
4998
5020
    if (key1->part > key2->part)
4999
5021
    {
5000
 
      swap_variables(SEL_ARG *, key1, key2);
 
5022
      std::swap(key1, key2);
5001
5023
      clone_flag=swap_clone_flag(clone_flag);
5002
5024
    }
5003
5025
    // key1->part < key2->part
5013
5035
       key2->type != SEL_ARG::MAYBE_KEY) ||
5014
5036
      key1->type == SEL_ARG::MAYBE_KEY)
5015
5037
  {                                             // Put simple key in key2
5016
 
    swap_variables(SEL_ARG *, key1, key2);
 
5038
    std::swap(key1, key2);
5017
5039
    clone_flag=swap_clone_flag(clone_flag);
5018
5040
  }
5019
5041
 
5029
5051
    }
5030
5052
    if (key1->type == SEL_ARG::MAYBE_KEY)
5031
5053
    {                                           // Both are maybe key
5032
 
      key1->next_key_part=key_and(param, key1->next_key_part, 
 
5054
      key1->next_key_part=key_and(param, key1->next_key_part,
5033
5055
                                  key2->next_key_part, clone_flag);
5034
5056
      if (key1->next_key_part &&
5035
5057
          key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5156
5178
  {
5157
5179
    if (key2->use_count == 0 || key1->elements > key2->elements)
5158
5180
    {
5159
 
      swap_variables(SEL_ARG *,key1,key2);
 
5181
      std::swap(key1,key2);
5160
5182
    }
5161
5183
    if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5162
5184
      return 0;                                 // OOM
5241
5263
      }
5242
5264
    }
5243
5265
 
5244
 
    // tmp.max >= key2.min && tmp.min <= key.max  (overlapping ranges)
 
5266
    // tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5245
5267
    if (eq_tree(tmp->next_key_part,key2->next_key_part))
5246
5268
    {
5247
5269
      if (tmp->is_same(key2))
5533
5555
  }
5534
5556
 
5535
5557
  if (root == &null_element)
5536
 
    return(0);                          // Maybe root later
 
5558
    return 0;                           // Maybe root later
5537
5559
  if (remove_color == BLACK)
5538
5560
    root=rb_delete_fixup(root,nod,fix_par);
 
5561
#ifdef EXTRA_DEBUG
5539
5562
  test_rb_tree(root,root->parent);
 
5563
#endif /* EXTRA_DEBUG */
5540
5564
 
5541
5565
  root->use_count=this->use_count;              // Fix root counters
5542
5566
  root->elements=this->elements-1;
5633
5657
    }
5634
5658
  }
5635
5659
  root->color=BLACK;
 
5660
#ifdef EXTRA_DEBUG
5636
5661
  test_rb_tree(root,root->parent);
 
5662
#endif /* EXTRA_DEBUG */
 
5663
 
5637
5664
  return root;
5638
5665
}
5639
5666
 
5728
5755
    return 0;                                   // Found end of tree
5729
5756
  if (element->parent != parent)
5730
5757
  {
5731
 
    sql_print_error("Wrong tree: Parent doesn't point at parent");
 
5758
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5732
5759
    return -1;
5733
5760
  }
5734
5761
  if (element->color == SEL_ARG::RED &&
5735
5762
      (element->left->color == SEL_ARG::RED ||
5736
5763
       element->right->color == SEL_ARG::RED))
5737
5764
  {
5738
 
    sql_print_error("Wrong tree: Found two red in a row");
 
5765
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5739
5766
    return -1;
5740
5767
  }
5741
5768
  if (element->left == element->right && element->left != &null_element)
5742
5769
  {                                             // Dummy test
5743
 
    sql_print_error("Wrong tree: Found right == left");
 
5770
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5744
5771
    return -1;
5745
5772
  }
5746
5773
  count_l=test_rb_tree(element->left,element);
5749
5776
  {
5750
5777
    if (count_l == count_r)
5751
5778
      return count_l+(element->color == SEL_ARG::BLACK);
5752
 
    sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
 
5779
    errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5753
5780
            count_l,count_r);
5754
5781
  }
5755
5782
  return -1;                                    // Error, no more warnings
5758
5785
 
5759
5786
/*
5760
5787
  Count how many times SEL_ARG graph "root" refers to its part "key"
5761
 
  
 
5788
 
5762
5789
  SYNOPSIS
5763
5790
    count_key_part_usage()
5764
5791
      root  An RB-Root node in a SEL_ARG graph.
5769
5796
    root->next->n
5770
5797
 
5771
5798
    This function counts how many times the node "key" is referred (via
5772
 
    SEL_ARG::next_key_part) by 
5773
 
     - intervals of RB-tree pointed by "root", 
5774
 
     - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from 
 
5799
    SEL_ARG::next_key_part) by
 
5800
     - intervals of RB-tree pointed by "root",
 
5801
     - intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5775
5802
       intervals of RB-tree pointed by "root",
5776
5803
     - and so on.
5777
 
    
5778
 
    Here is an example (horizontal links represent next_key_part pointers, 
5779
 
    vertical links - next/prev prev pointers):  
5780
 
    
 
5804
 
 
5805
    Here is an example (horizontal links represent next_key_part pointers,
 
5806
    vertical links - next/prev prev pointers):
 
5807
 
5781
5808
         +----+               $
5782
5809
         |root|-----------------+
5783
5810
         +----+               $ |
5796
5823
          ...     +---+       $    |
5797
5824
                  |   |------------+
5798
5825
                  +---+       $
5799
 
  RETURN 
 
5826
  RETURN
5800
5827
    Number of links to "key" from nodes reachable from "root".
5801
5828
*/
5802
5829
 
5833
5860
 
5834
5861
void SEL_ARG::test_use_count(SEL_ARG *root)
5835
5862
{
5836
 
  uint e_count=0;
 
5863
  uint32_t e_count=0;
5837
5864
  if (this == root && use_count != 1)
5838
5865
  {
5839
 
    sql_print_information("Use_count: Wrong count %lu for root",use_count);
 
5866
    errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5840
5867
    return;
5841
5868
  }
5842
5869
  if (this->type != SEL_ARG::KEY_RANGE)
5849
5876
      ulong count=count_key_part_usage(root,pos->next_key_part);
5850
5877
      if (count > pos->next_key_part->use_count)
5851
5878
      {
5852
 
        sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
 
5879
        errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5853
5880
                              "should be %lu", (long unsigned int)pos,
5854
5881
                              pos->next_key_part->use_count, count);
5855
5882
        return;
5858
5885
    }
5859
5886
  }
5860
5887
  if (e_count != elements)
5861
 
    sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
 
5888
    errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5862
5889
                      e_count, elements, (long unsigned int) this);
5863
5890
}
5864
5891
 
5869
5896
 ****************************************************************************/
5870
5897
 
5871
5898
/* MRR range sequence, SEL_ARG* implementation: stack entry */
5872
 
typedef struct st_range_seq_entry 
 
5899
typedef struct st_range_seq_entry
5873
5900
{
5874
 
  /* 
 
5901
  /*
5875
5902
    Pointers in min and max keys. They point to right-after-end of key
5876
5903
    images. The 0-th entry has these pointing to key tuple start.
5877
5904
  */
5878
 
  uchar *min_key, *max_key;
5879
 
  
5880
 
  /* 
 
5905
  unsigned char *min_key, *max_key;
 
5906
 
 
5907
  /*
5881
5908
    Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
5882
5909
    min_key_flag may have NULL_RANGE set.
5883
5910
  */
5884
 
  uint min_key_flag, max_key_flag;
5885
 
  
 
5911
  uint32_t min_key_flag, max_key_flag;
 
5912
 
5886
5913
  /* Number of key parts */
5887
 
  uint min_key_parts, max_key_parts;
 
5914
  uint32_t min_key_parts, max_key_parts;
5888
5915
  SEL_ARG *key_tree;
5889
5916
} RANGE_SEQ_ENTRY;
5890
5917
 
5894
5921
*/
5895
5922
typedef struct st_sel_arg_range_seq
5896
5923
{
5897
 
  uint keyno;      /* index of used tree in SEL_TREE structure */
5898
 
  uint real_keyno; /* Number of the index in tables */
 
5924
  uint32_t keyno;      /* index of used tree in SEL_TREE structure */
 
5925
  uint32_t real_keyno; /* Number of the index in tables */
5899
5926
  PARAM *param;
5900
5927
  SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
5901
 
  
 
5928
 
5902
5929
  RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
5903
5930
  int i; /* Index of last used element in the above array */
5904
 
  
 
5931
 
5905
5932
  bool at_start; /* true <=> The traversal has just started */
5906
5933
} SEL_ARG_RANGE_SEQ;
5907
5934
 
5912
5939
  SYNOPSIS
5913
5940
    init()
5914
5941
      init_params  SEL_ARG tree traversal context
5915
 
      n_ranges     [ignored] The number of ranges obtained 
 
5942
      n_ranges     [ignored] The number of ranges obtained
5916
5943
      flags        [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
5917
5944
 
5918
5945
  RETURN
5919
5946
    Value of init_param
5920
5947
*/
5921
5948
 
5922
 
range_seq_t sel_arg_range_seq_init(void *init_param,
5923
 
                                   uint n_ranges __attribute__((unused)),
5924
 
                                   uint flags __attribute__((unused)))
 
5949
range_seq_t sel_arg_range_seq_init(void *init_param, uint32_t, uint32_t)
5925
5950
{
5926
5951
  SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
5927
5952
  seq->at_start= true;
5942
5967
{
5943
5968
  RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
5944
5969
  RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
5945
 
  
 
5970
 
5946
5971
  cur->key_tree= key_tree;
5947
5972
  cur->min_key= prev->min_key;
5948
5973
  cur->max_key= prev->max_key;
5966
5991
 
5967
5992
/*
5968
5993
  Range sequence interface, SEL_ARG* implementation: get the next interval
5969
 
  
 
5994
 
5970
5995
  SYNOPSIS
5971
5996
    sel_arg_range_seq_next()
5972
5997
      rseq        Value returned from sel_arg_range_seq_init
5988
6013
*/
5989
6014
 
5990
6015
//psergey-merge-todo: support check_quick_keys:max_keypart
5991
 
uint sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
 
6016
uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
5992
6017
{
5993
6018
  SEL_ARG *key_tree;
5994
6019
  SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
6001
6026
 
6002
6027
  key_tree= seq->stack[seq->i].key_tree;
6003
6028
  /* Ok, we're at some "full tuple" position in the tree */
6004
 
 
 
6029
 
6005
6030
  /* Step down if we can */
6006
6031
  if (key_tree->next && key_tree->next != &null_element)
6007
6032
  {
6038
6063
    Walk right-up while we can
6039
6064
  */
6040
6065
walk_right_n_up:
6041
 
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element && 
 
6066
  while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
6042
6067
         key_tree->next_key_part->part == key_tree->part + 1 &&
6043
6068
         key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6044
6069
  {
6045
6070
    {
6046
6071
      RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6047
 
      uint min_key_length= cur->min_key - seq->param->min_key;
6048
 
      uint max_key_length= cur->max_key - seq->param->max_key;
6049
 
      uint len= cur->min_key - cur[-1].min_key;
 
6072
      uint32_t min_key_length= cur->min_key - seq->param->min_key;
 
6073
      uint32_t max_key_length= cur->max_key - seq->param->max_key;
 
6074
      uint32_t len= cur->min_key - cur[-1].min_key;
6050
6075
      if (!(min_key_length == max_key_length &&
6051
6076
            !memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
6052
6077
            !key_tree->min_flag && !key_tree->max_flag))
6053
6078
      {
6054
6079
        seq->param->is_ror_scan= false;
6055
6080
        if (!key_tree->min_flag)
6056
 
          cur->min_key_parts += 
 
6081
          cur->min_key_parts +=
6057
6082
            key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6058
6083
                                                   &cur->min_key,
6059
6084
                                                   &cur->min_key_flag);
6060
6085
        if (!key_tree->max_flag)
6061
 
          cur->max_key_parts += 
 
6086
          cur->max_key_parts +=
6062
6087
            key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6063
6088
                                                   &cur->max_key,
6064
6089
                                                   &cur->max_key_flag);
6065
6090
        break;
6066
6091
      }
6067
6092
    }
6068
 
  
 
6093
 
6069
6094
    /*
6070
6095
      Ok, current atomic interval is in form "t.field=const" and there is
6071
6096
      next_key_part interval. Step right, and walk up from there.
6083
6108
 
6084
6109
  /* Ok got a tuple */
6085
6110
  RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6086
 
  
 
6111
 
6087
6112
  range->ptr= (char*)(int)(key_tree->part);
6088
6113
  {
6089
6114
    range->range_flag= cur->min_key_flag | cur->max_key_flag;
6090
 
    
 
6115
 
6091
6116
    range->start_key.key=    seq->param->min_key;
6092
6117
    range->start_key.length= cur->min_key - seq->param->min_key;
6093
6118
    range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
6094
 
    range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY : 
 
6119
    range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
6095
6120
                                                           HA_READ_KEY_EXACT);
6096
6121
 
6097
6122
    range->end_key.key=    seq->param->max_key;
6098
6123
    range->end_key.length= cur->max_key - seq->param->max_key;
6099
 
    range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY : 
 
6124
    range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
6100
6125
                                                         HA_READ_AFTER_KEY);
6101
6126
    range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
6102
6127
 
6107
6132
        range->start_key.length == range->end_key.length &&
6108
6133
        !memcmp(seq->param->min_key,seq->param->max_key,range->start_key.length))
6109
6134
      range->range_flag= UNIQUE_RANGE | (cur->min_key_flag & NULL_RANGE);
6110
 
      
 
6135
 
6111
6136
    if (seq->param->is_ror_scan)
6112
6137
    {
6113
6138
      /*
6127
6152
    }
6128
6153
  }
6129
6154
  seq->param->range_count++;
6130
 
  seq->param->max_key_part=max(seq->param->max_key_part,(uint)key_tree->part);
 
6155
  seq->param->max_key_part=cmax(seq->param->max_key_part,(uint)key_tree->part);
6131
6156
  return 0;
6132
6157
}
6133
6158
 
6134
6159
 
6135
6160
/*
6136
 
  Calculate cost and E(#rows) for a given index and intervals tree 
 
6161
  Calculate cost and E(#rows) for a given index and intervals tree
6137
6162
 
6138
6163
  SYNOPSIS
6139
6164
    check_quick_select()
6160
6185
*/
6161
6186
 
6162
6187
static
6163
 
ha_rows check_quick_select(PARAM *param, uint idx, bool index_only,
6164
 
                           SEL_ARG *tree, bool update_tbl_stats, 
6165
 
                           uint *mrr_flags, uint *bufsize, COST_VECT *cost)
 
6188
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
 
6189
                           SEL_ARG *tree, bool update_tbl_stats,
 
6190
                           uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
6166
6191
{
6167
6192
  SEL_ARG_RANGE_SEQ seq;
6168
6193
  RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
6169
6194
  handler *file= param->table->file;
6170
6195
  ha_rows rows;
6171
 
  uint keynr= param->real_keynr[idx];
6172
 
  
 
6196
  uint32_t keynr= param->real_keynr[idx];
 
6197
 
6173
6198
  /* Handle cases when we don't have a valid non-empty list of range */
6174
6199
  if (!tree)
6175
6200
    return(HA_POS_ERROR);
6189
6214
  param->is_ror_scan= true;
6190
6215
  if (file->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)
6191
6216
    param->is_ror_scan= false;
6192
 
  
 
6217
 
6193
6218
  *mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
6194
6219
  *mrr_flags|= HA_MRR_NO_ASSOCIATION;
6195
6220
 
6196
6221
  bool pk_is_clustered= file->primary_key_is_clustered();
6197
 
  if (index_only && 
 
6222
  if (index_only &&
6198
6223
      (file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&
6199
6224
      !(pk_is_clustered && keynr == param->table->s->primary_key))
6200
6225
     *mrr_flags |= HA_MRR_INDEX_ONLY;
6201
 
  
6202
 
  if (current_thd->lex->sql_command != SQLCOM_SELECT)
 
6226
 
 
6227
  if (current_session->lex->sql_command != SQLCOM_SELECT)
6203
6228
    *mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6204
6229
 
6205
 
  *bufsize= param->thd->variables.read_rnd_buff_size;
 
6230
  *bufsize= param->session->variables.read_rnd_buff_size;
6206
6231
  rows= file->multi_range_read_info_const(keynr, &seq_if, (void*)&seq, 0,
6207
6232
                                          bufsize, mrr_flags, cost);
6208
6233
  if (rows != HA_POS_ERROR)
6214
6239
      param->table->quick_key_parts[keynr]=param->max_key_part+1;
6215
6240
      param->table->quick_n_ranges[keynr]= param->range_count;
6216
6241
      param->table->quick_condition_rows=
6217
 
        min(param->table->quick_condition_rows, rows);
 
6242
        cmin(param->table->quick_condition_rows, rows);
6218
6243
    }
6219
6244
  }
6220
6245
  /* Figure out if the key scan is ROR (returns rows in ROWID order) or not */
6221
6246
  enum ha_key_alg key_alg= param->table->key_info[seq.real_keyno].algorithm;
6222
6247
  if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF))
6223
6248
  {
6224
 
    /* 
 
6249
    /*
6225
6250
      All scans are non-ROR scans for those index types.
6226
 
      TODO: Don't have this logic here, make table engines return 
 
6251
      TODO: Don't have this logic here, make table engines return
6227
6252
      appropriate flags instead.
6228
6253
    */
6229
6254
    param->is_ror_scan= false;
6262
6287
 
6263
6288
    where the index is defined on (key1_1, ..., key1_N [,a_1, ..., a_n])
6264
6289
 
6265
 
    and the table has a clustered Primary Key defined as 
6266
 
      PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k) 
6267
 
    
6268
 
    i.e. the first key parts of it are identical to uncovered parts ot the 
 
6290
    and the table has a clustered Primary Key defined as
 
6291
      PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
 
6292
 
 
6293
    i.e. the first key parts of it are identical to uncovered parts ot the
6269
6294
    key being scanned. This function assumes that the index flags do not
6270
6295
    include HA_KEY_SCAN_NOT_ROR flag (that is checked elsewhere).
6271
6296
 
6276
6301
    false  Otherwise
6277
6302
*/
6278
6303
 
6279
 
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8_t nparts)
 
6304
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts)
6280
6305
{
6281
6306
  KEY *table_key= param->table->key_info + keynr;
6282
6307
  KEY_PART_INFO *key_part= table_key->key_part + nparts;
6283
6308
  KEY_PART_INFO *key_part_end= (table_key->key_part +
6284
6309
                                table_key->key_parts);
6285
 
  uint pk_number;
6286
 
  
 
6310
  uint32_t pk_number;
 
6311
 
6287
6312
  for (KEY_PART_INFO *kp= table_key->key_part; kp < key_part; kp++)
6288
6313
  {
6289
6314
    uint16_t fieldnr= param->table->key_info[keynr].
6329
6354
  NOTES
6330
6355
    The caller must call QUICK_SELECT::init for returned quick select.
6331
6356
 
6332
 
    CAUTION! This function may change thd->mem_root to a MEM_ROOT which will be
 
6357
    CAUTION! This function may change session->mem_root to a MEM_ROOT which will be
6333
6358
    deallocated when the returned quick select is deleted.
6334
6359
 
6335
6360
  RETURN
6338
6363
*/
6339
6364
 
6340
6365
QUICK_RANGE_SELECT *
6341
 
get_quick_select(PARAM *param,uint idx,SEL_ARG *key_tree, uint mrr_flags,
6342
 
                 uint mrr_buf_size, MEM_ROOT *parent_alloc)
 
6366
get_quick_select(PARAM *param,uint32_t idx,SEL_ARG *key_tree, uint32_t mrr_flags,
 
6367
                 uint32_t mrr_buf_size, MEM_ROOT *parent_alloc)
6343
6368
{
6344
6369
  QUICK_RANGE_SELECT *quick;
6345
6370
  bool create_err= false;
6346
6371
 
6347
 
  quick=new QUICK_RANGE_SELECT(param->thd, param->table,
 
6372
  quick=new QUICK_RANGE_SELECT(param->session, param->table,
6348
6373
                               param->real_keynr[idx],
6349
6374
                               test(parent_alloc), NULL, &create_err);
6350
6375
 
6368
6393
                    param->table->key_info[param->real_keynr[idx]].key_parts);
6369
6394
    }
6370
6395
  }
6371
 
  return(quick);
 
6396
  return quick;
6372
6397
}
6373
6398
 
6374
6399
 
6377
6402
*/
6378
6403
bool
6379
6404
get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
6380
 
               SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
6381
 
               uchar *max_key, uint max_key_flag)
 
6405
               SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
 
6406
               unsigned char *max_key, uint32_t max_key_flag)
6382
6407
{
6383
6408
  QUICK_RANGE *range;
6384
 
  uint flag;
 
6409
  uint32_t flag;
6385
6410
  int min_part= key_tree->part-1, // # of keypart values in min_key buffer
6386
6411
      max_part= key_tree->part-1; // # of keypart values in max_key buffer
6387
6412
 
6391
6416
                       min_key,min_key_flag, max_key, max_key_flag))
6392
6417
      return 1;
6393
6418
  }
6394
 
  uchar *tmp_min_key=min_key,*tmp_max_key=max_key;
 
6419
  unsigned char *tmp_min_key=min_key,*tmp_max_key=max_key;
6395
6420
  min_part+= key_tree->store_min(key[key_tree->part].store_length,
6396
6421
                                 &tmp_min_key,min_key_flag);
6397
6422
  max_part+= key_tree->store_max(key[key_tree->part].store_length,
6412
6437
      goto end;                                 // Ugly, but efficient
6413
6438
    }
6414
6439
    {
6415
 
      uint tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
 
6440
      uint32_t tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
6416
6441
      if (!tmp_min_flag)
6417
6442
        min_part+= key_tree->next_key_part->store_min_key(key, &tmp_min_key,
6418
6443
                                                          &tmp_min_flag);
6443
6468
  }
6444
6469
  if (flag == 0)
6445
6470
  {
6446
 
    uint length= (uint) (tmp_min_key - param->min_key);
 
6471
    uint32_t length= (uint) (tmp_min_key - param->min_key);
6447
6472
    if (length == (uint) (tmp_max_key - param->max_key) &&
6448
6473
        !memcmp(param->min_key,param->max_key,length))
6449
6474
    {
6476
6501
  set_if_bigger(quick->max_used_key_length, range->min_length);
6477
6502
  set_if_bigger(quick->max_used_key_length, range->max_length);
6478
6503
  set_if_bigger(quick->used_key_parts, (uint) key_tree->part+1);
6479
 
  if (insert_dynamic(&quick->ranges, (uchar*) &range))
 
6504
  if (insert_dynamic(&quick->ranges, (unsigned char*) &range))
6480
6505
    return 1;
6481
6506
 
6482
6507
 end:
6512
6537
  Return true if any part of the key is NULL
6513
6538
 
6514
6539
  SYNOPSIS
6515
 
    null_part_in_key()    
 
6540
    null_part_in_key()
6516
6541
      key_part  Array of key parts (index description)
6517
6542
      key       Key values tuple
6518
6543
      length    Length of key values tuple in bytes.
6522
6547
    false  Otherwise
6523
6548
*/
6524
6549
 
6525
 
static bool null_part_in_key(KEY_PART *key_part, const uchar *key, uint length)
 
6550
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key, uint32_t length)
6526
6551
{
6527
 
  for (const uchar *end=key+length ;
 
6552
  for (const unsigned char *end=key+length ;
6528
6553
       key < end;
6529
6554
       key+= key_part++->store_length)
6530
6555
  {
6582
6607
 
6583
6608
  SYNOPSIS
6584
6609
    get_quick_select_for_ref()
6585
 
      thd      Thread handle
 
6610
      session      Thread handle
6586
6611
      table    Table to access
6587
6612
      ref      ref[_or_null] scan parameters
6588
6613
      records  Estimate of number of records (needed only to construct
6596
6621
    NULL on error.
6597
6622
*/
6598
6623
 
6599
 
QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
 
6624
QUICK_RANGE_SELECT *get_quick_select_for_ref(Session *session, Table *table,
6600
6625
                                             TABLE_REF *ref, ha_rows records)
6601
6626
{
6602
6627
  MEM_ROOT *old_root, *alloc;
6604
6629
  KEY *key_info = &table->key_info[ref->key];
6605
6630
  KEY_PART *key_part;
6606
6631
  QUICK_RANGE *range;
6607
 
  uint part;
 
6632
  uint32_t part;
6608
6633
  bool create_err= false;
6609
6634
  COST_VECT cost;
6610
6635
 
6611
 
  old_root= thd->mem_root;
6612
 
  /* The following call may change thd->mem_root */
6613
 
  quick= new QUICK_RANGE_SELECT(thd, table, ref->key, 0, 0, &create_err);
 
6636
  old_root= session->mem_root;
 
6637
  /* The following call may change session->mem_root */
 
6638
  quick= new QUICK_RANGE_SELECT(session, table, ref->key, 0, 0, &create_err);
6614
6639
  /* save mem_root set by QUICK_RANGE_SELECT constructor */
6615
 
  alloc= thd->mem_root;
 
6640
  alloc= session->mem_root;
6616
6641
  /*
6617
 
    return back default mem_root (thd->mem_root) changed by
 
6642
    return back default mem_root (session->mem_root) changed by
6618
6643
    QUICK_RANGE_SELECT constructor
6619
6644
  */
6620
 
  thd->mem_root= old_root;
 
6645
  session->mem_root= old_root;
6621
6646
 
6622
6647
  if (!quick || create_err)
6623
6648
    return 0;                   /* no ranges found */
6625
6650
    goto err;
6626
6651
  quick->records= records;
6627
6652
 
6628
 
  if ((cp_buffer_from_ref(thd, table, ref) && thd->is_fatal_error) ||
 
6653
  if ((cp_buffer_from_ref(session, ref) && session->is_fatal_error) ||
6629
6654
      !(range= new(alloc) QUICK_RANGE()))
6630
6655
    goto err;                                   // out of memory
6631
6656
 
6649
6674
    key_part->null_bit=     key_info->key_part[part].null_bit;
6650
6675
    key_part->flag=         (uint8_t) key_info->key_part[part].key_part_flag;
6651
6676
  }
6652
 
  if (insert_dynamic(&quick->ranges,(uchar*)&range))
 
6677
  if (insert_dynamic(&quick->ranges,(unsigned char*)&range))
6653
6678
    goto err;
6654
6679
 
6655
6680
  /*
6670
6695
                      make_prev_keypart_map(ref->key_parts), EQ_RANGE)))
6671
6696
      goto err;
6672
6697
    *ref->null_ref_key= 0;              // Clear null byte
6673
 
    if (insert_dynamic(&quick->ranges,(uchar*)&null_range))
 
6698
    if (insert_dynamic(&quick->ranges,(unsigned char*)&null_range))
6674
6699
      goto err;
6675
6700
  }
6676
6701
 
6677
6702
  /* Call multi_range_read_info() to get the MRR flags and buffer size */
6678
 
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION | 
 
6703
  quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
6679
6704
                    (table->key_read ? HA_MRR_INDEX_ONLY : 0);
6680
 
  if (thd->lex->sql_command != SQLCOM_SELECT)
 
6705
  if (session->lex->sql_command != SQLCOM_SELECT)
6681
6706
    quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6682
6707
 
6683
 
  quick->mrr_buf_size= thd->variables.read_rnd_buff_size;
 
6708
  quick->mrr_buf_size= session->variables.read_rnd_buff_size;
6684
6709
  if (table->file->multi_range_read_info(quick->index, 1, (uint)records,
6685
6710
                                         &quick->mrr_buf_size,
6686
6711
                                         &quick->mrr_flags, &cost))
6694
6719
 
6695
6720
 
6696
6721
/*
6697
 
  Perform key scans for all used indexes (except CPK), get rowids and merge 
 
6722
  Perform key scans for all used indexes (except CPK), get rowids and merge
6698
6723
  them into an ordered non-recurrent sequence of rowids.
6699
 
  
 
6724
 
6700
6725
  The merge/duplicate removal is performed using Unique class. We put all
6701
6726
  rowids into Unique, get the sorted sequence and destroy the Unique.
6702
 
  
 
6727
 
6703
6728
  If table has a clustered primary key that covers all rows (true for bdb
6704
6729
  and innodb currently) and one of the index_merge scans is a scan on PK,
6705
 
  then rows that will be retrieved by PK scan are not put into Unique and 
 
6730
  then rows that will be retrieved by PK scan are not put into Unique and
6706
6731
  primary key scan is not performed here, it is performed later separately.
6707
6732
 
6708
6733
  RETURN
6724
6749
  cur_quick_it.rewind();
6725
6750
  cur_quick= cur_quick_it++;
6726
6751
  assert(cur_quick != 0);
6727
 
  
 
6752
 
6728
6753
  /*
6729
 
    We reuse the same instance of handler so we need to call both init and 
 
6754
    We reuse the same instance of handler so we need to call both init and
6730
6755
    reset here.
6731
6756
  */
6732
6757
  if (cur_quick->init() || cur_quick->reset())
6733
 
    return(1);
 
6758
    return 0;
6734
6759
 
6735
6760
  unique= new Unique(refpos_order_cmp, (void *)file,
6736
6761
                     file->ref_length,
6737
 
                     thd->variables.sortbuff_size);
 
6762
                     session->variables.sortbuff_size);
6738
6763
  if (!unique)
6739
 
    return(1);
 
6764
    return 0;
6740
6765
  for (;;)
6741
6766
  {
6742
6767
    while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6746
6771
      if (!cur_quick)
6747
6772
        break;
6748
6773
 
6749
 
      if (cur_quick->file->inited != handler::NONE) 
 
6774
      if (cur_quick->file->inited != handler::NONE)
6750
6775
        cur_quick->file->ha_index_end();
6751
6776
      if (cur_quick->init() || cur_quick->reset())
6752
 
        return(1);
 
6777
        return 0;
6753
6778
    }
6754
6779
 
6755
6780
    if (result)
6757
6782
      if (result != HA_ERR_END_OF_FILE)
6758
6783
      {
6759
6784
        cur_quick->range_end();
6760
 
        return(result);
 
6785
        return result;
6761
6786
      }
6762
6787
      break;
6763
6788
    }
6764
6789
 
6765
 
    if (thd->killed)
6766
 
      return(1);
 
6790
    if (session->killed)
 
6791
      return 0;
6767
6792
 
6768
6793
    /* skip row if it will be retrieved by clustered PK scan */
6769
6794
    if (pk_quick_select && pk_quick_select->row_in_ranges())
6772
6797
    cur_quick->file->position(cur_quick->record);
6773
6798
    result= unique->unique_add((char*)cur_quick->file->ref);
6774
6799
    if (result)
6775
 
      return(1);
 
6800
      return 0;
6776
6801
 
6777
6802
  }
6778
6803
 
6783
6808
  /* index_merge currently doesn't support "using index" at all */
6784
6809
  file->extra(HA_EXTRA_NO_KEYREAD);
6785
6810
  /* start table scan */
6786
 
  init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6787
 
  return(result);
 
6811
  init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
 
6812
  return result;
6788
6813
}
6789
6814
 
6790
6815
 
6814
6839
      doing_pk_scan= true;
6815
6840
      if ((result= pk_quick_select->init()) ||
6816
6841
          (result= pk_quick_select->reset()))
6817
 
        return(result);
 
6842
        return result;
6818
6843
      return(pk_quick_select->get_next());
6819
6844
    }
6820
6845
  }
6821
6846
 
6822
 
  return(result);
 
6847
  return result;
6823
6848
}
6824
6849
 
6825
6850
 
6848
6873
  List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6849
6874
  QUICK_RANGE_SELECT* quick;
6850
6875
  int error, cmp;
6851
 
  uint last_rowid_count=0;
 
6876
  uint32_t last_rowid_count=0;
6852
6877
 
6853
6878
  do
6854
6879
  {
6932
6957
{
6933
6958
  int error, dup_row;
6934
6959
  QUICK_SELECT_I *quick;
6935
 
  uchar *tmp;
 
6960
  unsigned char *tmp;
6936
6961
 
6937
6962
  do
6938
6963
  {
6980
7005
 
6981
7006
int QUICK_RANGE_SELECT::reset()
6982
7007
{
6983
 
  uint  buf_size;
6984
 
  uchar *mrange_buff;
 
7008
  uint32_t  buf_size;
 
7009
  unsigned char *mrange_buff;
6985
7010
  int   error;
6986
7011
  HANDLER_BUFFER empty_buf;
6987
7012
  last_range= NULL;
6989
7014
 
6990
7015
  if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6991
7016
    return(error);
6992
 
 
 
7017
 
6993
7018
  /* Allocate buffer if we need one but haven't allocated it yet */
6994
7019
  if (mrr_buf_size && !mrr_buf_desc)
6995
7020
  {
6997
7022
    while (buf_size && !my_multi_malloc(MYF(MY_WME),
6998
7023
                                        &mrr_buf_desc, sizeof(*mrr_buf_desc),
6999
7024
                                        &mrange_buff, buf_size,
7000
 
                                        NullS))
 
7025
                                        NULL))
7001
7026
    {
7002
7027
      /* Try to shrink the buffers until both are 0. */
7003
7028
      buf_size/= 2;
7013
7038
 
7014
7039
  if (!mrr_buf_desc)
7015
7040
    empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7016
 
 
 
7041
 
7017
7042
  if (sorted)
7018
7043
     mrr_flags |= HA_MRR_SORTED;
7019
7044
  RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7020
7045
  error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7021
 
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc: 
 
7046
                                     mrr_flags, mrr_buf_desc? mrr_buf_desc:
7022
7047
                                                              &empty_buf);
7023
7048
  return(error);
7024
7049
}
7026
7051
 
7027
7052
/*
7028
7053
  Range sequence interface implementation for array<QUICK_RANGE>: initialize
7029
 
  
 
7054
 
7030
7055
  SYNOPSIS
7031
7056
    quick_range_seq_init()
7032
7057
      init_param  Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
7033
7058
      n_ranges    Number of ranges in the sequence (ignored)
7034
 
      flags       MRR flags (currently not used) 
 
7059
      flags       MRR flags (currently not used)
7035
7060
 
7036
7061
  RETURN
7037
7062
    Opaque value to be passed to quick_range_seq_next
7038
7063
*/
7039
7064
 
7040
 
range_seq_t quick_range_seq_init(void *init_param,
7041
 
                                 uint n_ranges __attribute__((unused)),
7042
 
                                 uint flags __attribute__((unused)))
 
7065
range_seq_t quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7043
7066
{
7044
7067
  QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7045
7068
  quick->qr_traversal_ctx.first=  (QUICK_RANGE**)quick->ranges.buffer;
7052
7075
 
7053
7076
/*
7054
7077
  Range sequence interface implementation for array<QUICK_RANGE>: get next
7055
 
  
 
7078
 
7056
7079
  SYNOPSIS
7057
7080
    quick_range_seq_next()
7058
7081
      rseq        Value returned from quick_range_seq_init
7063
7086
    1  No more ranges in the sequence
7064
7087
*/
7065
7088
 
7066
 
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
 
7089
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7067
7090
{
7068
7091
  QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
7069
7092
 
7108
7131
    function returns a reference to the "range_flag" associated with the
7109
7132
    range number idx.
7110
7133
 
7111
 
    This function should be removed when we get a proper MRR/NDB 
 
7134
    This function should be removed when we get a proper MRR/NDB
7112
7135
    implementation.
7113
7136
 
7114
7137
  RETURN
7115
7138
    Reference to range_flag associated with range number #idx
7116
7139
*/
7117
7140
 
7118
 
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint idx)
 
7141
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7119
7142
{
7120
7143
  QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7121
7144
  return ctx->first[idx]->flag;
7147
7170
    Reference to range-associated data
7148
7171
*/
7149
7172
 
7150
 
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7151
 
                          uint idx __attribute__((unused)))
 
7173
char* &mrr_get_ptr_by_idx(range_seq_t, uint32_t)
7152
7174
{
7153
7175
  static char *dummy;
7154
7176
  return dummy;
7189
7211
    /* Restore bitmaps set on entry */
7190
7212
    head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7191
7213
  }
7192
 
  return(result);
 
7214
  return result;
7193
7215
}
7194
7216
 
7195
7217
 
7221
7243
    other              if some error occurred
7222
7244
*/
7223
7245
 
7224
 
int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
 
7246
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7225
7247
                                        key_part_map keypart_map,
7226
 
                                        uchar *cur_prefix)
 
7248
                                        unsigned char *cur_prefix)
7227
7249
{
7228
7250
  for (;;)
7229
7251
  {
7236
7258
      result= file->index_read_map(record, cur_prefix, keypart_map,
7237
7259
                                   HA_READ_AFTER_KEY);
7238
7260
      if (result || (file->compare_key(file->end_range) <= 0))
7239
 
        return(result);
 
7261
        return result;
7240
7262
    }
7241
7263
 
7242
 
    uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
 
7264
    uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7243
7265
    if (count == 0)
7244
7266
    {
7245
7267
      /* Ranges have already been used up before. None is left for read. */
7246
7268
      last_range= 0;
7247
 
      return(HA_ERR_END_OF_FILE);
 
7269
      return HA_ERR_END_OF_FILE;
7248
7270
    }
7249
7271
    last_range= *(cur_range++);
7250
7272
 
7251
 
    start_key.key=    (const uchar*) last_range->min_key;
7252
 
    start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
 
7273
    start_key.key=    (const unsigned char*) last_range->min_key;
 
7274
    start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7253
7275
    start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7254
7276
    start_key.flag=   ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7255
7277
                       (last_range->flag & EQ_RANGE) ?
7256
7278
                       HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7257
 
    end_key.key=      (const uchar*) last_range->max_key;
7258
 
    end_key.length=   min(last_range->max_length, (uint16_t)prefix_length);
 
7279
    end_key.key=      (const unsigned char*) last_range->max_key;
 
7280
    end_key.length=   cmin(last_range->max_length, (uint16_t)prefix_length);
7259
7281
    end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7260
7282
    /*
7261
7283
      We use READ_AFTER_KEY here because if we are reading on a key
7272
7294
      last_range= 0;                    // Stop searching
7273
7295
 
7274
7296
    if (result != HA_ERR_END_OF_FILE)
7275
 
      return(result);
 
7297
      return result;
7276
7298
    last_range= 0;                      // No matching rows; go to next range
7277
7299
  }
7278
7300
}
7299
7321
bool QUICK_RANGE_SELECT::row_in_ranges()
7300
7322
{
7301
7323
  QUICK_RANGE *res;
7302
 
  uint min= 0;
7303
 
  uint max= ranges.elements - 1;
7304
 
  uint mid= (max + min)/2;
 
7324
  uint32_t min= 0;
 
7325
  uint32_t max= ranges.elements - 1;
 
7326
  uint32_t mid= (max + min)/2;
7305
7327
 
7306
7328
  while (min != max)
7307
7329
  {
7328
7350
  for now, this seems to work right at least.
7329
7351
 */
7330
7352
 
7331
 
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7332
 
                                     uint used_key_parts_arg __attribute__((unused)),
7333
 
                                     bool *create_err __attribute__((unused)))
 
7353
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7334
7354
 :QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7335
7355
{
7336
7356
  QUICK_RANGE *r;
7378
7398
      if (!result)
7379
7399
      {
7380
7400
        if (cmp_prev(*rev_it.ref()) == 0)
7381
 
          return(0);
 
7401
          return 0;
7382
7402
      }
7383
7403
      else if (result != HA_ERR_END_OF_FILE)
7384
 
        return(result);
 
7404
        return result;
7385
7405
    }
7386
7406
 
7387
7407
    if (!(last_range= rev_it++))
7388
 
      return(HA_ERR_END_OF_FILE);               // All ranges used
 
7408
      return HA_ERR_END_OF_FILE;                // All ranges used
7389
7409
 
7390
7410
    if (last_range->flag & NO_MAX_RANGE)        // Read last record
7391
7411
    {
7393
7413
      if ((local_error=file->index_last(record)))
7394
7414
        return(local_error);            // Empty table
7395
7415
      if (cmp_prev(last_range) == 0)
7396
 
        return(0);
 
7416
        return 0;
7397
7417
      last_range= 0;                            // No match; go to next range
7398
7418
      continue;
7399
7419
    }
7417
7437
    if (result)
7418
7438
    {
7419
7439
      if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7420
 
        return(result);
 
7440
        return result;
7421
7441
      last_range= 0;                            // Not found, to next range
7422
7442
      continue;
7423
7443
    }
7425
7445
    {
7426
7446
      if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7427
7447
        last_range= 0;                          // Stop searching
7428
 
      return(0);                                // Found key is in range
 
7448
      return 0;                         // Found key is in range
7429
7449
    }
7430
7450
    last_range= 0;                              // To next range
7431
7451
  }
7435
7455
/*
7436
7456
  Compare if found key is over max-value
7437
7457
  Returns 0 if key <= range->max_key
7438
 
  TODO: Figure out why can't this function be as simple as cmp_prev(). 
 
7458
  TODO: Figure out why can't this function be as simple as cmp_prev().
7439
7459
*/
7440
7460
 
7441
7461
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7444
7464
    return 0;                                   /* key can't be to large */
7445
7465
 
7446
7466
  KEY_PART *key_part=key_parts;
7447
 
  uint store_length;
 
7467
  uint32_t store_length;
7448
7468
 
7449
 
  for (uchar *key=range_arg->max_key, *end=key+range_arg->max_length;
 
7469
  for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7450
7470
       key < end;
7451
7471
       key+= store_length, key_part++)
7452
7472
  {
7579
7599
                                              String *used_lengths)
7580
7600
{
7581
7601
  char buf[64];
7582
 
  uint length;
 
7602
  uint32_t length;
7583
7603
  KEY *key_info= head->key_info + index;
7584
7604
  key_names->append(key_info->name);
7585
7605
  length= int64_t2str(max_used_key_length, buf, 10) - buf;
7590
7610
                                                    String *used_lengths)
7591
7611
{
7592
7612
  char buf[64];
7593
 
  uint length;
 
7613
  uint32_t length;
7594
7614
  bool first= true;
7595
7615
  QUICK_RANGE_SELECT *quick;
7596
7616
 
7625
7645
                                                      String *used_lengths)
7626
7646
{
7627
7647
  char buf[64];
7628
 
  uint length;
 
7648
  uint32_t length;
7629
7649
  bool first= true;
7630
7650
  QUICK_RANGE_SELECT *quick;
7631
7651
  List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7679
7699
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7680
7700
*******************************************************************************/
7681
7701
 
7682
 
static inline uint get_field_keypart(KEY *index, Field *field);
7683
 
static inline SEL_ARG * get_index_range_tree(uint index, SEL_TREE* range_tree,
7684
 
                                             PARAM *param, uint *param_idx);
 
7702
static inline uint32_t get_field_keypart(KEY *index, Field *field);
 
7703
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
 
7704
                                             PARAM *param, uint32_t *param_idx);
7685
7705
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7686
7706
                       KEY_PART_INFO *first_non_group_part,
7687
7707
                       KEY_PART_INFO *min_max_arg_part,
7688
 
                       KEY_PART_INFO *last_part, THD *thd,
7689
 
                       uchar *key_infix, uint *key_infix_len,
 
7708
                       KEY_PART_INFO *last_part, Session *session,
 
7709
                       unsigned char *key_infix, uint32_t *key_infix_len,
7690
7710
                       KEY_PART_INFO **first_non_infix_part);
7691
7711
static bool
7692
7712
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7693
7713
                               Field::imagetype image_type);
7694
7714
 
7695
7715
static void
7696
 
cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts,
7697
 
                   uint group_key_parts, SEL_TREE *range_tree,
 
7716
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
 
7717
                   uint32_t group_key_parts, SEL_TREE *range_tree,
7698
7718
                   SEL_ARG *index_tree, ha_rows quick_prefix_records,
7699
7719
                   bool have_min, bool have_max,
7700
7720
                   double *read_cost, ha_rows *records);
7728
7748
        - NGA = QA - (GA union C) = {NG_1, ..., NG_m} - the ones not in
7729
7749
          GROUP BY and not referenced by MIN/MAX functions.
7730
7750
        with the following properties specified below.
7731
 
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not 
 
7751
    B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
7732
7752
        applicable.
7733
7753
 
7734
7754
    SA1. There is at most one attribute in SA referenced by any number of
7816
7836
    other field as in: "select min(a) from t1 group by a" ?
7817
7837
  - We assume that the general correctness of the GROUP-BY query was checked
7818
7838
    before this point. Is this correct, or do we have to check it completely?
7819
 
  - Lift the limitation in condition (B3), that is, make this access method 
 
7839
  - Lift the limitation in condition (B3), that is, make this access method
7820
7840
    applicable to ROLLUP queries.
7821
7841
 
7822
7842
  RETURN
7831
7851
static TRP_GROUP_MIN_MAX *
7832
7852
get_best_group_min_max(PARAM *param, SEL_TREE *tree)
7833
7853
{
7834
 
  THD *thd= param->thd;
7835
 
  JOIN *join= thd->lex->current_select->join;
7836
 
  TABLE *table= param->table;
 
7854
  Session *session= param->session;
 
7855
  JOIN *join= session->lex->current_select->join;
 
7856
  Table *table= param->table;
7837
7857
  bool have_min= false;              /* true if there is a MIN function. */
7838
7858
  bool have_max= false;              /* true if there is a MAX function. */
7839
7859
  Item_field *min_max_arg_item= NULL; // The argument of all MIN/MAX functions
7840
7860
  KEY_PART_INFO *min_max_arg_part= NULL; /* The corresponding keypart. */
7841
 
  uint group_prefix_len= 0; /* Length (in bytes) of the key prefix. */
 
7861
  uint32_t group_prefix_len= 0; /* Length (in bytes) of the key prefix. */
7842
7862
  KEY *index_info= NULL;    /* The index chosen for data access. */
7843
 
  uint index= 0;            /* The id of the chosen index. */
7844
 
  uint group_key_parts= 0;  // Number of index key parts in the group prefix.
7845
 
  uint used_key_parts= 0;   /* Number of index key parts used for access. */
7846
 
  uchar key_infix[MAX_KEY_LENGTH]; /* Constants from equality predicates.*/
7847
 
  uint key_infix_len= 0;          /* Length of key_infix. */
 
7863
  uint32_t index= 0;            /* The id of the chosen index. */
 
7864
  uint32_t group_key_parts= 0;  // Number of index key parts in the group prefix.
 
7865
  uint32_t used_key_parts= 0;   /* Number of index key parts used for access. */
 
7866
  unsigned char key_infix[MAX_KEY_LENGTH]; /* Constants from equality predicates.*/
 
7867
  uint32_t key_infix_len= 0;          /* Length of key_infix. */
7848
7868
  TRP_GROUP_MIN_MAX *read_plan= NULL; /* The eventually constructed TRP. */
7849
 
  uint key_part_nr;
7850
 
  ORDER *tmp_group;
 
7869
  uint32_t key_part_nr;
 
7870
  order_st *tmp_group;
7851
7871
  Item *item;
7852
7872
  Item_field *item_field;
7853
7873
 
7854
7874
  /* Perform few 'cheap' tests whether this access method is applicable. */
7855
7875
  if (!join)
7856
 
    return(NULL);        /* This is not a select statement. */
 
7876
    return NULL;        /* This is not a select statement. */
7857
7877
  if ((join->tables != 1) ||  /* The query must reference one table. */
7858
7878
      ((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
7859
7879
       (!join->select_distinct)) ||
7860
7880
      (join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
7861
 
    return(NULL);
 
7881
    return NULL;
7862
7882
  if (table->s->keys == 0)        /* There are no indexes to use. */
7863
 
    return(NULL);
 
7883
    return NULL;
7864
7884
 
7865
7885
  /* Analyze the query in more detail. */
7866
7886
  List_iterator<Item> select_items_it(join->fields_list);
7867
7887
 
7868
7888
  /* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
7869
7889
  if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
7870
 
    return(NULL);
 
7890
    return NULL;
7871
7891
  if (join->sum_funcs[0])
7872
7892
  {
7873
7893
    Item_sum *min_max_item;
7879
7899
      else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
7880
7900
        have_max= true;
7881
7901
      else
7882
 
        return(NULL);
 
7902
        return NULL;
7883
7903
 
7884
7904
      /* The argument of MIN/MAX. */
7885
 
      Item *expr= min_max_item->args[0]->real_item();    
 
7905
      Item *expr= min_max_item->args[0]->real_item();
7886
7906
      if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */
7887
7907
      {
7888
7908
        if (! min_max_arg_item)
7889
7909
          min_max_arg_item= (Item_field*) expr;
7890
7910
        else if (! min_max_arg_item->eq(expr, 1))
7891
 
          return(NULL);
 
7911
          return NULL;
7892
7912
      }
7893
7913
      else
7894
 
        return(NULL);
 
7914
        return NULL;
7895
7915
    }
7896
7916
  }
7897
7917
 
7901
7921
    while ((item= select_items_it++))
7902
7922
    {
7903
7923
      if (item->type() != Item::FIELD_ITEM)
7904
 
        return(NULL);
 
7924
        return NULL;
7905
7925
    }
7906
7926
  }
7907
7927
 
7909
7929
  for (tmp_group= join->group_list; tmp_group; tmp_group= tmp_group->next)
7910
7930
  {
7911
7931
    if ((*tmp_group->item)->type() != Item::FIELD_ITEM)
7912
 
      return(NULL);
 
7932
      return NULL;
7913
7933
  }
7914
7934
 
7915
7935
  /*
7925
7945
  KEY_PART_INFO *last_part= NULL;
7926
7946
  KEY_PART_INFO *first_non_group_part= NULL;
7927
7947
  KEY_PART_INFO *first_non_infix_part= NULL;
7928
 
  uint key_infix_parts= 0;
7929
 
  uint cur_group_key_parts= 0;
7930
 
  uint cur_group_prefix_len= 0;
 
7948
  uint32_t key_infix_parts= 0;
 
7949
  uint32_t cur_group_key_parts= 0;
 
7950
  uint32_t cur_group_prefix_len= 0;
7931
7951
  /* Cost-related variables for the best index so far. */
7932
7952
  double best_read_cost= DBL_MAX;
7933
7953
  ha_rows best_records= 0;
7934
7954
  SEL_ARG *best_index_tree= NULL;
7935
7955
  ha_rows best_quick_prefix_records= 0;
7936
 
  uint best_param_idx= 0;
 
7956
  uint32_t best_param_idx= 0;
7937
7957
  double cur_read_cost= DBL_MAX;
7938
7958
  ha_rows cur_records;
7939
7959
  SEL_ARG *cur_index_tree= NULL;
7940
7960
  ha_rows cur_quick_prefix_records= 0;
7941
 
  uint cur_param_idx=MAX_KEY;
 
7961
  uint32_t cur_param_idx=MAX_KEY;
7942
7962
  key_map cur_used_key_parts;
7943
 
  uint pk= param->table->s->primary_key;
 
7963
  uint32_t pk= param->table->s->primary_key;
7944
7964
 
7945
 
  for (uint cur_index= 0 ; cur_index_info != cur_index_info_end ;
 
7965
  for (uint32_t cur_index= 0 ; cur_index_info != cur_index_info_end ;
7946
7966
       cur_index_info++, cur_index++)
7947
7967
  {
7948
7968
    /* Check (B1) - if current index is covering. */
7962
7982
        (table->file->ha_table_flags() & HA_PRIMARY_KEY_IN_READ_INDEX))
7963
7983
    {
7964
7984
      /* For each table field */
7965
 
      for (uint i= 0; i < table->s->fields; i++)
 
7985
      for (uint32_t i= 0; i < table->s->fields; i++)
7966
7986
      {
7967
7987
        Field *cur_field= table->field[i];
7968
7988
        /*
8005
8025
    }
8006
8026
    /*
8007
8027
      Check (GA2) if this is a DISTINCT query.
8008
 
      If GA2, then Store a new ORDER object in group_fields_array at the
8009
 
      position of the key part of item_field->field. Thus we get the ORDER
 
8028
      If GA2, then Store a new order_st object in group_fields_array at the
 
8029
      position of the key part of item_field->field. Thus we get the order_st
8010
8030
      objects for each field ordered as the corresponding key parts.
8011
 
      Later group_fields_array of ORDER objects is used to convert the query
 
8031
      Later group_fields_array of order_st objects is used to convert the query
8012
8032
      to a GROUP query.
8013
8033
    */
8014
8034
    else if (join->select_distinct)
8015
8035
    {
8016
8036
      select_items_it.rewind();
8017
8037
      cur_used_key_parts.clear_all();
8018
 
      uint max_key_part= 0;
 
8038
      uint32_t max_key_part= 0;
8019
8039
      while ((item= select_items_it++))
8020
8040
      {
8021
8041
        item_field= (Item_field*) item; /* (SA5) already checked above. */
8033
8053
        cur_group_prefix_len+= cur_part->store_length;
8034
8054
        cur_used_key_parts.set_bit(key_part_nr);
8035
8055
        ++cur_group_key_parts;
8036
 
        max_key_part= max(max_key_part,key_part_nr);
 
8056
        max_key_part= cmax(max_key_part,key_part_nr);
8037
8057
      }
8038
8058
      /*
8039
8059
        Check that used key parts forms a prefix of the index.
8088
8108
    {
8089
8109
      if (tree)
8090
8110
      {
8091
 
        uint dummy;
 
8111
        uint32_t dummy;
8092
8112
        SEL_ARG *index_range_tree= get_index_range_tree(cur_index, tree, param,
8093
8113
                                                        &dummy);
8094
8114
        if (!get_constant_key_infix(cur_index_info, index_range_tree,
8095
8115
                                    first_non_group_part, min_max_arg_part,
8096
 
                                    last_part, thd, key_infix, &key_infix_len,
 
8116
                                    last_part, session, key_infix, &key_infix_len,
8097
8117
                                    &first_non_infix_part))
8098
8118
          goto next_index;
8099
8119
      }
8126
8146
 
8127
8147
        /* Check if cur_part is referenced in the WHERE clause. */
8128
8148
        if (join->conds->walk(&Item::find_item_in_field_list_processor, 0,
8129
 
                              (uchar*) key_part_range))
 
8149
                              (unsigned char*) key_part_range))
8130
8150
          goto next_index;
8131
8151
      }
8132
8152
    }
8159
8179
                                           &cur_param_idx);
8160
8180
      /* Check if this range tree can be used for prefix retrieval. */
8161
8181
      COST_VECT dummy_cost;
8162
 
      uint mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
8163
 
      uint mrr_bufsize=0;
8164
 
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx, 
8165
 
                                                   false /*don't care*/, 
 
8182
      uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
 
8183
      uint32_t mrr_bufsize=0;
 
8184
      cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
 
8185
                                                   false /*don't care*/,
8166
8186
                                                   cur_index_tree, true,
8167
8187
                                                   &mrr_flags, &mrr_bufsize,
8168
8188
                                                   &dummy_cost);
8195
8215
    cur_group_prefix_len= 0;
8196
8216
  }
8197
8217
  if (!index_info) /* No usable index found. */
8198
 
    return(NULL);
 
8218
    return NULL;
8199
8219
 
8200
8220
  /* Check (SA3) for the where clause. */
8201
8221
  if (join->conds && min_max_arg_item &&
8202
8222
      !check_group_min_max_predicates(join->conds, min_max_arg_item, Field::itRAW))
8203
 
    return(NULL);
 
8223
    return NULL;
8204
8224
 
8205
8225
  /* The query passes all tests, so construct a new TRP object. */
8206
8226
  read_plan= new (param->mem_root)
8214
8234
  if (read_plan)
8215
8235
  {
8216
8236
    if (tree && read_plan->quick_prefix_records == 0)
8217
 
      return(NULL);
 
8237
      return NULL;
8218
8238
 
8219
8239
    read_plan->read_cost= best_read_cost;
8220
8240
    read_plan->records=   best_records;
8221
8241
  }
8222
8242
 
8223
 
  return(read_plan);
 
8243
  return read_plan;
8224
8244
}
8225
8245
 
8226
8246
 
8262
8282
    {
8263
8283
      if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item,
8264
8284
                                         image_type))
8265
 
        return(false);
 
8285
        return false;
8266
8286
    }
8267
 
    return(true);
 
8287
    return true;
8268
8288
  }
8269
8289
 
8270
8290
  /*
8277
8297
    so.
8278
8298
  */
8279
8299
  if (cond_type == Item::SUBSELECT_ITEM)
8280
 
    return(false);
8281
 
  
 
8300
    return false;
 
8301
 
8282
8302
  /* We presume that at this point there are no other Items than functions. */
8283
8303
  assert(cond_type == Item::FUNC_ITEM);
8284
8304
 
8286
8306
  Item_func *pred= (Item_func*) cond;
8287
8307
  Item **arguments= pred->arguments();
8288
8308
  Item *cur_arg;
8289
 
  for (uint arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)
 
8309
  for (uint32_t arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)
8290
8310
  {
8291
8311
    cur_arg= arguments[arg_idx]->real_item();
8292
8312
    if (cur_arg->type() == Item::FIELD_ITEM)
8293
8313
    {
8294
 
      if (min_max_arg_item->eq(cur_arg, 1)) 
 
8314
      if (min_max_arg_item->eq(cur_arg, 1))
8295
8315
      {
8296
8316
       /*
8297
8317
         If pred references the MIN/MAX argument, check whether pred is a range
8308
8328
            pred_type != Item_func::ISNOTNULL_FUNC &&
8309
8329
            pred_type != Item_func::EQ_FUNC        &&
8310
8330
            pred_type != Item_func::NE_FUNC)
8311
 
          return(false);
 
8331
          return false;
8312
8332
 
8313
8333
        /* Check that pred compares min_max_arg_item with a constant. */
8314
8334
        Item *args[3];
8316
8336
        bool inv;
8317
8337
        /* Test if this is a comparison of a field and a constant. */
8318
8338
        if (!simple_pred(pred, args, &inv))
8319
 
          return(false);
 
8339
          return false;
8320
8340
 
8321
8341
        /* Check for compatible string comparisons - similar to get_mm_leaf. */
8322
8342
        if (args[0] && args[1] && !args[2] && // this is a binary function
8335
8355
             */
8336
8356
             (args[1]->result_type() != STRING_RESULT &&
8337
8357
              min_max_arg_item->field->cmp_type() != args[1]->result_type())))
8338
 
          return(false);
 
8358
          return false;
8339
8359
      }
8340
8360
    }
8341
8361
    else if (cur_arg->type() == Item::FUNC_ITEM)
8342
8362
    {
8343
8363
      if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,
8344
8364
                                         image_type))
8345
 
        return(false);
 
8365
        return false;
8346
8366
    }
8347
8367
    else if (cur_arg->const_item())
8348
8368
    {
8349
 
      return(true);
 
8369
      return true;
8350
8370
    }
8351
8371
    else
8352
 
      return(false);
 
8372
      return false;
8353
8373
  }
8354
8374
 
8355
 
  return(true);
 
8375
  return true;
8356
8376
}
8357
8377
 
8358
8378
 
8366
8386
    first_non_group_part   [in]  First index part after group attribute parts
8367
8387
    min_max_arg_part       [in]  The keypart of the MIN/MAX argument if any
8368
8388
    last_part              [in]  Last keypart of the index
8369
 
    thd                    [in]  Current thread
 
8389
    session                    [in]  Current thread
8370
8390
    key_infix              [out] Infix of constants to be used for index lookup
8371
8391
    key_infix_len          [out] Lenghth of the infix
8372
8392
    first_non_infix_part   [out] The first keypart after the infix (if any)
8373
 
    
 
8393
 
8374
8394
  DESCRIPTION
8375
8395
    Test conditions (NGA1, NGA2) from get_best_group_min_max(). Namely,
8376
8396
    for each keypart field NGF_i not in GROUP-BY, check that there is a
8388
8408
*/
8389
8409
 
8390
8410
static bool
8391
 
get_constant_key_infix(KEY *index_info __attribute__((unused)),
8392
 
                       SEL_ARG *index_range_tree,
 
8411
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
8393
8412
                       KEY_PART_INFO *first_non_group_part,
8394
8413
                       KEY_PART_INFO *min_max_arg_part,
8395
8414
                       KEY_PART_INFO *last_part,
8396
 
                       THD *thd __attribute__((unused)),
8397
 
                       uchar *key_infix, uint *key_infix_len,
 
8415
                       Session *, unsigned char *key_infix, uint32_t *key_infix_len,
8398
8416
                       KEY_PART_INFO **first_non_infix_part)
8399
8417
{
8400
8418
  SEL_ARG       *cur_range;
8403
8421
  KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
8404
8422
 
8405
8423
  *key_infix_len= 0;
8406
 
  uchar *key_ptr= key_infix;
 
8424
  unsigned char *key_ptr= key_infix;
8407
8425
  for (cur_part= first_non_group_part; cur_part != end_part; cur_part++)
8408
8426
  {
8409
8427
    /*
8435
8453
        (cur_range->min_flag & NEAR_MIN) || (cur_range->max_flag & NEAR_MAX))
8436
8454
      return false;
8437
8455
 
8438
 
    uint field_length= cur_part->store_length;
 
8456
    uint32_t field_length= cur_part->store_length;
8439
8457
    if ((cur_range->maybe_null &&
8440
8458
         cur_range->min_value[0] && cur_range->max_value[0]) ||
8441
8459
        !memcmp(cur_range->min_value, cur_range->max_value, field_length))
8510
8528
    Pointer to the SEL_ARG subtree that corresponds to index.
8511
8529
*/
8512
8530
 
8513
 
SEL_ARG * get_index_range_tree(uint index, SEL_TREE* range_tree, PARAM *param,
8514
 
                               uint *param_idx)
 
8531
SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree, PARAM *param,
 
8532
                               uint32_t *param_idx)
8515
8533
{
8516
 
  uint idx= 0; /* Index nr in param->key_parts */
 
8534
  uint32_t idx= 0; /* Index nr in param->key_parts */
8517
8535
  while (idx < param->keys)
8518
8536
  {
8519
8537
    if (index == param->real_keynr[idx])
8521
8539
    idx++;
8522
8540
  }
8523
8541
  *param_idx= idx;
8524
 
  return(range_tree->keys[idx]);
 
8542
  return range_tree->keys[idx];
8525
8543
}
8526
8544
 
8527
8545
 
8585
8603
    None
8586
8604
*/
8587
8605
 
8588
 
void cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts,
8589
 
                        uint group_key_parts, SEL_TREE *range_tree,
8590
 
                        SEL_ARG *index_tree __attribute__((unused)),
8591
 
                        ha_rows quick_prefix_records,
 
8606
void cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
 
8607
                        uint32_t group_key_parts, SEL_TREE *range_tree,
 
8608
                        SEL_ARG *, ha_rows quick_prefix_records,
8592
8609
                        bool have_min, bool have_max,
8593
8610
                        double *read_cost, ha_rows *records)
8594
8611
{
8595
8612
  ha_rows table_records;
8596
 
  uint num_groups;
8597
 
  uint num_blocks;
8598
 
  uint keys_per_block;
8599
 
  uint keys_per_group;
8600
 
  uint keys_per_subgroup; /* Average number of keys in sub-groups */
 
8613
  uint32_t num_groups;
 
8614
  uint32_t num_blocks;
 
8615
  uint32_t keys_per_block;
 
8616
  uint32_t keys_per_group;
 
8617
  uint32_t keys_per_subgroup; /* Average number of keys in sub-groups */
8601
8618
                          /* formed by a key infix. */
8602
8619
  double p_overlap; /* Probability that a sub-group overlaps two blocks. */
8603
8620
  double quick_prefix_selectivity;
8638
8655
    {
8639
8656
      double blocks_per_group= (double) num_blocks / (double) num_groups;
8640
8657
      p_overlap= (blocks_per_group * (keys_per_subgroup - 1)) / keys_per_group;
8641
 
      p_overlap= min(p_overlap, 1.0);
 
8658
      p_overlap= cmin(p_overlap, 1.0);
8642
8659
    }
8643
 
    io_cost= (double) min(num_groups * (1 + p_overlap), (double)num_blocks);
 
8660
    io_cost= (double) cmin(num_groups * (1 + p_overlap), (double)num_blocks);
8644
8661
  }
8645
8662
  else
8646
8663
    io_cost= (keys_per_group > keys_per_block) ?
8657
8674
 
8658
8675
  *read_cost= io_cost + cpu_cost;
8659
8676
  *records= num_groups;
8660
 
  return;
8661
8677
}
8662
8678
 
8663
8679
 
8683
8699
*/
8684
8700
 
8685
8701
QUICK_SELECT_I *
8686
 
TRP_GROUP_MIN_MAX::make_quick(PARAM *param,
8687
 
                              bool retrieve_full_rows __attribute__((unused)),
8688
 
                              MEM_ROOT *parent_alloc)
 
8702
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
8689
8703
{
8690
8704
  QUICK_GROUP_MIN_MAX_SELECT *quick;
8691
8705
 
8692
8706
  quick= new QUICK_GROUP_MIN_MAX_SELECT(param->table,
8693
 
                                        param->thd->lex->current_select->join,
 
8707
                                        param->session->lex->current_select->join,
8694
8708
                                        have_min, have_max, min_max_arg_part,
8695
8709
                                        group_prefix_len, group_key_parts,
8696
8710
                                        used_key_parts, index_info, index,
8697
8711
                                        read_cost, records, key_infix_len,
8698
8712
                                        key_infix, parent_alloc);
8699
8713
  if (!quick)
8700
 
    return(NULL);
 
8714
    return NULL;
8701
8715
 
8702
8716
  if (quick->init())
8703
8717
  {
8704
8718
    delete quick;
8705
 
    return(NULL);
 
8719
    return NULL;
8706
8720
  }
8707
8721
 
8708
8722
  if (range_tree)
8741
8755
        {
8742
8756
          delete quick;
8743
8757
          quick= NULL;
8744
 
          return(NULL);
 
8758
          return NULL;
8745
8759
        }
8746
8760
        min_max_range= min_max_range->next;
8747
8761
      }
8753
8767
  quick->update_key_stat();
8754
8768
  quick->adjust_prefix_ranges();
8755
8769
 
8756
 
  return(quick);
 
8770
  return quick;
8757
8771
}
8758
8772
 
8759
8773
 
8782
8796
*/
8783
8797
 
8784
8798
QUICK_GROUP_MIN_MAX_SELECT::
8785
 
QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join_arg, bool have_min_arg,
 
8799
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8786
8800
                           bool have_max_arg,
8787
8801
                           KEY_PART_INFO *min_max_arg_part_arg,
8788
 
                           uint group_prefix_len_arg, uint group_key_parts_arg,
8789
 
                           uint used_key_parts_arg, KEY *index_info_arg,
8790
 
                           uint use_index, double read_cost_arg,
8791
 
                           ha_rows records_arg, uint key_infix_len_arg,
8792
 
                           uchar *key_infix_arg, MEM_ROOT *parent_alloc)
 
8802
                           uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
 
8803
                           uint32_t used_key_parts_arg, KEY *index_info_arg,
 
8804
                           uint32_t use_index, double read_cost_arg,
 
8805
                           ha_rows records_arg, uint32_t key_infix_len_arg,
 
8806
                           unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8793
8807
  :join(join_arg), index_info(index_info_arg),
8794
8808
   group_prefix_len(group_prefix_len_arg),
8795
8809
   group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8818
8832
  assert(!parent_alloc);
8819
8833
  if (!parent_alloc)
8820
8834
  {
8821
 
    init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8822
 
    join->thd->mem_root= &alloc;
 
8835
    init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
 
8836
    join->session->mem_root= &alloc;
8823
8837
  }
8824
8838
  else
8825
8839
    memset(&alloc, 0, sizeof(MEM_ROOT));  // ensure that it's not used
8831
8845
 
8832
8846
  SYNOPSIS
8833
8847
    QUICK_GROUP_MIN_MAX_SELECT::init()
8834
 
  
 
8848
 
8835
8849
  DESCRIPTION
8836
8850
    The method performs initialization that cannot be done in the constructor
8837
8851
    such as memory allocations that may fail. It allocates memory for the
8848
8862
  if (group_prefix) /* Already initialized. */
8849
8863
    return 0;
8850
8864
 
8851
 
  if (!(last_prefix= (uchar*) alloc_root(&alloc, group_prefix_len)))
 
8865
  if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8852
8866
      return 1;
8853
8867
  /*
8854
8868
    We may use group_prefix to store keys with all select fields, so allocate
8855
8869
    enough space for it.
8856
8870
  */
8857
 
  if (!(group_prefix= (uchar*) alloc_root(&alloc,
 
8871
  if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
8858
8872
                                         real_prefix_len + min_max_arg_len)))
8859
8873
    return 1;
8860
8874
 
8864
8878
      The memory location pointed to by key_infix will be deleted soon, so
8865
8879
      allocate a new buffer and copy the key_infix into it.
8866
8880
    */
8867
 
    uchar *tmp_key_infix= (uchar*) alloc_root(&alloc, key_infix_len);
 
8881
    unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
8868
8882
    if (!tmp_key_infix)
8869
8883
      return 1;
8870
8884
    memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8922
8936
 
8923
8937
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8924
8938
{
8925
 
  if (file->inited != handler::NONE) 
 
8939
  if (file->inited != handler::NONE)
8926
8940
    file->ha_index_end();
8927
8941
  if (min_max_arg_part)
8928
8942
    delete_dynamic(&min_max_ranges);
8930
8944
  delete min_functions_it;
8931
8945
  delete max_functions_it;
8932
8946
  delete quick_prefix_select;
8933
 
  return; 
8934
8947
}
8935
8948
 
8936
8949
 
8939
8952
 
8940
8953
  SYNOPSIS
8941
8954
    QUICK_GROUP_MIN_MAX_SELECT::add_range()
8942
 
    sel_range  Range object from which a 
 
8955
    sel_range  Range object from which a
8943
8956
 
8944
8957
  NOTES
8945
8958
    Construct a new QUICK_RANGE object from a SEL_ARG object, and
8955
8968
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8956
8969
{
8957
8970
  QUICK_RANGE *range;
8958
 
  uint range_flag= sel_range->min_flag | sel_range->max_flag;
 
8971
  uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
8959
8972
 
8960
8973
  /* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8961
8974
  if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8978
8991
                         range_flag);
8979
8992
  if (!range)
8980
8993
    return true;
8981
 
  if (insert_dynamic(&min_max_ranges, (uchar*)&range))
 
8994
  if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
8982
8995
    return true;
8983
8996
  return false;
8984
8997
}
8993
9006
 
8994
9007
  NOTES
8995
9008
    quick_prefix_select is made over the conditions on the whole key.
8996
 
    It defines a number of ranges of length x. 
8997
 
    However when jumping through the prefixes we use only the the first 
 
9009
    It defines a number of ranges of length x.
 
9010
    However when jumping through the prefixes we use only the the first
8998
9011
    few most significant keyparts in the range key. However if there
8999
 
    are more keyparts to follow the ones we are using we must make the 
9000
 
    condition on the key inclusive (because x < "ab" means 
 
9012
    are more keyparts to follow the ones we are using we must make the
 
9013
    condition on the key inclusive (because x < "ab" means
9001
9014
    x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9002
9015
    To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9003
9016
*/
9007
9020
      group_prefix_len < quick_prefix_select->max_used_key_length)
9008
9021
  {
9009
9022
    DYNAMIC_ARRAY *arr;
9010
 
    uint inx;
 
9023
    uint32_t inx;
9011
9024
 
9012
9025
    for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9013
9026
    {
9014
9027
      QUICK_RANGE *range;
9015
9028
 
9016
 
      get_dynamic(arr, (uchar*)&range, inx);
 
9029
      get_dynamic(arr, (unsigned char*)&range, inx);
9017
9030
      range->flag &= ~(NEAR_MIN | NEAR_MAX);
9018
9031
    }
9019
9032
  }
9049
9062
    QUICK_RANGE *cur_range;
9050
9063
    if (have_min)
9051
9064
    { /* Check if the right-most range has a lower boundary. */
9052
 
      get_dynamic(&min_max_ranges, (uchar*)&cur_range,
 
9065
      get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9053
9066
                  min_max_ranges.elements - 1);
9054
9067
      if (!(cur_range->flag & NO_MIN_RANGE))
9055
9068
      {
9060
9073
    }
9061
9074
    if (have_max)
9062
9075
    { /* Check if the left-most range has an upper boundary. */
9063
 
      get_dynamic(&min_max_ranges, (uchar*)&cur_range, 0);
 
9076
      get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9064
9077
      if (!(cur_range->flag & NO_MAX_RANGE))
9065
9078
      {
9066
9079
        max_used_key_length+= min_max_arg_len;
9107
9120
 
9108
9121
  file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9109
9122
  if ((result= file->ha_index_init(index,1)))
9110
 
    return(result);
 
9123
    return result;
9111
9124
  if (quick_prefix_select && quick_prefix_select->reset())
9112
 
    return(1);
 
9125
    return 0;
9113
9126
  result= file->index_last(record);
9114
9127
  if (result == HA_ERR_END_OF_FILE)
9115
 
    return(0);
 
9128
    return 0;
9116
9129
  /* Save the prefix of the last group. */
9117
9130
  key_copy(last_prefix, record, index_info, group_prefix_len);
9118
9131
 
9119
 
  return(0);
 
9132
  return 0;
9120
9133
}
9121
9134
 
9122
9135
 
9123
9136
 
9124
 
/* 
 
9137
/*
9125
9138
  Get the next key containing the MIN and/or MAX key for the next group.
9126
9139
 
9127
9140
  SYNOPSIS
9172
9185
                              group_prefix_len);
9173
9186
      assert(is_last_prefix <= 0);
9174
9187
    }
9175
 
    else 
 
9188
    else
9176
9189
    {
9177
9190
      if (result == HA_ERR_KEY_NOT_FOUND)
9178
9191
        continue;
9193
9206
      if (max_res == 0)
9194
9207
        update_max_result();
9195
9208
      /* If a MIN was found, a MAX must have been found as well. */
9196
 
      assert((have_max && !have_min) ||
9197
 
                  (have_max && have_min && (max_res == 0)));
 
9209
      assert(((have_max && !have_min) ||
 
9210
                  (have_max && have_min && (max_res == 0))));
9198
9211
    }
9199
9212
    /*
9200
9213
      If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9223
9236
  else if (result == HA_ERR_KEY_NOT_FOUND)
9224
9237
    result= HA_ERR_END_OF_FILE;
9225
9238
 
9226
 
  return(result);
 
9239
  return result;
9227
9240
}
9228
9241
 
9229
9242
 
9258
9271
  if (min_max_ranges.elements > 0)
9259
9272
  {
9260
9273
    if ((result= next_min_in_range()))
9261
 
      return(result);
 
9274
      return result;
9262
9275
  }
9263
9276
  else
9264
9277
  {
9268
9281
      if ((result= file->index_read_map(record, group_prefix,
9269
9282
                                        make_prev_keypart_map(real_key_parts),
9270
9283
                                        HA_READ_KEY_EXACT)))
9271
 
        return(result);
 
9284
        return result;
9272
9285
    }
9273
9286
 
9274
9287
    /*
9309
9322
    If the MIN attribute is non-nullable, this->record already contains the
9310
9323
    MIN key in the group, so just return.
9311
9324
  */
9312
 
  return(result);
 
9325
  return result;
9313
9326
}
9314
9327
 
9315
9328
 
9316
 
/* 
 
9329
/*
9317
9330
  Retrieve the maximal key in the next group.
9318
9331
 
9319
9332
  SYNOPSIS
9340
9353
    result= file->index_read_map(record, group_prefix,
9341
9354
                                 make_prev_keypart_map(real_key_parts),
9342
9355
                                 HA_READ_PREFIX_LAST);
9343
 
  return(result);
 
9356
  return result;
9344
9357
}
9345
9358
 
9346
9359
 
9371
9384
 
9372
9385
  if (quick_prefix_select)
9373
9386
  {
9374
 
    uchar *cur_prefix= seen_first_key ? group_prefix : NULL;
 
9387
    unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9375
9388
    if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9376
9389
                         make_prev_keypart_map(group_key_parts), cur_prefix)))
9377
 
      return(result);
 
9390
      return result;
9378
9391
    seen_first_key= true;
9379
9392
  }
9380
9393
  else
9383
9396
    {
9384
9397
      result= file->index_first(record);
9385
9398
      if (result)
9386
 
        return(result);
 
9399
        return result;
9387
9400
      seen_first_key= true;
9388
9401
    }
9389
9402
    else
9393
9406
                                   make_prev_keypart_map(group_key_parts),
9394
9407
                                   HA_READ_AFTER_KEY);
9395
9408
      if (result)
9396
 
        return(result);
 
9409
        return result;
9397
9410
    }
9398
9411
  }
9399
9412
 
9404
9417
    memcpy(group_prefix + group_prefix_len,
9405
9418
           key_infix, key_infix_len);
9406
9419
 
9407
 
  return(0);
 
9420
  return 0;
9408
9421
}
9409
9422
 
9410
9423
 
9436
9449
  QUICK_RANGE *cur_range;
9437
9450
  bool found_null= false;
9438
9451
  int result= HA_ERR_KEY_NOT_FOUND;
 
9452
  basic_string<unsigned char> max_key;
 
9453
 
 
9454
  max_key.reserve(real_prefix_len + min_max_arg_len);
9439
9455
 
9440
9456
  assert(min_max_ranges.elements > 0);
9441
9457
 
9442
 
  for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
 
9458
  for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9443
9459
  { /* Search from the left-most range to the right. */
9444
 
    get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx);
 
9460
    get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9445
9461
 
9446
9462
    /*
9447
9463
      If the current value for the min/max argument is bigger than the right
9448
9464
      boundary of cur_range, there is no need to check this range.
9449
9465
    */
9450
9466
    if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9451
 
        (key_cmp(min_max_arg_part, (const uchar*) cur_range->max_key,
 
9467
        (key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9452
9468
                 min_max_arg_len) == 1))
9453
9469
      continue;
9454
9470
 
9509
9525
    if ( !(cur_range->flag & NO_MAX_RANGE) )
9510
9526
    {
9511
9527
      /* Compose the MAX key for the range. */
9512
 
      uchar *max_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9513
 
      memcpy(max_key, group_prefix, real_prefix_len);
9514
 
      memcpy(max_key + real_prefix_len, cur_range->max_key,
9515
 
             cur_range->max_length);
 
9528
      max_key.clear();
 
9529
      max_key.append(group_prefix, real_prefix_len);
 
9530
      max_key.append(cur_range->max_key, cur_range->max_length);
9516
9531
      /* Compare the found key with max_key. */
9517
 
      int cmp_res= key_cmp(index_info->key_part, max_key,
 
9532
      int cmp_res= key_cmp(index_info->key_part,
 
9533
                           max_key.data(),
9518
9534
                           real_prefix_len + min_max_arg_len);
9519
9535
      if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9520
9536
      {
9567
9583
  key_part_map keypart_map;
9568
9584
  QUICK_RANGE *cur_range;
9569
9585
  int result;
 
9586
  basic_string<unsigned char> min_key;
 
9587
  min_key.reserve(real_prefix_len + min_max_arg_len);
9570
9588
 
9571
9589
  assert(min_max_ranges.elements > 0);
9572
9590
 
9573
 
  for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
 
9591
  for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9574
9592
  { /* Search from the right-most range to the left. */
9575
 
    get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx - 1);
 
9593
    get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9576
9594
 
9577
9595
    /*
9578
9596
      If the current value for the min/max argument is smaller than the left
9580
9598
    */
9581
9599
    if (range_idx != min_max_ranges.elements &&
9582
9600
        !(cur_range->flag & NO_MIN_RANGE) &&
9583
 
        (key_cmp(min_max_arg_part, (const uchar*) cur_range->min_key,
 
9601
        (key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9584
9602
                 min_max_arg_len) == -1))
9585
9603
      continue;
9586
9604
 
9626
9644
    if ( !(cur_range->flag & NO_MIN_RANGE) )
9627
9645
    {
9628
9646
      /* Compose the MIN key for the range. */
9629
 
      uchar *min_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9630
 
      memcpy(min_key, group_prefix, real_prefix_len);
9631
 
      memcpy(min_key + real_prefix_len, cur_range->min_key,
9632
 
             cur_range->min_length);
 
9647
      min_key.clear();
 
9648
      min_key.append(group_prefix, real_prefix_len);
 
9649
      min_key.append(cur_range->min_key, cur_range->min_length);
 
9650
 
9633
9651
      /* Compare the found key with min_key. */
9634
 
      int cmp_res= key_cmp(index_info->key_part, min_key,
 
9652
      int cmp_res= key_cmp(index_info->key_part,
 
9653
                           min_key.data(),
9635
9654
                           real_prefix_len + min_max_arg_len);
9636
9655
      if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9637
9656
            (cmp_res >= 0)))
9728
9747
                                                      String *used_lengths)
9729
9748
{
9730
9749
  char buf[64];
9731
 
  uint length;
 
9750
  uint32_t length;
9732
9751
  key_names->append(index_info->name);
9733
9752
  length= int64_t2str(max_used_key_length, buf, 10) - buf;
9734
9753
  used_lengths->append(buf, length);
9735
9754
}
9736
9755
 
9737
 
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9738
 
                           const char *msg __attribute__((unused)))
 
9756
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9739
9757
{
9740
9758
  SEL_ARG **key,**end;
9741
9759
  int idx;
9749
9767
  {
9750
9768
    if (tree_map->is_set(idx))
9751
9769
    {
9752
 
      uint keynr= param->real_keynr[idx];
 
9770
      uint32_t keynr= param->real_keynr[idx];
9753
9771
      if (tmp.length())
9754
9772
        tmp.append(',');
9755
9773
      tmp.append(param->table->key_info[keynr].name);
9757
9775
  }
9758
9776
  if (!tmp.length())
9759
9777
    tmp.append(STRING_WITH_LEN("(empty)"));
9760
 
 
9761
 
  return;
9762
9778
}
9763
9779
 
9764
9780
 
9765
 
static void print_ror_scans_arr(TABLE *table,
9766
 
                                const char *msg __attribute__((unused)),
9767
 
                                struct st_ror_scan_info **start,
 
9781
static void print_ror_scans_arr(Table *table,
 
9782
                                const char *, struct st_ror_scan_info **start,
9768
9783
                                struct st_ror_scan_info **end)
9769
9784
{
9770
9785
  char buff[1024];
9778
9793
  }
9779
9794
  if (!tmp.length())
9780
9795
    tmp.append(STRING_WITH_LEN("(empty)"));
9781
 
  return;
9782
9796
}
9783
9797
 
9784
9798
/*****************************************************************************
9785
 
** Instantiate templates 
 
9799
** Instantiate templates
9786
9800
*****************************************************************************/
9787
9801
 
9788
9802
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION