Page 352 - 《软件学报》2026年第2期
P. 352

姬涛 等: AI 赋能的关系型数据库系统研究: 标准化、技术与挑战                                                831



                                                   表 4 智能索引推荐方法

                     方法        方法类型       配置生成                代价评估                   终止条件       索引间影响
                  AutoAdmin [98]  基于规则优化搜索 规则+优化器       What-if+代价推导 (代价减少)          索引数量          隐式
                  AIMeetAI [99]  基于规则优化搜索   规则           索引成对比较 (代价对比)               存储空间          隐式
                 BEN_KNAP [99]  基于规则优化搜索 规则+优化器       What-if+代价推导 (单位存储收益)          存储空间          显式
                   Extend [100]  基于规则优化搜索   规则       What-if+优化器 (单位存储代价减少)          存储空间          隐式
                   Cophy [101]  基于规则优化搜索    规则          What-if+代价推导 (整数规划)          整数规划          隐式
                  DISTILL [102]  基于规则优化搜索   规则         What-if+代价模型 (代价减少比)          索引数量          隐式
                   ISUM [103]  基于规则优化搜索     规则         What-if+代价推导 (代价减少比)          负载数量          隐式
                   MCTS [104]  强化学习      规则+优化器         What-if+代价推导 (代价减少)          索引数量          隐式
                  NoDBA [105]  强化学习         规则            优化器 (代价减少比)                索引数量          隐式
                 LanIdxAdvis [106]  强化学习  启发式规则         What-if+优化器 (代价减少比)      存储空间或索引数量         隐式
                   COLT [107]  智能算法         规则          What-if+代价推导 (代价减少)          存储空间          隐式
                  QB5000 [108]  智能算法      采样聚类                查询到达率              存储空间或索引数量         隐式
                  PDAlerter [109]  智能算法     规则              优化器+代价推导                 存储空间          隐式
                  OnlinePT [110]  智能算法    基于计划             优化器 (代价减少)                存储空间          显式
                   WFIT [111]  智能算法         规则         索引配置工作函数 (代价减少)               索引数量          隐式
                    AIM [112]  智能算法         规则    What-if+优化器 (CPU成本的代价减少比排名)        索引数量          隐式
                    LIB [113]  智能算法         规则                代价减少比                  索引数量          隐式
                 DBAbandits [114]  强化学习     规则                 总代价                   存储空间          隐式
                   SWIRL [115]  强化学习        规则       What-if+优化器 (单位存储代价减少)          存储空间          隐式
                  DRLindex [116]  强化学习      规则          What-if+优化器 (代价减少比)          索引数量          隐式
                   HMAB [117]  强化学习         规则           What-if+优化器 (总时间)           索引数量          隐式
                  AutoIndex [118]  强化学习     规则             优化器 (代价减少)                存储限制          隐式

                    索引推荐方法主要分为两种, 分别是传统的组合优化和基于机器学习的方法.
                                               [98]
                    传统的优化组合方法: AutoAdmin         通过迭代增加索引宽度生成候选索引集合. 首轮迭代为每个查询生成候
                 选单列索引, 后续通过合并或扩展形成多列索引组合. 采用预剪枝策略, 例如限制候选索引的最大列数                              (如  DTA [119]
                 算法初始即考虑多列索引), 并通过种子配置减少枚举次数. Dexter 算法基于查询优化器的假设索引功能, 自动为
                 所有未建立的潜在单列和多列索引            (最大列数为    2) 创建假设索引, 通过优化器反馈筛选候选. DB2 Advisor         [120] 将所
                 有潜在索引设为假设索引, 直接依赖查询优化器的执行计划推荐候选索引. 优化器在生成查询计划时自动筛选出
                 对单个查询最优的索引加入候选集. Relax           方法  [121] 初始候选索引由查询优化器为每个查询生成的最佳索引组成,
                 后续通过转换规则       (如合并、拆分、删除属性等) 动态调整候选集, 逐步降低存储开销. Cophy                  [101] 采用全枚举策略,
                 将所有可能的单列和多列索引纳入候选集, 通过线性规划模型筛选满足空间约束的最优组合.
                    基于机器学习的方法基于查询语法解析提取候选列, 通过排列组合生成多列索引, 结合特征工程筛选. 一些方
                 法从查询的聚合函数、WHERE、JOIN、ORDER BY、GROUP BY               子句中提取列, 生成单列候选, 再排列组合形
                 成两列、三列候选索引. 基于强化学习的方法往往将工作负载编码为矩阵, 通过马尔可夫决策过程生成候选索引
                 状态, 依赖历史负载数据训练模型动态调整候选策略.
                  3.1.2.2    索引推荐模型
                    索引推荐模型旨在从候选索引集合中选择最优子集, 需同时优化时间效率                         (降低查询延迟) 和空间开销        (控制
                 索引存储). 该问题被建模为组合优化问题, 属于             NP-Hard  问题, 需通过近似算法或启发式方法求解.
                    基于规则的索引推荐方法通常采用规则驱动的策略生成候选索引. AutoAdmin                      [98] 通过贪心算法迭代选择局部
                 最优索引, 并利用假设代价分析          (What-if) 评估索引收益. BEN_KNAP  [99] 进一步引入显式收益机制以量化索引间交
                 互效应. Extend [100] 采用动态搜索空间生成策略, 通过存储-查询代价比隐式编码索引关联性. Cophy                  [101] 则构建整数
   347   348   349   350   351   352   353   354   355   356   357