198
188
@param cost OUT The cost.
201
static void get_sweep_read_cost(Table *table,
204
optimizer::CostVector *cost)
191
static void get_sweep_read_cost(Table *table, ha_rows nrows, bool interrupted,
207
if (table->cursor->primary_key_is_clustered())
195
if (table->file->primary_key_is_clustered())
209
cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
210
static_cast<uint32_t>(nrows),
197
cost->io_count= table->file->read_time(table->s->primary_key,
198
(uint32_t) nrows, nrows);
216
ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);
203
ceil(uint64_t2double(table->file->stats.data_file_length) / IO_SIZE);
217
204
double busy_blocks=
218
205
n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));
219
206
if (busy_blocks < 1.0)
220
207
busy_blocks= 1.0;
222
cost->setIOCount(busy_blocks);
209
cost->io_count= busy_blocks;
226
213
/* Assume reading is done in one 'sweep' */
227
cost->setAvgIOCost((DISK_SEEK_BASE_COST +
228
DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
214
cost->avg_io_cost= (DISK_SEEK_BASE_COST +
215
DISK_SEEK_PROP_COST*n_blocks/busy_blocks);
233
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
236
Item_func::Functype type,
238
Item_result cmp_type);
240
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
244
Item_func::Functype type,
247
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
249
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
251
static ha_rows check_quick_select(Session *session,
252
optimizer::Parameter *param,
255
optimizer::SEL_ARG *tree,
256
bool update_tbl_stats,
259
optimizer::CostVector *cost);
261
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
262
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(Session *session,
281
optimizer::Parameter *param,
282
optimizer::SEL_IMERGE *imerge,
286
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
288
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
289
optimizer::SEL_TREE *tree1,
290
optimizer::SEL_TREE *tree2);
292
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
294
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
295
optimizer::SEL_ARG *key1,
296
optimizer::SEL_ARG *key2,
297
uint32_t clone_flag);
299
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
301
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
303
static bool null_part_in_key(KEY_PART *key_part,
304
const unsigned char *key,
220
class RANGE_OPT_PARAM;
222
A construction block of the SEL_ARG-graph.
224
The following description only covers graphs of SEL_ARG objects with
225
sel_arg->type==KEY_RANGE:
227
One SEL_ARG object represents an "elementary interval" in form
229
min_value <=? table.keypartX <=? max_value
231
The interval is a non-empty interval of any kind: with[out] minimum/maximum
232
bound, [half]open/closed, single-point interval, etc.
234
1. SEL_ARG GRAPH STRUCTURE
236
SEL_ARG objects are linked together in a graph. The meaning of the graph
237
is better demostrated by an example:
242
| part=1 $ part=2 $ part=3
244
| +-------+ $ +-------+ $ +--------+
245
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
246
| +-------+ $ +-------+ $ +--------+
252
\->| kp1=2 |--$--------------$-+
253
+-------+ $ $ | +--------+
255
+-------+ $ $ | +--------+
256
| kp1=3 |--$--------------$-+ |
257
+-------+ $ $ +--------+
261
The entire graph is partitioned into "interval lists".
263
An interval list is a sequence of ordered disjoint intervals over the same
264
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
265
all intervals in the list form an RB-tree, linked via left/right/parent
266
pointers. The RB-tree root SEL_ARG object will be further called "root of the
269
In the example pic, there are 4 interval lists:
270
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
271
The vertical lines represent SEL_ARG::next/prev pointers.
273
In an interval list, each member X may have SEL_ARG::next_key_part pointer
274
pointing to the root of another interval list Y. The pointed interval list
275
must cover a key part with greater number (i.e. Y->part > X->part).
277
In the example pic, the next_key_part pointers are represented by
280
2. SEL_ARG GRAPH SEMANTICS
282
It represents a condition in a special form (we don't have a name for it ATM)
283
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
285
For example, the picture represents the condition in form:
286
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
287
(kp1=2 AND (kp3=11 OR kp3=14)) OR
288
(kp1=3 AND (kp3=11 OR kp3=14))
293
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
294
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
295
intervals (i.e. intervals in form
297
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
299
Those intervals can be used to access the index. The uses are in:
300
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
301
how many table records are contained within all
303
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
304
and create QUICK_RANGE_SELECT object that will
305
read records within these intervals.
307
4. SPACE COMPLEXITY NOTES
309
SEL_ARG graph is a representation of an ordered disjoint sequence of
310
intervals over the ordered set of index tuple values.
312
For multi-part keys, one can construct a WHERE expression such that its
313
list of intervals will be of combinatorial size. Here is an example:
315
(keypart1 IN (1,2, ..., n1)) AND
316
(keypart2 IN (1,2, ..., n2)) AND
317
(keypart3 IN (1,2, ..., n3))
319
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
322
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
324
SEL_ARG graph structure aims to reduce the amount of required space by
325
"sharing" the elementary intervals when possible (the pic at the
326
beginning of this comment has examples of such sharing). The sharing may
327
prevent combinatorial blowup:
329
There are WHERE clauses that have combinatorial-size interval lists but
330
will be represented by a compact SEL_ARG graph.
332
(keypartN IN (1,2, ..., n1)) AND
334
(keypart2 IN (1,2, ..., n2)) AND
335
(keypart1 IN (1,2, ..., n3))
337
but not in all cases:
339
- There are WHERE clauses that do have a compact SEL_ARG-graph
340
representation but get_mm_tree() and its callees will construct a
341
graph of combinatorial size.
343
(keypart1 IN (1,2, ..., n1)) AND
344
(keypart2 IN (1,2, ..., n2)) AND
346
(keypartN IN (1,2, ..., n3))
348
- There are WHERE clauses for which the minimal possible SEL_ARG graph
349
representation will have combinatorial size.
351
By induction: Let's take any interval on some keypart in the middle:
355
Then let's AND it with this interval 'structure' from preceding and
358
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
360
We will obtain this SEL_ARG graph:
364
+---------+ $ +---------+ $ +---------+
365
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
366
+---------+ $ +---------+ $ +---------+
368
+---------+ $ +---------+ $
369
| kp14=c2 |--$-->| kp15=c0 | $
370
+---------+ $ +---------+ $
373
Note that we had to duplicate "kp15=c0" and there was no way to avoid
375
The induction step: AND the obtained expression with another "wrapping"
377
When the process ends because of the limit on max. number of keyparts
380
WHERE clause length is O(3*#max_keyparts)
381
SEL_ARG graph size is O(2^(#max_keyparts/2))
383
(it is also possible to construct a case where instead of 2 in 2^n we
384
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
387
We avoid consuming too much memory by setting a limit on the number of
388
SEL_ARG object we can construct during one range analysis invocation.
391
class SEL_ARG :public Sql_alloc
394
uint8_t min_flag,max_flag,maybe_flag;
395
uint8_t part; // Which key part
398
Number of children of this element in the RB-tree, plus 1 for this
403
Valid only for elements which are RB-tree roots: Number of times this
404
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
405
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
410
unsigned char *min_value,*max_value; // Pointer to range
413
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
415
SEL_ARG *left,*right; /* R-B tree children */
416
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
417
SEL_ARG *parent; /* R-B tree parent */
418
SEL_ARG *next_key_part;
419
enum leaf_color { BLACK,RED } color;
420
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
422
enum { MAX_SEL_ARGS = 16000 };
426
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
427
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
428
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
429
SEL_ARG(enum Type type_arg)
430
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
431
color(BLACK), type(type_arg)
433
inline bool is_same(SEL_ARG *arg)
435
if (type != arg->type || part != arg->part)
437
if (type != KEY_RANGE)
439
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
441
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
442
inline void maybe_smaller() { maybe_flag=1; }
443
/* Return true iff it's a single-point null interval */
444
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
445
inline int cmp_min_to_min(SEL_ARG* arg)
447
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
449
inline int cmp_min_to_max(SEL_ARG* arg)
451
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
453
inline int cmp_max_to_max(SEL_ARG* arg)
455
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
457
inline int cmp_max_to_min(SEL_ARG* arg)
459
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
461
SEL_ARG *clone_and(SEL_ARG* arg)
462
{ // Get overlapping range
463
unsigned char *new_min,*new_max;
464
uint8_t flag_min,flag_max;
465
if (cmp_min_to_min(arg) >= 0)
467
new_min=min_value; flag_min=min_flag;
471
new_min=arg->min_value; flag_min=arg->min_flag;
473
if (cmp_max_to_max(arg) <= 0)
475
new_max=max_value; flag_max=max_flag;
479
new_max=arg->max_value; flag_max=arg->max_flag;
481
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
482
test(maybe_flag && arg->maybe_flag));
484
SEL_ARG *clone_first(SEL_ARG *arg)
485
{ // min <= X < arg->min
486
return new SEL_ARG(field,part, min_value, arg->min_value,
487
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
488
maybe_flag | arg->maybe_flag);
490
SEL_ARG *clone_last(SEL_ARG *arg)
491
{ // min <= X <= key_max
492
return new SEL_ARG(field, part, min_value, arg->max_value,
493
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
495
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
497
bool copy_min(SEL_ARG* arg)
498
{ // Get overlapping range
499
if (cmp_min_to_min(arg) > 0)
501
min_value=arg->min_value; min_flag=arg->min_flag;
502
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
503
(NO_MAX_RANGE | NO_MIN_RANGE))
504
return 1; // Full range
506
maybe_flag|=arg->maybe_flag;
509
bool copy_max(SEL_ARG* arg)
510
{ // Get overlapping range
511
if (cmp_max_to_max(arg) <= 0)
513
max_value=arg->max_value; max_flag=arg->max_flag;
514
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
515
(NO_MAX_RANGE | NO_MIN_RANGE))
516
return 1; // Full range
518
maybe_flag|=arg->maybe_flag;
522
void copy_min_to_min(SEL_ARG *arg)
524
min_value=arg->min_value; min_flag=arg->min_flag;
526
void copy_min_to_max(SEL_ARG *arg)
528
max_value=arg->min_value;
529
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
531
void copy_max_to_min(SEL_ARG *arg)
533
min_value=arg->max_value;
534
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
536
/* returns a number of keypart values (0 or 1) appended to the key buffer */
537
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
539
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
540
if ((!(min_flag & NO_MIN_RANGE) &&
541
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
543
if (maybe_null && *min_value)
546
memset(*min_key+1, 0, length-1);
549
memcpy(*min_key,min_value,length);
555
/* returns a number of keypart values (0 or 1) appended to the key buffer */
556
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
558
if (!(max_flag & NO_MAX_RANGE) &&
559
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
561
if (maybe_null && *max_value)
564
memset(*max_key+1, 0, length-1);
567
memcpy(*max_key,max_value,length);
574
/* returns a number of keypart values appended to the key buffer */
575
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
577
SEL_ARG *key_tree= first();
578
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
579
range_key, *range_key_flag);
580
*range_key_flag|= key_tree->min_flag;
582
if (key_tree->next_key_part &&
583
key_tree->next_key_part->part == key_tree->part+1 &&
584
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
585
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
586
res+= key_tree->next_key_part->store_min_key(key, range_key,
591
/* returns a number of keypart values appended to the key buffer */
592
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
594
SEL_ARG *key_tree= last();
595
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
596
range_key, *range_key_flag);
597
(*range_key_flag)|= key_tree->max_flag;
598
if (key_tree->next_key_part &&
599
key_tree->next_key_part->part == key_tree->part+1 &&
600
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
601
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
602
res+= key_tree->next_key_part->store_max_key(key, range_key,
607
SEL_ARG *insert(SEL_ARG *key);
608
SEL_ARG *tree_delete(SEL_ARG *key);
609
SEL_ARG *find_range(SEL_ARG *key);
610
SEL_ARG *rb_insert(SEL_ARG *leaf);
611
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
613
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
614
void test_use_count(SEL_ARG *root);
619
inline bool simple_key()
621
return !next_key_part && elements == 1;
623
void increment_use_count(long count)
627
next_key_part->use_count+=count;
628
count*= (next_key_part->use_count-count);
629
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
630
if (pos->next_key_part)
631
pos->increment_use_count(count);
636
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
637
if (pos->next_key_part)
639
pos->next_key_part->use_count--;
640
pos->next_key_part->free_tree();
644
inline SEL_ARG **parent_ptr()
646
return parent->left == this ? &parent->left : &parent->right;
651
Check if this SEL_ARG object represents a single-point interval
657
Check if this SEL_ARG object (not tree) represents a single-point
658
interval, i.e. if it represents a "keypart = const" or
662
true This SEL_ARG object represents a singlepoint interval
666
bool is_singlepoint()
669
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
670
flags, and the same for right edge.
672
if (min_flag || max_flag)
674
unsigned char *min_val= min_value;
675
unsigned char *max_val= max_value;
679
/* First byte is a NULL value indicator */
680
if (*min_val != *max_val)
684
return true; /* This "x IS NULL" */
688
return !field->key_cmp(min_val, max_val);
690
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
696
class SEL_TREE :public Sql_alloc
700
Starting an effort to document this field:
701
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
702
(type == SEL_TREE::IMPOSSIBLE)
704
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
705
SEL_TREE(enum Type type_arg) :type(type_arg) {}
706
SEL_TREE() :type(KEY)
709
memset(keys, 0, sizeof(keys));
712
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
713
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
714
merit in range analyzer functions (e.g. get_mm_parts) returning a
715
pointer to such SEL_TREE instead of NULL)
717
SEL_ARG *keys[MAX_KEY];
718
key_map keys_map; /* bitmask of non-NULL elements in keys */
721
Possible ways to read rows using index_merge. The list is non-empty only
722
if type==KEY. Currently can be non empty only if keys_map.none().
724
vector<SEL_IMERGE*> merges;
726
/* The members below are filled/used only after get_mm_tree is done */
727
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
728
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
730
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
731
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
732
/* Note that #records for each key scan is stored in table->quick_rows */
735
class RANGE_OPT_PARAM
738
Session *session; /* Current thread handle */
739
Table *table; /* Table being analyzed */
740
COND *cond; /* Used inside get_mm_tree(). */
741
table_map prev_tables;
742
table_map read_tables;
743
table_map current_table; /* Bit of the table being analyzed */
745
/* Array of parts of all keys for which range analysis is performed */
747
KEY_PART *key_parts_end;
748
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
749
MEM_ROOT *old_root; /* Memory that will last until the query end */
751
Number of indexes used in range analysis (In SEL_TREE::keys only first
752
#keys elements are not empty)
757
If true, the index descriptions describe real indexes (and it is ok to
758
call field->optimize_range(real_keynr[...], ...).
759
Otherwise index description describes fake indexes.
761
bool using_real_indexes;
763
bool remove_jump_scans;
766
used_key_no -> table_key_no translation table. Only makes sense if
767
using_real_indexes==true
769
uint32_t real_keynr[MAX_KEY];
770
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
771
uint32_t alloced_sel_args;
772
bool force_default_mrr;
775
class PARAM : public RANGE_OPT_PARAM
778
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
780
uint32_t max_key_part;
781
/* Number of ranges in the last checked tree->key */
782
uint32_t range_count;
783
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
784
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
785
bool quick; // Don't calulate possible keys
787
uint32_t fields_bitmap_size;
788
MyBitmap needed_fields; /* bitmask of fields needed by the query */
789
MyBitmap tmp_covered_fields;
791
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
793
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
794
uint32_t imerge_cost_buff_size; /* size of the buffer */
796
/* true if last checked tree->key can be used for ROR-scan */
798
/* Number of ranges in the last checked tree->key */
802
class TABLE_READ_PLAN;
804
class TRP_ROR_INTERSECT;
806
class TRP_ROR_INDEX_MERGE;
807
class TRP_GROUP_MIN_MAX;
809
struct st_ror_scan_info;
811
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
812
Item_func::Functype type,Item *value,
813
Item_result cmp_type);
814
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
816
Item_func::Functype type,Item *value);
817
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
819
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
820
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
821
SEL_ARG *tree, bool update_tbl_stats,
822
uint32_t *mrr_flags, uint32_t *bufsize,
824
//bool update_tbl_stats);
825
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
826
unsigned char *min_key, uint32_t min_key_flag, int,
827
unsigned char *max_key, uint32_t max_key_flag, int);
830
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
831
SEL_ARG *key_tree, uint32_t mrr_flags,
832
uint32_t mrr_buf_size, MEM_ROOT *alloc);
833
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
834
bool index_read_must_be_used,
835
bool update_tbl_stats,
838
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
840
bool *are_all_covering);
842
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
846
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
849
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
851
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
853
static void print_ror_scans_arr(Table *table, const char *msg,
854
struct st_ror_scan_info **start,
855
struct st_ror_scan_info **end);
857
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
858
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
859
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
860
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
861
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
862
uint32_t clone_flag);
863
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
864
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
865
SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
866
unsigned char *max_key,uint32_t max_key_flag);
867
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
869
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
870
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
305
871
uint32_t length);
307
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
308
optimizer::SEL_TREE *tree2,
309
optimizer::RangeParameter *param);
317
Perform AND operation on two index_merge lists and store result in *im1.
320
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
872
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
876
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
877
a condition in the following form:
878
(t_1||t_2||...||t_N) && (next)
880
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
881
(t_i,t_j) contains SEL_ARGS for the same index.
883
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
885
This class relies on memory manager to do the cleanup.
888
class SEL_IMERGE : public Sql_alloc
890
enum { PREALLOCED_TREES= 10};
892
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
893
SEL_TREE **trees; /* trees used to do index_merge */
894
SEL_TREE **trees_next; /* last of these trees */
895
SEL_TREE **trees_end; /* end of allocated space */
897
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
900
trees(&trees_prealloced[0]),
902
trees_end(trees + PREALLOCED_TREES)
904
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
905
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
906
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
911
Add SEL_TREE to this index_merge without any checks,
914
This function implements the following:
915
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
922
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
924
if (trees_next == trees_end)
926
const int realloc_ratio= 2; /* Double size for next round */
927
uint32_t old_elements= (trees_end - trees);
928
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
929
uint32_t new_size= old_size * realloc_ratio;
930
SEL_TREE **new_trees;
931
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
933
memcpy(new_trees, trees, old_size);
935
trees_next= trees + old_elements;
936
trees_end= trees + old_elements * realloc_ratio;
938
*(trees_next++)= tree;
944
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
945
combining new_tree with one of the trees in this SEL_IMERGE if they both
946
have SEL_ARGs for the same key.
949
or_sel_tree_with_checks()
950
param PARAM from SQL_SELECT::test_quick_select
951
new_tree SEL_TREE with type KEY or KEY_SMALLER.
954
This does the following:
955
(t_1||...||t_k)||new_tree =
957
= (t_1||...||t_k||new_tree)
959
= (t_1||....||(t_j|| new_tree)||...||t_k),
961
where t_i, y are SEL_TREEs.
962
new_tree is combined with the first t_j it has a SEL_ARG on common
963
key with. As a consequence of this, choice of keys to do index_merge
964
read may depend on the order of conditions in WHERE part of the query.
968
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
969
and (*this) should be discarded.
970
-1 An error occurred.
973
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
975
for (SEL_TREE** tree = trees;
979
if (sel_trees_can_be_ored(*tree, new_tree, param))
981
*tree = tree_or(param, *tree, new_tree);
984
if (((*tree)->type == SEL_TREE::MAYBE) ||
985
((*tree)->type == SEL_TREE::ALWAYS))
987
/* SEL_TREE::IMPOSSIBLE is impossible here */
992
/* New tree cannot be combined with any of existing trees. */
993
return or_sel_tree(param, new_tree);
998
Perform OR operation on this index_merge and supplied index_merge list.
1002
1 - One of conditions in result is always true and this SEL_IMERGE
1003
should be discarded.
1004
-1 - An error occurred
1007
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
1009
for (SEL_TREE** tree= imerge->trees;
1010
tree != imerge->trees_next;
1013
if (or_sel_tree_with_checks(param, *tree))
1021
Perform AND operation on two index_merge lists and store result in im1.
1024
inline void imerge_list_and_list(vector<SEL_IMERGE*> &im1, vector<SEL_IMERGE*> &im2)
1026
im1.insert(im1.end(), im2.begin(), im2.end());
1032
Perform OR operation on 2 index_merge lists, storing result in first list.
1035
The following conversion is implemented:
1036
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
1039
i.e. all conjuncts except the first one are currently dropped.
1040
This is done to avoid producing N*K ways to do index_merge.
1042
If (a_1||b_1) produce a condition that is always true, NULL is returned
1043
and index_merge is discarded (while it is actually possible to try
1046
As a consequence of this, choice of keys to do index_merge read may depend
1047
on the order of conditions in WHERE part of the query.
1050
0 OK, result is stored in *im1
1051
other Error, both passed lists are unusable
1054
static int imerge_list_or_list(RANGE_OPT_PARAM *param,
1055
vector<SEL_IMERGE*> &im1,
1056
vector<SEL_IMERGE*> &im2)
1058
SEL_IMERGE *imerge= im1.front();
1060
im1.push_back(imerge);
1062
return imerge->or_sel_imerge_with_checks(param, im2.front());
1067
Perform OR operation on index_merge list and key tree.
1070
false OK, result is stored in im1.
1074
static bool imerge_list_or_tree(RANGE_OPT_PARAM *param,
1075
vector<SEL_IMERGE*> &im1,
1078
vector<SEL_IMERGE*>::iterator imerge= im1.begin();
1080
while (imerge != im1.end())
1082
if ((*imerge)->or_sel_tree_with_checks(param, tree))
1083
imerge= im1.erase( imerge );
326
1092
/***************************************************************************
327
** Basic functions for SqlSelect and QuickRangeSelect
1093
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
328
1094
***************************************************************************/
330
1096
/* make a select from mysql info
373
optimizer::SqlSelect::SqlSelect()
377
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1135
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
381
1138
needed_reg.reset();
386
void optimizer::SqlSelect::cleanup()
1143
void SQL_SELECT::cleanup()
400
file->close_cached_file();
1153
close_cached_file(&file);
404
optimizer::SqlSelect::~SqlSelect()
1157
SQL_SELECT::~SQL_SELECT()
410
bool optimizer::SqlSelect::check_quick(Session *session,
411
bool force_quick_range,
1163
bool SQL_SELECT::check_quick(Session *session, bool force_quick_range,
416
return (test_quick_select(session,
425
bool optimizer::SqlSelect::skip_record()
427
return (cond ? cond->val_int() == 0 : 0);
431
optimizer::QuickSelectInterface::QuickSelectInterface()
433
max_used_key_length(0),
1168
return test_quick_select(session, tmp, 0, limit,
1169
force_quick_range, false) < 0;
1173
bool SQL_SELECT::skip_record()
1175
return cond ? cond->val_int() == 0 : 0;
1179
QUICK_SELECT_I::QUICK_SELECT_I()
1180
:max_used_key_length(0),
1184
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1185
bool no_alloc, MEM_ROOT *parent_alloc,
1187
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1189
my_bitmap_map *bitmap;
1191
in_ror_merged_scan= 0;
1195
key_part_info= head->key_info[index].key_part;
1196
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1198
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1199
mrr_buf_size= session->variables.read_rnd_buff_size;
1202
if (!no_alloc && !parent_alloc)
1204
// Allocates everything through the internal memroot
1205
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1206
session->mem_root= &alloc;
1209
memset(&alloc, 0, sizeof(alloc));
1211
record= head->record[0];
1212
save_read_set= head->read_set;
1213
save_write_set= head->write_set;
1215
/* Allocate a bitmap for used columns. Using sql_alloc instead of malloc
1216
simply as a "fix" to the MySQL 6.0 code that also free()s it at the
1217
same time we destroy the mem_root.
1220
bitmap= reinterpret_cast<my_bitmap_map*>(sql_alloc(head->s->column_bitmap_size));
1223
column_bitmap.setBitmap(NULL);
1228
column_bitmap.init(bitmap, head->s->fields);
1233
int QUICK_RANGE_SELECT::init()
1235
if (file->inited != Cursor::NONE)
1236
file->ha_index_or_rnd_end();
1237
return(file->ha_index_init(index, 1));
1241
void QUICK_RANGE_SELECT::range_end()
1243
if (file->inited != Cursor::NONE)
1244
file->ha_index_or_rnd_end();
1248
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1252
/* file is NULL for CPK scan on covering ROR-intersection */
1259
file->extra(HA_EXTRA_NO_KEYREAD);
1263
file->ha_external_lock(current_session, F_UNLCK);
1268
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1269
free_root(&alloc,MYF(0));
1271
head->column_bitmaps_set(save_read_set, save_write_set);
1272
assert(mrr_buf_desc == NULL);
1278
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1280
:pk_quick_select(NULL), session(session_param)
1284
memset(&read_record, 0, sizeof(read_record));
1285
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1289
int QUICK_INDEX_MERGE_SELECT::init()
1294
int QUICK_INDEX_MERGE_SELECT::reset()
1296
return(read_keys_and_merge());
1300
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1303
Save quick_select that does scan on clustered primary key as it will be
1304
processed separately.
1306
if (head->file->primary_key_is_clustered() &&
1307
quick_sel_range->index == head->s->primary_key)
1308
pk_quick_select= quick_sel_range;
1310
return quick_selects.push_back(quick_sel_range);
1314
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1316
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1317
QUICK_RANGE_SELECT* quick;
1319
while ((quick= quick_it++))
1321
quick_selects.delete_elements();
1322
delete pk_quick_select;
1323
free_root(&alloc,MYF(0));
1328
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1330
bool retrieve_full_rows,
1331
MEM_ROOT *parent_alloc)
1332
: cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1337
record= head->record[0];
1339
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1341
memset(&alloc, 0, sizeof(MEM_ROOT));
1342
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1343
head->file->ref_length);
1348
Do post-constructor initialization.
1350
QUICK_ROR_INTERSECT_SELECT::init()
1357
int QUICK_ROR_INTERSECT_SELECT::init()
1359
/* Check if last_rowid was successfully allocated in ctor */
1360
return(!last_rowid);
1365
Initialize this quick select to be a ROR-merged scan.
1368
QUICK_RANGE_SELECT::init_ror_merged_scan()
1369
reuse_handler If true, use head->file, otherwise create a separate
1373
This function creates and prepares for subsequent use a separate Cursor
1374
object if it can't reuse head->file. The reason for this is that during
1375
ROR-merge several key scans are performed simultaneously, and a single
1376
Cursor is only capable of preserving context of a single key scan.
1378
In ROR-merge the quick select doing merge does full records retrieval,
1379
merged quick selects read only keys.
1382
0 ROR child scan initialized, ok to use.
1386
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1388
Cursor *save_file= file, *org_file;
1391
in_ror_merged_scan= 1;
1394
if (init() || reset())
1398
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1402
/* Create a separate Cursor object for this quick select */
1405
/* already have own 'Cursor' object. */
1409
session= head->in_use;
1410
if (!(file= head->file->clone(session->mem_root)))
1413
Manually set the error flag. Note: there seems to be quite a few
1414
places where a failure could cause the server to "hang" the client by
1415
sending no response to a query. ATM those are not real errors because
1416
the storage engine calls in question happen to never fail with the
1417
existing storage engines.
1419
my_error(ER_OUT_OF_RESOURCES, MYF(0));
1420
/* Caller will free the memory */
1424
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1426
if (file->ha_external_lock(session, F_RDLCK))
1429
if (init() || reset())
1431
file->ha_external_lock(session, F_UNLCK);
1436
last_rowid= file->ref;
1440
We are only going to read key fields and call position() on 'file'
1441
The following sets head->tmp_set to only use this key and then updates
1442
head->read_set and head->write_set to use this bitmap.
1443
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1445
org_file= head->file;
1447
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1448
if (!head->no_keyread)
1451
head->mark_columns_used_by_index(index);
1453
head->prepare_for_position();
1454
head->file= org_file;
1455
column_bitmap= *head->read_set;
1456
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1461
head->column_bitmaps_set(save_read_set, save_write_set);
1468
void QUICK_RANGE_SELECT::save_last_pos()
1470
file->position(record);
1475
Initialize this quick select to be a part of a ROR-merged scan.
1477
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1478
reuse_handler If true, use head->file, otherwise create separate
1484
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1486
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1487
QUICK_RANGE_SELECT* quick;
1489
/* Initialize all merged "children" quick selects */
1490
assert(!need_to_fetch_row || reuse_handler);
1491
if (!need_to_fetch_row && reuse_handler)
1495
There is no use of this->file. Use it for the first of merged range
1498
if (quick->init_ror_merged_scan(true))
1500
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1502
while ((quick= quick_it++))
1504
if (quick->init_ror_merged_scan(false))
1506
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1507
/* All merged scans share the same record buffer in intersection. */
1508
quick->record= head->record[0];
1511
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1520
Initialize quick select for row retrieval.
1528
int QUICK_ROR_INTERSECT_SELECT::reset()
1530
if (!scans_inited && init_ror_merged_scan(true))
1533
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1534
QUICK_RANGE_SELECT *quick;
1535
while ((quick= it++))
1542
Add a merged quick select to this ROR-intersection quick select.
1545
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1546
quick Quick select to be added. The quick select must return
1547
rows in rowid order.
1549
This call can only be made before init() is called.
1557
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1559
return quick_selects.push_back(quick);
1562
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1564
quick_selects.delete_elements();
1566
free_root(&alloc,MYF(0));
1567
if (need_to_fetch_row && head->file->inited != Cursor::NONE)
1568
head->file->ha_rnd_end();
1573
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1575
: session(session_param), scans_inited(false)
1579
rowid_length= table->file->ref_length;
1580
record= head->record[0];
1581
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1582
session_param->mem_root= &alloc;
1586
* Function object that is used as the comparison function
1587
* for the priority queue in the QUICK_ROR_UNION_SELECT
1590
class compare_functor
1592
QUICK_ROR_UNION_SELECT *self;
1594
compare_functor(QUICK_ROR_UNION_SELECT *in_arg)
1596
inline bool operator()(const QUICK_SELECT_I *i, const QUICK_SELECT_I *j) const
1598
int val= self->head->file->cmp_ref(i->last_rowid,
1605
Do post-constructor initialization.
1607
QUICK_ROR_UNION_SELECT::init()
1614
int QUICK_ROR_UNION_SELECT::init()
1617
new priority_queue<QUICK_SELECT_I *, vector<QUICK_SELECT_I *>, compare_functor >(compare_functor(this));
1618
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1620
prev_rowid= cur_rowid + head->file->ref_length;
1626
Initialize quick select for row retrieval.
1635
int QUICK_ROR_UNION_SELECT::reset()
1637
QUICK_SELECT_I *quick;
1639
have_prev_rowid= false;
1642
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1643
while ((quick= it++))
1645
if (quick->init_ror_merged_scan(false))
1650
while (!queue->empty())
1653
Initialize scans for merged quick selects and put all merged quick
1654
selects into the queue.
1656
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1657
while ((quick= it++))
1661
if ((error= quick->get_next()))
1663
if (error == HA_ERR_END_OF_FILE)
1667
quick->save_last_pos();
1671
if (head->file->ha_rnd_init(1))
1681
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1683
return quick_selects.push_back(quick_sel_range);
1686
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1688
while (!queue->empty())
1691
quick_selects.delete_elements();
1692
if (head->file->inited != Cursor::NONE)
1693
head->file->ha_rnd_end();
1694
free_root(&alloc,MYF(0));
1699
QUICK_RANGE::QUICK_RANGE()
1700
:min_key(0),max_key(0),min_length(0),max_length(0),
1701
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1702
min_keypart_map(0), max_keypart_map(0)
1705
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1708
min_flag=arg.min_flag;
1709
max_flag=arg.max_flag;
1710
maybe_flag=arg.maybe_flag;
1711
maybe_null=arg.maybe_null;
1714
min_value=arg.min_value;
1715
max_value=arg.max_value;
1716
next_key_part=arg.next_key_part;
1717
use_count=1; elements=1;
1721
inline void SEL_ARG::make_root()
1723
left=right= &null_element;
1726
use_count=0; elements=1;
1729
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1730
const unsigned char *max_value_arg)
1731
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1732
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1733
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1734
next_key_part(0),color(BLACK),type(KEY_RANGE)
1736
left=right= &null_element;
1739
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1740
unsigned char *min_value_, unsigned char *max_value_,
1741
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1742
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1743
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1744
field(field_), min_value(min_value_), max_value(max_value_),
1745
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1747
left=right= &null_element;
1750
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1755
/* Bail out if we have already generated too many SEL_ARGs */
1756
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1759
if (type != KEY_RANGE)
1761
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1762
return 0; // out of memory
1763
tmp->prev= *next_arg; // Link into next/prev chain
1764
(*next_arg)->next=tmp;
1769
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1770
min_flag, max_flag, maybe_flag)))
1772
tmp->parent=new_parent;
1773
tmp->next_key_part=next_key_part;
1774
if (left != &null_element)
1775
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1778
tmp->prev= *next_arg; // Link into next/prev chain
1779
(*next_arg)->next=tmp;
1782
if (right != &null_element)
1783
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1786
increment_use_count(1);
1788
tmp->elements= this->elements;
1792
SEL_ARG *SEL_ARG::first()
1794
SEL_ARG *next_arg=this;
1795
if (!next_arg->left)
1796
return 0; // MAYBE_KEY
1797
while (next_arg->left != &null_element)
1798
next_arg=next_arg->left;
1802
SEL_ARG *SEL_ARG::last()
1804
SEL_ARG *next_arg=this;
1805
if (!next_arg->right)
1806
return 0; // MAYBE_KEY
1807
while (next_arg->right != &null_element)
1808
next_arg=next_arg->right;
1814
Check if a compare is ok, when one takes ranges in account
1815
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1818
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1822
/* First check if there was a compare to a min or max element */
1823
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1825
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1826
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1828
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1830
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1831
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1833
if (field->real_maybe_null()) // If null is part of key
1840
goto end; // NULL where equal
1841
a++; b++; // Skip NULL marker
1843
cmp=field->key_cmp(a , b);
1844
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1846
// Check if the compared equal arguments was defined with open/closed range
1848
if (a_flag & (NEAR_MIN | NEAR_MAX))
1850
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1852
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1853
return (a_flag & NEAR_MIN) ? 2 : -2;
1854
return (a_flag & NEAR_MIN) ? 1 : -1;
1856
if (b_flag & (NEAR_MIN | NEAR_MAX))
1857
return (b_flag & NEAR_MIN) ? -2 : 2;
1858
return 0; // The elements where equal
1862
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1864
SEL_ARG tmp_link,*next_arg,*root;
1865
next_arg= &tmp_link;
1866
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1868
next_arg->next=0; // Fix last link
1869
tmp_link.next->prev=0; // Fix first link
1870
if (root) // If not OOM
3294
4929
if (*key1 || *key2)
3296
4931
if (*key1 && !(*key1)->simple_key())
3297
flag|=CLONE_KEY1_MAYBE;
4932
flag|=CLONE_KEY1_MAYBE;
3298
4933
if (*key2 && !(*key2)->simple_key())
3299
flag|=CLONE_KEY2_MAYBE;
4934
flag|=CLONE_KEY2_MAYBE;
3300
4935
*key1=key_and(param, *key1, *key2, flag);
3301
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
4936
if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
3303
tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
4938
tree1->type= SEL_TREE::IMPOSSIBLE;
3306
4941
result_keys.set(key1 - tree1->keys);
4943
if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4944
(*key1)->test_use_count(*key1);
3309
4948
tree1->keys_map= result_keys;
3310
4949
/* dispose index_merge if there is a "range" option */
3311
4950
if (result_keys.any())
3313
tree1->merges.empty();
4952
tree1->merges.clear();
3317
4956
/* ok, both trees are index_merge trees */
3318
imerge_list_and_list(&tree1->merges, &tree2->merges);
4957
imerge_list_and_list(tree1->merges, tree2->merges);
4963
Check if two SEL_TREES can be combined into one (i.e. a single key range
4964
read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
4968
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4969
RANGE_OPT_PARAM* param)
4971
key_map common_keys= tree1->keys_map;
4972
common_keys&= tree2->keys_map;
4974
if (common_keys.none())
4977
/* trees have a common key, check if they refer to same key part */
4978
SEL_ARG **key1,**key2;
4979
for (uint32_t key_no=0; key_no < param->keys; key_no++)
4981
if (common_keys.test(key_no))
4983
key1= tree1->keys + key_no;
4984
key2= tree2->keys + key_no;
4985
if ((*key1)->part == (*key2)->part)
4996
Remove the trees that are not suitable for record retrieval.
4998
param Range analysis parameter
4999
tree Tree to be processed, tree->type is KEY or KEY_SMALLER
5002
This function walks through tree->keys[] and removes the SEL_ARG* trees
5003
that are not "maybe" trees (*) and cannot be used to construct quick range
5005
(*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
5006
these types here as well.
5008
A SEL_ARG* tree cannot be used to construct quick select if it has
5009
tree->part != 0. (e.g. it could represent "keypart2 < const").
5011
WHY THIS FUNCTION IS NEEDED
5013
Normally we allow construction of SEL_TREE objects that have SEL_ARG
5014
trees that do not allow quick range select construction. For example for
5015
" keypart1=1 AND keypart2=2 " the execution will proceed as follows:
5016
tree1= SEL_TREE { SEL_ARG{keypart1=1} }
5017
tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
5019
call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
5022
There is an exception though: when we construct index_merge SEL_TREE,
5023
any SEL_ARG* tree that cannot be used to construct quick range select can
5024
be removed, because current range analysis code doesn't provide any way
5025
that tree could be later combined with another tree.
5026
Consider an example: we should not construct
5028
merges = SEL_IMERGE {
5029
SEL_TREE(t.key1part1 = 1),
5030
SEL_TREE(t.key2part2 = 2) -- (*)
5034
- (*) cannot be used to construct quick range select,
5035
- There is no execution path that would cause (*) to be converted to
5036
a tree that could be used.
5038
The latter is easy to verify: first, notice that the only way to convert
5039
(*) into a usable tree is to call tree_and(something, (*)).
5041
Second look at what tree_and/tree_or function would do when passed a
5042
SEL_TREE that has the structure like st1 tree has, and conlcude that
5043
tree_and(something, (*)) will not be called.
5046
0 Ok, some suitable trees left
5047
1 No tree->keys[] left.
5050
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree)
5053
for (uint32_t i=0; i < param->keys; i++)
5057
if (tree->keys[i]->part)
5059
tree->keys[i]= NULL;
5060
tree->keys_map.reset(i);
5071
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
5073
if (!tree1 || !tree2)
5075
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
5077
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
5079
if (tree1->type == SEL_TREE::MAYBE)
5080
return(tree1); // Can't use this
5081
if (tree2->type == SEL_TREE::MAYBE)
5084
SEL_TREE *result= 0;
5085
key_map result_keys;
5086
result_keys.reset();
5087
if (sel_trees_can_be_ored(tree1, tree2, param))
5089
/* Join the trees key per key */
5090
SEL_ARG **key1,**key2,**end;
5091
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
5092
key1 != end ; key1++,key2++)
5094
*key1=key_or(param, *key1, *key2);
5097
result=tree1; // Added to tree1
5098
result_keys.set(key1 - tree1->keys);
5100
if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
5101
(*key1)->test_use_count(*key1);
5106
result->keys_map= result_keys;
5110
/* ok, two trees have KEY type but cannot be used without index merge */
5111
if ((tree1->merges.empty() == true) && (tree2->merges.empty() == true))
5113
if (param->remove_jump_scans)
5115
bool no_trees= remove_nonrange_trees(param, tree1);
5116
no_trees= no_trees || remove_nonrange_trees(param, tree2);
5118
return(new SEL_TREE(SEL_TREE::ALWAYS));
5121
/* both trees are "range" trees, produce new index merge structure. */
5122
result= new SEL_TREE();
5123
SEL_IMERGE *merge= new SEL_IMERGE();
5124
result->merges.push_back(merge);
5126
if( merge->or_sel_tree(param, tree1) || merge->or_sel_tree(param, tree2))
5129
result->type= tree1->type;
5131
else if ((tree1->merges.empty() == false) && (tree2->merges.empty() == false))
5133
if (imerge_list_or_list(param, tree1->merges, tree2->merges))
5134
result= new SEL_TREE(SEL_TREE::ALWAYS);
5140
/* one tree is index merge tree and another is range tree */
5141
if (tree1->merges.empty() == true)
5142
std::swap(tree1, tree2);
5144
if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
5145
return(new SEL_TREE(SEL_TREE::ALWAYS));
5147
/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
5148
if (imerge_list_or_tree(param, tree1->merges, tree2))
5149
result= new SEL_TREE(SEL_TREE::ALWAYS);
3324
5158
/* And key trees where key1->part < key2 -> part */
3326
static optimizer::SEL_ARG *
3327
and_all_keys(optimizer::RangeParameter *param,
3328
optimizer::SEL_ARG *key1,
3329
optimizer::SEL_ARG *key2,
5161
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
3330
5162
uint32_t clone_flag)
3332
optimizer::SEL_ARG *next= NULL;
3333
5165
ulong use_count=key1->use_count;
3335
5167
if (key1->elements != 1)
5343
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5363
if (key1->part != key2->part)
5367
return 0; // Can't optimize this
5370
// If one of the key is MAYBE_KEY then the found region may be bigger
5371
if (key1->type == SEL_ARG::MAYBE_KEY)
5377
if (key2->type == SEL_ARG::MAYBE_KEY)
5384
if (key1->use_count > 0)
5386
if (key2->use_count == 0 || key1->elements > key2->elements)
5388
std::swap(key1,key2);
5390
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5394
// Add tree at key2 to tree at key1
5395
bool key2_shared=key2->use_count != 0;
5396
key1->maybe_flag|=key2->maybe_flag;
5398
for (key2=key2->first(); key2; )
5400
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5405
tmp=key1->first(); // tmp.min > key2.min
5408
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5409
{ // Found tmp.max < key2.min
5410
SEL_ARG *next=tmp->next;
5411
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5413
// Join near ranges like tmp.max < 0 and key2.min >= 0
5414
SEL_ARG *key2_next=key2->next;
5417
if (!(key2=new SEL_ARG(*key2)))
5418
return 0; // out of memory
5419
key2->increment_use_count(key1->use_count+1);
5420
key2->next=key2_next; // New copy of key2
5422
key2->copy_min(tmp);
5423
if (!(key1=key1->tree_delete(tmp)))
5424
{ // Only one key in tree
5431
if (!(tmp=next)) // tmp.min > key2.min
5432
break; // Copy rest of key2
5435
{ // tmp.min > key2.min
5437
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5439
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5440
{ // ranges are connected
5441
tmp->copy_min_to_min(key2);
5442
key1->merge_flags(key2);
5443
if (tmp->min_flag & NO_MIN_RANGE &&
5444
tmp->max_flag & NO_MAX_RANGE)
5446
if (key1->maybe_flag)
5447
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5450
key2->increment_use_count(-1); // Free not used tree
5456
SEL_ARG *next=key2->next; // Keys are not overlapping
5459
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5462
key1=key1->insert(cpy);
5463
key2->increment_use_count(key1->use_count+1);
5466
key1=key1->insert(key2); // Will destroy key2_root
5473
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5474
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5476
if (tmp->is_same(key2))
5478
tmp->merge_flags(key2); // Copy maybe flags
5479
key2->increment_use_count(-1); // Free not used tree
5484
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5485
eq_tree(last->next->next_key_part,key2->next_key_part))
5489
key1=key1->tree_delete(save);
5491
last->copy_min(tmp);
5492
if (last->copy_min(key2) || last->copy_max(key2))
5495
for (; key2 ; key2=key2->next)
5496
key2->increment_use_count(-1); // Free not used tree
5497
if (key1->maybe_flag)
5498
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5506
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5507
{ // tmp.min <= x < key2.min
5508
SEL_ARG *new_arg=tmp->clone_first(key2);
5511
if ((new_arg->next_key_part= key1->next_key_part))
5512
new_arg->increment_use_count(key1->use_count+1);
5513
tmp->copy_min_to_min(key2);
5514
key1=key1->insert(new_arg);
5517
// tmp.min >= key2.min && tmp.min <= key2.max
5518
SEL_ARG key(*key2); // Get copy we can modify
5521
if (tmp->cmp_min_to_min(&key) > 0)
5522
{ // key.min <= x < tmp.min
5523
SEL_ARG *new_arg=key.clone_first(tmp);
5526
if ((new_arg->next_key_part=key.next_key_part))
5527
new_arg->increment_use_count(key1->use_count+1);
5528
key1=key1->insert(new_arg);
5530
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5531
{ // tmp.min. <= x <= tmp.max
5532
tmp->maybe_flag|= key.maybe_flag;
5533
key.increment_use_count(key1->use_count+1);
5534
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5535
if (!cmp) // Key2 is ready
5537
key.copy_max_to_min(tmp);
5538
if (!(tmp=tmp->next))
5540
SEL_ARG *tmp2= new SEL_ARG(key);
5543
key1=key1->insert(tmp2);
5547
if (tmp->cmp_min_to_max(&key) > 0)
5549
SEL_ARG *tmp2= new SEL_ARG(key);
5552
key1=key1->insert(tmp2);
5558
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5561
tmp->copy_max_to_min(&key);
5562
tmp->increment_use_count(key1->use_count+1);
5563
/* Increment key count as it may be used for next loop */
5564
key.increment_use_count(1);
5565
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5566
key1=key1->insert(new_arg);
5576
SEL_ARG *next=key2->next;
5579
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5582
key2->increment_use_count(key1->use_count+1);
5583
key1=key1->insert(tmp);
5586
key1=key1->insert(key2); // Will destroy key2_root
5594
/* Compare if two trees are equal */
5596
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5600
if (!a || !b || !a->is_same(b))
5602
if (a->left != &null_element && b->left != &null_element)
5604
if (!eq_tree(a->left,b->left))
5607
else if (a->left != &null_element || b->left != &null_element)
5609
if (a->right != &null_element && b->right != &null_element)
5611
if (!eq_tree(a->right,b->right))
5614
else if (a->right != &null_element || b->right != &null_element)
5616
if (a->next_key_part != b->next_key_part)
5618
if (!a->next_key_part != !b->next_key_part ||
5619
!eq_tree(a->next_key_part, b->next_key_part))
5627
SEL_ARG::insert(SEL_ARG *key)
5629
SEL_ARG *element, **par= NULL, *last_element= NULL;
5631
for (element= this; element != &null_element ; )
5633
last_element=element;
5634
if (key->cmp_min_to_min(element) > 0)
5636
par= &element->right; element= element->right;
5640
par = &element->left; element= element->left;
5644
key->parent=last_element;
5646
if (par == &last_element->left)
5648
key->next=last_element;
5649
if ((key->prev=last_element->prev))
5650
key->prev->next=key;
5651
last_element->prev=key;
5655
if ((key->next=last_element->next))
5656
key->next->prev=key;
5657
key->prev=last_element;
5658
last_element->next=key;
5660
key->left=key->right= &null_element;
5661
SEL_ARG *root=rb_insert(key); // rebalance tree
5662
root->use_count=this->use_count; // copy root info
5663
root->elements= this->elements+1;
5664
root->maybe_flag=this->maybe_flag;
5670
** Find best key with min <= given key
5671
** Because the call context this should never return 0 to get_range
5675
SEL_ARG::find_range(SEL_ARG *key)
5677
SEL_ARG *element=this,*found=0;
5681
if (element == &null_element)
5683
int cmp=element->cmp_min_to_min(key);
5689
element=element->right;
5692
element=element->left;
5698
Remove a element from the tree
5702
key Key that is to be deleted from tree (this)
5705
This also frees all sub trees that is used by the element
5708
root of new tree (with key deleted)
5712
SEL_ARG::tree_delete(SEL_ARG *key)
5714
enum leaf_color remove_color;
5715
SEL_ARG *root,*nod,**par,*fix_par;
5720
/* Unlink from list */
5722
key->prev->next=key->next;
5724
key->next->prev=key->prev;
5725
key->increment_use_count(-1);
5729
par=key->parent_ptr();
5731
if (key->left == &null_element)
5733
*par=nod=key->right;
5734
fix_par=key->parent;
5735
if (nod != &null_element)
5736
nod->parent=fix_par;
5737
remove_color= key->color;
5739
else if (key->right == &null_element)
5741
*par= nod=key->left;
5742
nod->parent=fix_par=key->parent;
5743
remove_color= key->color;
5747
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5748
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5749
fix_par=tmp->parent;
5750
if (nod != &null_element)
5751
nod->parent=fix_par;
5752
remove_color= tmp->color;
5754
tmp->parent=key->parent; // Move node in place of key
5755
(tmp->left=key->left)->parent=tmp;
5756
if ((tmp->right=key->right) != &null_element)
5757
tmp->right->parent=tmp;
5758
tmp->color=key->color;
5760
if (fix_par == key) // key->right == key->next
5761
fix_par=tmp; // new parent of nod
5764
if (root == &null_element)
5765
return 0; // Maybe root later
5766
if (remove_color == BLACK)
5767
root=rb_delete_fixup(root,nod,fix_par);
5769
test_rb_tree(root,root->parent);
5770
#endif /* EXTRA_DEBUG */
5772
root->use_count=this->use_count; // Fix root counters
5773
root->elements=this->elements-1;
5774
root->maybe_flag=this->maybe_flag;
5779
/* Functions to fix up the tree after insert and delete */
5781
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5783
SEL_ARG *y=leaf->right;
5784
leaf->right=y->left;
5785
if (y->left != &null_element)
5786
y->left->parent=leaf;
5787
if (!(y->parent=leaf->parent))
5790
*leaf->parent_ptr()=y;
5795
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5797
SEL_ARG *y=leaf->left;
5798
leaf->left=y->right;
5799
if (y->right != &null_element)
5800
y->right->parent=leaf;
5801
if (!(y->parent=leaf->parent))
5804
*leaf->parent_ptr()=y;
5811
SEL_ARG::rb_insert(SEL_ARG *leaf)
5813
SEL_ARG *y,*par,*par2,*root;
5814
root= this; root->parent= 0;
5817
while (leaf != root && (par= leaf->parent)->color == RED)
5818
{ // This can't be root or 1 level under
5819
if (par == (par2= leaf->parent->parent)->left)
5822
if (y->color == RED)
5827
leaf->color=RED; /* And the loop continues */
5831
if (leaf == par->right)
5833
left_rotate(&root,leaf->parent);
5834
par=leaf; /* leaf is now parent to old leaf */
5838
right_rotate(&root,par2);
5845
if (y->color == RED)
5850
leaf->color=RED; /* And the loop continues */
5854
if (leaf == par->left)
5856
right_rotate(&root,par);
5861
left_rotate(&root,par2);
5868
test_rb_tree(root,root->parent);
5869
#endif /* EXTRA_DEBUG */
5875
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5881
while (x != root && x->color == SEL_ARG::BLACK)
5886
if (w->color == SEL_ARG::RED)
5888
w->color=SEL_ARG::BLACK;
5889
par->color=SEL_ARG::RED;
5890
left_rotate(&root,par);
5893
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5895
w->color=SEL_ARG::RED;
5900
if (w->right->color == SEL_ARG::BLACK)
5902
w->left->color=SEL_ARG::BLACK;
5903
w->color=SEL_ARG::RED;
5904
right_rotate(&root,w);
5907
w->color=par->color;
5908
par->color=SEL_ARG::BLACK;
5909
w->right->color=SEL_ARG::BLACK;
5910
left_rotate(&root,par);
5918
if (w->color == SEL_ARG::RED)
5920
w->color=SEL_ARG::BLACK;
5921
par->color=SEL_ARG::RED;
5922
right_rotate(&root,par);
5925
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5927
w->color=SEL_ARG::RED;
5932
if (w->left->color == SEL_ARG::BLACK)
5934
w->right->color=SEL_ARG::BLACK;
5935
w->color=SEL_ARG::RED;
5936
left_rotate(&root,w);
5939
w->color=par->color;
5940
par->color=SEL_ARG::BLACK;
5941
w->left->color=SEL_ARG::BLACK;
5942
right_rotate(&root,par);
5949
x->color=SEL_ARG::BLACK;
5954
/* Test that the properties for a red-black tree hold */
5957
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5959
int count_l,count_r;
5961
if (element == &null_element)
5962
return 0; // Found end of tree
5963
if (element->parent != parent)
5965
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5968
if (element->color == SEL_ARG::RED &&
5969
(element->left->color == SEL_ARG::RED ||
5970
element->right->color == SEL_ARG::RED))
5972
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5975
if (element->left == element->right && element->left != &null_element)
5977
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5980
count_l=test_rb_tree(element->left,element);
5981
count_r=test_rb_tree(element->right,element);
5982
if (count_l >= 0 && count_r >= 0)
5984
if (count_l == count_r)
5985
return count_l+(element->color == SEL_ARG::BLACK);
5986
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5989
return -1; // Error, no more warnings
5994
Count how many times SEL_ARG graph "root" refers to its part "key"
5997
count_key_part_usage()
5998
root An RB-Root node in a SEL_ARG graph.
5999
key Another RB-Root node in that SEL_ARG graph.
6002
The passed "root" node may refer to "key" node via root->next_key_part,
6005
This function counts how many times the node "key" is referred (via
6006
SEL_ARG::next_key_part) by
6007
- intervals of RB-tree pointed by "root",
6008
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
6009
intervals of RB-tree pointed by "root",
6012
Here is an example (horizontal links represent next_key_part pointers,
6013
vertical links - next/prev prev pointers):
6016
|root|-----------------+
6020
+----+ +---+ $ | +---+ Here the return value
6021
| |- ... -| |---$-+--+->|key| will be 4.
6022
+----+ +---+ $ | | +---+
6027
| |---| |---------+ |
6034
Number of links to "key" from nodes reachable from "root".
6037
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
6040
for (root=root->first(); root ; root=root->next)
6042
if (root->next_key_part)
6044
if (root->next_key_part == key)
6046
if (root->next_key_part->part < key->part)
6047
count+=count_key_part_usage(root->next_key_part,key);
6055
Check if SEL_ARG::use_count value is correct
6058
SEL_ARG::test_use_count()
6059
root The root node of the SEL_ARG graph (an RB-tree root node that
6060
has the least value of sel_arg->part in the entire graph, and
6061
thus is the "origin" of the graph)
6064
Check if SEL_ARG::use_count value is correct. See the definition of
6065
use_count for what is "correct".
6068
void SEL_ARG::test_use_count(SEL_ARG *root)
6071
if (this == root && use_count != 1)
6073
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
6076
if (this->type != SEL_ARG::KEY_RANGE)
6078
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
6081
if (pos->next_key_part)
6083
ulong count=count_key_part_usage(root,pos->next_key_part);
6084
if (count > pos->next_key_part->use_count)
6086
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
6087
"should be %lu", (long unsigned int)pos,
6088
pos->next_key_part->use_count, count);
6091
pos->next_key_part->test_use_count(root);
6094
if (e_count != elements)
6095
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
6096
e_count, elements, (long unsigned int) this);
3519
6101
/****************************************************************************
3520
6102
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3521
6103
****************************************************************************/
4335
Range sequence interface implementation for array<QuickRange>: initialize
6930
Perform key scans for all used indexes (except CPK), get rowids and merge
6931
them into an ordered non-recurrent sequence of rowids.
6933
The merge/duplicate removal is performed using Unique class. We put all
6934
rowids into Unique, get the sorted sequence and destroy the Unique.
6936
If table has a clustered primary key that covers all rows (true for bdb
6937
and innodb currently) and one of the index_merge scans is a scan on PK,
6938
then rows that will be retrieved by PK scan are not put into Unique and
6939
primary key scan is not performed here, it is performed later separately.
6946
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6948
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6949
QUICK_RANGE_SELECT* cur_quick;
6952
Cursor *file= head->file;
6954
file->extra(HA_EXTRA_KEYREAD);
6955
head->prepare_for_position();
6957
cur_quick_it.rewind();
6958
cur_quick= cur_quick_it++;
6959
assert(cur_quick != 0);
6962
We reuse the same instance of Cursor so we need to call both init and
6965
if (cur_quick->init() || cur_quick->reset())
6968
unique= new Unique(refpos_order_cmp, (void *)file,
6970
session->variables.sortbuff_size);
6975
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6977
cur_quick->range_end();
6978
cur_quick= cur_quick_it++;
6982
if (cur_quick->file->inited != Cursor::NONE)
6983
cur_quick->file->ha_index_end();
6984
if (cur_quick->init() || cur_quick->reset())
6990
if (result != HA_ERR_END_OF_FILE)
6992
cur_quick->range_end();
6998
if (session->killed)
7001
/* skip row if it will be retrieved by clustered PK scan */
7002
if (pk_quick_select && pk_quick_select->row_in_ranges())
7005
cur_quick->file->position(cur_quick->record);
7006
result= unique->unique_add((char*)cur_quick->file->ref);
7012
/* ok, all row ids are in Unique */
7013
result= unique->get(head);
7015
doing_pk_scan= false;
7016
/* index_merge currently doesn't support "using index" at all */
7017
file->extra(HA_EXTRA_NO_KEYREAD);
7018
/* start table scan */
7019
init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
7025
Get next row for index_merge.
7027
The rows are read from
7028
1. rowids stored in Unique.
7029
2. QUICK_RANGE_SELECT with clustered primary key (if any).
7030
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
7033
int QUICK_INDEX_MERGE_SELECT::get_next()
7038
return(pk_quick_select->get_next());
7040
if ((result= read_record.read_record(&read_record)) == -1)
7042
result= HA_ERR_END_OF_FILE;
7043
end_read_record(&read_record);
7044
/* All rows from Unique have been retrieved, do a clustered PK scan */
7045
if (pk_quick_select)
7047
doing_pk_scan= true;
7048
if ((result= pk_quick_select->init()) ||
7049
(result= pk_quick_select->reset()))
7051
return(pk_quick_select->get_next());
7060
Retrieve next record.
7062
QUICK_ROR_INTERSECT_SELECT::get_next()
7065
Invariant on enter/exit: all intersected selects have retrieved all index
7066
records with rowid <= some_rowid_val and no intersected select has
7067
retrieved any index records with rowid > some_rowid_val.
7068
We start fresh and loop until we have retrieved the same rowid in each of
7069
the key scans or we got an error.
7071
If a Clustered PK scan is present, it is used only to check if row
7072
satisfies its condition (and never used for row retrieval).
7076
other - Error code if any error occurred.
7079
int QUICK_ROR_INTERSECT_SELECT::get_next()
7081
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
7082
QUICK_RANGE_SELECT* quick;
7084
uint32_t last_rowid_count=0;
7088
/* Get a rowid for first quick and save it as a 'candidate' */
7090
error= quick->get_next();
7093
while (!error && !cpk_quick->row_in_ranges())
7094
error= quick->get_next();
7099
quick->file->position(quick->record);
7100
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7101
last_rowid_count= 1;
7103
while (last_rowid_count < quick_selects.elements)
7105
if (!(quick= quick_it++))
7113
if ((error= quick->get_next()))
7115
quick->file->position(quick->record);
7116
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
7119
/* Ok, current select 'caught up' and returned ref >= cur_ref */
7122
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
7125
while (!cpk_quick->row_in_ranges())
7127
if ((error= quick->get_next()))
7131
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7132
last_rowid_count= 1;
7136
/* current 'candidate' row confirmed by this select */
7141
/* We get here if we got the same row ref in all scans. */
7142
if (need_to_fetch_row)
7143
error= head->file->rnd_pos(head->record[0], last_rowid);
7144
} while (error == HA_ERR_RECORD_DELETED);
7150
Retrieve next record.
7152
QUICK_ROR_UNION_SELECT::get_next()
7155
Enter/exit invariant:
7156
For each quick select in the queue a {key,rowid} tuple has been
7157
retrieved but the corresponding row hasn't been passed to output.
7161
other - Error code if any error occurred.
7164
int QUICK_ROR_UNION_SELECT::get_next()
7167
QUICK_SELECT_I *quick;
7175
return(HA_ERR_END_OF_FILE);
7176
/* Ok, we have a queue with >= 1 scans */
7178
quick= queue->top();
7179
memcpy(cur_rowid, quick->last_rowid, rowid_length);
7181
/* put into queue rowid from the same stream as top element */
7182
if ((error= quick->get_next()))
7184
if (error != HA_ERR_END_OF_FILE)
7190
quick->save_last_pos();
7195
if (!have_prev_rowid)
7197
/* No rows have been returned yet */
7199
have_prev_rowid= true;
7202
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
7206
cur_rowid= prev_rowid;
7209
error= head->file->rnd_pos(quick->record, prev_rowid);
7210
} while (error == HA_ERR_RECORD_DELETED);
7215
int QUICK_RANGE_SELECT::reset()
7218
unsigned char *mrange_buff;
7220
HANDLER_BUFFER empty_buf;
7222
cur_range= (QUICK_RANGE**) ranges.buffer;
7224
if (file->inited == Cursor::NONE && (error= file->ha_index_init(index,1)))
7227
/* Allocate buffer if we need one but haven't allocated it yet */
7228
if (mrr_buf_size && !mrr_buf_desc)
7230
buf_size= mrr_buf_size;
7231
while (buf_size && ! memory::multi_malloc(false,
7232
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7233
&mrange_buff, buf_size,
7236
/* Try to shrink the buffers until both are 0. */
7240
return(HA_ERR_OUT_OF_MEM);
7242
/* Initialize the Cursor buffer. */
7243
mrr_buf_desc->buffer= mrange_buff;
7244
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7245
mrr_buf_desc->end_of_used_area= mrange_buff;
7249
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7252
mrr_flags |= HA_MRR_SORTED;
7253
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7254
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7255
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7262
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4338
7265
quick_range_seq_init()
4339
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7266
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4340
7267
n_ranges Number of ranges in the sequence (ignored)
4341
7268
flags MRR flags (currently not used)
4368
7295
1 No more ranges in the sequence
4370
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7298
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4372
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7300
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4374
7302
if (ctx->cur == ctx->last)
4375
7303
return 1; /* no more ranges */
4377
optimizer::QuickRange *cur= *(ctx->cur);
7305
QUICK_RANGE *cur= *(ctx->cur);
4378
7306
key_range *start_key= &range->start_key;
4379
key_range *end_key= &range->end_key;
7307
key_range *end_key= &range->end_key;
4381
start_key->key= cur->min_key;
7309
start_key->key= cur->min_key;
4382
7310
start_key->length= cur->min_length;
4383
7311
start_key->keypart_map= cur->min_keypart_map;
4384
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4385
(cur->flag & EQ_RANGE) ?
4386
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4387
end_key->key= cur->max_key;
4388
end_key->length= cur->max_length;
7312
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7313
(cur->flag & EQ_RANGE) ?
7314
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7315
end_key->key= cur->max_key;
7316
end_key->length= cur->max_length;
4389
7317
end_key->keypart_map= cur->max_keypart_map;
4391
7319
We use HA_READ_AFTER_KEY here because if we are reading on a key
4392
7320
prefix. We want to find all keys with this prefix.
4394
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7322
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4396
7324
range->range_flag= cur->flag;
4402
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4404
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4405
optimizer::SEL_TREE *range_tree,
4406
optimizer::Parameter *param,
4407
uint32_t *param_idx);
4409
static bool get_constant_key_infix(KeyInfo *index_info,
4410
optimizer::SEL_ARG *index_range_tree,
4411
KeyPartInfo *first_non_group_part,
4412
KeyPartInfo *min_max_arg_part,
4413
KeyPartInfo *last_part,
4415
unsigned char *key_infix,
4416
uint32_t *key_infix_len,
4417
KeyPartInfo **first_non_infix_part);
7331
Get next possible record using quick-struct.
7334
QUICK_RANGE_SELECT::get_next()
7337
Record is read into table->record[0]
7341
HA_ERR_END_OF_FILE No (more) rows in range
7345
int QUICK_RANGE_SELECT::get_next()
7348
if (in_ror_merged_scan)
7351
We don't need to signal the bitmap change as the bitmap is always the
7352
same for this head->file
7354
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
7357
int result= file->multi_range_read_next(&dummy);
7359
if (in_ror_merged_scan)
7361
/* Restore bitmaps set on entry */
7362
head->column_bitmaps_set(save_read_set, save_write_set);
7369
Get the next record with a different prefix.
7372
QUICK_RANGE_SELECT::get_next_prefix()
7373
prefix_length length of cur_prefix
7374
cur_prefix prefix of a key to be searched for
7377
Each subsequent call to the method retrieves the first record that has a
7378
prefix with length prefix_length different from cur_prefix, such that the
7379
record with the new prefix is within the ranges described by
7380
this->ranges. The record found is stored into the buffer pointed by
7382
The method is useful for GROUP-BY queries with range conditions to
7383
discover the prefix of the next group that satisfies the range conditions.
7386
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7387
methods should be unified into a more general one to reduce code
7392
HA_ERR_END_OF_FILE if returned all keys
7393
other if some error occurred
7396
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7397
key_part_map keypart_map,
7398
unsigned char *cur_prefix)
7403
key_range start_key, end_key;
7406
/* Read the next record in the same range with prefix after cur_prefix. */
7407
assert(cur_prefix != 0);
7408
result= file->index_read_map(record, cur_prefix, keypart_map,
7410
if (result || (file->compare_key(file->end_range) <= 0))
7414
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7417
/* Ranges have already been used up before. None is left for read. */
7419
return HA_ERR_END_OF_FILE;
7421
last_range= *(cur_range++);
7423
start_key.key= (const unsigned char*) last_range->min_key;
7424
start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
7425
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7426
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7427
(last_range->flag & EQ_RANGE) ?
7428
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7429
end_key.key= (const unsigned char*) last_range->max_key;
7430
end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
7431
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7433
We use READ_AFTER_KEY here because if we are reading on a key
7434
prefix we want to find all keys with this prefix
7436
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7439
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7440
last_range->max_keypart_map ? &end_key : 0,
7441
test(last_range->flag & EQ_RANGE),
7443
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7444
last_range= 0; // Stop searching
7446
if (result != HA_ERR_END_OF_FILE)
7448
last_range= 0; // No matching rows; go to next range
7454
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7457
It is assumed that currently a scan is being done on another index
7458
which reads all necessary parts of the index that is scanned by this
7460
The implementation does a binary search on sorted array of disjoint
7461
ranges, without taking size of range into account.
7463
This function is used to filter out clustered PK scan rows in
7464
index_merge quick select.
7467
true if current row will be retrieved by this quick select
7471
bool QUICK_RANGE_SELECT::row_in_ranges()
7475
uint32_t max= ranges.elements - 1;
7476
uint32_t mid= (max + min)/2;
7480
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7482
/* current row value > mid->max */
7487
mid= (min + max) / 2;
7489
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7490
return (!cmp_next(res) && !cmp_prev(res));
7494
This is a hack: we inherit from QUICK_SELECT so that we can use the
7495
get_next() interface, but we have to hold a pointer to the original
7496
QUICK_SELECT because its data are used all over the place. What
7497
should be done is to factor out the data that is needed into a base
7498
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7499
which handle the ranges and implement the get_next() function. But
7500
for now, this seems to work right at least.
7503
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7504
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7508
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7509
QUICK_RANGE **end_range= pr + ranges.elements;
7510
for (; pr!=end_range; pr++)
7511
rev_ranges.push_front(*pr);
7513
/* Remove EQ_RANGE flag for keys that are not using the full key */
7514
for (r = rev_it++; r; r = rev_it++)
7516
if ((r->flag & EQ_RANGE) &&
7517
head->key_info[index].key_length != r->max_length)
7518
r->flag&= ~EQ_RANGE;
7521
q->dont_free=1; // Don't free shared mem
7526
int QUICK_SELECT_DESC::get_next()
7528
/* The max key is handled as follows:
7529
* - if there is NO_MAX_RANGE, start at the end and move backwards
7530
* - if it is an EQ_RANGE, which means that max key covers the entire
7531
* key, go directly to the key and read through it (sorting backwards is
7532
* same as sorting forwards)
7533
* - if it is NEAR_MAX, go to the key or next, step back once, and
7535
* - otherwise (not NEAR_MAX == include the key), go after the key,
7536
* step back once, and move backwards
7543
{ // Already read through key
7544
result = ((last_range->flag & EQ_RANGE)
7545
? file->index_next_same(record, last_range->min_key,
7546
last_range->min_length) :
7547
file->index_prev(record));
7550
if (cmp_prev(*rev_it.ref()) == 0)
7553
else if (result != HA_ERR_END_OF_FILE)
7557
if (!(last_range= rev_it++))
7558
return HA_ERR_END_OF_FILE; // All ranges used
7560
if (last_range->flag & NO_MAX_RANGE) // Read last record
7563
if ((local_error=file->index_last(record)))
7564
return(local_error); // Empty table
7565
if (cmp_prev(last_range) == 0)
7567
last_range= 0; // No match; go to next range
7571
if (last_range->flag & EQ_RANGE)
7573
result = file->index_read_map(record, last_range->max_key,
7574
last_range->max_keypart_map,
7579
assert(last_range->flag & NEAR_MAX ||
7580
range_reads_after_key(last_range));
7581
result=file->index_read_map(record, last_range->max_key,
7582
last_range->max_keypart_map,
7583
((last_range->flag & NEAR_MAX) ?
7584
HA_READ_BEFORE_KEY :
7585
HA_READ_PREFIX_LAST_OR_PREV));
7589
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7591
last_range= 0; // Not found, to next range
7594
if (cmp_prev(last_range) == 0)
7596
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7597
last_range= 0; // Stop searching
7598
return 0; // Found key is in range
7600
last_range= 0; // To next range
7606
Compare if found key is over max-value
7607
Returns 0 if key <= range->max_key
7608
TODO: Figure out why can't this function be as simple as cmp_prev().
7611
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7613
if (range_arg->flag & NO_MAX_RANGE)
7614
return 0; /* key can't be to large */
7616
KEY_PART *key_part=key_parts;
7617
uint32_t store_length;
7619
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7621
key+= store_length, key_part++)
7624
store_length= key_part->store_length;
7625
if (key_part->null_bit)
7629
if (!key_part->field->is_null())
7633
else if (key_part->field->is_null())
7635
key++; // Skip null byte
7638
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7643
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7648
Returns 0 if found key is inside range (found key >= range->min_key).
7651
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7654
if (range_arg->flag & NO_MIN_RANGE)
7655
return 0; /* key can't be to small */
7657
cmp= key_cmp(key_part_info, range_arg->min_key,
7658
range_arg->min_length);
7659
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7661
return 1; // outside of range
7666
* true if this range will require using HA_READ_AFTER_KEY
7667
See comment in get_next() about this
7670
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7672
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7673
!(range_arg->flag & EQ_RANGE) ||
7674
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7678
void QUICK_RANGE_SELECT::add_info_string(String *str)
7680
KEY *key_info= head->key_info + index;
7681
str->append(key_info->name);
7684
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7686
QUICK_RANGE_SELECT *quick;
7688
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7689
str->append(STRING_WITH_LEN("sort_union("));
7690
while ((quick= it++))
7696
quick->add_info_string(str);
7698
if (pk_quick_select)
7701
pk_quick_select->add_info_string(str);
7706
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7709
QUICK_RANGE_SELECT *quick;
7710
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7711
str->append(STRING_WITH_LEN("intersect("));
7712
while ((quick= it++))
7714
KEY *key_info= head->key_info + quick->index;
7719
str->append(key_info->name);
7723
KEY *key_info= head->key_info + cpk_quick->index;
7725
str->append(key_info->name);
7730
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7733
QUICK_SELECT_I *quick;
7734
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7735
str->append(STRING_WITH_LEN("union("));
7736
while ((quick= it++))
7742
quick->add_info_string(str);
7748
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7749
String *used_lengths)
7753
KEY *key_info= head->key_info + index;
7754
key_names->append(key_info->name);
7755
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7756
used_lengths->append(buf, length);
7759
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7760
String *used_lengths)
7765
QUICK_RANGE_SELECT *quick;
7767
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7768
while ((quick= it++))
7774
key_names->append(',');
7775
used_lengths->append(',');
7778
KEY *key_info= head->key_info + quick->index;
7779
key_names->append(key_info->name);
7780
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7781
used_lengths->append(buf, length);
7783
if (pk_quick_select)
7785
KEY *key_info= head->key_info + pk_quick_select->index;
7786
key_names->append(',');
7787
key_names->append(key_info->name);
7788
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7789
used_lengths->append(',');
7790
used_lengths->append(buf, length);
7794
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7795
String *used_lengths)
7800
QUICK_RANGE_SELECT *quick;
7801
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7802
while ((quick= it++))
7804
KEY *key_info= head->key_info + quick->index;
7809
key_names->append(',');
7810
used_lengths->append(',');
7812
key_names->append(key_info->name);
7813
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7814
used_lengths->append(buf, length);
7819
KEY *key_info= head->key_info + cpk_quick->index;
7820
key_names->append(',');
7821
key_names->append(key_info->name);
7822
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7823
used_lengths->append(',');
7824
used_lengths->append(buf, length);
7828
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7829
String *used_lengths)
7832
QUICK_SELECT_I *quick;
7833
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7834
while ((quick= it++))
7840
used_lengths->append(',');
7841
key_names->append(',');
7843
quick->add_keys_and_lengths(key_names, used_lengths);
7848
/*******************************************************************************
7849
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7850
*******************************************************************************/
7852
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7853
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7854
PARAM *param, uint32_t *param_idx);
7855
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7856
KEY_PART_INFO *first_non_group_part,
7857
KEY_PART_INFO *min_max_arg_part,
7858
KEY_PART_INFO *last_part, Session *session,
7859
unsigned char *key_infix, uint32_t *key_infix_len,
7860
KEY_PART_INFO **first_non_infix_part);
4419
7861
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
4422
cost_group_min_max(Table* table,
4423
KeyInfo *index_info,
4424
uint32_t used_key_parts,
4425
uint32_t group_key_parts,
4426
optimizer::SEL_TREE *range_tree,
4427
optimizer::SEL_ARG *index_tree,
4428
ha_rows quick_prefix_records,
7864
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7865
uint32_t group_key_parts, SEL_TREE *range_tree,
7866
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7867
bool have_min, bool have_max,
7868
double *read_cost, ha_rows *records);
5553
optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5555
optimizer::QuickRangeSelect *quick= NULL;
5556
if ((quick= optimizer::get_quick_select(param,
5563
quick->records= records;
5564
quick->read_time= read_cost;
5570
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5572
boost::dynamic_bitset<> map= bitsToBitset();
5573
for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5584
size_t optimizer::RorScanInfo::getBitCount() const
5586
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5587
return tmp_bitset.count();
5591
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5593
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5594
tmp_bitset-= in_bitset;
5595
covered_fields= tmp_bitset.to_ulong();
5599
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5602
uint64_t conv= covered_fields;
5605
res.push_back((conv & 1) + '0');
5610
std::reverse(res.begin(), res.end());
5612
string final(covered_fields_size - res.length(), '0');
5614
return (boost::dynamic_bitset<>(final));
5618
} /* namespace drizzled */
8927
Construct new quick select for group queries with min/max.
8930
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8931
table The table being accessed
8932
join Descriptor of the current query
8933
have_min true if the query selects a MIN function
8934
have_max true if the query selects a MAX function
8935
min_max_arg_part The only argument field of all MIN/MAX functions
8936
group_prefix_len Length of all key parts in the group prefix
8937
prefix_key_parts All key parts in the group prefix
8938
index_info The index chosen for data access
8939
use_index The id of index_info
8940
read_cost Cost of this access method
8941
records Number of records returned
8942
key_infix_len Length of the key infix appended to the group prefix
8943
key_infix Infix of constants from equality predicates
8944
parent_alloc Memory pool for this and quick_prefix_select data
8950
QUICK_GROUP_MIN_MAX_SELECT::
8951
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8953
KEY_PART_INFO *min_max_arg_part_arg,
8954
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8955
uint32_t used_key_parts_arg, KEY *index_info_arg,
8956
uint32_t use_index, double read_cost_arg,
8957
ha_rows records_arg, uint32_t key_infix_len_arg,
8958
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8959
:join(join_arg), index_info(index_info_arg),
8960
group_prefix_len(group_prefix_len_arg),
8961
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8962
have_max(have_max_arg), seen_first_key(false),
8963
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8964
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8965
max_functions_it(NULL)
8970
record= head->record[0];
8971
tmp_record= head->record[1];
8972
read_time= read_cost_arg;
8973
records= records_arg;
8974
used_key_parts= used_key_parts_arg;
8975
real_key_parts= used_key_parts_arg;
8976
real_prefix_len= group_prefix_len + key_infix_len;
8978
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8981
We can't have parent_alloc set as the init function can't handle this case
8984
assert(!parent_alloc);
8987
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
8988
join->session->mem_root= &alloc;
8991
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8996
Do post-constructor initialization.
8999
QUICK_GROUP_MIN_MAX_SELECT::init()
9002
The method performs initialization that cannot be done in the constructor
9003
such as memory allocations that may fail. It allocates memory for the
9004
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
9005
updated during execution.
9012
int QUICK_GROUP_MIN_MAX_SELECT::init()
9014
if (group_prefix) /* Already initialized. */
9017
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
9020
We may use group_prefix to store keys with all select fields, so allocate
9021
enough space for it.
9023
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
9024
real_prefix_len + min_max_arg_len)))
9027
if (key_infix_len > 0)
9030
The memory location pointed to by key_infix will be deleted soon, so
9031
allocate a new buffer and copy the key_infix into it.
9033
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
9036
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
9037
this->key_infix= tmp_key_infix;
9040
if (min_max_arg_part)
9042
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
9047
if (!(min_functions= new List<Item_sum>))
9051
min_functions= NULL;
9054
if (!(max_functions= new List<Item_sum>))
9058
max_functions= NULL;
9060
Item_sum *min_max_item;
9061
Item_sum **func_ptr= join->sum_funcs;
9062
while ((min_max_item= *(func_ptr++)))
9064
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
9065
min_functions->push_back(min_max_item);
9066
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
9067
max_functions->push_back(min_max_item);
9072
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
9078
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
9083
min_max_ranges.elements= 0;
9089
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
9091
if (file->inited != Cursor::NONE)
9092
file->ha_index_end();
9093
if (min_max_arg_part)
9094
delete_dynamic(&min_max_ranges);
9095
free_root(&alloc,MYF(0));
9096
delete min_functions_it;
9097
delete max_functions_it;
9098
delete quick_prefix_select;
9103
Eventually create and add a new quick range object.
9106
QUICK_GROUP_MIN_MAX_SELECT::add_range()
9107
sel_range Range object from which a
9110
Construct a new QUICK_RANGE object from a SEL_ARG object, and
9111
add it to the array min_max_ranges. If sel_arg is an infinite
9112
range, e.g. (x < 5 or x > 4), then skip it and do not construct
9120
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
9123
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
9125
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
9126
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
9129
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
9130
!(sel_range->max_flag & NO_MAX_RANGE))
9132
if (sel_range->maybe_null &&
9133
sel_range->min_value[0] && sel_range->max_value[0])
9134
range_flag|= NULL_RANGE; /* IS NULL condition */
9135
else if (memcmp(sel_range->min_value, sel_range->max_value,
9136
min_max_arg_len) == 0)
9137
range_flag|= EQ_RANGE; /* equality condition */
9139
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
9140
make_keypart_map(sel_range->part),
9141
sel_range->max_value, min_max_arg_len,
9142
make_keypart_map(sel_range->part),
9146
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
9153
Opens the ranges if there are more conditions in quick_prefix_select than
9154
the ones used for jumping through the prefixes.
9157
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9160
quick_prefix_select is made over the conditions on the whole key.
9161
It defines a number of ranges of length x.
9162
However when jumping through the prefixes we use only the the first
9163
few most significant keyparts in the range key. However if there
9164
are more keyparts to follow the ones we are using we must make the
9165
condition on the key inclusive (because x < "ab" means
9166
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9167
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9169
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9171
if (quick_prefix_select &&
9172
group_prefix_len < quick_prefix_select->max_used_key_length)
9177
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9181
get_dynamic(arr, (unsigned char*)&range, inx);
9182
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9189
Determine the total number and length of the keys that will be used for
9193
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9196
The total length of the keys used for index lookup depends on whether
9197
there are any predicates referencing the min/max argument, and/or if
9198
the min/max argument field can be NULL.
9199
This function does an optimistic analysis whether the search key might
9200
be extended by a constant for the min/max keypart. It is 'optimistic'
9201
because during actual execution it may happen that a particular range
9202
is skipped, and then a shorter key will be used. However this is data
9203
dependent and can't be easily estimated here.
9209
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9211
max_used_key_length= real_prefix_len;
9212
if (min_max_ranges.elements > 0)
9214
QUICK_RANGE *cur_range;
9216
{ /* Check if the right-most range has a lower boundary. */
9217
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9218
min_max_ranges.elements - 1);
9219
if (!(cur_range->flag & NO_MIN_RANGE))
9221
max_used_key_length+= min_max_arg_len;
9227
{ /* Check if the left-most range has an upper boundary. */
9228
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9229
if (!(cur_range->flag & NO_MAX_RANGE))
9231
max_used_key_length+= min_max_arg_len;
9237
else if (have_min && min_max_arg_part &&
9238
min_max_arg_part->field->real_maybe_null())
9241
If a MIN/MAX argument value is NULL, we can quickly determine
9242
that we're in the beginning of the next group, because NULLs
9243
are always < any other value. This allows us to quickly
9244
determine the end of the current group and jump to the next
9245
group (see next_min()) and thus effectively increases the
9248
max_used_key_length+= min_max_arg_len;
9255
Initialize a quick group min/max select for key retrieval.
9258
QUICK_GROUP_MIN_MAX_SELECT::reset()
9261
Initialize the index chosen for access and find and store the prefix
9262
of the last group. The method is expensive since it performs disk access.
9269
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9273
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9274
if ((result= file->ha_index_init(index,1)))
9276
if (quick_prefix_select && quick_prefix_select->reset())
9278
result= file->index_last(record);
9279
if (result == HA_ERR_END_OF_FILE)
9281
/* Save the prefix of the last group. */
9282
key_copy(last_prefix, record, index_info, group_prefix_len);
9290
Get the next key containing the MIN and/or MAX key for the next group.
9293
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9296
The method finds the next subsequent group of records that satisfies the
9297
query conditions and finds the keys that contain the MIN/MAX values for
9298
the key part referenced by the MIN/MAX function(s). Once a group and its
9299
MIN/MAX values are found, store these values in the Item_sum objects for
9300
the MIN/MAX functions. The rest of the values in the result row are stored
9301
in the Item_field::result_field of each select field. If the query does
9302
not contain MIN and/or MAX functions, then the function only finds the
9303
group prefix, which is a query answer itself.
9306
If both MIN and MAX are computed, then we use the fact that if there is
9307
no MIN key, there can't be a MAX key as well, so we can skip looking
9308
for a MAX key in this case.
9312
HA_ERR_END_OF_FILE if returned all keys
9313
other if some error occurred
9316
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9321
int is_last_prefix= 0;
9324
Loop until a group is found that satisfies all query conditions or the last
9329
result= next_prefix();
9331
Check if this is the last group prefix. Notice that at this point
9332
this->record contains the current prefix in record format.
9336
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9338
assert(is_last_prefix <= 0);
9342
if (result == HA_ERR_KEY_NOT_FOUND)
9349
min_res= next_min();
9351
update_min_result();
9353
/* If there is no MIN in the group, there is no MAX either. */
9354
if ((have_max && !have_min) ||
9355
(have_max && have_min && (min_res == 0)))
9357
max_res= next_max();
9359
update_max_result();
9360
/* If a MIN was found, a MAX must have been found as well. */
9361
assert(((have_max && !have_min) ||
9362
(have_max && have_min && (max_res == 0))));
9365
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9366
are equality predicates for the key parts after the group, find the
9367
first sub-group with the extended prefix.
9369
if (!have_min && !have_max && key_infix_len > 0)
9370
result= file->index_read_map(record, group_prefix,
9371
make_prev_keypart_map(real_key_parts),
9374
result= have_min ? min_res : have_max ? max_res : result;
9375
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9376
is_last_prefix != 0);
9381
Partially mimic the behavior of end_select_send. Copy the
9382
field data from Item_field::field into Item_field::result_field
9383
of each non-aggregated field (the group fields, and optionally
9384
other fields in non-ANSI SQL mode).
9386
copy_fields(&join->tmp_table_param);
9388
else if (result == HA_ERR_KEY_NOT_FOUND)
9389
result= HA_ERR_END_OF_FILE;
9396
Retrieve the minimal key in the next group.
9399
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9402
Find the minimal key within this group such that the key satisfies the query
9403
conditions and NULL semantics. The found key is loaded into this->record.
9406
Depending on the values of min_max_ranges.elements, key_infix_len, and
9407
whether there is a NULL in the MIN field, this function may directly
9408
return without any data access. In this case we use the key loaded into
9409
this->record by the call to this->next_prefix() just before this call.
9413
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9414
HA_ERR_END_OF_FILE - "" -
9415
other if some error occurred
9418
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9422
/* Find the MIN key using the eventually extended group prefix. */
9423
if (min_max_ranges.elements > 0)
9425
if ((result= next_min_in_range()))
9430
/* Apply the constant equality conditions to the non-group select fields */
9431
if (key_infix_len > 0)
9433
if ((result= file->index_read_map(record, group_prefix,
9434
make_prev_keypart_map(real_key_parts),
9435
HA_READ_KEY_EXACT)))
9440
If the min/max argument field is NULL, skip subsequent rows in the same
9441
group with NULL in it. Notice that:
9442
- if the first row in a group doesn't have a NULL in the field, no row
9443
in the same group has (because NULL < any other value),
9444
- min_max_arg_part->field->ptr points to some place in 'record'.
9446
if (min_max_arg_part && min_max_arg_part->field->is_null())
9448
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9449
key_copy(tmp_record, record, index_info, 0);
9450
result= file->index_read_map(record, tmp_record,
9451
make_keypart_map(real_key_parts),
9454
Check if the new record belongs to the current group by comparing its
9455
prefix with the group's prefix. If it is from the next group, then the
9456
whole group has NULLs in the MIN/MAX field, so use the first record in
9457
the group as a result.
9459
It is possible to reuse this new record as the result candidate for the
9460
next call to next_min(), and to save one lookup in the next call. For
9461
this add a new member 'this->next_group_prefix'.
9465
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9466
key_restore(record, tmp_record, index_info, 0);
9468
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9469
result= 0; /* There is a result in any case. */
9474
If the MIN attribute is non-nullable, this->record already contains the
9475
MIN key in the group, so just return.
9482
Retrieve the maximal key in the next group.
9485
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9488
Lookup the maximal key of the group, and store it into this->record.
9492
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9493
HA_ERR_END_OF_FILE - "" -
9494
other if some error occurred
9497
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9501
/* Get the last key in the (possibly extended) group. */
9502
if (min_max_ranges.elements > 0)
9503
result= next_max_in_range();
9505
result= file->index_read_map(record, group_prefix,
9506
make_prev_keypart_map(real_key_parts),
9507
HA_READ_PREFIX_LAST);
9513
Determine the prefix of the next group.
9516
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9519
Determine the prefix of the next group that satisfies the query conditions.
9520
If there is a range condition referencing the group attributes, use a
9521
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9522
condition. If there is a key infix of constants, append this infix
9523
immediately after the group attributes. The possibly extended prefix is
9524
stored in this->group_prefix. The first key of the found group is stored in
9525
this->record, on which relies this->next_min().
9529
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9530
HA_ERR_END_OF_FILE if there are no more keys
9531
other if some error occurred
9533
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9537
if (quick_prefix_select)
9539
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9540
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9541
make_prev_keypart_map(group_key_parts), cur_prefix)))
9543
seen_first_key= true;
9547
if (!seen_first_key)
9549
result= file->index_first(record);
9552
seen_first_key= true;
9556
/* Load the first key in this group into record. */
9557
result= file->index_read_map(record, group_prefix,
9558
make_prev_keypart_map(group_key_parts),
9565
/* Save the prefix of this group for subsequent calls. */
9566
key_copy(group_prefix, record, index_info, group_prefix_len);
9567
/* Append key_infix to group_prefix. */
9568
if (key_infix_len > 0)
9569
memcpy(group_prefix + group_prefix_len,
9570
key_infix, key_infix_len);
9577
Find the minimal key in a group that satisfies some range conditions for the
9578
min/max argument field.
9581
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9584
Given the sequence of ranges min_max_ranges, find the minimal key that is
9585
in the left-most possible range. If there is no such key, then the current
9586
group does not have a MIN key that satisfies the WHERE clause. If a key is
9587
found, its value is stored in this->record.
9591
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9593
HA_ERR_END_OF_FILE - "" -
9597
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9599
ha_rkey_function find_flag;
9600
key_part_map keypart_map;
9601
QUICK_RANGE *cur_range;
9602
bool found_null= false;
9603
int result= HA_ERR_KEY_NOT_FOUND;
9604
basic_string<unsigned char> max_key;
9606
max_key.reserve(real_prefix_len + min_max_arg_len);
9608
assert(min_max_ranges.elements > 0);
9610
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9611
{ /* Search from the left-most range to the right. */
9612
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9615
If the current value for the min/max argument is bigger than the right
9616
boundary of cur_range, there is no need to check this range.
9618
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9619
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9620
min_max_arg_len) == 1))
9623
if (cur_range->flag & NO_MIN_RANGE)
9625
keypart_map= make_prev_keypart_map(real_key_parts);
9626
find_flag= HA_READ_KEY_EXACT;
9630
/* Extend the search key with the lower boundary for this range. */
9631
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9632
cur_range->min_length);
9633
keypart_map= make_keypart_map(real_key_parts);
9634
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9635
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9636
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9639
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9642
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9643
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9644
continue; /* Check the next range. */
9647
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9648
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9649
range, it can't succeed for any other subsequent range.
9654
/* A key was found. */
9655
if (cur_range->flag & EQ_RANGE)
9656
break; /* No need to perform the checks below for equal keys. */
9658
if (cur_range->flag & NULL_RANGE)
9661
Remember this key, and continue looking for a non-NULL key that
9662
satisfies some other condition.
9664
memcpy(tmp_record, record, head->s->rec_buff_length);
9669
/* Check if record belongs to the current group. */
9670
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9672
result= HA_ERR_KEY_NOT_FOUND;
9676
/* If there is an upper limit, check if the found key is in the range. */
9677
if ( !(cur_range->flag & NO_MAX_RANGE) )
9679
/* Compose the MAX key for the range. */
9681
max_key.append(group_prefix, real_prefix_len);
9682
max_key.append(cur_range->max_key, cur_range->max_length);
9683
/* Compare the found key with max_key. */
9684
int cmp_res= key_cmp(index_info->key_part,
9686
real_prefix_len + min_max_arg_len);
9687
if (!(((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
9690
result= HA_ERR_KEY_NOT_FOUND;
9694
/* If we got to this point, the current key qualifies as MIN. */
9695
assert(result == 0);
9699
If there was a key with NULL in the MIN/MAX field, and there was no other
9700
key without NULL from the same group that satisfies some other condition,
9701
then use the key with the NULL.
9703
if (found_null && result)
9705
memcpy(record, tmp_record, head->s->rec_buff_length);
9713
Find the maximal key in a group that satisfies some range conditions for the
9714
min/max argument field.
9717
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9720
Given the sequence of ranges min_max_ranges, find the maximal key that is
9721
in the right-most possible range. If there is no such key, then the current
9722
group does not have a MAX key that satisfies the WHERE clause. If a key is
9723
found, its value is stored in this->record.
9727
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9729
HA_ERR_END_OF_FILE - "" -
9733
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9735
ha_rkey_function find_flag;
9736
key_part_map keypart_map;
9737
QUICK_RANGE *cur_range;
9739
basic_string<unsigned char> min_key;
9740
min_key.reserve(real_prefix_len + min_max_arg_len);
9742
assert(min_max_ranges.elements > 0);
9744
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9745
{ /* Search from the right-most range to the left. */
9746
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9749
If the current value for the min/max argument is smaller than the left
9750
boundary of cur_range, there is no need to check this range.
9752
if (range_idx != min_max_ranges.elements &&
9753
!(cur_range->flag & NO_MIN_RANGE) &&
9754
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9755
min_max_arg_len) == -1))
9758
if (cur_range->flag & NO_MAX_RANGE)
9760
keypart_map= make_prev_keypart_map(real_key_parts);
9761
find_flag= HA_READ_PREFIX_LAST;
9765
/* Extend the search key with the upper boundary for this range. */
9766
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9767
cur_range->max_length);
9768
keypart_map= make_keypart_map(real_key_parts);
9769
find_flag= (cur_range->flag & EQ_RANGE) ?
9770
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9771
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9774
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9778
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9779
(cur_range->flag & EQ_RANGE))
9780
continue; /* Check the next range. */
9783
In no key was found with this upper bound, there certainly are no keys
9784
in the ranges to the left.
9788
/* A key was found. */
9789
if (cur_range->flag & EQ_RANGE)
9790
return 0; /* No need to perform the checks below for equal keys. */
9792
/* Check if record belongs to the current group. */
9793
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9794
continue; // Row not found
9796
/* If there is a lower limit, check if the found key is in the range. */
9797
if ( !(cur_range->flag & NO_MIN_RANGE) )
9799
/* Compose the MIN key for the range. */
9801
min_key.append(group_prefix, real_prefix_len);
9802
min_key.append(cur_range->min_key, cur_range->min_length);
9804
/* Compare the found key with min_key. */
9805
int cmp_res= key_cmp(index_info->key_part,
9807
real_prefix_len + min_max_arg_len);
9808
if (!(((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9812
/* If we got to this point, the current key qualifies as MAX. */
9815
return HA_ERR_KEY_NOT_FOUND;
9820
Update all MIN function results with the newly found value.
9823
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9826
The method iterates through all MIN functions and updates the result value
9827
of each function by calling Item_sum::reset(), which in turn picks the new
9828
result value from this->head->record[0], previously updated by
9829
next_min(). The updated value is stored in a member variable of each of the
9830
Item_sum objects, depending on the value type.
9833
The update must be done separately for MIN and MAX, immediately after
9834
next_min() was called and before next_max() is called, because both MIN and
9835
MAX take their result value from the same buffer this->head->record[0]
9836
(i.e. this->record).
9842
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9846
min_functions_it->rewind();
9847
while ((min_func= (*min_functions_it)++))
9853
Update all MAX function results with the newly found value.
9856
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9859
The method iterates through all MAX functions and updates the result value
9860
of each function by calling Item_sum::reset(), which in turn picks the new
9861
result value from this->head->record[0], previously updated by
9862
next_max(). The updated value is stored in a member variable of each of the
9863
Item_sum objects, depending on the value type.
9866
The update must be done separately for MIN and MAX, immediately after
9867
next_max() was called, because both MIN and MAX take their result value
9868
from the same buffer this->head->record[0] (i.e. this->record).
9874
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9878
max_functions_it->rewind();
9879
while ((max_func= (*max_functions_it)++))
9885
Append comma-separated list of keys this quick select uses to key_names;
9886
append comma-separated list of corresponding used lengths to used_lengths.
9889
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9890
key_names [out] Names of used indexes
9891
used_lengths [out] Corresponding lengths of the index names
9894
This method is used by select_describe to extract the names of the
9895
indexes used by a quick select.
9899
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9900
String *used_lengths)
9904
key_names->append(index_info->name);
9905
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9906
used_lengths->append(buf, length);
9909
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9911
SEL_ARG **key,**end;
9915
String tmp(buff,sizeof(buff),&my_charset_bin);
9917
for (idx= 0,key=tree->keys, end=key+param->keys ;
9921
if (tree_map->test(idx))
9923
uint32_t keynr= param->real_keynr[idx];
9926
tmp.append(param->table->key_info[keynr].name);
9930
tmp.append(STRING_WITH_LEN("(empty)"));
9934
static void print_ror_scans_arr(Table *table,
9935
const char *, struct st_ror_scan_info **start,
9936
struct st_ror_scan_info **end)
9939
String tmp(buff,sizeof(buff),&my_charset_bin);
9941
for (;start != end; start++)
9945
tmp.append(table->key_info[(*start)->keynr].name);
9948
tmp.append(STRING_WITH_LEN("(empty)"));
9951
/*****************************************************************************
9952
** Instantiate templates
9953
*****************************************************************************/
9955
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9956
template class List<QUICK_RANGE>;
9957
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
