-
Notifications
You must be signed in to change notification settings - Fork 1.6k
/
opt_range.cc
14955 lines (13017 loc) · 479 KB
/
opt_range.cc
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
/* Copyright (c) 2000, 2015, Oracle and/or its affiliates.
Copyright (c) 2008, 2015, MariaDB
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; version 2 of the License.
This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
GNU General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
/*
TODO:
Fix that MAYBE_KEY are stored in the tree so that we can detect use
of full hash keys for queries like:
select s.id, kws.keyword_id from sites as s,kws where s.id=kws.site_id and kws.keyword_id in (204,205);
*/
/*
This file contains:
RangeAnalysisModule
A module that accepts a condition, index (or partitioning) description,
and builds lists of intervals (in index/partitioning space), such that
all possible records that match the condition are contained within the
intervals.
The entry point for the range analysis module is get_mm_tree() function.
The lists are returned in form of complicated structure of interlinked
SEL_TREE/SEL_IMERGE/SEL_ARG objects.
See quick_range_seq_next, find_used_partitions for examples of how to walk
this structure.
All direct "users" of this module are located within this file, too.
PartitionPruningModule
A module that accepts a partitioned table, condition, and finds which
partitions we will need to use in query execution. Search down for
"PartitionPruningModule" for description.
The module has single entry point - prune_partitions() function.
Range/index_merge/groupby-minmax optimizer module
A module that accepts a table, condition, and returns
- a QUICK_*_SELECT object that can be used to retrieve rows that match
the specified condition, or a "no records will match the condition"
statement.
The module entry points are
test_quick_select()
get_quick_select_for_ref()
Record retrieval code for range/index_merge/groupby-min-max.
Implementations of QUICK_*_SELECT classes.
KeyTupleFormat
~~~~~~~~~~~~~~
The code in this file (and elsewhere) makes operations on key value tuples.
Those tuples are stored in the following format:
The tuple is a sequence of key part values. The length of key part value
depends only on its type (and not depends on the what value is stored)
KeyTuple: keypart1-data, keypart2-data, ...
The value of each keypart is stored in the following format:
keypart_data: [isnull_byte] keypart-value-bytes
If a keypart may have a NULL value (key_part->field->real_maybe_null() can
be used to check this), then the first byte is a NULL indicator with the
following valid values:
1 - keypart has NULL value.
0 - keypart has non-NULL value.
<questionable-statement> If isnull_byte==1 (NULL value), then the following
keypart->length bytes must be 0.
</questionable-statement>
keypart-value-bytes holds the value. Its format depends on the field type.
The length of keypart-value-bytes may or may not depend on the value being
stored. The default is that length is static and equal to
KEY_PART_INFO::length.
Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
value:
keypart-value-bytes: value_length value_bytes
The value_length part itself occupies HA_KEY_BLOB_LENGTH=2 bytes.
See key_copy() and key_restore() for code to move data between index tuple
and table record
CAUTION: the above description is only sergefp's understanding of the
subject and may omit some details.
*/
#ifdef USE_PRAGMA_IMPLEMENTATION
#pragma implementation // gcc: Class implementation
#endif
#include "mariadb.h"
#include "sql_priv.h"
#include "key.h" // is_key_used, key_copy, key_cmp, key_restore
#include "sql_parse.h" // check_stack_overrun
#include "sql_partition.h" // get_part_id_func, PARTITION_ITERATOR,
// struct partition_info, NOT_A_PARTITION_ID
#include "records.h" // init_read_record, end_read_record
#include <m_ctype.h>
#include "sql_select.h"
#include "sql_statistics.h"
#include "uniques.h"
#ifndef EXTRA_DEBUG
#define test_rb_tree(A,B) {}
#define test_use_count(A) {}
#endif
/*
Convert double value to #rows. Currently this does floor(), and we
might consider using round() instead.
*/
#define double2rows(x) ((ha_rows)(x))
/*
this should be long enough so that any memcmp with a string that
starts from '\0' won't cross is_null_string boundaries, even
if the memcmp is optimized to compare 4- 8- or 16- bytes at once
*/
static uchar is_null_string[20]= {1,0};
/**
Helper function to compare two SEL_ARG's.
*/
static bool all_same(const SEL_ARG *sa1, const SEL_ARG *sa2)
{
if (sa1 == NULL && sa2 == NULL)
return true;
if ((sa1 != NULL && sa2 == NULL) || (sa1 == NULL && sa2 != NULL))
return false;
return sa1->all_same(sa2);
}
class SEL_IMERGE;
#define CLONE_KEY1_MAYBE 1
#define CLONE_KEY2_MAYBE 2
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
/*
While objects of the class SEL_ARG represent ranges for indexes or
index infixes (including ranges for index prefixes and index suffixes),
objects of the class SEL_TREE represent AND/OR formulas of such ranges.
Currently an AND/OR formula represented by a SEL_TREE object can have
at most three levels:
<SEL_TREE formula> ::=
[ <SEL_RANGE_TREE formula> AND ]
[ <SEL_IMERGE formula> [ AND <SEL_IMERGE formula> ...] ]
<SEL_RANGE_TREE formula> ::=
<SEL_ARG formula> [ AND <SEL_ARG_formula> ... ]
<SEL_IMERGE formula> ::=
<SEL_RANGE_TREE formula> [ OR <SEL_RANGE_TREE formula> ]
As we can see from the above definitions:
- SEL_RANGE_TREE formula is a conjunction of SEL_ARG formulas
- SEL_IMERGE formula is a disjunction of SEL_RANGE_TREE formulas
- SEL_TREE formula is a conjunction of a SEL_RANGE_TREE formula
and SEL_IMERGE formulas.
It's required above that a SEL_TREE formula has at least one conjunct.
Usually we will consider normalized SEL_RANGE_TREE formulas where we use
TRUE as conjunct members for those indexes whose SEL_ARG trees are empty.
We will call an SEL_TREE object simply 'tree'.
The part of a tree that represents SEL_RANGE_TREE formula is called
'range part' of the tree while the remaining part is called 'imerge part'.
If a tree contains only a range part then we call such a tree 'range tree'.
Components of a range tree that represent SEL_ARG formulas are called ranges.
If a tree does not contain any range part we call such a tree 'imerge tree'.
Components of the imerge part of a tree that represent SEL_IMERGE formula
are called imerges.
Usually we'll designate:
SEL_TREE formulas by T_1,...,T_k
SEL_ARG formulas by R_1,...,R_k
SEL_RANGE_TREE formulas by RT_1,...,RT_k
SEL_IMERGE formulas by M_1,...,M_k
Accordingly we'll use:
t_1,...,t_k - to designate trees representing T_1,...,T_k
r_1,...,r_k - to designate ranges representing R_1,...,R_k
rt_1,...,r_tk - to designate range trees representing RT_1,...,RT_k
m_1,...,m_k - to designate imerges representing M_1,...,M_k
SEL_TREE objects are usually built from WHERE conditions or
ON expressions.
A SEL_TREE object always represents an inference of the condition it is
built from. Therefore, if a row satisfies a SEL_TREE formula it also
satisfies the condition it is built from.
The following transformations of tree t representing SEL_TREE formula T
yield a new tree t1 thar represents an inference of T: T=>T1.
(1) remove any of SEL_ARG tree from the range part of t
(2) remove any imerge from the tree t
(3) remove any of SEL_ARG tree from any range tree contained
in any imerge of tree
Since the basic blocks of any SEL_TREE objects are ranges, SEL_TREE
objects in many cases can be effectively used to filter out a big part
of table rows that do not satisfy WHERE/IN conditions utilizing
only single or multiple range index scans.
A single range index scan is constructed for a range tree that contains
only one SEL_ARG object for an index or an index prefix.
An index intersection scan can be constructed for a range tree
that contains several SEL_ARG objects. Currently index intersection
scans are constructed only for single-point ranges.
An index merge scan is constructed for a imerge tree that contains only
one imerge. If range trees of this imerge contain only single-point merges
than a union of index intersections can be built.
Usually the tree built by the range optimizer for a query table contains
more than one range in the range part, and additionally may contain some
imerges in the imerge part. The range optimizer evaluates all of them one
by one and chooses the range or the imerge that provides the cheapest
single or multiple range index scan of the table. According to rules
(1)-(3) this scan always filter out only those rows that do not satisfy
the query conditions.
For any condition the SEL_TREE object for it is built in a bottom up
manner starting from the range trees for the predicates. The tree_and
function builds a tree for any conjunction of formulas from the trees
for its conjuncts. The tree_or function builds a tree for any disjunction
of formulas from the trees for its disjuncts.
*/
class SEL_TREE :public Sql_alloc
{
public:
/*
Starting an effort to document this field:
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
(type == SEL_TREE::IMPOSSIBLE)
*/
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
SEL_TREE(enum Type type_arg, MEM_ROOT *root, size_t num_keys)
: type(type_arg), keys(root, num_keys), n_ror_scans(0)
{
keys_map.clear_all();
}
SEL_TREE(MEM_ROOT *root, size_t num_keys) :
type(KEY), keys(root, num_keys), n_ror_scans(0)
{
keys_map.clear_all();
}
SEL_TREE(SEL_TREE *arg, bool without_merges, RANGE_OPT_PARAM *param);
/*
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
merit in range analyzer functions (e.g. get_mm_parts) returning a
pointer to such SEL_TREE instead of NULL)
*/
Mem_root_array<SEL_ARG *, true> keys;
key_map keys_map; /* bitmask of non-NULL elements in keys */
/*
Possible ways to read rows using index_merge. The list is non-empty only
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
*/
List<SEL_IMERGE> merges;
/* The members below are filled/used only after get_mm_tree is done */
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
uint n_ror_scans; /* number of set bits in ror_scans_map */
struct st_index_scan_info **index_scans; /* list of index scans */
struct st_index_scan_info **index_scans_end; /* last index scan */
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
/* Note that #records for each key scan is stored in table->quick_rows */
bool without_ranges() { return keys_map.is_clear_all(); }
bool without_imerges() { return merges.is_empty(); }
};
class PARAM : public RANGE_OPT_PARAM
{
public:
ha_rows quick_rows[MAX_KEY];
/*
This will collect 'possible keys' based on the range optimization.
Queries with a JOIN object actually use ref optimizer (see add_key_field)
to collect possible_keys. This is used by single table UPDATE/DELETE.
*/
key_map possible_keys;
longlong baseflag;
uint max_key_part, range_count;
bool quick; // Don't calulate possible keys
uint fields_bitmap_size;
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
MY_BITMAP tmp_covered_fields;
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
uint *imerge_cost_buff; /* buffer for index_merge cost estimates */
uint imerge_cost_buff_size; /* size of the buffer */
/* TRUE if last checked tree->key can be used for ROR-scan */
bool is_ror_scan;
/* Number of ranges in the last checked tree->key */
uint n_ranges;
uint8 first_null_comp; /* first null component if any, 0 - otherwise */
};
class TABLE_READ_PLAN;
class TRP_RANGE;
class TRP_ROR_INTERSECT;
class TRP_ROR_UNION;
class TRP_INDEX_INTERSECT;
class TRP_INDEX_MERGE;
class TRP_GROUP_MIN_MAX;
struct st_index_scan_info;
struct st_ror_scan_info;
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8 nparts);
static ha_rows check_quick_select(PARAM *param, uint idx, bool index_only,
SEL_ARG *tree, bool update_tbl_stats,
uint *mrr_flags, uint *bufsize,
Cost_estimate *cost);
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint index,
SEL_ARG *key_tree, uint mrr_flags,
uint mrr_buf_size, MEM_ROOT *alloc);
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
bool index_read_must_be_used,
bool update_tbl_stats,
double read_time);
static
TRP_INDEX_INTERSECT *get_best_index_intersect(PARAM *param, SEL_TREE *tree,
double read_time);
static
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
double read_time,
bool *are_all_covering);
static
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
SEL_TREE *tree,
double read_time);
static
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
double read_time);
static
TABLE_READ_PLAN *merge_same_index_scans(PARAM *param, SEL_IMERGE *imerge,
TRP_INDEX_MERGE *imerge_trp,
double read_time);
static
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree,
double read_time);
#ifndef DBUG_OFF
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
const char *msg);
static void print_ror_scans_arr(TABLE *table, const char *msg,
struct st_ror_scan_info **start,
struct st_ror_scan_info **end);
static void print_quick(QUICK_SELECT_I *quick, const key_map *needed_reg);
#endif
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,
SEL_TREE *tree1, SEL_TREE *tree2);
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,
SEL_TREE *tree1,SEL_TREE *tree2);
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
static SEL_ARG *key_or(RANGE_OPT_PARAM *param,
SEL_ARG *key1, SEL_ARG *key2);
static SEL_ARG *key_and(RANGE_OPT_PARAM *param,
SEL_ARG *key1, SEL_ARG *key2,
uint clone_flag);
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
uchar *max_key,uint max_key_flag);
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
static bool null_part_in_key(KEY_PART *key_part, const uchar *key,
uint length);
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8 nparts);
#include "opt_range_mrr.cc"
static bool sel_trees_have_common_keys(SEL_TREE *tree1, SEL_TREE *tree2,
key_map *common_keys);
static void eliminate_single_tree_imerges(RANGE_OPT_PARAM *param,
SEL_TREE *tree);
static bool sel_trees_can_be_ored(RANGE_OPT_PARAM* param,
SEL_TREE *tree1, SEL_TREE *tree2,
key_map *common_keys);
static bool sel_trees_must_be_ored(RANGE_OPT_PARAM* param,
SEL_TREE *tree1, SEL_TREE *tree2,
key_map common_keys);
static int and_range_trees(RANGE_OPT_PARAM *param,
SEL_TREE *tree1, SEL_TREE *tree2,
SEL_TREE *result);
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree);
/*
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
a condition in the following form:
(t_1||t_2||...||t_N) && (next)
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
(t_i,t_j) contains SEL_ARGS for the same index.
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
This class relies on memory manager to do the cleanup.
*/
class SEL_IMERGE : public Sql_alloc
{
enum { PREALLOCED_TREES= 10};
public:
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
SEL_TREE **trees; /* trees used to do index_merge */
SEL_TREE **trees_next; /* last of these trees */
SEL_TREE **trees_end; /* end of allocated space */
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
SEL_IMERGE() :
trees(&trees_prealloced[0]),
trees_next(trees),
trees_end(trees + PREALLOCED_TREES)
{}
SEL_IMERGE (SEL_IMERGE *arg, uint cnt, RANGE_OPT_PARAM *param);
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
bool have_common_keys(RANGE_OPT_PARAM *param, SEL_TREE *tree);
int and_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree,
SEL_IMERGE *new_imerge);
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param,
uint n_init_trees,
SEL_TREE *new_tree,
bool is_first_check_pass,
bool *is_last_check_pass);
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param,
uint n_init_trees,
SEL_IMERGE* imerge,
bool is_first_check_pass,
bool *is_last_check_pass);
};
/*
Add a range tree to the range trees of this imerge
SYNOPSIS
or_sel_tree()
param Context info for the operation
tree SEL_TREE to add to this imerge
DESCRIPTION
The function just adds the range tree 'tree' to the range trees
of this imerge.
RETURN
0 if the operation is success
-1 if the function runs out memory
*/
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
{
if (trees_next == trees_end)
{
const int realloc_ratio= 2; /* Double size for next round */
size_t old_elements= (trees_end - trees);
size_t old_size= sizeof(SEL_TREE**) * old_elements;
size_t new_size= old_size * realloc_ratio;
SEL_TREE **new_trees;
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
return -1;
memcpy(new_trees, trees, old_size);
trees= new_trees;
trees_next= trees + old_elements;
trees_end= trees + old_elements * realloc_ratio;
}
*(trees_next++)= tree;
return 0;
}
/*
Check if any of the range trees of this imerge intersects with a given tree
SYNOPSIS
have_common_keys()
param Context info for the function
tree SEL_TREE intersection with the imerge range trees is checked for
DESCRIPTION
The function checks whether there is any range tree rt_i in this imerge
such that there are some indexes for which ranges are defined in both
rt_i and the range part of the SEL_TREE tree.
To check this the function calls the function sel_trees_have_common_keys.
RETURN
TRUE if there are such range trees in this imerge
FALSE otherwise
*/
bool SEL_IMERGE::have_common_keys(RANGE_OPT_PARAM *param, SEL_TREE *tree)
{
for (SEL_TREE** or_tree= trees, **bound= trees_next;
or_tree != bound; or_tree++)
{
key_map common_keys;
if (sel_trees_have_common_keys(*or_tree, tree, &common_keys))
return TRUE;
}
return FALSE;
}
/*
Perform AND operation for this imerge and the range part of a tree
SYNOPSIS
and_sel_tree()
param Context info for the operation
tree SEL_TREE for the second operand of the operation
new_imerge OUT imerge for the result of the operation
DESCRIPTION
This function performs AND operation for this imerge m and the
range part of the SEL_TREE tree rt. In other words the function
pushes rt into this imerge. The resulting imerge is returned in
the parameter new_imerge.
If this imerge m represent the formula
RT_1 OR ... OR RT_k
then the resulting imerge of the function represents the formula
(RT_1 AND RT) OR ... OR (RT_k AND RT)
The function calls the function and_range_trees to construct the
range tree representing (RT_i AND RT).
NOTE
The function may return an empty imerge without any range trees.
This happens when each call of and_range_trees returns an
impossible range tree (SEL_TREE::IMPOSSIBLE).
Example: (key1 < 2 AND key2 > 10) AND (key1 > 4 OR key2 < 6).
RETURN
0 if the operation is a success
-1 otherwise: there is not enough memory to perform the operation
*/
int SEL_IMERGE::and_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree,
SEL_IMERGE *new_imerge)
{
for (SEL_TREE** or_tree= trees; or_tree != trees_next; or_tree++)
{
SEL_TREE *res_or_tree= 0;
SEL_TREE *and_tree= 0;
if (!(res_or_tree= new SEL_TREE(param->mem_root, param->keys)) ||
!(and_tree= new SEL_TREE(tree, TRUE, param)))
return (-1);
if (!and_range_trees(param, *or_tree, and_tree, res_or_tree))
{
if (new_imerge->or_sel_tree(param, res_or_tree))
return (-1);
}
}
return 0;
}
/*
Perform OR operation on this imerge and the range part of a tree
SYNOPSIS
or_sel_tree_with_checks()
param Context info for the operation
n_trees Number of trees in this imerge to check for oring
tree SEL_TREE whose range part is to be ored
is_first_check_pass <=> the first call of the function for this imerge
is_last_check_pass OUT <=> no more calls of the function for this imerge
DESCRIPTION
The function performs OR operation on this imerge m and the range part
of the SEL_TREE tree rt. It always replaces this imerge with the result
of the operation.
The operation can be performed in two different modes: with
is_first_check_pass==TRUE and is_first_check_pass==FALSE, transforming
this imerge differently.
Given this imerge represents the formula
RT_1 OR ... OR RT_k:
1. In the first mode, when is_first_check_pass==TRUE :
1.1. If rt must be ored(see the function sel_trees_must_be_ored) with
some rt_j (there may be only one such range tree in the imerge)
then the function produces an imerge representing the formula
RT_1 OR ... OR (RT_j OR RT) OR ... OR RT_k,
where the tree for (RT_j OR RT) is built by oring the pairs
of SEL_ARG trees for the corresponding indexes
1.2. Otherwise the function produces the imerge representing the formula:
RT_1 OR ... OR RT_k OR RT.
2. In the second mode, when is_first_check_pass==FALSE :
2.1. For each rt_j in the imerge that can be ored (see the function
sel_trees_can_be_ored) with rt the function replaces rt_j for a
range tree such that for each index for which ranges are defined
in both in rt_j and rt the tree contains the result of oring of
these ranges.
2.2. In other cases the function does not produce any imerge.
When is_first_check==TRUE the function returns FALSE in the parameter
is_last_check_pass if there is no rt_j such that rt_j can be ored with rt,
but, at the same time, it's not true that rt_j must be ored with rt.
When is_first_check==FALSE the function always returns FALSE in the
parameter is_last_check_pass.
RETURN
1 The result of oring of rt_j and rt that must be ored returns the
the range tree with type==SEL_TREE::ALWAYS
(in this case the imerge m should be discarded)
-1 The function runs out of memory
0 in all other cases
*/
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param,
uint n_trees,
SEL_TREE *tree,
bool is_first_check_pass,
bool *is_last_check_pass)
{
bool was_ored= FALSE;
*is_last_check_pass= is_first_check_pass;
SEL_TREE** or_tree = trees;
for (uint i= 0; i < n_trees; i++, or_tree++)
{
SEL_TREE *result= 0;
key_map result_keys;
key_map ored_keys;
if (sel_trees_can_be_ored(param, *or_tree, tree, &ored_keys))
{
bool must_be_ored= sel_trees_must_be_ored(param, *or_tree, tree,
ored_keys);
if (must_be_ored || !is_first_check_pass)
{
result_keys.clear_all();
result= *or_tree;
for (uint key_no= 0; key_no < param->keys; key_no++)
{
if (!ored_keys.is_set(key_no))
{
result->keys[key_no]= 0;
continue;
}
SEL_ARG *key1= (*or_tree)->keys[key_no];
SEL_ARG *key2= tree->keys[key_no];
key2->incr_refs();
if ((result->keys[key_no]= key_or(param, key1, key2)))
{
result_keys.set_bit(key_no);
#ifdef EXTRA_DEBUG
if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
{
key1= result->keys[key_no];
(key1)->test_use_count(key1);
}
#endif
}
}
}
else if(is_first_check_pass)
*is_last_check_pass= FALSE;
}
if (result)
{
result->keys_map= result_keys;
if (result_keys.is_clear_all())
result->type= SEL_TREE::ALWAYS;
if ((result->type == SEL_TREE::MAYBE) ||
(result->type == SEL_TREE::ALWAYS))
return 1;
/* SEL_TREE::IMPOSSIBLE is impossible here */
*or_tree= result;
was_ored= TRUE;
}
}
if (was_ored)
return 0;
if (is_first_check_pass && !*is_last_check_pass &&
!(tree= new SEL_TREE(tree, FALSE, param)))
return (-1);
return or_sel_tree(param, tree);
}
/*
Perform OR operation on this imerge and and another imerge
SYNOPSIS
or_sel_imerge_with_checks()
param Context info for the operation
n_trees Number of trees in this imerge to check for oring
imerge The second operand of the operation
is_first_check_pass <=> the first call of the function for this imerge
is_last_check_pass OUT <=> no more calls of the function for this imerge
DESCRIPTION
For each range tree rt from 'imerge' the function calls the method
SEL_IMERGE::or_sel_tree_with_checks that performs OR operation on this
SEL_IMERGE object m and the tree rt. The mode of the operation is
specified by the parameter is_first_check_pass. Each call of
SEL_IMERGE::or_sel_tree_with_checks transforms this SEL_IMERGE object m.
The function returns FALSE in the prameter is_last_check_pass if
at least one of the calls of SEL_IMERGE::or_sel_tree_with_checks
returns FALSE as the value of its last parameter.
RETURN
1 One of the calls of SEL_IMERGE::or_sel_tree_with_checks returns 1.
(in this case the imerge m should be discarded)
-1 The function runs out of memory
0 in all other cases
*/
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param,
uint n_trees,
SEL_IMERGE* imerge,
bool is_first_check_pass,
bool *is_last_check_pass)
{
*is_last_check_pass= TRUE;
SEL_TREE** tree= imerge->trees;
SEL_TREE** tree_end= imerge->trees_next;
for ( ; tree < tree_end; tree++)
{
uint rc;
bool is_last= TRUE;
rc= or_sel_tree_with_checks(param, n_trees, *tree,
is_first_check_pass, &is_last);
if (!is_last)
*is_last_check_pass= FALSE;
if (rc)
return rc;
}
return 0;
}
/*
Copy constructor for SEL_TREE objects
SYNOPSIS
SEL_TREE
arg The source tree for the constructor
without_merges <=> only the range part of the tree arg is copied
param Context info for the operation
DESCRIPTION
The constructor creates a full copy of the SEL_TREE arg if
the prameter without_merges==FALSE. Otherwise a tree is created
that contains the copy only of the range part of the tree arg.
*/
SEL_TREE::SEL_TREE(SEL_TREE *arg, bool without_merges,
RANGE_OPT_PARAM *param)
: Sql_alloc(),
keys(param->mem_root, param->keys),
n_ror_scans(0)
{
keys_map= arg->keys_map;
type= arg->type;
MEM_ROOT *mem_root;
for (uint idx= 0; idx < param->keys; idx++)
{
if ((keys[idx]= arg->keys[idx]))
keys[idx]->incr_refs_all();
}
if (without_merges)
return;
mem_root= current_thd->mem_root;
List_iterator<SEL_IMERGE> it(arg->merges);
for (SEL_IMERGE *el= it++; el; el= it++)
{
SEL_IMERGE *merge= new (mem_root) SEL_IMERGE(el, 0, param);
if (!merge || merge->trees == merge->trees_next)
{
merges.empty();
return;
}
merges.push_back(merge, mem_root);
}
}
/*
Copy constructor for SEL_IMERGE objects
SYNOPSIS
SEL_IMERGE
arg The source imerge for the constructor
cnt How many trees from arg are to be copied
param Context info for the operation
DESCRIPTION
The cnt==0 then the constructor creates a full copy of the
imerge arg. Otherwise only the first cnt trees of the imerge
are copied.
*/
SEL_IMERGE::SEL_IMERGE(SEL_IMERGE *arg, uint cnt,
RANGE_OPT_PARAM *param) : Sql_alloc()
{
size_t elements= (arg->trees_end - arg->trees);
if (elements > PREALLOCED_TREES)
{
size_t size= elements * sizeof (SEL_TREE **);
if (!(trees= (SEL_TREE **)alloc_root(param->mem_root, size)))
goto mem_err;
}
else
trees= &trees_prealloced[0];
trees_next= trees + (cnt ? cnt : arg->trees_next-arg->trees);
trees_end= trees + elements;
for (SEL_TREE **tree = trees, **arg_tree= arg->trees; tree < trees_next;
tree++, arg_tree++)
{
if (!(*tree= new SEL_TREE(*arg_tree, TRUE, param)))
goto mem_err;
}
return;
mem_err:
trees= &trees_prealloced[0];
trees_next= trees;
trees_end= trees;
}
/*
Perform AND operation on two imerge lists
SYNOPSIS
imerge_list_and_list()
param Context info for the operation
im1 The first imerge list for the operation
im2 The second imerge list for the operation
DESCRIPTION
The function just appends the imerge list im2 to the imerge list im1
RETURN VALUE
none
*/
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
{
im1->append(im2);
}
/*
Perform OR operation on two imerge lists
SYNOPSIS
imerge_list_or_list()
param Context info for the operation
im1 The first imerge list for the operation
im2 The second imerge list for the operation
DESCRIPTION
Assuming that the first imerge list represents the formula
F1= M1_1 AND ... AND M1_k1
while the second imerge list represents the formula
F2= M2_1 AND ... AND M2_k2,
where M1_i= RT1_i_1 OR ... OR RT1_i_l1i (i in [1..k1])
and M2_i = RT2_i_1 OR ... OR RT2_i_l2i (i in [1..k2]),
the function builds a list of imerges for some formula that can be
inferred from the formula (F1 OR F2).
More exactly the function builds imerges for the formula (M1_1 OR M2_1).
Note that
(F1 OR F2) = (M1_1 AND ... AND M1_k1) OR (M2_1 AND ... AND M2_k2) =
AND (M1_i OR M2_j) (i in [1..k1], j in [1..k2]) =>
M1_1 OR M2_1.
So (M1_1 OR M2_1) is indeed an inference formula for (F1 OR F2).
To build imerges for the formula (M1_1 OR M2_1) the function invokes,
possibly twice, the method SEL_IMERGE::or_sel_imerge_with_checks
for the imerge m1_1.
At its first invocation the method SEL_IMERGE::or_sel_imerge_with_checks
performs OR operation on the imerge m1_1 and the range tree rt2_1_1 by
calling SEL_IMERGE::or_sel_tree_with_checks with is_first_pass_check==TRUE.
The resulting imerge of the operation is ored with the next range tree of
the imerge m2_1. This oring continues until the last range tree from
m2_1 has been ored.
At its second invocation the method SEL_IMERGE::or_sel_imerge_with_checks
performs the same sequence of OR operations, but now calling
SEL_IMERGE::or_sel_tree_with_checks with is_first_pass_check==FALSE.
The imerges that the operation produces replace those in the list im1
RETURN
0 if the operation is a success
-1 if the function has run out of memory
*/
int imerge_list_or_list(RANGE_OPT_PARAM *param,
List<SEL_IMERGE> *im1,
List<SEL_IMERGE> *im2)
{
uint rc;
bool is_last_check_pass= FALSE;
SEL_IMERGE *imerge= im1->head();
uint elems= (uint)(imerge->trees_next-imerge->trees);
MEM_ROOT *mem_root= current_thd->mem_root;
im1->empty();
im1->push_back(imerge, mem_root);
rc= imerge->or_sel_imerge_with_checks(param, elems, im2->head(),
TRUE, &is_last_check_pass);
if (rc)
{
if (rc == 1)
{
im1->empty();
rc= 0;
}
return rc;
}
if (!is_last_check_pass)
{
SEL_IMERGE* new_imerge= new (mem_root) SEL_IMERGE(imerge, elems, param);
if (new_imerge)
{
is_last_check_pass= TRUE;
rc= new_imerge->or_sel_imerge_with_checks(param, elems, im2->head(),
FALSE, &is_last_check_pass);
if (!rc)
im1->push_back(new_imerge, mem_root);
}
}
return rc;
}
/*
Perform OR operation for each imerge from a list and the range part of a tree
SYNOPSIS
imerge_list_or_tree()
param Context info for the operation
merges The list of imerges to be ored with the range part of tree
tree SEL_TREE whose range part is to be ored with the imerges
DESCRIPTION
For each imerge mi from the list 'merges' the function performes OR
operation with mi and the range part of 'tree' rt, producing one or
two imerges.