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>
137
#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
106
#ifdef USE_PRAGMA_IMPLEMENTATION
107
#pragma implementation // gcc: Class implementation
110
#include "mysql_priv.h"
111
#include "sql_select.h"
114
#define test_rb_tree(A,B) {}
115
#define test_use_count(A) {}
152
119
Convert double value to #rows. Currently this does floor(), and we
153
120
might consider using round() instead.
155
static inline ha_rows double2rows(double x)
157
return static_cast<ha_rows>(x);
160
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,
312
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
313
optimizer::SEL_TREE *tree2,
314
optimizer::RangeParameter *param);
122
#define double2rows(x) ((ha_rows)(x))
124
static int sel_cmp(Field *f,uchar *a,uchar *b,uint8_t a_flag,uint8_t b_flag);
126
static uchar is_null_string[2]= {1,0};
128
class RANGE_OPT_PARAM;
130
A construction block of the SEL_ARG-graph.
132
The following description only covers graphs of SEL_ARG objects with
133
sel_arg->type==KEY_RANGE:
135
One SEL_ARG object represents an "elementary interval" in form
137
min_value <=? table.keypartX <=? max_value
139
The interval is a non-empty interval of any kind: with[out] minimum/maximum
140
bound, [half]open/closed, single-point interval, etc.
142
1. SEL_ARG GRAPH STRUCTURE
144
SEL_ARG objects are linked together in a graph. The meaning of the graph
145
is better demostrated by an example:
150
| part=1 $ part=2 $ part=3
152
| +-------+ $ +-------+ $ +--------+
153
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
154
| +-------+ $ +-------+ $ +--------+
160
\->| kp1=2 |--$--------------$-+
161
+-------+ $ $ | +--------+
163
+-------+ $ $ | +--------+
164
| kp1=3 |--$--------------$-+ |
165
+-------+ $ $ +--------+
169
The entire graph is partitioned into "interval lists".
171
An interval list is a sequence of ordered disjoint intervals over the same
172
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
173
all intervals in the list form an RB-tree, linked via left/right/parent
174
pointers. The RB-tree root SEL_ARG object will be further called "root of the
177
In the example pic, there are 4 interval lists:
178
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
179
The vertical lines represent SEL_ARG::next/prev pointers.
181
In an interval list, each member X may have SEL_ARG::next_key_part pointer
182
pointing to the root of another interval list Y. The pointed interval list
183
must cover a key part with greater number (i.e. Y->part > X->part).
185
In the example pic, the next_key_part pointers are represented by
188
2. SEL_ARG GRAPH SEMANTICS
190
It represents a condition in a special form (we don't have a name for it ATM)
191
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
193
For example, the picture represents the condition in form:
194
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
195
(kp1=2 AND (kp3=11 OR kp3=14)) OR
196
(kp1=3 AND (kp3=11 OR kp3=14))
201
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
202
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
203
intervals (i.e. intervals in form
205
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
207
Those intervals can be used to access the index. The uses are in:
208
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
209
how many table records are contained within all
211
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
212
and create QUICK_RANGE_SELECT object that will
213
read records within these intervals.
215
4. SPACE COMPLEXITY NOTES
217
SEL_ARG graph is a representation of an ordered disjoint sequence of
218
intervals over the ordered set of index tuple values.
220
For multi-part keys, one can construct a WHERE expression such that its
221
list of intervals will be of combinatorial size. Here is an example:
223
(keypart1 IN (1,2, ..., n1)) AND
224
(keypart2 IN (1,2, ..., n2)) AND
225
(keypart3 IN (1,2, ..., n3))
227
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
230
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
232
SEL_ARG graph structure aims to reduce the amount of required space by
233
"sharing" the elementary intervals when possible (the pic at the
234
beginning of this comment has examples of such sharing). The sharing may
235
prevent combinatorial blowup:
237
There are WHERE clauses that have combinatorial-size interval lists but
238
will be represented by a compact SEL_ARG graph.
240
(keypartN IN (1,2, ..., n1)) AND
242
(keypart2 IN (1,2, ..., n2)) AND
243
(keypart1 IN (1,2, ..., n3))
245
but not in all cases:
247
- There are WHERE clauses that do have a compact SEL_ARG-graph
248
representation but get_mm_tree() and its callees will construct a
249
graph of combinatorial size.
251
(keypart1 IN (1,2, ..., n1)) AND
252
(keypart2 IN (1,2, ..., n2)) AND
254
(keypartN IN (1,2, ..., n3))
256
- There are WHERE clauses for which the minimal possible SEL_ARG graph
257
representation will have combinatorial size.
259
By induction: Let's take any interval on some keypart in the middle:
263
Then let's AND it with this interval 'structure' from preceding and
266
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
268
We will obtain this SEL_ARG graph:
272
+---------+ $ +---------+ $ +---------+
273
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
274
+---------+ $ +---------+ $ +---------+
276
+---------+ $ +---------+ $
277
| kp14=c2 |--$-->| kp15=c0 | $
278
+---------+ $ +---------+ $
281
Note that we had to duplicate "kp15=c0" and there was no way to avoid
283
The induction step: AND the obtained expression with another "wrapping"
285
When the process ends because of the limit on max. number of keyparts
288
WHERE clause length is O(3*#max_keyparts)
289
SEL_ARG graph size is O(2^(#max_keyparts/2))
291
(it is also possible to construct a case where instead of 2 in 2^n we
292
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
295
We avoid consuming too much memory by setting a limit on the number of
296
SEL_ARG object we can construct during one range analysis invocation.
299
class SEL_ARG :public Sql_alloc
302
uint8_t min_flag,max_flag,maybe_flag;
303
uint8_t part; // Which key part
306
Number of children of this element in the RB-tree, plus 1 for this
311
Valid only for elements which are RB-tree roots: Number of times this
312
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
313
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
318
uchar *min_value,*max_value; // Pointer to range
321
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
323
SEL_ARG *left,*right; /* R-B tree children */
324
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
325
SEL_ARG *parent; /* R-B tree parent */
326
SEL_ARG *next_key_part;
327
enum leaf_color { BLACK,RED } color;
328
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
330
enum { MAX_SEL_ARGS = 16000 };
334
SEL_ARG(Field *,const uchar *, const uchar *);
335
SEL_ARG(Field *field, uint8_t part, uchar *min_value, uchar *max_value,
336
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
337
SEL_ARG(enum Type type_arg)
338
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
339
color(BLACK), type(type_arg)
341
inline bool is_same(SEL_ARG *arg)
343
if (type != arg->type || part != arg->part)
345
if (type != KEY_RANGE)
347
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
349
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
350
inline void maybe_smaller() { maybe_flag=1; }
351
/* Return true iff it's a single-point null interval */
352
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
353
inline int cmp_min_to_min(SEL_ARG* arg)
355
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
357
inline int cmp_min_to_max(SEL_ARG* arg)
359
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
361
inline int cmp_max_to_max(SEL_ARG* arg)
363
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
365
inline int cmp_max_to_min(SEL_ARG* arg)
367
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
369
SEL_ARG *clone_and(SEL_ARG* arg)
370
{ // Get overlapping range
371
uchar *new_min,*new_max;
372
uint8_t flag_min,flag_max;
373
if (cmp_min_to_min(arg) >= 0)
375
new_min=min_value; flag_min=min_flag;
379
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
381
if (cmp_max_to_max(arg) <= 0)
383
new_max=max_value; flag_max=max_flag;
387
new_max=arg->max_value; flag_max=arg->max_flag;
389
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
390
test(maybe_flag && arg->maybe_flag));
392
SEL_ARG *clone_first(SEL_ARG *arg)
393
{ // min <= X < arg->min
394
return new SEL_ARG(field,part, min_value, arg->min_value,
395
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
396
maybe_flag | arg->maybe_flag);
398
SEL_ARG *clone_last(SEL_ARG *arg)
399
{ // min <= X <= key_max
400
return new SEL_ARG(field, part, min_value, arg->max_value,
401
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
403
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
405
bool copy_min(SEL_ARG* arg)
406
{ // Get overlapping range
407
if (cmp_min_to_min(arg) > 0)
409
min_value=arg->min_value; min_flag=arg->min_flag;
410
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
411
(NO_MAX_RANGE | NO_MIN_RANGE))
412
return 1; // Full range
414
maybe_flag|=arg->maybe_flag;
417
bool copy_max(SEL_ARG* arg)
418
{ // Get overlapping range
419
if (cmp_max_to_max(arg) <= 0)
421
max_value=arg->max_value; max_flag=arg->max_flag;
422
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
423
(NO_MAX_RANGE | NO_MIN_RANGE))
424
return 1; // Full range
426
maybe_flag|=arg->maybe_flag;
430
void copy_min_to_min(SEL_ARG *arg)
432
min_value=arg->min_value; min_flag=arg->min_flag;
434
void copy_min_to_max(SEL_ARG *arg)
436
max_value=arg->min_value;
437
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
439
void copy_max_to_min(SEL_ARG *arg)
441
min_value=arg->max_value;
442
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
444
/* returns a number of keypart values (0 or 1) appended to the key buffer */
445
int store_min(uint length, uchar **min_key,uint min_key_flag)
447
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
448
if ((!(min_flag & NO_MIN_RANGE) &&
449
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
451
if (maybe_null && *min_value)
454
memset(*min_key+1, 0, length-1);
457
memcpy(*min_key,min_value,length);
463
/* returns a number of keypart values (0 or 1) appended to the key buffer */
464
int store_max(uint length, uchar **max_key, uint max_key_flag)
466
if (!(max_flag & NO_MAX_RANGE) &&
467
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
469
if (maybe_null && *max_value)
472
memset(*max_key+1, 0, length-1);
475
memcpy(*max_key,max_value,length);
482
/* returns a number of keypart values appended to the key buffer */
483
int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
485
SEL_ARG *key_tree= first();
486
uint res= key_tree->store_min(key[key_tree->part].store_length,
487
range_key, *range_key_flag);
488
*range_key_flag|= key_tree->min_flag;
490
if (key_tree->next_key_part &&
491
key_tree->next_key_part->part == key_tree->part+1 &&
492
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
493
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
494
res+= key_tree->next_key_part->store_min_key(key, range_key,
499
/* returns a number of keypart values appended to the key buffer */
500
int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
502
SEL_ARG *key_tree= last();
503
uint res=key_tree->store_max(key[key_tree->part].store_length,
504
range_key, *range_key_flag);
505
(*range_key_flag)|= key_tree->max_flag;
506
if (key_tree->next_key_part &&
507
key_tree->next_key_part->part == key_tree->part+1 &&
508
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
509
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
510
res+= key_tree->next_key_part->store_max_key(key, range_key,
515
SEL_ARG *insert(SEL_ARG *key);
516
SEL_ARG *tree_delete(SEL_ARG *key);
517
SEL_ARG *find_range(SEL_ARG *key);
518
SEL_ARG *rb_insert(SEL_ARG *leaf);
519
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
521
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
522
void test_use_count(SEL_ARG *root);
527
inline bool simple_key()
529
return !next_key_part && elements == 1;
531
void increment_use_count(long count)
535
next_key_part->use_count+=count;
536
count*= (next_key_part->use_count-count);
537
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
538
if (pos->next_key_part)
539
pos->increment_use_count(count);
544
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
545
if (pos->next_key_part)
547
pos->next_key_part->use_count--;
548
pos->next_key_part->free_tree();
552
inline SEL_ARG **parent_ptr()
554
return parent->left == this ? &parent->left : &parent->right;
559
Check if this SEL_ARG object represents a single-point interval
565
Check if this SEL_ARG object (not tree) represents a single-point
566
interval, i.e. if it represents a "keypart = const" or
570
true This SEL_ARG object represents a singlepoint interval
574
bool is_singlepoint()
577
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
578
flags, and the same for right edge.
580
if (min_flag || max_flag)
582
uchar *min_val= min_value;
583
uchar *max_val= max_value;
587
/* First byte is a NULL value indicator */
588
if (*min_val != *max_val)
592
return true; /* This "x IS NULL" */
596
return !field->key_cmp(min_val, max_val);
598
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
604
class SEL_TREE :public Sql_alloc
608
Starting an effort to document this field:
609
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
610
(type == SEL_TREE::IMPOSSIBLE)
612
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
613
SEL_TREE(enum Type type_arg) :type(type_arg) {}
614
SEL_TREE() :type(KEY)
616
keys_map.clear_all();
617
memset((char*) keys, 0, sizeof(keys));
620
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
621
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
622
merit in range analyzer functions (e.g. get_mm_parts) returning a
623
pointer to such SEL_TREE instead of NULL)
625
SEL_ARG *keys[MAX_KEY];
626
key_map keys_map; /* bitmask of non-NULL elements in keys */
629
Possible ways to read rows using index_merge. The list is non-empty only
630
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
632
List<SEL_IMERGE> merges;
634
/* The members below are filled/used only after get_mm_tree is done */
635
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
636
uint n_ror_scans; /* number of set bits in ror_scans_map */
638
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
639
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
640
/* Note that #records for each key scan is stored in table->quick_rows */
643
class RANGE_OPT_PARAM
646
THD *thd; /* Current thread handle */
647
TABLE *table; /* Table being analyzed */
648
COND *cond; /* Used inside get_mm_tree(). */
649
table_map prev_tables;
650
table_map read_tables;
651
table_map current_table; /* Bit of the table being analyzed */
653
/* Array of parts of all keys for which range analysis is performed */
655
KEY_PART *key_parts_end;
656
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
657
MEM_ROOT *old_root; /* Memory that will last until the query end */
659
Number of indexes used in range analysis (In SEL_TREE::keys only first
660
#keys elements are not empty)
665
If true, the index descriptions describe real indexes (and it is ok to
666
call field->optimize_range(real_keynr[...], ...).
667
Otherwise index description describes fake indexes.
669
bool using_real_indexes;
671
bool remove_jump_scans;
674
used_key_no -> table_key_no translation table. Only makes sense if
675
using_real_indexes==true
677
uint real_keynr[MAX_KEY];
678
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
679
uint alloced_sel_args;
680
bool force_default_mrr;
683
class PARAM : public RANGE_OPT_PARAM
686
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
689
/* Number of ranges in the last checked tree->key */
691
uchar min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
692
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
693
bool quick; // Don't calulate possible keys
695
uint fields_bitmap_size;
696
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
697
MY_BITMAP tmp_covered_fields;
699
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
701
uint *imerge_cost_buff; /* buffer for index_merge cost estimates */
702
uint imerge_cost_buff_size; /* size of the buffer */
704
/* true if last checked tree->key can be used for ROR-scan */
706
/* Number of ranges in the last checked tree->key */
710
class TABLE_READ_PLAN;
712
class TRP_ROR_INTERSECT;
714
class TRP_ROR_INDEX_MERGE;
715
class TRP_GROUP_MIN_MAX;
717
struct st_ror_scan_info;
719
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
720
Item_func::Functype type,Item *value,
721
Item_result cmp_type);
722
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
724
Item_func::Functype type,Item *value);
725
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
727
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8_t nparts);
728
static ha_rows check_quick_select(PARAM *param, uint idx, bool index_only,
729
SEL_ARG *tree, bool update_tbl_stats,
730
uint *mrr_flags, uint *bufsize,
732
//bool update_tbl_stats);
733
/*static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
734
uchar *min_key, uint min_key_flag, int,
735
uchar *max_key, uint max_key_flag, int);
738
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint index,
739
SEL_ARG *key_tree, uint mrr_flags,
740
uint mrr_buf_size, MEM_ROOT *alloc);
741
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
742
bool index_read_must_be_used,
743
bool update_tbl_stats,
746
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
748
bool *are_all_covering);
750
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
754
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
757
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
759
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
761
static void print_ror_scans_arr(TABLE *table, const char *msg,
762
struct st_ror_scan_info **start,
763
struct st_ror_scan_info **end);
765
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
766
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
767
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
768
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
769
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
771
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
772
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
773
SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
774
uchar *max_key,uint max_key_flag);
775
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
777
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
778
static bool null_part_in_key(KEY_PART *key_part, const uchar *key,
780
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
784
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
785
a condition in the following form:
786
(t_1||t_2||...||t_N) && (next)
788
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
789
(t_i,t_j) contains SEL_ARGS for the same index.
791
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
793
This class relies on memory manager to do the cleanup.
796
class SEL_IMERGE : public Sql_alloc
798
enum { PREALLOCED_TREES= 10};
800
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
801
SEL_TREE **trees; /* trees used to do index_merge */
802
SEL_TREE **trees_next; /* last of these trees */
803
SEL_TREE **trees_end; /* end of allocated space */
805
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
808
trees(&trees_prealloced[0]),
810
trees_end(trees + PREALLOCED_TREES)
812
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
813
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
814
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
819
Add SEL_TREE to this index_merge without any checks,
822
This function implements the following:
823
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
830
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
832
if (trees_next == trees_end)
834
const int realloc_ratio= 2; /* Double size for next round */
835
uint old_elements= (trees_end - trees);
836
uint old_size= sizeof(SEL_TREE**) * old_elements;
837
uint new_size= old_size * realloc_ratio;
838
SEL_TREE **new_trees;
839
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
841
memcpy(new_trees, trees, old_size);
843
trees_next= trees + old_elements;
844
trees_end= trees + old_elements * realloc_ratio;
846
*(trees_next++)= tree;
852
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
853
combining new_tree with one of the trees in this SEL_IMERGE if they both
854
have SEL_ARGs for the same key.
857
or_sel_tree_with_checks()
858
param PARAM from SQL_SELECT::test_quick_select
859
new_tree SEL_TREE with type KEY or KEY_SMALLER.
862
This does the following:
863
(t_1||...||t_k)||new_tree =
865
= (t_1||...||t_k||new_tree)
867
= (t_1||....||(t_j|| new_tree)||...||t_k),
869
where t_i, y are SEL_TREEs.
870
new_tree is combined with the first t_j it has a SEL_ARG on common
871
key with. As a consequence of this, choice of keys to do index_merge
872
read may depend on the order of conditions in WHERE part of the query.
876
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
877
and (*this) should be discarded.
878
-1 An error occurred.
881
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
883
for (SEL_TREE** tree = trees;
887
if (sel_trees_can_be_ored(*tree, new_tree, param))
889
*tree = tree_or(param, *tree, new_tree);
892
if (((*tree)->type == SEL_TREE::MAYBE) ||
893
((*tree)->type == SEL_TREE::ALWAYS))
895
/* SEL_TREE::IMPOSSIBLE is impossible here */
900
/* New tree cannot be combined with any of existing trees. */
901
return or_sel_tree(param, new_tree);
906
Perform OR operation on this index_merge and supplied index_merge list.
910
1 - One of conditions in result is always true and this SEL_IMERGE
912
-1 - An error occurred
915
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
917
for (SEL_TREE** tree= imerge->trees;
918
tree != imerge->trees_next;
921
if (or_sel_tree_with_checks(param, *tree))
322
929
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)
932
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
327
934
im1->concat(im2);
939
Perform OR operation on 2 index_merge lists, storing result in first list.
942
The following conversion is implemented:
943
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
946
i.e. all conjuncts except the first one are currently dropped.
947
This is done to avoid producing N*K ways to do index_merge.
949
If (a_1||b_1) produce a condition that is always true, NULL is returned
950
and index_merge is discarded (while it is actually possible to try
953
As a consequence of this, choice of keys to do index_merge read may depend
954
on the order of conditions in WHERE part of the query.
957
0 OK, result is stored in *im1
958
other Error, both passed lists are unusable
961
int imerge_list_or_list(RANGE_OPT_PARAM *param,
962
List<SEL_IMERGE> *im1,
963
List<SEL_IMERGE> *im2)
965
SEL_IMERGE *imerge= im1->head();
967
im1->push_back(imerge);
969
return imerge->or_sel_imerge_with_checks(param, im2->head());
974
Perform OR operation on index_merge list and key tree.
977
0 OK, result is stored in *im1.
981
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
982
List<SEL_IMERGE> *im1,
986
List_iterator<SEL_IMERGE> it(*im1);
987
while ((imerge= it++))
989
if (imerge->or_sel_tree_with_checks(param, tree))
992
return im1->is_empty();
331
996
/***************************************************************************
332
** Basic functions for SqlSelect and QuickRangeSelect
997
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
333
998
***************************************************************************/
335
1000
/* make a select from mysql info
366
1027
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;
1029
select->file= *head->sort.io_cache;
1030
select->records=(ha_rows) (select->file.end_of_file/
1031
head->file->ref_length);
1032
my_free(head->sort.io_cache, MYF(0));
372
1033
head->sort.io_cache=0;
378
optimizer::SqlSelect::SqlSelect()
382
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1039
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1041
quick_keys.clear_all(); needed_reg.clear_all();
391
void optimizer::SqlSelect::cleanup()
1046
void SQL_SELECT::cleanup()
405
file->close_cached_file();
1056
close_cached_file(&file);
409
optimizer::SqlSelect::~SqlSelect()
1060
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),
1065
QUICK_SELECT_I::QUICK_SELECT_I()
1066
:max_used_key_length(0),
1070
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, TABLE *table, uint key_nr,
1071
bool no_alloc, MEM_ROOT *parent_alloc,
1073
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1075
my_bitmap_map *bitmap;
1077
in_ror_merged_scan= 0;
1081
key_part_info= head->key_info[index].key_part;
1082
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1084
/* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1085
mrr_buf_size= thd->variables.read_rnd_buff_size;
1088
if (!no_alloc && !parent_alloc)
1090
// Allocates everything through the internal memroot
1091
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1092
thd->mem_root= &alloc;
1095
memset((char*) &alloc, 0, sizeof(alloc));
1097
record= head->record[0];
1098
save_read_set= head->read_set;
1099
save_write_set= head->write_set;
1101
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1102
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1105
column_bitmap.bitmap= 0;
1109
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1114
int QUICK_RANGE_SELECT::init()
1116
if (file->inited != handler::NONE)
1117
file->ha_index_or_rnd_end();
1118
return(file->ha_index_init(index, 1));
1122
void QUICK_RANGE_SELECT::range_end()
1124
if (file->inited != handler::NONE)
1125
file->ha_index_or_rnd_end();
1129
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1133
/* file is NULL for CPK scan on covering ROR-intersection */
1140
file->extra(HA_EXTRA_NO_KEYREAD);
1144
file->ha_external_lock(current_thd, F_UNLCK);
1149
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1150
free_root(&alloc,MYF(0));
1151
my_free((char*) column_bitmap.bitmap, MYF(MY_ALLOW_ZERO_PTR));
1153
head->column_bitmaps_set(save_read_set, save_write_set);
1154
x_free(mrr_buf_desc);
1159
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1161
:pk_quick_select(NULL), thd(thd_param)
1165
memset(&read_record, 0, sizeof(read_record));
1166
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1170
int QUICK_INDEX_MERGE_SELECT::init()
1175
int QUICK_INDEX_MERGE_SELECT::reset()
1177
return(read_keys_and_merge());
1181
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1184
Save quick_select that does scan on clustered primary key as it will be
1185
processed separately.
1187
if (head->file->primary_key_is_clustered() &&
1188
quick_sel_range->index == head->s->primary_key)
1189
pk_quick_select= quick_sel_range;
1191
return quick_selects.push_back(quick_sel_range);
1195
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1197
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1198
QUICK_RANGE_SELECT* quick;
1200
while ((quick= quick_it++))
1202
quick_selects.delete_elements();
1203
delete pk_quick_select;
1204
free_root(&alloc,MYF(0));
1209
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1211
bool retrieve_full_rows,
1212
MEM_ROOT *parent_alloc)
1213
: cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
1218
record= head->record[0];
1220
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1222
memset(&alloc, 0, sizeof(MEM_ROOT));
1223
last_rowid= (uchar*) alloc_root(parent_alloc? parent_alloc : &alloc,
1224
head->file->ref_length);
1229
Do post-constructor initialization.
1231
QUICK_ROR_INTERSECT_SELECT::init()
1238
int QUICK_ROR_INTERSECT_SELECT::init()
1240
/* Check if last_rowid was successfully allocated in ctor */
1241
return(!last_rowid);
1246
Initialize this quick select to be a ROR-merged scan.
1249
QUICK_RANGE_SELECT::init_ror_merged_scan()
1250
reuse_handler If true, use head->file, otherwise create a separate
1254
This function creates and prepares for subsequent use a separate handler
1255
object if it can't reuse head->file. The reason for this is that during
1256
ROR-merge several key scans are performed simultaneously, and a single
1257
handler is only capable of preserving context of a single key scan.
1259
In ROR-merge the quick select doing merge does full records retrieval,
1260
merged quick selects read only keys.
1263
0 ROR child scan initialized, ok to use.
1267
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1269
handler *save_file= file, *org_file;
1272
in_ror_merged_scan= 1;
1275
if (init() || reset())
1279
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1283
/* Create a separate handler object for this quick select */
1286
/* already have own 'handler' object. */
1291
if (!(file= head->file->clone(thd->mem_root)))
1294
Manually set the error flag. Note: there seems to be quite a few
1295
places where a failure could cause the server to "hang" the client by
1296
sending no response to a query. ATM those are not real errors because
1297
the storage engine calls in question happen to never fail with the
1298
existing storage engines.
1300
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1301
/* Caller will free the memory */
1302
goto failure; /* purecov: inspected */
1305
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1307
if (file->ha_external_lock(thd, F_RDLCK))
1310
if (init() || reset())
1312
file->ha_external_lock(thd, F_UNLCK);
1317
last_rowid= file->ref;
1321
We are only going to read key fields and call position() on 'file'
1322
The following sets head->tmp_set to only use this key and then updates
1323
head->read_set and head->write_set to use this bitmap.
1324
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1326
org_file= head->file;
1328
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1329
if (!head->no_keyread)
1332
head->mark_columns_used_by_index(index);
1334
head->prepare_for_position();
1335
head->file= org_file;
1336
bitmap_copy(&column_bitmap, head->read_set);
1337
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1342
head->column_bitmaps_set(save_read_set, save_write_set);
1350
Initialize this quick select to be a part of a ROR-merged scan.
1352
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1353
reuse_handler If true, use head->file, otherwise create separate
1359
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1361
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1362
QUICK_RANGE_SELECT* quick;
1364
/* Initialize all merged "children" quick selects */
1365
assert(!need_to_fetch_row || reuse_handler);
1366
if (!need_to_fetch_row && reuse_handler)
1370
There is no use of this->file. Use it for the first of merged range
1373
if (quick->init_ror_merged_scan(true))
1375
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1377
while ((quick= quick_it++))
1379
if (quick->init_ror_merged_scan(false))
1381
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1382
/* All merged scans share the same record buffer in intersection. */
1383
quick->record= head->record[0];
1386
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1395
Initialize quick select for row retrieval.
1403
int QUICK_ROR_INTERSECT_SELECT::reset()
1405
if (!scans_inited && init_ror_merged_scan(true))
1408
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1409
QUICK_RANGE_SELECT *quick;
1410
while ((quick= it++))
1417
Add a merged quick select to this ROR-intersection quick select.
1420
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1421
quick Quick select to be added. The quick select must return
1422
rows in rowid order.
1424
This call can only be made before init() is called.
1432
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1434
return quick_selects.push_back(quick);
1437
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1439
quick_selects.delete_elements();
1441
free_root(&alloc,MYF(0));
1442
if (need_to_fetch_row && head->file->inited != handler::NONE)
1443
head->file->ha_rnd_end();
1448
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1450
: thd(thd_param), scans_inited(false)
1454
rowid_length= table->file->ref_length;
1455
record= head->record[0];
1456
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1457
thd_param->mem_root= &alloc;
1462
Do post-constructor initialization.
1464
QUICK_ROR_UNION_SELECT::init()
1471
int QUICK_ROR_UNION_SELECT::init()
1473
if (init_queue(&queue, quick_selects.elements, 0,
1474
false , QUICK_ROR_UNION_SELECT::queue_cmp,
1477
memset(&queue, 0, sizeof(QUEUE));
1481
if (!(cur_rowid= (uchar*) alloc_root(&alloc, 2*head->file->ref_length)))
1483
prev_rowid= cur_rowid + head->file->ref_length;
1489
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1493
QUICK_ROR_UNION_SELECT::queue_cmp()
1494
arg Pointer to QUICK_ROR_UNION_SELECT
1495
val1 First merged select
1496
val2 Second merged select
1499
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, uchar *val1, uchar *val2)
1501
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1502
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1503
((QUICK_SELECT_I*)val2)->last_rowid);
1508
Initialize quick select for row retrieval.
1517
int QUICK_ROR_UNION_SELECT::reset()
1519
QUICK_SELECT_I *quick;
1521
have_prev_rowid= false;
1524
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1525
while ((quick= it++))
1527
if (quick->init_ror_merged_scan(false))
1532
queue_remove_all(&queue);
1534
Initialize scans for merged quick selects and put all merged quick
1535
selects into the queue.
1537
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1538
while ((quick= it++))
1542
if ((error= quick->get_next()))
1544
if (error == HA_ERR_END_OF_FILE)
1548
quick->save_last_pos();
1549
queue_insert(&queue, (uchar*)quick);
1552
if (head->file->ha_rnd_init(1))
1562
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1564
return quick_selects.push_back(quick_sel_range);
1567
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1569
delete_queue(&queue);
1570
quick_selects.delete_elements();
1571
if (head->file->inited != handler::NONE)
1572
head->file->ha_rnd_end();
1573
free_root(&alloc,MYF(0));
1578
QUICK_RANGE::QUICK_RANGE()
1579
:min_key(0),max_key(0),min_length(0),max_length(0),
1580
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1581
min_keypart_map(0), max_keypart_map(0)
1584
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1587
min_flag=arg.min_flag;
1588
max_flag=arg.max_flag;
1589
maybe_flag=arg.maybe_flag;
1590
maybe_null=arg.maybe_null;
1593
min_value=arg.min_value;
1594
max_value=arg.max_value;
1595
next_key_part=arg.next_key_part;
1596
use_count=1; elements=1;
1600
inline void SEL_ARG::make_root()
1602
left=right= &null_element;
1605
use_count=0; elements=1;
1608
SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg,
1609
const uchar *max_value_arg)
1610
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1611
elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
1612
max_value((uchar*) max_value_arg), next(0),prev(0),
1613
next_key_part(0),color(BLACK),type(KEY_RANGE)
1615
left=right= &null_element;
1618
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1619
uchar *min_value_, uchar *max_value_,
1620
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1621
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1622
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1623
field(field_), min_value(min_value_), max_value(max_value_),
1624
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1626
left=right= &null_element;
1629
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1634
/* Bail out if we have already generated too many SEL_ARGs */
1635
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1638
if (type != KEY_RANGE)
1640
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1641
return 0; // out of memory
1642
tmp->prev= *next_arg; // Link into next/prev chain
1643
(*next_arg)->next=tmp;
1648
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1649
min_flag, max_flag, maybe_flag)))
1651
tmp->parent=new_parent;
1652
tmp->next_key_part=next_key_part;
1653
if (left != &null_element)
1654
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1657
tmp->prev= *next_arg; // Link into next/prev chain
1658
(*next_arg)->next=tmp;
1661
if (right != &null_element)
1662
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1665
increment_use_count(1);
1667
tmp->elements= this->elements;
1671
SEL_ARG *SEL_ARG::first()
1673
SEL_ARG *next_arg=this;
1674
if (!next_arg->left)
1675
return 0; // MAYBE_KEY
1676
while (next_arg->left != &null_element)
1677
next_arg=next_arg->left;
1681
SEL_ARG *SEL_ARG::last()
1683
SEL_ARG *next_arg=this;
1684
if (!next_arg->right)
1685
return 0; // MAYBE_KEY
1686
while (next_arg->right != &null_element)
1687
next_arg=next_arg->right;
1693
Check if a compare is ok, when one takes ranges in account
1694
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1697
static int sel_cmp(Field *field, uchar *a, uchar *b, uint8_t a_flag,
1701
/* First check if there was a compare to a min or max element */
1702
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1704
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1705
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1707
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1709
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1710
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1712
if (field->real_maybe_null()) // If null is part of key
1719
goto end; // NULL where equal
1720
a++; b++; // Skip NULL marker
1722
cmp=field->key_cmp(a , b);
1723
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1725
// Check if the compared equal arguments was defined with open/closed range
1727
if (a_flag & (NEAR_MIN | NEAR_MAX))
1729
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1731
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1732
return (a_flag & NEAR_MIN) ? 2 : -2;
1733
return (a_flag & NEAR_MIN) ? 1 : -1;
1735
if (b_flag & (NEAR_MIN | NEAR_MAX))
1736
return (b_flag & NEAR_MIN) ? -2 : 2;
1737
return 0; // The elements where equal
1741
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1743
SEL_ARG tmp_link,*next_arg,*root;
1744
next_arg= &tmp_link;
1745
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1747
next_arg->next=0; // Fix last link
1748
tmp_link.next->prev=0; // Fix first link
1749
if (root) // If not OOM
5118
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5138
if (key1->part != key2->part)
5142
return 0; // Can't optimize this
5145
// If one of the key is MAYBE_KEY then the found region may be bigger
5146
if (key1->type == SEL_ARG::MAYBE_KEY)
5152
if (key2->type == SEL_ARG::MAYBE_KEY)
5159
if (key1->use_count > 0)
5161
if (key2->use_count == 0 || key1->elements > key2->elements)
5163
swap_variables(SEL_ARG *,key1,key2);
5165
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5169
// Add tree at key2 to tree at key1
5170
bool key2_shared=key2->use_count != 0;
5171
key1->maybe_flag|=key2->maybe_flag;
5173
for (key2=key2->first(); key2; )
5175
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5180
tmp=key1->first(); // tmp.min > key2.min
5183
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5184
{ // Found tmp.max < key2.min
5185
SEL_ARG *next=tmp->next;
5186
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5188
// Join near ranges like tmp.max < 0 and key2.min >= 0
5189
SEL_ARG *key2_next=key2->next;
5192
if (!(key2=new SEL_ARG(*key2)))
5193
return 0; // out of memory
5194
key2->increment_use_count(key1->use_count+1);
5195
key2->next=key2_next; // New copy of key2
5197
key2->copy_min(tmp);
5198
if (!(key1=key1->tree_delete(tmp)))
5199
{ // Only one key in tree
5206
if (!(tmp=next)) // tmp.min > key2.min
5207
break; // Copy rest of key2
5210
{ // tmp.min > key2.min
5212
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5214
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5215
{ // ranges are connected
5216
tmp->copy_min_to_min(key2);
5217
key1->merge_flags(key2);
5218
if (tmp->min_flag & NO_MIN_RANGE &&
5219
tmp->max_flag & NO_MAX_RANGE)
5221
if (key1->maybe_flag)
5222
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5225
key2->increment_use_count(-1); // Free not used tree
5231
SEL_ARG *next=key2->next; // Keys are not overlapping
5234
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5237
key1=key1->insert(cpy);
5238
key2->increment_use_count(key1->use_count+1);
5241
key1=key1->insert(key2); // Will destroy key2_root
5248
// tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges)
5249
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5251
if (tmp->is_same(key2))
5253
tmp->merge_flags(key2); // Copy maybe flags
5254
key2->increment_use_count(-1); // Free not used tree
5259
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5260
eq_tree(last->next->next_key_part,key2->next_key_part))
5264
key1=key1->tree_delete(save);
5266
last->copy_min(tmp);
5267
if (last->copy_min(key2) || last->copy_max(key2))
5270
for (; key2 ; key2=key2->next)
5271
key2->increment_use_count(-1); // Free not used tree
5272
if (key1->maybe_flag)
5273
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5281
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5282
{ // tmp.min <= x < key2.min
5283
SEL_ARG *new_arg=tmp->clone_first(key2);
5286
if ((new_arg->next_key_part= key1->next_key_part))
5287
new_arg->increment_use_count(key1->use_count+1);
5288
tmp->copy_min_to_min(key2);
5289
key1=key1->insert(new_arg);
5292
// tmp.min >= key2.min && tmp.min <= key2.max
5293
SEL_ARG key(*key2); // Get copy we can modify
5296
if (tmp->cmp_min_to_min(&key) > 0)
5297
{ // key.min <= x < tmp.min
5298
SEL_ARG *new_arg=key.clone_first(tmp);
5301
if ((new_arg->next_key_part=key.next_key_part))
5302
new_arg->increment_use_count(key1->use_count+1);
5303
key1=key1->insert(new_arg);
5305
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5306
{ // tmp.min. <= x <= tmp.max
5307
tmp->maybe_flag|= key.maybe_flag;
5308
key.increment_use_count(key1->use_count+1);
5309
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5310
if (!cmp) // Key2 is ready
5312
key.copy_max_to_min(tmp);
5313
if (!(tmp=tmp->next))
5315
SEL_ARG *tmp2= new SEL_ARG(key);
5318
key1=key1->insert(tmp2);
5322
if (tmp->cmp_min_to_max(&key) > 0)
5324
SEL_ARG *tmp2= new SEL_ARG(key);
5327
key1=key1->insert(tmp2);
5333
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5336
tmp->copy_max_to_min(&key);
5337
tmp->increment_use_count(key1->use_count+1);
5338
/* Increment key count as it may be used for next loop */
5339
key.increment_use_count(1);
5340
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5341
key1=key1->insert(new_arg);
5351
SEL_ARG *next=key2->next;
5354
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5357
key2->increment_use_count(key1->use_count+1);
5358
key1=key1->insert(tmp);
5361
key1=key1->insert(key2); // Will destroy key2_root
5369
/* Compare if two trees are equal */
5371
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5375
if (!a || !b || !a->is_same(b))
5377
if (a->left != &null_element && b->left != &null_element)
5379
if (!eq_tree(a->left,b->left))
5382
else if (a->left != &null_element || b->left != &null_element)
5384
if (a->right != &null_element && b->right != &null_element)
5386
if (!eq_tree(a->right,b->right))
5389
else if (a->right != &null_element || b->right != &null_element)
5391
if (a->next_key_part != b->next_key_part)
5393
if (!a->next_key_part != !b->next_key_part ||
5394
!eq_tree(a->next_key_part, b->next_key_part))
5402
SEL_ARG::insert(SEL_ARG *key)
5404
SEL_ARG *element, **par= NULL, *last_element= NULL;
5406
for (element= this; element != &null_element ; )
5408
last_element=element;
5409
if (key->cmp_min_to_min(element) > 0)
5411
par= &element->right; element= element->right;
5415
par = &element->left; element= element->left;
5419
key->parent=last_element;
5421
if (par == &last_element->left)
5423
key->next=last_element;
5424
if ((key->prev=last_element->prev))
5425
key->prev->next=key;
5426
last_element->prev=key;
5430
if ((key->next=last_element->next))
5431
key->next->prev=key;
5432
key->prev=last_element;
5433
last_element->next=key;
5435
key->left=key->right= &null_element;
5436
SEL_ARG *root=rb_insert(key); // rebalance tree
5437
root->use_count=this->use_count; // copy root info
5438
root->elements= this->elements+1;
5439
root->maybe_flag=this->maybe_flag;
5445
** Find best key with min <= given key
5446
** Because the call context this should never return 0 to get_range
5450
SEL_ARG::find_range(SEL_ARG *key)
5452
SEL_ARG *element=this,*found=0;
5456
if (element == &null_element)
5458
int cmp=element->cmp_min_to_min(key);
5464
element=element->right;
5467
element=element->left;
5473
Remove a element from the tree
5477
key Key that is to be deleted from tree (this)
5480
This also frees all sub trees that is used by the element
5483
root of new tree (with key deleted)
5487
SEL_ARG::tree_delete(SEL_ARG *key)
5489
enum leaf_color remove_color;
5490
SEL_ARG *root,*nod,**par,*fix_par;
5495
/* Unlink from list */
5497
key->prev->next=key->next;
5499
key->next->prev=key->prev;
5500
key->increment_use_count(-1);
5504
par=key->parent_ptr();
5506
if (key->left == &null_element)
5508
*par=nod=key->right;
5509
fix_par=key->parent;
5510
if (nod != &null_element)
5511
nod->parent=fix_par;
5512
remove_color= key->color;
5514
else if (key->right == &null_element)
5516
*par= nod=key->left;
5517
nod->parent=fix_par=key->parent;
5518
remove_color= key->color;
5522
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5523
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5524
fix_par=tmp->parent;
5525
if (nod != &null_element)
5526
nod->parent=fix_par;
5527
remove_color= tmp->color;
5529
tmp->parent=key->parent; // Move node in place of key
5530
(tmp->left=key->left)->parent=tmp;
5531
if ((tmp->right=key->right) != &null_element)
5532
tmp->right->parent=tmp;
5533
tmp->color=key->color;
5535
if (fix_par == key) // key->right == key->next
5536
fix_par=tmp; // new parent of nod
5539
if (root == &null_element)
5540
return(0); // Maybe root later
5541
if (remove_color == BLACK)
5542
root=rb_delete_fixup(root,nod,fix_par);
5543
test_rb_tree(root,root->parent);
5545
root->use_count=this->use_count; // Fix root counters
5546
root->elements=this->elements-1;
5547
root->maybe_flag=this->maybe_flag;
5552
/* Functions to fix up the tree after insert and delete */
5554
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5556
SEL_ARG *y=leaf->right;
5557
leaf->right=y->left;
5558
if (y->left != &null_element)
5559
y->left->parent=leaf;
5560
if (!(y->parent=leaf->parent))
5563
*leaf->parent_ptr()=y;
5568
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5570
SEL_ARG *y=leaf->left;
5571
leaf->left=y->right;
5572
if (y->right != &null_element)
5573
y->right->parent=leaf;
5574
if (!(y->parent=leaf->parent))
5577
*leaf->parent_ptr()=y;
5584
SEL_ARG::rb_insert(SEL_ARG *leaf)
5586
SEL_ARG *y,*par,*par2,*root;
5587
root= this; root->parent= 0;
5590
while (leaf != root && (par= leaf->parent)->color == RED)
5591
{ // This can't be root or 1 level under
5592
if (par == (par2= leaf->parent->parent)->left)
5595
if (y->color == RED)
5600
leaf->color=RED; /* And the loop continues */
5604
if (leaf == par->right)
5606
left_rotate(&root,leaf->parent);
5607
par=leaf; /* leaf is now parent to old leaf */
5611
right_rotate(&root,par2);
5618
if (y->color == RED)
5623
leaf->color=RED; /* And the loop continues */
5627
if (leaf == par->left)
5629
right_rotate(&root,par);
5634
left_rotate(&root,par2);
5640
test_rb_tree(root,root->parent);
5645
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5651
while (x != root && x->color == SEL_ARG::BLACK)
5656
if (w->color == SEL_ARG::RED)
5658
w->color=SEL_ARG::BLACK;
5659
par->color=SEL_ARG::RED;
5660
left_rotate(&root,par);
5663
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5665
w->color=SEL_ARG::RED;
5670
if (w->right->color == SEL_ARG::BLACK)
5672
w->left->color=SEL_ARG::BLACK;
5673
w->color=SEL_ARG::RED;
5674
right_rotate(&root,w);
5677
w->color=par->color;
5678
par->color=SEL_ARG::BLACK;
5679
w->right->color=SEL_ARG::BLACK;
5680
left_rotate(&root,par);
5688
if (w->color == SEL_ARG::RED)
5690
w->color=SEL_ARG::BLACK;
5691
par->color=SEL_ARG::RED;
5692
right_rotate(&root,par);
5695
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5697
w->color=SEL_ARG::RED;
5702
if (w->left->color == SEL_ARG::BLACK)
5704
w->right->color=SEL_ARG::BLACK;
5705
w->color=SEL_ARG::RED;
5706
left_rotate(&root,w);
5709
w->color=par->color;
5710
par->color=SEL_ARG::BLACK;
5711
w->left->color=SEL_ARG::BLACK;
5712
right_rotate(&root,par);
5719
x->color=SEL_ARG::BLACK;
5724
/* Test that the properties for a red-black tree hold */
5727
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5729
int count_l,count_r;
5731
if (element == &null_element)
5732
return 0; // Found end of tree
5733
if (element->parent != parent)
5735
sql_print_error("Wrong tree: Parent doesn't point at parent");
5738
if (element->color == SEL_ARG::RED &&
5739
(element->left->color == SEL_ARG::RED ||
5740
element->right->color == SEL_ARG::RED))
5742
sql_print_error("Wrong tree: Found two red in a row");
5745
if (element->left == element->right && element->left != &null_element)
5747
sql_print_error("Wrong tree: Found right == left");
5750
count_l=test_rb_tree(element->left,element);
5751
count_r=test_rb_tree(element->right,element);
5752
if (count_l >= 0 && count_r >= 0)
5754
if (count_l == count_r)
5755
return count_l+(element->color == SEL_ARG::BLACK);
5756
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5759
return -1; // Error, no more warnings
5764
Count how many times SEL_ARG graph "root" refers to its part "key"
5767
count_key_part_usage()
5768
root An RB-Root node in a SEL_ARG graph.
5769
key Another RB-Root node in that SEL_ARG graph.
5772
The passed "root" node may refer to "key" node via root->next_key_part,
5775
This function counts how many times the node "key" is referred (via
5776
SEL_ARG::next_key_part) by
5777
- intervals of RB-tree pointed by "root",
5778
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5779
intervals of RB-tree pointed by "root",
5782
Here is an example (horizontal links represent next_key_part pointers,
5783
vertical links - next/prev prev pointers):
5786
|root|-----------------+
5790
+----+ +---+ $ | +---+ Here the return value
5791
| |- ... -| |---$-+--+->|key| will be 4.
5792
+----+ +---+ $ | | +---+
5797
| |---| |---------+ |
5804
Number of links to "key" from nodes reachable from "root".
5807
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5810
for (root=root->first(); root ; root=root->next)
5812
if (root->next_key_part)
5814
if (root->next_key_part == key)
5816
if (root->next_key_part->part < key->part)
5817
count+=count_key_part_usage(root->next_key_part,key);
5825
Check if SEL_ARG::use_count value is correct
5828
SEL_ARG::test_use_count()
5829
root The root node of the SEL_ARG graph (an RB-tree root node that
5830
has the least value of sel_arg->part in the entire graph, and
5831
thus is the "origin" of the graph)
5834
Check if SEL_ARG::use_count value is correct. See the definition of
5835
use_count for what is "correct".
5838
void SEL_ARG::test_use_count(SEL_ARG *root)
5841
if (this == root && use_count != 1)
5843
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5846
if (this->type != SEL_ARG::KEY_RANGE)
5848
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5851
if (pos->next_key_part)
5853
ulong count=count_key_part_usage(root,pos->next_key_part);
5854
if (count > pos->next_key_part->use_count)
5856
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5857
"should be %lu", (long unsigned int)pos,
5858
pos->next_key_part->use_count, count);
5861
pos->next_key_part->test_use_count(root);
5864
if (e_count != elements)
5865
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5866
e_count, elements, (long unsigned int) this);
3523
5871
/****************************************************************************
3524
5872
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3525
5873
****************************************************************************/
3527
5875
/* MRR range sequence, SEL_ARG* implementation: stack entry */
3528
typedef struct st_range_seq_entry
5876
typedef struct st_range_seq_entry
3531
5879
Pointers in min and max keys. They point to right-after-end of key
3532
5880
images. The 0-th entry has these pointing to key tuple start.
3534
unsigned char *min_key, *max_key;
5882
uchar *min_key, *max_key;
3537
5885
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3538
5886
min_key_flag may have NULL_RANGE set.
3540
uint32_t min_key_flag, max_key_flag;
5888
uint min_key_flag, max_key_flag;
3542
5890
/* Number of key parts */
3543
uint32_t min_key_parts, max_key_parts;
3544
optimizer::SEL_ARG *key_tree;
5891
uint min_key_parts, max_key_parts;
3545
5893
} RANGE_SEQ_ENTRY;
4339
Range sequence interface implementation for array<QuickRange>: initialize
6701
Perform key scans for all used indexes (except CPK), get rowids and merge
6702
them into an ordered non-recurrent sequence of rowids.
6704
The merge/duplicate removal is performed using Unique class. We put all
6705
rowids into Unique, get the sorted sequence and destroy the Unique.
6707
If table has a clustered primary key that covers all rows (true for bdb
6708
and innodb currently) and one of the index_merge scans is a scan on PK,
6709
then rows that will be retrieved by PK scan are not put into Unique and
6710
primary key scan is not performed here, it is performed later separately.
6717
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6719
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6720
QUICK_RANGE_SELECT* cur_quick;
6723
handler *file= head->file;
6725
file->extra(HA_EXTRA_KEYREAD);
6726
head->prepare_for_position();
6728
cur_quick_it.rewind();
6729
cur_quick= cur_quick_it++;
6730
assert(cur_quick != 0);
6733
We reuse the same instance of handler so we need to call both init and
6736
if (cur_quick->init() || cur_quick->reset())
6739
unique= new Unique(refpos_order_cmp, (void *)file,
6741
thd->variables.sortbuff_size);
6746
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6748
cur_quick->range_end();
6749
cur_quick= cur_quick_it++;
6753
if (cur_quick->file->inited != handler::NONE)
6754
cur_quick->file->ha_index_end();
6755
if (cur_quick->init() || cur_quick->reset())
6761
if (result != HA_ERR_END_OF_FILE)
6763
cur_quick->range_end();
6772
/* skip row if it will be retrieved by clustered PK scan */
6773
if (pk_quick_select && pk_quick_select->row_in_ranges())
6776
cur_quick->file->position(cur_quick->record);
6777
result= unique->unique_add((char*)cur_quick->file->ref);
6783
/* ok, all row ids are in Unique */
6784
result= unique->get(head);
6786
doing_pk_scan= false;
6787
/* index_merge currently doesn't support "using index" at all */
6788
file->extra(HA_EXTRA_NO_KEYREAD);
6789
/* start table scan */
6790
init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6796
Get next row for index_merge.
6798
The rows are read from
6799
1. rowids stored in Unique.
6800
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6801
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6804
int QUICK_INDEX_MERGE_SELECT::get_next()
6809
return(pk_quick_select->get_next());
6811
if ((result= read_record.read_record(&read_record)) == -1)
6813
result= HA_ERR_END_OF_FILE;
6814
end_read_record(&read_record);
6815
/* All rows from Unique have been retrieved, do a clustered PK scan */
6816
if (pk_quick_select)
6818
doing_pk_scan= true;
6819
if ((result= pk_quick_select->init()) ||
6820
(result= pk_quick_select->reset()))
6822
return(pk_quick_select->get_next());
6831
Retrieve next record.
6833
QUICK_ROR_INTERSECT_SELECT::get_next()
6836
Invariant on enter/exit: all intersected selects have retrieved all index
6837
records with rowid <= some_rowid_val and no intersected select has
6838
retrieved any index records with rowid > some_rowid_val.
6839
We start fresh and loop until we have retrieved the same rowid in each of
6840
the key scans or we got an error.
6842
If a Clustered PK scan is present, it is used only to check if row
6843
satisfies its condition (and never used for row retrieval).
6847
other - Error code if any error occurred.
6850
int QUICK_ROR_INTERSECT_SELECT::get_next()
6852
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6853
QUICK_RANGE_SELECT* quick;
6855
uint last_rowid_count=0;
6859
/* Get a rowid for first quick and save it as a 'candidate' */
6861
error= quick->get_next();
6864
while (!error && !cpk_quick->row_in_ranges())
6865
error= quick->get_next();
6870
quick->file->position(quick->record);
6871
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6872
last_rowid_count= 1;
6874
while (last_rowid_count < quick_selects.elements)
6876
if (!(quick= quick_it++))
6884
if ((error= quick->get_next()))
6886
quick->file->position(quick->record);
6887
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6890
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6893
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6896
while (!cpk_quick->row_in_ranges())
6898
if ((error= quick->get_next()))
6902
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6903
last_rowid_count= 1;
6907
/* current 'candidate' row confirmed by this select */
6912
/* We get here if we got the same row ref in all scans. */
6913
if (need_to_fetch_row)
6914
error= head->file->rnd_pos(head->record[0], last_rowid);
6915
} while (error == HA_ERR_RECORD_DELETED);
6921
Retrieve next record.
6923
QUICK_ROR_UNION_SELECT::get_next()
6926
Enter/exit invariant:
6927
For each quick select in the queue a {key,rowid} tuple has been
6928
retrieved but the corresponding row hasn't been passed to output.
6932
other - Error code if any error occurred.
6935
int QUICK_ROR_UNION_SELECT::get_next()
6938
QUICK_SELECT_I *quick;
6945
if (!queue.elements)
6946
return(HA_ERR_END_OF_FILE);
6947
/* Ok, we have a queue with >= 1 scans */
6949
quick= (QUICK_SELECT_I*)queue_top(&queue);
6950
memcpy(cur_rowid, quick->last_rowid, rowid_length);
6952
/* put into queue rowid from the same stream as top element */
6953
if ((error= quick->get_next()))
6955
if (error != HA_ERR_END_OF_FILE)
6957
queue_remove(&queue, 0);
6961
quick->save_last_pos();
6962
queue_replaced(&queue);
6965
if (!have_prev_rowid)
6967
/* No rows have been returned yet */
6969
have_prev_rowid= true;
6972
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
6976
cur_rowid= prev_rowid;
6979
error= head->file->rnd_pos(quick->record, prev_rowid);
6980
} while (error == HA_ERR_RECORD_DELETED);
6985
int QUICK_RANGE_SELECT::reset()
6990
HANDLER_BUFFER empty_buf;
6992
cur_range= (QUICK_RANGE**) ranges.buffer;
6994
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6997
/* Allocate buffer if we need one but haven't allocated it yet */
6998
if (mrr_buf_size && !mrr_buf_desc)
7000
buf_size= mrr_buf_size;
7001
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7002
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7003
&mrange_buff, buf_size,
7006
/* Try to shrink the buffers until both are 0. */
7010
return(HA_ERR_OUT_OF_MEM);
7012
/* Initialize the handler buffer. */
7013
mrr_buf_desc->buffer= mrange_buff;
7014
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7015
mrr_buf_desc->end_of_used_area= mrange_buff;
7019
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7022
mrr_flags |= HA_MRR_SORTED;
7023
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7024
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7025
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7032
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4342
7035
quick_range_seq_init()
4343
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7036
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4344
7037
n_ranges Number of ranges in the sequence (ignored)
4345
flags MRR flags (currently not used)
7038
flags MRR flags (currently not used)
4348
7041
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)
7044
range_seq_t quick_range_seq_init(void *init_param,
7045
uint n_ranges __attribute__((unused)),
7046
uint 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;
7048
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7049
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7050
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
4356
7051
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4357
7052
quick->ranges.elements;
4358
7053
return &quick->qr_traversal_ctx;
4372
7067
1 No more ranges in the sequence
4374
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7070
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4376
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7072
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4378
7074
if (ctx->cur == ctx->last)
4379
7075
return 1; /* no more ranges */
4381
optimizer::QuickRange *cur= *(ctx->cur);
7077
QUICK_RANGE *cur= *(ctx->cur);
4382
7078
key_range *start_key= &range->start_key;
4383
key_range *end_key= &range->end_key;
7079
key_range *end_key= &range->end_key;
4385
start_key->key= cur->min_key;
7081
start_key->key= cur->min_key;
4386
7082
start_key->length= cur->min_length;
4387
7083
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;
7084
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7085
(cur->flag & EQ_RANGE) ?
7086
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7087
end_key->key= cur->max_key;
7088
end_key->length= cur->max_length;
4393
7089
end_key->keypart_map= cur->max_keypart_map;
4395
7091
We use HA_READ_AFTER_KEY here because if we are reading on a key
4396
7092
prefix. We want to find all keys with this prefix.
4398
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7094
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4400
7096
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);
7103
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7106
mrr_persistent_flag_storage()
7107
seq Range sequence being traversed
7111
MRR/NDB implementation needs to store some bits for each range. This
7112
function returns a reference to the "range_flag" associated with the
7115
This function should be removed when we get a proper MRR/NDB
7119
Reference to range_flag associated with range number #idx
7122
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint idx)
7124
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7125
return ctx->first[idx]->flag;
7130
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7133
mrr_get_ptr_by_idx()
7134
seq Range sequence bening traversed
7135
idx Number of the range
7138
An extension of MRR range sequence interface needed by NDB: return the
7139
data associated with the given range.
7141
A proper MRR interface implementer is supposed to store and return
7142
range-associated data. NDB stores number of the range instead. So this
7143
is a helper function that translates range number to range associated
7146
This function does nothing, as currrently there is only one user of the
7147
MRR interface - the quick range select code, and this user doesn't need
7148
to use range-associated data.
7151
Reference to range-associated data
7154
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7155
uint idx __attribute__((unused)))
7163
Get next possible record using quick-struct.
7166
QUICK_RANGE_SELECT::get_next()
7169
Record is read into table->record[0]
7173
HA_ERR_END_OF_FILE No (more) rows in range
7177
int QUICK_RANGE_SELECT::get_next()
7180
if (in_ror_merged_scan)
7183
We don't need to signal the bitmap change as the bitmap is always the
7184
same for this head->file
7186
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7189
int result= file->multi_range_read_next(&dummy);
7191
if (in_ror_merged_scan)
7193
/* Restore bitmaps set on entry */
7194
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7201
Get the next record with a different prefix.
7204
QUICK_RANGE_SELECT::get_next_prefix()
7205
prefix_length length of cur_prefix
7206
cur_prefix prefix of a key to be searched for
7209
Each subsequent call to the method retrieves the first record that has a
7210
prefix with length prefix_length different from cur_prefix, such that the
7211
record with the new prefix is within the ranges described by
7212
this->ranges. The record found is stored into the buffer pointed by
7214
The method is useful for GROUP-BY queries with range conditions to
7215
discover the prefix of the next group that satisfies the range conditions.
7218
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7219
methods should be unified into a more general one to reduce code
7224
HA_ERR_END_OF_FILE if returned all keys
7225
other if some error occurred
7228
int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
7229
key_part_map keypart_map,
7235
key_range start_key, end_key;
7238
/* Read the next record in the same range with prefix after cur_prefix. */
7239
assert(cur_prefix != 0);
7240
result= file->index_read_map(record, cur_prefix, keypart_map,
7242
if (result || (file->compare_key(file->end_range) <= 0))
7246
uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7249
/* Ranges have already been used up before. None is left for read. */
7251
return(HA_ERR_END_OF_FILE);
7253
last_range= *(cur_range++);
7255
start_key.key= (const uchar*) last_range->min_key;
7256
start_key.length= min(last_range->min_length, prefix_length);
7257
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7258
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7259
(last_range->flag & EQ_RANGE) ?
7260
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7261
end_key.key= (const uchar*) last_range->max_key;
7262
end_key.length= min(last_range->max_length, prefix_length);
7263
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7265
We use READ_AFTER_KEY here because if we are reading on a key
7266
prefix we want to find all keys with this prefix
7268
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7271
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7272
last_range->max_keypart_map ? &end_key : 0,
7273
test(last_range->flag & EQ_RANGE),
7275
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7276
last_range= 0; // Stop searching
7278
if (result != HA_ERR_END_OF_FILE)
7280
last_range= 0; // No matching rows; go to next range
7286
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7289
It is assumed that currently a scan is being done on another index
7290
which reads all necessary parts of the index that is scanned by this
7292
The implementation does a binary search on sorted array of disjoint
7293
ranges, without taking size of range into account.
7295
This function is used to filter out clustered PK scan rows in
7296
index_merge quick select.
7299
true if current row will be retrieved by this quick select
7303
bool QUICK_RANGE_SELECT::row_in_ranges()
7307
uint max= ranges.elements - 1;
7308
uint mid= (max + min)/2;
7312
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7314
/* current row value > mid->max */
7319
mid= (min + max) / 2;
7321
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7322
return (!cmp_next(res) && !cmp_prev(res));
7326
This is a hack: we inherit from QUICK_SELECT so that we can use the
7327
get_next() interface, but we have to hold a pointer to the original
7328
QUICK_SELECT because its data are used all over the place. What
7329
should be done is to factor out the data that is needed into a base
7330
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7331
which handle the ranges and implement the get_next() function. But
7332
for now, this seems to work right at least.
7335
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7336
uint used_key_parts_arg __attribute__((unused)),
7337
bool *create_err __attribute__((unused)))
7338
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7342
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7343
QUICK_RANGE **end_range= pr + ranges.elements;
7344
for (; pr!=end_range; pr++)
7345
rev_ranges.push_front(*pr);
7347
/* Remove EQ_RANGE flag for keys that are not using the full key */
7348
for (r = rev_it++; r; r = rev_it++)
7350
if ((r->flag & EQ_RANGE) &&
7351
head->key_info[index].key_length != r->max_length)
7352
r->flag&= ~EQ_RANGE;
7355
q->dont_free=1; // Don't free shared mem
7360
int QUICK_SELECT_DESC::get_next()
7362
/* The max key is handled as follows:
7363
* - if there is NO_MAX_RANGE, start at the end and move backwards
7364
* - if it is an EQ_RANGE, which means that max key covers the entire
7365
* key, go directly to the key and read through it (sorting backwards is
7366
* same as sorting forwards)
7367
* - if it is NEAR_MAX, go to the key or next, step back once, and
7369
* - otherwise (not NEAR_MAX == include the key), go after the key,
7370
* step back once, and move backwards
7377
{ // Already read through key
7378
result = ((last_range->flag & EQ_RANGE)
7379
? file->index_next_same(record, last_range->min_key,
7380
last_range->min_length) :
7381
file->index_prev(record));
7384
if (cmp_prev(*rev_it.ref()) == 0)
7387
else if (result != HA_ERR_END_OF_FILE)
7391
if (!(last_range= rev_it++))
7392
return(HA_ERR_END_OF_FILE); // All ranges used
7394
if (last_range->flag & NO_MAX_RANGE) // Read last record
7397
if ((local_error=file->index_last(record)))
7398
return(local_error); // Empty table
7399
if (cmp_prev(last_range) == 0)
7401
last_range= 0; // No match; go to next range
7405
if (last_range->flag & EQ_RANGE)
7407
result = file->index_read_map(record, last_range->max_key,
7408
last_range->max_keypart_map,
7413
assert(last_range->flag & NEAR_MAX ||
7414
range_reads_after_key(last_range));
7415
result=file->index_read_map(record, last_range->max_key,
7416
last_range->max_keypart_map,
7417
((last_range->flag & NEAR_MAX) ?
7418
HA_READ_BEFORE_KEY :
7419
HA_READ_PREFIX_LAST_OR_PREV));
7423
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7425
last_range= 0; // Not found, to next range
7428
if (cmp_prev(last_range) == 0)
7430
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7431
last_range= 0; // Stop searching
7432
return(0); // Found key is in range
7434
last_range= 0; // To next range
7440
Compare if found key is over max-value
7441
Returns 0 if key <= range->max_key
7442
TODO: Figure out why can't this function be as simple as cmp_prev().
7445
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7447
if (range_arg->flag & NO_MAX_RANGE)
7448
return 0; /* key can't be to large */
7450
KEY_PART *key_part=key_parts;
7453
for (uchar *key=range_arg->max_key, *end=key+range_arg->max_length;
7455
key+= store_length, key_part++)
7458
store_length= key_part->store_length;
7459
if (key_part->null_bit)
7463
if (!key_part->field->is_null())
7467
else if (key_part->field->is_null())
7469
key++; // Skip null byte
7472
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7477
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7482
Returns 0 if found key is inside range (found key >= range->min_key).
7485
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7488
if (range_arg->flag & NO_MIN_RANGE)
7489
return 0; /* key can't be to small */
7491
cmp= key_cmp(key_part_info, range_arg->min_key,
7492
range_arg->min_length);
7493
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7495
return 1; // outside of range
7500
* true if this range will require using HA_READ_AFTER_KEY
7501
See comment in get_next() about this
7504
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7506
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7507
!(range_arg->flag & EQ_RANGE) ||
7508
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7512
void QUICK_RANGE_SELECT::add_info_string(String *str)
7514
KEY *key_info= head->key_info + index;
7515
str->append(key_info->name);
7518
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7520
QUICK_RANGE_SELECT *quick;
7522
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7523
str->append(STRING_WITH_LEN("sort_union("));
7524
while ((quick= it++))
7530
quick->add_info_string(str);
7532
if (pk_quick_select)
7535
pk_quick_select->add_info_string(str);
7540
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7543
QUICK_RANGE_SELECT *quick;
7544
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7545
str->append(STRING_WITH_LEN("intersect("));
7546
while ((quick= it++))
7548
KEY *key_info= head->key_info + quick->index;
7553
str->append(key_info->name);
7557
KEY *key_info= head->key_info + cpk_quick->index;
7559
str->append(key_info->name);
7564
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7567
QUICK_SELECT_I *quick;
7568
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7569
str->append(STRING_WITH_LEN("union("));
7570
while ((quick= it++))
7576
quick->add_info_string(str);
7582
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7583
String *used_lengths)
7587
KEY *key_info= head->key_info + index;
7588
key_names->append(key_info->name);
7589
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7590
used_lengths->append(buf, length);
7593
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7594
String *used_lengths)
7599
QUICK_RANGE_SELECT *quick;
7601
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7602
while ((quick= it++))
7608
key_names->append(',');
7609
used_lengths->append(',');
7612
KEY *key_info= head->key_info + quick->index;
7613
key_names->append(key_info->name);
7614
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7615
used_lengths->append(buf, length);
7617
if (pk_quick_select)
7619
KEY *key_info= head->key_info + pk_quick_select->index;
7620
key_names->append(',');
7621
key_names->append(key_info->name);
7622
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7623
used_lengths->append(',');
7624
used_lengths->append(buf, length);
7628
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7629
String *used_lengths)
7634
QUICK_RANGE_SELECT *quick;
7635
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7636
while ((quick= it++))
7638
KEY *key_info= head->key_info + quick->index;
7643
key_names->append(',');
7644
used_lengths->append(',');
7646
key_names->append(key_info->name);
7647
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7648
used_lengths->append(buf, length);
7653
KEY *key_info= head->key_info + cpk_quick->index;
7654
key_names->append(',');
7655
key_names->append(key_info->name);
7656
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7657
used_lengths->append(',');
7658
used_lengths->append(buf, length);
7662
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7663
String *used_lengths)
7666
QUICK_SELECT_I *quick;
7667
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7668
while ((quick= it++))
7674
used_lengths->append(',');
7675
key_names->append(',');
7677
quick->add_keys_and_lengths(key_names, used_lengths);
7682
/*******************************************************************************
7683
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7684
*******************************************************************************/
7686
static inline uint get_field_keypart(KEY *index, Field *field);
7687
static inline SEL_ARG * get_index_range_tree(uint index, SEL_TREE* range_tree,
7688
PARAM *param, uint *param_idx);
7689
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7690
KEY_PART_INFO *first_non_group_part,
7691
KEY_PART_INFO *min_max_arg_part,
7692
KEY_PART_INFO *last_part, THD *thd,
7693
uchar *key_infix, uint *key_infix_len,
7694
KEY_PART_INFO **first_non_infix_part);
7696
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7697
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,
7700
cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts,
7701
uint group_key_parts, SEL_TREE *range_tree,
7702
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7703
bool have_min, bool have_max,
7704
double *read_cost, ha_rows *records);
5550
8759
quick->update_key_stat();
5551
8760
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 */
8767
Construct new quick select for group queries with min/max.
8770
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8771
table The table being accessed
8772
join Descriptor of the current query
8773
have_min true if the query selects a MIN function
8774
have_max true if the query selects a MAX function
8775
min_max_arg_part The only argument field of all MIN/MAX functions
8776
group_prefix_len Length of all key parts in the group prefix
8777
prefix_key_parts All key parts in the group prefix
8778
index_info The index chosen for data access
8779
use_index The id of index_info
8780
read_cost Cost of this access method
8781
records Number of records returned
8782
key_infix_len Length of the key infix appended to the group prefix
8783
key_infix Infix of constants from equality predicates
8784
parent_alloc Memory pool for this and quick_prefix_select data
8790
QUICK_GROUP_MIN_MAX_SELECT::
8791
QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join_arg, bool have_min_arg,
8793
KEY_PART_INFO *min_max_arg_part_arg,
8794
uint group_prefix_len_arg, uint group_key_parts_arg,
8795
uint used_key_parts_arg, KEY *index_info_arg,
8796
uint use_index, double read_cost_arg,
8797
ha_rows records_arg, uint key_infix_len_arg,
8798
uchar *key_infix_arg, MEM_ROOT *parent_alloc)
8799
:join(join_arg), index_info(index_info_arg),
8800
group_prefix_len(group_prefix_len_arg),
8801
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8802
have_max(have_max_arg), seen_first_key(false),
8803
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8804
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8805
max_functions_it(NULL)
8810
record= head->record[0];
8811
tmp_record= head->record[1];
8812
read_time= read_cost_arg;
8813
records= records_arg;
8814
used_key_parts= used_key_parts_arg;
8815
real_key_parts= used_key_parts_arg;
8816
real_prefix_len= group_prefix_len + key_infix_len;
8818
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8821
We can't have parent_alloc set as the init function can't handle this case
8824
assert(!parent_alloc);
8827
init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8828
join->thd->mem_root= &alloc;
8831
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8836
Do post-constructor initialization.
8839
QUICK_GROUP_MIN_MAX_SELECT::init()
8842
The method performs initialization that cannot be done in the constructor
8843
such as memory allocations that may fail. It allocates memory for the
8844
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8845
updated during execution.
8852
int QUICK_GROUP_MIN_MAX_SELECT::init()
8854
if (group_prefix) /* Already initialized. */
8857
if (!(last_prefix= (uchar*) alloc_root(&alloc, group_prefix_len)))
8860
We may use group_prefix to store keys with all select fields, so allocate
8861
enough space for it.
8863
if (!(group_prefix= (uchar*) alloc_root(&alloc,
8864
real_prefix_len + min_max_arg_len)))
8867
if (key_infix_len > 0)
8870
The memory location pointed to by key_infix will be deleted soon, so
8871
allocate a new buffer and copy the key_infix into it.
8873
uchar *tmp_key_infix= (uchar*) alloc_root(&alloc, key_infix_len);
8876
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8877
this->key_infix= tmp_key_infix;
8880
if (min_max_arg_part)
8882
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8887
if (!(min_functions= new List<Item_sum>))
8891
min_functions= NULL;
8894
if (!(max_functions= new List<Item_sum>))
8898
max_functions= NULL;
8900
Item_sum *min_max_item;
8901
Item_sum **func_ptr= join->sum_funcs;
8902
while ((min_max_item= *(func_ptr++)))
8904
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8905
min_functions->push_back(min_max_item);
8906
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8907
max_functions->push_back(min_max_item);
8912
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
8918
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
8923
min_max_ranges.elements= 0;
8929
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8931
if (file->inited != handler::NONE)
8932
file->ha_index_end();
8933
if (min_max_arg_part)
8934
delete_dynamic(&min_max_ranges);
8935
free_root(&alloc,MYF(0));
8936
delete min_functions_it;
8937
delete max_functions_it;
8938
delete quick_prefix_select;
8944
Eventually create and add a new quick range object.
8947
QUICK_GROUP_MIN_MAX_SELECT::add_range()
8948
sel_range Range object from which a
8951
Construct a new QUICK_RANGE object from a SEL_ARG object, and
8952
add it to the array min_max_ranges. If sel_arg is an infinite
8953
range, e.g. (x < 5 or x > 4), then skip it and do not construct
8961
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8964
uint range_flag= sel_range->min_flag | sel_range->max_flag;
8966
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8967
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8970
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
8971
!(sel_range->max_flag & NO_MAX_RANGE))
8973
if (sel_range->maybe_null &&
8974
sel_range->min_value[0] && sel_range->max_value[0])
8975
range_flag|= NULL_RANGE; /* IS NULL condition */
8976
else if (memcmp(sel_range->min_value, sel_range->max_value,
8977
min_max_arg_len) == 0)
8978
range_flag|= EQ_RANGE; /* equality condition */
8980
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
8981
make_keypart_map(sel_range->part),
8982
sel_range->max_value, min_max_arg_len,
8983
make_keypart_map(sel_range->part),
8987
if (insert_dynamic(&min_max_ranges, (uchar*)&range))
8994
Opens the ranges if there are more conditions in quick_prefix_select than
8995
the ones used for jumping through the prefixes.
8998
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9001
quick_prefix_select is made over the conditions on the whole key.
9002
It defines a number of ranges of length x.
9003
However when jumping through the prefixes we use only the the first
9004
few most significant keyparts in the range key. However if there
9005
are more keyparts to follow the ones we are using we must make the
9006
condition on the key inclusive (because x < "ab" means
9007
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9008
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9010
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9012
if (quick_prefix_select &&
9013
group_prefix_len < quick_prefix_select->max_used_key_length)
9018
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9022
get_dynamic(arr, (uchar*)&range, inx);
9023
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9030
Determine the total number and length of the keys that will be used for
9034
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9037
The total length of the keys used for index lookup depends on whether
9038
there are any predicates referencing the min/max argument, and/or if
9039
the min/max argument field can be NULL.
9040
This function does an optimistic analysis whether the search key might
9041
be extended by a constant for the min/max keypart. It is 'optimistic'
9042
because during actual execution it may happen that a particular range
9043
is skipped, and then a shorter key will be used. However this is data
9044
dependent and can't be easily estimated here.
9050
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9052
max_used_key_length= real_prefix_len;
9053
if (min_max_ranges.elements > 0)
9055
QUICK_RANGE *cur_range;
9057
{ /* Check if the right-most range has a lower boundary. */
9058
get_dynamic(&min_max_ranges, (uchar*)&cur_range,
9059
min_max_ranges.elements - 1);
9060
if (!(cur_range->flag & NO_MIN_RANGE))
9062
max_used_key_length+= min_max_arg_len;
9068
{ /* Check if the left-most range has an upper boundary. */
9069
get_dynamic(&min_max_ranges, (uchar*)&cur_range, 0);
9070
if (!(cur_range->flag & NO_MAX_RANGE))
9072
max_used_key_length+= min_max_arg_len;
9078
else if (have_min && min_max_arg_part &&
9079
min_max_arg_part->field->real_maybe_null())
9082
If a MIN/MAX argument value is NULL, we can quickly determine
9083
that we're in the beginning of the next group, because NULLs
9084
are always < any other value. This allows us to quickly
9085
determine the end of the current group and jump to the next
9086
group (see next_min()) and thus effectively increases the
9089
max_used_key_length+= min_max_arg_len;
9096
Initialize a quick group min/max select for key retrieval.
9099
QUICK_GROUP_MIN_MAX_SELECT::reset()
9102
Initialize the index chosen for access and find and store the prefix
9103
of the last group. The method is expensive since it performs disk access.
9110
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9114
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9115
if ((result= file->ha_index_init(index,1)))
9117
if (quick_prefix_select && quick_prefix_select->reset())
9119
result= file->index_last(record);
9120
if (result == HA_ERR_END_OF_FILE)
9122
/* Save the prefix of the last group. */
9123
key_copy(last_prefix, record, index_info, group_prefix_len);
9131
Get the next key containing the MIN and/or MAX key for the next group.
9134
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9137
The method finds the next subsequent group of records that satisfies the
9138
query conditions and finds the keys that contain the MIN/MAX values for
9139
the key part referenced by the MIN/MAX function(s). Once a group and its
9140
MIN/MAX values are found, store these values in the Item_sum objects for
9141
the MIN/MAX functions. The rest of the values in the result row are stored
9142
in the Item_field::result_field of each select field. If the query does
9143
not contain MIN and/or MAX functions, then the function only finds the
9144
group prefix, which is a query answer itself.
9147
If both MIN and MAX are computed, then we use the fact that if there is
9148
no MIN key, there can't be a MAX key as well, so we can skip looking
9149
for a MAX key in this case.
9153
HA_ERR_END_OF_FILE if returned all keys
9154
other if some error occurred
9157
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9162
int is_last_prefix= 0;
9165
Loop until a group is found that satisfies all query conditions or the last
9170
result= next_prefix();
9172
Check if this is the last group prefix. Notice that at this point
9173
this->record contains the current prefix in record format.
9177
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9179
assert(is_last_prefix <= 0);
9183
if (result == HA_ERR_KEY_NOT_FOUND)
9190
min_res= next_min();
9192
update_min_result();
9194
/* If there is no MIN in the group, there is no MAX either. */
9195
if ((have_max && !have_min) ||
9196
(have_max && have_min && (min_res == 0)))
9198
max_res= next_max();
9200
update_max_result();
9201
/* If a MIN was found, a MAX must have been found as well. */
9202
assert((have_max && !have_min) ||
9203
(have_max && have_min && (max_res == 0)));
9206
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9207
are equality predicates for the key parts after the group, find the
9208
first sub-group with the extended prefix.
9210
if (!have_min && !have_max && key_infix_len > 0)
9211
result= file->index_read_map(record, group_prefix,
9212
make_prev_keypart_map(real_key_parts),
9215
result= have_min ? min_res : have_max ? max_res : result;
9216
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9217
is_last_prefix != 0);
9222
Partially mimic the behavior of end_select_send. Copy the
9223
field data from Item_field::field into Item_field::result_field
9224
of each non-aggregated field (the group fields, and optionally
9225
other fields in non-ANSI SQL mode).
9227
copy_fields(&join->tmp_table_param);
9229
else if (result == HA_ERR_KEY_NOT_FOUND)
9230
result= HA_ERR_END_OF_FILE;
9237
Retrieve the minimal key in the next group.
9240
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9243
Find the minimal key within this group such that the key satisfies the query
9244
conditions and NULL semantics. The found key is loaded into this->record.
9247
Depending on the values of min_max_ranges.elements, key_infix_len, and
9248
whether there is a NULL in the MIN field, this function may directly
9249
return without any data access. In this case we use the key loaded into
9250
this->record by the call to this->next_prefix() just before this call.
9254
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9255
HA_ERR_END_OF_FILE - "" -
9256
other if some error occurred
9259
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9263
/* Find the MIN key using the eventually extended group prefix. */
9264
if (min_max_ranges.elements > 0)
9266
if ((result= next_min_in_range()))
9271
/* Apply the constant equality conditions to the non-group select fields */
9272
if (key_infix_len > 0)
9274
if ((result= file->index_read_map(record, group_prefix,
9275
make_prev_keypart_map(real_key_parts),
9276
HA_READ_KEY_EXACT)))
9281
If the min/max argument field is NULL, skip subsequent rows in the same
9282
group with NULL in it. Notice that:
9283
- if the first row in a group doesn't have a NULL in the field, no row
9284
in the same group has (because NULL < any other value),
9285
- min_max_arg_part->field->ptr points to some place in 'record'.
9287
if (min_max_arg_part && min_max_arg_part->field->is_null())
9289
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9290
key_copy(tmp_record, record, index_info, 0);
9291
result= file->index_read_map(record, tmp_record,
9292
make_keypart_map(real_key_parts),
9295
Check if the new record belongs to the current group by comparing its
9296
prefix with the group's prefix. If it is from the next group, then the
9297
whole group has NULLs in the MIN/MAX field, so use the first record in
9298
the group as a result.
9300
It is possible to reuse this new record as the result candidate for the
9301
next call to next_min(), and to save one lookup in the next call. For
9302
this add a new member 'this->next_group_prefix'.
9306
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9307
key_restore(record, tmp_record, index_info, 0);
9309
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9310
result= 0; /* There is a result in any case. */
9315
If the MIN attribute is non-nullable, this->record already contains the
9316
MIN key in the group, so just return.
9323
Retrieve the maximal key in the next group.
9326
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9329
Lookup the maximal key of the group, and store it into this->record.
9333
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9334
HA_ERR_END_OF_FILE - "" -
9335
other if some error occurred
9338
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9342
/* Get the last key in the (possibly extended) group. */
9343
if (min_max_ranges.elements > 0)
9344
result= next_max_in_range();
9346
result= file->index_read_map(record, group_prefix,
9347
make_prev_keypart_map(real_key_parts),
9348
HA_READ_PREFIX_LAST);
9354
Determine the prefix of the next group.
9357
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9360
Determine the prefix of the next group that satisfies the query conditions.
9361
If there is a range condition referencing the group attributes, use a
9362
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9363
condition. If there is a key infix of constants, append this infix
9364
immediately after the group attributes. The possibly extended prefix is
9365
stored in this->group_prefix. The first key of the found group is stored in
9366
this->record, on which relies this->next_min().
9370
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9371
HA_ERR_END_OF_FILE if there are no more keys
9372
other if some error occurred
9374
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9378
if (quick_prefix_select)
9380
uchar *cur_prefix= seen_first_key ? group_prefix : NULL;
9381
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9382
make_prev_keypart_map(group_key_parts), cur_prefix)))
9384
seen_first_key= true;
9388
if (!seen_first_key)
9390
result= file->index_first(record);
9393
seen_first_key= true;
9397
/* Load the first key in this group into record. */
9398
result= file->index_read_map(record, group_prefix,
9399
make_prev_keypart_map(group_key_parts),
9406
/* Save the prefix of this group for subsequent calls. */
9407
key_copy(group_prefix, record, index_info, group_prefix_len);
9408
/* Append key_infix to group_prefix. */
9409
if (key_infix_len > 0)
9410
memcpy(group_prefix + group_prefix_len,
9411
key_infix, key_infix_len);
9418
Find the minimal key in a group that satisfies some range conditions for the
9419
min/max argument field.
9422
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9425
Given the sequence of ranges min_max_ranges, find the minimal key that is
9426
in the left-most possible range. If there is no such key, then the current
9427
group does not have a MIN key that satisfies the WHERE clause. If a key is
9428
found, its value is stored in this->record.
9432
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9434
HA_ERR_END_OF_FILE - "" -
9438
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9440
ha_rkey_function find_flag;
9441
key_part_map keypart_map;
9442
QUICK_RANGE *cur_range;
9443
bool found_null= false;
9444
int result= HA_ERR_KEY_NOT_FOUND;
9446
assert(min_max_ranges.elements > 0);
9448
for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9449
{ /* Search from the left-most range to the right. */
9450
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx);
9453
If the current value for the min/max argument is bigger than the right
9454
boundary of cur_range, there is no need to check this range.
9456
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9457
(key_cmp(min_max_arg_part, (const uchar*) cur_range->max_key,
9458
min_max_arg_len) == 1))
9461
if (cur_range->flag & NO_MIN_RANGE)
9463
keypart_map= make_prev_keypart_map(real_key_parts);
9464
find_flag= HA_READ_KEY_EXACT;
9468
/* Extend the search key with the lower boundary for this range. */
9469
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9470
cur_range->min_length);
9471
keypart_map= make_keypart_map(real_key_parts);
9472
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9473
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9474
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9477
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9480
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9481
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9482
continue; /* Check the next range. */
9485
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9486
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9487
range, it can't succeed for any other subsequent range.
9492
/* A key was found. */
9493
if (cur_range->flag & EQ_RANGE)
9494
break; /* No need to perform the checks below for equal keys. */
9496
if (cur_range->flag & NULL_RANGE)
9499
Remember this key, and continue looking for a non-NULL key that
9500
satisfies some other condition.
9502
memcpy(tmp_record, record, head->s->rec_buff_length);
9507
/* Check if record belongs to the current group. */
9508
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9510
result= HA_ERR_KEY_NOT_FOUND;
9514
/* If there is an upper limit, check if the found key is in the range. */
9515
if ( !(cur_range->flag & NO_MAX_RANGE) )
9517
/* Compose the MAX key for the range. */
9518
uchar *max_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9519
memcpy(max_key, group_prefix, real_prefix_len);
9520
memcpy(max_key + real_prefix_len, cur_range->max_key,
9521
cur_range->max_length);
9522
/* Compare the found key with max_key. */
9523
int cmp_res= key_cmp(index_info->key_part, max_key,
9524
real_prefix_len + min_max_arg_len);
9525
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9527
result= HA_ERR_KEY_NOT_FOUND;
9531
/* If we got to this point, the current key qualifies as MIN. */
9532
assert(result == 0);
9536
If there was a key with NULL in the MIN/MAX field, and there was no other
9537
key without NULL from the same group that satisfies some other condition,
9538
then use the key with the NULL.
9540
if (found_null && result)
9542
memcpy(record, tmp_record, head->s->rec_buff_length);
9550
Find the maximal key in a group that satisfies some range conditions for the
9551
min/max argument field.
9554
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9557
Given the sequence of ranges min_max_ranges, find the maximal key that is
9558
in the right-most possible range. If there is no such key, then the current
9559
group does not have a MAX key that satisfies the WHERE clause. If a key is
9560
found, its value is stored in this->record.
9564
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9566
HA_ERR_END_OF_FILE - "" -
9570
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9572
ha_rkey_function find_flag;
9573
key_part_map keypart_map;
9574
QUICK_RANGE *cur_range;
9577
assert(min_max_ranges.elements > 0);
9579
for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9580
{ /* Search from the right-most range to the left. */
9581
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx - 1);
9584
If the current value for the min/max argument is smaller than the left
9585
boundary of cur_range, there is no need to check this range.
9587
if (range_idx != min_max_ranges.elements &&
9588
!(cur_range->flag & NO_MIN_RANGE) &&
9589
(key_cmp(min_max_arg_part, (const uchar*) cur_range->min_key,
9590
min_max_arg_len) == -1))
9593
if (cur_range->flag & NO_MAX_RANGE)
9595
keypart_map= make_prev_keypart_map(real_key_parts);
9596
find_flag= HA_READ_PREFIX_LAST;
9600
/* Extend the search key with the upper boundary for this range. */
9601
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9602
cur_range->max_length);
9603
keypart_map= make_keypart_map(real_key_parts);
9604
find_flag= (cur_range->flag & EQ_RANGE) ?
9605
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9606
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9609
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9613
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9614
(cur_range->flag & EQ_RANGE))
9615
continue; /* Check the next range. */
9618
In no key was found with this upper bound, there certainly are no keys
9619
in the ranges to the left.
9623
/* A key was found. */
9624
if (cur_range->flag & EQ_RANGE)
9625
return 0; /* No need to perform the checks below for equal keys. */
9627
/* Check if record belongs to the current group. */
9628
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9629
continue; // Row not found
9631
/* If there is a lower limit, check if the found key is in the range. */
9632
if ( !(cur_range->flag & NO_MIN_RANGE) )
9634
/* Compose the MIN key for the range. */
9635
uchar *min_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9636
memcpy(min_key, group_prefix, real_prefix_len);
9637
memcpy(min_key + real_prefix_len, cur_range->min_key,
9638
cur_range->min_length);
9639
/* Compare the found key with min_key. */
9640
int cmp_res= key_cmp(index_info->key_part, min_key,
9641
real_prefix_len + min_max_arg_len);
9642
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9646
/* If we got to this point, the current key qualifies as MAX. */
9649
return HA_ERR_KEY_NOT_FOUND;
9654
Update all MIN function results with the newly found value.
9657
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9660
The method iterates through all MIN functions and updates the result value
9661
of each function by calling Item_sum::reset(), which in turn picks the new
9662
result value from this->head->record[0], previously updated by
9663
next_min(). The updated value is stored in a member variable of each of the
9664
Item_sum objects, depending on the value type.
9667
The update must be done separately for MIN and MAX, immediately after
9668
next_min() was called and before next_max() is called, because both MIN and
9669
MAX take their result value from the same buffer this->head->record[0]
9670
(i.e. this->record).
9676
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9680
min_functions_it->rewind();
9681
while ((min_func= (*min_functions_it)++))
9687
Update all MAX function results with the newly found value.
9690
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9693
The method iterates through all MAX functions and updates the result value
9694
of each function by calling Item_sum::reset(), which in turn picks the new
9695
result value from this->head->record[0], previously updated by
9696
next_max(). The updated value is stored in a member variable of each of the
9697
Item_sum objects, depending on the value type.
9700
The update must be done separately for MIN and MAX, immediately after
9701
next_max() was called, because both MIN and MAX take their result value
9702
from the same buffer this->head->record[0] (i.e. this->record).
9708
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9712
max_functions_it->rewind();
9713
while ((max_func= (*max_functions_it)++))
9719
Append comma-separated list of keys this quick select uses to key_names;
9720
append comma-separated list of corresponding used lengths to used_lengths.
9723
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9724
key_names [out] Names of used indexes
9725
used_lengths [out] Corresponding lengths of the index names
9728
This method is used by select_describe to extract the names of the
9729
indexes used by a quick select.
9733
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9734
String *used_lengths)
9738
key_names->append(index_info->name);
9739
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9740
used_lengths->append(buf, length);
9743
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9744
const char *msg __attribute__((unused)))
9746
SEL_ARG **key,**end;
9750
String tmp(buff,sizeof(buff),&my_charset_bin);
9752
for (idx= 0,key=tree->keys, end=key+param->keys ;
9756
if (tree_map->is_set(idx))
9758
uint keynr= param->real_keynr[idx];
9761
tmp.append(param->table->key_info[keynr].name);
9765
tmp.append(STRING_WITH_LEN("(empty)"));
9771
static void print_ror_scans_arr(TABLE *table,
9772
const char *msg __attribute__((unused)),
9773
struct st_ror_scan_info **start,
9774
struct st_ror_scan_info **end)
9777
String tmp(buff,sizeof(buff),&my_charset_bin);
9779
for (;start != end; start++)
9783
tmp.append(table->key_info[(*start)->keynr].name);
9786
tmp.append(STRING_WITH_LEN("(empty)"));
9790
/*****************************************************************************
9791
** Instantiate templates
9792
*****************************************************************************/
9794
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9795
template class List<QUICK_RANGE>;
9796
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
