1/*
2 Copyright (c) 2000, 2010, Oracle and/or its affiliates.
3
4 This program is free software; you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation; version 2 of the License.
7
8 This program is distributed in the hope that it will be useful,
9 but WITHOUT ANY WARRANTY; without even the implied warranty of
10 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 GNU General Public License for more details.
12
13 You should have received a copy of the GNU General Public License
14 along with this program; if not, write to the Free Software
15 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA */
16
17
18/* classes to use when handling where clause */
19
20#ifndef _opt_range_h
21#define _opt_range_h
22
23#ifdef USE_PRAGMA_INTERFACE
24#pragma interface /* gcc class implementation */
25#endif
26
27#include "records.h" /* READ_RECORD */
28#include "queues.h" /* QUEUE */
29#include "filesort.h" /* SORT_INFO */
30
31/*
32 It is necessary to include set_var.h instead of item.h because there
33 are dependencies on include order for set_var.h and item.h. This
34 will be resolved later.
35*/
36#include "sql_class.h" // set_var.h: THD
37#include "set_var.h" /* Item */
38
39class JOIN;
40class Item_sum;
41
42struct KEY_PART {
43 uint16 key,part;
44 /* See KEY_PART_INFO for meaning of the next two: */
45 uint16 store_length, length;
46 uint8 null_bit;
47 /*
48 Keypart flags (0 when this structure is used by partition pruning code
49 for fake partitioning index description)
50 */
51 uint8 flag;
52 Field *field;
53 Field::imagetype image_type;
54};
55
56
57class RANGE_OPT_PARAM;
58/*
59 A construction block of the SEL_ARG-graph.
60
61 The following description only covers graphs of SEL_ARG objects with
62 sel_arg->type==KEY_RANGE:
63
64 One SEL_ARG object represents an "elementary interval" in form
65
66 min_value <=? table.keypartX <=? max_value
67
68 The interval is a non-empty interval of any kind: with[out] minimum/maximum
69 bound, [half]open/closed, single-point interval, etc.
70
71 1. SEL_ARG GRAPH STRUCTURE
72
73 SEL_ARG objects are linked together in a graph. The meaning of the graph
74 is better demostrated by an example:
75
76 tree->keys[i]
77 |
78 | $ $
79 | part=1 $ part=2 $ part=3
80 | $ $
81 | +-------+ $ +-------+ $ +--------+
82 | | kp1<1 |--$-->| kp2=5 |--$-->| kp3=10 |
83 | +-------+ $ +-------+ $ +--------+
84 | | $ $ |
85 | | $ $ +--------+
86 | | $ $ | kp3=12 |
87 | | $ $ +--------+
88 | +-------+ $ $
89 \->| kp1=2 |--$--------------$-+
90 +-------+ $ $ | +--------+
91 | $ $ ==>| kp3=11 |
92 +-------+ $ $ | +--------+
93 | kp1=3 |--$--------------$-+ |
94 +-------+ $ $ +--------+
95 | $ $ | kp3=14 |
96 ... $ $ +--------+
97
98 The entire graph is partitioned into "interval lists".
99
100 An interval list is a sequence of ordered disjoint intervals over the same
101 key part. SEL_ARG are linked via "next" and "prev" pointers. Additionally,
102 all intervals in the list form an RB-tree, linked via left/right/parent
103 pointers. The RB-tree root SEL_ARG object will be further called "root of the
104 interval list".
105
106 In the example pic, there are 4 interval lists:
107 "kp<1 OR kp1=2 OR kp1=3", "kp2=5", "kp3=10 OR kp3=12", "kp3=11 OR kp3=13".
108 The vertical lines represent SEL_ARG::next/prev pointers.
109
110 In an interval list, each member X may have SEL_ARG::next_key_part pointer
111 pointing to the root of another interval list Y. The pointed interval list
112 must cover a key part with greater number (i.e. Y->part > X->part).
113
114 In the example pic, the next_key_part pointers are represented by
115 horisontal lines.
116
117 2. SEL_ARG GRAPH SEMANTICS
118
119 It represents a condition in a special form (we don't have a name for it ATM)
120 The SEL_ARG::next/prev is "OR", and next_key_part is "AND".
121
122 For example, the picture represents the condition in form:
123 (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
124 (kp1=2 AND (kp3=11 OR kp3=14)) OR
125 (kp1=3 AND (kp3=11 OR kp3=14))
126
127
128 3. SEL_ARG GRAPH USE
129
130 Use get_mm_tree() to construct SEL_ARG graph from WHERE condition.
131 Then walk the SEL_ARG graph and get a list of dijsoint ordered key
132 intervals (i.e. intervals in form
133
134 (constA1, .., const1_K) < (keypart1,.., keypartK) < (constB1, .., constB_K)
135
136 Those intervals can be used to access the index. The uses are in:
137 - check_quick_select() - Walk the SEL_ARG graph and find an estimate of
138 how many table records are contained within all
139 intervals.
140 - get_quick_select() - Walk the SEL_ARG, materialize the key intervals,
141 and create QUICK_RANGE_SELECT object that will
142 read records within these intervals.
143
144 4. SPACE COMPLEXITY NOTES
145
146 SEL_ARG graph is a representation of an ordered disjoint sequence of
147 intervals over the ordered set of index tuple values.
148
149 For multi-part keys, one can construct a WHERE expression such that its
150 list of intervals will be of combinatorial size. Here is an example:
151
152 (keypart1 IN (1,2, ..., n1)) AND
153 (keypart2 IN (1,2, ..., n2)) AND
154 (keypart3 IN (1,2, ..., n3))
155
156 For this WHERE clause the list of intervals will have n1*n2*n3 intervals
157 of form
158
159 (keypart1, keypart2, keypart3) = (k1, k2, k3), where 1 <= k{i} <= n{i}
160
161 SEL_ARG graph structure aims to reduce the amount of required space by
162 "sharing" the elementary intervals when possible (the pic at the
163 beginning of this comment has examples of such sharing). The sharing may
164 prevent combinatorial blowup:
165
166 There are WHERE clauses that have combinatorial-size interval lists but
167 will be represented by a compact SEL_ARG graph.
168 Example:
169 (keypartN IN (1,2, ..., n1)) AND
170 ...
171 (keypart2 IN (1,2, ..., n2)) AND
172 (keypart1 IN (1,2, ..., n3))
173
174 but not in all cases:
175
176 - There are WHERE clauses that do have a compact SEL_ARG-graph
177 representation but get_mm_tree() and its callees will construct a
178 graph of combinatorial size.
179 Example:
180 (keypart1 IN (1,2, ..., n1)) AND
181 (keypart2 IN (1,2, ..., n2)) AND
182 ...
183 (keypartN IN (1,2, ..., n3))
184
185 - There are WHERE clauses for which the minimal possible SEL_ARG graph
186 representation will have combinatorial size.
187 Example:
188 By induction: Let's take any interval on some keypart in the middle:
189
190 kp15=c0
191
192 Then let's AND it with this interval 'structure' from preceding and
193 following keyparts:
194
195 (kp14=c1 AND kp16=c3) OR keypart14=c2) (*)
196
197 We will obtain this SEL_ARG graph:
198
199 kp14 $ kp15 $ kp16
200 $ $
201 +---------+ $ +---------+ $ +---------+
202 | kp14=c1 |--$-->| kp15=c0 |--$-->| kp16=c3 |
203 +---------+ $ +---------+ $ +---------+
204 | $ $
205 +---------+ $ +---------+ $
206 | kp14=c2 |--$-->| kp15=c0 | $
207 +---------+ $ +---------+ $
208 $ $
209
210 Note that we had to duplicate "kp15=c0" and there was no way to avoid
211 that.
212 The induction step: AND the obtained expression with another "wrapping"
213 expression like (*).
214 When the process ends because of the limit on max. number of keyparts
215 we'll have:
216
217 WHERE clause length is O(3*#max_keyparts)
218 SEL_ARG graph size is O(2^(#max_keyparts/2))
219
220 (it is also possible to construct a case where instead of 2 in 2^n we
221 have a bigger constant, e.g. 4, and get a graph with 4^(31/2)= 2^31
222 nodes)
223
224 We avoid consuming too much memory by setting a limit on the number of
225 SEL_ARG object we can construct during one range analysis invocation.
226*/
227
228class SEL_ARG :public Sql_alloc
229{
230 static int sel_cmp(Field *field, uchar *a, uchar *b, uint8 a_flag,
231 uint8 b_flag);
232public:
233 uint8 min_flag,max_flag,maybe_flag;
234 uint8 part; // Which key part
235 uint8 maybe_null;
236 /*
237 The ordinal number the least significant component encountered in
238 the ranges of the SEL_ARG tree (the first component has number 1)
239 */
240 uint16 max_part_no;
241 /*
242 Number of children of this element in the RB-tree, plus 1 for this
243 element itself.
244 */
245 uint16 elements;
246 /*
247 Valid only for elements which are RB-tree roots: Number of times this
248 RB-tree is referred to (it is referred by SEL_ARG::next_key_part or by
249 SEL_TREE::keys[i] or by a temporary SEL_ARG* variable)
250 */
251 ulong use_count;
252
253 Field *field;
254 uchar *min_value,*max_value; // Pointer to range
255
256 /*
257 eq_tree() requires that left == right == 0 if the type is MAYBE_KEY.
258 */
259 SEL_ARG *left,*right; /* R-B tree children */
260 SEL_ARG *next,*prev; /* Links for bi-directional interval list */
261 SEL_ARG *parent; /* R-B tree parent */
262 SEL_ARG *next_key_part;
263 enum leaf_color { BLACK,RED } color;
264 enum Type { IMPOSSIBLE, MAYBE, MAYBE_KEY, KEY_RANGE } type;
265
266 enum { MAX_SEL_ARGS = 16000 };
267
268 SEL_ARG() {}
269 SEL_ARG(SEL_ARG &);
270 SEL_ARG(Field *,const uchar *, const uchar *);
271 SEL_ARG(Field *field, uint8 part, uchar *min_value, uchar *max_value,
272 uint8 min_flag, uint8 max_flag, uint8 maybe_flag);
273 SEL_ARG(enum Type type_arg)
274 :min_flag(0), max_part_no(0) /* first key part means 1. 0 mean 'no parts'*/,
275 elements(1),use_count(1),left(0),right(0),
276 next_key_part(0), color(BLACK), type(type_arg)
277 {}
278 /**
279 returns true if a range predicate is equal. Use all_same()
280 to check for equality of all the predicates on this keypart.
281 */
282 inline bool is_same(const SEL_ARG *arg) const
283 {
284 if (type != arg->type || part != arg->part)
285 return false;
286 if (type != KEY_RANGE)
287 return true;
288 return cmp_min_to_min(arg) == 0 && cmp_max_to_max(arg) == 0;
289 }
290 /**
291 returns true if all the predicates in the keypart tree are equal
292 */
293 bool all_same(const SEL_ARG *arg) const
294 {
295 if (type != arg->type || part != arg->part)
296 return false;
297 if (type != KEY_RANGE)
298 return true;
299 if (arg == this)
300 return true;
301 const SEL_ARG *cmp_arg= arg->first();
302 const SEL_ARG *cur_arg= first();
303 for (; cur_arg && cmp_arg && cur_arg->is_same(cmp_arg);
304 cur_arg= cur_arg->next, cmp_arg= cmp_arg->next) ;
305 if (cur_arg || cmp_arg)
306 return false;
307 return true;
308 }
309 inline void merge_flags(SEL_ARG *arg) { maybe_flag|=arg->maybe_flag; }
310 inline void maybe_smaller() { maybe_flag=1; }
311 /* Return true iff it's a single-point null interval */
312 inline bool is_null_interval() { return maybe_null && max_value[0] == 1; }
313 inline int cmp_min_to_min(const SEL_ARG* arg) const
314 {
315 return sel_cmp(field,min_value, arg->min_value, min_flag, arg->min_flag);
316 }
317 inline int cmp_min_to_max(const SEL_ARG* arg) const
318 {
319 return sel_cmp(field,min_value, arg->max_value, min_flag, arg->max_flag);
320 }
321 inline int cmp_max_to_max(const SEL_ARG* arg) const
322 {
323 return sel_cmp(field,max_value, arg->max_value, max_flag, arg->max_flag);
324 }
325 inline int cmp_max_to_min(const SEL_ARG* arg) const
326 {
327 return sel_cmp(field,max_value, arg->min_value, max_flag, arg->min_flag);
328 }
329 SEL_ARG *clone_and(THD *thd, SEL_ARG* arg)
330 { // Get overlapping range
331 uchar *new_min,*new_max;
332 uint8 flag_min,flag_max;
333 if (cmp_min_to_min(arg) >= 0)
334 {
335 new_min=min_value; flag_min=min_flag;
336 }
337 else
338 {
339 new_min=arg->min_value; flag_min=arg->min_flag; /* purecov: deadcode */
340 }
341 if (cmp_max_to_max(arg) <= 0)
342 {
343 new_max=max_value; flag_max=max_flag;
344 }
345 else
346 {
347 new_max=arg->max_value; flag_max=arg->max_flag;
348 }
349 return new (thd->mem_root) SEL_ARG(field, part, new_min, new_max, flag_min,
350 flag_max,
351 MY_TEST(maybe_flag && arg->maybe_flag));
352 }
353 SEL_ARG *clone_first(SEL_ARG *arg)
354 { // min <= X < arg->min
355 return new SEL_ARG(field,part, min_value, arg->min_value,
356 min_flag, arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX,
357 maybe_flag | arg->maybe_flag);
358 }
359 SEL_ARG *clone_last(SEL_ARG *arg)
360 { // min <= X <= key_max
361 return new SEL_ARG(field, part, min_value, arg->max_value,
362 min_flag, arg->max_flag, maybe_flag | arg->maybe_flag);
363 }
364 SEL_ARG *clone(RANGE_OPT_PARAM *param, SEL_ARG *new_parent, SEL_ARG **next);
365
366 bool copy_min(SEL_ARG* arg)
367 { // Get overlapping range
368 if (cmp_min_to_min(arg) > 0)
369 {
370 min_value=arg->min_value; min_flag=arg->min_flag;
371 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
372 (NO_MAX_RANGE | NO_MIN_RANGE))
373 return 1; // Full range
374 }
375 maybe_flag|=arg->maybe_flag;
376 return 0;
377 }
378 bool copy_max(SEL_ARG* arg)
379 { // Get overlapping range
380 if (cmp_max_to_max(arg) <= 0)
381 {
382 max_value=arg->max_value; max_flag=arg->max_flag;
383 if ((max_flag & (NO_MAX_RANGE | NO_MIN_RANGE)) ==
384 (NO_MAX_RANGE | NO_MIN_RANGE))
385 return 1; // Full range
386 }
387 maybe_flag|=arg->maybe_flag;
388 return 0;
389 }
390
391 void copy_min_to_min(SEL_ARG *arg)
392 {
393 min_value=arg->min_value; min_flag=arg->min_flag;
394 }
395 void copy_min_to_max(SEL_ARG *arg)
396 {
397 max_value=arg->min_value;
398 max_flag=arg->min_flag & NEAR_MIN ? 0 : NEAR_MAX;
399 }
400 void copy_max_to_min(SEL_ARG *arg)
401 {
402 min_value=arg->max_value;
403 min_flag=arg->max_flag & NEAR_MAX ? 0 : NEAR_MIN;
404 }
405 /* returns a number of keypart values (0 or 1) appended to the key buffer */
406 int store_min(uint length, uchar **min_key,uint min_key_flag)
407 {
408 /* "(kp1 > c1) AND (kp2 OP c2) AND ..." -> (kp1 > c1) */
409 if ((min_flag & GEOM_FLAG) ||
410 (!(min_flag & NO_MIN_RANGE) &&
411 !(min_key_flag & (NO_MIN_RANGE | NEAR_MIN))))
412 {
413 if (maybe_null && *min_value)
414 {
415 **min_key=1;
416 bzero(*min_key+1,length-1);
417 }
418 else
419 memcpy(*min_key,min_value,length);
420 (*min_key)+= length;
421 return 1;
422 }
423 return 0;
424 }
425 /* returns a number of keypart values (0 or 1) appended to the key buffer */
426 int store_max(uint length, uchar **max_key, uint max_key_flag)
427 {
428 if (!(max_flag & NO_MAX_RANGE) &&
429 !(max_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
430 {
431 if (maybe_null && *max_value)
432 {
433 **max_key=1;
434 bzero(*max_key+1,length-1);
435 }
436 else
437 memcpy(*max_key,max_value,length);
438 (*max_key)+= length;
439 return 1;
440 }
441 return 0;
442 }
443
444 /*
445 Returns a number of keypart values appended to the key buffer
446 for min key and max key. This function is used by both Range
447 Analysis and Partition pruning. For partition pruning we have
448 to ensure that we don't store also subpartition fields. Thus
449 we have to stop at the last partition part and not step into
450 the subpartition fields. For Range Analysis we set last_part
451 to MAX_KEY which we should never reach.
452 */
453 int store_min_key(KEY_PART *key,
454 uchar **range_key,
455 uint *range_key_flag,
456 uint last_part)
457 {
458 SEL_ARG *key_tree= first();
459 uint res= key_tree->store_min(key[key_tree->part].store_length,
460 range_key, *range_key_flag);
461 *range_key_flag|= key_tree->min_flag;
462 if (key_tree->next_key_part &&
463 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
464 key_tree->part != last_part &&
465 key_tree->next_key_part->part == key_tree->part+1 &&
466 !(*range_key_flag & (NO_MIN_RANGE | NEAR_MIN)))
467 res+= key_tree->next_key_part->store_min_key(key,
468 range_key,
469 range_key_flag,
470 last_part);
471 return res;
472 }
473
474 /* returns a number of keypart values appended to the key buffer */
475 int store_max_key(KEY_PART *key,
476 uchar **range_key,
477 uint *range_key_flag,
478 uint last_part)
479 {
480 SEL_ARG *key_tree= last();
481 uint res=key_tree->store_max(key[key_tree->part].store_length,
482 range_key, *range_key_flag);
483 (*range_key_flag)|= key_tree->max_flag;
484 if (key_tree->next_key_part &&
485 key_tree->next_key_part->type == SEL_ARG::KEY_RANGE &&
486 key_tree->part != last_part &&
487 key_tree->next_key_part->part == key_tree->part+1 &&
488 !(*range_key_flag & (NO_MAX_RANGE | NEAR_MAX)))
489 res+= key_tree->next_key_part->store_max_key(key,
490 range_key,
491 range_key_flag,
492 last_part);
493 return res;
494 }
495
496 SEL_ARG *insert(SEL_ARG *key);
497 SEL_ARG *tree_delete(SEL_ARG *key);
498 SEL_ARG *find_range(SEL_ARG *key);
499 SEL_ARG *rb_insert(SEL_ARG *leaf);
500 friend SEL_ARG *rb_delete_fixup(SEL_ARG *root,SEL_ARG *key, SEL_ARG *par);
501#ifdef EXTRA_DEBUG
502 friend int test_rb_tree(SEL_ARG *element,SEL_ARG *parent);
503 void test_use_count(SEL_ARG *root);
504#endif
505 SEL_ARG *first();
506 const SEL_ARG *first() const;
507 SEL_ARG *last();
508 void make_root();
509 inline bool simple_key()
510 {
511 return !next_key_part && elements == 1;
512 }
513 void increment_use_count(long count)
514 {
515 if (next_key_part)
516 {
517 next_key_part->use_count+=count;
518 count*= (next_key_part->use_count-count);
519 for (SEL_ARG *pos=next_key_part->first(); pos ; pos=pos->next)
520 if (pos->next_key_part)
521 pos->increment_use_count(count);
522 }
523 }
524 void incr_refs()
525 {
526 increment_use_count(1);
527 use_count++;
528 }
529 void incr_refs_all()
530 {
531 for (SEL_ARG *pos=first(); pos ; pos=pos->next)
532 {
533 pos->increment_use_count(1);
534 }
535 use_count++;
536 }
537 void free_tree()
538 {
539 for (SEL_ARG *pos=first(); pos ; pos=pos->next)
540 if (pos->next_key_part)
541 {
542 pos->next_key_part->use_count--;
543 pos->next_key_part->free_tree();
544 }
545 }
546
547 inline SEL_ARG **parent_ptr()
548 {
549 return parent->left == this ? &parent->left : &parent->right;
550 }
551
552
553 /*
554 Check if this SEL_ARG object represents a single-point interval
555
556 SYNOPSIS
557 is_singlepoint()
558
559 DESCRIPTION
560 Check if this SEL_ARG object (not tree) represents a single-point
561 interval, i.e. if it represents a "keypart = const" or
562 "keypart IS NULL".
563
564 RETURN
565 TRUE This SEL_ARG object represents a singlepoint interval
566 FALSE Otherwise
567 */
568
569 bool is_singlepoint()
570 {
571 /*
572 Check for NEAR_MIN ("strictly less") and NO_MIN_RANGE (-inf < field)
573 flags, and the same for right edge.
574 */
575 if (min_flag || max_flag)
576 return FALSE;
577 uchar *min_val= min_value;
578 uchar *max_val= max_value;
579
580 if (maybe_null)
581 {
582 /* First byte is a NULL value indicator */
583 if (*min_val != *max_val)
584 return FALSE;
585
586 if (*min_val)
587 return TRUE; /* This "x IS NULL" */
588 min_val++;
589 max_val++;
590 }
591 return !field->key_cmp(min_val, max_val);
592 }
593 SEL_ARG *clone_tree(RANGE_OPT_PARAM *param);
594};
595
596
597class SEL_ARG_IMPOSSIBLE: public SEL_ARG
598{
599public:
600 SEL_ARG_IMPOSSIBLE(Field *field)
601 :SEL_ARG(field, 0, 0)
602 {
603 type= SEL_ARG::IMPOSSIBLE;
604 }
605};
606
607
608class RANGE_OPT_PARAM
609{
610public:
611 THD *thd; /* Current thread handle */
612 TABLE *table; /* Table being analyzed */
613 table_map prev_tables;
614 table_map read_tables;
615 table_map current_table; /* Bit of the table being analyzed */
616
617 /* Array of parts of all keys for which range analysis is performed */
618 KEY_PART *key_parts;
619 KEY_PART *key_parts_end;
620 MEM_ROOT *mem_root; /* Memory that will be freed when range analysis completes */
621 MEM_ROOT *old_root; /* Memory that will last until the query end */
622 /*
623 Number of indexes used in range analysis (In SEL_TREE::keys only first
624 #keys elements are not empty)
625 */
626 uint keys;
627
628 /*
629 If true, the index descriptions describe real indexes (and it is ok to
630 call field->optimize_range(real_keynr[...], ...).
631 Otherwise index description describes fake indexes.
632 */
633 bool using_real_indexes;
634
635 /*
636 Aggressively remove "scans" that do not have conditions on first
637 keyparts. Such scans are usable when doing partition pruning but not
638 regular range optimization.
639 */
640 bool remove_jump_scans;
641
642 /*
643 TRUE <=> Range analyzer should remove parts of condition that are found
644 to be always FALSE.
645 */
646 bool remove_false_where_parts;
647
648 /*
649 used_key_no -> table_key_no translation table. Only makes sense if
650 using_real_indexes==TRUE
651 */
652 uint real_keynr[MAX_KEY];
653
654 /*
655 Used to store 'current key tuples', in both range analysis and
656 partitioning (list) analysis
657 */
658 uchar *min_key;
659 uchar *max_key;
660
661 /* Number of SEL_ARG objects allocated by SEL_ARG::clone_tree operations */
662 uint alloced_sel_args;
663
664 bool force_default_mrr;
665 KEY_PART *key[MAX_KEY]; /* First key parts of keys used in the query */
666
667 bool statement_should_be_aborted() const
668 {
669 return
670 thd->is_fatal_error ||
671 thd->is_error() ||
672 alloced_sel_args > SEL_ARG::MAX_SEL_ARGS;
673 }
674};
675
676
677class Explain_quick_select;
678/*
679 A "MIN_TUPLE < tbl.key_tuple < MAX_TUPLE" interval.
680
681 One of endpoints may be absent. 'flags' member has flags which tell whether
682 the endpoints are '<' or '<='.
683*/
684class QUICK_RANGE :public Sql_alloc {
685 public:
686 uchar *min_key,*max_key;
687 uint16 min_length,max_length,flag;
688 key_part_map min_keypart_map, // bitmap of used keyparts in min_key
689 max_keypart_map; // bitmap of used keyparts in max_key
690#ifdef HAVE_valgrind
691 uint16 dummy; /* Avoid warnings on 'flag' */
692#endif
693 QUICK_RANGE(); /* Full range */
694 QUICK_RANGE(THD *thd, const uchar *min_key_arg, uint min_length_arg,
695 key_part_map min_keypart_map_arg,
696 const uchar *max_key_arg, uint max_length_arg,
697 key_part_map max_keypart_map_arg,
698 uint flag_arg)
699 : min_key((uchar*) thd->memdup(min_key_arg, min_length_arg + 1)),
700 max_key((uchar*) thd->memdup(max_key_arg, max_length_arg + 1)),
701 min_length((uint16) min_length_arg),
702 max_length((uint16) max_length_arg),
703 flag((uint16) flag_arg),
704 min_keypart_map(min_keypart_map_arg),
705 max_keypart_map(max_keypart_map_arg)
706 {
707#ifdef HAVE_valgrind
708 dummy=0;
709#endif
710 }
711
712 /**
713 Initalizes a key_range object for communication with storage engine.
714
715 This function facilitates communication with the Storage Engine API by
716 translating the minimum endpoint of the interval represented by this
717 QUICK_RANGE into an index range endpoint specifier for the engine.
718
719 @param Pointer to an uninitialized key_range C struct.
720
721 @param prefix_length The length of the search key prefix to be used for
722 lookup.
723
724 @param keypart_map A set (bitmap) of keyparts to be used.
725 */
726 void make_min_endpoint(key_range *kr, uint prefix_length,
727 key_part_map keypart_map) {
728 make_min_endpoint(kr);
729 kr->length= MY_MIN(kr->length, prefix_length);
730 kr->keypart_map&= keypart_map;
731 }
732
733 /**
734 Initalizes a key_range object for communication with storage engine.
735
736 This function facilitates communication with the Storage Engine API by
737 translating the minimum endpoint of the interval represented by this
738 QUICK_RANGE into an index range endpoint specifier for the engine.
739
740 @param Pointer to an uninitialized key_range C struct.
741 */
742 void make_min_endpoint(key_range *kr) {
743 kr->key= (const uchar*)min_key;
744 kr->length= min_length;
745 kr->keypart_map= min_keypart_map;
746 kr->flag= ((flag & NEAR_MIN) ? HA_READ_AFTER_KEY :
747 (flag & EQ_RANGE) ? HA_READ_KEY_EXACT : HA_READ_KEY_OR_NEXT);
748 }
749
750 /**
751 Initalizes a key_range object for communication with storage engine.
752
753 This function facilitates communication with the Storage Engine API by
754 translating the maximum endpoint of the interval represented by this
755 QUICK_RANGE into an index range endpoint specifier for the engine.
756
757 @param Pointer to an uninitialized key_range C struct.
758
759 @param prefix_length The length of the search key prefix to be used for
760 lookup.
761
762 @param keypart_map A set (bitmap) of keyparts to be used.
763 */
764 void make_max_endpoint(key_range *kr, uint prefix_length,
765 key_part_map keypart_map) {
766 make_max_endpoint(kr);
767 kr->length= MY_MIN(kr->length, prefix_length);
768 kr->keypart_map&= keypart_map;
769 }
770
771 /**
772 Initalizes a key_range object for communication with storage engine.
773
774 This function facilitates communication with the Storage Engine API by
775 translating the maximum endpoint of the interval represented by this
776 QUICK_RANGE into an index range endpoint specifier for the engine.
777
778 @param Pointer to an uninitialized key_range C struct.
779 */
780 void make_max_endpoint(key_range *kr) {
781 kr->key= (const uchar*)max_key;
782 kr->length= max_length;
783 kr->keypart_map= max_keypart_map;
784 /*
785 We use READ_AFTER_KEY here because if we are reading on a key
786 prefix we want to find all keys with this prefix
787 */
788 kr->flag= (flag & NEAR_MAX ? HA_READ_BEFORE_KEY : HA_READ_AFTER_KEY);
789 }
790};
791
792
793/*
794 Quick select interface.
795 This class is a parent for all QUICK_*_SELECT and FT_SELECT classes.
796
797 The usage scenario is as follows:
798 1. Create quick select
799 quick= new QUICK_XXX_SELECT(...);
800
801 2. Perform lightweight initialization. This can be done in 2 ways:
802 2.a: Regular initialization
803 if (quick->init())
804 {
805 //the only valid action after failed init() call is delete
806 delete quick;
807 }
808 2.b: Special initialization for quick selects merged by QUICK_ROR_*_SELECT
809 if (quick->init_ror_merged_scan())
810 delete quick;
811
812 3. Perform zero, one, or more scans.
813 while (...)
814 {
815 // initialize quick select for scan. This may allocate
816 // buffers and/or prefetch rows.
817 if (quick->reset())
818 {
819 //the only valid action after failed reset() call is delete
820 delete quick;
821 //abort query
822 }
823
824 // perform the scan
825 do
826 {
827 res= quick->get_next();
828 } while (res && ...)
829 }
830
831 4. Delete the select:
832 delete quick;
833
834 NOTE
835 quick select doesn't use Sql_alloc/MEM_ROOT allocation because "range
836 checked for each record" functionality may create/destroy
837 O(#records_in_some_table) quick selects during query execution.
838*/
839
840class QUICK_SELECT_I
841{
842public:
843 ha_rows records; /* estimate of # of records to be retrieved */
844 double read_time; /* time to perform this retrieval */
845 TABLE *head;
846 /*
847 Index this quick select uses, or MAX_KEY for quick selects
848 that use several indexes
849 */
850 uint index;
851
852 /*
853 Total length of first used_key_parts parts of the key.
854 Applicable if index!= MAX_KEY.
855 */
856 uint max_used_key_length;
857
858 /*
859 Max. number of (first) key parts this quick select uses for retrieval.
860 eg. for "(key1p1=c1 AND key1p2=c2) OR key1p1=c2" used_key_parts == 2.
861 Applicable if index!= MAX_KEY.
862
863 For QUICK_GROUP_MIN_MAX_SELECT it includes MIN/MAX argument keyparts.
864 */
865 uint used_key_parts;
866
867 QUICK_SELECT_I();
868 virtual ~QUICK_SELECT_I(){};
869
870 /*
871 Do post-constructor initialization.
872 SYNOPSIS
873 init()
874
875 init() performs initializations that should have been in constructor if
876 it was possible to return errors from constructors. The join optimizer may
877 create and then delete quick selects without retrieving any rows so init()
878 must not contain any IO or CPU intensive code.
879
880 If init() call fails the only valid action is to delete this quick select,
881 reset() and get_next() must not be called.
882
883 RETURN
884 0 OK
885 other Error code
886 */
887 virtual int init() = 0;
888
889 /*
890 Initialize quick select for row retrieval.
891 SYNOPSIS
892 reset()
893
894 reset() should be called when it is certain that row retrieval will be
895 necessary. This call may do heavyweight initialization like buffering first
896 N records etc. If reset() call fails get_next() must not be called.
897 Note that reset() may be called several times if
898 * the quick select is executed in a subselect
899 * a JOIN buffer is used
900
901 RETURN
902 0 OK
903 other Error code
904 */
905 virtual int reset(void) = 0;
906
907 virtual int get_next() = 0; /* get next record to retrieve */
908
909 /* Range end should be called when we have looped over the whole index */
910 virtual void range_end() {}
911
912 virtual bool reverse_sorted() = 0;
913 virtual bool unique_key_range() { return false; }
914
915 /*
916 Request that this quick select produces sorted output. Not all quick
917 selects can do it, the caller is responsible for calling this function
918 only for those quick selects that can.
919 */
920 virtual void need_sorted_output() = 0;
921 enum {
922 QS_TYPE_RANGE = 0,
923 QS_TYPE_INDEX_INTERSECT = 1,
924 QS_TYPE_INDEX_MERGE = 2,
925 QS_TYPE_RANGE_DESC = 3,
926 QS_TYPE_FULLTEXT = 4,
927 QS_TYPE_ROR_INTERSECT = 5,
928 QS_TYPE_ROR_UNION = 6,
929 QS_TYPE_GROUP_MIN_MAX = 7
930 };
931
932 /* Get type of this quick select - one of the QS_TYPE_* values */
933 virtual int get_type() = 0;
934
935 /*
936 Initialize this quick select as a merged scan inside a ROR-union or a ROR-
937 intersection scan. The caller must not additionally call init() if this
938 function is called.
939 SYNOPSIS
940 init_ror_merged_scan()
941 reuse_handler If true, the quick select may use table->handler,
942 otherwise it must create and use a separate handler
943 object.
944 RETURN
945 0 Ok
946 other Error
947 */
948 virtual int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc)
949 { DBUG_ASSERT(0); return 1; }
950
951 /*
952 Save ROWID of last retrieved row in file->ref. This used in ROR-merging.
953 */
954 virtual void save_last_pos(){};
955
956 void add_key_and_length(String *key_names,
957 String *used_lengths,
958 bool *first);
959
960 /*
961 Append comma-separated list of keys this quick select uses to key_names;
962 append comma-separated list of corresponding used lengths to used_lengths.
963 This is used by select_describe.
964 */
965 virtual void add_keys_and_lengths(String *key_names,
966 String *used_lengths)=0;
967
968 void add_key_name(String *str, bool *first);
969
970 /* Save information about quick select's query plan */
971 virtual Explain_quick_select* get_explain(MEM_ROOT *alloc)= 0;
972
973 /*
974 Return 1 if any index used by this quick select
975 uses field which is marked in passed bitmap.
976 */
977 virtual bool is_keys_used(const MY_BITMAP *fields);
978
979 /**
980 Simple sanity check that the quick select has been set up
981 correctly. Function is overridden by quick selects that merge
982 indices.
983 */
984 virtual bool is_valid() { return index != MAX_KEY; };
985
986 /*
987 rowid of last row retrieved by this quick select. This is used only when
988 doing ROR-index_merge selects
989 */
990 uchar *last_rowid;
991
992 /*
993 Table record buffer used by this quick select.
994 */
995 uchar *record;
996
997 virtual void replace_handler(handler *new_file)
998 {
999 DBUG_ASSERT(0); /* Only supported in QUICK_RANGE_SELECT */
1000 }
1001
1002#ifndef DBUG_OFF
1003 /*
1004 Print quick select information to DBUG_FILE. Caller is responsible
1005 for locking DBUG_FILE before this call and unlocking it afterwards.
1006 */
1007 virtual void dbug_dump(int indent, bool verbose)= 0;
1008#endif
1009
1010 /*
1011 Returns a QUICK_SELECT with reverse order of to the index.
1012 */
1013 virtual QUICK_SELECT_I *make_reverse(uint used_key_parts_arg) { return NULL; }
1014
1015 /*
1016 Add the key columns used by the quick select into table's read set.
1017
1018 This is used by an optimization in filesort.
1019 */
1020 virtual void add_used_key_part_to_set()=0;
1021};
1022
1023
1024struct st_qsel_param;
1025class PARAM;
1026
1027
1028/*
1029 MRR range sequence, array<QUICK_RANGE> implementation: sequence traversal
1030 context.
1031*/
1032typedef struct st_quick_range_seq_ctx
1033{
1034 QUICK_RANGE **first;
1035 QUICK_RANGE **cur;
1036 QUICK_RANGE **last;
1037} QUICK_RANGE_SEQ_CTX;
1038
1039range_seq_t quick_range_seq_init(void *init_param, uint n_ranges, uint flags);
1040bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
1041
1042
1043/*
1044 Quick select that does a range scan on a single key. The records are
1045 returned in key order.
1046*/
1047class QUICK_RANGE_SELECT : public QUICK_SELECT_I
1048{
1049protected:
1050 THD *thd;
1051 bool no_alloc;
1052 MEM_ROOT *parent_alloc;
1053
1054 /* true if we enabled key only reads */
1055 handler *file;
1056
1057 /* Members to deal with case when this quick select is a ROR-merged scan */
1058 bool in_ror_merged_scan;
1059 MY_BITMAP column_bitmap;
1060 bool free_file; /* TRUE <=> this->file is "owned" by this quick select */
1061
1062 /* Range pointers to be used when not using MRR interface */
1063 /* Members needed to use the MRR interface */
1064 QUICK_RANGE_SEQ_CTX qr_traversal_ctx;
1065public:
1066 uint mrr_flags; /* Flags to be used with MRR interface */
1067protected:
1068 uint mrr_buf_size; /* copy from thd->variables.mrr_buff_size */
1069 HANDLER_BUFFER *mrr_buf_desc; /* the handler buffer */
1070
1071 /* Info about index we're scanning */
1072
1073 DYNAMIC_ARRAY ranges; /* ordered array of range ptrs */
1074 QUICK_RANGE **cur_range; /* current element in ranges */
1075
1076 QUICK_RANGE *last_range;
1077
1078 KEY_PART *key_parts;
1079 KEY_PART_INFO *key_part_info;
1080
1081 bool dont_free; /* Used by QUICK_SELECT_DESC */
1082
1083 int cmp_next(QUICK_RANGE *range);
1084 int cmp_prev(QUICK_RANGE *range);
1085 bool row_in_ranges();
1086public:
1087 MEM_ROOT alloc;
1088
1089 QUICK_RANGE_SELECT(THD *thd, TABLE *table,uint index_arg,bool no_alloc,
1090 MEM_ROOT *parent_alloc, bool *create_err);
1091 ~QUICK_RANGE_SELECT();
1092 virtual QUICK_RANGE_SELECT *clone(bool *create_error)
1093 { return new QUICK_RANGE_SELECT(thd, head, index, no_alloc, parent_alloc,
1094 create_error); }
1095
1096 void need_sorted_output();
1097 int init();
1098 int reset(void);
1099 int get_next();
1100 void range_end();
1101 int get_next_prefix(uint prefix_length, uint group_key_parts,
1102 uchar *cur_prefix);
1103 bool reverse_sorted() { return 0; }
1104 bool unique_key_range();
1105 int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc);
1106 void save_last_pos()
1107 { file->position(record); }
1108 int get_type() { return QS_TYPE_RANGE; }
1109 void add_keys_and_lengths(String *key_names, String *used_lengths);
1110 Explain_quick_select *get_explain(MEM_ROOT *alloc);
1111#ifndef DBUG_OFF
1112 void dbug_dump(int indent, bool verbose);
1113#endif
1114 virtual void replace_handler(handler *new_file) { file= new_file; }
1115 QUICK_SELECT_I *make_reverse(uint used_key_parts_arg);
1116
1117 virtual void add_used_key_part_to_set();
1118
1119private:
1120 /* Default copy ctor used by QUICK_SELECT_DESC */
1121 friend class TRP_ROR_INTERSECT;
1122 friend
1123 QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
1124 struct st_table_ref *ref,
1125 ha_rows records);
1126 friend bool get_quick_keys(PARAM *param, QUICK_RANGE_SELECT *quick,
1127 KEY_PART *key, SEL_ARG *key_tree,
1128 uchar *min_key, uint min_key_flag,
1129 uchar *max_key, uint max_key_flag);
1130 friend QUICK_RANGE_SELECT *get_quick_select(PARAM*,uint idx,
1131 SEL_ARG *key_tree,
1132 uint mrr_flags,
1133 uint mrr_buf_size,
1134 MEM_ROOT *alloc);
1135 friend class QUICK_SELECT_DESC;
1136 friend class QUICK_INDEX_SORT_SELECT;
1137 friend class QUICK_INDEX_MERGE_SELECT;
1138 friend class QUICK_ROR_INTERSECT_SELECT;
1139 friend class QUICK_INDEX_INTERSECT_SELECT;
1140 friend class QUICK_GROUP_MIN_MAX_SELECT;
1141 friend bool quick_range_seq_next(range_seq_t rseq, KEY_MULTI_RANGE *range);
1142 friend range_seq_t quick_range_seq_init(void *init_param,
1143 uint n_ranges, uint flags);
1144 friend
1145 int read_keys_and_merge_scans(THD *thd, TABLE *head,
1146 List<QUICK_RANGE_SELECT> quick_selects,
1147 QUICK_RANGE_SELECT *pk_quick_select,
1148 READ_RECORD *read_record,
1149 bool intersection,
1150 key_map *filtered_scans,
1151 Unique **unique_ptr);
1152
1153};
1154
1155
1156class QUICK_RANGE_SELECT_GEOM: public QUICK_RANGE_SELECT
1157{
1158public:
1159 QUICK_RANGE_SELECT_GEOM(THD *thd, TABLE *table, uint index_arg,
1160 bool no_alloc, MEM_ROOT *parent_alloc,
1161 bool *create_err)
1162 :QUICK_RANGE_SELECT(thd, table, index_arg, no_alloc, parent_alloc,
1163 create_err)
1164 {};
1165 virtual QUICK_RANGE_SELECT *clone(bool *create_error)
1166 {
1167 DBUG_ASSERT(0);
1168 return new QUICK_RANGE_SELECT_GEOM(thd, head, index, no_alloc,
1169 parent_alloc, create_error);
1170 }
1171 virtual int get_next();
1172};
1173
1174
1175/*
1176 QUICK_INDEX_SORT_SELECT is the base class for the common functionality of:
1177 - QUICK_INDEX_MERGE_SELECT, access based on multi-index merge/union
1178 - QUICK_INDEX_INTERSECT_SELECT, access based on multi-index intersection
1179
1180
1181 QUICK_INDEX_SORT_SELECT uses
1182 * QUICK_RANGE_SELECTs to get rows
1183 * Unique class
1184 - to remove duplicate rows for QUICK_INDEX_MERGE_SELECT
1185 - to intersect rows for QUICK_INDEX_INTERSECT_SELECT
1186
1187 INDEX MERGE OPTIMIZER
1188 Current implementation doesn't detect all cases where index merge could
1189 be used, in particular:
1190
1191 * index_merge+'using index' is not supported
1192
1193 * If WHERE part contains complex nested AND and OR conditions, some ways
1194 to retrieve rows using index merge will not be considered. The choice
1195 of read plan may depend on the order of conjuncts/disjuncts in WHERE
1196 part of the query, see comments near imerge_list_or_list and
1197 SEL_IMERGE::or_sel_tree_with_checks functions for details.
1198
1199 * There is no "index_merge_ref" method (but index merge on non-first
1200 table in join is possible with 'range checked for each record').
1201
1202
1203 ROW RETRIEVAL ALGORITHM
1204
1205 index merge/intersection uses Unique class for duplicates removal.
1206 index merge/intersection takes advantage of Clustered Primary Key (CPK)
1207 if the table has one.
1208 The index merge/intersection algorithm consists of two phases:
1209
1210 Phase 1
1211 (implemented by a QUICK_INDEX_MERGE_SELECT::read_keys_and_merge call):
1212
1213 prepare()
1214 {
1215 activate 'index only';
1216 while(retrieve next row for non-CPK scan)
1217 {
1218 if (there is a CPK scan and row will be retrieved by it)
1219 skip this row;
1220 else
1221 put its rowid into Unique;
1222 }
1223 deactivate 'index only';
1224 }
1225
1226 Phase 2
1227 (implemented as sequence of QUICK_INDEX_MERGE_SELECT::get_next calls):
1228
1229 fetch()
1230 {
1231 retrieve all rows from row pointers stored in Unique
1232 (merging/intersecting them);
1233 free Unique;
1234 if (! intersection)
1235 retrieve all rows for CPK scan;
1236 }
1237*/
1238
1239class QUICK_INDEX_SORT_SELECT : public QUICK_SELECT_I
1240{
1241protected:
1242 Unique *unique;
1243public:
1244 QUICK_INDEX_SORT_SELECT(THD *thd, TABLE *table);
1245 ~QUICK_INDEX_SORT_SELECT();
1246
1247 int init();
1248 void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }
1249 int reset(void);
1250 bool reverse_sorted() { return false; }
1251 bool unique_key_range() { return false; }
1252 bool is_keys_used(const MY_BITMAP *fields);
1253#ifndef DBUG_OFF
1254 void dbug_dump(int indent, bool verbose);
1255#endif
1256 Explain_quick_select *get_explain(MEM_ROOT *alloc);
1257
1258 bool push_quick_back(QUICK_RANGE_SELECT *quick_sel_range);
1259
1260 /* range quick selects this index merge/intersect consists of */
1261 List<QUICK_RANGE_SELECT> quick_selects;
1262
1263 /* quick select that uses clustered primary key (NULL if none) */
1264 QUICK_RANGE_SELECT* pk_quick_select;
1265
1266 MEM_ROOT alloc;
1267 THD *thd;
1268 virtual bool is_valid()
1269 {
1270 List_iterator_fast<QUICK_RANGE_SELECT> it(quick_selects);
1271 QUICK_RANGE_SELECT *quick;
1272 bool valid= true;
1273 while ((quick= it++))
1274 {
1275 if (!quick->is_valid())
1276 {
1277 valid= false;
1278 break;
1279 }
1280 }
1281 return valid;
1282 }
1283 virtual int read_keys_and_merge()= 0;
1284 /* used to get rows collected in Unique */
1285 READ_RECORD read_record;
1286
1287 virtual void add_used_key_part_to_set();
1288};
1289
1290
1291
1292class QUICK_INDEX_MERGE_SELECT : public QUICK_INDEX_SORT_SELECT
1293{
1294private:
1295 /* true if this select is currently doing a clustered PK scan */
1296 bool doing_pk_scan;
1297protected:
1298 int read_keys_and_merge();
1299
1300public:
1301 QUICK_INDEX_MERGE_SELECT(THD *thd_arg, TABLE *table)
1302 :QUICK_INDEX_SORT_SELECT(thd_arg, table) {}
1303
1304 int get_next();
1305 int get_type() { return QS_TYPE_INDEX_MERGE; }
1306 void add_keys_and_lengths(String *key_names, String *used_lengths);
1307};
1308
1309class QUICK_INDEX_INTERSECT_SELECT : public QUICK_INDEX_SORT_SELECT
1310{
1311protected:
1312 int read_keys_and_merge();
1313
1314public:
1315 QUICK_INDEX_INTERSECT_SELECT(THD *thd_arg, TABLE *table)
1316 :QUICK_INDEX_SORT_SELECT(thd_arg, table) {}
1317
1318 key_map filtered_scans;
1319 int get_next();
1320 int get_type() { return QS_TYPE_INDEX_INTERSECT; }
1321 void add_keys_and_lengths(String *key_names, String *used_lengths);
1322 Explain_quick_select *get_explain(MEM_ROOT *alloc);
1323};
1324
1325
1326/*
1327 Rowid-Ordered Retrieval (ROR) index intersection quick select.
1328 This quick select produces intersection of row sequences returned
1329 by several QUICK_RANGE_SELECTs it "merges".
1330
1331 All merged QUICK_RANGE_SELECTs must return rowids in rowid order.
1332 QUICK_ROR_INTERSECT_SELECT will return rows in rowid order, too.
1333
1334 All merged quick selects retrieve {rowid, covered_fields} tuples (not full
1335 table records).
1336 QUICK_ROR_INTERSECT_SELECT retrieves full records if it is not being used
1337 by QUICK_ROR_INTERSECT_SELECT and all merged quick selects together don't
1338 cover needed all fields.
1339
1340 If one of the merged quick selects is a Clustered PK range scan, it is
1341 used only to filter rowid sequence produced by other merged quick selects.
1342*/
1343
1344class QUICK_ROR_INTERSECT_SELECT : public QUICK_SELECT_I
1345{
1346public:
1347 QUICK_ROR_INTERSECT_SELECT(THD *thd, TABLE *table,
1348 bool retrieve_full_rows,
1349 MEM_ROOT *parent_alloc);
1350 ~QUICK_ROR_INTERSECT_SELECT();
1351
1352 int init();
1353 void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }
1354 int reset(void);
1355 int get_next();
1356 bool reverse_sorted() { return false; }
1357 bool unique_key_range() { return false; }
1358 int get_type() { return QS_TYPE_ROR_INTERSECT; }
1359 void add_keys_and_lengths(String *key_names, String *used_lengths);
1360 Explain_quick_select *get_explain(MEM_ROOT *alloc);
1361 bool is_keys_used(const MY_BITMAP *fields);
1362 void add_used_key_part_to_set();
1363#ifndef DBUG_OFF
1364 void dbug_dump(int indent, bool verbose);
1365#endif
1366 int init_ror_merged_scan(bool reuse_handler, MEM_ROOT *alloc);
1367 bool push_quick_back(MEM_ROOT *alloc, QUICK_RANGE_SELECT *quick_sel_range);
1368
1369 class QUICK_SELECT_WITH_RECORD : public Sql_alloc
1370 {
1371 public:
1372 QUICK_RANGE_SELECT *quick;
1373 uchar *key_tuple;
1374 ~QUICK_SELECT_WITH_RECORD() { delete quick; }
1375 };
1376
1377 /*
1378 Range quick selects this intersection consists of, not including
1379 cpk_quick.
1380 */
1381 List<QUICK_SELECT_WITH_RECORD> quick_selects;
1382
1383 virtual bool is_valid()
1384 {
1385 List_iterator_fast<QUICK_SELECT_WITH_RECORD> it(quick_selects);
1386 QUICK_SELECT_WITH_RECORD *quick;
1387 bool valid= true;
1388 while ((quick= it++))
1389 {
1390 if (!quick->quick->is_valid())
1391 {
1392 valid= false;
1393 break;
1394 }
1395 }
1396 return valid;
1397 }
1398
1399 /*
1400 Merged quick select that uses Clustered PK, if there is one. This quick
1401 select is not used for row retrieval, it is used for row retrieval.
1402 */
1403 QUICK_RANGE_SELECT *cpk_quick;
1404
1405 MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
1406 THD *thd; /* current thread */
1407 bool need_to_fetch_row; /* if true, do retrieve full table records. */
1408 /* in top-level quick select, true if merged scans where initialized */
1409 bool scans_inited;
1410};
1411
1412
1413/*
1414 Rowid-Ordered Retrieval index union select.
1415 This quick select produces union of row sequences returned by several
1416 quick select it "merges".
1417
1418 All merged quick selects must return rowids in rowid order.
1419 QUICK_ROR_UNION_SELECT will return rows in rowid order, too.
1420
1421 All merged quick selects are set not to retrieve full table records.
1422 ROR-union quick select always retrieves full records.
1423
1424*/
1425
1426class QUICK_ROR_UNION_SELECT : public QUICK_SELECT_I
1427{
1428public:
1429 QUICK_ROR_UNION_SELECT(THD *thd, TABLE *table);
1430 ~QUICK_ROR_UNION_SELECT();
1431
1432 int init();
1433 void need_sorted_output() { DBUG_ASSERT(0); /* Can't do it */ }
1434 int reset(void);
1435 int get_next();
1436 bool reverse_sorted() { return false; }
1437 bool unique_key_range() { return false; }
1438 int get_type() { return QS_TYPE_ROR_UNION; }
1439 void add_keys_and_lengths(String *key_names, String *used_lengths);
1440 Explain_quick_select *get_explain(MEM_ROOT *alloc);
1441 bool is_keys_used(const MY_BITMAP *fields);
1442 void add_used_key_part_to_set();
1443#ifndef DBUG_OFF
1444 void dbug_dump(int indent, bool verbose);
1445#endif
1446
1447 bool push_quick_back(QUICK_SELECT_I *quick_sel_range);
1448
1449 List<QUICK_SELECT_I> quick_selects; /* Merged quick selects */
1450
1451 virtual bool is_valid()
1452 {
1453 List_iterator_fast<QUICK_SELECT_I> it(quick_selects);
1454 QUICK_SELECT_I *quick;
1455 bool valid= true;
1456 while ((quick= it++))
1457 {
1458 if (!quick->is_valid())
1459 {
1460 valid= false;
1461 break;
1462 }
1463 }
1464 return valid;
1465 }
1466
1467 QUEUE queue; /* Priority queue for merge operation */
1468 MEM_ROOT alloc; /* Memory pool for this and merged quick selects data. */
1469
1470 THD *thd; /* current thread */
1471 uchar *cur_rowid; /* buffer used in get_next() */
1472 uchar *prev_rowid; /* rowid of last row returned by get_next() */
1473 bool have_prev_rowid; /* true if prev_rowid has valid data */
1474 uint rowid_length; /* table rowid length */
1475private:
1476 bool scans_inited;
1477};
1478
1479
1480/*
1481 Index scan for GROUP-BY queries with MIN/MAX aggregate functions.
1482
1483 This class provides a specialized index access method for GROUP-BY queries
1484 of the forms:
1485
1486 SELECT A_1,...,A_k, [B_1,...,B_m], [MIN(C)], [MAX(C)]
1487 FROM T
1488 WHERE [RNG(A_1,...,A_p ; where p <= k)]
1489 [AND EQ(B_1,...,B_m)]
1490 [AND PC(C)]
1491 [AND PA(A_i1,...,A_iq)]
1492 GROUP BY A_1,...,A_k;
1493
1494 or
1495
1496 SELECT DISTINCT A_i1,...,A_ik
1497 FROM T
1498 WHERE [RNG(A_1,...,A_p ; where p <= k)]
1499 [AND PA(A_i1,...,A_iq)];
1500
1501 where all selected fields are parts of the same index.
1502 The class of queries that can be processed by this quick select is fully
1503 specified in the description of get_best_trp_group_min_max() in opt_range.cc.
1504
1505 The get_next() method directly produces result tuples, thus obviating the
1506 need to call end_send_group() because all grouping is already done inside
1507 get_next().
1508
1509 Since one of the requirements is that all select fields are part of the same
1510 index, this class produces only index keys, and not complete records.
1511*/
1512
1513class QUICK_GROUP_MIN_MAX_SELECT : public QUICK_SELECT_I
1514{
1515private:
1516 handler * const file; /* The handler used to get data. */
1517 JOIN *join; /* Descriptor of the current query */
1518 KEY *index_info; /* The index chosen for data access */
1519 uchar *record; /* Buffer where the next record is returned. */
1520 uchar *tmp_record; /* Temporary storage for next_min(), next_max(). */
1521 uchar *group_prefix; /* Key prefix consisting of the GROUP fields. */
1522 const uint group_prefix_len; /* Length of the group prefix. */
1523 uint group_key_parts; /* A number of keyparts in the group prefix */
1524 uchar *last_prefix; /* Prefix of the last group for detecting EOF. */
1525 bool have_min; /* Specify whether we are computing */
1526 bool have_max; /* a MIN, a MAX, or both. */
1527 bool have_agg_distinct;/* aggregate_function(DISTINCT ...). */
1528 bool seen_first_key; /* Denotes whether the first key was retrieved.*/
1529 bool doing_key_read; /* true if we enabled key only reads */
1530
1531 KEY_PART_INFO *min_max_arg_part; /* The keypart of the only argument field */
1532 /* of all MIN/MAX functions. */
1533 uint min_max_arg_len; /* The length of the MIN/MAX argument field */
1534 uchar *key_infix; /* Infix of constants from equality predicates. */
1535 uint key_infix_len;
1536 DYNAMIC_ARRAY min_max_ranges; /* Array of range ptrs for the MIN/MAX field. */
1537 uint real_prefix_len; /* Length of key prefix extended with key_infix. */
1538 uint real_key_parts; /* A number of keyparts in the above value. */
1539 List<Item_sum> *min_functions;
1540 List<Item_sum> *max_functions;
1541 List_iterator<Item_sum> *min_functions_it;
1542 List_iterator<Item_sum> *max_functions_it;
1543 /*
1544 Use index scan to get the next different key instead of jumping into it
1545 through index read
1546 */
1547 bool is_index_scan;
1548public:
1549 /*
1550 The following two members are public to allow easy access from
1551 TRP_GROUP_MIN_MAX::make_quick()
1552 */
1553 MEM_ROOT alloc; /* Memory pool for this and quick_prefix_select data. */
1554 QUICK_RANGE_SELECT *quick_prefix_select;/* For retrieval of group prefixes. */
1555private:
1556 int next_prefix();
1557 int next_min_in_range();
1558 int next_max_in_range();
1559 int next_min();
1560 int next_max();
1561 void update_min_result();
1562 void update_max_result();
1563 int cmp_min_max_key(const uchar *key, uint16 length);
1564public:
1565 QUICK_GROUP_MIN_MAX_SELECT(TABLE *table, JOIN *join, bool have_min,
1566 bool have_max, bool have_agg_distinct,
1567 KEY_PART_INFO *min_max_arg_part,
1568 uint group_prefix_len, uint group_key_parts,
1569 uint used_key_parts, KEY *index_info, uint
1570 use_index, double read_cost, ha_rows records, uint
1571 key_infix_len, uchar *key_infix, MEM_ROOT
1572 *parent_alloc, bool is_index_scan);
1573 ~QUICK_GROUP_MIN_MAX_SELECT();
1574 bool add_range(SEL_ARG *sel_range);
1575 void update_key_stat();
1576 void adjust_prefix_ranges();
1577 bool alloc_buffers();
1578 int init();
1579 void need_sorted_output() { /* always do it */ }
1580 int reset();
1581 int get_next();
1582 bool reverse_sorted() { return false; }
1583 bool unique_key_range() { return false; }
1584 int get_type() { return QS_TYPE_GROUP_MIN_MAX; }
1585 void add_keys_and_lengths(String *key_names, String *used_lengths);
1586 void add_used_key_part_to_set();
1587#ifndef DBUG_OFF
1588 void dbug_dump(int indent, bool verbose);
1589#endif
1590 bool is_agg_distinct() { return have_agg_distinct; }
1591 bool loose_scan_is_scanning() { return is_index_scan; }
1592 Explain_quick_select *get_explain(MEM_ROOT *alloc);
1593};
1594
1595
1596class QUICK_SELECT_DESC: public QUICK_RANGE_SELECT
1597{
1598public:
1599 QUICK_SELECT_DESC(QUICK_RANGE_SELECT *q, uint used_key_parts);
1600 virtual QUICK_RANGE_SELECT *clone(bool *create_error)
1601 { DBUG_ASSERT(0); return new QUICK_SELECT_DESC(this, used_key_parts); }
1602 int get_next();
1603 bool reverse_sorted() { return 1; }
1604 int get_type() { return QS_TYPE_RANGE_DESC; }
1605 QUICK_SELECT_I *make_reverse(uint used_key_parts_arg)
1606 {
1607 return this; // is already reverse sorted
1608 }
1609private:
1610 bool range_reads_after_key(QUICK_RANGE *range);
1611 int reset(void) { rev_it.rewind(); return QUICK_RANGE_SELECT::reset(); }
1612 List<QUICK_RANGE> rev_ranges;
1613 List_iterator<QUICK_RANGE> rev_it;
1614 uint used_key_parts;
1615};
1616
1617
1618class SQL_SELECT :public Sql_alloc {
1619 public:
1620 QUICK_SELECT_I *quick; // If quick-select used
1621 COND *cond; // where condition
1622
1623 /*
1624 When using Index Condition Pushdown: condition that we've had before
1625 extracting and pushing index condition.
1626 In other cases, NULL.
1627 */
1628 Item *pre_idx_push_select_cond;
1629 TABLE *head;
1630 IO_CACHE file; // Positions to used records
1631 ha_rows records; // Records in use if read from file
1632 double read_time; // Time to read rows
1633 key_map quick_keys; // Possible quick keys
1634 key_map needed_reg; // Possible quick keys after prev tables.
1635 table_map const_tables,read_tables;
1636 /* See PARAM::possible_keys */
1637 key_map possible_keys;
1638 bool free_cond; /* Currently not used and always FALSE */
1639
1640 SQL_SELECT();
1641 ~SQL_SELECT();
1642 void cleanup();
1643 void set_quick(QUICK_SELECT_I *new_quick) { delete quick; quick= new_quick; }
1644 bool check_quick(THD *thd, bool force_quick_range, ha_rows limit)
1645 {
1646 key_map tmp;
1647 tmp.set_all();
1648 return test_quick_select(thd, tmp, 0, limit, force_quick_range, FALSE, FALSE) < 0;
1649 }
1650 /*
1651 RETURN
1652 0 if record must be skipped <-> (cond && cond->val_int() == 0)
1653 -1 if error
1654 1 otherwise
1655 */
1656 inline int skip_record(THD *thd)
1657 {
1658 int rc= MY_TEST(!cond || cond->val_int());
1659 if (thd->is_error())
1660 rc= -1;
1661 return rc;
1662 }
1663 int test_quick_select(THD *thd, key_map keys, table_map prev_tables,
1664 ha_rows limit, bool force_quick_range,
1665 bool ordered_output, bool remove_false_parts_of_where);
1666};
1667
1668
1669class SQL_SELECT_auto
1670{
1671 SQL_SELECT *select;
1672public:
1673 SQL_SELECT_auto(): select(NULL)
1674 {}
1675 ~SQL_SELECT_auto()
1676 {
1677 delete select;
1678 }
1679 SQL_SELECT_auto&
1680 operator= (SQL_SELECT *_select)
1681 {
1682 select= _select;
1683 return *this;
1684 }
1685 operator SQL_SELECT * () const
1686 {
1687 return select;
1688 }
1689 SQL_SELECT *
1690 operator-> () const
1691 {
1692 return select;
1693 }
1694 operator bool () const
1695 {
1696 return select;
1697 }
1698};
1699
1700
1701class FT_SELECT: public QUICK_RANGE_SELECT
1702{
1703public:
1704 FT_SELECT(THD *thd, TABLE *table, uint key, bool *create_err) :
1705 QUICK_RANGE_SELECT (thd, table, key, 1, NULL, create_err)
1706 { (void) init(); }
1707 ~FT_SELECT() { file->ft_end(); }
1708 virtual QUICK_RANGE_SELECT *clone(bool *create_error)
1709 { DBUG_ASSERT(0); return new FT_SELECT(thd, head, index, create_error); }
1710 int init() { return file->ft_init(); }
1711 int reset() { return 0; }
1712 int get_next() { return file->ha_ft_read(record); }
1713 int get_type() { return QS_TYPE_FULLTEXT; }
1714};
1715
1716FT_SELECT *get_ft_select(THD *thd, TABLE *table, uint key);
1717QUICK_RANGE_SELECT *get_quick_select_for_ref(THD *thd, TABLE *table,
1718 struct st_table_ref *ref,
1719 ha_rows records);
1720SQL_SELECT *make_select(TABLE *head, table_map const_tables,
1721 table_map read_tables, COND *conds,
1722 SORT_INFO* filesort,
1723 bool allow_null_cond, int *error);
1724
1725bool calculate_cond_selectivity_for_table(THD *thd, TABLE *table, Item **cond);
1726
1727#ifdef WITH_PARTITION_STORAGE_ENGINE
1728bool prune_partitions(THD *thd, TABLE *table, Item *pprune_cond);
1729#endif
1730void store_key_image_to_rec(Field *field, uchar *ptr, uint len);
1731
1732extern String null_string;
1733
1734/* check this number of rows (default value) */
1735#define SELECTIVITY_SAMPLING_LIMIT 100
1736/* but no more then this part of table (10%) */
1737#define SELECTIVITY_SAMPLING_SHARE 0.10
1738/* do not check if we are going check less then this number of records */
1739#define SELECTIVITY_SAMPLING_THRESHOLD 10
1740
1741#endif
1742