152
127
return static_cast<ha_rows>(x);
130
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
155
132
static unsigned char is_null_string[2]= {1,0};
159
Get cost of reading nrows table records in a "disk sweep"
161
A disk sweep read is a sequence of Cursor->rnd_pos(rowid) calls that made
162
for an ordered sequence of rowids.
164
We assume hard disk IO. The read is performed as follows:
166
1. The disk head is moved to the needed cylinder
167
2. The controller waits for the plate to rotate
168
3. The data is transferred
170
Time to do #3 is insignificant compared to #2+#1.
172
Time to move the disk head is proportional to head travel distance.
174
Time to wait for the plate to rotate depends on whether the disk head
177
If disk head wasn't moved, the wait time is proportional to distance
178
between the previous block and the block we're reading.
180
If the head was moved, we don't know how much we'll need to wait for the
181
plate to rotate. We assume the wait time to be a variate with a mean of
182
0.5 of full rotation time.
184
Our cost units are "random disk seeks". The cost of random disk seek is
185
actually not a constant, it depends one range of cylinders we're going
186
to access. We make it constant by introducing a fuzzy concept of "typical
187
datafile length" (it's fuzzy as it's hard to tell whether it should
188
include index cursor, temp.tables etc). Then random seek cost is:
190
1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length
192
We define half_rotation_cost as DISK_SEEK_BASE_COST=0.9.
194
@param table Table to be accessed
195
@param nrows Number of rows to retrieve
196
@param interrupted true <=> Assume that the disk sweep will be
197
interrupted by other disk IO. false - otherwise.
198
@param cost OUT The cost.
134
class RANGE_OPT_PARAM;
136
A construction block of the SEL_ARG-graph.
138
The following description only covers graphs of SEL_ARG objects with
139
sel_arg->type==KEY_RANGE:
141
One SEL_ARG object represents an "elementary interval" in form
143
min_value <=? table.keypartX <=? max_value
145
The interval is a non-empty interval of any kind: with[out] minimum/maximum
146
bound, [half]open/closed, single-point interval, etc.
148
1. SEL_ARG GRAPH STRUCTURE
150
SEL_ARG objects are linked together in a graph. The meaning of the graph
151
is better demostrated by an example:
156
| part=1 $ part=2 $ part=3
158
| +-------+ $ +-------+ $ +--------+
159
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
160
| +-------+ $ +-------+ $ +--------+
166
\->| kp1=2 |--$--------------$-+
167
+-------+ $ $ | +--------+
169
+-------+ $ $ | +--------+
170
| kp1=3 |--$--------------$-+ |
171
+-------+ $ $ +--------+
175
The entire graph is partitioned into "interval lists".
177
An interval list is a sequence of ordered disjoint intervals over the same
178
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
179
all intervals in the list form an RB-tree, linked via left/right/parent
180
pointers. The RB-tree root SEL_ARG object will be further called "root of the
183
In the example pic, there are 4 interval lists:
184
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
185
The vertical lines represent SEL_ARG::next/prev pointers.
187
In an interval list, each member X may have SEL_ARG::next_key_part pointer
188
pointing to the root of another interval list Y. The pointed interval list
189
must cover a key part with greater number (i.e. Y->part > X->part).
191
In the example pic, the next_key_part pointers are represented by
194
2. SEL_ARG GRAPH SEMANTICS
196
It represents a condition in a special form (we don't have a name for it ATM)
197
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
199
For example, the picture represents the condition in form:
200
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
201
(kp1=2 AND (kp3=11 OR kp3=14)) OR
202
(kp1=3 AND (kp3=11 OR kp3=14))
207
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
208
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
209
intervals (i.e. intervals in form
211
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
213
Those intervals can be used to access the index. The uses are in:
214
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
215
how many table records are contained within all
217
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
218
and create QUICK_RANGE_SELECT object that will
219
read records within these intervals.
221
4. SPACE COMPLEXITY NOTES
223
SEL_ARG graph is a representation of an ordered disjoint sequence of
224
intervals over the ordered set of index tuple values.
226
For multi-part keys, one can construct a WHERE expression such that its
227
list of intervals will be of combinatorial size. Here is an example:
229
(keypart1 IN (1,2, ..., n1)) AND
230
(keypart2 IN (1,2, ..., n2)) AND
231
(keypart3 IN (1,2, ..., n3))
233
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
236
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
238
SEL_ARG graph structure aims to reduce the amount of required space by
239
"sharing" the elementary intervals when possible (the pic at the
240
beginning of this comment has examples of such sharing). The sharing may
241
prevent combinatorial blowup:
243
There are WHERE clauses that have combinatorial-size interval lists but
244
will be represented by a compact SEL_ARG graph.
246
(keypartN IN (1,2, ..., n1)) AND
248
(keypart2 IN (1,2, ..., n2)) AND
249
(keypart1 IN (1,2, ..., n3))
251
but not in all cases:
253
- There are WHERE clauses that do have a compact SEL_ARG-graph
254
representation but get_mm_tree() and its callees will construct a
255
graph of combinatorial size.
257
(keypart1 IN (1,2, ..., n1)) AND
258
(keypart2 IN (1,2, ..., n2)) AND
260
(keypartN IN (1,2, ..., n3))
262
- There are WHERE clauses for which the minimal possible SEL_ARG graph
263
representation will have combinatorial size.
265
By induction: Let's take any interval on some keypart in the middle:
269
Then let's AND it with this interval 'structure' from preceding and
272
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
274
We will obtain this SEL_ARG graph:
278
+---------+ $ +---------+ $ +---------+
279
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
280
+---------+ $ +---------+ $ +---------+
282
+---------+ $ +---------+ $
283
| kp14=c2 |--$-->| kp15=c0 | $
284
+---------+ $ +---------+ $
287
Note that we had to duplicate "kp15=c0" and there was no way to avoid
289
The induction step: AND the obtained expression with another "wrapping"
291
When the process ends because of the limit on max. number of keyparts
294
WHERE clause length is O(3*#max_keyparts)
295
SEL_ARG graph size is O(2^(#max_keyparts/2))
297
(it is also possible to construct a case where instead of 2 in 2^n we
298
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
301
We avoid consuming too much memory by setting a limit on the number of
302
SEL_ARG object we can construct during one range analysis invocation.
201
static void get_sweep_read_cost(Table *table,
204
optimizer::CostVector *cost)
207
if (table->cursor->primary_key_is_clustered())
209
cost->setIOCount(table->cursor->read_time(table->s->primary_key,
210
static_cast<uint32_t>(nrows),
216
ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);
218
n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));
219
if (busy_blocks < 1.0)
222
cost->setIOCount(busy_blocks);
226
/* Assume reading is done in one 'sweep' */
227
cost->setAvgIOCost((DISK_SEEK_BASE_COST +
228
DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
305
class SEL_ARG :public Sql_alloc
308
uint8_t min_flag,max_flag,maybe_flag;
309
uint8_t part; // Which key part
312
Number of children of this element in the RB-tree, plus 1 for this
317
Valid only for elements which are RB-tree roots: Number of times this
318
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
319
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
324
unsigned char *min_value,*max_value; // Pointer to range
327
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
329
SEL_ARG *left,*right; /* R-B tree children */
330
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
331
SEL_ARG *parent; /* R-B tree parent */
332
SEL_ARG *next_key_part;
333
enum leaf_color { BLACK,RED } color;
334
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
336
enum { MAX_SEL_ARGS = 16000 };
340
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
341
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
342
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
343
SEL_ARG(enum Type type_arg)
344
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
345
color(BLACK), type(type_arg)
347
inline bool is_same(SEL_ARG *arg)
349
if (type != arg->type || part != arg->part)
351
if (type != KEY_RANGE)
353
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
355
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
356
inline void maybe_smaller() { maybe_flag=1; }
357
/* Return true iff it's a single-point null interval */
358
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
359
inline int cmp_min_to_min(SEL_ARG* arg)
361
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
363
inline int cmp_min_to_max(SEL_ARG* arg)
365
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
367
inline int cmp_max_to_max(SEL_ARG* arg)
369
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
371
inline int cmp_max_to_min(SEL_ARG* arg)
373
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
375
SEL_ARG *clone_and(SEL_ARG* arg)
376
{ // Get overlapping range
377
unsigned char *new_min,*new_max;
378
uint8_t flag_min,flag_max;
379
if (cmp_min_to_min(arg) >= 0)
381
new_min=min_value; flag_min=min_flag;
385
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
387
if (cmp_max_to_max(arg) <= 0)
389
new_max=max_value; flag_max=max_flag;
393
new_max=arg->max_value; flag_max=arg->max_flag;
395
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
396
test(maybe_flag && arg->maybe_flag));
398
SEL_ARG *clone_first(SEL_ARG *arg)
399
{ // min <= X < arg->min
400
return new SEL_ARG(field,part, min_value, arg->min_value,
401
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
402
maybe_flag | arg->maybe_flag);
404
SEL_ARG *clone_last(SEL_ARG *arg)
405
{ // min <= X <= key_max
406
return new SEL_ARG(field, part, min_value, arg->max_value,
407
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
409
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
411
bool copy_min(SEL_ARG* arg)
412
{ // Get overlapping range
413
if (cmp_min_to_min(arg) > 0)
415
min_value=arg->min_value; min_flag=arg->min_flag;
416
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
417
(NO_MAX_RANGE | NO_MIN_RANGE))
418
return 1; // Full range
420
maybe_flag|=arg->maybe_flag;
423
bool copy_max(SEL_ARG* arg)
424
{ // Get overlapping range
425
if (cmp_max_to_max(arg) <= 0)
427
max_value=arg->max_value; max_flag=arg->max_flag;
428
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
429
(NO_MAX_RANGE | NO_MIN_RANGE))
430
return 1; // Full range
432
maybe_flag|=arg->maybe_flag;
436
void copy_min_to_min(SEL_ARG *arg)
438
min_value=arg->min_value; min_flag=arg->min_flag;
440
void copy_min_to_max(SEL_ARG *arg)
442
max_value=arg->min_value;
443
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
445
void copy_max_to_min(SEL_ARG *arg)
447
min_value=arg->max_value;
448
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
450
/* returns a number of keypart values (0 or 1) appended to the key buffer */
451
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
453
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
454
if ((!(min_flag & NO_MIN_RANGE) &&
455
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
457
if (maybe_null && *min_value)
460
memset(*min_key+1, 0, length-1);
463
memcpy(*min_key,min_value,length);
469
/* returns a number of keypart values (0 or 1) appended to the key buffer */
470
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
472
if (!(max_flag & NO_MAX_RANGE) &&
473
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
475
if (maybe_null && *max_value)
478
memset(*max_key+1, 0, length-1);
481
memcpy(*max_key,max_value,length);
488
/* returns a number of keypart values appended to the key buffer */
489
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
491
SEL_ARG *key_tree= first();
492
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
493
range_key, *range_key_flag);
494
*range_key_flag|= key_tree->min_flag;
496
if (key_tree->next_key_part &&
497
key_tree->next_key_part->part == key_tree->part+1 &&
498
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
499
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
500
res+= key_tree->next_key_part->store_min_key(key, range_key,
505
/* returns a number of keypart values appended to the key buffer */
506
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
508
SEL_ARG *key_tree= last();
509
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
510
range_key, *range_key_flag);
511
(*range_key_flag)|= key_tree->max_flag;
512
if (key_tree->next_key_part &&
513
key_tree->next_key_part->part == key_tree->part+1 &&
514
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
515
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
516
res+= key_tree->next_key_part->store_max_key(key, range_key,
521
SEL_ARG *insert(SEL_ARG *key);
522
SEL_ARG *tree_delete(SEL_ARG *key);
523
SEL_ARG *find_range(SEL_ARG *key);
524
SEL_ARG *rb_insert(SEL_ARG *leaf);
525
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
527
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
528
void test_use_count(SEL_ARG *root);
533
inline bool simple_key()
535
return !next_key_part && elements == 1;
537
void increment_use_count(long count)
541
next_key_part->use_count+=count;
542
count*= (next_key_part->use_count-count);
543
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
544
if (pos->next_key_part)
545
pos->increment_use_count(count);
550
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
551
if (pos->next_key_part)
553
pos->next_key_part->use_count--;
554
pos->next_key_part->free_tree();
558
inline SEL_ARG **parent_ptr()
560
return parent->left == this ? &parent->left : &parent->right;
565
Check if this SEL_ARG object represents a single-point interval
571
Check if this SEL_ARG object (not tree) represents a single-point
572
interval, i.e. if it represents a "keypart = const" or
576
true This SEL_ARG object represents a singlepoint interval
580
bool is_singlepoint()
583
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
584
flags, and the same for right edge.
586
if (min_flag || max_flag)
588
unsigned char *min_val= min_value;
589
unsigned char *max_val= max_value;
593
/* First byte is a NULL value indicator */
594
if (*min_val != *max_val)
598
return true; /* This "x IS NULL" */
602
return !field->key_cmp(min_val, max_val);
604
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
610
class SEL_TREE :public Sql_alloc
614
Starting an effort to document this field:
615
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
616
(type == SEL_TREE::IMPOSSIBLE)
618
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
619
SEL_TREE(enum Type type_arg) :type(type_arg) {}
620
SEL_TREE() :type(KEY)
622
keys_map.clear_all();
623
memset(keys, 0, sizeof(keys));
626
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
627
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
628
merit in range analyzer functions (e.g. get_mm_parts) returning a
629
pointer to such SEL_TREE instead of NULL)
631
SEL_ARG *keys[MAX_KEY];
632
key_map keys_map; /* bitmask of non-NULL elements in keys */
635
Possible ways to read rows using index_merge. The list is non-empty only
636
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
638
List<SEL_IMERGE> merges;
640
/* The members below are filled/used only after get_mm_tree is done */
641
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
642
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
644
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
645
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
646
/* Note that #records for each key scan is stored in table->quick_rows */
649
class RANGE_OPT_PARAM
652
Session *session; /* Current thread handle */
653
Table *table; /* Table being analyzed */
654
COND *cond; /* Used inside get_mm_tree(). */
655
table_map prev_tables;
656
table_map read_tables;
657
table_map current_table; /* Bit of the table being analyzed */
659
/* Array of parts of all keys for which range analysis is performed */
661
KEY_PART *key_parts_end;
662
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
663
MEM_ROOT *old_root; /* Memory that will last until the query end */
665
Number of indexes used in range analysis (In SEL_TREE::keys only first
666
#keys elements are not empty)
671
If true, the index descriptions describe real indexes (and it is ok to
672
call field->optimize_range(real_keynr[...], ...).
673
Otherwise index description describes fake indexes.
675
bool using_real_indexes;
677
bool remove_jump_scans;
680
used_key_no -> table_key_no translation table. Only makes sense if
681
using_real_indexes==true
683
uint32_t real_keynr[MAX_KEY];
684
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
685
uint32_t alloced_sel_args;
686
bool force_default_mrr;
689
class PARAM : public RANGE_OPT_PARAM
692
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
694
uint32_t max_key_part;
695
/* Number of ranges in the last checked tree->key */
696
uint32_t range_count;
697
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
698
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
699
bool quick; // Don't calulate possible keys
701
uint32_t fields_bitmap_size;
702
bitset<MAX_FIELDS> needed_fields; /* bitmask of fields needed by the query */
703
bitset<MAX_FIELDS> tmp_covered_fields;
705
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
707
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
708
uint32_t imerge_cost_buff_size; /* size of the buffer */
710
/* true if last checked tree->key can be used for ROR-scan */
712
/* Number of ranges in the last checked tree->key */
716
class TABLE_READ_PLAN;
718
class TRP_ROR_INTERSECT;
720
class TRP_ROR_INDEX_MERGE;
721
class TRP_GROUP_MIN_MAX;
233
723
struct st_ror_scan_info;
235
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
238
Item_func::Functype type,
240
Item_result cmp_type);
242
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
246
Item_func::Functype type,
249
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
251
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
253
static ha_rows check_quick_select(optimizer::Parameter *param,
256
optimizer::SEL_ARG *tree,
257
bool update_tbl_stats,
260
optimizer::CostVector *cost);
262
static optimizer::RangeReadPlan *get_key_scans_params(optimizer::Parameter *param,
263
optimizer::SEL_TREE *tree,
264
bool index_read_must_be_used,
265
bool update_tbl_stats,
269
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
270
optimizer::SEL_TREE *tree,
272
bool *are_all_covering);
275
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
276
optimizer::SEL_TREE *tree,
280
optimizer::TableReadPlan *get_best_disjunct_quick(optimizer::Parameter *param,
281
optimizer::SEL_IMERGE *imerge,
285
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
287
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
288
optimizer::SEL_TREE *tree1,
289
optimizer::SEL_TREE *tree2);
291
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
293
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
294
optimizer::SEL_ARG *key1,
295
optimizer::SEL_ARG *key2,
296
uint32_t clone_flag);
298
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
300
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
302
static bool null_part_in_key(KEY_PART *key_part,
303
const unsigned char *key,
725
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
726
Item_func::Functype type,Item *value,
727
Item_result cmp_type);
728
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
730
Item_func::Functype type,Item *value);
731
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
733
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
734
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
735
SEL_ARG *tree, bool update_tbl_stats,
736
uint32_t *mrr_flags, uint32_t *bufsize,
738
//bool update_tbl_stats);
739
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
740
unsigned char *min_key, uint32_t min_key_flag, int,
741
unsigned char *max_key, uint32_t max_key_flag, int);
744
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
745
SEL_ARG *key_tree, uint32_t mrr_flags,
746
uint32_t mrr_buf_size, MEM_ROOT *alloc);
747
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
748
bool index_read_must_be_used,
749
bool update_tbl_stats,
752
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
754
bool *are_all_covering);
756
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
760
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
763
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
765
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
767
static void print_ror_scans_arr(Table *table, const char *msg,
768
struct st_ror_scan_info **start,
769
struct st_ror_scan_info **end);
771
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
772
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
773
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
774
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
775
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
776
uint32_t clone_flag);
777
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
778
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
779
SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
780
unsigned char *max_key,uint32_t max_key_flag);
781
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
783
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
784
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
304
785
uint32_t length);
306
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
307
optimizer::SEL_TREE *tree2,
308
optimizer::RangeParameter *param);
786
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
790
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
791
a condition in the following form:
792
(t_1||t_2||...||t_N) && (next)
794
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
795
(t_i,t_j) contains SEL_ARGS for the same index.
797
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
799
This class relies on memory manager to do the cleanup.
802
class SEL_IMERGE : public Sql_alloc
804
enum { PREALLOCED_TREES= 10};
806
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
807
SEL_TREE **trees; /* trees used to do index_merge */
808
SEL_TREE **trees_next; /* last of these trees */
809
SEL_TREE **trees_end; /* end of allocated space */
811
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
814
trees(&trees_prealloced[0]),
816
trees_end(trees + PREALLOCED_TREES)
818
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
819
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
820
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
825
Add SEL_TREE to this index_merge without any checks,
828
This function implements the following:
829
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
836
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
838
if (trees_next == trees_end)
840
const int realloc_ratio= 2; /* Double size for next round */
841
uint32_t old_elements= (trees_end - trees);
842
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
843
uint32_t new_size= old_size * realloc_ratio;
844
SEL_TREE **new_trees;
845
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
847
memcpy(new_trees, trees, old_size);
849
trees_next= trees + old_elements;
850
trees_end= trees + old_elements * realloc_ratio;
852
*(trees_next++)= tree;
858
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
859
combining new_tree with one of the trees in this SEL_IMERGE if they both
860
have SEL_ARGs for the same key.
863
or_sel_tree_with_checks()
864
param PARAM from SQL_SELECT::test_quick_select
865
new_tree SEL_TREE with type KEY or KEY_SMALLER.
868
This does the following:
869
(t_1||...||t_k)||new_tree =
871
= (t_1||...||t_k||new_tree)
873
= (t_1||....||(t_j|| new_tree)||...||t_k),
875
where t_i, y are SEL_TREEs.
876
new_tree is combined with the first t_j it has a SEL_ARG on common
877
key with. As a consequence of this, choice of keys to do index_merge
878
read may depend on the order of conditions in WHERE part of the query.
882
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
883
and (*this) should be discarded.
884
-1 An error occurred.
887
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
889
for (SEL_TREE** tree = trees;
893
if (sel_trees_can_be_ored(*tree, new_tree, param))
895
*tree = tree_or(param, *tree, new_tree);
898
if (((*tree)->type == SEL_TREE::MAYBE) ||
899
((*tree)->type == SEL_TREE::ALWAYS))
901
/* SEL_TREE::IMPOSSIBLE is impossible here */
906
/* New tree cannot be combined with any of existing trees. */
907
return or_sel_tree(param, new_tree);
912
Perform OR operation on this index_merge and supplied index_merge list.
916
1 - One of conditions in result is always true and this SEL_IMERGE
918
-1 - An error occurred
921
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
923
for (SEL_TREE** tree= imerge->trees;
924
tree != imerge->trees_next;
927
if (or_sel_tree_with_checks(param, *tree))
316
935
Perform AND operation on two index_merge lists and store result in *im1.
319
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
938
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
321
940
im1->concat(im2);
945
Perform OR operation on 2 index_merge lists, storing result in first list.
948
The following conversion is implemented:
949
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
952
i.e. all conjuncts except the first one are currently dropped.
953
This is done to avoid producing N*K ways to do index_merge.
955
If (a_1||b_1) produce a condition that is always true, NULL is returned
956
and index_merge is discarded (while it is actually possible to try
959
As a consequence of this, choice of keys to do index_merge read may depend
960
on the order of conditions in WHERE part of the query.
963
0 OK, result is stored in *im1
964
other Error, both passed lists are unusable
967
int imerge_list_or_list(RANGE_OPT_PARAM *param,
968
List<SEL_IMERGE> *im1,
969
List<SEL_IMERGE> *im2)
971
SEL_IMERGE *imerge= im1->head();
973
im1->push_back(imerge);
975
return imerge->or_sel_imerge_with_checks(param, im2->head());
980
Perform OR operation on index_merge list and key tree.
983
0 OK, result is stored in *im1.
987
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
988
List<SEL_IMERGE> *im1,
992
List_iterator<SEL_IMERGE> it(*im1);
993
while ((imerge= it++))
995
if (imerge->or_sel_tree_with_checks(param, tree))
998
return im1->is_empty();
325
1002
/***************************************************************************
326
** Basic functions for SqlSelect and QuickRangeSelect
1003
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
327
1004
***************************************************************************/
329
1006
/* make a select from mysql info
372
optimizer::SqlSelect::SqlSelect()
376
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1045
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1047
quick_keys.clear_all(); needed_reg.clear_all();
385
void optimizer::SqlSelect::cleanup()
1052
void SQL_SELECT::cleanup()
395
close_cached_file(file);
1062
close_cached_file(&file);
399
optimizer::SqlSelect::~SqlSelect()
1066
SQL_SELECT::~SQL_SELECT()
405
bool optimizer::SqlSelect::check_quick(Session *session,
406
bool force_quick_range,
1072
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
411
return (test_quick_select(session,
420
bool optimizer::SqlSelect::skip_record()
422
return (cond ? cond->val_int() == 0 : 0);
426
optimizer::QuickSelectInterface::QuickSelectInterface()
428
max_used_key_length(0),
1077
return test_quick_select(session, tmp, 0, limit,
1078
force_quick_range, false) < 0;
1082
bool SQL_SELECT::skip_record()
1084
return cond ? cond->val_int() == 0 : 0;
1088
QUICK_SELECT_I::QUICK_SELECT_I()
1089
:max_used_key_length(0),
1093
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1094
bool no_alloc, MEM_ROOT *parent_alloc)
1095
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1097
in_ror_merged_scan= 0;
1101
key_part_info= head->key_info[index].key_part;
1102
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1104
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1105
mrr_buf_size= session->variables.read_rnd_buff_size;
1108
if (!no_alloc && !parent_alloc)
1110
// Allocates everything through the internal memroot
1111
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1112
session->mem_root= &alloc;
1115
memset(&alloc, 0, sizeof(alloc));
1117
record= head->record[0];
1118
save_read_set= head->read_set;
1119
save_write_set= head->write_set;
1125
int QUICK_RANGE_SELECT::init()
1127
if (file->inited != handler::NONE)
1128
file->ha_index_or_rnd_end();
1129
return(file->ha_index_init(index, 1));
1133
void QUICK_RANGE_SELECT::range_end()
1135
if (file->inited != handler::NONE)
1136
file->ha_index_or_rnd_end();
1140
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1144
/* file is NULL for CPK scan on covering ROR-intersection */
1151
file->extra(HA_EXTRA_NO_KEYREAD);
1155
file->ha_external_lock(current_session, F_UNLCK);
1160
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1161
free_root(&alloc,MYF(0));
1163
head->column_bitmaps_set(save_read_set, save_write_set);
1170
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1172
:pk_quick_select(NULL), session(session_param)
1176
memset(&read_record, 0, sizeof(read_record));
1177
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1181
int QUICK_INDEX_MERGE_SELECT::init()
1186
int QUICK_INDEX_MERGE_SELECT::reset()
1188
return(read_keys_and_merge());
1192
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1195
Save quick_select that does scan on clustered primary key as it will be
1196
processed separately.
1198
if (head->file->primary_key_is_clustered() &&
1199
quick_sel_range->index == head->s->primary_key)
1200
pk_quick_select= quick_sel_range;
1202
return quick_selects.push_back(quick_sel_range);
1206
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1208
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1209
QUICK_RANGE_SELECT* quick;
1211
while ((quick= quick_it++))
1213
quick_selects.delete_elements();
1214
delete pk_quick_select;
1215
free_root(&alloc,MYF(0));
1220
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1222
bool retrieve_full_rows,
1223
MEM_ROOT *parent_alloc)
1224
: cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1229
record= head->record[0];
1231
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1233
memset(&alloc, 0, sizeof(MEM_ROOT));
1234
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1235
head->file->ref_length);
1240
Do post-constructor initialization.
1242
QUICK_ROR_INTERSECT_SELECT::init()
1249
int QUICK_ROR_INTERSECT_SELECT::init()
1251
/* Check if last_rowid was successfully allocated in ctor */
1252
return(!last_rowid);
1257
Initialize this quick select to be a ROR-merged scan.
1260
QUICK_RANGE_SELECT::init_ror_merged_scan()
1261
reuse_handler If true, use head->file, otherwise create a separate
1265
This function creates and prepares for subsequent use a separate handler
1266
object if it can't reuse head->file. The reason for this is that during
1267
ROR-merge several key scans are performed simultaneously, and a single
1268
handler is only capable of preserving context of a single key scan.
1270
In ROR-merge the quick select doing merge does full records retrieval,
1271
merged quick selects read only keys.
1274
0 ROR child scan initialized, ok to use.
1278
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1280
handler *save_file= file, *org_file;
1283
in_ror_merged_scan= 1;
1286
if (init() || reset())
1290
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1294
/* Create a separate handler object for this quick select */
1297
/* already have own 'handler' object. */
1301
session= head->in_use;
1302
if (!(file= head->file->clone(session->mem_root)))
1305
Manually set the error flag. Note: there seems to be quite a few
1306
places where a failure could cause the server to "hang" the client by
1307
sending no response to a query. ATM those are not real errors because
1308
the storage engine calls in question happen to never fail with the
1309
existing storage engines.
1311
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1312
/* Caller will free the memory */
1313
goto failure; /* purecov: inspected */
1316
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1318
if (file->ha_external_lock(session, F_RDLCK))
1321
if (init() || reset())
1323
file->ha_external_lock(session, F_UNLCK);
1328
last_rowid= file->ref;
1332
We are only going to read key fields and call position() on 'file'
1333
The following sets head->tmp_set to only use this key and then updates
1334
head->read_set and head->write_set to use this bitmap.
1335
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1337
org_file= head->file;
1339
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1340
if (!head->no_keyread)
1343
head->mark_columns_used_by_index(index);
1345
head->prepare_for_position();
1346
head->file= org_file;
1347
column_bitmap= *(head->read_set);
1348
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1353
head->column_bitmaps_set(save_read_set, save_write_set);
1360
void QUICK_RANGE_SELECT::save_last_pos()
1362
file->position(record);
1367
Initialize this quick select to be a part of a ROR-merged scan.
1369
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1370
reuse_handler If true, use head->file, otherwise create separate
1376
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1378
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1379
QUICK_RANGE_SELECT* quick;
1381
/* Initialize all merged "children" quick selects */
1382
assert(!need_to_fetch_row || reuse_handler);
1383
if (!need_to_fetch_row && reuse_handler)
1387
There is no use of this->file. Use it for the first of merged range
1390
if (quick->init_ror_merged_scan(true))
1392
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1394
while ((quick= quick_it++))
1396
if (quick->init_ror_merged_scan(false))
1398
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1399
/* All merged scans share the same record buffer in intersection. */
1400
quick->record= head->record[0];
1403
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1412
Initialize quick select for row retrieval.
1420
int QUICK_ROR_INTERSECT_SELECT::reset()
1422
if (!scans_inited && init_ror_merged_scan(true))
1425
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1426
QUICK_RANGE_SELECT *quick;
1427
while ((quick= it++))
1434
Add a merged quick select to this ROR-intersection quick select.
1437
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1438
quick Quick select to be added. The quick select must return
1439
rows in rowid order.
1441
This call can only be made before init() is called.
1449
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1451
return quick_selects.push_back(quick);
1454
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1456
quick_selects.delete_elements();
1458
free_root(&alloc,MYF(0));
1459
if (need_to_fetch_row && head->file->inited != handler::NONE)
1460
head->file->ha_rnd_end();
1465
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1467
: session(session_param), scans_inited(false)
1471
rowid_length= table->file->ref_length;
1472
record= head->record[0];
1473
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1474
session_param->mem_root= &alloc;
1478
* Function object that is used as the comparison function
1479
* for the priority queue in the QUICK_ROR_UNION_SELECT
1482
class compare_functor
1484
QUICK_ROR_UNION_SELECT *self;
1486
compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
1488
inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
1490
int val= self->head->file->cmp_ref(i->last_rowid,
1497
Do post-constructor initialization.
1499
QUICK_ROR_UNION_SELECT::init()
1506
int QUICK_ROR_UNION_SELECT::init()
1509
new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
1510
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1512
prev_rowid= cur_rowid + head->file->ref_length;
1518
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1522
QUICK_ROR_UNION_SELECT::queue_cmp()
1523
arg Pointer to QUICK_ROR_UNION_SELECT
1524
val1 First merged select
1525
val2 Second merged select
1528
int quick_ror_union_select_queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1530
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1531
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1532
((QUICK_SELECT_I*)val2)->last_rowid);
1537
Initialize quick select for row retrieval.
1546
int QUICK_ROR_UNION_SELECT::reset()
1548
QUICK_SELECT_I *quick;
1550
have_prev_rowid= false;
1553
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1554
while ((quick= it++))
1556
if (quick->init_ror_merged_scan(false))
1561
while (!queue->empty())
1564
Initialize scans for merged quick selects and put all merged quick
1565
selects into the queue.
1567
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1568
while ((quick= it++))
1572
if ((error= quick->get_next()))
1574
if (error == HA_ERR_END_OF_FILE)
1578
quick->save_last_pos();
1582
if (head->file->ha_rnd_init(1))
1592
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1594
return quick_selects.push_back(quick_sel_range);
1597
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1599
while (!queue->empty())
1602
quick_selects.delete_elements();
1603
if (head->file->inited != handler::NONE)
1604
head->file->ha_rnd_end();
1605
free_root(&alloc,MYF(0));
1610
QUICK_RANGE::QUICK_RANGE()
1611
:min_key(0),max_key(0),min_length(0),max_length(0),
1612
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1613
min_keypart_map(0), max_keypart_map(0)
1616
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1619
min_flag=arg.min_flag;
1620
max_flag=arg.max_flag;
1621
maybe_flag=arg.maybe_flag;
1622
maybe_null=arg.maybe_null;
1625
min_value=arg.min_value;
1626
max_value=arg.max_value;
1627
next_key_part=arg.next_key_part;
1628
use_count=1; elements=1;
1632
inline void SEL_ARG::make_root()
1634
left=right= &null_element;
1637
use_count=0; elements=1;
1640
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1641
const unsigned char *max_value_arg)
1642
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1643
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1644
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1645
next_key_part(0),color(BLACK),type(KEY_RANGE)
1647
left=right= &null_element;
1650
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1651
unsigned char *min_value_, unsigned char *max_value_,
1652
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1653
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1654
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1655
field(field_), min_value(min_value_), max_value(max_value_),
1656
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1658
left=right= &null_element;
1661
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1666
/* Bail out if we have already generated too many SEL_ARGs */
1667
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1670
if (type != KEY_RANGE)
1672
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1673
return 0; // out of memory
1674
tmp->prev= *next_arg; // Link into next/prev chain
1675
(*next_arg)->next=tmp;
1680
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1681
min_flag, max_flag, maybe_flag)))
1683
tmp->parent=new_parent;
1684
tmp->next_key_part=next_key_part;
1685
if (left != &null_element)
1686
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1689
tmp->prev= *next_arg; // Link into next/prev chain
1690
(*next_arg)->next=tmp;
1693
if (right != &null_element)
1694
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1697
increment_use_count(1);
1699
tmp->elements= this->elements;
1703
SEL_ARG *SEL_ARG::first()
1705
SEL_ARG *next_arg=this;
1706
if (!next_arg->left)
1707
return 0; // MAYBE_KEY
1708
while (next_arg->left != &null_element)
1709
next_arg=next_arg->left;
1713
SEL_ARG *SEL_ARG::last()
1715
SEL_ARG *next_arg=this;
1716
if (!next_arg->right)
1717
return 0; // MAYBE_KEY
1718
while (next_arg->right != &null_element)
1719
next_arg=next_arg->right;
1725
Check if a compare is ok, when one takes ranges in account
1726
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1729
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1733
/* First check if there was a compare to a min or max element */
1734
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1736
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1737
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1739
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1741
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1742
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1744
if (field->real_maybe_null()) // If null is part of key
1751
goto end; // NULL where equal
1752
a++; b++; // Skip NULL marker
1754
cmp=field->key_cmp(a , b);
1755
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1757
// Check if the compared equal arguments was defined with open/closed range
1759
if (a_flag & (NEAR_MIN | NEAR_MAX))
1761
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1763
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1764
return (a_flag & NEAR_MIN) ? 2 : -2;
1765
return (a_flag & NEAR_MIN) ? 1 : -1;
1767
if (b_flag & (NEAR_MIN | NEAR_MAX))
1768
return (b_flag & NEAR_MIN) ? -2 : 2;
1769
return 0; // The elements where equal
1773
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1775
SEL_ARG tmp_link,*next_arg,*root;
1776
next_arg= &tmp_link;
1777
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1779
next_arg->next=0; // Fix last link
1780
tmp_link.next->prev=0; // Fix first link
1781
if (root) // If not OOM
5215
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5235
if (key1->part != key2->part)
5239
return 0; // Can't optimize this
5242
// If one of the key is MAYBE_KEY then the found region may be bigger
5243
if (key1->type == SEL_ARG::MAYBE_KEY)
5249
if (key2->type == SEL_ARG::MAYBE_KEY)
5256
if (key1->use_count > 0)
5258
if (key2->use_count == 0 || key1->elements > key2->elements)
5260
std::swap(key1,key2);
5262
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5266
// Add tree at key2 to tree at key1
5267
bool key2_shared=key2->use_count != 0;
5268
key1->maybe_flag|=key2->maybe_flag;
5270
for (key2=key2->first(); key2; )
5272
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5277
tmp=key1->first(); // tmp.min > key2.min
5280
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5281
{ // Found tmp.max < key2.min
5282
SEL_ARG *next=tmp->next;
5283
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5285
// Join near ranges like tmp.max < 0 and key2.min >= 0
5286
SEL_ARG *key2_next=key2->next;
5289
if (!(key2=new SEL_ARG(*key2)))
5290
return 0; // out of memory
5291
key2->increment_use_count(key1->use_count+1);
5292
key2->next=key2_next; // New copy of key2
5294
key2->copy_min(tmp);
5295
if (!(key1=key1->tree_delete(tmp)))
5296
{ // Only one key in tree
5303
if (!(tmp=next)) // tmp.min > key2.min
5304
break; // Copy rest of key2
5307
{ // tmp.min > key2.min
5309
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5311
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5312
{ // ranges are connected
5313
tmp->copy_min_to_min(key2);
5314
key1->merge_flags(key2);
5315
if (tmp->min_flag & NO_MIN_RANGE &&
5316
tmp->max_flag & NO_MAX_RANGE)
5318
if (key1->maybe_flag)
5319
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5322
key2->increment_use_count(-1); // Free not used tree
5328
SEL_ARG *next=key2->next; // Keys are not overlapping
5331
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5334
key1=key1->insert(cpy);
5335
key2->increment_use_count(key1->use_count+1);
5338
key1=key1->insert(key2); // Will destroy key2_root
5345
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5346
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5348
if (tmp->is_same(key2))
5350
tmp->merge_flags(key2); // Copy maybe flags
5351
key2->increment_use_count(-1); // Free not used tree
5356
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5357
eq_tree(last->next->next_key_part,key2->next_key_part))
5361
key1=key1->tree_delete(save);
5363
last->copy_min(tmp);
5364
if (last->copy_min(key2) || last->copy_max(key2))
5367
for (; key2 ; key2=key2->next)
5368
key2->increment_use_count(-1); // Free not used tree
5369
if (key1->maybe_flag)
5370
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5378
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5379
{ // tmp.min <= x < key2.min
5380
SEL_ARG *new_arg=tmp->clone_first(key2);
5383
if ((new_arg->next_key_part= key1->next_key_part))
5384
new_arg->increment_use_count(key1->use_count+1);
5385
tmp->copy_min_to_min(key2);
5386
key1=key1->insert(new_arg);
5389
// tmp.min >= key2.min && tmp.min <= key2.max
5390
SEL_ARG key(*key2); // Get copy we can modify
5393
if (tmp->cmp_min_to_min(&key) > 0)
5394
{ // key.min <= x < tmp.min
5395
SEL_ARG *new_arg=key.clone_first(tmp);
5398
if ((new_arg->next_key_part=key.next_key_part))
5399
new_arg->increment_use_count(key1->use_count+1);
5400
key1=key1->insert(new_arg);
5402
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5403
{ // tmp.min. <= x <= tmp.max
5404
tmp->maybe_flag|= key.maybe_flag;
5405
key.increment_use_count(key1->use_count+1);
5406
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5407
if (!cmp) // Key2 is ready
5409
key.copy_max_to_min(tmp);
5410
if (!(tmp=tmp->next))
5412
SEL_ARG *tmp2= new SEL_ARG(key);
5415
key1=key1->insert(tmp2);
5419
if (tmp->cmp_min_to_max(&key) > 0)
5421
SEL_ARG *tmp2= new SEL_ARG(key);
5424
key1=key1->insert(tmp2);
5430
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5433
tmp->copy_max_to_min(&key);
5434
tmp->increment_use_count(key1->use_count+1);
5435
/* Increment key count as it may be used for next loop */
5436
key.increment_use_count(1);
5437
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5438
key1=key1->insert(new_arg);
5448
SEL_ARG *next=key2->next;
5451
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5454
key2->increment_use_count(key1->use_count+1);
5455
key1=key1->insert(tmp);
5458
key1=key1->insert(key2); // Will destroy key2_root
5466
/* Compare if two trees are equal */
5468
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5472
if (!a || !b || !a->is_same(b))
5474
if (a->left != &null_element && b->left != &null_element)
5476
if (!eq_tree(a->left,b->left))
5479
else if (a->left != &null_element || b->left != &null_element)
5481
if (a->right != &null_element && b->right != &null_element)
5483
if (!eq_tree(a->right,b->right))
5486
else if (a->right != &null_element || b->right != &null_element)
5488
if (a->next_key_part != b->next_key_part)
5490
if (!a->next_key_part != !b->next_key_part ||
5491
!eq_tree(a->next_key_part, b->next_key_part))
5499
SEL_ARG::insert(SEL_ARG *key)
5501
SEL_ARG *element, **par= NULL, *last_element= NULL;
5503
for (element= this; element != &null_element ; )
5505
last_element=element;
5506
if (key->cmp_min_to_min(element) > 0)
5508
par= &element->right; element= element->right;
5512
par = &element->left; element= element->left;
5516
key->parent=last_element;
5518
if (par == &last_element->left)
5520
key->next=last_element;
5521
if ((key->prev=last_element->prev))
5522
key->prev->next=key;
5523
last_element->prev=key;
5527
if ((key->next=last_element->next))
5528
key->next->prev=key;
5529
key->prev=last_element;
5530
last_element->next=key;
5532
key->left=key->right= &null_element;
5533
SEL_ARG *root=rb_insert(key); // rebalance tree
5534
root->use_count=this->use_count; // copy root info
5535
root->elements= this->elements+1;
5536
root->maybe_flag=this->maybe_flag;
5542
** Find best key with min <= given key
5543
** Because the call context this should never return 0 to get_range
5547
SEL_ARG::find_range(SEL_ARG *key)
5549
SEL_ARG *element=this,*found=0;
5553
if (element == &null_element)
5555
int cmp=element->cmp_min_to_min(key);
5561
element=element->right;
5564
element=element->left;
5570
Remove a element from the tree
5574
key Key that is to be deleted from tree (this)
5577
This also frees all sub trees that is used by the element
5580
root of new tree (with key deleted)
5584
SEL_ARG::tree_delete(SEL_ARG *key)
5586
enum leaf_color remove_color;
5587
SEL_ARG *root,*nod,**par,*fix_par;
5592
/* Unlink from list */
5594
key->prev->next=key->next;
5596
key->next->prev=key->prev;
5597
key->increment_use_count(-1);
5601
par=key->parent_ptr();
5603
if (key->left == &null_element)
5605
*par=nod=key->right;
5606
fix_par=key->parent;
5607
if (nod != &null_element)
5608
nod->parent=fix_par;
5609
remove_color= key->color;
5611
else if (key->right == &null_element)
5613
*par= nod=key->left;
5614
nod->parent=fix_par=key->parent;
5615
remove_color= key->color;
5619
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5620
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5621
fix_par=tmp->parent;
5622
if (nod != &null_element)
5623
nod->parent=fix_par;
5624
remove_color= tmp->color;
5626
tmp->parent=key->parent; // Move node in place of key
5627
(tmp->left=key->left)->parent=tmp;
5628
if ((tmp->right=key->right) != &null_element)
5629
tmp->right->parent=tmp;
5630
tmp->color=key->color;
5632
if (fix_par == key) // key->right == key->next
5633
fix_par=tmp; // new parent of nod
5636
if (root == &null_element)
5637
return 0; // Maybe root later
5638
if (remove_color == BLACK)
5639
root=rb_delete_fixup(root,nod,fix_par);
5641
test_rb_tree(root,root->parent);
5642
#endif /* EXTRA_DEBUG */
5644
root->use_count=this->use_count; // Fix root counters
5645
root->elements=this->elements-1;
5646
root->maybe_flag=this->maybe_flag;
5651
/* Functions to fix up the tree after insert and delete */
5653
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5655
SEL_ARG *y=leaf->right;
5656
leaf->right=y->left;
5657
if (y->left != &null_element)
5658
y->left->parent=leaf;
5659
if (!(y->parent=leaf->parent))
5662
*leaf->parent_ptr()=y;
5667
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5669
SEL_ARG *y=leaf->left;
5670
leaf->left=y->right;
5671
if (y->right != &null_element)
5672
y->right->parent=leaf;
5673
if (!(y->parent=leaf->parent))
5676
*leaf->parent_ptr()=y;
5683
SEL_ARG::rb_insert(SEL_ARG *leaf)
5685
SEL_ARG *y,*par,*par2,*root;
5686
root= this; root->parent= 0;
5689
while (leaf != root && (par= leaf->parent)->color == RED)
5690
{ // This can't be root or 1 level under
5691
if (par == (par2= leaf->parent->parent)->left)
5694
if (y->color == RED)
5699
leaf->color=RED; /* And the loop continues */
5703
if (leaf == par->right)
5705
left_rotate(&root,leaf->parent);
5706
par=leaf; /* leaf is now parent to old leaf */
5710
right_rotate(&root,par2);
5717
if (y->color == RED)
5722
leaf->color=RED; /* And the loop continues */
5726
if (leaf == par->left)
5728
right_rotate(&root,par);
5733
left_rotate(&root,par2);
5740
test_rb_tree(root,root->parent);
5741
#endif /* EXTRA_DEBUG */
5747
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5753
while (x != root && x->color == SEL_ARG::BLACK)
5758
if (w->color == SEL_ARG::RED)
5760
w->color=SEL_ARG::BLACK;
5761
par->color=SEL_ARG::RED;
5762
left_rotate(&root,par);
5765
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5767
w->color=SEL_ARG::RED;
5772
if (w->right->color == SEL_ARG::BLACK)
5774
w->left->color=SEL_ARG::BLACK;
5775
w->color=SEL_ARG::RED;
5776
right_rotate(&root,w);
5779
w->color=par->color;
5780
par->color=SEL_ARG::BLACK;
5781
w->right->color=SEL_ARG::BLACK;
5782
left_rotate(&root,par);
5790
if (w->color == SEL_ARG::RED)
5792
w->color=SEL_ARG::BLACK;
5793
par->color=SEL_ARG::RED;
5794
right_rotate(&root,par);
5797
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5799
w->color=SEL_ARG::RED;
5804
if (w->left->color == SEL_ARG::BLACK)
5806
w->right->color=SEL_ARG::BLACK;
5807
w->color=SEL_ARG::RED;
5808
left_rotate(&root,w);
5811
w->color=par->color;
5812
par->color=SEL_ARG::BLACK;
5813
w->left->color=SEL_ARG::BLACK;
5814
right_rotate(&root,par);
5821
x->color=SEL_ARG::BLACK;
5826
/* Test that the properties for a red-black tree hold */
5829
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5831
int count_l,count_r;
5833
if (element == &null_element)
5834
return 0; // Found end of tree
5835
if (element->parent != parent)
5837
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5840
if (element->color == SEL_ARG::RED &&
5841
(element->left->color == SEL_ARG::RED ||
5842
element->right->color == SEL_ARG::RED))
5844
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5847
if (element->left == element->right && element->left != &null_element)
5849
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5852
count_l=test_rb_tree(element->left,element);
5853
count_r=test_rb_tree(element->right,element);
5854
if (count_l >= 0 && count_r >= 0)
5856
if (count_l == count_r)
5857
return count_l+(element->color == SEL_ARG::BLACK);
5858
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5861
return -1; // Error, no more warnings
5866
Count how many times SEL_ARG graph "root" refers to its part "key"
5869
count_key_part_usage()
5870
root An RB-Root node in a SEL_ARG graph.
5871
key Another RB-Root node in that SEL_ARG graph.
5874
The passed "root" node may refer to "key" node via root->next_key_part,
5877
This function counts how many times the node "key" is referred (via
5878
SEL_ARG::next_key_part) by
5879
- intervals of RB-tree pointed by "root",
5880
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5881
intervals of RB-tree pointed by "root",
5884
Here is an example (horizontal links represent next_key_part pointers,
5885
vertical links - next/prev prev pointers):
5888
|root|-----------------+
5892
+----+ +---+ $ | +---+ Here the return value
5893
| |- ... -| |---$-+--+->|key| will be 4.
5894
+----+ +---+ $ | | +---+
5899
| |---| |---------+ |
5906
Number of links to "key" from nodes reachable from "root".
5909
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5912
for (root=root->first(); root ; root=root->next)
5914
if (root->next_key_part)
5916
if (root->next_key_part == key)
5918
if (root->next_key_part->part < key->part)
5919
count+=count_key_part_usage(root->next_key_part,key);
5927
Check if SEL_ARG::use_count value is correct
5930
SEL_ARG::test_use_count()
5931
root The root node of the SEL_ARG graph (an RB-tree root node that
5932
has the least value of sel_arg->part in the entire graph, and
5933
thus is the "origin" of the graph)
5936
Check if SEL_ARG::use_count value is correct. See the definition of
5937
use_count for what is "correct".
5940
void SEL_ARG::test_use_count(SEL_ARG *root)
5943
if (this == root && use_count != 1)
5945
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5948
if (this->type != SEL_ARG::KEY_RANGE)
5950
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5953
if (pos->next_key_part)
5955
ulong count=count_key_part_usage(root,pos->next_key_part);
5956
if (count > pos->next_key_part->use_count)
5958
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5959
"should be %lu", (long unsigned int)pos,
5960
pos->next_key_part->use_count, count);
5963
pos->next_key_part->test_use_count(root);
5966
if (e_count != elements)
5967
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5968
e_count, elements, (long unsigned int) this);
3534
5973
/****************************************************************************
3535
5974
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3536
5975
****************************************************************************/
4350
Range sequence interface implementation for array<QuickRange>: initialize
6801
Perform key scans for all used indexes (except CPK), get rowids and merge
6802
them into an ordered non-recurrent sequence of rowids.
6804
The merge/duplicate removal is performed using Unique class. We put all
6805
rowids into Unique, get the sorted sequence and destroy the Unique.
6807
If table has a clustered primary key that covers all rows (true for bdb
6808
and innodb currently) and one of the index_merge scans is a scan on PK,
6809
then rows that will be retrieved by PK scan are not put into Unique and
6810
primary key scan is not performed here, it is performed later separately.
6817
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6819
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6820
QUICK_RANGE_SELECT* cur_quick;
6823
handler *file= head->file;
6825
file->extra(HA_EXTRA_KEYREAD);
6826
head->prepare_for_position();
6828
cur_quick_it.rewind();
6829
cur_quick= cur_quick_it++;
6830
assert(cur_quick != 0);
6833
We reuse the same instance of handler so we need to call both init and
6836
if (cur_quick->init() || cur_quick->reset())
6839
unique= new Unique(refpos_order_cmp, (void *)file,
6841
session->variables.sortbuff_size);
6846
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6848
cur_quick->range_end();
6849
cur_quick= cur_quick_it++;
6853
if (cur_quick->file->inited != handler::NONE)
6854
cur_quick->file->ha_index_end();
6855
if (cur_quick->init() || cur_quick->reset())
6861
if (result != HA_ERR_END_OF_FILE)
6863
cur_quick->range_end();
6869
if (session->killed)
6872
/* skip row if it will be retrieved by clustered PK scan */
6873
if (pk_quick_select && pk_quick_select->row_in_ranges())
6876
cur_quick->file->position(cur_quick->record);
6877
result= unique->unique_add((char*)cur_quick->file->ref);
6883
/* ok, all row ids are in Unique */
6884
result= unique->get(head);
6886
doing_pk_scan= false;
6887
/* index_merge currently doesn't support "using index" at all */
6888
file->extra(HA_EXTRA_NO_KEYREAD);
6889
/* start table scan */
6890
init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
6896
Get next row for index_merge.
6898
The rows are read from
6899
1. rowids stored in Unique.
6900
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6901
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6904
int QUICK_INDEX_MERGE_SELECT::get_next()
6909
return(pk_quick_select->get_next());
6911
if ((result= read_record.read_record(&read_record)) == -1)
6913
result= HA_ERR_END_OF_FILE;
6914
end_read_record(&read_record);
6915
/* All rows from Unique have been retrieved, do a clustered PK scan */
6916
if (pk_quick_select)
6918
doing_pk_scan= true;
6919
if ((result= pk_quick_select->init()) ||
6920
(result= pk_quick_select->reset()))
6922
return(pk_quick_select->get_next());
6931
Retrieve next record.
6933
QUICK_ROR_INTERSECT_SELECT::get_next()
6936
Invariant on enter/exit: all intersected selects have retrieved all index
6937
records with rowid <= some_rowid_val and no intersected select has
6938
retrieved any index records with rowid > some_rowid_val.
6939
We start fresh and loop until we have retrieved the same rowid in each of
6940
the key scans or we got an error.
6942
If a Clustered PK scan is present, it is used only to check if row
6943
satisfies its condition (and never used for row retrieval).
6947
other - Error code if any error occurred.
6950
int QUICK_ROR_INTERSECT_SELECT::get_next()
6952
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6953
QUICK_RANGE_SELECT* quick;
6955
uint32_t last_rowid_count=0;
6959
/* Get a rowid for first quick and save it as a 'candidate' */
6961
error= quick->get_next();
6964
while (!error && !cpk_quick->row_in_ranges())
6965
error= quick->get_next();
6970
quick->file->position(quick->record);
6971
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6972
last_rowid_count= 1;
6974
while (last_rowid_count < quick_selects.elements)
6976
if (!(quick= quick_it++))
6984
if ((error= quick->get_next()))
6986
quick->file->position(quick->record);
6987
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6990
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6993
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6996
while (!cpk_quick->row_in_ranges())
6998
if ((error= quick->get_next()))
7002
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7003
last_rowid_count= 1;
7007
/* current 'candidate' row confirmed by this select */
7012
/* We get here if we got the same row ref in all scans. */
7013
if (need_to_fetch_row)
7014
error= head->file->rnd_pos(head->record[0], last_rowid);
7015
} while (error == HA_ERR_RECORD_DELETED);
7021
Retrieve next record.
7023
QUICK_ROR_UNION_SELECT::get_next()
7026
Enter/exit invariant:
7027
For each quick select in the queue a {key,rowid} tuple has been
7028
retrieved but the corresponding row hasn't been passed to output.
7032
other - Error code if any error occurred.
7035
int QUICK_ROR_UNION_SELECT::get_next()
7038
QUICK_SELECT_I *quick;
7046
return(HA_ERR_END_OF_FILE);
7047
/* Ok, we have a queue with >= 1 scans */
7049
quick= queue->top();
7050
memcpy(cur_rowid, quick->last_rowid, rowid_length);
7052
/* put into queue rowid from the same stream as top element */
7053
if ((error= quick->get_next()))
7055
if (error != HA_ERR_END_OF_FILE)
7061
quick->save_last_pos();
7066
if (!have_prev_rowid)
7068
/* No rows have been returned yet */
7070
have_prev_rowid= true;
7073
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
7077
cur_rowid= prev_rowid;
7080
error= head->file->rnd_pos(quick->record, prev_rowid);
7081
} while (error == HA_ERR_RECORD_DELETED);
7086
int QUICK_RANGE_SELECT::reset()
7089
unsigned char *mrange_buff;
7091
HANDLER_BUFFER empty_buf;
7093
cur_range= (QUICK_RANGE**) ranges.buffer;
7095
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
7098
/* Allocate buffer if we need one but haven't allocated it yet */
7099
if (mrr_buf_size && !mrr_buf_desc)
7101
buf_size= mrr_buf_size;
7102
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7103
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7104
&mrange_buff, buf_size,
7107
/* Try to shrink the buffers until both are 0. */
7111
return(HA_ERR_OUT_OF_MEM);
7113
/* Initialize the handler buffer. */
7114
mrr_buf_desc->buffer= mrange_buff;
7115
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7116
mrr_buf_desc->end_of_used_area= mrange_buff;
7120
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7123
mrr_flags |= HA_MRR_SORTED;
7124
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7125
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7126
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7133
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4353
7136
quick_range_seq_init()
4354
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7137
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4355
7138
n_ranges Number of ranges in the sequence (ignored)
4356
7139
flags MRR flags (currently not used)
4383
7166
1 No more ranges in the sequence
4385
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7169
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4387
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7171
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4389
7173
if (ctx->cur == ctx->last)
4390
7174
return 1; /* no more ranges */
4392
optimizer::QuickRange *cur= *(ctx->cur);
7176
QUICK_RANGE *cur= *(ctx->cur);
4393
7177
key_range *start_key= &range->start_key;
4394
key_range *end_key= &range->end_key;
7178
key_range *end_key= &range->end_key;
4396
start_key->key= cur->min_key;
7180
start_key->key= cur->min_key;
4397
7181
start_key->length= cur->min_length;
4398
7182
start_key->keypart_map= cur->min_keypart_map;
4399
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4400
(cur->flag & EQ_RANGE) ?
4401
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4402
end_key->key= cur->max_key;
4403
end_key->length= cur->max_length;
7183
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7184
(cur->flag & EQ_RANGE) ?
7185
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7186
end_key->key= cur->max_key;
7187
end_key->length= cur->max_length;
4404
7188
end_key->keypart_map= cur->max_keypart_map;
4406
7190
We use HA_READ_AFTER_KEY here because if we are reading on a key
4407
7191
prefix. We want to find all keys with this prefix.
4409
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7193
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4411
7195
range->range_flag= cur->flag;
7202
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7205
mrr_persistent_flag_storage()
7206
seq Range sequence being traversed
7210
MRR/NDB implementation needs to store some bits for each range. This
7211
function returns a reference to the "range_flag" associated with the
7214
This function should be removed when we get a proper MRR/NDB
7218
Reference to range_flag associated with range number #idx
7221
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7223
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7224
return ctx->first[idx]->flag;
7229
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7232
mrr_get_ptr_by_idx()
7233
seq Range sequence bening traversed
7234
idx Number of the range
7237
An extension of MRR range sequence interface needed by NDB: return the
7238
data associated with the given range.
7240
A proper MRR interface implementer is supposed to store and return
7241
range-associated data. NDB stores number of the range instead. So this
7242
is a helper function that translates range number to range associated
7245
This function does nothing, as currrently there is only one user of the
7246
MRR interface - the quick range select code, and this user doesn't need
7247
to use range-associated data.
7250
Reference to range-associated data
7253
char* &mrr_get_ptr_by_idx(range_seq_t, uint32_t)
7261
Get next possible record using quick-struct.
7264
QUICK_RANGE_SELECT::get_next()
7267
Record is read into table->record[0]
7271
HA_ERR_END_OF_FILE No (more) rows in range
7275
int QUICK_RANGE_SELECT::get_next()
7278
if (in_ror_merged_scan)
7281
We don't need to signal the bitmap change as the bitmap is always the
7282
same for this head->file
7284
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7287
int result= file->multi_range_read_next(&dummy);
7289
if (in_ror_merged_scan)
7291
/* Restore bitmaps set on entry */
7292
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7299
Get the next record with a different prefix.
7302
QUICK_RANGE_SELECT::get_next_prefix()
7303
prefix_length length of cur_prefix
7304
cur_prefix prefix of a key to be searched for
7307
Each subsequent call to the method retrieves the first record that has a
7308
prefix with length prefix_length different from cur_prefix, such that the
7309
record with the new prefix is within the ranges described by
7310
this->ranges. The record found is stored into the buffer pointed by
7312
The method is useful for GROUP-BY queries with range conditions to
7313
discover the prefix of the next group that satisfies the range conditions.
7316
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7317
methods should be unified into a more general one to reduce code
7322
HA_ERR_END_OF_FILE if returned all keys
7323
other if some error occurred
7326
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7327
key_part_map keypart_map,
7328
unsigned char *cur_prefix)
7333
key_range start_key, end_key;
7336
/* Read the next record in the same range with prefix after cur_prefix. */
7337
assert(cur_prefix != 0);
7338
result= file->index_read_map(record, cur_prefix, keypart_map,
7340
if (result || (file->compare_key(file->end_range) <= 0))
7344
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7347
/* Ranges have already been used up before. None is left for read. */
7349
return HA_ERR_END_OF_FILE;
7351
last_range= *(cur_range++);
7353
start_key.key= (const unsigned char*) last_range->min_key;
7354
start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7355
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7356
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7357
(last_range->flag & EQ_RANGE) ?
7358
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7359
end_key.key= (const unsigned char*) last_range->max_key;
7360
end_key.length= cmin(last_range->max_length, (uint16_t)prefix_length);
7361
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7363
We use READ_AFTER_KEY here because if we are reading on a key
7364
prefix we want to find all keys with this prefix
7366
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7369
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7370
last_range->max_keypart_map ? &end_key : 0,
7371
test(last_range->flag & EQ_RANGE),
7373
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7374
last_range= 0; // Stop searching
7376
if (result != HA_ERR_END_OF_FILE)
7378
last_range= 0; // No matching rows; go to next range
7384
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7387
It is assumed that currently a scan is being done on another index
7388
which reads all necessary parts of the index that is scanned by this
7390
The implementation does a binary search on sorted array of disjoint
7391
ranges, without taking size of range into account.
7393
This function is used to filter out clustered PK scan rows in
7394
index_merge quick select.
7397
true if current row will be retrieved by this quick select
7401
bool QUICK_RANGE_SELECT::row_in_ranges()
7405
uint32_t max= ranges.elements - 1;
7406
uint32_t mid= (max + min)/2;
7410
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7412
/* current row value > mid->max */
7417
mid= (min + max) / 2;
7419
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7420
return (!cmp_next(res) && !cmp_prev(res));
7424
This is a hack: we inherit from QUICK_SELECT so that we can use the
7425
get_next() interface, but we have to hold a pointer to the original
7426
QUICK_SELECT because its data are used all over the place. What
7427
should be done is to factor out the data that is needed into a base
7428
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7429
which handle the ranges and implement the get_next() function. But
7430
for now, this seems to work right at least.
7433
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7434
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7438
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7439
QUICK_RANGE **end_range= pr + ranges.elements;
7440
for (; pr!=end_range; pr++)
7441
rev_ranges.push_front(*pr);
7443
/* Remove EQ_RANGE flag for keys that are not using the full key */
7444
for (r = rev_it++; r; r = rev_it++)
7446
if ((r->flag & EQ_RANGE) &&
7447
head->key_info[index].key_length != r->max_length)
7448
r->flag&= ~EQ_RANGE;
7451
q->dont_free=1; // Don't free shared mem
7456
int QUICK_SELECT_DESC::get_next()
7458
/* The max key is handled as follows:
7459
* - if there is NO_MAX_RANGE, start at the end and move backwards
7460
* - if it is an EQ_RANGE, which means that max key covers the entire
7461
* key, go directly to the key and read through it (sorting backwards is
7462
* same as sorting forwards)
7463
* - if it is NEAR_MAX, go to the key or next, step back once, and
7465
* - otherwise (not NEAR_MAX == include the key), go after the key,
7466
* step back once, and move backwards
7473
{ // Already read through key
7474
result = ((last_range->flag & EQ_RANGE)
7475
? file->index_next_same(record, last_range->min_key,
7476
last_range->min_length) :
7477
file->index_prev(record));
7480
if (cmp_prev(*rev_it.ref()) == 0)
7483
else if (result != HA_ERR_END_OF_FILE)
7487
if (!(last_range= rev_it++))
7488
return HA_ERR_END_OF_FILE; // All ranges used
7490
if (last_range->flag & NO_MAX_RANGE) // Read last record
7493
if ((local_error=file->index_last(record)))
7494
return(local_error); // Empty table
7495
if (cmp_prev(last_range) == 0)
7497
last_range= 0; // No match; go to next range
7501
if (last_range->flag & EQ_RANGE)
7503
result = file->index_read_map(record, last_range->max_key,
7504
last_range->max_keypart_map,
7509
assert(last_range->flag & NEAR_MAX ||
7510
range_reads_after_key(last_range));
7511
result=file->index_read_map(record, last_range->max_key,
7512
last_range->max_keypart_map,
7513
((last_range->flag & NEAR_MAX) ?
7514
HA_READ_BEFORE_KEY :
7515
HA_READ_PREFIX_LAST_OR_PREV));
7519
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7521
last_range= 0; // Not found, to next range
7524
if (cmp_prev(last_range) == 0)
7526
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7527
last_range= 0; // Stop searching
7528
return 0; // Found key is in range
7530
last_range= 0; // To next range
7536
Compare if found key is over max-value
7537
Returns 0 if key <= range->max_key
7538
TODO: Figure out why can't this function be as simple as cmp_prev().
7541
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7543
if (range_arg->flag & NO_MAX_RANGE)
7544
return 0; /* key can't be to large */
7546
KEY_PART *key_part=key_parts;
7547
uint32_t store_length;
7549
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7551
key+= store_length, key_part++)
7554
store_length= key_part->store_length;
7555
if (key_part->null_bit)
7559
if (!key_part->field->is_null())
7563
else if (key_part->field->is_null())
7565
key++; // Skip null byte
7568
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7573
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7578
Returns 0 if found key is inside range (found key >= range->min_key).
7581
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7584
if (range_arg->flag & NO_MIN_RANGE)
7585
return 0; /* key can't be to small */
7587
cmp= key_cmp(key_part_info, range_arg->min_key,
7588
range_arg->min_length);
7589
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7591
return 1; // outside of range
7596
* true if this range will require using HA_READ_AFTER_KEY
7597
See comment in get_next() about this
7600
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7602
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7603
!(range_arg->flag & EQ_RANGE) ||
7604
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7608
void QUICK_RANGE_SELECT::add_info_string(String *str)
7610
KEY *key_info= head->key_info + index;
7611
str->append(key_info->name);
7614
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7616
QUICK_RANGE_SELECT *quick;
7618
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7619
str->append(STRING_WITH_LEN("sort_union("));
7620
while ((quick= it++))
7626
quick->add_info_string(str);
7628
if (pk_quick_select)
7631
pk_quick_select->add_info_string(str);
7636
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7639
QUICK_RANGE_SELECT *quick;
7640
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7641
str->append(STRING_WITH_LEN("intersect("));
7642
while ((quick= it++))
7644
KEY *key_info= head->key_info + quick->index;
7649
str->append(key_info->name);
7653
KEY *key_info= head->key_info + cpk_quick->index;
7655
str->append(key_info->name);
7660
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7663
QUICK_SELECT_I *quick;
7664
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7665
str->append(STRING_WITH_LEN("union("));
7666
while ((quick= it++))
7672
quick->add_info_string(str);
7678
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7679
String *used_lengths)
7683
KEY *key_info= head->key_info + index;
7684
key_names->append(key_info->name);
7685
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7686
used_lengths->append(buf, length);
7689
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7690
String *used_lengths)
7695
QUICK_RANGE_SELECT *quick;
7697
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7698
while ((quick= it++))
7704
key_names->append(',');
7705
used_lengths->append(',');
7708
KEY *key_info= head->key_info + quick->index;
7709
key_names->append(key_info->name);
7710
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7711
used_lengths->append(buf, length);
7713
if (pk_quick_select)
7715
KEY *key_info= head->key_info + pk_quick_select->index;
7716
key_names->append(',');
7717
key_names->append(key_info->name);
7718
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7719
used_lengths->append(',');
7720
used_lengths->append(buf, length);
7724
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7725
String *used_lengths)
7730
QUICK_RANGE_SELECT *quick;
7731
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7732
while ((quick= it++))
7734
KEY *key_info= head->key_info + quick->index;
7739
key_names->append(',');
7740
used_lengths->append(',');
7742
key_names->append(key_info->name);
7743
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7744
used_lengths->append(buf, length);
7749
KEY *key_info= head->key_info + cpk_quick->index;
7750
key_names->append(',');
7751
key_names->append(key_info->name);
7752
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7753
used_lengths->append(',');
7754
used_lengths->append(buf, length);
7758
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7759
String *used_lengths)
7762
QUICK_SELECT_I *quick;
7763
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7764
while ((quick= it++))
7770
used_lengths->append(',');
7771
key_names->append(',');
7773
quick->add_keys_and_lengths(key_names, used_lengths);
7778
/*******************************************************************************
7779
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7780
*******************************************************************************/
4417
7782
static inline uint32_t get_field_keypart(KEY *index, Field *field);
4419
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4420
optimizer::SEL_TREE *range_tree,
4421
optimizer::Parameter *param,
4422
uint32_t *param_idx);
4424
static bool get_constant_key_infix(KEY *index_info,
4425
optimizer::SEL_ARG *index_range_tree,
4426
KEY_PART_INFO *first_non_group_part,
4427
KEY_PART_INFO *min_max_arg_part,
4428
KEY_PART_INFO *last_part,
4430
unsigned char *key_infix,
4431
uint32_t *key_infix_len,
4432
KEY_PART_INFO **first_non_infix_part);
4434
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7783
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7784
PARAM *param, uint32_t *param_idx);
7785
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7786
KEY_PART_INFO *first_non_group_part,
7787
KEY_PART_INFO *min_max_arg_part,
7788
KEY_PART_INFO *last_part, Session *session,
7789
unsigned char *key_infix, uint32_t *key_infix_len,
7790
KEY_PART_INFO **first_non_infix_part);
7792
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7793
Field::imagetype image_type);
4437
cost_group_min_max(Table* table,
4439
uint32_t used_key_parts,
4440
uint32_t group_key_parts,
4441
optimizer::SEL_TREE *range_tree,
4442
optimizer::SEL_ARG *index_tree,
4443
ha_rows quick_prefix_records,
7796
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7797
uint32_t group_key_parts, SEL_TREE *range_tree,
7798
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7799
bool have_min, bool have_max,
7800
double *read_cost, ha_rows *records);
5567
optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5569
optimizer::QuickRangeSelect *quick= NULL;
5570
if ((quick= optimizer::get_quick_select(param,
5577
quick->records= records;
5578
quick->read_time= read_cost;
5584
} /* namespace drizzled */
8855
Construct new quick select for group queries with min/max.
8858
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8859
table The table being accessed
8860
join Descriptor of the current query
8861
have_min true if the query selects a MIN function
8862
have_max true if the query selects a MAX function
8863
min_max_arg_part The only argument field of all MIN/MAX functions
8864
group_prefix_len Length of all key parts in the group prefix
8865
prefix_key_parts All key parts in the group prefix
8866
index_info The index chosen for data access
8867
use_index The id of index_info
8868
read_cost Cost of this access method
8869
records Number of records returned
8870
key_infix_len Length of the key infix appended to the group prefix
8871
key_infix Infix of constants from equality predicates
8872
parent_alloc Memory pool for this and quick_prefix_select data
8878
QUICK_GROUP_MIN_MAX_SELECT::
8879
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8881
KEY_PART_INFO *min_max_arg_part_arg,
8882
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8883
uint32_t used_key_parts_arg, KEY *index_info_arg,
8884
uint32_t use_index, double read_cost_arg,
8885
ha_rows records_arg, uint32_t key_infix_len_arg,
8886
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8887
:join(join_arg), index_info(index_info_arg),
8888
group_prefix_len(group_prefix_len_arg),
8889
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8890
have_max(have_max_arg), seen_first_key(false),
8891
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8892
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8893
max_functions_it(NULL)
8898
record= head->record[0];
8899
tmp_record= head->record[1];
8900
read_time= read_cost_arg;
8901
records= records_arg;
8902
used_key_parts= used_key_parts_arg;
8903
real_key_parts= used_key_parts_arg;
8904
real_prefix_len= group_prefix_len + key_infix_len;
8906
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8909
We can't have parent_alloc set as the init function can't handle this case
8912
assert(!parent_alloc);
8915
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
8916
join->session->mem_root= &alloc;
8919
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8924
Do post-constructor initialization.
8927
QUICK_GROUP_MIN_MAX_SELECT::init()
8930
The method performs initialization that cannot be done in the constructor
8931
such as memory allocations that may fail. It allocates memory for the
8932
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8933
updated during execution.
8940
int QUICK_GROUP_MIN_MAX_SELECT::init()
8942
if (group_prefix) /* Already initialized. */
8945
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8948
We may use group_prefix to store keys with all select fields, so allocate
8949
enough space for it.
8951
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
8952
real_prefix_len + min_max_arg_len)))
8955
if (key_infix_len > 0)
8958
The memory location pointed to by key_infix will be deleted soon, so
8959
allocate a new buffer and copy the key_infix into it.
8961
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
8964
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8965
this->key_infix= tmp_key_infix;
8968
if (min_max_arg_part)
8970
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8975
if (!(min_functions= new List<Item_sum>))
8979
min_functions= NULL;
8982
if (!(max_functions= new List<Item_sum>))
8986
max_functions= NULL;
8988
Item_sum *min_max_item;
8989
Item_sum **func_ptr= join->sum_funcs;
8990
while ((min_max_item= *(func_ptr++)))
8992
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8993
min_functions->push_back(min_max_item);
8994
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8995
max_functions->push_back(min_max_item);
9000
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
9006
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
9011
min_max_ranges.elements= 0;
9017
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
9019
if (file->inited != handler::NONE)
9020
file->ha_index_end();
9021
if (min_max_arg_part)
9022
delete_dynamic(&min_max_ranges);
9023
free_root(&alloc,MYF(0));
9024
delete min_functions_it;
9025
delete max_functions_it;
9026
delete quick_prefix_select;
9031
Eventually create and add a new quick range object.
9034
QUICK_GROUP_MIN_MAX_SELECT::add_range()
9035
sel_range Range object from which a
9038
Construct a new QUICK_RANGE object from a SEL_ARG object, and
9039
add it to the array min_max_ranges. If sel_arg is an infinite
9040
range, e.g. (x < 5 or x > 4), then skip it and do not construct
9048
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
9051
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
9053
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
9054
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
9057
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
9058
!(sel_range->max_flag & NO_MAX_RANGE))
9060
if (sel_range->maybe_null &&
9061
sel_range->min_value[0] && sel_range->max_value[0])
9062
range_flag|= NULL_RANGE; /* IS NULL condition */
9063
else if (memcmp(sel_range->min_value, sel_range->max_value,
9064
min_max_arg_len) == 0)
9065
range_flag|= EQ_RANGE; /* equality condition */
9067
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
9068
make_keypart_map(sel_range->part),
9069
sel_range->max_value, min_max_arg_len,
9070
make_keypart_map(sel_range->part),
9074
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
9081
Opens the ranges if there are more conditions in quick_prefix_select than
9082
the ones used for jumping through the prefixes.
9085
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9088
quick_prefix_select is made over the conditions on the whole key.
9089
It defines a number of ranges of length x.
9090
However when jumping through the prefixes we use only the the first
9091
few most significant keyparts in the range key. However if there
9092
are more keyparts to follow the ones we are using we must make the
9093
condition on the key inclusive (because x < "ab" means
9094
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9095
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9097
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9099
if (quick_prefix_select &&
9100
group_prefix_len < quick_prefix_select->max_used_key_length)
9105
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9109
get_dynamic(arr, (unsigned char*)&range, inx);
9110
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9117
Determine the total number and length of the keys that will be used for
9121
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9124
The total length of the keys used for index lookup depends on whether
9125
there are any predicates referencing the min/max argument, and/or if
9126
the min/max argument field can be NULL.
9127
This function does an optimistic analysis whether the search key might
9128
be extended by a constant for the min/max keypart. It is 'optimistic'
9129
because during actual execution it may happen that a particular range
9130
is skipped, and then a shorter key will be used. However this is data
9131
dependent and can't be easily estimated here.
9137
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9139
max_used_key_length= real_prefix_len;
9140
if (min_max_ranges.elements > 0)
9142
QUICK_RANGE *cur_range;
9144
{ /* Check if the right-most range has a lower boundary. */
9145
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9146
min_max_ranges.elements - 1);
9147
if (!(cur_range->flag & NO_MIN_RANGE))
9149
max_used_key_length+= min_max_arg_len;
9155
{ /* Check if the left-most range has an upper boundary. */
9156
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9157
if (!(cur_range->flag & NO_MAX_RANGE))
9159
max_used_key_length+= min_max_arg_len;
9165
else if (have_min && min_max_arg_part &&
9166
min_max_arg_part->field->real_maybe_null())
9169
If a MIN/MAX argument value is NULL, we can quickly determine
9170
that we're in the beginning of the next group, because NULLs
9171
are always < any other value. This allows us to quickly
9172
determine the end of the current group and jump to the next
9173
group (see next_min()) and thus effectively increases the
9176
max_used_key_length+= min_max_arg_len;
9183
Initialize a quick group min/max select for key retrieval.
9186
QUICK_GROUP_MIN_MAX_SELECT::reset()
9189
Initialize the index chosen for access and find and store the prefix
9190
of the last group. The method is expensive since it performs disk access.
9197
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9201
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9202
if ((result= file->ha_index_init(index,1)))
9204
if (quick_prefix_select && quick_prefix_select->reset())
9206
result= file->index_last(record);
9207
if (result == HA_ERR_END_OF_FILE)
9209
/* Save the prefix of the last group. */
9210
key_copy(last_prefix, record, index_info, group_prefix_len);
9218
Get the next key containing the MIN and/or MAX key for the next group.
9221
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9224
The method finds the next subsequent group of records that satisfies the
9225
query conditions and finds the keys that contain the MIN/MAX values for
9226
the key part referenced by the MIN/MAX function(s). Once a group and its
9227
MIN/MAX values are found, store these values in the Item_sum objects for
9228
the MIN/MAX functions. The rest of the values in the result row are stored
9229
in the Item_field::result_field of each select field. If the query does
9230
not contain MIN and/or MAX functions, then the function only finds the
9231
group prefix, which is a query answer itself.
9234
If both MIN and MAX are computed, then we use the fact that if there is
9235
no MIN key, there can't be a MAX key as well, so we can skip looking
9236
for a MAX key in this case.
9240
HA_ERR_END_OF_FILE if returned all keys
9241
other if some error occurred
9244
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9249
int is_last_prefix= 0;
9252
Loop until a group is found that satisfies all query conditions or the last
9257
result= next_prefix();
9259
Check if this is the last group prefix. Notice that at this point
9260
this->record contains the current prefix in record format.
9264
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9266
assert(is_last_prefix <= 0);
9270
if (result == HA_ERR_KEY_NOT_FOUND)
9277
min_res= next_min();
9279
update_min_result();
9281
/* If there is no MIN in the group, there is no MAX either. */
9282
if ((have_max && !have_min) ||
9283
(have_max && have_min && (min_res == 0)))
9285
max_res= next_max();
9287
update_max_result();
9288
/* If a MIN was found, a MAX must have been found as well. */
9289
assert(((have_max && !have_min) ||
9290
(have_max && have_min && (max_res == 0))));
9293
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9294
are equality predicates for the key parts after the group, find the
9295
first sub-group with the extended prefix.
9297
if (!have_min && !have_max && key_infix_len > 0)
9298
result= file->index_read_map(record, group_prefix,
9299
make_prev_keypart_map(real_key_parts),
9302
result= have_min ? min_res : have_max ? max_res : result;
9303
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9304
is_last_prefix != 0);
9309
Partially mimic the behavior of end_select_send. Copy the
9310
field data from Item_field::field into Item_field::result_field
9311
of each non-aggregated field (the group fields, and optionally
9312
other fields in non-ANSI SQL mode).
9314
copy_fields(&join->tmp_table_param);
9316
else if (result == HA_ERR_KEY_NOT_FOUND)
9317
result= HA_ERR_END_OF_FILE;
9324
Retrieve the minimal key in the next group.
9327
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9330
Find the minimal key within this group such that the key satisfies the query
9331
conditions and NULL semantics. The found key is loaded into this->record.
9334
Depending on the values of min_max_ranges.elements, key_infix_len, and
9335
whether there is a NULL in the MIN field, this function may directly
9336
return without any data access. In this case we use the key loaded into
9337
this->record by the call to this->next_prefix() just before this call.
9341
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9342
HA_ERR_END_OF_FILE - "" -
9343
other if some error occurred
9346
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9350
/* Find the MIN key using the eventually extended group prefix. */
9351
if (min_max_ranges.elements > 0)
9353
if ((result= next_min_in_range()))
9358
/* Apply the constant equality conditions to the non-group select fields */
9359
if (key_infix_len > 0)
9361
if ((result= file->index_read_map(record, group_prefix,
9362
make_prev_keypart_map(real_key_parts),
9363
HA_READ_KEY_EXACT)))
9368
If the min/max argument field is NULL, skip subsequent rows in the same
9369
group with NULL in it. Notice that:
9370
- if the first row in a group doesn't have a NULL in the field, no row
9371
in the same group has (because NULL < any other value),
9372
- min_max_arg_part->field->ptr points to some place in 'record'.
9374
if (min_max_arg_part && min_max_arg_part->field->is_null())
9376
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9377
key_copy(tmp_record, record, index_info, 0);
9378
result= file->index_read_map(record, tmp_record,
9379
make_keypart_map(real_key_parts),
9382
Check if the new record belongs to the current group by comparing its
9383
prefix with the group's prefix. If it is from the next group, then the
9384
whole group has NULLs in the MIN/MAX field, so use the first record in
9385
the group as a result.
9387
It is possible to reuse this new record as the result candidate for the
9388
next call to next_min(), and to save one lookup in the next call. For
9389
this add a new member 'this->next_group_prefix'.
9393
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9394
key_restore(record, tmp_record, index_info, 0);
9396
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9397
result= 0; /* There is a result in any case. */
9402
If the MIN attribute is non-nullable, this->record already contains the
9403
MIN key in the group, so just return.
9410
Retrieve the maximal key in the next group.
9413
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9416
Lookup the maximal key of the group, and store it into this->record.
9420
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9421
HA_ERR_END_OF_FILE - "" -
9422
other if some error occurred
9425
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9429
/* Get the last key in the (possibly extended) group. */
9430
if (min_max_ranges.elements > 0)
9431
result= next_max_in_range();
9433
result= file->index_read_map(record, group_prefix,
9434
make_prev_keypart_map(real_key_parts),
9435
HA_READ_PREFIX_LAST);
9441
Determine the prefix of the next group.
9444
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9447
Determine the prefix of the next group that satisfies the query conditions.
9448
If there is a range condition referencing the group attributes, use a
9449
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9450
condition. If there is a key infix of constants, append this infix
9451
immediately after the group attributes. The possibly extended prefix is
9452
stored in this->group_prefix. The first key of the found group is stored in
9453
this->record, on which relies this->next_min().
9457
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9458
HA_ERR_END_OF_FILE if there are no more keys
9459
other if some error occurred
9461
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9465
if (quick_prefix_select)
9467
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9468
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9469
make_prev_keypart_map(group_key_parts), cur_prefix)))
9471
seen_first_key= true;
9475
if (!seen_first_key)
9477
result= file->index_first(record);
9480
seen_first_key= true;
9484
/* Load the first key in this group into record. */
9485
result= file->index_read_map(record, group_prefix,
9486
make_prev_keypart_map(group_key_parts),
9493
/* Save the prefix of this group for subsequent calls. */
9494
key_copy(group_prefix, record, index_info, group_prefix_len);
9495
/* Append key_infix to group_prefix. */
9496
if (key_infix_len > 0)
9497
memcpy(group_prefix + group_prefix_len,
9498
key_infix, key_infix_len);
9505
Find the minimal key in a group that satisfies some range conditions for the
9506
min/max argument field.
9509
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9512
Given the sequence of ranges min_max_ranges, find the minimal key that is
9513
in the left-most possible range. If there is no such key, then the current
9514
group does not have a MIN key that satisfies the WHERE clause. If a key is
9515
found, its value is stored in this->record.
9519
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9521
HA_ERR_END_OF_FILE - "" -
9525
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9527
ha_rkey_function find_flag;
9528
key_part_map keypart_map;
9529
QUICK_RANGE *cur_range;
9530
bool found_null= false;
9531
int result= HA_ERR_KEY_NOT_FOUND;
9532
basic_string<unsigned char> max_key;
9534
max_key.reserve(real_prefix_len + min_max_arg_len);
9536
assert(min_max_ranges.elements > 0);
9538
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9539
{ /* Search from the left-most range to the right. */
9540
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9543
If the current value for the min/max argument is bigger than the right
9544
boundary of cur_range, there is no need to check this range.
9546
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9547
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9548
min_max_arg_len) == 1))
9551
if (cur_range->flag & NO_MIN_RANGE)
9553
keypart_map= make_prev_keypart_map(real_key_parts);
9554
find_flag= HA_READ_KEY_EXACT;
9558
/* Extend the search key with the lower boundary for this range. */
9559
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9560
cur_range->min_length);
9561
keypart_map= make_keypart_map(real_key_parts);
9562
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9563
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9564
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9567
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9570
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9571
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9572
continue; /* Check the next range. */
9575
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9576
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9577
range, it can't succeed for any other subsequent range.
9582
/* A key was found. */
9583
if (cur_range->flag & EQ_RANGE)
9584
break; /* No need to perform the checks below for equal keys. */
9586
if (cur_range->flag & NULL_RANGE)
9589
Remember this key, and continue looking for a non-NULL key that
9590
satisfies some other condition.
9592
memcpy(tmp_record, record, head->s->rec_buff_length);
9597
/* Check if record belongs to the current group. */
9598
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9600
result= HA_ERR_KEY_NOT_FOUND;
9604
/* If there is an upper limit, check if the found key is in the range. */
9605
if ( !(cur_range->flag & NO_MAX_RANGE) )
9607
/* Compose the MAX key for the range. */
9609
max_key.append(group_prefix, real_prefix_len);
9610
max_key.append(cur_range->max_key, cur_range->max_length);
9611
/* Compare the found key with max_key. */
9612
int cmp_res= key_cmp(index_info->key_part,
9614
real_prefix_len + min_max_arg_len);
9615
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9617
result= HA_ERR_KEY_NOT_FOUND;
9621
/* If we got to this point, the current key qualifies as MIN. */
9622
assert(result == 0);
9626
If there was a key with NULL in the MIN/MAX field, and there was no other
9627
key without NULL from the same group that satisfies some other condition,
9628
then use the key with the NULL.
9630
if (found_null && result)
9632
memcpy(record, tmp_record, head->s->rec_buff_length);
9640
Find the maximal key in a group that satisfies some range conditions for the
9641
min/max argument field.
9644
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9647
Given the sequence of ranges min_max_ranges, find the maximal key that is
9648
in the right-most possible range. If there is no such key, then the current
9649
group does not have a MAX key that satisfies the WHERE clause. If a key is
9650
found, its value is stored in this->record.
9654
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9656
HA_ERR_END_OF_FILE - "" -
9660
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9662
ha_rkey_function find_flag;
9663
key_part_map keypart_map;
9664
QUICK_RANGE *cur_range;
9666
basic_string<unsigned char> min_key;
9667
min_key.reserve(real_prefix_len + min_max_arg_len);
9669
assert(min_max_ranges.elements > 0);
9671
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9672
{ /* Search from the right-most range to the left. */
9673
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9676
If the current value for the min/max argument is smaller than the left
9677
boundary of cur_range, there is no need to check this range.
9679
if (range_idx != min_max_ranges.elements &&
9680
!(cur_range->flag & NO_MIN_RANGE) &&
9681
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9682
min_max_arg_len) == -1))
9685
if (cur_range->flag & NO_MAX_RANGE)
9687
keypart_map= make_prev_keypart_map(real_key_parts);
9688
find_flag= HA_READ_PREFIX_LAST;
9692
/* Extend the search key with the upper boundary for this range. */
9693
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9694
cur_range->max_length);
9695
keypart_map= make_keypart_map(real_key_parts);
9696
find_flag= (cur_range->flag & EQ_RANGE) ?
9697
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9698
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9701
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9705
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9706
(cur_range->flag & EQ_RANGE))
9707
continue; /* Check the next range. */
9710
In no key was found with this upper bound, there certainly are no keys
9711
in the ranges to the left.
9715
/* A key was found. */
9716
if (cur_range->flag & EQ_RANGE)
9717
return 0; /* No need to perform the checks below for equal keys. */
9719
/* Check if record belongs to the current group. */
9720
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9721
continue; // Row not found
9723
/* If there is a lower limit, check if the found key is in the range. */
9724
if ( !(cur_range->flag & NO_MIN_RANGE) )
9726
/* Compose the MIN key for the range. */
9728
min_key.append(group_prefix, real_prefix_len);
9729
min_key.append(cur_range->min_key, cur_range->min_length);
9731
/* Compare the found key with min_key. */
9732
int cmp_res= key_cmp(index_info->key_part,
9734
real_prefix_len + min_max_arg_len);
9735
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9739
/* If we got to this point, the current key qualifies as MAX. */
9742
return HA_ERR_KEY_NOT_FOUND;
9747
Update all MIN function results with the newly found value.
9750
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9753
The method iterates through all MIN functions and updates the result value
9754
of each function by calling Item_sum::reset(), which in turn picks the new
9755
result value from this->head->record[0], previously updated by
9756
next_min(). The updated value is stored in a member variable of each of the
9757
Item_sum objects, depending on the value type.
9760
The update must be done separately for MIN and MAX, immediately after
9761
next_min() was called and before next_max() is called, because both MIN and
9762
MAX take their result value from the same buffer this->head->record[0]
9763
(i.e. this->record).
9769
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9773
min_functions_it->rewind();
9774
while ((min_func= (*min_functions_it)++))
9780
Update all MAX function results with the newly found value.
9783
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9786
The method iterates through all MAX functions and updates the result value
9787
of each function by calling Item_sum::reset(), which in turn picks the new
9788
result value from this->head->record[0], previously updated by
9789
next_max(). The updated value is stored in a member variable of each of the
9790
Item_sum objects, depending on the value type.
9793
The update must be done separately for MIN and MAX, immediately after
9794
next_max() was called, because both MIN and MAX take their result value
9795
from the same buffer this->head->record[0] (i.e. this->record).
9801
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9805
max_functions_it->rewind();
9806
while ((max_func= (*max_functions_it)++))
9812
Append comma-separated list of keys this quick select uses to key_names;
9813
append comma-separated list of corresponding used lengths to used_lengths.
9816
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9817
key_names [out] Names of used indexes
9818
used_lengths [out] Corresponding lengths of the index names
9821
This method is used by select_describe to extract the names of the
9822
indexes used by a quick select.
9826
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9827
String *used_lengths)
9831
key_names->append(index_info->name);
9832
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9833
used_lengths->append(buf, length);
9836
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9838
SEL_ARG **key,**end;
9842
String tmp(buff,sizeof(buff),&my_charset_bin);
9844
for (idx= 0,key=tree->keys, end=key+param->keys ;
9848
if (tree_map->is_set(idx))
9850
uint32_t keynr= param->real_keynr[idx];
9853
tmp.append(param->table->key_info[keynr].name);
9857
tmp.append(STRING_WITH_LEN("(empty)"));
9861
static void print_ror_scans_arr(Table *table,
9862
const char *, struct st_ror_scan_info **start,
9863
struct st_ror_scan_info **end)
9866
String tmp(buff,sizeof(buff),&my_charset_bin);
9868
for (;start != end; start++)
9872
tmp.append(table->key_info[(*start)->keynr].name);
9875
tmp.append(STRING_WITH_LEN("(empty)"));
9878
/*****************************************************************************
9879
** Instantiate templates
9880
*****************************************************************************/
9882
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9883
template class List<QUICK_RANGE>;
9884
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
