【GreatSQL优化器-17】DYNAMIC RANGE

【GreatSQL优化器-17】DYNAMIC RANGE

一、DYNAMIC RANGE介绍

GreatSQL 的优化器有一种扫描方式是动态范围扫描方式，类似于“已读乱回”模式，这种模式是在表有多个索引的情况下，对驱动表连接的时候部门选择索引的情况。优化器没有找到好的索引可以使用，但发现在知道前面表的列值后，大概会使用某些索引。对于前面表中的每个行组合，优化器查抄是否可以使用 range 或 index merge 访问方法来检索行。虽然这不是很快，但比执行完全没有索引的连接要快。
下面用一个简朴的例子来说明直方图怎么应用在优化器。

1. CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
2. INSERT INTO t1 VALUES (1,10,'2021-03-25 16:44:00.123456'),(2,1,'2022-03-26 16:44:00.123456'),(3,4,'2023-03-27 16:44:00.123456'),(5,5,'2024-03-25 16:44:00.123456'),(7,null,'2020-03-25 16:44:00.123456'),(8,10,'2020-10-25 16:44:00.123456'),(11,16,'2023-03-25 16:44:00.123456');
3. CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
4. INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
5. CREATE TABLE t3 (ccc1 INT, ccc2 varchar(100));
6. INSERT INTO t3 VALUES (1,'aa1'),(2,'bb1'),(3,'cc1'),(4,'dd1'),(null,'ee');
7. CREATE INDEX idx1 ON t1(c2);
8. CREATE INDEX idx2 ON t1(c2,date1);
9. CREATE INDEX idx2_1 ON t2(cc2);
10. CREATE INDEX idx3_1 ON t3(ccc1);
12. greatsql> EXPLAIN SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t1.c2<5;
13. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
14. | id | select_type | table | partitions | type | possible_keys     | key  | key_len | ref  | rows | filtered | Extra                                          |
15. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
16. |  1 | SIMPLE      | t3    | NULL       | ALL  | idx3_1            | NULL | NULL    | NULL |    5 |   100.00 | NULL                                           |
17. |  1 | SIMPLE      | t1    | NULL       | ALL  | PRIMARY,idx1,idx2 | NULL | NULL    | NULL |    7 |    43.67 | Range checked for each record (index map: 0x7) |
18. -- 这里的结果出现了Range checked，说明进行了DYNAMIC_RANGE
19. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
21. greatsql> SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t1.c2<5;
22. +----+------+---------------------+------+------+
23. | c1 | c2   | date1               | ccc1 | ccc2 |
24. +----+------+---------------------+------+------+
25. |  1 |   10 | 2021-03-25 16:44:00 |    1 | aa1  |
26. |  2 |    1 | 2022-03-26 16:44:00 |    1 | aa1  |
27. |  3 |    4 | 2023-03-27 16:44:00 |    1 | aa1  |
28. |  2 |    1 | 2022-03-26 16:44:00 |    2 | bb1  |
29. |  3 |    4 | 2023-03-27 16:44:00 |    2 | bb1  |
30. |  2 |    1 | 2022-03-26 16:44:00 |    3 | cc1  |
31. |  3 |    4 | 2023-03-27 16:44:00 |    3 | cc1  |
32. |  2 |    1 | 2022-03-26 16:44:00 |    4 | dd1  |
33. |  3 |    4 | 2023-03-27 16:44:00 |    4 | dd1  |
34. |  2 |    1 | 2022-03-26 16:44:00 | NULL | ee   |
35. |  3 |    4 | 2023-03-27 16:44:00 | NULL | ee   |
36. +----+------+---------------------+------+------+
38. greatsql> SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE;
39.              "attaching_conditions_to_tables": {
40.               "original_condition": "((`t1`.`c1` = `t3`.`ccc1`) or (`t1`.`c2` < 5))",
41.               "attached_conditions_computation": [
42.                 {
43.                   "table": "`t1`",
44.                   "rechecking_index_usage": { -- 这里对t1进行了recheck
45.                     "recheck_reason": "not_first_table",
46.                     "range_analysis": {
47.                       "table_scan": {
48.                         "rows": 7,
49.                         "cost": 3.05
50.                       },
51.                       "potential_range_indexes": [
52.                         {
53.                           "index": "PRIMARY",
54.                           "usable": true,
55.                           "key_parts": [
56.                             "c1"
57.                           ]
58.                         },
59.                         {
60.                           "index": "idx1",
61.                           "usable": true,
62.                           "key_parts": [
63.                             "c2",
64.                             "c1"
65.                           ]
66.                         },
67.                         {
68.                           "index": "idx2",
69.                           "usable": true,
70.                           "key_parts": [
71.                             "c2",
72.                             "date1",
73.                             "c1"
74.                           ]
75.                         }
76.                       ],
77.                       "best_covering_index_scan": {
78.                         "index": "idx2",
79.                         "cost": 0.952742,
80.                         "chosen": true
81.                       },
82.                       "setup_range_conditions": [
83.                       ],
84.                       "group_index_range": {
85.                         "chosen": false,
86.                         "cause": "not_single_table"
87.                       },
88.                       "skip_scan_range": {
89.                         "chosen": false,
90.                         "cause": "not_single_table"
91.                       },
92.                       "analyzing_range_alternatives": {
93.                         "range_scan_alternatives": [
94.                         ],
95.                         "analyzing_roworder_intersect": {
96.                           "usable": false,
97.                           "cause": "too_few_roworder_scans"
98.                         }
99.                       },
100.                       "analyzing_index_merge_union": [
101.                         {
102.                           "indexes_to_merge": [
103.                             {
104.                               "range_scan_alternatives": [
105.                                 {
106.                                   "index": "PRIMARY",
107.                                   "chosen": false,
108.                                   "cause": "depends_on_unread_values"
109.                                 }
110.                               ],
111.                               "chosen": false,
112.                               "cause": "cost"
113.                             },
114.                             {
115.                               "range_scan_alternatives": [
116.                                 {
117.                                   "index": "idx1",
118.                                   "ranges": [
119.                                     "NULL < c2 < 5"
120.                                   ],
121.                                   "index_dives_for_eq_ranges": true,
122.                                   "rowid_ordered": false,
123.                                   "using_mrr": false,
124.                                   "index_only": true,
125.                                   "in_memory": 1,
126.                                   "rows": 2,
127.                                   "cost": 0.460274,
128.                                   "chosen": true
129.                                 },
130.                                 {
131.                                   "index": "idx2",
132.                                   "ranges": [
133.                                     "NULL < c2 < 5"
134.                                   ],
135.                                   "index_dives_for_eq_ranges": true,
136.                                   "rowid_ordered": false,
137.                                   "using_mrr": false,
138.                                   "index_only": true,
139.                                   "in_memory": 1,
140.                                   "rows": 2,
141.                                   "cost": 0.460457,
142.                                   "chosen": false,
143.                                   "cause": "cost"
144.                                 }
145.                               ],
146.                               "chosen": false,
147.                               "cause": "cost"
148.                             }
149.                           ],
150.                           "cost_of_reading_ranges": 0,
151.                           "chosen": false,
152.                           "cause": "cost"
153.                         }
154.                       ]
155.                     }
156.                   }
157.                 }
158.               ],
159.               "attached_conditions_summary": [
160.                 {
161.                   "table": "`t3`",
162.                   "attached": null
163.                 },
164.                 {
165.                   "table": "`t1`",
166.                   "attached": "((`t1`.`c1` = `t3`.`ccc1`) or (`t1`.`c2` < 5))"
167.                 }
168.               ]
169.             }
170.      "join_execution": {
171.         "select#": 1,
172.         "steps": [
173.           {
174.             "rows_estimation_per_outer_row": { -- 这里只截取t3读第一行时候t1的索引选择
175.               "table": "`t1`",
176.               "range_analysis": {
177.                 "table_scan": {
178.                   "rows": 7,
179.                   "cost": 3.05
180.                 },
181.                 "potential_range_indexes": [
182.                   {
183.                     "index": "PRIMARY",
184.                     "usable": true,
185.                     "key_parts": [
186.                       "c1"
187.                     ]
188.                   },
189.                   {
190.                     "index": "idx1",
191.                     "usable": true,
192.                     "key_parts": [
193.                       "c2",
194.                       "c1"
195.                     ]
196.                   },
197.                   {
198.                     "index": "idx2",
199.                     "usable": true,
200.                     "key_parts": [
201.                       "c2",
202.                       "date1",
203.                       "c1"
204.                     ]
205.                   }
206.                 ],
207.                 "best_covering_index_scan": {
208.                   "index": "idx2",
209.                   "cost": 0.952742,
210.                   "chosen": true
211.                 },
212.                 "setup_range_conditions": [
213.                 ],
214.                 "group_index_range": {
215.                   "chosen": false,
216.                   "cause": "not_single_table"
217.                 },
218.                 "skip_scan_range": {
219.                   "chosen": false,
220.                   "cause": "not_single_table"
221.                 },
222.                 "analyzing_range_alternatives": {
223.                   "range_scan_alternatives": [
224.                   ],
225.                   "analyzing_roworder_intersect": {
226.                     "usable": false,
227.                     "cause": "too_few_roworder_scans"
228.                   }
229.                 },
230.                 "analyzing_index_merge_union": [
231.                   {
232.                     "indexes_to_merge": [
233.                       {
234.                         "range_scan_alternatives": [
235.                           {
236.                             "index": "PRIMARY",
237.                             "ranges": [
238.                               "c1 = 1"
239.                             ],
240.                             "index_dives_for_eq_ranges": true,
241.                             "rowid_ordered": true,
242.                             "using_mrr": false,
243.                             "index_only": true,
244.                             "in_memory": 1,
245.                             "rows": 1,
246.                             "cost": 0.36,
247.                             "chosen": true
248.                           }
249.                         ],
250.                         "index_to_merge": "PRIMARY",
251.                         "cumulated_cost": 0.36
252.                       },
253.                       {
254.                         "range_scan_alternatives": [
255.                           {
256.                             "index": "idx1",
257.                             "ranges": [
258.                               "NULL < c2 < 5"
259.                             ],
260.                             "index_dives_for_eq_ranges": true,
261.                             "rowid_ordered": false,
262.                             "using_mrr": false,
263.                             "index_only": true,
264.                             "in_memory": 1,
265.                             "rows": 2,
266.                             "cost": 0.460274,
267.                             "chosen": true
268.                           },
269.                           {
270.                             "index": "idx2",
271.                             "ranges": [
272.                               "NULL < c2 < 5"
273.                             ],
274.                             "index_dives_for_eq_ranges": true,
275.                             "rowid_ordered": false,
276.                             "using_mrr": false,
277.                             "index_only": true,
278.                             "in_memory": 1,
279.                             "rows": 2,
280.                             "cost": 0.460457,
281.                             "chosen": false,
282.                             "cause": "cost"
283.                           }
284.                         ],
285.                         "index_to_merge": "idx1",
286.                         "cumulated_cost": 0.820274
287.                       }
288.                     ],
289.                     "cost_of_reading_ranges": 0.820274,
290.                     "cost_of_mapping_rowid_in_non_clustered_pk_scan": 0.1,
291.                     "cost_sort_rowid_and_read_disk": 0.4375,
292.                     "use_roworder_index_merge": true, -- 根据上面结果选择了主键合并idx1的结果
293.                     "cause": "cost"
294.                   }
295.                 ]
296.               }
297.             }
298.           },
300. greatsql> EXPLAIN SELECT * FROM t1 join t3 ON t1.c1=t3.ccc1 or t1.c2<5;
301. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
302. | id | select_type | table | partitions | type | possible_keys     | key  | key_len | ref  | rows | filtered | Extra                                          |
303. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
304. |  1 | SIMPLE      | t3    | NULL       | ALL  | idx3_1            | NULL | NULL    | NULL |    5 |   100.00 | NULL                                           |
305. |  1 | SIMPLE      | t1    | NULL       | ALL  | PRIMARY,idx1,idx2 | NULL | NULL    | NULL |    7 |    42.85 | Range checked for each record (index map: 0x7) | -- 这里0x7指的是t1表的3条索引
306. +----+-------------+-------+------------+------+-------------------+------+---------+------+------+----------+------------------------------------------------+
308. -- 驱动表t3一共5条数据，每行记录都进行了一次test_quick_select()来查找t1是否有可用的更优索引

复制代码

表一：必要举行 recheck 的原因
场景条件非join表连接的第一张表存在针对这张表的条件连接的第一张表没有第一张表的列与常量值的比较，limit值小于预估的满足条件的行数表二：quick_type 范例
范例说明QS_NONE不使用快速扫描QS_RANGE使用范围扫描QS_DYNAMIC_RANGE使用动态范围表三：表用 QS_DYNAMIC_RANGE 的场合
条件(以下必须全部满足)说明条件列存在索引有机会天生mm treekeyuse_array数组没有值有值的话执行REF扫描，一般有OR条件时候导致该数组没有值表没有对应的mm tree无法天生mm tree的条件这张表不是join连接的第一张表对表执行recheckrecheck的原因见表一recheck以后天生AccessPath但是找到的范围老手数大于等于100行三、实际例子说明

接下来看几个例子来说明上面的代码：

1. static bool make_join_query_block(JOIN *join, Item *cond) {
2.         // 满足以下条件的需要进行RECHECK，要么是非第一张表要么是有limit语句
3.         if ((tab->type() == JT_ALL || tab->type() == JT_RANGE ||
4.              tab->type() == JT_INDEX_MERGE || tab->type() == JT_INDEX_SCAN) &&
5.             tab->use_quick != QS_RANGE) {
6.           if (cond &&                              // 1a
7.               (tab->keys() != tab->const_keys) &&  // 1b
8.               (i > 0 ||                            // 1c
9.                (join->query_block->master_query_expression()->item &&
10.                 cond->is_outer_reference())))
11.             recheck_reason = NOT_FIRST_TABLE;
12.           else if (!tab->const_keys.is_clear_all() &&  // 2a
13.                    i == join->const_tables &&          // 2b
14.                    (join->query_expression()->select_limit_cnt <
15.                     (tab->position()->rows_fetched *
16.                      tab->position()->filter_effect)) &&  // 2c
17.                    !join->calc_found_rows)                // 2d
18.             recheck_reason = LOW_LIMIT;
20.         // 满足这个if条件的执行QS_DYNAMIC_RANGE，详情见下面几张表
21.           if (!tab->table()->quick_keys.is_subset(tab->checked_keys) ||
22.               !tab->needed_reg.is_subset(tab->checked_keys)) {
23.             tab->keys().merge(tab->table()->quick_keys);
24.             tab->keys().merge(tab->needed_reg);
25.             if (!tab->needed_reg.is_clear_all() &&
26.                 (tab->table()->quick_keys.is_clear_all() ||
27.                  (tab->range_scan() &&
28.                   (tab->range_scan()->num_output_rows() >= 100.0)))) {
29.               tab->use_quick = QS_DYNAMIC_RANGE;
30.               tab->set_type(JT_ALL);
31.             } else
32.               tab->use_quick = QS_RANGE;
33.           }
34.         }
35. }
36. // 实际使用代码
37. bool DynamicRangeIterator::Init() {
38.   // 每次迭代器开始的时候先获取最佳索引组合和AccessPath
39.   AccessPath *range_scan;
40.   int rc = test_quick_select(&range_scan);
41. }

复制代码

四、总结

从上面关于 DYNAMIC RANGE 的解释我们知道这个状态必要经过一系列判断，并且只在特定条件才有大概出现，但是每行举行一次索引判断照旧很消耗资源的，最好照旧直接走索引，以是要只管避免这种情况，适当的时候可以举行 SQL 下令干预。

Enjoy GreatSQL
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。