@code
procedure greedy_search
input: remaining_tables
output: pplan;
{
pplan = <>;
do {
(t, a) = best_extension(pplan, remaining_tables);
pplan = concat(pplan, (t, a));
remaining_tables = remaining_tables - t;
} while (remaining_tables != {})
return pplan;
}
4. best_extension_by_limited_search ->
a) 从 join_tables 的 remain_tables 中选择一个 table 加入 pplan,目标使得整体 pplan
的开销最小
5. best_access_path ->
a) 若为单表,计算单表的全表扫描代价。
b) 若为多表,计算当前选择表的扫描代价。
6. make_join_readinfo -> pick_table_access_method -> tab->index = find_shortest_key(table, &
table->covering_keys) -> tab->read_first_record = join_read_first -> tab->type = JT_NEXT ->
a) 索引覆盖扫描路径优化。若当前为全表扫描,同时存在一个或多个可以进行索引覆
盖扫描的查询,那么优先选择索引覆盖扫描。
i. 原理:针对 Innodb 引擎,索引覆盖扫描一定要优于全表扫描
ii.
b) 对于单表扫描,步骤 0 确定是否可以选择索引。步骤 5 返回全表扫描开销。步骤 6
主要处理 index coverage scan 的部分优化。
c) 在函数 find_shortest_key 中,选择合适的索引,for index coverage scan。
i. 索引必须包含 scan 键值?
ii. 索引列的 key_length 最小?
3.1.1 records_in_range 函数分析
records_in_range -> btr_estimage_n_rows_in_range ->
tuple1 = min value in range scan,range scan 的范围起始值
btr_cur_search_to_nth_level(index, tuple1, &cursor) ->
tuple2 = max value in range scan,range scan 的范围终止值
btr_cur_search_to_nth_level(index, tuple2, &cursor) ->
根据起始值与终止值,做两次 search path,确定 index path,存储在 cursor 中我们
有了起始值与终止值的两个 path,起始值与终止值所对应的索引叶节点如何根据两个
叶节点计算叶节点范围内的数据量(records in range),想法如下:
1. 计算出两个叶节点间,包含多少个索引页,记为 n (n leaf pages in range)
2. 计算索引页平均包含多少个索引项,记为 r (records per leaf page)
3. 那么,records in range = n * r