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