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/sql_base.h"
115
#include "drizzled/sql_select.h"
116
#include "drizzled/error.h"
117
#include "drizzled/optimizer/cost_vector.h"
118
#include "drizzled/item/cmpfunc.h"
119
#include "drizzled/field/num.h"
120
#include "drizzled/check_stack_overrun.h"
121
#include "drizzled/optimizer/sum.h"
122
#include "drizzled/optimizer/range.h"
123
#include "drizzled/optimizer/quick_range.h"
124
#include "drizzled/optimizer/quick_range_select.h"
125
#include "drizzled/optimizer/quick_group_min_max_select.h"
126
#include "drizzled/optimizer/quick_index_merge_select.h"
127
#include "drizzled/optimizer/quick_ror_intersect_select.h"
128
#include "drizzled/optimizer/quick_ror_union_select.h"
129
#include "drizzled/optimizer/table_read_plan.h"
130
#include "drizzled/optimizer/sel_arg.h"
131
#include "drizzled/optimizer/sel_imerge.h"
132
#include "drizzled/optimizer/sel_tree.h"
133
#include "drizzled/optimizer/range_param.h"
134
#include "drizzled/records.h"
135
#include "drizzled/internal/my_sys.h"
136
#include "drizzled/internal/iocache.h"
138
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
144
#define HA_END_SPACE_KEY 0
106
#include <drizzled/server_includes.h>
107
#include <drizzled/sql_select.h>
110
#define test_rb_tree(A,B) {}
111
#define test_use_count(A) {}
147
115
Convert double value to #rows. Currently this does floor(), and we
148
116
might consider using round() instead.
150
static inline ha_rows double2rows(double x)
152
return static_cast<ha_rows>(x);
155
static unsigned char is_null_string[2]= {1,0};
159
Get cost of reading nrows table records in a "disk sweep"
161
A disk sweep read is a sequence of Cursor->rnd_pos(rowid) calls that made
162
for an ordered sequence of rowids.
164
We assume hard disk IO. The read is performed as follows:
166
1. The disk head is moved to the needed cylinder
167
2. The controller waits for the plate to rotate
168
3. The data is transferred
170
Time to do #3 is insignificant compared to #2+#1.
172
Time to move the disk head is proportional to head travel distance.
174
Time to wait for the plate to rotate depends on whether the disk head
177
If disk head wasn't moved, the wait time is proportional to distance
178
between the previous block and the block we're reading.
180
If the head was moved, we don't know how much we'll need to wait for the
181
plate to rotate. We assume the wait time to be a variate with a mean of
182
0.5 of full rotation time.
184
Our cost units are "random disk seeks". The cost of random disk seek is
185
actually not a constant, it depends one range of cylinders we're going
186
to access. We make it constant by introducing a fuzzy concept of "typical
187
datafile length" (it's fuzzy as it's hard to tell whether it should
188
include index cursor, temp.tables etc). Then random seek cost is:
190
1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length
192
We define half_rotation_cost as DISK_SEEK_BASE_COST=0.9.
194
@param table Table to be accessed
195
@param nrows Number of rows to retrieve
196
@param interrupted true <=> Assume that the disk sweep will be
197
interrupted by other disk IO. false - otherwise.
198
@param cost OUT The cost.
201
static void get_sweep_read_cost(Table *table,
204
optimizer::CostVector *cost)
207
if (table->cursor->primary_key_is_clustered())
209
cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
210
static_cast<uint32_t>(nrows),
216
ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);
218
n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));
219
if (busy_blocks < 1.0)
222
cost->setIOCount(busy_blocks);
226
/* Assume reading is done in one 'sweep' */
227
cost->setAvgIOCost((DISK_SEEK_BASE_COST +
228
DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
233
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
236
Item_func::Functype type,
238
Item_result cmp_type);
240
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
244
Item_func::Functype type,
247
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
249
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
251
static ha_rows check_quick_select(Session *session,
252
optimizer::Parameter *param,
255
optimizer::SEL_ARG *tree,
256
bool update_tbl_stats,
259
optimizer::CostVector *cost);
261
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
262
optimizer::Parameter *param,
263
optimizer::SEL_TREE *tree,
264
bool index_read_must_be_used,
265
bool update_tbl_stats,
269
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
270
optimizer::SEL_TREE *tree,
272
bool *are_all_covering);
275
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
276
optimizer::SEL_TREE *tree,
280
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
281
optimizer::Parameter *param,
282
optimizer::SEL_IMERGE *imerge,
286
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
288
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
289
optimizer::SEL_TREE *tree1,
290
optimizer::SEL_TREE *tree2);
292
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
294
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
295
optimizer::SEL_ARG *key1,
296
optimizer::SEL_ARG *key2,
297
uint32_t clone_flag);
299
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
301
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
303
static bool null_part_in_key(KEY_PART *key_part,
304
const unsigned char *key,
307
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
308
optimizer::SEL_TREE *tree2,
309
optimizer::RangeParameter *param);
118
#define double2rows(x) ((ha_rows)(x))
120
static int sel_cmp(Field *f,uchar *a,uchar *b,uint8_t a_flag,uint8_t b_flag);
122
static uchar is_null_string[2]= {1,0};
124
class RANGE_OPT_PARAM;
126
A construction block of the SEL_ARG-graph.
128
The following description only covers graphs of SEL_ARG objects with
129
sel_arg->type==KEY_RANGE:
131
One SEL_ARG object represents an "elementary interval" in form
133
min_value <=? table.keypartX <=? max_value
135
The interval is a non-empty interval of any kind: with[out] minimum/maximum
136
bound, [half]open/closed, single-point interval, etc.
138
1. SEL_ARG GRAPH STRUCTURE
140
SEL_ARG objects are linked together in a graph. The meaning of the graph
141
is better demostrated by an example:
146
| part=1 $ part=2 $ part=3
148
| +-------+ $ +-------+ $ +--------+
149
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
150
| +-------+ $ +-------+ $ +--------+
156
\->| kp1=2 |--$--------------$-+
157
+-------+ $ $ | +--------+
159
+-------+ $ $ | +--------+
160
| kp1=3 |--$--------------$-+ |
161
+-------+ $ $ +--------+
165
The entire graph is partitioned into "interval lists".
167
An interval list is a sequence of ordered disjoint intervals over the same
168
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
169
all intervals in the list form an RB-tree, linked via left/right/parent
170
pointers. The RB-tree root SEL_ARG object will be further called "root of the
173
In the example pic, there are 4 interval lists:
174
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
175
The vertical lines represent SEL_ARG::next/prev pointers.
177
In an interval list, each member X may have SEL_ARG::next_key_part pointer
178
pointing to the root of another interval list Y. The pointed interval list
179
must cover a key part with greater number (i.e. Y->part > X->part).
181
In the example pic, the next_key_part pointers are represented by
184
2. SEL_ARG GRAPH SEMANTICS
186
It represents a condition in a special form (we don't have a name for it ATM)
187
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
189
For example, the picture represents the condition in form:
190
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
191
(kp1=2 AND (kp3=11 OR kp3=14)) OR
192
(kp1=3 AND (kp3=11 OR kp3=14))
197
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
198
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
199
intervals (i.e. intervals in form
201
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
203
Those intervals can be used to access the index. The uses are in:
204
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
205
how many table records are contained within all
207
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
208
and create QUICK_RANGE_SELECT object that will
209
read records within these intervals.
211
4. SPACE COMPLEXITY NOTES
213
SEL_ARG graph is a representation of an ordered disjoint sequence of
214
intervals over the ordered set of index tuple values.
216
For multi-part keys, one can construct a WHERE expression such that its
217
list of intervals will be of combinatorial size. Here is an example:
219
(keypart1 IN (1,2, ..., n1)) AND
220
(keypart2 IN (1,2, ..., n2)) AND
221
(keypart3 IN (1,2, ..., n3))
223
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
226
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
228
SEL_ARG graph structure aims to reduce the amount of required space by
229
"sharing" the elementary intervals when possible (the pic at the
230
beginning of this comment has examples of such sharing). The sharing may
231
prevent combinatorial blowup:
233
There are WHERE clauses that have combinatorial-size interval lists but
234
will be represented by a compact SEL_ARG graph.
236
(keypartN IN (1,2, ..., n1)) AND
238
(keypart2 IN (1,2, ..., n2)) AND
239
(keypart1 IN (1,2, ..., n3))
241
but not in all cases:
243
- There are WHERE clauses that do have a compact SEL_ARG-graph
244
representation but get_mm_tree() and its callees will construct a
245
graph of combinatorial size.
247
(keypart1 IN (1,2, ..., n1)) AND
248
(keypart2 IN (1,2, ..., n2)) AND
250
(keypartN IN (1,2, ..., n3))
252
- There are WHERE clauses for which the minimal possible SEL_ARG graph
253
representation will have combinatorial size.
255
By induction: Let's take any interval on some keypart in the middle:
259
Then let's AND it with this interval 'structure' from preceding and
262
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
264
We will obtain this SEL_ARG graph:
268
+---------+ $ +---------+ $ +---------+
269
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
270
+---------+ $ +---------+ $ +---------+
272
+---------+ $ +---------+ $
273
| kp14=c2 |--$-->| kp15=c0 | $
274
+---------+ $ +---------+ $
277
Note that we had to duplicate "kp15=c0" and there was no way to avoid
279
The induction step: AND the obtained expression with another "wrapping"
281
When the process ends because of the limit on max. number of keyparts
284
WHERE clause length is O(3*#max_keyparts)
285
SEL_ARG graph size is O(2^(#max_keyparts/2))
287
(it is also possible to construct a case where instead of 2 in 2^n we
288
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
291
We avoid consuming too much memory by setting a limit on the number of
292
SEL_ARG object we can construct during one range analysis invocation.
295
class SEL_ARG :public Sql_alloc
298
uint8_t min_flag,max_flag,maybe_flag;
299
uint8_t part; // Which key part
302
Number of children of this element in the RB-tree, plus 1 for this
307
Valid only for elements which are RB-tree roots: Number of times this
308
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
309
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
314
uchar *min_value,*max_value; // Pointer to range
317
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
319
SEL_ARG *left,*right; /* R-B tree children */
320
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
321
SEL_ARG *parent; /* R-B tree parent */
322
SEL_ARG *next_key_part;
323
enum leaf_color { BLACK,RED } color;
324
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
326
enum { MAX_SEL_ARGS = 16000 };
330
SEL_ARG(Field *,const uchar *, const uchar *);
331
SEL_ARG(Field *field, uint8_t part, uchar *min_value, uchar *max_value,
332
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
333
SEL_ARG(enum Type type_arg)
334
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
335
color(BLACK), type(type_arg)
337
inline bool is_same(SEL_ARG *arg)
339
if (type != arg->type || part != arg->part)
341
if (type != KEY_RANGE)
343
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
345
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
346
inline void maybe_smaller() { maybe_flag=1; }
347
/* Return true iff it's a single-point null interval */
348
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
349
inline int cmp_min_to_min(SEL_ARG* arg)
351
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
353
inline int cmp_min_to_max(SEL_ARG* arg)
355
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
357
inline int cmp_max_to_max(SEL_ARG* arg)
359
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
361
inline int cmp_max_to_min(SEL_ARG* arg)
363
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
365
SEL_ARG *clone_and(SEL_ARG* arg)
366
{ // Get overlapping range
367
uchar *new_min,*new_max;
368
uint8_t flag_min,flag_max;
369
if (cmp_min_to_min(arg) >= 0)
371
new_min=min_value; flag_min=min_flag;
375
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
377
if (cmp_max_to_max(arg) <= 0)
379
new_max=max_value; flag_max=max_flag;
383
new_max=arg->max_value; flag_max=arg->max_flag;
385
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
386
test(maybe_flag && arg->maybe_flag));
388
SEL_ARG *clone_first(SEL_ARG *arg)
389
{ // min <= X < arg->min
390
return new SEL_ARG(field,part, min_value, arg->min_value,
391
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
392
maybe_flag | arg->maybe_flag);
394
SEL_ARG *clone_last(SEL_ARG *arg)
395
{ // min <= X <= key_max
396
return new SEL_ARG(field, part, min_value, arg->max_value,
397
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
399
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
401
bool copy_min(SEL_ARG* arg)
402
{ // Get overlapping range
403
if (cmp_min_to_min(arg) > 0)
405
min_value=arg->min_value; min_flag=arg->min_flag;
406
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
407
(NO_MAX_RANGE | NO_MIN_RANGE))
408
return 1; // Full range
410
maybe_flag|=arg->maybe_flag;
413
bool copy_max(SEL_ARG* arg)
414
{ // Get overlapping range
415
if (cmp_max_to_max(arg) <= 0)
417
max_value=arg->max_value; max_flag=arg->max_flag;
418
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
419
(NO_MAX_RANGE | NO_MIN_RANGE))
420
return 1; // Full range
422
maybe_flag|=arg->maybe_flag;
426
void copy_min_to_min(SEL_ARG *arg)
428
min_value=arg->min_value; min_flag=arg->min_flag;
430
void copy_min_to_max(SEL_ARG *arg)
432
max_value=arg->min_value;
433
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
435
void copy_max_to_min(SEL_ARG *arg)
437
min_value=arg->max_value;
438
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
440
/* returns a number of keypart values (0 or 1) appended to the key buffer */
441
int store_min(uint length, uchar **min_key,uint min_key_flag)
443
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
444
if ((!(min_flag & NO_MIN_RANGE) &&
445
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
447
if (maybe_null && *min_value)
450
memset(*min_key+1, 0, length-1);
453
memcpy(*min_key,min_value,length);
459
/* returns a number of keypart values (0 or 1) appended to the key buffer */
460
int store_max(uint length, uchar **max_key, uint max_key_flag)
462
if (!(max_flag & NO_MAX_RANGE) &&
463
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
465
if (maybe_null && *max_value)
468
memset(*max_key+1, 0, length-1);
471
memcpy(*max_key,max_value,length);
478
/* returns a number of keypart values appended to the key buffer */
479
int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
481
SEL_ARG *key_tree= first();
482
uint res= key_tree->store_min(key[key_tree->part].store_length,
483
range_key, *range_key_flag);
484
*range_key_flag|= key_tree->min_flag;
486
if (key_tree->next_key_part &&
487
key_tree->next_key_part->part == key_tree->part+1 &&
488
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
489
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
490
res+= key_tree->next_key_part->store_min_key(key, range_key,
495
/* returns a number of keypart values appended to the key buffer */
496
int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
498
SEL_ARG *key_tree= last();
499
uint res=key_tree->store_max(key[key_tree->part].store_length,
500
range_key, *range_key_flag);
501
(*range_key_flag)|= key_tree->max_flag;
502
if (key_tree->next_key_part &&
503
key_tree->next_key_part->part == key_tree->part+1 &&
504
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
505
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
506
res+= key_tree->next_key_part->store_max_key(key, range_key,
511
SEL_ARG *insert(SEL_ARG *key);
512
SEL_ARG *tree_delete(SEL_ARG *key);
513
SEL_ARG *find_range(SEL_ARG *key);
514
SEL_ARG *rb_insert(SEL_ARG *leaf);
515
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
517
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
518
void test_use_count(SEL_ARG *root);
523
inline bool simple_key()
525
return !next_key_part && elements == 1;
527
void increment_use_count(long count)
531
next_key_part->use_count+=count;
532
count*= (next_key_part->use_count-count);
533
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
534
if (pos->next_key_part)
535
pos->increment_use_count(count);
540
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
541
if (pos->next_key_part)
543
pos->next_key_part->use_count--;
544
pos->next_key_part->free_tree();
548
inline SEL_ARG **parent_ptr()
550
return parent->left == this ? &parent->left : &parent->right;
555
Check if this SEL_ARG object represents a single-point interval
561
Check if this SEL_ARG object (not tree) represents a single-point
562
interval, i.e. if it represents a "keypart = const" or
566
true This SEL_ARG object represents a singlepoint interval
570
bool is_singlepoint()
573
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
574
flags, and the same for right edge.
576
if (min_flag || max_flag)
578
uchar *min_val= min_value;
579
uchar *max_val= max_value;
583
/* First byte is a NULL value indicator */
584
if (*min_val != *max_val)
588
return true; /* This "x IS NULL" */
592
return !field->key_cmp(min_val, max_val);
594
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
600
class SEL_TREE :public Sql_alloc
604
Starting an effort to document this field:
605
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
606
(type == SEL_TREE::IMPOSSIBLE)
608
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
609
SEL_TREE(enum Type type_arg) :type(type_arg) {}
610
SEL_TREE() :type(KEY)
612
keys_map.clear_all();
613
memset(keys, 0, sizeof(keys));
616
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
617
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
618
merit in range analyzer functions (e.g. get_mm_parts) returning a
619
pointer to such SEL_TREE instead of NULL)
621
SEL_ARG *keys[MAX_KEY];
622
key_map keys_map; /* bitmask of non-NULL elements in keys */
625
Possible ways to read rows using index_merge. The list is non-empty only
626
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
628
List<SEL_IMERGE> merges;
630
/* The members below are filled/used only after get_mm_tree is done */
631
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
632
uint n_ror_scans; /* number of set bits in ror_scans_map */
634
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
635
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
636
/* Note that #records for each key scan is stored in table->quick_rows */
639
class RANGE_OPT_PARAM
642
THD *thd; /* Current thread handle */
643
Table *table; /* Table being analyzed */
644
COND *cond; /* Used inside get_mm_tree(). */
645
table_map prev_tables;
646
table_map read_tables;
647
table_map current_table; /* Bit of the table being analyzed */
649
/* Array of parts of all keys for which range analysis is performed */
651
KEY_PART *key_parts_end;
652
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
653
MEM_ROOT *old_root; /* Memory that will last until the query end */
655
Number of indexes used in range analysis (In SEL_TREE::keys only first
656
#keys elements are not empty)
661
If true, the index descriptions describe real indexes (and it is ok to
662
call field->optimize_range(real_keynr[...], ...).
663
Otherwise index description describes fake indexes.
665
bool using_real_indexes;
667
bool remove_jump_scans;
670
used_key_no -> table_key_no translation table. Only makes sense if
671
using_real_indexes==true
673
uint real_keynr[MAX_KEY];
674
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
675
uint alloced_sel_args;
676
bool force_default_mrr;
679
class PARAM : public RANGE_OPT_PARAM
682
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
685
/* Number of ranges in the last checked tree->key */
687
uchar min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
688
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
689
bool quick; // Don't calulate possible keys
691
uint fields_bitmap_size;
692
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
693
MY_BITMAP tmp_covered_fields;
695
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
697
uint *imerge_cost_buff; /* buffer for index_merge cost estimates */
698
uint imerge_cost_buff_size; /* size of the buffer */
700
/* true if last checked tree->key can be used for ROR-scan */
702
/* Number of ranges in the last checked tree->key */
706
class TABLE_READ_PLAN;
708
class TRP_ROR_INTERSECT;
710
class TRP_ROR_INDEX_MERGE;
711
class TRP_GROUP_MIN_MAX;
713
struct st_ror_scan_info;
715
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
716
Item_func::Functype type,Item *value,
717
Item_result cmp_type);
718
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
720
Item_func::Functype type,Item *value);
721
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
723
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8_t nparts);
724
static ha_rows check_quick_select(PARAM *param, uint idx, bool index_only,
725
SEL_ARG *tree, bool update_tbl_stats,
726
uint *mrr_flags, uint *bufsize,
728
//bool update_tbl_stats);
729
/*static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
730
uchar *min_key, uint min_key_flag, int,
731
uchar *max_key, uint max_key_flag, int);
734
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint index,
735
SEL_ARG *key_tree, uint mrr_flags,
736
uint mrr_buf_size, MEM_ROOT *alloc);
737
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
738
bool index_read_must_be_used,
739
bool update_tbl_stats,
742
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
744
bool *are_all_covering);
746
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
750
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
753
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
755
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
757
static void print_ror_scans_arr(Table *table, const char *msg,
758
struct st_ror_scan_info **start,
759
struct st_ror_scan_info **end);
761
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
762
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
763
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
764
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
765
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
767
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
768
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
769
SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
770
uchar *max_key,uint max_key_flag);
771
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
773
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
774
static bool null_part_in_key(KEY_PART *key_part, const uchar *key,
776
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
780
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
781
a condition in the following form:
782
(t_1||t_2||...||t_N) && (next)
784
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
785
(t_i,t_j) contains SEL_ARGS for the same index.
787
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
789
This class relies on memory manager to do the cleanup.
792
class SEL_IMERGE : public Sql_alloc
794
enum { PREALLOCED_TREES= 10};
796
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
797
SEL_TREE **trees; /* trees used to do index_merge */
798
SEL_TREE **trees_next; /* last of these trees */
799
SEL_TREE **trees_end; /* end of allocated space */
801
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
804
trees(&trees_prealloced[0]),
806
trees_end(trees + PREALLOCED_TREES)
808
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
809
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
810
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
815
Add SEL_TREE to this index_merge without any checks,
818
This function implements the following:
819
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
826
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
828
if (trees_next == trees_end)
830
const int realloc_ratio= 2; /* Double size for next round */
831
uint old_elements= (trees_end - trees);
832
uint old_size= sizeof(SEL_TREE**) * old_elements;
833
uint new_size= old_size * realloc_ratio;
834
SEL_TREE **new_trees;
835
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
837
memcpy(new_trees, trees, old_size);
839
trees_next= trees + old_elements;
840
trees_end= trees + old_elements * realloc_ratio;
842
*(trees_next++)= tree;
848
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
849
combining new_tree with one of the trees in this SEL_IMERGE if they both
850
have SEL_ARGs for the same key.
853
or_sel_tree_with_checks()
854
param PARAM from SQL_SELECT::test_quick_select
855
new_tree SEL_TREE with type KEY or KEY_SMALLER.
858
This does the following:
859
(t_1||...||t_k)||new_tree =
861
= (t_1||...||t_k||new_tree)
863
= (t_1||....||(t_j|| new_tree)||...||t_k),
865
where t_i, y are SEL_TREEs.
866
new_tree is combined with the first t_j it has a SEL_ARG on common
867
key with. As a consequence of this, choice of keys to do index_merge
868
read may depend on the order of conditions in WHERE part of the query.
872
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
873
and (*this) should be discarded.
874
-1 An error occurred.
877
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
879
for (SEL_TREE** tree = trees;
883
if (sel_trees_can_be_ored(*tree, new_tree, param))
885
*tree = tree_or(param, *tree, new_tree);
888
if (((*tree)->type == SEL_TREE::MAYBE) ||
889
((*tree)->type == SEL_TREE::ALWAYS))
891
/* SEL_TREE::IMPOSSIBLE is impossible here */
896
/* New tree cannot be combined with any of existing trees. */
897
return or_sel_tree(param, new_tree);
902
Perform OR operation on this index_merge and supplied index_merge list.
906
1 - One of conditions in result is always true and this SEL_IMERGE
908
-1 - An error occurred
911
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
913
for (SEL_TREE** tree= imerge->trees;
914
tree != imerge->trees_next;
917
if (or_sel_tree_with_checks(param, *tree))
317
925
Perform AND operation on two index_merge lists and store result in *im1.
320
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
928
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
322
930
im1->concat(im2);
935
Perform OR operation on 2 index_merge lists, storing result in first list.
938
The following conversion is implemented:
939
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
942
i.e. all conjuncts except the first one are currently dropped.
943
This is done to avoid producing N*K ways to do index_merge.
945
If (a_1||b_1) produce a condition that is always true, NULL is returned
946
and index_merge is discarded (while it is actually possible to try
949
As a consequence of this, choice of keys to do index_merge read may depend
950
on the order of conditions in WHERE part of the query.
953
0 OK, result is stored in *im1
954
other Error, both passed lists are unusable
957
int imerge_list_or_list(RANGE_OPT_PARAM *param,
958
List<SEL_IMERGE> *im1,
959
List<SEL_IMERGE> *im2)
961
SEL_IMERGE *imerge= im1->head();
963
im1->push_back(imerge);
965
return imerge->or_sel_imerge_with_checks(param, im2->head());
970
Perform OR operation on index_merge list and key tree.
973
0 OK, result is stored in *im1.
977
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
978
List<SEL_IMERGE> *im1,
982
List_iterator<SEL_IMERGE> it(*im1);
983
while ((imerge= it++))
985
if (imerge->or_sel_tree_with_checks(param, tree))
988
return im1->is_empty();
326
992
/***************************************************************************
327
** Basic functions for SqlSelect and QuickRangeSelect
993
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
328
994
***************************************************************************/
330
996
/* make a select from mysql info
361
1023
if (head->sort.io_cache)
363
memcpy(select->file, head->sort.io_cache, sizeof(internal::IO_CACHE));
364
select->records=(ha_rows) (select->file->end_of_file/
365
head->cursor->ref_length);
366
delete head->sort.io_cache;
1025
select->file= *head->sort.io_cache;
1026
select->records=(ha_rows) (select->file.end_of_file/
1027
head->file->ref_length);
1028
my_free(head->sort.io_cache, MYF(0));
367
1029
head->sort.io_cache=0;
373
optimizer::SqlSelect::SqlSelect()
377
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1035
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1037
quick_keys.clear_all(); needed_reg.clear_all();
386
void optimizer::SqlSelect::cleanup()
1042
void SQL_SELECT::cleanup()
400
file->close_cached_file();
1052
close_cached_file(&file);
404
optimizer::SqlSelect::~SqlSelect()
1056
SQL_SELECT::~SQL_SELECT()
410
bool optimizer::SqlSelect::check_quick(Session *session,
411
bool force_quick_range,
416
return (test_quick_select(session,
425
bool optimizer::SqlSelect::skip_record()
427
return (cond ? cond->val_int() == 0 : 0);
431
optimizer::QuickSelectInterface::QuickSelectInterface()
433
max_used_key_length(0),
1061
QUICK_SELECT_I::QUICK_SELECT_I()
1062
:max_used_key_length(0),
1066
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, Table *table, uint key_nr,
1067
bool no_alloc, MEM_ROOT *parent_alloc,
1069
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1071
my_bitmap_map *bitmap;
1073
in_ror_merged_scan= 0;
1077
key_part_info= head->key_info[index].key_part;
1078
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1080
/* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1081
mrr_buf_size= thd->variables.read_rnd_buff_size;
1084
if (!no_alloc && !parent_alloc)
1086
// Allocates everything through the internal memroot
1087
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1088
thd->mem_root= &alloc;
1091
memset(&alloc, 0, sizeof(alloc));
1093
record= head->record[0];
1094
save_read_set= head->read_set;
1095
save_write_set= head->write_set;
1097
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1098
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1101
column_bitmap.bitmap= 0;
1105
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1110
int QUICK_RANGE_SELECT::init()
1112
if (file->inited != handler::NONE)
1113
file->ha_index_or_rnd_end();
1114
return(file->ha_index_init(index, 1));
1118
void QUICK_RANGE_SELECT::range_end()
1120
if (file->inited != handler::NONE)
1121
file->ha_index_or_rnd_end();
1125
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1129
/* file is NULL for CPK scan on covering ROR-intersection */
1136
file->extra(HA_EXTRA_NO_KEYREAD);
1140
file->ha_external_lock(current_thd, F_UNLCK);
1145
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1146
free_root(&alloc,MYF(0));
1147
my_free((char*) column_bitmap.bitmap, MYF(MY_ALLOW_ZERO_PTR));
1149
head->column_bitmaps_set(save_read_set, save_write_set);
1150
x_free(mrr_buf_desc);
1155
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1157
:pk_quick_select(NULL), thd(thd_param)
1161
memset(&read_record, 0, sizeof(read_record));
1162
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1166
int QUICK_INDEX_MERGE_SELECT::init()
1171
int QUICK_INDEX_MERGE_SELECT::reset()
1173
return(read_keys_and_merge());
1177
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1180
Save quick_select that does scan on clustered primary key as it will be
1181
processed separately.
1183
if (head->file->primary_key_is_clustered() &&
1184
quick_sel_range->index == head->s->primary_key)
1185
pk_quick_select= quick_sel_range;
1187
return quick_selects.push_back(quick_sel_range);
1191
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1193
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1194
QUICK_RANGE_SELECT* quick;
1196
while ((quick= quick_it++))
1198
quick_selects.delete_elements();
1199
delete pk_quick_select;
1200
free_root(&alloc,MYF(0));
1205
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1207
bool retrieve_full_rows,
1208
MEM_ROOT *parent_alloc)
1209
: cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
1214
record= head->record[0];
1216
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1218
memset(&alloc, 0, sizeof(MEM_ROOT));
1219
last_rowid= (uchar*) alloc_root(parent_alloc? parent_alloc : &alloc,
1220
head->file->ref_length);
1225
Do post-constructor initialization.
1227
QUICK_ROR_INTERSECT_SELECT::init()
1234
int QUICK_ROR_INTERSECT_SELECT::init()
1236
/* Check if last_rowid was successfully allocated in ctor */
1237
return(!last_rowid);
1242
Initialize this quick select to be a ROR-merged scan.
1245
QUICK_RANGE_SELECT::init_ror_merged_scan()
1246
reuse_handler If true, use head->file, otherwise create a separate
1250
This function creates and prepares for subsequent use a separate handler
1251
object if it can't reuse head->file. The reason for this is that during
1252
ROR-merge several key scans are performed simultaneously, and a single
1253
handler is only capable of preserving context of a single key scan.
1255
In ROR-merge the quick select doing merge does full records retrieval,
1256
merged quick selects read only keys.
1259
0 ROR child scan initialized, ok to use.
1263
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1265
handler *save_file= file, *org_file;
1268
in_ror_merged_scan= 1;
1271
if (init() || reset())
1275
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1279
/* Create a separate handler object for this quick select */
1282
/* already have own 'handler' object. */
1287
if (!(file= head->file->clone(thd->mem_root)))
1290
Manually set the error flag. Note: there seems to be quite a few
1291
places where a failure could cause the server to "hang" the client by
1292
sending no response to a query. ATM those are not real errors because
1293
the storage engine calls in question happen to never fail with the
1294
existing storage engines.
1296
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1297
/* Caller will free the memory */
1298
goto failure; /* purecov: inspected */
1301
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1303
if (file->ha_external_lock(thd, F_RDLCK))
1306
if (init() || reset())
1308
file->ha_external_lock(thd, F_UNLCK);
1313
last_rowid= file->ref;
1317
We are only going to read key fields and call position() on 'file'
1318
The following sets head->tmp_set to only use this key and then updates
1319
head->read_set and head->write_set to use this bitmap.
1320
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1322
org_file= head->file;
1324
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1325
if (!head->no_keyread)
1328
head->mark_columns_used_by_index(index);
1330
head->prepare_for_position();
1331
head->file= org_file;
1332
bitmap_copy(&column_bitmap, head->read_set);
1333
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1338
head->column_bitmaps_set(save_read_set, save_write_set);
1346
Initialize this quick select to be a part of a ROR-merged scan.
1348
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1349
reuse_handler If true, use head->file, otherwise create separate
1355
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1357
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1358
QUICK_RANGE_SELECT* quick;
1360
/* Initialize all merged "children" quick selects */
1361
assert(!need_to_fetch_row || reuse_handler);
1362
if (!need_to_fetch_row && reuse_handler)
1366
There is no use of this->file. Use it for the first of merged range
1369
if (quick->init_ror_merged_scan(true))
1371
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1373
while ((quick= quick_it++))
1375
if (quick->init_ror_merged_scan(false))
1377
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1378
/* All merged scans share the same record buffer in intersection. */
1379
quick->record= head->record[0];
1382
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1391
Initialize quick select for row retrieval.
1399
int QUICK_ROR_INTERSECT_SELECT::reset()
1401
if (!scans_inited && init_ror_merged_scan(true))
1404
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1405
QUICK_RANGE_SELECT *quick;
1406
while ((quick= it++))
1413
Add a merged quick select to this ROR-intersection quick select.
1416
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1417
quick Quick select to be added. The quick select must return
1418
rows in rowid order.
1420
This call can only be made before init() is called.
1428
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1430
return quick_selects.push_back(quick);
1433
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1435
quick_selects.delete_elements();
1437
free_root(&alloc,MYF(0));
1438
if (need_to_fetch_row && head->file->inited != handler::NONE)
1439
head->file->ha_rnd_end();
1444
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1446
: thd(thd_param), scans_inited(false)
1450
rowid_length= table->file->ref_length;
1451
record= head->record[0];
1452
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1453
thd_param->mem_root= &alloc;
1458
Do post-constructor initialization.
1460
QUICK_ROR_UNION_SELECT::init()
1467
int QUICK_ROR_UNION_SELECT::init()
1469
if (init_queue(&queue, quick_selects.elements, 0,
1470
false , QUICK_ROR_UNION_SELECT::queue_cmp,
1473
memset(&queue, 0, sizeof(QUEUE));
1477
if (!(cur_rowid= (uchar*) alloc_root(&alloc, 2*head->file->ref_length)))
1479
prev_rowid= cur_rowid + head->file->ref_length;
1485
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1489
QUICK_ROR_UNION_SELECT::queue_cmp()
1490
arg Pointer to QUICK_ROR_UNION_SELECT
1491
val1 First merged select
1492
val2 Second merged select
1495
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, uchar *val1, uchar *val2)
1497
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1498
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1499
((QUICK_SELECT_I*)val2)->last_rowid);
1504
Initialize quick select for row retrieval.
1513
int QUICK_ROR_UNION_SELECT::reset()
1515
QUICK_SELECT_I *quick;
1517
have_prev_rowid= false;
1520
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1521
while ((quick= it++))
1523
if (quick->init_ror_merged_scan(false))
1528
queue_remove_all(&queue);
1530
Initialize scans for merged quick selects and put all merged quick
1531
selects into the queue.
1533
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1534
while ((quick= it++))
1538
if ((error= quick->get_next()))
1540
if (error == HA_ERR_END_OF_FILE)
1544
quick->save_last_pos();
1545
queue_insert(&queue, (uchar*)quick);
1548
if (head->file->ha_rnd_init(1))
1558
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1560
return quick_selects.push_back(quick_sel_range);
1563
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1565
delete_queue(&queue);
1566
quick_selects.delete_elements();
1567
if (head->file->inited != handler::NONE)
1568
head->file->ha_rnd_end();
1569
free_root(&alloc,MYF(0));
1574
QUICK_RANGE::QUICK_RANGE()
1575
:min_key(0),max_key(0),min_length(0),max_length(0),
1576
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1577
min_keypart_map(0), max_keypart_map(0)
1580
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1583
min_flag=arg.min_flag;
1584
max_flag=arg.max_flag;
1585
maybe_flag=arg.maybe_flag;
1586
maybe_null=arg.maybe_null;
1589
min_value=arg.min_value;
1590
max_value=arg.max_value;
1591
next_key_part=arg.next_key_part;
1592
use_count=1; elements=1;
1596
inline void SEL_ARG::make_root()
1598
left=right= &null_element;
1601
use_count=0; elements=1;
1604
SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg,
1605
const uchar *max_value_arg)
1606
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1607
elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
1608
max_value((uchar*) max_value_arg), next(0),prev(0),
1609
next_key_part(0),color(BLACK),type(KEY_RANGE)
1611
left=right= &null_element;
1614
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1615
uchar *min_value_, uchar *max_value_,
1616
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1617
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1618
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1619
field(field_), min_value(min_value_), max_value(max_value_),
1620
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1622
left=right= &null_element;
1625
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1630
/* Bail out if we have already generated too many SEL_ARGs */
1631
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1634
if (type != KEY_RANGE)
1636
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1637
return 0; // out of memory
1638
tmp->prev= *next_arg; // Link into next/prev chain
1639
(*next_arg)->next=tmp;
1644
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1645
min_flag, max_flag, maybe_flag)))
1647
tmp->parent=new_parent;
1648
tmp->next_key_part=next_key_part;
1649
if (left != &null_element)
1650
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1653
tmp->prev= *next_arg; // Link into next/prev chain
1654
(*next_arg)->next=tmp;
1657
if (right != &null_element)
1658
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1661
increment_use_count(1);
1663
tmp->elements= this->elements;
1667
SEL_ARG *SEL_ARG::first()
1669
SEL_ARG *next_arg=this;
1670
if (!next_arg->left)
1671
return 0; // MAYBE_KEY
1672
while (next_arg->left != &null_element)
1673
next_arg=next_arg->left;
1677
SEL_ARG *SEL_ARG::last()
1679
SEL_ARG *next_arg=this;
1680
if (!next_arg->right)
1681
return 0; // MAYBE_KEY
1682
while (next_arg->right != &null_element)
1683
next_arg=next_arg->right;
1689
Check if a compare is ok, when one takes ranges in account
1690
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1693
static int sel_cmp(Field *field, uchar *a, uchar *b, uint8_t a_flag,
1697
/* First check if there was a compare to a min or max element */
1698
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1700
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1701
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1703
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1705
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1706
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1708
if (field->real_maybe_null()) // If null is part of key
1715
goto end; // NULL where equal
1716
a++; b++; // Skip NULL marker
1718
cmp=field->key_cmp(a , b);
1719
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1721
// Check if the compared equal arguments was defined with open/closed range
1723
if (a_flag & (NEAR_MIN | NEAR_MAX))
1725
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1727
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1728
return (a_flag & NEAR_MIN) ? 2 : -2;
1729
return (a_flag & NEAR_MIN) ? 1 : -1;
1731
if (b_flag & (NEAR_MIN | NEAR_MAX))
1732
return (b_flag & NEAR_MIN) ? -2 : 2;
1733
return 0; // The elements where equal
1737
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1739
SEL_ARG tmp_link,*next_arg,*root;
1740
next_arg= &tmp_link;
1741
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1743
next_arg->next=0; // Fix last link
1744
tmp_link.next->prev=0; // Fix first link
1745
if (root) // If not OOM
5114
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5134
if (key1->part != key2->part)
5138
return 0; // Can't optimize this
5141
// If one of the key is MAYBE_KEY then the found region may be bigger
5142
if (key1->type == SEL_ARG::MAYBE_KEY)
5148
if (key2->type == SEL_ARG::MAYBE_KEY)
5155
if (key1->use_count > 0)
5157
if (key2->use_count == 0 || key1->elements > key2->elements)
5159
std::swap(key1,key2);
5161
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5165
// Add tree at key2 to tree at key1
5166
bool key2_shared=key2->use_count != 0;
5167
key1->maybe_flag|=key2->maybe_flag;
5169
for (key2=key2->first(); key2; )
5171
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5176
tmp=key1->first(); // tmp.min > key2.min
5179
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5180
{ // Found tmp.max < key2.min
5181
SEL_ARG *next=tmp->next;
5182
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5184
// Join near ranges like tmp.max < 0 and key2.min >= 0
5185
SEL_ARG *key2_next=key2->next;
5188
if (!(key2=new SEL_ARG(*key2)))
5189
return 0; // out of memory
5190
key2->increment_use_count(key1->use_count+1);
5191
key2->next=key2_next; // New copy of key2
5193
key2->copy_min(tmp);
5194
if (!(key1=key1->tree_delete(tmp)))
5195
{ // Only one key in tree
5202
if (!(tmp=next)) // tmp.min > key2.min
5203
break; // Copy rest of key2
5206
{ // tmp.min > key2.min
5208
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5210
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5211
{ // ranges are connected
5212
tmp->copy_min_to_min(key2);
5213
key1->merge_flags(key2);
5214
if (tmp->min_flag & NO_MIN_RANGE &&
5215
tmp->max_flag & NO_MAX_RANGE)
5217
if (key1->maybe_flag)
5218
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5221
key2->increment_use_count(-1); // Free not used tree
5227
SEL_ARG *next=key2->next; // Keys are not overlapping
5230
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5233
key1=key1->insert(cpy);
5234
key2->increment_use_count(key1->use_count+1);
5237
key1=key1->insert(key2); // Will destroy key2_root
5244
// tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges)
5245
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5247
if (tmp->is_same(key2))
5249
tmp->merge_flags(key2); // Copy maybe flags
5250
key2->increment_use_count(-1); // Free not used tree
5255
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5256
eq_tree(last->next->next_key_part,key2->next_key_part))
5260
key1=key1->tree_delete(save);
5262
last->copy_min(tmp);
5263
if (last->copy_min(key2) || last->copy_max(key2))
5266
for (; key2 ; key2=key2->next)
5267
key2->increment_use_count(-1); // Free not used tree
5268
if (key1->maybe_flag)
5269
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5277
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5278
{ // tmp.min <= x < key2.min
5279
SEL_ARG *new_arg=tmp->clone_first(key2);
5282
if ((new_arg->next_key_part= key1->next_key_part))
5283
new_arg->increment_use_count(key1->use_count+1);
5284
tmp->copy_min_to_min(key2);
5285
key1=key1->insert(new_arg);
5288
// tmp.min >= key2.min && tmp.min <= key2.max
5289
SEL_ARG key(*key2); // Get copy we can modify
5292
if (tmp->cmp_min_to_min(&key) > 0)
5293
{ // key.min <= x < tmp.min
5294
SEL_ARG *new_arg=key.clone_first(tmp);
5297
if ((new_arg->next_key_part=key.next_key_part))
5298
new_arg->increment_use_count(key1->use_count+1);
5299
key1=key1->insert(new_arg);
5301
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5302
{ // tmp.min. <= x <= tmp.max
5303
tmp->maybe_flag|= key.maybe_flag;
5304
key.increment_use_count(key1->use_count+1);
5305
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5306
if (!cmp) // Key2 is ready
5308
key.copy_max_to_min(tmp);
5309
if (!(tmp=tmp->next))
5311
SEL_ARG *tmp2= new SEL_ARG(key);
5314
key1=key1->insert(tmp2);
5318
if (tmp->cmp_min_to_max(&key) > 0)
5320
SEL_ARG *tmp2= new SEL_ARG(key);
5323
key1=key1->insert(tmp2);
5329
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5332
tmp->copy_max_to_min(&key);
5333
tmp->increment_use_count(key1->use_count+1);
5334
/* Increment key count as it may be used for next loop */
5335
key.increment_use_count(1);
5336
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5337
key1=key1->insert(new_arg);
5347
SEL_ARG *next=key2->next;
5350
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5353
key2->increment_use_count(key1->use_count+1);
5354
key1=key1->insert(tmp);
5357
key1=key1->insert(key2); // Will destroy key2_root
5365
/* Compare if two trees are equal */
5367
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5371
if (!a || !b || !a->is_same(b))
5373
if (a->left != &null_element && b->left != &null_element)
5375
if (!eq_tree(a->left,b->left))
5378
else if (a->left != &null_element || b->left != &null_element)
5380
if (a->right != &null_element && b->right != &null_element)
5382
if (!eq_tree(a->right,b->right))
5385
else if (a->right != &null_element || b->right != &null_element)
5387
if (a->next_key_part != b->next_key_part)
5389
if (!a->next_key_part != !b->next_key_part ||
5390
!eq_tree(a->next_key_part, b->next_key_part))
5398
SEL_ARG::insert(SEL_ARG *key)
5400
SEL_ARG *element, **par= NULL, *last_element= NULL;
5402
for (element= this; element != &null_element ; )
5404
last_element=element;
5405
if (key->cmp_min_to_min(element) > 0)
5407
par= &element->right; element= element->right;
5411
par = &element->left; element= element->left;
5415
key->parent=last_element;
5417
if (par == &last_element->left)
5419
key->next=last_element;
5420
if ((key->prev=last_element->prev))
5421
key->prev->next=key;
5422
last_element->prev=key;
5426
if ((key->next=last_element->next))
5427
key->next->prev=key;
5428
key->prev=last_element;
5429
last_element->next=key;
5431
key->left=key->right= &null_element;
5432
SEL_ARG *root=rb_insert(key); // rebalance tree
5433
root->use_count=this->use_count; // copy root info
5434
root->elements= this->elements+1;
5435
root->maybe_flag=this->maybe_flag;
5441
** Find best key with min <= given key
5442
** Because the call context this should never return 0 to get_range
5446
SEL_ARG::find_range(SEL_ARG *key)
5448
SEL_ARG *element=this,*found=0;
5452
if (element == &null_element)
5454
int cmp=element->cmp_min_to_min(key);
5460
element=element->right;
5463
element=element->left;
5469
Remove a element from the tree
5473
key Key that is to be deleted from tree (this)
5476
This also frees all sub trees that is used by the element
5479
root of new tree (with key deleted)
5483
SEL_ARG::tree_delete(SEL_ARG *key)
5485
enum leaf_color remove_color;
5486
SEL_ARG *root,*nod,**par,*fix_par;
5491
/* Unlink from list */
5493
key->prev->next=key->next;
5495
key->next->prev=key->prev;
5496
key->increment_use_count(-1);
5500
par=key->parent_ptr();
5502
if (key->left == &null_element)
5504
*par=nod=key->right;
5505
fix_par=key->parent;
5506
if (nod != &null_element)
5507
nod->parent=fix_par;
5508
remove_color= key->color;
5510
else if (key->right == &null_element)
5512
*par= nod=key->left;
5513
nod->parent=fix_par=key->parent;
5514
remove_color= key->color;
5518
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5519
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5520
fix_par=tmp->parent;
5521
if (nod != &null_element)
5522
nod->parent=fix_par;
5523
remove_color= tmp->color;
5525
tmp->parent=key->parent; // Move node in place of key
5526
(tmp->left=key->left)->parent=tmp;
5527
if ((tmp->right=key->right) != &null_element)
5528
tmp->right->parent=tmp;
5529
tmp->color=key->color;
5531
if (fix_par == key) // key->right == key->next
5532
fix_par=tmp; // new parent of nod
5535
if (root == &null_element)
5536
return(0); // Maybe root later
5537
if (remove_color == BLACK)
5538
root=rb_delete_fixup(root,nod,fix_par);
5539
test_rb_tree(root,root->parent);
5541
root->use_count=this->use_count; // Fix root counters
5542
root->elements=this->elements-1;
5543
root->maybe_flag=this->maybe_flag;
5548
/* Functions to fix up the tree after insert and delete */
5550
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5552
SEL_ARG *y=leaf->right;
5553
leaf->right=y->left;
5554
if (y->left != &null_element)
5555
y->left->parent=leaf;
5556
if (!(y->parent=leaf->parent))
5559
*leaf->parent_ptr()=y;
5564
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5566
SEL_ARG *y=leaf->left;
5567
leaf->left=y->right;
5568
if (y->right != &null_element)
5569
y->right->parent=leaf;
5570
if (!(y->parent=leaf->parent))
5573
*leaf->parent_ptr()=y;
5580
SEL_ARG::rb_insert(SEL_ARG *leaf)
5582
SEL_ARG *y,*par,*par2,*root;
5583
root= this; root->parent= 0;
5586
while (leaf != root && (par= leaf->parent)->color == RED)
5587
{ // This can't be root or 1 level under
5588
if (par == (par2= leaf->parent->parent)->left)
5591
if (y->color == RED)
5596
leaf->color=RED; /* And the loop continues */
5600
if (leaf == par->right)
5602
left_rotate(&root,leaf->parent);
5603
par=leaf; /* leaf is now parent to old leaf */
5607
right_rotate(&root,par2);
5614
if (y->color == RED)
5619
leaf->color=RED; /* And the loop continues */
5623
if (leaf == par->left)
5625
right_rotate(&root,par);
5630
left_rotate(&root,par2);
5636
test_rb_tree(root,root->parent);
5641
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5647
while (x != root && x->color == SEL_ARG::BLACK)
5652
if (w->color == SEL_ARG::RED)
5654
w->color=SEL_ARG::BLACK;
5655
par->color=SEL_ARG::RED;
5656
left_rotate(&root,par);
5659
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5661
w->color=SEL_ARG::RED;
5666
if (w->right->color == SEL_ARG::BLACK)
5668
w->left->color=SEL_ARG::BLACK;
5669
w->color=SEL_ARG::RED;
5670
right_rotate(&root,w);
5673
w->color=par->color;
5674
par->color=SEL_ARG::BLACK;
5675
w->right->color=SEL_ARG::BLACK;
5676
left_rotate(&root,par);
5684
if (w->color == SEL_ARG::RED)
5686
w->color=SEL_ARG::BLACK;
5687
par->color=SEL_ARG::RED;
5688
right_rotate(&root,par);
5691
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5693
w->color=SEL_ARG::RED;
5698
if (w->left->color == SEL_ARG::BLACK)
5700
w->right->color=SEL_ARG::BLACK;
5701
w->color=SEL_ARG::RED;
5702
left_rotate(&root,w);
5705
w->color=par->color;
5706
par->color=SEL_ARG::BLACK;
5707
w->left->color=SEL_ARG::BLACK;
5708
right_rotate(&root,par);
5715
x->color=SEL_ARG::BLACK;
5720
/* Test that the properties for a red-black tree hold */
5723
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5725
int count_l,count_r;
5727
if (element == &null_element)
5728
return 0; // Found end of tree
5729
if (element->parent != parent)
5731
sql_print_error("Wrong tree: Parent doesn't point at parent");
5734
if (element->color == SEL_ARG::RED &&
5735
(element->left->color == SEL_ARG::RED ||
5736
element->right->color == SEL_ARG::RED))
5738
sql_print_error("Wrong tree: Found two red in a row");
5741
if (element->left == element->right && element->left != &null_element)
5743
sql_print_error("Wrong tree: Found right == left");
5746
count_l=test_rb_tree(element->left,element);
5747
count_r=test_rb_tree(element->right,element);
5748
if (count_l >= 0 && count_r >= 0)
5750
if (count_l == count_r)
5751
return count_l+(element->color == SEL_ARG::BLACK);
5752
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5755
return -1; // Error, no more warnings
5760
Count how many times SEL_ARG graph "root" refers to its part "key"
5763
count_key_part_usage()
5764
root An RB-Root node in a SEL_ARG graph.
5765
key Another RB-Root node in that SEL_ARG graph.
5768
The passed "root" node may refer to "key" node via root->next_key_part,
5771
This function counts how many times the node "key" is referred (via
5772
SEL_ARG::next_key_part) by
5773
- intervals of RB-tree pointed by "root",
5774
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5775
intervals of RB-tree pointed by "root",
5778
Here is an example (horizontal links represent next_key_part pointers,
5779
vertical links - next/prev prev pointers):
5782
|root|-----------------+
5786
+----+ +---+ $ | +---+ Here the return value
5787
| |- ... -| |---$-+--+->|key| will be 4.
5788
+----+ +---+ $ | | +---+
5793
| |---| |---------+ |
5800
Number of links to "key" from nodes reachable from "root".
5803
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5806
for (root=root->first(); root ; root=root->next)
5808
if (root->next_key_part)
5810
if (root->next_key_part == key)
5812
if (root->next_key_part->part < key->part)
5813
count+=count_key_part_usage(root->next_key_part,key);
5821
Check if SEL_ARG::use_count value is correct
5824
SEL_ARG::test_use_count()
5825
root The root node of the SEL_ARG graph (an RB-tree root node that
5826
has the least value of sel_arg->part in the entire graph, and
5827
thus is the "origin" of the graph)
5830
Check if SEL_ARG::use_count value is correct. See the definition of
5831
use_count for what is "correct".
5834
void SEL_ARG::test_use_count(SEL_ARG *root)
5837
if (this == root && use_count != 1)
5839
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5842
if (this->type != SEL_ARG::KEY_RANGE)
5844
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5847
if (pos->next_key_part)
5849
ulong count=count_key_part_usage(root,pos->next_key_part);
5850
if (count > pos->next_key_part->use_count)
5852
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5853
"should be %lu", (long unsigned int)pos,
5854
pos->next_key_part->use_count, count);
5857
pos->next_key_part->test_use_count(root);
5860
if (e_count != elements)
5861
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5862
e_count, elements, (long unsigned int) this);
3519
5867
/****************************************************************************
3520
5868
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3521
5869
****************************************************************************/
3523
5871
/* MRR range sequence, SEL_ARG* implementation: stack entry */
3524
typedef struct st_range_seq_entry
5872
typedef struct st_range_seq_entry
3527
5875
Pointers in min and max keys. They point to right-after-end of key
3528
5876
images. The 0-th entry has these pointing to key tuple start.
3530
unsigned char *min_key, *max_key;
5878
uchar *min_key, *max_key;
3533
5881
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3534
5882
min_key_flag may have NULL_RANGE set.
3536
uint32_t min_key_flag, max_key_flag;
5884
uint min_key_flag, max_key_flag;
3538
5886
/* Number of key parts */
3539
uint32_t min_key_parts, max_key_parts;
3540
optimizer::SEL_ARG *key_tree;
5887
uint min_key_parts, max_key_parts;
3541
5889
} RANGE_SEQ_ENTRY;
4335
Range sequence interface implementation for array<QuickRange>: initialize
6697
Perform key scans for all used indexes (except CPK), get rowids and merge
6698
them into an ordered non-recurrent sequence of rowids.
6700
The merge/duplicate removal is performed using Unique class. We put all
6701
rowids into Unique, get the sorted sequence and destroy the Unique.
6703
If table has a clustered primary key that covers all rows (true for bdb
6704
and innodb currently) and one of the index_merge scans is a scan on PK,
6705
then rows that will be retrieved by PK scan are not put into Unique and
6706
primary key scan is not performed here, it is performed later separately.
6713
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6715
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6716
QUICK_RANGE_SELECT* cur_quick;
6719
handler *file= head->file;
6721
file->extra(HA_EXTRA_KEYREAD);
6722
head->prepare_for_position();
6724
cur_quick_it.rewind();
6725
cur_quick= cur_quick_it++;
6726
assert(cur_quick != 0);
6729
We reuse the same instance of handler so we need to call both init and
6732
if (cur_quick->init() || cur_quick->reset())
6735
unique= new Unique(refpos_order_cmp, (void *)file,
6737
thd->variables.sortbuff_size);
6742
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6744
cur_quick->range_end();
6745
cur_quick= cur_quick_it++;
6749
if (cur_quick->file->inited != handler::NONE)
6750
cur_quick->file->ha_index_end();
6751
if (cur_quick->init() || cur_quick->reset())
6757
if (result != HA_ERR_END_OF_FILE)
6759
cur_quick->range_end();
6768
/* skip row if it will be retrieved by clustered PK scan */
6769
if (pk_quick_select && pk_quick_select->row_in_ranges())
6772
cur_quick->file->position(cur_quick->record);
6773
result= unique->unique_add((char*)cur_quick->file->ref);
6779
/* ok, all row ids are in Unique */
6780
result= unique->get(head);
6782
doing_pk_scan= false;
6783
/* index_merge currently doesn't support "using index" at all */
6784
file->extra(HA_EXTRA_NO_KEYREAD);
6785
/* start table scan */
6786
init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6792
Get next row for index_merge.
6794
The rows are read from
6795
1. rowids stored in Unique.
6796
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6797
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6800
int QUICK_INDEX_MERGE_SELECT::get_next()
6805
return(pk_quick_select->get_next());
6807
if ((result= read_record.read_record(&read_record)) == -1)
6809
result= HA_ERR_END_OF_FILE;
6810
end_read_record(&read_record);
6811
/* All rows from Unique have been retrieved, do a clustered PK scan */
6812
if (pk_quick_select)
6814
doing_pk_scan= true;
6815
if ((result= pk_quick_select->init()) ||
6816
(result= pk_quick_select->reset()))
6818
return(pk_quick_select->get_next());
6827
Retrieve next record.
6829
QUICK_ROR_INTERSECT_SELECT::get_next()
6832
Invariant on enter/exit: all intersected selects have retrieved all index
6833
records with rowid <= some_rowid_val and no intersected select has
6834
retrieved any index records with rowid > some_rowid_val.
6835
We start fresh and loop until we have retrieved the same rowid in each of
6836
the key scans or we got an error.
6838
If a Clustered PK scan is present, it is used only to check if row
6839
satisfies its condition (and never used for row retrieval).
6843
other - Error code if any error occurred.
6846
int QUICK_ROR_INTERSECT_SELECT::get_next()
6848
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6849
QUICK_RANGE_SELECT* quick;
6851
uint last_rowid_count=0;
6855
/* Get a rowid for first quick and save it as a 'candidate' */
6857
error= quick->get_next();
6860
while (!error && !cpk_quick->row_in_ranges())
6861
error= quick->get_next();
6866
quick->file->position(quick->record);
6867
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6868
last_rowid_count= 1;
6870
while (last_rowid_count < quick_selects.elements)
6872
if (!(quick= quick_it++))
6880
if ((error= quick->get_next()))
6882
quick->file->position(quick->record);
6883
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6886
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6889
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6892
while (!cpk_quick->row_in_ranges())
6894
if ((error= quick->get_next()))
6898
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6899
last_rowid_count= 1;
6903
/* current 'candidate' row confirmed by this select */
6908
/* We get here if we got the same row ref in all scans. */
6909
if (need_to_fetch_row)
6910
error= head->file->rnd_pos(head->record[0], last_rowid);
6911
} while (error == HA_ERR_RECORD_DELETED);
6917
Retrieve next record.
6919
QUICK_ROR_UNION_SELECT::get_next()
6922
Enter/exit invariant:
6923
For each quick select in the queue a {key,rowid} tuple has been
6924
retrieved but the corresponding row hasn't been passed to output.
6928
other - Error code if any error occurred.
6931
int QUICK_ROR_UNION_SELECT::get_next()
6934
QUICK_SELECT_I *quick;
6941
if (!queue.elements)
6942
return(HA_ERR_END_OF_FILE);
6943
/* Ok, we have a queue with >= 1 scans */
6945
quick= (QUICK_SELECT_I*)queue_top(&queue);
6946
memcpy(cur_rowid, quick->last_rowid, rowid_length);
6948
/* put into queue rowid from the same stream as top element */
6949
if ((error= quick->get_next()))
6951
if (error != HA_ERR_END_OF_FILE)
6953
queue_remove(&queue, 0);
6957
quick->save_last_pos();
6958
queue_replaced(&queue);
6961
if (!have_prev_rowid)
6963
/* No rows have been returned yet */
6965
have_prev_rowid= true;
6968
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
6972
cur_rowid= prev_rowid;
6975
error= head->file->rnd_pos(quick->record, prev_rowid);
6976
} while (error == HA_ERR_RECORD_DELETED);
6981
int QUICK_RANGE_SELECT::reset()
6986
HANDLER_BUFFER empty_buf;
6988
cur_range= (QUICK_RANGE**) ranges.buffer;
6990
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6993
/* Allocate buffer if we need one but haven't allocated it yet */
6994
if (mrr_buf_size && !mrr_buf_desc)
6996
buf_size= mrr_buf_size;
6997
while (buf_size && !my_multi_malloc(MYF(MY_WME),
6998
&mrr_buf_desc, sizeof(*mrr_buf_desc),
6999
&mrange_buff, buf_size,
7002
/* Try to shrink the buffers until both are 0. */
7006
return(HA_ERR_OUT_OF_MEM);
7008
/* Initialize the handler buffer. */
7009
mrr_buf_desc->buffer= mrange_buff;
7010
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7011
mrr_buf_desc->end_of_used_area= mrange_buff;
7015
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7018
mrr_flags |= HA_MRR_SORTED;
7019
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7020
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7021
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7028
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4338
7031
quick_range_seq_init()
4339
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7032
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4340
7033
n_ranges Number of ranges in the sequence (ignored)
4341
flags MRR flags (currently not used)
7034
flags MRR flags (currently not used)
4344
7037
Opaque value to be passed to quick_range_seq_next
4347
range_seq_t optimizer::quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7040
range_seq_t quick_range_seq_init(void *init_param,
7041
uint n_ranges __attribute__((unused)),
7042
uint flags __attribute__((unused)))
4349
optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
4350
quick->qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
4351
quick->qr_traversal_ctx.cur= (optimizer::QuickRange**)quick->ranges.buffer;
7044
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7045
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7046
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
4352
7047
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4353
7048
quick->ranges.elements;
4354
7049
return &quick->qr_traversal_ctx;
4368
7063
1 No more ranges in the sequence
4370
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7066
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4372
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7068
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4374
7070
if (ctx->cur == ctx->last)
4375
7071
return 1; /* no more ranges */
4377
optimizer::QuickRange *cur= *(ctx->cur);
7073
QUICK_RANGE *cur= *(ctx->cur);
4378
7074
key_range *start_key= &range->start_key;
4379
key_range *end_key= &range->end_key;
7075
key_range *end_key= &range->end_key;
4381
start_key->key= cur->min_key;
7077
start_key->key= cur->min_key;
4382
7078
start_key->length= cur->min_length;
4383
7079
start_key->keypart_map= cur->min_keypart_map;
4384
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4385
(cur->flag & EQ_RANGE) ?
4386
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4387
end_key->key= cur->max_key;
4388
end_key->length= cur->max_length;
7080
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7081
(cur->flag & EQ_RANGE) ?
7082
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7083
end_key->key= cur->max_key;
7084
end_key->length= cur->max_length;
4389
7085
end_key->keypart_map= cur->max_keypart_map;
4391
7087
We use HA_READ_AFTER_KEY here because if we are reading on a key
4392
7088
prefix. We want to find all keys with this prefix.
4394
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7090
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4396
7092
range->range_flag= cur->flag;
4402
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4404
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4405
optimizer::SEL_TREE *range_tree,
4406
optimizer::Parameter *param,
4407
uint32_t *param_idx);
4409
static bool get_constant_key_infix(KeyInfo *index_info,
4410
optimizer::SEL_ARG *index_range_tree,
4411
KeyPartInfo *first_non_group_part,
4412
KeyPartInfo *min_max_arg_part,
4413
KeyPartInfo *last_part,
4415
unsigned char *key_infix,
4416
uint32_t *key_infix_len,
4417
KeyPartInfo **first_non_infix_part);
4419
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7099
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7102
mrr_persistent_flag_storage()
7103
seq Range sequence being traversed
7107
MRR/NDB implementation needs to store some bits for each range. This
7108
function returns a reference to the "range_flag" associated with the
7111
This function should be removed when we get a proper MRR/NDB
7115
Reference to range_flag associated with range number #idx
7118
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint idx)
7120
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7121
return ctx->first[idx]->flag;
7126
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7129
mrr_get_ptr_by_idx()
7130
seq Range sequence bening traversed
7131
idx Number of the range
7134
An extension of MRR range sequence interface needed by NDB: return the
7135
data associated with the given range.
7137
A proper MRR interface implementer is supposed to store and return
7138
range-associated data. NDB stores number of the range instead. So this
7139
is a helper function that translates range number to range associated
7142
This function does nothing, as currrently there is only one user of the
7143
MRR interface - the quick range select code, and this user doesn't need
7144
to use range-associated data.
7147
Reference to range-associated data
7150
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7151
uint idx __attribute__((unused)))
7159
Get next possible record using quick-struct.
7162
QUICK_RANGE_SELECT::get_next()
7165
Record is read into table->record[0]
7169
HA_ERR_END_OF_FILE No (more) rows in range
7173
int QUICK_RANGE_SELECT::get_next()
7176
if (in_ror_merged_scan)
7179
We don't need to signal the bitmap change as the bitmap is always the
7180
same for this head->file
7182
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7185
int result= file->multi_range_read_next(&dummy);
7187
if (in_ror_merged_scan)
7189
/* Restore bitmaps set on entry */
7190
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7197
Get the next record with a different prefix.
7200
QUICK_RANGE_SELECT::get_next_prefix()
7201
prefix_length length of cur_prefix
7202
cur_prefix prefix of a key to be searched for
7205
Each subsequent call to the method retrieves the first record that has a
7206
prefix with length prefix_length different from cur_prefix, such that the
7207
record with the new prefix is within the ranges described by
7208
this->ranges. The record found is stored into the buffer pointed by
7210
The method is useful for GROUP-BY queries with range conditions to
7211
discover the prefix of the next group that satisfies the range conditions.
7214
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7215
methods should be unified into a more general one to reduce code
7220
HA_ERR_END_OF_FILE if returned all keys
7221
other if some error occurred
7224
int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
7225
key_part_map keypart_map,
7231
key_range start_key, end_key;
7234
/* Read the next record in the same range with prefix after cur_prefix. */
7235
assert(cur_prefix != 0);
7236
result= file->index_read_map(record, cur_prefix, keypart_map,
7238
if (result || (file->compare_key(file->end_range) <= 0))
7242
uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7245
/* Ranges have already been used up before. None is left for read. */
7247
return(HA_ERR_END_OF_FILE);
7249
last_range= *(cur_range++);
7251
start_key.key= (const uchar*) last_range->min_key;
7252
start_key.length= min(last_range->min_length, (uint16_t)prefix_length);
7253
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7254
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7255
(last_range->flag & EQ_RANGE) ?
7256
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7257
end_key.key= (const uchar*) last_range->max_key;
7258
end_key.length= min(last_range->max_length, (uint16_t)prefix_length);
7259
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7261
We use READ_AFTER_KEY here because if we are reading on a key
7262
prefix we want to find all keys with this prefix
7264
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7267
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7268
last_range->max_keypart_map ? &end_key : 0,
7269
test(last_range->flag & EQ_RANGE),
7271
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7272
last_range= 0; // Stop searching
7274
if (result != HA_ERR_END_OF_FILE)
7276
last_range= 0; // No matching rows; go to next range
7282
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7285
It is assumed that currently a scan is being done on another index
7286
which reads all necessary parts of the index that is scanned by this
7288
The implementation does a binary search on sorted array of disjoint
7289
ranges, without taking size of range into account.
7291
This function is used to filter out clustered PK scan rows in
7292
index_merge quick select.
7295
true if current row will be retrieved by this quick select
7299
bool QUICK_RANGE_SELECT::row_in_ranges()
7303
uint max= ranges.elements - 1;
7304
uint mid= (max + min)/2;
7308
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7310
/* current row value > mid->max */
7315
mid= (min + max) / 2;
7317
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7318
return (!cmp_next(res) && !cmp_prev(res));
7322
This is a hack: we inherit from QUICK_SELECT so that we can use the
7323
get_next() interface, but we have to hold a pointer to the original
7324
QUICK_SELECT because its data are used all over the place. What
7325
should be done is to factor out the data that is needed into a base
7326
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7327
which handle the ranges and implement the get_next() function. But
7328
for now, this seems to work right at least.
7331
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7332
uint used_key_parts_arg __attribute__((unused)),
7333
bool *create_err __attribute__((unused)))
7334
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7338
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7339
QUICK_RANGE **end_range= pr + ranges.elements;
7340
for (; pr!=end_range; pr++)
7341
rev_ranges.push_front(*pr);
7343
/* Remove EQ_RANGE flag for keys that are not using the full key */
7344
for (r = rev_it++; r; r = rev_it++)
7346
if ((r->flag & EQ_RANGE) &&
7347
head->key_info[index].key_length != r->max_length)
7348
r->flag&= ~EQ_RANGE;
7351
q->dont_free=1; // Don't free shared mem
7356
int QUICK_SELECT_DESC::get_next()
7358
/* The max key is handled as follows:
7359
* - if there is NO_MAX_RANGE, start at the end and move backwards
7360
* - if it is an EQ_RANGE, which means that max key covers the entire
7361
* key, go directly to the key and read through it (sorting backwards is
7362
* same as sorting forwards)
7363
* - if it is NEAR_MAX, go to the key or next, step back once, and
7365
* - otherwise (not NEAR_MAX == include the key), go after the key,
7366
* step back once, and move backwards
7373
{ // Already read through key
7374
result = ((last_range->flag & EQ_RANGE)
7375
? file->index_next_same(record, last_range->min_key,
7376
last_range->min_length) :
7377
file->index_prev(record));
7380
if (cmp_prev(*rev_it.ref()) == 0)
7383
else if (result != HA_ERR_END_OF_FILE)
7387
if (!(last_range= rev_it++))
7388
return(HA_ERR_END_OF_FILE); // All ranges used
7390
if (last_range->flag & NO_MAX_RANGE) // Read last record
7393
if ((local_error=file->index_last(record)))
7394
return(local_error); // Empty table
7395
if (cmp_prev(last_range) == 0)
7397
last_range= 0; // No match; go to next range
7401
if (last_range->flag & EQ_RANGE)
7403
result = file->index_read_map(record, last_range->max_key,
7404
last_range->max_keypart_map,
7409
assert(last_range->flag & NEAR_MAX ||
7410
range_reads_after_key(last_range));
7411
result=file->index_read_map(record, last_range->max_key,
7412
last_range->max_keypart_map,
7413
((last_range->flag & NEAR_MAX) ?
7414
HA_READ_BEFORE_KEY :
7415
HA_READ_PREFIX_LAST_OR_PREV));
7419
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7421
last_range= 0; // Not found, to next range
7424
if (cmp_prev(last_range) == 0)
7426
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7427
last_range= 0; // Stop searching
7428
return(0); // Found key is in range
7430
last_range= 0; // To next range
7436
Compare if found key is over max-value
7437
Returns 0 if key <= range->max_key
7438
TODO: Figure out why can't this function be as simple as cmp_prev().
7441
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7443
if (range_arg->flag & NO_MAX_RANGE)
7444
return 0; /* key can't be to large */
7446
KEY_PART *key_part=key_parts;
7449
for (uchar *key=range_arg->max_key, *end=key+range_arg->max_length;
7451
key+= store_length, key_part++)
7454
store_length= key_part->store_length;
7455
if (key_part->null_bit)
7459
if (!key_part->field->is_null())
7463
else if (key_part->field->is_null())
7465
key++; // Skip null byte
7468
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7473
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7478
Returns 0 if found key is inside range (found key >= range->min_key).
7481
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7484
if (range_arg->flag & NO_MIN_RANGE)
7485
return 0; /* key can't be to small */
7487
cmp= key_cmp(key_part_info, range_arg->min_key,
7488
range_arg->min_length);
7489
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7491
return 1; // outside of range
7496
* true if this range will require using HA_READ_AFTER_KEY
7497
See comment in get_next() about this
7500
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7502
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7503
!(range_arg->flag & EQ_RANGE) ||
7504
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7508
void QUICK_RANGE_SELECT::add_info_string(String *str)
7510
KEY *key_info= head->key_info + index;
7511
str->append(key_info->name);
7514
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7516
QUICK_RANGE_SELECT *quick;
7518
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7519
str->append(STRING_WITH_LEN("sort_union("));
7520
while ((quick= it++))
7526
quick->add_info_string(str);
7528
if (pk_quick_select)
7531
pk_quick_select->add_info_string(str);
7536
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7539
QUICK_RANGE_SELECT *quick;
7540
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7541
str->append(STRING_WITH_LEN("intersect("));
7542
while ((quick= it++))
7544
KEY *key_info= head->key_info + quick->index;
7549
str->append(key_info->name);
7553
KEY *key_info= head->key_info + cpk_quick->index;
7555
str->append(key_info->name);
7560
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7563
QUICK_SELECT_I *quick;
7564
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7565
str->append(STRING_WITH_LEN("union("));
7566
while ((quick= it++))
7572
quick->add_info_string(str);
7578
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7579
String *used_lengths)
7583
KEY *key_info= head->key_info + index;
7584
key_names->append(key_info->name);
7585
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7586
used_lengths->append(buf, length);
7589
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7590
String *used_lengths)
7595
QUICK_RANGE_SELECT *quick;
7597
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7598
while ((quick= it++))
7604
key_names->append(',');
7605
used_lengths->append(',');
7608
KEY *key_info= head->key_info + quick->index;
7609
key_names->append(key_info->name);
7610
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7611
used_lengths->append(buf, length);
7613
if (pk_quick_select)
7615
KEY *key_info= head->key_info + pk_quick_select->index;
7616
key_names->append(',');
7617
key_names->append(key_info->name);
7618
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7619
used_lengths->append(',');
7620
used_lengths->append(buf, length);
7624
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7625
String *used_lengths)
7630
QUICK_RANGE_SELECT *quick;
7631
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7632
while ((quick= it++))
7634
KEY *key_info= head->key_info + quick->index;
7639
key_names->append(',');
7640
used_lengths->append(',');
7642
key_names->append(key_info->name);
7643
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7644
used_lengths->append(buf, length);
7649
KEY *key_info= head->key_info + cpk_quick->index;
7650
key_names->append(',');
7651
key_names->append(key_info->name);
7652
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7653
used_lengths->append(',');
7654
used_lengths->append(buf, length);
7658
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7659
String *used_lengths)
7662
QUICK_SELECT_I *quick;
7663
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7664
while ((quick= it++))
7670
used_lengths->append(',');
7671
key_names->append(',');
7673
quick->add_keys_and_lengths(key_names, used_lengths);
7678
/*******************************************************************************
7679
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7680
*******************************************************************************/
7682
static inline uint get_field_keypart(KEY *index, Field *field);
7683
static inline SEL_ARG * get_index_range_tree(uint index, SEL_TREE* range_tree,
7684
PARAM *param, uint *param_idx);
7685
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7686
KEY_PART_INFO *first_non_group_part,
7687
KEY_PART_INFO *min_max_arg_part,
7688
KEY_PART_INFO *last_part, THD *thd,
7689
uchar *key_infix, uint *key_infix_len,
7690
KEY_PART_INFO **first_non_infix_part);
7692
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7693
Field::imagetype image_type);
4422
cost_group_min_max(Table* table,
4423
KeyInfo *index_info,
4424
uint32_t used_key_parts,
4425
uint32_t group_key_parts,
4426
optimizer::SEL_TREE *range_tree,
4427
optimizer::SEL_ARG *index_tree,
4428
ha_rows quick_prefix_records,
7696
cost_group_min_max(Table* table, KEY *index_info, uint used_key_parts,
7697
uint group_key_parts, SEL_TREE *range_tree,
7698
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7699
bool have_min, bool have_max,
7700
double *read_cost, ha_rows *records);
5546
8753
quick->update_key_stat();
5547
8754
quick->adjust_prefix_ranges();
5553
optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5555
optimizer::QuickRangeSelect *quick= NULL;
5556
if ((quick= optimizer::get_quick_select(param,
5563
quick->records= records;
5564
quick->read_time= read_cost;
5570
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5572
boost::dynamic_bitset<> map= bitsToBitset();
5573
for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5584
size_t optimizer::RorScanInfo::getBitCount() const
5586
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5587
return tmp_bitset.count();
5591
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5593
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5594
tmp_bitset-= in_bitset;
5595
covered_fields= tmp_bitset.to_ulong();
5599
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5602
uint64_t conv= covered_fields;
5605
res.push_back((conv & 1) + '0');
5610
std::reverse(res.begin(), res.end());
5612
string final(covered_fields_size - res.length(), '0');
5614
return (boost::dynamic_bitset<>(final));
5618
} /* namespace drizzled */
8761
Construct new quick select for group queries with min/max.
8764
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8765
table The table being accessed
8766
join Descriptor of the current query
8767
have_min true if the query selects a MIN function
8768
have_max true if the query selects a MAX function
8769
min_max_arg_part The only argument field of all MIN/MAX functions
8770
group_prefix_len Length of all key parts in the group prefix
8771
prefix_key_parts All key parts in the group prefix
8772
index_info The index chosen for data access
8773
use_index The id of index_info
8774
read_cost Cost of this access method
8775
records Number of records returned
8776
key_infix_len Length of the key infix appended to the group prefix
8777
key_infix Infix of constants from equality predicates
8778
parent_alloc Memory pool for this and quick_prefix_select data
8784
QUICK_GROUP_MIN_MAX_SELECT::
8785
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8787
KEY_PART_INFO *min_max_arg_part_arg,
8788
uint group_prefix_len_arg, uint group_key_parts_arg,
8789
uint used_key_parts_arg, KEY *index_info_arg,
8790
uint use_index, double read_cost_arg,
8791
ha_rows records_arg, uint key_infix_len_arg,
8792
uchar *key_infix_arg, MEM_ROOT *parent_alloc)
8793
:join(join_arg), index_info(index_info_arg),
8794
group_prefix_len(group_prefix_len_arg),
8795
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8796
have_max(have_max_arg), seen_first_key(false),
8797
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8798
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8799
max_functions_it(NULL)
8804
record= head->record[0];
8805
tmp_record= head->record[1];
8806
read_time= read_cost_arg;
8807
records= records_arg;
8808
used_key_parts= used_key_parts_arg;
8809
real_key_parts= used_key_parts_arg;
8810
real_prefix_len= group_prefix_len + key_infix_len;
8812
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8815
We can't have parent_alloc set as the init function can't handle this case
8818
assert(!parent_alloc);
8821
init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8822
join->thd->mem_root= &alloc;
8825
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8830
Do post-constructor initialization.
8833
QUICK_GROUP_MIN_MAX_SELECT::init()
8836
The method performs initialization that cannot be done in the constructor
8837
such as memory allocations that may fail. It allocates memory for the
8838
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8839
updated during execution.
8846
int QUICK_GROUP_MIN_MAX_SELECT::init()
8848
if (group_prefix) /* Already initialized. */
8851
if (!(last_prefix= (uchar*) alloc_root(&alloc, group_prefix_len)))
8854
We may use group_prefix to store keys with all select fields, so allocate
8855
enough space for it.
8857
if (!(group_prefix= (uchar*) alloc_root(&alloc,
8858
real_prefix_len + min_max_arg_len)))
8861
if (key_infix_len > 0)
8864
The memory location pointed to by key_infix will be deleted soon, so
8865
allocate a new buffer and copy the key_infix into it.
8867
uchar *tmp_key_infix= (uchar*) alloc_root(&alloc, key_infix_len);
8870
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8871
this->key_infix= tmp_key_infix;
8874
if (min_max_arg_part)
8876
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8881
if (!(min_functions= new List<Item_sum>))
8885
min_functions= NULL;
8888
if (!(max_functions= new List<Item_sum>))
8892
max_functions= NULL;
8894
Item_sum *min_max_item;
8895
Item_sum **func_ptr= join->sum_funcs;
8896
while ((min_max_item= *(func_ptr++)))
8898
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8899
min_functions->push_back(min_max_item);
8900
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8901
max_functions->push_back(min_max_item);
8906
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
8912
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
8917
min_max_ranges.elements= 0;
8923
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8925
if (file->inited != handler::NONE)
8926
file->ha_index_end();
8927
if (min_max_arg_part)
8928
delete_dynamic(&min_max_ranges);
8929
free_root(&alloc,MYF(0));
8930
delete min_functions_it;
8931
delete max_functions_it;
8932
delete quick_prefix_select;
8938
Eventually create and add a new quick range object.
8941
QUICK_GROUP_MIN_MAX_SELECT::add_range()
8942
sel_range Range object from which a
8945
Construct a new QUICK_RANGE object from a SEL_ARG object, and
8946
add it to the array min_max_ranges. If sel_arg is an infinite
8947
range, e.g. (x < 5 or x > 4), then skip it and do not construct
8955
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8958
uint range_flag= sel_range->min_flag | sel_range->max_flag;
8960
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8961
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8964
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
8965
!(sel_range->max_flag & NO_MAX_RANGE))
8967
if (sel_range->maybe_null &&
8968
sel_range->min_value[0] && sel_range->max_value[0])
8969
range_flag|= NULL_RANGE; /* IS NULL condition */
8970
else if (memcmp(sel_range->min_value, sel_range->max_value,
8971
min_max_arg_len) == 0)
8972
range_flag|= EQ_RANGE; /* equality condition */
8974
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
8975
make_keypart_map(sel_range->part),
8976
sel_range->max_value, min_max_arg_len,
8977
make_keypart_map(sel_range->part),
8981
if (insert_dynamic(&min_max_ranges, (uchar*)&range))
8988
Opens the ranges if there are more conditions in quick_prefix_select than
8989
the ones used for jumping through the prefixes.
8992
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
8995
quick_prefix_select is made over the conditions on the whole key.
8996
It defines a number of ranges of length x.
8997
However when jumping through the prefixes we use only the the first
8998
few most significant keyparts in the range key. However if there
8999
are more keyparts to follow the ones we are using we must make the
9000
condition on the key inclusive (because x < "ab" means
9001
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9002
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9004
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9006
if (quick_prefix_select &&
9007
group_prefix_len < quick_prefix_select->max_used_key_length)
9012
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9016
get_dynamic(arr, (uchar*)&range, inx);
9017
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9024
Determine the total number and length of the keys that will be used for
9028
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9031
The total length of the keys used for index lookup depends on whether
9032
there are any predicates referencing the min/max argument, and/or if
9033
the min/max argument field can be NULL.
9034
This function does an optimistic analysis whether the search key might
9035
be extended by a constant for the min/max keypart. It is 'optimistic'
9036
because during actual execution it may happen that a particular range
9037
is skipped, and then a shorter key will be used. However this is data
9038
dependent and can't be easily estimated here.
9044
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9046
max_used_key_length= real_prefix_len;
9047
if (min_max_ranges.elements > 0)
9049
QUICK_RANGE *cur_range;
9051
{ /* Check if the right-most range has a lower boundary. */
9052
get_dynamic(&min_max_ranges, (uchar*)&cur_range,
9053
min_max_ranges.elements - 1);
9054
if (!(cur_range->flag & NO_MIN_RANGE))
9056
max_used_key_length+= min_max_arg_len;
9062
{ /* Check if the left-most range has an upper boundary. */
9063
get_dynamic(&min_max_ranges, (uchar*)&cur_range, 0);
9064
if (!(cur_range->flag & NO_MAX_RANGE))
9066
max_used_key_length+= min_max_arg_len;
9072
else if (have_min && min_max_arg_part &&
9073
min_max_arg_part->field->real_maybe_null())
9076
If a MIN/MAX argument value is NULL, we can quickly determine
9077
that we're in the beginning of the next group, because NULLs
9078
are always < any other value. This allows us to quickly
9079
determine the end of the current group and jump to the next
9080
group (see next_min()) and thus effectively increases the
9083
max_used_key_length+= min_max_arg_len;
9090
Initialize a quick group min/max select for key retrieval.
9093
QUICK_GROUP_MIN_MAX_SELECT::reset()
9096
Initialize the index chosen for access and find and store the prefix
9097
of the last group. The method is expensive since it performs disk access.
9104
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9108
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9109
if ((result= file->ha_index_init(index,1)))
9111
if (quick_prefix_select && quick_prefix_select->reset())
9113
result= file->index_last(record);
9114
if (result == HA_ERR_END_OF_FILE)
9116
/* Save the prefix of the last group. */
9117
key_copy(last_prefix, record, index_info, group_prefix_len);
9125
Get the next key containing the MIN and/or MAX key for the next group.
9128
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9131
The method finds the next subsequent group of records that satisfies the
9132
query conditions and finds the keys that contain the MIN/MAX values for
9133
the key part referenced by the MIN/MAX function(s). Once a group and its
9134
MIN/MAX values are found, store these values in the Item_sum objects for
9135
the MIN/MAX functions. The rest of the values in the result row are stored
9136
in the Item_field::result_field of each select field. If the query does
9137
not contain MIN and/or MAX functions, then the function only finds the
9138
group prefix, which is a query answer itself.
9141
If both MIN and MAX are computed, then we use the fact that if there is
9142
no MIN key, there can't be a MAX key as well, so we can skip looking
9143
for a MAX key in this case.
9147
HA_ERR_END_OF_FILE if returned all keys
9148
other if some error occurred
9151
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9156
int is_last_prefix= 0;
9159
Loop until a group is found that satisfies all query conditions or the last
9164
result= next_prefix();
9166
Check if this is the last group prefix. Notice that at this point
9167
this->record contains the current prefix in record format.
9171
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9173
assert(is_last_prefix <= 0);
9177
if (result == HA_ERR_KEY_NOT_FOUND)
9184
min_res= next_min();
9186
update_min_result();
9188
/* If there is no MIN in the group, there is no MAX either. */
9189
if ((have_max && !have_min) ||
9190
(have_max && have_min && (min_res == 0)))
9192
max_res= next_max();
9194
update_max_result();
9195
/* If a MIN was found, a MAX must have been found as well. */
9196
assert((have_max && !have_min) ||
9197
(have_max && have_min && (max_res == 0)));
9200
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9201
are equality predicates for the key parts after the group, find the
9202
first sub-group with the extended prefix.
9204
if (!have_min && !have_max && key_infix_len > 0)
9205
result= file->index_read_map(record, group_prefix,
9206
make_prev_keypart_map(real_key_parts),
9209
result= have_min ? min_res : have_max ? max_res : result;
9210
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9211
is_last_prefix != 0);
9216
Partially mimic the behavior of end_select_send. Copy the
9217
field data from Item_field::field into Item_field::result_field
9218
of each non-aggregated field (the group fields, and optionally
9219
other fields in non-ANSI SQL mode).
9221
copy_fields(&join->tmp_table_param);
9223
else if (result == HA_ERR_KEY_NOT_FOUND)
9224
result= HA_ERR_END_OF_FILE;
9231
Retrieve the minimal key in the next group.
9234
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9237
Find the minimal key within this group such that the key satisfies the query
9238
conditions and NULL semantics. The found key is loaded into this->record.
9241
Depending on the values of min_max_ranges.elements, key_infix_len, and
9242
whether there is a NULL in the MIN field, this function may directly
9243
return without any data access. In this case we use the key loaded into
9244
this->record by the call to this->next_prefix() just before this call.
9248
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9249
HA_ERR_END_OF_FILE - "" -
9250
other if some error occurred
9253
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9257
/* Find the MIN key using the eventually extended group prefix. */
9258
if (min_max_ranges.elements > 0)
9260
if ((result= next_min_in_range()))
9265
/* Apply the constant equality conditions to the non-group select fields */
9266
if (key_infix_len > 0)
9268
if ((result= file->index_read_map(record, group_prefix,
9269
make_prev_keypart_map(real_key_parts),
9270
HA_READ_KEY_EXACT)))
9275
If the min/max argument field is NULL, skip subsequent rows in the same
9276
group with NULL in it. Notice that:
9277
- if the first row in a group doesn't have a NULL in the field, no row
9278
in the same group has (because NULL < any other value),
9279
- min_max_arg_part->field->ptr points to some place in 'record'.
9281
if (min_max_arg_part && min_max_arg_part->field->is_null())
9283
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9284
key_copy(tmp_record, record, index_info, 0);
9285
result= file->index_read_map(record, tmp_record,
9286
make_keypart_map(real_key_parts),
9289
Check if the new record belongs to the current group by comparing its
9290
prefix with the group's prefix. If it is from the next group, then the
9291
whole group has NULLs in the MIN/MAX field, so use the first record in
9292
the group as a result.
9294
It is possible to reuse this new record as the result candidate for the
9295
next call to next_min(), and to save one lookup in the next call. For
9296
this add a new member 'this->next_group_prefix'.
9300
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9301
key_restore(record, tmp_record, index_info, 0);
9303
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9304
result= 0; /* There is a result in any case. */
9309
If the MIN attribute is non-nullable, this->record already contains the
9310
MIN key in the group, so just return.
9317
Retrieve the maximal key in the next group.
9320
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9323
Lookup the maximal key of the group, and store it into this->record.
9327
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9328
HA_ERR_END_OF_FILE - "" -
9329
other if some error occurred
9332
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9336
/* Get the last key in the (possibly extended) group. */
9337
if (min_max_ranges.elements > 0)
9338
result= next_max_in_range();
9340
result= file->index_read_map(record, group_prefix,
9341
make_prev_keypart_map(real_key_parts),
9342
HA_READ_PREFIX_LAST);
9348
Determine the prefix of the next group.
9351
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9354
Determine the prefix of the next group that satisfies the query conditions.
9355
If there is a range condition referencing the group attributes, use a
9356
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9357
condition. If there is a key infix of constants, append this infix
9358
immediately after the group attributes. The possibly extended prefix is
9359
stored in this->group_prefix. The first key of the found group is stored in
9360
this->record, on which relies this->next_min().
9364
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9365
HA_ERR_END_OF_FILE if there are no more keys
9366
other if some error occurred
9368
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9372
if (quick_prefix_select)
9374
uchar *cur_prefix= seen_first_key ? group_prefix : NULL;
9375
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9376
make_prev_keypart_map(group_key_parts), cur_prefix)))
9378
seen_first_key= true;
9382
if (!seen_first_key)
9384
result= file->index_first(record);
9387
seen_first_key= true;
9391
/* Load the first key in this group into record. */
9392
result= file->index_read_map(record, group_prefix,
9393
make_prev_keypart_map(group_key_parts),
9400
/* Save the prefix of this group for subsequent calls. */
9401
key_copy(group_prefix, record, index_info, group_prefix_len);
9402
/* Append key_infix to group_prefix. */
9403
if (key_infix_len > 0)
9404
memcpy(group_prefix + group_prefix_len,
9405
key_infix, key_infix_len);
9412
Find the minimal key in a group that satisfies some range conditions for the
9413
min/max argument field.
9416
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9419
Given the sequence of ranges min_max_ranges, find the minimal key that is
9420
in the left-most possible range. If there is no such key, then the current
9421
group does not have a MIN key that satisfies the WHERE clause. If a key is
9422
found, its value is stored in this->record.
9426
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9428
HA_ERR_END_OF_FILE - "" -
9432
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9434
ha_rkey_function find_flag;
9435
key_part_map keypart_map;
9436
QUICK_RANGE *cur_range;
9437
bool found_null= false;
9438
int result= HA_ERR_KEY_NOT_FOUND;
9440
assert(min_max_ranges.elements > 0);
9442
for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9443
{ /* Search from the left-most range to the right. */
9444
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx);
9447
If the current value for the min/max argument is bigger than the right
9448
boundary of cur_range, there is no need to check this range.
9450
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9451
(key_cmp(min_max_arg_part, (const uchar*) cur_range->max_key,
9452
min_max_arg_len) == 1))
9455
if (cur_range->flag & NO_MIN_RANGE)
9457
keypart_map= make_prev_keypart_map(real_key_parts);
9458
find_flag= HA_READ_KEY_EXACT;
9462
/* Extend the search key with the lower boundary for this range. */
9463
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9464
cur_range->min_length);
9465
keypart_map= make_keypart_map(real_key_parts);
9466
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9467
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9468
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9471
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9474
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9475
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9476
continue; /* Check the next range. */
9479
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9480
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9481
range, it can't succeed for any other subsequent range.
9486
/* A key was found. */
9487
if (cur_range->flag & EQ_RANGE)
9488
break; /* No need to perform the checks below for equal keys. */
9490
if (cur_range->flag & NULL_RANGE)
9493
Remember this key, and continue looking for a non-NULL key that
9494
satisfies some other condition.
9496
memcpy(tmp_record, record, head->s->rec_buff_length);
9501
/* Check if record belongs to the current group. */
9502
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9504
result= HA_ERR_KEY_NOT_FOUND;
9508
/* If there is an upper limit, check if the found key is in the range. */
9509
if ( !(cur_range->flag & NO_MAX_RANGE) )
9511
/* Compose the MAX key for the range. */
9512
uchar *max_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9513
memcpy(max_key, group_prefix, real_prefix_len);
9514
memcpy(max_key + real_prefix_len, cur_range->max_key,
9515
cur_range->max_length);
9516
/* Compare the found key with max_key. */
9517
int cmp_res= key_cmp(index_info->key_part, max_key,
9518
real_prefix_len + min_max_arg_len);
9519
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9521
result= HA_ERR_KEY_NOT_FOUND;
9525
/* If we got to this point, the current key qualifies as MIN. */
9526
assert(result == 0);
9530
If there was a key with NULL in the MIN/MAX field, and there was no other
9531
key without NULL from the same group that satisfies some other condition,
9532
then use the key with the NULL.
9534
if (found_null && result)
9536
memcpy(record, tmp_record, head->s->rec_buff_length);
9544
Find the maximal key in a group that satisfies some range conditions for the
9545
min/max argument field.
9548
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9551
Given the sequence of ranges min_max_ranges, find the maximal key that is
9552
in the right-most possible range. If there is no such key, then the current
9553
group does not have a MAX key that satisfies the WHERE clause. If a key is
9554
found, its value is stored in this->record.
9558
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9560
HA_ERR_END_OF_FILE - "" -
9564
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9566
ha_rkey_function find_flag;
9567
key_part_map keypart_map;
9568
QUICK_RANGE *cur_range;
9571
assert(min_max_ranges.elements > 0);
9573
for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9574
{ /* Search from the right-most range to the left. */
9575
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx - 1);
9578
If the current value for the min/max argument is smaller than the left
9579
boundary of cur_range, there is no need to check this range.
9581
if (range_idx != min_max_ranges.elements &&
9582
!(cur_range->flag & NO_MIN_RANGE) &&
9583
(key_cmp(min_max_arg_part, (const uchar*) cur_range->min_key,
9584
min_max_arg_len) == -1))
9587
if (cur_range->flag & NO_MAX_RANGE)
9589
keypart_map= make_prev_keypart_map(real_key_parts);
9590
find_flag= HA_READ_PREFIX_LAST;
9594
/* Extend the search key with the upper boundary for this range. */
9595
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9596
cur_range->max_length);
9597
keypart_map= make_keypart_map(real_key_parts);
9598
find_flag= (cur_range->flag & EQ_RANGE) ?
9599
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9600
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9603
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9607
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9608
(cur_range->flag & EQ_RANGE))
9609
continue; /* Check the next range. */
9612
In no key was found with this upper bound, there certainly are no keys
9613
in the ranges to the left.
9617
/* A key was found. */
9618
if (cur_range->flag & EQ_RANGE)
9619
return 0; /* No need to perform the checks below for equal keys. */
9621
/* Check if record belongs to the current group. */
9622
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9623
continue; // Row not found
9625
/* If there is a lower limit, check if the found key is in the range. */
9626
if ( !(cur_range->flag & NO_MIN_RANGE) )
9628
/* Compose the MIN key for the range. */
9629
uchar *min_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9630
memcpy(min_key, group_prefix, real_prefix_len);
9631
memcpy(min_key + real_prefix_len, cur_range->min_key,
9632
cur_range->min_length);
9633
/* Compare the found key with min_key. */
9634
int cmp_res= key_cmp(index_info->key_part, min_key,
9635
real_prefix_len + min_max_arg_len);
9636
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9640
/* If we got to this point, the current key qualifies as MAX. */
9643
return HA_ERR_KEY_NOT_FOUND;
9648
Update all MIN function results with the newly found value.
9651
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9654
The method iterates through all MIN functions and updates the result value
9655
of each function by calling Item_sum::reset(), which in turn picks the new
9656
result value from this->head->record[0], previously updated by
9657
next_min(). The updated value is stored in a member variable of each of the
9658
Item_sum objects, depending on the value type.
9661
The update must be done separately for MIN and MAX, immediately after
9662
next_min() was called and before next_max() is called, because both MIN and
9663
MAX take their result value from the same buffer this->head->record[0]
9664
(i.e. this->record).
9670
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9674
min_functions_it->rewind();
9675
while ((min_func= (*min_functions_it)++))
9681
Update all MAX function results with the newly found value.
9684
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9687
The method iterates through all MAX functions and updates the result value
9688
of each function by calling Item_sum::reset(), which in turn picks the new
9689
result value from this->head->record[0], previously updated by
9690
next_max(). The updated value is stored in a member variable of each of the
9691
Item_sum objects, depending on the value type.
9694
The update must be done separately for MIN and MAX, immediately after
9695
next_max() was called, because both MIN and MAX take their result value
9696
from the same buffer this->head->record[0] (i.e. this->record).
9702
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9706
max_functions_it->rewind();
9707
while ((max_func= (*max_functions_it)++))
9713
Append comma-separated list of keys this quick select uses to key_names;
9714
append comma-separated list of corresponding used lengths to used_lengths.
9717
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9718
key_names [out] Names of used indexes
9719
used_lengths [out] Corresponding lengths of the index names
9722
This method is used by select_describe to extract the names of the
9723
indexes used by a quick select.
9727
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9728
String *used_lengths)
9732
key_names->append(index_info->name);
9733
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9734
used_lengths->append(buf, length);
9737
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9738
const char *msg __attribute__((unused)))
9740
SEL_ARG **key,**end;
9744
String tmp(buff,sizeof(buff),&my_charset_bin);
9746
for (idx= 0,key=tree->keys, end=key+param->keys ;
9750
if (tree_map->is_set(idx))
9752
uint keynr= param->real_keynr[idx];
9755
tmp.append(param->table->key_info[keynr].name);
9759
tmp.append(STRING_WITH_LEN("(empty)"));
9765
static void print_ror_scans_arr(Table *table,
9766
const char *msg __attribute__((unused)),
9767
struct st_ror_scan_info **start,
9768
struct st_ror_scan_info **end)
9771
String tmp(buff,sizeof(buff),&my_charset_bin);
9773
for (;start != end; start++)
9777
tmp.append(table->key_info[(*start)->keynr].name);
9780
tmp.append(STRING_WITH_LEN("(empty)"));
9784
/*****************************************************************************
9785
** Instantiate templates
9786
*****************************************************************************/
9788
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9789
template class List<QUICK_RANGE>;
9790
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
