面向单记录的混合负载下物化视图异步增量维护任务生成

孙洋洋，姚俊萍，李晓军，范守祥，王自维

（1.火箭军工程大学 301教研室，西安 710025；2.中国人民解放66133部队，北京 100043；3.火箭军工程大学 205教研室，西安 710025）

0 引言

由于全量维护仅适用于大量数据被修改的情形［1］、同步维护将会降低事务的速度［2］、定期维护无法满足实时性需求［3］以及混合负载（Hybrid Transaction/Analytical Processing，HTAP）避免复杂耗时的抽取-转换-加载（Extract-Transform-Load，ETL）进而消除联机分析处理（On-Line Analytical Processing，OLAP）滞后性的优势［4］，因此HTAP 物化视图异步增量维护已经成为物化视图维护研究的热点。

HTAP 物化视图异步增量维护任务生成是HTAP 物化视图异步增量维护的核心步骤，但是现有研究［5］主要为面向多记录的HTAP 物化视图异步增量维护任务生成（简称为多记录维护任务生成），无法实现面向单记录的HTAP 物化视图异步增量维护任务生成（简称为单记录维护任务生成），导致磁盘IO 开销的增加，进而降低HTAP 物化视图异步增量维护性能。基于此，本文开展了单记录维护任务生成研究，实现了面向单记录的HTAP 物化视图异步增量维护任务生成，研究成果弥补了现有研究的不足。

1 相关研究

物化视图的维护是在候选视图物化代价预测、物化视图选择［6］之后需要解决的第3 个问题，目前已经开展了十分丰富的研究。从维护时机方面，可以分为同步维护、异步维护和定期维护，后两者也称为延迟维护。在Vinh 等［7］开展的针对结构化查询语言（Structured Query Language，SQL）递归查询的维护研究中，不难发现同步维护的特征为当基表中数据变化后维护任务立即执行。蔡磊等［8］开展的面向区块链的维护研究中，在CPU 空闲时依次执行维护任务队列内容，当查询到来时优先维护与查询相关的物化视图，因此异步维护的特点是将维护任务推迟至合适时机执行。定期维护在一段固定的时间后执行，例如一天执行一次维护［3］。从维护技术方面，可以分为全量维护和增量维护。全量维护是增量维护的替代方案，全量维护意味着一旦基表发生变化，物化视图需要被完全覆盖，因此仅仅适用于大量数据被修改的情形［1］。从Solank［9］基于辅助关系设计的维护过程中，可以得出增量维护的特点是仅仅维护“净更改（net changes）”对应的物化视图。从服务对象方面，可以分为服务于OLAP 的维护和服务于HTAP 的维护。传统的物化视图维护任务是服务于OLAP 的，但是此时联机事务处理（On-Line Transaction Processing，OLTP）与OLAP 之间存在隔阂，需要ETL 实现两者的连接，导致OLAP 及其采用的物化视图存在滞后性［10］。随着工业界与学术界研究的不断深入，同时支持OLTP 与OLAP 的HTAP 的出现解决了上述问题［11］。综上，鉴于同步维护将会降低事务的速度［2］、定期维护无法满足实时性需求［3］、全量维护仅适用于大量数据被修改的情形［1］以及HTAP 消除OLAP 滞后性的优势［4］，HTAP 物化视图异步增量维护已经成为物化视图维护研究的热点。

HTAP 物化视图异步增量维护任务生成是HTAP 物化视图异步增量维护的核心步骤，相关研究尚处于起步阶段，目前仅有华东师范大学的Duan 等［5］于2020 年开展了相关研究，他们基于贪心算法在每一轮迭代中对多记录维护任务生成所需的访问任务（简称为多记录访问任务，单记录维护任务生成所需的访问任务简称为单记录访问任务）进行匹配，目标是发现磁盘访问范围最为相似即多记录维护任务生成效益最高的一组多记录访问任务和事务。Duan 等的研究［5］实现了在执行成本增长约束下尽可能多地合并执行多记录访问任务和事务，一定程度上减少了磁盘IO 开销，提高了HTAP 物化视图异步增量维护性能；但是当访问任务和事务涉及单记录时，Duan 等的研究［5］无法根据访问范围计算维护任务生成代价，访问任务和事务的独立执行消耗大量的磁盘IO 开销，进而降低HTAP 物化视图异步增量维护性能，因此，单记录维护任务生成已经成为HTAP 物化视图异步增量维护任务的研究重点。

已有多记录维护任务生成算法主要基于贪心算法［5］，贪心算法静态设置的约束条件无法适应维护任务生成过程中存在的HTAP 的变化、数据量的增减和硬件的更新等负载和环境的动态变化。随着强化学习的不断发展，数据库领域与强化学习相结合已经成为必然的趋势；因此将单记录维护任务生成过程建模为马尔可夫决策过程（Markov Decision Process，MDP）并基于智能体与环境交互实现自适应负载和环境的动态变化，将是单记录维护任务生成未来十分具有前景的研究方向。

强化学习是与无监督学习、有监督学习并列的第三种机器学习范式，具体可以分为无模型强化学习［12］和模型化强化学习［13］。模型化强化学习首先利用智能体与环境交互获得的数据建立环境模型［14］，然后利用环境模型决定下一步动作。当面对的问题具有复杂的状态动作空间时，准确估计环境模型存在巨大挑战［15］，无模型强化学习中智能体通过与未知环境交互并根据反馈决定下一步动作，因此无需提前拟合出环境模型。无模型强化学习具体可以分为基于策略梯度和基于价值函数两种类型［16］。基于策略梯度的无模型强化学习广泛应用于连续型强化学习问题之中［17］，并不适用于具有离散动作空间的单记录维护任务生成问题；基于价值函数的无模型强化学习主要分为状态-动作-奖励-状态-动 作（State-Action-Reward-State-Action，SARSA）算法和Q-learning 算法［15］。SARSA 算法于1994 年提出，是一种同轨策略算法，采用ε-贪心算法更新动作与价值函数［18］；Q-learning 算法最早由Watkins［19］于1989 年提出，是一种离轨策略算法，采用ε-贪心算法更新动作，采用贪心算法更新价值函数。SARSA 算法和Q-learning 算法的区别在于价值函数的更新［20］：前者采用ε-贪心算法，后者采用贪心算法。虽然SARSA 算法具有更快的收敛速度，但是其容易陷入局部最优解［21］，因此本文采用Q-learning 算法进行单记录维护任务生成研究。

2 面向单记录的HTAP 物化视图异步增量维护任务生成效益模型

本文研究的目标为通过合并执行单记录访问任务和事务来减少磁盘IO 开销，因此在2.1 节首先需要对基于单记录访问任务和事务生成单记录维护任务过程进行形式化；与此同时，单记录访问任务和事务的匹配是否合理，需要相关效益模型进行量化评价，因此在2.2 节对单记录维护任务生成效益模型进行详细阐述。

2.1 形式化基于单记录访问任务和事务生成单记录维护任务过程

在实际应用中，物化视图往往基于多个基表构建，第x个查询Qx可以表示为：

其中：⊳⊲表示连接运算。对于包含GROUP、LIMIT 等运算类型的查询，可以在式（1）的基础上进行元素的丰富，例如包含GROUP 的查询可以表示为：

其中：Gx表示Qx中GROUP 部分包含的元素。结合式（1），物化视图Mx表示为：

其中：π表示投影运算。结合式（2），可以将式（4）改写为：

1）插入事务触发的单记录维护任务生成。

当向基表中的i位置插入记录时，的增量出现，此时表示为：

此时基表的集合Tx产生的增量dnewTx代表着插入事务触发生成的单记录维护任务，表示为：

2）删除事务触发的单记录维护任务生成。

此时Tx产生的增量doldTx代表着删除事务触发生成的单记录维护任务，表示为：

3）更新事务触发的单记录维护任务生成。

此时Tx产生的增量dupdTx代表着更新事务触发生成的单记录维护任务，表示为：

2.2 单记录维护任务生成效益模型

结合式（7）（9）和（11），基于多个基表构建的物化视图在单个或多个基表发生插入、删除和更新时失效，此时单个基表的增量并不等价于单记录维护任务，还需要访问其他基表与对应的部分，此时单记录访问任务产生。对于大量的单记录访问任务，可以通过在处理后续事务的过程中顺带完成，即通过合并执行单记录访问任务与事务，实现共享磁盘IO，进而提高HTAP 物化视图异步增量维护性能。

本文研究的目标为通过匹配执行单记录访问任务和事务减少磁盘IO 开销。每秒进行读写操作次数（Input/output Operations Per Second，IOPS）是衡量磁盘IO 开销的主要指标，IOPS 越低，单记录访问任务和事务合并执行后占用的系统资源越低。IOPS 的计算方式［22］如下：

其中：Tseek代表寻道时间，Trotation代表旋转延迟。因此面向单记录的HTAP 物化视图异步增量维护任务生成效益模型可以表示为：

3 基于Q-learning 的面向单记录的HTAP 物化视图异步增量维护任务生成算法

3.1 Q-learning算法

Q-learning 算法主 要由环 境（Environment）、智能体（Agent）、状态（State）、动作（Action）和奖励（Reward）这5 部分组成，如图1 所示。

图1 Q-learning算法结构Fig.1 Structure of Q-learning algorithm

Agent 做 出Action，Environment 的State 发生转 移，Environment 随后对Agent 的Action 给予Reward。Agent 通 过不断地与Environment 进行交互，从每个State 的累积收益值中选择最大值对应的Action 形成其最优策略。接下来详述Q-learning 算法的各个组成部分［23］。

1）Environment。

本文通过单记录访问任务与事务的匹配生成单记录维护任务，由于单记录访问任务和事务发生在数据库之中，因此本文将支持HTAP 和物化视图的数据库作为Environment。

2）Agent。

单记录维护任务生成本质上属于计算机操作系统（Operating System，OS）的磁盘存储器管理问题。当进程即本文中的单记录访问任务和事务试图从磁盘访问数据时，OS 使用磁盘调度算法将磁头从当前位置移动到包含所需扇区的磁盘面。由于磁头的Action 是唯一可以与Environment进行交互的元素，因此本文将磁头设置为Agent。

3）Action。

Agent 负责做出Action，即磁头负责在各个扇区移动，实现了单记录访问任务和事务的合并执行，进而决定了单记录维护任务的生成；因此是否将单记录访问任务和事务进行的合并是Agent 的Action，即Action=｛合并，不合并｝。

4）State。

Agent 做出Action，Environment 的State 发生转移，State 所发生的转移本质上是单记录访问任务和事务的匹配情况，因此本文将单记录访问任务和事务的匹配情况视为State。

5）Reward。

Environment 的State 发生转移，Environment 随后对Agent的Action 给予Reward，本文将单记录维护任务生成效益即式（13）等价于Reward。

3.2 MVM_QL

通过将单记录维护任务生成过程建模为MDP。基于Q-learning 的面向单记录的HTAP 物化视图异步增量维护任务生成算法（Materialized View Asynchronous Incremental Maintenance Task Generation Algorithm under HTAP for Single Record based on Q-learning，MVAIMTGAHTAPSRQ）为便于表述，本文后续部分将MVAIMTGAHTAPSRQ 简写为MVM_QL。MVM_QL 可以基于智能体与环境的交互，实现自适应HTAP的变化、数据量的增减和硬件的更新等负载和环境的动态变化。MVM_QL 的具体流程如算法1 所示。

算法1 MVM_QL。

4 实验与结果分析

4.1 参数设置

实验采用的数据仓库为某云服务供应商提供的支持HTAP 的AnalyticDB PostgreSQL，参数设置见表1。实验采用的数据来源于美国交易处理效能委员会提供的商业智能计算测试数据集TPC-H。

表1 AnalyticDB PostgreSQL 参数设置Tab.1 Parameter setting of AnalyticDB PostgreSQL

MVM_QL 的回合数max_episodes、学习率α、折扣因子γ、贪婪度ε等参数设置如表2 所示。

表2 MVM_QL参数设置Tab.2 Parameter setting of MVM_QL

为了模拟HTAP 的变化，本文开展了10 组实验，每组实验需要完成随机生成的7 个单记录访问任务和7 个事务的匹配。为了模拟硬件的更新，1、3、5、7 和9 号实验硬件配置为2C16GB，2、4、6、8 和10 号实验硬件配置为4C32GB。为了研究MVM_QL 在不同数据量下的性能，实验采用的TPC-H 基表的数据量依次为0.03 GB、0.09 GB、0.15 GB、0.21 GB 和0.27 GB。实验过程中数据量与环境的设置见表3。

表3 数据量与环境的设置Tab.3 Setting of data size and environment

4.2 结果分析

表4 展示了基于MVM_QL 与无算法指导的单记录维护任务生成在平均IOPS 方面的对比，MVM_QL 整体上显著优于无算法。

表4 平均IOPSTab.4 Average IOPS

平均IOPS 的最大值和最小值方面，MVM_QL 次数分别为8.85 和8.22，无算法次数分别为18.65 和17.31，因此在平均IOPS 的最大值和最小值方面MVM_QL 仍然显著优于无算法。id 为7 的实验中，MVM_QL 展现出了最优性能，低于无算法10.07 次。综上，本研究已经取得了较好的效果。

同时对CPU 利用率进行了观察，表5 展示了基于MVM_QL 与无算法指导的单记录维护任务生成在平均CPU（2 核）利用率方面的对比，MVM_QL 整体上显著优于无算法。

表5 平均CPU（2核）利用率 单位：%Tab.5 Average utilization of CPU（2-core） unit：%

平均CPU（2 核）利用率的最大值和最小值方面，MVM_QL 分别为1.81%和1.45%，无算法分别为4.00%和3.49%，因此在平均CPU（2 核）利用率的最大值和最小值方面MVM_QL 仍然显著优于无算法。id 为7 的实验中，MVM_QL 展现出了最优性能，低于无算法2.19 个百分点。MVM_QL 和无算法的平均CPU（2 核）利用率随着数据量的增加而明显上升。

表6 展示了基于MVM_QL 与无算法指导的单记录维护任务生成在平均CPU（4 核）利用率方面的对比，MVM_QL 整体上显著优于无算法。

表6 平均CPU（4核）利用率 单位：%Tab.6 Average utilization of CPU（4-core）unit：%

平均CPU（4 核）利用率的最大值和最小值方面，MVM_QL 分别为0.89%和0.71%，无算法分别为1.91%和1.73%，因此在平均CPU（4 核）利用率的最大值和最小值方面MVM_QL 仍然显著优于无算法。id 为2 的实验中，MVM_QL 展现出了最优性能，低于无算法1.08 个百分点。

5 结语

本文建立了面向单记录的HTAP 物化视图异步增量维护任务生成的效益模型，设计了基于Q-learning 的面向单记录的HTAP 物化视图异步增量维护任务生成算法。实验结果表明，本文提出的MVM_QL 实现了面向单记录的HTAP 物化视图异步增量维护任务生成，减小了IOPS、CPU 利用率等系统资源利用率，减少了磁盘IO，对于进一步提升HTAP 物化视图异步增量维护性能具有的重要理论和应用价值。本文仅采用IOPS 作为评价生成的单记录维护任务优劣的指标，因此发掘IOPS、内存利用率、CPU 利用率等内在关系并建立多元评价模型，将是下一步的研究重点。