【GreatSQL优化器-10】find_best_ref

【GreatSQL优化器-10】find_best_ref

一、find_best_ref介绍

GreatSQL的优化器对于join的表需要根据行数和cost来确定末了哪张表先实行哪张表后实行，这内里就涉及到预估满足条件的表数据，在keyuse_array数组有值的情况下，会用find_best_ref函数来通过索引进行cost和rows的估计，并且会找出最优的索引。这样就可能不会继承用后面的calculate_scan_cost()进行全表扫描盘算cost，可以节省查询时间。
这个功能是对之前【优化器05-条件过滤】的补充功能，二者有可能一起用，也有可能只选择一种盘算，要看具体条件。
下面用一个简单的例子来阐明find_best_ref函数获得的结果。

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> SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t1.c2<5;
13.           {
14.             "ref_optimizer_key_uses": [ 首先这里要有keyuse_array
15.               {
16.                 "table": "`t1`",
17.                 "field": "c1",
18.                 "equals": "`t2`.`cc1`",
19.                 "null_rejecting": true
20.               },
21.               {
22.                 "table": "`t2`",
23.                 "field": "cc1",
24.                 "equals": "`t1`.`c1`",
25.                 "null_rejecting": true
26.               }
27.             ]
28.           },
29.             "considered_execution_plans": [
30.               {
31.                 "plan_prefix": [
32.                 ],
33.                 "table": "`t1`",
34.                 "best_access_path": {
35.                   "considered_access_paths": [
36.                     {
37.                       "access_type": "ref",
38.                       "index": "PRIMARY",
39.                       "usable": false,
40.                       "chosen": false
41.                     },
42.                     {
43.                       "rows_to_scan": 2,
44.                       "filtering_effect": [
45.                       ],
46.                       "final_filtering_effect": 1,
47.                       "access_type": "range",
48.                       "range_details": {
49.                         "used_index": "idx2"
50.                       },
51.                       "resulting_rows": 2,
52.                       "cost": 0.660457,
53.                       "chosen": true
54.                     }
55.                   ]
56.                 },
57.                 "condition_filtering_pct": 100,
58.                 "rows_for_plan": 2,
59.                 "cost_for_plan": 0.660457,
60.                 "rest_of_plan": [
61.                   {
62.                     "plan_prefix": [
63.                       "`t1`"
64.                     ],
65.                     "table": "`t2`",
66.                     "best_access_path": {
67.                       "considered_access_paths": [
68.                         {
69.                           "access_type": "eq_ref",
70.                           "index": "PRIMARY",
71.                           "rows": 1, 这里就是通过find_best_ref()获得的结果
72.                           "cost": 0.7, 这里就是通过find_best_ref()获得的结果
73.                           "chosen": true,
74.                           "cause": "clustered_pk_chosen_by_heuristics"
75.                         },
76.                         {
77.                           "access_type": "scan",
78.                           "chosen": false,
79.                           "cause": "covering_index_better_than_full_scan"
80.                         }
81.                       ]
82.                     },
83.                     "condition_filtering_pct": 100,
84.                     "rows_for_plan": 2,
85.                     "cost_for_plan": 1.36046,
86.                     "chosen": true
87.                   }
88.                 ]
89.               },
90.               {
91.                 "plan_prefix": [
92.                 ],
93.                 "table": "`t2`",
94.                 "best_access_path": {
95.                   "considered_access_paths": [
96.                     {
97.                       "access_type": "ref",
98.                       "index": "PRIMARY",
99.                       "usable": false,
100.                       "chosen": false
101.                     },
102.                     {
103.                       "rows_to_scan": 5,
104.                       "filtering_effect": [
105.                       ],
106.                       "final_filtering_effect": 1,
107.                       "access_type": "scan",
108.                       "resulting_rows": 5,
109.                       "cost": 0.75,
110.                       "chosen": true
111.                     }
112.                   ]
113.                 },
114.                 "condition_filtering_pct": 100,
115.                 "rows_for_plan": 5,
116.                 "cost_for_plan": 0.75,
117.                 "rest_of_plan": [
118.                   {
119.                     "plan_prefix": [
120.                       "`t2`"
121.                     ],
122.                     "table": "`t1`",
123.                     "best_access_path": {
124.                       "considered_access_paths": [
125.                         {
126.                           "access_type": "eq_ref",
127.                           "index": "PRIMARY",
128.                           "rows": 1, 这里就是通过find_best_ref()获得的结果
129.                           "cost": 5.5, 这里就是通过find_best_ref()获得的结果
130.                           "chosen": true,
131.                           "cause": "clustered_pk_chosen_by_heuristics"
132.                         },
133.                         {
134.                           "rows_to_scan": 2,
135.                           "filtering_effect": [
136.                           ],
137.                           "final_filtering_effect": 1,
138.                           "access_type": "range",
139.                           "range_details": {
140.                             "used_index": "idx2"
141.                           },
142.                           "resulting_rows": 2,
143.                           "cost": 3.30229,
144.                           "chosen": true
145.                         }
146.                       ]
147.                     },
148.                     "condition_filtering_pct": 100,
149.                     "rows_for_plan": 10,
150.                     "cost_for_plan": 4.05229,
151.                     "pruned_by_cost": true
152.                   }
153.                 ]
154.               }
155.             ]

复制代码

表：接纳的rows和cost结果
接纳的rows和cost结果场景(以下任一个条件满足)find_best_ref()的结果find_best_ref()方式找到的行数和cost都小于之前estimate_rowcount盘算的值生成了mm tree并且找到最优索引，并且range_scan()->type结果为ROWID_INTERSECTION没有生成mm tree但是找到最优索引force index方式calculate_scan_cost()的结果以上都不满足表：find_best_ref函数获得的结果
函数结果阐明值cur_fanout总共需要读取多少行盘算方式见表一cur_read_cost读的开销盘算方式见表二best_refcost最低的索引索引优先级见表五表一：cur_fanout盘算方式
场景值阐明唯一索引1索引覆盖全部涉及列并且条件是列等于常量table->quick_keys有值table->quick_rowstable->quick_keys无值tab->records() / distinct_keys_estdistinct_keys_est表示的是一张表对应一个索引值的行数有几行，盘算方式见表三索引覆盖全部涉及列并且条件不是列等于常量keyinfo->has_records_per_key()keyinfo->records_per_key盘算方式见表四!keyinfo->has_records_per_key()((double)tab->records() / (double)distinct_keys_est * (1.0 + ((double)(table->s->max_key_length - keyinfo->key_length) / (double)table->s->max_key_length))); if (cur_fanout < 2.0) cur_fanout = 2.0索引不能覆盖全部涉及列并且条件是列等于常量table->quick_rows索引不能覆盖全部涉及列并且条件不是列等于常量当前用的索引keyinfo->has_records_per_key()keyinfo->records_per_keyrecords_per_key表示的是一张表对应一个索引值的行数有几行，盘算方式见表四当前用的索引没有keyinfo->has_records_per_key()(x * (b-a) + a*c-b)/(c-1)b = records matched by whole key a = records matched by first key part c = number of key parts in key x = used key parts (1 page_read_cost(1.0)索引覆盖全部涉及列prefix_rowcount * find_cost_for_ref(thd, table, key, cur_fanout, tab->worst_seeks)索引不能覆盖全部涉及列prefix_rowcount * find_cost_for_ref(thd, table, key, cur_fanout, tab->worst_seeks)表三：distinct_keys_est盘算方式
场景值初始值tab->records() / 10distinct_keys_est > keyuse->ref_table_rowskeyuse->ref_table_rowsdistinct_keys_est < 1010tab->records() < distinct_keys_esttab->records()

注：10是MATCHING_ROWS_IN_OTHER_TABLE

表四：keyuse->ref_table_rows盘算方式
keyuse->used_tables场景值PSEUDO_TABLE_BITS只有一张表max(tmp_table->file->stats.records, 100) 这里100是固定值OUTER_REF_TABLE_BIT有子查询的话只有一行满足1

注：通过JOIN:ptimize_keyuse()函数获得

表五：索引类型选择优先级
idx_type优先级阐明对应的access_typeCLUSTERED_PK最高primary key,优先级最高eq_refUNIQUE高唯一索引eq_refNOT_UNIQUE低非唯一索引refFULLTEXT最低fulltext索引，优先级最低ref三、实际例子阐明

接下来看一开始的例子来阐明上面的代码：
[code]greatsql> SELECT * FROM t1 JOIN t2 ON t1.c1=t2.cc1 AND t1.c2 SELECT * FROM t1 JOIN t2 JOIN t3 ON t1.c1=t2.cc1 AND t3.ccc1=t2.cc1 AND t1.c2