26
26
This file contains:
29
A module that accepts a condition, index (or partitioning) description,
30
and builds lists of intervals (in index/partitioning space), such that
31
all possible records that match the condition are contained within the
29
A module that accepts a condition, index (or partitioning) description,
30
and builds lists of intervals (in index/partitioning space), such that
31
all possible records that match the condition are contained within the
33
33
The entry point for the range analysis module is get_mm_tree() function.
35
35
The lists are returned in form of complicated structure of interlinked
36
36
SEL_TREE/SEL_IMERGE/SEL_ARG objects.
37
See quick_range_seq_next, find_used_partitions for examples of how to walk
37
See quick_range_seq_next, find_used_partitions for examples of how to walk
39
39
All direct "users" of this module are located within this file, too.
46
46
The module has single entry point - prune_partitions() function.
49
Range/index_merge/groupby-minmax optimizer module
50
A module that accepts a table, condition, and returns
49
Range/index_merge/groupby-minmax optimizer module
50
A module that accepts a table, condition, and returns
51
51
- a QUICK_*_SELECT object that can be used to retrieve rows that match
52
the specified condition, or a "no records will match the condition"
52
the specified condition, or a "no records will match the condition"
55
55
The module entry points are
65
65
The code in this file (and elsewhere) makes operations on key value tuples.
66
66
Those tuples are stored in the following format:
68
68
The tuple is a sequence of key part values. The length of key part value
69
69
depends only on its type (and not depends on the what value is stored)
71
71
KeyTuple: keypart1-data, keypart2-data, ...
73
73
The value of each keypart is stored in the following format:
75
75
keypart_data: [isnull_byte] keypart-value-bytes
77
77
If a keypart may have a NULL value (key_part->field->real_maybe_null() can
78
be used to check this), then the first byte is a NULL indicator with the
78
be used to check this), then the first byte is a NULL indicator with the
79
79
following valid values:
80
80
1 - keypart has NULL value.
81
81
0 - keypart has non-NULL value.
87
87
keypart-value-bytes holds the value. Its format depends on the field type.
88
88
The length of keypart-value-bytes may or may not depend on the value being
89
stored. The default is that length is static and equal to
89
stored. The default is that length is static and equal to
90
90
KEY_PART_INFO::length.
92
Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
92
Key parts with (key_part_flag & HA_BLOB_PART) have length depending of the
95
95
keypart-value-bytes: value_length value_bytes
97
97
The value_length part itself occupies HA_KEY_BLOB_LENGTH=2 bytes.
109
109
#include <drizzled/cost_vect.h>
110
110
#include <drizzled/item/cmpfunc.h>
111
111
#include <drizzled/field/num.h>
112
#include <drizzled/check_stack_overrun.h>
115
118
#if defined(CMATH_NAMESPACE)
116
119
using namespace CMATH_NAMESPACE;
129
132
class RANGE_OPT_PARAM;
131
134
A construction block of the SEL_ARG-graph.
133
The following description only covers graphs of SEL_ARG objects with
136
The following description only covers graphs of SEL_ARG objects with
134
137
sel_arg->type==KEY_RANGE:
136
139
One SEL_ARG object represents an "elementary interval" in form
138
141
min_value <=? table.keypartX <=? max_value
140
143
The interval is a non-empty interval of any kind: with[out] minimum/maximum
141
144
bound, [half]open/closed, single-point interval, etc.
143
146
1. SEL_ARG GRAPH STRUCTURE
145
148
SEL_ARG objects are linked together in a graph. The meaning of the graph
146
149
is better demostrated by an example:
151
154
| part=1 $ part=2 $ part=3
166
169
+-------+ $ $ +--------+
168
171
... $ $ +--------+
170
173
The entire graph is partitioned into "interval lists".
172
175
An interval list is a sequence of ordered disjoint intervals over the same
173
176
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
174
all intervals in the list form an RB-tree, linked via left/right/parent
177
all intervals in the list form an RB-tree, linked via left/right/parent
175
178
pointers. The RB-tree root SEL_ARG object will be further called "root of the
178
In the example pic, there are 4 interval lists:
181
In the example pic, there are 4 interval lists:
179
182
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
180
183
The vertical lines represent SEL_ARG::next/prev pointers.
182
185
In an interval list, each member X may have SEL_ARG::next_key_part pointer
183
186
pointing to the root of another interval list Y. The pointed interval list
184
187
must cover a key part with greater number (i.e. Y->part > X->part).
186
189
In the example pic, the next_key_part pointers are represented by
187
190
horisontal lines.
191
194
It represents a condition in a special form (we don't have a name for it ATM)
192
195
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
194
197
For example, the picture represents the condition in form:
195
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
196
(kp1=2 AND (kp3=11 OR kp3=14)) OR
198
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
199
(kp1=2 AND (kp3=11 OR kp3=14)) OR
197
200
(kp1=3 AND (kp3=11 OR kp3=14))
202
205
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
203
206
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
204
207
intervals (i.e. intervals in form
206
209
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
208
211
Those intervals can be used to access the index. The uses are in:
213
216
and create QUICK_RANGE_SELECT object that will
214
217
read records within these intervals.
216
4. SPACE COMPLEXITY NOTES
219
4. SPACE COMPLEXITY NOTES
218
221
SEL_ARG graph is a representation of an ordered disjoint sequence of
219
222
intervals over the ordered set of index tuple values.
221
224
For multi-part keys, one can construct a WHERE expression such that its
222
225
list of intervals will be of combinatorial size. Here is an example:
224
(keypart1 IN (1,2, ..., n1)) AND
225
(keypart2 IN (1,2, ..., n2)) AND
227
(keypart1 IN (1,2, ..., n1)) AND
228
(keypart2 IN (1,2, ..., n2)) AND
226
229
(keypart3 IN (1,2, ..., n3))
228
231
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
231
234
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
233
236
SEL_ARG graph structure aims to reduce the amount of required space by
234
237
"sharing" the elementary intervals when possible (the pic at the
235
beginning of this comment has examples of such sharing). The sharing may
238
beginning of this comment has examples of such sharing). The sharing may
236
239
prevent combinatorial blowup:
238
241
There are WHERE clauses that have combinatorial-size interval lists but
239
242
will be represented by a compact SEL_ARG graph.
241
(keypartN IN (1,2, ..., n1)) AND
244
(keypartN IN (1,2, ..., n1)) AND
243
(keypart2 IN (1,2, ..., n2)) AND
246
(keypart2 IN (1,2, ..., n2)) AND
244
247
(keypart1 IN (1,2, ..., n3))
246
249
but not in all cases:
249
252
representation but get_mm_tree() and its callees will construct a
250
253
graph of combinatorial size.
252
(keypart1 IN (1,2, ..., n1)) AND
253
(keypart2 IN (1,2, ..., n2)) AND
255
(keypart1 IN (1,2, ..., n1)) AND
256
(keypart2 IN (1,2, ..., n2)) AND
255
258
(keypartN IN (1,2, ..., n3))
260
263
By induction: Let's take any interval on some keypart in the middle:
264
267
Then let's AND it with this interval 'structure' from preceding and
265
268
following keyparts:
267
270
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
269
272
We will obtain this SEL_ARG graph:
271
274
kp14 $ kp15 $ kp16
273
276
+---------+ $ +---------+ $ +---------+
274
277
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
275
278
+---------+ $ +---------+ $ +---------+
277
+---------+ $ +---------+ $
278
| kp14=c2 |--$-->| kp15=c0 | $
279
+---------+ $ +---------+ $
280
+---------+ $ +---------+ $
281
| kp14=c2 |--$-->| kp15=c0 | $
282
+---------+ $ +---------+ $
282
285
Note that we had to duplicate "kp15=c0" and there was no way to avoid
284
287
The induction step: AND the obtained expression with another "wrapping"
285
288
expression like (*).
286
When the process ends because of the limit on max. number of keyparts
289
When the process ends because of the limit on max. number of keyparts
289
292
WHERE clause length is O(3*#max_keyparts)
324
327
SEL_ARG *left,*right; /* R-B tree children */
325
328
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
326
329
SEL_ARG *parent; /* R-B tree parent */
327
SEL_ARG *next_key_part;
330
SEL_ARG *next_key_part;
328
331
enum leaf_color { BLACK,RED } color;
329
332
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
350
353
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
351
354
inline void maybe_smaller() { maybe_flag=1; }
352
355
/* Return true iff it's a single-point null interval */
353
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
356
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
354
357
inline int cmp_min_to_min(SEL_ARG* arg)
356
359
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
487
490
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
488
491
range_key, *range_key_flag);
489
492
*range_key_flag|= key_tree->min_flag;
491
494
if (key_tree->next_key_part &&
492
495
key_tree->next_key_part->part == key_tree->part+1 &&
493
496
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
609
612
Starting an effort to document this field:
610
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
613
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
611
614
(type == SEL_TREE::IMPOSSIBLE)
613
616
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
661
664
#keys elements are not empty)
666
669
If true, the index descriptions describe real indexes (and it is ok to
667
670
call field->optimize_range(real_keynr[...], ...).
668
671
Otherwise index description describes fake indexes.
670
673
bool using_real_indexes;
672
675
bool remove_jump_scans;
675
678
used_key_no -> table_key_no translation table. Only makes sense if
676
679
using_real_indexes==true
678
681
uint32_t real_keynr[MAX_KEY];
679
682
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
680
uint32_t alloced_sel_args;
683
uint32_t alloced_sel_args;
681
684
bool force_default_mrr;
728
731
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
729
732
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
730
SEL_ARG *tree, bool update_tbl_stats,
733
SEL_ARG *tree, bool update_tbl_stats,
731
734
uint32_t *mrr_flags, uint32_t *bufsize,
732
735
COST_VECT *cost);
733
736
//bool update_tbl_stats);
739
742
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
740
SEL_ARG *key_tree, uint32_t mrr_flags,
743
SEL_ARG *key_tree, uint32_t mrr_flags,
741
744
uint32_t mrr_buf_size, MEM_ROOT *alloc);
742
745
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
743
746
bool index_read_must_be_used,
1016
1019
if (!conds && !allow_null_cond)
1018
1021
if (!(select= new SQL_SELECT))
1020
1023
*error= 1; // out of memory
1021
return(0); /* purecov: inspected */
1024
return 0; /* purecov: inspected */
1023
1026
select->read_tables=read_tables;
1024
1027
select->const_tables=const_tables;
1305
1307
/* already have own 'handler' object. */
1309
1311
session= head->in_use;
1310
1312
if (!(file= head->file->clone(session->mem_root)))
1313
1315
Manually set the error flag. Note: there seems to be quite a few
1314
1316
places where a failure could cause the server to "hang" the client by
1315
sending no response to a query. ATM those are not real errors because
1316
the storage engine calls in question happen to never fail with the
1317
existing storage engines.
1317
sending no response to a query. ATM those are not real errors because
1318
the storage engine calls in question happen to never fail with the
1319
existing storage engines.
1319
1321
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1320
1322
/* Caller will free the memory */
1398
1400
if (quick->init_ror_merged_scan(true))
1400
1402
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1402
1404
while ((quick= quick_it++))
1404
1406
if (quick->init_ror_merged_scan(false))
1406
1408
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1407
1409
/* All merged scans share the same record buffer in intersection. */
1408
1410
quick->record= head->record[0];
1823
1825
KEY_PART_INFO *keyinfo= table->key_info[idx].key_part;
1824
1826
uint32_t n_parts= table->key_info[idx].key_parts;
1825
1827
uint32_t partno= 0;
1828
The below check is sufficient considering we now have either BTREE
1829
indexes (records are returned in order for any index prefix) or HASH
1830
The below check is sufficient considering we now have either BTREE
1831
indexes (records are returned in order for any index prefix) or HASH
1830
1832
indexes (records are not returned in order for any index prefix).
1832
1834
if (!(table->file->index_flags(idx, 0, 1) & HA_READ_ORDER))
1838
1840
((Item_field*)item)->field->eq(keyinfo[partno].field)))
1842
1844
if (!ord && table->key_info[idx].key_length < match_key_len)
1845
1847
Ok, the ordering is compatible and this key is shorter then
1846
1848
previous match (we want shorter keys as we'll have to read fewer
1847
1849
index pages for the same number of records)
1910
1912
/* Table read plans are allocated on MEM_ROOT and are never deleted */
1911
1913
static void *operator new(size_t size, MEM_ROOT *mem_root)
1912
1914
{ return (void*) alloc_root(mem_root, (uint) size); }
1913
static void operator delete(void *ptr __attribute__((unused)),
1914
size_t size __attribute__((unused)))
1915
static void operator delete(void *, size_t)
1915
1916
{ TRASH(ptr, size); }
1916
static void operator delete(void *ptr __attribute__((unused)),
1917
MEM_ROOT *mem_root __attribute__((unused)))
1917
static void operator delete(void *, MEM_ROOT *)
1918
1918
{ /* Never called */ }
1919
1919
virtual ~TABLE_READ_PLAN() {} /* Remove gcc warning */
1946
1946
virtual ~TRP_RANGE() {} /* Remove gcc warning */
1948
QUICK_SELECT_I *make_quick(PARAM *param,
1949
bool retrieve_full_rows __attribute__((unused)),
1950
MEM_ROOT *parent_alloc)
1948
QUICK_SELECT_I *make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
1952
1950
QUICK_RANGE_SELECT *quick;
1953
1951
if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
2135
2133
quick_condition_rows value is obtained as follows:
2137
2135
It is a minimum of E(#output rows) for all considered table access
2138
2136
methods (range and index_merge accesses over various indexes).
2140
2138
The obtained value is not a true E(#rows that satisfy table condition)
2141
2139
but rather a pessimistic estimate. To obtain a true E(#...) one would
2142
2140
need to combine estimates of various access methods, taking into account
2143
2141
correlations between sets of rows they will return.
2145
2143
For example, if values of tbl.key1 and tbl.key2 are independent (a right
2146
2144
assumption if we have no information about their correlation) then the
2147
2145
correct estimate will be:
2149
E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
2147
E(#rows("tbl.key1 < c1 AND tbl.key2 < c2")) =
2150
2148
= E(#rows(tbl.key1 < c1)) / total_rows(tbl) * E(#rows(tbl.key2 < c2)
2152
which is smaller than
2150
which is smaller than
2154
2152
MIN(E(#rows(tbl.key1 < c1), E(#rows(tbl.key2 < c2)))
2156
2154
which is currently produced.
2159
2157
* Change the value returned in quick_condition_rows from a pessimistic
2160
estimate to true E(#rows that satisfy table condition).
2161
(we can re-use some of E(#rows) calcuation code from index_merge/intersection
2158
estimate to true E(#rows that satisfy table condition).
2159
(we can re-use some of E(#rows) calcuation code from index_merge/intersection
2164
2162
* Check if this function really needs to modify keys_to_use, and change the
2165
2163
code to pass it by reference if it doesn't.
2177
2175
int SQL_SELECT::test_quick_select(Session *session, key_map keys_to_use,
2178
2176
table_map prev_tables,
2179
ha_rows limit, bool force_quick_range,
2177
ha_rows limit, bool force_quick_range,
2180
2178
bool ordered_output)
2197
2195
if (limit < records)
2198
2196
read_time= (double) records + scan_time + 1; // Force to use index
2199
2197
else if (read_time <= 2.0 && !force_quick_range)
2200
return(0); /* No need for quick select */
2198
return 0; /* No need for quick select */
2202
2200
keys_to_use.intersect(head->keys_in_use_for_query);
2203
2201
if (!keys_to_use.is_clear_all())
2237
2235
session->no_errors=0;
2238
2236
free_root(&alloc,MYF(0)); // Return memory & allocator
2239
return(0); // Can't use range
2237
return 0; // Can't use range
2241
2239
key_parts= param.key_parts;
2242
2240
session->mem_root= &alloc;
2276
2274
if (!head->covering_keys.is_clear_all())
2278
2276
int key_for_use= head->find_shortest_key(&head->covering_keys);
2279
double key_read_time=
2280
param.table->file->index_only_read_time(key_for_use,
2277
double key_read_time=
2278
param.table->file->index_only_read_time(key_for_use,
2281
2279
rows2double(records)) +
2282
2280
(double) records / TIME_FOR_COMPARE;
2283
2281
if (key_read_time < read_time)
2381
2379
new_conj_trp= get_best_disjunct_quick(¶m, imerge, best_read_time);
2382
2380
if (new_conj_trp)
2383
set_if_smaller(param.table->quick_condition_rows,
2381
set_if_smaller(param.table->quick_condition_rows,
2384
2382
new_conj_trp->records);
2385
2383
if (!best_conj_trp || (new_conj_trp && new_conj_trp->read_cost <
2386
2384
best_conj_trp->read_cost))
2775
2773
if (!(bitmap_buf= (my_bitmap_map*) alloc_root(param->mem_root,
2776
2774
param->fields_bitmap_size)))
2779
2777
if (bitmap_init(&ror_scan->covered_fields, bitmap_buf,
2780
2778
param->table->s->fields, false))
2782
2780
bitmap_clear_all(&ror_scan->covered_fields);
2784
2782
KEY_PART_INFO *key_part= param->table->key_info[keynr].key_part;
2909
2907
void ror_intersect_cpy(ROR_INTERSECT_INFO *dst, const ROR_INTERSECT_INFO *src)
2911
2909
dst->param= src->param;
2912
memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
2910
memcpy(dst->covered_fields.bitmap, src->covered_fields.bitmap,
2913
2911
no_bytes_in_map(&src->covered_fields));
2914
2912
dst->out_rows= src->out_rows;
2915
2913
dst->is_covering= src->is_covering;
3009
3007
Selectivity of given ROR scan.
3012
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
3010
static double ror_scan_selectivity(const ROR_INTERSECT_INFO *info,
3013
3011
const ROR_SCAN_INFO *scan)
3015
3013
double selectivity_mult= 1.0;
3112
3110
E(rows_to_retrieve) = #rows_in_table * ror_scan_selectivity(null, scan1) *
3113
3111
ror_scan_selectivity({scan1}, scan2) * ... *
3114
ror_scan_selectivity({scan1,...}, scanN).
3112
ror_scan_selectivity({scan1,...}, scanN).
3116
3114
true ROR scan added to ROR-intersection, cost updated.
3117
3115
false It doesn't make sense to add this ROR scan to this ROR-intersection.
3126
3124
if (selectivity_mult == 1.0)
3128
3126
/* Don't add this scan if it doesn't improve selectivity. */
3132
3130
info->out_rows *= selectivity_mult;
3134
3132
if (is_cpk_scan)
3137
CPK scan is used to filter out rows. We apply filtering for
3135
CPK scan is used to filter out rows. We apply filtering for
3138
3136
each record of every scan. Assuming 1/TIME_FOR_COMPARE_ROWID
3139
3137
per check this gives us:
3141
info->index_scan_costs += rows2double(info->index_records) /
3139
info->index_scan_costs += rows2double(info->index_records) /
3142
3140
TIME_FOR_COMPARE_ROWID;
3240
3238
double min_cost= DBL_MAX;
3242
3240
if ((tree->n_ror_scans < 2) || !param->table->file->stats.records)
3246
Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
3244
Step1: Collect ROR-able SEL_ARGs and create ROR_SCAN_INFO for each of
3247
3245
them. Also find and save clustered PK scan if there is one.
3249
3247
ROR_SCAN_INFO **cur_ror_scan;
3300
3298
/* Create and incrementally update ROR intersection. */
3301
3299
ROR_INTERSECT_INFO *intersect, *intersect_best;
3302
if (!(intersect= ror_intersect_init(param)) ||
3300
if (!(intersect= ror_intersect_init(param)) ||
3303
3301
!(intersect_best= ror_intersect_init(param)))
3345
3343
Ok, found the best ROR-intersection of non-CPK key scans.
3346
Check if we should add a CPK scan. If the obtained ROR-intersection is
3344
Check if we should add a CPK scan. If the obtained ROR-intersection is
3347
3345
covering, it doesn't make sense to add CPK scan.
3349
3347
if (cpk_scan && !intersect->is_covering)
3351
if (ror_intersect_add(intersect, cpk_scan, true) &&
3349
if (ror_intersect_add(intersect, cpk_scan, true) &&
3352
3350
(intersect->total_cost < min_cost))
3354
3352
cpk_scan_used= true;
3365
3363
if (!(trp->first_scan=
3366
3364
(ROR_SCAN_INFO**)alloc_root(param->mem_root,
3367
3365
sizeof(ROR_SCAN_INFO*)*best_num)))
3369
3367
memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
3370
3368
trp->last_scan= trp->first_scan + best_num;
3371
3369
trp->is_covering= intersect_best->is_covering;
3437
3435
ror_scan_mark= tree->ror_scans;
3439
3437
MY_BITMAP *covered_fields= ¶m->tmp_covered_fields;
3440
if (!covered_fields->bitmap)
3438
if (!covered_fields->bitmap)
3441
3439
covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3442
3440
param->fields_bitmap_size);
3443
3441
if (!covered_fields->bitmap ||
3444
3442
bitmap_init(covered_fields, covered_fields->bitmap,
3445
3443
param->table->s->fields, false))
3447
3445
bitmap_clear_all(covered_fields);
3449
3447
double total_cost= 0.0f;
3481
3479
total_cost += (*ror_scan_mark)->index_read_cost;
3482
3480
records += (*ror_scan_mark)->records;
3483
3481
if (total_cost > read_time)
3485
3483
/* F=F-covered by first(I) */
3486
3484
bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3487
3485
all_covered= bitmap_is_subset(¶m->needed_fields, covered_fields);
3488
3486
} while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3490
3488
if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
3494
3492
Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
3513
3511
if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3514
3512
sizeof(ROR_SCAN_INFO*)*
3517
3515
memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
3518
3516
trp->last_scan= trp->first_scan + best_num;
3519
3517
trp->is_covering= true;
3520
3518
trp->read_cost= total_cost;
3521
3519
trp->records= records;
3522
3520
trp->cpk_scan= NULL;
3523
set_if_smaller(param->table->quick_condition_rows, records);
3521
set_if_smaller(param->table->quick_condition_rows, records);
3537
3535
(except for clustered PK indexes)
3538
3536
update_tbl_stats true <=> update table->quick_* with information
3539
3537
about range scans we've evaluated.
3540
read_time Maximum cost. i.e. don't create read plans with
3538
read_time Maximum cost. i.e. don't create read plans with
3541
3539
cost > read_time.
3544
Find the best "range" table read plan for given SEL_TREE.
3545
The side effects are
3542
Find the best "range" table read plan for given SEL_TREE.
3543
The side effects are
3546
3544
- tree->ror_scans is updated to indicate which scans are ROR scans.
3547
3545
- if update_tbl_stats=true then table->quick_* is updated with info
3548
3546
about every possible range scan.
3583
3581
(*key)->maybe_flag)
3584
3582
param->needed_reg->set_bit(keynr);
3586
bool read_index_only= index_read_must_be_used ||
3584
bool read_index_only= index_read_must_be_used ||
3587
3585
param->table->covering_keys.is_set(keynr);
3589
3587
found_records= check_quick_select(param, idx, read_index_only, *key,
3627
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param,
3628
bool retrieve_full_rows __attribute__((unused)),
3629
MEM_ROOT *parent_alloc __attribute__((unused)))
3625
QUICK_SELECT_I *TRP_INDEX_MERGE::make_quick(PARAM *param, bool, MEM_ROOT *)
3631
3627
QUICK_INDEX_MERGE_SELECT *quick_imerge;
3632
3628
QUICK_RANGE_SELECT *quick;
3704
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param,
3705
bool retrieve_full_rows __attribute__((unused)),
3706
MEM_ROOT *parent_alloc __attribute__((unused)))
3700
QUICK_SELECT_I *TRP_ROR_UNION::make_quick(PARAM *param, bool, MEM_ROOT *)
3708
3702
QUICK_ROR_UNION_SELECT *quick_roru;
3709
3703
TABLE_READ_PLAN **scan;
3739
3733
gt_value constant that field should be greaterr
3740
3734
cmp_type compare type for the field
3743
3737
# Pointer to tree built tree
3747
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3741
static SEL_TREE *get_ne_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3749
3743
Item *lt_value, Item *gt_value,
3750
3744
Item_result cmp_type)
3773
3767
value constant in the predicate
3774
3768
cmp_type compare type for the field
3775
3769
inv true <> NOT cond_func is considered
3776
(makes sense only when cond_func is BETWEEN or IN)
3770
(makes sense only when cond_func is BETWEEN or IN)
3779
3773
Pointer to the tree built tree
3782
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3776
static SEL_TREE *get_func_mm_tree(RANGE_OPT_PARAM *param, Item_func *cond_func,
3783
3777
Field *field, Item *value,
3784
3778
Item_result cmp_type, bool inv)
3843
3837
We get here for conditions in form "t.key NOT IN (c1, c2, ...)",
3844
where c{i} are constants. Our goal is to produce a SEL_TREE that
3838
where c{i} are constants. Our goal is to produce a SEL_TREE that
3845
3839
represents intervals:
3847
3841
($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR ... (*)
3849
3843
where $MIN is either "-inf" or NULL.
3851
3845
The most straightforward way to produce it is to convert NOT IN
3852
3846
into "(t.key != c1) AND (t.key != c2) AND ... " and let the range
3853
3847
analyzer to build SEL_TREE from that. The problem is that the
3858
3852
Another problem with big lists like (*) is that a big list is
3859
3853
unlikely to produce a good "range" access, while considering that
3860
range access will require expensive CPU calculations (and for
3854
range access will require expensive CPU calculations (and for
3861
3855
MyISAM even index accesses). In short, big NOT IN lists are rarely
3862
3856
worth analyzing.
3886
3880
/* Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval. */
3890
3884
func->array->value_to_item(i, value_item);
3891
3885
tree= get_mm_parts(param, cond_func, field, Item_func::LT_FUNC,
3928
3922
new_interval->min_flag= NEAR_MIN;
3932
3926
The following doesn't try to allocate memory so no need to
3933
3927
check for NULL.
3935
3929
tree= tree_or(param, tree, tree2);
3939
3933
if (tree && tree->type != SEL_TREE::IMPOSSIBLE)
3942
Get the SEL_TREE for the last "c_last < X < +inf" interval
3936
Get the SEL_TREE for the last "c_last < X < +inf" interval
3943
3937
(value_item cotains c_last already)
3945
3939
tree2= get_mm_parts(param, cond_func, field, Item_func::GT_FUNC,
3958
3952
for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3959
3953
arg < end ; arg++)
3961
tree= tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
3955
tree= tree_and(param, tree, get_ne_mm_tree(param, cond_func, field,
3962
3956
*arg, *arg, cmp_type));
3969
3963
tree= get_mm_parts(param, cond_func, field, Item_func::EQ_FUNC,
3970
3964
func->arguments()[1], cmp_type);
3974
3968
for (arg= func->arguments()+2, end= arg+func->argument_count()-2;
3975
3969
arg < end ; arg++)
3977
tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3971
tree= tree_or(param, tree, get_mm_parts(param, cond_func, field,
3978
3972
Item_func::EQ_FUNC,
3979
3973
*arg, cmp_type));
3988
3982
Here the function for the following predicates are processed:
3989
3983
<, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL.
3990
3984
If the predicate is of the form (value op field) it is handled
4012
4006
field_item field in the predicate
4013
4007
value constant in the predicate
4014
4008
(for BETWEEN it contains the number of the field argument,
4015
for IN it's always 0)
4009
for IN it's always 0)
4016
4010
inv true <> NOT cond_func is considered
4017
4011
(makes sense only when cond_func is BETWEEN or IN)
4021
4015
c is a constant, the function builds a conjunction of all SEL_TREES that can
4022
4016
be obtained by the substitution of f for all different fields equal to f.
4025
4019
If the WHERE condition contains a predicate (fi op c),
4026
4020
then not only SELL_TREE for this predicate is built, but
4027
4021
the trees for the results of substitution of fi for
4028
4022
each fj belonging to the same multiple equality as fi
4029
4023
are built as well.
4030
E.g. for WHERE t1.a=t2.a AND t2.a > 10
4024
E.g. for WHERE t1.a=t2.a AND t2.a > 10
4031
4025
a SEL_TREE for t2.a > 10 will be built for quick select from t2
4033
4027
a SEL_TREE for t1.a > 10 will be built for quick select from t1.
4035
4029
A BETWEEN predicate of the form (fi [NOT] BETWEEN c1 AND c2) is treated
4038
4032
Yet a predicate of the form (c BETWEEN f1i AND f2i) is processed
4039
4033
differently. It is considered as a conjuction of two SARGable
4040
4034
predicates (f1i <= c) and (f2i <=c) and the function get_full_func_mm_tree
4041
is called for each of them separately producing trees for
4042
AND j (f1j <=c ) and AND j (f2j <= c)
4035
is called for each of them separately producing trees for
4036
AND j (f1j <=c ) and AND j (f2j <= c)
4043
4037
After this these two trees are united in one conjunctive tree.
4044
4038
It's easy to see that the same tree is obtained for
4045
4039
AND j,k (f1j <=c AND f2k<=c)
4046
which is equivalent to
4040
which is equivalent to
4047
4041
AND j,k (c BETWEEN f1j AND f2k).
4048
4042
The validity of the processing of the predicate (c NOT BETWEEN f1i AND f2i)
4049
4043
which equivalent to (f1i > c OR f2i < c) is not so obvious. Here the
4050
4044
function get_full_func_mm_tree is called for (f1i > c) and (f2i < c)
4051
4045
producing trees for AND j (f1j > c) and AND j (f2j < c). Then this two
4052
trees are united in one OR-tree. The expression
4046
trees are united in one OR-tree. The expression
4053
4047
(AND j (f1j > c) OR AND j (f2j < c)
4054
4048
is equivalent to the expression
4055
AND j,k (f1j > c OR f2k < c)
4056
which is just a translation of
4049
AND j,k (f1j > c OR f2k < c)
4050
which is just a translation of
4057
4051
AND j,k (c NOT BETWEEN f1j AND f2k)
4059
4053
In the cases when one of the items f1, f2 is a constant c1 we do not create
4066
4060
As to IN predicates only ones of the form (f IN (c1,...,cn)),
4067
4061
where f1 is a field and c1,...,cn are constant, are considered as
4068
4062
SARGable. We never try to narrow the index scan using predicates of
4069
the form (c IN (c1,...,f,...,cn)).
4063
the form (c IN (c1,...,f,...,cn)).
4072
4066
Pointer to the tree representing the built conjunction of SEL_TREEs
4075
4069
static SEL_TREE *get_full_func_mm_tree(RANGE_OPT_PARAM *param,
4076
4070
Item_func *cond_func,
4077
Item_field *field_item, Item *value,
4071
Item_field *field_item, Item *value,
4080
4074
SEL_TREE *tree= 0;
4134
4128
while ((item=li++))
4136
4130
SEL_TREE *new_tree=get_mm_tree(param,item);
4137
if (param->session->is_fatal_error ||
4131
if (param->session->is_fatal_error ||
4138
4132
param->alloced_sel_args > SEL_ARG::MAX_SEL_ARGS)
4139
return(0); // out of memory
4133
return 0; // out of memory
4140
4134
tree=tree_and(param,tree,new_tree);
4141
4135
if (tree && tree->type == SEL_TREE::IMPOSSIBLE)
4153
4147
SEL_TREE *new_tree=get_mm_tree(param,item);
4155
return(0); // out of memory
4149
return 0; // out of memory
4156
4150
tree=tree_or(param,tree,new_tree);
4157
4151
if (!tree || tree->type == SEL_TREE::ALWAYS)
4165
4159
if (cond->const_item())
4168
During the cond->val_int() evaluation we can come across a subselect
4169
item which may allocate memory on the session->mem_root and assumes
4170
all the memory allocated has the same life span as the subselect
4162
During the cond->val_int() evaluation we can come across a subselect
4163
item which may allocate memory on the session->mem_root and assumes
4164
all the memory allocated has the same life span as the subselect
4171
4165
item itself. So we have to restore the thread's mem_root here.
4173
4167
MEM_ROOT *tmp_root= param->mem_root;
4216
4210
if (cond_func->arguments()[i]->real_item()->type() == Item::FIELD_ITEM)
4218
4212
field_item= (Item_field*) (cond_func->arguments()[i]->real_item());
4219
SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
4213
SEL_TREE *tmp= get_full_func_mm_tree(param, cond_func,
4220
4214
field_item, (Item*)(intptr_t)i, inv);
4222
4216
tree= !tree ? tmp : tree_or(param, tree, tmp);
4224
4218
tree= tree_and(param, tree, tmp);
4237
4231
Item_func_in *func=(Item_func_in*) cond_func;
4238
4232
if (func->key_item()->real_item()->type() != Item::FIELD_ITEM)
4240
4234
field_item= (Item_field*) (func->key_item()->real_item());
4241
4235
ftree= get_full_func_mm_tree(param, cond_func, field_item, NULL, inv);
4244
4238
case Item_func::MULT_EQUAL_FUNC:
4246
Item_equal *item_equal= (Item_equal *) cond;
4240
Item_equal *item_equal= (Item_equal *) cond;
4247
4241
if (!(value= item_equal->get_const()))
4249
4243
Item_equal_iterator it(*item_equal);
4250
4244
ref_tables= value->used_tables();
4251
4245
while ((field_item= it++))
4287
4281
static SEL_TREE *
4288
4282
get_mm_parts(RANGE_OPT_PARAM *param, COND *cond_func, Field *field,
4289
4283
Item_func::Functype type,
4291
Item_result cmp_type __attribute__((unused)))
4284
Item *value, Item_result)
4293
4286
if (field->table != param->table)
4296
4289
KEY_PART *key_part = param->key_parts;
4297
4290
KEY_PART *end = param->key_parts_end;
4298
4291
SEL_TREE *tree=0;
4300
4293
value->used_tables() & ~(param->prev_tables | param->read_tables))
4302
4295
for (; key_part != end ; key_part++)
4304
4297
if (field->eq(key_part->field))
4306
4299
SEL_ARG *sel_arg=0;
4307
4300
if (!tree && !(tree=new SEL_TREE()))
4309
4302
if (!value || !(value->used_tables() & ~param->read_tables))
4311
4304
sel_arg=get_mm_leaf(param,cond_func,
4323
4316
// This key may be used later
4324
4317
if (!(sel_arg= new SEL_ARG(SEL_ARG::MAYBE_KEY)))
4327
4320
sel_arg->part=(unsigned char) key_part->part;
4328
4321
tree->keys[key_part->key]=sel_add(tree->keys[key_part->key],sel_arg);
4329
4322
tree->keys_map.set_bit(key_part->key);
4528
4521
but a non-zero time part was cut off.
4530
4523
In MySQL's SQL dialect, DATE and DATETIME are compared as datetime
4531
values. Index over a DATE column uses DATE comparison. Changing
4524
values. Index over a DATE column uses DATE comparison. Changing
4532
4525
from one comparison to the other is possible:
4534
4527
datetime(date_col)< '2007-12-10 12:34:55' -> date_col<='2007-12-10'
4767
4760
using index_merge.
4770
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4763
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4771
4764
RANGE_OPT_PARAM* param)
4773
4766
key_map common_keys= tree1->keys_map;
4774
4767
common_keys.intersect(tree2->keys_map);
4776
4769
if (common_keys.is_clear_all())
4779
4772
/* trees have a common key, check if they refer to same key part */
4780
4773
SEL_ARG **key1,**key2;
4811
4804
tree->part != 0. (e.g. it could represent "keypart2 < const").
4813
4806
WHY THIS FUNCTION IS NEEDED
4815
4808
Normally we allow construction of SEL_TREE objects that have SEL_ARG
4816
4809
trees that do not allow quick range select construction. For example for
4817
4810
" keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4821
4814
call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4824
4817
There is an exception though: when we construct index_merge SEL_TREE,
4825
4818
any SEL_ARG* tree that cannot be used to construct quick range select can
4826
4819
be removed, because current range analysis code doesn't provide any way
4827
4820
that tree could be later combined with another tree.
4828
4821
Consider an example: we should not construct
4830
merges = SEL_IMERGE {
4831
SEL_TREE(t.key1part1 = 1),
4823
merges = SEL_IMERGE {
4824
SEL_TREE(t.key1part1 = 1),
4832
4825
SEL_TREE(t.key2part2 = 2) -- (*)
4836
- (*) cannot be used to construct quick range select,
4837
- There is no execution path that would cause (*) to be converted to
4829
- (*) cannot be used to construct quick range select,
4830
- There is no execution path that would cause (*) to be converted to
4838
4831
a tree that could be used.
4840
4833
The latter is easy to verify: first, notice that the only way to convert
4841
4834
(*) into a usable tree is to call tree_and(something, (*)).
4843
4836
Second look at what tree_and/tree_or function would do when passed a
4844
SEL_TREE that has the structure like st1 tree has, and conlcude that
4837
SEL_TREE that has the structure like st1 tree has, and conlcude that
4845
4838
tree_and(something, (*)) will not be called.
4941
4934
/* one tree is index merge tree and another is range tree */
4942
4935
if (tree1->merges.is_empty())
4943
4936
std::swap(tree1, tree2);
4945
4938
if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
4946
4939
return(new SEL_TREE(SEL_TREE::ALWAYS));
4947
4940
/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
4958
4951
/* And key trees where key1->part < key2 -> part */
4960
4953
static SEL_ARG *
4961
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4954
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
4962
4955
uint32_t clone_flag)
5059
5052
if (key1->type == SEL_ARG::MAYBE_KEY)
5060
5053
{ // Both are maybe key
5061
key1->next_key_part=key_and(param, key1->next_key_part,
5054
key1->next_key_part=key_and(param, key1->next_key_part,
5062
5055
key2->next_key_part, clone_flag);
5063
5056
if (key1->next_key_part &&
5064
5057
key1->next_key_part->type == SEL_ARG::IMPOSSIBLE)
5564
5557
if (root == &null_element)
5565
return(0); // Maybe root later
5558
return 0; // Maybe root later
5566
5559
if (remove_color == BLACK)
5567
5560
root=rb_delete_fixup(root,nod,fix_par);
5568
5561
#ifdef EXTRA_DEBUG
5762
5755
return 0; // Found end of tree
5763
5756
if (element->parent != parent)
5765
sql_print_error("Wrong tree: Parent doesn't point at parent");
5758
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Parent doesn't point at parent");
5768
5761
if (element->color == SEL_ARG::RED &&
5769
5762
(element->left->color == SEL_ARG::RED ||
5770
5763
element->right->color == SEL_ARG::RED))
5772
sql_print_error("Wrong tree: Found two red in a row");
5765
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found two red in a row");
5775
5768
if (element->left == element->right && element->left != &null_element)
5776
5769
{ // Dummy test
5777
sql_print_error("Wrong tree: Found right == left");
5770
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Found right == left");
5780
5773
count_l=test_rb_tree(element->left,element);
5784
5777
if (count_l == count_r)
5785
5778
return count_l+(element->color == SEL_ARG::BLACK);
5786
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5779
errmsg_printf(ERRMSG_LVL_ERROR, "Wrong tree: Incorrect black-count: %d - %d",
5787
5780
count_l,count_r);
5789
5782
return -1; // Error, no more warnings
5805
5798
This function counts how many times the node "key" is referred (via
5806
SEL_ARG::next_key_part) by
5807
- intervals of RB-tree pointed by "root",
5808
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5799
SEL_ARG::next_key_part) by
5800
- intervals of RB-tree pointed by "root",
5801
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5809
5802
intervals of RB-tree pointed by "root",
5812
Here is an example (horizontal links represent next_key_part pointers,
5813
vertical links - next/prev prev pointers):
5805
Here is an example (horizontal links represent next_key_part pointers,
5806
vertical links - next/prev prev pointers):
5816
5809
|root|-----------------+
5870
5863
uint32_t e_count=0;
5871
5864
if (this == root && use_count != 1)
5873
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5866
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count %lu for root",use_count);
5876
5869
if (this->type != SEL_ARG::KEY_RANGE)
5883
5876
ulong count=count_key_part_usage(root,pos->next_key_part);
5884
5877
if (count > pos->next_key_part->use_count)
5886
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5879
errmsg_printf(ERRMSG_LVL_INFO, "Use_count: Wrong count for key at 0x%lx, %lu "
5887
5880
"should be %lu", (long unsigned int)pos,
5888
5881
pos->next_key_part->use_count, count);
5894
5887
if (e_count != elements)
5895
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5888
errmsg_printf(ERRMSG_LVL_WARN, "Wrong use count: %u (should be %u) for tree at 0x%lx",
5896
5889
e_count, elements, (long unsigned int) this);
5903
5896
****************************************************************************/
5905
5898
/* MRR range sequence, SEL_ARG* implementation: stack entry */
5906
typedef struct st_range_seq_entry
5899
typedef struct st_range_seq_entry
5909
5902
Pointers in min and max keys. They point to right-after-end of key
5910
5903
images. The 0-th entry has these pointing to key tuple start.
5912
5905
unsigned char *min_key, *max_key;
5915
5908
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
5916
5909
min_key_flag may have NULL_RANGE set.
5918
5911
uint32_t min_key_flag, max_key_flag;
5920
5913
/* Number of key parts */
5921
5914
uint32_t min_key_parts, max_key_parts;
5922
5915
SEL_ARG *key_tree;
5932
5925
uint32_t real_keyno; /* Number of the index in tables */
5934
5927
SEL_ARG *start; /* Root node of the traversed SEL_ARG* graph */
5936
5929
RANGE_SEQ_ENTRY stack[MAX_REF_PARTS];
5937
5930
int i; /* Index of last used element in the above array */
5939
5932
bool at_start; /* true <=> The traversal has just started */
5940
5933
} SEL_ARG_RANGE_SEQ;
5948
5941
init_params SEL_ARG tree traversal context
5949
n_ranges [ignored] The number of ranges obtained
5942
n_ranges [ignored] The number of ranges obtained
5950
5943
flags [ignored] HA_MRR_SINGLE_POINT, HA_MRR_FIXED_KEY
5953
5946
Value of init_param
5956
range_seq_t sel_arg_range_seq_init(void *init_param,
5957
uint32_t n_ranges __attribute__((unused)),
5958
uint32_t flags __attribute__((unused)))
5949
range_seq_t sel_arg_range_seq_init(void *init_param, uint32_t, uint32_t)
5960
5951
SEL_ARG_RANGE_SEQ *seq= (SEL_ARG_RANGE_SEQ*)init_param;
5961
5952
seq->at_start= true;
6072
6063
Walk right-up while we can
6074
6065
walk_right_n_up:
6075
while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
6066
while (key_tree->next_key_part && key_tree->next_key_part != &null_element &&
6076
6067
key_tree->next_key_part->part == key_tree->part + 1 &&
6077
6068
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
6088
6079
seq->param->is_ror_scan= false;
6089
6080
if (!key_tree->min_flag)
6090
cur->min_key_parts +=
6081
cur->min_key_parts +=
6091
6082
key_tree->next_key_part->store_min_key(seq->param->key[seq->keyno],
6093
6084
&cur->min_key_flag);
6094
6085
if (!key_tree->max_flag)
6095
cur->max_key_parts +=
6086
cur->max_key_parts +=
6096
6087
key_tree->next_key_part->store_max_key(seq->param->key[seq->keyno],
6098
6089
&cur->max_key_flag);
6104
6095
Ok, current atomic interval is in form "t.field=const" and there is
6105
6096
next_key_part interval. Step right, and walk up from there.
6118
6109
/* Ok got a tuple */
6119
6110
RANGE_SEQ_ENTRY *cur= &seq->stack[seq->i];
6121
6112
range->ptr= (char*)(int)(key_tree->part);
6123
6114
range->range_flag= cur->min_key_flag | cur->max_key_flag;
6125
6116
range->start_key.key= seq->param->min_key;
6126
6117
range->start_key.length= cur->min_key - seq->param->min_key;
6127
6118
range->start_key.keypart_map= make_prev_keypart_map(cur->min_key_parts);
6128
range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
6119
range->start_key.flag= (cur->min_key_flag & NEAR_MIN ? HA_READ_AFTER_KEY :
6129
6120
HA_READ_KEY_EXACT);
6131
6122
range->end_key.key= seq->param->max_key;
6132
6123
range->end_key.length= cur->max_key - seq->param->max_key;
6133
range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
6124
range->end_key.flag= (cur->max_key_flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
6134
6125
HA_READ_AFTER_KEY);
6135
6126
range->end_key.keypart_map= make_prev_keypart_map(cur->max_key_parts);
6197
6188
ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
6198
SEL_ARG *tree, bool update_tbl_stats,
6189
SEL_ARG *tree, bool update_tbl_stats,
6199
6190
uint32_t *mrr_flags, uint32_t *bufsize, COST_VECT *cost)
6201
6192
SEL_ARG_RANGE_SEQ seq;
6223
6214
param->is_ror_scan= true;
6224
6215
if (file->index_flags(keynr, 0, true) & HA_KEY_SCAN_NOT_ROR)
6225
6216
param->is_ror_scan= false;
6227
6218
*mrr_flags= param->force_default_mrr? HA_MRR_USE_DEFAULT_IMPL: 0;
6228
6219
*mrr_flags|= HA_MRR_NO_ASSOCIATION;
6230
6221
bool pk_is_clustered= file->primary_key_is_clustered();
6232
6223
(file->index_flags(keynr, param->max_key_part, 1) & HA_KEYREAD_ONLY) &&
6233
6224
!(pk_is_clustered && keynr == param->table->s->primary_key))
6234
6225
*mrr_flags |= HA_MRR_INDEX_ONLY;
6236
6227
if (current_session->lex->sql_command != SQLCOM_SELECT)
6237
6228
*mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6255
6246
enum ha_key_alg key_alg= param->table->key_info[seq.real_keyno].algorithm;
6256
6247
if ((key_alg != HA_KEY_ALG_BTREE) && (key_alg!= HA_KEY_ALG_UNDEF))
6259
6250
All scans are non-ROR scans for those index types.
6260
TODO: Don't have this logic here, make table engines return
6251
TODO: Don't have this logic here, make table engines return
6261
6252
appropriate flags instead.
6263
6254
param->is_ror_scan= false;
6297
6288
where the index is defined on (key1_1, ..., key1_N [,a_1, ..., a_n])
6299
and the table has a clustered Primary Key defined as
6300
PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
6302
i.e. the first key parts of it are identical to uncovered parts ot the
6290
and the table has a clustered Primary Key defined as
6291
PRIMARY KEY(a_1, ..., a_n, b1, ..., b_k)
6293
i.e. the first key parts of it are identical to uncovered parts ot the
6303
6294
key being scanned. This function assumes that the index flags do not
6304
6295
include HA_KEY_SCAN_NOT_ROR flag (that is checked elsewhere).
6711
6702
/* Call multi_range_read_info() to get the MRR flags and buffer size */
6712
quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
6703
quick->mrr_flags= HA_MRR_NO_ASSOCIATION |
6713
6704
(table->key_read ? HA_MRR_INDEX_ONLY : 0);
6714
6705
if (session->lex->sql_command != SQLCOM_SELECT)
6715
6706
quick->mrr_flags |= HA_MRR_USE_DEFAULT_IMPL;
6731
Perform key scans for all used indexes (except CPK), get rowids and merge
6722
Perform key scans for all used indexes (except CPK), get rowids and merge
6732
6723
them into an ordered non-recurrent sequence of rowids.
6734
6725
The merge/duplicate removal is performed using Unique class. We put all
6735
6726
rowids into Unique, get the sorted sequence and destroy the Unique.
6737
6728
If table has a clustered primary key that covers all rows (true for bdb
6738
6729
and innodb currently) and one of the index_merge scans is a scan on PK,
6739
then rows that will be retrieved by PK scan are not put into Unique and
6730
then rows that will be retrieved by PK scan are not put into Unique and
6740
6731
primary key scan is not performed here, it is performed later separately.
6758
6749
cur_quick_it.rewind();
6759
6750
cur_quick= cur_quick_it++;
6760
6751
assert(cur_quick != 0);
6763
We reuse the same instance of handler so we need to call both init and
6754
We reuse the same instance of handler so we need to call both init and
6766
6757
if (cur_quick->init() || cur_quick->reset())
6769
6760
unique= new Unique(refpos_order_cmp, (void *)file,
6770
6761
file->ref_length,
6771
6762
session->variables.sortbuff_size);
6776
6767
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
7048
7039
if (!mrr_buf_desc)
7049
7040
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7052
7043
mrr_flags |= HA_MRR_SORTED;
7053
7044
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7054
7045
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7055
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7046
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7062
7053
Range sequence interface implementation for array<QUICK_RANGE>: initialize
7065
7056
quick_range_seq_init()
7066
7057
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
7067
7058
n_ranges Number of ranges in the sequence (ignored)
7068
flags MRR flags (currently not used)
7059
flags MRR flags (currently not used)
7071
7062
Opaque value to be passed to quick_range_seq_next
7074
range_seq_t quick_range_seq_init(void *init_param,
7075
uint32_t n_ranges __attribute__((unused)),
7076
uint32_t flags __attribute__((unused)))
7065
range_seq_t quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7078
7067
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7079
7068
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7362
7350
for now, this seems to work right at least.
7365
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7366
uint32_t used_key_parts_arg __attribute__((unused)),
7367
bool *create_err __attribute__((unused)))
7353
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint32_t, bool *)
7368
7354
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7370
7356
QUICK_RANGE *r;
7414
7400
if (cmp_prev(*rev_it.ref()) == 0)
7417
7403
else if (result != HA_ERR_END_OF_FILE)
7421
7407
if (!(last_range= rev_it++))
7422
return(HA_ERR_END_OF_FILE); // All ranges used
7408
return HA_ERR_END_OF_FILE; // All ranges used
7424
7410
if (last_range->flag & NO_MAX_RANGE) // Read last record
7470
7456
Compare if found key is over max-value
7471
7457
Returns 0 if key <= range->max_key
7472
TODO: Figure out why can't this function be as simple as cmp_prev().
7458
TODO: Figure out why can't this function be as simple as cmp_prev().
7475
7461
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7762
7748
- NGA = QA - (GA union C) = {NG_1, ..., NG_m} - the ones not in
7763
7749
GROUP BY and not referenced by MIN/MAX functions.
7764
7750
with the following properties specified below.
7765
B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
7751
B3. If Q has a GROUP BY WITH ROLLUP clause the access method is not
7768
7754
SA1. There is at most one attribute in SA referenced by any number of
7850
7836
other field as in: "select min(a) from t1 group by a" ?
7851
7837
- We assume that the general correctness of the GROUP-BY query was checked
7852
7838
before this point. Is this correct, or do we have to check it completely?
7853
- Lift the limitation in condition (B3), that is, make this access method
7839
- Lift the limitation in condition (B3), that is, make this access method
7854
7840
applicable to ROLLUP queries.
7888
7874
/* Perform few 'cheap' tests whether this access method is applicable. */
7890
return(NULL); /* This is not a select statement. */
7876
return NULL; /* This is not a select statement. */
7891
7877
if ((join->tables != 1) || /* The query must reference one table. */
7892
7878
((!join->group_list) && /* Neither GROUP BY nor a DISTINCT query. */
7893
7879
(!join->select_distinct)) ||
7894
7880
(join->select_lex->olap == ROLLUP_TYPE)) /* Check (B3) for ROLLUP */
7896
7882
if (table->s->keys == 0) /* There are no indexes to use. */
7899
7885
/* Analyze the query in more detail. */
7900
7886
List_iterator<Item> select_items_it(join->fields_list);
7902
7888
/* Check (SA1,SA4) and store the only MIN/MAX argument - the C attribute.*/
7903
7889
if (join->make_sum_func_list(join->all_fields, join->fields_list, 1))
7905
7891
if (join->sum_funcs[0])
7907
7893
Item_sum *min_max_item;
7913
7899
else if (min_max_item->sum_func() == Item_sum::MAX_FUNC)
7914
7900
have_max= true;
7918
7904
/* The argument of MIN/MAX. */
7919
Item *expr= min_max_item->args[0]->real_item();
7905
Item *expr= min_max_item->args[0]->real_item();
7920
7906
if (expr->type() == Item::FIELD_ITEM) /* Is it an attribute? */
7922
7908
if (! min_max_arg_item)
7923
7909
min_max_arg_item= (Item_field*) expr;
7924
7910
else if (! min_max_arg_item->eq(expr, 1))
8195
8181
COST_VECT dummy_cost;
8196
8182
uint32_t mrr_flags= HA_MRR_USE_DEFAULT_IMPL;
8197
8183
uint32_t mrr_bufsize=0;
8198
cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
8199
false /*don't care*/,
8184
cur_quick_prefix_records= check_quick_select(param, cur_param_idx,
8185
false /*don't care*/,
8200
8186
cur_index_tree, true,
8201
8187
&mrr_flags, &mrr_bufsize,
8229
8215
cur_group_prefix_len= 0;
8231
8217
if (!index_info) /* No usable index found. */
8234
8220
/* Check (SA3) for the where clause. */
8235
8221
if (join->conds && min_max_arg_item &&
8236
8222
!check_group_min_max_predicates(join->conds, min_max_arg_item, Field::itRAW))
8239
8225
/* The query passes all tests, so construct a new TRP object. */
8240
8226
read_plan= new (param->mem_root)
8325
8311
cur_arg= arguments[arg_idx]->real_item();
8326
8312
if (cur_arg->type() == Item::FIELD_ITEM)
8328
if (min_max_arg_item->eq(cur_arg, 1))
8314
if (min_max_arg_item->eq(cur_arg, 1))
8331
8317
If pred references the MIN/MAX argument, check whether pred is a range
8370
8356
(args[1]->result_type() != STRING_RESULT &&
8371
8357
min_max_arg_item->field->cmp_type() != args[1]->result_type())))
8375
8361
else if (cur_arg->type() == Item::FUNC_ITEM)
8377
8363
if (!check_group_min_max_predicates(cur_arg, min_max_arg_item,
8381
8367
else if (cur_arg->const_item())
8404
8390
key_infix [out] Infix of constants to be used for index lookup
8405
8391
key_infix_len [out] Lenghth of the infix
8406
8392
first_non_infix_part [out] The first keypart after the infix (if any)
8409
8395
Test conditions (NGA1, NGA2) from get_best_group_min_max(). Namely,
8410
8396
for each keypart field NGF_i not in GROUP-BY, check that there is a
8425
get_constant_key_infix(KEY *index_info __attribute__((unused)),
8426
SEL_ARG *index_range_tree,
8411
get_constant_key_infix(KEY *, SEL_ARG *index_range_tree,
8427
8412
KEY_PART_INFO *first_non_group_part,
8428
8413
KEY_PART_INFO *min_max_arg_part,
8429
8414
KEY_PART_INFO *last_part,
8430
Session *session __attribute__((unused)),
8431
unsigned char *key_infix, uint32_t *key_infix_len,
8415
Session *, unsigned char *key_infix, uint32_t *key_infix_len,
8432
8416
KEY_PART_INFO **first_non_infix_part)
8434
8418
SEL_ARG *cur_range;
8622
8606
void cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
8623
8607
uint32_t group_key_parts, SEL_TREE *range_tree,
8624
SEL_ARG *index_tree __attribute__((unused)),
8625
ha_rows quick_prefix_records,
8608
SEL_ARG *, ha_rows quick_prefix_records,
8626
8609
bool have_min, bool have_max,
8627
8610
double *read_cost, ha_rows *records)
8719
8701
QUICK_SELECT_I *
8720
TRP_GROUP_MIN_MAX::make_quick(PARAM *param,
8721
bool retrieve_full_rows __attribute__((unused)),
8722
MEM_ROOT *parent_alloc)
8702
TRP_GROUP_MIN_MAX::make_quick(PARAM *param, bool, MEM_ROOT *parent_alloc)
8724
8704
QUICK_GROUP_MIN_MAX_SELECT *quick;
9029
9008
quick_prefix_select is made over the conditions on the whole key.
9030
It defines a number of ranges of length x.
9031
However when jumping through the prefixes we use only the the first
9009
It defines a number of ranges of length x.
9010
However when jumping through the prefixes we use only the the first
9032
9011
few most significant keyparts in the range key. However if there
9033
are more keyparts to follow the ones we are using we must make the
9034
condition on the key inclusive (because x < "ab" means
9012
are more keyparts to follow the ones we are using we must make the
9013
condition on the key inclusive (because x < "ab" means
9035
9014
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9036
9015
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9142
9121
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9143
9122
if ((result= file->ha_index_init(index,1)))
9145
9124
if (quick_prefix_select && quick_prefix_select->reset())
9147
9126
result= file->index_last(record);
9148
9127
if (result == HA_ERR_END_OF_FILE)
9150
9129
/* Save the prefix of the last group. */
9151
9130
key_copy(last_prefix, record, index_info, group_prefix_len);
9159
9138
Get the next key containing the MIN and/or MAX key for the next group.
9227
9206
if (max_res == 0)
9228
9207
update_max_result();
9229
9208
/* If a MIN was found, a MAX must have been found as well. */
9230
assert((have_max && !have_min) ||
9231
(have_max && have_min && (max_res == 0)));
9209
assert(((have_max && !have_min) ||
9210
(have_max && have_min && (max_res == 0))));
9234
9213
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9543
9525
if ( !(cur_range->flag & NO_MAX_RANGE) )
9545
9527
/* Compose the MAX key for the range. */
9546
unsigned char *max_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9547
memcpy(max_key, group_prefix, real_prefix_len);
9548
memcpy(max_key + real_prefix_len, cur_range->max_key,
9549
cur_range->max_length);
9529
max_key.append(group_prefix, real_prefix_len);
9530
max_key.append(cur_range->max_key, cur_range->max_length);
9550
9531
/* Compare the found key with max_key. */
9551
int cmp_res= key_cmp(index_info->key_part, max_key,
9532
int cmp_res= key_cmp(index_info->key_part,
9552
9534
real_prefix_len + min_max_arg_len);
9553
9535
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9660
9644
if ( !(cur_range->flag & NO_MIN_RANGE) )
9662
9646
/* Compose the MIN key for the range. */
9663
unsigned char *min_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9664
memcpy(min_key, group_prefix, real_prefix_len);
9665
memcpy(min_key + real_prefix_len, cur_range->min_key,
9666
cur_range->min_length);
9648
min_key.append(group_prefix, real_prefix_len);
9649
min_key.append(cur_range->min_key, cur_range->min_length);
9667
9651
/* Compare the found key with min_key. */
9668
int cmp_res= key_cmp(index_info->key_part, min_key,
9652
int cmp_res= key_cmp(index_info->key_part,
9669
9654
real_prefix_len + min_max_arg_len);
9670
9655
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9671
9656
(cmp_res >= 0)))
9768
9753
used_lengths->append(buf, length);
9771
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9772
const char *msg __attribute__((unused)))
9756
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map, const char *)
9774
9758
SEL_ARG **key,**end;
9792
9776
if (!tmp.length())
9793
9777
tmp.append(STRING_WITH_LEN("(empty)"));
9799
9781
static void print_ror_scans_arr(Table *table,
9800
const char *msg __attribute__((unused)),
9801
struct st_ror_scan_info **start,
9782
const char *, struct st_ror_scan_info **start,
9802
9783
struct st_ror_scan_info **end)
9804
9785
char buff[1024];
added
removed
drizzled/opt_range.cc
