【GreatSQL优化器-03】查询开销估算

一、cost和read_time介绍

GreatSQL的优化器在创建执行计划的时候是根据每张表的行数和数据分布以及读数据硬盘消耗等信息来判断先查询哪张表后查询哪张表，要不要使用索引，这些表资源信息就被称为cost，俗称为"开销"。在这之前已经执行了update_ref_and_keys（参考【GreatSQL优化器-02】）和extract_const_tables（参考【GreatSQL优化器-01】），拿到了const tables信息和表的keyuse_array索引信息，这里就开始计算单张表扫描的开销，做一个初步的估计，用来给后面的choose_table_order()搜索最佳表顺序提供原始数据信息。

优化器通过estimate_rowcount函数初步计算单表开销，这个函数最后会计算出3个重要的数据。

下面用一个简单的例子来说明这三个数字怎么查看：

greatsql> CREATE TABLE t1 (c1 INT PRIMARY KEY, c2 INT,date1 DATETIME);
greatsql> 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');
greatsql> CREATE TABLE t2 (cc1 INT PRIMARY KEY, cc2 INT);
greatsql> INSERT INTO t2 VALUES (1,3),(2,1),(3,2),(4,3),(5,15);
greatsql> CREATE INDEX idx1 ON t1(c2);
greatsql> CREATE INDEX idx2 ON t1(c2,date1);
greatsql> CREATE INDEX idx2_1 ON t2(cc2);
greatsql> SET optimizer_trace = 'enabled=ON' ;

greatsql> SELECT * FROM t2,t1,(select 10) t3 where t1.c1=t2.cc2;
+-----+------+----+------+---------------------+----+
| cc1 | cc2  | c1 | c2   | date1               | 10 |
+-----+------+----+------+---------------------+----+
|   3 |    2 |  2 |    1 | 2022-03-26 16:44:00 | 10 |
|   1 |    3 |  3 |    4 | 2023-03-27 16:44:00 | 10 |
|   4 |    3 |  3 |    4 | 2023-03-27 16:44:00 | 10 |
|   2 |    1 |  1 |   10 | 2021-03-25 16:44:00 | 10 |
+-----+------+----+------+---------------------+----+
> SELECT * FROM INFORMATION_SCHEMA.OPTIMIZER_TRACE;
          {
            "rows_estimation": [
              {
                "table": "`t2`",  -- 按照上面查询顺序t2放第一个
                "table_scan": {
                  "rows": 5, 因为t2非const表，因此这里显示的是所有行
                  "cost": 0.25, 这个是t2查询5条的开销，
                  "worst_seeks": 2 这里是另外加上去的，为了查看方便
                }
              },
              {
                "table": "`t1`", 按照上面查询顺序t1放第二个
                "table_scan": {
                  "rows": 4, 因为t1非const表，因此这里显示的是所有行
                  "cost": 0.25,
                  "worst_seeks": 2 这里是另外加上去的，为了查看方便
                }
              },
              {
                "table": " `t3`", 按照上面查询顺序t3放第三个
                "rows": 1,
                "cost": 1, ※这里有疑问，实际的read_time=worst_seeks=0.25，但是代码用了固定值1
                "worst_seeks": 0.25 这里是另外加上去的，为了查看方便
                "table_type": "system", 因为t3是const表，因此这里显示的system
                "empty": false
              }
            ]
          },

附表：代价系数

二、estimate_rowcount代码执行过程

实际代码执行过程如下，其中test_quick_select()函数在下面第三节介绍：

bool JOIN::make_join_plan() {
  if (estimate_rowcount()) return true;
}

bool JOIN::estimate_rowcount() {
        // 遍历每张表，计算每张表的上面3个值
        for (JOIN_TAB *tab = join_tab; tab < tab_end; tab++) {
            // 计算下面几个值
        tab->set_records(tab->found_records = tab->table()->file->stats.records);
        const Cost_estimate table_scan_time = tab->table()->file->table_scan_cost();
        tab->read_time = table_scan_time.total_cost();
        tab->worst_seeks =
            find_worst_seeks(tab->table(), tab->found_records, tab->read_time);
                // 这个函数是副功能，用于发现可能用于 GROUP BY 或 DISTINCT 查询的索引或可能用于 SKIP SCAN 的索引。
                // 主要给skip_scan_keys和const_keys添加可以用的索引
                add_loose_index_scan_and_skip_scan_keys(this, tab);
                // 如果上面计算得到的read_time<= 2.0那就不做快速查询test_quick_select()直接返回了，但是如果大于的话就要找是否有索引用快速查询来估算开销了。
                get_quick_record_count();
        }
}

上面涉及的参数值见下表。

三、计算单表cost举例说明

例子1：SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t2.cc1=t1.c1 or t1.c1=5;
          {
            "rows_estimation": [
              {
                "table": "`t1`",
                "range_analysis": {
                  "table_scan": {
                    "rows": 4,
                    "cost": 3.5 这里算出来的开销大于2了，因此要走test_quick_select()估算
                  },
                  "potential_range_indexes": [ 这里开始循环t1的所有索引，找出条件涉及的索引
                    {
                      "index": "PRIMARY", 条件涉及到了t1.c1，因此这里PRIMARY索引被使用
                      "usable": true,
                      "key_parts": [
                        "c1"
                      ]
                    },
                    {
                      "index": "idx1", 条件不涉及idx1，因此这里idx1索引不被使用
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "idx2", 条件不涉及idx2，因此这里idx2索引不被使用
                      "usable": false,
                      "cause": "not_applicable"
                    }
                  ],
                  "best_covering_index_scan": { 通过find_shortest_key()找到的最短的索引，指覆盖所有需要的数据的联合索引table->covering_keys
                    "index": "idx2", 这个值为table->covering_keys，联合索引包含了主键信息
                    "cost": 1.40548, 开销小于上面的最早算出来的3.5，因此被选择。这里io_cost=1.00548，cpu_cost=4行*0.1（读每行开销）
                    "chosen": true
                  },
                  "setup_range_conditions": [ 没有找到mm tree
                  ],
                  "group_index_range": { 不是GROUP语句
                    "chosen": false,
                    "cause": "not_single_table"
                  },
                  "skip_scan_range": { 没有配置skip_scan，不需要skip_scan
                    "chosen": false,
                    "cause": "not_single_table"
                  }
                }
              },
              {
                "table": "`t2`",
                "table_scan": {
                  "rows": 5,
                  "cost": 1 表t2算出来的开销小于2，因此不继续用快速查询计算了。
                }
              }
            ]
          },
-- t1选择索引 idx2，因为cost更小
-- t2的选择结果需要结合后面的choose_table_order()看，下一期再讲
greatsql> EXPLAIN SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t2.cc1=t1.c1 or t1.c1=5;
+----+-------------+-------+------------+-------+---------------+--------+---------+------+------+----------+---------------------------------------------------------+
| id | select_type | table | partitions | type  | possible_keys | key    | key_len | ref  | rows | filtered | Extra                                                   |
+----+-------------+-------+------------+-------+---------------+--------+---------+------+------+----------+---------------------------------------------------------+
|  1 | SIMPLE      | t1    | NULL       | index | PRIMARY       | idx2   | 11      | NULL |    4 |   100.00 | Using index                                             |                               这里选择了idx2索引扫描，跟上面算出来的结论一致
|  1 | SIMPLE      | t2    | NULL       | index | PRIMARY       | idx2_1 | 5       | NULL |    5 |   100.00 | Using where; Using index; Using join buffer (hash join) |
+----+-------------+-------+------------+-------+---------------+--------+---------+------+------+----------+---------------------------------------------------------+

看另一个例子：

例子2：SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t1.c1<5;
          {
            "rows_estimation": [
              {
                "table": "`t1`",
                "range_analysis": {
                  "table_scan": {
                    "rows": 4,
                    "cost": 3.5 这里算出来的开销大于2了，因此要走test_quick_select()估算
                  },
                  "potential_range_indexes": [
                    {
                      "index": "PRIMARY", 条件涉及到了t1.c1，因此这里PRIMARY索引被使用
                      "usable": true,
                      "key_parts": [
                        "c1"
                      ]
                    },
                    {
                      "index": "idx1", 条件不涉及idx1，因此这里idx1索引不被使用
                      "usable": false,
                      "cause": "not_applicable"
                    },
                    {
                      "index": "idx2", 条件不涉及idx2，因此这里idx2索引不被使用
                      "usable": false,
                      "cause": "not_applicable"
                    }
                  ],
                  "best_covering_index_scan": { 找到联合索引，包含了主键信息
                    "index": "idx2",
                    "cost": 1.40548,
                    "chosen": true
                  },
                  "setup_range_conditions": [
                  ],
                  "group_index_range": { 不是GROUP语句
                    "chosen": false,
                    "cause": "not_single_table"
                  },
                  "skip_scan_range": { 没有配置skip_scan，不需要skip_scan
                    "chosen": false,
                    "cause": "not_single_table"
                  },
                  "analyzing_range_alternatives": {
                    "range_scan_alternatives": [
                      {
                        "index": "PRIMARY", 根据get_best_group_min_max算出来的mm tree找到的最佳索引
                        "ranges": [
                          "c1 < 5"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": true,
                        "using_mrr": false,
                        "index_only": false,
                        "in_memory": 0,
                        "rows": 3, 范围扫描c1 < 5找到的符合的条数3条
                        "cost": 1.31293, 比上面算出来的cost低，因此被选择
                        "chosen": true
                      }
                    ],
                    "analyzing_roworder_intersect": {
                      "usable": false,
                      "cause": "too_few_roworder_scans" 因为tree->n_ror_scans < 2，所以没有被选择
                    }
                  },
                  "chosen_range_access_summary": { 总结上面所有计算的结果得出结论
                    "range_access_plan": {
                      "type": "range_scan", 结论是走索引范围扫描
                      "index": "PRIMARY",
                      "rows": 3,
                      "ranges": [
                        "c1 < 5"
                      ]
                    },
                    "rows_for_plan": 3, 找到3条数据
                    "cost_for_plan": 1.31293,
                    "chosen": true
                  }
                }
              },
              {
                "table": "`t2`",
                "range_analysis": {
                  "table_scan": {
                    "rows": 5,
                    "cost": 3.6 这里算出来的开销大于2了，因此要走test_quick_select()估算
                  },
                  "potential_range_indexes": [
                    {
                      "index": "PRIMARY", 涉及到主键列，因此用到了
                      "usable": true,
                      "key_parts": [
                        "cc1"
                      ]
                    },
                    {
                      "index": "idx2_1", 没有涉及cc2，因此没有用到
                      "usable": false,
                      "cause": "not_applicable"
                    }
                  ],
                  "best_covering_index_scan": { 找到的非唯一索引，开销比上面的小，被选择
                    "index": "idx2_1",
                    "cost": 1.50439,
                    "chosen": true
                  },
                  "setup_range_conditions": [
                  ],
                  "group_index_range": {
                    "chosen": false,
                    "cause": "not_single_table"
                  },
                  "skip_scan_range": {
                    "chosen": false,
                    "cause": "not_single_table"
                  },
                  "analyzing_range_alternatives": {
                    "range_scan_alternatives": [
                      {
                        "index": "PRIMARY",
                        "ranges": [
                          "cc1 < 5"
                        ],
                        "index_dives_for_eq_ranges": true,
                        "rowid_ordered": true,
                        "using_mrr": false,
                        "index_only": false,
                        "in_memory": 0,
                        "rows": 4, 根据cc1 < 5条件找到4条数据记录
                        "cost": 1.4133, 开销更小，被选择
                        "chosen": true
                      }
                    ],
                    "analyzing_roworder_intersect": {
                      "usable": false,
                      "cause": "too_few_roworder_scans"
                    }
                  },
                  "chosen_range_access_summary": { 总结上面所有计算的结果得出结论
                    "range_access_plan": {
                      "type": "range_scan",  结论是走索引范围扫描
                      "index": "PRIMARY",
                      "rows": 4,
                      "ranges": [
                        "cc1 < 5"
                      ]
                    },
                    "rows_for_plan": 4, 找到4条记录
                    "cost_for_plan": 1.4133,
                    "chosen": true
                  }
                }
              }
            ]
          },

-- 结论：t1表用了范围扫描，跟上面结论一致
-- t2的选择结果需要结合后面的best_access_path()看，下一期再讲
greatsql> EXPLAIN SELECT * FROM t1 join t2 ON t1.c1=t2.cc1 and t1.c1<5;
+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+
| id | select_type | table | partitions | type   | possible_keys | key     | key_len | ref       | rows | filtered | Extra       |
+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+
|  1 | SIMPLE      | t1    | NULL       | range  | PRIMARY       | PRIMARY | 4       | NULL      |    3 |   100.00 | Using where |                                    
|  1 | SIMPLE      | t2    | NULL       | eq_ref | PRIMARY       | PRIMARY | 4       | db1.t1.c1 |    1 |   100.00 | NULL        |
+----+-------------+-------+------------+--------+---------------+---------+---------+-----------+------+----------+-------------+

四、总结

从上面优化器最早的步骤我们认识了优化器的cost和计算方式，知道了如何初步估算单表的扫描cost并且按照最小cost选择最佳索引，这些单表估算出来的cost会在后面greedy_search（贪婪搜索）的时候用来做为计算依据，然后按照每张表的扫描开销对表进行排序，算出哪张表先扫描哪张表后扫描，最后得出最佳执行计划。

需要注意的是，上面的初步估算cost<=2的时候是不会进行后续快速扫描计算的，因此如果实际运用中想查看表的正确cost的话，需要根据当时表的实际数据量来做执行计划计算，而不是在空表或者数据量很小时候先做一次执行计划，然后用这个结果得出结论。