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"
112
#include "sql_select.h"
115
#define test_rb_tree(A,B) {}
116
#define test_use_count(A) {}
151
120
Convert double value to #rows. Currently this does floor(), and we
152
121
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.
123
#define double2rows(x) ((ha_rows)(x))
125
static int sel_cmp(Field *f,uchar *a,uchar *b,uint8_t a_flag,uint8_t b_flag);
127
static uchar is_null_string[2]= {1,0};
129
class RANGE_OPT_PARAM;
131
A construction block of the SEL_ARG-graph.
133
The following description only covers graphs of SEL_ARG objects with
134
sel_arg->type==KEY_RANGE:
136
One SEL_ARG object represents an "elementary interval" in form
138
min_value <=? table.keypartX <=? max_value
140
The interval is a non-empty interval of any kind: with[out] minimum/maximum
141
bound, [half]open/closed, single-point interval, etc.
143
1. SEL_ARG GRAPH STRUCTURE
145
SEL_ARG objects are linked together in a graph. The meaning of the graph
146
is better demostrated by an example:
151
| part=1 $ part=2 $ part=3
153
| +-------+ $ +-------+ $ +--------+
154
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
155
| +-------+ $ +-------+ $ +--------+
161
\->| kp1=2 |--$--------------$-+
162
+-------+ $ $ | +--------+
164
+-------+ $ $ | +--------+
165
| kp1=3 |--$--------------$-+ |
166
+-------+ $ $ +--------+
170
The entire graph is partitioned into "interval lists".
172
An interval list is a sequence of ordered disjoint intervals over the same
173
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
174
all intervals in the list form an RB-tree, linked via left/right/parent
175
pointers. The RB-tree root SEL_ARG object will be further called "root of the
178
In the example pic, there are 4 interval lists:
179
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
180
The vertical lines represent SEL_ARG::next/prev pointers.
182
In an interval list, each member X may have SEL_ARG::next_key_part pointer
183
pointing to the root of another interval list Y. The pointed interval list
184
must cover a key part with greater number (i.e. Y->part > X->part).
186
In the example pic, the next_key_part pointers are represented by
189
2. SEL_ARG GRAPH SEMANTICS
191
It represents a condition in a special form (we don't have a name for it ATM)
192
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
194
For example, the picture represents the condition in form:
195
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
196
(kp1=2 AND (kp3=11 OR kp3=14)) OR
197
(kp1=3 AND (kp3=11 OR kp3=14))
202
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
203
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
204
intervals (i.e. intervals in form
206
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
208
Those intervals can be used to access the index. The uses are in:
209
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
210
how many table records are contained within all
212
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
213
and create QUICK_RANGE_SELECT object that will
214
read records within these intervals.
216
4. SPACE COMPLEXITY NOTES
218
SEL_ARG graph is a representation of an ordered disjoint sequence of
219
intervals over the ordered set of index tuple values.
221
For multi-part keys, one can construct a WHERE expression such that its
222
list of intervals will be of combinatorial size. Here is an example:
224
(keypart1 IN (1,2, ..., n1)) AND
225
(keypart2 IN (1,2, ..., n2)) AND
226
(keypart3 IN (1,2, ..., n3))
228
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
231
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
233
SEL_ARG graph structure aims to reduce the amount of required space by
234
"sharing" the elementary intervals when possible (the pic at the
235
beginning of this comment has examples of such sharing). The sharing may
236
prevent combinatorial blowup:
238
There are WHERE clauses that have combinatorial-size interval lists but
239
will be represented by a compact SEL_ARG graph.
241
(keypartN IN (1,2, ..., n1)) AND
243
(keypart2 IN (1,2, ..., n2)) AND
244
(keypart1 IN (1,2, ..., n3))
246
but not in all cases:
248
- There are WHERE clauses that do have a compact SEL_ARG-graph
249
representation but get_mm_tree() and its callees will construct a
250
graph of combinatorial size.
252
(keypart1 IN (1,2, ..., n1)) AND
253
(keypart2 IN (1,2, ..., n2)) AND
255
(keypartN IN (1,2, ..., n3))
257
- There are WHERE clauses for which the minimal possible SEL_ARG graph
258
representation will have combinatorial size.
260
By induction: Let's take any interval on some keypart in the middle:
264
Then let's AND it with this interval 'structure' from preceding and
267
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
269
We will obtain this SEL_ARG graph:
273
+---------+ $ +---------+ $ +---------+
274
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
275
+---------+ $ +---------+ $ +---------+
277
+---------+ $ +---------+ $
278
| kp14=c2 |--$-->| kp15=c0 | $
279
+---------+ $ +---------+ $
282
Note that we had to duplicate "kp15=c0" and there was no way to avoid
284
The induction step: AND the obtained expression with another "wrapping"
286
When the process ends because of the limit on max. number of keyparts
289
WHERE clause length is O(3*#max_keyparts)
290
SEL_ARG graph size is O(2^(#max_keyparts/2))
292
(it is also possible to construct a case where instead of 2 in 2^n we
293
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
296
We avoid consuming too much memory by setting a limit on the number of
297
SEL_ARG object we can construct during one range analysis invocation.
205
static void get_sweep_read_cost(Table *table,
300
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);
303
uint8_t min_flag,max_flag,maybe_flag;
304
uint8_t part; // Which key part
307
Number of children of this element in the RB-tree, plus 1 for this
312
Valid only for elements which are RB-tree roots: Number of times this
313
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
314
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
319
uchar *min_value,*max_value; // Pointer to range
322
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
324
SEL_ARG *left,*right; /* R-B tree children */
325
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
326
SEL_ARG *parent; /* R-B tree parent */
327
SEL_ARG *next_key_part;
328
enum leaf_color { BLACK,RED } color;
329
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
331
enum { MAX_SEL_ARGS = 16000 };
335
SEL_ARG(Field *,const uchar *, const uchar *);
336
SEL_ARG(Field *field, uint8_t part, uchar *min_value, uchar *max_value,
337
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
338
SEL_ARG(enum Type type_arg)
339
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
340
color(BLACK), type(type_arg)
342
inline bool is_same(SEL_ARG *arg)
344
if (type != arg->type || part != arg->part)
346
if (type != KEY_RANGE)
348
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
350
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
351
inline void maybe_smaller() { maybe_flag=1; }
352
/* Return true iff it's a single-point null interval */
353
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
354
inline int cmp_min_to_min(SEL_ARG* arg)
356
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
358
inline int cmp_min_to_max(SEL_ARG* arg)
360
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
362
inline int cmp_max_to_max(SEL_ARG* arg)
364
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
366
inline int cmp_max_to_min(SEL_ARG* arg)
368
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
370
SEL_ARG *clone_and(SEL_ARG* arg)
371
{ // Get overlapping range
372
uchar *new_min,*new_max;
373
uint8_t flag_min,flag_max;
374
if (cmp_min_to_min(arg) >= 0)
376
new_min=min_value; flag_min=min_flag;
380
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
382
if (cmp_max_to_max(arg) <= 0)
384
new_max=max_value; flag_max=max_flag;
388
new_max=arg->max_value; flag_max=arg->max_flag;
390
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
391
test(maybe_flag && arg->maybe_flag));
393
SEL_ARG *clone_first(SEL_ARG *arg)
394
{ // min <= X < arg->min
395
return new SEL_ARG(field,part, min_value, arg->min_value,
396
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
397
maybe_flag | arg->maybe_flag);
399
SEL_ARG *clone_last(SEL_ARG *arg)
400
{ // min <= X <= key_max
401
return new SEL_ARG(field, part, min_value, arg->max_value,
402
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
404
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
406
bool copy_min(SEL_ARG* arg)
407
{ // Get overlapping range
408
if (cmp_min_to_min(arg) > 0)
410
min_value=arg->min_value; min_flag=arg->min_flag;
411
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
412
(NO_MAX_RANGE | NO_MIN_RANGE))
413
return 1; // Full range
415
maybe_flag|=arg->maybe_flag;
418
bool copy_max(SEL_ARG* arg)
419
{ // Get overlapping range
420
if (cmp_max_to_max(arg) <= 0)
422
max_value=arg->max_value; max_flag=arg->max_flag;
423
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
424
(NO_MAX_RANGE | NO_MIN_RANGE))
425
return 1; // Full range
427
maybe_flag|=arg->maybe_flag;
431
void copy_min_to_min(SEL_ARG *arg)
433
min_value=arg->min_value; min_flag=arg->min_flag;
435
void copy_min_to_max(SEL_ARG *arg)
437
max_value=arg->min_value;
438
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
440
void copy_max_to_min(SEL_ARG *arg)
442
min_value=arg->max_value;
443
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
445
/* returns a number of keypart values (0 or 1) appended to the key buffer */
446
int store_min(uint length, uchar **min_key,uint min_key_flag)
448
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
449
if ((!(min_flag & NO_MIN_RANGE) &&
450
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
452
if (maybe_null && *min_value)
455
bzero(*min_key+1,length-1);
458
memcpy(*min_key,min_value,length);
464
/* returns a number of keypart values (0 or 1) appended to the key buffer */
465
int store_max(uint length, uchar **max_key, uint max_key_flag)
467
if (!(max_flag & NO_MAX_RANGE) &&
468
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
470
if (maybe_null && *max_value)
473
bzero(*max_key+1,length-1);
476
memcpy(*max_key,max_value,length);
483
/* returns a number of keypart values appended to the key buffer */
484
int store_min_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
486
SEL_ARG *key_tree= first();
487
uint res= key_tree->store_min(key[key_tree->part].store_length,
488
range_key, *range_key_flag);
489
*range_key_flag|= key_tree->min_flag;
491
if (key_tree->next_key_part &&
492
key_tree->next_key_part->part == key_tree->part+1 &&
493
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
494
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
495
res+= key_tree->next_key_part->store_min_key(key, range_key,
500
/* returns a number of keypart values appended to the key buffer */
501
int store_max_key(KEY_PART *key, uchar **range_key, uint *range_key_flag)
503
SEL_ARG *key_tree= last();
504
uint res=key_tree->store_max(key[key_tree->part].store_length,
505
range_key, *range_key_flag);
506
(*range_key_flag)|= key_tree->max_flag;
507
if (key_tree->next_key_part &&
508
key_tree->next_key_part->part == key_tree->part+1 &&
509
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
510
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
511
res+= key_tree->next_key_part->store_max_key(key, range_key,
516
SEL_ARG *insert(SEL_ARG *key);
517
SEL_ARG *tree_delete(SEL_ARG *key);
518
SEL_ARG *find_range(SEL_ARG *key);
519
SEL_ARG *rb_insert(SEL_ARG *leaf);
520
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
522
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
523
void test_use_count(SEL_ARG *root);
528
inline bool simple_key()
530
return !next_key_part && elements == 1;
532
void increment_use_count(long count)
536
next_key_part->use_count+=count;
537
count*= (next_key_part->use_count-count);
538
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
539
if (pos->next_key_part)
540
pos->increment_use_count(count);
545
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
546
if (pos->next_key_part)
548
pos->next_key_part->use_count--;
549
pos->next_key_part->free_tree();
553
inline SEL_ARG **parent_ptr()
555
return parent->left == this ? &parent->left : &parent->right;
560
Check if this SEL_ARG object represents a single-point interval
566
Check if this SEL_ARG object (not tree) represents a single-point
567
interval, i.e. if it represents a "keypart = const" or
571
true This SEL_ARG object represents a singlepoint interval
575
bool is_singlepoint()
578
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
579
flags, and the same for right edge.
581
if (min_flag || max_flag)
583
uchar *min_val= min_value;
584
uchar *max_val= max_value;
588
/* First byte is a NULL value indicator */
589
if (*min_val != *max_val)
593
return true; /* This "x IS NULL" */
597
return !field->key_cmp(min_val, max_val);
599
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
237
602
class SEL_IMERGE;
240
class SEL_TREE :public drizzled::memory::SqlAlloc
605
class SEL_TREE :public Sql_alloc
244
609
Starting an effort to document this field:
245
(for some i, keys[i]->type == optimizer::SEL_ARG::IMPOSSIBLE) =>
610
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
246
611
(type == SEL_TREE::IMPOSSIBLE)
613
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
257
614
SEL_TREE(enum Type type_arg) :type(type_arg) {}
258
615
SEL_TREE() :type(KEY)
261
memset(keys, 0, sizeof(keys));
617
keys_map.clear_all();
618
bzero((char*) keys,sizeof(keys));
264
621
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
266
623
merit in range analyzer functions (e.g. get_mm_parts) returning a
267
624
pointer to such SEL_TREE instead of NULL)
269
optimizer::SEL_ARG *keys[MAX_KEY];
626
SEL_ARG *keys[MAX_KEY];
270
627
key_map keys_map; /* bitmask of non-NULL elements in keys */
273
630
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().
631
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
276
633
List<SEL_IMERGE> merges;
278
635
/* The members below are filled/used only after get_mm_tree is done */
279
636
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 */
637
uint n_ror_scans; /* number of set bits in ror_scans_map */
282
639
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
283
640
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
284
641
/* Note that #records for each key scan is stored in table->quick_rows */
644
class RANGE_OPT_PARAM
647
THD *thd; /* Current thread handle */
648
TABLE *table; /* Table being analyzed */
649
COND *cond; /* Used inside get_mm_tree(). */
650
table_map prev_tables;
651
table_map read_tables;
652
table_map current_table; /* Bit of the table being analyzed */
654
/* Array of parts of all keys for which range analysis is performed */
656
KEY_PART *key_parts_end;
657
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
658
MEM_ROOT *old_root; /* Memory that will last until the query end */
660
Number of indexes used in range analysis (In SEL_TREE::keys only first
661
#keys elements are not empty)
666
If true, the index descriptions describe real indexes (and it is ok to
667
call field->optimize_range(real_keynr[...], ...).
668
Otherwise index description describes fake indexes.
670
bool using_real_indexes;
672
bool remove_jump_scans;
675
used_key_no -> table_key_no translation table. Only makes sense if
676
using_real_indexes==true
678
uint real_keynr[MAX_KEY];
679
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
680
uint alloced_sel_args;
681
bool force_default_mrr;
684
class PARAM : public RANGE_OPT_PARAM
687
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
690
/* Number of ranges in the last checked tree->key */
692
uchar min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
693
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
694
bool quick; // Don't calulate possible keys
696
uint fields_bitmap_size;
697
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
698
MY_BITMAP tmp_covered_fields;
700
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
702
uint *imerge_cost_buff; /* buffer for index_merge cost estimates */
703
uint imerge_cost_buff_size; /* size of the buffer */
705
/* true if last checked tree->key can be used for ROR-scan */
707
/* Number of ranges in the last checked tree->key */
711
class TABLE_READ_PLAN;
713
class TRP_ROR_INTERSECT;
715
class TRP_ROR_INDEX_MERGE;
716
class TRP_GROUP_MIN_MAX;
287
718
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,
720
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
721
Item_func::Functype type,Item *value,
722
Item_result cmp_type);
723
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
725
Item_func::Functype type,Item *value);
726
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
728
static bool is_key_scan_ror(PARAM *param, uint keynr, uint8_t nparts);
729
static ha_rows check_quick_select(PARAM *param, uint idx, bool index_only,
730
SEL_ARG *tree, bool update_tbl_stats,
731
uint *mrr_flags, uint *bufsize,
314
732
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,
733
//bool update_tbl_stats);
734
/*static ha_rows check_quick_keys(PARAM *param,uint index,SEL_ARG *key_tree,
735
uchar *min_key, uint min_key_flag, int,
736
uchar *max_key, uint max_key_flag, int);
739
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint index,
740
SEL_ARG *key_tree, uint mrr_flags,
741
uint mrr_buf_size, MEM_ROOT *alloc);
742
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
743
bool index_read_must_be_used,
744
bool update_tbl_stats,
747
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
749
bool *are_all_covering);
751
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
755
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
758
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
760
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
344
761
const char *msg);
346
static void print_ror_scans_arr(Table *table,
762
static void print_ror_scans_arr(TABLE *table, const char *msg,
348
763
struct st_ror_scan_info **start,
349
764
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);
766
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
767
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
768
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
769
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
770
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
772
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
773
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
774
SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
775
uchar *max_key,uint max_key_flag);
776
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
778
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
779
static bool null_part_in_key(KEY_PART *key_part, const uchar *key,
781
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
623
1028
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;
1030
select->file= *head->sort.io_cache;
1031
select->records=(ha_rows) (select->file.end_of_file/
1032
head->file->ref_length);
1033
my_free(head->sort.io_cache, MYF(0));
629
1034
head->sort.io_cache=0;
635
optimizer::SqlSelect::SqlSelect()
639
file(static_cast<IO_CACHE *>(memory::sql_calloc(sizeof(IO_CACHE)))),
1040
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1042
quick_keys.clear_all(); needed_reg.clear_all();
648
void optimizer::SqlSelect::cleanup()
1047
void SQL_SELECT::cleanup()
658
close_cached_file(file);
1057
close_cached_file(&file);
662
optimizer::SqlSelect::~SqlSelect()
1061
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),
1066
QUICK_SELECT_I::QUICK_SELECT_I()
1067
:max_used_key_length(0),
1071
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, TABLE *table, uint key_nr,
1072
bool no_alloc, MEM_ROOT *parent_alloc,
1074
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1076
my_bitmap_map *bitmap;
1078
in_ror_merged_scan= 0;
1082
key_part_info= head->key_info[index].key_part;
1083
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1085
/* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1086
mrr_buf_size= thd->variables.read_rnd_buff_size;
1089
if (!no_alloc && !parent_alloc)
1091
// Allocates everything through the internal memroot
1092
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1093
thd->mem_root= &alloc;
1096
bzero((char*) &alloc,sizeof(alloc));
1098
record= head->record[0];
1099
save_read_set= head->read_set;
1100
save_write_set= head->write_set;
1102
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1103
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1106
column_bitmap.bitmap= 0;
1110
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1115
int QUICK_RANGE_SELECT::init()
1117
if (file->inited != handler::NONE)
1118
file->ha_index_or_rnd_end();
1119
return(file->ha_index_init(index, 1));
1123
void QUICK_RANGE_SELECT::range_end()
1125
if (file->inited != handler::NONE)
1126
file->ha_index_or_rnd_end();
1130
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1134
/* file is NULL for CPK scan on covering ROR-intersection */
1141
file->extra(HA_EXTRA_NO_KEYREAD);
1145
file->ha_external_lock(current_thd, F_UNLCK);
1150
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1151
free_root(&alloc,MYF(0));
1152
my_free((char*) column_bitmap.bitmap, MYF(MY_ALLOW_ZERO_PTR));
1154
head->column_bitmaps_set(save_read_set, save_write_set);
1155
x_free(mrr_buf_desc);
1160
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1162
:pk_quick_select(NULL), thd(thd_param)
1166
bzero(&read_record, sizeof(read_record));
1167
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1171
int QUICK_INDEX_MERGE_SELECT::init()
1176
int QUICK_INDEX_MERGE_SELECT::reset()
1178
return(read_keys_and_merge());
1182
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1185
Save quick_select that does scan on clustered primary key as it will be
1186
processed separately.
1188
if (head->file->primary_key_is_clustered() &&
1189
quick_sel_range->index == head->s->primary_key)
1190
pk_quick_select= quick_sel_range;
1192
return quick_selects.push_back(quick_sel_range);
1196
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1198
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1199
QUICK_RANGE_SELECT* quick;
1201
while ((quick= quick_it++))
1203
quick_selects.delete_elements();
1204
delete pk_quick_select;
1205
free_root(&alloc,MYF(0));
1210
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1212
bool retrieve_full_rows,
1213
MEM_ROOT *parent_alloc)
1214
: cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
1219
record= head->record[0];
1221
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1223
bzero(&alloc, sizeof(MEM_ROOT));
1224
last_rowid= (uchar*) alloc_root(parent_alloc? parent_alloc : &alloc,
1225
head->file->ref_length);
1230
Do post-constructor initialization.
1232
QUICK_ROR_INTERSECT_SELECT::init()
1239
int QUICK_ROR_INTERSECT_SELECT::init()
1241
/* Check if last_rowid was successfully allocated in ctor */
1242
return(!last_rowid);
1247
Initialize this quick select to be a ROR-merged scan.
1250
QUICK_RANGE_SELECT::init_ror_merged_scan()
1251
reuse_handler If true, use head->file, otherwise create a separate
1255
This function creates and prepares for subsequent use a separate handler
1256
object if it can't reuse head->file. The reason for this is that during
1257
ROR-merge several key scans are performed simultaneously, and a single
1258
handler is only capable of preserving context of a single key scan.
1260
In ROR-merge the quick select doing merge does full records retrieval,
1261
merged quick selects read only keys.
1264
0 ROR child scan initialized, ok to use.
1268
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1270
handler *save_file= file, *org_file;
1273
in_ror_merged_scan= 1;
1276
if (init() || reset())
1280
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1284
/* Create a separate handler object for this quick select */
1287
/* already have own 'handler' object. */
1292
if (!(file= head->file->clone(thd->mem_root)))
1295
Manually set the error flag. Note: there seems to be quite a few
1296
places where a failure could cause the server to "hang" the client by
1297
sending no response to a query. ATM those are not real errors because
1298
the storage engine calls in question happen to never fail with the
1299
existing storage engines.
1301
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1302
/* Caller will free the memory */
1303
goto failure; /* purecov: inspected */
1306
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1308
if (file->ha_external_lock(thd, F_RDLCK))
1311
if (init() || reset())
1313
file->ha_external_lock(thd, F_UNLCK);
1318
last_rowid= file->ref;
1322
We are only going to read key fields and call position() on 'file'
1323
The following sets head->tmp_set to only use this key and then updates
1324
head->read_set and head->write_set to use this bitmap.
1325
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1327
org_file= head->file;
1329
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1330
if (!head->no_keyread)
1333
head->mark_columns_used_by_index(index);
1335
head->prepare_for_position();
1336
head->file= org_file;
1337
bitmap_copy(&column_bitmap, head->read_set);
1338
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1343
head->column_bitmaps_set(save_read_set, save_write_set);
1351
Initialize this quick select to be a part of a ROR-merged scan.
1353
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1354
reuse_handler If true, use head->file, otherwise create separate
1360
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1362
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1363
QUICK_RANGE_SELECT* quick;
1365
/* Initialize all merged "children" quick selects */
1366
assert(!need_to_fetch_row || reuse_handler);
1367
if (!need_to_fetch_row && reuse_handler)
1371
There is no use of this->file. Use it for the first of merged range
1374
if (quick->init_ror_merged_scan(true))
1376
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1378
while ((quick= quick_it++))
1380
if (quick->init_ror_merged_scan(false))
1382
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1383
/* All merged scans share the same record buffer in intersection. */
1384
quick->record= head->record[0];
1387
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1396
Initialize quick select for row retrieval.
1404
int QUICK_ROR_INTERSECT_SELECT::reset()
1406
if (!scans_inited && init_ror_merged_scan(true))
1409
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1410
QUICK_RANGE_SELECT *quick;
1411
while ((quick= it++))
1418
Add a merged quick select to this ROR-intersection quick select.
1421
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1422
quick Quick select to be added. The quick select must return
1423
rows in rowid order.
1425
This call can only be made before init() is called.
1433
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1435
return quick_selects.push_back(quick);
1438
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1440
quick_selects.delete_elements();
1442
free_root(&alloc,MYF(0));
1443
if (need_to_fetch_row && head->file->inited != handler::NONE)
1444
head->file->ha_rnd_end();
1449
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1451
: thd(thd_param), scans_inited(false)
1455
rowid_length= table->file->ref_length;
1456
record= head->record[0];
1457
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1458
thd_param->mem_root= &alloc;
1463
Do post-constructor initialization.
1465
QUICK_ROR_UNION_SELECT::init()
1472
int QUICK_ROR_UNION_SELECT::init()
1474
if (init_queue(&queue, quick_selects.elements, 0,
1475
false , QUICK_ROR_UNION_SELECT::queue_cmp,
1478
bzero(&queue, sizeof(QUEUE));
1482
if (!(cur_rowid= (uchar*) alloc_root(&alloc, 2*head->file->ref_length)))
1484
prev_rowid= cur_rowid + head->file->ref_length;
1490
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1494
QUICK_ROR_UNION_SELECT::queue_cmp()
1495
arg Pointer to QUICK_ROR_UNION_SELECT
1496
val1 First merged select
1497
val2 Second merged select
1500
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, uchar *val1, uchar *val2)
1502
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1503
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1504
((QUICK_SELECT_I*)val2)->last_rowid);
1509
Initialize quick select for row retrieval.
1518
int QUICK_ROR_UNION_SELECT::reset()
1520
QUICK_SELECT_I *quick;
1522
have_prev_rowid= false;
1525
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1526
while ((quick= it++))
1528
if (quick->init_ror_merged_scan(false))
1533
queue_remove_all(&queue);
1535
Initialize scans for merged quick selects and put all merged quick
1536
selects into the queue.
1538
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1539
while ((quick= it++))
1543
if ((error= quick->get_next()))
1545
if (error == HA_ERR_END_OF_FILE)
1549
quick->save_last_pos();
1550
queue_insert(&queue, (uchar*)quick);
1553
if (head->file->ha_rnd_init(1))
1563
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1565
return quick_selects.push_back(quick_sel_range);
1568
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1570
delete_queue(&queue);
1571
quick_selects.delete_elements();
1572
if (head->file->inited != handler::NONE)
1573
head->file->ha_rnd_end();
1574
free_root(&alloc,MYF(0));
1579
QUICK_RANGE::QUICK_RANGE()
1580
:min_key(0),max_key(0),min_length(0),max_length(0),
1581
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1582
min_keypart_map(0), max_keypart_map(0)
1585
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1588
min_flag=arg.min_flag;
1589
max_flag=arg.max_flag;
1590
maybe_flag=arg.maybe_flag;
1591
maybe_null=arg.maybe_null;
1594
min_value=arg.min_value;
1595
max_value=arg.max_value;
1596
next_key_part=arg.next_key_part;
1597
use_count=1; elements=1;
1601
inline void SEL_ARG::make_root()
1603
left=right= &null_element;
1606
use_count=0; elements=1;
1609
SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg,
1610
const uchar *max_value_arg)
1611
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1612
elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
1613
max_value((uchar*) max_value_arg), next(0),prev(0),
1614
next_key_part(0),color(BLACK),type(KEY_RANGE)
1616
left=right= &null_element;
1619
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1620
uchar *min_value_, uchar *max_value_,
1621
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1622
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1623
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1624
field(field_), min_value(min_value_), max_value(max_value_),
1625
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1627
left=right= &null_element;
1630
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1635
/* Bail out if we have already generated too many SEL_ARGs */
1636
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1639
if (type != KEY_RANGE)
1641
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1642
return 0; // out of memory
1643
tmp->prev= *next_arg; // Link into next/prev chain
1644
(*next_arg)->next=tmp;
1649
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1650
min_flag, max_flag, maybe_flag)))
1652
tmp->parent=new_parent;
1653
tmp->next_key_part=next_key_part;
1654
if (left != &null_element)
1655
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1658
tmp->prev= *next_arg; // Link into next/prev chain
1659
(*next_arg)->next=tmp;
1662
if (right != &null_element)
1663
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1666
increment_use_count(1);
1668
tmp->elements= this->elements;
1672
SEL_ARG *SEL_ARG::first()
1674
SEL_ARG *next_arg=this;
1675
if (!next_arg->left)
1676
return 0; // MAYBE_KEY
1677
while (next_arg->left != &null_element)
1678
next_arg=next_arg->left;
1682
SEL_ARG *SEL_ARG::last()
1684
SEL_ARG *next_arg=this;
1685
if (!next_arg->right)
1686
return 0; // MAYBE_KEY
1687
while (next_arg->right != &null_element)
1688
next_arg=next_arg->right;
1694
Check if a compare is ok, when one takes ranges in account
1695
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1698
static int sel_cmp(Field *field, uchar *a, uchar *b, uint8_t a_flag,
1702
/* First check if there was a compare to a min or max element */
1703
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1705
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1706
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1708
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1710
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1711
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1713
if (field->real_maybe_null()) // If null is part of key
1720
goto end; // NULL where equal
1721
a++; b++; // Skip NULL marker
1723
cmp=field->key_cmp(a , b);
1724
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1726
// Check if the compared equal arguments was defined with open/closed range
1728
if (a_flag & (NEAR_MIN | NEAR_MAX))
1730
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1732
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1733
return (a_flag & NEAR_MIN) ? 2 : -2;
1734
return (a_flag & NEAR_MIN) ? 1 : -1;
1736
if (b_flag & (NEAR_MIN | NEAR_MAX))
1737
return (b_flag & NEAR_MIN) ? -2 : 2;
1738
return 0; // The elements where equal
1742
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1744
SEL_ARG tmp_link,*next_arg,*root;
1745
next_arg= &tmp_link;
1746
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1748
next_arg->next=0; // Fix last link
1749
tmp_link.next->prev=0; // Fix first link
1750
if (root) // If not OOM
1847
Table rows retrieval plan. Range optimizer creates QUICK_SELECT_I-derived
1848
objects from table read plans.
1850
class TABLE_READ_PLAN
1854
Plan read cost, with or without cost of full row retrieval, depending
1855
on plan creation parameters.
1858
ha_rows records; /* estimate of #rows to be examined */
1861
If true, the scan returns rows in rowid order. This is used only for
1862
scans that can be both ROR and non-ROR.
1867
Create quick select for this plan.
1870
param Parameter from test_quick_select
1871
retrieve_full_rows If true, created quick select will do full record
1873
parent_alloc Memory pool to use, if any.
1876
retrieve_full_rows is ignored by some implementations.
1879
created quick select
1882
virtual QUICK_SELECT_I *make_quick(PARAM *param,
1883
bool retrieve_full_rows,
1884
MEM_ROOT *parent_alloc=NULL) = 0;
1886
/* Table read plans are allocated on MEM_ROOT and are never deleted */
1887
static void *operator new(size_t size, MEM_ROOT *mem_root)
1888
{ return (void*) alloc_root(mem_root, (uint) size); }
1889
static void operator delete(void *ptr __attribute__((unused)),
1890
size_t size __attribute__((unused)))
1891
{ TRASH(ptr, size); }
1892
static void operator delete(void *ptr __attribute__((unused)),
1893
MEM_ROOT *mem_root __attribute__((unused)))
1894
{ /* Never called */ }
1895
virtual ~TABLE_READ_PLAN() {} /* Remove gcc warning */
1899
class TRP_ROR_INTERSECT;
1900
class TRP_ROR_UNION;
1901
class TRP_INDEX_MERGE;
1905
Plan for a QUICK_RANGE_SELECT scan.
1906
TRP_RANGE::make_quick ignores retrieve_full_rows parameter because
1907
QUICK_RANGE_SELECT doesn't distinguish between 'index only' scans and full
1908
record retrieval scans.
1911
class TRP_RANGE : public TABLE_READ_PLAN
1914
SEL_ARG *key; /* set of intervals to be used in "range" method retrieval */
1915
uint key_idx; /* key number in PARAM::key */
1919
TRP_RANGE(SEL_ARG *key_arg, uint idx_arg, uint mrr_flags_arg)
1920
: key(key_arg), key_idx(idx_arg), mrr_flags(mrr_flags_arg)
1922
virtual ~TRP_RANGE() {} /* Remove gcc warning */
1924
QUICK_SELECT_I *make_quick(PARAM *param,
1925
bool retrieve_full_rows __attribute__((unused)),
1926
MEM_ROOT *parent_alloc)
1928
QUICK_RANGE_SELECT *quick;
1929
if ((quick= get_quick_select(param, key_idx, key, mrr_flags, mrr_buf_size,
1932
quick->records= records;
1933
quick->read_time= read_cost;
1940
/* Plan for QUICK_ROR_INTERSECT_SELECT scan. */
1942
class TRP_ROR_INTERSECT : public TABLE_READ_PLAN
1945
TRP_ROR_INTERSECT() {} /* Remove gcc warning */
1946
virtual ~TRP_ROR_INTERSECT() {} /* Remove gcc warning */
1947
QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows,
1948
MEM_ROOT *parent_alloc);
1950
/* Array of pointers to ROR range scans used in this intersection */
1951
struct st_ror_scan_info **first_scan;
1952
struct st_ror_scan_info **last_scan; /* End of the above array */
1953
struct st_ror_scan_info *cpk_scan; /* Clustered PK scan, if there is one */
1954
bool is_covering; /* true if no row retrieval phase is necessary */
1955
double index_scan_costs; /* SUM(cost(index_scan)) */
1960
Plan for QUICK_ROR_UNION_SELECT scan.
1961
QUICK_ROR_UNION_SELECT always retrieves full rows, so retrieve_full_rows
1962
is ignored by make_quick.
1965
class TRP_ROR_UNION : public TABLE_READ_PLAN
1968
TRP_ROR_UNION() {} /* Remove gcc warning */
1969
virtual ~TRP_ROR_UNION() {} /* Remove gcc warning */
1970
QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows,
1971
MEM_ROOT *parent_alloc);
1972
TABLE_READ_PLAN **first_ror; /* array of ptrs to plans for merged scans */
1973
TABLE_READ_PLAN **last_ror; /* end of the above array */
1978
Plan for QUICK_INDEX_MERGE_SELECT scan.
1979
QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
1980
is ignored by make_quick.
1983
class TRP_INDEX_MERGE : public TABLE_READ_PLAN
1986
TRP_INDEX_MERGE() {} /* Remove gcc warning */
1987
virtual ~TRP_INDEX_MERGE() {} /* Remove gcc warning */
1988
QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows,
1989
MEM_ROOT *parent_alloc);
1990
TRP_RANGE **range_scans; /* array of ptrs to plans of merged scans */
1991
TRP_RANGE **range_scans_end; /* end of the array */
1996
Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
1999
class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN
2002
bool have_min, have_max;
2003
KEY_PART_INFO *min_max_arg_part;
2004
uint group_prefix_len;
2005
uint used_key_parts;
2006
uint group_key_parts;
2010
uchar key_infix[MAX_KEY_LENGTH];
2011
SEL_TREE *range_tree; /* Represents all range predicates in the query. */
2012
SEL_ARG *index_tree; /* The SEL_ARG sub-tree corresponding to index_info. */
2013
uint param_idx; /* Index of used key in param->key. */
2014
/* Number of records selected by the ranges in index_tree. */
2016
ha_rows quick_prefix_records;
2018
TRP_GROUP_MIN_MAX(bool have_min_arg, bool have_max_arg,
2019
KEY_PART_INFO *min_max_arg_part_arg,
2020
uint group_prefix_len_arg, uint used_key_parts_arg,
2021
uint group_key_parts_arg, KEY *index_info_arg,
2022
uint index_arg, uint key_infix_len_arg,
2023
uchar *key_infix_arg,
2024
SEL_TREE *tree_arg, SEL_ARG *index_tree_arg,
2025
uint param_idx_arg, ha_rows quick_prefix_records_arg)
2026
: have_min(have_min_arg), have_max(have_max_arg),
2027
min_max_arg_part(min_max_arg_part_arg),
2028
group_prefix_len(group_prefix_len_arg), used_key_parts(used_key_parts_arg),
2029
group_key_parts(group_key_parts_arg), index_info(index_info_arg),
2030
index(index_arg), key_infix_len(key_infix_len_arg), range_tree(tree_arg),
2031
index_tree(index_tree_arg), param_idx(param_idx_arg),
2032
quick_prefix_records(quick_prefix_records_arg)
2035
memcpy(this->key_infix, key_infix_arg, key_infix_len);
2037
virtual ~TRP_GROUP_MIN_MAX() {} /* Remove gcc warning */
2039
QUICK_SELECT_I *make_quick(PARAM *param, bool retrieve_full_rows,
2040
MEM_ROOT *parent_alloc);
788
2045
Fill param->needed_fields with bitmap of fields used in the query.
4064
5162
if (key2->use_count == 0 || key1->elements > key2->elements)
4066
std::swap(key1,key2);
5164
swap_variables(SEL_ARG *,key1,key2);
4068
5166
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
4069
5167
return 0; // OOM
4072
5170
// Add tree at key2 to tree at key1
4073
bool key2_shared= key2->use_count != 0;
4074
key1->maybe_flag|= key2->maybe_flag;
5171
bool key2_shared=key2->use_count != 0;
5172
key1->maybe_flag|=key2->maybe_flag;
4076
5174
for (key2=key2->first(); key2; )
4078
optimizer::SEL_ARG *tmp= key1->find_range(key2); // Find key1.min <= key2.min
5176
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
4083
tmp=key1->first(); // tmp.min > key2.min
5181
tmp=key1->first(); // tmp.min > key2.min
4086
5184
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
4087
5185
{ // Found tmp.max < key2.min
4088
optimizer::SEL_ARG *next= tmp->next;
5186
SEL_ARG *next=tmp->next;
4089
5187
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
5189
// Join near ranges like tmp.max < 0 and key2.min >= 0
5190
SEL_ARG *key2_next=key2->next;
5193
if (!(key2=new SEL_ARG(*key2)))
5194
return 0; // out of memory
5195
key2->increment_use_count(key1->use_count+1);
5196
key2->next=key2_next; // New copy of key2
5198
key2->copy_min(tmp);
5199
if (!(key1=key1->tree_delete(tmp)))
5200
{ // Only one key in tree
4109
if (! (tmp= next)) // tmp.min > key2.min
4110
break; // Copy rest of key2
5207
if (!(tmp=next)) // tmp.min > key2.min
5208
break; // Copy rest of key2
4113
5211
{ // tmp.min > key2.min
4115
if ((tmp_cmp= tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5213
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
5215
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5216
{ // ranges are connected
5217
tmp->copy_min_to_min(key2);
5218
key1->merge_flags(key2);
5219
if (tmp->min_flag & NO_MIN_RANGE &&
5220
tmp->max_flag & NO_MAX_RANGE)
5222
if (key1->maybe_flag)
5223
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5226
key2->increment_use_count(-1); // Free not used tree
5232
SEL_ARG *next=key2->next; // Keys are not overlapping
5235
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5238
key1=key1->insert(cpy);
5239
key2->increment_use_count(key1->use_count+1);
5242
key1=key1->insert(key2); // Will destroy key2_root
4151
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5249
// tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges)
4152
5250
if (eq_tree(tmp->next_key_part,key2->next_key_part))
4154
5252
if (tmp->is_same(key2))
4156
tmp->merge_flags(key2); // Copy maybe flags
4157
key2->increment_use_count(-1); // Free not used tree
5254
tmp->merge_flags(key2); // Copy maybe flags
5255
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);
5260
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5261
eq_tree(last->next->next_key_part,key2->next_key_part))
5265
key1=key1->tree_delete(save);
4169
5267
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);
5268
if (last->copy_min(key2) || last->copy_max(key2))
5271
for (; key2 ; key2=key2->next)
5272
key2->increment_use_count(-1); // Free not used tree
5273
if (key1->maybe_flag)
5274
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
4184
5282
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
4185
5283
{ // tmp.min <= x < key2.min
4186
optimizer::SEL_ARG *new_arg= tmp->clone_first(key2);
5284
SEL_ARG *new_arg=tmp->clone_first(key2);
4189
5287
if ((new_arg->next_key_part= key1->next_key_part))
4190
new_arg->increment_use_count(key1->use_count+1);
5288
new_arg->increment_use_count(key1->use_count+1);
4191
5289
tmp->copy_min_to_min(key2);
4192
key1= key1->insert(new_arg);
5290
key1=key1->insert(new_arg);
4195
5293
// tmp.min >= key2.min && tmp.min <= key2.max
4196
optimizer::SEL_ARG key(*key2); // Get copy we can modify
5294
SEL_ARG key(*key2); // Get copy we can modify
4199
5297
if (tmp->cmp_min_to_min(&key) > 0)
4200
5298
{ // 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);
5299
SEL_ARG *new_arg=key.clone_first(tmp);
5302
if ((new_arg->next_key_part=key.next_key_part))
5303
new_arg->increment_use_count(key1->use_count+1);
5304
key1=key1->insert(new_arg);
4208
5306
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
4209
5307
{ // 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);
5308
tmp->maybe_flag|= key.maybe_flag;
5309
key.increment_use_count(key1->use_count+1);
5310
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5311
if (!cmp) // Key2 is ready
5313
key.copy_max_to_min(tmp);
5314
if (!(tmp=tmp->next))
5316
SEL_ARG *tmp2= new SEL_ARG(key);
5319
key1=key1->insert(tmp2);
5323
if (tmp->cmp_min_to_max(&key) > 0)
5325
SEL_ARG *tmp2= new SEL_ARG(key);
5328
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);
5334
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5337
tmp->copy_max_to_min(&key);
5338
tmp->increment_use_count(key1->use_count+1);
5339
/* Increment key count as it may be used for next loop */
5340
key.increment_use_count(1);
5341
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5342
key1=key1->insert(new_arg);
4254
optimizer::SEL_ARG *next= key2->next;
5352
SEL_ARG *next=key2->next;
4255
5353
if (key2_shared)
4257
optimizer::SEL_ARG *tmp= new optimizer::SEL_ARG(*key2); // Must make copy
5355
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
4260
5358
key2->increment_use_count(key1->use_count+1);
4261
key1= key1->insert(tmp);
5359
key1=key1->insert(tmp);
4264
key1= key1->insert(key2); // Will destroy key2_root
5362
key1=key1->insert(key2); // Will destroy key2_root
4267
5365
key1->use_count++;
4272
5370
/* Compare if two trees are equal */
4273
static bool eq_tree(optimizer::SEL_ARG *a, optimizer::SEL_ARG *b)
5372
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)
5376
if (!a || !b || !a->is_same(b))
5378
if (a->left != &null_element && b->left != &null_element)
5380
if (!eq_tree(a->left,b->left))
5383
else if (a->left != &null_element || b->left != &null_element)
5385
if (a->right != &null_element && b->right != &null_element)
5387
if (!eq_tree(a->right,b->right))
5390
else if (a->right != &null_element || b->right != &null_element)
4305
5392
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))
5394
if (!a->next_key_part != !b->next_key_part ||
5395
!eq_tree(a->next_key_part, b->next_key_part))
5403
SEL_ARG::insert(SEL_ARG *key)
5405
SEL_ARG *element, **par= NULL, *last_element= NULL;
5407
for (element= this; element != &null_element ; )
5409
last_element=element;
5410
if (key->cmp_min_to_min(element) > 0)
5412
par= &element->right; element= element->right;
5416
par = &element->left; element= element->left;
5420
key->parent=last_element;
5422
if (par == &last_element->left)
5424
key->next=last_element;
5425
if ((key->prev=last_element->prev))
5426
key->prev->next=key;
5427
last_element->prev=key;
5431
if ((key->next=last_element->next))
5432
key->next->prev=key;
5433
key->prev=last_element;
5434
last_element->next=key;
5436
key->left=key->right= &null_element;
5437
SEL_ARG *root=rb_insert(key); // rebalance tree
5438
root->use_count=this->use_count; // copy root info
5439
root->elements= this->elements+1;
5440
root->maybe_flag=this->maybe_flag;
5446
** Find best key with min <= given key
5447
** Because the call context this should never return 0 to get_range
5451
SEL_ARG::find_range(SEL_ARG *key)
5453
SEL_ARG *element=this,*found=0;
5457
if (element == &null_element)
5459
int cmp=element->cmp_min_to_min(key);
5465
element=element->right;
5468
element=element->left;
5474
Remove a element from the tree
5478
key Key that is to be deleted from tree (this)
5481
This also frees all sub trees that is used by the element
5484
root of new tree (with key deleted)
5488
SEL_ARG::tree_delete(SEL_ARG *key)
5490
enum leaf_color remove_color;
5491
SEL_ARG *root,*nod,**par,*fix_par;
5496
/* Unlink from list */
5498
key->prev->next=key->next;
5500
key->next->prev=key->prev;
5501
key->increment_use_count(-1);
5505
par=key->parent_ptr();
5507
if (key->left == &null_element)
5509
*par=nod=key->right;
5510
fix_par=key->parent;
5511
if (nod != &null_element)
5512
nod->parent=fix_par;
5513
remove_color= key->color;
5515
else if (key->right == &null_element)
5517
*par= nod=key->left;
5518
nod->parent=fix_par=key->parent;
5519
remove_color= key->color;
5523
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5524
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5525
fix_par=tmp->parent;
5526
if (nod != &null_element)
5527
nod->parent=fix_par;
5528
remove_color= tmp->color;
5530
tmp->parent=key->parent; // Move node in place of key
5531
(tmp->left=key->left)->parent=tmp;
5532
if ((tmp->right=key->right) != &null_element)
5533
tmp->right->parent=tmp;
5534
tmp->color=key->color;
5536
if (fix_par == key) // key->right == key->next
5537
fix_par=tmp; // new parent of nod
5540
if (root == &null_element)
5541
return(0); // Maybe root later
5542
if (remove_color == BLACK)
5543
root=rb_delete_fixup(root,nod,fix_par);
5544
test_rb_tree(root,root->parent);
5546
root->use_count=this->use_count; // Fix root counters
5547
root->elements=this->elements-1;
5548
root->maybe_flag=this->maybe_flag;
5553
/* Functions to fix up the tree after insert and delete */
5555
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5557
SEL_ARG *y=leaf->right;
5558
leaf->right=y->left;
5559
if (y->left != &null_element)
5560
y->left->parent=leaf;
5561
if (!(y->parent=leaf->parent))
5564
*leaf->parent_ptr()=y;
5569
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5571
SEL_ARG *y=leaf->left;
5572
leaf->left=y->right;
5573
if (y->right != &null_element)
5574
y->right->parent=leaf;
5575
if (!(y->parent=leaf->parent))
5578
*leaf->parent_ptr()=y;
5585
SEL_ARG::rb_insert(SEL_ARG *leaf)
5587
SEL_ARG *y,*par,*par2,*root;
5588
root= this; root->parent= 0;
5591
while (leaf != root && (par= leaf->parent)->color == RED)
5592
{ // This can't be root or 1 level under
5593
if (par == (par2= leaf->parent->parent)->left)
5596
if (y->color == RED)
5601
leaf->color=RED; /* And the loop continues */
5605
if (leaf == par->right)
5607
left_rotate(&root,leaf->parent);
5608
par=leaf; /* leaf is now parent to old leaf */
5612
right_rotate(&root,par2);
5619
if (y->color == RED)
5624
leaf->color=RED; /* And the loop continues */
5628
if (leaf == par->left)
5630
right_rotate(&root,par);
5635
left_rotate(&root,par2);
5641
test_rb_tree(root,root->parent);
5646
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5652
while (x != root && x->color == SEL_ARG::BLACK)
5657
if (w->color == SEL_ARG::RED)
5659
w->color=SEL_ARG::BLACK;
5660
par->color=SEL_ARG::RED;
5661
left_rotate(&root,par);
5664
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5666
w->color=SEL_ARG::RED;
5671
if (w->right->color == SEL_ARG::BLACK)
5673
w->left->color=SEL_ARG::BLACK;
5674
w->color=SEL_ARG::RED;
5675
right_rotate(&root,w);
5678
w->color=par->color;
5679
par->color=SEL_ARG::BLACK;
5680
w->right->color=SEL_ARG::BLACK;
5681
left_rotate(&root,par);
5689
if (w->color == SEL_ARG::RED)
5691
w->color=SEL_ARG::BLACK;
5692
par->color=SEL_ARG::RED;
5693
right_rotate(&root,par);
5696
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5698
w->color=SEL_ARG::RED;
5703
if (w->left->color == SEL_ARG::BLACK)
5705
w->right->color=SEL_ARG::BLACK;
5706
w->color=SEL_ARG::RED;
5707
left_rotate(&root,w);
5710
w->color=par->color;
5711
par->color=SEL_ARG::BLACK;
5712
w->left->color=SEL_ARG::BLACK;
5713
right_rotate(&root,par);
5720
x->color=SEL_ARG::BLACK;
5725
/* Test that the properties for a red-black tree hold */
5728
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5730
int count_l,count_r;
5732
if (element == &null_element)
5733
return 0; // Found end of tree
5734
if (element->parent != parent)
5736
sql_print_error("Wrong tree: Parent doesn't point at parent");
5739
if (element->color == SEL_ARG::RED &&
5740
(element->left->color == SEL_ARG::RED ||
5741
element->right->color == SEL_ARG::RED))
5743
sql_print_error("Wrong tree: Found two red in a row");
5746
if (element->left == element->right && element->left != &null_element)
5748
sql_print_error("Wrong tree: Found right == left");
5751
count_l=test_rb_tree(element->left,element);
5752
count_r=test_rb_tree(element->right,element);
5753
if (count_l >= 0 && count_r >= 0)
5755
if (count_l == count_r)
5756
return count_l+(element->color == SEL_ARG::BLACK);
5757
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5760
return -1; // Error, no more warnings
5765
Count how many times SEL_ARG graph "root" refers to its part "key"
5768
count_key_part_usage()
5769
root An RB-Root node in a SEL_ARG graph.
5770
key Another RB-Root node in that SEL_ARG graph.
5773
The passed "root" node may refer to "key" node via root->next_key_part,
5776
This function counts how many times the node "key" is referred (via
5777
SEL_ARG::next_key_part) by
5778
- intervals of RB-tree pointed by "root",
5779
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5780
intervals of RB-tree pointed by "root",
5783
Here is an example (horizontal links represent next_key_part pointers,
5784
vertical links - next/prev prev pointers):
5787
|root|-----------------+
5791
+----+ +---+ $ | +---+ Here the return value
5792
| |- ... -| |---$-+--+->|key| will be 4.
5793
+----+ +---+ $ | | +---+
5798
| |---| |---------+ |
5805
Number of links to "key" from nodes reachable from "root".
5808
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5811
for (root=root->first(); root ; root=root->next)
5813
if (root->next_key_part)
5815
if (root->next_key_part == key)
5817
if (root->next_key_part->part < key->part)
5818
count+=count_key_part_usage(root->next_key_part,key);
5826
Check if SEL_ARG::use_count value is correct
5829
SEL_ARG::test_use_count()
5830
root The root node of the SEL_ARG graph (an RB-tree root node that
5831
has the least value of sel_arg->part in the entire graph, and
5832
thus is the "origin" of the graph)
5835
Check if SEL_ARG::use_count value is correct. See the definition of
5836
use_count for what is "correct".
5839
void SEL_ARG::test_use_count(SEL_ARG *root)
5842
if (this == root && use_count != 1)
5844
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5847
if (this->type != SEL_ARG::KEY_RANGE)
5849
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5852
if (pos->next_key_part)
5854
ulong count=count_key_part_usage(root,pos->next_key_part);
5855
if (count > pos->next_key_part->use_count)
5857
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5858
"should be %lu", (long unsigned int)pos,
5859
pos->next_key_part->use_count, count);
5862
pos->next_key_part->test_use_count(root);
5865
if (e_count != elements)
5866
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5867
e_count, elements, (long unsigned int) this);
4316
5872
/****************************************************************************
4317
5873
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
4318
5874
****************************************************************************/
4320
5876
/* MRR range sequence, SEL_ARG* implementation: stack entry */
4321
typedef struct st_range_seq_entry
5877
typedef struct st_range_seq_entry
4324
5880
Pointers in min and max keys. They point to right-after-end of key
4325
5881
images. The 0-th entry has these pointing to key tuple start.
4327
unsigned char *min_key, *max_key;
5883
uchar *min_key, *max_key;
4330
5886
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
4331
5887
min_key_flag may have NULL_RANGE set.
4333
uint32_t min_key_flag, max_key_flag;
5889
uint min_key_flag, max_key_flag;
4335
5891
/* Number of key parts */
4336
uint32_t min_key_parts, max_key_parts;
4337
optimizer::SEL_ARG *key_tree;
5892
uint min_key_parts, max_key_parts;
4338
5894
} RANGE_SEQ_ENTRY;
5132
Range sequence interface implementation for array<QuickRange>: initialize
6702
Perform key scans for all used indexes (except CPK), get rowids and merge
6703
them into an ordered non-recurrent sequence of rowids.
6705
The merge/duplicate removal is performed using Unique class. We put all
6706
rowids into Unique, get the sorted sequence and destroy the Unique.
6708
If table has a clustered primary key that covers all rows (true for bdb
6709
and innodb currently) and one of the index_merge scans is a scan on PK,
6710
then rows that will be retrieved by PK scan are not put into Unique and
6711
primary key scan is not performed here, it is performed later separately.
6718
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6720
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6721
QUICK_RANGE_SELECT* cur_quick;
6724
handler *file= head->file;
6726
file->extra(HA_EXTRA_KEYREAD);
6727
head->prepare_for_position();
6729
cur_quick_it.rewind();
6730
cur_quick= cur_quick_it++;
6731
assert(cur_quick != 0);
6734
We reuse the same instance of handler so we need to call both init and
6737
if (cur_quick->init() || cur_quick->reset())
6740
unique= new Unique(refpos_order_cmp, (void *)file,
6742
thd->variables.sortbuff_size);
6747
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6749
cur_quick->range_end();
6750
cur_quick= cur_quick_it++;
6754
if (cur_quick->file->inited != handler::NONE)
6755
cur_quick->file->ha_index_end();
6756
if (cur_quick->init() || cur_quick->reset())
6762
if (result != HA_ERR_END_OF_FILE)
6764
cur_quick->range_end();
6773
/* skip row if it will be retrieved by clustered PK scan */
6774
if (pk_quick_select && pk_quick_select->row_in_ranges())
6777
cur_quick->file->position(cur_quick->record);
6778
result= unique->unique_add((char*)cur_quick->file->ref);
6784
/* ok, all row ids are in Unique */
6785
result= unique->get(head);
6787
doing_pk_scan= false;
6788
/* index_merge currently doesn't support "using index" at all */
6789
file->extra(HA_EXTRA_NO_KEYREAD);
6790
/* start table scan */
6791
init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6797
Get next row for index_merge.
6799
The rows are read from
6800
1. rowids stored in Unique.
6801
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6802
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6805
int QUICK_INDEX_MERGE_SELECT::get_next()
6810
return(pk_quick_select->get_next());
6812
if ((result= read_record.read_record(&read_record)) == -1)
6814
result= HA_ERR_END_OF_FILE;
6815
end_read_record(&read_record);
6816
/* All rows from Unique have been retrieved, do a clustered PK scan */
6817
if (pk_quick_select)
6819
doing_pk_scan= true;
6820
if ((result= pk_quick_select->init()) ||
6821
(result= pk_quick_select->reset()))
6823
return(pk_quick_select->get_next());
6832
Retrieve next record.
6834
QUICK_ROR_INTERSECT_SELECT::get_next()
6837
Invariant on enter/exit: all intersected selects have retrieved all index
6838
records with rowid <= some_rowid_val and no intersected select has
6839
retrieved any index records with rowid > some_rowid_val.
6840
We start fresh and loop until we have retrieved the same rowid in each of
6841
the key scans or we got an error.
6843
If a Clustered PK scan is present, it is used only to check if row
6844
satisfies its condition (and never used for row retrieval).
6848
other - Error code if any error occurred.
6851
int QUICK_ROR_INTERSECT_SELECT::get_next()
6853
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6854
QUICK_RANGE_SELECT* quick;
6856
uint last_rowid_count=0;
6860
/* Get a rowid for first quick and save it as a 'candidate' */
6862
error= quick->get_next();
6865
while (!error && !cpk_quick->row_in_ranges())
6866
error= quick->get_next();
6871
quick->file->position(quick->record);
6872
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6873
last_rowid_count= 1;
6875
while (last_rowid_count < quick_selects.elements)
6877
if (!(quick= quick_it++))
6885
if ((error= quick->get_next()))
6887
quick->file->position(quick->record);
6888
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6891
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6894
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6897
while (!cpk_quick->row_in_ranges())
6899
if ((error= quick->get_next()))
6903
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6904
last_rowid_count= 1;
6908
/* current 'candidate' row confirmed by this select */
6913
/* We get here if we got the same row ref in all scans. */
6914
if (need_to_fetch_row)
6915
error= head->file->rnd_pos(head->record[0], last_rowid);
6916
} while (error == HA_ERR_RECORD_DELETED);
6922
Retrieve next record.
6924
QUICK_ROR_UNION_SELECT::get_next()
6927
Enter/exit invariant:
6928
For each quick select in the queue a {key,rowid} tuple has been
6929
retrieved but the corresponding row hasn't been passed to output.
6933
other - Error code if any error occurred.
6936
int QUICK_ROR_UNION_SELECT::get_next()
6939
QUICK_SELECT_I *quick;
6946
if (!queue.elements)
6947
return(HA_ERR_END_OF_FILE);
6948
/* Ok, we have a queue with >= 1 scans */
6950
quick= (QUICK_SELECT_I*)queue_top(&queue);
6951
memcpy(cur_rowid, quick->last_rowid, rowid_length);
6953
/* put into queue rowid from the same stream as top element */
6954
if ((error= quick->get_next()))
6956
if (error != HA_ERR_END_OF_FILE)
6958
queue_remove(&queue, 0);
6962
quick->save_last_pos();
6963
queue_replaced(&queue);
6966
if (!have_prev_rowid)
6968
/* No rows have been returned yet */
6970
have_prev_rowid= true;
6973
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
6977
cur_rowid= prev_rowid;
6980
error= head->file->rnd_pos(quick->record, prev_rowid);
6981
} while (error == HA_ERR_RECORD_DELETED);
6986
int QUICK_RANGE_SELECT::reset()
6991
HANDLER_BUFFER empty_buf;
6993
cur_range= (QUICK_RANGE**) ranges.buffer;
6995
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
6998
/* Allocate buffer if we need one but haven't allocated it yet */
6999
if (mrr_buf_size && !mrr_buf_desc)
7001
buf_size= mrr_buf_size;
7002
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7003
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7004
&mrange_buff, buf_size,
7007
/* Try to shrink the buffers until both are 0. */
7011
return(HA_ERR_OUT_OF_MEM);
7013
/* Initialize the handler buffer. */
7014
mrr_buf_desc->buffer= mrange_buff;
7015
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7016
mrr_buf_desc->end_of_used_area= mrange_buff;
7020
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7023
mrr_flags |= HA_MRR_SORTED;
7024
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7025
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7026
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7033
Range sequence interface implementation for array<QUICK_RANGE>: initialize
5135
7036
quick_range_seq_init()
5136
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7037
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
5137
7038
n_ranges Number of ranges in the sequence (ignored)
5138
flags MRR flags (currently not used)
7039
flags MRR flags (currently not used)
5141
7042
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)
7045
range_seq_t quick_range_seq_init(void *init_param,
7046
uint n_ranges __attribute__((unused)),
7047
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;
7049
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7050
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7051
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
5149
7052
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
5150
7053
quick->ranges.elements;
5151
7054
return &quick->qr_traversal_ctx;
5165
7068
1 No more ranges in the sequence
5167
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7071
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
5169
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7073
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
5171
7075
if (ctx->cur == ctx->last)
5172
7076
return 1; /* no more ranges */
5174
optimizer::QuickRange *cur= *(ctx->cur);
7078
QUICK_RANGE *cur= *(ctx->cur);
5175
7079
key_range *start_key= &range->start_key;
5176
key_range *end_key= &range->end_key;
7080
key_range *end_key= &range->end_key;
5178
start_key->key= cur->min_key;
7082
start_key->key= cur->min_key;
5179
7083
start_key->length= cur->min_length;
5180
7084
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;
7085
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7086
(cur->flag & EQ_RANGE) ?
7087
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7088
end_key->key= cur->max_key;
7089
end_key->length= cur->max_length;
5186
7090
end_key->keypart_map= cur->max_keypart_map;
5188
7092
We use HA_READ_AFTER_KEY here because if we are reading on a key
5189
7093
prefix. We want to find all keys with this prefix.
5191
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7095
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
5193
7097
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);
7104
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7107
mrr_persistent_flag_storage()
7108
seq Range sequence being traversed
7112
MRR/NDB implementation needs to store some bits for each range. This
7113
function returns a reference to the "range_flag" associated with the
7116
This function should be removed when we get a proper MRR/NDB
7120
Reference to range_flag associated with range number #idx
7123
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint idx)
7125
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7126
return ctx->first[idx]->flag;
7131
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7134
mrr_get_ptr_by_idx()
7135
seq Range sequence bening traversed
7136
idx Number of the range
7139
An extension of MRR range sequence interface needed by NDB: return the
7140
data associated with the given range.
7142
A proper MRR interface implementer is supposed to store and return
7143
range-associated data. NDB stores number of the range instead. So this
7144
is a helper function that translates range number to range associated
7147
This function does nothing, as currrently there is only one user of the
7148
MRR interface - the quick range select code, and this user doesn't need
7149
to use range-associated data.
7152
Reference to range-associated data
7155
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7156
uint idx __attribute__((unused)))
7164
Get next possible record using quick-struct.
7167
QUICK_RANGE_SELECT::get_next()
7170
Record is read into table->record[0]
7174
HA_ERR_END_OF_FILE No (more) rows in range
7178
int QUICK_RANGE_SELECT::get_next()
7181
if (in_ror_merged_scan)
7184
We don't need to signal the bitmap change as the bitmap is always the
7185
same for this head->file
7187
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7190
int result= file->multi_range_read_next(&dummy);
7192
if (in_ror_merged_scan)
7194
/* Restore bitmaps set on entry */
7195
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7202
Get the next record with a different prefix.
7205
QUICK_RANGE_SELECT::get_next_prefix()
7206
prefix_length length of cur_prefix
7207
cur_prefix prefix of a key to be searched for
7210
Each subsequent call to the method retrieves the first record that has a
7211
prefix with length prefix_length different from cur_prefix, such that the
7212
record with the new prefix is within the ranges described by
7213
this->ranges. The record found is stored into the buffer pointed by
7215
The method is useful for GROUP-BY queries with range conditions to
7216
discover the prefix of the next group that satisfies the range conditions.
7219
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7220
methods should be unified into a more general one to reduce code
7225
HA_ERR_END_OF_FILE if returned all keys
7226
other if some error occurred
7229
int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
7230
key_part_map keypart_map,
7236
key_range start_key, end_key;
7239
/* Read the next record in the same range with prefix after cur_prefix. */
7240
assert(cur_prefix != 0);
7241
result= file->index_read_map(record, cur_prefix, keypart_map,
7243
if (result || (file->compare_key(file->end_range) <= 0))
7247
uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7250
/* Ranges have already been used up before. None is left for read. */
7252
return(HA_ERR_END_OF_FILE);
7254
last_range= *(cur_range++);
7256
start_key.key= (const uchar*) last_range->min_key;
7257
start_key.length= min(last_range->min_length, prefix_length);
7258
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7259
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7260
(last_range->flag & EQ_RANGE) ?
7261
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7262
end_key.key= (const uchar*) last_range->max_key;
7263
end_key.length= min(last_range->max_length, prefix_length);
7264
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7266
We use READ_AFTER_KEY here because if we are reading on a key
7267
prefix we want to find all keys with this prefix
7269
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7272
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7273
last_range->max_keypart_map ? &end_key : 0,
7274
test(last_range->flag & EQ_RANGE),
7276
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7277
last_range= 0; // Stop searching
7279
if (result != HA_ERR_END_OF_FILE)
7281
last_range= 0; // No matching rows; go to next range
7287
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7290
It is assumed that currently a scan is being done on another index
7291
which reads all necessary parts of the index that is scanned by this
7293
The implementation does a binary search on sorted array of disjoint
7294
ranges, without taking size of range into account.
7296
This function is used to filter out clustered PK scan rows in
7297
index_merge quick select.
7300
true if current row will be retrieved by this quick select
7304
bool QUICK_RANGE_SELECT::row_in_ranges()
7308
uint max= ranges.elements - 1;
7309
uint mid= (max + min)/2;
7313
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7315
/* current row value > mid->max */
7320
mid= (min + max) / 2;
7322
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7323
return (!cmp_next(res) && !cmp_prev(res));
7327
This is a hack: we inherit from QUICK_SELECT so that we can use the
7328
get_next() interface, but we have to hold a pointer to the original
7329
QUICK_SELECT because its data are used all over the place. What
7330
should be done is to factor out the data that is needed into a base
7331
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7332
which handle the ranges and implement the get_next() function. But
7333
for now, this seems to work right at least.
7336
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7337
uint used_key_parts_arg __attribute__((unused)),
7338
bool *create_err __attribute__((unused)))
7339
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7343
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7344
QUICK_RANGE **end_range= pr + ranges.elements;
7345
for (; pr!=end_range; pr++)
7346
rev_ranges.push_front(*pr);
7348
/* Remove EQ_RANGE flag for keys that are not using the full key */
7349
for (r = rev_it++; r; r = rev_it++)
7351
if ((r->flag & EQ_RANGE) &&
7352
head->key_info[index].key_length != r->max_length)
7353
r->flag&= ~EQ_RANGE;
7356
q->dont_free=1; // Don't free shared mem
7361
int QUICK_SELECT_DESC::get_next()
7363
/* The max key is handled as follows:
7364
* - if there is NO_MAX_RANGE, start at the end and move backwards
7365
* - if it is an EQ_RANGE, which means that max key covers the entire
7366
* key, go directly to the key and read through it (sorting backwards is
7367
* same as sorting forwards)
7368
* - if it is NEAR_MAX, go to the key or next, step back once, and
7370
* - otherwise (not NEAR_MAX == include the key), go after the key,
7371
* step back once, and move backwards
7378
{ // Already read through key
7379
result = ((last_range->flag & EQ_RANGE)
7380
? file->index_next_same(record, last_range->min_key,
7381
last_range->min_length) :
7382
file->index_prev(record));
7385
if (cmp_prev(*rev_it.ref()) == 0)
7388
else if (result != HA_ERR_END_OF_FILE)
7392
if (!(last_range= rev_it++))
7393
return(HA_ERR_END_OF_FILE); // All ranges used
7395
if (last_range->flag & NO_MAX_RANGE) // Read last record
7398
if ((local_error=file->index_last(record)))
7399
return(local_error); // Empty table
7400
if (cmp_prev(last_range) == 0)
7402
last_range= 0; // No match; go to next range
7406
if (last_range->flag & EQ_RANGE)
7408
result = file->index_read_map(record, last_range->max_key,
7409
last_range->max_keypart_map,
7414
assert(last_range->flag & NEAR_MAX ||
7415
range_reads_after_key(last_range));
7416
result=file->index_read_map(record, last_range->max_key,
7417
last_range->max_keypart_map,
7418
((last_range->flag & NEAR_MAX) ?
7419
HA_READ_BEFORE_KEY :
7420
HA_READ_PREFIX_LAST_OR_PREV));
7424
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7426
last_range= 0; // Not found, to next range
7429
if (cmp_prev(last_range) == 0)
7431
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7432
last_range= 0; // Stop searching
7433
return(0); // Found key is in range
7435
last_range= 0; // To next range
7441
Compare if found key is over max-value
7442
Returns 0 if key <= range->max_key
7443
TODO: Figure out why can't this function be as simple as cmp_prev().
7446
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7448
if (range_arg->flag & NO_MAX_RANGE)
7449
return 0; /* key can't be to large */
7451
KEY_PART *key_part=key_parts;
7454
for (uchar *key=range_arg->max_key, *end=key+range_arg->max_length;
7456
key+= store_length, key_part++)
7459
store_length= key_part->store_length;
7460
if (key_part->null_bit)
7464
if (!key_part->field->is_null())
7468
else if (key_part->field->is_null())
7470
key++; // Skip null byte
7473
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7478
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7483
Returns 0 if found key is inside range (found key >= range->min_key).
7486
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7489
if (range_arg->flag & NO_MIN_RANGE)
7490
return 0; /* key can't be to small */
7492
cmp= key_cmp(key_part_info, range_arg->min_key,
7493
range_arg->min_length);
7494
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7496
return 1; // outside of range
7501
* true if this range will require using HA_READ_AFTER_KEY
7502
See comment in get_next() about this
7505
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7507
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7508
!(range_arg->flag & EQ_RANGE) ||
7509
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7513
void QUICK_RANGE_SELECT::add_info_string(String *str)
7515
KEY *key_info= head->key_info + index;
7516
str->append(key_info->name);
7519
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7521
QUICK_RANGE_SELECT *quick;
7523
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7524
str->append(STRING_WITH_LEN("sort_union("));
7525
while ((quick= it++))
7531
quick->add_info_string(str);
7533
if (pk_quick_select)
7536
pk_quick_select->add_info_string(str);
7541
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7544
QUICK_RANGE_SELECT *quick;
7545
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7546
str->append(STRING_WITH_LEN("intersect("));
7547
while ((quick= it++))
7549
KEY *key_info= head->key_info + quick->index;
7554
str->append(key_info->name);
7558
KEY *key_info= head->key_info + cpk_quick->index;
7560
str->append(key_info->name);
7565
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7568
QUICK_SELECT_I *quick;
7569
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7570
str->append(STRING_WITH_LEN("union("));
7571
while ((quick= it++))
7577
quick->add_info_string(str);
7583
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7584
String *used_lengths)
7588
KEY *key_info= head->key_info + index;
7589
key_names->append(key_info->name);
7590
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7591
used_lengths->append(buf, length);
7594
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7595
String *used_lengths)
7600
QUICK_RANGE_SELECT *quick;
7602
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7603
while ((quick= it++))
7609
key_names->append(',');
7610
used_lengths->append(',');
7613
KEY *key_info= head->key_info + quick->index;
7614
key_names->append(key_info->name);
7615
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7616
used_lengths->append(buf, length);
7618
if (pk_quick_select)
7620
KEY *key_info= head->key_info + pk_quick_select->index;
7621
key_names->append(',');
7622
key_names->append(key_info->name);
7623
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7624
used_lengths->append(',');
7625
used_lengths->append(buf, length);
7629
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7630
String *used_lengths)
7635
QUICK_RANGE_SELECT *quick;
7636
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7637
while ((quick= it++))
7639
KEY *key_info= head->key_info + quick->index;
7644
key_names->append(',');
7645
used_lengths->append(',');
7647
key_names->append(key_info->name);
7648
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7649
used_lengths->append(buf, length);
7654
KEY *key_info= head->key_info + cpk_quick->index;
7655
key_names->append(',');
7656
key_names->append(key_info->name);
7657
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7658
used_lengths->append(',');
7659
used_lengths->append(buf, length);
7663
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7664
String *used_lengths)
7667
QUICK_SELECT_I *quick;
7668
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7669
while ((quick= it++))
7675
used_lengths->append(',');
7676
key_names->append(',');
7678
quick->add_keys_and_lengths(key_names, used_lengths);
7683
/*******************************************************************************
7684
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7685
*******************************************************************************/
7687
static inline uint get_field_keypart(KEY *index, Field *field);
7688
static inline SEL_ARG * get_index_range_tree(uint index, SEL_TREE* range_tree,
7689
PARAM *param, uint *param_idx);
7690
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7691
KEY_PART_INFO *first_non_group_part,
7692
KEY_PART_INFO *min_max_arg_part,
7693
KEY_PART_INFO *last_part, THD *thd,
7694
uchar *key_infix, uint *key_infix_len,
7695
KEY_PART_INFO **first_non_infix_part);
7697
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7698
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,
7701
cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts,
7702
uint group_key_parts, SEL_TREE *range_tree,
7703
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7704
bool have_min, bool have_max,
7705
double *read_cost, ha_rows *records);
6342
8760
quick->update_key_stat();
6343
8761
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;
8768
Construct new quick select for group queries with min/max.
8771
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8772
table The table being accessed
8773
join Descriptor of the current query
8774
have_min true if the query selects a MIN function
8775
have_max true if the query selects a MAX function
8776
min_max_arg_part The only argument field of all MIN/MAX functions
8777
group_prefix_len Length of all key parts in the group prefix
8778
prefix_key_parts All key parts in the group prefix
8779
index_info The index chosen for data access
8780
use_index The id of index_info
8781
read_cost Cost of this access method
8782
records Number of records returned
8783
key_infix_len Length of the key infix appended to the group prefix
8784
key_infix Infix of constants from equality predicates
8785
parent_alloc Memory pool for this and quick_prefix_select data
8791
QUICK_GROUP_MIN_MAX_SELECT::
8792
QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join_arg, bool have_min_arg,
8794
KEY_PART_INFO *min_max_arg_part_arg,
8795
uint group_prefix_len_arg, uint group_key_parts_arg,
8796
uint used_key_parts_arg, KEY *index_info_arg,
8797
uint use_index, double read_cost_arg,
8798
ha_rows records_arg, uint key_infix_len_arg,
8799
uchar *key_infix_arg, MEM_ROOT *parent_alloc)
8800
:join(join_arg), index_info(index_info_arg),
8801
group_prefix_len(group_prefix_len_arg),
8802
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8803
have_max(have_max_arg), seen_first_key(false),
8804
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8805
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8806
max_functions_it(NULL)
8811
record= head->record[0];
8812
tmp_record= head->record[1];
8813
read_time= read_cost_arg;
8814
records= records_arg;
8815
used_key_parts= used_key_parts_arg;
8816
real_key_parts= used_key_parts_arg;
8817
real_prefix_len= group_prefix_len + key_infix_len;
8819
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8822
We can't have parent_alloc set as the init function can't handle this case
8825
assert(!parent_alloc);
8828
init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8829
join->thd->mem_root= &alloc;
8832
bzero(&alloc, sizeof(MEM_ROOT)); // ensure that it's not used
8837
Do post-constructor initialization.
8840
QUICK_GROUP_MIN_MAX_SELECT::init()
8843
The method performs initialization that cannot be done in the constructor
8844
such as memory allocations that may fail. It allocates memory for the
8845
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8846
updated during execution.
8853
int QUICK_GROUP_MIN_MAX_SELECT::init()
8855
if (group_prefix) /* Already initialized. */
8858
if (!(last_prefix= (uchar*) alloc_root(&alloc, group_prefix_len)))
8861
We may use group_prefix to store keys with all select fields, so allocate
8862
enough space for it.
8864
if (!(group_prefix= (uchar*) alloc_root(&alloc,
8865
real_prefix_len + min_max_arg_len)))
8868
if (key_infix_len > 0)
8871
The memory location pointed to by key_infix will be deleted soon, so
8872
allocate a new buffer and copy the key_infix into it.
8874
uchar *tmp_key_infix= (uchar*) alloc_root(&alloc, key_infix_len);
8877
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8878
this->key_infix= tmp_key_infix;
8881
if (min_max_arg_part)
8883
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8888
if (!(min_functions= new List<Item_sum>))
8892
min_functions= NULL;
8895
if (!(max_functions= new List<Item_sum>))
8899
max_functions= NULL;
8901
Item_sum *min_max_item;
8902
Item_sum **func_ptr= join->sum_funcs;
8903
while ((min_max_item= *(func_ptr++)))
8905
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8906
min_functions->push_back(min_max_item);
8907
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8908
max_functions->push_back(min_max_item);
8913
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
8919
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
8924
min_max_ranges.elements= 0;
8930
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8932
if (file->inited != handler::NONE)
8933
file->ha_index_end();
8934
if (min_max_arg_part)
8935
delete_dynamic(&min_max_ranges);
8936
free_root(&alloc,MYF(0));
8937
delete min_functions_it;
8938
delete max_functions_it;
8939
delete quick_prefix_select;
8945
Eventually create and add a new quick range object.
8948
QUICK_GROUP_MIN_MAX_SELECT::add_range()
8949
sel_range Range object from which a
8952
Construct a new QUICK_RANGE object from a SEL_ARG object, and
8953
add it to the array min_max_ranges. If sel_arg is an infinite
8954
range, e.g. (x < 5 or x > 4), then skip it and do not construct
8962
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8965
uint range_flag= sel_range->min_flag | sel_range->max_flag;
8967
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8968
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8971
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
8972
!(sel_range->max_flag & NO_MAX_RANGE))
8974
if (sel_range->maybe_null &&
8975
sel_range->min_value[0] && sel_range->max_value[0])
8976
range_flag|= NULL_RANGE; /* IS NULL condition */
8977
else if (memcmp(sel_range->min_value, sel_range->max_value,
8978
min_max_arg_len) == 0)
8979
range_flag|= EQ_RANGE; /* equality condition */
8981
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
8982
make_keypart_map(sel_range->part),
8983
sel_range->max_value, min_max_arg_len,
8984
make_keypart_map(sel_range->part),
8988
if (insert_dynamic(&min_max_ranges, (uchar*)&range))
8995
Opens the ranges if there are more conditions in quick_prefix_select than
8996
the ones used for jumping through the prefixes.
8999
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9002
quick_prefix_select is made over the conditions on the whole key.
9003
It defines a number of ranges of length x.
9004
However when jumping through the prefixes we use only the the first
9005
few most significant keyparts in the range key. However if there
9006
are more keyparts to follow the ones we are using we must make the
9007
condition on the key inclusive (because x < "ab" means
9008
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9009
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9011
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9013
if (quick_prefix_select &&
9014
group_prefix_len < quick_prefix_select->max_used_key_length)
9019
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9023
get_dynamic(arr, (uchar*)&range, inx);
9024
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9031
Determine the total number and length of the keys that will be used for
9035
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9038
The total length of the keys used for index lookup depends on whether
9039
there are any predicates referencing the min/max argument, and/or if
9040
the min/max argument field can be NULL.
9041
This function does an optimistic analysis whether the search key might
9042
be extended by a constant for the min/max keypart. It is 'optimistic'
9043
because during actual execution it may happen that a particular range
9044
is skipped, and then a shorter key will be used. However this is data
9045
dependent and can't be easily estimated here.
9051
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9053
max_used_key_length= real_prefix_len;
9054
if (min_max_ranges.elements > 0)
9056
QUICK_RANGE *cur_range;
9058
{ /* Check if the right-most range has a lower boundary. */
9059
get_dynamic(&min_max_ranges, (uchar*)&cur_range,
9060
min_max_ranges.elements - 1);
9061
if (!(cur_range->flag & NO_MIN_RANGE))
9063
max_used_key_length+= min_max_arg_len;
9069
{ /* Check if the left-most range has an upper boundary. */
9070
get_dynamic(&min_max_ranges, (uchar*)&cur_range, 0);
9071
if (!(cur_range->flag & NO_MAX_RANGE))
9073
max_used_key_length+= min_max_arg_len;
9079
else if (have_min && min_max_arg_part &&
9080
min_max_arg_part->field->real_maybe_null())
9083
If a MIN/MAX argument value is NULL, we can quickly determine
9084
that we're in the beginning of the next group, because NULLs
9085
are always < any other value. This allows us to quickly
9086
determine the end of the current group and jump to the next
9087
group (see next_min()) and thus effectively increases the
9090
max_used_key_length+= min_max_arg_len;
9097
Initialize a quick group min/max select for key retrieval.
9100
QUICK_GROUP_MIN_MAX_SELECT::reset()
9103
Initialize the index chosen for access and find and store the prefix
9104
of the last group. The method is expensive since it performs disk access.
9111
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9115
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9116
if ((result= file->ha_index_init(index,1)))
9118
if (quick_prefix_select && quick_prefix_select->reset())
9120
result= file->index_last(record);
9121
if (result == HA_ERR_END_OF_FILE)
9123
/* Save the prefix of the last group. */
9124
key_copy(last_prefix, record, index_info, group_prefix_len);
9132
Get the next key containing the MIN and/or MAX key for the next group.
9135
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9138
The method finds the next subsequent group of records that satisfies the
9139
query conditions and finds the keys that contain the MIN/MAX values for
9140
the key part referenced by the MIN/MAX function(s). Once a group and its
9141
MIN/MAX values are found, store these values in the Item_sum objects for
9142
the MIN/MAX functions. The rest of the values in the result row are stored
9143
in the Item_field::result_field of each select field. If the query does
9144
not contain MIN and/or MAX functions, then the function only finds the
9145
group prefix, which is a query answer itself.
9148
If both MIN and MAX are computed, then we use the fact that if there is
9149
no MIN key, there can't be a MAX key as well, so we can skip looking
9150
for a MAX key in this case.
9154
HA_ERR_END_OF_FILE if returned all keys
9155
other if some error occurred
9158
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9163
int is_last_prefix= 0;
9166
Loop until a group is found that satisfies all query conditions or the last
9171
result= next_prefix();
9173
Check if this is the last group prefix. Notice that at this point
9174
this->record contains the current prefix in record format.
9178
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9180
assert(is_last_prefix <= 0);
9184
if (result == HA_ERR_KEY_NOT_FOUND)
9191
min_res= next_min();
9193
update_min_result();
9195
/* If there is no MIN in the group, there is no MAX either. */
9196
if ((have_max && !have_min) ||
9197
(have_max && have_min && (min_res == 0)))
9199
max_res= next_max();
9201
update_max_result();
9202
/* If a MIN was found, a MAX must have been found as well. */
9203
assert((have_max && !have_min) ||
9204
(have_max && have_min && (max_res == 0)));
9207
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9208
are equality predicates for the key parts after the group, find the
9209
first sub-group with the extended prefix.
9211
if (!have_min && !have_max && key_infix_len > 0)
9212
result= file->index_read_map(record, group_prefix,
9213
make_prev_keypart_map(real_key_parts),
9216
result= have_min ? min_res : have_max ? max_res : result;
9217
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9218
is_last_prefix != 0);
9223
Partially mimic the behavior of end_select_send. Copy the
9224
field data from Item_field::field into Item_field::result_field
9225
of each non-aggregated field (the group fields, and optionally
9226
other fields in non-ANSI SQL mode).
9228
copy_fields(&join->tmp_table_param);
9230
else if (result == HA_ERR_KEY_NOT_FOUND)
9231
result= HA_ERR_END_OF_FILE;
9238
Retrieve the minimal key in the next group.
9241
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9244
Find the minimal key within this group such that the key satisfies the query
9245
conditions and NULL semantics. The found key is loaded into this->record.
9248
Depending on the values of min_max_ranges.elements, key_infix_len, and
9249
whether there is a NULL in the MIN field, this function may directly
9250
return without any data access. In this case we use the key loaded into
9251
this->record by the call to this->next_prefix() just before this call.
9255
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9256
HA_ERR_END_OF_FILE - "" -
9257
other if some error occurred
9260
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9264
/* Find the MIN key using the eventually extended group prefix. */
9265
if (min_max_ranges.elements > 0)
9267
if ((result= next_min_in_range()))
9272
/* Apply the constant equality conditions to the non-group select fields */
9273
if (key_infix_len > 0)
9275
if ((result= file->index_read_map(record, group_prefix,
9276
make_prev_keypart_map(real_key_parts),
9277
HA_READ_KEY_EXACT)))
9282
If the min/max argument field is NULL, skip subsequent rows in the same
9283
group with NULL in it. Notice that:
9284
- if the first row in a group doesn't have a NULL in the field, no row
9285
in the same group has (because NULL < any other value),
9286
- min_max_arg_part->field->ptr points to some place in 'record'.
9288
if (min_max_arg_part && min_max_arg_part->field->is_null())
9290
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9291
key_copy(tmp_record, record, index_info, 0);
9292
result= file->index_read_map(record, tmp_record,
9293
make_keypart_map(real_key_parts),
9296
Check if the new record belongs to the current group by comparing its
9297
prefix with the group's prefix. If it is from the next group, then the
9298
whole group has NULLs in the MIN/MAX field, so use the first record in
9299
the group as a result.
9301
It is possible to reuse this new record as the result candidate for the
9302
next call to next_min(), and to save one lookup in the next call. For
9303
this add a new member 'this->next_group_prefix'.
9307
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9308
key_restore(record, tmp_record, index_info, 0);
9310
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9311
result= 0; /* There is a result in any case. */
9316
If the MIN attribute is non-nullable, this->record already contains the
9317
MIN key in the group, so just return.
9324
Retrieve the maximal key in the next group.
9327
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9330
Lookup the maximal key of the group, and store it into this->record.
9334
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9335
HA_ERR_END_OF_FILE - "" -
9336
other if some error occurred
9339
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9343
/* Get the last key in the (possibly extended) group. */
9344
if (min_max_ranges.elements > 0)
9345
result= next_max_in_range();
9347
result= file->index_read_map(record, group_prefix,
9348
make_prev_keypart_map(real_key_parts),
9349
HA_READ_PREFIX_LAST);
9355
Determine the prefix of the next group.
9358
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9361
Determine the prefix of the next group that satisfies the query conditions.
9362
If there is a range condition referencing the group attributes, use a
9363
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9364
condition. If there is a key infix of constants, append this infix
9365
immediately after the group attributes. The possibly extended prefix is
9366
stored in this->group_prefix. The first key of the found group is stored in
9367
this->record, on which relies this->next_min().
9371
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9372
HA_ERR_END_OF_FILE if there are no more keys
9373
other if some error occurred
9375
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9379
if (quick_prefix_select)
9381
uchar *cur_prefix= seen_first_key ? group_prefix : NULL;
9382
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9383
make_prev_keypart_map(group_key_parts), cur_prefix)))
9385
seen_first_key= true;
9389
if (!seen_first_key)
9391
result= file->index_first(record);
9394
seen_first_key= true;
9398
/* Load the first key in this group into record. */
9399
result= file->index_read_map(record, group_prefix,
9400
make_prev_keypart_map(group_key_parts),
9407
/* Save the prefix of this group for subsequent calls. */
9408
key_copy(group_prefix, record, index_info, group_prefix_len);
9409
/* Append key_infix to group_prefix. */
9410
if (key_infix_len > 0)
9411
memcpy(group_prefix + group_prefix_len,
9412
key_infix, key_infix_len);
9419
Find the minimal key in a group that satisfies some range conditions for the
9420
min/max argument field.
9423
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9426
Given the sequence of ranges min_max_ranges, find the minimal key that is
9427
in the left-most possible range. If there is no such key, then the current
9428
group does not have a MIN key that satisfies the WHERE clause. If a key is
9429
found, its value is stored in this->record.
9433
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9435
HA_ERR_END_OF_FILE - "" -
9439
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9441
ha_rkey_function find_flag;
9442
key_part_map keypart_map;
9443
QUICK_RANGE *cur_range;
9444
bool found_null= false;
9445
int result= HA_ERR_KEY_NOT_FOUND;
9447
assert(min_max_ranges.elements > 0);
9449
for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9450
{ /* Search from the left-most range to the right. */
9451
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx);
9454
If the current value for the min/max argument is bigger than the right
9455
boundary of cur_range, there is no need to check this range.
9457
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9458
(key_cmp(min_max_arg_part, (const uchar*) cur_range->max_key,
9459
min_max_arg_len) == 1))
9462
if (cur_range->flag & NO_MIN_RANGE)
9464
keypart_map= make_prev_keypart_map(real_key_parts);
9465
find_flag= HA_READ_KEY_EXACT;
9469
/* Extend the search key with the lower boundary for this range. */
9470
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9471
cur_range->min_length);
9472
keypart_map= make_keypart_map(real_key_parts);
9473
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9474
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9475
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9478
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9481
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9482
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9483
continue; /* Check the next range. */
9486
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9487
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9488
range, it can't succeed for any other subsequent range.
9493
/* A key was found. */
9494
if (cur_range->flag & EQ_RANGE)
9495
break; /* No need to perform the checks below for equal keys. */
9497
if (cur_range->flag & NULL_RANGE)
9500
Remember this key, and continue looking for a non-NULL key that
9501
satisfies some other condition.
9503
memcpy(tmp_record, record, head->s->rec_buff_length);
9508
/* Check if record belongs to the current group. */
9509
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9511
result= HA_ERR_KEY_NOT_FOUND;
9515
/* If there is an upper limit, check if the found key is in the range. */
9516
if ( !(cur_range->flag & NO_MAX_RANGE) )
9518
/* Compose the MAX key for the range. */
9519
uchar *max_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9520
memcpy(max_key, group_prefix, real_prefix_len);
9521
memcpy(max_key + real_prefix_len, cur_range->max_key,
9522
cur_range->max_length);
9523
/* Compare the found key with max_key. */
9524
int cmp_res= key_cmp(index_info->key_part, max_key,
9525
real_prefix_len + min_max_arg_len);
9526
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9528
result= HA_ERR_KEY_NOT_FOUND;
9532
/* If we got to this point, the current key qualifies as MIN. */
9533
assert(result == 0);
9537
If there was a key with NULL in the MIN/MAX field, and there was no other
9538
key without NULL from the same group that satisfies some other condition,
9539
then use the key with the NULL.
9541
if (found_null && result)
9543
memcpy(record, tmp_record, head->s->rec_buff_length);
9551
Find the maximal key in a group that satisfies some range conditions for the
9552
min/max argument field.
9555
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9558
Given the sequence of ranges min_max_ranges, find the maximal key that is
9559
in the right-most possible range. If there is no such key, then the current
9560
group does not have a MAX key that satisfies the WHERE clause. If a key is
9561
found, its value is stored in this->record.
9565
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9567
HA_ERR_END_OF_FILE - "" -
9571
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9573
ha_rkey_function find_flag;
9574
key_part_map keypart_map;
9575
QUICK_RANGE *cur_range;
9578
assert(min_max_ranges.elements > 0);
9580
for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9581
{ /* Search from the right-most range to the left. */
9582
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx - 1);
9585
If the current value for the min/max argument is smaller than the left
9586
boundary of cur_range, there is no need to check this range.
9588
if (range_idx != min_max_ranges.elements &&
9589
!(cur_range->flag & NO_MIN_RANGE) &&
9590
(key_cmp(min_max_arg_part, (const uchar*) cur_range->min_key,
9591
min_max_arg_len) == -1))
9594
if (cur_range->flag & NO_MAX_RANGE)
9596
keypart_map= make_prev_keypart_map(real_key_parts);
9597
find_flag= HA_READ_PREFIX_LAST;
9601
/* Extend the search key with the upper boundary for this range. */
9602
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9603
cur_range->max_length);
9604
keypart_map= make_keypart_map(real_key_parts);
9605
find_flag= (cur_range->flag & EQ_RANGE) ?
9606
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9607
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9610
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9614
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9615
(cur_range->flag & EQ_RANGE))
9616
continue; /* Check the next range. */
9619
In no key was found with this upper bound, there certainly are no keys
9620
in the ranges to the left.
9624
/* A key was found. */
9625
if (cur_range->flag & EQ_RANGE)
9626
return 0; /* No need to perform the checks below for equal keys. */
9628
/* Check if record belongs to the current group. */
9629
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9630
continue; // Row not found
9632
/* If there is a lower limit, check if the found key is in the range. */
9633
if ( !(cur_range->flag & NO_MIN_RANGE) )
9635
/* Compose the MIN key for the range. */
9636
uchar *min_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9637
memcpy(min_key, group_prefix, real_prefix_len);
9638
memcpy(min_key + real_prefix_len, cur_range->min_key,
9639
cur_range->min_length);
9640
/* Compare the found key with min_key. */
9641
int cmp_res= key_cmp(index_info->key_part, min_key,
9642
real_prefix_len + min_max_arg_len);
9643
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9647
/* If we got to this point, the current key qualifies as MAX. */
9650
return HA_ERR_KEY_NOT_FOUND;
9655
Update all MIN function results with the newly found value.
9658
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9661
The method iterates through all MIN functions and updates the result value
9662
of each function by calling Item_sum::reset(), which in turn picks the new
9663
result value from this->head->record[0], previously updated by
9664
next_min(). The updated value is stored in a member variable of each of the
9665
Item_sum objects, depending on the value type.
9668
The update must be done separately for MIN and MAX, immediately after
9669
next_min() was called and before next_max() is called, because both MIN and
9670
MAX take their result value from the same buffer this->head->record[0]
9671
(i.e. this->record).
9677
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9681
min_functions_it->rewind();
9682
while ((min_func= (*min_functions_it)++))
9688
Update all MAX function results with the newly found value.
9691
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9694
The method iterates through all MAX functions and updates the result value
9695
of each function by calling Item_sum::reset(), which in turn picks the new
9696
result value from this->head->record[0], previously updated by
9697
next_max(). The updated value is stored in a member variable of each of the
9698
Item_sum objects, depending on the value type.
9701
The update must be done separately for MIN and MAX, immediately after
9702
next_max() was called, because both MIN and MAX take their result value
9703
from the same buffer this->head->record[0] (i.e. this->record).
9709
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9713
max_functions_it->rewind();
9714
while ((max_func= (*max_functions_it)++))
9720
Append comma-separated list of keys this quick select uses to key_names;
9721
append comma-separated list of corresponding used lengths to used_lengths.
9724
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9725
key_names [out] Names of used indexes
9726
used_lengths [out] Corresponding lengths of the index names
9729
This method is used by select_describe to extract the names of the
9730
indexes used by a quick select.
9734
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9735
String *used_lengths)
9739
key_names->append(index_info->name);
9740
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9741
used_lengths->append(buf, length);
9744
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9745
const char *msg __attribute__((unused)))
9747
SEL_ARG **key,**end;
6371
9749
char buff[1024];
6373
9751
String tmp(buff,sizeof(buff),&my_charset_bin);
6375
for (idx= 0, key=tree->keys, end= key + param->keys;
9753
for (idx= 0,key=tree->keys, end=key+param->keys ;
6379
if (tree_map->test(idx))
9757
if (tree_map->is_set(idx))
6381
uint32_t keynr= param->real_keynr[idx];
9759
uint keynr= param->real_keynr[idx];
6382
9760
if (tmp.length())
6383
9761
tmp.append(',');
6384
9762
tmp.append(param->table->key_info[keynr].name);
6388
9766
tmp.append(STRING_WITH_LEN("(empty)"));
6392
static void print_ror_scans_arr(Table *table,
9772
static void print_ror_scans_arr(TABLE *table,
9773
const char *msg __attribute__((unused)),
6394
9774
struct st_ror_scan_info **start,
6395
9775
struct st_ror_scan_info **end)
6397
9777
char buff[1024];
6398
9778
String tmp(buff,sizeof(buff),&my_charset_bin);
6400
for (; start != end; start++)
9780
for (;start != end; start++)
6402
9782
if (tmp.length())
6403
9783
tmp.append(',');
6404
9784
tmp.append(table->key_info[(*start)->keynr].name);
6407
9787
tmp.append(STRING_WITH_LEN("(empty)"));
9791
/*****************************************************************************
9792
** Instantiate templates
9793
*****************************************************************************/
9795
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9796
template class List<QUICK_RANGE>;
9797
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
