我的书签
添加书签
移除书签- MySQL · 源码分析 · Range (Min-Max Tree)结构分析
- 概述
- SEL_TREE 图结构
- SEL_ROOT 图结构
- SEL_ARG 图结构
- 如何构造mm tree
- get_mm_tree (mm=min_max) 函数
- get_full_func_mm_tree 函数
- get_func_mm_tree 函数
- get_ne_mm_tree 函数
- get_mm_parts 函数
- get_func_mm_tree_from_in_predicate 函数
- get_mm_leaf 函数
- tree_and 函数
- tree_or 函数
- key_and 函数
- key_or 函数
- Range 概念
- 调用堆栈
- test_quick_select 函数
- get_key_scans_params 函数
- check_quick_select 函数
- Quick Read Plan 结构函数
- GDB分析工具
MySQL · 源码分析 · Range (Min-Max Tree)结构分析
概述
条件查询被广泛的使用在SQL查询中，复杂条件是否能在执行过程中被优化，比如恒为true或者false的条件，可以合并的条件。另外，由于索引是MySQL访问数据的基本方式，已经追求更快的访问方式，SARGable这个概念已经被我们遗忘了，因为他已经成为默认必要的方法（Search ARGument ABLE）。MySQL如何组织复杂条件并计算各个Ranges所影响到的对应可以使用的索引的代价和使用索引的不同快速方式，从而选出最优的计划，另外，MySQL分区表如何有效的进行条件剪枝？这都离不开一个结构mm tree。下面就让我们来揭开它的真实面纱。
我们在解决客户问题时 本文章的例子如下：
1. create table tmp_sel_arg(kp1 int, kp2 int, kp3 int, kp4 int);
2. create index ind_tmp_sel_arg on tmp_sel_arg(kp1, kp2, kp3);
3. select * from tmp_sel_arg where
4. (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR
5. (kp1=2 AND (kp3=11 OR kp3=14)) OR
6. (kp1=3 AND (kp3=11 OR kp3=14));
源代码路径：./sql/opt_range.cc
SEL_TREE 图结构
SEL_TREE结构的定义，记录选择的表上所有可选择的索引的图结构，针对索引的类森林数组
1. class SEL_TREE {
2. Mem_root_array<SEL_ROOT *> keys;
3. Key_map keys_map; /* bitmask of non-NULL elements in keys */
4. enum Type { IMPOSSIBLE, ALWAYS, MAYBE, KEY, KEY_SMALLER } type;
5. .......
6. }
8. IMPOSSIBLE: if keys[i]->type == SEL_ROOT::Type::IMPOSSIBLE for some i, then type == SEL_TREE::IMPOSSIBLE. Rationale: if the predicate for one of the indexes is always false, then the full predicate is also always false.
10. ALWAYS: if either (keys[i]->is_always()) or (keys[i] == NULL) for all i, then type == SEL_TREE::ALWAYS. Rationale: the range access method will not be able to filter out any rows when there are no range predicates that can be used to filter on any index.
12. KEY: There are range predicates that can be used on at least one index.
14. KEY_SMALLER: There are range predicates that can be used on at least one index. In addition, there are predicates that cannot be directly utilized by range access on key parts in the same index. These unused predicates makes it probable that the row estimate for range access on this index is too pessimistic.
SEL_ROOT 图结构
索引Range的图结构，针对于索引列的森林树结构
1. A graph of (possible multiple) key ranges, represented as a red-black binary tree. There are three types (see the Type enum); if KEY_RANGE, we have zero or more SEL_ARGs, described in the documentation on SEL_ARG.
3. class SEL_ROOT {
4. /**
5. Used to indicate if the range predicate for an index is always
6. true/false, depends on values from other tables or can be
7. evaluated as is.
8. */
9. enum class Type {
10. /** The range predicate for this index is always false. */
11. IMPOSSIBLE,
12. /**
13. There is a range predicate that refers to another table. The
14. range access method cannot be used on this index unless that
15. other table is earlier in the join sequence. The bit
16. representing the index is set in JOIN_TAB::needed_reg to
17. notify the join optimizer that there is a table dependency.
18. After deciding on join order, the optimizer may chose to rerun
19. the range optimizer for tables with such dependencies.
20. */
21. MAYBE_KEY,
22. /**
23. There is a range condition that can be used on this index. The
24. range conditions for this index in stored in the SEL_ARG tree.
25. */
26. KEY_RANGE
27. } type;
28. SEL_ARG *root; // The root node of the tree
29. }
SEL_ARG 图结构
记录了索引列的RB Tree结构，有两种表示形式，内部link和RB tree，各个keypart通过next_key_part相连
1. class SEL_ARG {
2. ......
3. Field *field{nullptr};
4. uchar *min_value, *max_value; // Pointer to range
5. ......
6. SEL_ARG *left, *right; /* R-B tree children */
7. SEL_ARG *next, *prev; /* Links for bi-directional interval list */
8. SEL_ARG *parent{nullptr}; /* R-B tree parent (nullptr for root) */
9. /*
10. R-B tree of intervals covering keyparts consecutive to this
11. SEL_ARG. See documentation of SEL_ARG GRAPH semantics for details.
12. */
13. SEL_ROOT *next_key_part{nullptr};
14. ......
15. }
Red-Black树结构
通过下面例子来展示内部的RB树结构如图：
1. (kp1 < 1 AND kp2=5 AND (kp3=10 OR kp3=12)) OR (kp1=2 AND (kp3=11 OR kp3=14)) OR
2. (kp1=3 AND (kp3=11 OR kp3=14));
3. Where / and \ denote left and right pointers and ... denotes next_key_part pointers to the root of the R-B tree of intervals for consecutive key parts.
5. tree->keys[0]
6. 0x7f59cf68a588
7. SEL_ROOT::Type::KEY_RANGE 0x7f59cf68aa90
8. use_count = 1, elements = 3 SEL_ROOT::Type::KEY_RANGE
9. || --> use_count = 1, elements = 2
10. || : ||
11. \/ : \/
12. 0x7f59cf68ac40 : 0x7f59cf68aa10
13. min_item=max_item=2 BLACK : min_item=max_item=11 BLACK
14. +-------+ : +--------+
15. | kp1=2 |.............. | kp3=11 |
16. +-------+ +--------+
17. / \ \
18. 0x7f59cf68a508 0x7f59cf68af88 0x7f59cf68ab28
19. max_item=1 RED min_item=max_item=3 RED min_item=max_item=14 RED
20. +-------+ +-------+ +--------+
21. | kp1<1 | | kp1=3 | | kp3=14 |
22. +-------+ +-------+ +--------+
23. : :
24. ...... .......
25. : :
26. SEL_ROOT::Type::KEY_RANGE SEL_ROOT::Type::KEY_RANGE
27. use_count = 1, elements = 1 use_count = 1, elements = 2
28. || ||
29. \/ \/
30. 0x7f59cf68a8f8 0x7f59cf68ad58
31. min_item=max_item=5 BLACK min_item=max_item=11 BLACK
32. +-------+ +--------+
33. | kp2=5 | | kp3=11 |
34. +-------+ +--------+
35. . \
36. ...... 0x7f59cf68ae70
37. . min_item=max_item=14 RED
38. 0x7f59cf68a6a8 +--------+
39. SEL_ROOT::Type::KEY_RANGE | kp3=14 |
40. use_count = 1, elements = 2 +--------+
41. ||
42. \/
43. 0x7f59cf68a628
44. min_item=max_item=10 BLACK
45. +--------+
46. | kp3=10 |
47. +--------+
48. \
49. 0x7f59cf68a740
50. min_item=max_item=12 RED
51. +--------+
52. | kp3=12 |
53. +--------+
内部的双向链表
SEL_ARG一组对象合成一个SEL_ROOT的图结构，内部通过SEL_ARG::next/prev来关联同一个索引列条件”OR”，通过next_key_part来关联不同索引列条件的”AND”
1. tree->keys[0] (SEL_ROOT::Type::KEY_RANGE)
2. |
3. | $ $
4. | part=1 $ part=2 $ part=3
5. | 0x7f59cf68a508 $ 0x7f59cf68a8f8 $ 0x7f59cf68a628
6. | left(RED) $ root(BLACK) $ root(BLACK)
7. | +-------+ $ +-------+ $ +--------+
8. | | kp1<1 |--------$------->| kp2=5 |-------$------>| kp3=10 |
9. | +-------+ $ +-------+ $ +--------+
10. | | $ $ |
11. | | $ $ right(RED)
12. | | $ $ 0x7f59cf68a740
13. | | $ $ +--------+
14. | | $ $ | kp3=12 |
15. | | $ $ +--------+
16. | | $ $
17. | 0x7f59cf68ac40 $ $ 0x7f59cf68aa10
18. | root(BLACK) $ $ root(BLACK)
19. | +-------+ $ $ +--------+
20. \------>| kp1=2 |-------$------------------------$------>| kp3=11 |
21. +-------+ $ $ +--------+
22. | $ $ |
23. | $ $ right(RED)
24. | $ $ 0x7f59cf68ab28
25. | $ $ +--------+
26. | $ $ | kp3=14 |
27. | $ $ +--------+
28. | $ $
29. right(RED) $ $ root(BLACK)
30. 0x7f59cf68af88 $ $ 0x7f59cf68ad58
31. +-------+ $ $ +--------+
32. | kp1=3 |-------$------------------------$------>| kp3=11 |
33. +-------+ $ $ +--------+
34. $ $ |
35. $ $ right(RED)
36. $ $ 0x7f59cf68ae70
37. $ $ +--------+
38. $ $ | kp3=14 |
39. $ $ +--------+
SEL_ARG flag标识
SEL_ARGs flag一共有6个bit来记录不同含义。前四个是借鉴enum key_range_flags.
1. flag = min_flag && max_flag
2. /*
3. The valid SEL_ARG representations are enumerated here:
5. bit5 bit4 bit3 bit2 bit1 bit0
6. NULL NULL NEAR NEAR NO NO
7. flag MAX MIN MAX MIN MAX MIN notation expr
8. 0 0 0 0 0 0 0 [a, a] X == a
9. 0 0 0 0 0 0 0 [a, b] X >= a && X <= b
10. 4 0 0 0 1 0 0 (a, b] X > a && X <= b
11. 8 0 0 1 0 0 0 [a, b) X >= a && X < b
12. C 0 0 1 1 0 0 (a, b) X > a && X < b
13. 1 0 0 0 - 0 1 b] X <= b
14. 2 0 0 - 0 1 0 [a, X >= a
15. 6 0 0 - 1 1 0 (a, X > a
16. 9 0 0 1 - 0 1 b) X < b
18. 10 0 1 - 0 0 0 [NULL, b] X IS NULL || X <= b
19. 18 0 1 - 0 1 0 [NULL, b) X IS NULL || X < b
20. 30 1 1 - 0 0 0 [NULL, NULL] X IS NULL
21. 14 0 1 0 1 0 0 (NULL, b] X <= b (nullable X)
22. 1C 0 1 1 1 0 0 (NULL, b) X < b (nullable X)
23. 16 - 1 - 1 1 0 (NULL, X IS NOT NULL
如何构造mm tree
get_mm_tree (mm=min_max) 函数
Range分析模块，用于找到所有可能索引的mm tree，构造的ranges可能会比原有的条件范围更大，比如下面简单的两个索引列和条件：
1. "WHERE fld1 > 'x' AND fld2 > 'y'"
这种场景，不论选择fld1的索引或者fld2的索引，可能读到的行数都比最终结果集多
1. static SEL_TREE *get_mm_tree(RANGE_OPT_PARAM *param, Item *cond) {
2. // Item And
3. while itemlist
4. new_tree = get_mm_tree
5. tree = tree_and(param, tree, new_tree);
6. // Item Or
7. while itemlist
8. new_tree = get_mm_tree
9. tree = tree_or(param, tree, new_tree);
10. }
get_full_func_mm_tree 函数
需要考虑所有等值列，构造多个mm trees WHERE t1.a=t2.a AND t2.a > 10 ==> WHERE t1.a=t2.a AND t2.a > 10 AND t1.a > 10 field->item_equal
1. The class Item_equal is used to represent conjunctions of equality | sql/sql_gather.cc:1824: List_iterator_fast<Item_equal> li(cond_equal->current_level)$
2. predicates of the form field1 = field2, and field=const in where | sql/sql_gather.cc:1825: Item_equal *item;
3. conditions and on expressions.
A BETWEEN predicate : fi [NOT] BETWEEN c1 AND c2 AND j,k (f1j <=c AND f2k<=c)
IN predicates: f IN (c1,…,cn) c IN (c1,…,f,…,cn) –> never try to narrow the index scan
get_func_mm_tree 函数
构造mm tree的入口函数
1. switch(func type) {
2. Item_func::NE_FUNC : get_ne_mm_tree
3. Item_func::BETWEEN : get_mm_parts
4. Item_func::IN_FUNC : get_func_mm_tree_from_in_predicate
5. default : get_mm_parts // <, <=, =, >=, >, LIKE, IS NULL, IS NOT NULL and GIS functions.
6. }
get_ne_mm_tree 函数
针对于 SEL_TREE for <> or NOT BETWEEN 条件构造mm tree kp1 <> 1 => kp1 < 1 or kp1 > 1
tree_or(kp1 < 1 , kp1 > 1)
1. (gdb) my sel tree
2. $k0 (SEL_TREE *) 0x7f7cf17c0cd0 [type=SEL_TREE::KEY,keys.m_size=1]
3. `--$k1 (SEL_ROOT *) 0x7f7cf17c0dc8 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=2]
4. `--$k2 (SEL_ARG *) 0x7f7cf17c0d48 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
5. | field = $k3 (Item_field *) 0x7f7cf04af268 field = test.tmp_sel_arg1.kp1
6. | scope = ( -infinity, $k4 (Item_int *) 0x7f7cf04ae670 value = 1 )
7. `--$k6 (SEL_ARG *) 0x7f7cf17c0e68 [color=SEL_ARG::RED, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=0 '\000', selectivity=1]
8. | field = $k7 (Item_field *) 0x7f7cf04af268 field = test.tmp_sel_arg1.kp1
9. | scope = ( $k8 (Item_int *) 0x7f7cf04ae670 value = 1, +infinity )
get_mm_parts 函数
通用的通过Item cond构造mm tree的方法
1. for (every key part) {
2. SEL_ROOT root = get_mm_leaf
3. SEL_TREE tree.root = root
4. }
get_func_mm_tree_from_in_predicate 函数
通过IN value构造mm tree
1. select * from tmp_sel_arg1 where kp1 in (1, 2, 3, 4, 5) and kp2 < 4;
2. (gdb) my sel tree
3. $d0 (SEL_TREE *) 0x7f7cf17c0cd0 [type=SEL_TREE::KEY,keys.m_size=2]
4. |--$d1 (SEL_ROOT *) 0x7f7cf17c0dd0 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=5]
5. | `--$d2 (SEL_ARG *) 0x7f7cf17c0e70 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
6. | | field = $d3 (Item_field *) 0x7f7cf0444938 field = test.tmp_sel_arg1.kp1
7. | | equal = [ $d4 (Item_int *) 0x7f7cf0d96420 value = 2 ]
8. | |--$d6 (SEL_ARG *) 0x7f7cf17c0d50 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
9. | | | field = $d7 (Item_field *) 0x7f7cf0444938 field = test.tmp_sel_arg1.kp1
10. | | | equal = [ $d8 (Item_int *) 0x7f7cf0d96320 value = 1 ]
11. | | `--$d12 (SEL_ROOT *) 0x7f7cf17c1370 [type=SEL_ROOT::Type::KEY_RANGE, use_count=5, elements=1]
12. | | `--$d13 (SEL_ARG *) 0x7f7cf17c12f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=1 '\001', selectivity=1]
13. | | | field = $d14 (Item_field *) 0x7f7cf0444ab0 field = test.tmp_sel_arg1.kp2
14. | | | scope = ( -infinity, $d15 (Item_int *) 0x7f7cf0d96b70 value = 4 )
15. | |--$d18 (SEL_ARG *) 0x7f7cf17c10b0 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
16. | | | field = $d19 (Item_field *) 0x7f7cf0444938 field = test.tmp_sel_arg1.kp1
17. | | | equal = [ $d20 (Item_int *) 0x7f7cf0d96668 value = 4 ]
18. | | |--$d22 (SEL_ARG *) 0x7f7cf17c0f90 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
19. | | | | field = $d23 (Item_field *) 0x7f7cf0444938 field = test.tmp_sel_arg1.kp1
20. | | | | equal = [ $d24 (Item_int *) 0x7f7cf0d96558 value = 3 ]
21. | | | `--$d28 (SEL_ROOT *) 0x7f7cf17c1370 [type=SEL_ROOT::Type::KEY_RANGE, use_count=5, elements=1]
22. | | | `--$d29 (SEL_ARG *) 0x7f7cf17c12f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=1 '\001', selectivity=1]
23. | | | | field = $d30 (Item_field *) 0x7f7cf0444ab0 field = test.tmp_sel_arg1.kp2
24. | | | | scope = ( -infinity, $d31 (Item_int *) 0x7f7cf0d96b70 value = 4 )
25. | | |--$d34 (SEL_ARG *) 0x7f7cf17c11d0 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
26. | | | | field = $d35 (Item_field *) 0x7f7cf0444938 field = test.tmp_sel_arg1.kp1
27. | | | | equal = [ $d36 (Item_int *) 0x7f7cf0d96778 value = 5 ]
28. | | | `--$d40 (SEL_ROOT *) 0x7f7cf17c1370 [type=SEL_ROOT::Type::KEY_RANGE, use_count=5, elements=1]
29. | | | `--$d41 (SEL_ARG *) 0x7f7cf17c12f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=1 '\001', selectivity=1]
30. | | | | field = $d42 (Item_field *) 0x7f7cf0444ab0 field = test.tmp_sel_arg1.kp2
31. | | | | scope = ( -infinity, $d43 (Item_int *) 0x7f7cf0d96b70 value = 4 )
32. | | `--$d46 (SEL_ROOT *) 0x7f7cf17c1370 [type=SEL_ROOT::Type::KEY_RANGE, use_count=5, elements=1]
33. | | `--$d47 (SEL_ARG *) 0x7f7cf17c12f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=1 '\001', selectivity=1]
34. | | | field = $d48 (Item_field *) 0x7f7cf0444ab0 field = test.tmp_sel_arg1.kp2
35. | | | scope = ( -infinity, $d49 (Item_int *) 0x7f7cf0d96b70 value = 4 )
36. | `--$d52 (SEL_ROOT *) 0x7f7cf17c1370 [type=SEL_ROOT::Type::KEY_RANGE, use_count=5, elements=1]
37. | `--$d53 (SEL_ARG *) 0x7f7cf17c12f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=1 '\001', selectivity=1]
38. | | field = $d54 (Item_field *) 0x7f7cf0444ab0 field = test.tmp_sel_arg1.kp2
39. | | scope = ( -infinity, $d55 (Item_int *) 0x7f7cf0d96b70 value = 4 )
40. `--$d58 (SEL_ROOT *) 0x7f7cf17c1420 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
41. `--$d59 (SEL_ARG *) 0x7f7cf17c13a0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
42. | field = $d60 (Item_field *) 0x7f7cf0444ab0 field = test.tmp_sel_arg1.kp2
43. | scope = ( -infinity, $d61 (Item_int *) 0x7f7cf0d96b70 value = 4 )
对于IN values
1. foreach op->arguments
2. tree_or (get_mm_parts)
NOT IN是有可能把内存oom的，因此not in的个数收到NOT_IN_IGNORE_THRESHOLD的控制，小于这个阈值，创建mmtree，否则返回null
1. const uint NOT_IN_IGNORE_THRESHOLD = 1000; // If we have t.key NOT IN (null, null, ...) or the list is too long
2. select * from tmp_sel_arg1 where kp1 not in (1, 2, 3, 4, 5)
3. (gdb) my st tree
4. $b0 (SEL_TREE *) 0x7f7cf040acd0 [type=SEL_TREE::KEY,keys.m_size=1]
5. `--$b1 (SEL_ROOT *) 0x7f7cf040adc8 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=6]
6. `--$b2 (SEL_ARG *) 0x7f7cf040ae68 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
7. | field = $b3 (Item_field *) 0x7f7cf0446438 field = test.tmp_sel_arg1.kp1
8. | scope = ( $b4 (Item_int *) 0x7f7cf04add58 value = 5, $b5 (Item_int *) 0x7f7cf04add58 value = 5 )
9. |--$b6 (SEL_ARG *) 0x7f7cf040ad48 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
10. | | field = $b7 (Item_field *) 0x7f7cf0446438 field = test.tmp_sel_arg1.kp1
11. | | scope = ( -infinity, $b8 (Item_int *) 0x7f7cf04add58 value = 5 )
12. `--$b11 (SEL_ARG *) 0x7f7cf040b0a8 [color=SEL_ARG::RED, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
13. | field = $b12 (Item_field *) 0x7f7cf0446438 field = test.tmp_sel_arg1.kp1
14. | scope = ( $b13 (Item_int *) 0x7f7cf04add58 value = 5, $b14 (Item_int *) 0x7f7cf04add58 value = 5 )
15. |--$b15 (SEL_ARG *) 0x7f7cf040af88 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
16. | | field = $b16 (Item_field *) 0x7f7cf0446438 field = test.tmp_sel_arg1.kp1
17. | | scope = ( $b17 (Item_int *) 0x7f7cf04add58 value = 5, $b18 (Item_int *) 0x7f7cf04add58 value = 5 )
18. `--$b21 (SEL_ARG *) 0x7f7cf040b1c8 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
19. | field = $b22 (Item_field *) 0x7f7cf0446438 field = test.tmp_sel_arg1.kp1
20. | scope = ( $b23 (Item_int *) 0x7f7cf04add58 value = 5, $b24 (Item_int *) 0x7f7cf04add58 value = 5 )
21. `--$b26 (SEL_ARG *) 0x7f7cf040b2e8 [color=SEL_ARG::RED, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=0 '\000', selectivity=1]
22. | field = $b27 (Item_field *) 0x7f7cf0446438 field = test.tmp_sel_arg1.kp1
23. | scope = ( $b28 (Item_int *) 0x7f7cf04add58 value = 5, +infinity )
记录NOT IN的变量，is_negated = true t.key NOT IN (c1, c2, …), c{i} are constants. => ($MIN<t.key<c1) OR (c1<t.key<c2) OR (c2<t.key<c3) OR … (*), $MIN is either “-inf” or NULL
1. 1. Get a SEL_TREE for "(-inf|NULL) < X < c_0" interval.
2. tree = get_mm_parts(param, op, field, Item_func::LT_FUNC, value_item);
3. 2. Get a SEL_TREE for "-inf < X < c_i" interval
4. tree2 = get_mm_parts(param, op, field, Item_func::LT_FUNC, value_item);
5. 3. Change all intervals to be "c_{i-1} < X < c_i
6. tree = tree_or(param, tree, tree2);
7. 4. Get the SEL_TREE for the last "c_last < X < +inf" interval
8. tree2 = get_mm_parts(param, op, field, Item_func::GT_FUNC, value_item);
9. tree = tree_or(param, tree, tree2);
get_mm_leaf 函数
构造SEL_ROOT结构
tree_and 函数
遍历所有keys，通过key_and合并 tree1和tree2
1. for (uint idx = 0; idx < param->keys; idx++) {
2. key_and // Produce a SEL_ARG graph that represents "key1 AND key2"
3. }
tree_or 函数
遍历所有keys，通过key_or合并 tree1和tree2 a) 可能产生简单的range (in tree->keys[]) b) 可能产生index merge range(in tree->merges)
1. for (uint idx = 0; idx < param->keys; idx++) {
2. key_or
3. }
key_and 函数
尽可能合并 SEL_ARG “key1 AND key2” . kp1 > 1 and kp1 < 5 (sel_arg1(min_value=1) and sel_arg2(max_value=5)) —-> 1 < kp1 < 5 (new_sel_arg(min_value=1, max_value=5))
kp1 > 1 and kp1 > 5 (sel_arg1(min_value=1) and sel_arg2(min_value=5)) —-> kp1 > 5 (new_sel_arg(min_value=5))
key_or 函数
尽可能合并 SEL_ARG “key1 OR key2” . => expr1 OR expr2. 对于重叠的子范围，递归调用key_or： (1) ( 1 < kp1 < 10 AND 1 < kp2 < 10 ) (2) ( 2 < kp1 < 20 AND 4 < kp2 < 20 ) key_or( 1 < kp2 < 10, 4 < kp2 < 20 ) => 1 < kp2 < 2
Range 概念
1. Notation for illustrations used in the rest of this function:
3. Range: [--------]
4. ^ ^
5. start stop
7. Two overlapping ranges:
8. [-----] [----] [--]
9. [---] or [---] or [-------]
11. Ambiguity: ***
12. The range starts or stops somewhere in the "***" range.
13. Example: a starts before b and may end before/the same place/after b
14. a: [----***]
15. b: [---]
17. Adjacent ranges:
18. Ranges that meet but do not overlap. Example: a = "x < 3", b = "x >= 3"
19. a: ----]
20. b: [----
比较函数cmp_xxx_to_yyy {xxx|yyy = min|max} find_range–>cmp_min_to_min
1. initialize cur_key1 to the latest range in key1 that starts the
2. same place or before the range in cur_key2 starts
4. cur_key2: [------]
5. key1: [---] [-----] [----]
6. ^
7. cur_key1
9. Used to describe how two key values are positioned compared to
10. each other. Consider key_value_a.<cmp_func>(key_value_b):
12. -2: key_value_a is smaller than key_value_b, and they are adjacent
13. -1: key_value_a is smaller than key_value_b (not adjacent)
14. 0: the key values are equal
15. 1: key_value_a is bigger than key_value_b (not adjacent)
16. 2: key_value_a is bigger than key_value_b, and they are adjacent
18. Example: "cmp= cur_key1->cmp_max_to_min(cur_key2)"
20. cur_key2: [-------- (10 <= x ... )
21. cur_key1: -----] ( ... x < 10) => cmp==-2
22. cur_key1: ----] ( ... x < 9) => cmp==-1
23. cur_key1: ------] ( ... x <= 10) => cmp== 0
24. cur_key1: --------] ( ... x <= 12) => cmp== 1
25. (cmp == 2 does not make sense for cmp_max_to_min())
典型的例子和处理逻辑：
1. Some typical examples:
3. 1. explain select * from tmp_sel_arg where kp1 between 1 and 10 or kp1 between 0 and 20;
5. cur_key2: [--------]
6. key1: [****--] [----] [-------]
7. ^
8. cur_key1
11. 2. explain select * from tmp_sel_arg where kp1 between 1 and 10 or kp1 between 10 and 20;
12. This is the case:
13. cur_key2: [-------]
14. cur_key1: [----]
16. Result:
17. cur_key2: [-------------] => inserted into key1 below
18. cur_key1: => deleted
20. (gdb) my sel key1
21. $p0 (SEL_ROOT *) 0x7f7cf17c0f48 [type=SEL_ROOT::Type::KEY_RANGE, use_count=0, elements=1]
22. `--$p1 (SEL_ARG *) 0x7f7cf17c0ec8 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
23. | field = $p2 (Item_field *) 0x7f7cf0444df0 field = test.tmp_sel_arg.kp1
24. | scope = [ $p3 (Item_int *) 0x7f7cf0d96340 value = 1, $p4 (Item_int *) 0x7f7cf0d96440 value = 10 ]
25. (gdb) my sel key2
26. $q0 (SEL_ROOT *) 0x7f7cf17c1220 [type=SEL_ROOT::Type::KEY_RANGE, use_count=0, elements=1]
27. `--$q1 (SEL_ARG *) 0x7f7cf17c11a0 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
28. | field = $q2 (Item_field *) 0x7f7cf0444f68 field = test.tmp_sel_arg.kp1
29. | scope = [ $q3 (Item_int *) 0x7f7cf0d969a0 value = 10, $q4 (Item_int *) 0x7f7cf0d96aa0 value = 20 ]
30. 8838 SEL_ROOT *new_key = key_or(param, key1, key2);
31. (gdb) my sel new_key
32. $r0 (SEL_ROOT *) 0x7f7cf17c0f48 [type=SEL_ROOT::Type::KEY_RANGE, use_count=0, elements=1]
33. `--$r1 (SEL_ARG *) 0x7f7cf17c0ec8 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
34. | field = $r2 (Item_field *) 0x7f7cf0444df0 field = test.tmp_sel_arg.kp1
35. | scope = [ $r3 (Item_int *) 0x7f7cf0d96340 value = 1, $r4 (Item_int *) 0x7f7cf0d96aa0 value = 20 ]
38. 3. explain select * from tmp_sel_arg where kp1 between 1 and 10 and kp2 > 1 or kp1 between 10 and 20 and kp2 > 1;
39. Adjacent ranges with equal next_key_part. Merge like this:
41. This is the case:
42. cur_key2: [------]
43. cur_key1: [-----]
45. Result:
46. cur_key2: [------]
47. cur_key1: [-------------] ? TODO:daoke.wangc why key2 is not deleted
49. $u0 (SEL_TREE *) 0x7f7cf040ac90 [type=SEL_TREE::KEY,keys.m_size=1]
50. `--$u1 (SEL_ROOT *) 0x7f7cf040af48 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=2]
51. `--$u2 (SEL_ARG *) 0x7f7cf040aec8 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
52. | field = $u3 (Item_field *) 0x7f7cf04b09e0 field = test.tmp_sel_arg.kp1
53. | scope = [ $u4 (Item_int *) 0x7f7cf04af218 value = 10, $u5 (Item_int *) 0x7f7cf04af318 value = 20 ]
54. |--$u6 (SEL_ARG *) 0x7f7cf040b470 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=8 '\b', part=0 '\000', selectivity=1]
55. | | field = $u7 (Item_field *) 0x7f7cf04b09e0 field = test.tmp_sel_arg.kp1
56. | | scope = [ $u8 (Item_int *) 0x7f7cf04ae6f0 value = 1, $u9 (Item_int *) 0x7f7cf04af218 value = 10 )
57. | `--$u12 (SEL_ROOT *) 0x7f7cf040b060 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
58. | `--$u13 (SEL_ARG *) 0x7f7cf040afe0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
59. | | field = $u14 (Item_field *) 0x7f7cf04b0b58 field = test.tmp_sel_arg.kp2
60. | | scope = ( $u15 (Item_int *) 0x7f7cf04aed50 value = 1, +infinity )
61. `--$u19 (SEL_ROOT *) 0x7f7cf040b570 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
62. `--$u20 (SEL_ARG *) 0x7f7cf040b4f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
63. | field = $u21 (Item_field *) 0x7f7cf04b0b58 field = test.tmp_sel_arg.kp2
64. | scope = ( $u22 (Item_int *) 0x7f7cf04aed50 value = 1, +infinity )
66. 4. explain select * from tmp_sel_arg where kp1 between 30 and 50 and kp2 > 1 or kp1 between 60 and 120 and kp2 > 20 or kp1 between 10 and 100 and kp2 > 1;
68. cur_key2: [****----------------------*******]
69. key1: [--] [----] [---] [-----] [xxxx]
70. ^ ^ ^
71. first last different next_key_part
73. Result:
74. cur_key2: [****----------------------*******]
75. [--] [----] [---] => deleted from key1
76. key1: [**------------------------***][xxxx]
77. ^ ^
78. cur_key1=last different next_key_part
80. $ab0 (SEL_TREE *) 0x7f7cf17c0c90 [type=SEL_TREE::KEY,keys.m_size=1]
81. `--$ab1 (SEL_ROOT *) 0x7f7cf17c0f48 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=3]
82. `--$ab2 (SEL_ARG *) 0x7f7cf17c1860 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
83. | field = $ab3 (Item_field *) 0x7f7cf0446718 field = test.tmp_sel_arg.kp1
84. | scope = [ $ab4 (Item_int *) 0x7f7cf0d96ee8 value = 60, $ab5 (Item_int *) 0x7f7cf0444cd0 value = 100 ]
85. |--$ab6 (SEL_ARG *) 0x7f7cf17c0ec8 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=8 '\b', part=0 '\000', selectivity=1]
86. | | field = $ab7 (Item_field *) 0x7f7cf0446228 field = test.tmp_sel_arg.kp1
87. | | scope = [ $ab8 (Item_int *) 0x7f7cf0444bd0 value = 10, $ab9 (Item_int *) 0x7f7cf0d96ee8 value = 60 )
88. | `--$ab12 (SEL_ROOT *) 0x7f7cf17c1060 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
89. | `--$ab13 (SEL_ARG *) 0x7f7cf17c0fe0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
90. | | field = $ab14 (Item_field *) 0x7f7cf04463a0 field = test.tmp_sel_arg.kp2
91. | | scope = ( $ab15 (Item_int *) 0x7f7cf0d96a20 value = 1, +infinity )
92. |--$ab18 (SEL_ARG *) 0x7f7cf17c12b8 [color=SEL_ARG::RED, is_asc=true, minflag=4 '\004', maxflag=0 '\000', part=0 '\000', selectivity=1]
93. | | field = $ab19 (Item_field *) 0x7f7cf0446718 field = test.tmp_sel_arg.kp1
94. | | scope = ( $ab20 (Item_int *) 0x7f7cf0444cd0 value = 100, $ab21 (Item_int *) 0x7f7cf0444028 value = 120 ]
95. | `--$ab24 (SEL_ROOT *) 0x7f7cf17c1450 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
96. | `--$ab25 (SEL_ARG *) 0x7f7cf17c13d0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
97. | | field = $ab26 (Item_field *) 0x7f7cf0446890 field = test.tmp_sel_arg.kp2
98. | | scope = ( $ab27 (Item_int *) 0x7f7cf0444588 value = 20, +infinity )
99. `--$ab30 (SEL_ROOT *) 0x7f7cf17c1960 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
100. `--$ab31 (SEL_ARG *) 0x7f7cf17c18e0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
101. | field = $ab32 (Item_field *) 0x7f7cf0446890 field = test.tmp_sel_arg.kp2
102. | scope = ( $ab33 (Item_int *) 0x7f7cf0445230 value = 1, +infinity )
105. 5. with next_key_part and not
106. This is the case:
107. cur_key2: [-------]
108. cur_key1: [---------]
110. Result:
111. cur_key2: deleted
112. cur_key1: [------------]
114. explain select * from tmp_sel_arg where kp1 between 5 and 15 or kp1 between 10 and 30;
115. $ae0 (SEL_TREE *) 0x7f7cf040ac90 [type=SEL_TREE::KEY,keys.m_size=1]
116. `--$ae1 (SEL_ROOT *) 0x7f7cf040af48 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
117. `--$ae2 (SEL_ARG *) 0x7f7cf040aec8 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
118. | field = $ae3 (Item_field *) 0x7f7cf0444df0 field = test.tmp_sel_arg.kp1
119. | scope = [ $ae4 (Item_int *) 0x7f7cf0d96340 value = 5, $ae5 (Item_int *) 0x7f7cf0d96aa0 value = 30 ]
121. This is the case:
122. cur_key2: [-------]
123. cur_key1: [---------]
125. Result:
126. cur_key2: [---]
127. cur_key1: [---------]
129. explain select * from tmp_sel_arg where kp1 between 5 and 15 and kp2 > 1 or kp1 between 10 and 30 and kp2 > 1;
130. $ad0 (SEL_TREE *) 0x7f7cf17c0c90 [type=SEL_TREE::KEY,keys.m_size=1]
131. `--$ad1 (SEL_ROOT *) 0x7f7cf17c0f48 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=2]
132. `--$ad2 (SEL_ARG *) 0x7f7cf17c0ec8 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
133. | field = $ad3 (Item_field *) 0x7f7cf04b09e0 field = test.tmp_sel_arg.kp1
134. | scope = [ $ad4 (Item_int *) 0x7f7cf04af218 value = 10, $ad5 (Item_int *) 0x7f7cf04af318 value = 30 ]
135. |--$ad6 (SEL_ARG *) 0x7f7cf17c1470 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=8 '\b', part=0 '\000', selectivity=1]
136. | | field = $ad7 (Item_field *) 0x7f7cf04b09e0 field = test.tmp_sel_arg.kp1
137. | | scope = [ $ad8 (Item_int *) 0x7f7cf04ae6f0 value = 5, $ad9 (Item_int *) 0x7f7cf04af218 value = 10 )
138. | `--$ad12 (SEL_ROOT *) 0x7f7cf17c1060 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
139. | `--$ad13 (SEL_ARG *) 0x7f7cf17c0fe0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
140. | | field = $ad14 (Item_field *) 0x7f7cf04b0b58 field = test.tmp_sel_arg.kp2
141. | | scope = ( $ad15 (Item_int *) 0x7f7cf04aed50 value = 1, +infinity )
142. `--$ad19 (SEL_ROOT *) 0x7f7cf17c1570 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
143. `--$ad20 (SEL_ARG *) 0x7f7cf17c14f0 [color=SEL_ARG::BLACK, is_asc=true, minflag=4 '\004', maxflag=2 '\002', part=1 '\001', selectivity=1]
144. | field = $ad21 (Item_field *) 0x7f7cf04b0b58 field = test.tmp_sel_arg.kp2
145. | scope = ( $ad22 (Item_int *) 0x7f7cf04aed50 value = 1, +infinity )
调用堆栈
通过range生成mm tree是在优化阶段进行的，目的是计算代价，选择更优quick访问路径。
1. select * from tmp_sel_arg where (kp1=1 and kp2=2 and kp3=3) or (kp1=1 and kp2=2 and kp3=4) or (kp1=1 and kp2=3 and kp3=5) or (kp1=1 and kp2=3 and kp3=6);
2. #3 0x000000000322ab92 in test_quick_select (thd=0x7f59d160b000, keys_to_use=..., prev_tables=0, limit=18446744073709551615, force_quick_range=false,
3. interesting_order=ORDER_NOT_RELEVANT, tab=0x7f59cf4dd690, cond=0x7f59d0ee3740, needed_reg=0x7f59cf4dd6e0, quick=0x7f5ad0efa738)
4. at /flash11/daoke.wangc/PolarDB_80/sql/opt_range.cc:4106
5. #4 0x0000000003384764 in get_quick_record_count (thd=0x7f59d160b000, tab=0x7f59cf4dd690, limit=18446744073709551615)
6. at /flash11/daoke.wangc/PolarDB_80/sql/sql_optimizer.cc:5980
7. #5 0x0000000003383c40 in JOIN::estimate_rowcount (this=0x7f59cf4dbc68) at /flash11/daoke.wangc/PolarDB_80/sql/sql_optimizer.cc:5713
8. #6 0x000000000338202c in JOIN::make_join_plan (this=0x7f59cf4dbc68) at /flash11/daoke.wangc/PolarDB_80/sql/sql_optimizer.cc:5123
9. #7 0x0000000003375d5b in JOIN::optimize (this=0x7f59cf4dbc68) at /flash11/daoke.wangc/PolarDB_80/sql/sql_optimizer.cc:688
10. #8 0x0000000003424076 in SELECT_LEX::optimize (this=0x7f59cf6ad968, thd=0x7f59d160b000) at /flash11/daoke.wangc/PolarDB_80/sql/sql_select.cc:1619
11. #9 0x00000000034223d2 in Sql_cmd_dml::execute_inner (this=0x7f59cf4db3f0, thd=0x7f59d160b000) at /flash11/daoke.wangc/PolarDB_80/sql/sql_select.cc:753
12. #10 0x0000000003421d53 in Sql_cmd_dml::execute (this=0x7f59cf4db3f0, thd=0x7f59d160b000) at /flash11/daoke.wangc/PolarDB_80/sql/sql_select.cc:631
13. #11 0x00000000033a7a71 in mysql_execute_command (thd=0x7f59d160b000, first_level=true) at /flash11/daoke.wangc/PolarDB_80/sql/sql_parse.cc:4897
14. #12 0x00000000033aa369 in mysql_parse (thd=0x7f59d160b000, parser_state=0x7f5ad0efc6f0, force_primary_storage_engine=false)
15. at /flash11/daoke.wangc/PolarDB_80/sql/sql_parse.cc:5722
16. #13 0x000000000339eaeb in dispatch_command (thd=0x7f59d160b000, com_data=0x7f5ad0efd1b0, command=COM_QUERY) at /flash11/daoke.wangc/PolarDB_80/sql/sql_parse.cc:1873
17. #14 0x000000000339cd7f in do_command(THD*, std::function<bool (THD*, COM_DATA const*, enum_server_command)>*) (thd=0x7f59d160b000, dispatcher=0x0)
18. at /flash11/daoke.wangc/PolarDB_80/sql/sql_parse.cc:1335
19. #15 0x000000000339cf1d in do_command (thd=0x7f59d160b000) at /flash11/daoke.wangc/PolarDB_80/sql/sql_parse.cc:1372
20. #16 0x00000000035f4930 in handle_connection (arg=0x7f5ad6180ec0) at /flash11/daoke.wangc/PolarDB_80/sql/conn_handler/connection_handler_per_thread.cc:316
21. #17 0x000000000506e2f3 in pfs_spawn_thread (arg=0x7f5ad628aa20) at /flash11/daoke.wangc/PolarDB_80/storage/perfschema/pfs.cc:2879
22. #18 0x00007f5af4027e25 in start_thread () from /lib64/libpthread.so.0
23. #19 0x00007f5af291df1d in clone () from /lib64/libc.so.6
test_quick_select 函数
test_quick_select用来根据范围选择索引是否有很快的代价最低的访问方式
步骤如下:
1. 0. prepare potential ranges scan index/keyparts
2. 1. setup_range_conditions
3. tree = get_mm_tree(¶m, cond);
4. 2. Fix the selectivity for SEL_ARGs by histogram
5. fix_sel_tree_selectivity(¶m, tree);
6. 3. Try to construct a QUICK_GROUP_MIN_MAX_SELECT
7. group_trp = get_best_group_min_max(¶m, tree, &best_cost);
8. 4. Try to construnct a QUICK_SKIP_SCAN_SELECT
9. skip_scan_trp = get_best_skip_scan(¶m, tree, force_skip_scan);
10. 5. Get best 'range' plan and prepare data for making other plans
11. range_trp = get_key_scans_params(¶m, tree, false, true, &best_cost)
12. 6. Get best non-covering ROR-intersection plan and prepare data for building covering ROR-intersection.
13. rori_trp = get_best_ror_intersect(¶m, tree, &best_cost, true)
14. 7. Try creating index_merge/ROR-union scan.
15. new_conj_trp = get_best_disjunct_quick(¶m, imerge, &best_cost);
16. 8. If we got a read plan, create a quick select from it.
17. qck = best_trp->make_quick(¶m, true)
get_key_scans_params 函数
获取最佳的range扫描方式
1. for (idx = 0; idx < param->keys; idx++) {
2. key = tree->keys[idx];
3. check_quick_select
4. find best trp
5. }
check_quick_select 函数
根据已知索引key，遍历对应SEL_ARG mm tree，计算所有range索引扫描的rows用来计算代价
1. ha_innobase::multi_range_read_info_const
2. for every range in key RB tree
3. get the next interval in the R-B tree
4. rows += ha_innobase/ha_innopart::records_in_range
5. n_ranges++
6. RANGE_SEQ_IF seq_if = {sel_arg_range_seq_init, sel_arg_range_seq_next, 0, 0};
7. MRR range sequence, SEL_ARG* implementation: SEL_ARG graph traversal context
8. Consider a query with these range predicates:
9. (kp0=1 and kp1=2 and kp2=3) or
10. (kp0=1 and kp1=2 and kp2=4) or
11. (kp0=1 and kp1=3 and kp2=5) or
12. (kp0=1 and kp1=3 and kp2=6)
14. 1) sel_arg_range_seq_next() is called the first time
15. - traverse the R-B tree (see SEL_ARG) to find the first range
16. - returns range "1:2:3"
17. - values in stack after this: stack[1, 1:2, 1:2:3]
18. 2) sel_arg_range_seq_next() is called second time
19. - keypart 2 has another range, so the next range in
20. keypart 2 is appended to stack[1] and saved
21. in stack[2]
22. - returns range "1:2:4"
23. - values in stack after this: stack[1, 1:2, 1:2:4]
24. 3) sel_arg_range_seq_next() is called the third time
25. - no more ranges in keypart 2, but keypart 1 has
26. another range, so the next range in keypart 1 is
27. appended to stack[0] and saved in stack[1]. The first
28. range in keypart 2 is then appended to stack[1] and
29. saved in stack[2]
30. - returns range "1:3:5"
31. - values in stack after this: stack[1, 1:3, 1:3:5]
32. 4) sel_arg_range_seq_next() is called the fourth time
33. - keypart 2 has another range, see 2)
34. - returns range "1:3:6"
35. - values in stack after this: stack[1, 1:3, 1:3:6]
Quick Read Plan 结构函数
1. /*
2. Table rows retrieval plan. Range optimizer creates QUICK_SELECT_I-derived
3. objects from table read plans.
4. */
5. class TABLE_READ_PLAN {
6. ......
7. }
9. /*
10. Plan for a QUICK_RANGE_SELECT scan.
11. TRP_RANGE::make_quick ignores retrieve_full_rows parameter because
12. QUICK_RANGE_SELECT doesn't distinguish between 'index only' scans and full
13. record retrieval scans.
14. */
16. class TRP_RANGE : public TABLE_READ_PLAN {
17. ......
18. SEL_ROOT *key;
19. ......
20. }
22. class TRP_ROR_INTERSECT : public TABLE_READ_PLAN {
23. ......
24. }
26. /*
27. Plan for QUICK_ROR_UNION_SELECT scan.
28. QUICK_ROR_UNION_SELECT always retrieves full rows, so retrieve_full_rows
29. is ignored by make_quick.
30. */
32. class TRP_ROR_UNION : public TABLE_READ_PLAN {
33. ......
34. }
36. /*
37. Plan for QUICK_INDEX_MERGE_SELECT scan.
38. QUICK_ROR_INTERSECT_SELECT always retrieves full rows, so retrieve_full_rows
39. is ignored by make_quick.
40. */
42. class TRP_INDEX_MERGE : public TABLE_READ_PLAN {
43. ......
44. }
46. /*
47. Plan for a QUICK_GROUP_MIN_MAX_SELECT scan.
48. */
50. class TRP_GROUP_MIN_MAX : public TABLE_READ_PLAN {
51. ......
52. }
54. /*
55. Plan for a QUICK_SKIP_SCAN_SELECT scan.
56. */
58. class TRP_SKIP_SCAN : public TABLE_READ_PLAN {
59. ......
60. }
TRP_RANGE::make_quick()是根据最优的Range查询计划，执行范围快速查询确定执行计划，生成对应的quick实例，QEP->quick = TRP_RANGE::make_quick()。
GDB分析工具
工具下载地址：https://github.com/cwang82566/mysql_debugging_tools
1. select * from tmp_sel_arg1 where (kp1=1 and kp2=2 and kp3=3) or (kp1=1 and kp2=2 and kp3=4) or (kp1=1 and kp2=3 and kp3=5) or (kp1=1 and kp2=3 and kp3=6);
2. (gdb) my st tree
3. $c0 (SEL_TREE *) 0x7f7cf040acd0 [type=SEL_TREE::KEY,keys.m_size=2]
4. |--$c1 (SEL_ROOT *) 0x7f7cf040add0 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=3]
5. | `--$c2 (SEL_ARG *) 0x7f7cf040b800 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
6. | | field = $c3 (Item_field *) 0x7f7cf04c1508 field = test.tmp_sel_arg1.kp1
7. | | equal = [ $c4 (Item_int *) 0x7f7cf04af718 value = 2 ]
8. | |--$c6 (SEL_ARG *) 0x7f7cf040ad50 [color=SEL_ARG::RED, is_asc=true, minflag=4 '\004', maxflag=8 '\b', part=0 '\000', selectivity=1]
9. | | | field = $c7 (Item_field *) 0x7f7cf04c0728 field = test.tmp_sel_arg1.kp1
10. | | | scope = ( -infinity, $c8 (Item_int *) 0x7f7cf04ae760 value = 1 )
11. | | `--$c11 (SEL_ROOT *) 0x7f7cf040b3d0 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=1]
12. | | `--$c12 (SEL_ARG *) 0x7f7cf040b350 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=1 '\001', selectivity=1]
13. | | | field = $c13 (Item_field *) 0x7f7cf04c0aa0 field = test.tmp_sel_arg1.kp2
14. | | | equal = [ $c14 (Item_int *) 0x7f7cf04aea80 value = 5 ]
15. | | `--$c18 (SEL_ROOT *) 0x7f7cf040aef8 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=2]
16. | | `--$c19 (SEL_ARG *) 0x7f7cf040ae78 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=2 '\002', selectivity=1]
17. | | | field = $c20 (Item_field *) 0x7f7cf04c0e18 field = test.tmp_sel_arg1.kp3
18. | | | equal = [ $c21 (Item_int *) 0x7f7cf04aef48 value = 10 ]
19. | | `--$c24 (SEL_ARG *) 0x7f7cf040b040 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=2 '\002', selectivity=1]
20. | | | field = $c25 (Item_field *) 0x7f7cf04c1190 field = test.tmp_sel_arg1.kp3
21. | | | equal = [ $c26 (Item_int *) 0x7f7cf04af268 value = 12 ]
22. | |--$c30 (SEL_ARG *) 0x7f7cf04370c8 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=0 '\000', selectivity=1]
23. | | | field = $c31 (Item_field *) 0x7f7cf04c1f70 field = test.tmp_sel_arg1.kp1
24. | | | equal = [ $c32 (Item_int *) 0x7f7cf04b0520 value = 3 ]
25. | | `--$c36 (SEL_ROOT *) 0x7f7cf040b9a0 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=2]
26. | | `--$c37 (SEL_ARG *) 0x7f7cf040b920 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=2 '\002', selectivity=1]
27. | | | field = $c38 (Item_field *) 0x7f7cf04c22e8 field = test.tmp_sel_arg1.kp3
28. | | | equal = [ $c39 (Item_int *) 0x7f7cf04b0840 value = 11 ]
29. | | `--$c42 (SEL_ARG *) 0x7f7cf040bae8 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=2 '\002', selectivity=1]
30. | | | field = $c43 (Item_field *) 0x7f7cf04c2660 field = test.tmp_sel_arg1.kp3
31. | | | equal = [ $c44 (Item_decimal *) 0x7f7cf04b0b60 value = 14 ]
32. | `--$c48 (SEL_ROOT *) 0x7f7cf040b4f0 [type=SEL_ROOT::Type::KEY_RANGE, use_count=1, elements=2]
33. | `--$c49 (SEL_ARG *) 0x7f7cf040b470 [color=SEL_ARG::BLACK, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=2 '\002', selectivity=1]
34. | | field = $c50 (Item_field *) 0x7f7cf04c1880 field = test.tmp_sel_arg1.kp3
35. | | equal = [ $c51 (Item_int *) 0x7f7cf04afa38 value = 11 ]
36. | `--$c54 (SEL_ARG *) 0x7f7cf040b638 [color=SEL_ARG::RED, is_asc=true, minflag=0 '\000', maxflag=0 '\000', part=2 '\002', selectivity=1]
37. | | field = $c55 (Item_field *) 0x7f7cf04c1bf8 field = test.tmp_sel_arg1.kp3
38. | | equal = [ $c56 (Item_int *) 0x7f7cf04afd58 value = 14 ]
39. `--$c60 (SEL_ROOT *) 0x0 Non
