96
99
See key_copy() and key_restore() for code to move data between index tuple
99
CAUTION: the above description is only sergefp's understanding of the
102
CAUTION: the above description is only sergefp's understanding of the
100
103
subject and may omit some details.
112
#include <boost/dynamic_bitset.hpp>
114
#include <drizzled/check_stack_overrun.h>
115
#include <drizzled/error.h>
116
#include <drizzled/field/num.h>
117
#include <drizzled/internal/iocache.h>
118
#include <drizzled/internal/my_sys.h>
119
#include <drizzled/item/cmpfunc.h>
120
#include <drizzled/optimizer/cost_vector.h>
121
#include <drizzled/optimizer/quick_group_min_max_select.h>
122
#include <drizzled/optimizer/quick_index_merge_select.h>
123
#include <drizzled/optimizer/quick_range.h>
124
#include <drizzled/optimizer/quick_range_select.h>
125
#include <drizzled/optimizer/quick_ror_intersect_select.h>
126
#include <drizzled/optimizer/quick_ror_union_select.h>
127
#include <drizzled/optimizer/range.h>
128
#include <drizzled/optimizer/range_param.h>
129
#include <drizzled/optimizer/sel_arg.h>
130
#include <drizzled/optimizer/sel_imerge.h>
131
#include <drizzled/optimizer/sel_tree.h>
132
#include <drizzled/optimizer/sum.h>
133
#include <drizzled/optimizer/table_read_plan.h>
134
#include <drizzled/plugin/storage_engine.h>
135
#include <drizzled/records.h>
136
#include <drizzled/sql_base.h>
106
#include <drizzled/server_includes.h>
137
107
#include <drizzled/sql_select.h>
138
#include <drizzled/table_reference.h>
139
#include <drizzled/session.h>
141
#include <drizzled/unique.h>
143
#include <drizzled/temporal.h> /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
149
#define HA_END_SPACE_KEY 0
110
#define test_rb_tree(A,B) {}
111
#define test_use_count(A) {}
152
115
Convert double value to #rows. Currently this does floor(), and we
153
116
might consider using round() instead.
155
static inline ha_rows double2rows(double x)
157
return static_cast<ha_rows>(x);
118
#define double2rows(x) ((ha_rows)(x))
120
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
160
122
static unsigned char is_null_string[2]= {1,0};
164
Get cost of reading nrows table records in a "disk sweep"
166
A disk sweep read is a sequence of Cursor->rnd_pos(rowid) calls that made
167
for an ordered sequence of rowids.
169
We assume hard disk IO. The read is performed as follows:
171
1. The disk head is moved to the needed cylinder
172
2. The controller waits for the plate to rotate
173
3. The data is transferred
175
Time to do #3 is insignificant compared to #2+#1.
177
Time to move the disk head is proportional to head travel distance.
179
Time to wait for the plate to rotate depends on whether the disk head
182
If disk head wasn't moved, the wait time is proportional to distance
183
between the previous block and the block we're reading.
185
If the head was moved, we don't know how much we'll need to wait for the
186
plate to rotate. We assume the wait time to be a variate with a mean of
187
0.5 of full rotation time.
189
Our cost units are "random disk seeks". The cost of random disk seek is
190
actually not a constant, it depends one range of cylinders we're going
191
to access. We make it constant by introducing a fuzzy concept of "typical
192
datafile length" (it's fuzzy as it's hard to tell whether it should
193
include index cursor, temp.tables etc). Then random seek cost is:
195
1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length
197
We define half_rotation_cost as DISK_SEEK_BASE_COST=0.9.
199
@param table Table to be accessed
200
@param nrows Number of rows to retrieve
201
@param interrupted true <=> Assume that the disk sweep will be
202
interrupted by other disk IO. false - otherwise.
203
@param cost OUT The cost.
206
static void get_sweep_read_cost(Table *table,
209
optimizer::CostVector *cost)
212
if (table->cursor->primary_key_is_clustered())
214
cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
215
static_cast<uint32_t>(nrows),
221
ceil(static_cast<double>(table->cursor->stats.data_file_length) / IO_SIZE);
223
n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, static_cast<double>(nrows)));
224
if (busy_blocks < 1.0)
227
cost->setIOCount(busy_blocks);
231
/* Assume reading is done in one 'sweep' */
232
cost->setAvgIOCost((DISK_SEEK_BASE_COST +
233
DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
238
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
241
Item_func::Functype type,
243
Item_result cmp_type);
245
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
249
Item_func::Functype type,
252
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
254
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
256
static ha_rows check_quick_select(Session *session,
257
optimizer::Parameter *param,
260
optimizer::SEL_ARG *tree,
261
bool update_tbl_stats,
264
optimizer::CostVector *cost);
266
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
267
optimizer::Parameter *param,
268
optimizer::SEL_TREE *tree,
269
bool index_read_must_be_used,
270
bool update_tbl_stats,
274
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
275
optimizer::SEL_TREE *tree,
277
bool *are_all_covering);
280
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
281
optimizer::SEL_TREE *tree,
285
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
286
optimizer::Parameter *param,
287
optimizer::SEL_IMERGE *imerge,
291
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
293
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
294
optimizer::SEL_TREE *tree1,
295
optimizer::SEL_TREE *tree2);
297
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
299
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
300
optimizer::SEL_ARG *key1,
301
optimizer::SEL_ARG *key2,
302
uint32_t clone_flag);
304
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
306
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
308
static bool null_part_in_key(KEY_PART *key_part,
309
const unsigned char *key,
124
class RANGE_OPT_PARAM;
126
A construction block of the SEL_ARG-graph.
128
The following description only covers graphs of SEL_ARG objects with
129
sel_arg->type==KEY_RANGE:
131
One SEL_ARG object represents an "elementary interval" in form
133
min_value <=? table.keypartX <=? max_value
135
The interval is a non-empty interval of any kind: with[out] minimum/maximum
136
bound, [half]open/closed, single-point interval, etc.
138
1. SEL_ARG GRAPH STRUCTURE
140
SEL_ARG objects are linked together in a graph. The meaning of the graph
141
is better demostrated by an example:
146
| part=1 $ part=2 $ part=3
148
| +-------+ $ +-------+ $ +--------+
149
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
150
| +-------+ $ +-------+ $ +--------+
156
\->| kp1=2 |--$--------------$-+
157
+-------+ $ $ | +--------+
159
+-------+ $ $ | +--------+
160
| kp1=3 |--$--------------$-+ |
161
+-------+ $ $ +--------+
165
The entire graph is partitioned into "interval lists".
167
An interval list is a sequence of ordered disjoint intervals over the same
168
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
169
all intervals in the list form an RB-tree, linked via left/right/parent
170
pointers. The RB-tree root SEL_ARG object will be further called "root of the
173
In the example pic, there are 4 interval lists:
174
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
175
The vertical lines represent SEL_ARG::next/prev pointers.
177
In an interval list, each member X may have SEL_ARG::next_key_part pointer
178
pointing to the root of another interval list Y. The pointed interval list
179
must cover a key part with greater number (i.e. Y->part > X->part).
181
In the example pic, the next_key_part pointers are represented by
184
2. SEL_ARG GRAPH SEMANTICS
186
It represents a condition in a special form (we don't have a name for it ATM)
187
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
189
For example, the picture represents the condition in form:
190
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
191
(kp1=2 AND (kp3=11 OR kp3=14)) OR
192
(kp1=3 AND (kp3=11 OR kp3=14))
197
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
198
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
199
intervals (i.e. intervals in form
201
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
203
Those intervals can be used to access the index. The uses are in:
204
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
205
how many table records are contained within all
207
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
208
and create QUICK_RANGE_SELECT object that will
209
read records within these intervals.
211
4. SPACE COMPLEXITY NOTES
213
SEL_ARG graph is a representation of an ordered disjoint sequence of
214
intervals over the ordered set of index tuple values.
216
For multi-part keys, one can construct a WHERE expression such that its
217
list of intervals will be of combinatorial size. Here is an example:
219
(keypart1 IN (1,2, ..., n1)) AND
220
(keypart2 IN (1,2, ..., n2)) AND
221
(keypart3 IN (1,2, ..., n3))
223
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
226
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
228
SEL_ARG graph structure aims to reduce the amount of required space by
229
"sharing" the elementary intervals when possible (the pic at the
230
beginning of this comment has examples of such sharing). The sharing may
231
prevent combinatorial blowup:
233
There are WHERE clauses that have combinatorial-size interval lists but
234
will be represented by a compact SEL_ARG graph.
236
(keypartN IN (1,2, ..., n1)) AND
238
(keypart2 IN (1,2, ..., n2)) AND
239
(keypart1 IN (1,2, ..., n3))
241
but not in all cases:
243
- There are WHERE clauses that do have a compact SEL_ARG-graph
244
representation but get_mm_tree() and its callees will construct a
245
graph of combinatorial size.
247
(keypart1 IN (1,2, ..., n1)) AND
248
(keypart2 IN (1,2, ..., n2)) AND
250
(keypartN IN (1,2, ..., n3))
252
- There are WHERE clauses for which the minimal possible SEL_ARG graph
253
representation will have combinatorial size.
255
By induction: Let's take any interval on some keypart in the middle:
259
Then let's AND it with this interval 'structure' from preceding and
262
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
264
We will obtain this SEL_ARG graph:
268
+---------+ $ +---------+ $ +---------+
269
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
270
+---------+ $ +---------+ $ +---------+
272
+---------+ $ +---------+ $
273
| kp14=c2 |--$-->| kp15=c0 | $
274
+---------+ $ +---------+ $
277
Note that we had to duplicate "kp15=c0" and there was no way to avoid
279
The induction step: AND the obtained expression with another "wrapping"
281
When the process ends because of the limit on max. number of keyparts
284
WHERE clause length is O(3*#max_keyparts)
285
SEL_ARG graph size is O(2^(#max_keyparts/2))
287
(it is also possible to construct a case where instead of 2 in 2^n we
288
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
291
We avoid consuming too much memory by setting a limit on the number of
292
SEL_ARG object we can construct during one range analysis invocation.
295
class SEL_ARG :public Sql_alloc
298
uint8_t min_flag,max_flag,maybe_flag;
299
uint8_t part; // Which key part
302
Number of children of this element in the RB-tree, plus 1 for this
307
Valid only for elements which are RB-tree roots: Number of times this
308
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
309
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
314
unsigned char *min_value,*max_value; // Pointer to range
317
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
319
SEL_ARG *left,*right; /* R-B tree children */
320
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
321
SEL_ARG *parent; /* R-B tree parent */
322
SEL_ARG *next_key_part;
323
enum leaf_color { BLACK,RED } color;
324
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
326
enum { MAX_SEL_ARGS = 16000 };
330
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
331
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
332
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
333
SEL_ARG(enum Type type_arg)
334
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
335
color(BLACK), type(type_arg)
337
inline bool is_same(SEL_ARG *arg)
339
if (type != arg->type || part != arg->part)
341
if (type != KEY_RANGE)
343
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
345
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
346
inline void maybe_smaller() { maybe_flag=1; }
347
/* Return true iff it's a single-point null interval */
348
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
349
inline int cmp_min_to_min(SEL_ARG* arg)
351
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
353
inline int cmp_min_to_max(SEL_ARG* arg)
355
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
357
inline int cmp_max_to_max(SEL_ARG* arg)
359
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
361
inline int cmp_max_to_min(SEL_ARG* arg)
363
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
365
SEL_ARG *clone_and(SEL_ARG* arg)
366
{ // Get overlapping range
367
unsigned char *new_min,*new_max;
368
uint8_t flag_min,flag_max;
369
if (cmp_min_to_min(arg) >= 0)
371
new_min=min_value; flag_min=min_flag;
375
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
377
if (cmp_max_to_max(arg) <= 0)
379
new_max=max_value; flag_max=max_flag;
383
new_max=arg->max_value; flag_max=arg->max_flag;
385
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
386
test(maybe_flag && arg->maybe_flag));
388
SEL_ARG *clone_first(SEL_ARG *arg)
389
{ // min <= X < arg->min
390
return new SEL_ARG(field,part, min_value, arg->min_value,
391
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
392
maybe_flag | arg->maybe_flag);
394
SEL_ARG *clone_last(SEL_ARG *arg)
395
{ // min <= X <= key_max
396
return new SEL_ARG(field, part, min_value, arg->max_value,
397
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
399
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
401
bool copy_min(SEL_ARG* arg)
402
{ // Get overlapping range
403
if (cmp_min_to_min(arg) > 0)
405
min_value=arg->min_value; min_flag=arg->min_flag;
406
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
407
(NO_MAX_RANGE | NO_MIN_RANGE))
408
return 1; // Full range
410
maybe_flag|=arg->maybe_flag;
413
bool copy_max(SEL_ARG* arg)
414
{ // Get overlapping range
415
if (cmp_max_to_max(arg) <= 0)
417
max_value=arg->max_value; max_flag=arg->max_flag;
418
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
419
(NO_MAX_RANGE | NO_MIN_RANGE))
420
return 1; // Full range
422
maybe_flag|=arg->maybe_flag;
426
void copy_min_to_min(SEL_ARG *arg)
428
min_value=arg->min_value; min_flag=arg->min_flag;
430
void copy_min_to_max(SEL_ARG *arg)
432
max_value=arg->min_value;
433
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
435
void copy_max_to_min(SEL_ARG *arg)
437
min_value=arg->max_value;
438
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
440
/* returns a number of keypart values (0 or 1) appended to the key buffer */
441
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
443
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
444
if ((!(min_flag & NO_MIN_RANGE) &&
445
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
447
if (maybe_null && *min_value)
450
memset(*min_key+1, 0, length-1);
453
memcpy(*min_key,min_value,length);
459
/* returns a number of keypart values (0 or 1) appended to the key buffer */
460
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
462
if (!(max_flag & NO_MAX_RANGE) &&
463
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
465
if (maybe_null && *max_value)
468
memset(*max_key+1, 0, length-1);
471
memcpy(*max_key,max_value,length);
478
/* returns a number of keypart values appended to the key buffer */
479
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
481
SEL_ARG *key_tree= first();
482
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
483
range_key, *range_key_flag);
484
*range_key_flag|= key_tree->min_flag;
486
if (key_tree->next_key_part &&
487
key_tree->next_key_part->part == key_tree->part+1 &&
488
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
489
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
490
res+= key_tree->next_key_part->store_min_key(key, range_key,
495
/* returns a number of keypart values appended to the key buffer */
496
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
498
SEL_ARG *key_tree= last();
499
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
500
range_key, *range_key_flag);
501
(*range_key_flag)|= key_tree->max_flag;
502
if (key_tree->next_key_part &&
503
key_tree->next_key_part->part == key_tree->part+1 &&
504
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
505
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
506
res+= key_tree->next_key_part->store_max_key(key, range_key,
511
SEL_ARG *insert(SEL_ARG *key);
512
SEL_ARG *tree_delete(SEL_ARG *key);
513
SEL_ARG *find_range(SEL_ARG *key);
514
SEL_ARG *rb_insert(SEL_ARG *leaf);
515
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
517
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
518
void test_use_count(SEL_ARG *root);
523
inline bool simple_key()
525
return !next_key_part && elements == 1;
527
void increment_use_count(long count)
531
next_key_part->use_count+=count;
532
count*= (next_key_part->use_count-count);
533
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
534
if (pos->next_key_part)
535
pos->increment_use_count(count);
540
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
541
if (pos->next_key_part)
543
pos->next_key_part->use_count--;
544
pos->next_key_part->free_tree();
548
inline SEL_ARG **parent_ptr()
550
return parent->left == this ? &parent->left : &parent->right;
555
Check if this SEL_ARG object represents a single-point interval
561
Check if this SEL_ARG object (not tree) represents a single-point
562
interval, i.e. if it represents a "keypart = const" or
566
true This SEL_ARG object represents a singlepoint interval
570
bool is_singlepoint()
573
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
574
flags, and the same for right edge.
576
if (min_flag || max_flag)
578
unsigned char *min_val= min_value;
579
unsigned char *max_val= max_value;
583
/* First byte is a NULL value indicator */
584
if (*min_val != *max_val)
588
return true; /* This "x IS NULL" */
592
return !field->key_cmp(min_val, max_val);
594
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
600
class SEL_TREE :public Sql_alloc
604
Starting an effort to document this field:
605
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
606
(type == SEL_TREE::IMPOSSIBLE)
608
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
609
SEL_TREE(enum Type type_arg) :type(type_arg) {}
610
SEL_TREE() :type(KEY)
612
keys_map.clear_all();
613
memset(keys, 0, sizeof(keys));
616
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
617
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
618
merit in range analyzer functions (e.g. get_mm_parts) returning a
619
pointer to such SEL_TREE instead of NULL)
621
SEL_ARG *keys[MAX_KEY];
622
key_map keys_map; /* bitmask of non-NULL elements in keys */
625
Possible ways to read rows using index_merge. The list is non-empty only
626
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
628
List<SEL_IMERGE> merges;
630
/* The members below are filled/used only after get_mm_tree is done */
631
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
632
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
634
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
635
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
636
/* Note that #records for each key scan is stored in table->quick_rows */
639
class RANGE_OPT_PARAM
642
THD *thd; /* Current thread handle */
643
Table *table; /* Table being analyzed */
644
COND *cond; /* Used inside get_mm_tree(). */
645
table_map prev_tables;
646
table_map read_tables;
647
table_map current_table; /* Bit of the table being analyzed */
649
/* Array of parts of all keys for which range analysis is performed */
651
KEY_PART *key_parts_end;
652
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
653
MEM_ROOT *old_root; /* Memory that will last until the query end */
655
Number of indexes used in range analysis (In SEL_TREE::keys only first
656
#keys elements are not empty)
661
If true, the index descriptions describe real indexes (and it is ok to
662
call field->optimize_range(real_keynr[...], ...).
663
Otherwise index description describes fake indexes.
665
bool using_real_indexes;
667
bool remove_jump_scans;
670
used_key_no -> table_key_no translation table. Only makes sense if
671
using_real_indexes==true
673
uint32_t real_keynr[MAX_KEY];
674
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
675
uint32_t alloced_sel_args;
676
bool force_default_mrr;
679
class PARAM : public RANGE_OPT_PARAM
682
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
684
uint32_t max_key_part;
685
/* Number of ranges in the last checked tree->key */
686
uint32_t range_count;
687
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
688
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
689
bool quick; // Don't calulate possible keys
691
uint32_t fields_bitmap_size;
692
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
693
MY_BITMAP tmp_covered_fields;
695
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
697
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
698
uint32_t imerge_cost_buff_size; /* size of the buffer */
700
/* true if last checked tree->key can be used for ROR-scan */
702
/* Number of ranges in the last checked tree->key */
706
class TABLE_READ_PLAN;
708
class TRP_ROR_INTERSECT;
710
class TRP_ROR_INDEX_MERGE;
711
class TRP_GROUP_MIN_MAX;
713
struct st_ror_scan_info;
715
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
716
Item_func::Functype type,Item *value,
717
Item_result cmp_type);
718
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
720
Item_func::Functype type,Item *value);
721
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
723
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
724
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
725
SEL_ARG *tree, bool update_tbl_stats,
726
uint32_t *mrr_flags, uint32_t *bufsize,
728
//bool update_tbl_stats);
729
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
730
unsigned char *min_key, uint32_t min_key_flag, int,
731
unsigned char *max_key, uint32_t max_key_flag, int);
734
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
735
SEL_ARG *key_tree, uint32_t mrr_flags,
736
uint32_t mrr_buf_size, MEM_ROOT *alloc);
737
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
738
bool index_read_must_be_used,
739
bool update_tbl_stats,
742
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
744
bool *are_all_covering);
746
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
750
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
753
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
755
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
757
static void print_ror_scans_arr(Table *table, const char *msg,
758
struct st_ror_scan_info **start,
759
struct st_ror_scan_info **end);
761
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
762
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
763
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
764
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
765
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
766
uint32_t clone_flag);
767
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
768
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
769
SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
770
unsigned char *max_key,uint32_t max_key_flag);
771
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
773
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
774
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
310
775
uint32_t length);
312
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
313
optimizer::SEL_TREE *tree2,
314
optimizer::RangeParameter *param);
776
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
780
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
781
a condition in the following form:
782
(t_1||t_2||...||t_N) && (next)
784
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
785
(t_i,t_j) contains SEL_ARGS for the same index.
787
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
789
This class relies on memory manager to do the cleanup.
792
class SEL_IMERGE : public Sql_alloc
794
enum { PREALLOCED_TREES= 10};
796
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
797
SEL_TREE **trees; /* trees used to do index_merge */
798
SEL_TREE **trees_next; /* last of these trees */
799
SEL_TREE **trees_end; /* end of allocated space */
801
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
804
trees(&trees_prealloced[0]),
806
trees_end(trees + PREALLOCED_TREES)
808
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
809
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
810
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
815
Add SEL_TREE to this index_merge without any checks,
818
This function implements the following:
819
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
826
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
828
if (trees_next == trees_end)
830
const int realloc_ratio= 2; /* Double size for next round */
831
uint32_t old_elements= (trees_end - trees);
832
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
833
uint32_t new_size= old_size * realloc_ratio;
834
SEL_TREE **new_trees;
835
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
837
memcpy(new_trees, trees, old_size);
839
trees_next= trees + old_elements;
840
trees_end= trees + old_elements * realloc_ratio;
842
*(trees_next++)= tree;
848
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
849
combining new_tree with one of the trees in this SEL_IMERGE if they both
850
have SEL_ARGs for the same key.
853
or_sel_tree_with_checks()
854
param PARAM from SQL_SELECT::test_quick_select
855
new_tree SEL_TREE with type KEY or KEY_SMALLER.
858
This does the following:
859
(t_1||...||t_k)||new_tree =
861
= (t_1||...||t_k||new_tree)
863
= (t_1||....||(t_j|| new_tree)||...||t_k),
865
where t_i, y are SEL_TREEs.
866
new_tree is combined with the first t_j it has a SEL_ARG on common
867
key with. As a consequence of this, choice of keys to do index_merge
868
read may depend on the order of conditions in WHERE part of the query.
872
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
873
and (*this) should be discarded.
874
-1 An error occurred.
877
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
879
for (SEL_TREE** tree = trees;
883
if (sel_trees_can_be_ored(*tree, new_tree, param))
885
*tree = tree_or(param, *tree, new_tree);
888
if (((*tree)->type == SEL_TREE::MAYBE) ||
889
((*tree)->type == SEL_TREE::ALWAYS))
891
/* SEL_TREE::IMPOSSIBLE is impossible here */
896
/* New tree cannot be combined with any of existing trees. */
897
return or_sel_tree(param, new_tree);
902
Perform OR operation on this index_merge and supplied index_merge list.
906
1 - One of conditions in result is always true and this SEL_IMERGE
908
-1 - An error occurred
911
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
913
for (SEL_TREE** tree= imerge->trees;
914
tree != imerge->trees_next;
917
if (or_sel_tree_with_checks(param, *tree))
322
925
Perform AND operation on two index_merge lists and store result in *im1.
325
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
928
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
327
930
im1->concat(im2);
935
Perform OR operation on 2 index_merge lists, storing result in first list.
938
The following conversion is implemented:
939
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
942
i.e. all conjuncts except the first one are currently dropped.
943
This is done to avoid producing N*K ways to do index_merge.
945
If (a_1||b_1) produce a condition that is always true, NULL is returned
946
and index_merge is discarded (while it is actually possible to try
949
As a consequence of this, choice of keys to do index_merge read may depend
950
on the order of conditions in WHERE part of the query.
953
0 OK, result is stored in *im1
954
other Error, both passed lists are unusable
957
int imerge_list_or_list(RANGE_OPT_PARAM *param,
958
List<SEL_IMERGE> *im1,
959
List<SEL_IMERGE> *im2)
961
SEL_IMERGE *imerge= im1->head();
963
im1->push_back(imerge);
965
return imerge->or_sel_imerge_with_checks(param, im2->head());
970
Perform OR operation on index_merge list and key tree.
973
0 OK, result is stored in *im1.
977
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
978
List<SEL_IMERGE> *im1,
982
List_iterator<SEL_IMERGE> it(*im1);
983
while ((imerge= it++))
985
if (imerge->or_sel_tree_with_checks(param, tree))
988
return im1->is_empty();
331
992
/***************************************************************************
332
** Basic functions for SqlSelect and QuickRangeSelect
993
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
333
994
***************************************************************************/
335
996
/* make a select from mysql info
366
1023
if (head->sort.io_cache)
368
memcpy(select->file, head->sort.io_cache, sizeof(internal::IO_CACHE));
369
select->records=(ha_rows) (select->file->end_of_file/
370
head->cursor->ref_length);
371
delete head->sort.io_cache;
1025
select->file= *head->sort.io_cache;
1026
select->records=(ha_rows) (select->file.end_of_file/
1027
head->file->ref_length);
1028
free(head->sort.io_cache);
372
1029
head->sort.io_cache=0;
378
optimizer::SqlSelect::SqlSelect()
382
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1035
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1037
quick_keys.clear_all(); needed_reg.clear_all();
391
void optimizer::SqlSelect::cleanup()
1042
void SQL_SELECT::cleanup()
405
file->close_cached_file();
1052
close_cached_file(&file);
409
optimizer::SqlSelect::~SqlSelect()
1056
SQL_SELECT::~SQL_SELECT()
415
bool optimizer::SqlSelect::check_quick(Session *session,
416
bool force_quick_range,
421
return (test_quick_select(session,
430
bool optimizer::SqlSelect::skip_record()
432
return (cond ? cond->val_int() == 0 : 0);
436
optimizer::QuickSelectInterface::QuickSelectInterface()
438
max_used_key_length(0),
1061
QUICK_SELECT_I::QUICK_SELECT_I()
1062
:max_used_key_length(0),
1066
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, Table *table, uint32_t key_nr,
1067
bool no_alloc, MEM_ROOT *parent_alloc,
1069
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1071
my_bitmap_map *bitmap;
1073
in_ror_merged_scan= 0;
1077
key_part_info= head->key_info[index].key_part;
1078
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1080
/* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1081
mrr_buf_size= thd->variables.read_rnd_buff_size;
1084
if (!no_alloc && !parent_alloc)
1086
// Allocates everything through the internal memroot
1087
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1088
thd->mem_root= &alloc;
1091
memset(&alloc, 0, sizeof(alloc));
1093
record= head->record[0];
1094
save_read_set= head->read_set;
1095
save_write_set= head->write_set;
1097
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1098
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1101
column_bitmap.bitmap= 0;
1105
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1110
int QUICK_RANGE_SELECT::init()
1112
if (file->inited != handler::NONE)
1113
file->ha_index_or_rnd_end();
1114
return(file->ha_index_init(index, 1));
1118
void QUICK_RANGE_SELECT::range_end()
1120
if (file->inited != handler::NONE)
1121
file->ha_index_or_rnd_end();
1125
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1129
/* file is NULL for CPK scan on covering ROR-intersection */
1136
file->extra(HA_EXTRA_NO_KEYREAD);
1140
file->ha_external_lock(current_thd, F_UNLCK);
1145
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1146
free_root(&alloc,MYF(0));
1147
free((char*) column_bitmap.bitmap);
1149
head->column_bitmaps_set(save_read_set, save_write_set);
1156
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1158
:pk_quick_select(NULL), thd(thd_param)
1162
memset(&read_record, 0, sizeof(read_record));
1163
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1167
int QUICK_INDEX_MERGE_SELECT::init()
1172
int QUICK_INDEX_MERGE_SELECT::reset()
1174
return(read_keys_and_merge());
1178
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1181
Save quick_select that does scan on clustered primary key as it will be
1182
processed separately.
1184
if (head->file->primary_key_is_clustered() &&
1185
quick_sel_range->index == head->s->primary_key)
1186
pk_quick_select= quick_sel_range;
1188
return quick_selects.push_back(quick_sel_range);
1192
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1194
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1195
QUICK_RANGE_SELECT* quick;
1197
while ((quick= quick_it++))
1199
quick_selects.delete_elements();
1200
delete pk_quick_select;
1201
free_root(&alloc,MYF(0));
1206
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1208
bool retrieve_full_rows,
1209
MEM_ROOT *parent_alloc)
1210
: cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
1215
record= head->record[0];
1217
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1219
memset(&alloc, 0, sizeof(MEM_ROOT));
1220
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1221
head->file->ref_length);
1226
Do post-constructor initialization.
1228
QUICK_ROR_INTERSECT_SELECT::init()
1235
int QUICK_ROR_INTERSECT_SELECT::init()
1237
/* Check if last_rowid was successfully allocated in ctor */
1238
return(!last_rowid);
1243
Initialize this quick select to be a ROR-merged scan.
1246
QUICK_RANGE_SELECT::init_ror_merged_scan()
1247
reuse_handler If true, use head->file, otherwise create a separate
1251
This function creates and prepares for subsequent use a separate handler
1252
object if it can't reuse head->file. The reason for this is that during
1253
ROR-merge several key scans are performed simultaneously, and a single
1254
handler is only capable of preserving context of a single key scan.
1256
In ROR-merge the quick select doing merge does full records retrieval,
1257
merged quick selects read only keys.
1260
0 ROR child scan initialized, ok to use.
1264
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1266
handler *save_file= file, *org_file;
1269
in_ror_merged_scan= 1;
1272
if (init() || reset())
1276
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1280
/* Create a separate handler object for this quick select */
1283
/* already have own 'handler' object. */
1288
if (!(file= head->file->clone(thd->mem_root)))
1291
Manually set the error flag. Note: there seems to be quite a few
1292
places where a failure could cause the server to "hang" the client by
1293
sending no response to a query. ATM those are not real errors because
1294
the storage engine calls in question happen to never fail with the
1295
existing storage engines.
1297
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1298
/* Caller will free the memory */
1299
goto failure; /* purecov: inspected */
1302
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1304
if (file->ha_external_lock(thd, F_RDLCK))
1307
if (init() || reset())
1309
file->ha_external_lock(thd, F_UNLCK);
1314
last_rowid= file->ref;
1318
We are only going to read key fields and call position() on 'file'
1319
The following sets head->tmp_set to only use this key and then updates
1320
head->read_set and head->write_set to use this bitmap.
1321
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1323
org_file= head->file;
1325
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1326
if (!head->no_keyread)
1329
head->mark_columns_used_by_index(index);
1331
head->prepare_for_position();
1332
head->file= org_file;
1333
bitmap_copy(&column_bitmap, head->read_set);
1334
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1339
head->column_bitmaps_set(save_read_set, save_write_set);
1347
Initialize this quick select to be a part of a ROR-merged scan.
1349
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1350
reuse_handler If true, use head->file, otherwise create separate
1356
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1358
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1359
QUICK_RANGE_SELECT* quick;
1361
/* Initialize all merged "children" quick selects */
1362
assert(!need_to_fetch_row || reuse_handler);
1363
if (!need_to_fetch_row && reuse_handler)
1367
There is no use of this->file. Use it for the first of merged range
1370
if (quick->init_ror_merged_scan(true))
1372
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1374
while ((quick= quick_it++))
1376
if (quick->init_ror_merged_scan(false))
1378
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1379
/* All merged scans share the same record buffer in intersection. */
1380
quick->record= head->record[0];
1383
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1392
Initialize quick select for row retrieval.
1400
int QUICK_ROR_INTERSECT_SELECT::reset()
1402
if (!scans_inited && init_ror_merged_scan(true))
1405
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1406
QUICK_RANGE_SELECT *quick;
1407
while ((quick= it++))
1414
Add a merged quick select to this ROR-intersection quick select.
1417
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1418
quick Quick select to be added. The quick select must return
1419
rows in rowid order.
1421
This call can only be made before init() is called.
1429
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1431
return quick_selects.push_back(quick);
1434
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1436
quick_selects.delete_elements();
1438
free_root(&alloc,MYF(0));
1439
if (need_to_fetch_row && head->file->inited != handler::NONE)
1440
head->file->ha_rnd_end();
1445
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1447
: thd(thd_param), scans_inited(false)
1451
rowid_length= table->file->ref_length;
1452
record= head->record[0];
1453
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1454
thd_param->mem_root= &alloc;
1459
Do post-constructor initialization.
1461
QUICK_ROR_UNION_SELECT::init()
1468
int QUICK_ROR_UNION_SELECT::init()
1470
if (init_queue(&queue, quick_selects.elements, 0,
1471
false , QUICK_ROR_UNION_SELECT::queue_cmp,
1474
memset(&queue, 0, sizeof(QUEUE));
1478
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1480
prev_rowid= cur_rowid + head->file->ref_length;
1486
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1490
QUICK_ROR_UNION_SELECT::queue_cmp()
1491
arg Pointer to QUICK_ROR_UNION_SELECT
1492
val1 First merged select
1493
val2 Second merged select
1496
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1498
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1499
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1500
((QUICK_SELECT_I*)val2)->last_rowid);
1505
Initialize quick select for row retrieval.
1514
int QUICK_ROR_UNION_SELECT::reset()
1516
QUICK_SELECT_I *quick;
1518
have_prev_rowid= false;
1521
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1522
while ((quick= it++))
1524
if (quick->init_ror_merged_scan(false))
1529
queue_remove_all(&queue);
1531
Initialize scans for merged quick selects and put all merged quick
1532
selects into the queue.
1534
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1535
while ((quick= it++))
1539
if ((error= quick->get_next()))
1541
if (error == HA_ERR_END_OF_FILE)
1545
quick->save_last_pos();
1546
queue_insert(&queue, (unsigned char*)quick);
1549
if (head->file->ha_rnd_init(1))
1559
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1561
return quick_selects.push_back(quick_sel_range);
1564
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1566
delete_queue(&queue);
1567
quick_selects.delete_elements();
1568
if (head->file->inited != handler::NONE)
1569
head->file->ha_rnd_end();
1570
free_root(&alloc,MYF(0));
1575
QUICK_RANGE::QUICK_RANGE()
1576
:min_key(0),max_key(0),min_length(0),max_length(0),
1577
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1578
min_keypart_map(0), max_keypart_map(0)
1581
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1584
min_flag=arg.min_flag;
1585
max_flag=arg.max_flag;
1586
maybe_flag=arg.maybe_flag;
1587
maybe_null=arg.maybe_null;
1590
min_value=arg.min_value;
1591
max_value=arg.max_value;
1592
next_key_part=arg.next_key_part;
1593
use_count=1; elements=1;
1597
inline void SEL_ARG::make_root()
1599
left=right= &null_element;
1602
use_count=0; elements=1;
1605
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1606
const unsigned char *max_value_arg)
1607
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1608
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1609
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1610
next_key_part(0),color(BLACK),type(KEY_RANGE)
1612
left=right= &null_element;
1615
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1616
unsigned char *min_value_, unsigned char *max_value_,
1617
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1618
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1619
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1620
field(field_), min_value(min_value_), max_value(max_value_),
1621
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1623
left=right= &null_element;
1626
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1631
/* Bail out if we have already generated too many SEL_ARGs */
1632
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1635
if (type != KEY_RANGE)
1637
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1638
return 0; // out of memory
1639
tmp->prev= *next_arg; // Link into next/prev chain
1640
(*next_arg)->next=tmp;
1645
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1646
min_flag, max_flag, maybe_flag)))
1648
tmp->parent=new_parent;
1649
tmp->next_key_part=next_key_part;
1650
if (left != &null_element)
1651
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1654
tmp->prev= *next_arg; // Link into next/prev chain
1655
(*next_arg)->next=tmp;
1658
if (right != &null_element)
1659
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1662
increment_use_count(1);
1664
tmp->elements= this->elements;
1668
SEL_ARG *SEL_ARG::first()
1670
SEL_ARG *next_arg=this;
1671
if (!next_arg->left)
1672
return 0; // MAYBE_KEY
1673
while (next_arg->left != &null_element)
1674
next_arg=next_arg->left;
1678
SEL_ARG *SEL_ARG::last()
1680
SEL_ARG *next_arg=this;
1681
if (!next_arg->right)
1682
return 0; // MAYBE_KEY
1683
while (next_arg->right != &null_element)
1684
next_arg=next_arg->right;
1690
Check if a compare is ok, when one takes ranges in account
1691
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1694
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1698
/* First check if there was a compare to a min or max element */
1699
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1701
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1702
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1704
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1706
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1707
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1709
if (field->real_maybe_null()) // If null is part of key
1716
goto end; // NULL where equal
1717
a++; b++; // Skip NULL marker
1719
cmp=field->key_cmp(a , b);
1720
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1722
// Check if the compared equal arguments was defined with open/closed range
1724
if (a_flag & (NEAR_MIN | NEAR_MAX))
1726
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1728
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1729
return (a_flag & NEAR_MIN) ? 2 : -2;
1730
return (a_flag & NEAR_MIN) ? 1 : -1;
1732
if (b_flag & (NEAR_MIN | NEAR_MAX))
1733
return (b_flag & NEAR_MIN) ? -2 : 2;
1734
return 0; // The elements where equal
1738
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1740
SEL_ARG tmp_link,*next_arg,*root;
1741
next_arg= &tmp_link;
1742
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1744
next_arg->next=0; // Fix last link
1745
tmp_link.next->prev=0; // Fix first link
1746
if (root) // If not OOM
5115
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5135
if (key1->part != key2->part)
5139
return 0; // Can't optimize this
5142
// If one of the key is MAYBE_KEY then the found region may be bigger
5143
if (key1->type == SEL_ARG::MAYBE_KEY)
5149
if (key2->type == SEL_ARG::MAYBE_KEY)
5156
if (key1->use_count > 0)
5158
if (key2->use_count == 0 || key1->elements > key2->elements)
5160
std::swap(key1,key2);
5162
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5166
// Add tree at key2 to tree at key1
5167
bool key2_shared=key2->use_count != 0;
5168
key1->maybe_flag|=key2->maybe_flag;
5170
for (key2=key2->first(); key2; )
5172
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5177
tmp=key1->first(); // tmp.min > key2.min
5180
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5181
{ // Found tmp.max < key2.min
5182
SEL_ARG *next=tmp->next;
5183
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5185
// Join near ranges like tmp.max < 0 and key2.min >= 0
5186
SEL_ARG *key2_next=key2->next;
5189
if (!(key2=new SEL_ARG(*key2)))
5190
return 0; // out of memory
5191
key2->increment_use_count(key1->use_count+1);
5192
key2->next=key2_next; // New copy of key2
5194
key2->copy_min(tmp);
5195
if (!(key1=key1->tree_delete(tmp)))
5196
{ // Only one key in tree
5203
if (!(tmp=next)) // tmp.min > key2.min
5204
break; // Copy rest of key2
5207
{ // tmp.min > key2.min
5209
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5211
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5212
{ // ranges are connected
5213
tmp->copy_min_to_min(key2);
5214
key1->merge_flags(key2);
5215
if (tmp->min_flag & NO_MIN_RANGE &&
5216
tmp->max_flag & NO_MAX_RANGE)
5218
if (key1->maybe_flag)
5219
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5222
key2->increment_use_count(-1); // Free not used tree
5228
SEL_ARG *next=key2->next; // Keys are not overlapping
5231
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5234
key1=key1->insert(cpy);
5235
key2->increment_use_count(key1->use_count+1);
5238
key1=key1->insert(key2); // Will destroy key2_root
5245
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5246
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5248
if (tmp->is_same(key2))
5250
tmp->merge_flags(key2); // Copy maybe flags
5251
key2->increment_use_count(-1); // Free not used tree
5256
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5257
eq_tree(last->next->next_key_part,key2->next_key_part))
5261
key1=key1->tree_delete(save);
5263
last->copy_min(tmp);
5264
if (last->copy_min(key2) || last->copy_max(key2))
5267
for (; key2 ; key2=key2->next)
5268
key2->increment_use_count(-1); // Free not used tree
5269
if (key1->maybe_flag)
5270
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5278
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5279
{ // tmp.min <= x < key2.min
5280
SEL_ARG *new_arg=tmp->clone_first(key2);
5283
if ((new_arg->next_key_part= key1->next_key_part))
5284
new_arg->increment_use_count(key1->use_count+1);
5285
tmp->copy_min_to_min(key2);
5286
key1=key1->insert(new_arg);
5289
// tmp.min >= key2.min && tmp.min <= key2.max
5290
SEL_ARG key(*key2); // Get copy we can modify
5293
if (tmp->cmp_min_to_min(&key) > 0)
5294
{ // key.min <= x < tmp.min
5295
SEL_ARG *new_arg=key.clone_first(tmp);
5298
if ((new_arg->next_key_part=key.next_key_part))
5299
new_arg->increment_use_count(key1->use_count+1);
5300
key1=key1->insert(new_arg);
5302
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5303
{ // tmp.min. <= x <= tmp.max
5304
tmp->maybe_flag|= key.maybe_flag;
5305
key.increment_use_count(key1->use_count+1);
5306
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5307
if (!cmp) // Key2 is ready
5309
key.copy_max_to_min(tmp);
5310
if (!(tmp=tmp->next))
5312
SEL_ARG *tmp2= new SEL_ARG(key);
5315
key1=key1->insert(tmp2);
5319
if (tmp->cmp_min_to_max(&key) > 0)
5321
SEL_ARG *tmp2= new SEL_ARG(key);
5324
key1=key1->insert(tmp2);
5330
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5333
tmp->copy_max_to_min(&key);
5334
tmp->increment_use_count(key1->use_count+1);
5335
/* Increment key count as it may be used for next loop */
5336
key.increment_use_count(1);
5337
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5338
key1=key1->insert(new_arg);
5348
SEL_ARG *next=key2->next;
5351
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5354
key2->increment_use_count(key1->use_count+1);
5355
key1=key1->insert(tmp);
5358
key1=key1->insert(key2); // Will destroy key2_root
5366
/* Compare if two trees are equal */
5368
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5372
if (!a || !b || !a->is_same(b))
5374
if (a->left != &null_element && b->left != &null_element)
5376
if (!eq_tree(a->left,b->left))
5379
else if (a->left != &null_element || b->left != &null_element)
5381
if (a->right != &null_element && b->right != &null_element)
5383
if (!eq_tree(a->right,b->right))
5386
else if (a->right != &null_element || b->right != &null_element)
5388
if (a->next_key_part != b->next_key_part)
5390
if (!a->next_key_part != !b->next_key_part ||
5391
!eq_tree(a->next_key_part, b->next_key_part))
5399
SEL_ARG::insert(SEL_ARG *key)
5401
SEL_ARG *element, **par= NULL, *last_element= NULL;
5403
for (element= this; element != &null_element ; )
5405
last_element=element;
5406
if (key->cmp_min_to_min(element) > 0)
5408
par= &element->right; element= element->right;
5412
par = &element->left; element= element->left;
5416
key->parent=last_element;
5418
if (par == &last_element->left)
5420
key->next=last_element;
5421
if ((key->prev=last_element->prev))
5422
key->prev->next=key;
5423
last_element->prev=key;
5427
if ((key->next=last_element->next))
5428
key->next->prev=key;
5429
key->prev=last_element;
5430
last_element->next=key;
5432
key->left=key->right= &null_element;
5433
SEL_ARG *root=rb_insert(key); // rebalance tree
5434
root->use_count=this->use_count; // copy root info
5435
root->elements= this->elements+1;
5436
root->maybe_flag=this->maybe_flag;
5442
** Find best key with min <= given key
5443
** Because the call context this should never return 0 to get_range
5447
SEL_ARG::find_range(SEL_ARG *key)
5449
SEL_ARG *element=this,*found=0;
5453
if (element == &null_element)
5455
int cmp=element->cmp_min_to_min(key);
5461
element=element->right;
5464
element=element->left;
5470
Remove a element from the tree
5474
key Key that is to be deleted from tree (this)
5477
This also frees all sub trees that is used by the element
5480
root of new tree (with key deleted)
5484
SEL_ARG::tree_delete(SEL_ARG *key)
5486
enum leaf_color remove_color;
5487
SEL_ARG *root,*nod,**par,*fix_par;
5492
/* Unlink from list */
5494
key->prev->next=key->next;
5496
key->next->prev=key->prev;
5497
key->increment_use_count(-1);
5501
par=key->parent_ptr();
5503
if (key->left == &null_element)
5505
*par=nod=key->right;
5506
fix_par=key->parent;
5507
if (nod != &null_element)
5508
nod->parent=fix_par;
5509
remove_color= key->color;
5511
else if (key->right == &null_element)
5513
*par= nod=key->left;
5514
nod->parent=fix_par=key->parent;
5515
remove_color= key->color;
5519
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5520
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5521
fix_par=tmp->parent;
5522
if (nod != &null_element)
5523
nod->parent=fix_par;
5524
remove_color= tmp->color;
5526
tmp->parent=key->parent; // Move node in place of key
5527
(tmp->left=key->left)->parent=tmp;
5528
if ((tmp->right=key->right) != &null_element)
5529
tmp->right->parent=tmp;
5530
tmp->color=key->color;
5532
if (fix_par == key) // key->right == key->next
5533
fix_par=tmp; // new parent of nod
5536
if (root == &null_element)
5537
return(0); // Maybe root later
5538
if (remove_color == BLACK)
5539
root=rb_delete_fixup(root,nod,fix_par);
5540
test_rb_tree(root,root->parent);
5542
root->use_count=this->use_count; // Fix root counters
5543
root->elements=this->elements-1;
5544
root->maybe_flag=this->maybe_flag;
5549
/* Functions to fix up the tree after insert and delete */
5551
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5553
SEL_ARG *y=leaf->right;
5554
leaf->right=y->left;
5555
if (y->left != &null_element)
5556
y->left->parent=leaf;
5557
if (!(y->parent=leaf->parent))
5560
*leaf->parent_ptr()=y;
5565
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5567
SEL_ARG *y=leaf->left;
5568
leaf->left=y->right;
5569
if (y->right != &null_element)
5570
y->right->parent=leaf;
5571
if (!(y->parent=leaf->parent))
5574
*leaf->parent_ptr()=y;
5581
SEL_ARG::rb_insert(SEL_ARG *leaf)
5583
SEL_ARG *y,*par,*par2,*root;
5584
root= this; root->parent= 0;
5587
while (leaf != root && (par= leaf->parent)->color == RED)
5588
{ // This can't be root or 1 level under
5589
if (par == (par2= leaf->parent->parent)->left)
5592
if (y->color == RED)
5597
leaf->color=RED; /* And the loop continues */
5601
if (leaf == par->right)
5603
left_rotate(&root,leaf->parent);
5604
par=leaf; /* leaf is now parent to old leaf */
5608
right_rotate(&root,par2);
5615
if (y->color == RED)
5620
leaf->color=RED; /* And the loop continues */
5624
if (leaf == par->left)
5626
right_rotate(&root,par);
5631
left_rotate(&root,par2);
5637
test_rb_tree(root,root->parent);
5642
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5648
while (x != root && x->color == SEL_ARG::BLACK)
5653
if (w->color == SEL_ARG::RED)
5655
w->color=SEL_ARG::BLACK;
5656
par->color=SEL_ARG::RED;
5657
left_rotate(&root,par);
5660
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5662
w->color=SEL_ARG::RED;
5667
if (w->right->color == SEL_ARG::BLACK)
5669
w->left->color=SEL_ARG::BLACK;
5670
w->color=SEL_ARG::RED;
5671
right_rotate(&root,w);
5674
w->color=par->color;
5675
par->color=SEL_ARG::BLACK;
5676
w->right->color=SEL_ARG::BLACK;
5677
left_rotate(&root,par);
5685
if (w->color == SEL_ARG::RED)
5687
w->color=SEL_ARG::BLACK;
5688
par->color=SEL_ARG::RED;
5689
right_rotate(&root,par);
5692
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5694
w->color=SEL_ARG::RED;
5699
if (w->left->color == SEL_ARG::BLACK)
5701
w->right->color=SEL_ARG::BLACK;
5702
w->color=SEL_ARG::RED;
5703
left_rotate(&root,w);
5706
w->color=par->color;
5707
par->color=SEL_ARG::BLACK;
5708
w->left->color=SEL_ARG::BLACK;
5709
right_rotate(&root,par);
5716
x->color=SEL_ARG::BLACK;
5721
/* Test that the properties for a red-black tree hold */
5724
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5726
int count_l,count_r;
5728
if (element == &null_element)
5729
return 0; // Found end of tree
5730
if (element->parent != parent)
5732
sql_print_error("Wrong tree: Parent doesn't point at parent");
5735
if (element->color == SEL_ARG::RED &&
5736
(element->left->color == SEL_ARG::RED ||
5737
element->right->color == SEL_ARG::RED))
5739
sql_print_error("Wrong tree: Found two red in a row");
5742
if (element->left == element->right && element->left != &null_element)
5744
sql_print_error("Wrong tree: Found right == left");
5747
count_l=test_rb_tree(element->left,element);
5748
count_r=test_rb_tree(element->right,element);
5749
if (count_l >= 0 && count_r >= 0)
5751
if (count_l == count_r)
5752
return count_l+(element->color == SEL_ARG::BLACK);
5753
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5756
return -1; // Error, no more warnings
5761
Count how many times SEL_ARG graph "root" refers to its part "key"
5764
count_key_part_usage()
5765
root An RB-Root node in a SEL_ARG graph.
5766
key Another RB-Root node in that SEL_ARG graph.
5769
The passed "root" node may refer to "key" node via root->next_key_part,
5772
This function counts how many times the node "key" is referred (via
5773
SEL_ARG::next_key_part) by
5774
- intervals of RB-tree pointed by "root",
5775
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5776
intervals of RB-tree pointed by "root",
5779
Here is an example (horizontal links represent next_key_part pointers,
5780
vertical links - next/prev prev pointers):
5783
|root|-----------------+
5787
+----+ +---+ $ | +---+ Here the return value
5788
| |- ... -| |---$-+--+->|key| will be 4.
5789
+----+ +---+ $ | | +---+
5794
| |---| |---------+ |
5801
Number of links to "key" from nodes reachable from "root".
5804
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5807
for (root=root->first(); root ; root=root->next)
5809
if (root->next_key_part)
5811
if (root->next_key_part == key)
5813
if (root->next_key_part->part < key->part)
5814
count+=count_key_part_usage(root->next_key_part,key);
5822
Check if SEL_ARG::use_count value is correct
5825
SEL_ARG::test_use_count()
5826
root The root node of the SEL_ARG graph (an RB-tree root node that
5827
has the least value of sel_arg->part in the entire graph, and
5828
thus is the "origin" of the graph)
5831
Check if SEL_ARG::use_count value is correct. See the definition of
5832
use_count for what is "correct".
5835
void SEL_ARG::test_use_count(SEL_ARG *root)
5838
if (this == root && use_count != 1)
5840
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5843
if (this->type != SEL_ARG::KEY_RANGE)
5845
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5848
if (pos->next_key_part)
5850
ulong count=count_key_part_usage(root,pos->next_key_part);
5851
if (count > pos->next_key_part->use_count)
5853
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5854
"should be %lu", (long unsigned int)pos,
5855
pos->next_key_part->use_count, count);
5858
pos->next_key_part->test_use_count(root);
5861
if (e_count != elements)
5862
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5863
e_count, elements, (long unsigned int) this);
3523
5868
/****************************************************************************
3524
5869
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3525
5870
****************************************************************************/
3527
5872
/* MRR range sequence, SEL_ARG* implementation: stack entry */
3528
typedef struct st_range_seq_entry
5873
typedef struct st_range_seq_entry
3531
5876
Pointers in min and max keys. They point to right-after-end of key
3532
5877
images. The 0-th entry has these pointing to key tuple start.
3534
5879
unsigned char *min_key, *max_key;
3537
5882
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3538
5883
min_key_flag may have NULL_RANGE set.
3540
5885
uint32_t min_key_flag, max_key_flag;
3542
5887
/* Number of key parts */
3543
5888
uint32_t min_key_parts, max_key_parts;
3544
optimizer::SEL_ARG *key_tree;
3545
5890
} RANGE_SEQ_ENTRY;
4339
Range sequence interface implementation for array<QuickRange>: initialize
6698
Perform key scans for all used indexes (except CPK), get rowids and merge
6699
them into an ordered non-recurrent sequence of rowids.
6701
The merge/duplicate removal is performed using Unique class. We put all
6702
rowids into Unique, get the sorted sequence and destroy the Unique.
6704
If table has a clustered primary key that covers all rows (true for bdb
6705
and innodb currently) and one of the index_merge scans is a scan on PK,
6706
then rows that will be retrieved by PK scan are not put into Unique and
6707
primary key scan is not performed here, it is performed later separately.
6714
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6716
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6717
QUICK_RANGE_SELECT* cur_quick;
6720
handler *file= head->file;
6722
file->extra(HA_EXTRA_KEYREAD);
6723
head->prepare_for_position();
6725
cur_quick_it.rewind();
6726
cur_quick= cur_quick_it++;
6727
assert(cur_quick != 0);
6730
We reuse the same instance of handler so we need to call both init and
6733
if (cur_quick->init() || cur_quick->reset())
6736
unique= new Unique(refpos_order_cmp, (void *)file,
6738
thd->variables.sortbuff_size);
6743
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6745
cur_quick->range_end();
6746
cur_quick= cur_quick_it++;
6750
if (cur_quick->file->inited != handler::NONE)
6751
cur_quick->file->ha_index_end();
6752
if (cur_quick->init() || cur_quick->reset())
6758
if (result != HA_ERR_END_OF_FILE)
6760
cur_quick->range_end();
6769
/* skip row if it will be retrieved by clustered PK scan */
6770
if (pk_quick_select && pk_quick_select->row_in_ranges())
6773
cur_quick->file->position(cur_quick->record);
6774
result= unique->unique_add((char*)cur_quick->file->ref);
6780
/* ok, all row ids are in Unique */
6781
result= unique->get(head);
6783
doing_pk_scan= false;
6784
/* index_merge currently doesn't support "using index" at all */
6785
file->extra(HA_EXTRA_NO_KEYREAD);
6786
/* start table scan */
6787
init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6793
Get next row for index_merge.
6795
The rows are read from
6796
1. rowids stored in Unique.
6797
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6798
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6801
int QUICK_INDEX_MERGE_SELECT::get_next()
6806
return(pk_quick_select->get_next());
6808
if ((result= read_record.read_record(&read_record)) == -1)
6810
result= HA_ERR_END_OF_FILE;
6811
end_read_record(&read_record);
6812
/* All rows from Unique have been retrieved, do a clustered PK scan */
6813
if (pk_quick_select)
6815
doing_pk_scan= true;
6816
if ((result= pk_quick_select->init()) ||
6817
(result= pk_quick_select->reset()))
6819
return(pk_quick_select->get_next());
6828
Retrieve next record.
6830
QUICK_ROR_INTERSECT_SELECT::get_next()
6833
Invariant on enter/exit: all intersected selects have retrieved all index
6834
records with rowid <= some_rowid_val and no intersected select has
6835
retrieved any index records with rowid > some_rowid_val.
6836
We start fresh and loop until we have retrieved the same rowid in each of
6837
the key scans or we got an error.
6839
If a Clustered PK scan is present, it is used only to check if row
6840
satisfies its condition (and never used for row retrieval).
6844
other - Error code if any error occurred.
6847
int QUICK_ROR_INTERSECT_SELECT::get_next()
6849
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6850
QUICK_RANGE_SELECT* quick;
6852
uint32_t last_rowid_count=0;
6856
/* Get a rowid for first quick and save it as a 'candidate' */
6858
error= quick->get_next();
6861
while (!error && !cpk_quick->row_in_ranges())
6862
error= quick->get_next();
6867
quick->file->position(quick->record);
6868
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6869
last_rowid_count= 1;
6871
while (last_rowid_count < quick_selects.elements)
6873
if (!(quick= quick_it++))
6881
if ((error= quick->get_next()))
6883
quick->file->position(quick->record);
6884
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6887
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6890
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6893
while (!cpk_quick->row_in_ranges())
6895
if ((error= quick->get_next()))
6899
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6900
last_rowid_count= 1;
6904
/* current 'candidate' row confirmed by this select */
6909
/* We get here if we got the same row ref in all scans. */
6910
if (need_to_fetch_row)
6911
error= head->file->rnd_pos(head->record[0], last_rowid);
6912
} while (error == HA_ERR_RECORD_DELETED);
6918
Retrieve next record.
6920
QUICK_ROR_UNION_SELECT::get_next()
6923
Enter/exit invariant:
6924
For each quick select in the queue a {key,rowid} tuple has been
6925
retrieved but the corresponding row hasn't been passed to output.
6929
other - Error code if any error occurred.
6932
int QUICK_ROR_UNION_SELECT::get_next()
6935
QUICK_SELECT_I *quick;
6942
if (!queue.elements)
6943
return(HA_ERR_END_OF_FILE);
6944
/* Ok, we have a queue with >= 1 scans */
6946
quick= (QUICK_SELECT_I*)queue_top(&queue);
6947
memcpy(cur_rowid, quick->last_rowid, rowid_length);
6949
/* put into queue rowid from the same stream as top element */
6950
if ((error= quick->get_next()))
6952
if (error != HA_ERR_END_OF_FILE)
6954
queue_remove(&queue, 0);
6958
quick->save_last_pos();
6959
queue_replaced(&queue);
6962
if (!have_prev_rowid)
6964
/* No rows have been returned yet */
6966
have_prev_rowid= true;
6969
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
6973
cur_rowid= prev_rowid;
6976
error= head->file->rnd_pos(quick->record, prev_rowid);
6977
} while (error == HA_ERR_RECORD_DELETED);
6982
int QUICK_RANGE_SELECT::reset()
6985
unsigned char *mrange_buff;
6987
HANDLER_BUFFER empty_buf;
6989
cur_range= (QUICK_RANGE**) ranges.buffer;
6991
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6994
/* Allocate buffer if we need one but haven't allocated it yet */
6995
if (mrr_buf_size && !mrr_buf_desc)
6997
buf_size= mrr_buf_size;
6998
while (buf_size && !my_multi_malloc(MYF(MY_WME),
6999
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7000
&mrange_buff, buf_size,
7003
/* Try to shrink the buffers until both are 0. */
7007
return(HA_ERR_OUT_OF_MEM);
7009
/* Initialize the handler buffer. */
7010
mrr_buf_desc->buffer= mrange_buff;
7011
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7012
mrr_buf_desc->end_of_used_area= mrange_buff;
7016
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7019
mrr_flags |= HA_MRR_SORTED;
7020
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7021
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7022
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7029
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4342
7032
quick_range_seq_init()
4343
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7033
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4344
7034
n_ranges Number of ranges in the sequence (ignored)
4345
flags MRR flags (currently not used)
7035
flags MRR flags (currently not used)
4348
7038
Opaque value to be passed to quick_range_seq_next
4351
range_seq_t optimizer::quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7041
range_seq_t quick_range_seq_init(void *init_param,
7042
uint32_t n_ranges __attribute__((unused)),
7043
uint32_t flags __attribute__((unused)))
4353
optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
4354
quick->qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
4355
quick->qr_traversal_ctx.cur= (optimizer::QuickRange**)quick->ranges.buffer;
7045
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7046
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7047
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
4356
7048
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4357
7049
quick->ranges.elements;
4358
7050
return &quick->qr_traversal_ctx;
4372
7064
1 No more ranges in the sequence
4374
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7067
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4376
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7069
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4378
7071
if (ctx->cur == ctx->last)
4379
7072
return 1; /* no more ranges */
4381
optimizer::QuickRange *cur= *(ctx->cur);
7074
QUICK_RANGE *cur= *(ctx->cur);
4382
7075
key_range *start_key= &range->start_key;
4383
key_range *end_key= &range->end_key;
7076
key_range *end_key= &range->end_key;
4385
start_key->key= cur->min_key;
7078
start_key->key= cur->min_key;
4386
7079
start_key->length= cur->min_length;
4387
7080
start_key->keypart_map= cur->min_keypart_map;
4388
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4389
(cur->flag & EQ_RANGE) ?
4390
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4391
end_key->key= cur->max_key;
4392
end_key->length= cur->max_length;
7081
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7082
(cur->flag & EQ_RANGE) ?
7083
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7084
end_key->key= cur->max_key;
7085
end_key->length= cur->max_length;
4393
7086
end_key->keypart_map= cur->max_keypart_map;
4395
7088
We use HA_READ_AFTER_KEY here because if we are reading on a key
4396
7089
prefix. We want to find all keys with this prefix.
4398
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7091
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4400
7093
range->range_flag= cur->flag;
4406
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4408
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4409
optimizer::SEL_TREE *range_tree,
4410
optimizer::Parameter *param,
4411
uint32_t *param_idx);
4413
static bool get_constant_key_infix(KeyInfo *index_info,
4414
optimizer::SEL_ARG *index_range_tree,
4415
KeyPartInfo *first_non_group_part,
4416
KeyPartInfo *min_max_arg_part,
4417
KeyPartInfo *last_part,
4419
unsigned char *key_infix,
4420
uint32_t *key_infix_len,
4421
KeyPartInfo **first_non_infix_part);
4423
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7100
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7103
mrr_persistent_flag_storage()
7104
seq Range sequence being traversed
7108
MRR/NDB implementation needs to store some bits for each range. This
7109
function returns a reference to the "range_flag" associated with the
7112
This function should be removed when we get a proper MRR/NDB
7116
Reference to range_flag associated with range number #idx
7119
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7121
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7122
return ctx->first[idx]->flag;
7127
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7130
mrr_get_ptr_by_idx()
7131
seq Range sequence bening traversed
7132
idx Number of the range
7135
An extension of MRR range sequence interface needed by NDB: return the
7136
data associated with the given range.
7138
A proper MRR interface implementer is supposed to store and return
7139
range-associated data. NDB stores number of the range instead. So this
7140
is a helper function that translates range number to range associated
7143
This function does nothing, as currrently there is only one user of the
7144
MRR interface - the quick range select code, and this user doesn't need
7145
to use range-associated data.
7148
Reference to range-associated data
7151
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7152
uint32_t idx __attribute__((unused)))
7160
Get next possible record using quick-struct.
7163
QUICK_RANGE_SELECT::get_next()
7166
Record is read into table->record[0]
7170
HA_ERR_END_OF_FILE No (more) rows in range
7174
int QUICK_RANGE_SELECT::get_next()
7177
if (in_ror_merged_scan)
7180
We don't need to signal the bitmap change as the bitmap is always the
7181
same for this head->file
7183
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7186
int result= file->multi_range_read_next(&dummy);
7188
if (in_ror_merged_scan)
7190
/* Restore bitmaps set on entry */
7191
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7198
Get the next record with a different prefix.
7201
QUICK_RANGE_SELECT::get_next_prefix()
7202
prefix_length length of cur_prefix
7203
cur_prefix prefix of a key to be searched for
7206
Each subsequent call to the method retrieves the first record that has a
7207
prefix with length prefix_length different from cur_prefix, such that the
7208
record with the new prefix is within the ranges described by
7209
this->ranges. The record found is stored into the buffer pointed by
7211
The method is useful for GROUP-BY queries with range conditions to
7212
discover the prefix of the next group that satisfies the range conditions.
7215
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7216
methods should be unified into a more general one to reduce code
7221
HA_ERR_END_OF_FILE if returned all keys
7222
other if some error occurred
7225
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7226
key_part_map keypart_map,
7227
unsigned char *cur_prefix)
7232
key_range start_key, end_key;
7235
/* Read the next record in the same range with prefix after cur_prefix. */
7236
assert(cur_prefix != 0);
7237
result= file->index_read_map(record, cur_prefix, keypart_map,
7239
if (result || (file->compare_key(file->end_range) <= 0))
7243
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7246
/* Ranges have already been used up before. None is left for read. */
7248
return(HA_ERR_END_OF_FILE);
7250
last_range= *(cur_range++);
7252
start_key.key= (const unsigned char*) last_range->min_key;
7253
start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7254
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7255
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7256
(last_range->flag & EQ_RANGE) ?
7257
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7258
end_key.key= (const unsigned char*) last_range->max_key;
7259
end_key.length= cmin(last_range->max_length, (uint16_t)prefix_length);
7260
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7262
We use READ_AFTER_KEY here because if we are reading on a key
7263
prefix we want to find all keys with this prefix
7265
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7268
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7269
last_range->max_keypart_map ? &end_key : 0,
7270
test(last_range->flag & EQ_RANGE),
7272
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7273
last_range= 0; // Stop searching
7275
if (result != HA_ERR_END_OF_FILE)
7277
last_range= 0; // No matching rows; go to next range
7283
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7286
It is assumed that currently a scan is being done on another index
7287
which reads all necessary parts of the index that is scanned by this
7289
The implementation does a binary search on sorted array of disjoint
7290
ranges, without taking size of range into account.
7292
This function is used to filter out clustered PK scan rows in
7293
index_merge quick select.
7296
true if current row will be retrieved by this quick select
7300
bool QUICK_RANGE_SELECT::row_in_ranges()
7304
uint32_t max= ranges.elements - 1;
7305
uint32_t mid= (max + min)/2;
7309
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7311
/* current row value > mid->max */
7316
mid= (min + max) / 2;
7318
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7319
return (!cmp_next(res) && !cmp_prev(res));
7323
This is a hack: we inherit from QUICK_SELECT so that we can use the
7324
get_next() interface, but we have to hold a pointer to the original
7325
QUICK_SELECT because its data are used all over the place. What
7326
should be done is to factor out the data that is needed into a base
7327
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7328
which handle the ranges and implement the get_next() function. But
7329
for now, this seems to work right at least.
7332
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7333
uint32_t used_key_parts_arg __attribute__((unused)),
7334
bool *create_err __attribute__((unused)))
7335
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7339
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7340
QUICK_RANGE **end_range= pr + ranges.elements;
7341
for (; pr!=end_range; pr++)
7342
rev_ranges.push_front(*pr);
7344
/* Remove EQ_RANGE flag for keys that are not using the full key */
7345
for (r = rev_it++; r; r = rev_it++)
7347
if ((r->flag & EQ_RANGE) &&
7348
head->key_info[index].key_length != r->max_length)
7349
r->flag&= ~EQ_RANGE;
7352
q->dont_free=1; // Don't free shared mem
7357
int QUICK_SELECT_DESC::get_next()
7359
/* The max key is handled as follows:
7360
* - if there is NO_MAX_RANGE, start at the end and move backwards
7361
* - if it is an EQ_RANGE, which means that max key covers the entire
7362
* key, go directly to the key and read through it (sorting backwards is
7363
* same as sorting forwards)
7364
* - if it is NEAR_MAX, go to the key or next, step back once, and
7366
* - otherwise (not NEAR_MAX == include the key), go after the key,
7367
* step back once, and move backwards
7374
{ // Already read through key
7375
result = ((last_range->flag & EQ_RANGE)
7376
? file->index_next_same(record, last_range->min_key,
7377
last_range->min_length) :
7378
file->index_prev(record));
7381
if (cmp_prev(*rev_it.ref()) == 0)
7384
else if (result != HA_ERR_END_OF_FILE)
7388
if (!(last_range= rev_it++))
7389
return(HA_ERR_END_OF_FILE); // All ranges used
7391
if (last_range->flag & NO_MAX_RANGE) // Read last record
7394
if ((local_error=file->index_last(record)))
7395
return(local_error); // Empty table
7396
if (cmp_prev(last_range) == 0)
7398
last_range= 0; // No match; go to next range
7402
if (last_range->flag & EQ_RANGE)
7404
result = file->index_read_map(record, last_range->max_key,
7405
last_range->max_keypart_map,
7410
assert(last_range->flag & NEAR_MAX ||
7411
range_reads_after_key(last_range));
7412
result=file->index_read_map(record, last_range->max_key,
7413
last_range->max_keypart_map,
7414
((last_range->flag & NEAR_MAX) ?
7415
HA_READ_BEFORE_KEY :
7416
HA_READ_PREFIX_LAST_OR_PREV));
7420
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7422
last_range= 0; // Not found, to next range
7425
if (cmp_prev(last_range) == 0)
7427
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7428
last_range= 0; // Stop searching
7429
return(0); // Found key is in range
7431
last_range= 0; // To next range
7437
Compare if found key is over max-value
7438
Returns 0 if key <= range->max_key
7439
TODO: Figure out why can't this function be as simple as cmp_prev().
7442
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7444
if (range_arg->flag & NO_MAX_RANGE)
7445
return 0; /* key can't be to large */
7447
KEY_PART *key_part=key_parts;
7448
uint32_t store_length;
7450
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7452
key+= store_length, key_part++)
7455
store_length= key_part->store_length;
7456
if (key_part->null_bit)
7460
if (!key_part->field->is_null())
7464
else if (key_part->field->is_null())
7466
key++; // Skip null byte
7469
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7474
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7479
Returns 0 if found key is inside range (found key >= range->min_key).
7482
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7485
if (range_arg->flag & NO_MIN_RANGE)
7486
return 0; /* key can't be to small */
7488
cmp= key_cmp(key_part_info, range_arg->min_key,
7489
range_arg->min_length);
7490
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7492
return 1; // outside of range
7497
* true if this range will require using HA_READ_AFTER_KEY
7498
See comment in get_next() about this
7501
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7503
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7504
!(range_arg->flag & EQ_RANGE) ||
7505
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7509
void QUICK_RANGE_SELECT::add_info_string(String *str)
7511
KEY *key_info= head->key_info + index;
7512
str->append(key_info->name);
7515
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7517
QUICK_RANGE_SELECT *quick;
7519
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7520
str->append(STRING_WITH_LEN("sort_union("));
7521
while ((quick= it++))
7527
quick->add_info_string(str);
7529
if (pk_quick_select)
7532
pk_quick_select->add_info_string(str);
7537
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7540
QUICK_RANGE_SELECT *quick;
7541
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7542
str->append(STRING_WITH_LEN("intersect("));
7543
while ((quick= it++))
7545
KEY *key_info= head->key_info + quick->index;
7550
str->append(key_info->name);
7554
KEY *key_info= head->key_info + cpk_quick->index;
7556
str->append(key_info->name);
7561
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7564
QUICK_SELECT_I *quick;
7565
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7566
str->append(STRING_WITH_LEN("union("));
7567
while ((quick= it++))
7573
quick->add_info_string(str);
7579
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7580
String *used_lengths)
7584
KEY *key_info= head->key_info + index;
7585
key_names->append(key_info->name);
7586
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7587
used_lengths->append(buf, length);
7590
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7591
String *used_lengths)
7596
QUICK_RANGE_SELECT *quick;
7598
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7599
while ((quick= it++))
7605
key_names->append(',');
7606
used_lengths->append(',');
7609
KEY *key_info= head->key_info + quick->index;
7610
key_names->append(key_info->name);
7611
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7612
used_lengths->append(buf, length);
7614
if (pk_quick_select)
7616
KEY *key_info= head->key_info + pk_quick_select->index;
7617
key_names->append(',');
7618
key_names->append(key_info->name);
7619
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7620
used_lengths->append(',');
7621
used_lengths->append(buf, length);
7625
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7626
String *used_lengths)
7631
QUICK_RANGE_SELECT *quick;
7632
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7633
while ((quick= it++))
7635
KEY *key_info= head->key_info + quick->index;
7640
key_names->append(',');
7641
used_lengths->append(',');
7643
key_names->append(key_info->name);
7644
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7645
used_lengths->append(buf, length);
7650
KEY *key_info= head->key_info + cpk_quick->index;
7651
key_names->append(',');
7652
key_names->append(key_info->name);
7653
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7654
used_lengths->append(',');
7655
used_lengths->append(buf, length);
7659
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7660
String *used_lengths)
7663
QUICK_SELECT_I *quick;
7664
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7665
while ((quick= it++))
7671
used_lengths->append(',');
7672
key_names->append(',');
7674
quick->add_keys_and_lengths(key_names, used_lengths);
7679
/*******************************************************************************
7680
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7681
*******************************************************************************/
7683
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7684
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7685
PARAM *param, uint32_t *param_idx);
7686
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7687
KEY_PART_INFO *first_non_group_part,
7688
KEY_PART_INFO *min_max_arg_part,
7689
KEY_PART_INFO *last_part, THD *thd,
7690
unsigned char *key_infix, uint32_t *key_infix_len,
7691
KEY_PART_INFO **first_non_infix_part);
7693
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7694
Field::imagetype image_type);
4426
cost_group_min_max(Table* table,
4427
KeyInfo *index_info,
4428
uint32_t used_key_parts,
4429
uint32_t group_key_parts,
4430
optimizer::SEL_TREE *range_tree,
4431
optimizer::SEL_ARG *index_tree,
4432
ha_rows quick_prefix_records,
7697
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7698
uint32_t group_key_parts, SEL_TREE *range_tree,
7699
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7700
bool have_min, bool have_max,
7701
double *read_cost, ha_rows *records);
5550
8754
quick->update_key_stat();
5551
8755
quick->adjust_prefix_ranges();
5557
optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5559
optimizer::QuickRangeSelect *quick= NULL;
5560
if ((quick= optimizer::get_quick_select(param,
5567
quick->records= records;
5568
quick->read_time= read_cost;
5574
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5576
boost::dynamic_bitset<> map= bitsToBitset();
5577
for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5588
size_t optimizer::RorScanInfo::getBitCount() const
5590
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5591
return tmp_bitset.count();
5595
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5597
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5598
tmp_bitset-= in_bitset;
5599
covered_fields= tmp_bitset.to_ulong();
5603
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5606
uint64_t conv= covered_fields;
5609
res.push_back((conv & 1) + '0');
5614
std::reverse(res.begin(), res.end());
5616
string final(covered_fields_size - res.length(), '0');
5618
return (boost::dynamic_bitset<>(final));
5622
} /* namespace drizzled */
8762
Construct new quick select for group queries with min/max.
8765
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8766
table The table being accessed
8767
join Descriptor of the current query
8768
have_min true if the query selects a MIN function
8769
have_max true if the query selects a MAX function
8770
min_max_arg_part The only argument field of all MIN/MAX functions
8771
group_prefix_len Length of all key parts in the group prefix
8772
prefix_key_parts All key parts in the group prefix
8773
index_info The index chosen for data access
8774
use_index The id of index_info
8775
read_cost Cost of this access method
8776
records Number of records returned
8777
key_infix_len Length of the key infix appended to the group prefix
8778
key_infix Infix of constants from equality predicates
8779
parent_alloc Memory pool for this and quick_prefix_select data
8785
QUICK_GROUP_MIN_MAX_SELECT::
8786
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8788
KEY_PART_INFO *min_max_arg_part_arg,
8789
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8790
uint32_t used_key_parts_arg, KEY *index_info_arg,
8791
uint32_t use_index, double read_cost_arg,
8792
ha_rows records_arg, uint32_t key_infix_len_arg,
8793
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8794
:join(join_arg), index_info(index_info_arg),
8795
group_prefix_len(group_prefix_len_arg),
8796
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8797
have_max(have_max_arg), seen_first_key(false),
8798
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8799
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8800
max_functions_it(NULL)
8805
record= head->record[0];
8806
tmp_record= head->record[1];
8807
read_time= read_cost_arg;
8808
records= records_arg;
8809
used_key_parts= used_key_parts_arg;
8810
real_key_parts= used_key_parts_arg;
8811
real_prefix_len= group_prefix_len + key_infix_len;
8813
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8816
We can't have parent_alloc set as the init function can't handle this case
8819
assert(!parent_alloc);
8822
init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8823
join->thd->mem_root= &alloc;
8826
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8831
Do post-constructor initialization.
8834
QUICK_GROUP_MIN_MAX_SELECT::init()
8837
The method performs initialization that cannot be done in the constructor
8838
such as memory allocations that may fail. It allocates memory for the
8839
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8840
updated during execution.
8847
int QUICK_GROUP_MIN_MAX_SELECT::init()
8849
if (group_prefix) /* Already initialized. */
8852
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8855
We may use group_prefix to store keys with all select fields, so allocate
8856
enough space for it.
8858
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
8859
real_prefix_len + min_max_arg_len)))
8862
if (key_infix_len > 0)
8865
The memory location pointed to by key_infix will be deleted soon, so
8866
allocate a new buffer and copy the key_infix into it.
8868
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
8871
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8872
this->key_infix= tmp_key_infix;
8875
if (min_max_arg_part)
8877
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8882
if (!(min_functions= new List<Item_sum>))
8886
min_functions= NULL;
8889
if (!(max_functions= new List<Item_sum>))
8893
max_functions= NULL;
8895
Item_sum *min_max_item;
8896
Item_sum **func_ptr= join->sum_funcs;
8897
while ((min_max_item= *(func_ptr++)))
8899
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8900
min_functions->push_back(min_max_item);
8901
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8902
max_functions->push_back(min_max_item);
8907
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
8913
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
8918
min_max_ranges.elements= 0;
8924
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8926
if (file->inited != handler::NONE)
8927
file->ha_index_end();
8928
if (min_max_arg_part)
8929
delete_dynamic(&min_max_ranges);
8930
free_root(&alloc,MYF(0));
8931
delete min_functions_it;
8932
delete max_functions_it;
8933
delete quick_prefix_select;
8939
Eventually create and add a new quick range object.
8942
QUICK_GROUP_MIN_MAX_SELECT::add_range()
8943
sel_range Range object from which a
8946
Construct a new QUICK_RANGE object from a SEL_ARG object, and
8947
add it to the array min_max_ranges. If sel_arg is an infinite
8948
range, e.g. (x < 5 or x > 4), then skip it and do not construct
8956
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8959
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
8961
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8962
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8965
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
8966
!(sel_range->max_flag & NO_MAX_RANGE))
8968
if (sel_range->maybe_null &&
8969
sel_range->min_value[0] && sel_range->max_value[0])
8970
range_flag|= NULL_RANGE; /* IS NULL condition */
8971
else if (memcmp(sel_range->min_value, sel_range->max_value,
8972
min_max_arg_len) == 0)
8973
range_flag|= EQ_RANGE; /* equality condition */
8975
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
8976
make_keypart_map(sel_range->part),
8977
sel_range->max_value, min_max_arg_len,
8978
make_keypart_map(sel_range->part),
8982
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
8989
Opens the ranges if there are more conditions in quick_prefix_select than
8990
the ones used for jumping through the prefixes.
8993
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
8996
quick_prefix_select is made over the conditions on the whole key.
8997
It defines a number of ranges of length x.
8998
However when jumping through the prefixes we use only the the first
8999
few most significant keyparts in the range key. However if there
9000
are more keyparts to follow the ones we are using we must make the
9001
condition on the key inclusive (because x < "ab" means
9002
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9003
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9005
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9007
if (quick_prefix_select &&
9008
group_prefix_len < quick_prefix_select->max_used_key_length)
9013
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9017
get_dynamic(arr, (unsigned char*)&range, inx);
9018
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9025
Determine the total number and length of the keys that will be used for
9029
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9032
The total length of the keys used for index lookup depends on whether
9033
there are any predicates referencing the min/max argument, and/or if
9034
the min/max argument field can be NULL.
9035
This function does an optimistic analysis whether the search key might
9036
be extended by a constant for the min/max keypart. It is 'optimistic'
9037
because during actual execution it may happen that a particular range
9038
is skipped, and then a shorter key will be used. However this is data
9039
dependent and can't be easily estimated here.
9045
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9047
max_used_key_length= real_prefix_len;
9048
if (min_max_ranges.elements > 0)
9050
QUICK_RANGE *cur_range;
9052
{ /* Check if the right-most range has a lower boundary. */
9053
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9054
min_max_ranges.elements - 1);
9055
if (!(cur_range->flag & NO_MIN_RANGE))
9057
max_used_key_length+= min_max_arg_len;
9063
{ /* Check if the left-most range has an upper boundary. */
9064
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9065
if (!(cur_range->flag & NO_MAX_RANGE))
9067
max_used_key_length+= min_max_arg_len;
9073
else if (have_min && min_max_arg_part &&
9074
min_max_arg_part->field->real_maybe_null())
9077
If a MIN/MAX argument value is NULL, we can quickly determine
9078
that we're in the beginning of the next group, because NULLs
9079
are always < any other value. This allows us to quickly
9080
determine the end of the current group and jump to the next
9081
group (see next_min()) and thus effectively increases the
9084
max_used_key_length+= min_max_arg_len;
9091
Initialize a quick group min/max select for key retrieval.
9094
QUICK_GROUP_MIN_MAX_SELECT::reset()
9097
Initialize the index chosen for access and find and store the prefix
9098
of the last group. The method is expensive since it performs disk access.
9105
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9109
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9110
if ((result= file->ha_index_init(index,1)))
9112
if (quick_prefix_select && quick_prefix_select->reset())
9114
result= file->index_last(record);
9115
if (result == HA_ERR_END_OF_FILE)
9117
/* Save the prefix of the last group. */
9118
key_copy(last_prefix, record, index_info, group_prefix_len);
9126
Get the next key containing the MIN and/or MAX key for the next group.
9129
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9132
The method finds the next subsequent group of records that satisfies the
9133
query conditions and finds the keys that contain the MIN/MAX values for
9134
the key part referenced by the MIN/MAX function(s). Once a group and its
9135
MIN/MAX values are found, store these values in the Item_sum objects for
9136
the MIN/MAX functions. The rest of the values in the result row are stored
9137
in the Item_field::result_field of each select field. If the query does
9138
not contain MIN and/or MAX functions, then the function only finds the
9139
group prefix, which is a query answer itself.
9142
If both MIN and MAX are computed, then we use the fact that if there is
9143
no MIN key, there can't be a MAX key as well, so we can skip looking
9144
for a MAX key in this case.
9148
HA_ERR_END_OF_FILE if returned all keys
9149
other if some error occurred
9152
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9157
int is_last_prefix= 0;
9160
Loop until a group is found that satisfies all query conditions or the last
9165
result= next_prefix();
9167
Check if this is the last group prefix. Notice that at this point
9168
this->record contains the current prefix in record format.
9172
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9174
assert(is_last_prefix <= 0);
9178
if (result == HA_ERR_KEY_NOT_FOUND)
9185
min_res= next_min();
9187
update_min_result();
9189
/* If there is no MIN in the group, there is no MAX either. */
9190
if ((have_max && !have_min) ||
9191
(have_max && have_min && (min_res == 0)))
9193
max_res= next_max();
9195
update_max_result();
9196
/* If a MIN was found, a MAX must have been found as well. */
9197
assert((have_max && !have_min) ||
9198
(have_max && have_min && (max_res == 0)));
9201
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9202
are equality predicates for the key parts after the group, find the
9203
first sub-group with the extended prefix.
9205
if (!have_min && !have_max && key_infix_len > 0)
9206
result= file->index_read_map(record, group_prefix,
9207
make_prev_keypart_map(real_key_parts),
9210
result= have_min ? min_res : have_max ? max_res : result;
9211
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9212
is_last_prefix != 0);
9217
Partially mimic the behavior of end_select_send. Copy the
9218
field data from Item_field::field into Item_field::result_field
9219
of each non-aggregated field (the group fields, and optionally
9220
other fields in non-ANSI SQL mode).
9222
copy_fields(&join->tmp_table_param);
9224
else if (result == HA_ERR_KEY_NOT_FOUND)
9225
result= HA_ERR_END_OF_FILE;
9232
Retrieve the minimal key in the next group.
9235
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9238
Find the minimal key within this group such that the key satisfies the query
9239
conditions and NULL semantics. The found key is loaded into this->record.
9242
Depending on the values of min_max_ranges.elements, key_infix_len, and
9243
whether there is a NULL in the MIN field, this function may directly
9244
return without any data access. In this case we use the key loaded into
9245
this->record by the call to this->next_prefix() just before this call.
9249
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9250
HA_ERR_END_OF_FILE - "" -
9251
other if some error occurred
9254
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9258
/* Find the MIN key using the eventually extended group prefix. */
9259
if (min_max_ranges.elements > 0)
9261
if ((result= next_min_in_range()))
9266
/* Apply the constant equality conditions to the non-group select fields */
9267
if (key_infix_len > 0)
9269
if ((result= file->index_read_map(record, group_prefix,
9270
make_prev_keypart_map(real_key_parts),
9271
HA_READ_KEY_EXACT)))
9276
If the min/max argument field is NULL, skip subsequent rows in the same
9277
group with NULL in it. Notice that:
9278
- if the first row in a group doesn't have a NULL in the field, no row
9279
in the same group has (because NULL < any other value),
9280
- min_max_arg_part->field->ptr points to some place in 'record'.
9282
if (min_max_arg_part && min_max_arg_part->field->is_null())
9284
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9285
key_copy(tmp_record, record, index_info, 0);
9286
result= file->index_read_map(record, tmp_record,
9287
make_keypart_map(real_key_parts),
9290
Check if the new record belongs to the current group by comparing its
9291
prefix with the group's prefix. If it is from the next group, then the
9292
whole group has NULLs in the MIN/MAX field, so use the first record in
9293
the group as a result.
9295
It is possible to reuse this new record as the result candidate for the
9296
next call to next_min(), and to save one lookup in the next call. For
9297
this add a new member 'this->next_group_prefix'.
9301
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9302
key_restore(record, tmp_record, index_info, 0);
9304
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9305
result= 0; /* There is a result in any case. */
9310
If the MIN attribute is non-nullable, this->record already contains the
9311
MIN key in the group, so just return.
9318
Retrieve the maximal key in the next group.
9321
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9324
Lookup the maximal key of the group, and store it into this->record.
9328
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9329
HA_ERR_END_OF_FILE - "" -
9330
other if some error occurred
9333
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9337
/* Get the last key in the (possibly extended) group. */
9338
if (min_max_ranges.elements > 0)
9339
result= next_max_in_range();
9341
result= file->index_read_map(record, group_prefix,
9342
make_prev_keypart_map(real_key_parts),
9343
HA_READ_PREFIX_LAST);
9349
Determine the prefix of the next group.
9352
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9355
Determine the prefix of the next group that satisfies the query conditions.
9356
If there is a range condition referencing the group attributes, use a
9357
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9358
condition. If there is a key infix of constants, append this infix
9359
immediately after the group attributes. The possibly extended prefix is
9360
stored in this->group_prefix. The first key of the found group is stored in
9361
this->record, on which relies this->next_min().
9365
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9366
HA_ERR_END_OF_FILE if there are no more keys
9367
other if some error occurred
9369
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9373
if (quick_prefix_select)
9375
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9376
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9377
make_prev_keypart_map(group_key_parts), cur_prefix)))
9379
seen_first_key= true;
9383
if (!seen_first_key)
9385
result= file->index_first(record);
9388
seen_first_key= true;
9392
/* Load the first key in this group into record. */
9393
result= file->index_read_map(record, group_prefix,
9394
make_prev_keypart_map(group_key_parts),
9401
/* Save the prefix of this group for subsequent calls. */
9402
key_copy(group_prefix, record, index_info, group_prefix_len);
9403
/* Append key_infix to group_prefix. */
9404
if (key_infix_len > 0)
9405
memcpy(group_prefix + group_prefix_len,
9406
key_infix, key_infix_len);
9413
Find the minimal key in a group that satisfies some range conditions for the
9414
min/max argument field.
9417
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9420
Given the sequence of ranges min_max_ranges, find the minimal key that is
9421
in the left-most possible range. If there is no such key, then the current
9422
group does not have a MIN key that satisfies the WHERE clause. If a key is
9423
found, its value is stored in this->record.
9427
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9429
HA_ERR_END_OF_FILE - "" -
9433
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9435
ha_rkey_function find_flag;
9436
key_part_map keypart_map;
9437
QUICK_RANGE *cur_range;
9438
bool found_null= false;
9439
int result= HA_ERR_KEY_NOT_FOUND;
9441
assert(min_max_ranges.elements > 0);
9443
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9444
{ /* Search from the left-most range to the right. */
9445
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9448
If the current value for the min/max argument is bigger than the right
9449
boundary of cur_range, there is no need to check this range.
9451
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9452
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9453
min_max_arg_len) == 1))
9456
if (cur_range->flag & NO_MIN_RANGE)
9458
keypart_map= make_prev_keypart_map(real_key_parts);
9459
find_flag= HA_READ_KEY_EXACT;
9463
/* Extend the search key with the lower boundary for this range. */
9464
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9465
cur_range->min_length);
9466
keypart_map= make_keypart_map(real_key_parts);
9467
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9468
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9469
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9472
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9475
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9476
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9477
continue; /* Check the next range. */
9480
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9481
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9482
range, it can't succeed for any other subsequent range.
9487
/* A key was found. */
9488
if (cur_range->flag & EQ_RANGE)
9489
break; /* No need to perform the checks below for equal keys. */
9491
if (cur_range->flag & NULL_RANGE)
9494
Remember this key, and continue looking for a non-NULL key that
9495
satisfies some other condition.
9497
memcpy(tmp_record, record, head->s->rec_buff_length);
9502
/* Check if record belongs to the current group. */
9503
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9505
result= HA_ERR_KEY_NOT_FOUND;
9509
/* If there is an upper limit, check if the found key is in the range. */
9510
if ( !(cur_range->flag & NO_MAX_RANGE) )
9512
/* Compose the MAX key for the range. */
9513
unsigned char *max_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9514
memcpy(max_key, group_prefix, real_prefix_len);
9515
memcpy(max_key + real_prefix_len, cur_range->max_key,
9516
cur_range->max_length);
9517
/* Compare the found key with max_key. */
9518
int cmp_res= key_cmp(index_info->key_part, max_key,
9519
real_prefix_len + min_max_arg_len);
9520
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9522
result= HA_ERR_KEY_NOT_FOUND;
9526
/* If we got to this point, the current key qualifies as MIN. */
9527
assert(result == 0);
9531
If there was a key with NULL in the MIN/MAX field, and there was no other
9532
key without NULL from the same group that satisfies some other condition,
9533
then use the key with the NULL.
9535
if (found_null && result)
9537
memcpy(record, tmp_record, head->s->rec_buff_length);
9545
Find the maximal key in a group that satisfies some range conditions for the
9546
min/max argument field.
9549
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9552
Given the sequence of ranges min_max_ranges, find the maximal key that is
9553
in the right-most possible range. If there is no such key, then the current
9554
group does not have a MAX key that satisfies the WHERE clause. If a key is
9555
found, its value is stored in this->record.
9559
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9561
HA_ERR_END_OF_FILE - "" -
9565
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9567
ha_rkey_function find_flag;
9568
key_part_map keypart_map;
9569
QUICK_RANGE *cur_range;
9572
assert(min_max_ranges.elements > 0);
9574
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9575
{ /* Search from the right-most range to the left. */
9576
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9579
If the current value for the min/max argument is smaller than the left
9580
boundary of cur_range, there is no need to check this range.
9582
if (range_idx != min_max_ranges.elements &&
9583
!(cur_range->flag & NO_MIN_RANGE) &&
9584
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9585
min_max_arg_len) == -1))
9588
if (cur_range->flag & NO_MAX_RANGE)
9590
keypart_map= make_prev_keypart_map(real_key_parts);
9591
find_flag= HA_READ_PREFIX_LAST;
9595
/* Extend the search key with the upper boundary for this range. */
9596
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9597
cur_range->max_length);
9598
keypart_map= make_keypart_map(real_key_parts);
9599
find_flag= (cur_range->flag & EQ_RANGE) ?
9600
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9601
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9604
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9608
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9609
(cur_range->flag & EQ_RANGE))
9610
continue; /* Check the next range. */
9613
In no key was found with this upper bound, there certainly are no keys
9614
in the ranges to the left.
9618
/* A key was found. */
9619
if (cur_range->flag & EQ_RANGE)
9620
return 0; /* No need to perform the checks below for equal keys. */
9622
/* Check if record belongs to the current group. */
9623
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9624
continue; // Row not found
9626
/* If there is a lower limit, check if the found key is in the range. */
9627
if ( !(cur_range->flag & NO_MIN_RANGE) )
9629
/* Compose the MIN key for the range. */
9630
unsigned char *min_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9631
memcpy(min_key, group_prefix, real_prefix_len);
9632
memcpy(min_key + real_prefix_len, cur_range->min_key,
9633
cur_range->min_length);
9634
/* Compare the found key with min_key. */
9635
int cmp_res= key_cmp(index_info->key_part, min_key,
9636
real_prefix_len + min_max_arg_len);
9637
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9641
/* If we got to this point, the current key qualifies as MAX. */
9644
return HA_ERR_KEY_NOT_FOUND;
9649
Update all MIN function results with the newly found value.
9652
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9655
The method iterates through all MIN functions and updates the result value
9656
of each function by calling Item_sum::reset(), which in turn picks the new
9657
result value from this->head->record[0], previously updated by
9658
next_min(). The updated value is stored in a member variable of each of the
9659
Item_sum objects, depending on the value type.
9662
The update must be done separately for MIN and MAX, immediately after
9663
next_min() was called and before next_max() is called, because both MIN and
9664
MAX take their result value from the same buffer this->head->record[0]
9665
(i.e. this->record).
9671
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9675
min_functions_it->rewind();
9676
while ((min_func= (*min_functions_it)++))
9682
Update all MAX function results with the newly found value.
9685
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9688
The method iterates through all MAX functions and updates the result value
9689
of each function by calling Item_sum::reset(), which in turn picks the new
9690
result value from this->head->record[0], previously updated by
9691
next_max(). The updated value is stored in a member variable of each of the
9692
Item_sum objects, depending on the value type.
9695
The update must be done separately for MIN and MAX, immediately after
9696
next_max() was called, because both MIN and MAX take their result value
9697
from the same buffer this->head->record[0] (i.e. this->record).
9703
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9707
max_functions_it->rewind();
9708
while ((max_func= (*max_functions_it)++))
9714
Append comma-separated list of keys this quick select uses to key_names;
9715
append comma-separated list of corresponding used lengths to used_lengths.
9718
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9719
key_names [out] Names of used indexes
9720
used_lengths [out] Corresponding lengths of the index names
9723
This method is used by select_describe to extract the names of the
9724
indexes used by a quick select.
9728
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9729
String *used_lengths)
9733
key_names->append(index_info->name);
9734
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9735
used_lengths->append(buf, length);
9738
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9739
const char *msg __attribute__((unused)))
9741
SEL_ARG **key,**end;
9745
String tmp(buff,sizeof(buff),&my_charset_bin);
9747
for (idx= 0,key=tree->keys, end=key+param->keys ;
9751
if (tree_map->is_set(idx))
9753
uint32_t keynr= param->real_keynr[idx];
9756
tmp.append(param->table->key_info[keynr].name);
9760
tmp.append(STRING_WITH_LEN("(empty)"));
9766
static void print_ror_scans_arr(Table *table,
9767
const char *msg __attribute__((unused)),
9768
struct st_ror_scan_info **start,
9769
struct st_ror_scan_info **end)
9772
String tmp(buff,sizeof(buff),&my_charset_bin);
9774
for (;start != end; start++)
9778
tmp.append(table->key_info[(*start)->keynr].name);
9781
tmp.append(STRING_WITH_LEN("(empty)"));
9785
/*****************************************************************************
9786
** Instantiate templates
9787
*****************************************************************************/
9789
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9790
template class List<QUICK_RANGE>;
9791
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
