数据库内核月报－ 2019/02 - MySQL · 源码分析 · 8.0 Functional index的实现过程 - 《数据库内核月报》

MySQL从8.0.13开始支持functional index。Functional index类似于ORACLE的Function-Based Indexes。该索引可以根据将索引定义的表达式的值按照索引顺序存到索引里，进而减少表达式的计算，加速查询。

下面我们看一下如何创建一个functional index：


1. CREATE TABLE t1 (col1 INT, col2 INT, INDEX func_index ((ABS(col1))));
2. CREATE INDEX idx1 ON t1 ((col1 + col2));
3. CREATE INDEX idx2 ON t1 ((col1 + col2), (col1 - col2), col1);
4. ALTER TABLE t1 ADD INDEX ((col1 * 40) DESC);

接下来我们继续看一下functional index的效果：


1. mysql> CREATE TABLE t1 (col1 INT, col2 INT);
2. Query OK, 0 rows affected (0.13 sec)

4. mysql> SELECT * FROM t1 WHERE col1+col2 > 10;
5. Empty set (0.01 sec)

7. mysql> EXPLAIN SELECT * FROM t1 WHERE col1+col2 > 10;
8. +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
9. | id | select_type | table | partitions | type | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
10. +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
11. |  1 | SIMPLE      | t1    | NULL       | ALL  | NULL          | NULL | NULL    | NULL |    1 |   100.00 | Using where |
12. +----+-------------+-------+------------+------+---------------+------+---------+------+------+----------+-------------+
13. 1 row in set, 1 warning (0.01 sec)

15. mysql> CREATE INDEX idx1 ON t1 ((col1 + col2));
16. Query OK, 0 rows affected (0.14 sec)
17. Records: 0  Duplicates: 0  Warnings: 0

19. mysql> EXPLAIN SELECT * FROM t1 WHERE col1+col2 > 10;
20. +----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-------------+
21. | id | select_type | table | partitions | type  | possible_keys | key  | key_len | ref  | rows | filtered | Extra       |
22. +----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-------------+
23. |  1 | SIMPLE      | t1    | NULL       | range | idx1          | idx1 | 9       | NULL |    1 |   100.00 | Using where |
24. +----+-------------+-------+------------+-------+---------------+------+---------+------+------+----------+-------------+
25. 1 row in set, 1 warning (0.00 sec)

从上面的例子中我们可以看到查询中使用了functional索引 idx1来加速查询。

MySQL的functinal index是利用generated column来辅助实现的，后面的章节中我们会详细的进行分析。所以对于创建functional index的一些限制可以参考：创建generated column 以及增加generated column。

下面我们从源码来看一下MySQL functional index的实现过程。

上面的流程图是MySQL创建functional index的一个基本流程。我们重点看一下add_functional_index_to_create_list这个函数的处理过程。


1. /**
2. Prepares a functional index by adding a hidden indexed generated column for the key part.

4. A functional index is implemented as a hidden generated column over the
5. expression specified in the index, and the hidden generated column is then indexed. This function adds a hidden generated column to the Create_list, and updates the key specification to point to this new column. The generated column is given a name that is a hash of the key name and the key part number.
6. */
7. static bool add_functional_index_to_create_list(THD *thd,
8. Key_spec *key_spec,
9. Alter_info *alter_info,
10. Key_part_spec *kp,
11. uint key_part_number,
12. HA_CREATE_INFO *create_info) {
13. // A functional index cannot be a primary key
14. /* 这里限制了functional index 不能作为主键，因为它是个generated column */
15. if (key_spec->type == KEYTYPE_PRIMARY) {
16. my_error(ER_FUNCTIONAL_INDEX_PRIMARY_KEY, MYF(0));
17. return true;
18. }

20. // If the key isn't given a name explicitly by the user, we must auto-generate
21. // a name here. "Normal" indexes will be given a name in prepare_key(), but
22. // that is too late for functional indexes since we want the hidden generated
23. // column name to be based on the index name.
24. // 生成一个默认的索引名称
25. if (key_spec->name.str == nullptr) {
26. std::string key_name;
27. int count = 2;
28. key_name.assign("functional_index");
29. while (key_name_exists(alter_info->key_list, key_name, nullptr)) {
30. key_name.assign("functional_index_");
31. key_name.append(std::to_string(count++));
32. }

34. key_spec->name.length = key_name.size();
35. key_spec->name.str = strmake_root(thd->stmt_arena->mem_root,
36. key_name.c_str(), key_name.size());
37. } else {    if (key_name_exists(alter_info->key_list,
38. {key_spec->name.str, key_spec->name.length},
39. key_spec)) {
40. my_error(ER_DUP_KEYNAME, MYF(0), key_spec->name.str);
41. return true;
42. }
43. }

45. // First we need to resolve the expression in the functional index so that we
46. // know the correct collation, data type, length etc...
47. ulong saved_privilege = thd->want_privilege;
48. thd->want_privilege = SELECT_ACL;

50. {
51. // Create a scope guard so that we are guaranteed that the privileges are
52. // set back to the original value.
53. auto handler_guard = create_scope_guard(
54. [thd, saved_privilege]() { thd->want_privilege = saved_privilege; });

56. Functional_index_error_handler error_handler(
57. {key_spec->name.str, key_spec->name.length}, thd);

59. Item *expr = kp->get_expression();
60. if (expr->type() == Item::FIELD_ITEM) {
61. my_error(ER_FUNCTIONAL_INDEX_ON_FIELD, MYF(0));
62. return true;
63. }
64. // 这里验证表达式的合法性，是否违反generated column的约束条件
65. if (pre_validate_value_generator_expr(kp->get_expression(),
66. key_spec->name.str, true)) {
67. return true;
68. }

70. Replace_field_processor_arg replace_field_argument(
71. thd, &alter_info->create_list, create_info, key_spec->name.str);
72. if (expr->walk(&Item::replace_field_processor, Item::WALK_PREFIX,
73. reinterpret_cast<uchar *>(&replace_field_argument))) {
74. return true;
75. }

77. if (kp->resolve_expression(thd)) return true;
78. }

80. // 默认隐式列生成一个名字
81. const char *field_name = make_functional_index_column_name(
82. {key_spec->name.str, key_spec->name.length}, key_part_number,
83. thd->stmt_arena->mem_root);

85. Item *item = kp->get_expression();

87. // Ensure that we aren't trying to index a field
88. DBUG_ASSERT(item->type() != Item::FIELD_ITEM);  TABLE tmp_table;
89. TABLE_SHARE share;
90. tmp_table.s = &share;
91. init_tmp_table_share(thd, &share, "", 0, "", "", nullptr);

93. tmp_table.s->db_create_options = 0;
94. tmp_table.s->db_low_byte_first = false;
95. tmp_table.set_not_started();
96. // 生成generated column的创建信息
97. Create_field *cr = generate_create_field(thd, item, &tmp_table);
98. if (cr == nullptr) {
99. return true; /* purecov: deadcode */
100. }

102. if (is_blob(cr->sql_type)) {
103. my_error(ER_FUNCTIONAL_INDEX_ON_LOB, MYF(0));
104. return true;
105. }

107. cr->field_name = field_name;
108. cr->field = nullptr;
109. cr->hidden = dd::Column::enum_hidden_type::HT_HIDDEN_SQL;
110. cr->stored_in_db = false;

112. Value_generator *gcol_info = new (thd->mem_root) Value_generator();
113. gcol_info->expr_item = kp->get_expression();
114. // 生成一个virtual generated column
115. gcol_info->set_field_stored(false);
116. gcol_info->set_field_type(cr->sql_type);  cr->gcol_info = gcol_info;
117. alter_info->create_list.push_back(cr);
118. alter_info->flags |= Alter_info::ALTER_ADD_COLUMN;

120. // 这里将KEY的索引列设置为隐式generated column
121. kp->set_name_and_prefix_length(field_name, 0);
122. return false;
123. }

函数的注释里面说的非常详细，functional index的创建过程依赖于generated column来做辅助。创建functional index的时候都要隐式的创建一个generated column，然后在该generated column上创建对应的索引。

上面我们看到了源码中是如何创建一个functional index。那么接下来我们继续看一下MySQL是如何为查询寻找合适的functional index的。

就拿上面的例子看一下调用堆栈：


1. EXPLAIN SELECT * FROM t1 WHERE col1+col2 > 10;

3. #0  substitute_gc (thd=0x2aab94000be0, select_lex=0x2aab94270298, where_cond=0x2aab94271ec8, group_list=0x0, order=0x0)
4. #1  0x0000000003049283 in JOIN::optimize (this=0x2aab94272750)
5. #2  0x0000000003165c32 in SELECT_LEX::optimize (this=0x2aab94270298, thd=0x2aab94000be0)
6. #3  0x000000000316221c in Sql_cmd_dml::execute_inner (this=0x2aab94272078, thd=0x2aab94000be0)
7. #4  0x00000000031614d3 in Sql_cmd_dml::execute (this=0x2aab94272078, thd=0x2aab94000be0)
8. #5  0x00000000030a7396 in mysql_execute_command (thd=0x2aab94000be0, first_level=true)
9. #6  0x00000000030ac74b in mysql_parse (thd=0x2aab94000be0, parser_state=0x2aab8c2462d0, force_primary_storage_engine=false)
10. #7  0x0000000003095b0d in dispatch_command (thd=0x2aab94000be0, com_data=0x2aab8c246c40, command=COM_QUERY)
11. #8  0x0000000003091d7d in do_command (thd=0x2aab94000be0)
12. #9  0x00000000033d145b in handle_connection (arg=0xcb9cee0)
13. #10 0x00000000066cd007 in pfs_spawn_thread (arg=0xca3bde0)
14. #11 0x00002aaaaacd4aa1 in start_thread () from /lib64/libpthread.so.0
15. #12 0x00002aaaabfb993d in clone () from /lib64/libc.so.6

上面的堆栈可以看到优化器调用了substitute_gc这个函数，这个函数就可以将WHERE，GROUP_BY 以及ORDER BY中的相关表达式替换为隐式的generated column，进而可以让优化器来选择functional index。我们再来研究一下substitute_gc这个函数的源码。


1. bool substitute_gc(THD *thd, SELECT_LEX *select_lex, Item *where_cond,
2. ORDER *group_list, ORDER *order) {
3. List<Field> indexed_gc;
4. Opt_trace_context *const trace = &thd->opt_trace;
5. Opt_trace_object trace_wrapper(trace);
6. Opt_trace_object subst_gc(trace, "substitute_generated_columns");

8. // Collect all GCs that are a part of a key
9. // 这里要遍历所有的表来收集所有可以被替换的generated columns。后面的代码中会分析哪些表达式可以被替换
10. for (TABLE_LIST *tl = select_lex->leaf_tables; tl; tl = tl->next_leaf) {
11. if (tl->table->s->keys == 0) continue;
12. for (uint i = 0; i < tl->table->s->fields; i++) {
13. Field *fld = tl->table->field[i];
14. // 这里判断只有在索引中的列并且generated column可以用来替换表达式才会作为候选的列。
15. if (fld->is_gcol() &&
16. !(fld->part_of_key.is_clear_all() &&
17. fld->part_of_prefixkey.is_clear_all()) &&
18. fld->gcol_info->expr_item->can_be_substituted_for_gc()) {
19. // Don't check allowed keys here as conditions/group/order use
20. // different keymaps for that.
21. indexed_gc.push_back(fld);
22. }
23. }
24. }  // No GC in the tables used in the query
25. if (indexed_gc.elements == 0) return false;

27. if (where_cond) {
28. // Item_func::compile will dereference this pointer, provide valid value.
29. uchar i, *dummy = &i;
30. /**
31. 这里会利用generated column来替换where_cond里面对应的表达式。

33. Item::gc_subst_analyzer 该虚函数定义了每一种Item是否需要进行generated column的替换过程
34. Item::gc_subst_transformer 该函数定义了每一种可替换的Item如何利用generated column进行替换
35. */
36. where_cond->compile(&Item::gc_subst_analyzer, &dummy,
37. &Item::gc_subst_transformer,
38. (uchar *)&indexed_gc);
39. subst_gc.add("resulting_condition", where_cond);
40. }

42. if (!(group_list || order)) return false;
43. // Filter out GCs that do not have index usable for GROUP/ORDER
44. Field *gc;
45. List_iterator<Field> li(indexed_gc);

47. while ((gc = li++)) {
48. Key_map tkm = gc->part_of_key;
49. // 这里判断generated column相关的索引是否与group-by 或者 order-by的列有交集，如果没有相关性，就忽略。
50. tkm.intersect(group_list ? gc->table->keys_in_use_for_group_by
51. : gc->table->keys_in_use_for_order_by);
52. if (tkm.is_clear_all()) li.remove();
53. }
54. if (!indexed_gc.elements) return false;

56. // Index could be used for ORDER only if there is no GROUP
57. ORDER *list = group_list ? group_list : order;
58. bool changed = false;
59. for (ORDER *ord = list; ord; ord = ord->next) {
60. li.rewind();
61. // 这里判断group-by或者order-by的列是否是表达式或者函数来进行generated column替换。
62. if (!(*ord->item)->can_be_substituted_for_gc()) continue;
63. while ((gc = li++)) {
64. Item_func *tmp = pointer_cast<Item_func *>(*ord->item);
65. Item_field *field;
66. // 这里会根据表达式与generated column->gcol_info->expr_item进行比较来获取匹配的generated column
67. if ((field = get_gc_for_expr(&tmp, gc, gc->result_type()))) {
68. changed = true;
69. /* Add new field to field list. */
70. ord->item = select_lex->add_hidden_item(field);
71. break;
72. }
73. }
74. }
75. if (changed && trace->is_started()) {
76. String str;
77. SELECT_LEX::print_order(
78. &str, list,
79. enum_query_type(QT_TO_SYSTEM_CHARSET | QT_SHOW_SELECT_NUMBER |
80. QT_NO_DEFAULT_DB));
81. subst_gc.add_utf8(group_list ? "resulting_GROUP_BY" : "resulting_ORDER_BY",
82. str.ptr(), str.length());
83. }
84. return changed;
85. }

综上所述，本篇文章主要从源码层面对MySQL 8.0 实现的Functional index进行了一下简要的分析。Functional index主要依赖于generated column，利用内部隐式的创建一个generated column来辅助创建functional index。代码层面也比较容易理解，希望该篇文章能够帮助广大读者了解MySQL functional index的实现原理。

原文：http://mysql.taobao.org/monthly/2019/02/06/