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>
106
#include <drizzled/server_includes.h>
107
#include <drizzled/sql_select.h>
115
108
#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
152
111
Convert double value to #rows. Currently this does floor(), and we
153
112
might consider using round() instead.
155
static inline ha_rows double2rows(double x)
157
return static_cast<ha_rows>(x);
114
#define double2rows(x) ((ha_rows)(x))
116
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
160
118
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,
120
class RANGE_OPT_PARAM;
122
A construction block of the SEL_ARG-graph.
124
The following description only covers graphs of SEL_ARG objects with
125
sel_arg->type==KEY_RANGE:
127
One SEL_ARG object represents an "elementary interval" in form
129
min_value <=? table.keypartX <=? max_value
131
The interval is a non-empty interval of any kind: with[out] minimum/maximum
132
bound, [half]open/closed, single-point interval, etc.
134
1. SEL_ARG GRAPH STRUCTURE
136
SEL_ARG objects are linked together in a graph. The meaning of the graph
137
is better demostrated by an example:
142
| part=1 $ part=2 $ part=3
144
| +-------+ $ +-------+ $ +--------+
145
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
146
| +-------+ $ +-------+ $ +--------+
152
\->| kp1=2 |--$--------------$-+
153
+-------+ $ $ | +--------+
155
+-------+ $ $ | +--------+
156
| kp1=3 |--$--------------$-+ |
157
+-------+ $ $ +--------+
161
The entire graph is partitioned into "interval lists".
163
An interval list is a sequence of ordered disjoint intervals over the same
164
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
165
all intervals in the list form an RB-tree, linked via left/right/parent
166
pointers. The RB-tree root SEL_ARG object will be further called "root of the
169
In the example pic, there are 4 interval lists:
170
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
171
The vertical lines represent SEL_ARG::next/prev pointers.
173
In an interval list, each member X may have SEL_ARG::next_key_part pointer
174
pointing to the root of another interval list Y. The pointed interval list
175
must cover a key part with greater number (i.e. Y->part > X->part).
177
In the example pic, the next_key_part pointers are represented by
180
2. SEL_ARG GRAPH SEMANTICS
182
It represents a condition in a special form (we don't have a name for it ATM)
183
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
185
For example, the picture represents the condition in form:
186
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
187
(kp1=2 AND (kp3=11 OR kp3=14)) OR
188
(kp1=3 AND (kp3=11 OR kp3=14))
193
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
194
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
195
intervals (i.e. intervals in form
197
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
199
Those intervals can be used to access the index. The uses are in:
200
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
201
how many table records are contained within all
203
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
204
and create QUICK_RANGE_SELECT object that will
205
read records within these intervals.
207
4. SPACE COMPLEXITY NOTES
209
SEL_ARG graph is a representation of an ordered disjoint sequence of
210
intervals over the ordered set of index tuple values.
212
For multi-part keys, one can construct a WHERE expression such that its
213
list of intervals will be of combinatorial size. Here is an example:
215
(keypart1 IN (1,2, ..., n1)) AND
216
(keypart2 IN (1,2, ..., n2)) AND
217
(keypart3 IN (1,2, ..., n3))
219
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
222
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
224
SEL_ARG graph structure aims to reduce the amount of required space by
225
"sharing" the elementary intervals when possible (the pic at the
226
beginning of this comment has examples of such sharing). The sharing may
227
prevent combinatorial blowup:
229
There are WHERE clauses that have combinatorial-size interval lists but
230
will be represented by a compact SEL_ARG graph.
232
(keypartN IN (1,2, ..., n1)) AND
234
(keypart2 IN (1,2, ..., n2)) AND
235
(keypart1 IN (1,2, ..., n3))
237
but not in all cases:
239
- There are WHERE clauses that do have a compact SEL_ARG-graph
240
representation but get_mm_tree() and its callees will construct a
241
graph of combinatorial size.
243
(keypart1 IN (1,2, ..., n1)) AND
244
(keypart2 IN (1,2, ..., n2)) AND
246
(keypartN IN (1,2, ..., n3))
248
- There are WHERE clauses for which the minimal possible SEL_ARG graph
249
representation will have combinatorial size.
251
By induction: Let's take any interval on some keypart in the middle:
255
Then let's AND it with this interval 'structure' from preceding and
258
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
260
We will obtain this SEL_ARG graph:
264
+---------+ $ +---------+ $ +---------+
265
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
266
+---------+ $ +---------+ $ +---------+
268
+---------+ $ +---------+ $
269
| kp14=c2 |--$-->| kp15=c0 | $
270
+---------+ $ +---------+ $
273
Note that we had to duplicate "kp15=c0" and there was no way to avoid
275
The induction step: AND the obtained expression with another "wrapping"
277
When the process ends because of the limit on max. number of keyparts
280
WHERE clause length is O(3*#max_keyparts)
281
SEL_ARG graph size is O(2^(#max_keyparts/2))
283
(it is also possible to construct a case where instead of 2 in 2^n we
284
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
287
We avoid consuming too much memory by setting a limit on the number of
288
SEL_ARG object we can construct during one range analysis invocation.
291
class SEL_ARG :public Sql_alloc
294
uint8_t min_flag,max_flag,maybe_flag;
295
uint8_t part; // Which key part
298
Number of children of this element in the RB-tree, plus 1 for this
303
Valid only for elements which are RB-tree roots: Number of times this
304
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
305
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
310
unsigned char *min_value,*max_value; // Pointer to range
313
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
315
SEL_ARG *left,*right; /* R-B tree children */
316
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
317
SEL_ARG *parent; /* R-B tree parent */
318
SEL_ARG *next_key_part;
319
enum leaf_color { BLACK,RED } color;
320
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
322
enum { MAX_SEL_ARGS = 16000 };
326
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
327
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
328
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
329
SEL_ARG(enum Type type_arg)
330
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
331
color(BLACK), type(type_arg)
333
inline bool is_same(SEL_ARG *arg)
335
if (type != arg->type || part != arg->part)
337
if (type != KEY_RANGE)
339
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
341
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
342
inline void maybe_smaller() { maybe_flag=1; }
343
/* Return true iff it's a single-point null interval */
344
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
345
inline int cmp_min_to_min(SEL_ARG* arg)
347
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
349
inline int cmp_min_to_max(SEL_ARG* arg)
351
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
353
inline int cmp_max_to_max(SEL_ARG* arg)
355
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
357
inline int cmp_max_to_min(SEL_ARG* arg)
359
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
361
SEL_ARG *clone_and(SEL_ARG* arg)
362
{ // Get overlapping range
363
unsigned char *new_min,*new_max;
364
uint8_t flag_min,flag_max;
365
if (cmp_min_to_min(arg) >= 0)
367
new_min=min_value; flag_min=min_flag;
371
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
373
if (cmp_max_to_max(arg) <= 0)
375
new_max=max_value; flag_max=max_flag;
379
new_max=arg->max_value; flag_max=arg->max_flag;
381
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
382
test(maybe_flag && arg->maybe_flag));
384
SEL_ARG *clone_first(SEL_ARG *arg)
385
{ // min <= X < arg->min
386
return new SEL_ARG(field,part, min_value, arg->min_value,
387
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
388
maybe_flag | arg->maybe_flag);
390
SEL_ARG *clone_last(SEL_ARG *arg)
391
{ // min <= X <= key_max
392
return new SEL_ARG(field, part, min_value, arg->max_value,
393
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
395
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
397
bool copy_min(SEL_ARG* arg)
398
{ // Get overlapping range
399
if (cmp_min_to_min(arg) > 0)
401
min_value=arg->min_value; min_flag=arg->min_flag;
402
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
403
(NO_MAX_RANGE | NO_MIN_RANGE))
404
return 1; // Full range
406
maybe_flag|=arg->maybe_flag;
409
bool copy_max(SEL_ARG* arg)
410
{ // Get overlapping range
411
if (cmp_max_to_max(arg) <= 0)
413
max_value=arg->max_value; max_flag=arg->max_flag;
414
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
415
(NO_MAX_RANGE | NO_MIN_RANGE))
416
return 1; // Full range
418
maybe_flag|=arg->maybe_flag;
422
void copy_min_to_min(SEL_ARG *arg)
424
min_value=arg->min_value; min_flag=arg->min_flag;
426
void copy_min_to_max(SEL_ARG *arg)
428
max_value=arg->min_value;
429
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
431
void copy_max_to_min(SEL_ARG *arg)
433
min_value=arg->max_value;
434
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
436
/* returns a number of keypart values (0 or 1) appended to the key buffer */
437
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
439
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
440
if ((!(min_flag & NO_MIN_RANGE) &&
441
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
443
if (maybe_null && *min_value)
446
memset(*min_key+1, 0, length-1);
449
memcpy(*min_key,min_value,length);
455
/* returns a number of keypart values (0 or 1) appended to the key buffer */
456
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
458
if (!(max_flag & NO_MAX_RANGE) &&
459
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
461
if (maybe_null && *max_value)
464
memset(*max_key+1, 0, length-1);
467
memcpy(*max_key,max_value,length);
474
/* returns a number of keypart values appended to the key buffer */
475
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
477
SEL_ARG *key_tree= first();
478
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
479
range_key, *range_key_flag);
480
*range_key_flag|= key_tree->min_flag;
482
if (key_tree->next_key_part &&
483
key_tree->next_key_part->part == key_tree->part+1 &&
484
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
485
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
486
res+= key_tree->next_key_part->store_min_key(key, range_key,
491
/* returns a number of keypart values appended to the key buffer */
492
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
494
SEL_ARG *key_tree= last();
495
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
496
range_key, *range_key_flag);
497
(*range_key_flag)|= key_tree->max_flag;
498
if (key_tree->next_key_part &&
499
key_tree->next_key_part->part == key_tree->part+1 &&
500
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
501
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
502
res+= key_tree->next_key_part->store_max_key(key, range_key,
507
SEL_ARG *insert(SEL_ARG *key);
508
SEL_ARG *tree_delete(SEL_ARG *key);
509
SEL_ARG *find_range(SEL_ARG *key);
510
SEL_ARG *rb_insert(SEL_ARG *leaf);
511
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
513
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
514
void test_use_count(SEL_ARG *root);
519
inline bool simple_key()
521
return !next_key_part && elements == 1;
523
void increment_use_count(long count)
527
next_key_part->use_count+=count;
528
count*= (next_key_part->use_count-count);
529
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
530
if (pos->next_key_part)
531
pos->increment_use_count(count);
536
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
537
if (pos->next_key_part)
539
pos->next_key_part->use_count--;
540
pos->next_key_part->free_tree();
544
inline SEL_ARG **parent_ptr()
546
return parent->left == this ? &parent->left : &parent->right;
551
Check if this SEL_ARG object represents a single-point interval
557
Check if this SEL_ARG object (not tree) represents a single-point
558
interval, i.e. if it represents a "keypart = const" or
562
true This SEL_ARG object represents a singlepoint interval
566
bool is_singlepoint()
569
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
570
flags, and the same for right edge.
572
if (min_flag || max_flag)
574
unsigned char *min_val= min_value;
575
unsigned char *max_val= max_value;
579
/* First byte is a NULL value indicator */
580
if (*min_val != *max_val)
584
return true; /* This "x IS NULL" */
588
return !field->key_cmp(min_val, max_val);
590
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
596
class SEL_TREE :public Sql_alloc
600
Starting an effort to document this field:
601
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
602
(type == SEL_TREE::IMPOSSIBLE)
604
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
605
SEL_TREE(enum Type type_arg) :type(type_arg) {}
606
SEL_TREE() :type(KEY)
608
keys_map.clear_all();
609
memset(keys, 0, sizeof(keys));
612
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
613
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
614
merit in range analyzer functions (e.g. get_mm_parts) returning a
615
pointer to such SEL_TREE instead of NULL)
617
SEL_ARG *keys[MAX_KEY];
618
key_map keys_map; /* bitmask of non-NULL elements in keys */
621
Possible ways to read rows using index_merge. The list is non-empty only
622
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
624
List<SEL_IMERGE> merges;
626
/* The members below are filled/used only after get_mm_tree is done */
627
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
628
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
630
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
631
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
632
/* Note that #records for each key scan is stored in table->quick_rows */
635
class RANGE_OPT_PARAM
638
Session *session; /* Current thread handle */
639
Table *table; /* Table being analyzed */
640
COND *cond; /* Used inside get_mm_tree(). */
641
table_map prev_tables;
642
table_map read_tables;
643
table_map current_table; /* Bit of the table being analyzed */
645
/* Array of parts of all keys for which range analysis is performed */
647
KEY_PART *key_parts_end;
648
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
649
MEM_ROOT *old_root; /* Memory that will last until the query end */
651
Number of indexes used in range analysis (In SEL_TREE::keys only first
652
#keys elements are not empty)
657
If true, the index descriptions describe real indexes (and it is ok to
658
call field->optimize_range(real_keynr[...], ...).
659
Otherwise index description describes fake indexes.
661
bool using_real_indexes;
663
bool remove_jump_scans;
666
used_key_no -> table_key_no translation table. Only makes sense if
667
using_real_indexes==true
669
uint32_t real_keynr[MAX_KEY];
670
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
671
uint32_t alloced_sel_args;
672
bool force_default_mrr;
675
class PARAM : public RANGE_OPT_PARAM
678
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
680
uint32_t max_key_part;
681
/* Number of ranges in the last checked tree->key */
682
uint32_t range_count;
683
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
684
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
685
bool quick; // Don't calulate possible keys
687
uint32_t fields_bitmap_size;
688
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
689
MY_BITMAP tmp_covered_fields;
691
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
693
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
694
uint32_t imerge_cost_buff_size; /* size of the buffer */
696
/* true if last checked tree->key can be used for ROR-scan */
698
/* Number of ranges in the last checked tree->key */
702
class TABLE_READ_PLAN;
704
class TRP_ROR_INTERSECT;
706
class TRP_ROR_INDEX_MERGE;
707
class TRP_GROUP_MIN_MAX;
709
struct st_ror_scan_info;
711
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
712
Item_func::Functype type,Item *value,
713
Item_result cmp_type);
714
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
716
Item_func::Functype type,Item *value);
717
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
719
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
720
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
721
SEL_ARG *tree, bool update_tbl_stats,
722
uint32_t *mrr_flags, uint32_t *bufsize,
724
//bool update_tbl_stats);
725
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
726
unsigned char *min_key, uint32_t min_key_flag, int,
727
unsigned char *max_key, uint32_t max_key_flag, int);
730
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
731
SEL_ARG *key_tree, uint32_t mrr_flags,
732
uint32_t mrr_buf_size, MEM_ROOT *alloc);
733
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
734
bool index_read_must_be_used,
735
bool update_tbl_stats,
738
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
740
bool *are_all_covering);
742
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
746
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
749
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
751
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
753
static void print_ror_scans_arr(Table *table, const char *msg,
754
struct st_ror_scan_info **start,
755
struct st_ror_scan_info **end);
757
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
758
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
759
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
760
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
761
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
762
uint32_t clone_flag);
763
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
764
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
765
SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
766
unsigned char *max_key,uint32_t max_key_flag);
767
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
769
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
770
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
310
771
uint32_t length);
312
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
313
optimizer::SEL_TREE *tree2,
314
optimizer::RangeParameter *param);
772
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
776
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
777
a condition in the following form:
778
(t_1||t_2||...||t_N) && (next)
780
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
781
(t_i,t_j) contains SEL_ARGS for the same index.
783
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
785
This class relies on memory manager to do the cleanup.
788
class SEL_IMERGE : public Sql_alloc
790
enum { PREALLOCED_TREES= 10};
792
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
793
SEL_TREE **trees; /* trees used to do index_merge */
794
SEL_TREE **trees_next; /* last of these trees */
795
SEL_TREE **trees_end; /* end of allocated space */
797
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
800
trees(&trees_prealloced[0]),
802
trees_end(trees + PREALLOCED_TREES)
804
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
805
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
806
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
811
Add SEL_TREE to this index_merge without any checks,
814
This function implements the following:
815
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
822
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
824
if (trees_next == trees_end)
826
const int realloc_ratio= 2; /* Double size for next round */
827
uint32_t old_elements= (trees_end - trees);
828
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
829
uint32_t new_size= old_size * realloc_ratio;
830
SEL_TREE **new_trees;
831
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
833
memcpy(new_trees, trees, old_size);
835
trees_next= trees + old_elements;
836
trees_end= trees + old_elements * realloc_ratio;
838
*(trees_next++)= tree;
844
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
845
combining new_tree with one of the trees in this SEL_IMERGE if they both
846
have SEL_ARGs for the same key.
849
or_sel_tree_with_checks()
850
param PARAM from SQL_SELECT::test_quick_select
851
new_tree SEL_TREE with type KEY or KEY_SMALLER.
854
This does the following:
855
(t_1||...||t_k)||new_tree =
857
= (t_1||...||t_k||new_tree)
859
= (t_1||....||(t_j|| new_tree)||...||t_k),
861
where t_i, y are SEL_TREEs.
862
new_tree is combined with the first t_j it has a SEL_ARG on common
863
key with. As a consequence of this, choice of keys to do index_merge
864
read may depend on the order of conditions in WHERE part of the query.
868
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
869
and (*this) should be discarded.
870
-1 An error occurred.
873
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
875
for (SEL_TREE** tree = trees;
879
if (sel_trees_can_be_ored(*tree, new_tree, param))
881
*tree = tree_or(param, *tree, new_tree);
884
if (((*tree)->type == SEL_TREE::MAYBE) ||
885
((*tree)->type == SEL_TREE::ALWAYS))
887
/* SEL_TREE::IMPOSSIBLE is impossible here */
892
/* New tree cannot be combined with any of existing trees. */
893
return or_sel_tree(param, new_tree);
898
Perform OR operation on this index_merge and supplied index_merge list.
902
1 - One of conditions in result is always true and this SEL_IMERGE
904
-1 - An error occurred
907
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
909
for (SEL_TREE** tree= imerge->trees;
910
tree != imerge->trees_next;
913
if (or_sel_tree_with_checks(param, *tree))
322
921
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)
924
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
327
926
im1->concat(im2);
931
Perform OR operation on 2 index_merge lists, storing result in first list.
934
The following conversion is implemented:
935
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
938
i.e. all conjuncts except the first one are currently dropped.
939
This is done to avoid producing N*K ways to do index_merge.
941
If (a_1||b_1) produce a condition that is always true, NULL is returned
942
and index_merge is discarded (while it is actually possible to try
945
As a consequence of this, choice of keys to do index_merge read may depend
946
on the order of conditions in WHERE part of the query.
949
0 OK, result is stored in *im1
950
other Error, both passed lists are unusable
953
int imerge_list_or_list(RANGE_OPT_PARAM *param,
954
List<SEL_IMERGE> *im1,
955
List<SEL_IMERGE> *im2)
957
SEL_IMERGE *imerge= im1->head();
959
im1->push_back(imerge);
961
return imerge->or_sel_imerge_with_checks(param, im2->head());
966
Perform OR operation on index_merge list and key tree.
969
0 OK, result is stored in *im1.
973
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
974
List<SEL_IMERGE> *im1,
978
List_iterator<SEL_IMERGE> it(*im1);
979
while ((imerge= it++))
981
if (imerge->or_sel_tree_with_checks(param, tree))
984
return im1->is_empty();
331
988
/***************************************************************************
332
** Basic functions for SqlSelect and QuickRangeSelect
989
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
333
990
***************************************************************************/
335
992
/* make a select from mysql info
366
1019
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;
1021
select->file= *head->sort.io_cache;
1022
select->records=(ha_rows) (select->file.end_of_file/
1023
head->file->ref_length);
1024
free(head->sort.io_cache);
372
1025
head->sort.io_cache=0;
378
optimizer::SqlSelect::SqlSelect()
382
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1031
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1033
quick_keys.clear_all(); needed_reg.clear_all();
391
void optimizer::SqlSelect::cleanup()
1038
void SQL_SELECT::cleanup()
405
file->close_cached_file();
1048
close_cached_file(&file);
409
optimizer::SqlSelect::~SqlSelect()
1052
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),
1057
QUICK_SELECT_I::QUICK_SELECT_I()
1058
:max_used_key_length(0),
1062
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1063
bool no_alloc, MEM_ROOT *parent_alloc,
1065
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1067
my_bitmap_map *bitmap;
1069
in_ror_merged_scan= 0;
1073
key_part_info= head->key_info[index].key_part;
1074
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1076
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1077
mrr_buf_size= session->variables.read_rnd_buff_size;
1080
if (!no_alloc && !parent_alloc)
1082
// Allocates everything through the internal memroot
1083
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1084
session->mem_root= &alloc;
1087
memset(&alloc, 0, sizeof(alloc));
1089
record= head->record[0];
1090
save_read_set= head->read_set;
1091
save_write_set= head->write_set;
1093
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1094
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1097
column_bitmap.bitmap= 0;
1101
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1106
int QUICK_RANGE_SELECT::init()
1108
if (file->inited != handler::NONE)
1109
file->ha_index_or_rnd_end();
1110
return(file->ha_index_init(index, 1));
1114
void QUICK_RANGE_SELECT::range_end()
1116
if (file->inited != handler::NONE)
1117
file->ha_index_or_rnd_end();
1121
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1125
/* file is NULL for CPK scan on covering ROR-intersection */
1132
file->extra(HA_EXTRA_NO_KEYREAD);
1136
file->ha_external_lock(current_session, F_UNLCK);
1141
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1142
free_root(&alloc,MYF(0));
1143
free((char*) column_bitmap.bitmap);
1145
head->column_bitmaps_set(save_read_set, save_write_set);
1152
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1154
:pk_quick_select(NULL), session(session_param)
1158
memset(&read_record, 0, sizeof(read_record));
1159
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1163
int QUICK_INDEX_MERGE_SELECT::init()
1168
int QUICK_INDEX_MERGE_SELECT::reset()
1170
return(read_keys_and_merge());
1174
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1177
Save quick_select that does scan on clustered primary key as it will be
1178
processed separately.
1180
if (head->file->primary_key_is_clustered() &&
1181
quick_sel_range->index == head->s->primary_key)
1182
pk_quick_select= quick_sel_range;
1184
return quick_selects.push_back(quick_sel_range);
1188
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1190
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1191
QUICK_RANGE_SELECT* quick;
1193
while ((quick= quick_it++))
1195
quick_selects.delete_elements();
1196
delete pk_quick_select;
1197
free_root(&alloc,MYF(0));
1202
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1204
bool retrieve_full_rows,
1205
MEM_ROOT *parent_alloc)
1206
: cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1211
record= head->record[0];
1213
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1215
memset(&alloc, 0, sizeof(MEM_ROOT));
1216
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1217
head->file->ref_length);
1222
Do post-constructor initialization.
1224
QUICK_ROR_INTERSECT_SELECT::init()
1231
int QUICK_ROR_INTERSECT_SELECT::init()
1233
/* Check if last_rowid was successfully allocated in ctor */
1234
return(!last_rowid);
1239
Initialize this quick select to be a ROR-merged scan.
1242
QUICK_RANGE_SELECT::init_ror_merged_scan()
1243
reuse_handler If true, use head->file, otherwise create a separate
1247
This function creates and prepares for subsequent use a separate handler
1248
object if it can't reuse head->file. The reason for this is that during
1249
ROR-merge several key scans are performed simultaneously, and a single
1250
handler is only capable of preserving context of a single key scan.
1252
In ROR-merge the quick select doing merge does full records retrieval,
1253
merged quick selects read only keys.
1256
0 ROR child scan initialized, ok to use.
1260
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1262
handler *save_file= file, *org_file;
1265
in_ror_merged_scan= 1;
1268
if (init() || reset())
1272
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1276
/* Create a separate handler object for this quick select */
1279
/* already have own 'handler' object. */
1283
session= head->in_use;
1284
if (!(file= head->file->clone(session->mem_root)))
1287
Manually set the error flag. Note: there seems to be quite a few
1288
places where a failure could cause the server to "hang" the client by
1289
sending no response to a query. ATM those are not real errors because
1290
the storage engine calls in question happen to never fail with the
1291
existing storage engines.
1293
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1294
/* Caller will free the memory */
1295
goto failure; /* purecov: inspected */
1298
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1300
if (file->ha_external_lock(session, F_RDLCK))
1303
if (init() || reset())
1305
file->ha_external_lock(session, F_UNLCK);
1310
last_rowid= file->ref;
1314
We are only going to read key fields and call position() on 'file'
1315
The following sets head->tmp_set to only use this key and then updates
1316
head->read_set and head->write_set to use this bitmap.
1317
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1319
org_file= head->file;
1321
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1322
if (!head->no_keyread)
1325
head->mark_columns_used_by_index(index);
1327
head->prepare_for_position();
1328
head->file= org_file;
1329
bitmap_copy(&column_bitmap, head->read_set);
1330
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1335
head->column_bitmaps_set(save_read_set, save_write_set);
1343
Initialize this quick select to be a part of a ROR-merged scan.
1345
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1346
reuse_handler If true, use head->file, otherwise create separate
1352
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1354
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1355
QUICK_RANGE_SELECT* quick;
1357
/* Initialize all merged "children" quick selects */
1358
assert(!need_to_fetch_row || reuse_handler);
1359
if (!need_to_fetch_row && reuse_handler)
1363
There is no use of this->file. Use it for the first of merged range
1366
if (quick->init_ror_merged_scan(true))
1368
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1370
while ((quick= quick_it++))
1372
if (quick->init_ror_merged_scan(false))
1374
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1375
/* All merged scans share the same record buffer in intersection. */
1376
quick->record= head->record[0];
1379
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1388
Initialize quick select for row retrieval.
1396
int QUICK_ROR_INTERSECT_SELECT::reset()
1398
if (!scans_inited && init_ror_merged_scan(true))
1401
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1402
QUICK_RANGE_SELECT *quick;
1403
while ((quick= it++))
1410
Add a merged quick select to this ROR-intersection quick select.
1413
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1414
quick Quick select to be added. The quick select must return
1415
rows in rowid order.
1417
This call can only be made before init() is called.
1425
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1427
return quick_selects.push_back(quick);
1430
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1432
quick_selects.delete_elements();
1434
free_root(&alloc,MYF(0));
1435
if (need_to_fetch_row && head->file->inited != handler::NONE)
1436
head->file->ha_rnd_end();
1441
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1443
: session(session_param), scans_inited(false)
1447
rowid_length= table->file->ref_length;
1448
record= head->record[0];
1449
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1450
session_param->mem_root= &alloc;
1455
Do post-constructor initialization.
1457
QUICK_ROR_UNION_SELECT::init()
1464
int QUICK_ROR_UNION_SELECT::init()
1466
if (init_queue(&queue, quick_selects.elements, 0,
1467
false , QUICK_ROR_UNION_SELECT::queue_cmp,
1470
memset(&queue, 0, sizeof(QUEUE));
1474
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1476
prev_rowid= cur_rowid + head->file->ref_length;
1482
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1486
QUICK_ROR_UNION_SELECT::queue_cmp()
1487
arg Pointer to QUICK_ROR_UNION_SELECT
1488
val1 First merged select
1489
val2 Second merged select
1492
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1494
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1495
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1496
((QUICK_SELECT_I*)val2)->last_rowid);
1501
Initialize quick select for row retrieval.
1510
int QUICK_ROR_UNION_SELECT::reset()
1512
QUICK_SELECT_I *quick;
1514
have_prev_rowid= false;
1517
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1518
while ((quick= it++))
1520
if (quick->init_ror_merged_scan(false))
1525
queue_remove_all(&queue);
1527
Initialize scans for merged quick selects and put all merged quick
1528
selects into the queue.
1530
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1531
while ((quick= it++))
1535
if ((error= quick->get_next()))
1537
if (error == HA_ERR_END_OF_FILE)
1541
quick->save_last_pos();
1542
queue_insert(&queue, (unsigned char*)quick);
1545
if (head->file->ha_rnd_init(1))
1555
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1557
return quick_selects.push_back(quick_sel_range);
1560
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1562
delete_queue(&queue);
1563
quick_selects.delete_elements();
1564
if (head->file->inited != handler::NONE)
1565
head->file->ha_rnd_end();
1566
free_root(&alloc,MYF(0));
1571
QUICK_RANGE::QUICK_RANGE()
1572
:min_key(0),max_key(0),min_length(0),max_length(0),
1573
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1574
min_keypart_map(0), max_keypart_map(0)
1577
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1580
min_flag=arg.min_flag;
1581
max_flag=arg.max_flag;
1582
maybe_flag=arg.maybe_flag;
1583
maybe_null=arg.maybe_null;
1586
min_value=arg.min_value;
1587
max_value=arg.max_value;
1588
next_key_part=arg.next_key_part;
1589
use_count=1; elements=1;
1593
inline void SEL_ARG::make_root()
1595
left=right= &null_element;
1598
use_count=0; elements=1;
1601
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1602
const unsigned char *max_value_arg)
1603
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1604
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1605
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1606
next_key_part(0),color(BLACK),type(KEY_RANGE)
1608
left=right= &null_element;
1611
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1612
unsigned char *min_value_, unsigned char *max_value_,
1613
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1614
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1615
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1616
field(field_), min_value(min_value_), max_value(max_value_),
1617
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1619
left=right= &null_element;
1622
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1627
/* Bail out if we have already generated too many SEL_ARGs */
1628
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1631
if (type != KEY_RANGE)
1633
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1634
return 0; // out of memory
1635
tmp->prev= *next_arg; // Link into next/prev chain
1636
(*next_arg)->next=tmp;
1641
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1642
min_flag, max_flag, maybe_flag)))
1644
tmp->parent=new_parent;
1645
tmp->next_key_part=next_key_part;
1646
if (left != &null_element)
1647
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1650
tmp->prev= *next_arg; // Link into next/prev chain
1651
(*next_arg)->next=tmp;
1654
if (right != &null_element)
1655
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1658
increment_use_count(1);
1660
tmp->elements= this->elements;
1664
SEL_ARG *SEL_ARG::first()
1666
SEL_ARG *next_arg=this;
1667
if (!next_arg->left)
1668
return 0; // MAYBE_KEY
1669
while (next_arg->left != &null_element)
1670
next_arg=next_arg->left;
1674
SEL_ARG *SEL_ARG::last()
1676
SEL_ARG *next_arg=this;
1677
if (!next_arg->right)
1678
return 0; // MAYBE_KEY
1679
while (next_arg->right != &null_element)
1680
next_arg=next_arg->right;
1686
Check if a compare is ok, when one takes ranges in account
1687
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1690
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1694
/* First check if there was a compare to a min or max element */
1695
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1697
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1698
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1700
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1702
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1703
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1705
if (field->real_maybe_null()) // If null is part of key
1712
goto end; // NULL where equal
1713
a++; b++; // Skip NULL marker
1715
cmp=field->key_cmp(a , b);
1716
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1718
// Check if the compared equal arguments was defined with open/closed range
1720
if (a_flag & (NEAR_MIN | NEAR_MAX))
1722
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1724
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1725
return (a_flag & NEAR_MIN) ? 2 : -2;
1726
return (a_flag & NEAR_MIN) ? 1 : -1;
1728
if (b_flag & (NEAR_MIN | NEAR_MAX))
1729
return (b_flag & NEAR_MIN) ? -2 : 2;
1730
return 0; // The elements where equal
1734
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1736
SEL_ARG tmp_link,*next_arg,*root;
1737
next_arg= &tmp_link;
1738
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1740
next_arg->next=0; // Fix last link
1741
tmp_link.next->prev=0; // Fix first link
1742
if (root) // If not OOM
5111
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5131
if (key1->part != key2->part)
5135
return 0; // Can't optimize this
5138
// If one of the key is MAYBE_KEY then the found region may be bigger
5139
if (key1->type == SEL_ARG::MAYBE_KEY)
5145
if (key2->type == SEL_ARG::MAYBE_KEY)
5152
if (key1->use_count > 0)
5154
if (key2->use_count == 0 || key1->elements > key2->elements)
5156
std::swap(key1,key2);
5158
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5162
// Add tree at key2 to tree at key1
5163
bool key2_shared=key2->use_count != 0;
5164
key1->maybe_flag|=key2->maybe_flag;
5166
for (key2=key2->first(); key2; )
5168
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5173
tmp=key1->first(); // tmp.min > key2.min
5176
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5177
{ // Found tmp.max < key2.min
5178
SEL_ARG *next=tmp->next;
5179
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5181
// Join near ranges like tmp.max < 0 and key2.min >= 0
5182
SEL_ARG *key2_next=key2->next;
5185
if (!(key2=new SEL_ARG(*key2)))
5186
return 0; // out of memory
5187
key2->increment_use_count(key1->use_count+1);
5188
key2->next=key2_next; // New copy of key2
5190
key2->copy_min(tmp);
5191
if (!(key1=key1->tree_delete(tmp)))
5192
{ // Only one key in tree
5199
if (!(tmp=next)) // tmp.min > key2.min
5200
break; // Copy rest of key2
5203
{ // tmp.min > key2.min
5205
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5207
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5208
{ // ranges are connected
5209
tmp->copy_min_to_min(key2);
5210
key1->merge_flags(key2);
5211
if (tmp->min_flag & NO_MIN_RANGE &&
5212
tmp->max_flag & NO_MAX_RANGE)
5214
if (key1->maybe_flag)
5215
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5218
key2->increment_use_count(-1); // Free not used tree
5224
SEL_ARG *next=key2->next; // Keys are not overlapping
5227
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5230
key1=key1->insert(cpy);
5231
key2->increment_use_count(key1->use_count+1);
5234
key1=key1->insert(key2); // Will destroy key2_root
5241
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5242
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5244
if (tmp->is_same(key2))
5246
tmp->merge_flags(key2); // Copy maybe flags
5247
key2->increment_use_count(-1); // Free not used tree
5252
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5253
eq_tree(last->next->next_key_part,key2->next_key_part))
5257
key1=key1->tree_delete(save);
5259
last->copy_min(tmp);
5260
if (last->copy_min(key2) || last->copy_max(key2))
5263
for (; key2 ; key2=key2->next)
5264
key2->increment_use_count(-1); // Free not used tree
5265
if (key1->maybe_flag)
5266
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5274
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5275
{ // tmp.min <= x < key2.min
5276
SEL_ARG *new_arg=tmp->clone_first(key2);
5279
if ((new_arg->next_key_part= key1->next_key_part))
5280
new_arg->increment_use_count(key1->use_count+1);
5281
tmp->copy_min_to_min(key2);
5282
key1=key1->insert(new_arg);
5285
// tmp.min >= key2.min && tmp.min <= key2.max
5286
SEL_ARG key(*key2); // Get copy we can modify
5289
if (tmp->cmp_min_to_min(&key) > 0)
5290
{ // key.min <= x < tmp.min
5291
SEL_ARG *new_arg=key.clone_first(tmp);
5294
if ((new_arg->next_key_part=key.next_key_part))
5295
new_arg->increment_use_count(key1->use_count+1);
5296
key1=key1->insert(new_arg);
5298
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5299
{ // tmp.min. <= x <= tmp.max
5300
tmp->maybe_flag|= key.maybe_flag;
5301
key.increment_use_count(key1->use_count+1);
5302
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5303
if (!cmp) // Key2 is ready
5305
key.copy_max_to_min(tmp);
5306
if (!(tmp=tmp->next))
5308
SEL_ARG *tmp2= new SEL_ARG(key);
5311
key1=key1->insert(tmp2);
5315
if (tmp->cmp_min_to_max(&key) > 0)
5317
SEL_ARG *tmp2= new SEL_ARG(key);
5320
key1=key1->insert(tmp2);
5326
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5329
tmp->copy_max_to_min(&key);
5330
tmp->increment_use_count(key1->use_count+1);
5331
/* Increment key count as it may be used for next loop */
5332
key.increment_use_count(1);
5333
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5334
key1=key1->insert(new_arg);
5344
SEL_ARG *next=key2->next;
5347
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5350
key2->increment_use_count(key1->use_count+1);
5351
key1=key1->insert(tmp);
5354
key1=key1->insert(key2); // Will destroy key2_root
5362
/* Compare if two trees are equal */
5364
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5368
if (!a || !b || !a->is_same(b))
5370
if (a->left != &null_element && b->left != &null_element)
5372
if (!eq_tree(a->left,b->left))
5375
else if (a->left != &null_element || b->left != &null_element)
5377
if (a->right != &null_element && b->right != &null_element)
5379
if (!eq_tree(a->right,b->right))
5382
else if (a->right != &null_element || b->right != &null_element)
5384
if (a->next_key_part != b->next_key_part)
5386
if (!a->next_key_part != !b->next_key_part ||
5387
!eq_tree(a->next_key_part, b->next_key_part))
5395
SEL_ARG::insert(SEL_ARG *key)
5397
SEL_ARG *element, **par= NULL, *last_element= NULL;
5399
for (element= this; element != &null_element ; )
5401
last_element=element;
5402
if (key->cmp_min_to_min(element) > 0)
5404
par= &element->right; element= element->right;
5408
par = &element->left; element= element->left;
5412
key->parent=last_element;
5414
if (par == &last_element->left)
5416
key->next=last_element;
5417
if ((key->prev=last_element->prev))
5418
key->prev->next=key;
5419
last_element->prev=key;
5423
if ((key->next=last_element->next))
5424
key->next->prev=key;
5425
key->prev=last_element;
5426
last_element->next=key;
5428
key->left=key->right= &null_element;
5429
SEL_ARG *root=rb_insert(key); // rebalance tree
5430
root->use_count=this->use_count; // copy root info
5431
root->elements= this->elements+1;
5432
root->maybe_flag=this->maybe_flag;
5438
** Find best key with min <= given key
5439
** Because the call context this should never return 0 to get_range
5443
SEL_ARG::find_range(SEL_ARG *key)
5445
SEL_ARG *element=this,*found=0;
5449
if (element == &null_element)
5451
int cmp=element->cmp_min_to_min(key);
5457
element=element->right;
5460
element=element->left;
5466
Remove a element from the tree
5470
key Key that is to be deleted from tree (this)
5473
This also frees all sub trees that is used by the element
5476
root of new tree (with key deleted)
5480
SEL_ARG::tree_delete(SEL_ARG *key)
5482
enum leaf_color remove_color;
5483
SEL_ARG *root,*nod,**par,*fix_par;
5488
/* Unlink from list */
5490
key->prev->next=key->next;
5492
key->next->prev=key->prev;
5493
key->increment_use_count(-1);
5497
par=key->parent_ptr();
5499
if (key->left == &null_element)
5501
*par=nod=key->right;
5502
fix_par=key->parent;
5503
if (nod != &null_element)
5504
nod->parent=fix_par;
5505
remove_color= key->color;
5507
else if (key->right == &null_element)
5509
*par= nod=key->left;
5510
nod->parent=fix_par=key->parent;
5511
remove_color= key->color;
5515
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5516
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5517
fix_par=tmp->parent;
5518
if (nod != &null_element)
5519
nod->parent=fix_par;
5520
remove_color= tmp->color;
5522
tmp->parent=key->parent; // Move node in place of key
5523
(tmp->left=key->left)->parent=tmp;
5524
if ((tmp->right=key->right) != &null_element)
5525
tmp->right->parent=tmp;
5526
tmp->color=key->color;
5528
if (fix_par == key) // key->right == key->next
5529
fix_par=tmp; // new parent of nod
5532
if (root == &null_element)
5533
return(0); // Maybe root later
5534
if (remove_color == BLACK)
5535
root=rb_delete_fixup(root,nod,fix_par);
5537
test_rb_tree(root,root->parent);
5538
#endif /* EXTRA_DEBUG */
5540
root->use_count=this->use_count; // Fix root counters
5541
root->elements=this->elements-1;
5542
root->maybe_flag=this->maybe_flag;
5547
/* Functions to fix up the tree after insert and delete */
5549
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5551
SEL_ARG *y=leaf->right;
5552
leaf->right=y->left;
5553
if (y->left != &null_element)
5554
y->left->parent=leaf;
5555
if (!(y->parent=leaf->parent))
5558
*leaf->parent_ptr()=y;
5563
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5565
SEL_ARG *y=leaf->left;
5566
leaf->left=y->right;
5567
if (y->right != &null_element)
5568
y->right->parent=leaf;
5569
if (!(y->parent=leaf->parent))
5572
*leaf->parent_ptr()=y;
5579
SEL_ARG::rb_insert(SEL_ARG *leaf)
5581
SEL_ARG *y,*par,*par2,*root;
5582
root= this; root->parent= 0;
5585
while (leaf != root && (par= leaf->parent)->color == RED)
5586
{ // This can't be root or 1 level under
5587
if (par == (par2= leaf->parent->parent)->left)
5590
if (y->color == RED)
5595
leaf->color=RED; /* And the loop continues */
5599
if (leaf == par->right)
5601
left_rotate(&root,leaf->parent);
5602
par=leaf; /* leaf is now parent to old leaf */
5606
right_rotate(&root,par2);
5613
if (y->color == RED)
5618
leaf->color=RED; /* And the loop continues */
5622
if (leaf == par->left)
5624
right_rotate(&root,par);
5629
left_rotate(&root,par2);
5636
test_rb_tree(root,root->parent);
5637
#endif /* EXTRA_DEBUG */
5643
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5649
while (x != root && x->color == SEL_ARG::BLACK)
5654
if (w->color == SEL_ARG::RED)
5656
w->color=SEL_ARG::BLACK;
5657
par->color=SEL_ARG::RED;
5658
left_rotate(&root,par);
5661
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5663
w->color=SEL_ARG::RED;
5668
if (w->right->color == SEL_ARG::BLACK)
5670
w->left->color=SEL_ARG::BLACK;
5671
w->color=SEL_ARG::RED;
5672
right_rotate(&root,w);
5675
w->color=par->color;
5676
par->color=SEL_ARG::BLACK;
5677
w->right->color=SEL_ARG::BLACK;
5678
left_rotate(&root,par);
5686
if (w->color == SEL_ARG::RED)
5688
w->color=SEL_ARG::BLACK;
5689
par->color=SEL_ARG::RED;
5690
right_rotate(&root,par);
5693
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5695
w->color=SEL_ARG::RED;
5700
if (w->left->color == SEL_ARG::BLACK)
5702
w->right->color=SEL_ARG::BLACK;
5703
w->color=SEL_ARG::RED;
5704
left_rotate(&root,w);
5707
w->color=par->color;
5708
par->color=SEL_ARG::BLACK;
5709
w->left->color=SEL_ARG::BLACK;
5710
right_rotate(&root,par);
5717
x->color=SEL_ARG::BLACK;
5722
/* Test that the properties for a red-black tree hold */
5725
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5727
int count_l,count_r;
5729
if (element == &null_element)
5730
return 0; // Found end of tree
5731
if (element->parent != parent)
5733
sql_print_error("Wrong tree: Parent doesn't point at parent");
5736
if (element->color == SEL_ARG::RED &&
5737
(element->left->color == SEL_ARG::RED ||
5738
element->right->color == SEL_ARG::RED))
5740
sql_print_error("Wrong tree: Found two red in a row");
5743
if (element->left == element->right && element->left != &null_element)
5745
sql_print_error("Wrong tree: Found right == left");
5748
count_l=test_rb_tree(element->left,element);
5749
count_r=test_rb_tree(element->right,element);
5750
if (count_l >= 0 && count_r >= 0)
5752
if (count_l == count_r)
5753
return count_l+(element->color == SEL_ARG::BLACK);
5754
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5757
return -1; // Error, no more warnings
5762
Count how many times SEL_ARG graph "root" refers to its part "key"
5765
count_key_part_usage()
5766
root An RB-Root node in a SEL_ARG graph.
5767
key Another RB-Root node in that SEL_ARG graph.
5770
The passed "root" node may refer to "key" node via root->next_key_part,
5773
This function counts how many times the node "key" is referred (via
5774
SEL_ARG::next_key_part) by
5775
- intervals of RB-tree pointed by "root",
5776
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5777
intervals of RB-tree pointed by "root",
5780
Here is an example (horizontal links represent next_key_part pointers,
5781
vertical links - next/prev prev pointers):
5784
|root|-----------------+
5788
+----+ +---+ $ | +---+ Here the return value
5789
| |- ... -| |---$-+--+->|key| will be 4.
5790
+----+ +---+ $ | | +---+
5795
| |---| |---------+ |
5802
Number of links to "key" from nodes reachable from "root".
5805
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5808
for (root=root->first(); root ; root=root->next)
5810
if (root->next_key_part)
5812
if (root->next_key_part == key)
5814
if (root->next_key_part->part < key->part)
5815
count+=count_key_part_usage(root->next_key_part,key);
5823
Check if SEL_ARG::use_count value is correct
5826
SEL_ARG::test_use_count()
5827
root The root node of the SEL_ARG graph (an RB-tree root node that
5828
has the least value of sel_arg->part in the entire graph, and
5829
thus is the "origin" of the graph)
5832
Check if SEL_ARG::use_count value is correct. See the definition of
5833
use_count for what is "correct".
5836
void SEL_ARG::test_use_count(SEL_ARG *root)
5839
if (this == root && use_count != 1)
5841
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5844
if (this->type != SEL_ARG::KEY_RANGE)
5846
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5849
if (pos->next_key_part)
5851
ulong count=count_key_part_usage(root,pos->next_key_part);
5852
if (count > pos->next_key_part->use_count)
5854
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5855
"should be %lu", (long unsigned int)pos,
5856
pos->next_key_part->use_count, count);
5859
pos->next_key_part->test_use_count(root);
5862
if (e_count != elements)
5863
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5864
e_count, elements, (long unsigned int) this);
3523
5869
/****************************************************************************
3524
5870
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3525
5871
****************************************************************************/
3527
5873
/* MRR range sequence, SEL_ARG* implementation: stack entry */
3528
typedef struct st_range_seq_entry
5874
typedef struct st_range_seq_entry
3531
5877
Pointers in min and max keys. They point to right-after-end of key
3532
5878
images. The 0-th entry has these pointing to key tuple start.
3534
5880
unsigned char *min_key, *max_key;
3537
5883
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3538
5884
min_key_flag may have NULL_RANGE set.
3540
5886
uint32_t min_key_flag, max_key_flag;
3542
5888
/* Number of key parts */
3543
5889
uint32_t min_key_parts, max_key_parts;
3544
optimizer::SEL_ARG *key_tree;
3545
5891
} RANGE_SEQ_ENTRY;
4339
Range sequence interface implementation for array<QuickRange>: initialize
6699
Perform key scans for all used indexes (except CPK), get rowids and merge
6700
them into an ordered non-recurrent sequence of rowids.
6702
The merge/duplicate removal is performed using Unique class. We put all
6703
rowids into Unique, get the sorted sequence and destroy the Unique.
6705
If table has a clustered primary key that covers all rows (true for bdb
6706
and innodb currently) and one of the index_merge scans is a scan on PK,
6707
then rows that will be retrieved by PK scan are not put into Unique and
6708
primary key scan is not performed here, it is performed later separately.
6715
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6717
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6718
QUICK_RANGE_SELECT* cur_quick;
6721
handler *file= head->file;
6723
file->extra(HA_EXTRA_KEYREAD);
6724
head->prepare_for_position();
6726
cur_quick_it.rewind();
6727
cur_quick= cur_quick_it++;
6728
assert(cur_quick != 0);
6731
We reuse the same instance of handler so we need to call both init and
6734
if (cur_quick->init() || cur_quick->reset())
6737
unique= new Unique(refpos_order_cmp, (void *)file,
6739
session->variables.sortbuff_size);
6744
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6746
cur_quick->range_end();
6747
cur_quick= cur_quick_it++;
6751
if (cur_quick->file->inited != handler::NONE)
6752
cur_quick->file->ha_index_end();
6753
if (cur_quick->init() || cur_quick->reset())
6759
if (result != HA_ERR_END_OF_FILE)
6761
cur_quick->range_end();
6767
if (session->killed)
6770
/* skip row if it will be retrieved by clustered PK scan */
6771
if (pk_quick_select && pk_quick_select->row_in_ranges())
6774
cur_quick->file->position(cur_quick->record);
6775
result= unique->unique_add((char*)cur_quick->file->ref);
6781
/* ok, all row ids are in Unique */
6782
result= unique->get(head);
6784
doing_pk_scan= false;
6785
/* index_merge currently doesn't support "using index" at all */
6786
file->extra(HA_EXTRA_NO_KEYREAD);
6787
/* start table scan */
6788
init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
6794
Get next row for index_merge.
6796
The rows are read from
6797
1. rowids stored in Unique.
6798
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6799
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6802
int QUICK_INDEX_MERGE_SELECT::get_next()
6807
return(pk_quick_select->get_next());
6809
if ((result= read_record.read_record(&read_record)) == -1)
6811
result= HA_ERR_END_OF_FILE;
6812
end_read_record(&read_record);
6813
/* All rows from Unique have been retrieved, do a clustered PK scan */
6814
if (pk_quick_select)
6816
doing_pk_scan= true;
6817
if ((result= pk_quick_select->init()) ||
6818
(result= pk_quick_select->reset()))
6820
return(pk_quick_select->get_next());
6829
Retrieve next record.
6831
QUICK_ROR_INTERSECT_SELECT::get_next()
6834
Invariant on enter/exit: all intersected selects have retrieved all index
6835
records with rowid <= some_rowid_val and no intersected select has
6836
retrieved any index records with rowid > some_rowid_val.
6837
We start fresh and loop until we have retrieved the same rowid in each of
6838
the key scans or we got an error.
6840
If a Clustered PK scan is present, it is used only to check if row
6841
satisfies its condition (and never used for row retrieval).
6845
other - Error code if any error occurred.
6848
int QUICK_ROR_INTERSECT_SELECT::get_next()
6850
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6851
QUICK_RANGE_SELECT* quick;
6853
uint32_t last_rowid_count=0;
6857
/* Get a rowid for first quick and save it as a 'candidate' */
6859
error= quick->get_next();
6862
while (!error && !cpk_quick->row_in_ranges())
6863
error= quick->get_next();
6868
quick->file->position(quick->record);
6869
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6870
last_rowid_count= 1;
6872
while (last_rowid_count < quick_selects.elements)
6874
if (!(quick= quick_it++))
6882
if ((error= quick->get_next()))
6884
quick->file->position(quick->record);
6885
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6888
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6891
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6894
while (!cpk_quick->row_in_ranges())
6896
if ((error= quick->get_next()))
6900
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6901
last_rowid_count= 1;
6905
/* current 'candidate' row confirmed by this select */
6910
/* We get here if we got the same row ref in all scans. */
6911
if (need_to_fetch_row)
6912
error= head->file->rnd_pos(head->record[0], last_rowid);
6913
} while (error == HA_ERR_RECORD_DELETED);
6919
Retrieve next record.
6921
QUICK_ROR_UNION_SELECT::get_next()
6924
Enter/exit invariant:
6925
For each quick select in the queue a {key,rowid} tuple has been
6926
retrieved but the corresponding row hasn't been passed to output.
6930
other - Error code if any error occurred.
6933
int QUICK_ROR_UNION_SELECT::get_next()
6936
QUICK_SELECT_I *quick;
6943
if (!queue.elements)
6944
return(HA_ERR_END_OF_FILE);
6945
/* Ok, we have a queue with >= 1 scans */
6947
quick= (QUICK_SELECT_I*)queue_top(&queue);
6948
memcpy(cur_rowid, quick->last_rowid, rowid_length);
6950
/* put into queue rowid from the same stream as top element */
6951
if ((error= quick->get_next()))
6953
if (error != HA_ERR_END_OF_FILE)
6955
queue_remove(&queue, 0);
6959
quick->save_last_pos();
6960
queue_replaced(&queue);
6963
if (!have_prev_rowid)
6965
/* No rows have been returned yet */
6967
have_prev_rowid= true;
6970
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
6974
cur_rowid= prev_rowid;
6977
error= head->file->rnd_pos(quick->record, prev_rowid);
6978
} while (error == HA_ERR_RECORD_DELETED);
6983
int QUICK_RANGE_SELECT::reset()
6986
unsigned char *mrange_buff;
6988
HANDLER_BUFFER empty_buf;
6990
cur_range= (QUICK_RANGE**) ranges.buffer;
6992
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6995
/* Allocate buffer if we need one but haven't allocated it yet */
6996
if (mrr_buf_size && !mrr_buf_desc)
6998
buf_size= mrr_buf_size;
6999
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7000
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7001
&mrange_buff, buf_size,
7004
/* Try to shrink the buffers until both are 0. */
7008
return(HA_ERR_OUT_OF_MEM);
7010
/* Initialize the handler buffer. */
7011
mrr_buf_desc->buffer= mrange_buff;
7012
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7013
mrr_buf_desc->end_of_used_area= mrange_buff;
7017
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7020
mrr_flags |= HA_MRR_SORTED;
7021
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7022
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7023
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7030
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4342
7033
quick_range_seq_init()
4343
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7034
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4344
7035
n_ranges Number of ranges in the sequence (ignored)
4345
flags MRR flags (currently not used)
7036
flags MRR flags (currently not used)
4348
7039
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)
7042
range_seq_t quick_range_seq_init(void *init_param,
7043
uint32_t n_ranges __attribute__((unused)),
7044
uint32_t flags __attribute__((unused)))
4353
optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
4354
quick->qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
4355
quick->qr_traversal_ctx.cur= (optimizer::QuickRange**)quick->ranges.buffer;
7046
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7047
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7048
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
4356
7049
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4357
7050
quick->ranges.elements;
4358
7051
return &quick->qr_traversal_ctx;
4372
7065
1 No more ranges in the sequence
4374
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7068
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4376
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7070
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4378
7072
if (ctx->cur == ctx->last)
4379
7073
return 1; /* no more ranges */
4381
optimizer::QuickRange *cur= *(ctx->cur);
7075
QUICK_RANGE *cur= *(ctx->cur);
4382
7076
key_range *start_key= &range->start_key;
4383
key_range *end_key= &range->end_key;
7077
key_range *end_key= &range->end_key;
4385
start_key->key= cur->min_key;
7079
start_key->key= cur->min_key;
4386
7080
start_key->length= cur->min_length;
4387
7081
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;
7082
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7083
(cur->flag & EQ_RANGE) ?
7084
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7085
end_key->key= cur->max_key;
7086
end_key->length= cur->max_length;
4393
7087
end_key->keypart_map= cur->max_keypart_map;
4395
7089
We use HA_READ_AFTER_KEY here because if we are reading on a key
4396
7090
prefix. We want to find all keys with this prefix.
4398
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7092
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4400
7094
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);
7101
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7104
mrr_persistent_flag_storage()
7105
seq Range sequence being traversed
7109
MRR/NDB implementation needs to store some bits for each range. This
7110
function returns a reference to the "range_flag" associated with the
7113
This function should be removed when we get a proper MRR/NDB
7117
Reference to range_flag associated with range number #idx
7120
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7122
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7123
return ctx->first[idx]->flag;
7128
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7131
mrr_get_ptr_by_idx()
7132
seq Range sequence bening traversed
7133
idx Number of the range
7136
An extension of MRR range sequence interface needed by NDB: return the
7137
data associated with the given range.
7139
A proper MRR interface implementer is supposed to store and return
7140
range-associated data. NDB stores number of the range instead. So this
7141
is a helper function that translates range number to range associated
7144
This function does nothing, as currrently there is only one user of the
7145
MRR interface - the quick range select code, and this user doesn't need
7146
to use range-associated data.
7149
Reference to range-associated data
7152
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7153
uint32_t idx __attribute__((unused)))
7161
Get next possible record using quick-struct.
7164
QUICK_RANGE_SELECT::get_next()
7167
Record is read into table->record[0]
7171
HA_ERR_END_OF_FILE No (more) rows in range
7175
int QUICK_RANGE_SELECT::get_next()
7178
if (in_ror_merged_scan)
7181
We don't need to signal the bitmap change as the bitmap is always the
7182
same for this head->file
7184
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7187
int result= file->multi_range_read_next(&dummy);
7189
if (in_ror_merged_scan)
7191
/* Restore bitmaps set on entry */
7192
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7199
Get the next record with a different prefix.
7202
QUICK_RANGE_SELECT::get_next_prefix()
7203
prefix_length length of cur_prefix
7204
cur_prefix prefix of a key to be searched for
7207
Each subsequent call to the method retrieves the first record that has a
7208
prefix with length prefix_length different from cur_prefix, such that the
7209
record with the new prefix is within the ranges described by
7210
this->ranges. The record found is stored into the buffer pointed by
7212
The method is useful for GROUP-BY queries with range conditions to
7213
discover the prefix of the next group that satisfies the range conditions.
7216
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7217
methods should be unified into a more general one to reduce code
7222
HA_ERR_END_OF_FILE if returned all keys
7223
other if some error occurred
7226
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7227
key_part_map keypart_map,
7228
unsigned char *cur_prefix)
7233
key_range start_key, end_key;
7236
/* Read the next record in the same range with prefix after cur_prefix. */
7237
assert(cur_prefix != 0);
7238
result= file->index_read_map(record, cur_prefix, keypart_map,
7240
if (result || (file->compare_key(file->end_range) <= 0))
7244
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7247
/* Ranges have already been used up before. None is left for read. */
7249
return(HA_ERR_END_OF_FILE);
7251
last_range= *(cur_range++);
7253
start_key.key= (const unsigned char*) last_range->min_key;
7254
start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7255
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7256
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7257
(last_range->flag & EQ_RANGE) ?
7258
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7259
end_key.key= (const unsigned char*) last_range->max_key;
7260
end_key.length= cmin(last_range->max_length, (uint16_t)prefix_length);
7261
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7263
We use READ_AFTER_KEY here because if we are reading on a key
7264
prefix we want to find all keys with this prefix
7266
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7269
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7270
last_range->max_keypart_map ? &end_key : 0,
7271
test(last_range->flag & EQ_RANGE),
7273
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7274
last_range= 0; // Stop searching
7276
if (result != HA_ERR_END_OF_FILE)
7278
last_range= 0; // No matching rows; go to next range
7284
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7287
It is assumed that currently a scan is being done on another index
7288
which reads all necessary parts of the index that is scanned by this
7290
The implementation does a binary search on sorted array of disjoint
7291
ranges, without taking size of range into account.
7293
This function is used to filter out clustered PK scan rows in
7294
index_merge quick select.
7297
true if current row will be retrieved by this quick select
7301
bool QUICK_RANGE_SELECT::row_in_ranges()
7305
uint32_t max= ranges.elements - 1;
7306
uint32_t mid= (max + min)/2;
7310
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7312
/* current row value > mid->max */
7317
mid= (min + max) / 2;
7319
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7320
return (!cmp_next(res) && !cmp_prev(res));
7324
This is a hack: we inherit from QUICK_SELECT so that we can use the
7325
get_next() interface, but we have to hold a pointer to the original
7326
QUICK_SELECT because its data are used all over the place. What
7327
should be done is to factor out the data that is needed into a base
7328
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7329
which handle the ranges and implement the get_next() function. But
7330
for now, this seems to work right at least.
7333
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7334
uint32_t used_key_parts_arg __attribute__((unused)),
7335
bool *create_err __attribute__((unused)))
7336
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7340
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7341
QUICK_RANGE **end_range= pr + ranges.elements;
7342
for (; pr!=end_range; pr++)
7343
rev_ranges.push_front(*pr);
7345
/* Remove EQ_RANGE flag for keys that are not using the full key */
7346
for (r = rev_it++; r; r = rev_it++)
7348
if ((r->flag & EQ_RANGE) &&
7349
head->key_info[index].key_length != r->max_length)
7350
r->flag&= ~EQ_RANGE;
7353
q->dont_free=1; // Don't free shared mem
7358
int QUICK_SELECT_DESC::get_next()
7360
/* The max key is handled as follows:
7361
* - if there is NO_MAX_RANGE, start at the end and move backwards
7362
* - if it is an EQ_RANGE, which means that max key covers the entire
7363
* key, go directly to the key and read through it (sorting backwards is
7364
* same as sorting forwards)
7365
* - if it is NEAR_MAX, go to the key or next, step back once, and
7367
* - otherwise (not NEAR_MAX == include the key), go after the key,
7368
* step back once, and move backwards
7375
{ // Already read through key
7376
result = ((last_range->flag & EQ_RANGE)
7377
? file->index_next_same(record, last_range->min_key,
7378
last_range->min_length) :
7379
file->index_prev(record));
7382
if (cmp_prev(*rev_it.ref()) == 0)
7385
else if (result != HA_ERR_END_OF_FILE)
7389
if (!(last_range= rev_it++))
7390
return(HA_ERR_END_OF_FILE); // All ranges used
7392
if (last_range->flag & NO_MAX_RANGE) // Read last record
7395
if ((local_error=file->index_last(record)))
7396
return(local_error); // Empty table
7397
if (cmp_prev(last_range) == 0)
7399
last_range= 0; // No match; go to next range
7403
if (last_range->flag & EQ_RANGE)
7405
result = file->index_read_map(record, last_range->max_key,
7406
last_range->max_keypart_map,
7411
assert(last_range->flag & NEAR_MAX ||
7412
range_reads_after_key(last_range));
7413
result=file->index_read_map(record, last_range->max_key,
7414
last_range->max_keypart_map,
7415
((last_range->flag & NEAR_MAX) ?
7416
HA_READ_BEFORE_KEY :
7417
HA_READ_PREFIX_LAST_OR_PREV));
7421
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7423
last_range= 0; // Not found, to next range
7426
if (cmp_prev(last_range) == 0)
7428
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7429
last_range= 0; // Stop searching
7430
return(0); // Found key is in range
7432
last_range= 0; // To next range
7438
Compare if found key is over max-value
7439
Returns 0 if key <= range->max_key
7440
TODO: Figure out why can't this function be as simple as cmp_prev().
7443
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7445
if (range_arg->flag & NO_MAX_RANGE)
7446
return 0; /* key can't be to large */
7448
KEY_PART *key_part=key_parts;
7449
uint32_t store_length;
7451
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7453
key+= store_length, key_part++)
7456
store_length= key_part->store_length;
7457
if (key_part->null_bit)
7461
if (!key_part->field->is_null())
7465
else if (key_part->field->is_null())
7467
key++; // Skip null byte
7470
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7475
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7480
Returns 0 if found key is inside range (found key >= range->min_key).
7483
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7486
if (range_arg->flag & NO_MIN_RANGE)
7487
return 0; /* key can't be to small */
7489
cmp= key_cmp(key_part_info, range_arg->min_key,
7490
range_arg->min_length);
7491
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7493
return 1; // outside of range
7498
* true if this range will require using HA_READ_AFTER_KEY
7499
See comment in get_next() about this
7502
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7504
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7505
!(range_arg->flag & EQ_RANGE) ||
7506
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7510
void QUICK_RANGE_SELECT::add_info_string(String *str)
7512
KEY *key_info= head->key_info + index;
7513
str->append(key_info->name);
7516
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7518
QUICK_RANGE_SELECT *quick;
7520
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7521
str->append(STRING_WITH_LEN("sort_union("));
7522
while ((quick= it++))
7528
quick->add_info_string(str);
7530
if (pk_quick_select)
7533
pk_quick_select->add_info_string(str);
7538
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7541
QUICK_RANGE_SELECT *quick;
7542
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7543
str->append(STRING_WITH_LEN("intersect("));
7544
while ((quick= it++))
7546
KEY *key_info= head->key_info + quick->index;
7551
str->append(key_info->name);
7555
KEY *key_info= head->key_info + cpk_quick->index;
7557
str->append(key_info->name);
7562
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7565
QUICK_SELECT_I *quick;
7566
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7567
str->append(STRING_WITH_LEN("union("));
7568
while ((quick= it++))
7574
quick->add_info_string(str);
7580
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7581
String *used_lengths)
7585
KEY *key_info= head->key_info + index;
7586
key_names->append(key_info->name);
7587
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7588
used_lengths->append(buf, length);
7591
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7592
String *used_lengths)
7597
QUICK_RANGE_SELECT *quick;
7599
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7600
while ((quick= it++))
7606
key_names->append(',');
7607
used_lengths->append(',');
7610
KEY *key_info= head->key_info + quick->index;
7611
key_names->append(key_info->name);
7612
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7613
used_lengths->append(buf, length);
7615
if (pk_quick_select)
7617
KEY *key_info= head->key_info + pk_quick_select->index;
7618
key_names->append(',');
7619
key_names->append(key_info->name);
7620
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7621
used_lengths->append(',');
7622
used_lengths->append(buf, length);
7626
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7627
String *used_lengths)
7632
QUICK_RANGE_SELECT *quick;
7633
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7634
while ((quick= it++))
7636
KEY *key_info= head->key_info + quick->index;
7641
key_names->append(',');
7642
used_lengths->append(',');
7644
key_names->append(key_info->name);
7645
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7646
used_lengths->append(buf, length);
7651
KEY *key_info= head->key_info + cpk_quick->index;
7652
key_names->append(',');
7653
key_names->append(key_info->name);
7654
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7655
used_lengths->append(',');
7656
used_lengths->append(buf, length);
7660
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7661
String *used_lengths)
7664
QUICK_SELECT_I *quick;
7665
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7666
while ((quick= it++))
7672
used_lengths->append(',');
7673
key_names->append(',');
7675
quick->add_keys_and_lengths(key_names, used_lengths);
7680
/*******************************************************************************
7681
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7682
*******************************************************************************/
7684
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7685
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7686
PARAM *param, uint32_t *param_idx);
7687
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7688
KEY_PART_INFO *first_non_group_part,
7689
KEY_PART_INFO *min_max_arg_part,
7690
KEY_PART_INFO *last_part, Session *session,
7691
unsigned char *key_infix, uint32_t *key_infix_len,
7692
KEY_PART_INFO **first_non_infix_part);
7694
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7695
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,
7698
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7699
uint32_t group_key_parts, SEL_TREE *range_tree,
7700
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7701
bool have_min, bool have_max,
7702
double *read_cost, ha_rows *records);
5550
8755
quick->update_key_stat();
5551
8756
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 */
8763
Construct new quick select for group queries with min/max.
8766
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8767
table The table being accessed
8768
join Descriptor of the current query
8769
have_min true if the query selects a MIN function
8770
have_max true if the query selects a MAX function
8771
min_max_arg_part The only argument field of all MIN/MAX functions
8772
group_prefix_len Length of all key parts in the group prefix
8773
prefix_key_parts All key parts in the group prefix
8774
index_info The index chosen for data access
8775
use_index The id of index_info
8776
read_cost Cost of this access method
8777
records Number of records returned
8778
key_infix_len Length of the key infix appended to the group prefix
8779
key_infix Infix of constants from equality predicates
8780
parent_alloc Memory pool for this and quick_prefix_select data
8786
QUICK_GROUP_MIN_MAX_SELECT::
8787
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8789
KEY_PART_INFO *min_max_arg_part_arg,
8790
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8791
uint32_t used_key_parts_arg, KEY *index_info_arg,
8792
uint32_t use_index, double read_cost_arg,
8793
ha_rows records_arg, uint32_t key_infix_len_arg,
8794
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8795
:join(join_arg), index_info(index_info_arg),
8796
group_prefix_len(group_prefix_len_arg),
8797
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8798
have_max(have_max_arg), seen_first_key(false),
8799
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8800
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8801
max_functions_it(NULL)
8806
record= head->record[0];
8807
tmp_record= head->record[1];
8808
read_time= read_cost_arg;
8809
records= records_arg;
8810
used_key_parts= used_key_parts_arg;
8811
real_key_parts= used_key_parts_arg;
8812
real_prefix_len= group_prefix_len + key_infix_len;
8814
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8817
We can't have parent_alloc set as the init function can't handle this case
8820
assert(!parent_alloc);
8823
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
8824
join->session->mem_root= &alloc;
8827
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8832
Do post-constructor initialization.
8835
QUICK_GROUP_MIN_MAX_SELECT::init()
8838
The method performs initialization that cannot be done in the constructor
8839
such as memory allocations that may fail. It allocates memory for the
8840
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8841
updated during execution.
8848
int QUICK_GROUP_MIN_MAX_SELECT::init()
8850
if (group_prefix) /* Already initialized. */
8853
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8856
We may use group_prefix to store keys with all select fields, so allocate
8857
enough space for it.
8859
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
8860
real_prefix_len + min_max_arg_len)))
8863
if (key_infix_len > 0)
8866
The memory location pointed to by key_infix will be deleted soon, so
8867
allocate a new buffer and copy the key_infix into it.
8869
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
8872
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8873
this->key_infix= tmp_key_infix;
8876
if (min_max_arg_part)
8878
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8883
if (!(min_functions= new List<Item_sum>))
8887
min_functions= NULL;
8890
if (!(max_functions= new List<Item_sum>))
8894
max_functions= NULL;
8896
Item_sum *min_max_item;
8897
Item_sum **func_ptr= join->sum_funcs;
8898
while ((min_max_item= *(func_ptr++)))
8900
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8901
min_functions->push_back(min_max_item);
8902
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8903
max_functions->push_back(min_max_item);
8908
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
8914
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
8919
min_max_ranges.elements= 0;
8925
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8927
if (file->inited != handler::NONE)
8928
file->ha_index_end();
8929
if (min_max_arg_part)
8930
delete_dynamic(&min_max_ranges);
8931
free_root(&alloc,MYF(0));
8932
delete min_functions_it;
8933
delete max_functions_it;
8934
delete quick_prefix_select;
8940
Eventually create and add a new quick range object.
8943
QUICK_GROUP_MIN_MAX_SELECT::add_range()
8944
sel_range Range object from which a
8947
Construct a new QUICK_RANGE object from a SEL_ARG object, and
8948
add it to the array min_max_ranges. If sel_arg is an infinite
8949
range, e.g. (x < 5 or x > 4), then skip it and do not construct
8957
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8960
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
8962
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8963
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8966
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
8967
!(sel_range->max_flag & NO_MAX_RANGE))
8969
if (sel_range->maybe_null &&
8970
sel_range->min_value[0] && sel_range->max_value[0])
8971
range_flag|= NULL_RANGE; /* IS NULL condition */
8972
else if (memcmp(sel_range->min_value, sel_range->max_value,
8973
min_max_arg_len) == 0)
8974
range_flag|= EQ_RANGE; /* equality condition */
8976
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
8977
make_keypart_map(sel_range->part),
8978
sel_range->max_value, min_max_arg_len,
8979
make_keypart_map(sel_range->part),
8983
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
8990
Opens the ranges if there are more conditions in quick_prefix_select than
8991
the ones used for jumping through the prefixes.
8994
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
8997
quick_prefix_select is made over the conditions on the whole key.
8998
It defines a number of ranges of length x.
8999
However when jumping through the prefixes we use only the the first
9000
few most significant keyparts in the range key. However if there
9001
are more keyparts to follow the ones we are using we must make the
9002
condition on the key inclusive (because x < "ab" means
9003
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9004
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9006
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9008
if (quick_prefix_select &&
9009
group_prefix_len < quick_prefix_select->max_used_key_length)
9014
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9018
get_dynamic(arr, (unsigned char*)&range, inx);
9019
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9026
Determine the total number and length of the keys that will be used for
9030
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9033
The total length of the keys used for index lookup depends on whether
9034
there are any predicates referencing the min/max argument, and/or if
9035
the min/max argument field can be NULL.
9036
This function does an optimistic analysis whether the search key might
9037
be extended by a constant for the min/max keypart. It is 'optimistic'
9038
because during actual execution it may happen that a particular range
9039
is skipped, and then a shorter key will be used. However this is data
9040
dependent and can't be easily estimated here.
9046
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9048
max_used_key_length= real_prefix_len;
9049
if (min_max_ranges.elements > 0)
9051
QUICK_RANGE *cur_range;
9053
{ /* Check if the right-most range has a lower boundary. */
9054
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9055
min_max_ranges.elements - 1);
9056
if (!(cur_range->flag & NO_MIN_RANGE))
9058
max_used_key_length+= min_max_arg_len;
9064
{ /* Check if the left-most range has an upper boundary. */
9065
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9066
if (!(cur_range->flag & NO_MAX_RANGE))
9068
max_used_key_length+= min_max_arg_len;
9074
else if (have_min && min_max_arg_part &&
9075
min_max_arg_part->field->real_maybe_null())
9078
If a MIN/MAX argument value is NULL, we can quickly determine
9079
that we're in the beginning of the next group, because NULLs
9080
are always < any other value. This allows us to quickly
9081
determine the end of the current group and jump to the next
9082
group (see next_min()) and thus effectively increases the
9085
max_used_key_length+= min_max_arg_len;
9092
Initialize a quick group min/max select for key retrieval.
9095
QUICK_GROUP_MIN_MAX_SELECT::reset()
9098
Initialize the index chosen for access and find and store the prefix
9099
of the last group. The method is expensive since it performs disk access.
9106
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9110
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9111
if ((result= file->ha_index_init(index,1)))
9113
if (quick_prefix_select && quick_prefix_select->reset())
9115
result= file->index_last(record);
9116
if (result == HA_ERR_END_OF_FILE)
9118
/* Save the prefix of the last group. */
9119
key_copy(last_prefix, record, index_info, group_prefix_len);
9127
Get the next key containing the MIN and/or MAX key for the next group.
9130
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9133
The method finds the next subsequent group of records that satisfies the
9134
query conditions and finds the keys that contain the MIN/MAX values for
9135
the key part referenced by the MIN/MAX function(s). Once a group and its
9136
MIN/MAX values are found, store these values in the Item_sum objects for
9137
the MIN/MAX functions. The rest of the values in the result row are stored
9138
in the Item_field::result_field of each select field. If the query does
9139
not contain MIN and/or MAX functions, then the function only finds the
9140
group prefix, which is a query answer itself.
9143
If both MIN and MAX are computed, then we use the fact that if there is
9144
no MIN key, there can't be a MAX key as well, so we can skip looking
9145
for a MAX key in this case.
9149
HA_ERR_END_OF_FILE if returned all keys
9150
other if some error occurred
9153
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9158
int is_last_prefix= 0;
9161
Loop until a group is found that satisfies all query conditions or the last
9166
result= next_prefix();
9168
Check if this is the last group prefix. Notice that at this point
9169
this->record contains the current prefix in record format.
9173
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9175
assert(is_last_prefix <= 0);
9179
if (result == HA_ERR_KEY_NOT_FOUND)
9186
min_res= next_min();
9188
update_min_result();
9190
/* If there is no MIN in the group, there is no MAX either. */
9191
if ((have_max && !have_min) ||
9192
(have_max && have_min && (min_res == 0)))
9194
max_res= next_max();
9196
update_max_result();
9197
/* If a MIN was found, a MAX must have been found as well. */
9198
assert((have_max && !have_min) ||
9199
(have_max && have_min && (max_res == 0)));
9202
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9203
are equality predicates for the key parts after the group, find the
9204
first sub-group with the extended prefix.
9206
if (!have_min && !have_max && key_infix_len > 0)
9207
result= file->index_read_map(record, group_prefix,
9208
make_prev_keypart_map(real_key_parts),
9211
result= have_min ? min_res : have_max ? max_res : result;
9212
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9213
is_last_prefix != 0);
9218
Partially mimic the behavior of end_select_send. Copy the
9219
field data from Item_field::field into Item_field::result_field
9220
of each non-aggregated field (the group fields, and optionally
9221
other fields in non-ANSI SQL mode).
9223
copy_fields(&join->tmp_table_param);
9225
else if (result == HA_ERR_KEY_NOT_FOUND)
9226
result= HA_ERR_END_OF_FILE;
9233
Retrieve the minimal key in the next group.
9236
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9239
Find the minimal key within this group such that the key satisfies the query
9240
conditions and NULL semantics. The found key is loaded into this->record.
9243
Depending on the values of min_max_ranges.elements, key_infix_len, and
9244
whether there is a NULL in the MIN field, this function may directly
9245
return without any data access. In this case we use the key loaded into
9246
this->record by the call to this->next_prefix() just before this call.
9250
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9251
HA_ERR_END_OF_FILE - "" -
9252
other if some error occurred
9255
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9259
/* Find the MIN key using the eventually extended group prefix. */
9260
if (min_max_ranges.elements > 0)
9262
if ((result= next_min_in_range()))
9267
/* Apply the constant equality conditions to the non-group select fields */
9268
if (key_infix_len > 0)
9270
if ((result= file->index_read_map(record, group_prefix,
9271
make_prev_keypart_map(real_key_parts),
9272
HA_READ_KEY_EXACT)))
9277
If the min/max argument field is NULL, skip subsequent rows in the same
9278
group with NULL in it. Notice that:
9279
- if the first row in a group doesn't have a NULL in the field, no row
9280
in the same group has (because NULL < any other value),
9281
- min_max_arg_part->field->ptr points to some place in 'record'.
9283
if (min_max_arg_part && min_max_arg_part->field->is_null())
9285
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9286
key_copy(tmp_record, record, index_info, 0);
9287
result= file->index_read_map(record, tmp_record,
9288
make_keypart_map(real_key_parts),
9291
Check if the new record belongs to the current group by comparing its
9292
prefix with the group's prefix. If it is from the next group, then the
9293
whole group has NULLs in the MIN/MAX field, so use the first record in
9294
the group as a result.
9296
It is possible to reuse this new record as the result candidate for the
9297
next call to next_min(), and to save one lookup in the next call. For
9298
this add a new member 'this->next_group_prefix'.
9302
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9303
key_restore(record, tmp_record, index_info, 0);
9305
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9306
result= 0; /* There is a result in any case. */
9311
If the MIN attribute is non-nullable, this->record already contains the
9312
MIN key in the group, so just return.
9319
Retrieve the maximal key in the next group.
9322
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9325
Lookup the maximal key of the group, and store it into this->record.
9329
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9330
HA_ERR_END_OF_FILE - "" -
9331
other if some error occurred
9334
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9338
/* Get the last key in the (possibly extended) group. */
9339
if (min_max_ranges.elements > 0)
9340
result= next_max_in_range();
9342
result= file->index_read_map(record, group_prefix,
9343
make_prev_keypart_map(real_key_parts),
9344
HA_READ_PREFIX_LAST);
9350
Determine the prefix of the next group.
9353
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9356
Determine the prefix of the next group that satisfies the query conditions.
9357
If there is a range condition referencing the group attributes, use a
9358
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9359
condition. If there is a key infix of constants, append this infix
9360
immediately after the group attributes. The possibly extended prefix is
9361
stored in this->group_prefix. The first key of the found group is stored in
9362
this->record, on which relies this->next_min().
9366
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9367
HA_ERR_END_OF_FILE if there are no more keys
9368
other if some error occurred
9370
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9374
if (quick_prefix_select)
9376
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9377
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9378
make_prev_keypart_map(group_key_parts), cur_prefix)))
9380
seen_first_key= true;
9384
if (!seen_first_key)
9386
result= file->index_first(record);
9389
seen_first_key= true;
9393
/* Load the first key in this group into record. */
9394
result= file->index_read_map(record, group_prefix,
9395
make_prev_keypart_map(group_key_parts),
9402
/* Save the prefix of this group for subsequent calls. */
9403
key_copy(group_prefix, record, index_info, group_prefix_len);
9404
/* Append key_infix to group_prefix. */
9405
if (key_infix_len > 0)
9406
memcpy(group_prefix + group_prefix_len,
9407
key_infix, key_infix_len);
9414
Find the minimal key in a group that satisfies some range conditions for the
9415
min/max argument field.
9418
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9421
Given the sequence of ranges min_max_ranges, find the minimal key that is
9422
in the left-most possible range. If there is no such key, then the current
9423
group does not have a MIN key that satisfies the WHERE clause. If a key is
9424
found, its value is stored in this->record.
9428
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9430
HA_ERR_END_OF_FILE - "" -
9434
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9436
ha_rkey_function find_flag;
9437
key_part_map keypart_map;
9438
QUICK_RANGE *cur_range;
9439
bool found_null= false;
9440
int result= HA_ERR_KEY_NOT_FOUND;
9442
assert(min_max_ranges.elements > 0);
9444
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9445
{ /* Search from the left-most range to the right. */
9446
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9449
If the current value for the min/max argument is bigger than the right
9450
boundary of cur_range, there is no need to check this range.
9452
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9453
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9454
min_max_arg_len) == 1))
9457
if (cur_range->flag & NO_MIN_RANGE)
9459
keypart_map= make_prev_keypart_map(real_key_parts);
9460
find_flag= HA_READ_KEY_EXACT;
9464
/* Extend the search key with the lower boundary for this range. */
9465
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9466
cur_range->min_length);
9467
keypart_map= make_keypart_map(real_key_parts);
9468
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9469
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9470
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9473
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9476
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9477
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9478
continue; /* Check the next range. */
9481
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9482
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9483
range, it can't succeed for any other subsequent range.
9488
/* A key was found. */
9489
if (cur_range->flag & EQ_RANGE)
9490
break; /* No need to perform the checks below for equal keys. */
9492
if (cur_range->flag & NULL_RANGE)
9495
Remember this key, and continue looking for a non-NULL key that
9496
satisfies some other condition.
9498
memcpy(tmp_record, record, head->s->rec_buff_length);
9503
/* Check if record belongs to the current group. */
9504
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9506
result= HA_ERR_KEY_NOT_FOUND;
9510
/* If there is an upper limit, check if the found key is in the range. */
9511
if ( !(cur_range->flag & NO_MAX_RANGE) )
9513
/* Compose the MAX key for the range. */
9514
unsigned char *max_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9515
memcpy(max_key, group_prefix, real_prefix_len);
9516
memcpy(max_key + real_prefix_len, cur_range->max_key,
9517
cur_range->max_length);
9518
/* Compare the found key with max_key. */
9519
int cmp_res= key_cmp(index_info->key_part, max_key,
9520
real_prefix_len + min_max_arg_len);
9521
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9523
result= HA_ERR_KEY_NOT_FOUND;
9527
/* If we got to this point, the current key qualifies as MIN. */
9528
assert(result == 0);
9532
If there was a key with NULL in the MIN/MAX field, and there was no other
9533
key without NULL from the same group that satisfies some other condition,
9534
then use the key with the NULL.
9536
if (found_null && result)
9538
memcpy(record, tmp_record, head->s->rec_buff_length);
9546
Find the maximal key in a group that satisfies some range conditions for the
9547
min/max argument field.
9550
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9553
Given the sequence of ranges min_max_ranges, find the maximal key that is
9554
in the right-most possible range. If there is no such key, then the current
9555
group does not have a MAX key that satisfies the WHERE clause. If a key is
9556
found, its value is stored in this->record.
9560
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9562
HA_ERR_END_OF_FILE - "" -
9566
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9568
ha_rkey_function find_flag;
9569
key_part_map keypart_map;
9570
QUICK_RANGE *cur_range;
9573
assert(min_max_ranges.elements > 0);
9575
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9576
{ /* Search from the right-most range to the left. */
9577
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9580
If the current value for the min/max argument is smaller than the left
9581
boundary of cur_range, there is no need to check this range.
9583
if (range_idx != min_max_ranges.elements &&
9584
!(cur_range->flag & NO_MIN_RANGE) &&
9585
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9586
min_max_arg_len) == -1))
9589
if (cur_range->flag & NO_MAX_RANGE)
9591
keypart_map= make_prev_keypart_map(real_key_parts);
9592
find_flag= HA_READ_PREFIX_LAST;
9596
/* Extend the search key with the upper boundary for this range. */
9597
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9598
cur_range->max_length);
9599
keypart_map= make_keypart_map(real_key_parts);
9600
find_flag= (cur_range->flag & EQ_RANGE) ?
9601
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9602
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9605
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9609
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9610
(cur_range->flag & EQ_RANGE))
9611
continue; /* Check the next range. */
9614
In no key was found with this upper bound, there certainly are no keys
9615
in the ranges to the left.
9619
/* A key was found. */
9620
if (cur_range->flag & EQ_RANGE)
9621
return 0; /* No need to perform the checks below for equal keys. */
9623
/* Check if record belongs to the current group. */
9624
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9625
continue; // Row not found
9627
/* If there is a lower limit, check if the found key is in the range. */
9628
if ( !(cur_range->flag & NO_MIN_RANGE) )
9630
/* Compose the MIN key for the range. */
9631
unsigned char *min_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9632
memcpy(min_key, group_prefix, real_prefix_len);
9633
memcpy(min_key + real_prefix_len, cur_range->min_key,
9634
cur_range->min_length);
9635
/* Compare the found key with min_key. */
9636
int cmp_res= key_cmp(index_info->key_part, min_key,
9637
real_prefix_len + min_max_arg_len);
9638
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9642
/* If we got to this point, the current key qualifies as MAX. */
9645
return HA_ERR_KEY_NOT_FOUND;
9650
Update all MIN function results with the newly found value.
9653
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9656
The method iterates through all MIN functions and updates the result value
9657
of each function by calling Item_sum::reset(), which in turn picks the new
9658
result value from this->head->record[0], previously updated by
9659
next_min(). The updated value is stored in a member variable of each of the
9660
Item_sum objects, depending on the value type.
9663
The update must be done separately for MIN and MAX, immediately after
9664
next_min() was called and before next_max() is called, because both MIN and
9665
MAX take their result value from the same buffer this->head->record[0]
9666
(i.e. this->record).
9672
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9676
min_functions_it->rewind();
9677
while ((min_func= (*min_functions_it)++))
9683
Update all MAX function results with the newly found value.
9686
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9689
The method iterates through all MAX functions and updates the result value
9690
of each function by calling Item_sum::reset(), which in turn picks the new
9691
result value from this->head->record[0], previously updated by
9692
next_max(). The updated value is stored in a member variable of each of the
9693
Item_sum objects, depending on the value type.
9696
The update must be done separately for MIN and MAX, immediately after
9697
next_max() was called, because both MIN and MAX take their result value
9698
from the same buffer this->head->record[0] (i.e. this->record).
9704
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9708
max_functions_it->rewind();
9709
while ((max_func= (*max_functions_it)++))
9715
Append comma-separated list of keys this quick select uses to key_names;
9716
append comma-separated list of corresponding used lengths to used_lengths.
9719
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9720
key_names [out] Names of used indexes
9721
used_lengths [out] Corresponding lengths of the index names
9724
This method is used by select_describe to extract the names of the
9725
indexes used by a quick select.
9729
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9730
String *used_lengths)
9734
key_names->append(index_info->name);
9735
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9736
used_lengths->append(buf, length);
9739
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9740
const char *msg __attribute__((unused)))
9742
SEL_ARG **key,**end;
9746
String tmp(buff,sizeof(buff),&my_charset_bin);
9748
for (idx= 0,key=tree->keys, end=key+param->keys ;
9752
if (tree_map->is_set(idx))
9754
uint32_t keynr= param->real_keynr[idx];
9757
tmp.append(param->table->key_info[keynr].name);
9761
tmp.append(STRING_WITH_LEN("(empty)"));
9767
static void print_ror_scans_arr(Table *table,
9768
const char *msg __attribute__((unused)),
9769
struct st_ror_scan_info **start,
9770
struct st_ror_scan_info **end)
9773
String tmp(buff,sizeof(buff),&my_charset_bin);
9775
for (;start != end; start++)
9779
tmp.append(table->key_info[(*start)->keynr].name);
9782
tmp.append(STRING_WITH_LEN("(empty)"));
9786
/*****************************************************************************
9787
** Instantiate templates
9788
*****************************************************************************/
9790
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9791
template class List<QUICK_RANGE>;
9792
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
