96
99
See key_copy() and key_restore() for code to move data between index tuple
99
CAUTION: the above description is only sergefp's understanding of the
102
CAUTION: the above description is only sergefp's understanding of the
100
103
subject and may omit some details.
112
#include <boost/dynamic_bitset.hpp>
114
#include "drizzled/check_stack_overrun.h"
115
#include "drizzled/error.h"
116
#include "drizzled/field/num.h"
117
#include "drizzled/internal/iocache.h"
118
#include "drizzled/internal/my_sys.h"
119
#include "drizzled/item/cmpfunc.h"
120
#include "drizzled/optimizer/cost_vector.h"
121
#include "drizzled/optimizer/quick_group_min_max_select.h"
122
#include "drizzled/optimizer/quick_index_merge_select.h"
123
#include "drizzled/optimizer/quick_range.h"
124
#include "drizzled/optimizer/quick_range_select.h"
125
#include "drizzled/optimizer/quick_ror_intersect_select.h"
126
#include "drizzled/optimizer/quick_ror_union_select.h"
127
#include "drizzled/optimizer/range.h"
128
#include "drizzled/optimizer/range_param.h"
129
#include "drizzled/optimizer/sel_arg.h"
130
#include "drizzled/optimizer/sel_imerge.h"
131
#include "drizzled/optimizer/sel_tree.h"
132
#include "drizzled/optimizer/sum.h"
133
#include "drizzled/optimizer/table_read_plan.h"
134
#include "drizzled/plugin/storage_engine.h"
135
#include "drizzled/records.h"
136
#include "drizzled/sql_base.h"
137
#include "drizzled/sql_select.h"
138
#include "drizzled/table_reference.h"
140
#include "drizzled/temporal.h" /* Needed in get_mm_leaf() for timestamp -> datetime comparisons */
146
#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) {}
149
120
Convert double value to #rows. Currently this does floor(), and we
150
121
might consider using round() instead.
152
static inline ha_rows double2rows(double x)
154
return static_cast<ha_rows>(x);
157
static unsigned char is_null_string[2]= {1,0};
161
Get cost of reading nrows table records in a "disk sweep"
163
A disk sweep read is a sequence of Cursor->rnd_pos(rowid) calls that made
164
for an ordered sequence of rowids.
166
We assume hard disk IO. The read is performed as follows:
168
1. The disk head is moved to the needed cylinder
169
2. The controller waits for the plate to rotate
170
3. The data is transferred
172
Time to do #3 is insignificant compared to #2+#1.
174
Time to move the disk head is proportional to head travel distance.
176
Time to wait for the plate to rotate depends on whether the disk head
179
If disk head wasn't moved, the wait time is proportional to distance
180
between the previous block and the block we're reading.
182
If the head was moved, we don't know how much we'll need to wait for the
183
plate to rotate. We assume the wait time to be a variate with a mean of
184
0.5 of full rotation time.
186
Our cost units are "random disk seeks". The cost of random disk seek is
187
actually not a constant, it depends one range of cylinders we're going
188
to access. We make it constant by introducing a fuzzy concept of "typical
189
datafile length" (it's fuzzy as it's hard to tell whether it should
190
include index cursor, temp.tables etc). Then random seek cost is:
192
1 = half_rotation_cost + move_cost * 1/3 * typical_data_file_length
194
We define half_rotation_cost as DISK_SEEK_BASE_COST=0.9.
196
@param table Table to be accessed
197
@param nrows Number of rows to retrieve
198
@param interrupted true <=> Assume that the disk sweep will be
199
interrupted by other disk IO. false - otherwise.
200
@param cost OUT The cost.
203
static void get_sweep_read_cost(Table *table,
206
optimizer::CostVector *cost)
209
if (table->cursor->primary_key_is_clustered())
211
cost->setIOCount(table->cursor->read_time(table->getShare()->getPrimaryKey(),
212
static_cast<uint32_t>(nrows),
218
ceil(uint64_t2double(table->cursor->stats.data_file_length) / IO_SIZE);
220
n_blocks * (1.0 - pow(1.0 - 1.0/n_blocks, rows2double(nrows)));
221
if (busy_blocks < 1.0)
224
cost->setIOCount(busy_blocks);
228
/* Assume reading is done in one 'sweep' */
229
cost->setAvgIOCost((DISK_SEEK_BASE_COST +
230
DISK_SEEK_PROP_COST*n_blocks/busy_blocks));
235
static optimizer::SEL_TREE * get_mm_parts(optimizer::RangeParameter *param,
238
Item_func::Functype type,
240
Item_result cmp_type);
242
static optimizer::SEL_ARG *get_mm_leaf(optimizer::RangeParameter *param,
246
Item_func::Functype type,
249
static optimizer::SEL_TREE *get_mm_tree(optimizer::RangeParameter *param, COND *cond);
251
static bool is_key_scan_ror(optimizer::Parameter *param, uint32_t keynr, uint8_t nparts);
253
static ha_rows check_quick_select(Session *session,
254
optimizer::Parameter *param,
257
optimizer::SEL_ARG *tree,
258
bool update_tbl_stats,
261
optimizer::CostVector *cost);
263
static optimizer::RangeReadPlan *get_key_scans_params(Session *session,
264
optimizer::Parameter *param,
265
optimizer::SEL_TREE *tree,
266
bool index_read_must_be_used,
267
bool update_tbl_stats,
271
optimizer::RorIntersectReadPlan *get_best_ror_intersect(const optimizer::Parameter *param,
272
optimizer::SEL_TREE *tree,
274
bool *are_all_covering);
277
optimizer::RorIntersectReadPlan *get_best_covering_ror_intersect(optimizer::Parameter *param,
278
optimizer::SEL_TREE *tree,
282
optimizer::TableReadPlan *get_best_disjunct_quick(Session *session,
283
optimizer::Parameter *param,
284
optimizer::SEL_IMERGE *imerge,
288
optimizer::GroupMinMaxReadPlan *get_best_group_min_max(optimizer::Parameter *param, optimizer::SEL_TREE *tree);
290
static optimizer::SEL_TREE *tree_and(optimizer::RangeParameter *param,
291
optimizer::SEL_TREE *tree1,
292
optimizer::SEL_TREE *tree2);
294
static optimizer::SEL_ARG *sel_add(optimizer::SEL_ARG *key1, optimizer::SEL_ARG *key2);
296
static optimizer::SEL_ARG *key_and(optimizer::RangeParameter *param,
297
optimizer::SEL_ARG *key1,
298
optimizer::SEL_ARG *key2,
299
uint32_t clone_flag);
301
static bool get_range(optimizer::SEL_ARG **e1, optimizer::SEL_ARG **e2, optimizer::SEL_ARG *root1);
303
optimizer::SEL_ARG optimizer::null_element(optimizer::SEL_ARG::IMPOSSIBLE);
305
static bool null_part_in_key(KEY_PART *key_part,
306
const unsigned char *key,
309
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
310
optimizer::SEL_TREE *tree2,
311
optimizer::RangeParameter *param);
123
#define double2rows(x) ((ha_rows)(x))
125
static int sel_cmp(Field *f,uchar *a,uchar *b,uint8 a_flag,uint8 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.
300
class SEL_ARG :public Sql_alloc
303
uint8 min_flag,max_flag,maybe_flag;
304
uint8 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 part, uchar *min_value, uchar *max_value,
337
uint8 min_flag, uint8 max_flag, uint8 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 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);
605
class SEL_TREE :public Sql_alloc
609
Starting an effort to document this field:
610
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
611
(type == SEL_TREE::IMPOSSIBLE)
613
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
614
SEL_TREE(enum Type type_arg) :type(type_arg) {}
615
SEL_TREE() :type(KEY)
617
keys_map.clear_all();
618
bzero((char*) keys,sizeof(keys));
621
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
622
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
623
merit in range analyzer functions (e.g. get_mm_parts) returning a
624
pointer to such SEL_TREE instead of NULL)
626
SEL_ARG *keys[MAX_KEY];
627
key_map keys_map; /* bitmask of non-NULL elements in keys */
630
Possible ways to read rows using index_merge. The list is non-empty only
631
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
633
List<SEL_IMERGE> merges;
635
/* The members below are filled/used only after get_mm_tree is done */
636
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
637
uint n_ror_scans; /* number of set bits in ror_scans_map */
639
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
640
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
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;
718
struct st_ror_scan_info;
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 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,
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);
761
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
763
static void print_ror_scans_arr(TABLE *table, const char *msg,
764
struct st_ror_scan_info **start,
765
struct st_ror_scan_info **end);
766
static void print_quick(QUICK_SELECT_I *quick, const key_map *needed_reg);
769
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
770
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
771
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
772
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
773
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
775
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
776
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
777
SEL_ARG *key_tree, uchar *min_key,uint min_key_flag,
778
uchar *max_key,uint max_key_flag);
779
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
781
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
782
static bool null_part_in_key(KEY_PART *key_part, const uchar *key,
784
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
788
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
789
a condition in the following form:
790
(t_1||t_2||...||t_N) && (next)
792
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
793
(t_i,t_j) contains SEL_ARGS for the same index.
795
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
797
This class relies on memory manager to do the cleanup.
800
class SEL_IMERGE : public Sql_alloc
802
enum { PREALLOCED_TREES= 10};
804
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
805
SEL_TREE **trees; /* trees used to do index_merge */
806
SEL_TREE **trees_next; /* last of these trees */
807
SEL_TREE **trees_end; /* end of allocated space */
809
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
812
trees(&trees_prealloced[0]),
814
trees_end(trees + PREALLOCED_TREES)
816
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
817
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
818
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
823
Add SEL_TREE to this index_merge without any checks,
826
This function implements the following:
827
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
834
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
836
if (trees_next == trees_end)
838
const int realloc_ratio= 2; /* Double size for next round */
839
uint old_elements= (trees_end - trees);
840
uint old_size= sizeof(SEL_TREE**) * old_elements;
841
uint new_size= old_size * realloc_ratio;
842
SEL_TREE **new_trees;
843
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
845
memcpy(new_trees, trees, old_size);
847
trees_next= trees + old_elements;
848
trees_end= trees + old_elements * realloc_ratio;
850
*(trees_next++)= tree;
856
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
857
combining new_tree with one of the trees in this SEL_IMERGE if they both
858
have SEL_ARGs for the same key.
861
or_sel_tree_with_checks()
862
param PARAM from SQL_SELECT::test_quick_select
863
new_tree SEL_TREE with type KEY or KEY_SMALLER.
866
This does the following:
867
(t_1||...||t_k)||new_tree =
869
= (t_1||...||t_k||new_tree)
871
= (t_1||....||(t_j|| new_tree)||...||t_k),
873
where t_i, y are SEL_TREEs.
874
new_tree is combined with the first t_j it has a SEL_ARG on common
875
key with. As a consequence of this, choice of keys to do index_merge
876
read may depend on the order of conditions in WHERE part of the query.
880
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
881
and (*this) should be discarded.
882
-1 An error occurred.
885
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
887
for (SEL_TREE** tree = trees;
891
if (sel_trees_can_be_ored(*tree, new_tree, param))
893
*tree = tree_or(param, *tree, new_tree);
896
if (((*tree)->type == SEL_TREE::MAYBE) ||
897
((*tree)->type == SEL_TREE::ALWAYS))
899
/* SEL_TREE::IMPOSSIBLE is impossible here */
904
/* New tree cannot be combined with any of existing trees. */
905
return or_sel_tree(param, new_tree);
910
Perform OR operation on this index_merge and supplied index_merge list.
914
1 - One of conditions in result is always TRUE and this SEL_IMERGE
916
-1 - An error occurred
919
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
921
for (SEL_TREE** tree= imerge->trees;
922
tree != imerge->trees_next;
925
if (or_sel_tree_with_checks(param, *tree))
319
933
Perform AND operation on two index_merge lists and store result in *im1.
322
inline void imerge_list_and_list(List<optimizer::SEL_IMERGE> *im1, List<optimizer::SEL_IMERGE> *im2)
936
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
324
938
im1->concat(im2);
943
Perform OR operation on 2 index_merge lists, storing result in first list.
946
The following conversion is implemented:
947
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
950
i.e. all conjuncts except the first one are currently dropped.
951
This is done to avoid producing N*K ways to do index_merge.
953
If (a_1||b_1) produce a condition that is always TRUE, NULL is returned
954
and index_merge is discarded (while it is actually possible to try
957
As a consequence of this, choice of keys to do index_merge read may depend
958
on the order of conditions in WHERE part of the query.
961
0 OK, result is stored in *im1
962
other Error, both passed lists are unusable
965
int imerge_list_or_list(RANGE_OPT_PARAM *param,
966
List<SEL_IMERGE> *im1,
967
List<SEL_IMERGE> *im2)
969
SEL_IMERGE *imerge= im1->head();
971
im1->push_back(imerge);
973
return imerge->or_sel_imerge_with_checks(param, im2->head());
978
Perform OR operation on index_merge list and key tree.
981
0 OK, result is stored in *im1.
985
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
986
List<SEL_IMERGE> *im1,
990
List_iterator<SEL_IMERGE> it(*im1);
991
while ((imerge= it++))
993
if (imerge->or_sel_tree_with_checks(param, tree))
996
return im1->is_empty();
328
1000
/***************************************************************************
329
** Basic functions for SqlSelect and QuickRangeSelect
1001
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
330
1002
***************************************************************************/
332
1004
/* make a select from mysql info
363
1032
if (head->sort.io_cache)
365
memcpy(select->file, head->sort.io_cache, sizeof(internal::IO_CACHE));
366
select->records=(ha_rows) (select->file->end_of_file/
367
head->cursor->ref_length);
368
delete head->sort.io_cache;
1034
select->file= *head->sort.io_cache;
1035
select->records=(ha_rows) (select->file.end_of_file/
1036
head->file->ref_length);
1037
my_free(head->sort.io_cache, MYF(0));
369
1038
head->sort.io_cache=0;
375
optimizer::SqlSelect::SqlSelect()
379
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
388
void optimizer::SqlSelect::cleanup()
1040
DBUG_RETURN(select);
1044
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1046
quick_keys.clear_all(); needed_reg.clear_all();
1051
void SQL_SELECT::cleanup()
402
file->close_cached_file();
1061
close_cached_file(&file);
406
optimizer::SqlSelect::~SqlSelect()
1065
SQL_SELECT::~SQL_SELECT()
412
bool optimizer::SqlSelect::check_quick(Session *session,
413
bool force_quick_range,
418
return (test_quick_select(session,
427
bool optimizer::SqlSelect::skip_record()
429
return (cond ? cond->val_int() == 0 : 0);
433
optimizer::QuickSelectInterface::QuickSelectInterface()
435
max_used_key_length(0),
1070
#undef index // Fix for Unixware 7
1072
QUICK_SELECT_I::QUICK_SELECT_I()
1073
:max_used_key_length(0),
1077
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(THD *thd, TABLE *table, uint key_nr,
1078
bool no_alloc, MEM_ROOT *parent_alloc,
1080
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1082
my_bitmap_map *bitmap;
1083
DBUG_ENTER("QUICK_RANGE_SELECT::QUICK_RANGE_SELECT");
1085
in_ror_merged_scan= 0;
1089
key_part_info= head->key_info[index].key_part;
1090
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1092
/* 'thd' is not accessible in QUICK_RANGE_SELECT::reset(). */
1093
mrr_buf_size= thd->variables.read_rnd_buff_size;
1096
if (!no_alloc && !parent_alloc)
1098
// Allocates everything through the internal memroot
1099
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1100
thd->mem_root= &alloc;
1103
bzero((char*) &alloc,sizeof(alloc));
1105
record= head->record[0];
1106
save_read_set= head->read_set;
1107
save_write_set= head->write_set;
1109
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1110
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1113
column_bitmap.bitmap= 0;
1117
bitmap_init(&column_bitmap, bitmap, head->s->fields, FALSE);
1122
int QUICK_RANGE_SELECT::init()
1124
DBUG_ENTER("QUICK_RANGE_SELECT::init");
1126
if (file->inited != handler::NONE)
1127
file->ha_index_or_rnd_end();
1128
DBUG_RETURN(file->ha_index_init(index, 1));
1132
void QUICK_RANGE_SELECT::range_end()
1134
if (file->inited != handler::NONE)
1135
file->ha_index_or_rnd_end();
1139
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1141
DBUG_ENTER("QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT");
1144
/* file is NULL for CPK scan on covering ROR-intersection */
1151
file->extra(HA_EXTRA_NO_KEYREAD);
1155
DBUG_PRINT("info", ("Freeing separate handler 0x%lx (free: %d)", (long) file,
1157
file->ha_external_lock(current_thd, F_UNLCK);
1162
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1163
free_root(&alloc,MYF(0));
1164
my_free((char*) column_bitmap.bitmap, MYF(MY_ALLOW_ZERO_PTR));
1166
head->column_bitmaps_set(save_read_set, save_write_set);
1167
x_free(mrr_buf_desc);
1172
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(THD *thd_param,
1174
:pk_quick_select(NULL), thd(thd_param)
1176
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT");
1179
bzero(&read_record, sizeof(read_record));
1180
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1184
int QUICK_INDEX_MERGE_SELECT::init()
1186
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::init");
1190
int QUICK_INDEX_MERGE_SELECT::reset()
1192
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::reset");
1193
DBUG_RETURN(read_keys_and_merge());
1197
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1200
Save quick_select that does scan on clustered primary key as it will be
1201
processed separately.
1203
if (head->file->primary_key_is_clustered() &&
1204
quick_sel_range->index == head->s->primary_key)
1205
pk_quick_select= quick_sel_range;
1207
return quick_selects.push_back(quick_sel_range);
1211
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1213
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1214
QUICK_RANGE_SELECT* quick;
1215
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT");
1217
while ((quick= quick_it++))
1219
quick_selects.delete_elements();
1220
delete pk_quick_select;
1221
free_root(&alloc,MYF(0));
1226
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(THD *thd_param,
1228
bool retrieve_full_rows,
1229
MEM_ROOT *parent_alloc)
1230
: cpk_quick(NULL), thd(thd_param), need_to_fetch_row(retrieve_full_rows),
1235
record= head->record[0];
1237
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1239
bzero(&alloc, sizeof(MEM_ROOT));
1240
last_rowid= (uchar*) alloc_root(parent_alloc? parent_alloc : &alloc,
1241
head->file->ref_length);
1246
Do post-constructor initialization.
1248
QUICK_ROR_INTERSECT_SELECT::init()
1255
int QUICK_ROR_INTERSECT_SELECT::init()
1257
DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init");
1258
/* Check if last_rowid was successfully allocated in ctor */
1259
DBUG_RETURN(!last_rowid);
1264
Initialize this quick select to be a ROR-merged scan.
1267
QUICK_RANGE_SELECT::init_ror_merged_scan()
1268
reuse_handler If TRUE, use head->file, otherwise create a separate
1272
This function creates and prepares for subsequent use a separate handler
1273
object if it can't reuse head->file. The reason for this is that during
1274
ROR-merge several key scans are performed simultaneously, and a single
1275
handler is only capable of preserving context of a single key scan.
1277
In ROR-merge the quick select doing merge does full records retrieval,
1278
merged quick selects read only keys.
1281
0 ROR child scan initialized, ok to use.
1285
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1287
handler *save_file= file, *org_file;
1289
DBUG_ENTER("QUICK_RANGE_SELECT::init_ror_merged_scan");
1291
in_ror_merged_scan= 1;
1294
DBUG_PRINT("info", ("Reusing handler 0x%lx", (long) file));
1295
if (init() || reset())
1299
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1303
/* Create a separate handler object for this quick select */
1306
/* already have own 'handler' object. */
1311
if (!(file= head->file->clone(thd->mem_root)))
1314
Manually set the error flag. Note: there seems to be quite a few
1315
places where a failure could cause the server to "hang" the client by
1316
sending no response to a query. ATM those are not real errors because
1317
the storage engine calls in question happen to never fail with the
1318
existing storage engines.
1320
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1321
/* Caller will free the memory */
1322
goto failure; /* purecov: inspected */
1325
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1327
if (file->ha_external_lock(thd, F_RDLCK))
1330
if (init() || reset())
1332
file->ha_external_lock(thd, F_UNLCK);
1337
last_rowid= file->ref;
1341
We are only going to read key fields and call position() on 'file'
1342
The following sets head->tmp_set to only use this key and then updates
1343
head->read_set and head->write_set to use this bitmap.
1344
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1346
org_file= head->file;
1348
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1349
if (!head->no_keyread)
1352
head->mark_columns_used_by_index(index);
1354
head->prepare_for_position();
1355
head->file= org_file;
1356
bitmap_copy(&column_bitmap, head->read_set);
1357
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1362
head->column_bitmaps_set(save_read_set, save_write_set);
1370
Initialize this quick select to be a part of a ROR-merged scan.
1372
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1373
reuse_handler If TRUE, use head->file, otherwise create separate
1379
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1381
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1382
QUICK_RANGE_SELECT* quick;
1383
DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan");
1385
/* Initialize all merged "children" quick selects */
1386
DBUG_ASSERT(!need_to_fetch_row || reuse_handler);
1387
if (!need_to_fetch_row && reuse_handler)
1391
There is no use of this->file. Use it for the first of merged range
1394
if (quick->init_ror_merged_scan(TRUE))
1396
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1398
while ((quick= quick_it++))
1400
if (quick->init_ror_merged_scan(FALSE))
1402
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1403
/* All merged scans share the same record buffer in intersection. */
1404
quick->record= head->record[0];
1407
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1409
DBUG_PRINT("error", ("ROR index_merge rnd_init call failed"));
1417
Initialize quick select for row retrieval.
1425
int QUICK_ROR_INTERSECT_SELECT::reset()
1427
DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::reset");
1428
if (!scans_inited && init_ror_merged_scan(TRUE))
1431
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1432
QUICK_RANGE_SELECT *quick;
1433
while ((quick= it++))
1440
Add a merged quick select to this ROR-intersection quick select.
1443
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1444
quick Quick select to be added. The quick select must return
1445
rows in rowid order.
1447
This call can only be made before init() is called.
1455
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1457
return quick_selects.push_back(quick);
1460
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1462
DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT");
1463
quick_selects.delete_elements();
1465
free_root(&alloc,MYF(0));
1466
if (need_to_fetch_row && head->file->inited != handler::NONE)
1467
head->file->ha_rnd_end();
1472
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(THD *thd_param,
1474
: thd(thd_param), scans_inited(FALSE)
1478
rowid_length= table->file->ref_length;
1479
record= head->record[0];
1480
init_sql_alloc(&alloc, thd->variables.range_alloc_block_size, 0);
1481
thd_param->mem_root= &alloc;
1486
Do post-constructor initialization.
1488
QUICK_ROR_UNION_SELECT::init()
1495
int QUICK_ROR_UNION_SELECT::init()
1497
DBUG_ENTER("QUICK_ROR_UNION_SELECT::init");
1498
if (init_queue(&queue, quick_selects.elements, 0,
1499
FALSE , QUICK_ROR_UNION_SELECT::queue_cmp,
1502
bzero(&queue, sizeof(QUEUE));
1506
if (!(cur_rowid= (uchar*) alloc_root(&alloc, 2*head->file->ref_length)))
1508
prev_rowid= cur_rowid + head->file->ref_length;
1514
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1518
QUICK_ROR_UNION_SELECT::queue_cmp()
1519
arg Pointer to QUICK_ROR_UNION_SELECT
1520
val1 First merged select
1521
val2 Second merged select
1524
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, uchar *val1, uchar *val2)
1526
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1527
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1528
((QUICK_SELECT_I*)val2)->last_rowid);
1533
Initialize quick select for row retrieval.
1542
int QUICK_ROR_UNION_SELECT::reset()
1544
QUICK_SELECT_I *quick;
1546
DBUG_ENTER("QUICK_ROR_UNION_SELECT::reset");
1547
have_prev_rowid= FALSE;
1550
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1551
while ((quick= it++))
1553
if (quick->init_ror_merged_scan(FALSE))
1558
queue_remove_all(&queue);
1560
Initialize scans for merged quick selects and put all merged quick
1561
selects into the queue.
1563
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1564
while ((quick= it++))
1568
if ((error= quick->get_next()))
1570
if (error == HA_ERR_END_OF_FILE)
1574
quick->save_last_pos();
1575
queue_insert(&queue, (uchar*)quick);
1578
if (head->file->ha_rnd_init(1))
1580
DBUG_PRINT("error", ("ROR index_merge rnd_init call failed"));
1589
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1591
return quick_selects.push_back(quick_sel_range);
1594
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1596
DBUG_ENTER("QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT");
1597
delete_queue(&queue);
1598
quick_selects.delete_elements();
1599
if (head->file->inited != handler::NONE)
1600
head->file->ha_rnd_end();
1601
free_root(&alloc,MYF(0));
1606
QUICK_RANGE::QUICK_RANGE()
1607
:min_key(0),max_key(0),min_length(0),max_length(0),
1608
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1609
min_keypart_map(0), max_keypart_map(0)
1612
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1615
min_flag=arg.min_flag;
1616
max_flag=arg.max_flag;
1617
maybe_flag=arg.maybe_flag;
1618
maybe_null=arg.maybe_null;
1621
min_value=arg.min_value;
1622
max_value=arg.max_value;
1623
next_key_part=arg.next_key_part;
1624
use_count=1; elements=1;
1628
inline void SEL_ARG::make_root()
1630
left=right= &null_element;
1633
use_count=0; elements=1;
1636
SEL_ARG::SEL_ARG(Field *f,const uchar *min_value_arg,
1637
const uchar *max_value_arg)
1638
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1639
elements(1), use_count(1), field(f), min_value((uchar*) min_value_arg),
1640
max_value((uchar*) max_value_arg), next(0),prev(0),
1641
next_key_part(0),color(BLACK),type(KEY_RANGE)
1643
left=right= &null_element;
1646
SEL_ARG::SEL_ARG(Field *field_,uint8 part_,
1647
uchar *min_value_, uchar *max_value_,
1648
uint8 min_flag_,uint8 max_flag_,uint8 maybe_flag_)
1649
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1650
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1651
field(field_), min_value(min_value_), max_value(max_value_),
1652
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1654
left=right= &null_element;
1657
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1662
/* Bail out if we have already generated too many SEL_ARGs */
1663
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1666
if (type != KEY_RANGE)
1668
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1669
return 0; // out of memory
1670
tmp->prev= *next_arg; // Link into next/prev chain
1671
(*next_arg)->next=tmp;
1676
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1677
min_flag, max_flag, maybe_flag)))
1679
tmp->parent=new_parent;
1680
tmp->next_key_part=next_key_part;
1681
if (left != &null_element)
1682
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1685
tmp->prev= *next_arg; // Link into next/prev chain
1686
(*next_arg)->next=tmp;
1689
if (right != &null_element)
1690
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1693
increment_use_count(1);
1695
tmp->elements= this->elements;
1699
SEL_ARG *SEL_ARG::first()
1701
SEL_ARG *next_arg=this;
1702
if (!next_arg->left)
1703
return 0; // MAYBE_KEY
1704
while (next_arg->left != &null_element)
1705
next_arg=next_arg->left;
1709
SEL_ARG *SEL_ARG::last()
1711
SEL_ARG *next_arg=this;
1712
if (!next_arg->right)
1713
return 0; // MAYBE_KEY
1714
while (next_arg->right != &null_element)
1715
next_arg=next_arg->right;
1721
Check if a compare is ok, when one takes ranges in account
1722
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1725
static int sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag,
1729
/* First check if there was a compare to a min or max element */
1730
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1732
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1733
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1735
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1737
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1738
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1740
if (field->real_maybe_null()) // If null is part of key
1747
goto end; // NULL where equal
1748
a++; b++; // Skip NULL marker
1750
cmp=field->key_cmp(a , b);
1751
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1753
// Check if the compared equal arguments was defined with open/closed range
1755
if (a_flag & (NEAR_MIN | NEAR_MAX))
1757
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1759
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1760
return (a_flag & NEAR_MIN) ? 2 : -2;
1761
return (a_flag & NEAR_MIN) ? 1 : -1;
1763
if (b_flag & (NEAR_MIN | NEAR_MAX))
1764
return (b_flag & NEAR_MIN) ? -2 : 2;
1765
return 0; // The elements where equal
1769
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1771
SEL_ARG tmp_link,*next_arg,*root;
1772
next_arg= &tmp_link;
1773
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1775
next_arg->next=0; // Fix last link
1776
tmp_link.next->prev=0; // Fix first link
1777
if (root) // If not OOM
1843
3321
tree->ror_scans_end= cur_ror_scan;
3322
DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "original",
3324
tree->ror_scans_end););
1845
3326
Ok, [ror_scans, ror_scans_end) is array of ptrs to initialized
1846
optimizer::RorScanInfo's.
1847
3328
Step 2: Get best ROR-intersection using an approximate algorithm.
1849
internal::my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(optimizer::RorScanInfo*),
1850
(qsort_cmp)cmp_ror_scan_info);
3330
my_qsort(tree->ror_scans, tree->n_ror_scans, sizeof(ROR_SCAN_INFO*),
3331
(qsort_cmp)cmp_ror_scan_info);
3332
DBUG_EXECUTE("info",print_ror_scans_arr(param->table, "ordered",
3334
tree->ror_scans_end););
1852
optimizer::RorScanInfo **intersect_scans= NULL; /* ROR scans used in index intersection */
1853
optimizer::RorScanInfo **intersect_scans_end= NULL;
1854
if (! (intersect_scans= (optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*) * tree->n_ror_scans)))
3336
ROR_SCAN_INFO **intersect_scans; /* ROR scans used in index intersection */
3337
ROR_SCAN_INFO **intersect_scans_end;
3338
if (!(intersect_scans= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3339
sizeof(ROR_SCAN_INFO*)*
3340
tree->n_ror_scans)))
1856
3342
intersect_scans_end= intersect_scans;
1858
3344
/* Create and incrementally update ROR intersection. */
1859
ROR_INTERSECT_INFO intersect(param);
1860
ROR_INTERSECT_INFO intersect_best(param);
3345
ROR_INTERSECT_INFO *intersect, *intersect_best;
3346
if (!(intersect= ror_intersect_init(param)) ||
3347
!(intersect_best= ror_intersect_init(param)))
1862
3350
/* [intersect_scans,intersect_scans_best) will hold the best intersection */
1863
optimizer::RorScanInfo **intersect_scans_best= NULL;
3351
ROR_SCAN_INFO **intersect_scans_best;
1864
3352
cur_ror_scan= tree->ror_scans;
1865
3353
intersect_scans_best= intersect_scans;
1866
while (cur_ror_scan != tree->ror_scans_end && ! intersect.is_covering)
3354
while (cur_ror_scan != tree->ror_scans_end && !intersect->is_covering)
1868
3356
/* S= S + first(R); R= R - first(R); */
1869
if (! ror_intersect_add(&intersect, *cur_ror_scan, false))
3357
if (!ror_intersect_add(intersect, *cur_ror_scan, FALSE))
1871
3359
cur_ror_scan++;
1875
3363
*(intersect_scans_end++)= *(cur_ror_scan++);
1877
if (intersect.total_cost < min_cost)
3365
if (intersect->total_cost < min_cost)
1879
3367
/* Local minimum found, save it */
1880
ror_intersect_cpy(&intersect_best, &intersect);
3368
ror_intersect_cpy(intersect_best, intersect);
1881
3369
intersect_scans_best= intersect_scans_end;
1882
min_cost = intersect.total_cost;
3370
min_cost = intersect->total_cost;
1886
3374
if (intersect_scans_best == intersect_scans)
3376
DBUG_PRINT("info", ("None of scans increase selectivity"));
3380
DBUG_EXECUTE("info",print_ror_scans_arr(param->table,
3381
"best ROR-intersection",
3383
intersect_scans_best););
1891
*are_all_covering= intersect.is_covering;
1892
uint32_t best_num= intersect_scans_best - intersect_scans;
1893
ror_intersect_cpy(&intersect, &intersect_best);
3385
*are_all_covering= intersect->is_covering;
3386
uint best_num= intersect_scans_best - intersect_scans;
3387
ror_intersect_cpy(intersect, intersect_best);
1896
3390
Ok, found the best ROR-intersection of non-CPK key scans.
1897
Check if we should add a CPK scan. If the obtained ROR-intersection is
3391
Check if we should add a CPK scan. If the obtained ROR-intersection is
1898
3392
covering, it doesn't make sense to add CPK scan.
1900
if (cpk_scan && ! intersect.is_covering)
3394
if (cpk_scan && !intersect->is_covering)
1902
if (ror_intersect_add(&intersect, cpk_scan, true) &&
1903
(intersect.total_cost < min_cost))
3396
if (ror_intersect_add(intersect, cpk_scan, TRUE) &&
3397
(intersect->total_cost < min_cost))
1905
cpk_scan_used= true;
3399
cpk_scan_used= TRUE;
1906
3400
intersect_best= intersect; //just set pointer here
1910
3404
/* Ok, return ROR-intersect plan if we have found one */
1911
optimizer::RorIntersectReadPlan *trp= NULL;
3405
TRP_ROR_INTERSECT *trp= NULL;
1912
3406
if (min_cost < read_time && (cpk_scan_used || best_num > 1))
1914
if (! (trp= new (param->mem_root) optimizer::RorIntersectReadPlan))
1917
if (! (trp->first_scan=
1918
(optimizer::RorScanInfo**)param->mem_root->alloc_root(sizeof(optimizer::RorScanInfo*)*best_num)))
1920
memcpy(trp->first_scan, intersect_scans, best_num*sizeof(optimizer::RorScanInfo*));
3408
if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
3410
if (!(trp->first_scan=
3411
(ROR_SCAN_INFO**)alloc_root(param->mem_root,
3412
sizeof(ROR_SCAN_INFO*)*best_num)))
3414
memcpy(trp->first_scan, intersect_scans, best_num*sizeof(ROR_SCAN_INFO*));
1921
3415
trp->last_scan= trp->first_scan + best_num;
1922
trp->is_covering= intersect_best.is_covering;
1923
trp->read_cost= intersect_best.total_cost;
3416
trp->is_covering= intersect_best->is_covering;
3417
trp->read_cost= intersect_best->total_cost;
1924
3418
/* Prevent divisons by zero */
1925
ha_rows best_rows = double2rows(intersect_best.out_rows);
3419
ha_rows best_rows = double2rows(intersect_best->out_rows);
1928
3422
set_if_smaller(param->table->quick_condition_rows, best_rows);
1929
3423
trp->records= best_rows;
1930
trp->index_scan_costs= intersect_best.index_scan_costs;
3424
trp->index_scan_costs= intersect_best->index_scan_costs;
1931
3425
trp->cpk_scan= cpk_scan_used? cpk_scan: NULL;
3426
DBUG_PRINT("info", ("Returning non-covering ROR-intersect plan:"
3427
"cost %g, records %lu",
3428
trp->read_cost, (ulong) trp->records));
1938
Get best "range" table read plan for given optimizer::SEL_TREE, also update some info
3435
Get best covering ROR-intersection.
3437
get_best_covering_ror_intersect()
3438
param Parameter from test_quick_select function.
3439
tree SEL_TREE with sets of intervals for different keys.
3440
read_time Don't return table read plans with cost > read_time.
3443
Best covering ROR-intersection plan
3444
NULL if no plan found.
3447
get_best_ror_intersect must be called for a tree before calling this
3449
This function invalidates tree->ror_scans member values.
3451
The following approximate algorithm is used:
3452
I=set of all covering indexes
3453
F=set of all fields to cover
3458
Order I by (#covered fields in F desc,
3460
number of first not covered component asc);
3461
F=F-covered by first(I);
3464
} while F is not empty.
3468
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
3472
ROR_SCAN_INFO **ror_scan_mark;
3473
ROR_SCAN_INFO **ror_scans_end= tree->ror_scans_end;
3474
DBUG_ENTER("get_best_covering_ror_intersect");
3476
for (ROR_SCAN_INFO **scan= tree->ror_scans; scan != ror_scans_end; ++scan)
3477
(*scan)->key_components=
3478
param->table->key_info[(*scan)->keynr].key_parts;
3481
Run covering-ROR-search algorithm.
3482
Assume set I is [ror_scan .. ror_scans_end)
3485
/*I=set of all covering indexes */
3486
ror_scan_mark= tree->ror_scans;
3488
MY_BITMAP *covered_fields= ¶m->tmp_covered_fields;
3489
if (!covered_fields->bitmap)
3490
covered_fields->bitmap= (my_bitmap_map*)alloc_root(param->mem_root,
3491
param->fields_bitmap_size);
3492
if (!covered_fields->bitmap ||
3493
bitmap_init(covered_fields, covered_fields->bitmap,
3494
param->table->s->fields, FALSE))
3496
bitmap_clear_all(covered_fields);
3498
double total_cost= 0.0f;
3502
DBUG_PRINT("info", ("Building covering ROR-intersection"));
3503
DBUG_EXECUTE("info", print_ror_scans_arr(param->table,
3504
"building covering ROR-I",
3505
ror_scan_mark, ror_scans_end););
3509
Update changed sorting info:
3511
number of first not covered component
3512
Calculate and save these values for each of remaining scans.
3514
for (ROR_SCAN_INFO **scan= ror_scan_mark; scan != ror_scans_end; ++scan)
3516
bitmap_subtract(&(*scan)->covered_fields, covered_fields);
3517
(*scan)->used_fields_covered=
3518
bitmap_bits_set(&(*scan)->covered_fields);
3519
(*scan)->first_uncovered_field=
3520
bitmap_get_first(&(*scan)->covered_fields);
3523
my_qsort(ror_scan_mark, ror_scans_end-ror_scan_mark, sizeof(ROR_SCAN_INFO*),
3524
(qsort_cmp)cmp_ror_scan_info_covering);
3526
DBUG_EXECUTE("info", print_ror_scans_arr(param->table,
3528
ror_scan_mark, ror_scans_end););
3531
total_cost += (*ror_scan_mark)->index_read_cost;
3532
records += (*ror_scan_mark)->records;
3533
DBUG_PRINT("info", ("Adding scan on %s",
3534
param->table->key_info[(*ror_scan_mark)->keynr].name));
3535
if (total_cost > read_time)
3537
/* F=F-covered by first(I) */
3538
bitmap_union(covered_fields, &(*ror_scan_mark)->covered_fields);
3539
all_covered= bitmap_is_subset(¶m->needed_fields, covered_fields);
3540
} while ((++ror_scan_mark < ror_scans_end) && !all_covered);
3542
if (!all_covered || (ror_scan_mark - tree->ror_scans) == 1)
3546
Ok, [tree->ror_scans .. ror_scan) holds covering index_intersection with
3549
DBUG_PRINT("info", ("Covering ROR-intersect scans cost: %g", total_cost));
3550
DBUG_EXECUTE("info", print_ror_scans_arr(param->table,
3551
"creating covering ROR-intersect",
3552
tree->ror_scans, ror_scan_mark););
3554
/* Add priority queue use cost. */
3555
total_cost += rows2double(records)*
3556
log((double)(ror_scan_mark - tree->ror_scans)) /
3557
(TIME_FOR_COMPARE_ROWID * M_LN2);
3558
DBUG_PRINT("info", ("Covering ROR-intersect full cost: %g", total_cost));
3560
if (total_cost > read_time)
3563
TRP_ROR_INTERSECT *trp;
3564
if (!(trp= new (param->mem_root) TRP_ROR_INTERSECT))
3566
uint best_num= (ror_scan_mark - tree->ror_scans);
3567
if (!(trp->first_scan= (ROR_SCAN_INFO**)alloc_root(param->mem_root,
3568
sizeof(ROR_SCAN_INFO*)*
3571
memcpy(trp->first_scan, tree->ror_scans, best_num*sizeof(ROR_SCAN_INFO*));
3572
trp->last_scan= trp->first_scan + best_num;
3573
trp->is_covering= TRUE;
3574
trp->read_cost= total_cost;
3575
trp->records= records;
3576
trp->cpk_scan= NULL;
3577
set_if_smaller(param->table->quick_condition_rows, records);
3580
("Returning covering ROR-intersect plan: cost %g, records %lu",
3581
trp->read_cost, (ulong) trp->records));
3587
Get best "range" table read plan for given SEL_TREE, also update some info
1941
3590
get_key_scans_params()
1943
3591
param Parameters from test_quick_select
1944
tree Make range select for this optimizer::SEL_TREE
1945
index_read_must_be_used true <=> assume 'index only' option will be set
3592
tree Make range select for this SEL_TREE
3593
index_read_must_be_used TRUE <=> assume 'index only' option will be set
1946
3594
(except for clustered PK indexes)
1947
update_tbl_stats true <=> update table->quick_* with information
3595
update_tbl_stats TRUE <=> update table->quick_* with information
1948
3596
about range scans we've evaluated.
1949
read_time Maximum cost. i.e. don't create read plans with
3597
read_time Maximum cost. i.e. don't create read plans with
1950
3598
cost > read_time.
1953
Find the best "range" table read plan for given optimizer::SEL_TREE.
1954
The side effects are
3601
Find the best "range" table read plan for given SEL_TREE.
3602
The side effects are
1955
3603
- tree->ror_scans is updated to indicate which scans are ROR scans.
1956
- if update_tbl_stats=true then table->quick_* is updated with info
3604
- if update_tbl_stats=TRUE then table->quick_* is updated with info
1957
3605
about every possible range scan.
3260
4767
#define CLONE_KEY1_MAYBE 1
3261
4768
#define CLONE_KEY2_MAYBE 2
3263
static uint32_t swap_clone_flag(uint32_t a)
3265
return ((a & 1) << 1) | ((a & 2) >> 1);
3268
static optimizer::SEL_TREE *
3269
tree_and(optimizer::RangeParameter *param, optimizer::SEL_TREE *tree1, optimizer::SEL_TREE *tree2)
4769
#define swap_clone_flag(A) ((A & 1) << 1) | ((A & 2) >> 1)
4773
tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4775
DBUG_ENTER("tree_and");
3275
if (tree1->type == optimizer::SEL_TREE::IMPOSSIBLE || tree2->type == optimizer::SEL_TREE::ALWAYS)
3277
if (tree2->type == optimizer::SEL_TREE::IMPOSSIBLE || tree1->type == optimizer::SEL_TREE::ALWAYS)
3279
if (tree1->type == optimizer::SEL_TREE::MAYBE)
4780
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4782
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4784
if (tree1->type == SEL_TREE::MAYBE)
3281
if (tree2->type == optimizer::SEL_TREE::KEY)
3282
tree2->type=optimizer::SEL_TREE::KEY_SMALLER;
4786
if (tree2->type == SEL_TREE::KEY)
4787
tree2->type=SEL_TREE::KEY_SMALLER;
3285
if (tree2->type == optimizer::SEL_TREE::MAYBE)
4790
if (tree2->type == SEL_TREE::MAYBE)
3287
tree1->type=optimizer::SEL_TREE::KEY_SMALLER;
4792
tree1->type=SEL_TREE::KEY_SMALLER;
3290
4795
key_map result_keys;
3291
result_keys.reset();
4796
result_keys.clear_all();
3293
4798
/* Join the trees key per key */
3294
optimizer::SEL_ARG **key1,**key2,**end;
4799
SEL_ARG **key1,**key2,**end;
3295
4800
for (key1= tree1->keys,key2= tree2->keys,end=key1+param->keys ;
3296
4801
key1 != end ; key1++,key2++)
3299
4804
if (*key1 || *key2)
3301
4806
if (*key1 && !(*key1)->simple_key())
3302
flag|=CLONE_KEY1_MAYBE;
4807
flag|=CLONE_KEY1_MAYBE;
3303
4808
if (*key2 && !(*key2)->simple_key())
3304
flag|=CLONE_KEY2_MAYBE;
4809
flag|=CLONE_KEY2_MAYBE;
3305
4810
*key1=key_and(param, *key1, *key2, flag);
3306
if (*key1 && (*key1)->type == optimizer::SEL_ARG::IMPOSSIBLE)
4811
if (*key1 && (*key1)->type == SEL_ARG::IMPOSSIBLE)
3308
tree1->type= optimizer::SEL_TREE::IMPOSSIBLE;
4813
tree1->type= SEL_TREE::IMPOSSIBLE;
3311
result_keys.set(key1 - tree1->keys);
4816
result_keys.set_bit(key1 - tree1->keys);
4818
if (*key1 && param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4819
(*key1)->test_use_count(*key1);
3314
4823
tree1->keys_map= result_keys;
3315
4824
/* dispose index_merge if there is a "range" option */
3316
if (result_keys.any())
4825
if (!result_keys.is_clear_all())
3318
4827
tree1->merges.empty();
3322
4831
/* ok, both trees are index_merge trees */
3323
4832
imerge_list_and_list(&tree1->merges, &tree2->merges);
4838
Check if two SEL_TREES can be combined into one (i.e. a single key range
4839
read can be constructed for "cond_of_tree1 OR cond_of_tree2" ) without
4843
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2,
4844
RANGE_OPT_PARAM* param)
4846
key_map common_keys= tree1->keys_map;
4847
DBUG_ENTER("sel_trees_can_be_ored");
4848
common_keys.intersect(tree2->keys_map);
4850
if (common_keys.is_clear_all())
4853
/* trees have a common key, check if they refer to same key part */
4854
SEL_ARG **key1,**key2;
4855
for (uint key_no=0; key_no < param->keys; key_no++)
4857
if (common_keys.is_set(key_no))
4859
key1= tree1->keys + key_no;
4860
key2= tree2->keys + key_no;
4861
if ((*key1)->part == (*key2)->part)
4872
Remove the trees that are not suitable for record retrieval.
4874
param Range analysis parameter
4875
tree Tree to be processed, tree->type is KEY or KEY_SMALLER
4878
This function walks through tree->keys[] and removes the SEL_ARG* trees
4879
that are not "maybe" trees (*) and cannot be used to construct quick range
4881
(*) - have type MAYBE or MAYBE_KEY. Perhaps we should remove trees of
4882
these types here as well.
4884
A SEL_ARG* tree cannot be used to construct quick select if it has
4885
tree->part != 0. (e.g. it could represent "keypart2 < const").
4887
WHY THIS FUNCTION IS NEEDED
4889
Normally we allow construction of SEL_TREE objects that have SEL_ARG
4890
trees that do not allow quick range select construction. For example for
4891
" keypart1=1 AND keypart2=2 " the execution will proceed as follows:
4892
tree1= SEL_TREE { SEL_ARG{keypart1=1} }
4893
tree2= SEL_TREE { SEL_ARG{keypart2=2} } -- can't make quick range select
4895
call tree_and(tree1, tree2) -- this joins SEL_ARGs into a usable SEL_ARG
4898
There is an exception though: when we construct index_merge SEL_TREE,
4899
any SEL_ARG* tree that cannot be used to construct quick range select can
4900
be removed, because current range analysis code doesn't provide any way
4901
that tree could be later combined with another tree.
4902
Consider an example: we should not construct
4904
merges = SEL_IMERGE {
4905
SEL_TREE(t.key1part1 = 1),
4906
SEL_TREE(t.key2part2 = 2) -- (*)
4910
- (*) cannot be used to construct quick range select,
4911
- There is no execution path that would cause (*) to be converted to
4912
a tree that could be used.
4914
The latter is easy to verify: first, notice that the only way to convert
4915
(*) into a usable tree is to call tree_and(something, (*)).
4917
Second look at what tree_and/tree_or function would do when passed a
4918
SEL_TREE that has the structure like st1 tree has, and conlcude that
4919
tree_and(something, (*)) will not be called.
4922
0 Ok, some suitable trees left
4923
1 No tree->keys[] left.
4926
static bool remove_nonrange_trees(RANGE_OPT_PARAM *param, SEL_TREE *tree)
4929
for (uint i=0; i < param->keys; i++)
4933
if (tree->keys[i]->part)
4935
tree->keys[i]= NULL;
4936
tree->keys_map.clear_bit(i);
4947
tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2)
4949
DBUG_ENTER("tree_or");
4950
if (!tree1 || !tree2)
4952
if (tree1->type == SEL_TREE::IMPOSSIBLE || tree2->type == SEL_TREE::ALWAYS)
4954
if (tree2->type == SEL_TREE::IMPOSSIBLE || tree1->type == SEL_TREE::ALWAYS)
4956
if (tree1->type == SEL_TREE::MAYBE)
4957
DBUG_RETURN(tree1); // Can't use this
4958
if (tree2->type == SEL_TREE::MAYBE)
4961
SEL_TREE *result= 0;
4962
key_map result_keys;
4963
result_keys.clear_all();
4964
if (sel_trees_can_be_ored(tree1, tree2, param))
4966
/* Join the trees key per key */
4967
SEL_ARG **key1,**key2,**end;
4968
for (key1= tree1->keys,key2= tree2->keys,end= key1+param->keys ;
4969
key1 != end ; key1++,key2++)
4971
*key1=key_or(param, *key1, *key2);
4974
result=tree1; // Added to tree1
4975
result_keys.set_bit(key1 - tree1->keys);
4977
if (param->alloced_sel_args < SEL_ARG::MAX_SEL_ARGS)
4978
(*key1)->test_use_count(*key1);
4983
result->keys_map= result_keys;
4987
/* ok, two trees have KEY type but cannot be used without index merge */
4988
if (tree1->merges.is_empty() && tree2->merges.is_empty())
4990
if (param->remove_jump_scans)
4992
bool no_trees= remove_nonrange_trees(param, tree1);
4993
no_trees= no_trees || remove_nonrange_trees(param, tree2);
4995
DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));
4998
/* both trees are "range" trees, produce new index merge structure */
4999
if (!(result= new SEL_TREE()) || !(merge= new SEL_IMERGE()) ||
5000
(result->merges.push_back(merge)) ||
5001
(merge->or_sel_tree(param, tree1)) ||
5002
(merge->or_sel_tree(param, tree2)))
5005
result->type= tree1->type;
5007
else if (!tree1->merges.is_empty() && !tree2->merges.is_empty())
5009
if (imerge_list_or_list(param, &tree1->merges, &tree2->merges))
5010
result= new SEL_TREE(SEL_TREE::ALWAYS);
5016
/* one tree is index merge tree and another is range tree */
5017
if (tree1->merges.is_empty())
5018
swap_variables(SEL_TREE*, tree1, tree2);
5020
if (param->remove_jump_scans && remove_nonrange_trees(param, tree2))
5021
DBUG_RETURN(new SEL_TREE(SEL_TREE::ALWAYS));
5022
/* add tree2 to tree1->merges, checking if it collapses to ALWAYS */
5023
if (imerge_list_or_tree(param, &tree1->merges, tree2))
5024
result= new SEL_TREE(SEL_TREE::ALWAYS);
5029
DBUG_RETURN(result);
3329
5033
/* And key trees where key1->part < key2 -> part */
3331
static optimizer::SEL_ARG *
3332
and_all_keys(optimizer::RangeParameter *param,
3333
optimizer::SEL_ARG *key1,
3334
optimizer::SEL_ARG *key2,
3335
uint32_t clone_flag)
5036
and_all_keys(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
3337
optimizer::SEL_ARG *next= NULL;
3338
5040
ulong use_count=key1->use_count;
3340
5042
if (key1->elements != 1)
5218
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5238
if (key1->part != key2->part)
5242
return 0; // Can't optimize this
5245
// If one of the key is MAYBE_KEY then the found region may be bigger
5246
if (key1->type == SEL_ARG::MAYBE_KEY)
5252
if (key2->type == SEL_ARG::MAYBE_KEY)
5259
if (key1->use_count > 0)
5261
if (key2->use_count == 0 || key1->elements > key2->elements)
5263
swap_variables(SEL_ARG *,key1,key2);
5265
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5269
// Add tree at key2 to tree at key1
5270
bool key2_shared=key2->use_count != 0;
5271
key1->maybe_flag|=key2->maybe_flag;
5273
for (key2=key2->first(); key2; )
5275
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5280
tmp=key1->first(); // tmp.min > key2.min
5283
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5284
{ // Found tmp.max < key2.min
5285
SEL_ARG *next=tmp->next;
5286
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5288
// Join near ranges like tmp.max < 0 and key2.min >= 0
5289
SEL_ARG *key2_next=key2->next;
5292
if (!(key2=new SEL_ARG(*key2)))
5293
return 0; // out of memory
5294
key2->increment_use_count(key1->use_count+1);
5295
key2->next=key2_next; // New copy of key2
5297
key2->copy_min(tmp);
5298
if (!(key1=key1->tree_delete(tmp)))
5299
{ // Only one key in tree
5306
if (!(tmp=next)) // tmp.min > key2.min
5307
break; // Copy rest of key2
5310
{ // tmp.min > key2.min
5312
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5314
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5315
{ // ranges are connected
5316
tmp->copy_min_to_min(key2);
5317
key1->merge_flags(key2);
5318
if (tmp->min_flag & NO_MIN_RANGE &&
5319
tmp->max_flag & NO_MAX_RANGE)
5321
if (key1->maybe_flag)
5322
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5325
key2->increment_use_count(-1); // Free not used tree
5331
SEL_ARG *next=key2->next; // Keys are not overlapping
5334
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5337
key1=key1->insert(cpy);
5338
key2->increment_use_count(key1->use_count+1);
5341
key1=key1->insert(key2); // Will destroy key2_root
5348
// tmp.max >= key2.min && tmp.min <= key.max (overlapping ranges)
5349
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5351
if (tmp->is_same(key2))
5353
tmp->merge_flags(key2); // Copy maybe flags
5354
key2->increment_use_count(-1); // Free not used tree
5359
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5360
eq_tree(last->next->next_key_part,key2->next_key_part))
5364
key1=key1->tree_delete(save);
5366
last->copy_min(tmp);
5367
if (last->copy_min(key2) || last->copy_max(key2))
5370
for (; key2 ; key2=key2->next)
5371
key2->increment_use_count(-1); // Free not used tree
5372
if (key1->maybe_flag)
5373
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5381
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5382
{ // tmp.min <= x < key2.min
5383
SEL_ARG *new_arg=tmp->clone_first(key2);
5386
if ((new_arg->next_key_part= key1->next_key_part))
5387
new_arg->increment_use_count(key1->use_count+1);
5388
tmp->copy_min_to_min(key2);
5389
key1=key1->insert(new_arg);
5392
// tmp.min >= key2.min && tmp.min <= key2.max
5393
SEL_ARG key(*key2); // Get copy we can modify
5396
if (tmp->cmp_min_to_min(&key) > 0)
5397
{ // key.min <= x < tmp.min
5398
SEL_ARG *new_arg=key.clone_first(tmp);
5401
if ((new_arg->next_key_part=key.next_key_part))
5402
new_arg->increment_use_count(key1->use_count+1);
5403
key1=key1->insert(new_arg);
5405
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5406
{ // tmp.min. <= x <= tmp.max
5407
tmp->maybe_flag|= key.maybe_flag;
5408
key.increment_use_count(key1->use_count+1);
5409
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5410
if (!cmp) // Key2 is ready
5412
key.copy_max_to_min(tmp);
5413
if (!(tmp=tmp->next))
5415
SEL_ARG *tmp2= new SEL_ARG(key);
5418
key1=key1->insert(tmp2);
5422
if (tmp->cmp_min_to_max(&key) > 0)
5424
SEL_ARG *tmp2= new SEL_ARG(key);
5427
key1=key1->insert(tmp2);
5433
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5436
tmp->copy_max_to_min(&key);
5437
tmp->increment_use_count(key1->use_count+1);
5438
/* Increment key count as it may be used for next loop */
5439
key.increment_use_count(1);
5440
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5441
key1=key1->insert(new_arg);
5451
SEL_ARG *next=key2->next;
5454
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5457
key2->increment_use_count(key1->use_count+1);
5458
key1=key1->insert(tmp);
5461
key1=key1->insert(key2); // Will destroy key2_root
5469
/* Compare if two trees are equal */
5471
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5475
if (!a || !b || !a->is_same(b))
5477
if (a->left != &null_element && b->left != &null_element)
5479
if (!eq_tree(a->left,b->left))
5482
else if (a->left != &null_element || b->left != &null_element)
5484
if (a->right != &null_element && b->right != &null_element)
5486
if (!eq_tree(a->right,b->right))
5489
else if (a->right != &null_element || b->right != &null_element)
5491
if (a->next_key_part != b->next_key_part)
5493
if (!a->next_key_part != !b->next_key_part ||
5494
!eq_tree(a->next_key_part, b->next_key_part))
5502
SEL_ARG::insert(SEL_ARG *key)
5504
SEL_ARG *element, **par= NULL, *last_element= NULL;
5506
for (element= this; element != &null_element ; )
5508
last_element=element;
5509
if (key->cmp_min_to_min(element) > 0)
5511
par= &element->right; element= element->right;
5515
par = &element->left; element= element->left;
5519
key->parent=last_element;
5521
if (par == &last_element->left)
5523
key->next=last_element;
5524
if ((key->prev=last_element->prev))
5525
key->prev->next=key;
5526
last_element->prev=key;
5530
if ((key->next=last_element->next))
5531
key->next->prev=key;
5532
key->prev=last_element;
5533
last_element->next=key;
5535
key->left=key->right= &null_element;
5536
SEL_ARG *root=rb_insert(key); // rebalance tree
5537
root->use_count=this->use_count; // copy root info
5538
root->elements= this->elements+1;
5539
root->maybe_flag=this->maybe_flag;
5545
** Find best key with min <= given key
5546
** Because the call context this should never return 0 to get_range
5550
SEL_ARG::find_range(SEL_ARG *key)
5552
SEL_ARG *element=this,*found=0;
5556
if (element == &null_element)
5558
int cmp=element->cmp_min_to_min(key);
5564
element=element->right;
5567
element=element->left;
5573
Remove a element from the tree
5577
key Key that is to be deleted from tree (this)
5580
This also frees all sub trees that is used by the element
5583
root of new tree (with key deleted)
5587
SEL_ARG::tree_delete(SEL_ARG *key)
5589
enum leaf_color remove_color;
5590
SEL_ARG *root,*nod,**par,*fix_par;
5591
DBUG_ENTER("tree_delete");
5596
/* Unlink from list */
5598
key->prev->next=key->next;
5600
key->next->prev=key->prev;
5601
key->increment_use_count(-1);
5605
par=key->parent_ptr();
5607
if (key->left == &null_element)
5609
*par=nod=key->right;
5610
fix_par=key->parent;
5611
if (nod != &null_element)
5612
nod->parent=fix_par;
5613
remove_color= key->color;
5615
else if (key->right == &null_element)
5617
*par= nod=key->left;
5618
nod->parent=fix_par=key->parent;
5619
remove_color= key->color;
5623
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5624
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5625
fix_par=tmp->parent;
5626
if (nod != &null_element)
5627
nod->parent=fix_par;
5628
remove_color= tmp->color;
5630
tmp->parent=key->parent; // Move node in place of key
5631
(tmp->left=key->left)->parent=tmp;
5632
if ((tmp->right=key->right) != &null_element)
5633
tmp->right->parent=tmp;
5634
tmp->color=key->color;
5636
if (fix_par == key) // key->right == key->next
5637
fix_par=tmp; // new parent of nod
5640
if (root == &null_element)
5641
DBUG_RETURN(0); // Maybe root later
5642
if (remove_color == BLACK)
5643
root=rb_delete_fixup(root,nod,fix_par);
5644
test_rb_tree(root,root->parent);
5646
root->use_count=this->use_count; // Fix root counters
5647
root->elements=this->elements-1;
5648
root->maybe_flag=this->maybe_flag;
5653
/* Functions to fix up the tree after insert and delete */
5655
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5657
SEL_ARG *y=leaf->right;
5658
leaf->right=y->left;
5659
if (y->left != &null_element)
5660
y->left->parent=leaf;
5661
if (!(y->parent=leaf->parent))
5664
*leaf->parent_ptr()=y;
5669
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5671
SEL_ARG *y=leaf->left;
5672
leaf->left=y->right;
5673
if (y->right != &null_element)
5674
y->right->parent=leaf;
5675
if (!(y->parent=leaf->parent))
5678
*leaf->parent_ptr()=y;
5685
SEL_ARG::rb_insert(SEL_ARG *leaf)
5687
SEL_ARG *y,*par,*par2,*root;
5688
root= this; root->parent= 0;
5691
while (leaf != root && (par= leaf->parent)->color == RED)
5692
{ // This can't be root or 1 level under
5693
if (par == (par2= leaf->parent->parent)->left)
5696
if (y->color == RED)
5701
leaf->color=RED; /* And the loop continues */
5705
if (leaf == par->right)
5707
left_rotate(&root,leaf->parent);
5708
par=leaf; /* leaf is now parent to old leaf */
5712
right_rotate(&root,par2);
5719
if (y->color == RED)
5724
leaf->color=RED; /* And the loop continues */
5728
if (leaf == par->left)
5730
right_rotate(&root,par);
5735
left_rotate(&root,par2);
5741
test_rb_tree(root,root->parent);
5746
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5752
while (x != root && x->color == SEL_ARG::BLACK)
5757
if (w->color == SEL_ARG::RED)
5759
w->color=SEL_ARG::BLACK;
5760
par->color=SEL_ARG::RED;
5761
left_rotate(&root,par);
5764
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5766
w->color=SEL_ARG::RED;
5771
if (w->right->color == SEL_ARG::BLACK)
5773
w->left->color=SEL_ARG::BLACK;
5774
w->color=SEL_ARG::RED;
5775
right_rotate(&root,w);
5778
w->color=par->color;
5779
par->color=SEL_ARG::BLACK;
5780
w->right->color=SEL_ARG::BLACK;
5781
left_rotate(&root,par);
5789
if (w->color == SEL_ARG::RED)
5791
w->color=SEL_ARG::BLACK;
5792
par->color=SEL_ARG::RED;
5793
right_rotate(&root,par);
5796
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5798
w->color=SEL_ARG::RED;
5803
if (w->left->color == SEL_ARG::BLACK)
5805
w->right->color=SEL_ARG::BLACK;
5806
w->color=SEL_ARG::RED;
5807
left_rotate(&root,w);
5810
w->color=par->color;
5811
par->color=SEL_ARG::BLACK;
5812
w->left->color=SEL_ARG::BLACK;
5813
right_rotate(&root,par);
5820
x->color=SEL_ARG::BLACK;
5825
/* Test that the properties for a red-black tree hold */
5828
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5830
int count_l,count_r;
5832
if (element == &null_element)
5833
return 0; // Found end of tree
5834
if (element->parent != parent)
5836
sql_print_error("Wrong tree: Parent doesn't point at parent");
5839
if (element->color == SEL_ARG::RED &&
5840
(element->left->color == SEL_ARG::RED ||
5841
element->right->color == SEL_ARG::RED))
5843
sql_print_error("Wrong tree: Found two red in a row");
5846
if (element->left == element->right && element->left != &null_element)
5848
sql_print_error("Wrong tree: Found right == left");
5851
count_l=test_rb_tree(element->left,element);
5852
count_r=test_rb_tree(element->right,element);
5853
if (count_l >= 0 && count_r >= 0)
5855
if (count_l == count_r)
5856
return count_l+(element->color == SEL_ARG::BLACK);
5857
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5860
return -1; // Error, no more warnings
5865
Count how many times SEL_ARG graph "root" refers to its part "key"
5868
count_key_part_usage()
5869
root An RB-Root node in a SEL_ARG graph.
5870
key Another RB-Root node in that SEL_ARG graph.
5873
The passed "root" node may refer to "key" node via root->next_key_part,
5876
This function counts how many times the node "key" is referred (via
5877
SEL_ARG::next_key_part) by
5878
- intervals of RB-tree pointed by "root",
5879
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5880
intervals of RB-tree pointed by "root",
5883
Here is an example (horizontal links represent next_key_part pointers,
5884
vertical links - next/prev prev pointers):
5887
|root|-----------------+
5891
+----+ +---+ $ | +---+ Here the return value
5892
| |- ... -| |---$-+--+->|key| will be 4.
5893
+----+ +---+ $ | | +---+
5898
| |---| |---------+ |
5905
Number of links to "key" from nodes reachable from "root".
5908
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5911
for (root=root->first(); root ; root=root->next)
5913
if (root->next_key_part)
5915
if (root->next_key_part == key)
5917
if (root->next_key_part->part < key->part)
5918
count+=count_key_part_usage(root->next_key_part,key);
5926
Check if SEL_ARG::use_count value is correct
5929
SEL_ARG::test_use_count()
5930
root The root node of the SEL_ARG graph (an RB-tree root node that
5931
has the least value of sel_arg->part in the entire graph, and
5932
thus is the "origin" of the graph)
5935
Check if SEL_ARG::use_count value is correct. See the definition of
5936
use_count for what is "correct".
5939
void SEL_ARG::test_use_count(SEL_ARG *root)
5942
if (this == root && use_count != 1)
5944
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5947
if (this->type != SEL_ARG::KEY_RANGE)
5949
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5952
if (pos->next_key_part)
5954
ulong count=count_key_part_usage(root,pos->next_key_part);
5955
if (count > pos->next_key_part->use_count)
5957
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5958
"should be %lu", (long unsigned int)pos,
5959
pos->next_key_part->use_count, count);
5962
pos->next_key_part->test_use_count(root);
5965
if (e_count != elements)
5966
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5967
e_count, elements, (long unsigned int) this);
3524
5972
/****************************************************************************
3525
5973
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3526
5974
****************************************************************************/
3528
5976
/* MRR range sequence, SEL_ARG* implementation: stack entry */
3529
typedef struct st_range_seq_entry
5977
typedef struct st_range_seq_entry
3532
5980
Pointers in min and max keys. They point to right-after-end of key
3533
5981
images. The 0-th entry has these pointing to key tuple start.
3535
unsigned char *min_key, *max_key;
5983
uchar *min_key, *max_key;
3538
5986
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3539
5987
min_key_flag may have NULL_RANGE set.
3541
uint32_t min_key_flag, max_key_flag;
5989
uint min_key_flag, max_key_flag;
3543
5991
/* Number of key parts */
3544
uint32_t min_key_parts, max_key_parts;
3545
optimizer::SEL_ARG *key_tree;
5992
uint min_key_parts, max_key_parts;
3546
5994
} RANGE_SEQ_ENTRY;
4340
Range sequence interface implementation for array<QuickRange>: initialize
6803
Perform key scans for all used indexes (except CPK), get rowids and merge
6804
them into an ordered non-recurrent sequence of rowids.
6806
The merge/duplicate removal is performed using Unique class. We put all
6807
rowids into Unique, get the sorted sequence and destroy the Unique.
6809
If table has a clustered primary key that covers all rows (TRUE for bdb
6810
and innodb currently) and one of the index_merge scans is a scan on PK,
6811
then rows that will be retrieved by PK scan are not put into Unique and
6812
primary key scan is not performed here, it is performed later separately.
6819
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6821
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6822
QUICK_RANGE_SELECT* cur_quick;
6825
handler *file= head->file;
6826
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::read_keys_and_merge");
6828
file->extra(HA_EXTRA_KEYREAD);
6829
head->prepare_for_position();
6831
cur_quick_it.rewind();
6832
cur_quick= cur_quick_it++;
6833
DBUG_ASSERT(cur_quick != 0);
6836
We reuse the same instance of handler so we need to call both init and
6839
if (cur_quick->init() || cur_quick->reset())
6842
unique= new Unique(refpos_order_cmp, (void *)file,
6844
thd->variables.sortbuff_size);
6849
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6851
cur_quick->range_end();
6852
cur_quick= cur_quick_it++;
6856
if (cur_quick->file->inited != handler::NONE)
6857
cur_quick->file->ha_index_end();
6858
if (cur_quick->init() || cur_quick->reset())
6864
if (result != HA_ERR_END_OF_FILE)
6866
cur_quick->range_end();
6867
DBUG_RETURN(result);
6875
/* skip row if it will be retrieved by clustered PK scan */
6876
if (pk_quick_select && pk_quick_select->row_in_ranges())
6879
cur_quick->file->position(cur_quick->record);
6880
result= unique->unique_add((char*)cur_quick->file->ref);
6886
DBUG_PRINT("info", ("ok"));
6887
/* ok, all row ids are in Unique */
6888
result= unique->get(head);
6890
doing_pk_scan= FALSE;
6891
/* index_merge currently doesn't support "using index" at all */
6892
file->extra(HA_EXTRA_NO_KEYREAD);
6893
/* start table scan */
6894
init_read_record(&read_record, thd, head, (SQL_SELECT*) 0, 1, 1);
6895
DBUG_RETURN(result);
6900
Get next row for index_merge.
6902
The rows are read from
6903
1. rowids stored in Unique.
6904
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6905
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6908
int QUICK_INDEX_MERGE_SELECT::get_next()
6911
DBUG_ENTER("QUICK_INDEX_MERGE_SELECT::get_next");
6914
DBUG_RETURN(pk_quick_select->get_next());
6916
if ((result= read_record.read_record(&read_record)) == -1)
6918
result= HA_ERR_END_OF_FILE;
6919
end_read_record(&read_record);
6920
/* All rows from Unique have been retrieved, do a clustered PK scan */
6921
if (pk_quick_select)
6923
doing_pk_scan= TRUE;
6924
if ((result= pk_quick_select->init()) ||
6925
(result= pk_quick_select->reset()))
6926
DBUG_RETURN(result);
6927
DBUG_RETURN(pk_quick_select->get_next());
6931
DBUG_RETURN(result);
6936
Retrieve next record.
6938
QUICK_ROR_INTERSECT_SELECT::get_next()
6941
Invariant on enter/exit: all intersected selects have retrieved all index
6942
records with rowid <= some_rowid_val and no intersected select has
6943
retrieved any index records with rowid > some_rowid_val.
6944
We start fresh and loop until we have retrieved the same rowid in each of
6945
the key scans or we got an error.
6947
If a Clustered PK scan is present, it is used only to check if row
6948
satisfies its condition (and never used for row retrieval).
6952
other - Error code if any error occurred.
6955
int QUICK_ROR_INTERSECT_SELECT::get_next()
6957
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6958
QUICK_RANGE_SELECT* quick;
6960
uint last_rowid_count=0;
6961
DBUG_ENTER("QUICK_ROR_INTERSECT_SELECT::get_next");
6965
/* Get a rowid for first quick and save it as a 'candidate' */
6967
error= quick->get_next();
6970
while (!error && !cpk_quick->row_in_ranges())
6971
error= quick->get_next();
6976
quick->file->position(quick->record);
6977
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6978
last_rowid_count= 1;
6980
while (last_rowid_count < quick_selects.elements)
6982
if (!(quick= quick_it++))
6990
if ((error= quick->get_next()))
6992
quick->file->position(quick->record);
6993
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6996
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6999
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
7002
while (!cpk_quick->row_in_ranges())
7004
if ((error= quick->get_next()))
7008
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
7009
last_rowid_count= 1;
7013
/* current 'candidate' row confirmed by this select */
7018
/* We get here if we got the same row ref in all scans. */
7019
if (need_to_fetch_row)
7020
error= head->file->rnd_pos(head->record[0], last_rowid);
7021
} while (error == HA_ERR_RECORD_DELETED);
7027
Retrieve next record.
7029
QUICK_ROR_UNION_SELECT::get_next()
7032
Enter/exit invariant:
7033
For each quick select in the queue a {key,rowid} tuple has been
7034
retrieved but the corresponding row hasn't been passed to output.
7038
other - Error code if any error occurred.
7041
int QUICK_ROR_UNION_SELECT::get_next()
7044
QUICK_SELECT_I *quick;
7046
DBUG_ENTER("QUICK_ROR_UNION_SELECT::get_next");
7052
if (!queue.elements)
7053
DBUG_RETURN(HA_ERR_END_OF_FILE);
7054
/* Ok, we have a queue with >= 1 scans */
7056
quick= (QUICK_SELECT_I*)queue_top(&queue);
7057
memcpy(cur_rowid, quick->last_rowid, rowid_length);
7059
/* put into queue rowid from the same stream as top element */
7060
if ((error= quick->get_next()))
7062
if (error != HA_ERR_END_OF_FILE)
7064
queue_remove(&queue, 0);
7068
quick->save_last_pos();
7069
queue_replaced(&queue);
7072
if (!have_prev_rowid)
7074
/* No rows have been returned yet */
7076
have_prev_rowid= TRUE;
7079
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
7083
cur_rowid= prev_rowid;
7086
error= head->file->rnd_pos(quick->record, prev_rowid);
7087
} while (error == HA_ERR_RECORD_DELETED);
7092
int QUICK_RANGE_SELECT::reset()
7097
HANDLER_BUFFER empty_buf;
7098
DBUG_ENTER("QUICK_RANGE_SELECT::reset");
7100
cur_range= (QUICK_RANGE**) ranges.buffer;
7102
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
7105
/* Allocate buffer if we need one but haven't allocated it yet */
7106
if (mrr_buf_size && !mrr_buf_desc)
7108
buf_size= mrr_buf_size;
7109
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7110
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7111
&mrange_buff, buf_size,
7114
/* Try to shrink the buffers until both are 0. */
7118
DBUG_RETURN(HA_ERR_OUT_OF_MEM);
7120
/* Initialize the handler buffer. */
7121
mrr_buf_desc->buffer= mrange_buff;
7122
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7123
mrr_buf_desc->end_of_used_area= mrange_buff;
7127
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7130
mrr_flags |= HA_MRR_SORTED;
7131
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7132
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7133
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7140
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4343
7143
quick_range_seq_init()
4344
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7144
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4345
7145
n_ranges Number of ranges in the sequence (ignored)
4346
flags MRR flags (currently not used)
7146
flags MRR flags (currently not used)
4349
7149
Opaque value to be passed to quick_range_seq_next
4352
range_seq_t optimizer::quick_range_seq_init(void *init_param, uint32_t, uint32_t)
7152
range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags)
4354
optimizer::QuickRangeSelect *quick= (optimizer::QuickRangeSelect*)init_param;
4355
quick->qr_traversal_ctx.first= (optimizer::QuickRange**)quick->ranges.buffer;
4356
quick->qr_traversal_ctx.cur= (optimizer::QuickRange**)quick->ranges.buffer;
4357
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
7154
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7155
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7156
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
7157
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4358
7158
quick->ranges.elements;
4359
7159
return &quick->qr_traversal_ctx;
4364
Range sequence interface implementation for array<QuickRange>: get next
7164
Range sequence interface implementation for array<QUICK_RANGE>: get next
4367
7167
quick_range_seq_next()
4368
7168
rseq Value returned from quick_range_seq_init
4373
7173
1 No more ranges in the sequence
4375
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7176
uint quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4377
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7178
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4379
7180
if (ctx->cur == ctx->last)
4380
7181
return 1; /* no more ranges */
4382
optimizer::QuickRange *cur= *(ctx->cur);
7183
QUICK_RANGE *cur= *(ctx->cur);
4383
7184
key_range *start_key= &range->start_key;
4384
key_range *end_key= &range->end_key;
7185
key_range *end_key= &range->end_key;
4386
start_key->key= cur->min_key;
7187
start_key->key= cur->min_key;
4387
7188
start_key->length= cur->min_length;
4388
7189
start_key->keypart_map= cur->min_keypart_map;
4389
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
4390
(cur->flag & EQ_RANGE) ?
4391
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
4392
end_key->key= cur->max_key;
4393
end_key->length= cur->max_length;
7190
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7191
(cur->flag & EQ_RANGE) ?
7192
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7193
end_key->key= cur->max_key;
7194
end_key->length= cur->max_length;
4394
7195
end_key->keypart_map= cur->max_keypart_map;
4396
7197
We use HA_READ_AFTER_KEY here because if we are reading on a key
4397
7198
prefix. We want to find all keys with this prefix.
4399
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7200
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4401
7202
range->range_flag= cur->flag;
4407
static inline uint32_t get_field_keypart(KeyInfo *index, Field *field);
4409
static inline optimizer::SEL_ARG * get_index_range_tree(uint32_t index,
4410
optimizer::SEL_TREE *range_tree,
4411
optimizer::Parameter *param,
4412
uint32_t *param_idx);
4414
static bool get_constant_key_infix(KeyInfo *index_info,
4415
optimizer::SEL_ARG *index_range_tree,
4416
KeyPartInfo *first_non_group_part,
4417
KeyPartInfo *min_max_arg_part,
4418
KeyPartInfo *last_part,
4420
unsigned char *key_infix,
4421
uint32_t *key_infix_len,
4422
KeyPartInfo **first_non_infix_part);
4424
static bool check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item);
7209
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7212
mrr_persistent_flag_storage()
7213
seq Range sequence being traversed
7217
MRR/NDB implementation needs to store some bits for each range. This
7218
function returns a reference to the "range_flag" associated with the
7221
This function should be removed when we get a proper MRR/NDB
7225
Reference to range_flag associated with range number #idx
7228
uint16 &mrr_persistent_flag_storage(range_seq_t seq, uint idx)
7230
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7231
return ctx->first[idx]->flag;
7236
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7239
mrr_get_ptr_by_idx()
7240
seq Range sequence bening traversed
7241
idx Number of the range
7244
An extension of MRR range sequence interface needed by NDB: return the
7245
data associated with the given range.
7247
A proper MRR interface implementer is supposed to store and return
7248
range-associated data. NDB stores number of the range instead. So this
7249
is a helper function that translates range number to range associated
7252
This function does nothing, as currrently there is only one user of the
7253
MRR interface - the quick range select code, and this user doesn't need
7254
to use range-associated data.
7257
Reference to range-associated data
7260
char* &mrr_get_ptr_by_idx(range_seq_t seq, uint idx)
7268
Get next possible record using quick-struct.
7271
QUICK_RANGE_SELECT::get_next()
7274
Record is read into table->record[0]
7278
HA_ERR_END_OF_FILE No (more) rows in range
7282
int QUICK_RANGE_SELECT::get_next()
7285
DBUG_ENTER("QUICK_RANGE_SELECT::get_next");
7286
if (in_ror_merged_scan)
7289
We don't need to signal the bitmap change as the bitmap is always the
7290
same for this head->file
7292
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7295
int result= file->multi_range_read_next(&dummy);
7297
if (in_ror_merged_scan)
7299
/* Restore bitmaps set on entry */
7300
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7302
DBUG_RETURN(result);
7307
Get the next record with a different prefix.
7310
QUICK_RANGE_SELECT::get_next_prefix()
7311
prefix_length length of cur_prefix
7312
cur_prefix prefix of a key to be searched for
7315
Each subsequent call to the method retrieves the first record that has a
7316
prefix with length prefix_length different from cur_prefix, such that the
7317
record with the new prefix is within the ranges described by
7318
this->ranges. The record found is stored into the buffer pointed by
7320
The method is useful for GROUP-BY queries with range conditions to
7321
discover the prefix of the next group that satisfies the range conditions.
7324
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7325
methods should be unified into a more general one to reduce code
7330
HA_ERR_END_OF_FILE if returned all keys
7331
other if some error occurred
7334
int QUICK_RANGE_SELECT::get_next_prefix(uint prefix_length,
7335
key_part_map keypart_map,
7338
DBUG_ENTER("QUICK_RANGE_SELECT::get_next_prefix");
7343
key_range start_key, end_key;
7346
/* Read the next record in the same range with prefix after cur_prefix. */
7347
DBUG_ASSERT(cur_prefix != 0);
7348
result= file->index_read_map(record, cur_prefix, keypart_map,
7350
if (result || (file->compare_key(file->end_range) <= 0))
7351
DBUG_RETURN(result);
7354
uint count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7357
/* Ranges have already been used up before. None is left for read. */
7359
DBUG_RETURN(HA_ERR_END_OF_FILE);
7361
last_range= *(cur_range++);
7363
start_key.key= (const uchar*) last_range->min_key;
7364
start_key.length= min(last_range->min_length, prefix_length);
7365
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7366
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7367
(last_range->flag & EQ_RANGE) ?
7368
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7369
end_key.key= (const uchar*) last_range->max_key;
7370
end_key.length= min(last_range->max_length, prefix_length);
7371
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7373
We use READ_AFTER_KEY here because if we are reading on a key
7374
prefix we want to find all keys with this prefix
7376
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7379
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7380
last_range->max_keypart_map ? &end_key : 0,
7381
test(last_range->flag & EQ_RANGE),
7383
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7384
last_range= 0; // Stop searching
7386
if (result != HA_ERR_END_OF_FILE)
7387
DBUG_RETURN(result);
7388
last_range= 0; // No matching rows; go to next range
7394
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7397
It is assumed that currently a scan is being done on another index
7398
which reads all necessary parts of the index that is scanned by this
7400
The implementation does a binary search on sorted array of disjoint
7401
ranges, without taking size of range into account.
7403
This function is used to filter out clustered PK scan rows in
7404
index_merge quick select.
7407
TRUE if current row will be retrieved by this quick select
7411
bool QUICK_RANGE_SELECT::row_in_ranges()
7415
uint max= ranges.elements - 1;
7416
uint mid= (max + min)/2;
7420
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7422
/* current row value > mid->max */
7427
mid= (min + max) / 2;
7429
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7430
return (!cmp_next(res) && !cmp_prev(res));
7434
This is a hack: we inherit from QUICK_SELECT so that we can use the
7435
get_next() interface, but we have to hold a pointer to the original
7436
QUICK_SELECT because its data are used all over the place. What
7437
should be done is to factor out the data that is needed into a base
7438
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7439
which handle the ranges and implement the get_next() function. But
7440
for now, this seems to work right at least.
7443
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7444
uint used_key_parts_arg,
7446
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7450
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7451
QUICK_RANGE **end_range= pr + ranges.elements;
7452
for (; pr!=end_range; pr++)
7453
rev_ranges.push_front(*pr);
7455
/* Remove EQ_RANGE flag for keys that are not using the full key */
7456
for (r = rev_it++; r; r = rev_it++)
7458
if ((r->flag & EQ_RANGE) &&
7459
head->key_info[index].key_length != r->max_length)
7460
r->flag&= ~EQ_RANGE;
7463
q->dont_free=1; // Don't free shared mem
7468
int QUICK_SELECT_DESC::get_next()
7470
DBUG_ENTER("QUICK_SELECT_DESC::get_next");
7472
/* The max key is handled as follows:
7473
* - if there is NO_MAX_RANGE, start at the end and move backwards
7474
* - if it is an EQ_RANGE, which means that max key covers the entire
7475
* key, go directly to the key and read through it (sorting backwards is
7476
* same as sorting forwards)
7477
* - if it is NEAR_MAX, go to the key or next, step back once, and
7479
* - otherwise (not NEAR_MAX == include the key), go after the key,
7480
* step back once, and move backwards
7487
{ // Already read through key
7488
result = ((last_range->flag & EQ_RANGE)
7489
? file->index_next_same(record, last_range->min_key,
7490
last_range->min_length) :
7491
file->index_prev(record));
7494
if (cmp_prev(*rev_it.ref()) == 0)
7497
else if (result != HA_ERR_END_OF_FILE)
7498
DBUG_RETURN(result);
7501
if (!(last_range= rev_it++))
7502
DBUG_RETURN(HA_ERR_END_OF_FILE); // All ranges used
7504
if (last_range->flag & NO_MAX_RANGE) // Read last record
7507
if ((local_error=file->index_last(record)))
7508
DBUG_RETURN(local_error); // Empty table
7509
if (cmp_prev(last_range) == 0)
7511
last_range= 0; // No match; go to next range
7515
if (last_range->flag & EQ_RANGE)
7517
result = file->index_read_map(record, last_range->max_key,
7518
last_range->max_keypart_map,
7523
DBUG_ASSERT(last_range->flag & NEAR_MAX ||
7524
range_reads_after_key(last_range));
7525
result=file->index_read_map(record, last_range->max_key,
7526
last_range->max_keypart_map,
7527
((last_range->flag & NEAR_MAX) ?
7528
HA_READ_BEFORE_KEY :
7529
HA_READ_PREFIX_LAST_OR_PREV));
7533
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7534
DBUG_RETURN(result);
7535
last_range= 0; // Not found, to next range
7538
if (cmp_prev(last_range) == 0)
7540
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7541
last_range= 0; // Stop searching
7542
DBUG_RETURN(0); // Found key is in range
7544
last_range= 0; // To next range
7550
Compare if found key is over max-value
7551
Returns 0 if key <= range->max_key
7552
TODO: Figure out why can't this function be as simple as cmp_prev().
7555
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7557
if (range_arg->flag & NO_MAX_RANGE)
7558
return 0; /* key can't be to large */
7560
KEY_PART *key_part=key_parts;
7563
for (uchar *key=range_arg->max_key, *end=key+range_arg->max_length;
7565
key+= store_length, key_part++)
7568
store_length= key_part->store_length;
7569
if (key_part->null_bit)
7573
if (!key_part->field->is_null())
7577
else if (key_part->field->is_null())
7579
key++; // Skip null byte
7582
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7587
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7592
Returns 0 if found key is inside range (found key >= range->min_key).
7595
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7598
if (range_arg->flag & NO_MIN_RANGE)
7599
return 0; /* key can't be to small */
7601
cmp= key_cmp(key_part_info, range_arg->min_key,
7602
range_arg->min_length);
7603
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7605
return 1; // outside of range
7610
* TRUE if this range will require using HA_READ_AFTER_KEY
7611
See comment in get_next() about this
7614
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7616
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7617
!(range_arg->flag & EQ_RANGE) ||
7618
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7622
void QUICK_RANGE_SELECT::add_info_string(String *str)
7624
KEY *key_info= head->key_info + index;
7625
str->append(key_info->name);
7628
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7630
QUICK_RANGE_SELECT *quick;
7632
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7633
str->append(STRING_WITH_LEN("sort_union("));
7634
while ((quick= it++))
7640
quick->add_info_string(str);
7642
if (pk_quick_select)
7645
pk_quick_select->add_info_string(str);
7650
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7653
QUICK_RANGE_SELECT *quick;
7654
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7655
str->append(STRING_WITH_LEN("intersect("));
7656
while ((quick= it++))
7658
KEY *key_info= head->key_info + quick->index;
7663
str->append(key_info->name);
7667
KEY *key_info= head->key_info + cpk_quick->index;
7669
str->append(key_info->name);
7674
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7677
QUICK_SELECT_I *quick;
7678
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7679
str->append(STRING_WITH_LEN("union("));
7680
while ((quick= it++))
7686
quick->add_info_string(str);
7692
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7693
String *used_lengths)
7697
KEY *key_info= head->key_info + index;
7698
key_names->append(key_info->name);
7699
length= longlong2str(max_used_key_length, buf, 10) - buf;
7700
used_lengths->append(buf, length);
7703
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7704
String *used_lengths)
7709
QUICK_RANGE_SELECT *quick;
7711
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7712
while ((quick= it++))
7718
key_names->append(',');
7719
used_lengths->append(',');
7722
KEY *key_info= head->key_info + quick->index;
7723
key_names->append(key_info->name);
7724
length= longlong2str(quick->max_used_key_length, buf, 10) - buf;
7725
used_lengths->append(buf, length);
7727
if (pk_quick_select)
7729
KEY *key_info= head->key_info + pk_quick_select->index;
7730
key_names->append(',');
7731
key_names->append(key_info->name);
7732
length= longlong2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7733
used_lengths->append(',');
7734
used_lengths->append(buf, length);
7738
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7739
String *used_lengths)
7744
QUICK_RANGE_SELECT *quick;
7745
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7746
while ((quick= it++))
7748
KEY *key_info= head->key_info + quick->index;
7753
key_names->append(',');
7754
used_lengths->append(',');
7756
key_names->append(key_info->name);
7757
length= longlong2str(quick->max_used_key_length, buf, 10) - buf;
7758
used_lengths->append(buf, length);
7763
KEY *key_info= head->key_info + cpk_quick->index;
7764
key_names->append(',');
7765
key_names->append(key_info->name);
7766
length= longlong2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7767
used_lengths->append(',');
7768
used_lengths->append(buf, length);
7772
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7773
String *used_lengths)
7776
QUICK_SELECT_I *quick;
7777
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7778
while ((quick= it++))
7784
used_lengths->append(',');
7785
key_names->append(',');
7787
quick->add_keys_and_lengths(key_names, used_lengths);
7792
/*******************************************************************************
7793
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7794
*******************************************************************************/
7796
static inline uint get_field_keypart(KEY *index, Field *field);
7797
static inline SEL_ARG * get_index_range_tree(uint index, SEL_TREE* range_tree,
7798
PARAM *param, uint *param_idx);
7799
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7800
KEY_PART_INFO *first_non_group_part,
7801
KEY_PART_INFO *min_max_arg_part,
7802
KEY_PART_INFO *last_part, THD *thd,
7803
uchar *key_infix, uint *key_infix_len,
7804
KEY_PART_INFO **first_non_infix_part);
7806
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7807
Field::imagetype image_type);
4427
cost_group_min_max(Table* table,
4428
KeyInfo *index_info,
4429
uint32_t used_key_parts,
4430
uint32_t group_key_parts,
4431
optimizer::SEL_TREE *range_tree,
4432
optimizer::SEL_ARG *index_tree,
4433
ha_rows quick_prefix_records,
7810
cost_group_min_max(TABLE* table, KEY *index_info, uint used_key_parts,
7811
uint group_key_parts, SEL_TREE *range_tree,
7812
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7813
bool have_min, bool have_max,
7814
double *read_cost, ha_rows *records);
5551
8881
quick->update_key_stat();
5552
8882
quick->adjust_prefix_ranges();
5558
optimizer::QuickSelectInterface *optimizer::RangeReadPlan::make_quick(optimizer::Parameter *param, bool, memory::Root *parent_alloc)
5560
optimizer::QuickRangeSelect *quick= NULL;
5561
if ((quick= optimizer::get_quick_select(param,
5568
quick->records= records;
5569
quick->read_time= read_cost;
5575
uint32_t optimizer::RorScanInfo::findFirstNotSet() const
5577
boost::dynamic_bitset<> map= bitsToBitset();
5578
for (boost::dynamic_bitset<>::size_type i= 0; i < map.size(); i++)
5589
size_t optimizer::RorScanInfo::getBitCount() const
5591
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5592
return tmp_bitset.count();
5596
void optimizer::RorScanInfo::subtractBitset(const boost::dynamic_bitset<>& in_bitset)
5598
boost::dynamic_bitset<> tmp_bitset= bitsToBitset();
5599
tmp_bitset-= in_bitset;
5600
covered_fields= tmp_bitset.to_ulong();
5604
boost::dynamic_bitset<> optimizer::RorScanInfo::bitsToBitset() const
5607
uint64_t conv= covered_fields;
5610
res.push_back((conv & 1) + '0');
5615
std::reverse(res.begin(), res.end());
5617
string final(covered_fields_size - res.length(), '0');
5619
return (boost::dynamic_bitset<>(final));
5623
} /* namespace drizzled */
8889
Construct new quick select for group queries with min/max.
8892
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8893
table The table being accessed
8894
join Descriptor of the current query
8895
have_min TRUE if the query selects a MIN function
8896
have_max TRUE if the query selects a MAX function
8897
min_max_arg_part The only argument field of all MIN/MAX functions
8898
group_prefix_len Length of all key parts in the group prefix
8899
prefix_key_parts All key parts in the group prefix
8900
index_info The index chosen for data access
8901
use_index The id of index_info
8902
read_cost Cost of this access method
8903
records Number of records returned
8904
key_infix_len Length of the key infix appended to the group prefix
8905
key_infix Infix of constants from equality predicates
8906
parent_alloc Memory pool for this and quick_prefix_select data
8912
QUICK_GROUP_MIN_MAX_SELECT::
8913
QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join_arg, bool have_min_arg,
8915
KEY_PART_INFO *min_max_arg_part_arg,
8916
uint group_prefix_len_arg, uint group_key_parts_arg,
8917
uint used_key_parts_arg, KEY *index_info_arg,
8918
uint use_index, double read_cost_arg,
8919
ha_rows records_arg, uint key_infix_len_arg,
8920
uchar *key_infix_arg, MEM_ROOT *parent_alloc)
8921
:join(join_arg), index_info(index_info_arg),
8922
group_prefix_len(group_prefix_len_arg),
8923
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8924
have_max(have_max_arg), seen_first_key(FALSE),
8925
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8926
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8927
max_functions_it(NULL)
8932
record= head->record[0];
8933
tmp_record= head->record[1];
8934
read_time= read_cost_arg;
8935
records= records_arg;
8936
used_key_parts= used_key_parts_arg;
8937
real_key_parts= used_key_parts_arg;
8938
real_prefix_len= group_prefix_len + key_infix_len;
8940
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8943
We can't have parent_alloc set as the init function can't handle this case
8946
DBUG_ASSERT(!parent_alloc);
8949
init_sql_alloc(&alloc, join->thd->variables.range_alloc_block_size, 0);
8950
join->thd->mem_root= &alloc;
8953
bzero(&alloc, sizeof(MEM_ROOT)); // ensure that it's not used
8958
Do post-constructor initialization.
8961
QUICK_GROUP_MIN_MAX_SELECT::init()
8964
The method performs initialization that cannot be done in the constructor
8965
such as memory allocations that may fail. It allocates memory for the
8966
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8967
updated during execution.
8974
int QUICK_GROUP_MIN_MAX_SELECT::init()
8976
if (group_prefix) /* Already initialized. */
8979
if (!(last_prefix= (uchar*) alloc_root(&alloc, group_prefix_len)))
8982
We may use group_prefix to store keys with all select fields, so allocate
8983
enough space for it.
8985
if (!(group_prefix= (uchar*) alloc_root(&alloc,
8986
real_prefix_len + min_max_arg_len)))
8989
if (key_infix_len > 0)
8992
The memory location pointed to by key_infix will be deleted soon, so
8993
allocate a new buffer and copy the key_infix into it.
8995
uchar *tmp_key_infix= (uchar*) alloc_root(&alloc, key_infix_len);
8998
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8999
this->key_infix= tmp_key_infix;
9002
if (min_max_arg_part)
9004
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
9009
if (!(min_functions= new List<Item_sum>))
9013
min_functions= NULL;
9016
if (!(max_functions= new List<Item_sum>))
9020
max_functions= NULL;
9022
Item_sum *min_max_item;
9023
Item_sum **func_ptr= join->sum_funcs;
9024
while ((min_max_item= *(func_ptr++)))
9026
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
9027
min_functions->push_back(min_max_item);
9028
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
9029
max_functions->push_back(min_max_item);
9034
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
9040
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
9045
min_max_ranges.elements= 0;
9051
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
9053
DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT");
9054
if (file->inited != handler::NONE)
9055
file->ha_index_end();
9056
if (min_max_arg_part)
9057
delete_dynamic(&min_max_ranges);
9058
free_root(&alloc,MYF(0));
9059
delete min_functions_it;
9060
delete max_functions_it;
9061
delete quick_prefix_select;
9067
Eventually create and add a new quick range object.
9070
QUICK_GROUP_MIN_MAX_SELECT::add_range()
9071
sel_range Range object from which a
9074
Construct a new QUICK_RANGE object from a SEL_ARG object, and
9075
add it to the array min_max_ranges. If sel_arg is an infinite
9076
range, e.g. (x < 5 or x > 4), then skip it and do not construct
9084
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
9087
uint range_flag= sel_range->min_flag | sel_range->max_flag;
9089
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
9090
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
9093
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
9094
!(sel_range->max_flag & NO_MAX_RANGE))
9096
if (sel_range->maybe_null &&
9097
sel_range->min_value[0] && sel_range->max_value[0])
9098
range_flag|= NULL_RANGE; /* IS NULL condition */
9099
else if (memcmp(sel_range->min_value, sel_range->max_value,
9100
min_max_arg_len) == 0)
9101
range_flag|= EQ_RANGE; /* equality condition */
9103
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
9104
make_keypart_map(sel_range->part),
9105
sel_range->max_value, min_max_arg_len,
9106
make_keypart_map(sel_range->part),
9110
if (insert_dynamic(&min_max_ranges, (uchar*)&range))
9117
Opens the ranges if there are more conditions in quick_prefix_select than
9118
the ones used for jumping through the prefixes.
9121
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9124
quick_prefix_select is made over the conditions on the whole key.
9125
It defines a number of ranges of length x.
9126
However when jumping through the prefixes we use only the the first
9127
few most significant keyparts in the range key. However if there
9128
are more keyparts to follow the ones we are using we must make the
9129
condition on the key inclusive (because x < "ab" means
9130
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9131
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9133
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9135
if (quick_prefix_select &&
9136
group_prefix_len < quick_prefix_select->max_used_key_length)
9141
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9145
get_dynamic(arr, (uchar*)&range, inx);
9146
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9153
Determine the total number and length of the keys that will be used for
9157
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9160
The total length of the keys used for index lookup depends on whether
9161
there are any predicates referencing the min/max argument, and/or if
9162
the min/max argument field can be NULL.
9163
This function does an optimistic analysis whether the search key might
9164
be extended by a constant for the min/max keypart. It is 'optimistic'
9165
because during actual execution it may happen that a particular range
9166
is skipped, and then a shorter key will be used. However this is data
9167
dependent and can't be easily estimated here.
9173
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9175
max_used_key_length= real_prefix_len;
9176
if (min_max_ranges.elements > 0)
9178
QUICK_RANGE *cur_range;
9180
{ /* Check if the right-most range has a lower boundary. */
9181
get_dynamic(&min_max_ranges, (uchar*)&cur_range,
9182
min_max_ranges.elements - 1);
9183
if (!(cur_range->flag & NO_MIN_RANGE))
9185
max_used_key_length+= min_max_arg_len;
9191
{ /* Check if the left-most range has an upper boundary. */
9192
get_dynamic(&min_max_ranges, (uchar*)&cur_range, 0);
9193
if (!(cur_range->flag & NO_MAX_RANGE))
9195
max_used_key_length+= min_max_arg_len;
9201
else if (have_min && min_max_arg_part &&
9202
min_max_arg_part->field->real_maybe_null())
9205
If a MIN/MAX argument value is NULL, we can quickly determine
9206
that we're in the beginning of the next group, because NULLs
9207
are always < any other value. This allows us to quickly
9208
determine the end of the current group and jump to the next
9209
group (see next_min()) and thus effectively increases the
9212
max_used_key_length+= min_max_arg_len;
9219
Initialize a quick group min/max select for key retrieval.
9222
QUICK_GROUP_MIN_MAX_SELECT::reset()
9225
Initialize the index chosen for access and find and store the prefix
9226
of the last group. The method is expensive since it performs disk access.
9233
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9236
DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::reset");
9238
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9239
if ((result= file->ha_index_init(index,1)))
9240
DBUG_RETURN(result);
9241
if (quick_prefix_select && quick_prefix_select->reset())
9243
result= file->index_last(record);
9244
if (result == HA_ERR_END_OF_FILE)
9246
/* Save the prefix of the last group. */
9247
key_copy(last_prefix, record, index_info, group_prefix_len);
9255
Get the next key containing the MIN and/or MAX key for the next group.
9258
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9261
The method finds the next subsequent group of records that satisfies the
9262
query conditions and finds the keys that contain the MIN/MAX values for
9263
the key part referenced by the MIN/MAX function(s). Once a group and its
9264
MIN/MAX values are found, store these values in the Item_sum objects for
9265
the MIN/MAX functions. The rest of the values in the result row are stored
9266
in the Item_field::result_field of each select field. If the query does
9267
not contain MIN and/or MAX functions, then the function only finds the
9268
group prefix, which is a query answer itself.
9271
If both MIN and MAX are computed, then we use the fact that if there is
9272
no MIN key, there can't be a MAX key as well, so we can skip looking
9273
for a MAX key in this case.
9277
HA_ERR_END_OF_FILE if returned all keys
9278
other if some error occurred
9281
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9286
int is_last_prefix= 0;
9288
DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::get_next");
9291
Loop until a group is found that satisfies all query conditions or the last
9296
result= next_prefix();
9298
Check if this is the last group prefix. Notice that at this point
9299
this->record contains the current prefix in record format.
9303
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9305
DBUG_ASSERT(is_last_prefix <= 0);
9309
if (result == HA_ERR_KEY_NOT_FOUND)
9316
min_res= next_min();
9318
update_min_result();
9320
/* If there is no MIN in the group, there is no MAX either. */
9321
if ((have_max && !have_min) ||
9322
(have_max && have_min && (min_res == 0)))
9324
max_res= next_max();
9326
update_max_result();
9327
/* If a MIN was found, a MAX must have been found as well. */
9328
DBUG_ASSERT((have_max && !have_min) ||
9329
(have_max && have_min && (max_res == 0)));
9332
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9333
are equality predicates for the key parts after the group, find the
9334
first sub-group with the extended prefix.
9336
if (!have_min && !have_max && key_infix_len > 0)
9337
result= file->index_read_map(record, group_prefix,
9338
make_prev_keypart_map(real_key_parts),
9341
result= have_min ? min_res : have_max ? max_res : result;
9342
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9343
is_last_prefix != 0);
9348
Partially mimic the behavior of end_select_send. Copy the
9349
field data from Item_field::field into Item_field::result_field
9350
of each non-aggregated field (the group fields, and optionally
9351
other fields in non-ANSI SQL mode).
9353
copy_fields(&join->tmp_table_param);
9355
else if (result == HA_ERR_KEY_NOT_FOUND)
9356
result= HA_ERR_END_OF_FILE;
9358
DBUG_RETURN(result);
9363
Retrieve the minimal key in the next group.
9366
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9369
Find the minimal key within this group such that the key satisfies the query
9370
conditions and NULL semantics. The found key is loaded into this->record.
9373
Depending on the values of min_max_ranges.elements, key_infix_len, and
9374
whether there is a NULL in the MIN field, this function may directly
9375
return without any data access. In this case we use the key loaded into
9376
this->record by the call to this->next_prefix() just before this call.
9380
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9381
HA_ERR_END_OF_FILE - "" -
9382
other if some error occurred
9385
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9388
DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_min");
9390
/* Find the MIN key using the eventually extended group prefix. */
9391
if (min_max_ranges.elements > 0)
9393
if ((result= next_min_in_range()))
9394
DBUG_RETURN(result);
9398
/* Apply the constant equality conditions to the non-group select fields */
9399
if (key_infix_len > 0)
9401
if ((result= file->index_read_map(record, group_prefix,
9402
make_prev_keypart_map(real_key_parts),
9403
HA_READ_KEY_EXACT)))
9404
DBUG_RETURN(result);
9408
If the min/max argument field is NULL, skip subsequent rows in the same
9409
group with NULL in it. Notice that:
9410
- if the first row in a group doesn't have a NULL in the field, no row
9411
in the same group has (because NULL < any other value),
9412
- min_max_arg_part->field->ptr points to some place in 'record'.
9414
if (min_max_arg_part && min_max_arg_part->field->is_null())
9416
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9417
key_copy(tmp_record, record, index_info, 0);
9418
result= file->index_read_map(record, tmp_record,
9419
make_keypart_map(real_key_parts),
9422
Check if the new record belongs to the current group by comparing its
9423
prefix with the group's prefix. If it is from the next group, then the
9424
whole group has NULLs in the MIN/MAX field, so use the first record in
9425
the group as a result.
9427
It is possible to reuse this new record as the result candidate for the
9428
next call to next_min(), and to save one lookup in the next call. For
9429
this add a new member 'this->next_group_prefix'.
9433
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9434
key_restore(record, tmp_record, index_info, 0);
9436
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9437
result= 0; /* There is a result in any case. */
9442
If the MIN attribute is non-nullable, this->record already contains the
9443
MIN key in the group, so just return.
9445
DBUG_RETURN(result);
9450
Retrieve the maximal key in the next group.
9453
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9456
Lookup the maximal key of the group, and store it into this->record.
9460
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9461
HA_ERR_END_OF_FILE - "" -
9462
other if some error occurred
9465
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9469
DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_max");
9471
/* Get the last key in the (possibly extended) group. */
9472
if (min_max_ranges.elements > 0)
9473
result= next_max_in_range();
9475
result= file->index_read_map(record, group_prefix,
9476
make_prev_keypart_map(real_key_parts),
9477
HA_READ_PREFIX_LAST);
9478
DBUG_RETURN(result);
9483
Determine the prefix of the next group.
9486
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9489
Determine the prefix of the next group that satisfies the query conditions.
9490
If there is a range condition referencing the group attributes, use a
9491
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9492
condition. If there is a key infix of constants, append this infix
9493
immediately after the group attributes. The possibly extended prefix is
9494
stored in this->group_prefix. The first key of the found group is stored in
9495
this->record, on which relies this->next_min().
9499
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9500
HA_ERR_END_OF_FILE if there are no more keys
9501
other if some error occurred
9503
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9506
DBUG_ENTER("QUICK_GROUP_MIN_MAX_SELECT::next_prefix");
9508
if (quick_prefix_select)
9510
uchar *cur_prefix= seen_first_key ? group_prefix : NULL;
9511
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9512
make_prev_keypart_map(group_key_parts), cur_prefix)))
9513
DBUG_RETURN(result);
9514
seen_first_key= TRUE;
9518
if (!seen_first_key)
9520
result= file->index_first(record);
9522
DBUG_RETURN(result);
9523
seen_first_key= TRUE;
9527
/* Load the first key in this group into record. */
9528
result= file->index_read_map(record, group_prefix,
9529
make_prev_keypart_map(group_key_parts),
9532
DBUG_RETURN(result);
9536
/* Save the prefix of this group for subsequent calls. */
9537
key_copy(group_prefix, record, index_info, group_prefix_len);
9538
/* Append key_infix to group_prefix. */
9539
if (key_infix_len > 0)
9540
memcpy(group_prefix + group_prefix_len,
9541
key_infix, key_infix_len);
9548
Find the minimal key in a group that satisfies some range conditions for the
9549
min/max argument field.
9552
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9555
Given the sequence of ranges min_max_ranges, find the minimal key that is
9556
in the left-most possible range. If there is no such key, then the current
9557
group does not have a MIN key that satisfies the WHERE clause. If a key is
9558
found, its value is stored in this->record.
9562
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9564
HA_ERR_END_OF_FILE - "" -
9568
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9570
ha_rkey_function find_flag;
9571
key_part_map keypart_map;
9572
QUICK_RANGE *cur_range;
9573
bool found_null= FALSE;
9574
int result= HA_ERR_KEY_NOT_FOUND;
9576
DBUG_ASSERT(min_max_ranges.elements > 0);
9578
for (uint range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9579
{ /* Search from the left-most range to the right. */
9580
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx);
9583
If the current value for the min/max argument is bigger than the right
9584
boundary of cur_range, there is no need to check this range.
9586
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9587
(key_cmp(min_max_arg_part, (const uchar*) cur_range->max_key,
9588
min_max_arg_len) == 1))
9591
if (cur_range->flag & NO_MIN_RANGE)
9593
keypart_map= make_prev_keypart_map(real_key_parts);
9594
find_flag= HA_READ_KEY_EXACT;
9598
/* Extend the search key with the lower boundary for this range. */
9599
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9600
cur_range->min_length);
9601
keypart_map= make_keypart_map(real_key_parts);
9602
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9603
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9604
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9607
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9610
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9611
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9612
continue; /* Check the next range. */
9615
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9616
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9617
range, it can't succeed for any other subsequent range.
9622
/* A key was found. */
9623
if (cur_range->flag & EQ_RANGE)
9624
break; /* No need to perform the checks below for equal keys. */
9626
if (cur_range->flag & NULL_RANGE)
9629
Remember this key, and continue looking for a non-NULL key that
9630
satisfies some other condition.
9632
memcpy(tmp_record, record, head->s->rec_buff_length);
9637
/* Check if record belongs to the current group. */
9638
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9640
result= HA_ERR_KEY_NOT_FOUND;
9644
/* If there is an upper limit, check if the found key is in the range. */
9645
if ( !(cur_range->flag & NO_MAX_RANGE) )
9647
/* Compose the MAX key for the range. */
9648
uchar *max_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9649
memcpy(max_key, group_prefix, real_prefix_len);
9650
memcpy(max_key + real_prefix_len, cur_range->max_key,
9651
cur_range->max_length);
9652
/* Compare the found key with max_key. */
9653
int cmp_res= key_cmp(index_info->key_part, max_key,
9654
real_prefix_len + min_max_arg_len);
9655
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9657
result= HA_ERR_KEY_NOT_FOUND;
9661
/* If we got to this point, the current key qualifies as MIN. */
9662
DBUG_ASSERT(result == 0);
9666
If there was a key with NULL in the MIN/MAX field, and there was no other
9667
key without NULL from the same group that satisfies some other condition,
9668
then use the key with the NULL.
9670
if (found_null && result)
9672
memcpy(record, tmp_record, head->s->rec_buff_length);
9680
Find the maximal key in a group that satisfies some range conditions for the
9681
min/max argument field.
9684
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9687
Given the sequence of ranges min_max_ranges, find the maximal key that is
9688
in the right-most possible range. If there is no such key, then the current
9689
group does not have a MAX key that satisfies the WHERE clause. If a key is
9690
found, its value is stored in this->record.
9694
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9696
HA_ERR_END_OF_FILE - "" -
9700
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9702
ha_rkey_function find_flag;
9703
key_part_map keypart_map;
9704
QUICK_RANGE *cur_range;
9707
DBUG_ASSERT(min_max_ranges.elements > 0);
9709
for (uint range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9710
{ /* Search from the right-most range to the left. */
9711
get_dynamic(&min_max_ranges, (uchar*)&cur_range, range_idx - 1);
9714
If the current value for the min/max argument is smaller than the left
9715
boundary of cur_range, there is no need to check this range.
9717
if (range_idx != min_max_ranges.elements &&
9718
!(cur_range->flag & NO_MIN_RANGE) &&
9719
(key_cmp(min_max_arg_part, (const uchar*) cur_range->min_key,
9720
min_max_arg_len) == -1))
9723
if (cur_range->flag & NO_MAX_RANGE)
9725
keypart_map= make_prev_keypart_map(real_key_parts);
9726
find_flag= HA_READ_PREFIX_LAST;
9730
/* Extend the search key with the upper boundary for this range. */
9731
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9732
cur_range->max_length);
9733
keypart_map= make_keypart_map(real_key_parts);
9734
find_flag= (cur_range->flag & EQ_RANGE) ?
9735
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9736
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9739
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9743
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9744
(cur_range->flag & EQ_RANGE))
9745
continue; /* Check the next range. */
9748
In no key was found with this upper bound, there certainly are no keys
9749
in the ranges to the left.
9753
/* A key was found. */
9754
if (cur_range->flag & EQ_RANGE)
9755
return 0; /* No need to perform the checks below for equal keys. */
9757
/* Check if record belongs to the current group. */
9758
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9759
continue; // Row not found
9761
/* If there is a lower limit, check if the found key is in the range. */
9762
if ( !(cur_range->flag & NO_MIN_RANGE) )
9764
/* Compose the MIN key for the range. */
9765
uchar *min_key= (uchar*) my_alloca(real_prefix_len + min_max_arg_len);
9766
memcpy(min_key, group_prefix, real_prefix_len);
9767
memcpy(min_key + real_prefix_len, cur_range->min_key,
9768
cur_range->min_length);
9769
/* Compare the found key with min_key. */
9770
int cmp_res= key_cmp(index_info->key_part, min_key,
9771
real_prefix_len + min_max_arg_len);
9772
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9776
/* If we got to this point, the current key qualifies as MAX. */
9779
return HA_ERR_KEY_NOT_FOUND;
9784
Update all MIN function results with the newly found value.
9787
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9790
The method iterates through all MIN functions and updates the result value
9791
of each function by calling Item_sum::reset(), which in turn picks the new
9792
result value from this->head->record[0], previously updated by
9793
next_min(). The updated value is stored in a member variable of each of the
9794
Item_sum objects, depending on the value type.
9797
The update must be done separately for MIN and MAX, immediately after
9798
next_min() was called and before next_max() is called, because both MIN and
9799
MAX take their result value from the same buffer this->head->record[0]
9800
(i.e. this->record).
9806
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9810
min_functions_it->rewind();
9811
while ((min_func= (*min_functions_it)++))
9817
Update all MAX function results with the newly found value.
9820
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9823
The method iterates through all MAX functions and updates the result value
9824
of each function by calling Item_sum::reset(), which in turn picks the new
9825
result value from this->head->record[0], previously updated by
9826
next_max(). The updated value is stored in a member variable of each of the
9827
Item_sum objects, depending on the value type.
9830
The update must be done separately for MIN and MAX, immediately after
9831
next_max() was called, because both MIN and MAX take their result value
9832
from the same buffer this->head->record[0] (i.e. this->record).
9838
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9842
max_functions_it->rewind();
9843
while ((max_func= (*max_functions_it)++))
9849
Append comma-separated list of keys this quick select uses to key_names;
9850
append comma-separated list of corresponding used lengths to used_lengths.
9853
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9854
key_names [out] Names of used indexes
9855
used_lengths [out] Corresponding lengths of the index names
9858
This method is used by select_describe to extract the names of the
9859
indexes used by a quick select.
9863
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9864
String *used_lengths)
9868
key_names->append(index_info->name);
9869
length= longlong2str(max_used_key_length, buf, 10) - buf;
9870
used_lengths->append(buf, length);
9876
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9879
SEL_ARG **key,**end;
9882
DBUG_ENTER("print_sel_tree");
9884
String tmp(buff,sizeof(buff),&my_charset_bin);
9886
for (idx= 0,key=tree->keys, end=key+param->keys ;
9890
if (tree_map->is_set(idx))
9892
uint keynr= param->real_keynr[idx];
9895
tmp.append(param->table->key_info[keynr].name);
9899
tmp.append(STRING_WITH_LEN("(empty)"));
9901
DBUG_PRINT("info", ("SEL_TREE: 0x%lx (%s) scans: %s", (long) tree, msg, tmp.ptr()));
9907
static void print_ror_scans_arr(TABLE *table, const char *msg,
9908
struct st_ror_scan_info **start,
9909
struct st_ror_scan_info **end)
9911
DBUG_ENTER("print_ror_scans_arr");
9914
String tmp(buff,sizeof(buff),&my_charset_bin);
9916
for (;start != end; start++)
9920
tmp.append(table->key_info[(*start)->keynr].name);
9923
tmp.append(STRING_WITH_LEN("(empty)"));
9924
DBUG_PRINT("info", ("ROR key scans (%s): %s", msg, tmp.ptr()));
9929
/*****************************************************************************
9930
** Print a quick range for debugging
9932
** This should be changed to use a String to store each row instead
9933
** of locking the DEBUG stream !
9934
*****************************************************************************/
9937
print_key(KEY_PART *key_part, const uchar *key, uint used_length)
9940
const uchar *key_end= key+used_length;
9941
String tmp(buff,sizeof(buff),&my_charset_bin);
9943
TABLE *table= key_part->field->table;
9944
my_bitmap_map *old_write_set, *old_read_set;
9945
old_write_set= dbug_tmp_use_all_columns(table, table->write_set);
9946
old_read_set= dbug_tmp_use_all_columns(table, table->read_set);
9948
for (; key < key_end; key+=store_length, key_part++)
9950
Field *field= key_part->field;
9951
store_length= key_part->store_length;
9953
if (field->real_maybe_null())
9957
fwrite("NULL",sizeof(char),4,DBUG_FILE);
9960
key++; // Skip null byte
9963
field->set_key_image(key, key_part->length);
9964
if (field->type() == MYSQL_TYPE_BIT)
9965
(void) field->val_int_as_str(&tmp, 1);
9967
field->val_str(&tmp);
9968
fwrite(tmp.ptr(),sizeof(char),tmp.length(),DBUG_FILE);
9969
if (key+store_length < key_end)
9970
fputc('/',DBUG_FILE);
9972
dbug_tmp_restore_column_map(table->write_set, old_write_set);
9973
dbug_tmp_restore_column_map(table->read_set, old_read_set);
9977
static void print_quick(QUICK_SELECT_I *quick, const key_map *needed_reg)
9979
char buf[MAX_KEY/8+1];
9981
my_bitmap_map *old_read_map, *old_write_map;
9982
DBUG_ENTER("print_quick");
9988
old_read_map= dbug_tmp_use_all_columns(table, table->read_set);
9989
old_write_map= dbug_tmp_use_all_columns(table, table->write_set);
9990
quick->dbug_dump(0, TRUE);
9991
dbug_tmp_restore_column_map(table->read_set, old_read_map);
9992
dbug_tmp_restore_column_map(table->write_set, old_write_map);
9994
fprintf(DBUG_FILE,"other_keys: 0x%s:\n", needed_reg->print(buf));
10001
void QUICK_RANGE_SELECT::dbug_dump(int indent, bool verbose)
10003
/* purecov: begin inspected */
10004
fprintf(DBUG_FILE, "%*squick range select, key %s, length: %d\n",
10005
indent, "", head->key_info[index].name, max_used_key_length);
10009
QUICK_RANGE *range;
10010
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
10011
QUICK_RANGE **end_range= pr + ranges.elements;
10012
for (; pr != end_range; ++pr)
10014
fprintf(DBUG_FILE, "%*s", indent + 2, "");
10016
if (!(range->flag & NO_MIN_RANGE))
10018
print_key(key_parts, range->min_key, range->min_length);
10019
if (range->flag & NEAR_MIN)
10020
fputs(" < ",DBUG_FILE);
10022
fputs(" <= ",DBUG_FILE);
10024
fputs("X",DBUG_FILE);
10026
if (!(range->flag & NO_MAX_RANGE))
10028
if (range->flag & NEAR_MAX)
10029
fputs(" < ",DBUG_FILE);
10031
fputs(" <= ",DBUG_FILE);
10032
print_key(key_parts, range->max_key, range->max_length);
10034
fputs("\n",DBUG_FILE);
10040
void QUICK_INDEX_MERGE_SELECT::dbug_dump(int indent, bool verbose)
10042
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
10043
QUICK_RANGE_SELECT *quick;
10044
fprintf(DBUG_FILE, "%*squick index_merge select\n", indent, "");
10045
fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");
10046
while ((quick= it++))
10047
quick->dbug_dump(indent+2, verbose);
10048
if (pk_quick_select)
10050
fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, "");
10051
pk_quick_select->dbug_dump(indent+2, verbose);
10053
fprintf(DBUG_FILE, "%*s}\n", indent, "");
10056
void QUICK_ROR_INTERSECT_SELECT::dbug_dump(int indent, bool verbose)
10058
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
10059
QUICK_RANGE_SELECT *quick;
10060
fprintf(DBUG_FILE, "%*squick ROR-intersect select, %scovering\n",
10061
indent, "", need_to_fetch_row? "":"non-");
10062
fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");
10063
while ((quick= it++))
10064
quick->dbug_dump(indent+2, verbose);
10067
fprintf(DBUG_FILE, "%*sclustered PK quick:\n", indent, "");
10068
cpk_quick->dbug_dump(indent+2, verbose);
10070
fprintf(DBUG_FILE, "%*s}\n", indent, "");
10073
void QUICK_ROR_UNION_SELECT::dbug_dump(int indent, bool verbose)
10075
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
10076
QUICK_SELECT_I *quick;
10077
fprintf(DBUG_FILE, "%*squick ROR-union select\n", indent, "");
10078
fprintf(DBUG_FILE, "%*smerged scans {\n", indent, "");
10079
while ((quick= it++))
10080
quick->dbug_dump(indent+2, verbose);
10081
fprintf(DBUG_FILE, "%*s}\n", indent, "");
10086
Print quick select information to DBUG_FILE.
10089
QUICK_GROUP_MIN_MAX_SELECT::dbug_dump()
10090
indent Indentation offset
10091
verbose If TRUE show more detailed output.
10094
Print the contents of this quick select to DBUG_FILE. The method also
10095
calls dbug_dump() for the used quick select if any.
10098
Caller is responsible for locking DBUG_FILE before this call and unlocking
10105
void QUICK_GROUP_MIN_MAX_SELECT::dbug_dump(int indent, bool verbose)
10108
"%*squick_group_min_max_select: index %s (%d), length: %d\n",
10109
indent, "", index_info->name, index, max_used_key_length);
10110
if (key_infix_len > 0)
10112
fprintf(DBUG_FILE, "%*susing key_infix with length %d:\n",
10113
indent, "", key_infix_len);
10115
if (quick_prefix_select)
10117
fprintf(DBUG_FILE, "%*susing quick_range_select:\n", indent, "");
10118
quick_prefix_select->dbug_dump(indent + 2, verbose);
10120
if (min_max_ranges.elements > 0)
10122
fprintf(DBUG_FILE, "%*susing %d quick_ranges for MIN/MAX:\n",
10123
indent, "", min_max_ranges.elements);
10128
#endif /* NOT_USED */
10130
/*****************************************************************************
10131
** Instantiate templates
10132
*****************************************************************************/
10134
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
10135
template class List<QUICK_RANGE>;
10136
template class List_iterator<QUICK_RANGE>;
added
removed
sql/opt_range.cc
