软件学报ISSN 1000-9825, CODEN RUXUEW E-mail:************ Journal of Software,2021,32(3):622−635 [doi: 10.13328/jki.jos.006179] ©中国科学院软件研究所版权所有. Tel: +86-10-62562563
数据库内AI模型优化∗
钮泽平,  李国良
(清华大学计算机科学与技术系，北京  100084)
通讯作者: 李国良,E-mail:***********************
摘要: 在大量变化着的数据中，数据分析师常常只关心预测结果为特定值的少量数据.然而，利用机器学习模型进行推理的工作流程中，由于机器学习算法库默认数据以单表方式组织，用户必须先通过SQL语句查询出全部数据，即使随后在模型推理过程中会将大量数据丢弃.指出了在这个过程中，如果可以预先从模型中提取信息，就有望能在数据获取阶段快速排除不需要的数据，从而降低数据获取过程中的多表连接代价、进程间通信代价以及模型预测代价，进而加速整个工作流程.以决策树模型为例，首先提出一种预筛选+验证的执行方法对查询过程进行优化，之后给出了从决策树中提取用于预筛选谓词的离线算法，最后在真实数据集上进行测试.实验结果表明，所提出的方法能够对借助决策树模型推理结果对数据进行筛选的应用场景起到较好的加速效果.
关键词: SQL；数据库；决策树;DB4AI
中图法分类号: TP311
中文引用格式: 钮泽平，李国良.数据库内AI模型优化.软件学报,2021,32(3):622−635./1000-9825/ 6179.htm
英文引用格式: Niu ZP, Li GL. In-database AI model optimization. Ruan Jian Xue Bao/Journal of Software, 2021,32(3):622−635 (in Chinese)./1000-9825/6179.htm
In-database AI Model Optimization
NIU Ze-Ping,  LI Guo-Liang
(Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China)
Abstract: In a large number of changing data, data analysts often only care about a small amount of data with specific prediction results. However, users must query all the data by SQL before inference step, even if a large amount of data will be dropped, because the machine learning algorithm libraries always assume that the data is organized in a single table. This study points out that in this process, if some hints can be gotten from model in advance, it is expected that unnecessary data can be quickly eliminated in the data acquisition phase, thus reducing the cost of multi-table join, inter-process communication, and model prediction. This work takes a specific kind of machine learning model, i.e., decision tree, as an example. Firstly, a pre-filtering and validation execution workflow is proposed. Then, an offline algorithm is used to extract pre-filtering predicates from the decision tree. Finally, the algorithm is tested on real world dataset. Experiments show that the method proposed in this study can accelerate the execution of SQL queries containing predicates on decision tree prediction result.
Key words: SQL; database; decision tree; DB4AI
近年来，数据量爆炸式增长.生产环境中，大部分数据都由数据库管理系统进行管理.机器学习算法目前
广泛应用于各种数据分析与线上应用场景，然而在易用性方面，由于编写机器学习代码的复杂性且数据分析师更
∗基金项目: 国家自然科学基金(61925205, 61632016)
Foundation item: National Natural Science Foundation of China (61925205, 61632016)
本文由“支撑人工智能的数据管理与分析技术”专刊特约编辑陈雷教授、王宏志教授、童咏昕教授、高宏教授推荐.
收稿时间: 2020-07-20; 修改时间: 2020-09-03; 采用时间: 2020-11-06; jos在线出版时间: 2021-01-21
钮泽平 等：数据库内AI 模型优化 623 熟悉SQL 而存在较大提升空间；在执行效率方面，由于机器学习算法与数据库操作分离而无法借助数据库查询优化过程进行优化[1,2].数据库提供的SQL 接口具有声明式的特点，用户通过SQL 简练地指定查询任务，无需关注内部实现方法，数据库就可以通过一系列查询处理过程，将查询语句转化为一系列算子操作，利用索引、缓存等进行加速，选取合适的多表连接方案，确保准确而高效地获得数据.机器学习的训练与预测可以看作新的操作符，通过SQL 支持这种新的操作符，一方面可以将数据获取与训练/预测过程通过SQL 进行融合，使系统更易于使用；另一方面，提供了使用数据库优化机器学习算子的可能.已有的工作中，主要为通过数据库的用户定义函数(UDF)功
能，对机器学习运算进行支持；或者通过结合硬件特点，利用数据库内联用户定义函数，将声明式查询与命令式数据处理转化为中间表示后统一优化等方式进行加速[2].
然而，在机器学习推理过程的优化中，前人的工作主要集中于通过查询语句中的谓词特点对模型进行剪枝，而对模型特征的利用仍不够彻底.考虑一个例子“选择周营业额预测值大于20万元的商店”，可以通过SQL 查询表示为:
SELECT  StoreName
FROM  store , sales , features AS f
WHERE  (store .id =sales .storeid  AND  sales .time =f .time ) AND
predict (store .dept ,f .CPI ,...)>200000;
在这类查询中，满足条件，需要返回给用户的数据可能只占全部数据中很小的比例.类似的例子还有：大型连锁超市希望知道各分店各销售部门中，营业额少于特定金额的有哪些；银行希望出违约概率高于一定值的账户等.这些场景中，通过支持UDF 的SQL 可以表示为WHERE 子句中包含机器学习预测函数的形式，即，使用机器学习模型预测结果对数据进行筛选可看作一种新的谓词.当数据量较大时，如果按照用户定义函数的方式进行执行，首先需要将多个包含特征列的表进行代价较为高昂的连接操作，之后
必须在得到的全部数据上进行机器学习推理，才能得到占总数据量比例很小的查询结果.
然而，这种朴素的方式不一定是最优的.一方面，在未进行连接时，通过单表中某些重要特征的取值已经可以排除其在最终结果中的可能，但这种朴素的方式仍然会将连接操作进行到底，造成计算的浪费；另一方面，机器学习的推理过程与简单谓词相比复杂得多——较为复杂的决策树预测一条数据可能相当于十余条简单谓词的执行时间，故连接操作生成过多的无用结果，也会造成推理过程时间大幅增加.对于这类使用了机器学习推理结果对结果进行筛选的SQL 查询，如果能够提前从模型中提取一些条件对数据预先进行筛选过滤，则可以同时减少数据获取中的连接代价与后续模型推理过程中的计算代价，从而提高执行效率.这样的规则需要是保守的，即不能因为应用规则导致应在最终结果中的数据被丢弃.直接进行连接操作得到的数据记为S join ，经过机器学习推理谓词过滤得到的结果记为S result ，使用规则筛选得到的数据记为S filter ，它们之间的关系可以表示为图1.对于一个特定问题,S join 与S result 越大，使用规则进行初筛的优化潜力就越大；而为了实际达到良好的加速效果，我们的目标便是让S filter 尽可能接近S result
.
Fig.1  Relation of S join , S filter  and S result
图1  S join ,S filter ,S result 三者应满足的关系
用于初筛的规则一定与模型相关——只有模型才能够决定推理的结果，故我们可以尝试从以下两个角度切入.
(1) 构建更容易获得初筛规则的模型.机器学习模型中，各种特征重要性不同，如果我们能够在构建模型
624 Journal of Software软件学报 V ol.32, No.3, March 2021
过程中，在不显著损失预测准确率的情况下构建出能够让更多数据仅通过少量重要特征判断即可得
到结果的模型，那么对这种更简单的模型放宽条件，有助于我们得到更接近S result的S filter;
(2)对已有模型进行简化，提取结果数据的“大致特征”(使用谓词进行刻画)作为初筛规则.这里的谓词必
须足够简单，因为过于复杂的谓词用于初筛会造成查询优化过程与执行过程中的性能损失.如果能得
到满足上述特征的简单谓词，那么就可以借助数据库查询优化过程，下推用于初筛的简单谓词，降低
数据获取过程中的多表连接开销；同时，初筛去掉大量结果后，需要执行推理的数据量也会显著降低.
本工作以机器学习中经典的决策树算法为例，通过SQL对决策树模型的训练方法以及包含决策树推理的谓词进行了支持，并设计算法进行性能优化.本文尝试利用数据库对一种特定的机器学习算法，决策树的推理过程进行优化.主要的贡献是：实现了通过SQL进行模型训练，加速模型推理的工作流程；提出通过预筛选+验证方法加速决策树推理SQL的速度，并设计了从决策树提取用于对查询结果预筛选的谓词算法；在真实数据集上测试加速效果，并分析实验结果.
本文第1节介绍使用数据库支持机器学习方向已有的工作.第2节以决策树模型为例，介绍了AI模型训练和推理SQL在数据库内的优化工作流程.第3节介绍数据库内决策树训练和推理的主要优化算法，针对前文提出的两个切入点进行尝试.第4节介绍在真实数据集上进行测试的效果并分析原因.第5节对其他AI模型上的优化进行探讨.最后，在第6节中进行总结.
1  相关工作
机器学习包括数据清洗与特征工程、模型训练、模型选择与评估、模型上线部署等一整套流程.消耗更少时间、得到更好的模型有利于提高数据分析师的效率，提升模型开发效率，降低应用系统处理延迟.近年来，数据库研究者对对机器学习整个流程的优化做出了诸多贡献(DB4AI)，主要集中于扩展SQL语句支持机器学习算法、自动特征选取、模型训练加速、执行引擎优化方面.
•声明式机器学习
为了能够降低机器学习算法的使用门槛，数据库社区出现了一些通过扩展SQL对机器学习算法进行支持的尝试.其思想为：通过声明式语言对复杂的机器学习算法执行过程进行封装，让用户能像使用SQL一样只需定义任务，系统便能自动实现细节，完成整个机器学习流程.MADlib[3]是开源的数据库内分析算法库，提供了基于SQL的机器学习算法，用户无需将数据导入导出其他工具即可完成机器学习任务.MADlib的实现利用了PostgreSQL数据库的服务器端编程特性，将C++,Python编写的机器学习算法声明为用户定义函数.C++语言用于实现对性能要求较高的机器学习算法底层操作，如矩阵运算;Python实现算法更高抽象层次上的逻辑.训练算法方面,MADlib支持迭代式的训练过程；推理算法方面,MADlib要求数据预先被连接为单表，推理结果亦通过表的方式返回给用户.MLlib[4]是Spark上原生的机器学习API，它提供了快速、分布式的机器学习算法实现. MLlib具有易于搭建机器学习全流程的API，便于用户对从数据与处理、特征选取、训练模型、验证的全流程中各种方法进行替换.MLog[5]支持类似SQL的语法.MLog将查询中机器学习运算与数据库运算分开，在Tensorflow,Keras等平台上通过GPU执行机器学习任务，在数据库中执行数据库运算.由于运算分开在不同平台执行，所以会有较大的通信开销.
•自动特征选取
机器学习算法使用的数据需要包含足够的有用特征，尽量减少无关特征.给定一个用于训练机器学习任务的数据库，数据分析师需要耗费很多精力判断需要连接哪些表、是否需要通过额外的数据表增加特征.文献[6]首先提出，数据库中某些连接是可以避免的，他们提出数据库中一些表主键的值可以作为其中新特
征的表示，避免与这些表的连接不会对模型的预测准确度产生影响.ARDA[7]借助用户给定的一个用于机器学习任务的数据基表和一个与该任务可能相关的大量数据表构成的数据仓库，自动发掘数据间的潜在连接关系，并寻对机器学习任务帮助大的特征对数据集进行增强.
钮泽平 等：数据库内AI 模型优化
625
• 模型训练加速 (1) 通过分布式训练加速模型训练，其主要目标为提高并行度，降低通信中数据与模型的通信代价.
LAPSE [8]将数据分布于各个计算节点，实现了在计算节点之间动态分配参数.ColumnSGD [9]提出将数据按列组织，将模型参数巧妙拆分，分配到各个计算节点，支持逻辑回归、SVM 和部分DNN 模型;
(2) DB4ML [10]提出通过扩展SQL 使其支持迭代事务时，传统的事务执行过于笨重，该工作针对不同机器
学习算法使用不同隔离级别，调整迭代事务中MVCC 记录方式，可以在满足训练要求条件下大幅提升训练效率.
• 执行引擎优化
机器学习算法中常会涉及到线性代数运算，对其执行进行优化可以提升训练和推理算法执行速度. LARA [11]提出一种新代数，在逻辑表示方式上融合了线性代数(LA)和关系代数(RA)，从而获得了更多优化机会. SPORES [12]引入了对线性代数表达式的一种新的通用优化方法：构建一系列线性代数表达式和关系代数表达式之间相互转化的规则，借助规则先将线性代数表达式转换为关系代数表达式，对后者进行优化，再将结果转换回线性代数表达式.
当前，对模型推理进行加速的工作相对少.与本文举例介绍的通过数据库技术优化决策树模型推理较为接近的研究为文献[13]，该工作介绍了LinkedIn(领英)对职位搜索和推荐系统的优化，他们训练决策树学习文档特征到文档质量高低的映射，为了获得top-k 文档，借助决策树叶子上包含样本正负例数目比例选取部分叶子到根路径上的条件得到新查询.本文在技术上虽然同样借助了决策树解释性强的特点从模型中提取信息，但本文并非解决top-k 问题，从而引起从模型中提取的筛选谓词过多的问题，本文给出了谓词合并算法加以解决，并提出了通过初筛对含机器学习模型推理谓词的查询进行优化的总体框架.
2  数据库内AI 模型工作流程
AI 算法通常包含训练与推理算法，需要通过设计SQL 接口从语法上分别进行支持,SQL 接口的封装整合了AI 算法与数据库查询操作，赋予AI 算法声明式特点，同时也是借助数据库特性进行优化的前提.为了加速推理执行速度，在训练过程中，可以构建适合于数据库优化的模型，离线提取特征；在推理过程中，
可以借助提取出的模型特征设计数据库算子和机器学习算子的联合优化.本文以决策树为例给出训练和推理过程中的优化技巧，整体工作流程如图2所示，本节将对其进行详细介绍
.
Fig.2  In-database decision tree optimization workflow
图2  数据库内决策树优化工作流程
进程间通信实验总结626 Journal of Software软件学报 V ol.32, No.3, March 2021
2.1  决策树训练SQL的执行过程
首先，用户输入定义模型的SQL语句,SELECT子句中包含ain函数，其参数依次序分别指定参与训练过程的特征列表(fea_list)、各特征是定类特征或数值特征(is_numeric)、预测目标列名称(target_ column)，以及训练决策树需要的超参数(如使用gini系数或cross entropy、决策树最大深度等).定义模型训练任务的SQL语句首先进入数据收集器(data collector)，收集器会从ain函数参数中提取出训练所需的特征列名，通过修改原SQL语法树的方式构造生成训练数据的SQL语句，进而通过数据库获取训练数据集.收集器获取到训练数据后，将训练数据与训练超参数传递给训练模块生成决策树.
本工作复现了CART(classification and regression tree)算法[14]进行模型训练.在CART算法之外，亦尝试修改决策树训练算法.通过按照表的顺序建立决策树，借助后减枝[15]避免过拟合，在不显著降低模型准确度的情况下，获得更多只包含少量表特征的分支，从而降低推理过程的计算代价，并通过这种方式初步简化模型以利于提取谓词，相关部分见第3.2节.
训练后的决策树模型会被传递给谓词提取模块(predicate extractor).由于谓词提取过程较为耗时，且可以在进行推理前进行离线预处理，故我们会在训练得到决策树后马上进行谓词提取，并将提取出的谓词与原决策树模型一同存入数据库.决策树的叶子节点对应一个分类结果，根到叶子的路径上每个节点对应一个谓词，这些谓词组成的合取表达式可筛选出到达这个叶子节点的数据.然而，决策树模型的叶子数量可能十分庞大，如果用过多叶子节点对应的谓词共同组成的析取表达式直接生成SQL表达式，相当于每条数据需要对所有的决策树分支进行判断，在计算量上是不可接受的，所以谓词提取步骤是必要的.谓词提取器会对每个分类结果对应的谓词析取表达式进行合并，通过适当“放宽”条件，获得能够描述该类别主要特征的少量谓词.最终，提取后的谓词、决策树模型以及关于决策树使用的各特征类型(数值或者定类)将被存入到数据库中，同时将新创建的模型名称被返回给用户，以供包含决策树推理的SQL查询调用.
2.2  含决策树推理的SQL查询优化过程
用户希望借助训练好的决策树模型筛选预测值为特定值的数据时，可输入WHERE子句中包含决策树推理谓词的SQL.
查询首先到达重写器(rewriter)，重写器将查询转化为语法树，从决策树推理函数的参数中提取出模型名称与期望筛选的分类结果.借助模型名称，重写器从数据库中取出决策树模型、被提取出的预筛选谓词以及各列特征的类型信息.随后，重写器从预筛选谓词中取出筛选的分类目标对应的初筛条件，将其转化为
谓词的语法树格式后，对决策树推理谓词进行整体替换.需要注意：当决策树推理谓词被NOT否定时，替换过程中有一些细节问题需要处理，将在第3.4中进行讨论.修改后的语法树被转换回用于初筛的SQL，在数据库中进行执行得到初筛后的结果.初筛后的结果被送达验证模块.验证模块将初筛后的数据逐条通过决策树模型进行预测，筛除不符合用户输入语义的部分，将最终结果返回给用户.
3  数据库内决策树模型优化算法
本节会从引言部分最后给出的两个角度入手，引入并详细介绍上一节中决策树训练与推理优化过程中的关键算法.
3.1  通过谓词筛选执行决策树推理
决策树推理算法的输入是一棵决策树以及一组需要执行推理算法的数据，输出是这组数据中每条的分类结果.通常的推理算法需要对数据中的每个条目，从决策树根开始，根据是否满足节点所对应的谓词条件选择向左/右分支前进，直到走到叶子节点得到分类结果.然而，我们也有另一种策略可供选择，下面举例介绍.
例：医院需要用决策树模型获得预测手术后住院时间大于等于10天的患者.数据集包含属性：患者姓名，患者年龄，患者性别，手术类别，医生姓名，医生年龄，医生职称.训练后得到图3所示的决策树.
我们可以采用一种从结果逆推条件、在数据中进行选择的方式进行决策树推理.从决策树中我们可以看