« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1237.13.6
- compare with another revision
- compare with revision 2466
- download diff
- download tarball
- view history from revision 1237.13.6
- Committer: Padraig O'Sullivan
- Date: 2009-12-08 00:22:46 UTC
- mto: (1192.3.76 pandora-build) (1240.3.1 build) (1241.2.6 build)
- mto: This revision was merged to the branch mainline in revision 1241.
- Revision ID: osullivan.padraig@gmail.com-20091208002246-uxc0f5ralh958u1v
Moved the SEL_ARG class into its own header and implementation files. Cleaned up a bunch of style
issues in the code for that class. Next commit will clean up more style issues in that class.
issues in the code for that class. Next commit will clean up more style issues in that class.
added
removed
drizzled/optimizer/range.cc
120
120
#include "drizzled/optimizer/quick_range.h"
121
121
#include "drizzled/optimizer/quick_range_select.h"
122
122
#include "drizzled/optimizer/quick_index_merge_select.h"
123
#include "drizzled/optimizer/sel_arg.h"
124
#include "drizzled/optimizer/range_param.h"
123
125
#include "drizzled/records.h"
124
126
125
127
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
144
146
return static_cast<ha_rows>(x);
145
147
}
146
148
147
static int sel_cmp(Field *f, unsigned char *a, unsigned char *b, uint8_t a_flag, uint8_t b_flag);
148
149
149
static unsigned char is_null_string[2]= {1,0};
150
150
151
151
224
224
}
225
225
}
226
226
227
class RANGE_OPT_PARAM;
228
/*
229
A construction block of the SEL_ARG-graph.
230
231
The following description only covers graphs of SEL_ARG objects with
232
sel_arg->type==KEY_RANGE:
233
234
One SEL_ARG object represents an "elementary interval" in form
235
236
min_value <=? table.keypartX <=? max_value
237
238
The interval is a non-empty interval of any kind: with[out] minimum/maximum
239
bound, [half]open/closed, single-point interval, etc.
240
241
1. SEL_ARG GRAPH STRUCTURE
242
243
SEL_ARG objects are linked together in a graph. The meaning of the graph
244
is better demostrated by an example:
245
246
tree->keys[i]
247
|
248
| $ $
249
| part=1 $ part=2 $ part=3
250
| $ $
251
| +-------+ $ +-------+ $ +--------+
252
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
253
| +-------+ $ +-------+ $ +--------+
254
| | $ $ |
255
| | $ $ +--------+
256
| | $ $ | kp3=12 |
257
| | $ $ +--------+
258
| +-------+ $ $
259
\->| kp1=2 |--$--------------$-+
260
+-------+ $ $ | +--------+
261
| $ $ ==>| kp3=11 |
262
+-------+ $ $ | +--------+
263
| kp1=3 |--$--------------$-+ |
264
+-------+ $ $ +--------+
265
| $ $ | kp3=14 |
266
... $ $ +--------+
267
268
The entire graph is partitioned into "interval lists".
269
270
An interval list is a sequence of ordered disjoint intervals over the same
271
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
272
all intervals in the list form an RB-tree, linked via left/right/parent
273
pointers. The RB-tree root SEL_ARG object will be further called "root of the
274
interval list".
275
276
In the example pic, there are 4 interval lists:
277
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
278
The vertical lines represent SEL_ARG::next/prev pointers.
279
280
In an interval list, each member X may have SEL_ARG::next_key_part pointer
281
pointing to the root of another interval list Y. The pointed interval list
282
must cover a key part with greater number (i.e. Y->part > X->part).
283
284
In the example pic, the next_key_part pointers are represented by
285
horisontal lines.
286
287
2. SEL_ARG GRAPH SEMANTICS
288
289
It represents a condition in a special form (we don't have a name for it ATM)
290
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
291
292
For example, the picture represents the condition in form:
293
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
294
(kp1=2 AND (kp3=11 OR kp3=14)) OR
295
(kp1=3 AND (kp3=11 OR kp3=14))
296
297
298
3. SEL_ARG GRAPH USE
299
300
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
301
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
302
intervals (i.e. intervals in form
303
304
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
305
306
Those intervals can be used to access the index. The uses are in:
307
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
308
how many table records are contained within all
309
intervals.
310
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
311
and create QuickRangeSelect object that will
312
read records within these intervals.
313
314
4. SPACE COMPLEXITY NOTES
315
316
SEL_ARG graph is a representation of an ordered disjoint sequence of
317
intervals over the ordered set of index tuple values.
318
319
For multi-part keys, one can construct a WHERE expression such that its
320
list of intervals will be of combinatorial size. Here is an example:
321
322
(keypart1 IN (1,2, ..., n1)) AND
323
(keypart2 IN (1,2, ..., n2)) AND
324
(keypart3 IN (1,2, ..., n3))
325
326
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
327
of form
328
329
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
330
331
SEL_ARG graph structure aims to reduce the amount of required space by
332
"sharing" the elementary intervals when possible (the pic at the
333
beginning of this comment has examples of such sharing). The sharing may
334
prevent combinatorial blowup:
335
336
There are WHERE clauses that have combinatorial-size interval lists but
337
will be represented by a compact SEL_ARG graph.
338
Example:
339
(keypartN IN (1,2, ..., n1)) AND
340
...
341
(keypart2 IN (1,2, ..., n2)) AND
342
(keypart1 IN (1,2, ..., n3))
343
344
but not in all cases:
345
346
- There are WHERE clauses that do have a compact SEL_ARG-graph
347
representation but get_mm_tree() and its callees will construct a
348
graph of combinatorial size.
349
Example:
350
(keypart1 IN (1,2, ..., n1)) AND
351
(keypart2 IN (1,2, ..., n2)) AND
352
...
353
(keypartN IN (1,2, ..., n3))
354
355
- There are WHERE clauses for which the minimal possible SEL_ARG graph
356
representation will have combinatorial size.
357
Example:
358
By induction: Let's take any interval on some keypart in the middle:
359
360
kp15=c0
361
362
Then let's AND it with this interval 'structure' from preceding and
363
following keyparts:
364
365
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
366
367
We will obtain this SEL_ARG graph:
368
369
kp14 $ kp15 $ kp16
370
$ $
371
+---------+ $ +---------+ $ +---------+
372
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
373
+---------+ $ +---------+ $ +---------+
374
| $ $
375
+---------+ $ +---------+ $
376
| kp14=c2 |--$-->| kp15=c0 | $
377
+---------+ $ +---------+ $
378
$ $
379
380
Note that we had to duplicate "kp15=c0" and there was no way to avoid
381
that.
382
The induction step: AND the obtained expression with another "wrapping"
383
expression like (*).
384
When the process ends because of the limit on max. number of keyparts
385
we'll have:
386
387
WHERE clause length is O(3*#max_keyparts)
388
SEL_ARG graph size is O(2^(#max_keyparts/2))
389
390
(it is also possible to construct a case where instead of 2 in 2^n we
391
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
392
nodes)
393
394
We avoid consuming too much memory by setting a limit on the number of
395
SEL_ARG object we can construct during one range analysis invocation.
396
*/
397
398
class SEL_ARG :public Sql_alloc
399
{
400
public:
401
uint8_t min_flag,max_flag,maybe_flag;
402
uint8_t part; // Which key part
403
uint8_t maybe_null;
404
/*
405
Number of children of this element in the RB-tree, plus 1 for this
406
element itself.
407
*/
408
uint16_t elements;
409
/*
410
Valid only for elements which are RB-tree roots: Number of times this
411
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
412
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
413
*/
414
ulong use_count;
415
416
Field *field;
417
unsigned char *min_value,*max_value; // Pointer to range
418
419
/*
420
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
421
*/
422
SEL_ARG *left,*right; /* R-B tree children */
423
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
424
SEL_ARG *parent; /* R-B tree parent */
425
SEL_ARG *next_key_part;
426
enum leaf_color { BLACK,RED } color;
427
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
428
429
enum { MAX_SEL_ARGS = 16000 };
430
431
SEL_ARG() {}
432
433
SEL_ARG(SEL_ARG &);
434
435
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
436
437
SEL_ARG(Field *field,
438
uint8_t part,
439
unsigned char *min_value,
440
unsigned char *max_value,
441
uint8_t min_flag,
442
uint8_t max_flag,
443
uint8_t maybe_flag);
444
445
SEL_ARG(enum Type type_arg)
446
:
447
min_flag(0),
448
elements(1),
449
use_count(1),
450
left(0),
451
right(0),
452
next_key_part(0),
453
color(BLACK),
454
type(type_arg)
455
{}
456
457
inline bool is_same(SEL_ARG *arg)
458
{
459
if (type != arg->type || part != arg->part)
460
return 0;
461
if (type != KEY_RANGE)
462
return 1;
463
return (cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0);
464
}
465
466
inline void merge_flags(SEL_ARG *arg)
467
{
468
maybe_flag|= arg->maybe_flag;
469
}
470
471
inline void maybe_smaller()
472
{
473
maybe_flag= 1;
474
}
475
476
/* Return true iff it's a single-point null interval */
477
inline bool is_null_interval()
478
{
479
return (maybe_null && max_value[0] == 1);
480
}
481
482
inline int cmp_min_to_min(SEL_ARG *arg)
483
{
484
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
485
}
486
487
inline int cmp_min_to_max(SEL_ARG *arg)
488
{
489
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
490
}
491
492
inline int cmp_max_to_max(SEL_ARG *arg)
493
{
494
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
495
}
496
497
inline int cmp_max_to_min(SEL_ARG *arg)
498
{
499
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
500
}
501
502
SEL_ARG *clone_and(SEL_ARG *arg)
503
{ // Get overlapping range
504
unsigned char *new_min= NULL;
505
unsigned char *new_max= NULL;
506
uint8_t flag_min;
507
uint8_t flag_max;
508
509
if (cmp_min_to_min(arg) >= 0)
510
{
511
new_min= min_value;
512
flag_min= min_flag;
513
}
514
else
515
{
516
new_min=arg->min_value; flag_min=arg->min_flag;
517
}
518
if (cmp_max_to_max(arg) <= 0)
519
{
520
new_max= max_value;
521
flag_max= max_flag;
522
}
523
else
524
{
525
new_max= arg->max_value;
526
flag_max= arg->max_flag;
527
}
528
return (new SEL_ARG(field,
529
part,
530
new_min,
531
new_max,
532
flag_min,
533
flag_max,
534
test(maybe_flag && arg->maybe_flag)));
535
}
536
537
SEL_ARG *clone_first(SEL_ARG *arg)
538
{ // min <= X < arg->min
539
return (new SEL_ARG(field,part,
540
min_value,
541
arg->min_value,
542
min_flag,
543
arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
544
maybe_flag | arg->maybe_flag));
545
}
546
547
SEL_ARG *clone_last(SEL_ARG *arg)
548
{ // min <= X <= key_max
549
return (new SEL_ARG(field,
550
part,
551
min_value,
552
arg->max_value,
553
min_flag,
554
arg->max_flag,
555
maybe_flag | arg->maybe_flag));
556
}
557
558
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
559
560
bool copy_min(SEL_ARG *arg)
561
{ // Get overlapping range
562
if (cmp_min_to_min(arg) > 0)
563
{
564
min_value= arg->min_value;
565
min_flag=arg->min_flag;
566
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
567
(NO_MAX_RANGE | NO_MIN_RANGE))
568
{
569
return 1; // Full range
570
}
571
}
572
maybe_flag|= arg->maybe_flag;
573
return 0;
574
}
575
576
bool copy_max(SEL_ARG *arg)
577
{ // Get overlapping range
578
if (cmp_max_to_max(arg) <= 0)
579
{
580
max_value= arg->max_value;
581
max_flag= arg->max_flag;
582
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
583
(NO_MAX_RANGE | NO_MIN_RANGE))
584
{
585
return 1; // Full range
586
}
587
}
588
maybe_flag|= arg->maybe_flag;
589
return 0;
590
}
591
592
void copy_min_to_min(SEL_ARG *arg)
593
{
594
min_value= arg->min_value;
595
min_flag= arg->min_flag;
596
}
597
598
void copy_min_to_max(SEL_ARG *arg)
599
{
600
max_value= arg->min_value;
601
max_flag= arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
602
}
603
604
void copy_max_to_min(SEL_ARG *arg)
605
{
606
min_value= arg->max_value;
607
min_flag= arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
608
}
609
610
/* returns a number of keypart values (0 or 1) appended to the key buffer */
611
int store_min(uint32_t length, unsigned char **min_key, uint32_t min_key_flag)
612
{
613
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
614
if ((! (min_flag & NO_MIN_RANGE) &&
615
! (min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
616
{
617
if (maybe_null && *min_value)
618
{
619
**min_key= 1;
620
memset(*min_key+1, 0, length-1);
621
}
622
else
623
{
624
memcpy(*min_key,min_value,length);
625
}
626
(*min_key)+= length;
627
return 1;
628
}
629
return 0;
630
}
631
632
/* returns a number of keypart values (0 or 1) appended to the key buffer */
633
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
634
{
635
if (! (max_flag & NO_MAX_RANGE) &&
636
! (max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
637
{
638
if (maybe_null && *max_value)
639
{
640
**max_key= 1;
641
memset(*max_key + 1, 0, length-1);
642
}
643
else
644
{
645
memcpy(*max_key,max_value,length);
646
}
647
(*max_key)+= length;
648
return 1;
649
}
650
return 0;
651
}
652
653
/* returns a number of keypart values appended to the key buffer */
654
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
655
{
656
SEL_ARG *key_tree= first();
657
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
658
range_key,
659
*range_key_flag);
660
*range_key_flag|= key_tree->min_flag;
661
662
if (key_tree->next_key_part &&
663
key_tree->next_key_part->part == key_tree->part+1 &&
664
! (*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
665
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
666
{
667
res+= key_tree->next_key_part->store_min_key(key,
668
range_key,
669
range_key_flag);
670
}
671
return res;
672
}
673
674
/* returns a number of keypart values appended to the key buffer */
675
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
676
{
677
SEL_ARG *key_tree= last();
678
uint32_t res= key_tree->store_max(key[key_tree->part].store_length,
679
range_key,
680
*range_key_flag);
681
(*range_key_flag)|= key_tree->max_flag;
682
if (key_tree->next_key_part &&
683
key_tree->next_key_part->part == key_tree->part+1 &&
684
! (*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
685
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
686
res+= key_tree->next_key_part->store_max_key(key,
687
range_key,
688
range_key_flag);
689
return res;
690
}
691
692
SEL_ARG *insert(SEL_ARG *key);
693
SEL_ARG *tree_delete(SEL_ARG *key);
694
SEL_ARG *find_range(SEL_ARG *key);
695
SEL_ARG *rb_insert(SEL_ARG *leaf);
696
697
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
698
#ifdef EXTRA_DEBUG
699
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
700
void test_use_count(SEL_ARG *root);
701
#endif
702
SEL_ARG *first();
703
SEL_ARG *last();
704
void make_root();
705
706
inline bool simple_key()
707
{
708
return (! next_key_part && elements == 1);
709
}
710
711
void increment_use_count(long count)
712
{
713
if (next_key_part)
714
{
715
next_key_part->use_count+= count;
716
count*= (next_key_part->use_count - count);
717
for (SEL_ARG *pos= next_key_part->first(); pos; pos= pos->next)
718
if (pos->next_key_part)
719
pos->increment_use_count(count);
720
}
721
}
722
723
void free_tree()
724
{
725
for (SEL_ARG *pos= first(); pos; pos= pos->next)
726
if (pos->next_key_part)
727
{
728
pos->next_key_part->use_count--;
729
pos->next_key_part->free_tree();
730
}
731
}
732
733
inline SEL_ARG **parent_ptr()
734
{
735
return parent->left == this ? &parent->left : &parent->right;
736
}
737
738
739
/*
740
Check if this SEL_ARG object represents a single-point interval
741
742
SYNOPSIS
743
is_singlepoint()
744
745
DESCRIPTION
746
Check if this SEL_ARG object (not tree) represents a single-point
747
interval, i.e. if it represents a "keypart = const" or
748
"keypart IS NULL".
749
750
RETURN
751
true This SEL_ARG object represents a singlepoint interval
752
false Otherwise
753
*/
754
755
bool is_singlepoint()
756
{
757
/*
758
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
759
flags, and the same for right edge.
760
*/
761
if (min_flag || max_flag)
762
return false;
763
unsigned char *min_val= min_value;
764
unsigned char *max_val= max_value;
765
766
if (maybe_null)
767
{
768
/* First byte is a NULL value indicator */
769
if (*min_val != *max_val)
770
return false;
771
772
if (*min_val)
773
return true; /* This "x IS NULL" */
774
min_val++;
775
max_val++;
776
}
777
return ! field->key_cmp(min_val, max_val);
778
}
779
780
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
781
};
782
783
227
class SEL_IMERGE;
784
228
785
229
788
232
public:
789
233
/*
790
234
Starting an effort to document this field:
791
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
235
(for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
792
236
(type == SEL_TREE::IMPOSSIBLE)
793
237
*/
794
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
238
enum Type
239
{
240
IMPOSSIBLE,
241
ALWAYS,
242
MAYBE,
243
KEY,
244
KEY_SMALLER
245
} type;
246
795
247
SEL_TREE(enum Type type_arg) :type(type_arg) {}
796
248
SEL_TREE() :type(KEY)
797
249
{
804
256
merit in range analyzer functions (e.g. get_mm_parts) returning a
805
257
pointer to such SEL_TREE instead of NULL)
806
258
*/
807
SEL_ARG *keys[MAX_KEY];
259
optimizer::SEL_ARG *keys[MAX_KEY];
808
260
key_map keys_map; /* bitmask of non-NULL elements in keys */
809
261
810
262
/*
822
274
/* Note that #records for each key scan is stored in table->quick_rows */
823
275
};
824
276
825
class RANGE_OPT_PARAM
826
{
827
public:
828
Session *session; /* Current thread handle */
829
Table *table; /* Table being analyzed */
830
COND *cond; /* Used inside get_mm_tree(). */
831
table_map prev_tables;
832
table_map read_tables;
833
table_map current_table; /* Bit of the table being analyzed */
834
835
/* Array of parts of all keys for which range analysis is performed */
836
KEY_PART *key_parts;
837
KEY_PART *key_parts_end;
838
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
839
MEM_ROOT *old_root; /* Memory that will last until the query end */
840
/*
841
Number of indexes used in range analysis (In SEL_TREE::keys only first
842
#keys elements are not empty)
843
*/
844
uint32_t keys;
845
846
/*
847
If true, the index descriptions describe real indexes (and it is ok to
848
call field->optimize_range(real_keynr[...], ...).
849
Otherwise index description describes fake indexes.
850
*/
851
bool using_real_indexes;
852
853
bool remove_jump_scans;
854
855
/*
856
used_key_no -> table_key_no translation table. Only makes sense if
857
using_real_indexes==true
858
*/
859
uint32_t real_keynr[MAX_KEY];
860
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
861
uint32_t alloced_sel_args;
862
bool force_default_mrr;
863
};
864
865
class PARAM : public RANGE_OPT_PARAM
866
{
867
public:
868
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
869
uint32_t max_key_part;
870
/* Number of ranges in the last checked tree->key */
871
uint32_t range_count;
872
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
873
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
874
bool quick; // Don't calulate possible keys
875
876
uint32_t fields_bitmap_size;
877
MyBitmap needed_fields; /* bitmask of fields needed by the query */
878
MyBitmap tmp_covered_fields;
879
880
key_map *needed_reg; /* ptr to SqlSelect::needed_reg */
881
882
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
883
uint32_t imerge_cost_buff_size; /* size of the buffer */
884
885
/* true if last checked tree->key can be used for ROR-scan */
886
bool is_ror_scan;
887
/* Number of ranges in the last checked tree->key */
888
uint32_t n_ranges;
889
};
890
891
277
class TABLE_READ_PLAN;
892
278
class TRP_RANGE;
893
279
class TRP_ROR_INTERSECT;
897
283
898
284
struct st_ror_scan_info;
899
285
900
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,
286
static SEL_TREE * get_mm_parts(optimizer::RANGE_OPT_PARAM *param,
901
287
COND *cond_func,
902
288
Field *field,
903
289
Item_func::Functype type,
904
290
Item *value,
905
291
Item_result cmp_type);
906
292
907
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,
908
COND *cond_func,Field *field,
909
KEY_PART *key_part,
910
Item_func::Functype type,Item *value);
911
912
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
913
914
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
915
916
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
917
SEL_ARG *tree, bool update_tbl_stats,
918
uint32_t *mrr_flags, uint32_t *bufsize,
293
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RANGE_OPT_PARAM *param,
294
COND *cond_func,
295
Field *field,
296
KEY_PART *key_part,
297
Item_func::Functype type,
298
Item *value);
299
300
static SEL_TREE *get_mm_tree(optimizer::RANGE_OPT_PARAM *param, COND *cond);
301
302
static bool is_key_scan_ror(optimizer::PARAM *param, uint32_t keynr, uint8_t nparts);
303
304
static ha_rows check_quick_select(optimizer::PARAM *param,
305
uint32_t idx,
306
bool index_only,
307
optimizer::SEL_ARG *tree,
308
bool update_tbl_stats,
309
uint32_t *mrr_flags,
310
uint32_t *bufsize,
919
311
COST_VECT *cost);
920
312
921
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
313
static TRP_RANGE *get_key_scans_params(optimizer::PARAM *param,
314
SEL_TREE *tree,
922
315
bool index_read_must_be_used,
923
316
bool update_tbl_stats,
924
317
double read_time);
925
318
926
319
static
927
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
320
TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::PARAM *param,
321
SEL_TREE *tree,
928
322
double read_time,
929
323
bool *are_all_covering);
930
324
931
325
static
932
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
326
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::PARAM *param,
933
327
SEL_TREE *tree,
934
328
double read_time);
935
329
936
330
static
937
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param,
331
TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::PARAM *param,
938
332
SEL_IMERGE *imerge,
939
333
double read_time);
940
334
941
335
static
942
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
336
TRP_GROUP_MIN_MAX *get_best_group_min_max(optimizer::PARAM *param, SEL_TREE *tree);
943
337
944
static void print_sel_tree(PARAM *param,
338
static void print_sel_tree(optimizer::PARAM *param,
945
339
SEL_TREE *tree,
946
340
key_map *tree_map,
947
341
const char *msg);
951
345
struct st_ror_scan_info **start,
952
346
struct st_ror_scan_info **end);
953
347
954
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
955
956
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
957
958
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
959
960
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
961
962
static SEL_ARG *key_and(RANGE_OPT_PARAM *param,
963
SEL_ARG *key1,
964
SEL_ARG *key2,
965
uint32_t clone_flag);
966
967
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
968
969
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
970
971
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
348
static SEL_TREE *tree_and(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2);
349
350
static SEL_TREE *tree_or(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2);
351
352
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
353
354
static optimizer::SEL_ARG *key_or(optimizer::RANGE_OPT_PARAM *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
355
356
static optimizer::SEL_ARG *key_and(optimizer::RANGE_OPT_PARAM *param,
357
optimizer::SEL_ARG *key1,
358
optimizer::SEL_ARG *key2,
359
uint32_t clone_flag);
360
361
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
362
363
static bool eq_tree(optimizer::SEL_ARG* a, optimizer::SEL_ARG *b);
364
365
optimizer::SEL_ARG drizzled::optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
972
366
973
367
static bool null_part_in_key(KEY_PART *key_part,
974
368
const unsigned char *key,
975
369
uint32_t length);
976
370
977
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
371
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RANGE_OPT_PARAM *param);
978
372
979
373
980
374
/*
999
393
SEL_TREE **trees_next; /* last of these trees */
1000
394
SEL_TREE **trees_end; /* end of allocated space */
1001
395
1002
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
396
optimizer::SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
1003
397
1004
398
SEL_IMERGE() :
1005
399
trees(&trees_prealloced[0]),
1006
400
trees_next(trees),
1007
401
trees_end(trees + PREALLOCED_TREES)
1008
402
{}
1009
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
1010
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
1011
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
403
int or_sel_tree(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *tree);
404
int or_sel_tree_with_checks(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
405
int or_sel_imerge_with_checks(optimizer::RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
1012
406
};
1013
407
1014
408
1023
417
0 - OK
1024
418
-1 - Out of memory.
1025
419
*/
1026
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
420
int SEL_IMERGE::or_sel_tree(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *tree)
1027
421
{
1028
422
if (trees_next == trees_end)
1029
423
{
1073
467
and (*this) should be discarded.
1074
468
-1 An error occurred.
1075
469
*/
1076
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
470
int SEL_IMERGE::or_sel_tree_with_checks(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
1077
471
{
1078
472
for (SEL_TREE** tree = trees;
1079
473
tree != trees_next;
1107
501
-1 - An error occurred
1108
502
*/
1109
503
1110
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
504
int SEL_IMERGE::or_sel_imerge_with_checks(optimizer::RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
1111
505
{
1112
506
for (SEL_TREE** tree= imerge->trees;
1113
507
tree != imerge->trees_next;
1153
547
other Error, both passed lists are unusable
1154
548
*/
1155
549
1156
static int imerge_list_or_list(RANGE_OPT_PARAM *param,
550
static int imerge_list_or_list(optimizer::RANGE_OPT_PARAM *param,
1157
551
List<SEL_IMERGE> *im1,
1158
552
List<SEL_IMERGE> *im2)
1159
553
{
1173
567
other Error
1174
568
*/
1175
569
1176
static int imerge_list_or_tree(RANGE_OPT_PARAM *param,
570
static int imerge_list_or_tree(optimizer::RANGE_OPT_PARAM *param,
1177
571
List<SEL_IMERGE> *im1,
1178
572
SEL_TREE *tree)
1179
573
{
1581
975
}
1582
976
1583
977
1584
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1585
{
1586
type=arg.type;
1587
min_flag=arg.min_flag;
1588
max_flag=arg.max_flag;
1589
maybe_flag=arg.maybe_flag;
1590
maybe_null=arg.maybe_null;
1591
part=arg.part;
1592
field=arg.field;
1593
min_value=arg.min_value;
1594
max_value=arg.max_value;
1595
next_key_part=arg.next_key_part;
1596
use_count=1; elements=1;
1597
}
1598
1599
1600
inline void SEL_ARG::make_root()
1601
{
1602
left=right= &null_element;
1603
color=BLACK;
1604
next=prev=0;
1605
use_count=0; elements=1;
1606
}
1607
1608
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1609
const unsigned char *max_value_arg)
1610
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1611
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1612
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1613
next_key_part(0),color(BLACK),type(KEY_RANGE)
1614
{
1615
left=right= &null_element;
1616
}
1617
1618
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1619
unsigned char *min_value_, unsigned char *max_value_,
1620
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1621
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1622
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1623
field(field_), min_value(min_value_), max_value(max_value_),
1624
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1625
{
1626
left=right= &null_element;
1627
}
1628
1629
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1630
SEL_ARG **next_arg)
1631
{
1632
SEL_ARG *tmp;
1633
1634
/* Bail out if we have already generated too many SEL_ARGs */
1635
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1636
return 0;
1637
1638
if (type != KEY_RANGE)
1639
{
1640
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1641
return 0; // out of memory
1642
tmp->prev= *next_arg; // Link into next/prev chain
1643
(*next_arg)->next=tmp;
1644
(*next_arg)= tmp;
1645
}
1646
else
1647
{
1648
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1649
min_flag, max_flag, maybe_flag)))
1650
return 0; // OOM
1651
tmp->parent=new_parent;
1652
tmp->next_key_part=next_key_part;
1653
if (left != &null_element)
1654
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1655
return 0; // OOM
1656
1657
tmp->prev= *next_arg; // Link into next/prev chain
1658
(*next_arg)->next=tmp;
1659
(*next_arg)= tmp;
1660
1661
if (right != &null_element)
1662
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1663
return 0; // OOM
1664
}
1665
increment_use_count(1);
1666
tmp->color= color;
1667
tmp->elements= this->elements;
1668
return tmp;
1669
}
1670
1671
SEL_ARG *SEL_ARG::first()
1672
{
1673
SEL_ARG *next_arg=this;
1674
if (!next_arg->left)
1675
return 0; // MAYBE_KEY
1676
while (next_arg->left != &null_element)
1677
next_arg=next_arg->left;
1678
return next_arg;
1679
}
1680
1681
SEL_ARG *SEL_ARG::last()
1682
{
1683
SEL_ARG *next_arg=this;
1684
if (!next_arg->right)
1685
return 0; // MAYBE_KEY
1686
while (next_arg->right != &null_element)
1687
next_arg=next_arg->right;
1688
return next_arg;
1689
}
1690
1691
1692
/*
1693
Check if a compare is ok, when one takes ranges in account
1694
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1695
*/
1696
1697
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1698
uint8_t b_flag)
1699
{
1700
int cmp;
1701
/* First check if there was a compare to a min or max element */
1702
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1703
{
1704
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1705
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1706
return 0;
1707
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1708
}
1709
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1710
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1711
1712
if (field->real_maybe_null()) // If null is part of key
1713
{
1714
if (*a != *b)
1715
{
1716
return *a ? -1 : 1;
1717
}
1718
if (*a)
1719
goto end; // NULL where equal
1720
a++; b++; // Skip NULL marker
1721
}
1722
cmp=field->key_cmp(a , b);
1723
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1724
1725
// Check if the compared equal arguments was defined with open/closed range
1726
end:
1727
if (a_flag & (NEAR_MIN | NEAR_MAX))
1728
{
1729
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1730
return 0;
1731
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1732
return (a_flag & NEAR_MIN) ? 2 : -2;
1733
return (a_flag & NEAR_MIN) ? 1 : -1;
1734
}
1735
if (b_flag & (NEAR_MIN | NEAR_MAX))
1736
return (b_flag & NEAR_MIN) ? -2 : 2;
1737
return 0; // The elements where equal
1738
}
1739
1740
1741
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1742
{
1743
SEL_ARG tmp_link,*next_arg,*root;
1744
next_arg= &tmp_link;
1745
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1746
return 0;
1747
next_arg->next=0; // Fix last link
1748
tmp_link.next->prev=0; // Fix first link
1749
if (root) // If not OOM
1750
root->use_count= 0;
1751
return root;
1752
}
1753
1754
1755
978
/*
1756
979
Find the best index to retrieve first N records in given order
1757
980
1809
1032
for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)
1810
1033
{
1811
1034
Item *item= order->item[0];
1812
if (!(item->type() == Item::FIELD_ITEM &&
1035
if (! (item->type() == Item::FIELD_ITEM &&
1813
1036
((Item_field*)item)->field->eq(keyinfo[partno].field)))
1814
1037
break;
1815
1038
}
1816
1039
1817
if (!ord && table->key_info[idx].key_length < match_key_len)
1040
if (! ord && table->key_info[idx].key_length < match_key_len)
1818
1041
{
1819
1042
/*
1820
1043
Ok, the ordering is compatible and this key is shorter then
1878
1101
created quick select
1879
1102
NULL on any error.
1880
1103
*/
1881
virtual optimizer::QuickSelectInterface *make_quick(PARAM *param,
1882
bool retrieve_full_rows,
1883
MEM_ROOT *parent_alloc=NULL) = 0;
1104
virtual optimizer::QuickSelectInterface *make_quick(optimizer::PARAM *param,
1105
bool retrieve_full_rows,
1106
MEM_ROOT *parent_alloc=NULL) = 0;
1884
1107
1885
1108
/* Table read plans are allocated on MEM_ROOT and are never deleted */
1886
1109
static void *operator new(size_t size, MEM_ROOT *mem_root)
1908
1131
class TRP_RANGE : public TABLE_READ_PLAN
1909
1132
{
1910
1133
public:
1911
SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1134
optimizer::SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1912
1135
uint32_t key_idx; /* key number in PARAM::key */
1913
1136
uint32_t mrr_flags;
1914
1137
uint32_t mrr_buf_size;
1915
1138
1916
TRP_RANGE(SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1917
: key(key_arg), key_idx(idx_arg), mrr_flags(mrr_flags_arg)
1139
TRP_RANGE(optimizer::SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
1140
:
1141
key(key_arg),
1142
key_idx(idx_arg),
1143
mrr_flags(mrr_flags_arg)
1918
1144
{}
1919
1145
virtual ~TRP_RANGE() {} /* Remove gcc warning */
1920
1146
1921
optimizer::QuickSelectInterface *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1147
optimizer::QuickSelectInterface *make_quick(optimizer::PARAM *param, bool, MEM_ROOT *parent_alloc)
1922
1148
{
1923
1149
optimizer::QuickRangeSelect *quick= NULL;
1924
1150
if ((quick= optimizer::get_quick_select(param,
1943
1169
public:
1944
1170
TRP_ROR_INTERSECT() {} /* Remove gcc warning */
1945
1171
virtual ~TRP_ROR_INTERSECT() {} /* Remove gcc warning */
1946
optimizer::QuickSelectInterface *make_quick(PARAM *param,
1947
bool retrieve_full_rows,
1948
MEM_ROOT *parent_alloc);
1172
optimizer::QuickSelectInterface *make_quick(optimizer::PARAM *param,
1173
bool retrieve_full_rows,
1174
MEM_ROOT *parent_alloc);
1949
1175
1950
1176
/* Array of pointers to ROR range scans used in this intersection */
1951
1177
struct st_ror_scan_info **first_scan;
1967
1193
public:
1968
1194
TRP_ROR_UNION() {} /* Remove gcc warning */
1969
1195
virtual ~TRP_ROR_UNION() {} /* Remove gcc warning */
1970
optimizer::QuickSelectInterface *make_quick(PARAM *param,
1971
bool retrieve_full_rows,
1972
MEM_ROOT *parent_alloc);
1196
optimizer::QuickSelectInterface *make_quick(optimizer::PARAM *param,
1197
bool retrieve_full_rows,
1198
MEM_ROOT *parent_alloc);
1973
1199
TABLE_READ_PLAN **first_ror; /* array of ptrs to plans for merged scans */
1974
1200
TABLE_READ_PLAN **last_ror; /* end of the above array */
1975
1201
};
1986
1212
public:
1987
1213
TRP_INDEX_MERGE() {} /* Remove gcc warning */
1988
1214
virtual ~TRP_INDEX_MERGE() {} /* Remove gcc warning */
1989
optimizer::QuickSelectInterface *make_quick(PARAM *param,
1990
bool retrieve_full_rows,
1991
MEM_ROOT *parent_alloc);
1215
optimizer::QuickSelectInterface *make_quick(optimizer::PARAM *param,
1216
bool retrieve_full_rows,
1217
MEM_ROOT *parent_alloc);
1992
1218
TRP_RANGE **range_scans; /* array of ptrs to plans of merged scans */
1993
1219
TRP_RANGE **range_scans_end; /* end of the array */
1994
1220
};
2011
1237
uint32_t key_infix_len;
2012
1238
unsigned char key_infix[MAX_KEY_LENGTH];
2013
1239
SEL_TREE *range_tree; /* Represents all range predicates in the query. */
2014
SEL_ARG *index_tree; /* The SEL_ARG sub-tree corresponding to index_info. */
1240
optimizer::SEL_ARG *index_tree; /* The SEL_ARG sub-tree corresponding to index_info. */
2015
1241
uint32_t param_idx; /* Index of used key in param->key. */
2016
1242
/* Number of records selected by the ranges in index_tree. */
2017
1243
public:
2023
1249
uint32_t group_key_parts_arg, KEY *index_info_arg,
2024
1250
uint32_t index_arg, uint32_t key_infix_len_arg,
2025
1251
unsigned char *key_infix_arg,
2026
SEL_TREE *tree_arg, SEL_ARG *index_tree_arg,
1252
SEL_TREE *tree_arg, optimizer::SEL_ARG *index_tree_arg,
2027
1253
uint32_t param_idx_arg, ha_rows quick_prefix_records_arg)
2028
: have_min(have_min_arg), have_max(have_max_arg),
2029
min_max_arg_part(min_max_arg_part_arg),
2030
group_prefix_len(group_prefix_len_arg), used_key_parts(used_key_parts_arg),
2031
group_key_parts(group_key_parts_arg), index_info(index_info_arg),
2032
index(index_arg), key_infix_len(key_infix_len_arg), range_tree(tree_arg),
2033
index_tree(index_tree_arg), param_idx(param_idx_arg),
2034
quick_prefix_records(quick_prefix_records_arg)
1254
:
1255
have_min(have_min_arg),
1256
have_max(have_max_arg),
1257
min_max_arg_part(min_max_arg_part_arg),
1258
group_prefix_len(group_prefix_len_arg),
1259
used_key_parts(used_key_parts_arg),
1260
group_key_parts(group_key_parts_arg),
1261
index_info(index_info_arg),
1262
index(index_arg),
1263
key_infix_len(key_infix_len_arg),
1264
range_tree(tree_arg),
1265
index_tree(index_tree_arg),
1266
param_idx(param_idx_arg),
1267
quick_prefix_records(quick_prefix_records_arg)
2035
1268
{
2036
1269
if (key_infix_len)
2037
1270
memcpy(this->key_infix, key_infix_arg, key_infix_len);
2038
1271
}
2039
1272
virtual ~TRP_GROUP_MIN_MAX() {} /* Remove gcc warning */
2040
1273
2041
optimizer::QuickSelectInterface *make_quick(PARAM *param,
2042
bool retrieve_full_rows,
2043
MEM_ROOT *parent_alloc);
1274
optimizer::QuickSelectInterface *make_quick(optimizer::PARAM *param,
1275
bool retrieve_full_rows,
1276
MEM_ROOT *parent_alloc);
2044
1277
};
2045
1278
2046
1279
2058
1291
1 Out of memory.
2059
1292
*/
2060
1293
2061
static int fill_used_fields_bitmap(PARAM *param)
1294
static int fill_used_fields_bitmap(optimizer::PARAM *param)
2062
1295
{
2063
1296
Table *table= param->table;
2064
1297
my_bitmap_map *tmp;
2187
1420
SEL_TREE *tree= NULL;
2188
1421
KEY_PART *key_parts;
2189
1422
KEY *key_info;
2190
PARAM param;
1423
optimizer::PARAM param;
2191
1424
2192
1425
if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
2193
1426
return 0; // Fatal error flag is set
2377
1610
if (best_trp)
2378
1611
{
2379
1612
records= best_trp->records;
2380
if (!(quick= best_trp->make_quick(¶m, true)) || quick->init())
1613
if (! (quick= best_trp->make_quick(¶m, true)) || quick->init())
2381
1614
{
2382
1615
delete quick;
2383
1616
quick= NULL;
2463
1696
*/
2464
1697
2465
1698
static
2466
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
1699
TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::PARAM *param,
1700
SEL_IMERGE *imerge,
2467
1701
double read_time)
2468
1702
{
2469
1703
SEL_TREE **ptree;
2702
1936
ha_rows records; /* estimate of # records this scan will return */
2703
1937
2704
1938
/* Set of intervals over key fields that will be used for row retrieval. */
2705
SEL_ARG *sel_arg;
1939
optimizer::SEL_ARG *sel_arg;
2706
1940
2707
1941
/* Fields used in the query and covered by this ROR scan. */
2708
1942
MyBitmap covered_fields;
2735
1969
*/
2736
1970
2737
1971
static
2738
ROR_SCAN_INFO *make_ror_scan(const PARAM *param, int idx, SEL_ARG *sel_arg)
1972
ROR_SCAN_INFO *make_ror_scan(const optimizer::PARAM *param, int idx, optimizer::SEL_ARG *sel_arg)
2739
1973
{
2740
1974
ROR_SCAN_INFO *ror_scan;
2741
1975
my_bitmap_map *bitmap_buf;
2835
2069
/* Auxiliary structure for incremental ROR-intersection creation */
2836
2070
typedef struct
2837
2071
{
2838
const PARAM *param;
2072
const optimizer::PARAM *param;
2839
2073
MyBitmap covered_fields; /* union of fields covered by all scans */
2840
2074
/*
2841
2075
Fraction of table records that satisfies conditions of all scans.
2865
2099
*/
2866
2100
2867
2101
static
2868
ROR_INTERSECT_INFO* ror_intersect_init(const PARAM *param)
2102
ROR_INTERSECT_INFO* ror_intersect_init(const optimizer::PARAM *param)
2869
2103
{
2870
2104
ROR_INTERSECT_INFO *info;
2871
2105
my_bitmap_map* buf;
2996
2230
KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part;
2997
2231
unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
2998
2232
unsigned char *key_ptr= key_val;
2999
SEL_ARG *sel_arg, *tuple_arg= NULL;
2233
optimizer::SEL_ARG *sel_arg= NULL;
2234
optimizer::SEL_ARG *tuple_arg= NULL;
3000
2235
key_part_map keypart_map= 0;
3001
2236
bool cur_covered;
3002
2237
bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
3211
2446
*/
3212
2447
3213
2448
static
3214
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param,
3215
SEL_TREE *tree,
3216
double read_time,
3217
bool *are_all_covering)
2449
TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::PARAM *param,
2450
SEL_TREE *tree,
2451
double read_time,
2452
bool *are_all_covering)
3218
2453
{
3219
2454
uint32_t idx;
3220
2455
double min_cost= DBL_MAX;
3397
2632
*/
3398
2633
3399
2634
static
3400
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
3401
SEL_TREE *tree,
3402
double read_time)
2635
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::PARAM *param,
2636
SEL_TREE *tree,
2637
double read_time)
3403
2638
{
3404
2639
ROR_SCAN_INFO **ror_scan_mark;
3405
2640
ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
3535
2770
NULL if no plan found or error occurred
3536
2771
*/
3537
2772
3538
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
2773
static TRP_RANGE *get_key_scans_params(optimizer::PARAM *param,
2774
SEL_TREE *tree,
3539
2775
bool index_read_must_be_used,
3540
2776
bool update_tbl_stats,
3541
2777
double read_time)
3542
2778
{
3543
2779
uint32_t idx;
3544
SEL_ARG **key,**end, **key_to_read= NULL;
2780
optimizer::SEL_ARG **key,**end, **key_to_read= NULL;
3545
2781
ha_rows best_records= 0;
3546
2782
uint32_t best_mrr_flags= 0, best_buf_size= 0;
3547
2783
TRP_RANGE* read_plan= NULL;
3562
2798
double found_read_time= 0.0;
3563
2799
uint32_t mrr_flags, buf_size;
3564
2800
uint32_t keynr= param->real_keynr[idx];
3565
if ((*key)->type == SEL_ARG::MAYBE_KEY ||
2801
if ((*key)->type == optimizer::SEL_ARG::MAYBE_KEY ||
3566
2802
(*key)->maybe_flag)
3567
2803
param->needed_reg->set(keynr);
3568
2804
3607
2843
}
3608
2844
3609
2845
3610
optimizer::QuickSelectInterface *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
2846
optimizer::QuickSelectInterface *TRP_INDEX_MERGE::make_quick(optimizer::PARAM *param, bool, MEM_ROOT *)
3611
2847
{
3612
2848
optimizer::QuickIndexMergeSelect *quick_imerge;
3613
2849
optimizer::QuickRangeSelect *quick= NULL;
3634
2870
return quick_imerge;
3635
2871
}
3636
2872
3637
optimizer::QuickSelectInterface *TRP_ROR_INTERSECT::make_quick(PARAM *param,
2873
optimizer::QuickSelectInterface *TRP_ROR_INTERSECT::make_quick(optimizer::PARAM *param,
3638
2874
bool retrieve_full_rows,
3639
2875
MEM_ROOT *parent_alloc)
3640
2876
{
3689
2925
}
3690
2926
3691
2927
3692
optimizer::QuickSelectInterface *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
2928
optimizer::QuickSelectInterface *TRP_ROR_UNION::make_quick(optimizer::PARAM *param, bool, MEM_ROOT *)
3693
2929
{
3694
2930
optimizer::QUICK_ROR_UNION_SELECT *quick_roru;
3695
2931
TABLE_READ_PLAN **scan;
3732
2968
0 on error
3733
2969
*/
3734
2970
3735
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
2971
static SEL_TREE *get_ne_mm_tree(optimizer::RANGE_OPT_PARAM *param,
2972
Item_func *cond_func,
3736
2973
Field *field,
3737
2974
Item *lt_value, Item *gt_value,
3738
2975
Item_result cmp_type)
3742
2979
lt_value, cmp_type);
3743
2980
if (tree)
3744
2981
{
3745
tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3746
Item_func::GT_FUNC,
3747
gt_value, cmp_type));
2982
tree= tree_or(param,
2983
tree,
2984
get_mm_parts(param, cond_func, field,
2985
Item_func::GT_FUNC,
2986
gt_value,
2987
cmp_type));
3748
2988
}
3749
2989
return tree;
3750
2990
}
3767
3007
Pointer to the tree built tree
3768
3008
*/
3769
3009
3770
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3010
static SEL_TREE *get_func_mm_tree(optimizer::RANGE_OPT_PARAM *param,
3011
Item_func *cond_func,
3771
3012
Field *field, Item *value,
3772
3013
Item_result cmp_type, bool inv)
3773
3014
{
3907
3148
/* Change all intervals to be "c_{i-1} < X < c_i" */
3908
3149
for (uint32_t idx= 0; idx < param->keys; idx++)
3909
3150
{
3910
SEL_ARG *new_interval, *last_val;
3151
optimizer::SEL_ARG *new_interval, *last_val;
3911
3152
if (((new_interval= tree2->keys[idx])) &&
3912
3153
(tree->keys[idx]) &&
3913
3154
((last_val= tree->keys[idx]->last())))
4060
3301
Pointer to the tree representing the built conjunction of SEL_TREEs
4061
3302
*/
4062
3303
4063
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
3304
static SEL_TREE *get_full_func_mm_tree(optimizer::RANGE_OPT_PARAM *param,
4064
3305
Item_func *cond_func,
4065
3306
Item_field *field_item, Item *value,
4066
3307
bool inv)
4108
3349
4109
3350
/* make a select tree of all keys in condition */
4110
3351
4111
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond)
3352
static SEL_TREE *get_mm_tree(optimizer::RANGE_OPT_PARAM *param, COND *cond)
4112
3353
{
4113
3354
SEL_TREE *tree=0;
4114
3355
SEL_TREE *ftree= 0;
4126
3367
Item *item;
4127
3368
while ((item=li++))
4128
3369
{
4129
SEL_TREE *new_tree=get_mm_tree(param,item);
3370
SEL_TREE *new_tree= get_mm_tree(param,item);
4130
3371
if (param->session->is_fatal_error ||
4131
param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
3372
param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
4132
3373
return 0; // out of memory
4133
3374
tree=tree_and(param,tree,new_tree);
4134
3375
if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4137
3378
}
4138
3379
else
4139
3380
{ // COND OR
4140
tree=get_mm_tree(param,li++);
3381
tree= get_mm_tree(param,li++);
4141
3382
if (tree)
4142
3383
{
4143
3384
Item *item;
4144
3385
while ((item=li++))
4145
3386
{
4146
SEL_TREE *new_tree=get_mm_tree(param,item);
3387
SEL_TREE *new_tree= get_mm_tree(param,item);
4147
3388
if (!new_tree)
4148
3389
return 0; // out of memory
4149
3390
tree=tree_or(param,tree,new_tree);
4280
3521
4281
3522
4282
3523
static SEL_TREE *
4283
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4284
Item_func::Functype type,
4285
Item *value, Item_result)
3524
get_mm_parts(optimizer::RANGE_OPT_PARAM *param,
3525
COND *cond_func,
3526
Field *field,
3527
Item_func::Functype type,
3528
Item *value, Item_result)
4286
3529
{
4287
3530
if (field->table != param->table)
4288
3531
return 0;
4293
3536
if (value &&
4294
3537
value->used_tables() & ~(param->prev_tables | param->read_tables))
4295
3538
return 0;
4296
for (; key_part != end ; key_part++)
3539
for (; key_part != end; key_part++)
4297
3540
{
4298
3541
if (field->eq(key_part->field))
4299
3542
{
4300
SEL_ARG *sel_arg=0;
3543
optimizer::SEL_ARG *sel_arg=0;
4301
3544
if (!tree && !(tree=new SEL_TREE()))
4302
return 0; // OOM
3545
return 0; // OOM
4303
3546
if (!value || !(value->used_tables() & ~param->read_tables))
4304
3547
{
4305
sel_arg=get_mm_leaf(param,cond_func,
4306
key_part->field,key_part,type,value);
4307
if (!sel_arg)
4308
continue;
4309
if (sel_arg->type == SEL_ARG::IMPOSSIBLE)
4310
{
4311
tree->type=SEL_TREE::IMPOSSIBLE;
4312
return(tree);
4313
}
3548
sel_arg= get_mm_leaf(param,cond_func,
3549
key_part->field,key_part,type,value);
3550
if (! sel_arg)
3551
continue;
3552
if (sel_arg->type == optimizer::SEL_ARG::IMPOSSIBLE)
3553
{
3554
tree->type=SEL_TREE::IMPOSSIBLE;
3555
return(tree);
3556
}
4314
3557
}
4315
3558
else
4316
3559
{
4317
// This key may be used later
4318
if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4319
return 0; // OOM
3560
// This key may be used later
3561
if (! (sel_arg= new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY)))
3562
return 0; // OOM
4320
3563
}
4321
3564
sel_arg->part=(unsigned char) key_part->part;
4322
3565
tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4324
3567
}
4325
3568
}
4326
3569
4327
return(tree);
3570
return tree;
4328
3571
}
4329
3572
4330
3573
4331
static SEL_ARG *
4332
get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field,
4333
KEY_PART *key_part, Item_func::Functype type,Item *value)
3574
static optimizer::SEL_ARG *
3575
get_mm_leaf(optimizer::RANGE_OPT_PARAM *param,
3576
COND *conf_func,
3577
Field *field,
3578
KEY_PART *key_part,
3579
Item_func::Functype type,
3580
Item *value)
4334
3581
{
4335
3582
uint32_t maybe_null=(uint32_t) field->real_maybe_null();
4336
3583
bool optimize_range;
4337
SEL_ARG *tree= 0;
3584
optimizer::SEL_ARG *tree= NULL;
4338
3585
MEM_ROOT *alloc= param->mem_root;
4339
3586
unsigned char *str;
4340
3587
int err= 0;
4355
3602
if (!maybe_null) // Not null field
4356
3603
{
4357
3604
if (type == Item_func::ISNULL_FUNC)
4358
tree= &null_element;
3605
tree= &optimizer::null_element;
4359
3606
goto end;
4360
3607
}
4361
if (!(tree= new (alloc) SEL_ARG(field,is_null_string,is_null_string)))
3608
if (!(tree= new (alloc) optimizer::SEL_ARG(field,is_null_string,is_null_string)))
4362
3609
goto end; // out of memory
4363
3610
if (type == Item_func::ISNOTNULL_FUNC)
4364
3611
{
4405
3652
goto end;
4406
3653
if (!(res= value->val_str(&tmp)))
4407
3654
{
4408
tree= &null_element;
3655
tree= &optimizer::null_element;
4409
3656
goto end;
4410
3657
}
4411
3658
4471
3718
int2store(min_str+maybe_null,min_length);
4472
3719
int2store(max_str+maybe_null,max_length);
4473
3720
}
4474
tree= new (alloc) SEL_ARG(field, min_str, max_str);
3721
tree= new (alloc) optimizer::SEL_ARG(field, min_str, max_str);
4475
3722
goto end;
4476
3723
}
4477
3724
4478
if (!optimize_range &&
3725
if (! optimize_range &&
4479
3726
type != Item_func::EQ_FUNC &&
4480
3727
type != Item_func::EQUAL_FUNC)
4481
3728
goto end; // Can't optimize this
4605
3852
value->result_type() == item_cmp_type(field->result_type(),
4606
3853
value->result_type()))
4607
3854
{
4608
tree= new (alloc) SEL_ARG(field, 0, 0);
4609
tree->type= SEL_ARG::IMPOSSIBLE;
3855
tree= new (alloc) optimizer::SEL_ARG(field, 0, 0);
3856
tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
4610
3857
goto end;
4611
3858
}
4612
3859
else
4663
3910
else if (err < 0)
4664
3911
{
4665
3912
/* This happens when we try to insert a NULL field in a not null column */
4666
tree= &null_element; // cmp with NULL is never true
3913
tree= &optimizer::null_element; // cmp with NULL is never true
4667
3914
goto end;
4668
3915
}
4669
3916
str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
4672
3919
if (maybe_null)
4673
3920
*str= (unsigned char) field->is_real_null(); // Set to 1 if null
4674
3921
field->get_key_image(str+maybe_null, key_part->length);
4675
if (!(tree= new (alloc) SEL_ARG(field, str, str)))
4676
goto end; // out of memory
3922
if (! (tree= new (alloc) optimizer::SEL_ARG(field, str, str)))
3923
goto end; // out of memory
4677
3924
4678
3925
/*
4679
3926
Check if we are comparing an UNSIGNED integer with a negative constant.
4695
3942
{
4696
3943
if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC)
4697
3944
{
4698
tree->type= SEL_ARG::IMPOSSIBLE;
3945
tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
4699
3946
goto end;
4700
3947
}
4701
3948
if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC)
4756
4003
This will never be called for same key parts.
4757
4004
*/
4758
4005
4759
static SEL_ARG *
4760
sel_add(SEL_ARG *key1,SEL_ARG *key2)
4006
static optimizer::SEL_ARG *
4007
sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
4761
4008
{
4762
SEL_ARG *root,**key_link;
4009
optimizer::SEL_ARG *root= NULL;
4010
optimizer::SEL_ARG **key_link= NULL;
4763
4011
4764
4012
if (!key1)
4765
4013
return key2;
4792
4040
4793
4041
4794
4042
static SEL_TREE *
4795
tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4043
tree_and(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *tree1, SEL_TREE *tree2)
4796
4044
{
4797
4045
if (!tree1)
4798
4046
return(tree2);
4817
4065
result_keys.reset();
4818
4066
4819
4067
/* Join the trees key per key */
4820
SEL_ARG **key1,**key2,**end;
4068
optimizer::SEL_ARG **key1,**key2,**end;
4821
4069
for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
4822
4070
key1 != end ; key1++,key2++)
4823
4071
{
4825
4073
if (*key1 || *key2)
4826
4074
{
4827
4075
if (*key1 && !(*key1)->simple_key())
4828
flag|=CLONE_KEY1_MAYBE;
4076
flag|=CLONE_KEY1_MAYBE;
4829
4077
if (*key2 && !(*key2)->simple_key())
4830
flag|=CLONE_KEY2_MAYBE;
4078
flag|=CLONE_KEY2_MAYBE;
4831
4079
*key1=key_and(param, *key1, *key2, flag);
4832
if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
4080
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
4833
4081
{
4834
tree1->type= SEL_TREE::IMPOSSIBLE;
4082
tree1->type= SEL_TREE::IMPOSSIBLE;
4835
4083
return(tree1);
4836
4084
}
4837
4085
result_keys.set(key1 - tree1->keys);
4838
#ifdef EXTRA_DEBUG
4839
if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4840
(*key1)->test_use_count(*key1);
4841
#endif
4842
4086
}
4843
4087
}
4844
4088
tree1->keys_map= result_keys;
4862
4106
*/
4863
4107
4864
4108
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4865
RANGE_OPT_PARAM* param)
4109
optimizer::RANGE_OPT_PARAM* param)
4866
4110
{
4867
4111
key_map common_keys= tree1->keys_map;
4868
4112
common_keys&= tree2->keys_map;
4871
4115
return false;
4872
4116
4873
4117
/* trees have a common key, check if they refer to same key part */
4874
SEL_ARG **key1,**key2;
4118
optimizer::SEL_ARG **key1,**key2;
4875
4119
for (uint32_t key_no=0; key_no < param->keys; key_no++)
4876
4120
{
4877
4121
if (common_keys.test(key_no))
4943
4187
1 No tree->keys[] left.
4944
4188
*/
4945
4189
4946
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree)
4190
static bool remove_nonrange_trees(optimizer::RANGE_OPT_PARAM *param, SEL_TREE *tree)
4947
4191
{
4948
4192
bool res= false;
4949
4193
for (uint32_t i=0; i < param->keys; i++)
4964
4208
4965
4209
4966
4210
static SEL_TREE *
4967
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4211
tree_or(optimizer::RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4968
4212
{
4969
4213
if (!tree1 || !tree2)
4970
4214
return 0;
4983
4227
if (sel_trees_can_be_ored(tree1, tree2, param))
4984
4228
{
4985
4229
/* Join the trees key per key */
4986
SEL_ARG **key1,**key2,**end;
4230
optimizer::SEL_ARG **key1,**key2,**end;
4987
4231
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
4988
4232
key1 != end ; key1++,key2++)
4989
4233
{
4992
4236
{
4993
4237
result=tree1; // Added to tree1
4994
4238
result_keys.set(key1 - tree1->keys);
4995
#ifdef EXTRA_DEBUG
4996
if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4997
(*key1)->test_use_count(*key1);
4998
#endif
4999
4239
}
5000
4240
}
5001
4241
if (result)
5051
4291
5052
4292
/* And key trees where key1->part < key2 -> part */
5053
4293
5054
static SEL_ARG *
5055
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4294
static optimizer::SEL_ARG *
4295
and_all_keys(optimizer::RANGE_OPT_PARAM *param,
4296
optimizer::SEL_ARG *key1,
4297
optimizer::SEL_ARG *key2,
5056
4298
uint32_t clone_flag)
5057
4299
{
5058
SEL_ARG *next;
4300
optimizer::SEL_ARG *next= NULL;
5059
4301
ulong use_count=key1->use_count;
5060
4302
5061
4303
if (key1->elements != 1)
5063
4305
key2->use_count+=key1->elements-1; //psergey: why we don't count that key1 has n-k-p?
5064
4306
key2->increment_use_count((int) key1->elements-1);
5065
4307
}
5066
if (key1->type == SEL_ARG::MAYBE_KEY)
4308
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5067
4309
{
5068
key1->right= key1->left= &null_element;
4310
key1->right= key1->left= &optimizer::null_element;
5069
4311
key1->next= key1->prev= 0;
5070
4312
}
5071
for (next=key1->first(); next ; next=next->next)
4313
for (next= key1->first(); next ; next=next->next)
5072
4314
{
5073
4315
if (next->next_key_part)
5074
4316
{
5075
SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag);
5076
if (tmp && tmp->type == SEL_ARG::IMPOSSIBLE)
4317
optimizer::SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag);
4318
if (tmp && tmp->type == optimizer::SEL_ARG::IMPOSSIBLE)
5077
4319
{
5078
key1=key1->tree_delete(next);
5079
continue;
4320
key1=key1->tree_delete(next);
4321
continue;
5080
4322
}
5081
4323
next->next_key_part=tmp;
5082
4324
if (use_count)
5083
next->increment_use_count(use_count);
5084
if (param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
4325
next->increment_use_count(use_count);
4326
if (param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
5085
4327
break;
5086
4328
}
5087
4329
else
5088
4330
next->next_key_part=key2;
5089
4331
}
5090
if (!key1)
5091
return &null_element; // Impossible ranges
4332
if (! key1)
4333
return &optimizer::null_element; // Impossible ranges
5092
4334
key1->use_count++;
5093
4335
return key1;
5094
4336
}
5109
4351
NULL if the result of AND operation is an empty interval {0}.
5110
4352
*/
5111
4353
5112
static SEL_ARG *
5113
key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2, uint32_t clone_flag)
4354
static optimizer::SEL_ARG *
4355
key_and(optimizer::RANGE_OPT_PARAM *param,
4356
optimizer::SEL_ARG *key1,
4357
optimizer::SEL_ARG *key2,
4358
uint32_t clone_flag)
5114
4359
{
5115
if (!key1)
4360
if (! key1)
5116
4361
return key2;
5117
if (!key2)
4362
if (! key2)
5118
4363
return key1;
5119
4364
if (key1->part != key2->part)
5120
4365
{
5126
4371
// key1->part < key2->part
5127
4372
key1->use_count--;
5128
4373
if (key1->use_count > 0)
5129
if (!(key1= key1->clone_tree(param)))
5130
return 0; // OOM
4374
if (! (key1= key1->clone_tree(param)))
4375
return 0; // OOM
5131
4376
return and_all_keys(param, key1, key2, clone_flag);
5132
4377
}
5133
4378
5134
4379
if (((clone_flag & CLONE_KEY2_MAYBE) &&
5135
!(clone_flag & CLONE_KEY1_MAYBE) &&
5136
key2->type != SEL_ARG::MAYBE_KEY) ||
5137
key1->type == SEL_ARG::MAYBE_KEY)
4380
! (clone_flag & CLONE_KEY1_MAYBE) &&
4381
key2->type != optimizer::SEL_ARG::MAYBE_KEY) ||
4382
key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5138
4383
{ // Put simple key in key2
5139
4384
std::swap(key1, key2);
5140
clone_flag=swap_clone_flag(clone_flag);
4385
clone_flag= swap_clone_flag(clone_flag);
5141
4386
}
5142
4387
5143
4388
/* If one of the key is MAYBE_KEY then the found region may be smaller */
5144
if (key2->type == SEL_ARG::MAYBE_KEY)
4389
if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
5145
4390
{
5146
4391
if (key1->use_count > 1)
5147
4392
{
5148
4393
key1->use_count--;
5149
if (!(key1=key1->clone_tree(param)))
5150
return 0; // OOM
4394
if (! (key1=key1->clone_tree(param)))
4395
return 0; // OOM
5151
4396
key1->use_count++;
5152
4397
}
5153
if (key1->type == SEL_ARG::MAYBE_KEY)
4398
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5154
4399
{ // Both are maybe key
5155
key1->next_key_part=key_and(param, key1->next_key_part,
5156
key2->next_key_part, clone_flag);
4400
key1->next_key_part= key_and(param,
4401
key1->next_key_part,
4402
key2->next_key_part,
4403
clone_flag);
5157
4404
if (key1->next_key_part &&
5158
key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5159
return key1;
4405
key1->next_key_part->type == optimizer::SEL_ARG::IMPOSSIBLE)
4406
return key1;
5160
4407
}
5161
4408
else
5162
4409
{
5163
4410
key1->maybe_smaller();
5164
4411
if (key2->next_key_part)
5165
4412
{
5166
key1->use_count--; // Incremented in and_all_keys
5167
return and_all_keys(param, key1, key2, clone_flag);
4413
key1->use_count--; // Incremented in and_all_keys
4414
return and_all_keys(param, key1, key2, clone_flag);
5168
4415
}
5169
4416
key2->use_count--; // Key2 doesn't have a tree
5170
4417
}
5173
4420
5174
4421
key1->use_count--;
5175
4422
key2->use_count--;
5176
SEL_ARG *e1=key1->first(), *e2=key2->first(), *new_tree=0;
4423
optimizer::SEL_ARG *e1= key1->first();
4424
optimizer::SEL_ARG *e2= key2->first();
4425
optimizer::SEL_ARG *new_tree= NULL;
5177
4426
5178
4427
while (e1 && e2)
5179
4428
{
5180
int cmp=e1->cmp_min_to_min(e2);
4429
int cmp= e1->cmp_min_to_min(e2);
5181
4430
if (cmp < 0)
5182
4431
{
5183
if (get_range(&e1,&e2,key1))
5184
continue;
4432
if (get_range(&e1, &e2, key1))
4433
continue;
5185
4434
}
5186
else if (get_range(&e2,&e1,key2))
4435
else if (get_range(&e2, &e1, key2))
5187
4436
continue;
5188
SEL_ARG *next=key_and(param, e1->next_key_part, e2->next_key_part,
5189
clone_flag);
4437
optimizer::SEL_ARG *next= key_and(param,
4438
e1->next_key_part,
4439
e2->next_key_part,
4440
clone_flag);
5190
4441
e1->increment_use_count(1);
5191
4442
e2->increment_use_count(1);
5192
if (!next || next->type != SEL_ARG::IMPOSSIBLE)
4443
if (! next || next->type != optimizer::SEL_ARG::IMPOSSIBLE)
5193
4444
{
5194
SEL_ARG *new_arg= e1->clone_and(e2);
5195
if (!new_arg)
5196
return &null_element; // End of memory
4445
optimizer::SEL_ARG *new_arg= e1->clone_and(e2);
4446
if (! new_arg)
4447
return &optimizer::null_element; // End of memory
5197
4448
new_arg->next_key_part=next;
5198
if (!new_tree)
4449
if (! new_tree)
5199
4450
{
5200
new_tree=new_arg;
4451
new_tree=new_arg;
5201
4452
}
5202
4453
else
5203
new_tree=new_tree->insert(new_arg);
4454
new_tree=new_tree->insert(new_arg);
5204
4455
}
5205
4456
if (e1->cmp_max_to_max(e2) < 0)
5206
4457
e1=e1->next; // e1 can't overlapp next e2
5209
4460
}
5210
4461
key1->free_tree();
5211
4462
key2->free_tree();
5212
if (!new_tree)
5213
return &null_element; // Impossible range
4463
if (! new_tree)
4464
return &optimizer::null_element; // Impossible range
5214
4465
return new_tree;
5215
4466
}
5216
4467
5217
4468
5218
4469
static bool
5219
get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1)
4470
get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1)
5220
4471
{
5221
(*e1)=root1->find_range(*e2); // first e1->min < e2->min
4472
(*e1)= root1->find_range(*e2); // first e1->min < e2->min
5222
4473
if ((*e1)->cmp_max_to_min(*e2) < 0)
5223
4474
{
5224
if (!((*e1)=(*e1)->next))
4475
if (! ((*e1)=(*e1)->next))
5225
4476
return 1;
5226
4477
if ((*e1)->cmp_min_to_max(*e2) > 0)
5227
4478
{
5233
4484
}
5234
4485
5235
4486
5236
static SEL_ARG *
5237
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
4487
static optimizer::SEL_ARG *
4488
key_or(optimizer::RANGE_OPT_PARAM *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
5238
4489
{
5239
if (!key1)
4490
if (! key1)
5240
4491
{
5241
4492
if (key2)
5242
4493
{
5245
4496
}
5246
4497
return 0;
5247
4498
}
5248
if (!key2)
4499
if (! key2)
5249
4500
{
5250
4501
key1->use_count--;
5251
4502
key1->free_tree();
5262
4513
}
5263
4514
5264
4515
// If one of the key is MAYBE_KEY then the found region may be bigger
5265
if (key1->type == SEL_ARG::MAYBE_KEY)
4516
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5266
4517
{
5267
4518
key2->free_tree();
5268
4519
key1->use_count++;
5269
4520
return key1;
5270
4521
}
5271
if (key2->type == SEL_ARG::MAYBE_KEY)
4522
if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
5272
4523
{
5273
4524
key1->free_tree();
5274
4525
key2->use_count++;
5286
4537
}
5287
4538
5288
4539
// Add tree at key2 to tree at key1
5289
bool key2_shared=key2->use_count != 0;
5290
key1->maybe_flag|=key2->maybe_flag;
4540
bool key2_shared= key2->use_count != 0;
4541
key1->maybe_flag|= key2->maybe_flag;
5291
4542
5292
4543
for (key2=key2->first(); key2; )
5293
4544
{
5294
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
4545
optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
5295
4546
int cmp;
5296
4547
5297
if (!tmp)
4548
if (! tmp)
5298
4549
{
5299
tmp=key1->first(); // tmp.min > key2.min
4550
tmp=key1->first(); // tmp.min > key2.min
5300
4551
cmp= -1;
5301
4552
}
5302
4553
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5303
4554
{ // Found tmp.max < key2.min
5304
SEL_ARG *next=tmp->next;
4555
optimizer::SEL_ARG *next= tmp->next;
5305
4556
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5306
4557
{
5307
// Join near ranges like tmp.max < 0 and key2.min >= 0
5308
SEL_ARG *key2_next=key2->next;
5309
if (key2_shared)
5310
{
5311
if (!(key2=new SEL_ARG(*key2)))
5312
return 0; // out of memory
5313
key2->increment_use_count(key1->use_count+1);
5314
key2->next=key2_next; // New copy of key2
5315
}
5316
key2->copy_min(tmp);
5317
if (!(key1=key1->tree_delete(tmp)))
5318
{ // Only one key in tree
5319
key1=key2;
5320
key1->make_root();
5321
key2=key2_next;
5322
break;
5323
}
4558
// Join near ranges like tmp.max < 0 and key2.min >= 0
4559
optimizer::SEL_ARG *key2_next=key2->next;
4560
if (key2_shared)
4561
{
4562
if (! (key2=new optimizer::SEL_ARG(*key2)))
4563
return 0; // out of memory
4564
key2->increment_use_count(key1->use_count+1);
4565
key2->next= key2_next; // New copy of key2
4566
}
4567
key2->copy_min(tmp);
4568
if (! (key1=key1->tree_delete(tmp)))
4569
{ // Only one key in tree
4570
key1= key2;
4571
key1->make_root();
4572
key2= key2_next;
4573
break;
4574
}
5324
4575
}
5325
if (!(tmp=next)) // tmp.min > key2.min
5326
break; // Copy rest of key2
4576
if (! (tmp= next)) // tmp.min > key2.min
4577
break; // Copy rest of key2
5327
4578
}
5328
4579
if (cmp < 0)
5329
4580
{ // tmp.min > key2.min
5330
4581
int tmp_cmp;
5331
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
4582
if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5332
4583
{
5333
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5334
{ // ranges are connected
5335
tmp->copy_min_to_min(key2);
5336
key1->merge_flags(key2);
5337
if (tmp->min_flag & NO_MIN_RANGE &&
5338
tmp->max_flag & NO_MAX_RANGE)
5339
{
5340
if (key1->maybe_flag)
5341
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5342
return 0;
5343
}
5344
key2->increment_use_count(-1); // Free not used tree
5345
key2=key2->next;
5346
continue;
5347
}
5348
else
5349
{
5350
SEL_ARG *next=key2->next; // Keys are not overlapping
5351
if (key2_shared)
5352
{
5353
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5354
if (!cpy)
5355
return 0; // OOM
5356
key1=key1->insert(cpy);
5357
key2->increment_use_count(key1->use_count+1);
5358
}
5359
else
5360
key1=key1->insert(key2); // Will destroy key2_root
5361
key2=next;
5362
continue;
5363
}
4584
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
4585
{ // ranges are connected
4586
tmp->copy_min_to_min(key2);
4587
key1->merge_flags(key2);
4588
if (tmp->min_flag & NO_MIN_RANGE &&
4589
tmp->max_flag & NO_MAX_RANGE)
4590
{
4591
if (key1->maybe_flag)
4592
return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
4593
return 0;
4594
}
4595
key2->increment_use_count(-1); // Free not used tree
4596
key2= key2->next;
4597
continue;
4598
}
4599
else
4600
{
4601
optimizer::SEL_ARG *next= key2->next; // Keys are not overlapping
4602
if (key2_shared)
4603
{
4604
optimizer::SEL_ARG *cpy= new optimizer::SEL_ARG(*key2); // Must make copy
4605
if (! cpy)
4606
return 0; // OOM
4607
key1= key1->insert(cpy);
4608
key2->increment_use_count(key1->use_count+1);
4609
}
4610
else
4611
key1= key1->insert(key2); // Will destroy key2_root
4612
key2= next;
4613
continue;
4614
}
5364
4615
}
5365
4616
}
5366
4617
5369
4620
{
5370
4621
if (tmp->is_same(key2))
5371
4622
{
5372
tmp->merge_flags(key2); // Copy maybe flags
5373
key2->increment_use_count(-1); // Free not used tree
4623
tmp->merge_flags(key2); // Copy maybe flags
4624
key2->increment_use_count(-1); // Free not used tree
5374
4625
}
5375
4626
else
5376
4627
{
5377
SEL_ARG *last=tmp;
5378
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5379
eq_tree(last->next->next_key_part,key2->next_key_part))
5380
{
5381
SEL_ARG *save=last;
5382
last=last->next;
5383
key1=key1->tree_delete(save);
5384
}
4628
optimizer::SEL_ARG *last= tmp;
4629
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
4630
eq_tree(last->next->next_key_part,key2->next_key_part))
4631
{
4632
optimizer::SEL_ARG *save= last;
4633
last= last->next;
4634
key1= key1->tree_delete(save);
4635
}
5385
4636
last->copy_min(tmp);
5386
if (last->copy_min(key2) || last->copy_max(key2))
5387
{ // Full range
5388
key1->free_tree();
5389
for (; key2 ; key2=key2->next)
5390
key2->increment_use_count(-1); // Free not used tree
5391
if (key1->maybe_flag)
5392
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5393
return 0;
5394
}
4637
if (last->copy_min(key2) || last->copy_max(key2))
4638
{ // Full range
4639
key1->free_tree();
4640
for (; key2; key2= key2->next)
4641
key2->increment_use_count(-1); // Free not used tree
4642
if (key1->maybe_flag)
4643
return new optimizer::SEL_ARG(optimizer::SEL_ARG::MAYBE_KEY);
4644
return 0;
4645
}
5395
4646
}
5396
key2=key2->next;
4647
key2= key2->next;
5397
4648
continue;
5398
4649
}
5399
4650
5400
4651
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5401
4652
{ // tmp.min <= x < key2.min
5402
SEL_ARG *new_arg=tmp->clone_first(key2);
5403
if (!new_arg)
5404
return 0; // OOM
4653
optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
4654
if (! new_arg)
4655
return 0; // OOM
5405
4656
if ((new_arg->next_key_part= key1->next_key_part))
5406
new_arg->increment_use_count(key1->use_count+1);
4657
new_arg->increment_use_count(key1->use_count+1);
5407
4658
tmp->copy_min_to_min(key2);
5408
key1=key1->insert(new_arg);
4659
key1= key1->insert(new_arg);
5409
4660
}
5410
4661
5411
4662
// tmp.min >= key2.min && tmp.min <= key2.max
5412
SEL_ARG key(*key2); // Get copy we can modify
4663
optimizer::SEL_ARG key(*key2); // Get copy we can modify
5413
4664
for (;;)
5414
4665
{
5415
4666
if (tmp->cmp_min_to_min(&key) > 0)
5416
4667
{ // key.min <= x < tmp.min
5417
SEL_ARG *new_arg=key.clone_first(tmp);
5418
if (!new_arg)
5419
return 0; // OOM
5420
if ((new_arg->next_key_part=key.next_key_part))
5421
new_arg->increment_use_count(key1->use_count+1);
5422
key1=key1->insert(new_arg);
4668
optimizer::SEL_ARG *new_arg= key.clone_first(tmp);
4669
if (! new_arg)
4670
return 0; // OOM
4671
if ((new_arg->next_key_part=key.next_key_part))
4672
new_arg->increment_use_count(key1->use_count+1);
4673
key1= key1->insert(new_arg);
5423
4674
}
5424
4675
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5425
4676
{ // tmp.min. <= x <= tmp.max
5426
tmp->maybe_flag|= key.maybe_flag;
5427
key.increment_use_count(key1->use_count+1);
5428
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5429
if (!cmp) // Key2 is ready
5430
break;
5431
key.copy_max_to_min(tmp);
5432
if (!(tmp=tmp->next))
5433
{
5434
SEL_ARG *tmp2= new SEL_ARG(key);
5435
if (!tmp2)
5436
return 0; // OOM
5437
key1=key1->insert(tmp2);
5438
key2=key2->next;
5439
goto end;
5440
}
5441
if (tmp->cmp_min_to_max(&key) > 0)
5442
{
5443
SEL_ARG *tmp2= new SEL_ARG(key);
5444
if (!tmp2)
5445
return 0; // OOM
5446
key1=key1->insert(tmp2);
5447
break;
5448
}
4677
tmp->maybe_flag|= key.maybe_flag;
4678
key.increment_use_count(key1->use_count+1);
4679
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
4680
if (! cmp) // Key2 is ready
4681
break;
4682
key.copy_max_to_min(tmp);
4683
if (! (tmp= tmp->next))
4684
{
4685
optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
4686
if (! tmp2)
4687
return 0; // OOM
4688
key1= key1->insert(tmp2);
4689
key2= key2->next;
4690
goto end;
4691
}
4692
if (tmp->cmp_min_to_max(&key) > 0)
4693
{
4694
optimizer::SEL_ARG *tmp2= new optimizer::SEL_ARG(key);
4695
if (! tmp2)
4696
return 0; // OOM
4697
key1= key1->insert(tmp2);
4698
break;
4699
}
5449
4700
}
5450
4701
else
5451
4702
{
5452
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5453
if (!new_arg)
5454
return 0; // OOM
5455
tmp->copy_max_to_min(&key);
5456
tmp->increment_use_count(key1->use_count+1);
5457
/* Increment key count as it may be used for next loop */
5458
key.increment_use_count(1);
5459
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5460
key1=key1->insert(new_arg);
5461
break;
4703
optimizer::SEL_ARG *new_arg= tmp->clone_last(&key); // tmp.min <= x <= key.max
4704
if (! new_arg)
4705
return 0; // OOM
4706
tmp->copy_max_to_min(&key);
4707
tmp->increment_use_count(key1->use_count+1);
4708
/* Increment key count as it may be used for next loop */
4709
key.increment_use_count(1);
4710
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
4711
key1= key1->insert(new_arg);
4712
break;
5462
4713
}
5463
4714
}
5464
key2=key2->next;
4715
key2= key2->next;
5465
4716
}
5466
4717
5467
4718
end:
5468
4719
while (key2)
5469
4720
{
5470
SEL_ARG *next=key2->next;
4721
optimizer::SEL_ARG *next= key2->next;
5471
4722
if (key2_shared)
5472
4723
{
5473
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5474
if (!tmp)
5475
return 0;
4724
optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
4725
if (! tmp)
4726
return 0;
5476
4727
key2->increment_use_count(key1->use_count+1);
5477
key1=key1->insert(tmp);
4728
key1= key1->insert(tmp);
5478
4729
}
5479
4730
else
5480
key1=key1->insert(key2); // Will destroy key2_root
5481
key2=next;
4731
key1= key1->insert(key2); // Will destroy key2_root
4732
key2= next;
5482
4733
}
5483
4734
key1->use_count++;
5484
4735
return key1;
5486
4737
5487
4738
5488
4739
/* Compare if two trees are equal */
5489
5490
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
4740
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
5491
4741
{
5492
4742
if (a == b)
5493
return 1;
5494
if (!a || !b || !a->is_same(b))
5495
return 0;
5496
if (a->left != &null_element && b->left != &null_element)
5497
{
5498
if (!eq_tree(a->left,b->left))
5499
return 0;
5500
}
5501
else if (a->left != &null_element || b->left != &null_element)
5502
return 0;
5503
if (a->right != &null_element && b->right != &null_element)
5504
{
5505
if (!eq_tree(a->right,b->right))
5506
return 0;
5507
}
5508
else if (a->right != &null_element || b->right != &null_element)
5509
return 0;
4743
{
4744
return true;
4745
}
4746
4747
if (! a || ! b || ! a->is_same(b))
4748
{
4749
return false;
4750
}
4751
4752
if (a->left != &optimizer::null_element && b->left != &optimizer::null_element)
4753
{
4754
if (! eq_tree(a->left,b->left))
4755
return false;
4756
}
4757
else if (a->left != &optimizer::null_element || b->left != &optimizer::null_element)
4758
{
4759
return false;
4760
}
4761
4762
if (a->right != &optimizer::null_element && b->right != &optimizer::null_element)
4763
{
4764
if (! eq_tree(a->right,b->right))
4765
return false;
4766
}
4767
else if (a->right != &optimizer::null_element || b->right != &optimizer::null_element)
4768
{
4769
return false;
4770
}
4771
5510
4772
if (a->next_key_part != b->next_key_part)
5511
4773
{ // Sub range
5512
if (!a->next_key_part != !b->next_key_part ||
5513
!eq_tree(a->next_key_part, b->next_key_part))
5514
return 0;
5515
}
5516
return 1;
5517
}
5518
5519
5520
SEL_ARG *
5521
SEL_ARG::insert(SEL_ARG *key)
5522
{
5523
SEL_ARG *element, **par= NULL, *last_element= NULL;
5524
5525
for (element= this; element != &null_element ; )
5526
{
5527
last_element=element;
5528
if (key->cmp_min_to_min(element) > 0)
5529
{
5530
par= &element->right; element= element->right;
5531
}
5532
else
5533
{
5534
par = &element->left; element= element->left;
5535
}
5536
}
5537
*par=key;
5538
key->parent=last_element;
5539
/* Link in list */
5540
if (par == &last_element->left)
5541
{
5542
key->next=last_element;
5543
if ((key->prev=last_element->prev))
5544
key->prev->next=key;
5545
last_element->prev=key;
5546
}
5547
else
5548
{
5549
if ((key->next=last_element->next))
5550
key->next->prev=key;
5551
key->prev=last_element;
5552
last_element->next=key;
5553
}
5554
key->left=key->right= &null_element;
5555
SEL_ARG *root=rb_insert(key); // rebalance tree
5556
root->use_count=this->use_count; // copy root info
5557
root->elements= this->elements+1;
5558
root->maybe_flag=this->maybe_flag;
5559
return root;
5560
}
5561
5562
5563
/*
5564
** Find best key with min <= given key
5565
** Because the call context this should never return 0 to get_range
5566
*/
5567
5568
SEL_ARG *
5569
SEL_ARG::find_range(SEL_ARG *key)
5570
{
5571
SEL_ARG *element=this,*found=0;
5572
5573
for (;;)
5574
{
5575
if (element == &null_element)
5576
return found;
5577
int cmp=element->cmp_min_to_min(key);
5578
if (cmp == 0)
5579
return element;
5580
if (cmp < 0)
5581
{
5582
found=element;
5583
element=element->right;
5584
}
5585
else
5586
element=element->left;
5587
}
5588
}
5589
5590
5591
/*
5592
Remove a element from the tree
5593
5594
SYNOPSIS
5595
tree_delete()
5596
key Key that is to be deleted from tree (this)
5597
5598
NOTE
5599
This also frees all sub trees that is used by the element
5600
5601
RETURN
5602
root of new tree (with key deleted)
5603
*/
5604
5605
SEL_ARG *
5606
SEL_ARG::tree_delete(SEL_ARG *key)
5607
{
5608
enum leaf_color remove_color;
5609
SEL_ARG *root,*nod,**par,*fix_par;
5610
5611
root=this;
5612
this->parent= 0;
5613
5614
/* Unlink from list */
5615
if (key->prev)
5616
key->prev->next=key->next;
5617
if (key->next)
5618
key->next->prev=key->prev;
5619
key->increment_use_count(-1);
5620
if (!key->parent)
5621
par= &root;
5622
else
5623
par=key->parent_ptr();
5624
5625
if (key->left == &null_element)
5626
{
5627
*par=nod=key->right;
5628
fix_par=key->parent;
5629
if (nod != &null_element)
5630
nod->parent=fix_par;
5631
remove_color= key->color;
5632
}
5633
else if (key->right == &null_element)
5634
{
5635
*par= nod=key->left;
5636
nod->parent=fix_par=key->parent;
5637
remove_color= key->color;
5638
}
5639
else
5640
{
5641
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5642
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5643
fix_par=tmp->parent;
5644
if (nod != &null_element)
5645
nod->parent=fix_par;
5646
remove_color= tmp->color;
5647
5648
tmp->parent=key->parent; // Move node in place of key
5649
(tmp->left=key->left)->parent=tmp;
5650
if ((tmp->right=key->right) != &null_element)
5651
tmp->right->parent=tmp;
5652
tmp->color=key->color;
5653
*par=tmp;
5654
if (fix_par == key) // key->right == key->next
5655
fix_par=tmp; // new parent of nod
5656
}
5657
5658
if (root == &null_element)
5659
return 0; // Maybe root later
5660
if (remove_color == BLACK)
5661
root=rb_delete_fixup(root,nod,fix_par);
5662
#ifdef EXTRA_DEBUG
5663
test_rb_tree(root,root->parent);
5664
#endif /* EXTRA_DEBUG */
5665
5666
root->use_count=this->use_count; // Fix root counters
5667
root->elements=this->elements-1;
5668
root->maybe_flag=this->maybe_flag;
5669
return(root);
5670
}
5671
5672
5673
/* Functions to fix up the tree after insert and delete */
5674
5675
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5676
{
5677
SEL_ARG *y=leaf->right;
5678
leaf->right=y->left;
5679
if (y->left != &null_element)
5680
y->left->parent=leaf;
5681
if (!(y->parent=leaf->parent))
5682
*root=y;
5683
else
5684
*leaf->parent_ptr()=y;
5685
y->left=leaf;
5686
leaf->parent=y;
5687
}
5688
5689
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5690
{
5691
SEL_ARG *y=leaf->left;
5692
leaf->left=y->right;
5693
if (y->right != &null_element)
5694
y->right->parent=leaf;
5695
if (!(y->parent=leaf->parent))
5696
*root=y;
5697
else
5698
*leaf->parent_ptr()=y;
5699
y->right=leaf;
5700
leaf->parent=y;
5701
}
5702
5703
5704
SEL_ARG *
5705
SEL_ARG::rb_insert(SEL_ARG *leaf)
5706
{
5707
SEL_ARG *y,*par,*par2,*root;
5708
root= this; root->parent= 0;
5709
5710
leaf->color=RED;
5711
while (leaf != root && (par= leaf->parent)->color == RED)
5712
{ // This can't be root or 1 level under
5713
if (par == (par2= leaf->parent->parent)->left)
5714
{
5715
y= par2->right;
5716
if (y->color == RED)
5717
{
5718
par->color=BLACK;
5719
y->color=BLACK;
5720
leaf=par2;
5721
leaf->color=RED; /* And the loop continues */
5722
}
5723
else
5724
{
5725
if (leaf == par->right)
5726
{
5727
left_rotate(&root,leaf->parent);
5728
par=leaf; /* leaf is now parent to old leaf */
5729
}
5730
par->color=BLACK;
5731
par2->color=RED;
5732
right_rotate(&root,par2);
5733
break;
5734
}
5735
}
5736
else
5737
{
5738
y= par2->left;
5739
if (y->color == RED)
5740
{
5741
par->color=BLACK;
5742
y->color=BLACK;
5743
leaf=par2;
5744
leaf->color=RED; /* And the loop continues */
5745
}
5746
else
5747
{
5748
if (leaf == par->left)
5749
{
5750
right_rotate(&root,par);
5751
par=leaf;
5752
}
5753
par->color=BLACK;
5754
par2->color=RED;
5755
left_rotate(&root,par2);
5756
break;
5757
}
5758
}
5759
}
5760
root->color=BLACK;
5761
#ifdef EXTRA_DEBUG
5762
test_rb_tree(root,root->parent);
5763
#endif /* EXTRA_DEBUG */
5764
5765
return root;
5766
}
5767
5768
5769
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5770
{
5771
SEL_ARG *x,*w;
5772
root->parent=0;
5773
5774
x= key;
5775
while (x != root && x->color == SEL_ARG::BLACK)
5776
{
5777
if (x == par->left)
5778
{
5779
w=par->right;
5780
if (w->color == SEL_ARG::RED)
5781
{
5782
w->color=SEL_ARG::BLACK;
5783
par->color=SEL_ARG::RED;
5784
left_rotate(&root,par);
5785
w=par->right;
5786
}
5787
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5788
{
5789
w->color=SEL_ARG::RED;
5790
x=par;
5791
}
5792
else
5793
{
5794
if (w->right->color == SEL_ARG::BLACK)
5795
{
5796
w->left->color=SEL_ARG::BLACK;
5797
w->color=SEL_ARG::RED;
5798
right_rotate(&root,w);
5799
w=par->right;
5800
}
5801
w->color=par->color;
5802
par->color=SEL_ARG::BLACK;
5803
w->right->color=SEL_ARG::BLACK;
5804
left_rotate(&root,par);
5805
x=root;
5806
break;
5807
}
5808
}
5809
else
5810
{
5811
w=par->left;
5812
if (w->color == SEL_ARG::RED)
5813
{
5814
w->color=SEL_ARG::BLACK;
5815
par->color=SEL_ARG::RED;
5816
right_rotate(&root,par);
5817
w=par->left;
5818
}
5819
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5820
{
5821
w->color=SEL_ARG::RED;
5822
x=par;
5823
}
5824
else
5825
{
5826
if (w->left->color == SEL_ARG::BLACK)
5827
{
5828
w->right->color=SEL_ARG::BLACK;
5829
w->color=SEL_ARG::RED;
5830
left_rotate(&root,w);
5831
w=par->left;
5832
}
5833
w->color=par->color;
5834
par->color=SEL_ARG::BLACK;
5835
w->left->color=SEL_ARG::BLACK;
5836
right_rotate(&root,par);
5837
x=root;
5838
break;
5839
}
5840
}
5841
par=x->parent;
5842
}
5843
x->color=SEL_ARG::BLACK;
5844
return root;
5845
}
5846
5847
5848
/* Test that the properties for a red-black tree hold */
5849
5850
#ifdef EXTRA_DEBUG
5851
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5852
{
5853
int count_l,count_r;
5854
5855
if (element == &null_element)
5856
return 0; // Found end of tree
5857
if (element->parent != parent)
5858
{
5859
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5860
return -1;
5861
}
5862
if (element->color == SEL_ARG::RED &&
5863
(element->left->color == SEL_ARG::RED ||
5864
element->right->color == SEL_ARG::RED))
5865
{
5866
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5867
return -1;
5868
}
5869
if (element->left == element->right && element->left != &null_element)
5870
{ // Dummy test
5871
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5872
return -1;
5873
}
5874
count_l=test_rb_tree(element->left,element);
5875
count_r=test_rb_tree(element->right,element);
5876
if (count_l >= 0 && count_r >= 0)
5877
{
5878
if (count_l == count_r)
5879
return count_l+(element->color == SEL_ARG::BLACK);
5880
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5881
count_l,count_r);
5882
}
5883
return -1; // Error, no more warnings
5884
}
5885
5886
5887
/*
5888
Count how many times SEL_ARG graph "root" refers to its part "key"
5889
5890
SYNOPSIS
5891
count_key_part_usage()
5892
root An RB-Root node in a SEL_ARG graph.
5893
key Another RB-Root node in that SEL_ARG graph.
5894
5895
DESCRIPTION
5896
The passed "root" node may refer to "key" node via root->next_key_part,
5897
root->next->n
5898
5899
This function counts how many times the node "key" is referred (via
5900
SEL_ARG::next_key_part) by
5901
- intervals of RB-tree pointed by "root",
5902
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5903
intervals of RB-tree pointed by "root",
5904
- and so on.
5905
5906
Here is an example (horizontal links represent next_key_part pointers,
5907
vertical links - next/prev prev pointers):
5908
5909
+----+ $
5910
|root|-----------------+
5911
+----+ $ |
5912
| $ |
5913
| $ |
5914
+----+ +---+ $ | +---+ Here the return value
5915
| |- ... -| |---$-+--+->|key| will be 4.
5916
+----+ +---+ $ | | +---+
5917
| $ | |
5918
... $ | |
5919
| $ | |
5920
+----+ +---+ $ | |
5921
| |---| |---------+ |
5922
+----+ +---+ $ |
5923
| | $ |
5924
... +---+ $ |
5925
| |------------+
5926
+---+ $
5927
RETURN
5928
Number of links to "key" from nodes reachable from "root".
5929
*/
5930
5931
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5932
{
5933
ulong count= 0;
5934
for (root=root->first(); root ; root=root->next)
5935
{
5936
if (root->next_key_part)
5937
{
5938
if (root->next_key_part == key)
5939
count++;
5940
if (root->next_key_part->part < key->part)
5941
count+=count_key_part_usage(root->next_key_part,key);
5942
}
5943
}
5944
return count;
5945
}
5946
5947
5948
/*
5949
Check if SEL_ARG::use_count value is correct
5950
5951
SYNOPSIS
5952
SEL_ARG::test_use_count()
5953
root The root node of the SEL_ARG graph (an RB-tree root node that
5954
has the least value of sel_arg->part in the entire graph, and
5955
thus is the "origin" of the graph)
5956
5957
DESCRIPTION
5958
Check if SEL_ARG::use_count value is correct. See the definition of
5959
use_count for what is "correct".
5960
*/
5961
5962
void SEL_ARG::test_use_count(SEL_ARG *root)
5963
{
5964
uint32_t e_count=0;
5965
if (this == root && use_count != 1)
5966
{
5967
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5968
return;
5969
}
5970
if (this->type != SEL_ARG::KEY_RANGE)
5971
return;
5972
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5973
{
5974
e_count++;
5975
if (pos->next_key_part)
5976
{
5977
ulong count=count_key_part_usage(root,pos->next_key_part);
5978
if (count > pos->next_key_part->use_count)
5979
{
5980
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5981
"should be %lu", (long unsigned int)pos,
5982
pos->next_key_part->use_count, count);
5983
return;
5984
}
5985
pos->next_key_part->test_use_count(root);
5986
}
5987
}
5988
if (e_count != elements)
5989
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5990
e_count, elements, (long unsigned int) this);
5991
}
5992
5993
#endif
4774
if (! a->next_key_part != ! b->next_key_part ||
4775
! eq_tree(a->next_key_part, b->next_key_part))
4776
return false;
4777
}
4778
4779
return true;
4780
}
4781
5994
4782
5995
4783
/****************************************************************************
5996
4784
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
6013
4801
6014
4802
/* Number of key parts */
6015
4803
uint32_t min_key_parts, max_key_parts;
6016
SEL_ARG *key_tree;
4804
optimizer::SEL_ARG *key_tree;
6017
4805
} RANGE_SEQ_ENTRY;
6018
4806
6019
4807
6024
4812
{
6025
4813
uint32_t keyno; /* index of used tree in SEL_TREE structure */
6026
4814
uint32_t real_keyno; /* Number of the index in tables */
6027
PARAM *param;
6028
SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
4815
optimizer::PARAM *param;
4816
optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
6029
4817
6030
4818
RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
6031
4819
int i; /* Index of last used element in the above array */
6064
4852
}
6065
4853
6066
4854
6067
static void step_down_to(SEL_ARG_RANGE_SEQ *arg, SEL_ARG *key_tree)
4855
static void step_down_to(SEL_ARG_RANGE_SEQ *arg, optimizer::SEL_ARG *key_tree)
6068
4856
{
6069
4857
RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
6070
4858
RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
6116
4904
//psergey-merge-todo: support check_quick_keys:max_keypart
6117
4905
static uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
6118
4906
{
6119
SEL_ARG *key_tree;
4907
optimizer::SEL_ARG *key_tree;
6120
4908
SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
6121
4909
if (seq->at_start)
6122
4910
{
6129
4917
/* Ok, we're at some "full tuple" position in the tree */
6130
4918
6131
4919
/* Step down if we can */
6132
if (key_tree->next && key_tree->next != &null_element)
4920
if (key_tree->next && key_tree->next != &optimizer::null_element)
6133
4921
{
6134
4922
//step down; (update the tuple, we'll step right and stay there)
6135
4923
seq->i--;
6149
4937
key_tree= seq->stack[seq->i].key_tree;
6150
4938
6151
4939
/* Step down if we can */
6152
if (key_tree->next && key_tree->next != &null_element)
4940
if (key_tree->next && key_tree->next != &optimizer::null_element)
6153
4941
{
6154
4942
// Step down; update the tuple
6155
4943
seq->i--;
6164
4952
Walk right-up while we can
6165
4953
*/
6166
4954
walk_right_n_up:
6167
while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
4955
while (key_tree->next_key_part && key_tree->next_key_part != &optimizer::null_element &&
6168
4956
key_tree->next_key_part->part == key_tree->part + 1 &&
6169
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
4957
key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
6170
4958
{
6171
4959
{
6172
4960
RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6173
4961
uint32_t min_key_length= cur->min_key - seq->param->min_key;
6174
4962
uint32_t max_key_length= cur->max_key - seq->param->max_key;
6175
4963
uint32_t len= cur->min_key - cur[-1].min_key;
6176
if (!(min_key_length == max_key_length &&
6177
!memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
6178
!key_tree->min_flag && !key_tree->max_flag))
4964
if (! (min_key_length == max_key_length &&
4965
! memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
4966
! key_tree->min_flag && !key_tree->max_flag))
6179
4967
{
6180
4968
seq->param->is_ror_scan= false;
6181
if (!key_tree->min_flag)
4969
if (! key_tree->min_flag)
6182
4970
cur->min_key_parts +=
6183
4971
key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6184
4972
&cur->min_key,
6185
4973
&cur->min_key_flag);
6186
if (!key_tree->max_flag)
4974
if (! key_tree->max_flag)
6187
4975
cur->max_key_parts +=
6188
4976
key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6189
4977
&cur->max_key,
6199
4987
key_tree= key_tree->next_key_part;
6200
4988
6201
4989
walk_up_n_right:
6202
while (key_tree->prev && key_tree->prev != &null_element)
4990
while (key_tree->prev && key_tree->prev != &optimizer::null_element)
6203
4991
{
6204
4992
/* Step up */
6205
4993
key_tree= key_tree->prev;
6286
5074
*/
6287
5075
6288
5076
static
6289
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
6290
SEL_ARG *tree, bool update_tbl_stats,
6291
uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
5077
ha_rows check_quick_select(optimizer::PARAM *param,
5078
uint32_t idx,
5079
bool index_only,
5080
optimizer::SEL_ARG *tree,
5081
bool update_tbl_stats,
5082
uint32_t *mrr_flags,
5083
uint32_t *bufsize,
5084
COST_VECT *cost)
6292
5085
{
6293
5086
SEL_ARG_RANGE_SEQ seq;
6294
5087
RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
6297
5090
uint32_t keynr= param->real_keynr[idx];
6298
5091
6299
5092
/* Handle cases when we don't have a valid non-empty list of range */
6300
if (!tree)
5093
if (! tree)
6301
5094
return(HA_POS_ERROR);
6302
if (tree->type == SEL_ARG::IMPOSSIBLE)
5095
if (tree->type == optimizer::SEL_ARG::IMPOSSIBLE)
6303
5096
return(0L);
6304
if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)
5097
if (tree->type != optimizer::SEL_ARG::KEY_RANGE || tree->part != 0)
6305
5098
return(HA_POS_ERROR);
6306
5099
6307
5100
seq.keyno= idx;
6402
5195
false Otherwise
6403
5196
*/
6404
5197
6405
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts)
5198
static bool is_key_scan_ror(optimizer::PARAM *param, uint32_t keynr, uint8_t nparts)
6406
5199
{
6407
5200
KEY *table_key= param->table->key_info + keynr;
6408
5201
KEY_PART_INFO *key_part= table_key->key_part + nparts;
6443
5236
optimizer::QuickRangeSelect *
6444
5237
optimizer::get_quick_select(PARAM *param,
6445
5238
uint32_t idx,
6446
SEL_ARG *key_tree,
5239
optimizer::SEL_ARG *key_tree,
6447
5240
uint32_t mrr_flags,
6448
5241
uint32_t mrr_buf_size,
6449
5242
MEM_ROOT *parent_alloc)
6492
5285
** Fix this to get all possible sub_ranges
6493
5286
*/
6494
5287
bool
6495
optimizer::get_quick_keys(PARAM *param,
5288
optimizer::get_quick_keys(optimizer::PARAM *param,
6496
5289
optimizer::QuickRangeSelect *quick,
6497
5290
KEY_PART *key,
6498
SEL_ARG *key_tree,
5291
optimizer::SEL_ARG *key_tree,
6499
5292
unsigned char *min_key,
6500
5293
uint32_t min_key_flag,
6501
5294
unsigned char *max_key,
6506
5299
int min_part= key_tree->part - 1; // # of keypart values in min_key buffer
6507
5300
int max_part= key_tree->part - 1; // # of keypart values in max_key buffer
6508
5301
6509
if (key_tree->left != &null_element)
5302
if (key_tree->left != &optimizer::null_element)
6510
5303
{
6511
5304
if (get_quick_keys(param,
6512
5305
quick,
6520
5313
return 1;
6521
5314
}
6522
5315
}
6523
unsigned char *tmp_min_key=min_key,*tmp_max_key=max_key;
5316
unsigned char *tmp_min_key= min_key,*tmp_max_key= max_key;
6524
5317
min_part+= key_tree->store_min(key[key_tree->part].store_length,
6525
5318
&tmp_min_key,min_key_flag);
6526
5319
max_part+= key_tree->store_max(key[key_tree->part].store_length,
6528
5321
6529
5322
if (key_tree->next_key_part &&
6530
5323
key_tree->next_key_part->part == key_tree->part+1 &&
6531
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
5324
key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
6532
5325
{ // const key as prefix
6533
5326
if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
6534
5327
memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
6636
5429
}
6637
5430
6638
5431
end:
6639
if (key_tree->right != &null_element)
5432
if (key_tree->right != &optimizer::null_element)
6640
5433
{
6641
5434
return get_quick_keys(param,
6642
5435
quick,
7155
5948
7156
5949
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7157
5950
7158
static inline SEL_ARG * get_index_range_tree(uint32_t index,
7159
SEL_TREE* range_tree,
7160
PARAM *param,
7161
uint32_t *param_idx);
5951
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
5952
SEL_TREE *range_tree,
5953
optimizer::PARAM *param,
5954
uint32_t *param_idx);
7162
5955
7163
5956
static bool get_constant_key_infix(KEY *index_info,
7164
SEL_ARG *index_range_tree,
5957
optimizer::SEL_ARG *index_range_tree,
7165
5958
KEY_PART_INFO *first_non_group_part,
7166
5959
KEY_PART_INFO *min_max_arg_part,
7167
5960
KEY_PART_INFO *last_part,
7178
5971
uint32_t used_key_parts,
7179
5972
uint32_t group_key_parts,
7180
5973
SEL_TREE *range_tree,
7181
SEL_ARG *index_tree,
5974
optimizer::SEL_ARG *index_tree,
7182
5975
ha_rows quick_prefix_records,
7183
5976
bool have_min,
7184
5977
bool have_max,
7314
6107
- NULL
7315
6108
*/
7316
6109
static TRP_GROUP_MIN_MAX *
7317
get_best_group_min_max(PARAM *param, SEL_TREE *tree)
6110
get_best_group_min_max(optimizer::PARAM *param, SEL_TREE *tree)
7318
6111
{
7319
6112
Session *session= param->session;
7320
6113
JOIN *join= session->lex->current_select->join;
7418
6211
/* Cost-related variables for the best index so far. */
7419
6212
double best_read_cost= DBL_MAX;
7420
6213
ha_rows best_records= 0;
7421
SEL_ARG *best_index_tree= NULL;
6214
optimizer::SEL_ARG *best_index_tree= NULL;
7422
6215
ha_rows best_quick_prefix_records= 0;
7423
6216
uint32_t best_param_idx= 0;
7424
6217
double cur_read_cost= DBL_MAX;
7425
6218
ha_rows cur_records;
7426
SEL_ARG *cur_index_tree= NULL;
6219
optimizer::SEL_ARG *cur_index_tree= NULL;
7427
6220
ha_rows cur_quick_prefix_records= 0;
7428
6221
uint32_t cur_param_idx= MAX_KEY;
7429
6222
key_map used_key_parts_map;
7583
6376
if (tree)
7584
6377
{
7585
6378
uint32_t dummy;
7586
SEL_ARG *index_range_tree= get_index_range_tree(cur_index,
7587
tree,
7588
param,
7589
&dummy);
6379
optimizer::SEL_ARG *index_range_tree= get_index_range_tree(cur_index,
6380
tree,
6381
param,
6382
&dummy);
7590
6383
if (! get_constant_key_infix(cur_index_info,
7591
6384
index_range_tree,
7592
6385
first_non_group_part,
7915
6708
false o/w
7916
6709
*/
7917
6710
static bool
7918
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
6711
get_constant_key_infix(KEY *,
6712
optimizer::SEL_ARG *index_range_tree,
7919
6713
KEY_PART_INFO *first_non_group_part,
7920
6714
KEY_PART_INFO *min_max_arg_part,
7921
6715
KEY_PART_INFO *last_part,
7924
6718
uint32_t *key_infix_len,
7925
6719
KEY_PART_INFO **first_non_infix_part)
7926
6720
{
7927
SEL_ARG *cur_range= NULL;
6721
optimizer::SEL_ARG *cur_range= NULL;
7928
6722
KEY_PART_INFO *cur_part= NULL;
7929
6723
/* End part for the first loop below. */
7930
6724
KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
8037
6831
RETURN
8038
6832
Pointer to the SEL_ARG subtree that corresponds to index.
8039
6833
*/
8040
SEL_ARG * get_index_range_tree(uint32_t index,
6834
optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
8041
6835
SEL_TREE* range_tree,
8042
PARAM *param,
6836
optimizer::PARAM *param,
8043
6837
uint32_t *param_idx)
8044
6838
{
8045
6839
uint32_t idx= 0; /* Index nr in param->key_parts */
8118
6912
uint32_t used_key_parts,
8119
6913
uint32_t group_key_parts,
8120
6914
SEL_TREE *range_tree,
8121
SEL_ARG *,
6915
optimizer::SEL_ARG *,
8122
6916
ha_rows quick_prefix_records,
8123
6917
bool have_min,
8124
6918
bool have_max,
8214
7008
NULL otherwise.
8215
7009
*/
8216
7010
optimizer::QuickSelectInterface *
8217
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
7011
TRP_GROUP_MIN_MAX::make_quick(optimizer::PARAM *param, bool, MEM_ROOT *parent_alloc)
8218
7012
{
8219
7013
optimizer::QUICK_GROUP_MIN_MAX_SELECT *quick= NULL;
8220
7014
8269
7063
*/
8270
7064
if (min_max_arg_part)
8271
7065
{
8272
SEL_ARG *min_max_range= index_tree;
7066
optimizer::SEL_ARG *min_max_range= index_tree;
8273
7067
while (min_max_range) /* Find the tree for the MIN/MAX key part. */
8274
7068
{
8275
7069
if (min_max_range->field->eq(min_max_arg_part->field))
9303
8097
used_lengths->append(buf, length);
9304
8098
}
9305
8099
9306
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
8100
static void print_sel_tree(optimizer::PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9307
8101
{
9308
SEL_ARG **key= NULL;
9309
SEL_ARG **end= NULL;
8102
optimizer::SEL_ARG **key= NULL;
8103
optimizer::SEL_ARG **end= NULL;
9310
8104
int idx= 0;
9311
8105
char buff[1024];
9312
8106
Loggerhead is a web-based interface for Breezy
Version: 2.0.1