157
126
return static_cast<ha_rows>(x);
129
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
160
131
static unsigned char is_null_string[2]= {1,0};
164
Get cost of reading nrows table records in a "disk sweep"
166
A disk sweep read is a sequence of Cursor->rnd_pos(rowid) calls that made
167
for an ordered sequence of rowids.
169
We assume hard disk IO. The read is performed as follows:
171
1. The disk head is moved to the needed cylinder
172
2. The controller waits for the plate to rotate
173
3. The data is transferred
175
Time to do #3 is insignificant compared to #2+#1.
177
Time to move the disk head is proportional to head travel distance.
179
Time to wait for the plate to rotate depends on whether the disk head
182
If disk head wasn't moved, the wait time is proportional to distance
183
between the previous block and the block we're reading.
185
If the head was moved, we don't know how much we'll need to wait for the
186
plate to rotate. We assume the wait time to be a variate with a mean of
187
0.5 of full rotation time.
189
Our cost units are "random disk seeks". The cost of random disk seek is
190
actually not a constant, it depends one range of cylinders we're going
191
to access. We make it constant by introducing a fuzzy concept of "typical
192
datafile length" (it's fuzzy as it's hard to tell whether it should
193
include index cursor, temp.tables etc). Then random seek cost is:
195
1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length
197
We define half_rotation_cost as DISK_SEEK_BASE_COST=0.9.
199
@param table Table to be accessed
200
@param nrows Number of rows to retrieve
201
@param interrupted true <=> Assume that the disk sweep will be
202
interrupted by other disk IO. false - otherwise.
203
@param cost OUT The cost.
206
static void get_sweep_read_cost(Table *table,
209
optimizer::CostVector *cost)
212
if (table->cursor->primary_key_is_clustered())
214
cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
215
static_cast<uint32_t>(nrows),
221
ceil(static_cast<double>(table->cursor->stats.data_file_length) / IO_SIZE);
223
n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, static_cast<double>(nrows)));
224
if (busy_blocks < 1.0)
227
cost->setIOCount(busy_blocks);
231
/* Assume reading is done in one 'sweep' */
232
cost->setAvgIOCost((DISK_SEEK_BASE_COST +
233
DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
238
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
241
Item_func::Functype type,
243
Item_result cmp_type);
245
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
249
Item_func::Functype type,
252
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
254
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
256
static ha_rows check_quick_select(Session *session,
257
optimizer::Parameter *param,
260
optimizer::SEL_ARG *tree,
261
bool update_tbl_stats,
264
optimizer::CostVector *cost);
266
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
267
optimizer::Parameter *param,
268
optimizer::SEL_TREE *tree,
269
bool index_read_must_be_used,
270
bool update_tbl_stats,
274
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
275
optimizer::SEL_TREE *tree,
277
bool *are_all_covering);
280
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
281
optimizer::SEL_TREE *tree,
285
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
286
optimizer::Parameter *param,
287
optimizer::SEL_IMERGE *imerge,
291
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
293
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
294
optimizer::SEL_TREE *tree1,
295
optimizer::SEL_TREE *tree2);
297
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
299
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
300
optimizer::SEL_ARG *key1,
301
optimizer::SEL_ARG *key2,
302
uint32_t clone_flag);
304
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
306
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
308
static bool null_part_in_key(KEY_PART *key_part,
309
const unsigned char *key,
133
class RANGE_OPT_PARAM;
135
A construction block of the SEL_ARG-graph.
137
The following description only covers graphs of SEL_ARG objects with
138
sel_arg->type==KEY_RANGE:
140
One SEL_ARG object represents an "elementary interval" in form
142
min_value <=? table.keypartX <=? max_value
144
The interval is a non-empty interval of any kind: with[out] minimum/maximum
145
bound, [half]open/closed, single-point interval, etc.
147
1. SEL_ARG GRAPH STRUCTURE
149
SEL_ARG objects are linked together in a graph. The meaning of the graph
150
is better demostrated by an example:
155
| part=1 $ part=2 $ part=3
157
| +-------+ $ +-------+ $ +--------+
158
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
159
| +-------+ $ +-------+ $ +--------+
165
\->| kp1=2 |--$--------------$-+
166
+-------+ $ $ | +--------+
168
+-------+ $ $ | +--------+
169
| kp1=3 |--$--------------$-+ |
170
+-------+ $ $ +--------+
174
The entire graph is partitioned into "interval lists".
176
An interval list is a sequence of ordered disjoint intervals over the same
177
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
178
all intervals in the list form an RB-tree, linked via left/right/parent
179
pointers. The RB-tree root SEL_ARG object will be further called "root of the
182
In the example pic, there are 4 interval lists:
183
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
184
The vertical lines represent SEL_ARG::next/prev pointers.
186
In an interval list, each member X may have SEL_ARG::next_key_part pointer
187
pointing to the root of another interval list Y. The pointed interval list
188
must cover a key part with greater number (i.e. Y->part > X->part).
190
In the example pic, the next_key_part pointers are represented by
193
2. SEL_ARG GRAPH SEMANTICS
195
It represents a condition in a special form (we don't have a name for it ATM)
196
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
198
For example, the picture represents the condition in form:
199
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
200
(kp1=2 AND (kp3=11 OR kp3=14)) OR
201
(kp1=3 AND (kp3=11 OR kp3=14))
206
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
207
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
208
intervals (i.e. intervals in form
210
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
212
Those intervals can be used to access the index. The uses are in:
213
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
214
how many table records are contained within all
216
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
217
and create QUICK_RANGE_SELECT object that will
218
read records within these intervals.
220
4. SPACE COMPLEXITY NOTES
222
SEL_ARG graph is a representation of an ordered disjoint sequence of
223
intervals over the ordered set of index tuple values.
225
For multi-part keys, one can construct a WHERE expression such that its
226
list of intervals will be of combinatorial size. Here is an example:
228
(keypart1 IN (1,2, ..., n1)) AND
229
(keypart2 IN (1,2, ..., n2)) AND
230
(keypart3 IN (1,2, ..., n3))
232
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
235
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
237
SEL_ARG graph structure aims to reduce the amount of required space by
238
"sharing" the elementary intervals when possible (the pic at the
239
beginning of this comment has examples of such sharing). The sharing may
240
prevent combinatorial blowup:
242
There are WHERE clauses that have combinatorial-size interval lists but
243
will be represented by a compact SEL_ARG graph.
245
(keypartN IN (1,2, ..., n1)) AND
247
(keypart2 IN (1,2, ..., n2)) AND
248
(keypart1 IN (1,2, ..., n3))
250
but not in all cases:
252
- There are WHERE clauses that do have a compact SEL_ARG-graph
253
representation but get_mm_tree() and its callees will construct a
254
graph of combinatorial size.
256
(keypart1 IN (1,2, ..., n1)) AND
257
(keypart2 IN (1,2, ..., n2)) AND
259
(keypartN IN (1,2, ..., n3))
261
- There are WHERE clauses for which the minimal possible SEL_ARG graph
262
representation will have combinatorial size.
264
By induction: Let's take any interval on some keypart in the middle:
268
Then let's AND it with this interval 'structure' from preceding and
271
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
273
We will obtain this SEL_ARG graph:
277
+---------+ $ +---------+ $ +---------+
278
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
279
+---------+ $ +---------+ $ +---------+
281
+---------+ $ +---------+ $
282
| kp14=c2 |--$-->| kp15=c0 | $
283
+---------+ $ +---------+ $
286
Note that we had to duplicate "kp15=c0" and there was no way to avoid
288
The induction step: AND the obtained expression with another "wrapping"
290
When the process ends because of the limit on max. number of keyparts
293
WHERE clause length is O(3*#max_keyparts)
294
SEL_ARG graph size is O(2^(#max_keyparts/2))
296
(it is also possible to construct a case where instead of 2 in 2^n we
297
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
300
We avoid consuming too much memory by setting a limit on the number of
301
SEL_ARG object we can construct during one range analysis invocation.
304
class SEL_ARG :public Sql_alloc
307
uint8_t min_flag,max_flag,maybe_flag;
308
uint8_t part; // Which key part
311
Number of children of this element in the RB-tree, plus 1 for this
316
Valid only for elements which are RB-tree roots: Number of times this
317
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
318
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
323
unsigned char *min_value,*max_value; // Pointer to range
326
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
328
SEL_ARG *left,*right; /* R-B tree children */
329
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
330
SEL_ARG *parent; /* R-B tree parent */
331
SEL_ARG *next_key_part;
332
enum leaf_color { BLACK,RED } color;
333
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
335
enum { MAX_SEL_ARGS = 16000 };
339
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
340
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
341
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
342
SEL_ARG(enum Type type_arg)
343
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
344
color(BLACK), type(type_arg)
346
inline bool is_same(SEL_ARG *arg)
348
if (type != arg->type || part != arg->part)
350
if (type != KEY_RANGE)
352
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
354
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
355
inline void maybe_smaller() { maybe_flag=1; }
356
/* Return true iff it's a single-point null interval */
357
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
358
inline int cmp_min_to_min(SEL_ARG* arg)
360
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
362
inline int cmp_min_to_max(SEL_ARG* arg)
364
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
366
inline int cmp_max_to_max(SEL_ARG* arg)
368
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
370
inline int cmp_max_to_min(SEL_ARG* arg)
372
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
374
SEL_ARG *clone_and(SEL_ARG* arg)
375
{ // Get overlapping range
376
unsigned char *new_min,*new_max;
377
uint8_t flag_min,flag_max;
378
if (cmp_min_to_min(arg) >= 0)
380
new_min=min_value; flag_min=min_flag;
384
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
386
if (cmp_max_to_max(arg) <= 0)
388
new_max=max_value; flag_max=max_flag;
392
new_max=arg->max_value; flag_max=arg->max_flag;
394
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
395
test(maybe_flag && arg->maybe_flag));
397
SEL_ARG *clone_first(SEL_ARG *arg)
398
{ // min <= X < arg->min
399
return new SEL_ARG(field,part, min_value, arg->min_value,
400
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
401
maybe_flag | arg->maybe_flag);
403
SEL_ARG *clone_last(SEL_ARG *arg)
404
{ // min <= X <= key_max
405
return new SEL_ARG(field, part, min_value, arg->max_value,
406
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
408
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
410
bool copy_min(SEL_ARG* arg)
411
{ // Get overlapping range
412
if (cmp_min_to_min(arg) > 0)
414
min_value=arg->min_value; min_flag=arg->min_flag;
415
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
416
(NO_MAX_RANGE | NO_MIN_RANGE))
417
return 1; // Full range
419
maybe_flag|=arg->maybe_flag;
422
bool copy_max(SEL_ARG* arg)
423
{ // Get overlapping range
424
if (cmp_max_to_max(arg) <= 0)
426
max_value=arg->max_value; max_flag=arg->max_flag;
427
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
428
(NO_MAX_RANGE | NO_MIN_RANGE))
429
return 1; // Full range
431
maybe_flag|=arg->maybe_flag;
435
void copy_min_to_min(SEL_ARG *arg)
437
min_value=arg->min_value; min_flag=arg->min_flag;
439
void copy_min_to_max(SEL_ARG *arg)
441
max_value=arg->min_value;
442
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
444
void copy_max_to_min(SEL_ARG *arg)
446
min_value=arg->max_value;
447
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
449
/* returns a number of keypart values (0 or 1) appended to the key buffer */
450
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
452
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
453
if ((!(min_flag & NO_MIN_RANGE) &&
454
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
456
if (maybe_null && *min_value)
459
memset(*min_key+1, 0, length-1);
462
memcpy(*min_key,min_value,length);
468
/* returns a number of keypart values (0 or 1) appended to the key buffer */
469
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
471
if (!(max_flag & NO_MAX_RANGE) &&
472
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
474
if (maybe_null && *max_value)
477
memset(*max_key+1, 0, length-1);
480
memcpy(*max_key,max_value,length);
487
/* returns a number of keypart values appended to the key buffer */
488
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
490
SEL_ARG *key_tree= first();
491
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
492
range_key, *range_key_flag);
493
*range_key_flag|= key_tree->min_flag;
495
if (key_tree->next_key_part &&
496
key_tree->next_key_part->part == key_tree->part+1 &&
497
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
498
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
499
res+= key_tree->next_key_part->store_min_key(key, range_key,
504
/* returns a number of keypart values appended to the key buffer */
505
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
507
SEL_ARG *key_tree= last();
508
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
509
range_key, *range_key_flag);
510
(*range_key_flag)|= key_tree->max_flag;
511
if (key_tree->next_key_part &&
512
key_tree->next_key_part->part == key_tree->part+1 &&
513
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
514
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
515
res+= key_tree->next_key_part->store_max_key(key, range_key,
520
SEL_ARG *insert(SEL_ARG *key);
521
SEL_ARG *tree_delete(SEL_ARG *key);
522
SEL_ARG *find_range(SEL_ARG *key);
523
SEL_ARG *rb_insert(SEL_ARG *leaf);
524
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
526
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
527
void test_use_count(SEL_ARG *root);
532
inline bool simple_key()
534
return !next_key_part && elements == 1;
536
void increment_use_count(long count)
540
next_key_part->use_count+=count;
541
count*= (next_key_part->use_count-count);
542
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
543
if (pos->next_key_part)
544
pos->increment_use_count(count);
549
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
550
if (pos->next_key_part)
552
pos->next_key_part->use_count--;
553
pos->next_key_part->free_tree();
557
inline SEL_ARG **parent_ptr()
559
return parent->left == this ? &parent->left : &parent->right;
564
Check if this SEL_ARG object represents a single-point interval
570
Check if this SEL_ARG object (not tree) represents a single-point
571
interval, i.e. if it represents a "keypart = const" or
575
true This SEL_ARG object represents a singlepoint interval
579
bool is_singlepoint()
582
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
583
flags, and the same for right edge.
585
if (min_flag || max_flag)
587
unsigned char *min_val= min_value;
588
unsigned char *max_val= max_value;
592
/* First byte is a NULL value indicator */
593
if (*min_val != *max_val)
597
return true; /* This "x IS NULL" */
601
return !field->key_cmp(min_val, max_val);
603
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
609
class SEL_TREE :public Sql_alloc
613
Starting an effort to document this field:
614
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
615
(type == SEL_TREE::IMPOSSIBLE)
617
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
618
SEL_TREE(enum Type type_arg) :type(type_arg) {}
619
SEL_TREE() :type(KEY)
621
keys_map.clear_all();
622
memset(keys, 0, sizeof(keys));
625
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
626
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
627
merit in range analyzer functions (e.g. get_mm_parts) returning a
628
pointer to such SEL_TREE instead of NULL)
630
SEL_ARG *keys[MAX_KEY];
631
key_map keys_map; /* bitmask of non-NULL elements in keys */
634
Possible ways to read rows using index_merge. The list is non-empty only
635
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
637
List<SEL_IMERGE> merges;
639
/* The members below are filled/used only after get_mm_tree is done */
640
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
641
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
643
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
644
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
645
/* Note that #records for each key scan is stored in table->quick_rows */
648
class RANGE_OPT_PARAM
651
Session *session; /* Current thread handle */
652
Table *table; /* Table being analyzed */
653
COND *cond; /* Used inside get_mm_tree(). */
654
table_map prev_tables;
655
table_map read_tables;
656
table_map current_table; /* Bit of the table being analyzed */
658
/* Array of parts of all keys for which range analysis is performed */
660
KEY_PART *key_parts_end;
661
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
662
MEM_ROOT *old_root; /* Memory that will last until the query end */
664
Number of indexes used in range analysis (In SEL_TREE::keys only first
665
#keys elements are not empty)
670
If true, the index descriptions describe real indexes (and it is ok to
671
call field->optimize_range(real_keynr[...], ...).
672
Otherwise index description describes fake indexes.
674
bool using_real_indexes;
676
bool remove_jump_scans;
679
used_key_no -> table_key_no translation table. Only makes sense if
680
using_real_indexes==true
682
uint32_t real_keynr[MAX_KEY];
683
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
684
uint32_t alloced_sel_args;
685
bool force_default_mrr;
688
class PARAM : public RANGE_OPT_PARAM
691
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
693
uint32_t max_key_part;
694
/* Number of ranges in the last checked tree->key */
695
uint32_t range_count;
696
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
697
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
698
bool quick; // Don't calulate possible keys
700
uint32_t fields_bitmap_size;
701
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
702
MY_BITMAP tmp_covered_fields;
704
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
706
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
707
uint32_t imerge_cost_buff_size; /* size of the buffer */
709
/* true if last checked tree->key can be used for ROR-scan */
711
/* Number of ranges in the last checked tree->key */
715
class TABLE_READ_PLAN;
717
class TRP_ROR_INTERSECT;
719
class TRP_ROR_INDEX_MERGE;
720
class TRP_GROUP_MIN_MAX;
722
struct st_ror_scan_info;
724
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
725
Item_func::Functype type,Item *value,
726
Item_result cmp_type);
727
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
729
Item_func::Functype type,Item *value);
730
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
732
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
733
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
734
SEL_ARG *tree, bool update_tbl_stats,
735
uint32_t *mrr_flags, uint32_t *bufsize,
737
//bool update_tbl_stats);
738
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
739
unsigned char *min_key, uint32_t min_key_flag, int,
740
unsigned char *max_key, uint32_t max_key_flag, int);
743
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
744
SEL_ARG *key_tree, uint32_t mrr_flags,
745
uint32_t mrr_buf_size, MEM_ROOT *alloc);
746
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
747
bool index_read_must_be_used,
748
bool update_tbl_stats,
751
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
753
bool *are_all_covering);
755
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
759
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
762
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
764
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
766
static void print_ror_scans_arr(Table *table, const char *msg,
767
struct st_ror_scan_info **start,
768
struct st_ror_scan_info **end);
770
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
771
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
772
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
773
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
774
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
775
uint32_t clone_flag);
776
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
777
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
778
SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
779
unsigned char *max_key,uint32_t max_key_flag);
780
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
782
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
783
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
310
784
uint32_t length);
312
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
313
optimizer::SEL_TREE *tree2,
314
optimizer::RangeParameter *param);
785
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
789
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
790
a condition in the following form:
791
(t_1||t_2||...||t_N) && (next)
793
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
794
(t_i,t_j) contains SEL_ARGS for the same index.
796
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
798
This class relies on memory manager to do the cleanup.
801
class SEL_IMERGE : public Sql_alloc
803
enum { PREALLOCED_TREES= 10};
805
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
806
SEL_TREE **trees; /* trees used to do index_merge */
807
SEL_TREE **trees_next; /* last of these trees */
808
SEL_TREE **trees_end; /* end of allocated space */
810
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
813
trees(&trees_prealloced[0]),
815
trees_end(trees + PREALLOCED_TREES)
817
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
818
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
819
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
824
Add SEL_TREE to this index_merge without any checks,
827
This function implements the following:
828
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
835
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
837
if (trees_next == trees_end)
839
const int realloc_ratio= 2; /* Double size for next round */
840
uint32_t old_elements= (trees_end - trees);
841
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
842
uint32_t new_size= old_size * realloc_ratio;
843
SEL_TREE **new_trees;
844
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
846
memcpy(new_trees, trees, old_size);
848
trees_next= trees + old_elements;
849
trees_end= trees + old_elements * realloc_ratio;
851
*(trees_next++)= tree;
857
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
858
combining new_tree with one of the trees in this SEL_IMERGE if they both
859
have SEL_ARGs for the same key.
862
or_sel_tree_with_checks()
863
param PARAM from SQL_SELECT::test_quick_select
864
new_tree SEL_TREE with type KEY or KEY_SMALLER.
867
This does the following:
868
(t_1||...||t_k)||new_tree =
870
= (t_1||...||t_k||new_tree)
872
= (t_1||....||(t_j|| new_tree)||...||t_k),
874
where t_i, y are SEL_TREEs.
875
new_tree is combined with the first t_j it has a SEL_ARG on common
876
key with. As a consequence of this, choice of keys to do index_merge
877
read may depend on the order of conditions in WHERE part of the query.
881
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
882
and (*this) should be discarded.
883
-1 An error occurred.
886
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
888
for (SEL_TREE** tree = trees;
892
if (sel_trees_can_be_ored(*tree, new_tree, param))
894
*tree = tree_or(param, *tree, new_tree);
897
if (((*tree)->type == SEL_TREE::MAYBE) ||
898
((*tree)->type == SEL_TREE::ALWAYS))
900
/* SEL_TREE::IMPOSSIBLE is impossible here */
905
/* New tree cannot be combined with any of existing trees. */
906
return or_sel_tree(param, new_tree);
911
Perform OR operation on this index_merge and supplied index_merge list.
915
1 - One of conditions in result is always true and this SEL_IMERGE
917
-1 - An error occurred
920
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
922
for (SEL_TREE** tree= imerge->trees;
923
tree != imerge->trees_next;
926
if (or_sel_tree_with_checks(param, *tree))
322
934
Perform AND operation on two index_merge lists and store result in *im1.
325
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
937
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
327
939
im1->concat(im2);
944
Perform OR operation on 2 index_merge lists, storing result in first list.
947
The following conversion is implemented:
948
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
951
i.e. all conjuncts except the first one are currently dropped.
952
This is done to avoid producing N*K ways to do index_merge.
954
If (a_1||b_1) produce a condition that is always true, NULL is returned
955
and index_merge is discarded (while it is actually possible to try
958
As a consequence of this, choice of keys to do index_merge read may depend
959
on the order of conditions in WHERE part of the query.
962
0 OK, result is stored in *im1
963
other Error, both passed lists are unusable
966
int imerge_list_or_list(RANGE_OPT_PARAM *param,
967
List<SEL_IMERGE> *im1,
968
List<SEL_IMERGE> *im2)
970
SEL_IMERGE *imerge= im1->head();
972
im1->push_back(imerge);
974
return imerge->or_sel_imerge_with_checks(param, im2->head());
979
Perform OR operation on index_merge list and key tree.
982
0 OK, result is stored in *im1.
986
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
987
List<SEL_IMERGE> *im1,
991
List_iterator<SEL_IMERGE> it(*im1);
992
while ((imerge= it++))
994
if (imerge->or_sel_tree_with_checks(param, tree))
997
return im1->is_empty();
331
1001
/***************************************************************************
332
** Basic functions for SqlSelect and QuickRangeSelect
1002
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
333
1003
***************************************************************************/
335
1005
/* make a select from mysql info
378
optimizer::SqlSelect::SqlSelect()
382
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1044
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1046
quick_keys.clear_all(); needed_reg.clear_all();
391
void optimizer::SqlSelect::cleanup()
1051
void SQL_SELECT::cleanup()
405
file->close_cached_file();
1061
close_cached_file(&file);
409
optimizer::SqlSelect::~SqlSelect()
1065
SQL_SELECT::~SQL_SELECT()
415
bool optimizer::SqlSelect::check_quick(Session *session,
416
bool force_quick_range,
1071
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
421
return (test_quick_select(session,
430
bool optimizer::SqlSelect::skip_record()
432
return (cond ? cond->val_int() == 0 : 0);
436
optimizer::QuickSelectInterface::QuickSelectInterface()
438
max_used_key_length(0),
1076
return test_quick_select(session, tmp, 0, limit,
1077
force_quick_range, false) < 0;
1081
bool SQL_SELECT::skip_record()
1083
return cond ? cond->val_int() == 0 : 0;
1087
QUICK_SELECT_I::QUICK_SELECT_I()
1088
:max_used_key_length(0),
1092
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1093
bool no_alloc, MEM_ROOT *parent_alloc,
1095
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1097
my_bitmap_map *bitmap;
1099
in_ror_merged_scan= 0;
1103
key_part_info= head->key_info[index].key_part;
1104
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1106
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1107
mrr_buf_size= session->variables.read_rnd_buff_size;
1110
if (!no_alloc && !parent_alloc)
1112
// Allocates everything through the internal memroot
1113
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1114
session->mem_root= &alloc;
1117
memset(&alloc, 0, sizeof(alloc));
1119
record= head->record[0];
1120
save_read_set= head->read_set;
1121
save_write_set= head->write_set;
1123
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1124
if (!(bitmap= (my_bitmap_map*) malloc(head->s->column_bitmap_size)))
1126
column_bitmap.bitmap= 0;
1130
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1135
int QUICK_RANGE_SELECT::init()
1137
if (file->inited != handler::NONE)
1138
file->ha_index_or_rnd_end();
1139
return(file->ha_index_init(index, 1));
1143
void QUICK_RANGE_SELECT::range_end()
1145
if (file->inited != handler::NONE)
1146
file->ha_index_or_rnd_end();
1150
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1154
/* file is NULL for CPK scan on covering ROR-intersection */
1161
file->extra(HA_EXTRA_NO_KEYREAD);
1165
file->ha_external_lock(current_session, F_UNLCK);
1170
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1171
free_root(&alloc,MYF(0));
1172
free((char*) column_bitmap.bitmap);
1174
head->column_bitmaps_set(save_read_set, save_write_set);
1181
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1183
:pk_quick_select(NULL), session(session_param)
1187
memset(&read_record, 0, sizeof(read_record));
1188
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1192
int QUICK_INDEX_MERGE_SELECT::init()
1197
int QUICK_INDEX_MERGE_SELECT::reset()
1199
return(read_keys_and_merge());
1203
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1206
Save quick_select that does scan on clustered primary key as it will be
1207
processed separately.
1209
if (head->file->primary_key_is_clustered() &&
1210
quick_sel_range->index == head->s->primary_key)
1211
pk_quick_select= quick_sel_range;
1213
return quick_selects.push_back(quick_sel_range);
1217
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1219
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1220
QUICK_RANGE_SELECT* quick;
1222
while ((quick= quick_it++))
1224
quick_selects.delete_elements();
1225
delete pk_quick_select;
1226
free_root(&alloc,MYF(0));
1231
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1233
bool retrieve_full_rows,
1234
MEM_ROOT *parent_alloc)
1235
: cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1240
record= head->record[0];
1242
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1244
memset(&alloc, 0, sizeof(MEM_ROOT));
1245
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1246
head->file->ref_length);
1251
Do post-constructor initialization.
1253
QUICK_ROR_INTERSECT_SELECT::init()
1260
int QUICK_ROR_INTERSECT_SELECT::init()
1262
/* Check if last_rowid was successfully allocated in ctor */
1263
return(!last_rowid);
1268
Initialize this quick select to be a ROR-merged scan.
1271
QUICK_RANGE_SELECT::init_ror_merged_scan()
1272
reuse_handler If true, use head->file, otherwise create a separate
1276
This function creates and prepares for subsequent use a separate handler
1277
object if it can't reuse head->file. The reason for this is that during
1278
ROR-merge several key scans are performed simultaneously, and a single
1279
handler is only capable of preserving context of a single key scan.
1281
In ROR-merge the quick select doing merge does full records retrieval,
1282
merged quick selects read only keys.
1285
0 ROR child scan initialized, ok to use.
1289
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1291
handler *save_file= file, *org_file;
1294
in_ror_merged_scan= 1;
1297
if (init() || reset())
1301
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1305
/* Create a separate handler object for this quick select */
1308
/* already have own 'handler' object. */
1312
session= head->in_use;
1313
if (!(file= head->file->clone(session->mem_root)))
1316
Manually set the error flag. Note: there seems to be quite a few
1317
places where a failure could cause the server to "hang" the client by
1318
sending no response to a query. ATM those are not real errors because
1319
the storage engine calls in question happen to never fail with the
1320
existing storage engines.
1322
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1323
/* Caller will free the memory */
1324
goto failure; /* purecov: inspected */
1327
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1329
if (file->ha_external_lock(session, F_RDLCK))
1332
if (init() || reset())
1334
file->ha_external_lock(session, F_UNLCK);
1339
last_rowid= file->ref;
1343
We are only going to read key fields and call position() on 'file'
1344
The following sets head->tmp_set to only use this key and then updates
1345
head->read_set and head->write_set to use this bitmap.
1346
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1348
org_file= head->file;
1350
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1351
if (!head->no_keyread)
1354
head->mark_columns_used_by_index(index);
1356
head->prepare_for_position();
1357
head->file= org_file;
1358
bitmap_copy(&column_bitmap, head->read_set);
1359
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1364
head->column_bitmaps_set(save_read_set, save_write_set);
1371
void QUICK_RANGE_SELECT::save_last_pos()
1373
file->position(record);
1378
Initialize this quick select to be a part of a ROR-merged scan.
1380
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1381
reuse_handler If true, use head->file, otherwise create separate
1387
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1389
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1390
QUICK_RANGE_SELECT* quick;
1392
/* Initialize all merged "children" quick selects */
1393
assert(!need_to_fetch_row || reuse_handler);
1394
if (!need_to_fetch_row && reuse_handler)
1398
There is no use of this->file. Use it for the first of merged range
1401
if (quick->init_ror_merged_scan(true))
1403
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1405
while ((quick= quick_it++))
1407
if (quick->init_ror_merged_scan(false))
1409
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1410
/* All merged scans share the same record buffer in intersection. */
1411
quick->record= head->record[0];
1414
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1423
Initialize quick select for row retrieval.
1431
int QUICK_ROR_INTERSECT_SELECT::reset()
1433
if (!scans_inited && init_ror_merged_scan(true))
1436
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1437
QUICK_RANGE_SELECT *quick;
1438
while ((quick= it++))
1445
Add a merged quick select to this ROR-intersection quick select.
1448
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1449
quick Quick select to be added. The quick select must return
1450
rows in rowid order.
1452
This call can only be made before init() is called.
1460
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1462
return quick_selects.push_back(quick);
1465
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1467
quick_selects.delete_elements();
1469
free_root(&alloc,MYF(0));
1470
if (need_to_fetch_row && head->file->inited != handler::NONE)
1471
head->file->ha_rnd_end();
1476
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1478
: session(session_param), scans_inited(false)
1482
rowid_length= table->file->ref_length;
1483
record= head->record[0];
1484
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1485
session_param->mem_root= &alloc;
1490
Do post-constructor initialization.
1492
QUICK_ROR_UNION_SELECT::init()
1499
int QUICK_ROR_UNION_SELECT::init()
1501
if (init_queue(&queue, quick_selects.elements, 0,
1502
false, quick_ror_union_select_queue_cmp,
1505
memset(&queue, 0, sizeof(QUEUE));
1509
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1511
prev_rowid= cur_rowid + head->file->ref_length;
1517
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1521
QUICK_ROR_UNION_SELECT::queue_cmp()
1522
arg Pointer to QUICK_ROR_UNION_SELECT
1523
val1 First merged select
1524
val2 Second merged select
1527
int quick_ror_union_select_queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1529
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1530
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1531
((QUICK_SELECT_I*)val2)->last_rowid);
1536
Initialize quick select for row retrieval.
1545
int QUICK_ROR_UNION_SELECT::reset()
1547
QUICK_SELECT_I *quick;
1549
have_prev_rowid= false;
1552
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1553
while ((quick= it++))
1555
if (quick->init_ror_merged_scan(false))
1560
queue_remove_all(&queue);
1562
Initialize scans for merged quick selects and put all merged quick
1563
selects into the queue.
1565
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1566
while ((quick= it++))
1570
if ((error= quick->get_next()))
1572
if (error == HA_ERR_END_OF_FILE)
1576
quick->save_last_pos();
1577
queue_insert(&queue, (unsigned char*)quick);
1580
if (head->file->ha_rnd_init(1))
1590
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1592
return quick_selects.push_back(quick_sel_range);
1595
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1597
delete_queue(&queue);
1598
quick_selects.delete_elements();
1599
if (head->file->inited != handler::NONE)
1600
head->file->ha_rnd_end();
1601
free_root(&alloc,MYF(0));
1606
QUICK_RANGE::QUICK_RANGE()
1607
:min_key(0),max_key(0),min_length(0),max_length(0),
1608
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1609
min_keypart_map(0), max_keypart_map(0)
1612
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1615
min_flag=arg.min_flag;
1616
max_flag=arg.max_flag;
1617
maybe_flag=arg.maybe_flag;
1618
maybe_null=arg.maybe_null;
1621
min_value=arg.min_value;
1622
max_value=arg.max_value;
1623
next_key_part=arg.next_key_part;
1624
use_count=1; elements=1;
1628
inline void SEL_ARG::make_root()
1630
left=right= &null_element;
1633
use_count=0; elements=1;
1636
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1637
const unsigned char *max_value_arg)
1638
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1639
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1640
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1641
next_key_part(0),color(BLACK),type(KEY_RANGE)
1643
left=right= &null_element;
1646
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1647
unsigned char *min_value_, unsigned char *max_value_,
1648
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1649
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1650
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1651
field(field_), min_value(min_value_), max_value(max_value_),
1652
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1654
left=right= &null_element;
1657
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1662
/* Bail out if we have already generated too many SEL_ARGs */
1663
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1666
if (type != KEY_RANGE)
1668
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1669
return 0; // out of memory
1670
tmp->prev= *next_arg; // Link into next/prev chain
1671
(*next_arg)->next=tmp;
1676
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1677
min_flag, max_flag, maybe_flag)))
1679
tmp->parent=new_parent;
1680
tmp->next_key_part=next_key_part;
1681
if (left != &null_element)
1682
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1685
tmp->prev= *next_arg; // Link into next/prev chain
1686
(*next_arg)->next=tmp;
1689
if (right != &null_element)
1690
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1693
increment_use_count(1);
1695
tmp->elements= this->elements;
1699
SEL_ARG *SEL_ARG::first()
1701
SEL_ARG *next_arg=this;
1702
if (!next_arg->left)
1703
return 0; // MAYBE_KEY
1704
while (next_arg->left != &null_element)
1705
next_arg=next_arg->left;
1709
SEL_ARG *SEL_ARG::last()
1711
SEL_ARG *next_arg=this;
1712
if (!next_arg->right)
1713
return 0; // MAYBE_KEY
1714
while (next_arg->right != &null_element)
1715
next_arg=next_arg->right;
1721
Check if a compare is ok, when one takes ranges in account
1722
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1725
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1729
/* First check if there was a compare to a min or max element */
1730
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1732
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1733
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1735
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1737
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1738
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1740
if (field->real_maybe_null()) // If null is part of key
1747
goto end; // NULL where equal
1748
a++; b++; // Skip NULL marker
1750
cmp=field->key_cmp(a , b);
1751
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1753
// Check if the compared equal arguments was defined with open/closed range
1755
if (a_flag & (NEAR_MIN | NEAR_MAX))
1757
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1759
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1760
return (a_flag & NEAR_MIN) ? 2 : -2;
1761
return (a_flag & NEAR_MIN) ? 1 : -1;
1763
if (b_flag & (NEAR_MIN | NEAR_MAX))
1764
return (b_flag & NEAR_MIN) ? -2 : 2;
1765
return 0; // The elements where equal
1769
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1771
SEL_ARG tmp_link,*next_arg,*root;
1772
next_arg= &tmp_link;
1773
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1775
next_arg->next=0; // Fix last link
1776
tmp_link.next->prev=0; // Fix first link
1777
if (root) // If not OOM
5232
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5252
if (key1->part != key2->part)
5256
return 0; // Can't optimize this
5259
// If one of the key is MAYBE_KEY then the found region may be bigger
5260
if (key1->type == SEL_ARG::MAYBE_KEY)
5266
if (key2->type == SEL_ARG::MAYBE_KEY)
5273
if (key1->use_count > 0)
5275
if (key2->use_count == 0 || key1->elements > key2->elements)
5277
std::swap(key1,key2);
5279
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5283
// Add tree at key2 to tree at key1
5284
bool key2_shared=key2->use_count != 0;
5285
key1->maybe_flag|=key2->maybe_flag;
5287
for (key2=key2->first(); key2; )
5289
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5294
tmp=key1->first(); // tmp.min > key2.min
5297
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5298
{ // Found tmp.max < key2.min
5299
SEL_ARG *next=tmp->next;
5300
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5302
// Join near ranges like tmp.max < 0 and key2.min >= 0
5303
SEL_ARG *key2_next=key2->next;
5306
if (!(key2=new SEL_ARG(*key2)))
5307
return 0; // out of memory
5308
key2->increment_use_count(key1->use_count+1);
5309
key2->next=key2_next; // New copy of key2
5311
key2->copy_min(tmp);
5312
if (!(key1=key1->tree_delete(tmp)))
5313
{ // Only one key in tree
5320
if (!(tmp=next)) // tmp.min > key2.min
5321
break; // Copy rest of key2
5324
{ // tmp.min > key2.min
5326
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5328
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5329
{ // ranges are connected
5330
tmp->copy_min_to_min(key2);
5331
key1->merge_flags(key2);
5332
if (tmp->min_flag & NO_MIN_RANGE &&
5333
tmp->max_flag & NO_MAX_RANGE)
5335
if (key1->maybe_flag)
5336
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5339
key2->increment_use_count(-1); // Free not used tree
5345
SEL_ARG *next=key2->next; // Keys are not overlapping
5348
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5351
key1=key1->insert(cpy);
5352
key2->increment_use_count(key1->use_count+1);
5355
key1=key1->insert(key2); // Will destroy key2_root
5362
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5363
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5365
if (tmp->is_same(key2))
5367
tmp->merge_flags(key2); // Copy maybe flags
5368
key2->increment_use_count(-1); // Free not used tree
5373
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5374
eq_tree(last->next->next_key_part,key2->next_key_part))
5378
key1=key1->tree_delete(save);
5380
last->copy_min(tmp);
5381
if (last->copy_min(key2) || last->copy_max(key2))
5384
for (; key2 ; key2=key2->next)
5385
key2->increment_use_count(-1); // Free not used tree
5386
if (key1->maybe_flag)
5387
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5395
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5396
{ // tmp.min <= x < key2.min
5397
SEL_ARG *new_arg=tmp->clone_first(key2);
5400
if ((new_arg->next_key_part= key1->next_key_part))
5401
new_arg->increment_use_count(key1->use_count+1);
5402
tmp->copy_min_to_min(key2);
5403
key1=key1->insert(new_arg);
5406
// tmp.min >= key2.min && tmp.min <= key2.max
5407
SEL_ARG key(*key2); // Get copy we can modify
5410
if (tmp->cmp_min_to_min(&key) > 0)
5411
{ // key.min <= x < tmp.min
5412
SEL_ARG *new_arg=key.clone_first(tmp);
5415
if ((new_arg->next_key_part=key.next_key_part))
5416
new_arg->increment_use_count(key1->use_count+1);
5417
key1=key1->insert(new_arg);
5419
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5420
{ // tmp.min. <= x <= tmp.max
5421
tmp->maybe_flag|= key.maybe_flag;
5422
key.increment_use_count(key1->use_count+1);
5423
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5424
if (!cmp) // Key2 is ready
5426
key.copy_max_to_min(tmp);
5427
if (!(tmp=tmp->next))
5429
SEL_ARG *tmp2= new SEL_ARG(key);
5432
key1=key1->insert(tmp2);
5436
if (tmp->cmp_min_to_max(&key) > 0)
5438
SEL_ARG *tmp2= new SEL_ARG(key);
5441
key1=key1->insert(tmp2);
5447
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5450
tmp->copy_max_to_min(&key);
5451
tmp->increment_use_count(key1->use_count+1);
5452
/* Increment key count as it may be used for next loop */
5453
key.increment_use_count(1);
5454
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5455
key1=key1->insert(new_arg);
5465
SEL_ARG *next=key2->next;
5468
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5471
key2->increment_use_count(key1->use_count+1);
5472
key1=key1->insert(tmp);
5475
key1=key1->insert(key2); // Will destroy key2_root
5483
/* Compare if two trees are equal */
5485
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5489
if (!a || !b || !a->is_same(b))
5491
if (a->left != &null_element && b->left != &null_element)
5493
if (!eq_tree(a->left,b->left))
5496
else if (a->left != &null_element || b->left != &null_element)
5498
if (a->right != &null_element && b->right != &null_element)
5500
if (!eq_tree(a->right,b->right))
5503
else if (a->right != &null_element || b->right != &null_element)
5505
if (a->next_key_part != b->next_key_part)
5507
if (!a->next_key_part != !b->next_key_part ||
5508
!eq_tree(a->next_key_part, b->next_key_part))
5516
SEL_ARG::insert(SEL_ARG *key)
5518
SEL_ARG *element, **par= NULL, *last_element= NULL;
5520
for (element= this; element != &null_element ; )
5522
last_element=element;
5523
if (key->cmp_min_to_min(element) > 0)
5525
par= &element->right; element= element->right;
5529
par = &element->left; element= element->left;
5533
key->parent=last_element;
5535
if (par == &last_element->left)
5537
key->next=last_element;
5538
if ((key->prev=last_element->prev))
5539
key->prev->next=key;
5540
last_element->prev=key;
5544
if ((key->next=last_element->next))
5545
key->next->prev=key;
5546
key->prev=last_element;
5547
last_element->next=key;
5549
key->left=key->right= &null_element;
5550
SEL_ARG *root=rb_insert(key); // rebalance tree
5551
root->use_count=this->use_count; // copy root info
5552
root->elements= this->elements+1;
5553
root->maybe_flag=this->maybe_flag;
5559
** Find best key with min <= given key
5560
** Because the call context this should never return 0 to get_range
5564
SEL_ARG::find_range(SEL_ARG *key)
5566
SEL_ARG *element=this,*found=0;
5570
if (element == &null_element)
5572
int cmp=element->cmp_min_to_min(key);
5578
element=element->right;
5581
element=element->left;
5587
Remove a element from the tree
5591
key Key that is to be deleted from tree (this)
5594
This also frees all sub trees that is used by the element
5597
root of new tree (with key deleted)
5601
SEL_ARG::tree_delete(SEL_ARG *key)
5603
enum leaf_color remove_color;
5604
SEL_ARG *root,*nod,**par,*fix_par;
5609
/* Unlink from list */
5611
key->prev->next=key->next;
5613
key->next->prev=key->prev;
5614
key->increment_use_count(-1);
5618
par=key->parent_ptr();
5620
if (key->left == &null_element)
5622
*par=nod=key->right;
5623
fix_par=key->parent;
5624
if (nod != &null_element)
5625
nod->parent=fix_par;
5626
remove_color= key->color;
5628
else if (key->right == &null_element)
5630
*par= nod=key->left;
5631
nod->parent=fix_par=key->parent;
5632
remove_color= key->color;
5636
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5637
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5638
fix_par=tmp->parent;
5639
if (nod != &null_element)
5640
nod->parent=fix_par;
5641
remove_color= tmp->color;
5643
tmp->parent=key->parent; // Move node in place of key
5644
(tmp->left=key->left)->parent=tmp;
5645
if ((tmp->right=key->right) != &null_element)
5646
tmp->right->parent=tmp;
5647
tmp->color=key->color;
5649
if (fix_par == key) // key->right == key->next
5650
fix_par=tmp; // new parent of nod
5653
if (root == &null_element)
5654
return 0; // Maybe root later
5655
if (remove_color == BLACK)
5656
root=rb_delete_fixup(root,nod,fix_par);
5658
test_rb_tree(root,root->parent);
5659
#endif /* EXTRA_DEBUG */
5661
root->use_count=this->use_count; // Fix root counters
5662
root->elements=this->elements-1;
5663
root->maybe_flag=this->maybe_flag;
5668
/* Functions to fix up the tree after insert and delete */
5670
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5672
SEL_ARG *y=leaf->right;
5673
leaf->right=y->left;
5674
if (y->left != &null_element)
5675
y->left->parent=leaf;
5676
if (!(y->parent=leaf->parent))
5679
*leaf->parent_ptr()=y;
5684
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5686
SEL_ARG *y=leaf->left;
5687
leaf->left=y->right;
5688
if (y->right != &null_element)
5689
y->right->parent=leaf;
5690
if (!(y->parent=leaf->parent))
5693
*leaf->parent_ptr()=y;
5700
SEL_ARG::rb_insert(SEL_ARG *leaf)
5702
SEL_ARG *y,*par,*par2,*root;
5703
root= this; root->parent= 0;
5706
while (leaf != root && (par= leaf->parent)->color == RED)
5707
{ // This can't be root or 1 level under
5708
if (par == (par2= leaf->parent->parent)->left)
5711
if (y->color == RED)
5716
leaf->color=RED; /* And the loop continues */
5720
if (leaf == par->right)
5722
left_rotate(&root,leaf->parent);
5723
par=leaf; /* leaf is now parent to old leaf */
5727
right_rotate(&root,par2);
5734
if (y->color == RED)
5739
leaf->color=RED; /* And the loop continues */
5743
if (leaf == par->left)
5745
right_rotate(&root,par);
5750
left_rotate(&root,par2);
5757
test_rb_tree(root,root->parent);
5758
#endif /* EXTRA_DEBUG */
5764
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5770
while (x != root && x->color == SEL_ARG::BLACK)
5775
if (w->color == SEL_ARG::RED)
5777
w->color=SEL_ARG::BLACK;
5778
par->color=SEL_ARG::RED;
5779
left_rotate(&root,par);
5782
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5784
w->color=SEL_ARG::RED;
5789
if (w->right->color == SEL_ARG::BLACK)
5791
w->left->color=SEL_ARG::BLACK;
5792
w->color=SEL_ARG::RED;
5793
right_rotate(&root,w);
5796
w->color=par->color;
5797
par->color=SEL_ARG::BLACK;
5798
w->right->color=SEL_ARG::BLACK;
5799
left_rotate(&root,par);
5807
if (w->color == SEL_ARG::RED)
5809
w->color=SEL_ARG::BLACK;
5810
par->color=SEL_ARG::RED;
5811
right_rotate(&root,par);
5814
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5816
w->color=SEL_ARG::RED;
5821
if (w->left->color == SEL_ARG::BLACK)
5823
w->right->color=SEL_ARG::BLACK;
5824
w->color=SEL_ARG::RED;
5825
left_rotate(&root,w);
5828
w->color=par->color;
5829
par->color=SEL_ARG::BLACK;
5830
w->left->color=SEL_ARG::BLACK;
5831
right_rotate(&root,par);
5838
x->color=SEL_ARG::BLACK;
5843
/* Test that the properties for a red-black tree hold */
5846
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5848
int count_l,count_r;
5850
if (element == &null_element)
5851
return 0; // Found end of tree
5852
if (element->parent != parent)
5854
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5857
if (element->color == SEL_ARG::RED &&
5858
(element->left->color == SEL_ARG::RED ||
5859
element->right->color == SEL_ARG::RED))
5861
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5864
if (element->left == element->right && element->left != &null_element)
5866
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5869
count_l=test_rb_tree(element->left,element);
5870
count_r=test_rb_tree(element->right,element);
5871
if (count_l >= 0 && count_r >= 0)
5873
if (count_l == count_r)
5874
return count_l+(element->color == SEL_ARG::BLACK);
5875
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5878
return -1; // Error, no more warnings
5883
Count how many times SEL_ARG graph "root" refers to its part "key"
5886
count_key_part_usage()
5887
root An RB-Root node in a SEL_ARG graph.
5888
key Another RB-Root node in that SEL_ARG graph.
5891
The passed "root" node may refer to "key" node via root->next_key_part,
5894
This function counts how many times the node "key" is referred (via
5895
SEL_ARG::next_key_part) by
5896
- intervals of RB-tree pointed by "root",
5897
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5898
intervals of RB-tree pointed by "root",
5901
Here is an example (horizontal links represent next_key_part pointers,
5902
vertical links - next/prev prev pointers):
5905
|root|-----------------+
5909
+----+ +---+ $ | +---+ Here the return value
5910
| |- ... -| |---$-+--+->|key| will be 4.
5911
+----+ +---+ $ | | +---+
5916
| |---| |---------+ |
5923
Number of links to "key" from nodes reachable from "root".
5926
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5929
for (root=root->first(); root ; root=root->next)
5931
if (root->next_key_part)
5933
if (root->next_key_part == key)
5935
if (root->next_key_part->part < key->part)
5936
count+=count_key_part_usage(root->next_key_part,key);
5944
Check if SEL_ARG::use_count value is correct
5947
SEL_ARG::test_use_count()
5948
root The root node of the SEL_ARG graph (an RB-tree root node that
5949
has the least value of sel_arg->part in the entire graph, and
5950
thus is the "origin" of the graph)
5953
Check if SEL_ARG::use_count value is correct. See the definition of
5954
use_count for what is "correct".
5957
void SEL_ARG::test_use_count(SEL_ARG *root)
5960
if (this == root && use_count != 1)
5962
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5965
if (this->type != SEL_ARG::KEY_RANGE)
5967
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5970
if (pos->next_key_part)
5972
ulong count=count_key_part_usage(root,pos->next_key_part);
5973
if (count > pos->next_key_part->use_count)
5975
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5976
"should be %lu", (long unsigned int)pos,
5977
pos->next_key_part->use_count, count);
5980
pos->next_key_part->test_use_count(root);
5983
if (e_count != elements)
5984
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5985
e_count, elements, (long unsigned int) this);
3523
5990
/****************************************************************************
3524
5991
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3525
5992
****************************************************************************/
4339
Range sequence interface implementation for array<QuickRange>: initialize
6818
Perform key scans for all used indexes (except CPK), get rowids and merge
6819
them into an ordered non-recurrent sequence of rowids.
6821
The merge/duplicate removal is performed using Unique class. We put all
6822
rowids into Unique, get the sorted sequence and destroy the Unique.
6824
If table has a clustered primary key that covers all rows (true for bdb
6825
and innodb currently) and one of the index_merge scans is a scan on PK,
6826
then rows that will be retrieved by PK scan are not put into Unique and
6827
primary key scan is not performed here, it is performed later separately.
6834
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6836
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6837
QUICK_RANGE_SELECT* cur_quick;
6840
handler *file= head->file;
6842
file->extra(HA_EXTRA_KEYREAD);
6843
head->prepare_for_position();
6845
cur_quick_it.rewind();
6846
cur_quick= cur_quick_it++;
6847
assert(cur_quick != 0);
6850
We reuse the same instance of handler so we need to call both init and
6853
if (cur_quick->init() || cur_quick->reset())
6856
unique= new Unique(refpos_order_cmp, (void *)file,
6858
session->variables.sortbuff_size);
6863
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6865
cur_quick->range_end();
6866
cur_quick= cur_quick_it++;
6870
if (cur_quick->file->inited != handler::NONE)
6871
cur_quick->file->ha_index_end();
6872
if (cur_quick->init() || cur_quick->reset())
6878
if (result != HA_ERR_END_OF_FILE)
6880
cur_quick->range_end();
6886
if (session->killed)
6889
/* skip row if it will be retrieved by clustered PK scan */
6890
if (pk_quick_select && pk_quick_select->row_in_ranges())
6893
cur_quick->file->position(cur_quick->record);
6894
result= unique->unique_add((char*)cur_quick->file->ref);
6900
/* ok, all row ids are in Unique */
6901
result= unique->get(head);
6903
doing_pk_scan= false;
6904
/* index_merge currently doesn't support "using index" at all */
6905
file->extra(HA_EXTRA_NO_KEYREAD);
6906
/* start table scan */
6907
init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
6913
Get next row for index_merge.
6915
The rows are read from
6916
1. rowids stored in Unique.
6917
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6918
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6921
int QUICK_INDEX_MERGE_SELECT::get_next()
6926
return(pk_quick_select->get_next());
6928
if ((result= read_record.read_record(&read_record)) == -1)
6930
result= HA_ERR_END_OF_FILE;
6931
end_read_record(&read_record);
6932
/* All rows from Unique have been retrieved, do a clustered PK scan */
6933
if (pk_quick_select)
6935
doing_pk_scan= true;
6936
if ((result= pk_quick_select->init()) ||
6937
(result= pk_quick_select->reset()))
6939
return(pk_quick_select->get_next());
6948
Retrieve next record.
6950
QUICK_ROR_INTERSECT_SELECT::get_next()
6953
Invariant on enter/exit: all intersected selects have retrieved all index
6954
records with rowid <= some_rowid_val and no intersected select has
6955
retrieved any index records with rowid > some_rowid_val.
6956
We start fresh and loop until we have retrieved the same rowid in each of
6957
the key scans or we got an error.
6959
If a Clustered PK scan is present, it is used only to check if row
6960
satisfies its condition (and never used for row retrieval).
6964
other - Error code if any error occurred.
6967
int QUICK_ROR_INTERSECT_SELECT::get_next()
6969
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6970
QUICK_RANGE_SELECT* quick;
6972
uint32_t last_rowid_count=0;
6976
/* Get a rowid for first quick and save it as a 'candidate' */
6978
error= quick->get_next();
6981
while (!error && !cpk_quick->row_in_ranges())
6982
error= quick->get_next();
6987
quick->file->position(quick->record);
6988
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6989
last_rowid_count= 1;
6991
while (last_rowid_count < quick_selects.elements)
6993
if (!(quick= quick_it++))
7001
if ((error= quick->get_next()))
7003
quick->file->position(quick->record);
7004
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
7007
/* Ok, current select 'caught up' and returned ref >= cur_ref */
7010
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
7013
while (!cpk_quick->row_in_ranges())
7015
if ((error= quick->get_next()))
7019
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7020
last_rowid_count= 1;
7024
/* current 'candidate' row confirmed by this select */
7029
/* We get here if we got the same row ref in all scans. */
7030
if (need_to_fetch_row)
7031
error= head->file->rnd_pos(head->record[0], last_rowid);
7032
} while (error == HA_ERR_RECORD_DELETED);
7038
Retrieve next record.
7040
QUICK_ROR_UNION_SELECT::get_next()
7043
Enter/exit invariant:
7044
For each quick select in the queue a {key,rowid} tuple has been
7045
retrieved but the corresponding row hasn't been passed to output.
7049
other - Error code if any error occurred.
7052
int QUICK_ROR_UNION_SELECT::get_next()
7055
QUICK_SELECT_I *quick;
7062
if (!queue.elements)
7063
return(HA_ERR_END_OF_FILE);
7064
/* Ok, we have a queue with >= 1 scans */
7066
quick= (QUICK_SELECT_I*)queue_top(&queue);
7067
memcpy(cur_rowid, quick->last_rowid, rowid_length);
7069
/* put into queue rowid from the same stream as top element */
7070
if ((error= quick->get_next()))
7072
if (error != HA_ERR_END_OF_FILE)
7074
queue_remove(&queue, 0);
7078
quick->save_last_pos();
7079
queue_replaced(&queue);
7082
if (!have_prev_rowid)
7084
/* No rows have been returned yet */
7086
have_prev_rowid= true;
7089
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
7093
cur_rowid= prev_rowid;
7096
error= head->file->rnd_pos(quick->record, prev_rowid);
7097
} while (error == HA_ERR_RECORD_DELETED);
7102
int QUICK_RANGE_SELECT::reset()
7105
unsigned char *mrange_buff;
7107
HANDLER_BUFFER empty_buf;
7109
cur_range= (QUICK_RANGE**) ranges.buffer;
7111
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
7114
/* Allocate buffer if we need one but haven't allocated it yet */
7115
if (mrr_buf_size && !mrr_buf_desc)
7117
buf_size= mrr_buf_size;
7118
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7119
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7120
&mrange_buff, buf_size,
7123
/* Try to shrink the buffers until both are 0. */
7127
return(HA_ERR_OUT_OF_MEM);
7129
/* Initialize the handler buffer. */
7130
mrr_buf_desc->buffer= mrange_buff;
7131
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7132
mrr_buf_desc->end_of_used_area= mrange_buff;
7136
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7139
mrr_flags |= HA_MRR_SORTED;
7140
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7141
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7142
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7149
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4342
7152
quick_range_seq_init()
4343
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7153
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4344
7154
n_ranges Number of ranges in the sequence (ignored)
4345
7155
flags MRR flags (currently not used)
4372
7182
1 No more ranges in the sequence
4374
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7185
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4376
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7187
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4378
7189
if (ctx->cur == ctx->last)
4379
7190
return 1; /* no more ranges */
4381
optimizer::QuickRange *cur= *(ctx->cur);
7192
QUICK_RANGE *cur= *(ctx->cur);
4382
7193
key_range *start_key= &range->start_key;
4383
key_range *end_key= &range->end_key;
7194
key_range *end_key= &range->end_key;
4385
start_key->key= cur->min_key;
7196
start_key->key= cur->min_key;
4386
7197
start_key->length= cur->min_length;
4387
7198
start_key->keypart_map= cur->min_keypart_map;
4388
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4389
(cur->flag & EQ_RANGE) ?
4390
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4391
end_key->key= cur->max_key;
4392
end_key->length= cur->max_length;
7199
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7200
(cur->flag & EQ_RANGE) ?
7201
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7202
end_key->key= cur->max_key;
7203
end_key->length= cur->max_length;
4393
7204
end_key->keypart_map= cur->max_keypart_map;
4395
7206
We use HA_READ_AFTER_KEY here because if we are reading on a key
4396
7207
prefix. We want to find all keys with this prefix.
4398
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7209
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4400
7211
range->range_flag= cur->flag;
4406
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4408
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4409
optimizer::SEL_TREE *range_tree,
4410
optimizer::Parameter *param,
4411
uint32_t *param_idx);
4413
static bool get_constant_key_infix(KeyInfo *index_info,
4414
optimizer::SEL_ARG *index_range_tree,
4415
KeyPartInfo *first_non_group_part,
4416
KeyPartInfo *min_max_arg_part,
4417
KeyPartInfo *last_part,
4419
unsigned char *key_infix,
4420
uint32_t *key_infix_len,
4421
KeyPartInfo **first_non_infix_part);
4423
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7218
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7221
mrr_persistent_flag_storage()
7222
seq Range sequence being traversed
7226
MRR/NDB implementation needs to store some bits for each range. This
7227
function returns a reference to the "range_flag" associated with the
7230
This function should be removed when we get a proper MRR/NDB
7234
Reference to range_flag associated with range number #idx
7237
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7239
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7240
return ctx->first[idx]->flag;
7245
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7248
mrr_get_ptr_by_idx()
7249
seq Range sequence bening traversed
7250
idx Number of the range
7253
An extension of MRR range sequence interface needed by NDB: return the
7254
data associated with the given range.
7256
A proper MRR interface implementer is supposed to store and return
7257
range-associated data. NDB stores number of the range instead. So this
7258
is a helper function that translates range number to range associated
7261
This function does nothing, as currrently there is only one user of the
7262
MRR interface - the quick range select code, and this user doesn't need
7263
to use range-associated data.
7266
Reference to range-associated data
7269
char* &mrr_get_ptr_by_idx(range_seq_t, uint32_t)
7277
Get next possible record using quick-struct.
7280
QUICK_RANGE_SELECT::get_next()
7283
Record is read into table->record[0]
7287
HA_ERR_END_OF_FILE No (more) rows in range
7291
int QUICK_RANGE_SELECT::get_next()
7294
if (in_ror_merged_scan)
7297
We don't need to signal the bitmap change as the bitmap is always the
7298
same for this head->file
7300
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7303
int result= file->multi_range_read_next(&dummy);
7305
if (in_ror_merged_scan)
7307
/* Restore bitmaps set on entry */
7308
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7315
Get the next record with a different prefix.
7318
QUICK_RANGE_SELECT::get_next_prefix()
7319
prefix_length length of cur_prefix
7320
cur_prefix prefix of a key to be searched for
7323
Each subsequent call to the method retrieves the first record that has a
7324
prefix with length prefix_length different from cur_prefix, such that the
7325
record with the new prefix is within the ranges described by
7326
this->ranges. The record found is stored into the buffer pointed by
7328
The method is useful for GROUP-BY queries with range conditions to
7329
discover the prefix of the next group that satisfies the range conditions.
7332
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7333
methods should be unified into a more general one to reduce code
7338
HA_ERR_END_OF_FILE if returned all keys
7339
other if some error occurred
7342
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7343
key_part_map keypart_map,
7344
unsigned char *cur_prefix)
7349
key_range start_key, end_key;
7352
/* Read the next record in the same range with prefix after cur_prefix. */
7353
assert(cur_prefix != 0);
7354
result= file->index_read_map(record, cur_prefix, keypart_map,
7356
if (result || (file->compare_key(file->end_range) <= 0))
7360
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7363
/* Ranges have already been used up before. None is left for read. */
7365
return HA_ERR_END_OF_FILE;
7367
last_range= *(cur_range++);
7369
start_key.key= (const unsigned char*) last_range->min_key;
7370
start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7371
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7372
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7373
(last_range->flag & EQ_RANGE) ?
7374
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7375
end_key.key= (const unsigned char*) last_range->max_key;
7376
end_key.length= cmin(last_range->max_length, (uint16_t)prefix_length);
7377
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7379
We use READ_AFTER_KEY here because if we are reading on a key
7380
prefix we want to find all keys with this prefix
7382
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7385
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7386
last_range->max_keypart_map ? &end_key : 0,
7387
test(last_range->flag & EQ_RANGE),
7389
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7390
last_range= 0; // Stop searching
7392
if (result != HA_ERR_END_OF_FILE)
7394
last_range= 0; // No matching rows; go to next range
7400
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7403
It is assumed that currently a scan is being done on another index
7404
which reads all necessary parts of the index that is scanned by this
7406
The implementation does a binary search on sorted array of disjoint
7407
ranges, without taking size of range into account.
7409
This function is used to filter out clustered PK scan rows in
7410
index_merge quick select.
7413
true if current row will be retrieved by this quick select
7417
bool QUICK_RANGE_SELECT::row_in_ranges()
7421
uint32_t max= ranges.elements - 1;
7422
uint32_t mid= (max + min)/2;
7426
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7428
/* current row value > mid->max */
7433
mid= (min + max) / 2;
7435
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7436
return (!cmp_next(res) && !cmp_prev(res));
7440
This is a hack: we inherit from QUICK_SELECT so that we can use the
7441
get_next() interface, but we have to hold a pointer to the original
7442
QUICK_SELECT because its data are used all over the place. What
7443
should be done is to factor out the data that is needed into a base
7444
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7445
which handle the ranges and implement the get_next() function. But
7446
for now, this seems to work right at least.
7449
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7450
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7454
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7455
QUICK_RANGE **end_range= pr + ranges.elements;
7456
for (; pr!=end_range; pr++)
7457
rev_ranges.push_front(*pr);
7459
/* Remove EQ_RANGE flag for keys that are not using the full key */
7460
for (r = rev_it++; r; r = rev_it++)
7462
if ((r->flag & EQ_RANGE) &&
7463
head->key_info[index].key_length != r->max_length)
7464
r->flag&= ~EQ_RANGE;
7467
q->dont_free=1; // Don't free shared mem
7472
int QUICK_SELECT_DESC::get_next()
7474
/* The max key is handled as follows:
7475
* - if there is NO_MAX_RANGE, start at the end and move backwards
7476
* - if it is an EQ_RANGE, which means that max key covers the entire
7477
* key, go directly to the key and read through it (sorting backwards is
7478
* same as sorting forwards)
7479
* - if it is NEAR_MAX, go to the key or next, step back once, and
7481
* - otherwise (not NEAR_MAX == include the key), go after the key,
7482
* step back once, and move backwards
7489
{ // Already read through key
7490
result = ((last_range->flag & EQ_RANGE)
7491
? file->index_next_same(record, last_range->min_key,
7492
last_range->min_length) :
7493
file->index_prev(record));
7496
if (cmp_prev(*rev_it.ref()) == 0)
7499
else if (result != HA_ERR_END_OF_FILE)
7503
if (!(last_range= rev_it++))
7504
return HA_ERR_END_OF_FILE; // All ranges used
7506
if (last_range->flag & NO_MAX_RANGE) // Read last record
7509
if ((local_error=file->index_last(record)))
7510
return(local_error); // Empty table
7511
if (cmp_prev(last_range) == 0)
7513
last_range= 0; // No match; go to next range
7517
if (last_range->flag & EQ_RANGE)
7519
result = file->index_read_map(record, last_range->max_key,
7520
last_range->max_keypart_map,
7525
assert(last_range->flag & NEAR_MAX ||
7526
range_reads_after_key(last_range));
7527
result=file->index_read_map(record, last_range->max_key,
7528
last_range->max_keypart_map,
7529
((last_range->flag & NEAR_MAX) ?
7530
HA_READ_BEFORE_KEY :
7531
HA_READ_PREFIX_LAST_OR_PREV));
7535
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7537
last_range= 0; // Not found, to next range
7540
if (cmp_prev(last_range) == 0)
7542
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7543
last_range= 0; // Stop searching
7544
return 0; // Found key is in range
7546
last_range= 0; // To next range
7552
Compare if found key is over max-value
7553
Returns 0 if key <= range->max_key
7554
TODO: Figure out why can't this function be as simple as cmp_prev().
7557
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7559
if (range_arg->flag & NO_MAX_RANGE)
7560
return 0; /* key can't be to large */
7562
KEY_PART *key_part=key_parts;
7563
uint32_t store_length;
7565
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7567
key+= store_length, key_part++)
7570
store_length= key_part->store_length;
7571
if (key_part->null_bit)
7575
if (!key_part->field->is_null())
7579
else if (key_part->field->is_null())
7581
key++; // Skip null byte
7584
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7589
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7594
Returns 0 if found key is inside range (found key >= range->min_key).
7597
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7600
if (range_arg->flag & NO_MIN_RANGE)
7601
return 0; /* key can't be to small */
7603
cmp= key_cmp(key_part_info, range_arg->min_key,
7604
range_arg->min_length);
7605
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7607
return 1; // outside of range
7612
* true if this range will require using HA_READ_AFTER_KEY
7613
See comment in get_next() about this
7616
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7618
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7619
!(range_arg->flag & EQ_RANGE) ||
7620
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7624
void QUICK_RANGE_SELECT::add_info_string(String *str)
7626
KEY *key_info= head->key_info + index;
7627
str->append(key_info->name);
7630
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7632
QUICK_RANGE_SELECT *quick;
7634
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7635
str->append(STRING_WITH_LEN("sort_union("));
7636
while ((quick= it++))
7642
quick->add_info_string(str);
7644
if (pk_quick_select)
7647
pk_quick_select->add_info_string(str);
7652
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7655
QUICK_RANGE_SELECT *quick;
7656
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7657
str->append(STRING_WITH_LEN("intersect("));
7658
while ((quick= it++))
7660
KEY *key_info= head->key_info + quick->index;
7665
str->append(key_info->name);
7669
KEY *key_info= head->key_info + cpk_quick->index;
7671
str->append(key_info->name);
7676
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7679
QUICK_SELECT_I *quick;
7680
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7681
str->append(STRING_WITH_LEN("union("));
7682
while ((quick= it++))
7688
quick->add_info_string(str);
7694
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7695
String *used_lengths)
7699
KEY *key_info= head->key_info + index;
7700
key_names->append(key_info->name);
7701
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7702
used_lengths->append(buf, length);
7705
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7706
String *used_lengths)
7711
QUICK_RANGE_SELECT *quick;
7713
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7714
while ((quick= it++))
7720
key_names->append(',');
7721
used_lengths->append(',');
7724
KEY *key_info= head->key_info + quick->index;
7725
key_names->append(key_info->name);
7726
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7727
used_lengths->append(buf, length);
7729
if (pk_quick_select)
7731
KEY *key_info= head->key_info + pk_quick_select->index;
7732
key_names->append(',');
7733
key_names->append(key_info->name);
7734
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7735
used_lengths->append(',');
7736
used_lengths->append(buf, length);
7740
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7741
String *used_lengths)
7746
QUICK_RANGE_SELECT *quick;
7747
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7748
while ((quick= it++))
7750
KEY *key_info= head->key_info + quick->index;
7755
key_names->append(',');
7756
used_lengths->append(',');
7758
key_names->append(key_info->name);
7759
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7760
used_lengths->append(buf, length);
7765
KEY *key_info= head->key_info + cpk_quick->index;
7766
key_names->append(',');
7767
key_names->append(key_info->name);
7768
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7769
used_lengths->append(',');
7770
used_lengths->append(buf, length);
7774
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7775
String *used_lengths)
7778
QUICK_SELECT_I *quick;
7779
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7780
while ((quick= it++))
7786
used_lengths->append(',');
7787
key_names->append(',');
7789
quick->add_keys_and_lengths(key_names, used_lengths);
7794
/*******************************************************************************
7795
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7796
*******************************************************************************/
7798
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7799
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7800
PARAM *param, uint32_t *param_idx);
7801
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7802
KEY_PART_INFO *first_non_group_part,
7803
KEY_PART_INFO *min_max_arg_part,
7804
KEY_PART_INFO *last_part, Session *session,
7805
unsigned char *key_infix, uint32_t *key_infix_len,
7806
KEY_PART_INFO **first_non_infix_part);
7808
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7809
Field::imagetype image_type);
4426
cost_group_min_max(Table* table,
4427
KeyInfo *index_info,
4428
uint32_t used_key_parts,
4429
uint32_t group_key_parts,
4430
optimizer::SEL_TREE *range_tree,
4431
optimizer::SEL_ARG *index_tree,
4432
ha_rows quick_prefix_records,
7812
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7813
uint32_t group_key_parts, SEL_TREE *range_tree,
7814
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7815
bool have_min, bool have_max,
7816
double *read_cost, ha_rows *records);
5557
optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5559
optimizer::QuickRangeSelect *quick= NULL;
5560
if ((quick= optimizer::get_quick_select(param,
5567
quick->records= records;
5568
quick->read_time= read_cost;
5574
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5576
boost::dynamic_bitset<> map= bitsToBitset();
5577
for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5588
size_t optimizer::RorScanInfo::getBitCount() const
5590
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5591
return tmp_bitset.count();
5595
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5597
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5598
tmp_bitset-= in_bitset;
5599
covered_fields= tmp_bitset.to_ulong();
5603
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5606
uint64_t conv= covered_fields;
5609
res.push_back((conv & 1) + '0');
5614
std::reverse(res.begin(), res.end());
5616
string final(covered_fields_size - res.length(), '0');
5618
return (boost::dynamic_bitset<>(final));
5622
} /* namespace drizzled */
8871
Construct new quick select for group queries with min/max.
8874
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8875
table The table being accessed
8876
join Descriptor of the current query
8877
have_min true if the query selects a MIN function
8878
have_max true if the query selects a MAX function
8879
min_max_arg_part The only argument field of all MIN/MAX functions
8880
group_prefix_len Length of all key parts in the group prefix
8881
prefix_key_parts All key parts in the group prefix
8882
index_info The index chosen for data access
8883
use_index The id of index_info
8884
read_cost Cost of this access method
8885
records Number of records returned
8886
key_infix_len Length of the key infix appended to the group prefix
8887
key_infix Infix of constants from equality predicates
8888
parent_alloc Memory pool for this and quick_prefix_select data
8894
QUICK_GROUP_MIN_MAX_SELECT::
8895
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8897
KEY_PART_INFO *min_max_arg_part_arg,
8898
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8899
uint32_t used_key_parts_arg, KEY *index_info_arg,
8900
uint32_t use_index, double read_cost_arg,
8901
ha_rows records_arg, uint32_t key_infix_len_arg,
8902
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8903
:join(join_arg), index_info(index_info_arg),
8904
group_prefix_len(group_prefix_len_arg),
8905
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8906
have_max(have_max_arg), seen_first_key(false),
8907
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8908
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8909
max_functions_it(NULL)
8914
record= head->record[0];
8915
tmp_record= head->record[1];
8916
read_time= read_cost_arg;
8917
records= records_arg;
8918
used_key_parts= used_key_parts_arg;
8919
real_key_parts= used_key_parts_arg;
8920
real_prefix_len= group_prefix_len + key_infix_len;
8922
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8925
We can't have parent_alloc set as the init function can't handle this case
8928
assert(!parent_alloc);
8931
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
8932
join->session->mem_root= &alloc;
8935
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8940
Do post-constructor initialization.
8943
QUICK_GROUP_MIN_MAX_SELECT::init()
8946
The method performs initialization that cannot be done in the constructor
8947
such as memory allocations that may fail. It allocates memory for the
8948
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8949
updated during execution.
8956
int QUICK_GROUP_MIN_MAX_SELECT::init()
8958
if (group_prefix) /* Already initialized. */
8961
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8964
We may use group_prefix to store keys with all select fields, so allocate
8965
enough space for it.
8967
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
8968
real_prefix_len + min_max_arg_len)))
8971
if (key_infix_len > 0)
8974
The memory location pointed to by key_infix will be deleted soon, so
8975
allocate a new buffer and copy the key_infix into it.
8977
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
8980
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8981
this->key_infix= tmp_key_infix;
8984
if (min_max_arg_part)
8986
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8991
if (!(min_functions= new List<Item_sum>))
8995
min_functions= NULL;
8998
if (!(max_functions= new List<Item_sum>))
9002
max_functions= NULL;
9004
Item_sum *min_max_item;
9005
Item_sum **func_ptr= join->sum_funcs;
9006
while ((min_max_item= *(func_ptr++)))
9008
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
9009
min_functions->push_back(min_max_item);
9010
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
9011
max_functions->push_back(min_max_item);
9016
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
9022
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
9027
min_max_ranges.elements= 0;
9033
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
9035
if (file->inited != handler::NONE)
9036
file->ha_index_end();
9037
if (min_max_arg_part)
9038
delete_dynamic(&min_max_ranges);
9039
free_root(&alloc,MYF(0));
9040
delete min_functions_it;
9041
delete max_functions_it;
9042
delete quick_prefix_select;
9047
Eventually create and add a new quick range object.
9050
QUICK_GROUP_MIN_MAX_SELECT::add_range()
9051
sel_range Range object from which a
9054
Construct a new QUICK_RANGE object from a SEL_ARG object, and
9055
add it to the array min_max_ranges. If sel_arg is an infinite
9056
range, e.g. (x < 5 or x > 4), then skip it and do not construct
9064
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
9067
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
9069
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
9070
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
9073
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
9074
!(sel_range->max_flag & NO_MAX_RANGE))
9076
if (sel_range->maybe_null &&
9077
sel_range->min_value[0] && sel_range->max_value[0])
9078
range_flag|= NULL_RANGE; /* IS NULL condition */
9079
else if (memcmp(sel_range->min_value, sel_range->max_value,
9080
min_max_arg_len) == 0)
9081
range_flag|= EQ_RANGE; /* equality condition */
9083
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
9084
make_keypart_map(sel_range->part),
9085
sel_range->max_value, min_max_arg_len,
9086
make_keypart_map(sel_range->part),
9090
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
9097
Opens the ranges if there are more conditions in quick_prefix_select than
9098
the ones used for jumping through the prefixes.
9101
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9104
quick_prefix_select is made over the conditions on the whole key.
9105
It defines a number of ranges of length x.
9106
However when jumping through the prefixes we use only the the first
9107
few most significant keyparts in the range key. However if there
9108
are more keyparts to follow the ones we are using we must make the
9109
condition on the key inclusive (because x < "ab" means
9110
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9111
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9113
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9115
if (quick_prefix_select &&
9116
group_prefix_len < quick_prefix_select->max_used_key_length)
9121
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9125
get_dynamic(arr, (unsigned char*)&range, inx);
9126
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9133
Determine the total number and length of the keys that will be used for
9137
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9140
The total length of the keys used for index lookup depends on whether
9141
there are any predicates referencing the min/max argument, and/or if
9142
the min/max argument field can be NULL.
9143
This function does an optimistic analysis whether the search key might
9144
be extended by a constant for the min/max keypart. It is 'optimistic'
9145
because during actual execution it may happen that a particular range
9146
is skipped, and then a shorter key will be used. However this is data
9147
dependent and can't be easily estimated here.
9153
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9155
max_used_key_length= real_prefix_len;
9156
if (min_max_ranges.elements > 0)
9158
QUICK_RANGE *cur_range;
9160
{ /* Check if the right-most range has a lower boundary. */
9161
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9162
min_max_ranges.elements - 1);
9163
if (!(cur_range->flag & NO_MIN_RANGE))
9165
max_used_key_length+= min_max_arg_len;
9171
{ /* Check if the left-most range has an upper boundary. */
9172
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9173
if (!(cur_range->flag & NO_MAX_RANGE))
9175
max_used_key_length+= min_max_arg_len;
9181
else if (have_min && min_max_arg_part &&
9182
min_max_arg_part->field->real_maybe_null())
9185
If a MIN/MAX argument value is NULL, we can quickly determine
9186
that we're in the beginning of the next group, because NULLs
9187
are always < any other value. This allows us to quickly
9188
determine the end of the current group and jump to the next
9189
group (see next_min()) and thus effectively increases the
9192
max_used_key_length+= min_max_arg_len;
9199
Initialize a quick group min/max select for key retrieval.
9202
QUICK_GROUP_MIN_MAX_SELECT::reset()
9205
Initialize the index chosen for access and find and store the prefix
9206
of the last group. The method is expensive since it performs disk access.
9213
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9217
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9218
if ((result= file->ha_index_init(index,1)))
9220
if (quick_prefix_select && quick_prefix_select->reset())
9222
result= file->index_last(record);
9223
if (result == HA_ERR_END_OF_FILE)
9225
/* Save the prefix of the last group. */
9226
key_copy(last_prefix, record, index_info, group_prefix_len);
9234
Get the next key containing the MIN and/or MAX key for the next group.
9237
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9240
The method finds the next subsequent group of records that satisfies the
9241
query conditions and finds the keys that contain the MIN/MAX values for
9242
the key part referenced by the MIN/MAX function(s). Once a group and its
9243
MIN/MAX values are found, store these values in the Item_sum objects for
9244
the MIN/MAX functions. The rest of the values in the result row are stored
9245
in the Item_field::result_field of each select field. If the query does
9246
not contain MIN and/or MAX functions, then the function only finds the
9247
group prefix, which is a query answer itself.
9250
If both MIN and MAX are computed, then we use the fact that if there is
9251
no MIN key, there can't be a MAX key as well, so we can skip looking
9252
for a MAX key in this case.
9256
HA_ERR_END_OF_FILE if returned all keys
9257
other if some error occurred
9260
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9265
int is_last_prefix= 0;
9268
Loop until a group is found that satisfies all query conditions or the last
9273
result= next_prefix();
9275
Check if this is the last group prefix. Notice that at this point
9276
this->record contains the current prefix in record format.
9280
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9282
assert(is_last_prefix <= 0);
9286
if (result == HA_ERR_KEY_NOT_FOUND)
9293
min_res= next_min();
9295
update_min_result();
9297
/* If there is no MIN in the group, there is no MAX either. */
9298
if ((have_max && !have_min) ||
9299
(have_max && have_min && (min_res == 0)))
9301
max_res= next_max();
9303
update_max_result();
9304
/* If a MIN was found, a MAX must have been found as well. */
9305
assert(((have_max && !have_min) ||
9306
(have_max && have_min && (max_res == 0))));
9309
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9310
are equality predicates for the key parts after the group, find the
9311
first sub-group with the extended prefix.
9313
if (!have_min && !have_max && key_infix_len > 0)
9314
result= file->index_read_map(record, group_prefix,
9315
make_prev_keypart_map(real_key_parts),
9318
result= have_min ? min_res : have_max ? max_res : result;
9319
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9320
is_last_prefix != 0);
9325
Partially mimic the behavior of end_select_send. Copy the
9326
field data from Item_field::field into Item_field::result_field
9327
of each non-aggregated field (the group fields, and optionally
9328
other fields in non-ANSI SQL mode).
9330
copy_fields(&join->tmp_table_param);
9332
else if (result == HA_ERR_KEY_NOT_FOUND)
9333
result= HA_ERR_END_OF_FILE;
9340
Retrieve the minimal key in the next group.
9343
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9346
Find the minimal key within this group such that the key satisfies the query
9347
conditions and NULL semantics. The found key is loaded into this->record.
9350
Depending on the values of min_max_ranges.elements, key_infix_len, and
9351
whether there is a NULL in the MIN field, this function may directly
9352
return without any data access. In this case we use the key loaded into
9353
this->record by the call to this->next_prefix() just before this call.
9357
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9358
HA_ERR_END_OF_FILE - "" -
9359
other if some error occurred
9362
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9366
/* Find the MIN key using the eventually extended group prefix. */
9367
if (min_max_ranges.elements > 0)
9369
if ((result= next_min_in_range()))
9374
/* Apply the constant equality conditions to the non-group select fields */
9375
if (key_infix_len > 0)
9377
if ((result= file->index_read_map(record, group_prefix,
9378
make_prev_keypart_map(real_key_parts),
9379
HA_READ_KEY_EXACT)))
9384
If the min/max argument field is NULL, skip subsequent rows in the same
9385
group with NULL in it. Notice that:
9386
- if the first row in a group doesn't have a NULL in the field, no row
9387
in the same group has (because NULL < any other value),
9388
- min_max_arg_part->field->ptr points to some place in 'record'.
9390
if (min_max_arg_part && min_max_arg_part->field->is_null())
9392
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9393
key_copy(tmp_record, record, index_info, 0);
9394
result= file->index_read_map(record, tmp_record,
9395
make_keypart_map(real_key_parts),
9398
Check if the new record belongs to the current group by comparing its
9399
prefix with the group's prefix. If it is from the next group, then the
9400
whole group has NULLs in the MIN/MAX field, so use the first record in
9401
the group as a result.
9403
It is possible to reuse this new record as the result candidate for the
9404
next call to next_min(), and to save one lookup in the next call. For
9405
this add a new member 'this->next_group_prefix'.
9409
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9410
key_restore(record, tmp_record, index_info, 0);
9412
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9413
result= 0; /* There is a result in any case. */
9418
If the MIN attribute is non-nullable, this->record already contains the
9419
MIN key in the group, so just return.
9426
Retrieve the maximal key in the next group.
9429
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9432
Lookup the maximal key of the group, and store it into this->record.
9436
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9437
HA_ERR_END_OF_FILE - "" -
9438
other if some error occurred
9441
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9445
/* Get the last key in the (possibly extended) group. */
9446
if (min_max_ranges.elements > 0)
9447
result= next_max_in_range();
9449
result= file->index_read_map(record, group_prefix,
9450
make_prev_keypart_map(real_key_parts),
9451
HA_READ_PREFIX_LAST);
9457
Determine the prefix of the next group.
9460
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9463
Determine the prefix of the next group that satisfies the query conditions.
9464
If there is a range condition referencing the group attributes, use a
9465
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9466
condition. If there is a key infix of constants, append this infix
9467
immediately after the group attributes. The possibly extended prefix is
9468
stored in this->group_prefix. The first key of the found group is stored in
9469
this->record, on which relies this->next_min().
9473
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9474
HA_ERR_END_OF_FILE if there are no more keys
9475
other if some error occurred
9477
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9481
if (quick_prefix_select)
9483
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9484
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9485
make_prev_keypart_map(group_key_parts), cur_prefix)))
9487
seen_first_key= true;
9491
if (!seen_first_key)
9493
result= file->index_first(record);
9496
seen_first_key= true;
9500
/* Load the first key in this group into record. */
9501
result= file->index_read_map(record, group_prefix,
9502
make_prev_keypart_map(group_key_parts),
9509
/* Save the prefix of this group for subsequent calls. */
9510
key_copy(group_prefix, record, index_info, group_prefix_len);
9511
/* Append key_infix to group_prefix. */
9512
if (key_infix_len > 0)
9513
memcpy(group_prefix + group_prefix_len,
9514
key_infix, key_infix_len);
9521
Find the minimal key in a group that satisfies some range conditions for the
9522
min/max argument field.
9525
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9528
Given the sequence of ranges min_max_ranges, find the minimal key that is
9529
in the left-most possible range. If there is no such key, then the current
9530
group does not have a MIN key that satisfies the WHERE clause. If a key is
9531
found, its value is stored in this->record.
9535
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9537
HA_ERR_END_OF_FILE - "" -
9541
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9543
ha_rkey_function find_flag;
9544
key_part_map keypart_map;
9545
QUICK_RANGE *cur_range;
9546
bool found_null= false;
9547
int result= HA_ERR_KEY_NOT_FOUND;
9548
basic_string<unsigned char> max_key;
9550
max_key.reserve(real_prefix_len + min_max_arg_len);
9552
assert(min_max_ranges.elements > 0);
9554
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9555
{ /* Search from the left-most range to the right. */
9556
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9559
If the current value for the min/max argument is bigger than the right
9560
boundary of cur_range, there is no need to check this range.
9562
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9563
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9564
min_max_arg_len) == 1))
9567
if (cur_range->flag & NO_MIN_RANGE)
9569
keypart_map= make_prev_keypart_map(real_key_parts);
9570
find_flag= HA_READ_KEY_EXACT;
9574
/* Extend the search key with the lower boundary for this range. */
9575
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9576
cur_range->min_length);
9577
keypart_map= make_keypart_map(real_key_parts);
9578
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9579
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9580
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9583
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9586
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9587
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9588
continue; /* Check the next range. */
9591
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9592
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9593
range, it can't succeed for any other subsequent range.
9598
/* A key was found. */
9599
if (cur_range->flag & EQ_RANGE)
9600
break; /* No need to perform the checks below for equal keys. */
9602
if (cur_range->flag & NULL_RANGE)
9605
Remember this key, and continue looking for a non-NULL key that
9606
satisfies some other condition.
9608
memcpy(tmp_record, record, head->s->rec_buff_length);
9613
/* Check if record belongs to the current group. */
9614
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9616
result= HA_ERR_KEY_NOT_FOUND;
9620
/* If there is an upper limit, check if the found key is in the range. */
9621
if ( !(cur_range->flag & NO_MAX_RANGE) )
9623
/* Compose the MAX key for the range. */
9625
max_key.append(group_prefix, real_prefix_len);
9626
max_key.append(cur_range->max_key, cur_range->max_length);
9627
/* Compare the found key with max_key. */
9628
int cmp_res= key_cmp(index_info->key_part,
9630
real_prefix_len + min_max_arg_len);
9631
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9633
result= HA_ERR_KEY_NOT_FOUND;
9637
/* If we got to this point, the current key qualifies as MIN. */
9638
assert(result == 0);
9642
If there was a key with NULL in the MIN/MAX field, and there was no other
9643
key without NULL from the same group that satisfies some other condition,
9644
then use the key with the NULL.
9646
if (found_null && result)
9648
memcpy(record, tmp_record, head->s->rec_buff_length);
9656
Find the maximal key in a group that satisfies some range conditions for the
9657
min/max argument field.
9660
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9663
Given the sequence of ranges min_max_ranges, find the maximal key that is
9664
in the right-most possible range. If there is no such key, then the current
9665
group does not have a MAX key that satisfies the WHERE clause. If a key is
9666
found, its value is stored in this->record.
9670
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9672
HA_ERR_END_OF_FILE - "" -
9676
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9678
ha_rkey_function find_flag;
9679
key_part_map keypart_map;
9680
QUICK_RANGE *cur_range;
9682
basic_string<unsigned char> min_key;
9683
min_key.reserve(real_prefix_len + min_max_arg_len);
9685
assert(min_max_ranges.elements > 0);
9687
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9688
{ /* Search from the right-most range to the left. */
9689
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9692
If the current value for the min/max argument is smaller than the left
9693
boundary of cur_range, there is no need to check this range.
9695
if (range_idx != min_max_ranges.elements &&
9696
!(cur_range->flag & NO_MIN_RANGE) &&
9697
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9698
min_max_arg_len) == -1))
9701
if (cur_range->flag & NO_MAX_RANGE)
9703
keypart_map= make_prev_keypart_map(real_key_parts);
9704
find_flag= HA_READ_PREFIX_LAST;
9708
/* Extend the search key with the upper boundary for this range. */
9709
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9710
cur_range->max_length);
9711
keypart_map= make_keypart_map(real_key_parts);
9712
find_flag= (cur_range->flag & EQ_RANGE) ?
9713
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9714
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9717
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9721
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9722
(cur_range->flag & EQ_RANGE))
9723
continue; /* Check the next range. */
9726
In no key was found with this upper bound, there certainly are no keys
9727
in the ranges to the left.
9731
/* A key was found. */
9732
if (cur_range->flag & EQ_RANGE)
9733
return 0; /* No need to perform the checks below for equal keys. */
9735
/* Check if record belongs to the current group. */
9736
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9737
continue; // Row not found
9739
/* If there is a lower limit, check if the found key is in the range. */
9740
if ( !(cur_range->flag & NO_MIN_RANGE) )
9742
/* Compose the MIN key for the range. */
9744
min_key.append(group_prefix, real_prefix_len);
9745
min_key.append(cur_range->min_key, cur_range->min_length);
9747
/* Compare the found key with min_key. */
9748
int cmp_res= key_cmp(index_info->key_part,
9750
real_prefix_len + min_max_arg_len);
9751
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9755
/* If we got to this point, the current key qualifies as MAX. */
9758
return HA_ERR_KEY_NOT_FOUND;
9763
Update all MIN function results with the newly found value.
9766
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9769
The method iterates through all MIN functions and updates the result value
9770
of each function by calling Item_sum::reset(), which in turn picks the new
9771
result value from this->head->record[0], previously updated by
9772
next_min(). The updated value is stored in a member variable of each of the
9773
Item_sum objects, depending on the value type.
9776
The update must be done separately for MIN and MAX, immediately after
9777
next_min() was called and before next_max() is called, because both MIN and
9778
MAX take their result value from the same buffer this->head->record[0]
9779
(i.e. this->record).
9785
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9789
min_functions_it->rewind();
9790
while ((min_func= (*min_functions_it)++))
9796
Update all MAX function results with the newly found value.
9799
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9802
The method iterates through all MAX functions and updates the result value
9803
of each function by calling Item_sum::reset(), which in turn picks the new
9804
result value from this->head->record[0], previously updated by
9805
next_max(). The updated value is stored in a member variable of each of the
9806
Item_sum objects, depending on the value type.
9809
The update must be done separately for MIN and MAX, immediately after
9810
next_max() was called, because both MIN and MAX take their result value
9811
from the same buffer this->head->record[0] (i.e. this->record).
9817
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9821
max_functions_it->rewind();
9822
while ((max_func= (*max_functions_it)++))
9828
Append comma-separated list of keys this quick select uses to key_names;
9829
append comma-separated list of corresponding used lengths to used_lengths.
9832
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9833
key_names [out] Names of used indexes
9834
used_lengths [out] Corresponding lengths of the index names
9837
This method is used by select_describe to extract the names of the
9838
indexes used by a quick select.
9842
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9843
String *used_lengths)
9847
key_names->append(index_info->name);
9848
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9849
used_lengths->append(buf, length);
9852
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9854
SEL_ARG **key,**end;
9858
String tmp(buff,sizeof(buff),&my_charset_bin);
9860
for (idx= 0,key=tree->keys, end=key+param->keys ;
9864
if (tree_map->is_set(idx))
9866
uint32_t keynr= param->real_keynr[idx];
9869
tmp.append(param->table->key_info[keynr].name);
9873
tmp.append(STRING_WITH_LEN("(empty)"));
9877
static void print_ror_scans_arr(Table *table,
9878
const char *, struct st_ror_scan_info **start,
9879
struct st_ror_scan_info **end)
9882
String tmp(buff,sizeof(buff),&my_charset_bin);
9884
for (;start != end; start++)
9888
tmp.append(table->key_info[(*start)->keynr].name);
9891
tmp.append(STRING_WITH_LEN("(empty)"));
9894
/*****************************************************************************
9895
** Instantiate templates
9896
*****************************************************************************/
9898
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9899
template class List<QUICK_RANGE>;
9900
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
