« back to all changes in this revision
Viewing changes to drizzled/optimizer/range.cc
- browse files at revision 1240.1.4
- compare with another revision
- compare with revision 2466
- download diff
- download tarball
- view history from revision 1240.1.4
- Committer: Brian Aker
- Date: 2009-12-08 22:02:21 UTC
- mfrom: (1240.3.8 build)
- mto: (1192.3.79 pandora-build)
- mto: This revision was merged to the branch mainline in revision 1241.
- Revision ID: brian@gaz-20091208220221-lni8fg25a4iwr70k
Big merge.
- files added:
- drizzled/optimizer/quick_index_merge_select.cc
- plugin/show_schema_proto
- plugin/show_schema_proto/tests
- plugin/show_schema_proto/tests/r
- plugin/show_schema_proto/tests/t
- files modified:
- drizzled/Makefile.am
added
removed
drizzled/optimizer/range.cc
117
117
#include "drizzled/check_stack_overrun.h"
118
118
#include "drizzled/optimizer/sum.h"
119
119
#include "drizzled/optimizer/range.h"
120
#include "drizzled/optimizer/quick_range.h"
121
#include "drizzled/optimizer/quick_range_select.h"
122
#include "drizzled/optimizer/quick_index_merge_select.h"
123
#include "drizzled/optimizer/sel_arg.h"
124
#include "drizzled/optimizer/range_param.h"
120
125
#include "drizzled/records.h"
121
126
122
127
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
141
146
return static_cast<ha_rows>(x);
142
147
}
143
148
144
extern "C" int refpos_order_cmp(void *arg, const void *a, const void *b)
145
{
146
Cursor *cursor= (Cursor*)arg;
147
return cursor->cmp_ref((const unsigned char *) a, (const unsigned char *) b);
148
}
149
150
static int sel_cmp(Field *f, unsigned char *a, unsigned char *b, uint8_t a_flag, uint8_t b_flag);
151
152
149
static unsigned char is_null_string[2]= {1,0};
153
150
154
151
195
192
@param cost OUT The cost.
196
193
*/
197
194
198
static void get_sweep_read_cost(Table *table,
199
ha_rows nrows,
195
static void get_sweep_read_cost(Table *table,
196
ha_rows nrows,
200
197
bool interrupted,
201
198
COST_VECT *cost)
202
199
{
227
224
}
228
225
}
229
226
230
class RANGE_OPT_PARAM;
231
/*
232
A construction block of the SEL_ARG-graph.
233
234
The following description only covers graphs of SEL_ARG objects with
235
sel_arg->type==KEY_RANGE:
236
237
One SEL_ARG object represents an "elementary interval" in form
238
239
min_value <=? table.keypartX <=? max_value
240
241
The interval is a non-empty interval of any kind: with[out] minimum/maximum
242
bound, [half]open/closed, single-point interval, etc.
243
244
1. SEL_ARG GRAPH STRUCTURE
245
246
SEL_ARG objects are linked together in a graph. The meaning of the graph
247
is better demostrated by an example:
248
249
tree->keys[i]
250
|
251
| $ $
252
| part=1 $ part=2 $ part=3
253
| $ $
254
| +-------+ $ +-------+ $ +--------+
255
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
256
| +-------+ $ +-------+ $ +--------+
257
| | $ $ |
258
| | $ $ +--------+
259
| | $ $ | kp3=12 |
260
| | $ $ +--------+
261
| +-------+ $ $
262
\->| kp1=2 |--$--------------$-+
263
+-------+ $ $ | +--------+
264
| $ $ ==>| kp3=11 |
265
+-------+ $ $ | +--------+
266
| kp1=3 |--$--------------$-+ |
267
+-------+ $ $ +--------+
268
| $ $ | kp3=14 |
269
... $ $ +--------+
270
271
The entire graph is partitioned into "interval lists".
272
273
An interval list is a sequence of ordered disjoint intervals over the same
274
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
275
all intervals in the list form an RB-tree, linked via left/right/parent
276
pointers. The RB-tree root SEL_ARG object will be further called "root of the
277
interval list".
278
279
In the example pic, there are 4 interval lists:
280
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
281
The vertical lines represent SEL_ARG::next/prev pointers.
282
283
In an interval list, each member X may have SEL_ARG::next_key_part pointer
284
pointing to the root of another interval list Y. The pointed interval list
285
must cover a key part with greater number (i.e. Y->part > X->part).
286
287
In the example pic, the next_key_part pointers are represented by
288
horisontal lines.
289
290
2. SEL_ARG GRAPH SEMANTICS
291
292
It represents a condition in a special form (we don't have a name for it ATM)
293
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
294
295
For example, the picture represents the condition in form:
296
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
297
(kp1=2 AND (kp3=11 OR kp3=14)) OR
298
(kp1=3 AND (kp3=11 OR kp3=14))
299
300
301
3. SEL_ARG GRAPH USE
302
303
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
304
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
305
intervals (i.e. intervals in form
306
307
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
308
309
Those intervals can be used to access the index. The uses are in:
310
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
311
how many table records are contained within all
312
intervals.
313
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
314
and create QUICK_RANGE_SELECT object that will
315
read records within these intervals.
316
317
4. SPACE COMPLEXITY NOTES
318
319
SEL_ARG graph is a representation of an ordered disjoint sequence of
320
intervals over the ordered set of index tuple values.
321
322
For multi-part keys, one can construct a WHERE expression such that its
323
list of intervals will be of combinatorial size. Here is an example:
324
325
(keypart1 IN (1,2, ..., n1)) AND
326
(keypart2 IN (1,2, ..., n2)) AND
327
(keypart3 IN (1,2, ..., n3))
328
329
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
330
of form
331
332
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
333
334
SEL_ARG graph structure aims to reduce the amount of required space by
335
"sharing" the elementary intervals when possible (the pic at the
336
beginning of this comment has examples of such sharing). The sharing may
337
prevent combinatorial blowup:
338
339
There are WHERE clauses that have combinatorial-size interval lists but
340
will be represented by a compact SEL_ARG graph.
341
Example:
342
(keypartN IN (1,2, ..., n1)) AND
343
...
344
(keypart2 IN (1,2, ..., n2)) AND
345
(keypart1 IN (1,2, ..., n3))
346
347
but not in all cases:
348
349
- There are WHERE clauses that do have a compact SEL_ARG-graph
350
representation but get_mm_tree() and its callees will construct a
351
graph of combinatorial size.
352
Example:
353
(keypart1 IN (1,2, ..., n1)) AND
354
(keypart2 IN (1,2, ..., n2)) AND
355
...
356
(keypartN IN (1,2, ..., n3))
357
358
- There are WHERE clauses for which the minimal possible SEL_ARG graph
359
representation will have combinatorial size.
360
Example:
361
By induction: Let's take any interval on some keypart in the middle:
362
363
kp15=c0
364
365
Then let's AND it with this interval 'structure' from preceding and
366
following keyparts:
367
368
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
369
370
We will obtain this SEL_ARG graph:
371
372
kp14 $ kp15 $ kp16
373
$ $
374
+---------+ $ +---------+ $ +---------+
375
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
376
+---------+ $ +---------+ $ +---------+
377
| $ $
378
+---------+ $ +---------+ $
379
| kp14=c2 |--$-->| kp15=c0 | $
380
+---------+ $ +---------+ $
381
$ $
382
383
Note that we had to duplicate "kp15=c0" and there was no way to avoid
384
that.
385
The induction step: AND the obtained expression with another "wrapping"
386
expression like (*).
387
When the process ends because of the limit on max. number of keyparts
388
we'll have:
389
390
WHERE clause length is O(3*#max_keyparts)
391
SEL_ARG graph size is O(2^(#max_keyparts/2))
392
393
(it is also possible to construct a case where instead of 2 in 2^n we
394
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
395
nodes)
396
397
We avoid consuming too much memory by setting a limit on the number of
398
SEL_ARG object we can construct during one range analysis invocation.
399
*/
400
401
class SEL_ARG :public Sql_alloc
402
{
403
public:
404
uint8_t min_flag,max_flag,maybe_flag;
405
uint8_t part; // Which key part
406
uint8_t maybe_null;
407
/*
408
Number of children of this element in the RB-tree, plus 1 for this
409
element itself.
410
*/
411
uint16_t elements;
412
/*
413
Valid only for elements which are RB-tree roots: Number of times this
414
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
415
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
416
*/
417
ulong use_count;
418
419
Field *field;
420
unsigned char *min_value,*max_value; // Pointer to range
421
422
/*
423
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
424
*/
425
SEL_ARG *left,*right; /* R-B tree children */
426
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
427
SEL_ARG *parent; /* R-B tree parent */
428
SEL_ARG *next_key_part;
429
enum leaf_color { BLACK,RED } color;
430
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
431
432
enum { MAX_SEL_ARGS = 16000 };
433
434
SEL_ARG() {}
435
SEL_ARG(SEL_ARG &);
436
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
437
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
438
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
439
SEL_ARG(enum Type type_arg)
440
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
441
color(BLACK), type(type_arg)
442
{}
443
inline bool is_same(SEL_ARG *arg)
444
{
445
if (type != arg->type || part != arg->part)
446
return 0;
447
if (type != KEY_RANGE)
448
return 1;
449
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
450
}
451
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
452
inline void maybe_smaller() { maybe_flag=1; }
453
/* Return true iff it's a single-point null interval */
454
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
455
inline int cmp_min_to_min(SEL_ARG* arg)
456
{
457
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
458
}
459
inline int cmp_min_to_max(SEL_ARG* arg)
460
{
461
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
462
}
463
inline int cmp_max_to_max(SEL_ARG* arg)
464
{
465
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
466
}
467
inline int cmp_max_to_min(SEL_ARG* arg)
468
{
469
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
470
}
471
SEL_ARG *clone_and(SEL_ARG* arg)
472
{ // Get overlapping range
473
unsigned char *new_min,*new_max;
474
uint8_t flag_min,flag_max;
475
if (cmp_min_to_min(arg) >= 0)
476
{
477
new_min=min_value; flag_min=min_flag;
478
}
479
else
480
{
481
new_min=arg->min_value; flag_min=arg->min_flag;
482
}
483
if (cmp_max_to_max(arg) <= 0)
484
{
485
new_max=max_value; flag_max=max_flag;
486
}
487
else
488
{
489
new_max=arg->max_value; flag_max=arg->max_flag;
490
}
491
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
492
test(maybe_flag && arg->maybe_flag));
493
}
494
SEL_ARG *clone_first(SEL_ARG *arg)
495
{ // min <= X < arg->min
496
return new SEL_ARG(field,part, min_value, arg->min_value,
497
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
498
maybe_flag | arg->maybe_flag);
499
}
500
SEL_ARG *clone_last(SEL_ARG *arg)
501
{ // min <= X <= key_max
502
return new SEL_ARG(field, part, min_value, arg->max_value,
503
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
504
}
505
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
506
507
bool copy_min(SEL_ARG* arg)
508
{ // Get overlapping range
509
if (cmp_min_to_min(arg) > 0)
510
{
511
min_value=arg->min_value; min_flag=arg->min_flag;
512
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
513
(NO_MAX_RANGE | NO_MIN_RANGE))
514
return 1; // Full range
515
}
516
maybe_flag|=arg->maybe_flag;
517
return 0;
518
}
519
bool copy_max(SEL_ARG* arg)
520
{ // Get overlapping range
521
if (cmp_max_to_max(arg) <= 0)
522
{
523
max_value=arg->max_value; max_flag=arg->max_flag;
524
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
525
(NO_MAX_RANGE | NO_MIN_RANGE))
526
return 1; // Full range
527
}
528
maybe_flag|=arg->maybe_flag;
529
return 0;
530
}
531
532
void copy_min_to_min(SEL_ARG *arg)
533
{
534
min_value=arg->min_value; min_flag=arg->min_flag;
535
}
536
void copy_min_to_max(SEL_ARG *arg)
537
{
538
max_value=arg->min_value;
539
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
540
}
541
void copy_max_to_min(SEL_ARG *arg)
542
{
543
min_value=arg->max_value;
544
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
545
}
546
/* returns a number of keypart values (0 or 1) appended to the key buffer */
547
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
548
{
549
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
550
if ((!(min_flag & NO_MIN_RANGE) &&
551
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
552
{
553
if (maybe_null && *min_value)
554
{
555
**min_key=1;
556
memset(*min_key+1, 0, length-1);
557
}
558
else
559
memcpy(*min_key,min_value,length);
560
(*min_key)+= length;
561
return 1;
562
}
563
return 0;
564
}
565
/* returns a number of keypart values (0 or 1) appended to the key buffer */
566
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
567
{
568
if (!(max_flag & NO_MAX_RANGE) &&
569
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
570
{
571
if (maybe_null && *max_value)
572
{
573
**max_key=1;
574
memset(*max_key+1, 0, length-1);
575
}
576
else
577
memcpy(*max_key,max_value,length);
578
(*max_key)+= length;
579
return 1;
580
}
581
return 0;
582
}
583
584
/* returns a number of keypart values appended to the key buffer */
585
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
586
{
587
SEL_ARG *key_tree= first();
588
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
589
range_key, *range_key_flag);
590
*range_key_flag|= key_tree->min_flag;
591
592
if (key_tree->next_key_part &&
593
key_tree->next_key_part->part == key_tree->part+1 &&
594
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
595
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
596
res+= key_tree->next_key_part->store_min_key(key, range_key,
597
range_key_flag);
598
return res;
599
}
600
601
/* returns a number of keypart values appended to the key buffer */
602
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
603
{
604
SEL_ARG *key_tree= last();
605
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
606
range_key, *range_key_flag);
607
(*range_key_flag)|= key_tree->max_flag;
608
if (key_tree->next_key_part &&
609
key_tree->next_key_part->part == key_tree->part+1 &&
610
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
611
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
612
res+= key_tree->next_key_part->store_max_key(key, range_key,
613
range_key_flag);
614
return res;
615
}
616
617
SEL_ARG *insert(SEL_ARG *key);
618
SEL_ARG *tree_delete(SEL_ARG *key);
619
SEL_ARG *find_range(SEL_ARG *key);
620
SEL_ARG *rb_insert(SEL_ARG *leaf);
621
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
622
#ifdef EXTRA_DEBUG
623
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
624
void test_use_count(SEL_ARG *root);
625
#endif
626
SEL_ARG *first();
627
SEL_ARG *last();
628
void make_root();
629
inline bool simple_key()
630
{
631
return !next_key_part && elements == 1;
632
}
633
void increment_use_count(long count)
634
{
635
if (next_key_part)
636
{
637
next_key_part->use_count+=count;
638
count*= (next_key_part->use_count-count);
639
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
640
if (pos->next_key_part)
641
pos->increment_use_count(count);
642
}
643
}
644
void free_tree()
645
{
646
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
647
if (pos->next_key_part)
648
{
649
pos->next_key_part->use_count--;
650
pos->next_key_part->free_tree();
651
}
652
}
653
654
inline SEL_ARG **parent_ptr()
655
{
656
return parent->left == this ? &parent->left : &parent->right;
657
}
658
659
660
/*
661
Check if this SEL_ARG object represents a single-point interval
662
663
SYNOPSIS
664
is_singlepoint()
665
666
DESCRIPTION
667
Check if this SEL_ARG object (not tree) represents a single-point
668
interval, i.e. if it represents a "keypart = const" or
669
"keypart IS NULL".
670
671
RETURN
672
true This SEL_ARG object represents a singlepoint interval
673
false Otherwise
674
*/
675
676
bool is_singlepoint()
677
{
678
/*
679
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
680
flags, and the same for right edge.
681
*/
682
if (min_flag || max_flag)
683
return false;
684
unsigned char *min_val= min_value;
685
unsigned char *max_val= max_value;
686
687
if (maybe_null)
688
{
689
/* First byte is a NULL value indicator */
690
if (*min_val != *max_val)
691
return false;
692
693
if (*min_val)
694
return true; /* This "x IS NULL" */
695
min_val++;
696
max_val++;
697
}
698
return !field->key_cmp(min_val, max_val);
699
}
700
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
701
};
702
703
227
class SEL_IMERGE;
704
228
705
229
708
232
public:
709
233
/*
710
234
Starting an effort to document this field:
711
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
235
(for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
712
236
(type == SEL_TREE::IMPOSSIBLE)
713
237
*/
714
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
715
247
SEL_TREE(enum Type type_arg) :type(type_arg) {}
716
248
SEL_TREE() :type(KEY)
717
249
{
724
256
merit in range analyzer functions (e.g. get_mm_parts) returning a
725
257
pointer to such SEL_TREE instead of NULL)
726
258
*/
727
SEL_ARG *keys[MAX_KEY];
259
optimizer::SEL_ARG *keys[MAX_KEY];
728
260
key_map keys_map; /* bitmask of non-NULL elements in keys */
729
261
730
262
/*
735
267
736
268
/* The members below are filled/used only after get_mm_tree is done */
737
269
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
738
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
270
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
739
271
740
272
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
741
273
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
742
274
/* Note that #records for each key scan is stored in table->quick_rows */
743
275
};
744
276
745
class RANGE_OPT_PARAM
746
{
747
public:
748
Session *session; /* Current thread handle */
749
Table *table; /* Table being analyzed */
750
COND *cond; /* Used inside get_mm_tree(). */
751
table_map prev_tables;
752
table_map read_tables;
753
table_map current_table; /* Bit of the table being analyzed */
754
755
/* Array of parts of all keys for which range analysis is performed */
756
KEY_PART *key_parts;
757
KEY_PART *key_parts_end;
758
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
759
MEM_ROOT *old_root; /* Memory that will last until the query end */
760
/*
761
Number of indexes used in range analysis (In SEL_TREE::keys only first
762
#keys elements are not empty)
763
*/
764
uint32_t keys;
765
766
/*
767
If true, the index descriptions describe real indexes (and it is ok to
768
call field->optimize_range(real_keynr[...], ...).
769
Otherwise index description describes fake indexes.
770
*/
771
bool using_real_indexes;
772
773
bool remove_jump_scans;
774
775
/*
776
used_key_no -> table_key_no translation table. Only makes sense if
777
using_real_indexes==true
778
*/
779
uint32_t real_keynr[MAX_KEY];
780
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
781
uint32_t alloced_sel_args;
782
bool force_default_mrr;
783
};
784
785
class PARAM : public RANGE_OPT_PARAM
786
{
787
public:
788
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
789
uint32_t max_key_part;
790
/* Number of ranges in the last checked tree->key */
791
uint32_t range_count;
792
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
793
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
794
bool quick; // Don't calulate possible keys
795
796
uint32_t fields_bitmap_size;
797
MyBitmap needed_fields; /* bitmask of fields needed by the query */
798
MyBitmap tmp_covered_fields;
799
800
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
801
802
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
803
uint32_t imerge_cost_buff_size; /* size of the buffer */
804
805
/* true if last checked tree->key can be used for ROR-scan */
806
bool is_ror_scan;
807
/* Number of ranges in the last checked tree->key */
808
uint32_t n_ranges;
809
};
810
811
277
class TABLE_READ_PLAN;
812
278
class TRP_RANGE;
813
279
class TRP_ROR_INTERSECT;
817
283
818
284
struct st_ror_scan_info;
819
285
820
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
821
Item_func::Functype type,Item *value,
822
Item_result cmp_type);
823
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
824
KEY_PART *key_part,
825
Item_func::Functype type,Item *value);
826
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
827
828
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
829
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
830
SEL_ARG *tree, bool update_tbl_stats,
831
uint32_t *mrr_flags, uint32_t *bufsize,
286
static SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
287
COND *cond_func,
288
Field *field,
289
Item_func::Functype type,
290
Item *value,
291
Item_result cmp_type);
292
293
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *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::RangeParameter *param, COND *cond);
301
302
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
303
304
static ha_rows check_quick_select(optimizer::Parameter *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,
832
311
COST_VECT *cost);
833
312
834
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
313
static TRP_RANGE *get_key_scans_params(optimizer::Parameter *param,
314
SEL_TREE *tree,
835
315
bool index_read_must_be_used,
836
316
bool update_tbl_stats,
837
317
double read_time);
318
838
319
static
839
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
320
TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::Parameter *param,
321
SEL_TREE *tree,
840
322
double read_time,
841
323
bool *are_all_covering);
324
842
325
static
843
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
326
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::Parameter *param,
844
327
SEL_TREE *tree,
845
328
double read_time);
329
846
330
static
847
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
331
TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::Parameter *param,
332
SEL_IMERGE *imerge,
848
333
double read_time);
334
849
335
static
850
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::Parameter *param, SEL_TREE *tree);
851
337
852
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
338
static void print_sel_tree(optimizer::Parameter *param,
339
SEL_TREE *tree,
340
key_map *tree_map,
853
341
const char *msg);
854
static void print_ror_scans_arr(Table *table, const char *msg,
342
343
static void print_ror_scans_arr(Table *table,
344
const char *msg,
855
345
struct st_ror_scan_info **start,
856
346
struct st_ror_scan_info **end);
857
347
858
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
859
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
860
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
861
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
862
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
863
uint32_t clone_flag);
864
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
865
866
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
867
868
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
869
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
348
static SEL_TREE *tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2);
349
350
static SEL_TREE *tree_or(optimizer::RangeParameter *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::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
355
356
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *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);
366
367
static bool null_part_in_key(KEY_PART *key_part,
368
const unsigned char *key,
870
369
uint32_t length);
871
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
370
371
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, optimizer::RangeParameter *param);
872
372
873
373
874
374
/*
893
393
SEL_TREE **trees_next; /* last of these trees */
894
394
SEL_TREE **trees_end; /* end of allocated space */
895
395
896
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
396
optimizer::SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
897
397
898
398
SEL_IMERGE() :
899
399
trees(&trees_prealloced[0]),
900
400
trees_next(trees),
901
401
trees_end(trees + PREALLOCED_TREES)
902
402
{}
903
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
904
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
905
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
403
int or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree);
404
int or_sel_tree_with_checks(optimizer::RangeParameter *param, SEL_TREE *new_tree);
405
int or_sel_imerge_with_checks(optimizer::RangeParameter *param, SEL_IMERGE* imerge);
906
406
};
907
407
908
408
917
417
0 - OK
918
418
-1 - Out of memory.
919
419
*/
920
921
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
420
int SEL_IMERGE::or_sel_tree(optimizer::RangeParameter *param, SEL_TREE *tree)
922
421
{
923
422
if (trees_next == trees_end)
924
423
{
930
429
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
931
430
return -1;
932
431
memcpy(new_trees, trees, old_size);
933
trees= new_trees;
432
trees= new_trees;
934
433
trees_next= trees + old_elements;
935
trees_end= trees + old_elements * realloc_ratio;
434
trees_end= trees + old_elements * realloc_ratio;
936
435
}
937
436
*(trees_next++)= tree;
938
437
return 0;
946
445
947
446
SYNOPSIS
948
447
or_sel_tree_with_checks()
949
param PARAM from SQL_SELECT::test_quick_select
448
param Parameter from SqlSelect::test_quick_select
950
449
new_tree SEL_TREE with type KEY or KEY_SMALLER.
951
450
952
451
NOTES
968
467
and (*this) should be discarded.
969
468
-1 An error occurred.
970
469
*/
971
972
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::RangeParameter *param, SEL_TREE *new_tree)
973
471
{
974
472
for (SEL_TREE** tree = trees;
975
473
tree != trees_next;
1003
501
-1 - An error occurred
1004
502
*/
1005
503
1006
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::RangeParameter *param, SEL_IMERGE* imerge)
1007
505
{
1008
506
for (SEL_TREE** tree= imerge->trees;
1009
507
tree != imerge->trees_next;
1049
547
other Error, both passed lists are unusable
1050
548
*/
1051
549
1052
static int imerge_list_or_list(RANGE_OPT_PARAM *param,
550
static int imerge_list_or_list(optimizer::RangeParameter *param,
1053
551
List<SEL_IMERGE> *im1,
1054
552
List<SEL_IMERGE> *im2)
1055
553
{
1068
566
0 OK, result is stored in *im1.
1069
567
other Error
1070
568
*/
1071
1072
static int imerge_list_or_tree(RANGE_OPT_PARAM *param,
569
570
static int imerge_list_or_tree(optimizer::RangeParameter *param,
1073
571
List<SEL_IMERGE> *im1,
1074
572
SEL_TREE *tree)
1075
573
{
1085
583
1086
584
1087
585
/***************************************************************************
1088
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
586
** Basic functions for SqlSelect and QuickRangeSelect
1089
587
***************************************************************************/
1090
588
1091
589
/* make a select from mysql info
1094
592
1 = Got some error (out of memory?)
1095
593
*/
1096
594
1097
optimizer::SQL_SELECT *optimizer::make_select(Table *head,
595
optimizer::SqlSelect *optimizer::make_select(Table *head,
1098
596
table_map const_tables,
1099
table_map read_tables,
597
table_map read_tables,
1100
598
COND *conds,
1101
599
bool allow_null_cond,
1102
600
int *error)
1103
601
{
1104
optimizer::SQL_SELECT *select= NULL;
602
optimizer::SqlSelect *select= NULL;
1105
603
1106
604
*error= 0;
1107
605
1109
607
{
1110
608
return 0;
1111
609
}
1112
if (! (select= new optimizer::SQL_SELECT))
610
if (! (select= new optimizer::SqlSelect))
1113
611
{
1114
612
*error= 1; // out of memory
1115
613
return 0;
1131
629
}
1132
630
1133
631
1134
optimizer::SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
632
optimizer::SqlSelect::SqlSelect() :quick(0),cond(0),free_cond(0)
1135
633
{
1136
quick_keys.reset();
634
quick_keys.reset();
1137
635
needed_reg.reset();
1138
636
my_b_clear(&file);
1139
637
}
1140
638
1141
639
1142
void optimizer::SQL_SELECT::cleanup()
640
void optimizer::SqlSelect::cleanup()
1143
641
{
1144
642
delete quick;
1145
643
quick= 0;
1153
651
}
1154
652
1155
653
1156
optimizer::SQL_SELECT::~SQL_SELECT()
654
optimizer::SqlSelect::~SqlSelect()
1157
655
{
1158
656
cleanup();
1159
657
}
1160
658
1161
659
1162
bool optimizer::SQL_SELECT::check_quick(Session *session, bool force_quick_range,
660
bool optimizer::SqlSelect::check_quick(Session *session, bool force_quick_range,
1163
661
ha_rows limit)
1164
662
{
1165
663
key_map tmp;
1169
667
}
1170
668
1171
669
1172
bool optimizer::SQL_SELECT::skip_record()
670
bool optimizer::SqlSelect::skip_record()
1173
671
{
1174
672
return cond ? cond->val_int() == 0 : 0;
1175
673
}
1176
674
1177
675
1178
optimizer::QUICK_SELECT_I::QUICK_SELECT_I()
676
optimizer::QuickSelectInterface::QuickSelectInterface()
1179
677
:
1180
678
max_used_key_length(0),
1181
679
used_key_parts(0)
1182
680
{}
1183
681
1184
optimizer::QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session,
1185
Table *table,
1186
uint32_t key_nr,
1187
bool no_alloc,
1188
MEM_ROOT *parent_alloc,
1189
bool *create_error)
1190
:
1191
free_file(0),
1192
cur_range(NULL),
1193
last_range(0),
1194
dont_free(0)
1195
{
1196
my_bitmap_map *bitmap= NULL;
1197
1198
in_ror_merged_scan= 0;
1199
sorted= 0;
1200
index= key_nr;
1201
head= table;
1202
key_part_info= head->key_info[index].key_part;
1203
my_init_dynamic_array(&ranges, sizeof(optimizer::QUICK_RANGE*), 16, 16);
1204
1205
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1206
mrr_buf_size= session->variables.read_rnd_buff_size;
1207
mrr_buf_desc= NULL;
1208
1209
if (!no_alloc && !parent_alloc)
1210
{
1211
// Allocates everything through the internal memroot
1212
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1213
session->mem_root= &alloc;
1214
}
1215
else
1216
memset(&alloc, 0, sizeof(alloc));
1217
cursor= head->cursor;
1218
record= head->record[0];
1219
save_read_set= head->read_set;
1220
save_write_set= head->write_set;
1221
1222
/* Allocate a bitmap for used columns. Using sql_alloc instead of malloc
1223
simply as a "fix" to the MySQL 6.0 code that also free()s it at the
1224
same time we destroy the mem_root.
1225
*/
1226
1227
bitmap= reinterpret_cast<my_bitmap_map*>(sql_alloc(head->s->column_bitmap_size));
1228
if (! bitmap)
1229
{
1230
column_bitmap.setBitmap(NULL);
1231
*create_error= 1;
1232
}
1233
else
1234
{
1235
column_bitmap.init(bitmap, head->s->fields);
1236
}
1237
}
1238
1239
1240
int optimizer::QUICK_RANGE_SELECT::init()
1241
{
1242
if (cursor->inited != Cursor::NONE)
1243
cursor->ha_index_or_rnd_end();
1244
return (cursor->ha_index_init(index, 1));
1245
}
1246
1247
1248
void optimizer::QUICK_RANGE_SELECT::range_end()
1249
{
1250
if (cursor->inited != Cursor::NONE)
1251
cursor->ha_index_or_rnd_end();
1252
}
1253
1254
1255
optimizer::QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1256
{
1257
if (!dont_free)
1258
{
1259
/* cursor is NULL for CPK scan on covering ROR-intersection */
1260
if (cursor)
1261
{
1262
range_end();
1263
if (head->key_read)
1264
{
1265
head->key_read= 0;
1266
cursor->extra(HA_EXTRA_NO_KEYREAD);
1267
}
1268
if (free_file)
1269
{
1270
cursor->ha_external_lock(current_session, F_UNLCK);
1271
cursor->close();
1272
delete cursor;
1273
}
1274
}
1275
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1276
free_root(&alloc,MYF(0));
1277
}
1278
head->column_bitmaps_set(save_read_set, save_write_set);
1279
assert(mrr_buf_desc == NULL);
1280
if (mrr_buf_desc)
1281
{
1282
free(mrr_buf_desc);
1283
}
1284
}
1285
1286
1287
optimizer::QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1288
Table *table)
1289
:
1290
pk_quick_select(NULL),
1291
session(session_param)
1292
{
1293
index= MAX_KEY;
1294
head= table;
1295
memset(&read_record, 0, sizeof(read_record));
1296
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1297
return;
1298
}
1299
1300
int optimizer::QUICK_INDEX_MERGE_SELECT::init()
1301
{
1302
return 0;
1303
}
1304
1305
int optimizer::QUICK_INDEX_MERGE_SELECT::reset()
1306
{
1307
return (read_keys_and_merge());
1308
}
1309
1310
bool
1311
optimizer::QUICK_INDEX_MERGE_SELECT::push_quick_back(optimizer::QUICK_RANGE_SELECT *quick_sel_range)
1312
{
1313
/*
1314
Save quick_select that does scan on clustered primary key as it will be
1315
processed separately.
1316
*/
1317
if (head->cursor->primary_key_is_clustered() &&
1318
quick_sel_range->index == head->s->primary_key)
1319
{
1320
pk_quick_select= quick_sel_range;
1321
}
1322
else
1323
{
1324
return quick_selects.push_back(quick_sel_range);
1325
}
1326
return 0;
1327
}
1328
1329
optimizer::QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1330
{
1331
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> quick_it(quick_selects);
1332
optimizer::QUICK_RANGE_SELECT* quick;
1333
quick_it.rewind();
1334
while ((quick= quick_it++))
1335
{
1336
quick->cursor= NULL;
1337
}
1338
quick_selects.delete_elements();
1339
delete pk_quick_select;
1340
free_root(&alloc,MYF(0));
1341
return;
1342
}
1343
682
1344
683
1345
684
optimizer::QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1346
685
Table *table,
1347
686
bool retrieve_full_rows,
1348
687
MEM_ROOT *parent_alloc)
1349
:
1350
cpk_quick(NULL),
1351
session(session_param),
688
:
689
cpk_quick(NULL),
690
session(session_param),
1352
691
need_to_fetch_row(retrieve_full_rows),
1353
692
scans_inited(false)
1354
693
{
1386
725
1387
726
1388
727
/*
1389
Initialize this quick select to be a ROR-merged scan.
1390
1391
SYNOPSIS
1392
QUICK_RANGE_SELECT::init_ror_merged_scan()
1393
reuse_handler If true, use head->cursor, otherwise create a separate
1394
Cursor object
1395
1396
NOTES
1397
This function creates and prepares for subsequent use a separate Cursor
1398
object if it can't reuse head->cursor. The reason for this is that during
1399
ROR-merge several key scans are performed simultaneously, and a single
1400
Cursor is only capable of preserving context of a single key scan.
1401
1402
In ROR-merge the quick select doing merge does full records retrieval,
1403
merged quick selects read only keys.
1404
1405
RETURN
1406
0 ROR child scan initialized, ok to use.
1407
1 error
1408
*/
1409
1410
int optimizer::QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1411
{
1412
Cursor *save_file= cursor, *org_file;
1413
Session *session;
1414
1415
in_ror_merged_scan= 1;
1416
if (reuse_handler)
1417
{
1418
if (init() || reset())
1419
{
1420
return 0;
1421
}
1422
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1423
goto end;
1424
}
1425
1426
/* Create a separate Cursor object for this quick select */
1427
if (free_file)
1428
{
1429
/* already have own 'Cursor' object. */
1430
return 0;
1431
}
1432
1433
session= head->in_use;
1434
if (! (cursor= head->cursor->clone(session->mem_root)))
1435
{
1436
/*
1437
Manually set the error flag. Note: there seems to be quite a few
1438
places where a failure could cause the server to "hang" the client by
1439
sending no response to a query. ATM those are not real errors because
1440
the storage engine calls in question happen to never fail with the
1441
existing storage engines.
1442
*/
1443
my_error(ER_OUT_OF_RESOURCES, MYF(0));
1444
/* Caller will free the memory */
1445
goto failure;
1446
}
1447
1448
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1449
1450
if (cursor->ha_external_lock(session, F_RDLCK))
1451
goto failure;
1452
1453
if (init() || reset())
1454
{
1455
cursor->ha_external_lock(session, F_UNLCK);
1456
cursor->close();
1457
goto failure;
1458
}
1459
free_file= true;
1460
last_rowid= cursor->ref;
1461
1462
end:
1463
/*
1464
We are only going to read key fields and call position() on 'cursor'
1465
The following sets head->tmp_set to only use this key and then updates
1466
head->read_set and head->write_set to use this bitmap.
1467
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1468
*/
1469
org_file= head->cursor;
1470
head->cursor= cursor;
1471
/* We don't have to set 'head->keyread' here as the 'cursor' is unique */
1472
if (! head->no_keyread)
1473
{
1474
head->key_read= 1;
1475
head->mark_columns_used_by_index(index);
1476
}
1477
head->prepare_for_position();
1478
head->cursor= org_file;
1479
column_bitmap= *head->read_set;
1480
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1481
1482
return 0;
1483
1484
failure:
1485
head->column_bitmaps_set(save_read_set, save_write_set);
1486
delete cursor;
1487
cursor= save_file;
1488
return 0;
1489
}
1490
1491
1492
void optimizer::QUICK_RANGE_SELECT::save_last_pos()
1493
{
1494
cursor->position(record);
1495
}
1496
1497
1498
/*
1499
728
Initialize this quick select to be a part of a ROR-merged scan.
1500
729
SYNOPSIS
1501
730
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1507
736
*/
1508
737
int optimizer::QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1509
738
{
1510
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> quick_it(quick_selects);
1511
optimizer::QUICK_RANGE_SELECT* quick;
739
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
740
optimizer::QuickRangeSelect *quick= NULL;
1512
741
1513
742
/* Initialize all merged "children" quick selects */
1514
743
assert(!need_to_fetch_row || reuse_handler);
1558
787
return 0;
1559
788
}
1560
789
scans_inited= true;
1561
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> it(quick_selects);
1562
optimizer::QUICK_RANGE_SELECT *quick;
790
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
791
optimizer::QuickRangeSelect *quick= NULL;
1563
792
while ((quick= it++))
1564
793
{
1565
794
quick->reset();
1584
813
*/
1585
814
1586
815
bool
1587
optimizer::QUICK_ROR_INTERSECT_SELECT::push_quick_back(optimizer::QUICK_RANGE_SELECT *quick)
816
optimizer::QUICK_ROR_INTERSECT_SELECT::push_quick_back(optimizer::QuickRangeSelect *quick)
1588
817
{
1589
818
return quick_selects.push_back(quick);
1590
819
}
1604
833
1605
834
optimizer::QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1606
835
Table *table)
1607
:
1608
session(session_param),
836
:
837
session(session_param),
1609
838
scans_inited(false)
1610
839
{
1611
840
index= MAX_KEY;
1627
856
public:
1628
857
compare_functor(optimizer::QUICK_ROR_UNION_SELECT *in_arg)
1629
858
: self(in_arg) { }
1630
inline bool operator()(const optimizer::QUICK_SELECT_I *i, const optimizer::QUICK_SELECT_I *j) const
859
inline bool operator()(const optimizer::QuickSelectInterface *i, const optimizer::QuickSelectInterface *j) const
1631
860
{
1632
861
int val= self->head->cursor->cmp_ref(i->last_rowid,
1633
862
j->last_rowid);
1647
876
1648
877
int optimizer::QUICK_ROR_UNION_SELECT::init()
1649
878
{
1650
queue=
1651
new priority_queue<optimizer::QUICK_SELECT_I *,
1652
vector<optimizer::QUICK_SELECT_I *>,
879
queue=
880
new priority_queue<optimizer::QuickSelectInterface *,
881
vector<optimizer::QuickSelectInterface *>,
1653
882
optimizer::compare_functor >(optimizer::compare_functor(this));
1654
883
if (! (cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->cursor->ref_length)))
1655
884
{
1672
901
1673
902
int optimizer::QUICK_ROR_UNION_SELECT::reset()
1674
903
{
1675
QUICK_SELECT_I *quick= NULL;
904
QuickSelectInterface *quick= NULL;
1676
905
int error;
1677
906
have_prev_rowid= false;
1678
907
if (! scans_inited)
1679
908
{
1680
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
909
List_iterator_fast<QuickSelectInterface> it(quick_selects);
1681
910
while ((quick= it++))
1682
911
{
1683
912
if (quick->init_ror_merged_scan(false))
1695
924
Initialize scans for merged quick selects and put all merged quick
1696
925
selects into the queue.
1697
926
*/
1698
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
927
List_iterator_fast<QuickSelectInterface> it(quick_selects);
1699
928
while ((quick= it++))
1700
929
{
1701
930
if (quick->reset())
1724
953
1725
954
1726
955
bool
1727
optimizer::QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
956
optimizer::QUICK_ROR_UNION_SELECT::push_quick_back(QuickSelectInterface *quick_sel_range)
1728
957
{
1729
958
return quick_selects.push_back(quick_sel_range);
1730
959
}
1746
975
}
1747
976
1748
977
1749
optimizer::QUICK_RANGE::QUICK_RANGE()
1750
:
1751
min_key(0),
1752
max_key(0),
1753
min_length(0),
1754
max_length(0),
1755
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1756
min_keypart_map(0),
1757
max_keypart_map(0)
1758
{}
1759
1760
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1761
{
1762
type=arg.type;
1763
min_flag=arg.min_flag;
1764
max_flag=arg.max_flag;
1765
maybe_flag=arg.maybe_flag;
1766
maybe_null=arg.maybe_null;
1767
part=arg.part;
1768
field=arg.field;
1769
min_value=arg.min_value;
1770
max_value=arg.max_value;
1771
next_key_part=arg.next_key_part;
1772
use_count=1; elements=1;
1773
}
1774
1775
1776
inline void SEL_ARG::make_root()
1777
{
1778
left=right= &null_element;
1779
color=BLACK;
1780
next=prev=0;
1781
use_count=0; elements=1;
1782
}
1783
1784
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1785
const unsigned char *max_value_arg)
1786
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1787
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1788
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1789
next_key_part(0),color(BLACK),type(KEY_RANGE)
1790
{
1791
left=right= &null_element;
1792
}
1793
1794
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1795
unsigned char *min_value_, unsigned char *max_value_,
1796
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1797
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1798
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1799
field(field_), min_value(min_value_), max_value(max_value_),
1800
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1801
{
1802
left=right= &null_element;
1803
}
1804
1805
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1806
SEL_ARG **next_arg)
1807
{
1808
SEL_ARG *tmp;
1809
1810
/* Bail out if we have already generated too many SEL_ARGs */
1811
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1812
return 0;
1813
1814
if (type != KEY_RANGE)
1815
{
1816
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1817
return 0; // out of memory
1818
tmp->prev= *next_arg; // Link into next/prev chain
1819
(*next_arg)->next=tmp;
1820
(*next_arg)= tmp;
1821
}
1822
else
1823
{
1824
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1825
min_flag, max_flag, maybe_flag)))
1826
return 0; // OOM
1827
tmp->parent=new_parent;
1828
tmp->next_key_part=next_key_part;
1829
if (left != &null_element)
1830
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1831
return 0; // OOM
1832
1833
tmp->prev= *next_arg; // Link into next/prev chain
1834
(*next_arg)->next=tmp;
1835
(*next_arg)= tmp;
1836
1837
if (right != &null_element)
1838
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1839
return 0; // OOM
1840
}
1841
increment_use_count(1);
1842
tmp->color= color;
1843
tmp->elements= this->elements;
1844
return tmp;
1845
}
1846
1847
SEL_ARG *SEL_ARG::first()
1848
{
1849
SEL_ARG *next_arg=this;
1850
if (!next_arg->left)
1851
return 0; // MAYBE_KEY
1852
while (next_arg->left != &null_element)
1853
next_arg=next_arg->left;
1854
return next_arg;
1855
}
1856
1857
SEL_ARG *SEL_ARG::last()
1858
{
1859
SEL_ARG *next_arg=this;
1860
if (!next_arg->right)
1861
return 0; // MAYBE_KEY
1862
while (next_arg->right != &null_element)
1863
next_arg=next_arg->right;
1864
return next_arg;
1865
}
1866
1867
1868
/*
1869
Check if a compare is ok, when one takes ranges in account
1870
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1871
*/
1872
1873
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1874
uint8_t b_flag)
1875
{
1876
int cmp;
1877
/* First check if there was a compare to a min or max element */
1878
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1879
{
1880
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1881
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1882
return 0;
1883
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1884
}
1885
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1886
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1887
1888
if (field->real_maybe_null()) // If null is part of key
1889
{
1890
if (*a != *b)
1891
{
1892
return *a ? -1 : 1;
1893
}
1894
if (*a)
1895
goto end; // NULL where equal
1896
a++; b++; // Skip NULL marker
1897
}
1898
cmp=field->key_cmp(a , b);
1899
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1900
1901
// Check if the compared equal arguments was defined with open/closed range
1902
end:
1903
if (a_flag & (NEAR_MIN | NEAR_MAX))
1904
{
1905
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1906
return 0;
1907
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1908
return (a_flag & NEAR_MIN) ? 2 : -2;
1909
return (a_flag & NEAR_MIN) ? 1 : -1;
1910
}
1911
if (b_flag & (NEAR_MIN | NEAR_MAX))
1912
return (b_flag & NEAR_MIN) ? -2 : 2;
1913
return 0; // The elements where equal
1914
}
1915
1916
1917
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1918
{
1919
SEL_ARG tmp_link,*next_arg,*root;
1920
next_arg= &tmp_link;
1921
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1922
return 0;
1923
next_arg->next=0; // Fix last link
1924
tmp_link.next->prev=0; // Fix first link
1925
if (root) // If not OOM
1926
root->use_count= 0;
1927
return root;
1928
}
1929
1930
1931
978
/*
1932
979
Find the best index to retrieve first N records in given order
1933
980
1985
1032
for (ord= order; ord && partno < n_parts; ord= ord->next, partno++)
1986
1033
{
1987
1034
Item *item= order->item[0];
1988
if (!(item->type() == Item::FIELD_ITEM &&
1035
if (! (item->type() == Item::FIELD_ITEM &&
1989
1036
((Item_field*)item)->field->eq(keyinfo[partno].field)))
1990
1037
break;
1991
1038
}
1992
1039
1993
if (!ord && table->key_info[idx].key_length < match_key_len)
1040
if (! ord && table->key_info[idx].key_length < match_key_len)
1994
1041
{
1995
1042
/*
1996
1043
Ok, the ordering is compatible and this key is shorter then
2019
1066
2020
1067
2021
1068
/*
2022
Table rows retrieval plan. Range optimizer creates QUICK_SELECT_I-derived
1069
Table rows retrieval plan. Range optimizer creates QuickSelectInterface-derived
2023
1070
objects from table read plans.
2024
1071
*/
2025
1072
class TABLE_READ_PLAN
2054
1101
created quick select
2055
1102
NULL on any error.
2056
1103
*/
2057
virtual optimizer::QUICK_SELECT_I *make_quick(PARAM *param,
2058
bool retrieve_full_rows,
2059
MEM_ROOT *parent_alloc=NULL) = 0;
1104
virtual optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1105
bool retrieve_full_rows,
1106
MEM_ROOT *parent_alloc=NULL) = 0;
2060
1107
2061
1108
/* Table read plans are allocated on MEM_ROOT and are never deleted */
2062
1109
static void *operator new(size_t size, MEM_ROOT *mem_root)
2075
1122
2076
1123
2077
1124
/*
2078
Plan for a QUICK_RANGE_SELECT scan.
1125
Plan for a QuickRangeSelect scan.
2079
1126
TRP_RANGE::make_quick ignores retrieve_full_rows parameter because
2080
QUICK_RANGE_SELECT doesn't distinguish between 'index only' scans and full
1127
QuickRangeSelect doesn't distinguish between 'index only' scans and full
2081
1128
record retrieval scans.
2082
1129
*/
2083
1130
2084
1131
class TRP_RANGE : public TABLE_READ_PLAN
2085
1132
{
2086
1133
public:
2087
SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
2088
uint32_t key_idx; /* key number in PARAM::key */
1134
optimizer::SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1135
uint32_t key_idx; /* key number in Parameter::key */
2089
1136
uint32_t mrr_flags;
2090
1137
uint32_t mrr_buf_size;
2091
1138
2092
TRP_RANGE(SEL_ARG *key_arg, uint32_t idx_arg, uint32_t mrr_flags_arg)
2093
: 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)
2094
1144
{}
2095
1145
virtual ~TRP_RANGE() {} /* Remove gcc warning */
2096
1146
2097
optimizer::QUICK_SELECT_I *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1147
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param, bool, MEM_ROOT *parent_alloc)
2098
1148
{
2099
optimizer::QUICK_RANGE_SELECT *quick;
2100
if ((quick= optimizer::get_quick_select(param,
2101
key_idx,
2102
key,
2103
mrr_flags,
1149
optimizer::QuickRangeSelect *quick= NULL;
1150
if ((quick= optimizer::get_quick_select(param,
1151
key_idx,
1152
key,
1153
mrr_flags,
2104
1154
mrr_buf_size,
2105
1155
parent_alloc)))
2106
1156
{
2119
1169
public:
2120
1170
TRP_ROR_INTERSECT() {} /* Remove gcc warning */
2121
1171
virtual ~TRP_ROR_INTERSECT() {} /* Remove gcc warning */
2122
optimizer::QUICK_SELECT_I *make_quick(PARAM *param,
2123
bool retrieve_full_rows,
2124
MEM_ROOT *parent_alloc);
1172
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1173
bool retrieve_full_rows,
1174
MEM_ROOT *parent_alloc);
2125
1175
2126
1176
/* Array of pointers to ROR range scans used in this intersection */
2127
1177
struct st_ror_scan_info **first_scan;
2143
1193
public:
2144
1194
TRP_ROR_UNION() {} /* Remove gcc warning */
2145
1195
virtual ~TRP_ROR_UNION() {} /* Remove gcc warning */
2146
optimizer::QUICK_SELECT_I *make_quick(PARAM *param,
2147
bool retrieve_full_rows,
2148
MEM_ROOT *parent_alloc);
1196
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1197
bool retrieve_full_rows,
1198
MEM_ROOT *parent_alloc);
2149
1199
TABLE_READ_PLAN **first_ror; /* array of ptrs to plans for merged scans */
2150
1200
TABLE_READ_PLAN **last_ror; /* end of the above array */
2151
1201
};
2152
1202
2153
1203
2154
1204
/*
2155
Plan for QUICK_INDEX_MERGE_SELECT scan.
1205
Plan for QuickIndexMergeSelect scan.
2156
1206
QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
2157
1207
is ignored by make_quick.
2158
1208
*/
2162
1212
public:
2163
1213
TRP_INDEX_MERGE() {} /* Remove gcc warning */
2164
1214
virtual ~TRP_INDEX_MERGE() {} /* Remove gcc warning */
2165
optimizer::QUICK_SELECT_I *make_quick(PARAM *param,
2166
bool retrieve_full_rows,
2167
MEM_ROOT *parent_alloc);
1215
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1216
bool retrieve_full_rows,
1217
MEM_ROOT *parent_alloc);
2168
1218
TRP_RANGE **range_scans; /* array of ptrs to plans of merged scans */
2169
1219
TRP_RANGE **range_scans_end; /* end of the array */
2170
1220
};
2187
1237
uint32_t key_infix_len;
2188
1238
unsigned char key_infix[MAX_KEY_LENGTH];
2189
1239
SEL_TREE *range_tree; /* Represents all range predicates in the query. */
2190
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. */
2191
1241
uint32_t param_idx; /* Index of used key in param->key. */
2192
1242
/* Number of records selected by the ranges in index_tree. */
2193
1243
public:
2199
1249
uint32_t group_key_parts_arg, KEY *index_info_arg,
2200
1250
uint32_t index_arg, uint32_t key_infix_len_arg,
2201
1251
unsigned char *key_infix_arg,
2202
SEL_TREE *tree_arg, SEL_ARG *index_tree_arg,
1252
SEL_TREE *tree_arg, optimizer::SEL_ARG *index_tree_arg,
2203
1253
uint32_t param_idx_arg, ha_rows quick_prefix_records_arg)
2204
: have_min(have_min_arg), have_max(have_max_arg),
2205
min_max_arg_part(min_max_arg_part_arg),
2206
group_prefix_len(group_prefix_len_arg), used_key_parts(used_key_parts_arg),
2207
group_key_parts(group_key_parts_arg), index_info(index_info_arg),
2208
index(index_arg), key_infix_len(key_infix_len_arg), range_tree(tree_arg),
2209
index_tree(index_tree_arg), param_idx(param_idx_arg),
2210
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)
2211
1268
{
2212
1269
if (key_infix_len)
2213
1270
memcpy(this->key_infix, key_infix_arg, key_infix_len);
2214
1271
}
2215
1272
virtual ~TRP_GROUP_MIN_MAX() {} /* Remove gcc warning */
2216
1273
2217
optimizer::QUICK_SELECT_I *make_quick(PARAM *param,
2218
bool retrieve_full_rows,
2219
MEM_ROOT *parent_alloc);
1274
optimizer::QuickSelectInterface *make_quick(optimizer::Parameter *param,
1275
bool retrieve_full_rows,
1276
MEM_ROOT *parent_alloc);
2220
1277
};
2221
1278
2222
1279
2234
1291
1 Out of memory.
2235
1292
*/
2236
1293
2237
static int fill_used_fields_bitmap(PARAM *param)
1294
static int fill_used_fields_bitmap(optimizer::Parameter *param)
2238
1295
{
2239
1296
Table *table= param->table;
2240
1297
my_bitmap_map *tmp;
2267
1324
Test if a key can be used in different ranges
2268
1325
2269
1326
SYNOPSIS
2270
SQL_SELECT::test_quick_select()
1327
SqlSelect::test_quick_select()
2271
1328
session Current thread
2272
1329
keys_to_use Keys to use for range retrieval
2273
1330
prev_tables Tables assumed to be already read when the scan is
2329
1386
1 if found usable ranges and quick select has been successfully created.
2330
1387
*/
2331
1388
2332
int optimizer::SQL_SELECT::test_quick_select(Session *session,
1389
int optimizer::SqlSelect::test_quick_select(Session *session,
2333
1390
key_map keys_to_use,
2334
1391
table_map prev_tables,
2335
ha_rows limit,
1392
ha_rows limit,
2336
1393
bool force_quick_range,
2337
1394
bool ordered_output)
2338
1395
{
2363
1420
SEL_TREE *tree= NULL;
2364
1421
KEY_PART *key_parts;
2365
1422
KEY *key_info;
2366
PARAM param;
1423
optimizer::Parameter param;
2367
1424
2368
1425
if (check_stack_overrun(session, 2*STACK_MIN_SIZE, NULL))
2369
1426
return 0; // Fatal error flag is set
2553
1610
if (best_trp)
2554
1611
{
2555
1612
records= best_trp->records;
2556
if (!(quick= best_trp->make_quick(¶m, true)) || quick->init())
1613
if (! (quick= best_trp->make_quick(¶m, true)) || quick->init())
2557
1614
{
2558
1615
delete quick;
2559
1616
quick= NULL;
2639
1696
*/
2640
1697
2641
1698
static
2642
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
1699
TABLE_READ_PLAN *get_best_disjunct_quick(optimizer::Parameter *param,
1700
SEL_IMERGE *imerge,
2643
1701
double read_time)
2644
1702
{
2645
1703
SEL_TREE **ptree;
2682
1740
One of index scans in this index_merge is more expensive than entire
2683
1741
table read for another available option. The entire index_merge (and
2684
1742
any possible ROR-union) will be more expensive then, too. We continue
2685
here only to update SQL_SELECT members.
1743
here only to update SqlSelect members.
2686
1744
*/
2687
1745
imerge_too_expensive= true;
2688
1746
}
2721
1779
{
2722
1780
/*
2723
1781
Add one ROWID comparison for each row retrieved on non-CPK scan. (it
2724
is done in QUICK_RANGE_SELECT::row_in_ranges)
1782
is done in QuickRangeSelect::row_in_ranges)
2725
1783
*/
2726
1784
imerge_cost += non_cpk_scan_records / TIME_FOR_COMPARE_ROWID;
2727
1785
}
2878
1936
ha_rows records; /* estimate of # records this scan will return */
2879
1937
2880
1938
/* Set of intervals over key fields that will be used for row retrieval. */
2881
SEL_ARG *sel_arg;
1939
optimizer::SEL_ARG *sel_arg;
2882
1940
2883
1941
/* Fields used in the query and covered by this ROR scan. */
2884
1942
MyBitmap covered_fields;
2911
1969
*/
2912
1970
2913
1971
static
2914
ROR_SCAN_INFO *make_ror_scan(const PARAM *param, int idx, SEL_ARG *sel_arg)
1972
ROR_SCAN_INFO *make_ror_scan(const optimizer::Parameter *param, int idx, optimizer::SEL_ARG *sel_arg)
2915
1973
{
2916
1974
ROR_SCAN_INFO *ror_scan;
2917
1975
my_bitmap_map *bitmap_buf;
3011
2069
/* Auxiliary structure for incremental ROR-intersection creation */
3012
2070
typedef struct
3013
2071
{
3014
const PARAM *param;
2072
const optimizer::Parameter *param;
3015
2073
MyBitmap covered_fields; /* union of fields covered by all scans */
3016
2074
/*
3017
2075
Fraction of table records that satisfies conditions of all scans.
3041
2099
*/
3042
2100
3043
2101
static
3044
ROR_INTERSECT_INFO* ror_intersect_init(const PARAM *param)
2102
ROR_INTERSECT_INFO* ror_intersect_init(const optimizer::Parameter *param)
3045
2103
{
3046
2104
ROR_INTERSECT_INFO *info;
3047
2105
my_bitmap_map* buf;
3172
2230
KEY_PART_INFO *key_part= info->param->table->key_info[scan->keynr].key_part;
3173
2231
unsigned char key_val[MAX_KEY_LENGTH+MAX_FIELD_WIDTH]; /* key values tuple */
3174
2232
unsigned char *key_ptr= key_val;
3175
SEL_ARG *sel_arg, *tuple_arg= NULL;
2233
optimizer::SEL_ARG *sel_arg= NULL;
2234
optimizer::SEL_ARG *tuple_arg= NULL;
3176
2235
key_part_map keypart_map= 0;
3177
2236
bool cur_covered;
3178
2237
bool prev_covered= test(info->covered_fields.isBitSet(key_part->fieldnr-1));
3187
2246
for (sel_arg= scan->sel_arg; sel_arg;
3188
2247
sel_arg= sel_arg->next_key_part)
3189
2248
{
3190
cur_covered=
2249
cur_covered=
3191
2250
test(info->covered_fields.isBitSet(key_part[sel_arg->part].fieldnr-1));
3192
2251
if (cur_covered != prev_covered)
3193
2252
{
3387
2446
*/
3388
2447
3389
2448
static
3390
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param,
3391
SEL_TREE *tree,
3392
double read_time,
3393
bool *are_all_covering)
2449
TRP_ROR_INTERSECT *get_best_ror_intersect(const optimizer::Parameter *param,
2450
SEL_TREE *tree,
2451
double read_time,
2452
bool *are_all_covering)
3394
2453
{
3395
2454
uint32_t idx;
3396
2455
double min_cost= DBL_MAX;
3573
2632
*/
3574
2633
3575
2634
static
3576
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
3577
SEL_TREE *tree,
3578
double read_time)
2635
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(optimizer::Parameter *param,
2636
SEL_TREE *tree,
2637
double read_time)
3579
2638
{
3580
2639
ROR_SCAN_INFO **ror_scan_mark;
3581
2640
ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
3711
2770
NULL if no plan found or error occurred
3712
2771
*/
3713
2772
3714
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
2773
static TRP_RANGE *get_key_scans_params(optimizer::Parameter *param,
2774
SEL_TREE *tree,
3715
2775
bool index_read_must_be_used,
3716
2776
bool update_tbl_stats,
3717
2777
double read_time)
3718
2778
{
3719
2779
uint32_t idx;
3720
SEL_ARG **key,**end, **key_to_read= NULL;
2780
optimizer::SEL_ARG **key,**end, **key_to_read= NULL;
3721
2781
ha_rows best_records= 0;
3722
2782
uint32_t best_mrr_flags= 0, best_buf_size= 0;
3723
2783
TRP_RANGE* read_plan= NULL;
3738
2798
double found_read_time= 0.0;
3739
2799
uint32_t mrr_flags, buf_size;
3740
2800
uint32_t keynr= param->real_keynr[idx];
3741
if ((*key)->type == SEL_ARG::MAYBE_KEY ||
2801
if ((*key)->type == optimizer::SEL_ARG::MAYBE_KEY ||
3742
2802
(*key)->maybe_flag)
3743
2803
param->needed_reg->set(keynr);
3744
2804
3783
2843
}
3784
2844
3785
2845
3786
optimizer::QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
2846
optimizer::QuickSelectInterface *TRP_INDEX_MERGE::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *)
3787
2847
{
3788
optimizer::QUICK_INDEX_MERGE_SELECT *quick_imerge;
3789
optimizer::QUICK_RANGE_SELECT *quick;
2848
optimizer::QuickIndexMergeSelect *quick_imerge;
2849
optimizer::QuickRangeSelect *quick= NULL;
3790
2850
/* index_merge always retrieves full rows, ignore retrieve_full_rows */
3791
if (! (quick_imerge= new optimizer::QUICK_INDEX_MERGE_SELECT(param->session, param->table)))
2851
if (! (quick_imerge= new optimizer::QuickIndexMergeSelect(param->session, param->table)))
3792
2852
{
3793
2853
return NULL;
3794
2854
}
3798
2858
for (TRP_RANGE **range_scan= range_scans; range_scan != range_scans_end;
3799
2859
range_scan++)
3800
2860
{
3801
if (!(quick= (optimizer::QUICK_RANGE_SELECT*)
2861
if (!(quick= (optimizer::QuickRangeSelect*)
3802
2862
((*range_scan)->make_quick(param, false, &quick_imerge->alloc)))||
3803
2863
quick_imerge->push_quick_back(quick))
3804
2864
{
3810
2870
return quick_imerge;
3811
2871
}
3812
2872
3813
optimizer::QUICK_SELECT_I *TRP_ROR_INTERSECT::make_quick(PARAM *param,
2873
optimizer::QuickSelectInterface *TRP_ROR_INTERSECT::make_quick(optimizer::Parameter *param,
3814
2874
bool retrieve_full_rows,
3815
2875
MEM_ROOT *parent_alloc)
3816
2876
{
3817
optimizer::QUICK_ROR_INTERSECT_SELECT *quick_intrsect= NULL;
3818
optimizer::QUICK_RANGE_SELECT *quick= NULL;
2877
optimizer::QUICK_ROR_INTERSECT_SELECT *quick_intersect= NULL;
2878
optimizer::QuickRangeSelect *quick= NULL;
3819
2879
MEM_ROOT *alloc= NULL;
3820
2880
3821
if ((quick_intrsect=
3822
new optimizer::QUICK_ROR_INTERSECT_SELECT(param->session, param->table,
3823
(retrieve_full_rows? (!is_covering) :
3824
false),
2881
if ((quick_intersect=
2882
new optimizer::QUICK_ROR_INTERSECT_SELECT(param->session,
2883
param->table,
2884
(retrieve_full_rows? (! is_covering) : false),
3825
2885
parent_alloc)))
3826
2886
{
3827
2887
print_ror_scans_arr(param->table,
3828
"creating ROR-intersect",
3829
first_scan, last_scan);
3830
alloc= parent_alloc? parent_alloc: &quick_intrsect->alloc;
3831
for (; first_scan != last_scan;++first_scan)
2888
"creating ROR-intersect",
2889
first_scan,
2890
last_scan);
2891
alloc= parent_alloc ? parent_alloc : &quick_intersect->alloc;
2892
for (; first_scan != last_scan; ++first_scan)
3832
2893
{
3833
if (! (quick= optimizer::get_quick_select(param,
2894
if (! (quick= optimizer::get_quick_select(param,
3834
2895
(*first_scan)->idx,
3835
2896
(*first_scan)->sel_arg,
3836
2897
HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
3837
0,
2898
0,
3838
2899
alloc)) ||
3839
quick_intrsect->push_quick_back(quick))
2900
quick_intersect->push_quick_back(quick))
3840
2901
{
3841
delete quick_intrsect;
2902
delete quick_intersect;
3842
2903
return NULL;
3843
2904
}
3844
2905
}
3845
2906
if (cpk_scan)
3846
2907
{
3847
if (! (quick= optimizer::get_quick_select(param,
2908
if (! (quick= optimizer::get_quick_select(param,
3848
2909
cpk_scan->idx,
3849
2910
cpk_scan->sel_arg,
3850
2911
HA_MRR_USE_DEFAULT_IMPL | HA_MRR_SORTED,
3851
0,
2912
0,
3852
2913
alloc)))
3853
2914
{
3854
delete quick_intrsect;
2915
delete quick_intersect;
3855
2916
return NULL;
3856
2917
}
3857
2918
quick->resetCursor();
3858
quick_intrsect->cpk_quick= quick;
2919
quick_intersect->cpk_quick= quick;
3859
2920
}
3860
quick_intrsect->records= records;
3861
quick_intrsect->read_time= read_cost;
2921
quick_intersect->records= records;
2922
quick_intersect->read_time= read_cost;
3862
2923
}
3863
return quick_intrsect;
2924
return quick_intersect;
3864
2925
}
3865
2926
3866
2927
3867
optimizer::QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
2928
optimizer::QuickSelectInterface *TRP_ROR_UNION::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *)
3868
2929
{
3869
2930
optimizer::QUICK_ROR_UNION_SELECT *quick_roru;
3870
2931
TABLE_READ_PLAN **scan;
3871
optimizer::QUICK_SELECT_I *quick;
2932
optimizer::QuickSelectInterface *quick;
3872
2933
/*
3873
2934
It is impossible to construct a ROR-union that will not retrieve full
3874
2935
rows, ignore retrieve_full_rows parameter.
3895
2956
3896
2957
SYNOPSIS
3897
2958
get_ne_mm_tree()
3898
param PARAM from SQL_SELECT::test_quick_select
2959
param Parameter from SqlSelect::test_quick_select
3899
2960
cond_func item for the predicate
3900
2961
field field in the predicate
3901
2962
lt_value constant that field should be smaller
3907
2968
0 on error
3908
2969
*/
3909
2970
3910
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
2971
static SEL_TREE *get_ne_mm_tree(optimizer::RangeParameter *param,
2972
Item_func *cond_func,
3911
2973
Field *field,
3912
2974
Item *lt_value, Item *gt_value,
3913
2975
Item_result cmp_type)
3917
2979
lt_value, cmp_type);
3918
2980
if (tree)
3919
2981
{
3920
tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3921
Item_func::GT_FUNC,
3922
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));
3923
2988
}
3924
2989
return tree;
3925
2990
}
3930
2995
3931
2996
SYNOPSIS
3932
2997
get_func_mm_tree()
3933
param PARAM from SQL_SELECT::test_quick_select
2998
param Parameter from SqlSelect::test_quick_select
3934
2999
cond_func item for the predicate
3935
3000
field field in the predicate
3936
3001
value constant in the predicate
3942
3007
Pointer to the tree built tree
3943
3008
*/
3944
3009
3945
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3010
static SEL_TREE *get_func_mm_tree(optimizer::RangeParameter *param,
3011
Item_func *cond_func,
3946
3012
Field *field, Item *value,
3947
3013
Item_result cmp_type, bool inv)
3948
3014
{
4082
3148
/* Change all intervals to be "c_{i-1} < X < c_i" */
4083
3149
for (uint32_t idx= 0; idx < param->keys; idx++)
4084
3150
{
4085
SEL_ARG *new_interval, *last_val;
3151
optimizer::SEL_ARG *new_interval, *last_val;
4086
3152
if (((new_interval= tree2->keys[idx])) &&
4087
3153
(tree->keys[idx]) &&
4088
3154
((last_val= tree->keys[idx]->last())))
4170
3236
4171
3237
SYNOPSIS
4172
3238
get_full_func_mm_tree()
4173
param PARAM from SQL_SELECT::test_quick_select
3239
param Parameter from SqlSelect::test_quick_select
4174
3240
cond_func item for the predicate
4175
3241
field_item field in the predicate
4176
3242
value constant in the predicate
4235
3301
Pointer to the tree representing the built conjunction of SEL_TREEs
4236
3302
*/
4237
3303
4238
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
3304
static SEL_TREE *get_full_func_mm_tree(optimizer::RangeParameter *param,
4239
3305
Item_func *cond_func,
4240
3306
Item_field *field_item, Item *value,
4241
3307
bool inv)
4283
3349
4284
3350
/* make a select tree of all keys in condition */
4285
3351
4286
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond)
3352
static SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond)
4287
3353
{
4288
3354
SEL_TREE *tree=0;
4289
3355
SEL_TREE *ftree= 0;
4301
3367
Item *item;
4302
3368
while ((item=li++))
4303
3369
{
4304
SEL_TREE *new_tree=get_mm_tree(param,item);
3370
SEL_TREE *new_tree= get_mm_tree(param,item);
4305
3371
if (param->session->is_fatal_error ||
4306
param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
3372
param->alloced_sel_args > optimizer::SEL_ARG::MAX_SEL_ARGS)
4307
3373
return 0; // out of memory
4308
3374
tree=tree_and(param,tree,new_tree);
4309
3375
if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4312
3378
}
4313
3379
else
4314
3380
{ // COND OR
4315
tree=get_mm_tree(param,li++);
3381
tree= get_mm_tree(param,li++);
4316
3382
if (tree)
4317
3383
{
4318
3384
Item *item;
4319
3385
while ((item=li++))
4320
3386
{
4321
SEL_TREE *new_tree=get_mm_tree(param,item);
3387
SEL_TREE *new_tree= get_mm_tree(param,item);
4322
3388
if (!new_tree)
4323
3389
return 0; // out of memory
4324
3390
tree=tree_or(param,tree,new_tree);
4455
3521
4456
3522
4457
3523
static SEL_TREE *
4458
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4459
Item_func::Functype type,
4460
Item *value, Item_result)
3524
get_mm_parts(optimizer::RangeParameter *param,
3525
COND *cond_func,
3526
Field *field,
3527
Item_func::Functype type,
3528
Item *value, Item_result)
4461
3529
{
4462
3530
if (field->table != param->table)
4463
3531
return 0;
4468
3536
if (value &&
4469
3537
value->used_tables() & ~(param->prev_tables | param->read_tables))
4470
3538
return 0;
4471
for (; key_part != end ; key_part++)
3539
for (; key_part != end; key_part++)
4472
3540
{
4473
3541
if (field->eq(key_part->field))
4474
3542
{
4475
SEL_ARG *sel_arg=0;
3543
optimizer::SEL_ARG *sel_arg=0;
4476
3544
if (!tree && !(tree=new SEL_TREE()))
4477
return 0; // OOM
3545
return 0; // OOM
4478
3546
if (!value || !(value->used_tables() & ~param->read_tables))
4479
3547
{
4480
sel_arg=get_mm_leaf(param,cond_func,
4481
key_part->field,key_part,type,value);
4482
if (!sel_arg)
4483
continue;
4484
if (sel_arg->type == SEL_ARG::IMPOSSIBLE)
4485
{
4486
tree->type=SEL_TREE::IMPOSSIBLE;
4487
return(tree);
4488
}
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
}
4489
3557
}
4490
3558
else
4491
3559
{
4492
// This key may be used later
4493
if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4494
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
4495
3563
}
4496
3564
sel_arg->part=(unsigned char) key_part->part;
4497
3565
tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4499
3567
}
4500
3568
}
4501
3569
4502
return(tree);
3570
return tree;
4503
3571
}
4504
3572
4505
3573
4506
static SEL_ARG *
4507
get_mm_leaf(RANGE_OPT_PARAM *param, COND *conf_func, Field *field,
4508
KEY_PART *key_part, Item_func::Functype type,Item *value)
3574
static optimizer::SEL_ARG *
3575
get_mm_leaf(optimizer::RangeParameter *param,
3576
COND *conf_func,
3577
Field *field,
3578
KEY_PART *key_part,
3579
Item_func::Functype type,
3580
Item *value)
4509
3581
{
4510
3582
uint32_t maybe_null=(uint32_t) field->real_maybe_null();
4511
3583
bool optimize_range;
4512
SEL_ARG *tree= 0;
3584
optimizer::SEL_ARG *tree= NULL;
4513
3585
MEM_ROOT *alloc= param->mem_root;
4514
3586
unsigned char *str;
4515
3587
int err= 0;
4530
3602
if (!maybe_null) // Not null field
4531
3603
{
4532
3604
if (type == Item_func::ISNULL_FUNC)
4533
tree= &null_element;
3605
tree= &optimizer::null_element;
4534
3606
goto end;
4535
3607
}
4536
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)))
4537
3609
goto end; // out of memory
4538
3610
if (type == Item_func::ISNOTNULL_FUNC)
4539
3611
{
4580
3652
goto end;
4581
3653
if (!(res= value->val_str(&tmp)))
4582
3654
{
4583
tree= &null_element;
3655
tree= &optimizer::null_element;
4584
3656
goto end;
4585
3657
}
4586
3658
4646
3718
int2store(min_str+maybe_null,min_length);
4647
3719
int2store(max_str+maybe_null,max_length);
4648
3720
}
4649
tree= new (alloc) SEL_ARG(field, min_str, max_str);
3721
tree= new (alloc) optimizer::SEL_ARG(field, min_str, max_str);
4650
3722
goto end;
4651
3723
}
4652
3724
4653
if (!optimize_range &&
3725
if (! optimize_range &&
4654
3726
type != Item_func::EQ_FUNC &&
4655
3727
type != Item_func::EQUAL_FUNC)
4656
3728
goto end; // Can't optimize this
4670
3742
* OK, so previously, and in MySQL, what the optimizer does here is
4671
3743
* override the sql_mode variable to ignore out-of-range or bad date-
4672
3744
* time values. It does this because the optimizer is populating the
4673
* field variable with the incoming value from the comparison field,
3745
* field variable with the incoming value from the comparison field,
4674
3746
* and the value may exceed the bounds of a proper column type.
4675
3747
*
4676
3748
* For instance, assume the following:
4677
3749
*
4678
* CREATE TABLE t1 (ts TIMESTAMP);
3750
* CREATE TABLE t1 (ts TIMESTAMP);
4679
3751
* INSERT INTO t1 ('2009-03-04 00:00:00');
4680
* CREATE TABLE t2 (dt1 DATETIME, dt2 DATETIME);
3752
* CREATE TABLE t2 (dt1 DATETIME, dt2 DATETIME);
4681
3753
* INSERT INT t2 ('2003-12-31 00:00:00','2999-12-31 00:00:00');
4682
3754
*
4683
3755
* If we issue this query:
4690
3762
* but Drizzle always throws errors on bad data storage in a Field class.
4691
3763
*
4692
3764
* Therefore, to get around the problem of the Field class being used for
4693
* "storage" here without actually storing anything...we must check to see
3765
* "storage" here without actually storing anything...we must check to see
4694
3766
* if the value being stored in a Field_timestamp here is out of range. If
4695
3767
* it is, then we must convert to the highest Timestamp value (or lowest,
4696
3768
* depending on whether the datetime is before or after the epoch.
4697
3769
*/
4698
3770
if (field->type() == DRIZZLE_TYPE_TIMESTAMP)
4699
3771
{
4700
/*
4701
* The left-side of the range comparison is a timestamp field. Therefore,
3772
/*
3773
* The left-side of the range comparison is a timestamp field. Therefore,
4702
3774
* we must check to see if the value in the right-hand side is outside the
4703
3775
* range of the UNIX epoch, and cut to the epoch bounds if it is.
4704
3776
*/
4714
3786
goto end;
4715
3787
else
4716
3788
{
4717
/*
3789
/*
4718
3790
* Create a datetime from the string and compare to fixed timestamp
4719
3791
* instances representing the epoch boundaries.
4720
3792
*/
4732
3804
/* We rely on Temporal class operator overloads to do our comparisons. */
4733
3805
if (value_datetime < min_timestamp)
4734
3806
{
4735
/*
3807
/*
4736
3808
* Datetime in right-hand side column is before UNIX epoch, so adjust to
4737
3809
* lower bound.
4738
3810
*/
4780
3852
value->result_type() == item_cmp_type(field->result_type(),
4781
3853
value->result_type()))
4782
3854
{
4783
tree= new (alloc) SEL_ARG(field, 0, 0);
4784
tree->type= SEL_ARG::IMPOSSIBLE;
3855
tree= new (alloc) optimizer::SEL_ARG(field, 0, 0);
3856
tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
4785
3857
goto end;
4786
3858
}
4787
3859
else
4838
3910
else if (err < 0)
4839
3911
{
4840
3912
/* This happens when we try to insert a NULL field in a not null column */
4841
tree= &null_element; // cmp with NULL is never true
3913
tree= &optimizer::null_element; // cmp with NULL is never true
4842
3914
goto end;
4843
3915
}
4844
3916
str= (unsigned char*) alloc_root(alloc, key_part->store_length+1);
4847
3919
if (maybe_null)
4848
3920
*str= (unsigned char) field->is_real_null(); // Set to 1 if null
4849
3921
field->get_key_image(str+maybe_null, key_part->length);
4850
if (!(tree= new (alloc) SEL_ARG(field, str, str)))
4851
goto end; // out of memory
3922
if (! (tree= new (alloc) optimizer::SEL_ARG(field, str, str)))
3923
goto end; // out of memory
4852
3924
4853
3925
/*
4854
3926
Check if we are comparing an UNSIGNED integer with a negative constant.
4870
3942
{
4871
3943
if (type == Item_func::LT_FUNC || type == Item_func::LE_FUNC)
4872
3944
{
4873
tree->type= SEL_ARG::IMPOSSIBLE;
3945
tree->type= optimizer::SEL_ARG::IMPOSSIBLE;
4874
3946
goto end;
4875
3947
}
4876
3948
if (type == Item_func::GT_FUNC || type == Item_func::GE_FUNC)
4931
4003
This will never be called for same key parts.
4932
4004
*/
4933
4005
4934
static SEL_ARG *
4935
sel_add(SEL_ARG *key1,SEL_ARG *key2)
4006
static optimizer::SEL_ARG *
4007
sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
4936
4008
{
4937
SEL_ARG *root,**key_link;
4009
optimizer::SEL_ARG *root= NULL;
4010
optimizer::SEL_ARG **key_link= NULL;
4938
4011
4939
4012
if (!key1)
4940
4013
return key2;
4967
4040
4968
4041
4969
4042
static SEL_TREE *
4970
tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4043
tree_and(optimizer::RangeParameter *param, SEL_TREE *tree1, SEL_TREE *tree2)
4971
4044
{
4972
4045
if (!tree1)
4973
4046
return(tree2);
4992
4065
result_keys.reset();
4993
4066
4994
4067
/* Join the trees key per key */
4995
SEL_ARG **key1,**key2,**end;
4068
optimizer::SEL_ARG **key1,**key2,**end;
4996
4069
for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
4997
4070
key1 != end ; key1++,key2++)
4998
4071
{
5000
4073
if (*key1 || *key2)
5001
4074
{
5002
4075
if (*key1 && !(*key1)->simple_key())
5003
flag|=CLONE_KEY1_MAYBE;
4076
flag|=CLONE_KEY1_MAYBE;
5004
4077
if (*key2 && !(*key2)->simple_key())
5005
flag|=CLONE_KEY2_MAYBE;
4078
flag|=CLONE_KEY2_MAYBE;
5006
4079
*key1=key_and(param, *key1, *key2, flag);
5007
if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
4080
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
5008
4081
{
5009
tree1->type= SEL_TREE::IMPOSSIBLE;
4082
tree1->type= SEL_TREE::IMPOSSIBLE;
5010
4083
return(tree1);
5011
4084
}
5012
4085
result_keys.set(key1 - tree1->keys);
5013
#ifdef EXTRA_DEBUG
5014
if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
5015
(*key1)->test_use_count(*key1);
5016
#endif
5017
4086
}
5018
4087
}
5019
4088
tree1->keys_map= result_keys;
5037
4106
*/
5038
4107
5039
4108
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
5040
RANGE_OPT_PARAM* param)
4109
optimizer::RangeParameter* param)
5041
4110
{
5042
4111
key_map common_keys= tree1->keys_map;
5043
4112
common_keys&= tree2->keys_map;
5046
4115
return false;
5047
4116
5048
4117
/* trees have a common key, check if they refer to same key part */
5049
SEL_ARG **key1,**key2;
4118
optimizer::SEL_ARG **key1,**key2;
5050
4119
for (uint32_t key_no=0; key_no < param->keys; key_no++)
5051
4120
{
5052
4121
if (common_keys.test(key_no))
5118
4187
1 No tree->keys[] left.
5119
4188
*/
5120
4189
5121
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree)
4190
static bool remove_nonrange_trees(optimizer::RangeParameter *param, SEL_TREE *tree)
5122
4191
{
5123
4192
bool res= false;
5124
4193
for (uint32_t i=0; i < param->keys; i++)
5139
4208
5140
4209
5141
4210
static SEL_TREE *
5142
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4211
tree_or(optimizer::RangeParameter *param,SEL_TREE *tree1,SEL_TREE *tree2)
5143
4212
{
5144
4213
if (!tree1 || !tree2)
5145
4214
return 0;
5158
4227
if (sel_trees_can_be_ored(tree1, tree2, param))
5159
4228
{
5160
4229
/* Join the trees key per key */
5161
SEL_ARG **key1,**key2,**end;
4230
optimizer::SEL_ARG **key1,**key2,**end;
5162
4231
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
5163
4232
key1 != end ; key1++,key2++)
5164
4233
{
5167
4236
{
5168
4237
result=tree1; // Added to tree1
5169
4238
result_keys.set(key1 - tree1->keys);
5170
#ifdef EXTRA_DEBUG
5171
if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
5172
(*key1)->test_use_count(*key1);
5173
#endif
5174
4239
}
5175
4240
}
5176
4241
if (result)
5226
4291
5227
4292
/* And key trees where key1->part < key2 -> part */
5228
4293
5229
static SEL_ARG *
5230
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4294
static optimizer::SEL_ARG *
4295
and_all_keys(optimizer::RangeParameter *param,
4296
optimizer::SEL_ARG *key1,
4297
optimizer::SEL_ARG *key2,
5231
4298
uint32_t clone_flag)
5232
4299
{
5233
SEL_ARG *next;
4300
optimizer::SEL_ARG *next= NULL;
5234
4301
ulong use_count=key1->use_count;
5235
4302
5236
4303
if (key1->elements != 1)
5238
4305
key2->use_count+=key1->elements-1; //psergey: why we don't count that key1 has n-k-p?
5239
4306
key2->increment_use_count((int) key1->elements-1);
5240
4307
}
5241
if (key1->type == SEL_ARG::MAYBE_KEY)
4308
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5242
4309
{
5243
key1->right= key1->left= &null_element;
4310
key1->right= key1->left= &optimizer::null_element;
5244
4311
key1->next= key1->prev= 0;
5245
4312
}
5246
for (next=key1->first(); next ; next=next->next)
4313
for (next= key1->first(); next ; next=next->next)
5247
4314
{
5248
4315
if (next->next_key_part)
5249
4316
{
5250
SEL_ARG *tmp= key_and(param, next->next_key_part, key2, clone_flag);
5251
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)
5252
4319
{
5253
key1=key1->tree_delete(next);
5254
continue;
4320
key1=key1->tree_delete(next);
4321
continue;
5255
4322
}
5256
4323
next->next_key_part=tmp;
5257
4324
if (use_count)
5258
next->increment_use_count(use_count);
5259
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)
5260
4327
break;
5261
4328
}
5262
4329
else
5263
4330
next->next_key_part=key2;
5264
4331
}
5265
if (!key1)
5266
return &null_element; // Impossible ranges
4332
if (! key1)
4333
return &optimizer::null_element; // Impossible ranges
5267
4334
key1->use_count++;
5268
4335
return key1;
5269
4336
}
5284
4351
NULL if the result of AND operation is an empty interval {0}.
5285
4352
*/
5286
4353
5287
static SEL_ARG *
5288
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::RangeParameter *param,
4356
optimizer::SEL_ARG *key1,
4357
optimizer::SEL_ARG *key2,
4358
uint32_t clone_flag)
5289
4359
{
5290
if (!key1)
4360
if (! key1)
5291
4361
return key2;
5292
if (!key2)
4362
if (! key2)
5293
4363
return key1;
5294
4364
if (key1->part != key2->part)
5295
4365
{
5301
4371
// key1->part < key2->part
5302
4372
key1->use_count--;
5303
4373
if (key1->use_count > 0)
5304
if (!(key1= key1->clone_tree(param)))
5305
return 0; // OOM
4374
if (! (key1= key1->clone_tree(param)))
4375
return 0; // OOM
5306
4376
return and_all_keys(param, key1, key2, clone_flag);
5307
4377
}
5308
4378
5309
4379
if (((clone_flag & CLONE_KEY2_MAYBE) &&
5310
!(clone_flag & CLONE_KEY1_MAYBE) &&
5311
key2->type != SEL_ARG::MAYBE_KEY) ||
5312
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)
5313
4383
{ // Put simple key in key2
5314
4384
std::swap(key1, key2);
5315
clone_flag=swap_clone_flag(clone_flag);
4385
clone_flag= swap_clone_flag(clone_flag);
5316
4386
}
5317
4387
5318
4388
/* If one of the key is MAYBE_KEY then the found region may be smaller */
5319
if (key2->type == SEL_ARG::MAYBE_KEY)
4389
if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
5320
4390
{
5321
4391
if (key1->use_count > 1)
5322
4392
{
5323
4393
key1->use_count--;
5324
if (!(key1=key1->clone_tree(param)))
5325
return 0; // OOM
4394
if (! (key1=key1->clone_tree(param)))
4395
return 0; // OOM
5326
4396
key1->use_count++;
5327
4397
}
5328
if (key1->type == SEL_ARG::MAYBE_KEY)
4398
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5329
4399
{ // Both are maybe key
5330
key1->next_key_part=key_and(param, key1->next_key_part,
5331
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);
5332
4404
if (key1->next_key_part &&
5333
key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5334
return key1;
4405
key1->next_key_part->type == optimizer::SEL_ARG::IMPOSSIBLE)
4406
return key1;
5335
4407
}
5336
4408
else
5337
4409
{
5338
4410
key1->maybe_smaller();
5339
4411
if (key2->next_key_part)
5340
4412
{
5341
key1->use_count--; // Incremented in and_all_keys
5342
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);
5343
4415
}
5344
4416
key2->use_count--; // Key2 doesn't have a tree
5345
4417
}
5348
4420
5349
4421
key1->use_count--;
5350
4422
key2->use_count--;
5351
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;
5352
4426
5353
4427
while (e1 && e2)
5354
4428
{
5355
int cmp=e1->cmp_min_to_min(e2);
4429
int cmp= e1->cmp_min_to_min(e2);
5356
4430
if (cmp < 0)
5357
4431
{
5358
if (get_range(&e1,&e2,key1))
5359
continue;
4432
if (get_range(&e1, &e2, key1))
4433
continue;
5360
4434
}
5361
else if (get_range(&e2,&e1,key2))
4435
else if (get_range(&e2, &e1, key2))
5362
4436
continue;
5363
SEL_ARG *next=key_and(param, e1->next_key_part, e2->next_key_part,
5364
clone_flag);
4437
optimizer::SEL_ARG *next= key_and(param,
4438
e1->next_key_part,
4439
e2->next_key_part,
4440
clone_flag);
5365
4441
e1->increment_use_count(1);
5366
4442
e2->increment_use_count(1);
5367
if (!next || next->type != SEL_ARG::IMPOSSIBLE)
4443
if (! next || next->type != optimizer::SEL_ARG::IMPOSSIBLE)
5368
4444
{
5369
SEL_ARG *new_arg= e1->clone_and(e2);
5370
if (!new_arg)
5371
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
5372
4448
new_arg->next_key_part=next;
5373
if (!new_tree)
4449
if (! new_tree)
5374
4450
{
5375
new_tree=new_arg;
4451
new_tree=new_arg;
5376
4452
}
5377
4453
else
5378
new_tree=new_tree->insert(new_arg);
4454
new_tree=new_tree->insert(new_arg);
5379
4455
}
5380
4456
if (e1->cmp_max_to_max(e2) < 0)
5381
4457
e1=e1->next; // e1 can't overlapp next e2
5384
4460
}
5385
4461
key1->free_tree();
5386
4462
key2->free_tree();
5387
if (!new_tree)
5388
return &null_element; // Impossible range
4463
if (! new_tree)
4464
return &optimizer::null_element; // Impossible range
5389
4465
return new_tree;
5390
4466
}
5391
4467
5392
4468
5393
4469
static bool
5394
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)
5395
4471
{
5396
(*e1)=root1->find_range(*e2); // first e1->min < e2->min
4472
(*e1)= root1->find_range(*e2); // first e1->min < e2->min
5397
4473
if ((*e1)->cmp_max_to_min(*e2) < 0)
5398
4474
{
5399
if (!((*e1)=(*e1)->next))
4475
if (! ((*e1)=(*e1)->next))
5400
4476
return 1;
5401
4477
if ((*e1)->cmp_min_to_max(*e2) > 0)
5402
4478
{
5408
4484
}
5409
4485
5410
4486
5411
static SEL_ARG *
5412
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
4487
static optimizer::SEL_ARG *
4488
key_or(optimizer::RangeParameter *param, optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2)
5413
4489
{
5414
if (!key1)
4490
if (! key1)
5415
4491
{
5416
4492
if (key2)
5417
4493
{
5420
4496
}
5421
4497
return 0;
5422
4498
}
5423
if (!key2)
4499
if (! key2)
5424
4500
{
5425
4501
key1->use_count--;
5426
4502
key1->free_tree();
5437
4513
}
5438
4514
5439
4515
// If one of the key is MAYBE_KEY then the found region may be bigger
5440
if (key1->type == SEL_ARG::MAYBE_KEY)
4516
if (key1->type == optimizer::SEL_ARG::MAYBE_KEY)
5441
4517
{
5442
4518
key2->free_tree();
5443
4519
key1->use_count++;
5444
4520
return key1;
5445
4521
}
5446
if (key2->type == SEL_ARG::MAYBE_KEY)
4522
if (key2->type == optimizer::SEL_ARG::MAYBE_KEY)
5447
4523
{
5448
4524
key1->free_tree();
5449
4525
key2->use_count++;
5461
4537
}
5462
4538
5463
4539
// Add tree at key2 to tree at key1
5464
bool key2_shared=key2->use_count != 0;
5465
key1->maybe_flag|=key2->maybe_flag;
4540
bool key2_shared= key2->use_count != 0;
4541
key1->maybe_flag|= key2->maybe_flag;
5466
4542
5467
4543
for (key2=key2->first(); key2; )
5468
4544
{
5469
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
5470
4546
int cmp;
5471
4547
5472
if (!tmp)
4548
if (! tmp)
5473
4549
{
5474
tmp=key1->first(); // tmp.min > key2.min
4550
tmp=key1->first(); // tmp.min > key2.min
5475
4551
cmp= -1;
5476
4552
}
5477
4553
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5478
4554
{ // Found tmp.max < key2.min
5479
SEL_ARG *next=tmp->next;
4555
optimizer::SEL_ARG *next= tmp->next;
5480
4556
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5481
4557
{
5482
// Join near ranges like tmp.max < 0 and key2.min >= 0
5483
SEL_ARG *key2_next=key2->next;
5484
if (key2_shared)
5485
{
5486
if (!(key2=new SEL_ARG(*key2)))
5487
return 0; // out of memory
5488
key2->increment_use_count(key1->use_count+1);
5489
key2->next=key2_next; // New copy of key2
5490
}
5491
key2->copy_min(tmp);
5492
if (!(key1=key1->tree_delete(tmp)))
5493
{ // Only one key in tree
5494
key1=key2;
5495
key1->make_root();
5496
key2=key2_next;
5497
break;
5498
}
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
}
5499
4575
}
5500
if (!(tmp=next)) // tmp.min > key2.min
5501
break; // Copy rest of key2
4576
if (! (tmp= next)) // tmp.min > key2.min
4577
break; // Copy rest of key2
5502
4578
}
5503
4579
if (cmp < 0)
5504
4580
{ // tmp.min > key2.min
5505
4581
int tmp_cmp;
5506
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
5507
4583
{
5508
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5509
{ // ranges are connected
5510
tmp->copy_min_to_min(key2);
5511
key1->merge_flags(key2);
5512
if (tmp->min_flag & NO_MIN_RANGE &&
5513
tmp->max_flag & NO_MAX_RANGE)
5514
{
5515
if (key1->maybe_flag)
5516
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5517
return 0;
5518
}
5519
key2->increment_use_count(-1); // Free not used tree
5520
key2=key2->next;
5521
continue;
5522
}
5523
else
5524
{
5525
SEL_ARG *next=key2->next; // Keys are not overlapping
5526
if (key2_shared)
5527
{
5528
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5529
if (!cpy)
5530
return 0; // OOM
5531
key1=key1->insert(cpy);
5532
key2->increment_use_count(key1->use_count+1);
5533
}
5534
else
5535
key1=key1->insert(key2); // Will destroy key2_root
5536
key2=next;
5537
continue;
5538
}
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
}
5539
4615
}
5540
4616
}
5541
4617
5544
4620
{
5545
4621
if (tmp->is_same(key2))
5546
4622
{
5547
tmp->merge_flags(key2); // Copy maybe flags
5548
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
5549
4625
}
5550
4626
else
5551
4627
{
5552
SEL_ARG *last=tmp;
5553
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5554
eq_tree(last->next->next_key_part,key2->next_key_part))
5555
{
5556
SEL_ARG *save=last;
5557
last=last->next;
5558
key1=key1->tree_delete(save);
5559
}
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
}
5560
4636
last->copy_min(tmp);
5561
if (last->copy_min(key2) || last->copy_max(key2))
5562
{ // Full range
5563
key1->free_tree();
5564
for (; key2 ; key2=key2->next)
5565
key2->increment_use_count(-1); // Free not used tree
5566
if (key1->maybe_flag)
5567
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5568
return 0;
5569
}
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
}
5570
4646
}
5571
key2=key2->next;
4647
key2= key2->next;
5572
4648
continue;
5573
4649
}
5574
4650
5575
4651
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5576
4652
{ // tmp.min <= x < key2.min
5577
SEL_ARG *new_arg=tmp->clone_first(key2);
5578
if (!new_arg)
5579
return 0; // OOM
4653
optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
4654
if (! new_arg)
4655
return 0; // OOM
5580
4656
if ((new_arg->next_key_part= key1->next_key_part))
5581
new_arg->increment_use_count(key1->use_count+1);
4657
new_arg->increment_use_count(key1->use_count+1);
5582
4658
tmp->copy_min_to_min(key2);
5583
key1=key1->insert(new_arg);
4659
key1= key1->insert(new_arg);
5584
4660
}
5585
4661
5586
4662
// tmp.min >= key2.min && tmp.min <= key2.max
5587
SEL_ARG key(*key2); // Get copy we can modify
4663
optimizer::SEL_ARG key(*key2); // Get copy we can modify
5588
4664
for (;;)
5589
4665
{
5590
4666
if (tmp->cmp_min_to_min(&key) > 0)
5591
4667
{ // key.min <= x < tmp.min
5592
SEL_ARG *new_arg=key.clone_first(tmp);
5593
if (!new_arg)
5594
return 0; // OOM
5595
if ((new_arg->next_key_part=key.next_key_part))
5596
new_arg->increment_use_count(key1->use_count+1);
5597
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);
5598
4674
}
5599
4675
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5600
4676
{ // tmp.min. <= x <= tmp.max
5601
tmp->maybe_flag|= key.maybe_flag;
5602
key.increment_use_count(key1->use_count+1);
5603
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5604
if (!cmp) // Key2 is ready
5605
break;
5606
key.copy_max_to_min(tmp);
5607
if (!(tmp=tmp->next))
5608
{
5609
SEL_ARG *tmp2= new SEL_ARG(key);
5610
if (!tmp2)
5611
return 0; // OOM
5612
key1=key1->insert(tmp2);
5613
key2=key2->next;
5614
goto end;
5615
}
5616
if (tmp->cmp_min_to_max(&key) > 0)
5617
{
5618
SEL_ARG *tmp2= new SEL_ARG(key);
5619
if (!tmp2)
5620
return 0; // OOM
5621
key1=key1->insert(tmp2);
5622
break;
5623
}
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
}
5624
4700
}
5625
4701
else
5626
4702
{
5627
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5628
if (!new_arg)
5629
return 0; // OOM
5630
tmp->copy_max_to_min(&key);
5631
tmp->increment_use_count(key1->use_count+1);
5632
/* Increment key count as it may be used for next loop */
5633
key.increment_use_count(1);
5634
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5635
key1=key1->insert(new_arg);
5636
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;
5637
4713
}
5638
4714
}
5639
key2=key2->next;
4715
key2= key2->next;
5640
4716
}
5641
4717
5642
4718
end:
5643
4719
while (key2)
5644
4720
{
5645
SEL_ARG *next=key2->next;
4721
optimizer::SEL_ARG *next= key2->next;
5646
4722
if (key2_shared)
5647
4723
{
5648
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5649
if (!tmp)
5650
return 0;
4724
optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
4725
if (! tmp)
4726
return 0;
5651
4727
key2->increment_use_count(key1->use_count+1);
5652
key1=key1->insert(tmp);
4728
key1= key1->insert(tmp);
5653
4729
}
5654
4730
else
5655
key1=key1->insert(key2); // Will destroy key2_root
5656
key2=next;
4731
key1= key1->insert(key2); // Will destroy key2_root
4732
key2= next;
5657
4733
}
5658
4734
key1->use_count++;
5659
4735
return key1;
5661
4737
5662
4738
5663
4739
/* Compare if two trees are equal */
5664
5665
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
4740
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
5666
4741
{
5667
4742
if (a == b)
5668
return 1;
5669
if (!a || !b || !a->is_same(b))
5670
return 0;
5671
if (a->left != &null_element && b->left != &null_element)
5672
{
5673
if (!eq_tree(a->left,b->left))
5674
return 0;
5675
}
5676
else if (a->left != &null_element || b->left != &null_element)
5677
return 0;
5678
if (a->right != &null_element && b->right != &null_element)
5679
{
5680
if (!eq_tree(a->right,b->right))
5681
return 0;
5682
}
5683
else if (a->right != &null_element || b->right != &null_element)
5684
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
5685
4772
if (a->next_key_part != b->next_key_part)
5686
4773
{ // Sub range
5687
if (!a->next_key_part != !b->next_key_part ||
5688
!eq_tree(a->next_key_part, b->next_key_part))
5689
return 0;
5690
}
5691
return 1;
5692
}
5693
5694
5695
SEL_ARG *
5696
SEL_ARG::insert(SEL_ARG *key)
5697
{
5698
SEL_ARG *element, **par= NULL, *last_element= NULL;
5699
5700
for (element= this; element != &null_element ; )
5701
{
5702
last_element=element;
5703
if (key->cmp_min_to_min(element) > 0)
5704
{
5705
par= &element->right; element= element->right;
5706
}
5707
else
5708
{
5709
par = &element->left; element= element->left;
5710
}
5711
}
5712
*par=key;
5713
key->parent=last_element;
5714
/* Link in list */
5715
if (par == &last_element->left)
5716
{
5717
key->next=last_element;
5718
if ((key->prev=last_element->prev))
5719
key->prev->next=key;
5720
last_element->prev=key;
5721
}
5722
else
5723
{
5724
if ((key->next=last_element->next))
5725
key->next->prev=key;
5726
key->prev=last_element;
5727
last_element->next=key;
5728
}
5729
key->left=key->right= &null_element;
5730
SEL_ARG *root=rb_insert(key); // rebalance tree
5731
root->use_count=this->use_count; // copy root info
5732
root->elements= this->elements+1;
5733
root->maybe_flag=this->maybe_flag;
5734
return root;
5735
}
5736
5737
5738
/*
5739
** Find best key with min <= given key
5740
** Because the call context this should never return 0 to get_range
5741
*/
5742
5743
SEL_ARG *
5744
SEL_ARG::find_range(SEL_ARG *key)
5745
{
5746
SEL_ARG *element=this,*found=0;
5747
5748
for (;;)
5749
{
5750
if (element == &null_element)
5751
return found;
5752
int cmp=element->cmp_min_to_min(key);
5753
if (cmp == 0)
5754
return element;
5755
if (cmp < 0)
5756
{
5757
found=element;
5758
element=element->right;
5759
}
5760
else
5761
element=element->left;
5762
}
5763
}
5764
5765
5766
/*
5767
Remove a element from the tree
5768
5769
SYNOPSIS
5770
tree_delete()
5771
key Key that is to be deleted from tree (this)
5772
5773
NOTE
5774
This also frees all sub trees that is used by the element
5775
5776
RETURN
5777
root of new tree (with key deleted)
5778
*/
5779
5780
SEL_ARG *
5781
SEL_ARG::tree_delete(SEL_ARG *key)
5782
{
5783
enum leaf_color remove_color;
5784
SEL_ARG *root,*nod,**par,*fix_par;
5785
5786
root=this;
5787
this->parent= 0;
5788
5789
/* Unlink from list */
5790
if (key->prev)
5791
key->prev->next=key->next;
5792
if (key->next)
5793
key->next->prev=key->prev;
5794
key->increment_use_count(-1);
5795
if (!key->parent)
5796
par= &root;
5797
else
5798
par=key->parent_ptr();
5799
5800
if (key->left == &null_element)
5801
{
5802
*par=nod=key->right;
5803
fix_par=key->parent;
5804
if (nod != &null_element)
5805
nod->parent=fix_par;
5806
remove_color= key->color;
5807
}
5808
else if (key->right == &null_element)
5809
{
5810
*par= nod=key->left;
5811
nod->parent=fix_par=key->parent;
5812
remove_color= key->color;
5813
}
5814
else
5815
{
5816
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5817
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5818
fix_par=tmp->parent;
5819
if (nod != &null_element)
5820
nod->parent=fix_par;
5821
remove_color= tmp->color;
5822
5823
tmp->parent=key->parent; // Move node in place of key
5824
(tmp->left=key->left)->parent=tmp;
5825
if ((tmp->right=key->right) != &null_element)
5826
tmp->right->parent=tmp;
5827
tmp->color=key->color;
5828
*par=tmp;
5829
if (fix_par == key) // key->right == key->next
5830
fix_par=tmp; // new parent of nod
5831
}
5832
5833
if (root == &null_element)
5834
return 0; // Maybe root later
5835
if (remove_color == BLACK)
5836
root=rb_delete_fixup(root,nod,fix_par);
5837
#ifdef EXTRA_DEBUG
5838
test_rb_tree(root,root->parent);
5839
#endif /* EXTRA_DEBUG */
5840
5841
root->use_count=this->use_count; // Fix root counters
5842
root->elements=this->elements-1;
5843
root->maybe_flag=this->maybe_flag;
5844
return(root);
5845
}
5846
5847
5848
/* Functions to fix up the tree after insert and delete */
5849
5850
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5851
{
5852
SEL_ARG *y=leaf->right;
5853
leaf->right=y->left;
5854
if (y->left != &null_element)
5855
y->left->parent=leaf;
5856
if (!(y->parent=leaf->parent))
5857
*root=y;
5858
else
5859
*leaf->parent_ptr()=y;
5860
y->left=leaf;
5861
leaf->parent=y;
5862
}
5863
5864
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5865
{
5866
SEL_ARG *y=leaf->left;
5867
leaf->left=y->right;
5868
if (y->right != &null_element)
5869
y->right->parent=leaf;
5870
if (!(y->parent=leaf->parent))
5871
*root=y;
5872
else
5873
*leaf->parent_ptr()=y;
5874
y->right=leaf;
5875
leaf->parent=y;
5876
}
5877
5878
5879
SEL_ARG *
5880
SEL_ARG::rb_insert(SEL_ARG *leaf)
5881
{
5882
SEL_ARG *y,*par,*par2,*root;
5883
root= this; root->parent= 0;
5884
5885
leaf->color=RED;
5886
while (leaf != root && (par= leaf->parent)->color == RED)
5887
{ // This can't be root or 1 level under
5888
if (par == (par2= leaf->parent->parent)->left)
5889
{
5890
y= par2->right;
5891
if (y->color == RED)
5892
{
5893
par->color=BLACK;
5894
y->color=BLACK;
5895
leaf=par2;
5896
leaf->color=RED; /* And the loop continues */
5897
}
5898
else
5899
{
5900
if (leaf == par->right)
5901
{
5902
left_rotate(&root,leaf->parent);
5903
par=leaf; /* leaf is now parent to old leaf */
5904
}
5905
par->color=BLACK;
5906
par2->color=RED;
5907
right_rotate(&root,par2);
5908
break;
5909
}
5910
}
5911
else
5912
{
5913
y= par2->left;
5914
if (y->color == RED)
5915
{
5916
par->color=BLACK;
5917
y->color=BLACK;
5918
leaf=par2;
5919
leaf->color=RED; /* And the loop continues */
5920
}
5921
else
5922
{
5923
if (leaf == par->left)
5924
{
5925
right_rotate(&root,par);
5926
par=leaf;
5927
}
5928
par->color=BLACK;
5929
par2->color=RED;
5930
left_rotate(&root,par2);
5931
break;
5932
}
5933
}
5934
}
5935
root->color=BLACK;
5936
#ifdef EXTRA_DEBUG
5937
test_rb_tree(root,root->parent);
5938
#endif /* EXTRA_DEBUG */
5939
5940
return root;
5941
}
5942
5943
5944
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5945
{
5946
SEL_ARG *x,*w;
5947
root->parent=0;
5948
5949
x= key;
5950
while (x != root && x->color == SEL_ARG::BLACK)
5951
{
5952
if (x == par->left)
5953
{
5954
w=par->right;
5955
if (w->color == SEL_ARG::RED)
5956
{
5957
w->color=SEL_ARG::BLACK;
5958
par->color=SEL_ARG::RED;
5959
left_rotate(&root,par);
5960
w=par->right;
5961
}
5962
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5963
{
5964
w->color=SEL_ARG::RED;
5965
x=par;
5966
}
5967
else
5968
{
5969
if (w->right->color == SEL_ARG::BLACK)
5970
{
5971
w->left->color=SEL_ARG::BLACK;
5972
w->color=SEL_ARG::RED;
5973
right_rotate(&root,w);
5974
w=par->right;
5975
}
5976
w->color=par->color;
5977
par->color=SEL_ARG::BLACK;
5978
w->right->color=SEL_ARG::BLACK;
5979
left_rotate(&root,par);
5980
x=root;
5981
break;
5982
}
5983
}
5984
else
5985
{
5986
w=par->left;
5987
if (w->color == SEL_ARG::RED)
5988
{
5989
w->color=SEL_ARG::BLACK;
5990
par->color=SEL_ARG::RED;
5991
right_rotate(&root,par);
5992
w=par->left;
5993
}
5994
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5995
{
5996
w->color=SEL_ARG::RED;
5997
x=par;
5998
}
5999
else
6000
{
6001
if (w->left->color == SEL_ARG::BLACK)
6002
{
6003
w->right->color=SEL_ARG::BLACK;
6004
w->color=SEL_ARG::RED;
6005
left_rotate(&root,w);
6006
w=par->left;
6007
}
6008
w->color=par->color;
6009
par->color=SEL_ARG::BLACK;
6010
w->left->color=SEL_ARG::BLACK;
6011
right_rotate(&root,par);
6012
x=root;
6013
break;
6014
}
6015
}
6016
par=x->parent;
6017
}
6018
x->color=SEL_ARG::BLACK;
6019
return root;
6020
}
6021
6022
6023
/* Test that the properties for a red-black tree hold */
6024
6025
#ifdef EXTRA_DEBUG
6026
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
6027
{
6028
int count_l,count_r;
6029
6030
if (element == &null_element)
6031
return 0; // Found end of tree
6032
if (element->parent != parent)
6033
{
6034
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
6035
return -1;
6036
}
6037
if (element->color == SEL_ARG::RED &&
6038
(element->left->color == SEL_ARG::RED ||
6039
element->right->color == SEL_ARG::RED))
6040
{
6041
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
6042
return -1;
6043
}
6044
if (element->left == element->right && element->left != &null_element)
6045
{ // Dummy test
6046
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
6047
return -1;
6048
}
6049
count_l=test_rb_tree(element->left,element);
6050
count_r=test_rb_tree(element->right,element);
6051
if (count_l >= 0 && count_r >= 0)
6052
{
6053
if (count_l == count_r)
6054
return count_l+(element->color == SEL_ARG::BLACK);
6055
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
6056
count_l,count_r);
6057
}
6058
return -1; // Error, no more warnings
6059
}
6060
6061
6062
/*
6063
Count how many times SEL_ARG graph "root" refers to its part "key"
6064
6065
SYNOPSIS
6066
count_key_part_usage()
6067
root An RB-Root node in a SEL_ARG graph.
6068
key Another RB-Root node in that SEL_ARG graph.
6069
6070
DESCRIPTION
6071
The passed "root" node may refer to "key" node via root->next_key_part,
6072
root->next->n
6073
6074
This function counts how many times the node "key" is referred (via
6075
SEL_ARG::next_key_part) by
6076
- intervals of RB-tree pointed by "root",
6077
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
6078
intervals of RB-tree pointed by "root",
6079
- and so on.
6080
6081
Here is an example (horizontal links represent next_key_part pointers,
6082
vertical links - next/prev prev pointers):
6083
6084
+----+ $
6085
|root|-----------------+
6086
+----+ $ |
6087
| $ |
6088
| $ |
6089
+----+ +---+ $ | +---+ Here the return value
6090
| |- ... -| |---$-+--+->|key| will be 4.
6091
+----+ +---+ $ | | +---+
6092
| $ | |
6093
... $ | |
6094
| $ | |
6095
+----+ +---+ $ | |
6096
| |---| |---------+ |
6097
+----+ +---+ $ |
6098
| | $ |
6099
... +---+ $ |
6100
| |------------+
6101
+---+ $
6102
RETURN
6103
Number of links to "key" from nodes reachable from "root".
6104
*/
6105
6106
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
6107
{
6108
ulong count= 0;
6109
for (root=root->first(); root ; root=root->next)
6110
{
6111
if (root->next_key_part)
6112
{
6113
if (root->next_key_part == key)
6114
count++;
6115
if (root->next_key_part->part < key->part)
6116
count+=count_key_part_usage(root->next_key_part,key);
6117
}
6118
}
6119
return count;
6120
}
6121
6122
6123
/*
6124
Check if SEL_ARG::use_count value is correct
6125
6126
SYNOPSIS
6127
SEL_ARG::test_use_count()
6128
root The root node of the SEL_ARG graph (an RB-tree root node that
6129
has the least value of sel_arg->part in the entire graph, and
6130
thus is the "origin" of the graph)
6131
6132
DESCRIPTION
6133
Check if SEL_ARG::use_count value is correct. See the definition of
6134
use_count for what is "correct".
6135
*/
6136
6137
void SEL_ARG::test_use_count(SEL_ARG *root)
6138
{
6139
uint32_t e_count=0;
6140
if (this == root && use_count != 1)
6141
{
6142
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
6143
return;
6144
}
6145
if (this->type != SEL_ARG::KEY_RANGE)
6146
return;
6147
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
6148
{
6149
e_count++;
6150
if (pos->next_key_part)
6151
{
6152
ulong count=count_key_part_usage(root,pos->next_key_part);
6153
if (count > pos->next_key_part->use_count)
6154
{
6155
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
6156
"should be %lu", (long unsigned int)pos,
6157
pos->next_key_part->use_count, count);
6158
return;
6159
}
6160
pos->next_key_part->test_use_count(root);
6161
}
6162
}
6163
if (e_count != elements)
6164
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
6165
e_count, elements, (long unsigned int) this);
6166
}
6167
6168
#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
6169
4782
6170
4783
/****************************************************************************
6171
4784
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
6188
4801
6189
4802
/* Number of key parts */
6190
4803
uint32_t min_key_parts, max_key_parts;
6191
SEL_ARG *key_tree;
4804
optimizer::SEL_ARG *key_tree;
6192
4805
} RANGE_SEQ_ENTRY;
6193
4806
6194
4807
6199
4812
{
6200
4813
uint32_t keyno; /* index of used tree in SEL_TREE structure */
6201
4814
uint32_t real_keyno; /* Number of the index in tables */
6202
PARAM *param;
6203
SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
4815
optimizer::Parameter *param;
4816
optimizer::SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
6204
4817
6205
4818
RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
6206
4819
int i; /* Index of last used element in the above array */
6239
4852
}
6240
4853
6241
4854
6242
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)
6243
4856
{
6244
4857
RANGE_SEQ_ENTRY *cur= &arg->stack[arg->i+1];
6245
4858
RANGE_SEQ_ENTRY *prev= &arg->stack[arg->i];
6291
4904
//psergey-merge-todo: support check_quick_keys:max_keypart
6292
4905
static uint32_t sel_arg_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
6293
4906
{
6294
SEL_ARG *key_tree;
4907
optimizer::SEL_ARG *key_tree;
6295
4908
SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)rseq;
6296
4909
if (seq->at_start)
6297
4910
{
6304
4917
/* Ok, we're at some "full tuple" position in the tree */
6305
4918
6306
4919
/* Step down if we can */
6307
if (key_tree->next && key_tree->next != &null_element)
4920
if (key_tree->next && key_tree->next != &optimizer::null_element)
6308
4921
{
6309
4922
//step down; (update the tuple, we'll step right and stay there)
6310
4923
seq->i--;
6324
4937
key_tree= seq->stack[seq->i].key_tree;
6325
4938
6326
4939
/* Step down if we can */
6327
if (key_tree->next && key_tree->next != &null_element)
4940
if (key_tree->next && key_tree->next != &optimizer::null_element)
6328
4941
{
6329
4942
// Step down; update the tuple
6330
4943
seq->i--;
6339
4952
Walk right-up while we can
6340
4953
*/
6341
4954
walk_right_n_up:
6342
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 &&
6343
4956
key_tree->next_key_part->part == key_tree->part + 1 &&
6344
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
4957
key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
6345
4958
{
6346
4959
{
6347
4960
RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6348
4961
uint32_t min_key_length= cur->min_key - seq->param->min_key;
6349
4962
uint32_t max_key_length= cur->max_key - seq->param->max_key;
6350
4963
uint32_t len= cur->min_key - cur[-1].min_key;
6351
if (!(min_key_length == max_key_length &&
6352
!memcmp(cur[-1].min_key, cur[-1].max_key, len) &&
6353
!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))
6354
4967
{
6355
4968
seq->param->is_ror_scan= false;
6356
if (!key_tree->min_flag)
4969
if (! key_tree->min_flag)
6357
4970
cur->min_key_parts +=
6358
4971
key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6359
4972
&cur->min_key,
6360
4973
&cur->min_key_flag);
6361
if (!key_tree->max_flag)
4974
if (! key_tree->max_flag)
6362
4975
cur->max_key_parts +=
6363
4976
key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6364
4977
&cur->max_key,
6374
4987
key_tree= key_tree->next_key_part;
6375
4988
6376
4989
walk_up_n_right:
6377
while (key_tree->prev && key_tree->prev != &null_element)
4990
while (key_tree->prev && key_tree->prev != &optimizer::null_element)
6378
4991
{
6379
4992
/* Step up */
6380
4993
key_tree= key_tree->prev;
6439
5052
SYNOPSIS
6440
5053
check_quick_select()
6441
5054
param Parameter from test_quick_select
6442
idx Number of index to use in PARAM::key SEL_TREE::key
5055
idx Number of index to use in Parameter::key SEL_TREE::key
6443
5056
index_only true - assume only index tuples will be accessed
6444
5057
false - assume full table rows will be read
6445
5058
tree Transformed selection condition, tree->key[idx] holds
6461
5074
*/
6462
5075
6463
5076
static
6464
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
6465
SEL_ARG *tree, bool update_tbl_stats,
6466
uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
5077
ha_rows check_quick_select(optimizer::Parameter *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)
6467
5085
{
6468
5086
SEL_ARG_RANGE_SEQ seq;
6469
5087
RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next};
6472
5090
uint32_t keynr= param->real_keynr[idx];
6473
5091
6474
5092
/* Handle cases when we don't have a valid non-empty list of range */
6475
if (!tree)
5093
if (! tree)
6476
5094
return(HA_POS_ERROR);
6477
if (tree->type == SEL_ARG::IMPOSSIBLE)
5095
if (tree->type == optimizer::SEL_ARG::IMPOSSIBLE)
6478
5096
return(0L);
6479
if (tree->type != SEL_ARG::KEY_RANGE || tree->part != 0)
5097
if (tree->type != optimizer::SEL_ARG::KEY_RANGE || tree->part != 0)
6480
5098
return(HA_POS_ERROR);
6481
5099
6482
5100
seq.keyno= idx;
6577
5195
false Otherwise
6578
5196
*/
6579
5197
6580
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts)
5198
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts)
6581
5199
{
6582
5200
KEY *table_key= param->table->key_info + keynr;
6583
5201
KEY_PART_INFO *key_part= table_key->key_part + nparts;
6615
5233
}
6616
5234
6617
5235
6618
optimizer::QUICK_RANGE_SELECT *
6619
optimizer::get_quick_select(PARAM *param,
5236
optimizer::QuickRangeSelect *
5237
optimizer::get_quick_select(Parameter *param,
6620
5238
uint32_t idx,
6621
SEL_ARG *key_tree,
5239
optimizer::SEL_ARG *key_tree,
6622
5240
uint32_t mrr_flags,
6623
uint32_t mrr_buf_size,
5241
uint32_t mrr_buf_size,
6624
5242
MEM_ROOT *parent_alloc)
6625
5243
{
6626
optimizer::QUICK_RANGE_SELECT *quick= NULL;
5244
optimizer::QuickRangeSelect *quick= NULL;
6627
5245
bool create_err= false;
6628
5246
6629
quick=new optimizer::QUICK_RANGE_SELECT(param->session, param->table,
6630
param->real_keynr[idx],
6631
test(parent_alloc), NULL, &create_err);
5247
quick= new optimizer::QuickRangeSelect(param->session,
5248
param->table,
5249
param->real_keynr[idx],
5250
test(parent_alloc),
5251
NULL,
5252
&create_err);
6632
5253
6633
5254
if (quick)
6634
5255
{
6643
5264
0))
6644
5265
{
6645
5266
delete quick;
6646
quick=0;
5267
quick= NULL;
6647
5268
}
6648
5269
else
6649
5270
{
6664
5285
** Fix this to get all possible sub_ranges
6665
5286
*/
6666
5287
bool
6667
optimizer::get_quick_keys(PARAM *param,
6668
optimizer::QUICK_RANGE_SELECT *quick,
5288
optimizer::get_quick_keys(optimizer::Parameter *param,
5289
optimizer::QuickRangeSelect *quick,
6669
5290
KEY_PART *key,
6670
SEL_ARG *key_tree,
5291
optimizer::SEL_ARG *key_tree,
6671
5292
unsigned char *min_key,
6672
5293
uint32_t min_key_flag,
6673
5294
unsigned char *max_key,
6674
5295
uint32_t max_key_flag)
6675
5296
{
6676
optimizer::QUICK_RANGE *range= NULL;
5297
optimizer::QuickRange *range= NULL;
6677
5298
uint32_t flag;
6678
5299
int min_part= key_tree->part - 1; // # of keypart values in min_key buffer
6679
5300
int max_part= key_tree->part - 1; // # of keypart values in max_key buffer
6680
5301
6681
if (key_tree->left != &null_element)
5302
if (key_tree->left != &optimizer::null_element)
6682
5303
{
6683
5304
if (get_quick_keys(param,
6684
5305
quick,
6692
5313
return 1;
6693
5314
}
6694
5315
}
6695
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;
6696
5317
min_part+= key_tree->store_min(key[key_tree->part].store_length,
6697
5318
&tmp_min_key,min_key_flag);
6698
5319
max_part+= key_tree->store_max(key[key_tree->part].store_length,
6700
5321
6701
5322
if (key_tree->next_key_part &&
6702
5323
key_tree->next_key_part->part == key_tree->part+1 &&
6703
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
5324
key_tree->next_key_part->type == optimizer::SEL_ARG::KEY_RANGE)
6704
5325
{ // const key as prefix
6705
5326
if ((tmp_min_key - min_key) == (tmp_max_key - max_key) &&
6706
5327
memcmp(min_key, max_key, (uint32_t)(tmp_max_key - max_key))==0 &&
6710
5331
quick,
6711
5332
key,
6712
5333
key_tree->next_key_part,
6713
tmp_min_key,
5334
tmp_min_key,
6714
5335
min_key_flag | key_tree->min_flag,
6715
tmp_max_key,
5336
tmp_max_key,
6716
5337
max_key_flag | key_tree->max_flag))
6717
5338
{
6718
5339
return 1;
6723
5344
uint32_t tmp_min_flag=key_tree->min_flag,tmp_max_flag=key_tree->max_flag;
6724
5345
if (! tmp_min_flag)
6725
5346
{
6726
min_part+= key_tree->next_key_part->store_min_key(key,
5347
min_part+= key_tree->next_key_part->store_min_key(key,
6727
5348
&tmp_min_key,
6728
5349
&tmp_min_flag);
6729
5350
}
6730
5351
if (! tmp_max_flag)
6731
5352
{
6732
max_part+= key_tree->next_key_part->store_max_key(key,
5353
max_part+= key_tree->next_key_part->store_max_key(key,
6733
5354
&tmp_max_key,
6734
5355
&tmp_max_flag);
6735
5356
}
6788
5409
}
6789
5410
6790
5411
/* Get range for retrieving rows in QUICK_SELECT::get_next */
6791
if (! (range= new optimizer::QUICK_RANGE(param->min_key,
5412
if (! (range= new optimizer::QuickRange(param->min_key,
6792
5413
(uint32_t) (tmp_min_key - param->min_key),
6793
5414
min_part >=0 ? make_keypart_map(min_part) : 0,
6794
5415
param->max_key,
6808
5429
}
6809
5430
6810
5431
end:
6811
if (key_tree->right != &null_element)
5432
if (key_tree->right != &optimizer::null_element)
6812
5433
{
6813
5434
return get_quick_keys(param,
6814
5435
quick,
6823
5444
}
6824
5445
6825
5446
/*
6826
Return 1 if there is only one range and this uses the whole primary key
6827
*/
6828
6829
bool optimizer::QUICK_RANGE_SELECT::unique_key_range()
6830
{
6831
if (ranges.elements == 1)
6832
{
6833
optimizer::QUICK_RANGE *tmp= *((optimizer::QUICK_RANGE**)ranges.buffer);
6834
if ((tmp->flag & (EQ_RANGE | NULL_RANGE)) == EQ_RANGE)
6835
{
6836
KEY *key=head->key_info+index;
6837
return ((key->flags & (HA_NOSAME)) == HA_NOSAME &&
6838
key->key_length == tmp->min_length);
6839
}
6840
}
6841
return 0;
6842
}
6843
6844
6845
6846
/*
6847
5447
Return true if any part of the key is NULL
6848
5448
6849
5449
SYNOPSIS
6870
5470
}
6871
5471
6872
5472
6873
bool optimizer::QUICK_SELECT_I::is_keys_used(const MyBitmap *fields)
5473
bool optimizer::QuickSelectInterface::is_keys_used(const MyBitmap *fields)
6874
5474
{
6875
5475
return is_key_used(head, index, fields);
6876
5476
}
6877
5477
6878
bool optimizer::QUICK_INDEX_MERGE_SELECT::is_keys_used(const MyBitmap *fields)
6879
{
6880
optimizer::QUICK_RANGE_SELECT *quick= NULL;
6881
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
6882
while ((quick= it++))
6883
{
6884
if (is_key_used(head, quick->index, fields))
6885
return 1;
6886
}
6887
return 0;
6888
}
6889
5478
6890
5479
bool optimizer::QUICK_ROR_INTERSECT_SELECT::is_keys_used(const MyBitmap *fields)
6891
5480
{
6892
optimizer::QUICK_RANGE_SELECT *quick;
6893
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> it(quick_selects);
5481
optimizer::QuickRangeSelect *quick;
5482
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
6894
5483
while ((quick= it++))
6895
5484
{
6896
5485
if (is_key_used(head, quick->index, fields))
6901
5490
6902
5491
bool optimizer::QUICK_ROR_UNION_SELECT::is_keys_used(const MyBitmap *fields)
6903
5492
{
6904
optimizer::QUICK_SELECT_I *quick;
6905
List_iterator_fast<optimizer::QUICK_SELECT_I> it(quick_selects);
5493
optimizer::QuickSelectInterface *quick;
5494
List_iterator_fast<optimizer::QuickSelectInterface> it(quick_selects);
6906
5495
while ((quick= it++))
6907
5496
{
6908
5497
if (quick->is_keys_used(fields))
6931
5520
NULL on error.
6932
5521
*/
6933
5522
6934
optimizer::QUICK_RANGE_SELECT *optimizer::get_quick_select_for_ref(Session *session,
6935
Table *table,
6936
table_reference_st *ref,
6937
ha_rows records)
5523
optimizer::QuickRangeSelect *optimizer::get_quick_select_for_ref(Session *session,
5524
Table *table,
5525
table_reference_st *ref,
5526
ha_rows records)
6938
5527
{
6939
5528
MEM_ROOT *old_root, *alloc;
6940
optimizer::QUICK_RANGE_SELECT *quick= NULL;
5529
optimizer::QuickRangeSelect *quick= NULL;
6941
5530
KEY *key_info = &table->key_info[ref->key];
6942
5531
KEY_PART *key_part;
6943
optimizer::QUICK_RANGE *range;
5532
optimizer::QuickRange *range= NULL;
6944
5533
uint32_t part;
6945
5534
bool create_err= false;
6946
5535
COST_VECT cost;
6947
5536
6948
5537
old_root= session->mem_root;
6949
5538
/* The following call may change session->mem_root */
6950
quick= new optimizer::QUICK_RANGE_SELECT(session, table, ref->key, 0, 0, &create_err);
6951
/* save mem_root set by QUICK_RANGE_SELECT constructor */
5539
quick= new optimizer::QuickRangeSelect(session, table, ref->key, 0, 0, &create_err);
5540
/* save mem_root set by QuickRangeSelect constructor */
6952
5541
alloc= session->mem_root;
6953
5542
/*
6954
5543
return back default mem_root (session->mem_root) changed by
6955
QUICK_RANGE_SELECT constructor
5544
QuickRangeSelect constructor
6956
5545
*/
6957
5546
session->mem_root= old_root;
6958
5547
6963
5552
quick->records= records;
6964
5553
6965
5554
if ((cp_buffer_from_ref(session, ref) && session->is_fatal_error) ||
6966
!(range= new(alloc) optimizer::QUICK_RANGE()))
5555
!(range= new(alloc) optimizer::QuickRange()))
6967
5556
goto err; // out of memory
6968
5557
6969
5558
range->min_key= range->max_key= ref->key_buff;
6998
5587
*/
6999
5588
if (ref->null_ref_key)
7000
5589
{
7001
optimizer::QUICK_RANGE *null_range;
5590
optimizer::QuickRange *null_range= NULL;
7002
5591
7003
5592
*ref->null_ref_key= 1; // Set null byte then create a range
7004
5593
if (!(null_range= new (alloc)
7005
optimizer::QUICK_RANGE(ref->key_buff, ref->key_length,
5594
optimizer::QuickRange(ref->key_buff, ref->key_length,
7006
5595
make_prev_keypart_map(ref->key_parts),
7007
5596
ref->key_buff, ref->key_length,
7008
5597
make_prev_keypart_map(ref->key_parts), EQ_RANGE)))
7032
5621
7033
5622
7034
5623
/*
7035
Perform key scans for all used indexes (except CPK), get rowids and merge
7036
them into an ordered non-recurrent sequence of rowids.
7037
7038
The merge/duplicate removal is performed using Unique class. We put all
7039
rowids into Unique, get the sorted sequence and destroy the Unique.
7040
7041
If table has a clustered primary key that covers all rows (true for bdb
7042
and innodb currently) and one of the index_merge scans is a scan on PK,
7043
then rows that will be retrieved by PK scan are not put into Unique and
7044
primary key scan is not performed here, it is performed later separately.
7045
7046
RETURN
7047
0 OK
7048
other error
7049
*/
7050
7051
int optimizer::QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
7052
{
7053
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
7054
optimizer::QUICK_RANGE_SELECT* cur_quick;
7055
int result;
7056
Unique *unique;
7057
Cursor *cursor= head->cursor;
7058
7059
cursor->extra(HA_EXTRA_KEYREAD);
7060
head->prepare_for_position();
7061
7062
cur_quick_it.rewind();
7063
cur_quick= cur_quick_it++;
7064
assert(cur_quick != 0);
7065
7066
/*
7067
We reuse the same instance of Cursor so we need to call both init and
7068
reset here.
7069
*/
7070
if (cur_quick->init() || cur_quick->reset())
7071
return 0;
7072
7073
unique= new Unique(refpos_order_cmp, (void *)cursor,
7074
cursor->ref_length,
7075
session->variables.sortbuff_size);
7076
if (!unique)
7077
return 0;
7078
for (;;)
7079
{
7080
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
7081
{
7082
cur_quick->range_end();
7083
cur_quick= cur_quick_it++;
7084
if (!cur_quick)
7085
break;
7086
7087
if (cur_quick->cursor->inited != Cursor::NONE)
7088
cur_quick->cursor->ha_index_end();
7089
if (cur_quick->init() || cur_quick->reset())
7090
return 0;
7091
}
7092
7093
if (result)
7094
{
7095
if (result != HA_ERR_END_OF_FILE)
7096
{
7097
cur_quick->range_end();
7098
return result;
7099
}
7100
break;
7101
}
7102
7103
if (session->killed)
7104
return 0;
7105
7106
/* skip row if it will be retrieved by clustered PK scan */
7107
if (pk_quick_select && pk_quick_select->row_in_ranges())
7108
continue;
7109
7110
cur_quick->cursor->position(cur_quick->record);
7111
result= unique->unique_add((char*)cur_quick->cursor->ref);
7112
if (result)
7113
return 0;
7114
7115
}
7116
7117
/* ok, all row ids are in Unique */
7118
result= unique->get(head);
7119
delete unique;
7120
doing_pk_scan= false;
7121
/* index_merge currently doesn't support "using index" at all */
7122
cursor->extra(HA_EXTRA_NO_KEYREAD);
7123
/* start table scan */
7124
init_read_record(&read_record, session, head, (optimizer::SQL_SELECT*) 0, 1, 1);
7125
return result;
7126
}
7127
7128
7129
/*
7130
Get next row for index_merge.
7131
NOTES
7132
The rows are read from
7133
1. rowids stored in Unique.
7134
2. QUICK_RANGE_SELECT with clustered primary key (if any).
7135
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
7136
*/
7137
7138
int optimizer::QUICK_INDEX_MERGE_SELECT::get_next()
7139
{
7140
int result;
7141
7142
if (doing_pk_scan)
7143
return(pk_quick_select->get_next());
7144
7145
if ((result= read_record.read_record(&read_record)) == -1)
7146
{
7147
result= HA_ERR_END_OF_FILE;
7148
end_read_record(&read_record);
7149
/* All rows from Unique have been retrieved, do a clustered PK scan */
7150
if (pk_quick_select)
7151
{
7152
doing_pk_scan= true;
7153
if ((result= pk_quick_select->init()) ||
7154
(result= pk_quick_select->reset()))
7155
return result;
7156
return(pk_quick_select->get_next());
7157
}
7158
}
7159
7160
return result;
7161
}
7162
7163
7164
/*
7165
5624
Retrieve next record.
7166
5625
SYNOPSIS
7167
5626
QUICK_ROR_INTERSECT_SELECT::get_next()
7183
5642
7184
5643
int optimizer::QUICK_ROR_INTERSECT_SELECT::get_next()
7185
5644
{
7186
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> quick_it(quick_selects);
7187
optimizer::QUICK_RANGE_SELECT* quick;
5645
List_iterator_fast<optimizer::QuickRangeSelect> quick_it(quick_selects);
5646
optimizer::QuickRangeSelect* quick;
7188
5647
int error, cmp;
7189
5648
uint32_t last_rowid_count=0;
7190
5649
7269
5728
int optimizer::QUICK_ROR_UNION_SELECT::get_next()
7270
5729
{
7271
5730
int error, dup_row;
7272
optimizer::QUICK_SELECT_I *quick;
5731
optimizer::QuickSelectInterface *quick;
7273
5732
unsigned char *tmp;
7274
5733
7275
5734
do
7317
5776
}
7318
5777
7319
5778
7320
int optimizer::QUICK_RANGE_SELECT::reset()
7321
{
7322
uint32_t buf_size;
7323
unsigned char *mrange_buff;
7324
int error;
7325
HANDLER_BUFFER empty_buf;
7326
last_range= NULL;
7327
cur_range= (optimizer::QUICK_RANGE**) ranges.buffer;
7328
7329
if (cursor->inited == Cursor::NONE && (error= cursor->ha_index_init(index,1)))
7330
return(error);
7331
7332
/* Allocate buffer if we need one but haven't allocated it yet */
7333
if (mrr_buf_size && !mrr_buf_desc)
7334
{
7335
buf_size= mrr_buf_size;
7336
while (buf_size && ! memory::multi_malloc(false,
7337
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7338
&mrange_buff, buf_size,
7339
NULL))
7340
{
7341
/* Try to shrink the buffers until both are 0. */
7342
buf_size/= 2;
7343
}
7344
if (!mrr_buf_desc)
7345
return(HA_ERR_OUT_OF_MEM);
7346
7347
/* Initialize the Cursor buffer. */
7348
mrr_buf_desc->buffer= mrange_buff;
7349
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7350
mrr_buf_desc->end_of_used_area= mrange_buff;
7351
}
7352
7353
if (!mrr_buf_desc)
7354
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7355
7356
if (sorted)
7357
mrr_flags |= HA_MRR_SORTED;
7358
RANGE_SEQ_IF seq_funcs= {optimizer::quick_range_seq_init, optimizer::quick_range_seq_next};
7359
error= cursor->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7360
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7361
&empty_buf);
7362
return(error);
7363
}
7364
7365
7366
5779
/*
7367
Range sequence interface implementation for array<QUICK_RANGE>: initialize
5780
Range sequence interface implementation for array<QuickRange>: initialize
7368
5781
7369
5782
SYNOPSIS
7370
5783
quick_range_seq_init()
7371
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
5784
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7372
5785
n_ranges Number of ranges in the sequence (ignored)
7373
5786
flags MRR flags (currently not used)
7374
5787
7378
5791
7379
5792
range_seq_t optimizer::quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7380
5793
{
7381
optimizer::QUICK_RANGE_SELECT *quick= (optimizer::QUICK_RANGE_SELECT*)init_param;
7382
quick->qr_traversal_ctx.first= (optimizer::QUICK_RANGE**)quick->ranges.buffer;
7383
quick->qr_traversal_ctx.cur= (optimizer::QUICK_RANGE**)quick->ranges.buffer;
5794
optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
5795
quick->qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
5796
quick->qr_traversal_ctx.cur= (optimizer::QuickRange**)quick->ranges.buffer;
7384
5797
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
7385
5798
quick->ranges.elements;
7386
5799
return &quick->qr_traversal_ctx;
7388
5801
7389
5802
7390
5803
/*
7391
Range sequence interface implementation for array<QUICK_RANGE>: get next
5804
Range sequence interface implementation for array<QuickRange>: get next
7392
5805
7393
5806
SYNOPSIS
7394
5807
quick_range_seq_next()
7399
5812
0 Ok
7400
5813
1 No more ranges in the sequence
7401
5814
*/
7402
7403
5815
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7404
5816
{
7405
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
5817
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7406
5818
7407
5819
if (ctx->cur == ctx->last)
7408
5820
return 1; /* no more ranges */
7409
5821
7410
optimizer::QUICK_RANGE *cur= *(ctx->cur);
5822
optimizer::QuickRange *cur= *(ctx->cur);
7411
5823
key_range *start_key= &range->start_key;
7412
key_range *end_key= &range->end_key;
5824
key_range *end_key= &range->end_key;
7413
5825
7414
start_key->key= cur->min_key;
5826
start_key->key= cur->min_key;
7415
5827
start_key->length= cur->min_length;
7416
5828
start_key->keypart_map= cur->min_keypart_map;
7417
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7418
(cur->flag & EQ_RANGE) ?
7419
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7420
end_key->key= cur->max_key;
7421
end_key->length= cur->max_length;
5829
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
5830
(cur->flag & EQ_RANGE) ?
5831
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
5832
end_key->key= cur->max_key;
5833
end_key->length= cur->max_length;
7422
5834
end_key->keypart_map= cur->max_keypart_map;
7423
5835
/*
7424
5836
We use HA_READ_AFTER_KEY here because if we are reading on a key
7425
5837
prefix. We want to find all keys with this prefix.
7426
5838
*/
7427
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7428
HA_READ_AFTER_KEY);
5839
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
5840
HA_READ_AFTER_KEY);
7429
5841
range->range_flag= cur->flag;
7430
5842
ctx->cur++;
7431
5843
return 0;
7432
5844
}
7433
5845
7434
5846
7435
/*
7436
Get next possible record using quick-struct.
7437
7438
SYNOPSIS
7439
QUICK_RANGE_SELECT::get_next()
7440
7441
NOTES
7442
Record is read into table->record[0]
7443
7444
RETURN
7445
0 Found row
7446
HA_ERR_END_OF_FILE No (more) rows in range
7447
# Error code
7448
*/
7449
7450
int optimizer::QUICK_RANGE_SELECT::get_next()
7451
{
7452
char *dummy;
7453
if (in_ror_merged_scan)
7454
{
7455
/*
7456
We don't need to signal the bitmap change as the bitmap is always the
7457
same for this head->cursor
7458
*/
7459
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
7460
}
7461
7462
int result= cursor->multi_range_read_next(&dummy);
7463
7464
if (in_ror_merged_scan)
7465
{
7466
/* Restore bitmaps set on entry */
7467
head->column_bitmaps_set(save_read_set, save_write_set);
7468
}
7469
return result;
7470
}
7471
7472
7473
/*
7474
Get the next record with a different prefix.
7475
7476
SYNOPSIS
7477
QUICK_RANGE_SELECT::get_next_prefix()
7478
prefix_length length of cur_prefix
7479
cur_prefix prefix of a key to be searched for
7480
7481
DESCRIPTION
7482
Each subsequent call to the method retrieves the first record that has a
7483
prefix with length prefix_length different from cur_prefix, such that the
7484
record with the new prefix is within the ranges described by
7485
this->ranges. The record found is stored into the buffer pointed by
7486
this->record.
7487
The method is useful for GROUP-BY queries with range conditions to
7488
discover the prefix of the next group that satisfies the range conditions.
7489
7490
TODO
7491
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7492
methods should be unified into a more general one to reduce code
7493
duplication.
7494
7495
RETURN
7496
0 on success
7497
HA_ERR_END_OF_FILE if returned all keys
7498
other if some error occurred
7499
*/
7500
7501
int optimizer::QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7502
key_part_map keypart_map,
7503
unsigned char *cur_prefix)
7504
{
7505
for (;;)
7506
{
7507
int result;
7508
key_range start_key, end_key;
7509
if (last_range)
7510
{
7511
/* Read the next record in the same range with prefix after cur_prefix. */
7512
assert(cur_prefix != 0);
7513
result= cursor->index_read_map(record, cur_prefix, keypart_map,
7514
HA_READ_AFTER_KEY);
7515
if (result || (cursor->compare_key(cursor->end_range) <= 0))
7516
return result;
7517
}
7518
7519
uint32_t count= ranges.elements - (cur_range - (optimizer::QUICK_RANGE**) ranges.buffer);
7520
if (count == 0)
7521
{
7522
/* Ranges have already been used up before. None is left for read. */
7523
last_range= 0;
7524
return HA_ERR_END_OF_FILE;
7525
}
7526
last_range= *(cur_range++);
7527
7528
start_key.key= (const unsigned char*) last_range->min_key;
7529
start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
7530
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7531
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7532
(last_range->flag & EQ_RANGE) ?
7533
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7534
end_key.key= (const unsigned char*) last_range->max_key;
7535
end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
7536
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7537
/*
7538
We use READ_AFTER_KEY here because if we are reading on a key
7539
prefix we want to find all keys with this prefix
7540
*/
7541
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7542
HA_READ_AFTER_KEY);
7543
7544
result= cursor->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7545
last_range->max_keypart_map ? &end_key : 0,
7546
test(last_range->flag & EQ_RANGE),
7547
sorted);
7548
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7549
last_range= 0; // Stop searching
7550
7551
if (result != HA_ERR_END_OF_FILE)
7552
return result;
7553
last_range= 0; // No matching rows; go to next range
7554
}
7555
}
7556
7557
7558
/*
7559
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7560
7561
NOTES
7562
It is assumed that currently a scan is being done on another index
7563
which reads all necessary parts of the index that is scanned by this
7564
quick select.
7565
The implementation does a binary search on sorted array of disjoint
7566
ranges, without taking size of range into account.
7567
7568
This function is used to filter out clustered PK scan rows in
7569
index_merge quick select.
7570
7571
RETURN
7572
true if current row will be retrieved by this quick select
7573
false if not
7574
*/
7575
7576
bool optimizer::QUICK_RANGE_SELECT::row_in_ranges()
7577
{
7578
optimizer::QUICK_RANGE *res;
7579
uint32_t min= 0;
7580
uint32_t max= ranges.elements - 1;
7581
uint32_t mid= (max + min)/2;
7582
7583
while (min != max)
7584
{
7585
if (cmp_next(*(optimizer::QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7586
{
7587
/* current row value > mid->max */
7588
min= mid + 1;
7589
}
7590
else
7591
max= mid;
7592
mid= (min + max) / 2;
7593
}
7594
res= *(optimizer::QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7595
return (!cmp_next(res) && !cmp_prev(res));
7596
}
7597
7598
/*
7599
This is a hack: we inherit from QUICK_SELECT so that we can use the
7600
get_next() interface, but we have to hold a pointer to the original
7601
QUICK_SELECT because its data are used all over the place. What
7602
should be done is to factor out the data that is needed into a base
7603
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7604
which handle the ranges and implement the get_next() function. But
7605
for now, this seems to work right at least.
7606
*/
7607
7608
optimizer::QUICK_SELECT_DESC::QUICK_SELECT_DESC(optimizer::QUICK_RANGE_SELECT *q, uint32_t, bool *)
7609
:
7610
optimizer::QUICK_RANGE_SELECT(*q),
7611
rev_it(rev_ranges)
7612
{
7613
optimizer::QUICK_RANGE *r;
7614
7615
optimizer::QUICK_RANGE **pr= (optimizer::QUICK_RANGE**)ranges.buffer;
7616
optimizer::QUICK_RANGE **end_range= pr + ranges.elements;
7617
for (; pr!=end_range; pr++)
7618
rev_ranges.push_front(*pr);
7619
7620
/* Remove EQ_RANGE flag for keys that are not using the full key */
7621
for (r = rev_it++; r; r = rev_it++)
7622
{
7623
if ((r->flag & EQ_RANGE) &&
7624
head->key_info[index].key_length != r->max_length)
7625
r->flag&= ~EQ_RANGE;
7626
}
7627
rev_it.rewind();
7628
q->dont_free=1; // Don't free shared mem
7629
delete q;
7630
}
7631
7632
7633
int optimizer::QUICK_SELECT_DESC::get_next()
7634
{
7635
/* The max key is handled as follows:
7636
* - if there is NO_MAX_RANGE, start at the end and move backwards
7637
* - if it is an EQ_RANGE, which means that max key covers the entire
7638
* key, go directly to the key and read through it (sorting backwards is
7639
* same as sorting forwards)
7640
* - if it is NEAR_MAX, go to the key or next, step back once, and
7641
* move backwards
7642
* - otherwise (not NEAR_MAX == include the key), go after the key,
7643
* step back once, and move backwards
7644
*/
7645
7646
for (;;)
7647
{
7648
int result;
7649
if (last_range)
7650
{ // Already read through key
7651
result = ((last_range->flag & EQ_RANGE)
7652
? cursor->index_next_same(record, last_range->min_key,
7653
last_range->min_length) :
7654
cursor->index_prev(record));
7655
if (!result)
7656
{
7657
if (cmp_prev(*rev_it.ref()) == 0)
7658
return 0;
7659
}
7660
else if (result != HA_ERR_END_OF_FILE)
7661
return result;
7662
}
7663
7664
if (!(last_range= rev_it++))
7665
return HA_ERR_END_OF_FILE; // All ranges used
7666
7667
if (last_range->flag & NO_MAX_RANGE) // Read last record
7668
{
7669
int local_error;
7670
if ((local_error=cursor->index_last(record)))
7671
return(local_error); // Empty table
7672
if (cmp_prev(last_range) == 0)
7673
return 0;
7674
last_range= 0; // No match; go to next range
7675
continue;
7676
}
7677
7678
if (last_range->flag & EQ_RANGE)
7679
{
7680
result = cursor->index_read_map(record, last_range->max_key,
7681
last_range->max_keypart_map,
7682
HA_READ_KEY_EXACT);
7683
}
7684
else
7685
{
7686
assert(last_range->flag & NEAR_MAX ||
7687
range_reads_after_key(last_range));
7688
result=cursor->index_read_map(record, last_range->max_key,
7689
last_range->max_keypart_map,
7690
((last_range->flag & NEAR_MAX) ?
7691
HA_READ_BEFORE_KEY :
7692
HA_READ_PREFIX_LAST_OR_PREV));
7693
}
7694
if (result)
7695
{
7696
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7697
return result;
7698
last_range= 0; // Not found, to next range
7699
continue;
7700
}
7701
if (cmp_prev(last_range) == 0)
7702
{
7703
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7704
last_range= 0; // Stop searching
7705
return 0; // Found key is in range
7706
}
7707
last_range= 0; // To next range
7708
}
7709
}
7710
7711
7712
/*
7713
Compare if found key is over max-value
7714
Returns 0 if key <= range->max_key
7715
TODO: Figure out why can't this function be as simple as cmp_prev().
7716
*/
7717
7718
int optimizer::QUICK_RANGE_SELECT::cmp_next(optimizer::QUICK_RANGE *range_arg)
7719
{
7720
if (range_arg->flag & NO_MAX_RANGE)
7721
return 0; /* key can't be to large */
7722
7723
KEY_PART *key_part=key_parts;
7724
uint32_t store_length;
7725
7726
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7727
key < end;
7728
key+= store_length, key_part++)
7729
{
7730
int cmp;
7731
store_length= key_part->store_length;
7732
if (key_part->null_bit)
7733
{
7734
if (*key)
7735
{
7736
if (!key_part->field->is_null())
7737
return 1;
7738
continue;
7739
}
7740
else if (key_part->field->is_null())
7741
return 0;
7742
key++; // Skip null byte
7743
store_length--;
7744
}
7745
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7746
return 0;
7747
if (cmp > 0)
7748
return 1;
7749
}
7750
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7751
}
7752
7753
7754
/*
7755
Returns 0 if found key is inside range (found key >= range->min_key).
7756
*/
7757
7758
int optimizer::QUICK_RANGE_SELECT::cmp_prev(optimizer::QUICK_RANGE *range_arg)
7759
{
7760
int cmp;
7761
if (range_arg->flag & NO_MIN_RANGE)
7762
return 0; /* key can't be to small */
7763
7764
cmp= key_cmp(key_part_info, range_arg->min_key,
7765
range_arg->min_length);
7766
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7767
return 0;
7768
return 1; // outside of range
7769
}
7770
7771
7772
/*
7773
* true if this range will require using HA_READ_AFTER_KEY
7774
See comment in get_next() about this
7775
*/
7776
7777
bool optimizer::QUICK_SELECT_DESC::range_reads_after_key(optimizer::QUICK_RANGE *range_arg)
7778
{
7779
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7780
!(range_arg->flag & EQ_RANGE) ||
7781
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7782
}
7783
7784
7785
void optimizer::QUICK_RANGE_SELECT::add_info_string(String *str)
7786
{
7787
KEY *key_info= head->key_info + index;
7788
str->append(key_info->name);
7789
}
7790
7791
void optimizer::QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7792
{
7793
optimizer::QUICK_RANGE_SELECT *quick;
7794
bool first= true;
7795
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> it(quick_selects);
7796
str->append(STRING_WITH_LEN("sort_union("));
7797
while ((quick= it++))
7798
{
7799
if (!first)
7800
str->append(',');
7801
else
7802
first= false;
7803
quick->add_info_string(str);
7804
}
7805
if (pk_quick_select)
7806
{
7807
str->append(',');
7808
pk_quick_select->add_info_string(str);
7809
}
7810
str->append(')');
7811
}
7812
7813
5847
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7814
5848
{
7815
5849
bool first= true;
7816
optimizer::QUICK_RANGE_SELECT *quick;
7817
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> it(quick_selects);
5850
optimizer::QuickRangeSelect *quick;
5851
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
7818
5852
str->append(STRING_WITH_LEN("intersect("));
7819
5853
while ((quick= it++))
7820
5854
{
7821
5855
KEY *key_info= head->key_info + quick->index;
7822
if (!first)
5856
if (! first)
7823
5857
str->append(',');
7824
5858
else
7825
5859
first= false;
7834
5868
str->append(')');
7835
5869
}
7836
5870
5871
7837
5872
void optimizer::QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7838
5873
{
7839
5874
bool first= true;
7840
optimizer::QUICK_SELECT_I *quick;
7841
List_iterator_fast<optimizer::QUICK_SELECT_I> it(quick_selects);
5875
optimizer::QuickSelectInterface *quick;
5876
List_iterator_fast<optimizer::QuickSelectInterface> it(quick_selects);
7842
5877
str->append(STRING_WITH_LEN("union("));
7843
5878
while ((quick= it++))
7844
5879
{
7845
if (!first)
5880
if (! first)
7846
5881
str->append(',');
7847
5882
else
7848
5883
first= false;
7852
5887
}
7853
5888
7854
5889
7855
void optimizer::QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7856
String *used_lengths)
7857
{
7858
char buf[64];
7859
uint32_t length;
7860
KEY *key_info= head->key_info + index;
7861
key_names->append(key_info->name);
7862
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7863
used_lengths->append(buf, length);
7864
}
7865
7866
void optimizer::QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7867
String *used_lengths)
7868
{
7869
char buf[64];
7870
uint32_t length;
7871
bool first= true;
7872
optimizer::QUICK_RANGE_SELECT *quick;
7873
7874
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> it(quick_selects);
7875
while ((quick= it++))
7876
{
7877
if (first)
7878
first= false;
7879
else
7880
{
7881
key_names->append(',');
7882
used_lengths->append(',');
7883
}
7884
7885
KEY *key_info= head->key_info + quick->index;
7886
key_names->append(key_info->name);
7887
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7888
used_lengths->append(buf, length);
7889
}
7890
if (pk_quick_select)
7891
{
7892
KEY *key_info= head->key_info + pk_quick_select->index;
7893
key_names->append(',');
7894
key_names->append(key_info->name);
7895
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7896
used_lengths->append(',');
7897
used_lengths->append(buf, length);
7898
}
7899
}
7900
7901
5890
void optimizer::QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7902
5891
String *used_lengths)
7903
5892
{
7904
5893
char buf[64];
7905
5894
uint32_t length;
7906
5895
bool first= true;
7907
optimizer::QUICK_RANGE_SELECT *quick;
7908
List_iterator_fast<optimizer::QUICK_RANGE_SELECT> it(quick_selects);
5896
optimizer::QuickRangeSelect *quick;
5897
List_iterator_fast<optimizer::QuickRangeSelect> it(quick_selects);
7909
5898
while ((quick= it++))
7910
5899
{
7911
5900
KEY *key_info= head->key_info + quick->index;
7932
5921
}
7933
5922
}
7934
5923
5924
7935
5925
void optimizer::QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7936
5926
String *used_lengths)
7937
5927
{
7938
5928
bool first= true;
7939
optimizer::QUICK_SELECT_I *quick;
7940
List_iterator_fast<optimizer::QUICK_SELECT_I> it(quick_selects);
5929
optimizer::QuickSelectInterface *quick;
5930
List_iterator_fast<optimizer::QuickSelectInterface> it(quick_selects);
7941
5931
while ((quick= it++))
7942
5932
{
7943
5933
if (first)
7957
5947
*******************************************************************************/
7958
5948
7959
5949
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7960
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7961
PARAM *param, uint32_t *param_idx);
7962
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7963
KEY_PART_INFO *first_non_group_part,
7964
KEY_PART_INFO *min_max_arg_part,
7965
KEY_PART_INFO *last_part, Session *session,
7966
unsigned char *key_infix, uint32_t *key_infix_len,
7967
KEY_PART_INFO **first_non_infix_part);
5950
5951
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
5952
SEL_TREE *range_tree,
5953
optimizer::Parameter *param,
5954
uint32_t *param_idx);
5955
5956
static bool get_constant_key_infix(KEY *index_info,
5957
optimizer::SEL_ARG *index_range_tree,
5958
KEY_PART_INFO *first_non_group_part,
5959
KEY_PART_INFO *min_max_arg_part,
5960
KEY_PART_INFO *last_part,
5961
Session *session,
5962
unsigned char *key_infix,
5963
uint32_t *key_infix_len,
5964
KEY_PART_INFO **first_non_infix_part);
5965
7968
5966
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7969
5967
7970
5968
static void
7971
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7972
uint32_t group_key_parts, SEL_TREE *range_tree,
7973
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7974
bool have_min, bool have_max,
7975
double *read_cost, ha_rows *records);
5969
cost_group_min_max(Table* table,
5970
KEY *index_info,
5971
uint32_t used_key_parts,
5972
uint32_t group_key_parts,
5973
SEL_TREE *range_tree,
5974
optimizer::SEL_ARG *index_tree,
5975
ha_rows quick_prefix_records,
5976
bool have_min,
5977
bool have_max,
5978
double *read_cost,
5979
ha_rows *records);
7976
5980
7977
5981
7978
5982
/*
8102
6106
If mem_root == NULL
8103
6107
- NULL
8104
6108
*/
8105
8106
6109
static TRP_GROUP_MIN_MAX *
8107
get_best_group_min_max(PARAM *param, SEL_TREE *tree)
6110
get_best_group_min_max(optimizer::Parameter *param, SEL_TREE *tree)
8108
6111
{
8109
6112
Session *session= param->session;
8110
6113
JOIN *join= session->lex->current_select->join;
8122
6125
uint32_t key_infix_len= 0; /* Length of key_infix. */
8123
6126
TRP_GROUP_MIN_MAX *read_plan= NULL; /* The eventually constructed TRP. */
8124
6127
uint32_t key_part_nr;
8125
order_st *tmp_group;
8126
Item *item;
8127
Item_field *item_field;
6128
order_st *tmp_group= NULL;
6129
Item *item= NULL;
6130
Item_field *item_field= NULL;
8128
6131
8129
6132
/* Perform few 'cheap' tests whether this access method is applicable. */
8130
if (!join)
6133
if (! join)
8131
6134
return NULL; /* This is not a select statement. */
6135
8132
6136
if ((join->tables != 1) || /* The query must reference one table. */
8133
((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
8134
(!join->select_distinct)) ||
6137
((! join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
6138
(! join->select_distinct)) ||
8135
6139
(join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
8136
6140
return NULL;
8137
6141
if (table->s->keys == 0) /* There are no indexes to use. */
8143
6147
/* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
8144
6148
if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
8145
6149
return NULL;
6150
8146
6151
if (join->sum_funcs[0])
8147
6152
{
8148
Item_sum *min_max_item;
6153
Item_sum *min_max_item= NULL;
8149
6154
Item_sum **func_ptr= join->sum_funcs;
8150
6155
while ((min_max_item= *(func_ptr++)))
8151
6156
{
8195
6200
KEY *cur_index_info= table->key_info;
8196
6201
KEY *cur_index_info_end= cur_index_info + table->s->keys;
8197
6202
KEY_PART_INFO *cur_part= NULL;
8198
KEY_PART_INFO *end_part; /* Last part for loops. */
6203
KEY_PART_INFO *end_part= NULL; /* Last part for loops. */
8199
6204
/* Last index part. */
8200
6205
KEY_PART_INFO *last_part= NULL;
8201
6206
KEY_PART_INFO *first_non_group_part= NULL;
8206
6211
/* Cost-related variables for the best index so far. */
8207
6212
double best_read_cost= DBL_MAX;
8208
6213
ha_rows best_records= 0;
8209
SEL_ARG *best_index_tree= NULL;
6214
optimizer::SEL_ARG *best_index_tree= NULL;
8210
6215
ha_rows best_quick_prefix_records= 0;
8211
6216
uint32_t best_param_idx= 0;
8212
6217
double cur_read_cost= DBL_MAX;
8213
6218
ha_rows cur_records;
8214
SEL_ARG *cur_index_tree= NULL;
6219
optimizer::SEL_ARG *cur_index_tree= NULL;
8215
6220
ha_rows cur_quick_prefix_records= 0;
8216
uint32_t cur_param_idx=MAX_KEY;
6221
uint32_t cur_param_idx= MAX_KEY;
8217
6222
key_map used_key_parts_map;
8218
6223
uint32_t cur_key_infix_len= 0;
8219
6224
unsigned char cur_key_infix[MAX_KEY_LENGTH];
8220
6225
uint32_t cur_used_key_parts= 0;
8221
6226
uint32_t pk= param->table->s->primary_key;
8222
6227
8223
for (uint32_t cur_index= 0 ; cur_index_info != cur_index_info_end ;
6228
for (uint32_t cur_index= 0;
6229
cur_index_info != cur_index_info_end;
8224
6230
cur_index_info++, cur_index++)
8225
6231
{
8226
6232
/* Check (B1) - if current index is covering. */
8227
if (!table->covering_keys.test(cur_index))
6233
if (! table->covering_keys.test(cur_index))
8228
6234
goto next_index;
8229
6235
8230
6236
/*
8248
6254
part of 'cur_index'
8249
6255
*/
8250
6256
if ((cur_field->isReadSet()) &&
8251
!cur_field->part_of_key_not_clustered.test(cur_index))
6257
! cur_field->part_of_key_not_clustered.test(cur_index))
8252
6258
goto next_index; // Field was not part of key
8253
6259
}
8254
6260
}
8261
6267
cur_part= cur_index_info->key_part;
8262
6268
end_part= cur_part + cur_index_info->key_parts;
8263
6269
/* Iterate in parallel over the GROUP list and the index parts. */
8264
for (tmp_group= join->group_list; tmp_group && (cur_part != end_part);
6270
for (tmp_group= join->group_list;
6271
tmp_group && (cur_part != end_part);
8265
6272
tmp_group= tmp_group->next, cur_part++)
8266
6273
{
8267
6274
/*
8319
6326
all_parts have all bits set from 0 to (max_key_part-1).
8320
6327
cur_parts have bits set for only used keyparts.
8321
6328
*/
8322
key_map all_parts, cur_parts;
6329
key_map all_parts;
6330
key_map cur_parts;
8323
6331
for (uint32_t pos= 0; pos < max_key_part; pos++)
8324
6332
all_parts.set(pos);
8325
6333
cur_parts= used_key_parts_map >> 1;
8363
6371
NULL :
8364
6372
NULL;
8365
6373
if (first_non_group_part &&
8366
(!min_max_arg_part || (min_max_arg_part - first_non_group_part > 0)))
6374
(! min_max_arg_part || (min_max_arg_part - first_non_group_part > 0)))
8367
6375
{
8368
6376
if (tree)
8369
6377
{
8370
6378
uint32_t dummy;
8371
SEL_ARG *index_range_tree= get_index_range_tree(cur_index, tree, param,
8372
&dummy);
8373
if (!get_constant_key_infix(cur_index_info, index_range_tree,
8374
first_non_group_part, min_max_arg_part,
8375
last_part, session, cur_key_infix,
8376
&cur_key_infix_len,
8377
&first_non_infix_part))
6379
optimizer::SEL_ARG *index_range_tree= get_index_range_tree(cur_index,
6380
tree,
6381
param,
6382
&dummy);
6383
if (! get_constant_key_infix(cur_index_info,
6384
index_range_tree,
6385
first_non_group_part,
6386
min_max_arg_part,
6387
last_part,
6388
session,
6389
cur_key_infix,
6390
&cur_key_infix_len,
6391
&first_non_infix_part))
6392
{
8378
6393
goto next_index;
6394
}
8379
6395
}
8380
6396
else if (min_max_arg_part &&
8381
6397
(min_max_arg_part - first_non_group_part > 0))
8405
6421
key_part_range[1]= last_part;
8406
6422
8407
6423
/* Check if cur_part is referenced in the WHERE clause. */
8408
if (join->conds->walk(&Item::find_item_in_field_list_processor, 0,
6424
if (join->conds->walk(&Item::find_item_in_field_list_processor,
6425
0,
8409
6426
(unsigned char*) key_part_range))
8410
6427
goto next_index;
8411
6428
}
8435
6452
if (tree)
8436
6453
{
8437
6454
/* Find the SEL_ARG sub-tree that corresponds to the chosen index. */
8438
cur_index_tree= get_index_range_tree(cur_index, tree, param,
6455
cur_index_tree= get_index_range_tree(cur_index,
6456
tree,
6457
param,
8439
6458
&cur_param_idx);
8440
6459
/* Check if this range tree can be used for prefix retrieval. */
8441
6460
COST_VECT dummy_cost;
8442
6461
uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
8443
uint32_t mrr_bufsize=0;
8444
cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
6462
uint32_t mrr_bufsize= 0;
6463
cur_quick_prefix_records= check_quick_select(param,
6464
cur_param_idx,
8445
6465
false /*don't care*/,
8446
cur_index_tree, true,
8447
&mrr_flags, &mrr_bufsize,
6466
cur_index_tree,
6467
true,
6468
&mrr_flags,
6469
&mrr_bufsize,
8448
6470
&dummy_cost);
8449
6471
}
8450
cost_group_min_max(table, cur_index_info, cur_used_key_parts,
8451
cur_group_key_parts, tree, cur_index_tree,
8452
cur_quick_prefix_records, have_min, have_max,
8453
&cur_read_cost, &cur_records);
6472
cost_group_min_max(table,
6473
cur_index_info,
6474
cur_used_key_parts,
6475
cur_group_key_parts,
6476
tree,
6477
cur_index_tree,
6478
cur_quick_prefix_records,
6479
have_min,
6480
have_max,
6481
&cur_read_cost,
6482
&cur_records);
8454
6483
/*
8455
6484
If cur_read_cost is lower than best_read_cost use cur_index.
8456
6485
Do not compare doubles directly because they may have different
8469
6498
group_key_parts= cur_group_key_parts;
8470
6499
group_prefix_len= cur_group_prefix_len;
8471
6500
key_infix_len= cur_key_infix_len;
6501
8472
6502
if (key_infix_len)
8473
memcpy (key_infix, cur_key_infix, sizeof (key_infix));
6503
{
6504
memcpy(key_infix, cur_key_infix, sizeof (key_infix));
6505
}
6506
8474
6507
used_key_parts= cur_used_key_parts;
8475
6508
}
8476
6509
8479
6512
cur_group_prefix_len= 0;
8480
6513
cur_key_infix_len= 0;
8481
6514
}
8482
if (!index_info) /* No usable index found. */
6515
if (! index_info) /* No usable index found. */
8483
6516
return NULL;
8484
6517
8485
6518
/* Check (SA3) for the where clause. */
8488
6521
return NULL;
8489
6522
8490
6523
/* The query passes all tests, so construct a new TRP object. */
8491
read_plan= new (param->mem_root)
8492
TRP_GROUP_MIN_MAX(have_min, have_max, min_max_arg_part,
8493
group_prefix_len, used_key_parts,
8494
group_key_parts, index_info, index,
8495
key_infix_len,
8496
(key_infix_len > 0) ? key_infix : NULL,
8497
tree, best_index_tree, best_param_idx,
8498
best_quick_prefix_records);
6524
read_plan=
6525
new(param->mem_root) TRP_GROUP_MIN_MAX(have_min,
6526
have_max,
6527
min_max_arg_part,
6528
group_prefix_len,
6529
used_key_parts,
6530
group_key_parts,
6531
index_info,
6532
index,
6533
key_infix_len,
6534
(key_infix_len > 0) ? key_infix : NULL,
6535
tree,
6536
best_index_tree,
6537
best_param_idx,
6538
best_quick_prefix_records);
8499
6539
if (read_plan)
8500
6540
{
8501
6541
if (tree && read_plan->quick_prefix_records == 0)
8502
6542
return NULL;
8503
6543
8504
6544
read_plan->read_cost= best_read_cost;
8505
read_plan->records= best_records;
6545
read_plan->records= best_records;
8506
6546
}
8507
6547
8508
6548
return read_plan;
8539
6579
if (cond_type == Item::COND_ITEM) /* 'AND' or 'OR' */
8540
6580
{
8541
6581
List_iterator_fast<Item> li(*((Item_cond*) cond)->argument_list());
8542
Item *and_or_arg;
6582
Item *and_or_arg= NULL;
8543
6583
while ((and_or_arg= li++))
8544
6584
{
8545
if (!check_group_min_max_predicates(and_or_arg, min_max_arg_item))
6585
if (! check_group_min_max_predicates(and_or_arg, min_max_arg_item))
8546
6586
return false;
8547
6587
}
8548
6588
return true;
8566
6606
/* Test if cond references only group-by or non-group fields. */
8567
6607
Item_func *pred= (Item_func*) cond;
8568
6608
Item **arguments= pred->arguments();
8569
Item *cur_arg;
6609
Item *cur_arg= NULL;
8570
6610
for (uint32_t arg_idx= 0; arg_idx < pred->argument_count (); arg_idx++)
8571
6611
{
8572
6612
cur_arg= arguments[arg_idx]->real_item();
8594
6634
/* Check that pred compares min_max_arg_item with a constant. */
8595
6635
Item *args[3];
8596
6636
memset(args, 0, 3 * sizeof(Item*));
8597
bool inv;
6637
bool inv= false;
8598
6638
/* Test if this is a comparison of a field and a constant. */
8599
if (! optimizer::simple_pred(pred, args, &inv))
6639
if (! optimizer::simple_pred(pred, args, inv))
8600
6640
return false;
8601
6641
8602
6642
/* Check for compatible string comparisons - similar to get_mm_leaf. */
8615
6655
*/
8616
6656
(args[1]->result_type() != STRING_RESULT &&
8617
6657
min_max_arg_item->field->cmp_type() != args[1]->result_type())))
6658
{
8618
6659
return false;
6660
}
8619
6661
}
8620
6662
}
8621
6663
else if (cur_arg->type() == Item::FUNC_ITEM)
8665
6707
true if the index passes the test
8666
6708
false o/w
8667
6709
*/
8668
8669
6710
static bool
8670
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
6711
get_constant_key_infix(KEY *,
6712
optimizer::SEL_ARG *index_range_tree,
8671
6713
KEY_PART_INFO *first_non_group_part,
8672
6714
KEY_PART_INFO *min_max_arg_part,
8673
6715
KEY_PART_INFO *last_part,
8674
Session *, unsigned char *key_infix, uint32_t *key_infix_len,
6716
Session *,
6717
unsigned char *key_infix,
6718
uint32_t *key_infix_len,
8675
6719
KEY_PART_INFO **first_non_infix_part)
8676
6720
{
8677
SEL_ARG *cur_range;
8678
KEY_PART_INFO *cur_part;
6721
optimizer::SEL_ARG *cur_range= NULL;
6722
KEY_PART_INFO *cur_part= NULL;
8679
6723
/* End part for the first loop below. */
8680
6724
KEY_PART_INFO *end_part= min_max_arg_part ? min_max_arg_part : last_part;
8681
6725
8693
6737
if (cur_range->field->eq(cur_part->field))
8694
6738
break;
8695
6739
}
8696
if (!cur_range)
6740
if (! cur_range)
8697
6741
{
8698
6742
if (min_max_arg_part)
8699
6743
return false; /* The current keypart has no range predicates at all. */
8709
6753
return false; /* This is not the only range predicate for the field. */
8710
6754
if ((cur_range->min_flag & NO_MIN_RANGE) ||
8711
6755
(cur_range->max_flag & NO_MAX_RANGE) ||
8712
(cur_range->min_flag & NEAR_MIN) || (cur_range->max_flag & NEAR_MAX))
6756
(cur_range->min_flag & NEAR_MIN) ||
6757
(cur_range->max_flag & NEAR_MAX))
8713
6758
return false;
8714
6759
8715
6760
uint32_t field_length= cur_part->store_length;
8749
6794
Positive number which is the consecutive number of the key part, or
8750
6795
0 if field does not reference any index field.
8751
6796
*/
8752
8753
6797
static inline uint
8754
6798
get_field_keypart(KEY *index, Field *field)
8755
6799
{
8756
KEY_PART_INFO *part, *end;
6800
KEY_PART_INFO *part= NULL;
6801
KEY_PART_INFO *end= NULL;
8757
6802
8758
6803
for (part= index->key_part, end= part + index->key_parts; part < end; part++)
8759
6804
{
8771
6816
get_index_range_tree()
8772
6817
index [in] The ID of the index being looked for
8773
6818
range_tree[in] Tree of ranges being searched
8774
param [in] PARAM from SQL_SELECT::test_quick_select
8775
param_idx [out] Index in the array PARAM::key that corresponds to 'index'
6819
param [in] Parameter from SqlSelect::test_quick_select
6820
param_idx [out] Index in the array Parameter::key that corresponds to 'index'
8776
6821
8777
6822
DESCRIPTION
8778
6823
8779
6824
A SEL_TREE contains range trees for all usable indexes. This procedure
8780
6825
finds the SEL_ARG sub-tree for 'index'. The members of a SEL_TREE are
8781
ordered in the same way as the members of PARAM::key, thus we first find
8782
the corresponding index in the array PARAM::key. This index is returned
6826
ordered in the same way as the members of Parameter::key, thus we first find
6827
the corresponding index in the array Parameter::key. This index is returned
8783
6828
through the variable param_idx, to be used later as argument of
8784
6829
check_quick_select().
8785
6830
8786
6831
RETURN
8787
6832
Pointer to the SEL_ARG subtree that corresponds to index.
8788
6833
*/
8789
8790
SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree, PARAM *param,
6834
optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
6835
SEL_TREE* range_tree,
6836
optimizer::Parameter *param,
8791
6837
uint32_t *param_idx)
8792
6838
{
8793
6839
uint32_t idx= 0; /* Index nr in param->key_parts */
8861
6907
RETURN
8862
6908
None
8863
6909
*/
8864
8865
void cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
8866
uint32_t group_key_parts, SEL_TREE *range_tree,
8867
SEL_ARG *, ha_rows quick_prefix_records,
8868
bool have_min, bool have_max,
8869
double *read_cost, ha_rows *records)
6910
void cost_group_min_max(Table* table,
6911
KEY *index_info,
6912
uint32_t used_key_parts,
6913
uint32_t group_key_parts,
6914
SEL_TREE *range_tree,
6915
optimizer::SEL_ARG *,
6916
ha_rows quick_prefix_records,
6917
bool have_min,
6918
bool have_max,
6919
double *read_cost,
6920
ha_rows *records)
8870
6921
{
8871
6922
ha_rows table_records;
8872
6923
uint32_t num_groups;
8884
6935
keys_per_block= (table->cursor->stats.block_size / 2 /
8885
6936
(index_info->key_length + table->cursor->ref_length)
8886
6937
+ 1);
8887
num_blocks= (uint32_t)(table_records / keys_per_block) + 1;
6938
num_blocks= (uint32_t) (table_records / keys_per_block) + 1;
8888
6939
8889
6940
/* Compute the number of keys in a group. */
8890
6941
keys_per_group= index_info->rec_per_key[group_key_parts - 1];
8927
6978
/*
8928
6979
TODO: If there is no WHERE clause and no other expressions, there should be
8929
6980
no CPU cost. We leave it here to make this cost comparable to that of index
8930
scan as computed in SQL_SELECT::test_quick_select().
6981
scan as computed in SqlSelect::test_quick_select().
8931
6982
*/
8932
6983
cpu_cost= (double) num_groups / TIME_FOR_COMPARE;
8933
6984
8956
7007
New QUICK_GROUP_MIN_MAX_SELECT object if successfully created,
8957
7008
NULL otherwise.
8958
7009
*/
8959
8960
optimizer::QUICK_SELECT_I *
8961
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
7010
optimizer::QuickSelectInterface *
7011
TRP_GROUP_MIN_MAX::make_quick(optimizer::Parameter *param, bool, MEM_ROOT *parent_alloc)
8962
7012
{
8963
optimizer::QUICK_GROUP_MIN_MAX_SELECT *quick;
7013
optimizer::QUICK_GROUP_MIN_MAX_SELECT *quick= NULL;
8964
7014
8965
7015
quick= new optimizer::QUICK_GROUP_MIN_MAX_SELECT(param->table,
8966
7016
param->session->lex->current_select->join,
8967
have_min,
8968
have_max,
7017
have_min,
7018
have_max,
8969
7019
min_max_arg_part,
8970
group_prefix_len,
7020
group_prefix_len,
8971
7021
group_key_parts,
8972
used_key_parts,
8973
index_info,
7022
used_key_parts,
7023
index_info,
8974
7024
index,
8975
read_cost,
8976
records,
7025
read_cost,
7026
records,
8977
7027
key_infix_len,
8978
key_infix,
7028
key_infix,
8979
7029
parent_alloc);
8980
7030
if (! quick)
8981
7031
{
8997
7047
}
8998
7048
else
8999
7049
{
9000
/* Make a QUICK_RANGE_SELECT to be used for group prefix retrieval. */
9001
quick->quick_prefix_select= optimizer::get_quick_select(param,
7050
/* Make a QuickRangeSelect to be used for group prefix retrieval. */
7051
quick->quick_prefix_select= optimizer::get_quick_select(param,
9002
7052
param_idx,
9003
7053
index_tree,
9004
HA_MRR_USE_DEFAULT_IMPL,
7054
HA_MRR_USE_DEFAULT_IMPL,
9005
7055
0,
9006
7056
&quick->alloc);
9007
7057
}
9008
7058
9009
7059
/*
9010
7060
Extract the SEL_ARG subtree that contains only ranges for the MIN/MAX
9011
attribute, and create an array of QUICK_RANGES to be used by the
7061
attribute, and create an array of QuickRanges to be used by the
9012
7062
new quick select.
9013
7063
*/
9014
7064
if (min_max_arg_part)
9015
7065
{
9016
SEL_ARG *min_max_range= index_tree;
7066
optimizer::SEL_ARG *min_max_range= index_tree;
9017
7067
while (min_max_range) /* Find the tree for the MIN/MAX key part. */
9018
7068
{
9019
7069
if (min_max_range->field->eq(min_max_arg_part->field))
9023
7073
/* Scroll to the leftmost interval for the MIN/MAX argument. */
9024
7074
while (min_max_range && min_max_range->prev)
9025
7075
min_max_range= min_max_range->prev;
9026
/* Create an array of QUICK_RANGEs for the MIN/MAX argument. */
7076
/* Create an array of QuickRanges for the MIN/MAX argument. */
9027
7077
while (min_max_range)
9028
7078
{
9029
7079
if (quick->add_range(min_max_range))
9069
7119
RETURN
9070
7120
None
9071
7121
*/
9072
9073
7122
optimizer::QUICK_GROUP_MIN_MAX_SELECT::
9074
QUICK_GROUP_MIN_MAX_SELECT(Table *table,
9075
JOIN *join_arg,
7123
QUICK_GROUP_MIN_MAX_SELECT(Table *table,
7124
JOIN *join_arg,
9076
7125
bool have_min_arg,
9077
7126
bool have_max_arg,
9078
7127
KEY_PART_INFO *min_max_arg_part_arg,
9079
uint32_t group_prefix_len_arg,
7128
uint32_t group_prefix_len_arg,
9080
7129
uint32_t group_key_parts_arg,
9081
uint32_t used_key_parts_arg,
7130
uint32_t used_key_parts_arg,
9082
7131
KEY *index_info_arg,
9083
uint32_t use_index,
7132
uint32_t use_index,
9084
7133
double read_cost_arg,
9085
ha_rows records_arg,
7134
ha_rows records_arg,
9086
7135
uint32_t key_infix_len_arg,
9087
unsigned char *key_infix_arg,
7136
unsigned char *key_infix_arg,
9088
7137
MEM_ROOT *parent_alloc)
9089
7138
:
9090
join(join_arg),
7139
join(join_arg),
9091
7140
index_info(index_info_arg),
9092
group_prefix_len(group_prefix_len_arg),
9093
group_key_parts(group_key_parts_arg),
9094
have_min(have_min_arg),
9095
have_max(have_max_arg),
9096
seen_first_key(false),
9097
min_max_arg_part(min_max_arg_part_arg),
9098
key_infix(key_infix_arg),
9099
key_infix_len(key_infix_len_arg),
9100
min_functions_it(NULL),
9101
max_functions_it(NULL)
7141
group_prefix_len(group_prefix_len_arg),
7142
group_key_parts(group_key_parts_arg),
7143
have_min(have_min_arg),
7144
have_max(have_max_arg),
7145
seen_first_key(false),
7146
min_max_arg_part(min_max_arg_part_arg),
7147
key_infix(key_infix_arg),
7148
key_infix_len(key_infix_len_arg),
7149
min_functions_it(NULL),
7150
max_functions_it(NULL)
9102
7151
{
9103
head= table;
9104
cursor= head->cursor;
9105
index= use_index;
9106
record= head->record[0];
7152
head= table;
7153
cursor= head->cursor;
7154
index= use_index;
7155
record= head->record[0];
9107
7156
tmp_record= head->record[1];
9108
7157
read_time= read_cost_arg;
9109
7158
records= records_arg;
9117
7166
We can't have parent_alloc set as the init function can't handle this case
9118
7167
yet.
9119
7168
*/
9120
assert(!parent_alloc);
9121
if (!parent_alloc)
7169
assert(! parent_alloc);
7170
if (! parent_alloc)
9122
7171
{
9123
7172
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
9124
7173
join->session->mem_root= &alloc;
9144
7193
0 OK
9145
7194
other Error code
9146
7195
*/
9147
9148
7196
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::init()
9149
7197
{
9150
7198
if (group_prefix) /* Already initialized. */
9151
7199
return 0;
9152
7200
9153
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
7201
if (! (last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
9154
7202
return 1;
9155
7203
/*
9156
7204
We may use group_prefix to store keys with all select fields, so allocate
9157
7205
enough space for it.
9158
7206
*/
9159
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
9160
real_prefix_len + min_max_arg_len)))
7207
if (! (group_prefix= (unsigned char*) alloc_root(&alloc,
7208
real_prefix_len + min_max_arg_len)))
9161
7209
return 1;
9162
7210
9163
7211
if (key_infix_len > 0)
9167
7215
allocate a new buffer and copy the key_infix into it.
9168
7216
*/
9169
7217
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
9170
if (!tmp_key_infix)
7218
if (! tmp_key_infix)
9171
7219
return 1;
9172
7220
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
9173
7221
this->key_infix= tmp_key_infix;
9175
7223
9176
7224
if (min_max_arg_part)
9177
7225
{
9178
if (my_init_dynamic_array(&min_max_ranges, sizeof(optimizer::QUICK_RANGE*), 16, 16))
7226
if (my_init_dynamic_array(&min_max_ranges, sizeof(optimizer::QuickRange*), 16, 16))
9179
7227
return 1;
9180
7228
9181
7229
if (have_min)
9182
7230
{
9183
if (!(min_functions= new List<Item_sum>))
7231
if (! (min_functions= new List<Item_sum>))
9184
7232
return 1;
9185
7233
}
9186
7234
else
9187
7235
min_functions= NULL;
9188
7236
if (have_max)
9189
7237
{
9190
if (!(max_functions= new List<Item_sum>))
7238
if (! (max_functions= new List<Item_sum>))
9191
7239
return 1;
9192
7240
}
9193
7241
else
9194
7242
max_functions= NULL;
9195
7243
9196
Item_sum *min_max_item;
7244
Item_sum *min_max_item= NULL;
9197
7245
Item_sum **func_ptr= join->sum_funcs;
9198
7246
while ((min_max_item= *(func_ptr++)))
9199
7247
{
9205
7253
9206
7254
if (have_min)
9207
7255
{
9208
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
7256
if (! (min_functions_it= new List_iterator<Item_sum>(*min_functions)))
9209
7257
return 1;
9210
7258
}
9211
7259
9212
7260
if (have_max)
9213
7261
{
9214
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
7262
if (! (max_functions_it= new List_iterator<Item_sum>(*max_functions)))
9215
7263
return 1;
9216
7264
}
9217
7265
}
9247
7295
sel_range Range object from which a
9248
7296
9249
7297
NOTES
9250
Construct a new QUICK_RANGE object from a SEL_ARG object, and
7298
Construct a new QuickRange object from a SEL_ARG object, and
9251
7299
add it to the array min_max_ranges. If sel_arg is an infinite
9252
7300
range, e.g. (x < 5 or x > 4), then skip it and do not construct
9253
7301
a quick range.
9256
7304
false on success
9257
7305
true otherwise
9258
7306
*/
9259
9260
7307
bool optimizer::QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
9261
7308
{
9262
optimizer::QUICK_RANGE *range;
7309
optimizer::QuickRange *range= NULL;
9263
7310
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
9264
7311
9265
7312
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
9266
7313
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
9267
7314
return false;
9268
7315
9269
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
9270
!(sel_range->max_flag & NO_MAX_RANGE))
7316
if (! (sel_range->min_flag & NO_MIN_RANGE) &&
7317
! (sel_range->max_flag & NO_MAX_RANGE))
9271
7318
{
9272
7319
if (sel_range->maybe_null &&
9273
7320
sel_range->min_value[0] && sel_range->max_value[0])
9276
7323
min_max_arg_len) == 0)
9277
7324
range_flag|= EQ_RANGE; /* equality condition */
9278
7325
}
9279
range= new optimizer::QUICK_RANGE(sel_range->min_value, min_max_arg_len,
9280
make_keypart_map(sel_range->part),
9281
sel_range->max_value, min_max_arg_len,
9282
make_keypart_map(sel_range->part),
9283
range_flag);
9284
if (!range)
7326
range= new optimizer::QuickRange(sel_range->min_value,
7327
min_max_arg_len,
7328
make_keypart_map(sel_range->part),
7329
sel_range->max_value,
7330
min_max_arg_len,
7331
make_keypart_map(sel_range->part),
7332
range_flag);
7333
if (! range)
9285
7334
return true;
9286
7335
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
9287
7336
return true;
9311
7360
if (quick_prefix_select &&
9312
7361
group_prefix_len < quick_prefix_select->max_used_key_length)
9313
7362
{
9314
DYNAMIC_ARRAY *arr;
7363
DYNAMIC_ARRAY *arr= NULL;
9315
7364
uint32_t inx;
9316
7365
9317
7366
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9318
7367
{
9319
optimizer::QUICK_RANGE *range;
7368
optimizer::QuickRange *range= NULL;
9320
7369
9321
7370
get_dynamic(arr, (unsigned char*)&range, inx);
9322
7371
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9345
7394
RETURN
9346
7395
None
9347
7396
*/
9348
9349
7397
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9350
7398
{
9351
7399
max_used_key_length= real_prefix_len;
9352
7400
if (min_max_ranges.elements > 0)
9353
7401
{
9354
optimizer::QUICK_RANGE *cur_range;
7402
optimizer::QuickRange *cur_range= NULL;
9355
7403
if (have_min)
9356
7404
{ /* Check if the right-most range has a lower boundary. */
9357
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
7405
get_dynamic(&min_max_ranges,
7406
(unsigned char*) &cur_range,
9358
7407
min_max_ranges.elements - 1);
9359
if (!(cur_range->flag & NO_MIN_RANGE))
7408
if (! (cur_range->flag & NO_MIN_RANGE))
9360
7409
{
9361
7410
max_used_key_length+= min_max_arg_len;
9362
7411
used_key_parts++;
9366
7415
if (have_max)
9367
7416
{ /* Check if the left-most range has an upper boundary. */
9368
7417
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9369
if (!(cur_range->flag & NO_MAX_RANGE))
7418
if (! (cur_range->flag & NO_MAX_RANGE))
9370
7419
{
9371
7420
max_used_key_length+= min_max_arg_len;
9372
7421
used_key_parts++;
9405
7454
0 OK
9406
7455
other Error code
9407
7456
*/
9408
9409
7457
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9410
7458
{
9411
7459
int result;
9452
7500
HA_ERR_END_OF_FILE if returned all keys
9453
7501
other if some error occurred
9454
7502
*/
9455
9456
7503
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::get_next()
9457
7504
{
9458
7505
int min_res= 0;
9459
7506
int max_res= 0;
9460
int result;
7507
int result= 0;
9461
7508
int is_last_prefix= 0;
9462
7509
9463
7510
/*
9471
7518
Check if this is the last group prefix. Notice that at this point
9472
7519
this->record contains the current prefix in record format.
9473
7520
*/
9474
if (!result)
7521
if (! result)
9475
7522
{
9476
7523
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9477
7524
group_prefix_len);
9506
7553
are equality predicates for the key parts after the group, find the
9507
7554
first sub-group with the extended prefix.
9508
7555
*/
9509
if (!have_min && !have_max && key_infix_len > 0)
9510
result= cursor->index_read_map(record, group_prefix,
9511
make_prev_keypart_map(real_key_parts),
9512
HA_READ_KEY_EXACT);
7556
if (! have_min && ! have_max && key_infix_len > 0)
7557
result= cursor->index_read_map(record,
7558
group_prefix,
7559
make_prev_keypart_map(real_key_parts),
7560
HA_READ_KEY_EXACT);
9513
7561
9514
7562
result= have_min ? min_res : have_max ? max_res : result;
9515
7563
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9554
7602
HA_ERR_END_OF_FILE - "" -
9555
7603
other if some error occurred
9556
7604
*/
9557
9558
7605
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_min()
9559
7606
{
9560
7607
int result= 0;
9570
7617
/* Apply the constant equality conditions to the non-group select fields */
9571
7618
if (key_infix_len > 0)
9572
7619
{
9573
if ((result= cursor->index_read_map(record, group_prefix,
9574
make_prev_keypart_map(real_key_parts),
9575
HA_READ_KEY_EXACT)))
7620
if ((result= cursor->index_read_map(record,
7621
group_prefix,
7622
make_prev_keypart_map(real_key_parts),
7623
HA_READ_KEY_EXACT)))
9576
7624
return result;
9577
7625
}
9578
7626
9587
7635
{
9588
7636
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9589
7637
key_copy(tmp_record, record, index_info, 0);
9590
result= cursor->index_read_map(record, tmp_record,
9591
make_keypart_map(real_key_parts),
9592
HA_READ_AFTER_KEY);
7638
result= cursor->index_read_map(record,
7639
tmp_record,
7640
make_keypart_map(real_key_parts),
7641
HA_READ_AFTER_KEY);
9593
7642
/*
9594
7643
Check if the new record belongs to the current group by comparing its
9595
7644
prefix with the group's prefix. If it is from the next group, then the
9600
7649
next call to next_min(), and to save one lookup in the next call. For
9601
7650
this add a new member 'this->next_group_prefix'.
9602
7651
*/
9603
if (!result)
7652
if (! result)
9604
7653
{
9605
7654
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9606
7655
key_restore(record, tmp_record, index_info, 0);
9633
7682
HA_ERR_END_OF_FILE - "" -
9634
7683
other if some error occurred
9635
7684
*/
9636
9637
7685
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_max()
9638
7686
{
9639
int result;
7687
int result= 0;
9640
7688
9641
7689
/* Get the last key in the (possibly extended) group. */
9642
7690
if (min_max_ranges.elements > 0)
9643
7691
result= next_max_in_range();
9644
7692
else
9645
result= cursor->index_read_map(record, group_prefix,
9646
make_prev_keypart_map(real_key_parts),
9647
HA_READ_PREFIX_LAST);
7693
result= cursor->index_read_map(record,
7694
group_prefix,
7695
make_prev_keypart_map(real_key_parts),
7696
HA_READ_PREFIX_LAST);
9648
7697
return result;
9649
7698
}
9650
7699
9658
7707
DESCRIPTION
9659
7708
Determine the prefix of the next group that satisfies the query conditions.
9660
7709
If there is a range condition referencing the group attributes, use a
9661
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
7710
QuickRangeSelect object to retrieve the *first* key that satisfies the
9662
7711
condition. If there is a key infix of constants, append this infix
9663
7712
immediately after the group attributes. The possibly extended prefix is
9664
7713
stored in this->group_prefix. The first key of the found group is stored in
9672
7721
*/
9673
7722
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9674
7723
{
9675
int result;
7724
int result= 0;
9676
7725
9677
7726
if (quick_prefix_select)
9678
7727
{
9679
7728
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9680
7729
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9681
make_prev_keypart_map(group_key_parts), cur_prefix)))
7730
make_prev_keypart_map(group_key_parts),
7731
cur_prefix)))
9682
7732
return result;
9683
7733
seen_first_key= true;
9684
7734
}
9685
7735
else
9686
7736
{
9687
if (!seen_first_key)
7737
if (! seen_first_key)
9688
7738
{
9689
7739
result= cursor->index_first(record);
9690
7740
if (result)
9694
7744
else
9695
7745
{
9696
7746
/* Load the first key in this group into record. */
9697
result= cursor->index_read_map(record, group_prefix,
9698
make_prev_keypart_map(group_key_parts),
9699
HA_READ_AFTER_KEY);
7747
result= cursor->index_read_map(record,
7748
group_prefix,
7749
make_prev_keypart_map(group_key_parts),
7750
HA_READ_AFTER_KEY);
9700
7751
if (result)
9701
7752
return result;
9702
7753
}
9707
7758
/* Append key_infix to group_prefix. */
9708
7759
if (key_infix_len > 0)
9709
7760
memcpy(group_prefix + group_prefix_len,
9710
key_infix, key_infix_len);
7761
key_infix,
7762
key_infix_len);
9711
7763
9712
7764
return 0;
9713
7765
}
9733
7785
HA_ERR_END_OF_FILE - "" -
9734
7786
other if some error
9735
7787
*/
9736
9737
7788
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9738
7789
{
9739
7790
ha_rkey_function find_flag;
9740
7791
key_part_map keypart_map;
9741
optimizer::QUICK_RANGE *cur_range;
7792
optimizer::QuickRange *cur_range= NULL;
9742
7793
bool found_null= false;
9743
7794
int result= HA_ERR_KEY_NOT_FOUND;
9744
7795
basic_string<unsigned char> max_key;
9756
7807
boundary of cur_range, there is no need to check this range.
9757
7808
*/
9758
7809
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9759
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
7810
(key_cmp(min_max_arg_part,
7811
(const unsigned char*) cur_range->max_key,
9760
7812
min_max_arg_len) == 1))
9761
7813
continue;
9762
7814
9768
7820
else
9769
7821
{
9770
7822
/* Extend the search key with the lower boundary for this range. */
9771
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
7823
memcpy(group_prefix + real_prefix_len,
7824
cur_range->min_key,
9772
7825
cur_range->min_length);
9773
7826
keypart_map= make_keypart_map(real_key_parts);
9774
7827
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9814
7867
}
9815
7868
9816
7869
/* If there is an upper limit, check if the found key is in the range. */
9817
if ( !(cur_range->flag & NO_MAX_RANGE) )
7870
if (! (cur_range->flag & NO_MAX_RANGE) )
9818
7871
{
9819
7872
/* Compose the MAX key for the range. */
9820
7873
max_key.clear();
9824
7877
int cmp_res= key_cmp(index_info->key_part,
9825
7878
max_key.data(),
9826
7879
real_prefix_len + min_max_arg_len);
9827
if (!(((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
9828
(cmp_res <= 0)))
7880
if (! (((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) ||
7881
(cmp_res <= 0)))
9829
7882
{
9830
7883
result= HA_ERR_KEY_NOT_FOUND;
9831
7884
continue;
9869
7922
HA_ERR_END_OF_FILE - "" -
9870
7923
other if some error
9871
7924
*/
9872
9873
7925
int optimizer::QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9874
7926
{
9875
7927
ha_rkey_function find_flag;
9876
7928
key_part_map keypart_map;
9877
optimizer::QUICK_RANGE *cur_range;
9878
int result;
7929
optimizer::QuickRange *cur_range= NULL;
7930
int result= 0;
9879
7931
basic_string<unsigned char> min_key;
9880
7932
min_key.reserve(real_prefix_len + min_max_arg_len);
9881
7933
9890
7942
boundary of cur_range, there is no need to check this range.
9891
7943
*/
9892
7944
if (range_idx != min_max_ranges.elements &&
9893
!(cur_range->flag & NO_MIN_RANGE) &&
9894
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
7945
! (cur_range->flag & NO_MIN_RANGE) &&
7946
(key_cmp(min_max_arg_part,
7947
(const unsigned char*) cur_range->min_key,
9895
7948
min_max_arg_len) == -1))
9896
7949
continue;
9897
7950
9903
7956
else
9904
7957
{
9905
7958
/* Extend the search key with the upper boundary for this range. */
9906
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
7959
memcpy(group_prefix + real_prefix_len,
7960
cur_range->max_key,
9907
7961
cur_range->max_length);
9908
7962
keypart_map= make_keypart_map(real_key_parts);
9909
7963
find_flag= (cur_range->flag & EQ_RANGE) ?
9934
7988
continue; // Row not found
9935
7989
9936
7990
/* If there is a lower limit, check if the found key is in the range. */
9937
if ( !(cur_range->flag & NO_MIN_RANGE) )
7991
if (! (cur_range->flag & NO_MIN_RANGE) )
9938
7992
{
9939
7993
/* Compose the MIN key for the range. */
9940
7994
min_key.clear();
9945
7999
int cmp_res= key_cmp(index_info->key_part,
9946
8000
min_key.data(),
9947
8001
real_prefix_len + min_max_arg_len);
9948
if (!(((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9949
(cmp_res >= 0)))
8002
if (! (((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
8003
(cmp_res >= 0)))
9950
8004
continue;
9951
8005
}
9952
8006
/* If we got to this point, the current key qualifies as MAX. */
9978
8032
RETURN
9979
8033
None
9980
8034
*/
9981
9982
8035
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9983
8036
{
9984
Item_sum *min_func;
8037
Item_sum *min_func= NULL;
9985
8038
9986
8039
min_functions_it->rewind();
9987
8040
while ((min_func= (*min_functions_it)++))
10010
8063
RETURN
10011
8064
None
10012
8065
*/
10013
10014
8066
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
10015
8067
{
10016
Item_sum *max_func;
8068
Item_sum *max_func= NULL;
10017
8069
10018
8070
max_functions_it->rewind();
10019
8071
while ((max_func= (*max_functions_it)++))
10035
8087
indexes used by a quick select.
10036
8088
10037
8089
*/
10038
10039
8090
void optimizer::QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
10040
8091
String *used_lengths)
10041
8092
{
10046
8097
used_lengths->append(buf, length);
10047
8098
}
10048
8099
10049
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
8100
static void print_sel_tree(optimizer::Parameter *param, SEL_TREE *tree, key_map *tree_map, const char *)
10050
8101
{
10051
SEL_ARG **key,**end;
10052
int idx;
8102
optimizer::SEL_ARG **key= NULL;
8103
optimizer::SEL_ARG **end= NULL;
8104
int idx= 0;
10053
8105
char buff[1024];
10054
8106
10055
8107
String tmp(buff,sizeof(buff),&my_charset_bin);
10056
8108
tmp.length(0);
10057
for (idx= 0,key=tree->keys, end=key+param->keys ;
10058
key != end ;
10059
key++,idx++)
8109
for (idx= 0, key=tree->keys, end= key + param->keys;
8110
key != end;
8111
key++, idx++)
10060
8112
{
10061
8113
if (tree_map->test(idx))
10062
8114
{
10066
8118
tmp.append(param->table->key_info[keynr].name);
10067
8119
}
10068
8120
}
10069
if (!tmp.length())
8121
if (! tmp.length())
10070
8122
tmp.append(STRING_WITH_LEN("(empty)"));
10071
8123
}
10072
8124
10073
8125
10074
8126
static void print_ror_scans_arr(Table *table,
10075
const char *, struct st_ror_scan_info **start,
8127
const char *,
8128
struct st_ror_scan_info **start,
10076
8129
struct st_ror_scan_info **end)
10077
8130
{
10078
8131
char buff[1024];
10093
8146
*****************************************************************************/
10094
8147
10095
8148
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
10096
template class List<optimizer::QUICK_RANGE>;
10097
template class List_iterator<optimizer::QUICK_RANGE>;
8149
template class List<optimizer::QuickRange>;
8150
template class List_iterator<optimizer::QuickRange>;
10098
8151
#endif
Loggerhead is a web-based interface for Breezy
Version: 2.0.1