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
#include <drizzled/server_includes.h>
107
#include <drizzled/sql_select.h>
108
#include <drizzled/error.h>
109
#include <drizzled/cost_vect.h>
113
#if defined(CMATH_NAMESPACE)
114
using namespace CMATH_NAMESPACE;
149
118
Convert double value to #rows. Currently this does floor(), and we
150
119
might consider using round() instead.
152
static inline ha_rows double2rows(double x)
154
return static_cast<ha_rows>(x);
121
#define double2rows(x) ((ha_rows)(x))
123
static int sel_cmp(Field *f,unsigned char *a,unsigned char *b,uint8_t a_flag,uint8_t b_flag);
157
125
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,
127
class RANGE_OPT_PARAM;
129
A construction block of the SEL_ARG-graph.
131
The following description only covers graphs of SEL_ARG objects with
132
sel_arg->type==KEY_RANGE:
134
One SEL_ARG object represents an "elementary interval" in form
136
min_value <=? table.keypartX <=? max_value
138
The interval is a non-empty interval of any kind: with[out] minimum/maximum
139
bound, [half]open/closed, single-point interval, etc.
141
1. SEL_ARG GRAPH STRUCTURE
143
SEL_ARG objects are linked together in a graph. The meaning of the graph
144
is better demostrated by an example:
149
| part=1 $ part=2 $ part=3
151
| +-------+ $ +-------+ $ +--------+
152
| | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
153
| +-------+ $ +-------+ $ +--------+
159
\->| kp1=2 |--$--------------$-+
160
+-------+ $ $ | +--------+
162
+-------+ $ $ | +--------+
163
| kp1=3 |--$--------------$-+ |
164
+-------+ $ $ +--------+
168
The entire graph is partitioned into "interval lists".
170
An interval list is a sequence of ordered disjoint intervals over the same
171
key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
172
all intervals in the list form an RB-tree, linked via left/right/parent
173
pointers. The RB-tree root SEL_ARG object will be further called "root of the
176
In the example pic, there are 4 interval lists:
177
"kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
178
The vertical lines represent SEL_ARG::next/prev pointers.
180
In an interval list, each member X may have SEL_ARG::next_key_part pointer
181
pointing to the root of another interval list Y. The pointed interval list
182
must cover a key part with greater number (i.e. Y->part > X->part).
184
In the example pic, the next_key_part pointers are represented by
187
2. SEL_ARG GRAPH SEMANTICS
189
It represents a condition in a special form (we don't have a name for it ATM)
190
The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
192
For example, the picture represents the condition in form:
193
(kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
194
(kp1=2 AND (kp3=11 OR kp3=14)) OR
195
(kp1=3 AND (kp3=11 OR kp3=14))
200
Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
201
Then walk the SEL_ARG graph and get a list of dijsoint ordered key
202
intervals (i.e. intervals in form
204
(constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
206
Those intervals can be used to access the index. The uses are in:
207
- check_quick_select() - Walk the SEL_ARG graph and find an estimate of
208
how many table records are contained within all
210
- get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
211
and create QUICK_RANGE_SELECT object that will
212
read records within these intervals.
214
4. SPACE COMPLEXITY NOTES
216
SEL_ARG graph is a representation of an ordered disjoint sequence of
217
intervals over the ordered set of index tuple values.
219
For multi-part keys, one can construct a WHERE expression such that its
220
list of intervals will be of combinatorial size. Here is an example:
222
(keypart1 IN (1,2, ..., n1)) AND
223
(keypart2 IN (1,2, ..., n2)) AND
224
(keypart3 IN (1,2, ..., n3))
226
For this WHERE clause the list of intervals will have n1*n2*n3 intervals
229
(keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
231
SEL_ARG graph structure aims to reduce the amount of required space by
232
"sharing" the elementary intervals when possible (the pic at the
233
beginning of this comment has examples of such sharing). The sharing may
234
prevent combinatorial blowup:
236
There are WHERE clauses that have combinatorial-size interval lists but
237
will be represented by a compact SEL_ARG graph.
239
(keypartN IN (1,2, ..., n1)) AND
241
(keypart2 IN (1,2, ..., n2)) AND
242
(keypart1 IN (1,2, ..., n3))
244
but not in all cases:
246
- There are WHERE clauses that do have a compact SEL_ARG-graph
247
representation but get_mm_tree() and its callees will construct a
248
graph of combinatorial size.
250
(keypart1 IN (1,2, ..., n1)) AND
251
(keypart2 IN (1,2, ..., n2)) AND
253
(keypartN IN (1,2, ..., n3))
255
- There are WHERE clauses for which the minimal possible SEL_ARG graph
256
representation will have combinatorial size.
258
By induction: Let's take any interval on some keypart in the middle:
262
Then let's AND it with this interval 'structure' from preceding and
265
(kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
267
We will obtain this SEL_ARG graph:
271
+---------+ $ +---------+ $ +---------+
272
| kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
273
+---------+ $ +---------+ $ +---------+
275
+---------+ $ +---------+ $
276
| kp14=c2 |--$-->| kp15=c0 | $
277
+---------+ $ +---------+ $
280
Note that we had to duplicate "kp15=c0" and there was no way to avoid
282
The induction step: AND the obtained expression with another "wrapping"
284
When the process ends because of the limit on max. number of keyparts
287
WHERE clause length is O(3*#max_keyparts)
288
SEL_ARG graph size is O(2^(#max_keyparts/2))
290
(it is also possible to construct a case where instead of 2 in 2^n we
291
have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
294
We avoid consuming too much memory by setting a limit on the number of
295
SEL_ARG object we can construct during one range analysis invocation.
298
class SEL_ARG :public Sql_alloc
301
uint8_t min_flag,max_flag,maybe_flag;
302
uint8_t part; // Which key part
305
Number of children of this element in the RB-tree, plus 1 for this
310
Valid only for elements which are RB-tree roots: Number of times this
311
RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
312
SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
317
unsigned char *min_value,*max_value; // Pointer to range
320
eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
322
SEL_ARG *left,*right; /* R-B tree children */
323
SEL_ARG *next,*prev; /* Links for bi-directional interval list */
324
SEL_ARG *parent; /* R-B tree parent */
325
SEL_ARG *next_key_part;
326
enum leaf_color { BLACK,RED } color;
327
enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
329
enum { MAX_SEL_ARGS = 16000 };
333
SEL_ARG(Field *,const unsigned char *, const unsigned char *);
334
SEL_ARG(Field *field, uint8_t part, unsigned char *min_value, unsigned char *max_value,
335
uint8_t min_flag, uint8_t max_flag, uint8_t maybe_flag);
336
SEL_ARG(enum Type type_arg)
337
:min_flag(0),elements(1),use_count(1),left(0),right(0),next_key_part(0),
338
color(BLACK), type(type_arg)
340
inline bool is_same(SEL_ARG *arg)
342
if (type != arg->type || part != arg->part)
344
if (type != KEY_RANGE)
346
return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
348
inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
349
inline void maybe_smaller() { maybe_flag=1; }
350
/* Return true iff it's a single-point null interval */
351
inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
352
inline int cmp_min_to_min(SEL_ARG* arg)
354
return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
356
inline int cmp_min_to_max(SEL_ARG* arg)
358
return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
360
inline int cmp_max_to_max(SEL_ARG* arg)
362
return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
364
inline int cmp_max_to_min(SEL_ARG* arg)
366
return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
368
SEL_ARG *clone_and(SEL_ARG* arg)
369
{ // Get overlapping range
370
unsigned char *new_min,*new_max;
371
uint8_t flag_min,flag_max;
372
if (cmp_min_to_min(arg) >= 0)
374
new_min=min_value; flag_min=min_flag;
378
new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
380
if (cmp_max_to_max(arg) <= 0)
382
new_max=max_value; flag_max=max_flag;
386
new_max=arg->max_value; flag_max=arg->max_flag;
388
return new SEL_ARG(field, part, new_min, new_max, flag_min, flag_max,
389
test(maybe_flag && arg->maybe_flag));
391
SEL_ARG *clone_first(SEL_ARG *arg)
392
{ // min <= X < arg->min
393
return new SEL_ARG(field,part, min_value, arg->min_value,
394
min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
395
maybe_flag | arg->maybe_flag);
397
SEL_ARG *clone_last(SEL_ARG *arg)
398
{ // min <= X <= key_max
399
return new SEL_ARG(field, part, min_value, arg->max_value,
400
min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
402
SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
404
bool copy_min(SEL_ARG* arg)
405
{ // Get overlapping range
406
if (cmp_min_to_min(arg) > 0)
408
min_value=arg->min_value; min_flag=arg->min_flag;
409
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
410
(NO_MAX_RANGE | NO_MIN_RANGE))
411
return 1; // Full range
413
maybe_flag|=arg->maybe_flag;
416
bool copy_max(SEL_ARG* arg)
417
{ // Get overlapping range
418
if (cmp_max_to_max(arg) <= 0)
420
max_value=arg->max_value; max_flag=arg->max_flag;
421
if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
422
(NO_MAX_RANGE | NO_MIN_RANGE))
423
return 1; // Full range
425
maybe_flag|=arg->maybe_flag;
429
void copy_min_to_min(SEL_ARG *arg)
431
min_value=arg->min_value; min_flag=arg->min_flag;
433
void copy_min_to_max(SEL_ARG *arg)
435
max_value=arg->min_value;
436
max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
438
void copy_max_to_min(SEL_ARG *arg)
440
min_value=arg->max_value;
441
min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
443
/* returns a number of keypart values (0 or 1) appended to the key buffer */
444
int store_min(uint32_t length, unsigned char **min_key,uint32_t min_key_flag)
446
/* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
447
if ((!(min_flag & NO_MIN_RANGE) &&
448
!(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
450
if (maybe_null && *min_value)
453
memset(*min_key+1, 0, length-1);
456
memcpy(*min_key,min_value,length);
462
/* returns a number of keypart values (0 or 1) appended to the key buffer */
463
int store_max(uint32_t length, unsigned char **max_key, uint32_t max_key_flag)
465
if (!(max_flag & NO_MAX_RANGE) &&
466
!(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
468
if (maybe_null && *max_value)
471
memset(*max_key+1, 0, length-1);
474
memcpy(*max_key,max_value,length);
481
/* returns a number of keypart values appended to the key buffer */
482
int store_min_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
484
SEL_ARG *key_tree= first();
485
uint32_t res= key_tree->store_min(key[key_tree->part].store_length,
486
range_key, *range_key_flag);
487
*range_key_flag|= key_tree->min_flag;
489
if (key_tree->next_key_part &&
490
key_tree->next_key_part->part == key_tree->part+1 &&
491
!(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)) &&
492
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
493
res+= key_tree->next_key_part->store_min_key(key, range_key,
498
/* returns a number of keypart values appended to the key buffer */
499
int store_max_key(KEY_PART *key, unsigned char **range_key, uint32_t *range_key_flag)
501
SEL_ARG *key_tree= last();
502
uint32_t res=key_tree->store_max(key[key_tree->part].store_length,
503
range_key, *range_key_flag);
504
(*range_key_flag)|= key_tree->max_flag;
505
if (key_tree->next_key_part &&
506
key_tree->next_key_part->part == key_tree->part+1 &&
507
!(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)) &&
508
key_tree->next_key_part->type == SEL_ARG::KEY_RANGE)
509
res+= key_tree->next_key_part->store_max_key(key, range_key,
514
SEL_ARG *insert(SEL_ARG *key);
515
SEL_ARG *tree_delete(SEL_ARG *key);
516
SEL_ARG *find_range(SEL_ARG *key);
517
SEL_ARG *rb_insert(SEL_ARG *leaf);
518
friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
520
friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
521
void test_use_count(SEL_ARG *root);
526
inline bool simple_key()
528
return !next_key_part && elements == 1;
530
void increment_use_count(long count)
534
next_key_part->use_count+=count;
535
count*= (next_key_part->use_count-count);
536
for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
537
if (pos->next_key_part)
538
pos->increment_use_count(count);
543
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
544
if (pos->next_key_part)
546
pos->next_key_part->use_count--;
547
pos->next_key_part->free_tree();
551
inline SEL_ARG **parent_ptr()
553
return parent->left == this ? &parent->left : &parent->right;
558
Check if this SEL_ARG object represents a single-point interval
564
Check if this SEL_ARG object (not tree) represents a single-point
565
interval, i.e. if it represents a "keypart = const" or
569
true This SEL_ARG object represents a singlepoint interval
573
bool is_singlepoint()
576
Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
577
flags, and the same for right edge.
579
if (min_flag || max_flag)
581
unsigned char *min_val= min_value;
582
unsigned char *max_val= max_value;
586
/* First byte is a NULL value indicator */
587
if (*min_val != *max_val)
591
return true; /* This "x IS NULL" */
595
return !field->key_cmp(min_val, max_val);
597
SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
603
class SEL_TREE :public Sql_alloc
607
Starting an effort to document this field:
608
(for some i, keys[i]->type == SEL_ARG::IMPOSSIBLE) =>
609
(type == SEL_TREE::IMPOSSIBLE)
611
enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
612
SEL_TREE(enum Type type_arg) :type(type_arg) {}
613
SEL_TREE() :type(KEY)
615
keys_map.clear_all();
616
memset(keys, 0, sizeof(keys));
619
Note: there may exist SEL_TREE objects with sel_tree->type=KEY and
620
keys[i]=0 for all i. (SergeyP: it is not clear whether there is any
621
merit in range analyzer functions (e.g. get_mm_parts) returning a
622
pointer to such SEL_TREE instead of NULL)
624
SEL_ARG *keys[MAX_KEY];
625
key_map keys_map; /* bitmask of non-NULL elements in keys */
628
Possible ways to read rows using index_merge. The list is non-empty only
629
if type==KEY. Currently can be non empty only if keys_map.is_clear_all().
631
List<SEL_IMERGE> merges;
633
/* The members below are filled/used only after get_mm_tree is done */
634
key_map ror_scans_map; /* bitmask of ROR scan-able elements in keys */
635
uint32_t n_ror_scans; /* number of set bits in ror_scans_map */
637
struct st_ror_scan_info **ror_scans; /* list of ROR key scans */
638
struct st_ror_scan_info **ror_scans_end; /* last ROR scan */
639
/* Note that #records for each key scan is stored in table->quick_rows */
642
class RANGE_OPT_PARAM
645
Session *session; /* Current thread handle */
646
Table *table; /* Table being analyzed */
647
COND *cond; /* Used inside get_mm_tree(). */
648
table_map prev_tables;
649
table_map read_tables;
650
table_map current_table; /* Bit of the table being analyzed */
652
/* Array of parts of all keys for which range analysis is performed */
654
KEY_PART *key_parts_end;
655
MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
656
MEM_ROOT *old_root; /* Memory that will last until the query end */
658
Number of indexes used in range analysis (In SEL_TREE::keys only first
659
#keys elements are not empty)
664
If true, the index descriptions describe real indexes (and it is ok to
665
call field->optimize_range(real_keynr[...], ...).
666
Otherwise index description describes fake indexes.
668
bool using_real_indexes;
670
bool remove_jump_scans;
673
used_key_no -> table_key_no translation table. Only makes sense if
674
using_real_indexes==true
676
uint32_t real_keynr[MAX_KEY];
677
/* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
678
uint32_t alloced_sel_args;
679
bool force_default_mrr;
682
class PARAM : public RANGE_OPT_PARAM
685
KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
687
uint32_t max_key_part;
688
/* Number of ranges in the last checked tree->key */
689
uint32_t range_count;
690
unsigned char min_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH],
691
max_key[MAX_KEY_LENGTH+MAX_FIELD_WIDTH];
692
bool quick; // Don't calulate possible keys
694
uint32_t fields_bitmap_size;
695
MY_BITMAP needed_fields; /* bitmask of fields needed by the query */
696
MY_BITMAP tmp_covered_fields;
698
key_map *needed_reg; /* ptr to SQL_SELECT::needed_reg */
700
uint32_t *imerge_cost_buff; /* buffer for index_merge cost estimates */
701
uint32_t imerge_cost_buff_size; /* size of the buffer */
703
/* true if last checked tree->key can be used for ROR-scan */
705
/* Number of ranges in the last checked tree->key */
709
class TABLE_READ_PLAN;
711
class TRP_ROR_INTERSECT;
713
class TRP_ROR_INDEX_MERGE;
714
class TRP_GROUP_MIN_MAX;
716
struct st_ror_scan_info;
718
static SEL_TREE * get_mm_parts(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
719
Item_func::Functype type,Item *value,
720
Item_result cmp_type);
721
static SEL_ARG *get_mm_leaf(RANGE_OPT_PARAM *param,COND *cond_func,Field *field,
723
Item_func::Functype type,Item *value);
724
static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param,COND *cond);
726
static bool is_key_scan_ror(PARAM *param, uint32_t keynr, uint8_t nparts);
727
static ha_rows check_quick_select(PARAM *param, uint32_t idx, bool index_only,
728
SEL_ARG *tree, bool update_tbl_stats,
729
uint32_t *mrr_flags, uint32_t *bufsize,
731
//bool update_tbl_stats);
732
/*static ha_rows check_quick_keys(PARAM *param,uint32_t index,SEL_ARG *key_tree,
733
unsigned char *min_key, uint32_t min_key_flag, int,
734
unsigned char *max_key, uint32_t max_key_flag, int);
737
QUICK_RANGE_SELECT *get_quick_select(PARAM *param,uint32_t index,
738
SEL_ARG *key_tree, uint32_t mrr_flags,
739
uint32_t mrr_buf_size, MEM_ROOT *alloc);
740
static TRP_RANGE *get_key_scans_params(PARAM *param, SEL_TREE *tree,
741
bool index_read_must_be_used,
742
bool update_tbl_stats,
745
TRP_ROR_INTERSECT *get_best_ror_intersect(const PARAM *param, SEL_TREE *tree,
747
bool *are_all_covering);
749
TRP_ROR_INTERSECT *get_best_covering_ror_intersect(PARAM *param,
753
TABLE_READ_PLAN *get_best_disjunct_quick(PARAM *param, SEL_IMERGE *imerge,
756
TRP_GROUP_MIN_MAX *get_best_group_min_max(PARAM *param, SEL_TREE *tree);
758
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
760
static void print_ror_scans_arr(Table *table, const char *msg,
761
struct st_ror_scan_info **start,
762
struct st_ror_scan_info **end);
764
static SEL_TREE *tree_and(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
765
static SEL_TREE *tree_or(RANGE_OPT_PARAM *param,SEL_TREE *tree1,SEL_TREE *tree2);
766
static SEL_ARG *sel_add(SEL_ARG *key1,SEL_ARG *key2);
767
static SEL_ARG *key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2);
768
static SEL_ARG *key_and(RANGE_OPT_PARAM *param, SEL_ARG *key1, SEL_ARG *key2,
769
uint32_t clone_flag);
770
static bool get_range(SEL_ARG **e1,SEL_ARG **e2,SEL_ARG *root1);
771
bool get_quick_keys(PARAM *param,QUICK_RANGE_SELECT *quick,KEY_PART *key,
772
SEL_ARG *key_tree, unsigned char *min_key,uint32_t min_key_flag,
773
unsigned char *max_key,uint32_t max_key_flag);
774
static bool eq_tree(SEL_ARG* a,SEL_ARG *b);
776
static SEL_ARG null_element(SEL_ARG::IMPOSSIBLE);
777
static bool null_part_in_key(KEY_PART *key_part, const unsigned char *key,
307
778
uint32_t length);
309
bool sel_trees_can_be_ored(optimizer::SEL_TREE *tree1,
310
optimizer::SEL_TREE *tree2,
311
optimizer::RangeParameter *param);
779
bool sel_trees_can_be_ored(SEL_TREE *tree1, SEL_TREE *tree2, RANGE_OPT_PARAM* param);
783
SEL_IMERGE is a list of possible ways to do index merge, i.e. it is
784
a condition in the following form:
785
(t_1||t_2||...||t_N) && (next)
787
where all t_i are SEL_TREEs, next is another SEL_IMERGE and no pair
788
(t_i,t_j) contains SEL_ARGS for the same index.
790
SEL_TREE contained in SEL_IMERGE always has merges=NULL.
792
This class relies on memory manager to do the cleanup.
795
class SEL_IMERGE : public Sql_alloc
797
enum { PREALLOCED_TREES= 10};
799
SEL_TREE *trees_prealloced[PREALLOCED_TREES];
800
SEL_TREE **trees; /* trees used to do index_merge */
801
SEL_TREE **trees_next; /* last of these trees */
802
SEL_TREE **trees_end; /* end of allocated space */
804
SEL_ARG ***best_keys; /* best keys to read in SEL_TREEs */
807
trees(&trees_prealloced[0]),
809
trees_end(trees + PREALLOCED_TREES)
811
int or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree);
812
int or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree);
813
int or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge);
818
Add SEL_TREE to this index_merge without any checks,
821
This function implements the following:
822
(x_1||...||x_N) || t = (x_1||...||x_N||t), where x_i, t are SEL_TREEs
829
int SEL_IMERGE::or_sel_tree(RANGE_OPT_PARAM *param, SEL_TREE *tree)
831
if (trees_next == trees_end)
833
const int realloc_ratio= 2; /* Double size for next round */
834
uint32_t old_elements= (trees_end - trees);
835
uint32_t old_size= sizeof(SEL_TREE**) * old_elements;
836
uint32_t new_size= old_size * realloc_ratio;
837
SEL_TREE **new_trees;
838
if (!(new_trees= (SEL_TREE**)alloc_root(param->mem_root, new_size)))
840
memcpy(new_trees, trees, old_size);
842
trees_next= trees + old_elements;
843
trees_end= trees + old_elements * realloc_ratio;
845
*(trees_next++)= tree;
851
Perform OR operation on this SEL_IMERGE and supplied SEL_TREE new_tree,
852
combining new_tree with one of the trees in this SEL_IMERGE if they both
853
have SEL_ARGs for the same key.
856
or_sel_tree_with_checks()
857
param PARAM from SQL_SELECT::test_quick_select
858
new_tree SEL_TREE with type KEY or KEY_SMALLER.
861
This does the following:
862
(t_1||...||t_k)||new_tree =
864
= (t_1||...||t_k||new_tree)
866
= (t_1||....||(t_j|| new_tree)||...||t_k),
868
where t_i, y are SEL_TREEs.
869
new_tree is combined with the first t_j it has a SEL_ARG on common
870
key with. As a consequence of this, choice of keys to do index_merge
871
read may depend on the order of conditions in WHERE part of the query.
875
1 One of the trees was combined with new_tree to SEL_TREE::ALWAYS,
876
and (*this) should be discarded.
877
-1 An error occurred.
880
int SEL_IMERGE::or_sel_tree_with_checks(RANGE_OPT_PARAM *param, SEL_TREE *new_tree)
882
for (SEL_TREE** tree = trees;
886
if (sel_trees_can_be_ored(*tree, new_tree, param))
888
*tree = tree_or(param, *tree, new_tree);
891
if (((*tree)->type == SEL_TREE::MAYBE) ||
892
((*tree)->type == SEL_TREE::ALWAYS))
894
/* SEL_TREE::IMPOSSIBLE is impossible here */
899
/* New tree cannot be combined with any of existing trees. */
900
return or_sel_tree(param, new_tree);
905
Perform OR operation on this index_merge and supplied index_merge list.
909
1 - One of conditions in result is always true and this SEL_IMERGE
911
-1 - An error occurred
914
int SEL_IMERGE::or_sel_imerge_with_checks(RANGE_OPT_PARAM *param, SEL_IMERGE* imerge)
916
for (SEL_TREE** tree= imerge->trees;
917
tree != imerge->trees_next;
920
if (or_sel_tree_with_checks(param, *tree))
319
928
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)
931
inline void imerge_list_and_list(List<SEL_IMERGE> *im1, List<SEL_IMERGE> *im2)
324
933
im1->concat(im2);
938
Perform OR operation on 2 index_merge lists, storing result in first list.
941
The following conversion is implemented:
942
(a_1 &&...&& a_N)||(b_1 &&...&& b_K) = AND_i,j(a_i || b_j) =>
945
i.e. all conjuncts except the first one are currently dropped.
946
This is done to avoid producing N*K ways to do index_merge.
948
If (a_1||b_1) produce a condition that is always true, NULL is returned
949
and index_merge is discarded (while it is actually possible to try
952
As a consequence of this, choice of keys to do index_merge read may depend
953
on the order of conditions in WHERE part of the query.
956
0 OK, result is stored in *im1
957
other Error, both passed lists are unusable
960
int imerge_list_or_list(RANGE_OPT_PARAM *param,
961
List<SEL_IMERGE> *im1,
962
List<SEL_IMERGE> *im2)
964
SEL_IMERGE *imerge= im1->head();
966
im1->push_back(imerge);
968
return imerge->or_sel_imerge_with_checks(param, im2->head());
973
Perform OR operation on index_merge list and key tree.
976
0 OK, result is stored in *im1.
980
int imerge_list_or_tree(RANGE_OPT_PARAM *param,
981
List<SEL_IMERGE> *im1,
985
List_iterator<SEL_IMERGE> it(*im1);
986
while ((imerge= it++))
988
if (imerge->or_sel_tree_with_checks(param, tree))
991
return im1->is_empty();
328
995
/***************************************************************************
329
** Basic functions for SqlSelect and QuickRangeSelect
996
** Basic functions for SQL_SELECT and QUICK_RANGE_SELECT
330
997
***************************************************************************/
332
999
/* make a select from mysql info
363
1026
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;
1028
select->file= *head->sort.io_cache;
1029
select->records=(ha_rows) (select->file.end_of_file/
1030
head->file->ref_length);
1031
free(head->sort.io_cache);
369
1032
head->sort.io_cache=0;
375
optimizer::SqlSelect::SqlSelect()
379
file(static_cast<internal::IO_CACHE *>(memory::sql_calloc(sizeof(internal::IO_CACHE)))),
1038
SQL_SELECT::SQL_SELECT() :quick(0),cond(0),free_cond(0)
1040
quick_keys.clear_all(); needed_reg.clear_all();
388
void optimizer::SqlSelect::cleanup()
1045
void SQL_SELECT::cleanup()
402
file->close_cached_file();
1055
close_cached_file(&file);
406
optimizer::SqlSelect::~SqlSelect()
1059
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),
1064
QUICK_SELECT_I::QUICK_SELECT_I()
1065
:max_used_key_length(0),
1069
QUICK_RANGE_SELECT::QUICK_RANGE_SELECT(Session *session, Table *table, uint32_t key_nr,
1070
bool no_alloc, MEM_ROOT *parent_alloc,
1072
:free_file(0),cur_range(NULL),last_range(0),dont_free(0)
1074
my_bitmap_map *bitmap;
1076
in_ror_merged_scan= 0;
1080
key_part_info= head->key_info[index].key_part;
1081
my_init_dynamic_array(&ranges, sizeof(QUICK_RANGE*), 16, 16);
1083
/* 'session' is not accessible in QUICK_RANGE_SELECT::reset(). */
1084
mrr_buf_size= session->variables.read_rnd_buff_size;
1087
if (!no_alloc && !parent_alloc)
1089
// Allocates everything through the internal memroot
1090
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1091
session->mem_root= &alloc;
1094
memset(&alloc, 0, sizeof(alloc));
1096
record= head->record[0];
1097
save_read_set= head->read_set;
1098
save_write_set= head->write_set;
1100
/* Allocate a bitmap for used columns (Q: why not on MEM_ROOT?) */
1101
if (!(bitmap= (my_bitmap_map*) my_malloc(head->s->column_bitmap_size,
1104
column_bitmap.bitmap= 0;
1108
bitmap_init(&column_bitmap, bitmap, head->s->fields, false);
1113
int QUICK_RANGE_SELECT::init()
1115
if (file->inited != handler::NONE)
1116
file->ha_index_or_rnd_end();
1117
return(file->ha_index_init(index, 1));
1121
void QUICK_RANGE_SELECT::range_end()
1123
if (file->inited != handler::NONE)
1124
file->ha_index_or_rnd_end();
1128
QUICK_RANGE_SELECT::~QUICK_RANGE_SELECT()
1132
/* file is NULL for CPK scan on covering ROR-intersection */
1139
file->extra(HA_EXTRA_NO_KEYREAD);
1143
file->ha_external_lock(current_session, F_UNLCK);
1148
delete_dynamic(&ranges); /* ranges are allocated in alloc */
1149
free_root(&alloc,MYF(0));
1150
free((char*) column_bitmap.bitmap);
1152
head->column_bitmaps_set(save_read_set, save_write_set);
1159
QUICK_INDEX_MERGE_SELECT::QUICK_INDEX_MERGE_SELECT(Session *session_param,
1161
:pk_quick_select(NULL), session(session_param)
1165
memset(&read_record, 0, sizeof(read_record));
1166
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1170
int QUICK_INDEX_MERGE_SELECT::init()
1175
int QUICK_INDEX_MERGE_SELECT::reset()
1177
return(read_keys_and_merge());
1181
QUICK_INDEX_MERGE_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick_sel_range)
1184
Save quick_select that does scan on clustered primary key as it will be
1185
processed separately.
1187
if (head->file->primary_key_is_clustered() &&
1188
quick_sel_range->index == head->s->primary_key)
1189
pk_quick_select= quick_sel_range;
1191
return quick_selects.push_back(quick_sel_range);
1195
QUICK_INDEX_MERGE_SELECT::~QUICK_INDEX_MERGE_SELECT()
1197
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1198
QUICK_RANGE_SELECT* quick;
1200
while ((quick= quick_it++))
1202
quick_selects.delete_elements();
1203
delete pk_quick_select;
1204
free_root(&alloc,MYF(0));
1209
QUICK_ROR_INTERSECT_SELECT::QUICK_ROR_INTERSECT_SELECT(Session *session_param,
1211
bool retrieve_full_rows,
1212
MEM_ROOT *parent_alloc)
1213
: cpk_quick(NULL), session(session_param), need_to_fetch_row(retrieve_full_rows),
1218
record= head->record[0];
1220
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1222
memset(&alloc, 0, sizeof(MEM_ROOT));
1223
last_rowid= (unsigned char*) alloc_root(parent_alloc? parent_alloc : &alloc,
1224
head->file->ref_length);
1229
Do post-constructor initialization.
1231
QUICK_ROR_INTERSECT_SELECT::init()
1238
int QUICK_ROR_INTERSECT_SELECT::init()
1240
/* Check if last_rowid was successfully allocated in ctor */
1241
return(!last_rowid);
1246
Initialize this quick select to be a ROR-merged scan.
1249
QUICK_RANGE_SELECT::init_ror_merged_scan()
1250
reuse_handler If true, use head->file, otherwise create a separate
1254
This function creates and prepares for subsequent use a separate handler
1255
object if it can't reuse head->file. The reason for this is that during
1256
ROR-merge several key scans are performed simultaneously, and a single
1257
handler is only capable of preserving context of a single key scan.
1259
In ROR-merge the quick select doing merge does full records retrieval,
1260
merged quick selects read only keys.
1263
0 ROR child scan initialized, ok to use.
1267
int QUICK_RANGE_SELECT::init_ror_merged_scan(bool reuse_handler)
1269
handler *save_file= file, *org_file;
1272
in_ror_merged_scan= 1;
1275
if (init() || reset())
1279
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1283
/* Create a separate handler object for this quick select */
1286
/* already have own 'handler' object. */
1290
session= head->in_use;
1291
if (!(file= head->file->clone(session->mem_root)))
1294
Manually set the error flag. Note: there seems to be quite a few
1295
places where a failure could cause the server to "hang" the client by
1296
sending no response to a query. ATM those are not real errors because
1297
the storage engine calls in question happen to never fail with the
1298
existing storage engines.
1300
my_error(ER_OUT_OF_RESOURCES, MYF(0)); /* purecov: inspected */
1301
/* Caller will free the memory */
1302
goto failure; /* purecov: inspected */
1305
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1307
if (file->ha_external_lock(session, F_RDLCK))
1310
if (init() || reset())
1312
file->ha_external_lock(session, F_UNLCK);
1317
last_rowid= file->ref;
1321
We are only going to read key fields and call position() on 'file'
1322
The following sets head->tmp_set to only use this key and then updates
1323
head->read_set and head->write_set to use this bitmap.
1324
The now bitmap is stored in 'column_bitmap' which is used in ::get_next()
1326
org_file= head->file;
1328
/* We don't have to set 'head->keyread' here as the 'file' is unique */
1329
if (!head->no_keyread)
1332
head->mark_columns_used_by_index(index);
1334
head->prepare_for_position();
1335
head->file= org_file;
1336
bitmap_copy(&column_bitmap, head->read_set);
1337
head->column_bitmaps_set(&column_bitmap, &column_bitmap);
1342
head->column_bitmaps_set(save_read_set, save_write_set);
1350
Initialize this quick select to be a part of a ROR-merged scan.
1352
QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan()
1353
reuse_handler If true, use head->file, otherwise create separate
1359
int QUICK_ROR_INTERSECT_SELECT::init_ror_merged_scan(bool reuse_handler)
1361
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
1362
QUICK_RANGE_SELECT* quick;
1364
/* Initialize all merged "children" quick selects */
1365
assert(!need_to_fetch_row || reuse_handler);
1366
if (!need_to_fetch_row && reuse_handler)
1370
There is no use of this->file. Use it for the first of merged range
1373
if (quick->init_ror_merged_scan(true))
1375
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1377
while ((quick= quick_it++))
1379
if (quick->init_ror_merged_scan(false))
1381
quick->file->extra(HA_EXTRA_KEYREAD_PRESERVE_FIELDS);
1382
/* All merged scans share the same record buffer in intersection. */
1383
quick->record= head->record[0];
1386
if (need_to_fetch_row && head->file->ha_rnd_init(1))
1395
Initialize quick select for row retrieval.
1403
int QUICK_ROR_INTERSECT_SELECT::reset()
1405
if (!scans_inited && init_ror_merged_scan(true))
1408
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1409
QUICK_RANGE_SELECT *quick;
1410
while ((quick= it++))
1417
Add a merged quick select to this ROR-intersection quick select.
1420
QUICK_ROR_INTERSECT_SELECT::push_quick_back()
1421
quick Quick select to be added. The quick select must return
1422
rows in rowid order.
1424
This call can only be made before init() is called.
1432
QUICK_ROR_INTERSECT_SELECT::push_quick_back(QUICK_RANGE_SELECT *quick)
1434
return quick_selects.push_back(quick);
1437
QUICK_ROR_INTERSECT_SELECT::~QUICK_ROR_INTERSECT_SELECT()
1439
quick_selects.delete_elements();
1441
free_root(&alloc,MYF(0));
1442
if (need_to_fetch_row && head->file->inited != handler::NONE)
1443
head->file->ha_rnd_end();
1448
QUICK_ROR_UNION_SELECT::QUICK_ROR_UNION_SELECT(Session *session_param,
1450
: session(session_param), scans_inited(false)
1454
rowid_length= table->file->ref_length;
1455
record= head->record[0];
1456
init_sql_alloc(&alloc, session->variables.range_alloc_block_size, 0);
1457
session_param->mem_root= &alloc;
1462
Do post-constructor initialization.
1464
QUICK_ROR_UNION_SELECT::init()
1471
int QUICK_ROR_UNION_SELECT::init()
1473
if (init_queue(&queue, quick_selects.elements, 0,
1474
false , QUICK_ROR_UNION_SELECT::queue_cmp,
1477
memset(&queue, 0, sizeof(QUEUE));
1481
if (!(cur_rowid= (unsigned char*) alloc_root(&alloc, 2*head->file->ref_length)))
1483
prev_rowid= cur_rowid + head->file->ref_length;
1489
Comparison function to be used QUICK_ROR_UNION_SELECT::queue priority
1493
QUICK_ROR_UNION_SELECT::queue_cmp()
1494
arg Pointer to QUICK_ROR_UNION_SELECT
1495
val1 First merged select
1496
val2 Second merged select
1499
int QUICK_ROR_UNION_SELECT::queue_cmp(void *arg, unsigned char *val1, unsigned char *val2)
1501
QUICK_ROR_UNION_SELECT *self= (QUICK_ROR_UNION_SELECT*)arg;
1502
return self->head->file->cmp_ref(((QUICK_SELECT_I*)val1)->last_rowid,
1503
((QUICK_SELECT_I*)val2)->last_rowid);
1508
Initialize quick select for row retrieval.
1517
int QUICK_ROR_UNION_SELECT::reset()
1519
QUICK_SELECT_I *quick;
1521
have_prev_rowid= false;
1524
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1525
while ((quick= it++))
1527
if (quick->init_ror_merged_scan(false))
1532
queue_remove_all(&queue);
1534
Initialize scans for merged quick selects and put all merged quick
1535
selects into the queue.
1537
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1538
while ((quick= it++))
1542
if ((error= quick->get_next()))
1544
if (error == HA_ERR_END_OF_FILE)
1548
quick->save_last_pos();
1549
queue_insert(&queue, (unsigned char*)quick);
1552
if (head->file->ha_rnd_init(1))
1562
QUICK_ROR_UNION_SELECT::push_quick_back(QUICK_SELECT_I *quick_sel_range)
1564
return quick_selects.push_back(quick_sel_range);
1567
QUICK_ROR_UNION_SELECT::~QUICK_ROR_UNION_SELECT()
1569
delete_queue(&queue);
1570
quick_selects.delete_elements();
1571
if (head->file->inited != handler::NONE)
1572
head->file->ha_rnd_end();
1573
free_root(&alloc,MYF(0));
1578
QUICK_RANGE::QUICK_RANGE()
1579
:min_key(0),max_key(0),min_length(0),max_length(0),
1580
flag(NO_MIN_RANGE | NO_MAX_RANGE),
1581
min_keypart_map(0), max_keypart_map(0)
1584
SEL_ARG::SEL_ARG(SEL_ARG &arg) :Sql_alloc()
1587
min_flag=arg.min_flag;
1588
max_flag=arg.max_flag;
1589
maybe_flag=arg.maybe_flag;
1590
maybe_null=arg.maybe_null;
1593
min_value=arg.min_value;
1594
max_value=arg.max_value;
1595
next_key_part=arg.next_key_part;
1596
use_count=1; elements=1;
1600
inline void SEL_ARG::make_root()
1602
left=right= &null_element;
1605
use_count=0; elements=1;
1608
SEL_ARG::SEL_ARG(Field *f,const unsigned char *min_value_arg,
1609
const unsigned char *max_value_arg)
1610
:min_flag(0), max_flag(0), maybe_flag(0), maybe_null(f->real_maybe_null()),
1611
elements(1), use_count(1), field(f), min_value((unsigned char*) min_value_arg),
1612
max_value((unsigned char*) max_value_arg), next(0),prev(0),
1613
next_key_part(0),color(BLACK),type(KEY_RANGE)
1615
left=right= &null_element;
1618
SEL_ARG::SEL_ARG(Field *field_,uint8_t part_,
1619
unsigned char *min_value_, unsigned char *max_value_,
1620
uint8_t min_flag_,uint8_t max_flag_,uint8_t maybe_flag_)
1621
:min_flag(min_flag_),max_flag(max_flag_),maybe_flag(maybe_flag_),
1622
part(part_),maybe_null(field_->real_maybe_null()), elements(1),use_count(1),
1623
field(field_), min_value(min_value_), max_value(max_value_),
1624
next(0),prev(0),next_key_part(0),color(BLACK),type(KEY_RANGE)
1626
left=right= &null_element;
1629
SEL_ARG *SEL_ARG::clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent,
1634
/* Bail out if we have already generated too many SEL_ARGs */
1635
if (++param->alloced_sel_args > MAX_SEL_ARGS)
1638
if (type != KEY_RANGE)
1640
if (!(tmp= new (param->mem_root) SEL_ARG(type)))
1641
return 0; // out of memory
1642
tmp->prev= *next_arg; // Link into next/prev chain
1643
(*next_arg)->next=tmp;
1648
if (!(tmp= new (param->mem_root) SEL_ARG(field,part, min_value,max_value,
1649
min_flag, max_flag, maybe_flag)))
1651
tmp->parent=new_parent;
1652
tmp->next_key_part=next_key_part;
1653
if (left != &null_element)
1654
if (!(tmp->left=left->clone(param, tmp, next_arg)))
1657
tmp->prev= *next_arg; // Link into next/prev chain
1658
(*next_arg)->next=tmp;
1661
if (right != &null_element)
1662
if (!(tmp->right= right->clone(param, tmp, next_arg)))
1665
increment_use_count(1);
1667
tmp->elements= this->elements;
1671
SEL_ARG *SEL_ARG::first()
1673
SEL_ARG *next_arg=this;
1674
if (!next_arg->left)
1675
return 0; // MAYBE_KEY
1676
while (next_arg->left != &null_element)
1677
next_arg=next_arg->left;
1681
SEL_ARG *SEL_ARG::last()
1683
SEL_ARG *next_arg=this;
1684
if (!next_arg->right)
1685
return 0; // MAYBE_KEY
1686
while (next_arg->right != &null_element)
1687
next_arg=next_arg->right;
1693
Check if a compare is ok, when one takes ranges in account
1694
Returns -2 or 2 if the ranges where 'joined' like < 2 and >= 2
1697
static int sel_cmp(Field *field, unsigned char *a, unsigned char *b, uint8_t a_flag,
1701
/* First check if there was a compare to a min or max element */
1702
if (a_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1704
if ((a_flag & (NO_MIN_RANGE | NO_MAX_RANGE)) ==
1705
(b_flag & (NO_MIN_RANGE | NO_MAX_RANGE)))
1707
return (a_flag & NO_MIN_RANGE) ? -1 : 1;
1709
if (b_flag & (NO_MIN_RANGE | NO_MAX_RANGE))
1710
return (b_flag & NO_MIN_RANGE) ? 1 : -1;
1712
if (field->real_maybe_null()) // If null is part of key
1719
goto end; // NULL where equal
1720
a++; b++; // Skip NULL marker
1722
cmp=field->key_cmp(a , b);
1723
if (cmp) return cmp < 0 ? -1 : 1; // The values differed
1725
// Check if the compared equal arguments was defined with open/closed range
1727
if (a_flag & (NEAR_MIN | NEAR_MAX))
1729
if ((a_flag & (NEAR_MIN | NEAR_MAX)) == (b_flag & (NEAR_MIN | NEAR_MAX)))
1731
if (!(b_flag & (NEAR_MIN | NEAR_MAX)))
1732
return (a_flag & NEAR_MIN) ? 2 : -2;
1733
return (a_flag & NEAR_MIN) ? 1 : -1;
1735
if (b_flag & (NEAR_MIN | NEAR_MAX))
1736
return (b_flag & NEAR_MIN) ? -2 : 2;
1737
return 0; // The elements where equal
1741
SEL_ARG *SEL_ARG::clone_tree(RANGE_OPT_PARAM *param)
1743
SEL_ARG tmp_link,*next_arg,*root;
1744
next_arg= &tmp_link;
1745
if (!(root= clone(param, (SEL_ARG *) 0, &next_arg)))
1747
next_arg->next=0; // Fix last link
1748
tmp_link.next->prev=0; // Fix first link
1749
if (root) // If not OOM
5118
key_or(RANGE_OPT_PARAM *param, SEL_ARG *key1,SEL_ARG *key2)
5138
if (key1->part != key2->part)
5142
return 0; // Can't optimize this
5145
// If one of the key is MAYBE_KEY then the found region may be bigger
5146
if (key1->type == SEL_ARG::MAYBE_KEY)
5152
if (key2->type == SEL_ARG::MAYBE_KEY)
5159
if (key1->use_count > 0)
5161
if (key2->use_count == 0 || key1->elements > key2->elements)
5163
std::swap(key1,key2);
5165
if (key1->use_count > 0 || !(key1=key1->clone_tree(param)))
5169
// Add tree at key2 to tree at key1
5170
bool key2_shared=key2->use_count != 0;
5171
key1->maybe_flag|=key2->maybe_flag;
5173
for (key2=key2->first(); key2; )
5175
SEL_ARG *tmp=key1->find_range(key2); // Find key1.min <= key2.min
5180
tmp=key1->first(); // tmp.min > key2.min
5183
else if ((cmp=tmp->cmp_max_to_min(key2)) < 0)
5184
{ // Found tmp.max < key2.min
5185
SEL_ARG *next=tmp->next;
5186
if (cmp == -2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5188
// Join near ranges like tmp.max < 0 and key2.min >= 0
5189
SEL_ARG *key2_next=key2->next;
5192
if (!(key2=new SEL_ARG(*key2)))
5193
return 0; // out of memory
5194
key2->increment_use_count(key1->use_count+1);
5195
key2->next=key2_next; // New copy of key2
5197
key2->copy_min(tmp);
5198
if (!(key1=key1->tree_delete(tmp)))
5199
{ // Only one key in tree
5206
if (!(tmp=next)) // tmp.min > key2.min
5207
break; // Copy rest of key2
5210
{ // tmp.min > key2.min
5212
if ((tmp_cmp=tmp->cmp_min_to_max(key2)) > 0) // if tmp.min > key2.max
5214
if (tmp_cmp == 2 && eq_tree(tmp->next_key_part,key2->next_key_part))
5215
{ // ranges are connected
5216
tmp->copy_min_to_min(key2);
5217
key1->merge_flags(key2);
5218
if (tmp->min_flag & NO_MIN_RANGE &&
5219
tmp->max_flag & NO_MAX_RANGE)
5221
if (key1->maybe_flag)
5222
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5225
key2->increment_use_count(-1); // Free not used tree
5231
SEL_ARG *next=key2->next; // Keys are not overlapping
5234
SEL_ARG *cpy= new SEL_ARG(*key2); // Must make copy
5237
key1=key1->insert(cpy);
5238
key2->increment_use_count(key1->use_count+1);
5241
key1=key1->insert(key2); // Will destroy key2_root
5248
// tmp.max >= key2.min && tmp.min <= key.cmax(overlapping ranges)
5249
if (eq_tree(tmp->next_key_part,key2->next_key_part))
5251
if (tmp->is_same(key2))
5253
tmp->merge_flags(key2); // Copy maybe flags
5254
key2->increment_use_count(-1); // Free not used tree
5259
while (last->next && last->next->cmp_min_to_max(key2) <= 0 &&
5260
eq_tree(last->next->next_key_part,key2->next_key_part))
5264
key1=key1->tree_delete(save);
5266
last->copy_min(tmp);
5267
if (last->copy_min(key2) || last->copy_max(key2))
5270
for (; key2 ; key2=key2->next)
5271
key2->increment_use_count(-1); // Free not used tree
5272
if (key1->maybe_flag)
5273
return new SEL_ARG(SEL_ARG::MAYBE_KEY);
5281
if (cmp >= 0 && tmp->cmp_min_to_min(key2) < 0)
5282
{ // tmp.min <= x < key2.min
5283
SEL_ARG *new_arg=tmp->clone_first(key2);
5286
if ((new_arg->next_key_part= key1->next_key_part))
5287
new_arg->increment_use_count(key1->use_count+1);
5288
tmp->copy_min_to_min(key2);
5289
key1=key1->insert(new_arg);
5292
// tmp.min >= key2.min && tmp.min <= key2.max
5293
SEL_ARG key(*key2); // Get copy we can modify
5296
if (tmp->cmp_min_to_min(&key) > 0)
5297
{ // key.min <= x < tmp.min
5298
SEL_ARG *new_arg=key.clone_first(tmp);
5301
if ((new_arg->next_key_part=key.next_key_part))
5302
new_arg->increment_use_count(key1->use_count+1);
5303
key1=key1->insert(new_arg);
5305
if ((cmp=tmp->cmp_max_to_max(&key)) <= 0)
5306
{ // tmp.min. <= x <= tmp.max
5307
tmp->maybe_flag|= key.maybe_flag;
5308
key.increment_use_count(key1->use_count+1);
5309
tmp->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5310
if (!cmp) // Key2 is ready
5312
key.copy_max_to_min(tmp);
5313
if (!(tmp=tmp->next))
5315
SEL_ARG *tmp2= new SEL_ARG(key);
5318
key1=key1->insert(tmp2);
5322
if (tmp->cmp_min_to_max(&key) > 0)
5324
SEL_ARG *tmp2= new SEL_ARG(key);
5327
key1=key1->insert(tmp2);
5333
SEL_ARG *new_arg=tmp->clone_last(&key); // tmp.min <= x <= key.max
5336
tmp->copy_max_to_min(&key);
5337
tmp->increment_use_count(key1->use_count+1);
5338
/* Increment key count as it may be used for next loop */
5339
key.increment_use_count(1);
5340
new_arg->next_key_part= key_or(param, tmp->next_key_part, key.next_key_part);
5341
key1=key1->insert(new_arg);
5351
SEL_ARG *next=key2->next;
5354
SEL_ARG *tmp=new SEL_ARG(*key2); // Must make copy
5357
key2->increment_use_count(key1->use_count+1);
5358
key1=key1->insert(tmp);
5361
key1=key1->insert(key2); // Will destroy key2_root
5369
/* Compare if two trees are equal */
5371
static bool eq_tree(SEL_ARG* a,SEL_ARG *b)
5375
if (!a || !b || !a->is_same(b))
5377
if (a->left != &null_element && b->left != &null_element)
5379
if (!eq_tree(a->left,b->left))
5382
else if (a->left != &null_element || b->left != &null_element)
5384
if (a->right != &null_element && b->right != &null_element)
5386
if (!eq_tree(a->right,b->right))
5389
else if (a->right != &null_element || b->right != &null_element)
5391
if (a->next_key_part != b->next_key_part)
5393
if (!a->next_key_part != !b->next_key_part ||
5394
!eq_tree(a->next_key_part, b->next_key_part))
5402
SEL_ARG::insert(SEL_ARG *key)
5404
SEL_ARG *element, **par= NULL, *last_element= NULL;
5406
for (element= this; element != &null_element ; )
5408
last_element=element;
5409
if (key->cmp_min_to_min(element) > 0)
5411
par= &element->right; element= element->right;
5415
par = &element->left; element= element->left;
5419
key->parent=last_element;
5421
if (par == &last_element->left)
5423
key->next=last_element;
5424
if ((key->prev=last_element->prev))
5425
key->prev->next=key;
5426
last_element->prev=key;
5430
if ((key->next=last_element->next))
5431
key->next->prev=key;
5432
key->prev=last_element;
5433
last_element->next=key;
5435
key->left=key->right= &null_element;
5436
SEL_ARG *root=rb_insert(key); // rebalance tree
5437
root->use_count=this->use_count; // copy root info
5438
root->elements= this->elements+1;
5439
root->maybe_flag=this->maybe_flag;
5445
** Find best key with min <= given key
5446
** Because the call context this should never return 0 to get_range
5450
SEL_ARG::find_range(SEL_ARG *key)
5452
SEL_ARG *element=this,*found=0;
5456
if (element == &null_element)
5458
int cmp=element->cmp_min_to_min(key);
5464
element=element->right;
5467
element=element->left;
5473
Remove a element from the tree
5477
key Key that is to be deleted from tree (this)
5480
This also frees all sub trees that is used by the element
5483
root of new tree (with key deleted)
5487
SEL_ARG::tree_delete(SEL_ARG *key)
5489
enum leaf_color remove_color;
5490
SEL_ARG *root,*nod,**par,*fix_par;
5495
/* Unlink from list */
5497
key->prev->next=key->next;
5499
key->next->prev=key->prev;
5500
key->increment_use_count(-1);
5504
par=key->parent_ptr();
5506
if (key->left == &null_element)
5508
*par=nod=key->right;
5509
fix_par=key->parent;
5510
if (nod != &null_element)
5511
nod->parent=fix_par;
5512
remove_color= key->color;
5514
else if (key->right == &null_element)
5516
*par= nod=key->left;
5517
nod->parent=fix_par=key->parent;
5518
remove_color= key->color;
5522
SEL_ARG *tmp=key->next; // next bigger key (exist!)
5523
nod= *tmp->parent_ptr()= tmp->right; // unlink tmp from tree
5524
fix_par=tmp->parent;
5525
if (nod != &null_element)
5526
nod->parent=fix_par;
5527
remove_color= tmp->color;
5529
tmp->parent=key->parent; // Move node in place of key
5530
(tmp->left=key->left)->parent=tmp;
5531
if ((tmp->right=key->right) != &null_element)
5532
tmp->right->parent=tmp;
5533
tmp->color=key->color;
5535
if (fix_par == key) // key->right == key->next
5536
fix_par=tmp; // new parent of nod
5539
if (root == &null_element)
5540
return(0); // Maybe root later
5541
if (remove_color == BLACK)
5542
root=rb_delete_fixup(root,nod,fix_par);
5544
test_rb_tree(root,root->parent);
5545
#endif /* EXTRA_DEBUG */
5547
root->use_count=this->use_count; // Fix root counters
5548
root->elements=this->elements-1;
5549
root->maybe_flag=this->maybe_flag;
5554
/* Functions to fix up the tree after insert and delete */
5556
static void left_rotate(SEL_ARG **root,SEL_ARG *leaf)
5558
SEL_ARG *y=leaf->right;
5559
leaf->right=y->left;
5560
if (y->left != &null_element)
5561
y->left->parent=leaf;
5562
if (!(y->parent=leaf->parent))
5565
*leaf->parent_ptr()=y;
5570
static void right_rotate(SEL_ARG **root,SEL_ARG *leaf)
5572
SEL_ARG *y=leaf->left;
5573
leaf->left=y->right;
5574
if (y->right != &null_element)
5575
y->right->parent=leaf;
5576
if (!(y->parent=leaf->parent))
5579
*leaf->parent_ptr()=y;
5586
SEL_ARG::rb_insert(SEL_ARG *leaf)
5588
SEL_ARG *y,*par,*par2,*root;
5589
root= this; root->parent= 0;
5592
while (leaf != root && (par= leaf->parent)->color == RED)
5593
{ // This can't be root or 1 level under
5594
if (par == (par2= leaf->parent->parent)->left)
5597
if (y->color == RED)
5602
leaf->color=RED; /* And the loop continues */
5606
if (leaf == par->right)
5608
left_rotate(&root,leaf->parent);
5609
par=leaf; /* leaf is now parent to old leaf */
5613
right_rotate(&root,par2);
5620
if (y->color == RED)
5625
leaf->color=RED; /* And the loop continues */
5629
if (leaf == par->left)
5631
right_rotate(&root,par);
5636
left_rotate(&root,par2);
5643
test_rb_tree(root,root->parent);
5644
#endif /* EXTRA_DEBUG */
5650
SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key,SEL_ARG *par)
5656
while (x != root && x->color == SEL_ARG::BLACK)
5661
if (w->color == SEL_ARG::RED)
5663
w->color=SEL_ARG::BLACK;
5664
par->color=SEL_ARG::RED;
5665
left_rotate(&root,par);
5668
if (w->left->color == SEL_ARG::BLACK && w->right->color == SEL_ARG::BLACK)
5670
w->color=SEL_ARG::RED;
5675
if (w->right->color == SEL_ARG::BLACK)
5677
w->left->color=SEL_ARG::BLACK;
5678
w->color=SEL_ARG::RED;
5679
right_rotate(&root,w);
5682
w->color=par->color;
5683
par->color=SEL_ARG::BLACK;
5684
w->right->color=SEL_ARG::BLACK;
5685
left_rotate(&root,par);
5693
if (w->color == SEL_ARG::RED)
5695
w->color=SEL_ARG::BLACK;
5696
par->color=SEL_ARG::RED;
5697
right_rotate(&root,par);
5700
if (w->right->color == SEL_ARG::BLACK && w->left->color == SEL_ARG::BLACK)
5702
w->color=SEL_ARG::RED;
5707
if (w->left->color == SEL_ARG::BLACK)
5709
w->right->color=SEL_ARG::BLACK;
5710
w->color=SEL_ARG::RED;
5711
left_rotate(&root,w);
5714
w->color=par->color;
5715
par->color=SEL_ARG::BLACK;
5716
w->left->color=SEL_ARG::BLACK;
5717
right_rotate(&root,par);
5724
x->color=SEL_ARG::BLACK;
5729
/* Test that the properties for a red-black tree hold */
5732
int test_rb_tree(SEL_ARG *element,SEL_ARG *parent)
5734
int count_l,count_r;
5736
if (element == &null_element)
5737
return 0; // Found end of tree
5738
if (element->parent != parent)
5740
sql_print_error("Wrong tree: Parent doesn't point at parent");
5743
if (element->color == SEL_ARG::RED &&
5744
(element->left->color == SEL_ARG::RED ||
5745
element->right->color == SEL_ARG::RED))
5747
sql_print_error("Wrong tree: Found two red in a row");
5750
if (element->left == element->right && element->left != &null_element)
5752
sql_print_error("Wrong tree: Found right == left");
5755
count_l=test_rb_tree(element->left,element);
5756
count_r=test_rb_tree(element->right,element);
5757
if (count_l >= 0 && count_r >= 0)
5759
if (count_l == count_r)
5760
return count_l+(element->color == SEL_ARG::BLACK);
5761
sql_print_error("Wrong tree: Incorrect black-count: %d - %d",
5764
return -1; // Error, no more warnings
5769
Count how many times SEL_ARG graph "root" refers to its part "key"
5772
count_key_part_usage()
5773
root An RB-Root node in a SEL_ARG graph.
5774
key Another RB-Root node in that SEL_ARG graph.
5777
The passed "root" node may refer to "key" node via root->next_key_part,
5780
This function counts how many times the node "key" is referred (via
5781
SEL_ARG::next_key_part) by
5782
- intervals of RB-tree pointed by "root",
5783
- intervals of RB-trees that are pointed by SEL_ARG::next_key_part from
5784
intervals of RB-tree pointed by "root",
5787
Here is an example (horizontal links represent next_key_part pointers,
5788
vertical links - next/prev prev pointers):
5791
|root|-----------------+
5795
+----+ +---+ $ | +---+ Here the return value
5796
| |- ... -| |---$-+--+->|key| will be 4.
5797
+----+ +---+ $ | | +---+
5802
| |---| |---------+ |
5809
Number of links to "key" from nodes reachable from "root".
5812
static ulong count_key_part_usage(SEL_ARG *root, SEL_ARG *key)
5815
for (root=root->first(); root ; root=root->next)
5817
if (root->next_key_part)
5819
if (root->next_key_part == key)
5821
if (root->next_key_part->part < key->part)
5822
count+=count_key_part_usage(root->next_key_part,key);
5830
Check if SEL_ARG::use_count value is correct
5833
SEL_ARG::test_use_count()
5834
root The root node of the SEL_ARG graph (an RB-tree root node that
5835
has the least value of sel_arg->part in the entire graph, and
5836
thus is the "origin" of the graph)
5839
Check if SEL_ARG::use_count value is correct. See the definition of
5840
use_count for what is "correct".
5843
void SEL_ARG::test_use_count(SEL_ARG *root)
5846
if (this == root && use_count != 1)
5848
sql_print_information("Use_count: Wrong count %lu for root",use_count);
5851
if (this->type != SEL_ARG::KEY_RANGE)
5853
for (SEL_ARG *pos=first(); pos ; pos=pos->next)
5856
if (pos->next_key_part)
5858
ulong count=count_key_part_usage(root,pos->next_key_part);
5859
if (count > pos->next_key_part->use_count)
5861
sql_print_information("Use_count: Wrong count for key at 0x%lx, %lu "
5862
"should be %lu", (long unsigned int)pos,
5863
pos->next_key_part->use_count, count);
5866
pos->next_key_part->test_use_count(root);
5869
if (e_count != elements)
5870
sql_print_warning("Wrong use count: %u (should be %u) for tree at 0x%lx",
5871
e_count, elements, (long unsigned int) this);
3524
5876
/****************************************************************************
3525
5877
MRR Range Sequence Interface implementation that walks a SEL_ARG* tree.
3526
5878
****************************************************************************/
3528
5880
/* MRR range sequence, SEL_ARG* implementation: stack entry */
3529
typedef struct st_range_seq_entry
5881
typedef struct st_range_seq_entry
3532
5884
Pointers in min and max keys. They point to right-after-end of key
3533
5885
images. The 0-th entry has these pointing to key tuple start.
3535
5887
unsigned char *min_key, *max_key;
3538
5890
Flags, for {keypart0, keypart1, ... this_keypart} subtuple.
3539
5891
min_key_flag may have NULL_RANGE set.
3541
5893
uint32_t min_key_flag, max_key_flag;
3543
5895
/* Number of key parts */
3544
5896
uint32_t min_key_parts, max_key_parts;
3545
optimizer::SEL_ARG *key_tree;
3546
5898
} RANGE_SEQ_ENTRY;
4340
Range sequence interface implementation for array<QuickRange>: initialize
6706
Perform key scans for all used indexes (except CPK), get rowids and merge
6707
them into an ordered non-recurrent sequence of rowids.
6709
The merge/duplicate removal is performed using Unique class. We put all
6710
rowids into Unique, get the sorted sequence and destroy the Unique.
6712
If table has a clustered primary key that covers all rows (true for bdb
6713
and innodb currently) and one of the index_merge scans is a scan on PK,
6714
then rows that will be retrieved by PK scan are not put into Unique and
6715
primary key scan is not performed here, it is performed later separately.
6722
int QUICK_INDEX_MERGE_SELECT::read_keys_and_merge()
6724
List_iterator_fast<QUICK_RANGE_SELECT> cur_quick_it(quick_selects);
6725
QUICK_RANGE_SELECT* cur_quick;
6728
handler *file= head->file;
6730
file->extra(HA_EXTRA_KEYREAD);
6731
head->prepare_for_position();
6733
cur_quick_it.rewind();
6734
cur_quick= cur_quick_it++;
6735
assert(cur_quick != 0);
6738
We reuse the same instance of handler so we need to call both init and
6741
if (cur_quick->init() || cur_quick->reset())
6744
unique= new Unique(refpos_order_cmp, (void *)file,
6746
session->variables.sortbuff_size);
6751
while ((result= cur_quick->get_next()) == HA_ERR_END_OF_FILE)
6753
cur_quick->range_end();
6754
cur_quick= cur_quick_it++;
6758
if (cur_quick->file->inited != handler::NONE)
6759
cur_quick->file->ha_index_end();
6760
if (cur_quick->init() || cur_quick->reset())
6766
if (result != HA_ERR_END_OF_FILE)
6768
cur_quick->range_end();
6774
if (session->killed)
6777
/* skip row if it will be retrieved by clustered PK scan */
6778
if (pk_quick_select && pk_quick_select->row_in_ranges())
6781
cur_quick->file->position(cur_quick->record);
6782
result= unique->unique_add((char*)cur_quick->file->ref);
6788
/* ok, all row ids are in Unique */
6789
result= unique->get(head);
6791
doing_pk_scan= false;
6792
/* index_merge currently doesn't support "using index" at all */
6793
file->extra(HA_EXTRA_NO_KEYREAD);
6794
/* start table scan */
6795
init_read_record(&read_record, session, head, (SQL_SELECT*) 0, 1, 1);
6801
Get next row for index_merge.
6803
The rows are read from
6804
1. rowids stored in Unique.
6805
2. QUICK_RANGE_SELECT with clustered primary key (if any).
6806
The sets of rows retrieved in 1) and 2) are guaranteed to be disjoint.
6809
int QUICK_INDEX_MERGE_SELECT::get_next()
6814
return(pk_quick_select->get_next());
6816
if ((result= read_record.read_record(&read_record)) == -1)
6818
result= HA_ERR_END_OF_FILE;
6819
end_read_record(&read_record);
6820
/* All rows from Unique have been retrieved, do a clustered PK scan */
6821
if (pk_quick_select)
6823
doing_pk_scan= true;
6824
if ((result= pk_quick_select->init()) ||
6825
(result= pk_quick_select->reset()))
6827
return(pk_quick_select->get_next());
6836
Retrieve next record.
6838
QUICK_ROR_INTERSECT_SELECT::get_next()
6841
Invariant on enter/exit: all intersected selects have retrieved all index
6842
records with rowid <= some_rowid_val and no intersected select has
6843
retrieved any index records with rowid > some_rowid_val.
6844
We start fresh and loop until we have retrieved the same rowid in each of
6845
the key scans or we got an error.
6847
If a Clustered PK scan is present, it is used only to check if row
6848
satisfies its condition (and never used for row retrieval).
6852
other - Error code if any error occurred.
6855
int QUICK_ROR_INTERSECT_SELECT::get_next()
6857
List_iterator_fast<QUICK_RANGE_SELECT> quick_it(quick_selects);
6858
QUICK_RANGE_SELECT* quick;
6860
uint32_t last_rowid_count=0;
6864
/* Get a rowid for first quick and save it as a 'candidate' */
6866
error= quick->get_next();
6869
while (!error && !cpk_quick->row_in_ranges())
6870
error= quick->get_next();
6875
quick->file->position(quick->record);
6876
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6877
last_rowid_count= 1;
6879
while (last_rowid_count < quick_selects.elements)
6881
if (!(quick= quick_it++))
6889
if ((error= quick->get_next()))
6891
quick->file->position(quick->record);
6892
cmp= head->file->cmp_ref(quick->file->ref, last_rowid);
6895
/* Ok, current select 'caught up' and returned ref >= cur_ref */
6898
/* Found a row with ref > cur_ref. Make it a new 'candidate' */
6901
while (!cpk_quick->row_in_ranges())
6903
if ((error= quick->get_next()))
6907
memcpy(last_rowid, quick->file->ref, head->file->ref_length);
6908
last_rowid_count= 1;
6912
/* current 'candidate' row confirmed by this select */
6917
/* We get here if we got the same row ref in all scans. */
6918
if (need_to_fetch_row)
6919
error= head->file->rnd_pos(head->record[0], last_rowid);
6920
} while (error == HA_ERR_RECORD_DELETED);
6926
Retrieve next record.
6928
QUICK_ROR_UNION_SELECT::get_next()
6931
Enter/exit invariant:
6932
For each quick select in the queue a {key,rowid} tuple has been
6933
retrieved but the corresponding row hasn't been passed to output.
6937
other - Error code if any error occurred.
6940
int QUICK_ROR_UNION_SELECT::get_next()
6943
QUICK_SELECT_I *quick;
6950
if (!queue.elements)
6951
return(HA_ERR_END_OF_FILE);
6952
/* Ok, we have a queue with >= 1 scans */
6954
quick= (QUICK_SELECT_I*)queue_top(&queue);
6955
memcpy(cur_rowid, quick->last_rowid, rowid_length);
6957
/* put into queue rowid from the same stream as top element */
6958
if ((error= quick->get_next()))
6960
if (error != HA_ERR_END_OF_FILE)
6962
queue_remove(&queue, 0);
6966
quick->save_last_pos();
6967
queue_replaced(&queue);
6970
if (!have_prev_rowid)
6972
/* No rows have been returned yet */
6974
have_prev_rowid= true;
6977
dup_row= !head->file->cmp_ref(cur_rowid, prev_rowid);
6981
cur_rowid= prev_rowid;
6984
error= head->file->rnd_pos(quick->record, prev_rowid);
6985
} while (error == HA_ERR_RECORD_DELETED);
6990
int QUICK_RANGE_SELECT::reset()
6993
unsigned char *mrange_buff;
6995
HANDLER_BUFFER empty_buf;
6997
cur_range= (QUICK_RANGE**) ranges.buffer;
6999
if (file->inited == handler::NONE && (error= file->ha_index_init(index,1)))
7002
/* Allocate buffer if we need one but haven't allocated it yet */
7003
if (mrr_buf_size && !mrr_buf_desc)
7005
buf_size= mrr_buf_size;
7006
while (buf_size && !my_multi_malloc(MYF(MY_WME),
7007
&mrr_buf_desc, sizeof(*mrr_buf_desc),
7008
&mrange_buff, buf_size,
7011
/* Try to shrink the buffers until both are 0. */
7015
return(HA_ERR_OUT_OF_MEM);
7017
/* Initialize the handler buffer. */
7018
mrr_buf_desc->buffer= mrange_buff;
7019
mrr_buf_desc->buffer_end= mrange_buff + buf_size;
7020
mrr_buf_desc->end_of_used_area= mrange_buff;
7024
empty_buf.buffer= empty_buf.buffer_end= empty_buf.end_of_used_area= NULL;
7027
mrr_flags |= HA_MRR_SORTED;
7028
RANGE_SEQ_IF seq_funcs= {quick_range_seq_init, quick_range_seq_next};
7029
error= file->multi_range_read_init(&seq_funcs, (void*)this, ranges.elements,
7030
mrr_flags, mrr_buf_desc? mrr_buf_desc:
7037
Range sequence interface implementation for array<QUICK_RANGE>: initialize
4343
7040
quick_range_seq_init()
4344
init_param Caller-opaque paramenter: QuickRangeSelect* pointer
7041
init_param Caller-opaque paramenter: QUICK_RANGE_SELECT* pointer
4345
7042
n_ranges Number of ranges in the sequence (ignored)
4346
flags MRR flags (currently not used)
7043
flags MRR flags (currently not used)
4349
7046
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)
7049
range_seq_t quick_range_seq_init(void *init_param,
7050
uint32_t n_ranges __attribute__((unused)),
7051
uint32_t flags __attribute__((unused)))
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;
7053
QUICK_RANGE_SELECT *quick= (QUICK_RANGE_SELECT*)init_param;
7054
quick->qr_traversal_ctx.first= (QUICK_RANGE**)quick->ranges.buffer;
7055
quick->qr_traversal_ctx.cur= (QUICK_RANGE**)quick->ranges.buffer;
4357
7056
quick->qr_traversal_ctx.last= quick->qr_traversal_ctx.cur +
4358
7057
quick->ranges.elements;
4359
7058
return &quick->qr_traversal_ctx;
4373
7072
1 No more ranges in the sequence
4375
uint32_t optimizer::quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
7075
uint32_t quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range)
4377
QuickRangeSequenceContext *ctx= (QuickRangeSequenceContext*) rseq;
7077
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)rseq;
4379
7079
if (ctx->cur == ctx->last)
4380
7080
return 1; /* no more ranges */
4382
optimizer::QuickRange *cur= *(ctx->cur);
7082
QUICK_RANGE *cur= *(ctx->cur);
4383
7083
key_range *start_key= &range->start_key;
4384
key_range *end_key= &range->end_key;
7084
key_range *end_key= &range->end_key;
4386
start_key->key= cur->min_key;
7086
start_key->key= cur->min_key;
4387
7087
start_key->length= cur->min_length;
4388
7088
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;
7089
start_key->flag= ((cur->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7090
(cur->flag & EQ_RANGE) ?
7091
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7092
end_key->key= cur->max_key;
7093
end_key->length= cur->max_length;
4394
7094
end_key->keypart_map= cur->max_keypart_map;
4396
7096
We use HA_READ_AFTER_KEY here because if we are reading on a key
4397
7097
prefix. We want to find all keys with this prefix.
4399
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7099
end_key->flag= (cur->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
4401
7101
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);
7108
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7111
mrr_persistent_flag_storage()
7112
seq Range sequence being traversed
7116
MRR/NDB implementation needs to store some bits for each range. This
7117
function returns a reference to the "range_flag" associated with the
7120
This function should be removed when we get a proper MRR/NDB
7124
Reference to range_flag associated with range number #idx
7127
uint16_t &mrr_persistent_flag_storage(range_seq_t seq, uint32_t idx)
7129
QUICK_RANGE_SEQ_CTX *ctx= (QUICK_RANGE_SEQ_CTX*)seq;
7130
return ctx->first[idx]->flag;
7135
MRR range sequence interface: array<QUICK_RANGE> impl: utility func for NDB
7138
mrr_get_ptr_by_idx()
7139
seq Range sequence bening traversed
7140
idx Number of the range
7143
An extension of MRR range sequence interface needed by NDB: return the
7144
data associated with the given range.
7146
A proper MRR interface implementer is supposed to store and return
7147
range-associated data. NDB stores number of the range instead. So this
7148
is a helper function that translates range number to range associated
7151
This function does nothing, as currrently there is only one user of the
7152
MRR interface - the quick range select code, and this user doesn't need
7153
to use range-associated data.
7156
Reference to range-associated data
7159
char* &mrr_get_ptr_by_idx(range_seq_t seq __attribute__((unused)),
7160
uint32_t idx __attribute__((unused)))
7168
Get next possible record using quick-struct.
7171
QUICK_RANGE_SELECT::get_next()
7174
Record is read into table->record[0]
7178
HA_ERR_END_OF_FILE No (more) rows in range
7182
int QUICK_RANGE_SELECT::get_next()
7185
if (in_ror_merged_scan)
7188
We don't need to signal the bitmap change as the bitmap is always the
7189
same for this head->file
7191
head->column_bitmaps_set_no_signal(&column_bitmap, &column_bitmap);
7194
int result= file->multi_range_read_next(&dummy);
7196
if (in_ror_merged_scan)
7198
/* Restore bitmaps set on entry */
7199
head->column_bitmaps_set_no_signal(save_read_set, save_write_set);
7206
Get the next record with a different prefix.
7209
QUICK_RANGE_SELECT::get_next_prefix()
7210
prefix_length length of cur_prefix
7211
cur_prefix prefix of a key to be searched for
7214
Each subsequent call to the method retrieves the first record that has a
7215
prefix with length prefix_length different from cur_prefix, such that the
7216
record with the new prefix is within the ranges described by
7217
this->ranges. The record found is stored into the buffer pointed by
7219
The method is useful for GROUP-BY queries with range conditions to
7220
discover the prefix of the next group that satisfies the range conditions.
7223
This method is a modified copy of QUICK_RANGE_SELECT::get_next(), so both
7224
methods should be unified into a more general one to reduce code
7229
HA_ERR_END_OF_FILE if returned all keys
7230
other if some error occurred
7233
int QUICK_RANGE_SELECT::get_next_prefix(uint32_t prefix_length,
7234
key_part_map keypart_map,
7235
unsigned char *cur_prefix)
7240
key_range start_key, end_key;
7243
/* Read the next record in the same range with prefix after cur_prefix. */
7244
assert(cur_prefix != 0);
7245
result= file->index_read_map(record, cur_prefix, keypart_map,
7247
if (result || (file->compare_key(file->end_range) <= 0))
7251
uint32_t count= ranges.elements - (cur_range - (QUICK_RANGE**) ranges.buffer);
7254
/* Ranges have already been used up before. None is left for read. */
7256
return(HA_ERR_END_OF_FILE);
7258
last_range= *(cur_range++);
7260
start_key.key= (const unsigned char*) last_range->min_key;
7261
start_key.length= cmin(last_range->min_length, (uint16_t)prefix_length);
7262
start_key.keypart_map= last_range->min_keypart_map & keypart_map;
7263
start_key.flag= ((last_range->flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
7264
(last_range->flag & EQ_RANGE) ?
7265
HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
7266
end_key.key= (const unsigned char*) last_range->max_key;
7267
end_key.length= cmin(last_range->max_length, (uint16_t)prefix_length);
7268
end_key.keypart_map= last_range->max_keypart_map & keypart_map;
7270
We use READ_AFTER_KEY here because if we are reading on a key
7271
prefix we want to find all keys with this prefix
7273
end_key.flag= (last_range->flag & NEAR_MAX ? HA_READ_BEFORE_KEY :
7276
result= file->read_range_first(last_range->min_keypart_map ? &start_key : 0,
7277
last_range->max_keypart_map ? &end_key : 0,
7278
test(last_range->flag & EQ_RANGE),
7280
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7281
last_range= 0; // Stop searching
7283
if (result != HA_ERR_END_OF_FILE)
7285
last_range= 0; // No matching rows; go to next range
7291
Check if current row will be retrieved by this QUICK_RANGE_SELECT
7294
It is assumed that currently a scan is being done on another index
7295
which reads all necessary parts of the index that is scanned by this
7297
The implementation does a binary search on sorted array of disjoint
7298
ranges, without taking size of range into account.
7300
This function is used to filter out clustered PK scan rows in
7301
index_merge quick select.
7304
true if current row will be retrieved by this quick select
7308
bool QUICK_RANGE_SELECT::row_in_ranges()
7312
uint32_t max= ranges.elements - 1;
7313
uint32_t mid= (max + min)/2;
7317
if (cmp_next(*(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid)))
7319
/* current row value > mid->max */
7324
mid= (min + max) / 2;
7326
res= *(QUICK_RANGE**)dynamic_array_ptr(&ranges, mid);
7327
return (!cmp_next(res) && !cmp_prev(res));
7331
This is a hack: we inherit from QUICK_SELECT so that we can use the
7332
get_next() interface, but we have to hold a pointer to the original
7333
QUICK_SELECT because its data are used all over the place. What
7334
should be done is to factor out the data that is needed into a base
7335
class (QUICK_SELECT), and then have two subclasses (_ASC and _DESC)
7336
which handle the ranges and implement the get_next() function. But
7337
for now, this seems to work right at least.
7340
QUICK_SELECT_DESC::QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q,
7341
uint32_t used_key_parts_arg __attribute__((unused)),
7342
bool *create_err __attribute__((unused)))
7343
:QUICK_RANGE_SELECT(*q), rev_it(rev_ranges)
7347
QUICK_RANGE **pr= (QUICK_RANGE**)ranges.buffer;
7348
QUICK_RANGE **end_range= pr + ranges.elements;
7349
for (; pr!=end_range; pr++)
7350
rev_ranges.push_front(*pr);
7352
/* Remove EQ_RANGE flag for keys that are not using the full key */
7353
for (r = rev_it++; r; r = rev_it++)
7355
if ((r->flag & EQ_RANGE) &&
7356
head->key_info[index].key_length != r->max_length)
7357
r->flag&= ~EQ_RANGE;
7360
q->dont_free=1; // Don't free shared mem
7365
int QUICK_SELECT_DESC::get_next()
7367
/* The max key is handled as follows:
7368
* - if there is NO_MAX_RANGE, start at the end and move backwards
7369
* - if it is an EQ_RANGE, which means that max key covers the entire
7370
* key, go directly to the key and read through it (sorting backwards is
7371
* same as sorting forwards)
7372
* - if it is NEAR_MAX, go to the key or next, step back once, and
7374
* - otherwise (not NEAR_MAX == include the key), go after the key,
7375
* step back once, and move backwards
7382
{ // Already read through key
7383
result = ((last_range->flag & EQ_RANGE)
7384
? file->index_next_same(record, last_range->min_key,
7385
last_range->min_length) :
7386
file->index_prev(record));
7389
if (cmp_prev(*rev_it.ref()) == 0)
7392
else if (result != HA_ERR_END_OF_FILE)
7396
if (!(last_range= rev_it++))
7397
return(HA_ERR_END_OF_FILE); // All ranges used
7399
if (last_range->flag & NO_MAX_RANGE) // Read last record
7402
if ((local_error=file->index_last(record)))
7403
return(local_error); // Empty table
7404
if (cmp_prev(last_range) == 0)
7406
last_range= 0; // No match; go to next range
7410
if (last_range->flag & EQ_RANGE)
7412
result = file->index_read_map(record, last_range->max_key,
7413
last_range->max_keypart_map,
7418
assert(last_range->flag & NEAR_MAX ||
7419
range_reads_after_key(last_range));
7420
result=file->index_read_map(record, last_range->max_key,
7421
last_range->max_keypart_map,
7422
((last_range->flag & NEAR_MAX) ?
7423
HA_READ_BEFORE_KEY :
7424
HA_READ_PREFIX_LAST_OR_PREV));
7428
if (result != HA_ERR_KEY_NOT_FOUND && result != HA_ERR_END_OF_FILE)
7430
last_range= 0; // Not found, to next range
7433
if (cmp_prev(last_range) == 0)
7435
if (last_range->flag == (UNIQUE_RANGE | EQ_RANGE))
7436
last_range= 0; // Stop searching
7437
return(0); // Found key is in range
7439
last_range= 0; // To next range
7445
Compare if found key is over max-value
7446
Returns 0 if key <= range->max_key
7447
TODO: Figure out why can't this function be as simple as cmp_prev().
7450
int QUICK_RANGE_SELECT::cmp_next(QUICK_RANGE *range_arg)
7452
if (range_arg->flag & NO_MAX_RANGE)
7453
return 0; /* key can't be to large */
7455
KEY_PART *key_part=key_parts;
7456
uint32_t store_length;
7458
for (unsigned char *key=range_arg->max_key, *end=key+range_arg->max_length;
7460
key+= store_length, key_part++)
7463
store_length= key_part->store_length;
7464
if (key_part->null_bit)
7468
if (!key_part->field->is_null())
7472
else if (key_part->field->is_null())
7474
key++; // Skip null byte
7477
if ((cmp=key_part->field->key_cmp(key, key_part->length)) < 0)
7482
return (range_arg->flag & NEAR_MAX) ? 1 : 0; // Exact match
7487
Returns 0 if found key is inside range (found key >= range->min_key).
7490
int QUICK_RANGE_SELECT::cmp_prev(QUICK_RANGE *range_arg)
7493
if (range_arg->flag & NO_MIN_RANGE)
7494
return 0; /* key can't be to small */
7496
cmp= key_cmp(key_part_info, range_arg->min_key,
7497
range_arg->min_length);
7498
if (cmp > 0 || (cmp == 0 && (range_arg->flag & NEAR_MIN) == false))
7500
return 1; // outside of range
7505
* true if this range will require using HA_READ_AFTER_KEY
7506
See comment in get_next() about this
7509
bool QUICK_SELECT_DESC::range_reads_after_key(QUICK_RANGE *range_arg)
7511
return ((range_arg->flag & (NO_MAX_RANGE | NEAR_MAX)) ||
7512
!(range_arg->flag & EQ_RANGE) ||
7513
head->key_info[index].key_length != range_arg->max_length) ? 1 : 0;
7517
void QUICK_RANGE_SELECT::add_info_string(String *str)
7519
KEY *key_info= head->key_info + index;
7520
str->append(key_info->name);
7523
void QUICK_INDEX_MERGE_SELECT::add_info_string(String *str)
7525
QUICK_RANGE_SELECT *quick;
7527
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7528
str->append(STRING_WITH_LEN("sort_union("));
7529
while ((quick= it++))
7535
quick->add_info_string(str);
7537
if (pk_quick_select)
7540
pk_quick_select->add_info_string(str);
7545
void QUICK_ROR_INTERSECT_SELECT::add_info_string(String *str)
7548
QUICK_RANGE_SELECT *quick;
7549
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7550
str->append(STRING_WITH_LEN("intersect("));
7551
while ((quick= it++))
7553
KEY *key_info= head->key_info + quick->index;
7558
str->append(key_info->name);
7562
KEY *key_info= head->key_info + cpk_quick->index;
7564
str->append(key_info->name);
7569
void QUICK_ROR_UNION_SELECT::add_info_string(String *str)
7572
QUICK_SELECT_I *quick;
7573
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7574
str->append(STRING_WITH_LEN("union("));
7575
while ((quick= it++))
7581
quick->add_info_string(str);
7587
void QUICK_RANGE_SELECT::add_keys_and_lengths(String *key_names,
7588
String *used_lengths)
7592
KEY *key_info= head->key_info + index;
7593
key_names->append(key_info->name);
7594
length= int64_t2str(max_used_key_length, buf, 10) - buf;
7595
used_lengths->append(buf, length);
7598
void QUICK_INDEX_MERGE_SELECT::add_keys_and_lengths(String *key_names,
7599
String *used_lengths)
7604
QUICK_RANGE_SELECT *quick;
7606
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7607
while ((quick= it++))
7613
key_names->append(',');
7614
used_lengths->append(',');
7617
KEY *key_info= head->key_info + quick->index;
7618
key_names->append(key_info->name);
7619
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7620
used_lengths->append(buf, length);
7622
if (pk_quick_select)
7624
KEY *key_info= head->key_info + pk_quick_select->index;
7625
key_names->append(',');
7626
key_names->append(key_info->name);
7627
length= int64_t2str(pk_quick_select->max_used_key_length, buf, 10) - buf;
7628
used_lengths->append(',');
7629
used_lengths->append(buf, length);
7633
void QUICK_ROR_INTERSECT_SELECT::add_keys_and_lengths(String *key_names,
7634
String *used_lengths)
7639
QUICK_RANGE_SELECT *quick;
7640
List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
7641
while ((quick= it++))
7643
KEY *key_info= head->key_info + quick->index;
7648
key_names->append(',');
7649
used_lengths->append(',');
7651
key_names->append(key_info->name);
7652
length= int64_t2str(quick->max_used_key_length, buf, 10) - buf;
7653
used_lengths->append(buf, length);
7658
KEY *key_info= head->key_info + cpk_quick->index;
7659
key_names->append(',');
7660
key_names->append(key_info->name);
7661
length= int64_t2str(cpk_quick->max_used_key_length, buf, 10) - buf;
7662
used_lengths->append(',');
7663
used_lengths->append(buf, length);
7667
void QUICK_ROR_UNION_SELECT::add_keys_and_lengths(String *key_names,
7668
String *used_lengths)
7671
QUICK_SELECT_I *quick;
7672
List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
7673
while ((quick= it++))
7679
used_lengths->append(',');
7680
key_names->append(',');
7682
quick->add_keys_and_lengths(key_names, used_lengths);
7687
/*******************************************************************************
7688
* Implementation of QUICK_GROUP_MIN_MAX_SELECT
7689
*******************************************************************************/
7691
static inline uint32_t get_field_keypart(KEY *index, Field *field);
7692
static inline SEL_ARG * get_index_range_tree(uint32_t index, SEL_TREE* range_tree,
7693
PARAM *param, uint32_t *param_idx);
7694
static bool get_constant_key_infix(KEY *index_info, SEL_ARG *index_range_tree,
7695
KEY_PART_INFO *first_non_group_part,
7696
KEY_PART_INFO *min_max_arg_part,
7697
KEY_PART_INFO *last_part, Session *session,
7698
unsigned char *key_infix, uint32_t *key_infix_len,
7699
KEY_PART_INFO **first_non_infix_part);
7701
check_group_min_max_predicates(COND *cond, Item_field *min_max_arg_item,
7702
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,
7705
cost_group_min_max(Table* table, KEY *index_info, uint32_t used_key_parts,
7706
uint32_t group_key_parts, SEL_TREE *range_tree,
7707
SEL_ARG *index_tree, ha_rows quick_prefix_records,
7708
bool have_min, bool have_max,
7709
double *read_cost, ha_rows *records);
5551
8762
quick->update_key_stat();
5552
8763
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 */
8770
Construct new quick select for group queries with min/max.
8773
QUICK_GROUP_MIN_MAX_SELECT::QUICK_GROUP_MIN_MAX_SELECT()
8774
table The table being accessed
8775
join Descriptor of the current query
8776
have_min true if the query selects a MIN function
8777
have_max true if the query selects a MAX function
8778
min_max_arg_part The only argument field of all MIN/MAX functions
8779
group_prefix_len Length of all key parts in the group prefix
8780
prefix_key_parts All key parts in the group prefix
8781
index_info The index chosen for data access
8782
use_index The id of index_info
8783
read_cost Cost of this access method
8784
records Number of records returned
8785
key_infix_len Length of the key infix appended to the group prefix
8786
key_infix Infix of constants from equality predicates
8787
parent_alloc Memory pool for this and quick_prefix_select data
8793
QUICK_GROUP_MIN_MAX_SELECT::
8794
QUICK_GROUP_MIN_MAX_SELECT(Table *table, JOIN *join_arg, bool have_min_arg,
8796
KEY_PART_INFO *min_max_arg_part_arg,
8797
uint32_t group_prefix_len_arg, uint32_t group_key_parts_arg,
8798
uint32_t used_key_parts_arg, KEY *index_info_arg,
8799
uint32_t use_index, double read_cost_arg,
8800
ha_rows records_arg, uint32_t key_infix_len_arg,
8801
unsigned char *key_infix_arg, MEM_ROOT *parent_alloc)
8802
:join(join_arg), index_info(index_info_arg),
8803
group_prefix_len(group_prefix_len_arg),
8804
group_key_parts(group_key_parts_arg), have_min(have_min_arg),
8805
have_max(have_max_arg), seen_first_key(false),
8806
min_max_arg_part(min_max_arg_part_arg), key_infix(key_infix_arg),
8807
key_infix_len(key_infix_len_arg), min_functions_it(NULL),
8808
max_functions_it(NULL)
8813
record= head->record[0];
8814
tmp_record= head->record[1];
8815
read_time= read_cost_arg;
8816
records= records_arg;
8817
used_key_parts= used_key_parts_arg;
8818
real_key_parts= used_key_parts_arg;
8819
real_prefix_len= group_prefix_len + key_infix_len;
8821
min_max_arg_len= min_max_arg_part ? min_max_arg_part->store_length : 0;
8824
We can't have parent_alloc set as the init function can't handle this case
8827
assert(!parent_alloc);
8830
init_sql_alloc(&alloc, join->session->variables.range_alloc_block_size, 0);
8831
join->session->mem_root= &alloc;
8834
memset(&alloc, 0, sizeof(MEM_ROOT)); // ensure that it's not used
8839
Do post-constructor initialization.
8842
QUICK_GROUP_MIN_MAX_SELECT::init()
8845
The method performs initialization that cannot be done in the constructor
8846
such as memory allocations that may fail. It allocates memory for the
8847
group prefix and inifix buffers, and for the lists of MIN/MAX item to be
8848
updated during execution.
8855
int QUICK_GROUP_MIN_MAX_SELECT::init()
8857
if (group_prefix) /* Already initialized. */
8860
if (!(last_prefix= (unsigned char*) alloc_root(&alloc, group_prefix_len)))
8863
We may use group_prefix to store keys with all select fields, so allocate
8864
enough space for it.
8866
if (!(group_prefix= (unsigned char*) alloc_root(&alloc,
8867
real_prefix_len + min_max_arg_len)))
8870
if (key_infix_len > 0)
8873
The memory location pointed to by key_infix will be deleted soon, so
8874
allocate a new buffer and copy the key_infix into it.
8876
unsigned char *tmp_key_infix= (unsigned char*) alloc_root(&alloc, key_infix_len);
8879
memcpy(tmp_key_infix, this->key_infix, key_infix_len);
8880
this->key_infix= tmp_key_infix;
8883
if (min_max_arg_part)
8885
if (my_init_dynamic_array(&min_max_ranges, sizeof(QUICK_RANGE*), 16, 16))
8890
if (!(min_functions= new List<Item_sum>))
8894
min_functions= NULL;
8897
if (!(max_functions= new List<Item_sum>))
8901
max_functions= NULL;
8903
Item_sum *min_max_item;
8904
Item_sum **func_ptr= join->sum_funcs;
8905
while ((min_max_item= *(func_ptr++)))
8907
if (have_min && (min_max_item->sum_func() == Item_sum::MIN_FUNC))
8908
min_functions->push_back(min_max_item);
8909
else if (have_max && (min_max_item->sum_func() == Item_sum::MAX_FUNC))
8910
max_functions->push_back(min_max_item);
8915
if (!(min_functions_it= new List_iterator<Item_sum>(*min_functions)))
8921
if (!(max_functions_it= new List_iterator<Item_sum>(*max_functions)))
8926
min_max_ranges.elements= 0;
8932
QUICK_GROUP_MIN_MAX_SELECT::~QUICK_GROUP_MIN_MAX_SELECT()
8934
if (file->inited != handler::NONE)
8935
file->ha_index_end();
8936
if (min_max_arg_part)
8937
delete_dynamic(&min_max_ranges);
8938
free_root(&alloc,MYF(0));
8939
delete min_functions_it;
8940
delete max_functions_it;
8941
delete quick_prefix_select;
8947
Eventually create and add a new quick range object.
8950
QUICK_GROUP_MIN_MAX_SELECT::add_range()
8951
sel_range Range object from which a
8954
Construct a new QUICK_RANGE object from a SEL_ARG object, and
8955
add it to the array min_max_ranges. If sel_arg is an infinite
8956
range, e.g. (x < 5 or x > 4), then skip it and do not construct
8964
bool QUICK_GROUP_MIN_MAX_SELECT::add_range(SEL_ARG *sel_range)
8967
uint32_t range_flag= sel_range->min_flag | sel_range->max_flag;
8969
/* Skip (-inf,+inf) ranges, e.g. (x < 5 or x > 4). */
8970
if ((range_flag & NO_MIN_RANGE) && (range_flag & NO_MAX_RANGE))
8973
if (!(sel_range->min_flag & NO_MIN_RANGE) &&
8974
!(sel_range->max_flag & NO_MAX_RANGE))
8976
if (sel_range->maybe_null &&
8977
sel_range->min_value[0] && sel_range->max_value[0])
8978
range_flag|= NULL_RANGE; /* IS NULL condition */
8979
else if (memcmp(sel_range->min_value, sel_range->max_value,
8980
min_max_arg_len) == 0)
8981
range_flag|= EQ_RANGE; /* equality condition */
8983
range= new QUICK_RANGE(sel_range->min_value, min_max_arg_len,
8984
make_keypart_map(sel_range->part),
8985
sel_range->max_value, min_max_arg_len,
8986
make_keypart_map(sel_range->part),
8990
if (insert_dynamic(&min_max_ranges, (unsigned char*)&range))
8997
Opens the ranges if there are more conditions in quick_prefix_select than
8998
the ones used for jumping through the prefixes.
9001
QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges()
9004
quick_prefix_select is made over the conditions on the whole key.
9005
It defines a number of ranges of length x.
9006
However when jumping through the prefixes we use only the the first
9007
few most significant keyparts in the range key. However if there
9008
are more keyparts to follow the ones we are using we must make the
9009
condition on the key inclusive (because x < "ab" means
9010
x[0] < 'a' OR (x[0] == 'a' AND x[1] < 'b').
9011
To achive the above we must turn off the NEAR_MIN/NEAR_MAX
9013
void QUICK_GROUP_MIN_MAX_SELECT::adjust_prefix_ranges ()
9015
if (quick_prefix_select &&
9016
group_prefix_len < quick_prefix_select->max_used_key_length)
9021
for (inx= 0, arr= &quick_prefix_select->ranges; inx < arr->elements; inx++)
9025
get_dynamic(arr, (unsigned char*)&range, inx);
9026
range->flag &= ~(NEAR_MIN | NEAR_MAX);
9033
Determine the total number and length of the keys that will be used for
9037
QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9040
The total length of the keys used for index lookup depends on whether
9041
there are any predicates referencing the min/max argument, and/or if
9042
the min/max argument field can be NULL.
9043
This function does an optimistic analysis whether the search key might
9044
be extended by a constant for the min/max keypart. It is 'optimistic'
9045
because during actual execution it may happen that a particular range
9046
is skipped, and then a shorter key will be used. However this is data
9047
dependent and can't be easily estimated here.
9053
void QUICK_GROUP_MIN_MAX_SELECT::update_key_stat()
9055
max_used_key_length= real_prefix_len;
9056
if (min_max_ranges.elements > 0)
9058
QUICK_RANGE *cur_range;
9060
{ /* Check if the right-most range has a lower boundary. */
9061
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range,
9062
min_max_ranges.elements - 1);
9063
if (!(cur_range->flag & NO_MIN_RANGE))
9065
max_used_key_length+= min_max_arg_len;
9071
{ /* Check if the left-most range has an upper boundary. */
9072
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, 0);
9073
if (!(cur_range->flag & NO_MAX_RANGE))
9075
max_used_key_length+= min_max_arg_len;
9081
else if (have_min && min_max_arg_part &&
9082
min_max_arg_part->field->real_maybe_null())
9085
If a MIN/MAX argument value is NULL, we can quickly determine
9086
that we're in the beginning of the next group, because NULLs
9087
are always < any other value. This allows us to quickly
9088
determine the end of the current group and jump to the next
9089
group (see next_min()) and thus effectively increases the
9092
max_used_key_length+= min_max_arg_len;
9099
Initialize a quick group min/max select for key retrieval.
9102
QUICK_GROUP_MIN_MAX_SELECT::reset()
9105
Initialize the index chosen for access and find and store the prefix
9106
of the last group. The method is expensive since it performs disk access.
9113
int QUICK_GROUP_MIN_MAX_SELECT::reset(void)
9117
file->extra(HA_EXTRA_KEYREAD); /* We need only the key attributes */
9118
if ((result= file->ha_index_init(index,1)))
9120
if (quick_prefix_select && quick_prefix_select->reset())
9122
result= file->index_last(record);
9123
if (result == HA_ERR_END_OF_FILE)
9125
/* Save the prefix of the last group. */
9126
key_copy(last_prefix, record, index_info, group_prefix_len);
9134
Get the next key containing the MIN and/or MAX key for the next group.
9137
QUICK_GROUP_MIN_MAX_SELECT::get_next()
9140
The method finds the next subsequent group of records that satisfies the
9141
query conditions and finds the keys that contain the MIN/MAX values for
9142
the key part referenced by the MIN/MAX function(s). Once a group and its
9143
MIN/MAX values are found, store these values in the Item_sum objects for
9144
the MIN/MAX functions. The rest of the values in the result row are stored
9145
in the Item_field::result_field of each select field. If the query does
9146
not contain MIN and/or MAX functions, then the function only finds the
9147
group prefix, which is a query answer itself.
9150
If both MIN and MAX are computed, then we use the fact that if there is
9151
no MIN key, there can't be a MAX key as well, so we can skip looking
9152
for a MAX key in this case.
9156
HA_ERR_END_OF_FILE if returned all keys
9157
other if some error occurred
9160
int QUICK_GROUP_MIN_MAX_SELECT::get_next()
9165
int is_last_prefix= 0;
9168
Loop until a group is found that satisfies all query conditions or the last
9173
result= next_prefix();
9175
Check if this is the last group prefix. Notice that at this point
9176
this->record contains the current prefix in record format.
9180
is_last_prefix= key_cmp(index_info->key_part, last_prefix,
9182
assert(is_last_prefix <= 0);
9186
if (result == HA_ERR_KEY_NOT_FOUND)
9193
min_res= next_min();
9195
update_min_result();
9197
/* If there is no MIN in the group, there is no MAX either. */
9198
if ((have_max && !have_min) ||
9199
(have_max && have_min && (min_res == 0)))
9201
max_res= next_max();
9203
update_max_result();
9204
/* If a MIN was found, a MAX must have been found as well. */
9205
assert((have_max && !have_min) ||
9206
(have_max && have_min && (max_res == 0)));
9209
If this is just a GROUP BY or DISTINCT without MIN or MAX and there
9210
are equality predicates for the key parts after the group, find the
9211
first sub-group with the extended prefix.
9213
if (!have_min && !have_max && key_infix_len > 0)
9214
result= file->index_read_map(record, group_prefix,
9215
make_prev_keypart_map(real_key_parts),
9218
result= have_min ? min_res : have_max ? max_res : result;
9219
} while ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9220
is_last_prefix != 0);
9225
Partially mimic the behavior of end_select_send. Copy the
9226
field data from Item_field::field into Item_field::result_field
9227
of each non-aggregated field (the group fields, and optionally
9228
other fields in non-ANSI SQL mode).
9230
copy_fields(&join->tmp_table_param);
9232
else if (result == HA_ERR_KEY_NOT_FOUND)
9233
result= HA_ERR_END_OF_FILE;
9240
Retrieve the minimal key in the next group.
9243
QUICK_GROUP_MIN_MAX_SELECT::next_min()
9246
Find the minimal key within this group such that the key satisfies the query
9247
conditions and NULL semantics. The found key is loaded into this->record.
9250
Depending on the values of min_max_ranges.elements, key_infix_len, and
9251
whether there is a NULL in the MIN field, this function may directly
9252
return without any data access. In this case we use the key loaded into
9253
this->record by the call to this->next_prefix() just before this call.
9257
HA_ERR_KEY_NOT_FOUND if no MIN key was found that fulfills all conditions.
9258
HA_ERR_END_OF_FILE - "" -
9259
other if some error occurred
9262
int QUICK_GROUP_MIN_MAX_SELECT::next_min()
9266
/* Find the MIN key using the eventually extended group prefix. */
9267
if (min_max_ranges.elements > 0)
9269
if ((result= next_min_in_range()))
9274
/* Apply the constant equality conditions to the non-group select fields */
9275
if (key_infix_len > 0)
9277
if ((result= file->index_read_map(record, group_prefix,
9278
make_prev_keypart_map(real_key_parts),
9279
HA_READ_KEY_EXACT)))
9284
If the min/max argument field is NULL, skip subsequent rows in the same
9285
group with NULL in it. Notice that:
9286
- if the first row in a group doesn't have a NULL in the field, no row
9287
in the same group has (because NULL < any other value),
9288
- min_max_arg_part->field->ptr points to some place in 'record'.
9290
if (min_max_arg_part && min_max_arg_part->field->is_null())
9292
/* Find the first subsequent record without NULL in the MIN/MAX field. */
9293
key_copy(tmp_record, record, index_info, 0);
9294
result= file->index_read_map(record, tmp_record,
9295
make_keypart_map(real_key_parts),
9298
Check if the new record belongs to the current group by comparing its
9299
prefix with the group's prefix. If it is from the next group, then the
9300
whole group has NULLs in the MIN/MAX field, so use the first record in
9301
the group as a result.
9303
It is possible to reuse this new record as the result candidate for the
9304
next call to next_min(), and to save one lookup in the next call. For
9305
this add a new member 'this->next_group_prefix'.
9309
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9310
key_restore(record, tmp_record, index_info, 0);
9312
else if (result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE)
9313
result= 0; /* There is a result in any case. */
9318
If the MIN attribute is non-nullable, this->record already contains the
9319
MIN key in the group, so just return.
9326
Retrieve the maximal key in the next group.
9329
QUICK_GROUP_MIN_MAX_SELECT::next_max()
9332
Lookup the maximal key of the group, and store it into this->record.
9336
HA_ERR_KEY_NOT_FOUND if no MAX key was found that fulfills all conditions.
9337
HA_ERR_END_OF_FILE - "" -
9338
other if some error occurred
9341
int QUICK_GROUP_MIN_MAX_SELECT::next_max()
9345
/* Get the last key in the (possibly extended) group. */
9346
if (min_max_ranges.elements > 0)
9347
result= next_max_in_range();
9349
result= file->index_read_map(record, group_prefix,
9350
make_prev_keypart_map(real_key_parts),
9351
HA_READ_PREFIX_LAST);
9357
Determine the prefix of the next group.
9360
QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9363
Determine the prefix of the next group that satisfies the query conditions.
9364
If there is a range condition referencing the group attributes, use a
9365
QUICK_RANGE_SELECT object to retrieve the *first* key that satisfies the
9366
condition. If there is a key infix of constants, append this infix
9367
immediately after the group attributes. The possibly extended prefix is
9368
stored in this->group_prefix. The first key of the found group is stored in
9369
this->record, on which relies this->next_min().
9373
HA_ERR_KEY_NOT_FOUND if there is no key with the formed prefix
9374
HA_ERR_END_OF_FILE if there are no more keys
9375
other if some error occurred
9377
int QUICK_GROUP_MIN_MAX_SELECT::next_prefix()
9381
if (quick_prefix_select)
9383
unsigned char *cur_prefix= seen_first_key ? group_prefix : NULL;
9384
if ((result= quick_prefix_select->get_next_prefix(group_prefix_len,
9385
make_prev_keypart_map(group_key_parts), cur_prefix)))
9387
seen_first_key= true;
9391
if (!seen_first_key)
9393
result= file->index_first(record);
9396
seen_first_key= true;
9400
/* Load the first key in this group into record. */
9401
result= file->index_read_map(record, group_prefix,
9402
make_prev_keypart_map(group_key_parts),
9409
/* Save the prefix of this group for subsequent calls. */
9410
key_copy(group_prefix, record, index_info, group_prefix_len);
9411
/* Append key_infix to group_prefix. */
9412
if (key_infix_len > 0)
9413
memcpy(group_prefix + group_prefix_len,
9414
key_infix, key_infix_len);
9421
Find the minimal key in a group that satisfies some range conditions for the
9422
min/max argument field.
9425
QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9428
Given the sequence of ranges min_max_ranges, find the minimal key that is
9429
in the left-most possible range. If there is no such key, then the current
9430
group does not have a MIN key that satisfies the WHERE clause. If a key is
9431
found, its value is stored in this->record.
9435
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9437
HA_ERR_END_OF_FILE - "" -
9441
int QUICK_GROUP_MIN_MAX_SELECT::next_min_in_range()
9443
ha_rkey_function find_flag;
9444
key_part_map keypart_map;
9445
QUICK_RANGE *cur_range;
9446
bool found_null= false;
9447
int result= HA_ERR_KEY_NOT_FOUND;
9449
assert(min_max_ranges.elements > 0);
9451
for (uint32_t range_idx= 0; range_idx < min_max_ranges.elements; range_idx++)
9452
{ /* Search from the left-most range to the right. */
9453
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx);
9456
If the current value for the min/max argument is bigger than the right
9457
boundary of cur_range, there is no need to check this range.
9459
if (range_idx != 0 && !(cur_range->flag & NO_MAX_RANGE) &&
9460
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->max_key,
9461
min_max_arg_len) == 1))
9464
if (cur_range->flag & NO_MIN_RANGE)
9466
keypart_map= make_prev_keypart_map(real_key_parts);
9467
find_flag= HA_READ_KEY_EXACT;
9471
/* Extend the search key with the lower boundary for this range. */
9472
memcpy(group_prefix + real_prefix_len, cur_range->min_key,
9473
cur_range->min_length);
9474
keypart_map= make_keypart_map(real_key_parts);
9475
find_flag= (cur_range->flag & (EQ_RANGE | NULL_RANGE)) ?
9476
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MIN) ?
9477
HA_READ_AFTER_KEY : HA_READ_KEY_OR_NEXT;
9480
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9483
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9484
(cur_range->flag & (EQ_RANGE | NULL_RANGE)))
9485
continue; /* Check the next range. */
9488
In all other cases (HA_ERR_*, HA_READ_KEY_EXACT with NO_MIN_RANGE,
9489
HA_READ_AFTER_KEY, HA_READ_KEY_OR_NEXT) if the lookup failed for this
9490
range, it can't succeed for any other subsequent range.
9495
/* A key was found. */
9496
if (cur_range->flag & EQ_RANGE)
9497
break; /* No need to perform the checks below for equal keys. */
9499
if (cur_range->flag & NULL_RANGE)
9502
Remember this key, and continue looking for a non-NULL key that
9503
satisfies some other condition.
9505
memcpy(tmp_record, record, head->s->rec_buff_length);
9510
/* Check if record belongs to the current group. */
9511
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9513
result= HA_ERR_KEY_NOT_FOUND;
9517
/* If there is an upper limit, check if the found key is in the range. */
9518
if ( !(cur_range->flag & NO_MAX_RANGE) )
9520
/* Compose the MAX key for the range. */
9521
unsigned char *max_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9522
memcpy(max_key, group_prefix, real_prefix_len);
9523
memcpy(max_key + real_prefix_len, cur_range->max_key,
9524
cur_range->max_length);
9525
/* Compare the found key with max_key. */
9526
int cmp_res= key_cmp(index_info->key_part, max_key,
9527
real_prefix_len + min_max_arg_len);
9528
if ((!((cur_range->flag & NEAR_MAX) && (cmp_res == -1)) || (cmp_res <= 0)))
9530
result= HA_ERR_KEY_NOT_FOUND;
9534
/* If we got to this point, the current key qualifies as MIN. */
9535
assert(result == 0);
9539
If there was a key with NULL in the MIN/MAX field, and there was no other
9540
key without NULL from the same group that satisfies some other condition,
9541
then use the key with the NULL.
9543
if (found_null && result)
9545
memcpy(record, tmp_record, head->s->rec_buff_length);
9553
Find the maximal key in a group that satisfies some range conditions for the
9554
min/max argument field.
9557
QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9560
Given the sequence of ranges min_max_ranges, find the maximal key that is
9561
in the right-most possible range. If there is no such key, then the current
9562
group does not have a MAX key that satisfies the WHERE clause. If a key is
9563
found, its value is stored in this->record.
9567
HA_ERR_KEY_NOT_FOUND if there is no key with the given prefix in any of
9569
HA_ERR_END_OF_FILE - "" -
9573
int QUICK_GROUP_MIN_MAX_SELECT::next_max_in_range()
9575
ha_rkey_function find_flag;
9576
key_part_map keypart_map;
9577
QUICK_RANGE *cur_range;
9580
assert(min_max_ranges.elements > 0);
9582
for (uint32_t range_idx= min_max_ranges.elements; range_idx > 0; range_idx--)
9583
{ /* Search from the right-most range to the left. */
9584
get_dynamic(&min_max_ranges, (unsigned char*)&cur_range, range_idx - 1);
9587
If the current value for the min/max argument is smaller than the left
9588
boundary of cur_range, there is no need to check this range.
9590
if (range_idx != min_max_ranges.elements &&
9591
!(cur_range->flag & NO_MIN_RANGE) &&
9592
(key_cmp(min_max_arg_part, (const unsigned char*) cur_range->min_key,
9593
min_max_arg_len) == -1))
9596
if (cur_range->flag & NO_MAX_RANGE)
9598
keypart_map= make_prev_keypart_map(real_key_parts);
9599
find_flag= HA_READ_PREFIX_LAST;
9603
/* Extend the search key with the upper boundary for this range. */
9604
memcpy(group_prefix + real_prefix_len, cur_range->max_key,
9605
cur_range->max_length);
9606
keypart_map= make_keypart_map(real_key_parts);
9607
find_flag= (cur_range->flag & EQ_RANGE) ?
9608
HA_READ_KEY_EXACT : (cur_range->flag & NEAR_MAX) ?
9609
HA_READ_BEFORE_KEY : HA_READ_PREFIX_LAST_OR_PREV;
9612
result= file->index_read_map(record, group_prefix, keypart_map, find_flag);
9616
if ((result == HA_ERR_KEY_NOT_FOUND || result == HA_ERR_END_OF_FILE) &&
9617
(cur_range->flag & EQ_RANGE))
9618
continue; /* Check the next range. */
9621
In no key was found with this upper bound, there certainly are no keys
9622
in the ranges to the left.
9626
/* A key was found. */
9627
if (cur_range->flag & EQ_RANGE)
9628
return 0; /* No need to perform the checks below for equal keys. */
9630
/* Check if record belongs to the current group. */
9631
if (key_cmp(index_info->key_part, group_prefix, real_prefix_len))
9632
continue; // Row not found
9634
/* If there is a lower limit, check if the found key is in the range. */
9635
if ( !(cur_range->flag & NO_MIN_RANGE) )
9637
/* Compose the MIN key for the range. */
9638
unsigned char *min_key= (unsigned char*) my_alloca(real_prefix_len + min_max_arg_len);
9639
memcpy(min_key, group_prefix, real_prefix_len);
9640
memcpy(min_key + real_prefix_len, cur_range->min_key,
9641
cur_range->min_length);
9642
/* Compare the found key with min_key. */
9643
int cmp_res= key_cmp(index_info->key_part, min_key,
9644
real_prefix_len + min_max_arg_len);
9645
if ((!((cur_range->flag & NEAR_MIN) && (cmp_res == 1)) ||
9649
/* If we got to this point, the current key qualifies as MAX. */
9652
return HA_ERR_KEY_NOT_FOUND;
9657
Update all MIN function results with the newly found value.
9660
QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9663
The method iterates through all MIN functions and updates the result value
9664
of each function by calling Item_sum::reset(), which in turn picks the new
9665
result value from this->head->record[0], previously updated by
9666
next_min(). The updated value is stored in a member variable of each of the
9667
Item_sum objects, depending on the value type.
9670
The update must be done separately for MIN and MAX, immediately after
9671
next_min() was called and before next_max() is called, because both MIN and
9672
MAX take their result value from the same buffer this->head->record[0]
9673
(i.e. this->record).
9679
void QUICK_GROUP_MIN_MAX_SELECT::update_min_result()
9683
min_functions_it->rewind();
9684
while ((min_func= (*min_functions_it)++))
9690
Update all MAX function results with the newly found value.
9693
QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9696
The method iterates through all MAX functions and updates the result value
9697
of each function by calling Item_sum::reset(), which in turn picks the new
9698
result value from this->head->record[0], previously updated by
9699
next_max(). The updated value is stored in a member variable of each of the
9700
Item_sum objects, depending on the value type.
9703
The update must be done separately for MIN and MAX, immediately after
9704
next_max() was called, because both MIN and MAX take their result value
9705
from the same buffer this->head->record[0] (i.e. this->record).
9711
void QUICK_GROUP_MIN_MAX_SELECT::update_max_result()
9715
max_functions_it->rewind();
9716
while ((max_func= (*max_functions_it)++))
9722
Append comma-separated list of keys this quick select uses to key_names;
9723
append comma-separated list of corresponding used lengths to used_lengths.
9726
QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths()
9727
key_names [out] Names of used indexes
9728
used_lengths [out] Corresponding lengths of the index names
9731
This method is used by select_describe to extract the names of the
9732
indexes used by a quick select.
9736
void QUICK_GROUP_MIN_MAX_SELECT::add_keys_and_lengths(String *key_names,
9737
String *used_lengths)
9741
key_names->append(index_info->name);
9742
length= int64_t2str(max_used_key_length, buf, 10) - buf;
9743
used_lengths->append(buf, length);
9746
static void print_sel_tree(PARAM *param, SEL_TREE *tree, key_map *tree_map,
9747
const char *msg __attribute__((unused)))
9749
SEL_ARG **key,**end;
9753
String tmp(buff,sizeof(buff),&my_charset_bin);
9755
for (idx= 0,key=tree->keys, end=key+param->keys ;
9759
if (tree_map->is_set(idx))
9761
uint32_t keynr= param->real_keynr[idx];
9764
tmp.append(param->table->key_info[keynr].name);
9768
tmp.append(STRING_WITH_LEN("(empty)"));
9774
static void print_ror_scans_arr(Table *table,
9775
const char *msg __attribute__((unused)),
9776
struct st_ror_scan_info **start,
9777
struct st_ror_scan_info **end)
9780
String tmp(buff,sizeof(buff),&my_charset_bin);
9782
for (;start != end; start++)
9786
tmp.append(table->key_info[(*start)->keynr].name);
9789
tmp.append(STRING_WITH_LEN("(empty)"));
9793
/*****************************************************************************
9794
** Instantiate templates
9795
*****************************************************************************/
9797
#ifdef HAVE_EXPLICIT_TEMPLATE_INSTANTIATION
9798
template class List<QUICK_RANGE>;
9799
template class List_iterator<QUICK_RANGE>;
added
removed
drizzled/opt_range.cc
