openGauss 数据库源码解析系列文章——AI 技术（2.2）
四、智能索引推荐
数据库的索引管理是一项非常普遍且重要的事情，任何数据库的性能优化都需要考虑索引的选择。为此，openGauss 支持原生的索引推荐功能，可以通过系统函数等形式进行使用。
4.1 使用场景
在大型关系型数据库中，索引的设计和优化对 SQL 语句的执行效率至关重要。一直以来，数据库管理人员往往基于相关理论知识和经验，进行人工设计和调整索引。这样做的缺点在于，消耗了大量的时间和人力，同时人工设计的方式往往不能确保索引是最优的。
openGauss 提供了智能索引推荐功能，该功能将索引设计的流程自动化、标准化，可分别针对单条查询语句和工作负载推荐最优的索引，提升作业效率、减少数据库管理人员的运维操作。
openGauss 的智能索引推荐功能可覆盖多种任务级别和使用场景，具体包含以下三个特性。
（1） 单条查询语句的索引推荐。该特性可基于查询语句的语义信息和数据库的统计信息，对用户输入的单条查询语句生成推荐的索引。
（2） 虚拟索引。该特性可模拟真实索引的建立，同时避免真实索引创建所需的时间和空间开销，用户可通过优化器评估虚拟索引对指定查询语句的代价影响。
（3） 基于工作负载的索引推荐。该特性将包含有多条 DML 语句的工作负载作为任务的输入，最终生成一批可优化整体工作负载执行时间的索引。该功能适用于多种使用场景，例如，当面对一批全新的业务 SQL 且当前系统中无索引，本功能将针对该工作负载量身定制，推荐出效果最优的一批索引；当系统中已存在索引时，本功能仍可查漏补缺，对当前生产环境中运行的作业，通过获取日志来推荐可提升工作负载执行效率的索引，或者针对极个别的慢 SQL 进行单条查询语句的索引推荐。
4.2 现有技术
索引推荐技术按照任务级别划分，可分为基于单条查询语句的索引推荐和基于工作负载的索引推荐。对于基于单条查询语句的索引推荐，使用者每次向索引设计工具提供一个查询语句，工具会针对该语句生成最佳的索引。目前的主流算法是首先提取该查询语句的语义信息和数据库中的统计信息，然后基于相关的索引设计和优化理论，对各子句中的谓词进行分析和处理，启发式地推荐最优索引。此类任务主要是针对个别查询时间慢的 SQL 进行索引优化，应用场景较为有限。
一般来说，更广泛使用的任务场景是基于工作负载的索引推荐，即给定一个包含多种类型 SQL 语句的工作负载，生成使得系统在该工作负载下的运行时间降至最低的索引集合。在索引选择算法中，核心是量化和估计索引对于工作负载的收益，这里的收益是指，当该索引应用于指定工作负载时，工作负载的总代价的减少量。根据代价估计的方式的不同，目前的算法可分为两大类。
（1） 基于优化器的代价估计的方法。采用优化器的代价模型来对索引进行代价估计是较为准确的，因为优化器负责查询计划和索引的选择。同时，一些数据库系统支持虚拟索引的功能，虚拟索引并没有在存储空间中创建物理上的索引，而是通过模拟索引的效果来影响优化器的代价估计。目前的主流数据库产品均采用了该种方法，如 SQL Server 的 AutoAdmin、DB2 的 DB2 Advisor 等。
（2） 基于机器学习的方法。上一种方法由于优化器的局限性，会导致索引收益的估计发生偏差，例如选择度的错误估算或者代价估计模型不准确。在学术界的最新进展中，一些方法采用了机器学习算法来预测和分类哪种查询计划更加有效，或者是采用基于神经网络的代价模型来缓解传统模型带来的问题。但是此类方法往往需要大量的训练数据，并不适用于全部的业务环境。
4.3 实现原理
1. 针对单条查询语句的索引推荐
单条查询语句的索引推荐是以数据库的系统函数形式提供的，用户可以通过调用 gs_index_advise()命令使用。其原理是利用在 SQL 引擎、优化器等处获取到的信息，使用启发式算法进行推荐。该功能可以用来对因索引配置不当而导致的慢 SQL 进行优化。
图 8 单条查询语句的索引推荐流程图
单条查询语句的索引推荐步骤如图 8 所示，该过程如下。
（1） 对给定的查询语句进行词法和语法解析，得到解析树。
（2） 依次对解析树中的单个或多个查询子句的结构进行分析。
（3） 整理查询条件，分析各个子句中的谓词。
（4） 解析 From 子句，提取其中的表信息，如果其中含有 join 子句，则解析并保存 join 关系。
（5） 解析 Where 子句，如果是谓词表达式，则计算各谓词的选择度，并将各谓词根据选择度的大小进行倒序排列，依据最左匹配原则添加候选索引，如果是 Join 关系，则解析并保存 join 关系。
（6） 如果是多表查询，即该语句中含有 join 关系，则将结果集最小的表作为驱动表，根据前述过程中保存的 join 关系和连接谓词为其他被驱动表添加候选索引。
（7） 解析 Group 和 Order 子句，判断其中的谓词是否有效，如果有效则插入到候选索引的合适位置，Group 子句中的谓词优于 Order 子句，且两者只能同时存在一个；这里，候选索引的排列优先级为：join 中的谓词> Where 等值表达式中的谓词> Group 或 Order 中的谓词> Where 非等值表达式中的谓词。
（8） 检查该索引是否在数据库中已存在，若存在则不再重复推荐。
（9） 输出最终的索引推荐建议。
2. 虚拟索引
通过虚拟索引功能实现对待创建索引的效果和代价进行估计。对于给定的索引表名和列名，可以在数据库内部建立虚拟索引，该虚拟索引只具有待创建索引的元信息，而不会真正创建物理索引文件，因此避免了真实索引的创建开销。这些元信息包括：待创建索引的表名、列名和其他统计信息，虚拟索引仅用于通过 explain 语句显示优化器的可能执行路径，不能提供真正的索引扫描。
因此，对某条 SQL 语句执行 explain 命令，可以查看到创建索引前后优化器规划出的执行计划、检验该待创建索引是否被数据库采用以及是否有性能提升。虚拟索引主要是基于数据库中的 hook（钩子机制）实现的，即通过使用全局的函数指针 get_relation_info_hook 和 explain_get_index _name_hook，来干预和改变查询计划的估计过程，让优化器在规划路径时，考虑到可能出现的索引扫描。
3. 基于工作负载的索引推荐
基于工作负载的索引推荐功能的主要模块如图 9 所示。
图 9 基于工作负载索引推荐流程图
主要包括以下步骤。
（1） 对于给定的工作负载，首先对工作负载进行压缩。由于工作负载中通常存在着大量相似的语句，为了减少数据库功能的调用次数，我们会对工作负载中的 SQL 语句进行模板化和采样。
（2） 对压缩后的工作负载，调用单条查询语句的索引推荐功能为每条语句生成推荐索引，作为候选索引集合。
（3） 对候选索引集合中的每个索引，在数据库中创建对应的虚拟索引，根据优化器的代价估计来计算该索引对整个负载的收益。
（4） 在候选索引集合的基础上，基于索引代价和收益进行索引的选择。openGauss 实现了两种算法进行索引优选：一种是在限定索引集大小的条件下，根据索引的收益进行排序，然后选取靠前的候选索引来最大化索引集的总收益，最后采用微调策略，基于索引间的相关性进行调整和去重，得到最终的推荐索引集合；另一种方法是采用贪心算法来迭代地进行索引集合的添加和代价推断，最终生成推荐的索引集合。两种算法各有优劣，第一种方法未充分考虑索引间的相互关系，而第二种方法会伴随较多的迭代过程。
（5） 输出最终的索引推荐建议。
4.4 关键源码解析
1. 项目结构
智能索引推荐功能在项目中的源代码路径在 openGauss-server/src/gausskernel/dbmind 中，涉及的相关文件如表 3 所示。
表 3 智能索引推荐功能源代码路径
其中，单条查询语句的索引推荐功能和虚拟索引的功能通过数据库的系统函数进行调用，基于工作负载的索引推荐功能需要通过数据库外部的脚本运行。
2. 关键代码解析
单条语句索引推荐的所有实现部分都只存在于 index_advisor.cpp 文件中，该功能的主要入口为 suggest_index 函数，它通过系统函数 gs_index_advise 进行调用，代码如下：
SuggestedIndex *suggest_index(const char *query_string, _out_ int *len){ …… // 对查询语句进行词法和语法解析，获得解析树List *parse_tree_list = raw_parser(query_string);… // 递归地搜索解析树中的SelectStmt结构 Node *parsetree = (Node *)lfirst(list_head(parse_tree_list)); find_select_stmt(parsetree); …
// 依次解析和处理SelectStmt结构中的各个子句部分 ListCell *item = NULL;
foreach (item, g_stmt_list) { SelectStmt *stmt = (SelectStmt *)lfirst(item); /* 处理SelectStmt 结构体中涉及的FROM子句，提取涉及的表，解析和保存这些表中的join关系 */ parse_from_clause(stmt->fromClause); … if (g_table_list) { // 处理WHERE子句，提取条件表达式中的谓词并添加候选索引，解析和保存其中的join关系 parse_where_clause(stmt->whereClause); // 根据保存的join关系确定驱动表 determine_driver_table(); // 处理GROUP子句，如果满足条件，则将其中的谓词添加为候选索引 if (parse_group_clause(stmt->groupClause, stmt->targetList)) { add_index_from_group_order(g_driver_table, stmt->groupClause, stmt->targetList, true); /* 处理ORDER子句，如果满足条件，则将其中的谓词添加为候选索引 */ } else if (parse_order_clause(stmt->sortClause, stmt->targetList)) { add_index_from_group_order(g_driver_table, stmt->sortClause, stmt->targetList, false); } // 如果是多表查询，则根据保存的join关系为被驱动表添加候选索引 if (g_table_list->length > 1 && g_driver_table) { add_index_for_drived_tables(); } /* 对全局变量中的每个table依次进行处理，函数generate_final_index将前述过程生成的候选索引进行字符串拼接，并检查和已存在的索引是否重复 */ ListCell *table_item = NULL;
foreach (table_item, g_table_list) { TableCell *table = (TableCell *)lfirst(table_item); if (table->index != NIL) { Oid table_oid = find_table_oid(query_tree->rtable, table->table_name); if (table_oid == 0) { continue; } generate_final_index(table, table_oid); } } g_driver_table = NULL; } }…… return array;}
复制代码
虚拟索引的核心功能全部位于 hypopg_index.cpp 文件中。用户通过 SQL 语句调用系统函数 hypopg_create_index 来创建虚拟索引，该系统函数主要通过调用 hypo_index_store_parsetree 函数来完成虚拟索引的创建。虚拟索引的结构体名为 hypoIndex，该结构体的许多字段是从它涉及的表的 RelOptInfo 结构体中读取的，hypoIndex 的结构如下：
typedef struct hypoIndex { Oid oid; /* 虚拟索引的oid，该oid是唯一的 */ Oid relid; /* 涉及的表的oid */ … char *indexname; /* 虚拟索引名 */
BlockNumber pages; /* 预估索引使用的磁盘页数 */ double tuples; /* 预估索引所涉及的元组数目 */
/* 索引描述信息 */ int ncolumns; /* 涉及的总列数 */ int nkeycolumns; /* 涉及的关键列数 */ … Oid relam; /* 记录索引操作回调函数的元组的oid, 从pg_am系统表中获取的 */ … } hypoIndex;
复制代码
函数 hypo_index_store_parsetree 的输入参数为创建索引的 SQL 语句和其语法树，依据该语句的解析结果来创建新的虚拟索引，代码如下：
hypoIndex *hypo_index_store_parsetree(IndexStmt *node, const char *queryString){……// 获得创建索引的表的oid relid = RangeVarGetRelid(node->relation, AccessShareLock, false); …… // 对该创建索引的语句进行语法解析 node = transformIndexStmt(relid, node, queryString); …… // 新建虚拟索引，该虚拟索引的结构体类型hypoIndex定于位于文件openGauss-server/src/include/dbmind/hypopg_index.h，与索引结构体IndexOptInfo类似 entry = hypo_newIndex(relid, node->accessMethod, nkeycolumns, ninccolumns, node->options); // 根据语法树的解析结果为虚拟索引entry内的各个成员赋值 PG_TRY();{ …… entry->unique = node->unique; entry->ncolumns = nkeycolumns + ninccolumns; entry->nkeycolumns = nkeycolumns; …… } PG_CATCH(); { hypo_index_pfree(entry); PG_RE_THROW(); } PG_END_TRY(); // 设置虚拟索引的名字 hypo_set_indexname(entry, indexRelationName.data); // 将新建的虚拟索引entry添加到虚拟索引的全局链表hypoIndexes上，该全局变量为节点类型为hypoIndex*的List链表，记录了全部创建过的虚拟索引 hypo_addIndex(entry);
return entry;}// 该函数被赋值给全局的函数指针get_relation_info_hook，当数据库执行EXPLAIN时，会通过该函数指针跳转到本函数 void hypo_get_relation_info_hook(PlannerInfo *root, Oid relationObjectId, bool inhparent, RelOptInfo *rel){ /* 判断是否开启GUC参数enable_hypo_index，当SQL语句是EXPLAIN命令时，变量isExplain的值为真 */ if (u_sess->attr.attr_sql.enable_hypo_index && isExplain) { Relation relation;
relation = heap_open(relationObjectId, AccessShareLock);
if (relation->rd_rel->relkind == RELKIND_RELATION) { ListCell *lc; /* 遍历全局变量链表hypoIndexes中的每个创建过的虚拟索引 */ foreach (lc, hypoIndexes) { hypoIndex *entry = (hypoIndex *)lfirst(lc); // 判断该虚拟索引和该表是否匹配 if (hypo_index_match_table(entry, RelationGetRelid(relation))) { // 如果匹配，则将该索引加入该表的indexlist中，indexlist是节点类型为IndexOptInfo的链表，是结构体类型RelOptInfo的成员，记录了表的所有的索引 hypo_injectHypotheticalIndex(root, relationObjectId, inhparent, rel, relation, entry); } } } heap_close(relation, AccessShareLock);}……}
复制代码
4.5 使用示例
1. 单条查询语句的索引推荐
单条查询语句的索引推荐功能支持用户在数据库中直接进行操作，本功能基于查询语句的语义信息和数据库的统计信息，对用户输入的单条查询语句生成推荐的索引。本功能涉及的函数接口如表 4 所示。
表 4 单 query 索引推荐功能的函数接口
使用上述函数，获取针对该 query 生成的推荐索引，推荐结果由索引的表名和列名组成。
opengauss=> select * from gs_index_advise('SELECT c_discount from bmsql_customer where c_w_id = 10'); table | column ----------------+---------- bmsql_customer | (c_w_id)(1 row)
复制代码
上述结果表明：应当在 bmsql_customer 的 c_w_id 列上创建索引，例如可以通过下述 SQL 语句创建索引。
CREATE INDEX idx on bmsql_customer(c_w_id);
复制代码
某些 SQL 语句，也可能被推荐创建联合索引，例如：
opengauss=# select * from gs_index_advise('select name, age, sex from t1 where age >= 18 and age < 35 and sex = ''f'';'); table | column-------+------------ t1 | (age, sex)(1 row)
复制代码
上述语句结果表明应该在表 t1 上创建一个联合索引(age, sex)，可以通过下述命令创建该索引，并将其命名为 idx1。
CREATE INDEX idx1 on t1(age, sex);
复制代码
2. 虚拟索引
虚拟索引功能支持用户在数据库中直接进行操作，该功能模拟真实索引的建立，避免真实索引创建所需的时间和空间开销，用户基于虚拟索引，可通过优化器评估该索引对指定查询语句的代价影响。
虚拟索引功能涉及的系统函数接口如表 5 所示。
表 8-10 虚拟索引功能的接口
本功能涉及的 GUC 参数如表 6 所示。
表 8-11 GUC 参数
（1） 使用 hypopg_create_index 函数创建虚拟索引。例如：
opengauss=> select * from hypopg_create_index('create index on bmsql_customer(c_w_id)'); indexrelid | indexname ------------+------------------------------------- 329726 | <329726>btree_bmsql_customer_c_w_id(1 row)
复制代码
（2） 开启 GUC 参数 enable_hypo_index，该参数控制数据库的优化器进行 EXPLAIN 时是否考虑创建的虚拟索引。通过对特定的查询语句执行 explain，用户可根据优化器给出的执行计划评估该索引是否能够提升该查询语句的执行效率。例如：
opengauss=> set enable_hypo_index = on;SET
复制代码
开启 GUC 参数前，执行 EXPLAIN+查询语句，如下所示：
opengauss=> explain SELECT c_discount from bmsql_customer where c_w_id = 10; QUERY PLAN -------------------------------------------------------------------- Seq Scan on bmsql_customer (cost=0.00..52963.06 rows=31224 width=4) Filter: (c_w_id = 10)(2 rows)
复制代码
开启 GUC 参数后，执行 EXPLAIN+查询语句，如下所示：
opengauss=> explain SELECT c_discount from bmsql_customer where c_w_id = 10; QUERY PLAN -------------------------------------------------------------------- [Bypass] Index Scan using <329726>btree_bmsql_customer_c_w_id on bmsql_customer (cost=0.00..39678.69 rows=31224 width=4) Index Cond: (c_w_id = 10)(3 rows)
复制代码
通过对比两个执行计划可以观察到，该索引预计会降低指定查询语句的执行代价，用户可考虑创建对应的真实索引。
（3） （可选）使用 hypopg_display_index 函数展示所有创建过的虚拟索引。例如：
opengauss=> select * from hypopg_display_index(); indexname | indexrelid | table | column --------------------------------------------+------------+----------------+------------------ <329726>btree_bmsql_customer_c_w_id | 329726 | bmsql_customer | (c_w_id) <329729>btree_bmsql_customer_c_d_id_c_w_id | 329729 | bmsql_customer | (c_d_id, c_w_id)(2 rows)
复制代码
（4） （可选）使用 hypopg_estimate_size 函数估计虚拟索引创建所需的空间大小（单位：字节）。例如：
opengauss=> select * from hypopg_estimate_size(329730); hypopg_estimate_size ---------------------- 15687680(1 row)
复制代码
（5） 删除虚拟索引。
① 使用 hypopg_drop_index 函数删除指定 oid 的虚拟索引。例如：
opengauss=> select * from hypopg_drop_index(329726); hypopg_drop_index ------------------- t(1 row)
复制代码
② 使用 hypopg_reset_index 函数一次性清除所有创建的虚拟索引。例如：
opengauss=> select * from hypopg_reset_index(); hypopg_reset_index -------------------- (1 row)
复制代码
3. 基于工作负载的索引推荐
对于工作负载级别的索引推荐，用户可通过运行数据库外的脚本使用此功能，本功能将包含有多条 DML 语句的工作负载作为输入，最终生成一批可对针对整体工作负载的索引。
（1） 准备好包含有多条 DML 语句的文件作为输入的工作负载，文件中每条语句占据一行。用户可从数据库的离线日志中获得历史的业务语句。
（2） 运行 python 脚本 index_advisor_workload.py，命令如下：
python index_advisor_workload.py [p PORT] [d DATABASE] [f FILE] [--h HOST] [-U USERNAME] [-W PASSWORD][--max_index_num MAX_INDEX_NUM] [--multi_iter_mode]
复制代码
其中的输入参数如下。
① PORT：连接数据库的端口号。
② DATABASE：连接数据库的名字。
③ FILE：包含 workload 语句的文件路径。
④ HOST：（可选）连接数据库的主机号。
⑤ USERNAME：（可选）连接数据库的用户名。
⑥ PASSWORD：（可选）连接数据库用户的密码。
⑦ MAX_INDEX_NUM：（可选）最大的索引推荐数目。
⑧ multi_iter_mode：（可选）算法模式，可通过是否设置该参数来切换算法。例如：
python index_advisor_workload.py 6001 opengauss tpcc_log.txt --max_index_num 10 --multi_iter_mode
复制代码
评论