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)
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.none().
638
vector<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
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
703
MY_BITMAP 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);
316
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)
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))
935
Perform AND operation on two index_merge lists and store result in im1.
938
inline void imerge_list_and_list(vector<SEL_IMERGE*> &im1, vector<SEL_IMERGE*> &im2)
940
im1.insert(im1.end(), im2.begin(), im2.end());
946
Perform OR operation on 2 index_merge lists, storing result in first list.
949
The following conversion is implemented:
950
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
953
i.e. all conjuncts except the first one are currently dropped.
954
This is done to avoid producing N*K ways to do index_merge.
956
If (a_1||b_1) produce a condition that is always true, NULL is returned
957
and index_merge is discarded (while it is actually possible to try
960
As a consequence of this, choice of keys to do index_merge read may depend
961
on the order of conditions in WHERE part of the query.
964
0 OK, result is stored in *im1
965
other Error, both passed lists are unusable
968
int imerge_list_or_list(RANGE_OPT_PARAM *param,
969
vector<SEL_IMERGE*> &im1,
970
vector<SEL_IMERGE*> &im2)
972
SEL_IMERGE *imerge= im1.front();
974
im1.push_back(imerge);
976
return imerge->or_sel_imerge_with_checks(param, im2.front());
981
Perform OR operation on index_merge list and key tree.
984
false OK, result is stored in im1.
988
bool imerge_list_or_tree(RANGE_OPT_PARAM *param,
989
vector<SEL_IMERGE*> &im1,
992
vector<SEL_IMERGE*>::iterator imerge= im1.begin();
994
while (imerge != im1.end())
996
if ((*imerge)->or_sel_tree_with_checks(param, tree))
997
imerge= im1.erase( imerge );
325
1006
/***************************************************************************
326
** Basic functions for SqlSelect and QuickRangeSelect
1007
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
327
1008
***************************************************************************/
329
1010
/* make a select from mysql info
372
optimizer::SqlSelect::SqlSelect()
376
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1049
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
380
1052
needed_reg.reset();
385
void optimizer::SqlSelect::cleanup()
1057
void SQL_SELECT::cleanup()
395
close_cached_file(file);
1067
close_cached_file(&file);
399
optimizer::SqlSelect::~SqlSelect()
1071
SQL_SELECT::~SQL_SELECT()
405
bool optimizer::SqlSelect::check_quick(Session *session,
406
bool force_quick_range,
1077
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),
1082
return test_quick_select(session, tmp, 0, limit,
1083
force_quick_range, false) < 0;
1087
bool SQL_SELECT::skip_record()
1089
return cond ? cond->val_int() == 0 : 0;
1093
QUICK_SELECT_I::QUICK_SELECT_I()
1094
:max_used_key_length(0),
1098
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1099
bool no_alloc, MEM_ROOT *parent_alloc,
1101
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1103
my_bitmap_map *bitmap;
1105
in_ror_merged_scan= 0;
1109
key_part_info= head->key_info[index].key_part;
1110
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1112
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1113
mrr_buf_size= session->variables.read_rnd_buff_size;
1116
if (!no_alloc && !parent_alloc)
1118
// Allocates everything through the internal memroot
1119
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1120
session->mem_root= &alloc;
1123
memset(&alloc, 0, sizeof(alloc));
1125
record= head->record[0];
1126
save_read_set= head->read_set;
1127
save_write_set= head->write_set;
1129
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1130
if (!(bitmap= (my_bitmap_map*) malloc(head->s->column_bitmap_size)))
1132
column_bitmap.bitmap= 0;
1136
bitmap_init(&column_bitmap, bitmap, head->s->fields);
1141
int QUICK_RANGE_SELECT::init()
1143
if (file->inited != handler::NONE)
1144
file->ha_index_or_rnd_end();
1145
return(file->ha_index_init(index, 1));
1149
void QUICK_RANGE_SELECT::range_end()
1151
if (file->inited != handler::NONE)
1152
file->ha_index_or_rnd_end();
1156
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1160
/* file is NULL for CPK scan on covering ROR-intersection */
1167
file->extra(HA_EXTRA_NO_KEYREAD);
1171
file->ha_external_lock(current_session, F_UNLCK);
1176
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1177
free_root(&alloc,MYF(0));
1178
free((char*) column_bitmap.bitmap);
1180
head->column_bitmaps_set(save_read_set, save_write_set);
1187
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1189
:pk_quick_select(NULL), session(session_param)
1193
memset(&read_record, 0, sizeof(read_record));
1194
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1198
int QUICK_INDEX_MERGE_SELECT::init()
1203
int QUICK_INDEX_MERGE_SELECT::reset()
1205
return(read_keys_and_merge());
1209
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1212
Save quick_select that does scan on clustered primary key as it will be
1213
processed separately.
1215
if (head->file->primary_key_is_clustered() &&
1216
quick_sel_range->index == head->s->primary_key)
1217
pk_quick_select= quick_sel_range;
1219
return quick_selects.push_back(quick_sel_range);
1223
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1225
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1226
QUICK_RANGE_SELECT* quick;
1228
while ((quick= quick_it++))
1230
quick_selects.delete_elements();
1231
delete pk_quick_select;
1232
free_root(&alloc,MYF(0));
1237
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1239
bool retrieve_full_rows,
1240
MEM_ROOT *parent_alloc)
1241
: cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1246
record= head->record[0];
1248
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1250
memset(&alloc, 0, sizeof(MEM_ROOT));
1251
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1252
head->file->ref_length);
1257
Do post-constructor initialization.
1259
QUICK_ROR_INTERSECT_SELECT::init()
1266
int QUICK_ROR_INTERSECT_SELECT::init()
1268
/* Check if last_rowid was successfully allocated in ctor */
1269
return(!last_rowid);
1274
Initialize this quick select to be a ROR-merged scan.
1277
QUICK_RANGE_SELECT::init_ror_merged_scan()
1278
reuse_handler If true, use head->file, otherwise create a separate
1282
This function creates and prepares for subsequent use a separate handler
1283
object if it can't reuse head->file. The reason for this is that during
1284
ROR-merge several key scans are performed simultaneously, and a single
1285
handler is only capable of preserving context of a single key scan.
1287
In ROR-merge the quick select doing merge does full records retrieval,
1288
merged quick selects read only keys.
1291
0 ROR child scan initialized, ok to use.
1295
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1297
handler *save_file= file, *org_file;
1300
in_ror_merged_scan= 1;
1303
if (init() || reset())
1307
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1311
/* Create a separate handler object for this quick select */
1314
/* already have own 'handler' object. */
1318
session= head->in_use;
1319
if (!(file= head->file->clone(session->mem_root)))
1322
Manually set the error flag. Note: there seems to be quite a few
1323
places where a failure could cause the server to "hang" the client by
1324
sending no response to a query. ATM those are not real errors because
1325
the storage engine calls in question happen to never fail with the
1326
existing storage engines.
1328
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1329
/* Caller will free the memory */
1330
goto failure; /* purecov: inspected */
1333
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1335
if (file->ha_external_lock(session, F_RDLCK))
1338
if (init() || reset())
1340
file->ha_external_lock(session, F_UNLCK);
1345
last_rowid= file->ref;
1349
We are only going to read key fields and call position() on 'file'
1350
The following sets head->tmp_set to only use this key and then updates
1351
head->read_set and head->write_set to use this bitmap.
1352
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1354
org_file= head->file;
1356
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1357
if (!head->no_keyread)
1360
head->mark_columns_used_by_index(index);
1362
head->prepare_for_position();
1363
head->file= org_file;
1364
bitmap_copy(&column_bitmap, head->read_set);
1365
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1370
head->column_bitmaps_set(save_read_set, save_write_set);
1377
void QUICK_RANGE_SELECT::save_last_pos()
1379
file->position(record);
1384
Initialize this quick select to be a part of a ROR-merged scan.
1386
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1387
reuse_handler If true, use head->file, otherwise create separate
1393
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1395
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1396
QUICK_RANGE_SELECT* quick;
1398
/* Initialize all merged "children" quick selects */
1399
assert(!need_to_fetch_row || reuse_handler);
1400
if (!need_to_fetch_row && reuse_handler)
1404
There is no use of this->file. Use it for the first of merged range
1407
if (quick->init_ror_merged_scan(true))
1409
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1411
while ((quick= quick_it++))
1413
if (quick->init_ror_merged_scan(false))
1415
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1416
/* All merged scans share the same record buffer in intersection. */
1417
quick->record= head->record[0];
1420
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1429
Initialize quick select for row retrieval.
1437
int QUICK_ROR_INTERSECT_SELECT::reset()
1439
if (!scans_inited && init_ror_merged_scan(true))
1442
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1443
QUICK_RANGE_SELECT *quick;
1444
while ((quick= it++))
1451
Add a merged quick select to this ROR-intersection quick select.
1454
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1455
quick Quick select to be added. The quick select must return
1456
rows in rowid order.
1458
This call can only be made before init() is called.
1466
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1468
return quick_selects.push_back(quick);
1471
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1473
quick_selects.delete_elements();
1475
free_root(&alloc,MYF(0));
1476
if (need_to_fetch_row && head->file->inited != handler::NONE)
1477
head->file->ha_rnd_end();
1482
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1484
: session(session_param), scans_inited(false)
1488
rowid_length= table->file->ref_length;
1489
record= head->record[0];
1490
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1491
session_param->mem_root= &alloc;
1495
* Function object that is used as the comparison function
1496
* for the priority queue in the QUICK_ROR_UNION_SELECT
1499
class compare_functor
1501
QUICK_ROR_UNION_SELECT *self;
1503
compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
1505
inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
1507
int val= self->head->file->cmp_ref(i->last_rowid,
1514
Do post-constructor initialization.
1516
QUICK_ROR_UNION_SELECT::init()
1523
int QUICK_ROR_UNION_SELECT::init()
1526
new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
1527
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1529
prev_rowid= cur_rowid + head->file->ref_length;
1535
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1539
QUICK_ROR_UNION_SELECT::queue_cmp()
1540
arg Pointer to QUICK_ROR_UNION_SELECT
1541
val1 First merged select
1542
val2 Second merged select
1545
int quick_ror_union_select_queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1547
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1548
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1549
((QUICK_SELECT_I*)val2)->last_rowid);
1554
Initialize quick select for row retrieval.
1563
int QUICK_ROR_UNION_SELECT::reset()
1565
QUICK_SELECT_I *quick;
1567
have_prev_rowid= false;
1570
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1571
while ((quick= it++))
1573
if (quick->init_ror_merged_scan(false))
1578
while (!queue->empty())
1581
Initialize scans for merged quick selects and put all merged quick
1582
selects into the queue.
1584
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1585
while ((quick= it++))
1589
if ((error= quick->get_next()))
1591
if (error == HA_ERR_END_OF_FILE)
1595
quick->save_last_pos();
1599
if (head->file->ha_rnd_init(1))
1609
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1611
return quick_selects.push_back(quick_sel_range);
1614
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1616
while (!queue->empty())
1619
quick_selects.delete_elements();
1620
if (head->file->inited != handler::NONE)
1621
head->file->ha_rnd_end();
1622
free_root(&alloc,MYF(0));
1627
QUICK_RANGE::QUICK_RANGE()
1628
:min_key(0),max_key(0),min_length(0),max_length(0),
1629
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1630
min_keypart_map(0), max_keypart_map(0)
1633
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1636
min_flag=arg.min_flag;
1637
max_flag=arg.max_flag;
1638
maybe_flag=arg.maybe_flag;
1639
maybe_null=arg.maybe_null;
1642
min_value=arg.min_value;
1643
max_value=arg.max_value;
1644
next_key_part=arg.next_key_part;
1645
use_count=1; elements=1;
1649
inline void SEL_ARG::make_root()
1651
left=right= &null_element;
1654
use_count=0; elements=1;
1657
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1658
const unsigned char *max_value_arg)
1659
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1660
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1661
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1662
next_key_part(0),color(BLACK),type(KEY_RANGE)
1664
left=right= &null_element;
1667
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1668
unsigned char *min_value_, unsigned char *max_value_,
1669
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1670
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1671
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1672
field(field_), min_value(min_value_), max_value(max_value_),
1673
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1675
left=right= &null_element;
1678
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1683
/* Bail out if we have already generated too many SEL_ARGs */
1684
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1687
if (type != KEY_RANGE)
1689
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1690
return 0; // out of memory
1691
tmp->prev= *next_arg; // Link into next/prev chain
1692
(*next_arg)->next=tmp;
1697
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1698
min_flag, max_flag, maybe_flag)))
1700
tmp->parent=new_parent;
1701
tmp->next_key_part=next_key_part;
1702
if (left != &null_element)
1703
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1706
tmp->prev= *next_arg; // Link into next/prev chain
1707
(*next_arg)->next=tmp;
1710
if (right != &null_element)
1711
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1714
increment_use_count(1);
1716
tmp->elements= this->elements;
1720
SEL_ARG *SEL_ARG::first()
1722
SEL_ARG *next_arg=this;
1723
if (!next_arg->left)
1724
return 0; // MAYBE_KEY
1725
while (next_arg->left != &null_element)
1726
next_arg=next_arg->left;
1730
SEL_ARG *SEL_ARG::last()
1732
SEL_ARG *next_arg=this;
1733
if (!next_arg->right)
1734
return 0; // MAYBE_KEY
1735
while (next_arg->right != &null_element)
1736
next_arg=next_arg->right;
1742
Check if a compare is ok, when one takes ranges in account
1743
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1746
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1750
/* First check if there was a compare to a min or max element */
1751
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1753
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1754
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1756
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1758
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1759
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1761
if (field->real_maybe_null()) // If null is part of key
1768
goto end; // NULL where equal
1769
a++; b++; // Skip NULL marker
1771
cmp=field->key_cmp(a , b);
1772
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1774
// Check if the compared equal arguments was defined with open/closed range
1776
if (a_flag & (NEAR_MIN | NEAR_MAX))
1778
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1780
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1781
return (a_flag & NEAR_MIN) ? 2 : -2;
1782
return (a_flag & NEAR_MIN) ? 1 : -1;
1784
if (b_flag & (NEAR_MIN | NEAR_MAX))
1785
return (b_flag & NEAR_MIN) ? -2 : 2;
1786
return 0; // The elements where equal
1790
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1792
SEL_ARG tmp_link,*next_arg,*root;
1793
next_arg= &tmp_link;
1794
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1796
next_arg->next=0; // Fix last link
1797
tmp_link.next->prev=0; // Fix first link
1798
if (root) // If not OOM
3309
4848
if (*key1 || *key2)
3311
4850
if (*key1 && !(*key1)->simple_key())
3312
flag|=CLONE_KEY1_MAYBE;
4851
flag|=CLONE_KEY1_MAYBE;
3313
4852
if (*key2 && !(*key2)->simple_key())
3314
flag|=CLONE_KEY2_MAYBE;
4853
flag|=CLONE_KEY2_MAYBE;
3315
4854
*key1=key_and(param, *key1, *key2, flag);
3316
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
4855
if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
3318
tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
4857
tree1->type= SEL_TREE::IMPOSSIBLE;
3321
4860
result_keys.set(key1 - tree1->keys);
4862
if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4863
(*key1)->test_use_count(*key1);
3324
4867
tree1->keys_map= result_keys;
3325
4868
/* dispose index_merge if there is a "range" option */
3326
4869
if (result_keys.any())
3328
tree1->merges.empty();
4871
tree1->merges.clear();
3332
4875
/* ok, both trees are index_merge trees */
3333
imerge_list_and_list(&tree1->merges, &tree2->merges);
4876
imerge_list_and_list(tree1->merges, tree2->merges);
4882
Check if two SEL_TREES can be combined into one (i.e. a single key range
4883
read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
4887
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4888
RANGE_OPT_PARAM* param)
4890
key_map common_keys= tree1->keys_map;
4891
common_keys&= tree2->keys_map;
4893
if (common_keys.none())
4896
/* trees have a common key, check if they refer to same key part */
4897
SEL_ARG **key1,**key2;
4898
for (uint32_t key_no=0; key_no < param->keys; key_no++)
4900
if (common_keys.test(key_no))
4902
key1= tree1->keys + key_no;
4903
key2= tree2->keys + key_no;
4904
if ((*key1)->part == (*key2)->part)
4915
Remove the trees that are not suitable for record retrieval.
4917
param Range analysis parameter
4918
tree Tree to be processed, tree->type is KEY or KEY_SMALLER
4921
This function walks through tree->keys[] and removes the SEL_ARG* trees
4922
that are not "maybe" trees (*) and cannot be used to construct quick range
4924
(*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
4925
these types here as well.
4927
A SEL_ARG* tree cannot be used to construct quick select if it has
4928
tree->part != 0. (e.g. it could represent "keypart2 < const").
4930
WHY THIS FUNCTION IS NEEDED
4932
Normally we allow construction of SEL_TREE objects that have SEL_ARG
4933
trees that do not allow quick range select construction. For example for
4934
" keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4935
tree1= SEL_TREE { SEL_ARG{keypart1=1} }
4936
tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
4938
call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4941
There is an exception though: when we construct index_merge SEL_TREE,
4942
any SEL_ARG* tree that cannot be used to construct quick range select can
4943
be removed, because current range analysis code doesn't provide any way
4944
that tree could be later combined with another tree.
4945
Consider an example: we should not construct
4947
merges = SEL_IMERGE {
4948
SEL_TREE(t.key1part1 = 1),
4949
SEL_TREE(t.key2part2 = 2) -- (*)
4953
- (*) cannot be used to construct quick range select,
4954
- There is no execution path that would cause (*) to be converted to
4955
a tree that could be used.
4957
The latter is easy to verify: first, notice that the only way to convert
4958
(*) into a usable tree is to call tree_and(something, (*)).
4960
Second look at what tree_and/tree_or function would do when passed a
4961
SEL_TREE that has the structure like st1 tree has, and conlcude that
4962
tree_and(something, (*)) will not be called.
4965
0 Ok, some suitable trees left
4966
1 No tree->keys[] left.
4969
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree)
4972
for (uint32_t i=0; i < param->keys; i++)
4976
if (tree->keys[i]->part)
4978
tree->keys[i]= NULL;
4979
tree->keys_map.reset(i);
4990
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4992
if (!tree1 || !tree2)
4994
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4996
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4998
if (tree1->type == SEL_TREE::MAYBE)
4999
return(tree1); // Can't use this
5000
if (tree2->type == SEL_TREE::MAYBE)
5003
SEL_TREE *result= 0;
5004
key_map result_keys;
5005
result_keys.reset();
5006
if (sel_trees_can_be_ored(tree1, tree2, param))
5008
/* Join the trees key per key */
5009
SEL_ARG **key1,**key2,**end;
5010
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
5011
key1 != end ; key1++,key2++)
5013
*key1=key_or(param, *key1, *key2);
5016
result=tree1; // Added to tree1
5017
result_keys.set(key1 - tree1->keys);
5019
if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
5020
(*key1)->test_use_count(*key1);
5025
result->keys_map= result_keys;
5029
/* ok, two trees have KEY type but cannot be used without index merge */
5030
if ((tree1->merges.empty() == true) && (tree2->merges.empty() == true))
5032
if (param->remove_jump_scans)
5034
bool no_trees= remove_nonrange_trees(param, tree1);
5035
no_trees= no_trees || remove_nonrange_trees(param, tree2);
5037
return(new SEL_TREE(SEL_TREE::ALWAYS));
5040
/* both trees are "range" trees, produce new index merge structure. */
5041
result= new SEL_TREE();
5042
SEL_IMERGE *merge= new SEL_IMERGE();
5043
result->merges.push_back(merge);
5045
if( merge->or_sel_tree(param, tree1) || merge->or_sel_tree(param, tree2))
5048
result->type= tree1->type;
5050
else if ((tree1->merges.empty() == false) && (tree2->merges.empty() == false))
5052
if (imerge_list_or_list(param, tree1->merges, tree2->merges))
5053
result= new SEL_TREE(SEL_TREE::ALWAYS);
5059
/* one tree is index merge tree and another is range tree */
5060
if (tree1->merges.empty() == true)
5061
std::swap(tree1, tree2);
5063
if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
5064
return(new SEL_TREE(SEL_TREE::ALWAYS));
5066
/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
5067
if (imerge_list_or_tree(param, tree1->merges, tree2))
5068
result= new SEL_TREE(SEL_TREE::ALWAYS);
3339
5077
/* And key trees where key1->part < key2 -> part */
3341
static optimizer::SEL_ARG *
3342
and_all_keys(optimizer::RangeParameter *param,
3343
optimizer::SEL_ARG *key1,
3344
optimizer::SEL_ARG *key2,
5080
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
3345
5081
uint32_t clone_flag)
3347
optimizer::SEL_ARG *next= NULL;
3348
5084
ulong use_count=key1->use_count;
3350
5086
if (key1->elements != 1)
5262
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5282
if (key1->part != key2->part)
5286
return 0; // Can't optimize this
5289
// If one of the key is MAYBE_KEY then the found region may be bigger
5290
if (key1->type == SEL_ARG::MAYBE_KEY)
5296
if (key2->type == SEL_ARG::MAYBE_KEY)
5303
if (key1->use_count > 0)
5305
if (key2->use_count == 0 || key1->elements > key2->elements)
5307
std::swap(key1,key2);
5309
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5313
// Add tree at key2 to tree at key1
5314
bool key2_shared=key2->use_count != 0;
5315
key1->maybe_flag|=key2->maybe_flag;
5317
for (key2=key2->first(); key2; )
5319
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5324
tmp=key1->first(); // tmp.min > key2.min
5327
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5328
{ // Found tmp.max < key2.min
5329
SEL_ARG *next=tmp->next;
5330
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5332
// Join near ranges like tmp.max < 0 and key2.min >= 0
5333
SEL_ARG *key2_next=key2->next;
5336
if (!(key2=new SEL_ARG(*key2)))
5337
return 0; // out of memory
5338
key2->increment_use_count(key1->use_count+1);
5339
key2->next=key2_next; // New copy of key2
5341
key2->copy_min(tmp);
5342
if (!(key1=key1->tree_delete(tmp)))
5343
{ // Only one key in tree
5350
if (!(tmp=next)) // tmp.min > key2.min
5351
break; // Copy rest of key2
5354
{ // tmp.min > key2.min
5356
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5358
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5359
{ // ranges are connected
5360
tmp->copy_min_to_min(key2);
5361
key1->merge_flags(key2);
5362
if (tmp->min_flag & NO_MIN_RANGE &&
5363
tmp->max_flag & NO_MAX_RANGE)
5365
if (key1->maybe_flag)
5366
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5369
key2->increment_use_count(-1); // Free not used tree
5375
SEL_ARG *next=key2->next; // Keys are not overlapping
5378
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5381
key1=key1->insert(cpy);
5382
key2->increment_use_count(key1->use_count+1);
5385
key1=key1->insert(key2); // Will destroy key2_root
5392
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5393
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5395
if (tmp->is_same(key2))
5397
tmp->merge_flags(key2); // Copy maybe flags
5398
key2->increment_use_count(-1); // Free not used tree
5403
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5404
eq_tree(last->next->next_key_part,key2->next_key_part))
5408
key1=key1->tree_delete(save);
5410
last->copy_min(tmp);
5411
if (last->copy_min(key2) || last->copy_max(key2))
5414
for (; key2 ; key2=key2->next)
5415
key2->increment_use_count(-1); // Free not used tree
5416
if (key1->maybe_flag)
5417
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5425
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5426
{ // tmp.min <= x < key2.min
5427
SEL_ARG *new_arg=tmp->clone_first(key2);
5430
if ((new_arg->next_key_part= key1->next_key_part))
5431
new_arg->increment_use_count(key1->use_count+1);
5432
tmp->copy_min_to_min(key2);
5433
key1=key1->insert(new_arg);
5436
// tmp.min >= key2.min && tmp.min <= key2.max
5437
SEL_ARG key(*key2); // Get copy we can modify
5440
if (tmp->cmp_min_to_min(&key) > 0)
5441
{ // key.min <= x < tmp.min
5442
SEL_ARG *new_arg=key.clone_first(tmp);
5445
if ((new_arg->next_key_part=key.next_key_part))
5446
new_arg->increment_use_count(key1->use_count+1);
5447
key1=key1->insert(new_arg);
5449
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5450
{ // tmp.min. <= x <= tmp.max
5451
tmp->maybe_flag|= key.maybe_flag;
5452
key.increment_use_count(key1->use_count+1);
5453
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5454
if (!cmp) // Key2 is ready
5456
key.copy_max_to_min(tmp);
5457
if (!(tmp=tmp->next))
5459
SEL_ARG *tmp2= new SEL_ARG(key);
5462
key1=key1->insert(tmp2);
5466
if (tmp->cmp_min_to_max(&key) > 0)
5468
SEL_ARG *tmp2= new SEL_ARG(key);
5471
key1=key1->insert(tmp2);
5477
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5480
tmp->copy_max_to_min(&key);
5481
tmp->increment_use_count(key1->use_count+1);
5482
/* Increment key count as it may be used for next loop */
5483
key.increment_use_count(1);
5484
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5485
key1=key1->insert(new_arg);
5495
SEL_ARG *next=key2->next;
5498
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5501
key2->increment_use_count(key1->use_count+1);
5502
key1=key1->insert(tmp);
5505
key1=key1->insert(key2); // Will destroy key2_root
5513
/* Compare if two trees are equal */
5515
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5519
if (!a || !b || !a->is_same(b))
5521
if (a->left != &null_element && b->left != &null_element)
5523
if (!eq_tree(a->left,b->left))
5526
else if (a->left != &null_element || b->left != &null_element)
5528
if (a->right != &null_element && b->right != &null_element)
5530
if (!eq_tree(a->right,b->right))
5533
else if (a->right != &null_element || b->right != &null_element)
5535
if (a->next_key_part != b->next_key_part)
5537
if (!a->next_key_part != !b->next_key_part ||
5538
!eq_tree(a->next_key_part, b->next_key_part))
5546
SEL_ARG::insert(SEL_ARG *key)
5548
SEL_ARG *element, **par= NULL, *last_element= NULL;
5550
for (element= this; element != &null_element ; )
5552
last_element=element;
5553
if (key->cmp_min_to_min(element) > 0)
5555
par= &element->right; element= element->right;
5559
par = &element->left; element= element->left;
5563
key->parent=last_element;
5565
if (par == &last_element->left)
5567
key->next=last_element;
5568
if ((key->prev=last_element->prev))
5569
key->prev->next=key;
5570
last_element->prev=key;
5574
if ((key->next=last_element->next))
5575
key->next->prev=key;
5576
key->prev=last_element;
5577
last_element->next=key;
5579
key->left=key->right= &null_element;
5580
SEL_ARG *root=rb_insert(key); // rebalance tree
5581
root->use_count=this->use_count; // copy root info
5582
root->elements= this->elements+1;
5583
root->maybe_flag=this->maybe_flag;
5589
** Find best key with min <= given key
5590
** Because the call context this should never return 0 to get_range
5594
SEL_ARG::find_range(SEL_ARG *key)
5596
SEL_ARG *element=this,*found=0;
5600
if (element == &null_element)
5602
int cmp=element->cmp_min_to_min(key);
5608
element=element->right;
5611
element=element->left;
5617
Remove a element from the tree
5621
key Key that is to be deleted from tree (this)
5624
This also frees all sub trees that is used by the element
5627
root of new tree (with key deleted)
5631
SEL_ARG::tree_delete(SEL_ARG *key)
5633
enum leaf_color remove_color;
5634
SEL_ARG *root,*nod,**par,*fix_par;
5639
/* Unlink from list */
5641
key->prev->next=key->next;
5643
key->next->prev=key->prev;
5644
key->increment_use_count(-1);
5648
par=key->parent_ptr();
5650
if (key->left == &null_element)
5652
*par=nod=key->right;
5653
fix_par=key->parent;
5654
if (nod != &null_element)
5655
nod->parent=fix_par;
5656
remove_color= key->color;
5658
else if (key->right == &null_element)
5660
*par= nod=key->left;
5661
nod->parent=fix_par=key->parent;
5662
remove_color= key->color;
5666
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5667
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5668
fix_par=tmp->parent;
5669
if (nod != &null_element)
5670
nod->parent=fix_par;
5671
remove_color= tmp->color;
5673
tmp->parent=key->parent; // Move node in place of key
5674
(tmp->left=key->left)->parent=tmp;
5675
if ((tmp->right=key->right) != &null_element)
5676
tmp->right->parent=tmp;
5677
tmp->color=key->color;
5679
if (fix_par == key) // key->right == key->next
5680
fix_par=tmp; // new parent of nod
5683
if (root == &null_element)
5684
return 0; // Maybe root later
5685
if (remove_color == BLACK)
5686
root=rb_delete_fixup(root,nod,fix_par);
5688
test_rb_tree(root,root->parent);
5689
#endif /* EXTRA_DEBUG */
5691
root->use_count=this->use_count; // Fix root counters
5692
root->elements=this->elements-1;
5693
root->maybe_flag=this->maybe_flag;
5698
/* Functions to fix up the tree after insert and delete */
5700
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5702
SEL_ARG *y=leaf->right;
5703
leaf->right=y->left;
5704
if (y->left != &null_element)
5705
y->left->parent=leaf;
5706
if (!(y->parent=leaf->parent))
5709
*leaf->parent_ptr()=y;
5714
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5716
SEL_ARG *y=leaf->left;
5717
leaf->left=y->right;
5718
if (y->right != &null_element)
5719
y->right->parent=leaf;
5720
if (!(y->parent=leaf->parent))
5723
*leaf->parent_ptr()=y;
5730
SEL_ARG::rb_insert(SEL_ARG *leaf)
5732
SEL_ARG *y,*par,*par2,*root;
5733
root= this; root->parent= 0;
5736
while (leaf != root && (par= leaf->parent)->color == RED)
5737
{ // This can't be root or 1 level under
5738
if (par == (par2= leaf->parent->parent)->left)
5741
if (y->color == RED)
5746
leaf->color=RED; /* And the loop continues */
5750
if (leaf == par->right)
5752
left_rotate(&root,leaf->parent);
5753
par=leaf; /* leaf is now parent to old leaf */
5757
right_rotate(&root,par2);
5764
if (y->color == RED)
5769
leaf->color=RED; /* And the loop continues */
5773
if (leaf == par->left)
5775
right_rotate(&root,par);
5780
left_rotate(&root,par2);
5787
test_rb_tree(root,root->parent);
5788
#endif /* EXTRA_DEBUG */
5794
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5800
while (x != root && x->color == SEL_ARG::BLACK)
5805
if (w->color == SEL_ARG::RED)
5807
w->color=SEL_ARG::BLACK;
5808
par->color=SEL_ARG::RED;
5809
left_rotate(&root,par);
5812
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5814
w->color=SEL_ARG::RED;
5819
if (w->right->color == SEL_ARG::BLACK)
5821
w->left->color=SEL_ARG::BLACK;
5822
w->color=SEL_ARG::RED;
5823
right_rotate(&root,w);
5826
w->color=par->color;
5827
par->color=SEL_ARG::BLACK;
5828
w->right->color=SEL_ARG::BLACK;
5829
left_rotate(&root,par);
5837
if (w->color == SEL_ARG::RED)
5839
w->color=SEL_ARG::BLACK;
5840
par->color=SEL_ARG::RED;
5841
right_rotate(&root,par);
5844
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5846
w->color=SEL_ARG::RED;
5851
if (w->left->color == SEL_ARG::BLACK)
5853
w->right->color=SEL_ARG::BLACK;
5854
w->color=SEL_ARG::RED;
5855
left_rotate(&root,w);
5858
w->color=par->color;
5859
par->color=SEL_ARG::BLACK;
5860
w->left->color=SEL_ARG::BLACK;
5861
right_rotate(&root,par);
5868
x->color=SEL_ARG::BLACK;
5873
/* Test that the properties for a red-black tree hold */
5876
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5878
int count_l,count_r;
5880
if (element == &null_element)
5881
return 0; // Found end of tree
5882
if (element->parent != parent)
5884
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5887
if (element->color == SEL_ARG::RED &&
5888
(element->left->color == SEL_ARG::RED ||
5889
element->right->color == SEL_ARG::RED))
5891
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5894
if (element->left == element->right && element->left != &null_element)
5896
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5899
count_l=test_rb_tree(element->left,element);
5900
count_r=test_rb_tree(element->right,element);
5901
if (count_l >= 0 && count_r >= 0)
5903
if (count_l == count_r)
5904
return count_l+(element->color == SEL_ARG::BLACK);
5905
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5908
return -1; // Error, no more warnings
5913
Count how many times SEL_ARG graph "root" refers to its part "key"
5916
count_key_part_usage()
5917
root An RB-Root node in a SEL_ARG graph.
5918
key Another RB-Root node in that SEL_ARG graph.
5921
The passed "root" node may refer to "key" node via root->next_key_part,
5924
This function counts how many times the node "key" is referred (via
5925
SEL_ARG::next_key_part) by
5926
- intervals of RB-tree pointed by "root",
5927
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5928
intervals of RB-tree pointed by "root",
5931
Here is an example (horizontal links represent next_key_part pointers,
5932
vertical links - next/prev prev pointers):
5935
|root|-----------------+
5939
+----+ +---+ $ | +---+ Here the return value
5940
| |- ... -| |---$-+--+->|key| will be 4.
5941
+----+ +---+ $ | | +---+
5946
| |---| |---------+ |
5953
Number of links to "key" from nodes reachable from "root".
5956
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5959
for (root=root->first(); root ; root=root->next)
5961
if (root->next_key_part)
5963
if (root->next_key_part == key)
5965
if (root->next_key_part->part < key->part)
5966
count+=count_key_part_usage(root->next_key_part,key);
5974
Check if SEL_ARG::use_count value is correct
5977
SEL_ARG::test_use_count()
5978
root The root node of the SEL_ARG graph (an RB-tree root node that
5979
has the least value of sel_arg->part in the entire graph, and
5980
thus is the "origin" of the graph)
5983
Check if SEL_ARG::use_count value is correct. See the definition of
5984
use_count for what is "correct".
5987
void SEL_ARG::test_use_count(SEL_ARG *root)
5990
if (this == root && use_count != 1)
5992
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5995
if (this->type != SEL_ARG::KEY_RANGE)
5997
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
6000
if (pos->next_key_part)
6002
ulong count=count_key_part_usage(root,pos->next_key_part);
6003
if (count > pos->next_key_part->use_count)
6005
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
6006
"should be %lu", (long unsigned int)pos,
6007
pos->next_key_part->use_count, count);
6010
pos->next_key_part->test_use_count(root);
6013
if (e_count != elements)
6014
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
6015
e_count, elements, (long unsigned int) this);
3534
6020
/****************************************************************************
3535
6021
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3536
6022
****************************************************************************/
4350
Range sequence interface implementation for array<QuickRange>: initialize
6848
Perform key scans for all used indexes (except CPK), get rowids and merge
6849
them into an ordered non-recurrent sequence of rowids.
6851
The merge/duplicate removal is performed using Unique class. We put all
6852
rowids into Unique, get the sorted sequence and destroy the Unique.
6854
If table has a clustered primary key that covers all rows (true for bdb
6855
and innodb currently) and one of the index_merge scans is a scan on PK,
6856
then rows that will be retrieved by PK scan are not put into Unique and
6857
primary key scan is not performed here, it is performed later separately.
6864
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6866
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6867
QUICK_RANGE_SELECT* cur_quick;
6870
handler *file= head->file;
6872
file->extra(HA_EXTRA_KEYREAD);
6873
head->prepare_for_position();
6875
cur_quick_it.rewind();
6876
cur_quick= cur_quick_it++;
6877
assert(cur_quick != 0);
6880
We reuse the same instance of handler so we need to call both init and
6883
if (cur_quick->init() || cur_quick->reset())
6886
unique= new Unique(refpos_order_cmp, (void *)file,
6888
session->variables.sortbuff_size);
6893
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6895
cur_quick->range_end();
6896
cur_quick= cur_quick_it++;
6900
if (cur_quick->file->inited != handler::NONE)
6901
cur_quick->file->ha_index_end();
6902
if (cur_quick->init() || cur_quick->reset())
6908
if (result != HA_ERR_END_OF_FILE)
6910
cur_quick->range_end();
6916
if (session->killed)
6919
/* skip row if it will be retrieved by clustered PK scan */
6920
if (pk_quick_select && pk_quick_select->row_in_ranges())
6923
cur_quick->file->position(cur_quick->record);
6924
result= unique->unique_add((char*)cur_quick->file->ref);
6930
/* ok, all row ids are in Unique */
6931
result= unique->get(head);
6933
doing_pk_scan= false;
6934
/* index_merge currently doesn't support "using index" at all */
6935
file->extra(HA_EXTRA_NO_KEYREAD);
6936
/* start table scan */
6937
init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
6943
Get next row for index_merge.
6945
The rows are read from
6946
1. rowids stored in Unique.
6947
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6948
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6951
int QUICK_INDEX_MERGE_SELECT::get_next()
6956
return(pk_quick_select->get_next());
6958
if ((result= read_record.read_record(&read_record)) == -1)
6960
result= HA_ERR_END_OF_FILE;
6961
end_read_record(&read_record);
6962
/* All rows from Unique have been retrieved, do a clustered PK scan */
6963
if (pk_quick_select)
6965
doing_pk_scan= true;
6966
if ((result= pk_quick_select->init()) ||
6967
(result= pk_quick_select->reset()))
6969
return(pk_quick_select->get_next());
6978
Retrieve next record.
6980
QUICK_ROR_INTERSECT_SELECT::get_next()
6983
Invariant on enter/exit: all intersected selects have retrieved all index
6984
records with rowid <= some_rowid_val and no intersected select has
6985
retrieved any index records with rowid > some_rowid_val.
6986
We start fresh and loop until we have retrieved the same rowid in each of
6987
the key scans or we got an error.
6989
If a Clustered PK scan is present, it is used only to check if row
6990
satisfies its condition (and never used for row retrieval).
6994
other - Error code if any error occurred.
6997
int QUICK_ROR_INTERSECT_SELECT::get_next()
6999
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
7000
QUICK_RANGE_SELECT* quick;
7002
uint32_t last_rowid_count=0;
7006
/* Get a rowid for first quick and save it as a 'candidate' */
7008
error= quick->get_next();
7011
while (!error && !cpk_quick->row_in_ranges())
7012
error= quick->get_next();
7017
quick->file->position(quick->record);
7018
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7019
last_rowid_count= 1;
7021
while (last_rowid_count < quick_selects.elements)
7023
if (!(quick= quick_it++))
7031
if ((error= quick->get_next()))
7033
quick->file->position(quick->record);
7034
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
7037
/* Ok, current select 'caught up' and returned ref >= cur_ref */
7040
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
7043
while (!cpk_quick->row_in_ranges())
7045
if ((error= quick->get_next()))
7049
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7050
last_rowid_count= 1;
7054
/* current 'candidate' row confirmed by this select */
7059
/* We get here if we got the same row ref in all scans. */
7060
if (need_to_fetch_row)
7061
error= head->file->rnd_pos(head->record[0], last_rowid);
7062
} while (error == HA_ERR_RECORD_DELETED);
7068
Retrieve next record.
7070
QUICK_ROR_UNION_SELECT::get_next()
7073
Enter/exit invariant:
7074
For each quick select in the queue a {key,rowid} tuple has been
7075
retrieved but the corresponding row hasn't been passed to output.
7079
other - Error code if any error occurred.
7082
int QUICK_ROR_UNION_SELECT::get_next()
7085
QUICK_SELECT_I *quick;
7093
return(HA_ERR_END_OF_FILE);
7094
/* Ok, we have a queue with >= 1 scans */
7096
quick= queue->top();
7097
memcpy(cur_rowid, quick->last_rowid, rowid_length);
7099
/* put into queue rowid from the same stream as top element */
7100
if ((error= quick->get_next()))
7102
if (error != HA_ERR_END_OF_FILE)
7108
quick->save_last_pos();
7113
if (!have_prev_rowid)
7115
/* No rows have been returned yet */
7117
have_prev_rowid= true;
7120
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
7124
cur_rowid= prev_rowid;
7127
error= head->file->rnd_pos(quick->record, prev_rowid);
7128
} while (error == HA_ERR_RECORD_DELETED);
7133
int QUICK_RANGE_SELECT::reset()
7136
unsigned char *mrange_buff;
7138
HANDLER_BUFFER empty_buf;
7140
cur_range= (QUICK_RANGE**) ranges.buffer;
7142
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
7145
/* Allocate buffer if we need one but haven't allocated it yet */
7146
if (mrr_buf_size && !mrr_buf_desc)
7148
buf_size= mrr_buf_size;
7149
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7150
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7151
&mrange_buff, buf_size,
7154
/* Try to shrink the buffers until both are 0. */
7158
return(HA_ERR_OUT_OF_MEM);
7160
/* Initialize the handler buffer. */
7161
mrr_buf_desc->buffer= mrange_buff;
7162
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7163
mrr_buf_desc->end_of_used_area= mrange_buff;
7167
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7170
mrr_flags |= HA_MRR_SORTED;
7171
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7172
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7173
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7180
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4353
7183
quick_range_seq_init()
4354
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7184
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4355
7185
n_ranges Number of ranges in the sequence (ignored)
4356
7186
flags MRR flags (currently not used)
4383
7213
1 No more ranges in the sequence
4385
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7216
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4387
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7218
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4389
7220
if (ctx->cur == ctx->last)
4390
7221
return 1; /* no more ranges */
4392
optimizer::QuickRange *cur= *(ctx->cur);
7223
QUICK_RANGE *cur= *(ctx->cur);
4393
7224
key_range *start_key= &range->start_key;
4394
key_range *end_key= &range->end_key;
7225
key_range *end_key= &range->end_key;
4396
start_key->key= cur->min_key;
7227
start_key->key= cur->min_key;
4397
7228
start_key->length= cur->min_length;
4398
7229
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;
7230
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7231
(cur->flag & EQ_RANGE) ?
7232
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7233
end_key->key= cur->max_key;
7234
end_key->length= cur->max_length;
4404
7235
end_key->keypart_map= cur->max_keypart_map;
4406
7237
We use HA_READ_AFTER_KEY here because if we are reading on a key
4407
7238
prefix. We want to find all keys with this prefix.
4409
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7240
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4411
7242
range->range_flag= cur->flag;
7249
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7252
mrr_persistent_flag_storage()
7253
seq Range sequence being traversed
7257
MRR/NDB implementation needs to store some bits for each range. This
7258
function returns a reference to the "range_flag" associated with the
7261
This function should be removed when we get a proper MRR/NDB
7265
Reference to range_flag associated with range number #idx
7268
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7270
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7271
return ctx->first[idx]->flag;
7276
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7279
mrr_get_ptr_by_idx()
7280
seq Range sequence bening traversed
7281
idx Number of the range
7284
An extension of MRR range sequence interface needed by NDB: return the
7285
data associated with the given range.
7287
A proper MRR interface implementer is supposed to store and return
7288
range-associated data. NDB stores number of the range instead. So this
7289
is a helper function that translates range number to range associated
7292
This function does nothing, as currrently there is only one user of the
7293
MRR interface - the quick range select code, and this user doesn't need
7294
to use range-associated data.
7297
Reference to range-associated data
7300
char* &mrr_get_ptr_by_idx(range_seq_t, uint32_t)
7308
Get next possible record using quick-struct.
7311
QUICK_RANGE_SELECT::get_next()
7314
Record is read into table->record[0]
7318
HA_ERR_END_OF_FILE No (more) rows in range
7322
int QUICK_RANGE_SELECT::get_next()
7325
if (in_ror_merged_scan)
7328
We don't need to signal the bitmap change as the bitmap is always the
7329
same for this head->file
7331
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
7334
int result= file->multi_range_read_next(&dummy);
7336
if (in_ror_merged_scan)
7338
/* Restore bitmaps set on entry */
7339
head->column_bitmaps_set(save_read_set, save_write_set);
7346
Get the next record with a different prefix.
7349
QUICK_RANGE_SELECT::get_next_prefix()
7350
prefix_length length of cur_prefix
7351
cur_prefix prefix of a key to be searched for
7354
Each subsequent call to the method retrieves the first record that has a
7355
prefix with length prefix_length different from cur_prefix, such that the
7356
record with the new prefix is within the ranges described by
7357
this->ranges. The record found is stored into the buffer pointed by
7359
The method is useful for GROUP-BY queries with range conditions to
7360
discover the prefix of the next group that satisfies the range conditions.
7363
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7364
methods should be unified into a more general one to reduce code
7369
HA_ERR_END_OF_FILE if returned all keys
7370
other if some error occurred
7373
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7374
key_part_map keypart_map,
7375
unsigned char *cur_prefix)
7380
key_range start_key, end_key;
7383
/* Read the next record in the same range with prefix after cur_prefix. */
7384
assert(cur_prefix != 0);
7385
result= file->index_read_map(record, cur_prefix, keypart_map,
7387
if (result || (file->compare_key(file->end_range) <= 0))
7391
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7394
/* Ranges have already been used up before. None is left for read. */
7396
return HA_ERR_END_OF_FILE;
7398
last_range= *(cur_range++);
7400
start_key.key= (const unsigned char*) last_range->min_key;
7401
start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7402
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7403
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7404
(last_range->flag & EQ_RANGE) ?
7405
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7406
end_key.key= (const unsigned char*) last_range->max_key;
7407
end_key.length= cmin(last_range->max_length, (uint16_t)prefix_length);
7408
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7410
We use READ_AFTER_KEY here because if we are reading on a key
7411
prefix we want to find all keys with this prefix
7413
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7416
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7417
last_range->max_keypart_map ? &end_key : 0,
7418
test(last_range->flag & EQ_RANGE),
7420
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7421
last_range= 0; // Stop searching
7423
if (result != HA_ERR_END_OF_FILE)
7425
last_range= 0; // No matching rows; go to next range
7431
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7434
It is assumed that currently a scan is being done on another index
7435
which reads all necessary parts of the index that is scanned by this
7437
The implementation does a binary search on sorted array of disjoint
7438
ranges, without taking size of range into account.
7440
This function is used to filter out clustered PK scan rows in
7441
index_merge quick select.
7444
true if current row will be retrieved by this quick select
7448
bool QUICK_RANGE_SELECT::row_in_ranges()
7452
uint32_t max= ranges.elements - 1;
7453
uint32_t mid= (max + min)/2;
7457
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7459
/* current row value > mid->max */
7464
mid= (min + max) / 2;
7466
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7467
return (!cmp_next(res) && !cmp_prev(res));
7471
This is a hack: we inherit from QUICK_SELECT so that we can use the
7472
get_next() interface, but we have to hold a pointer to the original
7473
QUICK_SELECT because its data are used all over the place. What
7474
should be done is to factor out the data that is needed into a base
7475
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7476
which handle the ranges and implement the get_next() function. But
7477
for now, this seems to work right at least.
7480
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7481
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7485
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7486
QUICK_RANGE **end_range= pr + ranges.elements;
7487
for (; pr!=end_range; pr++)
7488
rev_ranges.push_front(*pr);
7490
/* Remove EQ_RANGE flag for keys that are not using the full key */
7491
for (r = rev_it++; r; r = rev_it++)
7493
if ((r->flag & EQ_RANGE) &&
7494
head->key_info[index].key_length != r->max_length)
7495
r->flag&= ~EQ_RANGE;
7498
q->dont_free=1; // Don't free shared mem
7503
int QUICK_SELECT_DESC::get_next()
7505
/* The max key is handled as follows:
7506
* - if there is NO_MAX_RANGE, start at the end and move backwards
7507
* - if it is an EQ_RANGE, which means that max key covers the entire
7508
* key, go directly to the key and read through it (sorting backwards is
7509
* same as sorting forwards)
7510
* - if it is NEAR_MAX, go to the key or next, step back once, and
7512
* - otherwise (not NEAR_MAX == include the key), go after the key,
7513
* step back once, and move backwards
7520
{ // Already read through key
7521
result = ((last_range->flag & EQ_RANGE)
7522
? file->index_next_same(record, last_range->min_key,
7523
last_range->min_length) :
7524
file->index_prev(record));
7527
if (cmp_prev(*rev_it.ref()) == 0)
7530
else if (result != HA_ERR_END_OF_FILE)
7534
if (!(last_range= rev_it++))
7535
return HA_ERR_END_OF_FILE; // All ranges used
7537
if (last_range->flag & NO_MAX_RANGE) // Read last record
7540
if ((local_error=file->index_last(record)))
7541
return(local_error); // Empty table
7542
if (cmp_prev(last_range) == 0)
7544
last_range= 0; // No match; go to next range
7548
if (last_range->flag & EQ_RANGE)
7550
result = file->index_read_map(record, last_range->max_key,
7551
last_range->max_keypart_map,
7556
assert(last_range->flag & NEAR_MAX ||
7557
range_reads_after_key(last_range));
7558
result=file->index_read_map(record, last_range->max_key,
7559
last_range->max_keypart_map,
7560
((last_range->flag & NEAR_MAX) ?
7561
HA_READ_BEFORE_KEY :
7562
HA_READ_PREFIX_LAST_OR_PREV));
7566
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7568
last_range= 0; // Not found, to next range
7571
if (cmp_prev(last_range) == 0)
7573
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7574
last_range= 0; // Stop searching
7575
return 0; // Found key is in range
7577
last_range= 0; // To next range
7583
Compare if found key is over max-value
7584
Returns 0 if key <= range->max_key
7585
TODO: Figure out why can't this function be as simple as cmp_prev().
7588
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7590
if (range_arg->flag & NO_MAX_RANGE)
7591
return 0; /* key can't be to large */
7593
KEY_PART *key_part=key_parts;
7594
uint32_t store_length;
7596
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7598
key+= store_length, key_part++)
7601
store_length= key_part->store_length;
7602
if (key_part->null_bit)
7606
if (!key_part->field->is_null())
7610
else if (key_part->field->is_null())
7612
key++; // Skip null byte
7615
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7620
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7625
Returns 0 if found key is inside range (found key >= range->min_key).
7628
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7631
if (range_arg->flag & NO_MIN_RANGE)
7632
return 0; /* key can't be to small */
7634
cmp= key_cmp(key_part_info, range_arg->min_key,
7635
range_arg->min_length);
7636
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7638
return 1; // outside of range
7643
* true if this range will require using HA_READ_AFTER_KEY
7644
See comment in get_next() about this
7647
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7649
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7650
!(range_arg->flag & EQ_RANGE) ||
7651
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7655
void QUICK_RANGE_SELECT::add_info_string(String *str)
7657
KEY *key_info= head->key_info + index;
7658
str->append(key_info->name);
7661
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7663
QUICK_RANGE_SELECT *quick;
7665
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7666
str->append(STRING_WITH_LEN("sort_union("));
7667
while ((quick= it++))
7673
quick->add_info_string(str);
7675
if (pk_quick_select)
7678
pk_quick_select->add_info_string(str);
7683
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7686
QUICK_RANGE_SELECT *quick;
7687
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7688
str->append(STRING_WITH_LEN("intersect("));
7689
while ((quick= it++))
7691
KEY *key_info= head->key_info + quick->index;
7696
str->append(key_info->name);
7700
KEY *key_info= head->key_info + cpk_quick->index;
7702
str->append(key_info->name);
7707
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7710
QUICK_SELECT_I *quick;
7711
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7712
str->append(STRING_WITH_LEN("union("));
7713
while ((quick= it++))
7719
quick->add_info_string(str);
7725
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7726
String *used_lengths)
7730
KEY *key_info= head->key_info + index;
7731
key_names->append(key_info->name);
7732
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7733
used_lengths->append(buf, length);
7736
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7737
String *used_lengths)
7742
QUICK_RANGE_SELECT *quick;
7744
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7745
while ((quick= it++))
7751
key_names->append(',');
7752
used_lengths->append(',');
7755
KEY *key_info= head->key_info + quick->index;
7756
key_names->append(key_info->name);
7757
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7758
used_lengths->append(buf, length);
7760
if (pk_quick_select)
7762
KEY *key_info= head->key_info + pk_quick_select->index;
7763
key_names->append(',');
7764
key_names->append(key_info->name);
7765
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7766
used_lengths->append(',');
7767
used_lengths->append(buf, length);
7771
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7772
String *used_lengths)
7777
QUICK_RANGE_SELECT *quick;
7778
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7779
while ((quick= it++))
7781
KEY *key_info= head->key_info + quick->index;
7786
key_names->append(',');
7787
used_lengths->append(',');
7789
key_names->append(key_info->name);
7790
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7791
used_lengths->append(buf, length);
7796
KEY *key_info= head->key_info + cpk_quick->index;
7797
key_names->append(',');
7798
key_names->append(key_info->name);
7799
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7800
used_lengths->append(',');
7801
used_lengths->append(buf, length);
7805
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7806
String *used_lengths)
7809
QUICK_SELECT_I *quick;
7810
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7811
while ((quick= it++))
7817
used_lengths->append(',');
7818
key_names->append(',');
7820
quick->add_keys_and_lengths(key_names, used_lengths);
7825
/*******************************************************************************
7826
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7827
*******************************************************************************/
4417
7829
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);
7830
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7831
PARAM *param, uint32_t *param_idx);
7832
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7833
KEY_PART_INFO *first_non_group_part,
7834
KEY_PART_INFO *min_max_arg_part,
7835
KEY_PART_INFO *last_part, Session *session,
7836
unsigned char *key_infix, uint32_t *key_infix_len,
7837
KEY_PART_INFO **first_non_infix_part);
4434
7838
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
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,
7841
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7842
uint32_t group_key_parts, SEL_TREE *range_tree,
7843
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7844
bool have_min, bool have_max,
7845
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 */
8904
Construct new quick select for group queries with min/max.
8907
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8908
table The table being accessed
8909
join Descriptor of the current query
8910
have_min true if the query selects a MIN function
8911
have_max true if the query selects a MAX function
8912
min_max_arg_part The only argument field of all MIN/MAX functions
8913
group_prefix_len Length of all key parts in the group prefix
8914
prefix_key_parts All key parts in the group prefix
8915
index_info The index chosen for data access
8916
use_index The id of index_info
8917
read_cost Cost of this access method
8918
records Number of records returned
8919
key_infix_len Length of the key infix appended to the group prefix
8920
key_infix Infix of constants from equality predicates
8921
parent_alloc Memory pool for this and quick_prefix_select data
8927
QUICK_GROUP_MIN_MAX_SELECT::
8928
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8930
KEY_PART_INFO *min_max_arg_part_arg,
8931
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8932
uint32_t used_key_parts_arg, KEY *index_info_arg,
8933
uint32_t use_index, double read_cost_arg,
8934
ha_rows records_arg, uint32_t key_infix_len_arg,
8935
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8936
:join(join_arg), index_info(index_info_arg),
8937
group_prefix_len(group_prefix_len_arg),
8938
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8939
have_max(have_max_arg), seen_first_key(false),
8940
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8941
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8942
max_functions_it(NULL)
8947
record= head->record[0];
8948
tmp_record= head->record[1];
8949
read_time= read_cost_arg;
8950
records= records_arg;
8951
used_key_parts= used_key_parts_arg;
8952
real_key_parts= used_key_parts_arg;
8953
real_prefix_len= group_prefix_len + key_infix_len;
8955
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8958
We can't have parent_alloc set as the init function can't handle this case
8961
assert(!parent_alloc);
8964
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
8965
join->session->mem_root= &alloc;
8968
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8973
Do post-constructor initialization.
8976
QUICK_GROUP_MIN_MAX_SELECT::init()
8979
The method performs initialization that cannot be done in the constructor
8980
such as memory allocations that may fail. It allocates memory for the
8981
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8982
updated during execution.
8989
int QUICK_GROUP_MIN_MAX_SELECT::init()
8991
if (group_prefix) /* Already initialized. */
8994
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8997
We may use group_prefix to store keys with all select fields, so allocate
8998
enough space for it.
9000
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
9001
real_prefix_len + min_max_arg_len)))
9004
if (key_infix_len > 0)
9007
The memory location pointed to by key_infix will be deleted soon, so
9008
allocate a new buffer and copy the key_infix into it.
9010
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
9013
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
9014
this->key_infix= tmp_key_infix;
9017
if (min_max_arg_part)
9019
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
9024
if (!(min_functions= new List<Item_sum>))
9028
min_functions= NULL;
9031
if (!(max_functions= new List<Item_sum>))
9035
max_functions= NULL;
9037
Item_sum *min_max_item;
9038
Item_sum **func_ptr= join->sum_funcs;
9039
while ((min_max_item= *(func_ptr++)))
9041
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
9042
min_functions->push_back(min_max_item);
9043
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
9044
max_functions->push_back(min_max_item);
9049
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
9055
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
9060
min_max_ranges.elements= 0;
9066
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
9068
if (file->inited != handler::NONE)
9069
file->ha_index_end();
9070
if (min_max_arg_part)
9071
delete_dynamic(&min_max_ranges);
9072
free_root(&alloc,MYF(0));
9073
delete min_functions_it;
9074
delete max_functions_it;
9075
delete quick_prefix_select;
9080
Eventually create and add a new quick range object.
9083
QUICK_GROUP_MIN_MAX_SELECT::add_range()
9084
sel_range Range object from which a
9087
Construct a new QUICK_RANGE object from a SEL_ARG object, and
9088
add it to the array min_max_ranges. If sel_arg is an infinite
9089
range, e.g. (x < 5 or x > 4), then skip it and do not construct
9097
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
9100
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
9102
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
9103
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
9106
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
9107
!(sel_range->max_flag & NO_MAX_RANGE))
9109
if (sel_range->maybe_null &&
9110
sel_range->min_value[0] && sel_range->max_value[0])
9111
range_flag|= NULL_RANGE; /* IS NULL condition */
9112
else if (memcmp(sel_range->min_value, sel_range->max_value,
9113
min_max_arg_len) == 0)
9114
range_flag|= EQ_RANGE; /* equality condition */
9116
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
9117
make_keypart_map(sel_range->part),
9118
sel_range->max_value, min_max_arg_len,
9119
make_keypart_map(sel_range->part),
9123
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
9130
Opens the ranges if there are more conditions in quick_prefix_select than
9131
the ones used for jumping through the prefixes.
9134
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9137
quick_prefix_select is made over the conditions on the whole key.
9138
It defines a number of ranges of length x.
9139
However when jumping through the prefixes we use only the the first
9140
few most significant keyparts in the range key. However if there
9141
are more keyparts to follow the ones we are using we must make the
9142
condition on the key inclusive (because x < "ab" means
9143
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9144
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9146
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9148
if (quick_prefix_select &&
9149
group_prefix_len < quick_prefix_select->max_used_key_length)
9154
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9158
get_dynamic(arr, (unsigned char*)&range, inx);
9159
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9166
Determine the total number and length of the keys that will be used for
9170
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9173
The total length of the keys used for index lookup depends on whether
9174
there are any predicates referencing the min/max argument, and/or if
9175
the min/max argument field can be NULL.
9176
This function does an optimistic analysis whether the search key might
9177
be extended by a constant for the min/max keypart. It is 'optimistic'
9178
because during actual execution it may happen that a particular range
9179
is skipped, and then a shorter key will be used. However this is data
9180
dependent and can't be easily estimated here.
9186
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9188
max_used_key_length= real_prefix_len;
9189
if (min_max_ranges.elements > 0)
9191
QUICK_RANGE *cur_range;
9193
{ /* Check if the right-most range has a lower boundary. */
9194
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9195
min_max_ranges.elements - 1);
9196
if (!(cur_range->flag & NO_MIN_RANGE))
9198
max_used_key_length+= min_max_arg_len;
9204
{ /* Check if the left-most range has an upper boundary. */
9205
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9206
if (!(cur_range->flag & NO_MAX_RANGE))
9208
max_used_key_length+= min_max_arg_len;
9214
else if (have_min && min_max_arg_part &&
9215
min_max_arg_part->field->real_maybe_null())
9218
If a MIN/MAX argument value is NULL, we can quickly determine
9219
that we're in the beginning of the next group, because NULLs
9220
are always < any other value. This allows us to quickly
9221
determine the end of the current group and jump to the next
9222
group (see next_min()) and thus effectively increases the
9225
max_used_key_length+= min_max_arg_len;
9232
Initialize a quick group min/max select for key retrieval.
9235
QUICK_GROUP_MIN_MAX_SELECT::reset()
9238
Initialize the index chosen for access and find and store the prefix
9239
of the last group. The method is expensive since it performs disk access.
9246
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9250
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9251
if ((result= file->ha_index_init(index,1)))
9253
if (quick_prefix_select && quick_prefix_select->reset())
9255
result= file->index_last(record);
9256
if (result == HA_ERR_END_OF_FILE)
9258
/* Save the prefix of the last group. */
9259
key_copy(last_prefix, record, index_info, group_prefix_len);
9267
Get the next key containing the MIN and/or MAX key for the next group.
9270
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9273
The method finds the next subsequent group of records that satisfies the
9274
query conditions and finds the keys that contain the MIN/MAX values for
9275
the key part referenced by the MIN/MAX function(s). Once a group and its
9276
MIN/MAX values are found, store these values in the Item_sum objects for
9277
the MIN/MAX functions. The rest of the values in the result row are stored
9278
in the Item_field::result_field of each select field. If the query does
9279
not contain MIN and/or MAX functions, then the function only finds the
9280
group prefix, which is a query answer itself.
9283
If both MIN and MAX are computed, then we use the fact that if there is
9284
no MIN key, there can't be a MAX key as well, so we can skip looking
9285
for a MAX key in this case.
9289
HA_ERR_END_OF_FILE if returned all keys
9290
other if some error occurred
9293
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9298
int is_last_prefix= 0;
9301
Loop until a group is found that satisfies all query conditions or the last
9306
result= next_prefix();
9308
Check if this is the last group prefix. Notice that at this point
9309
this->record contains the current prefix in record format.
9313
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9315
assert(is_last_prefix <= 0);
9319
if (result == HA_ERR_KEY_NOT_FOUND)
9326
min_res= next_min();
9328
update_min_result();
9330
/* If there is no MIN in the group, there is no MAX either. */
9331
if ((have_max && !have_min) ||
9332
(have_max && have_min && (min_res == 0)))
9334
max_res= next_max();
9336
update_max_result();
9337
/* If a MIN was found, a MAX must have been found as well. */
9338
assert(((have_max && !have_min) ||
9339
(have_max && have_min && (max_res == 0))));
9342
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9343
are equality predicates for the key parts after the group, find the
9344
first sub-group with the extended prefix.
9346
if (!have_min && !have_max && key_infix_len > 0)
9347
result= file->index_read_map(record, group_prefix,
9348
make_prev_keypart_map(real_key_parts),
9351
result= have_min ? min_res : have_max ? max_res : result;
9352
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9353
is_last_prefix != 0);
9358
Partially mimic the behavior of end_select_send. Copy the
9359
field data from Item_field::field into Item_field::result_field
9360
of each non-aggregated field (the group fields, and optionally
9361
other fields in non-ANSI SQL mode).
9363
copy_fields(&join->tmp_table_param);
9365
else if (result == HA_ERR_KEY_NOT_FOUND)
9366
result= HA_ERR_END_OF_FILE;
9373
Retrieve the minimal key in the next group.
9376
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9379
Find the minimal key within this group such that the key satisfies the query
9380
conditions and NULL semantics. The found key is loaded into this->record.
9383
Depending on the values of min_max_ranges.elements, key_infix_len, and
9384
whether there is a NULL in the MIN field, this function may directly
9385
return without any data access. In this case we use the key loaded into
9386
this->record by the call to this->next_prefix() just before this call.
9390
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9391
HA_ERR_END_OF_FILE - "" -
9392
other if some error occurred
9395
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9399
/* Find the MIN key using the eventually extended group prefix. */
9400
if (min_max_ranges.elements > 0)
9402
if ((result= next_min_in_range()))
9407
/* Apply the constant equality conditions to the non-group select fields */
9408
if (key_infix_len > 0)
9410
if ((result= file->index_read_map(record, group_prefix,
9411
make_prev_keypart_map(real_key_parts),
9412
HA_READ_KEY_EXACT)))
9417
If the min/max argument field is NULL, skip subsequent rows in the same
9418
group with NULL in it. Notice that:
9419
- if the first row in a group doesn't have a NULL in the field, no row
9420
in the same group has (because NULL < any other value),
9421
- min_max_arg_part->field->ptr points to some place in 'record'.
9423
if (min_max_arg_part && min_max_arg_part->field->is_null())
9425
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9426
key_copy(tmp_record, record, index_info, 0);
9427
result= file->index_read_map(record, tmp_record,
9428
make_keypart_map(real_key_parts),
9431
Check if the new record belongs to the current group by comparing its
9432
prefix with the group's prefix. If it is from the next group, then the
9433
whole group has NULLs in the MIN/MAX field, so use the first record in
9434
the group as a result.
9436
It is possible to reuse this new record as the result candidate for the
9437
next call to next_min(), and to save one lookup in the next call. For
9438
this add a new member 'this->next_group_prefix'.
9442
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9443
key_restore(record, tmp_record, index_info, 0);
9445
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9446
result= 0; /* There is a result in any case. */
9451
If the MIN attribute is non-nullable, this->record already contains the
9452
MIN key in the group, so just return.
9459
Retrieve the maximal key in the next group.
9462
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9465
Lookup the maximal key of the group, and store it into this->record.
9469
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9470
HA_ERR_END_OF_FILE - "" -
9471
other if some error occurred
9474
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9478
/* Get the last key in the (possibly extended) group. */
9479
if (min_max_ranges.elements > 0)
9480
result= next_max_in_range();
9482
result= file->index_read_map(record, group_prefix,
9483
make_prev_keypart_map(real_key_parts),
9484
HA_READ_PREFIX_LAST);
9490
Determine the prefix of the next group.
9493
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9496
Determine the prefix of the next group that satisfies the query conditions.
9497
If there is a range condition referencing the group attributes, use a
9498
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9499
condition. If there is a key infix of constants, append this infix
9500
immediately after the group attributes. The possibly extended prefix is
9501
stored in this->group_prefix. The first key of the found group is stored in
9502
this->record, on which relies this->next_min().
9506
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9507
HA_ERR_END_OF_FILE if there are no more keys
9508
other if some error occurred
9510
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9514
if (quick_prefix_select)
9516
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9517
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9518
make_prev_keypart_map(group_key_parts), cur_prefix)))
9520
seen_first_key= true;
9524
if (!seen_first_key)
9526
result= file->index_first(record);
9529
seen_first_key= true;
9533
/* Load the first key in this group into record. */
9534
result= file->index_read_map(record, group_prefix,
9535
make_prev_keypart_map(group_key_parts),
9542
/* Save the prefix of this group for subsequent calls. */
9543
key_copy(group_prefix, record, index_info, group_prefix_len);
9544
/* Append key_infix to group_prefix. */
9545
if (key_infix_len > 0)
9546
memcpy(group_prefix + group_prefix_len,
9547
key_infix, key_infix_len);
9554
Find the minimal key in a group that satisfies some range conditions for the
9555
min/max argument field.
9558
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9561
Given the sequence of ranges min_max_ranges, find the minimal key that is
9562
in the left-most possible range. If there is no such key, then the current
9563
group does not have a MIN key that satisfies the WHERE clause. If a key is
9564
found, its value is stored in this->record.
9568
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9570
HA_ERR_END_OF_FILE - "" -
9574
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9576
ha_rkey_function find_flag;
9577
key_part_map keypart_map;
9578
QUICK_RANGE *cur_range;
9579
bool found_null= false;
9580
int result= HA_ERR_KEY_NOT_FOUND;
9581
basic_string<unsigned char> max_key;
9583
max_key.reserve(real_prefix_len + min_max_arg_len);
9585
assert(min_max_ranges.elements > 0);
9587
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9588
{ /* Search from the left-most range to the right. */
9589
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9592
If the current value for the min/max argument is bigger than the right
9593
boundary of cur_range, there is no need to check this range.
9595
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9596
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9597
min_max_arg_len) == 1))
9600
if (cur_range->flag & NO_MIN_RANGE)
9602
keypart_map= make_prev_keypart_map(real_key_parts);
9603
find_flag= HA_READ_KEY_EXACT;
9607
/* Extend the search key with the lower boundary for this range. */
9608
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9609
cur_range->min_length);
9610
keypart_map= make_keypart_map(real_key_parts);
9611
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9612
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9613
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9616
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9619
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9620
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9621
continue; /* Check the next range. */
9624
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9625
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9626
range, it can't succeed for any other subsequent range.
9631
/* A key was found. */
9632
if (cur_range->flag & EQ_RANGE)
9633
break; /* No need to perform the checks below for equal keys. */
9635
if (cur_range->flag & NULL_RANGE)
9638
Remember this key, and continue looking for a non-NULL key that
9639
satisfies some other condition.
9641
memcpy(tmp_record, record, head->s->rec_buff_length);
9646
/* Check if record belongs to the current group. */
9647
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9649
result= HA_ERR_KEY_NOT_FOUND;
9653
/* If there is an upper limit, check if the found key is in the range. */
9654
if ( !(cur_range->flag & NO_MAX_RANGE) )
9656
/* Compose the MAX key for the range. */
9658
max_key.append(group_prefix, real_prefix_len);
9659
max_key.append(cur_range->max_key, cur_range->max_length);
9660
/* Compare the found key with max_key. */
9661
int cmp_res= key_cmp(index_info->key_part,
9663
real_prefix_len + min_max_arg_len);
9664
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9666
result= HA_ERR_KEY_NOT_FOUND;
9670
/* If we got to this point, the current key qualifies as MIN. */
9671
assert(result == 0);
9675
If there was a key with NULL in the MIN/MAX field, and there was no other
9676
key without NULL from the same group that satisfies some other condition,
9677
then use the key with the NULL.
9679
if (found_null && result)
9681
memcpy(record, tmp_record, head->s->rec_buff_length);
9689
Find the maximal key in a group that satisfies some range conditions for the
9690
min/max argument field.
9693
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9696
Given the sequence of ranges min_max_ranges, find the maximal key that is
9697
in the right-most possible range. If there is no such key, then the current
9698
group does not have a MAX key that satisfies the WHERE clause. If a key is
9699
found, its value is stored in this->record.
9703
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9705
HA_ERR_END_OF_FILE - "" -
9709
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9711
ha_rkey_function find_flag;
9712
key_part_map keypart_map;
9713
QUICK_RANGE *cur_range;
9715
basic_string<unsigned char> min_key;
9716
min_key.reserve(real_prefix_len + min_max_arg_len);
9718
assert(min_max_ranges.elements > 0);
9720
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9721
{ /* Search from the right-most range to the left. */
9722
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9725
If the current value for the min/max argument is smaller than the left
9726
boundary of cur_range, there is no need to check this range.
9728
if (range_idx != min_max_ranges.elements &&
9729
!(cur_range->flag & NO_MIN_RANGE) &&
9730
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9731
min_max_arg_len) == -1))
9734
if (cur_range->flag & NO_MAX_RANGE)
9736
keypart_map= make_prev_keypart_map(real_key_parts);
9737
find_flag= HA_READ_PREFIX_LAST;
9741
/* Extend the search key with the upper boundary for this range. */
9742
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9743
cur_range->max_length);
9744
keypart_map= make_keypart_map(real_key_parts);
9745
find_flag= (cur_range->flag & EQ_RANGE) ?
9746
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9747
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9750
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9754
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9755
(cur_range->flag & EQ_RANGE))
9756
continue; /* Check the next range. */
9759
In no key was found with this upper bound, there certainly are no keys
9760
in the ranges to the left.
9764
/* A key was found. */
9765
if (cur_range->flag & EQ_RANGE)
9766
return 0; /* No need to perform the checks below for equal keys. */
9768
/* Check if record belongs to the current group. */
9769
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9770
continue; // Row not found
9772
/* If there is a lower limit, check if the found key is in the range. */
9773
if ( !(cur_range->flag & NO_MIN_RANGE) )
9775
/* Compose the MIN key for the range. */
9777
min_key.append(group_prefix, real_prefix_len);
9778
min_key.append(cur_range->min_key, cur_range->min_length);
9780
/* Compare the found key with min_key. */
9781
int cmp_res= key_cmp(index_info->key_part,
9783
real_prefix_len + min_max_arg_len);
9784
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9788
/* If we got to this point, the current key qualifies as MAX. */
9791
return HA_ERR_KEY_NOT_FOUND;
9796
Update all MIN function results with the newly found value.
9799
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9802
The method iterates through all MIN functions and updates the result value
9803
of each function by calling Item_sum::reset(), which in turn picks the new
9804
result value from this->head->record[0], previously updated by
9805
next_min(). The updated value is stored in a member variable of each of the
9806
Item_sum objects, depending on the value type.
9809
The update must be done separately for MIN and MAX, immediately after
9810
next_min() was called and before next_max() is called, because both MIN and
9811
MAX take their result value from the same buffer this->head->record[0]
9812
(i.e. this->record).
9818
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9822
min_functions_it->rewind();
9823
while ((min_func= (*min_functions_it)++))
9829
Update all MAX function results with the newly found value.
9832
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9835
The method iterates through all MAX functions and updates the result value
9836
of each function by calling Item_sum::reset(), which in turn picks the new
9837
result value from this->head->record[0], previously updated by
9838
next_max(). The updated value is stored in a member variable of each of the
9839
Item_sum objects, depending on the value type.
9842
The update must be done separately for MIN and MAX, immediately after
9843
next_max() was called, because both MIN and MAX take their result value
9844
from the same buffer this->head->record[0] (i.e. this->record).
9850
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9854
max_functions_it->rewind();
9855
while ((max_func= (*max_functions_it)++))
9861
Append comma-separated list of keys this quick select uses to key_names;
9862
append comma-separated list of corresponding used lengths to used_lengths.
9865
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9866
key_names [out] Names of used indexes
9867
used_lengths [out] Corresponding lengths of the index names
9870
This method is used by select_describe to extract the names of the
9871
indexes used by a quick select.
9875
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9876
String *used_lengths)
9880
key_names->append(index_info->name);
9881
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9882
used_lengths->append(buf, length);
9885
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9887
SEL_ARG **key,**end;
9891
String tmp(buff,sizeof(buff),&my_charset_bin);
9893
for (idx= 0,key=tree->keys, end=key+param->keys ;
9897
if (tree_map->test(idx))
9899
uint32_t keynr= param->real_keynr[idx];
9902
tmp.append(param->table->key_info[keynr].name);
9906
tmp.append(STRING_WITH_LEN("(empty)"));
9910
static void print_ror_scans_arr(Table *table,
9911
const char *, struct st_ror_scan_info **start,
9912
struct st_ror_scan_info **end)
9915
String tmp(buff,sizeof(buff),&my_charset_bin);
9917
for (;start != end; start++)
9921
tmp.append(table->key_info[(*start)->keynr].name);
9924
tmp.append(STRING_WITH_LEN("(empty)"));
9927
/*****************************************************************************
9928
** Instantiate templates
9929
*****************************************************************************/
9931
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9932
template class List<QUICK_RANGE>;
9933
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
