通过概率谓词加速数据库中机器学习函数推理
KaiwuDB 社区官方号
2023-04-12
原文链接：https://www.vldb.org/pvldb/vol15/p2032-yang.pdf
PART 02
背景
随着人工智能技术的应用与发展，数据库中经典的查询优化技术（如谓词下推）在机器学习推理查询中作用变得十分有限：因为其中使用到的用户定义函数 UDF（User Defined Function）通常是从非结构化输入中提取所需相关信息列。而这类函数一般非常昂贵。
通过构建机器学习的 UDF，在功能上确实给用户提供了在 SQL 上一站式操作的便捷。但对于查询处理来说，这相当于构建了一系列的黑盒子，给优化器带来了许多问题，ML（Machine Learning）推理的 UDF 无法参与正常的查询优化，即使待训练或预测数据表上有足够的统计信息，也难以利用。
如果查询谓词恰好需要 UDF 生成的相关数据信息，那么查询将始终滞留在这些 UDF 后面等待。例如下面的查询是始于应用用户定义的函数（UDF）从 Blob 中提取相关 Column：
图 1 查询示例
在上面的例子中，VehDector 从每一个 video frame 里面提取所需的 vehBox，然后 F1 和 F2 从 vehBox 中提取所需相关特征，C1 和 C2 是使用提取的特征识别车辆类型和颜色的分类器。
对于此类查询，传统的查询优化技术（如上面提到的谓词下推）在这里没有办法发挥作用，因为优化器无法将谓词下推到生成谓词列的 UDF 下。这就导致所有的数据都会进入 UDF，ML 推理的 UDF 的使用成本通常比较高，而且在后面的谓词过滤中一大部分数据可能并不会被用到，但它们都占据了 UDF 的处理成本。
图 2 逻辑计划
在《Accelerating Machine Learning Inference with Probabilistic Predicates》文中提出了概率谓词（Probabilistic Predicates or PP），它的优化方案是假设查询谓词之间具有独立性，每个谓词单独构建代理模型，通过在昂贵的 ML 推理的 UDF 注入廉价的代理模型来重写一个新的查询。
通过这种方式将不满足查询谓词的输入提前过滤出去，避免大量的无用数据进入 ML 推理的 UDF 占用资源和时间（逻辑计划变化如下图）。
图 3 产生的新逻辑计划
但采用谓词独立的假设有可能导致次优计划，在本文中，作者提出了一个名为“CORE”的查询优化器，它可以更好地利用 ML 推理中的谓词相关性来加速查询。给定一个临时查询，CORE 会在线构建代理模型，并利用分支和定界搜索过程来减少构建成本。
PART 03
相关工作
1. 数据库优化中的操作符重排序
《Optimization of Queries with User-defined Predicates》研究了数据库系统中 select-project-join 操作符的重排序问题。《Adaptive ordering of pipelined stream filters》研究了如何在流系统中对相关谓词排序，该算法采用贪心算法进行选择排序，并在运行时采集样本估计选择性。CORE 的查询优化算法给出了一个最优解，并使用分支定界搜索在代理模型空间中快速修剪计划。
《Optimization of Complex Dataflows with User-Defined Functions》研究了复杂用户自定义函数在 map-reduce 型大数据系统上的各种优化技术，如谓词简单化和 UDF 语义推理。
这些技术与 CORE 的解决方案是正交的。基于采样的近似查询处理技术是通过在数据的一个小采样子集上运行查询来提供查询的近似答案，而 CORE 利用 ML 推理谓词的准确性提供近似答案。
2. 机器学习中的代理模型（级联分类器）
最早的代理模型是通过级联一系列轻量级分类器来丢弃图像的背景区域，以加速目标检测，改进分类、检测、语义图像分割和姿态估计的性能。与使用分类器级联来快速拒绝图像的子区域的方法不同，CORE 使用代理模型来减少 ML 推理的 UDF 要处理的记录的大小。
与将代理模型集成到 DNN 模型中来提高训练阶段的性能的方法不同，本文的 CORE 使用代理模型作为单独的操作符来加速 ML 推理。
3. 数据库中的代理模型
代理模型最近常被应用于大数据系统中，以加速基于 ML 推理的分析任务。《NoScope: Optimizing Deep CNN-Based Queries over Video Streams at Scale》提出 NoScope 首次在昂贵的 DNN 之前级联了一个廉价的模型，以加速选择视频查询。之后，使用代理模型优化了某些视频查询类别，包括无保证选择、统计保证选择、聚合和限制查询。
《Task-agnostic Indexes for Deep Learning-based Queries over Unstructured Data》中提出了一种通用索引解决方案，以加速对目标 DNN 诱导的模式的视频查询。
4. 概率谓词（Probabilistic Predicates or PP）
代理模型最近常被应用于大数据系统中，以加速基于 ML 推理的分析任务。《NoScope: Optimizing Deep CNN-Based Queries over Video Streams at Scale》提出 NoScope 首次在昂贵的 DNN 之前级联了一个廉价的模型，以加速选择视频查询。
之后，使用代理模型优化了某些视频查询类别，包括无保证选择、统计保证选择、聚合和限制查询。《Task-agnostic Indexes for Deep Learning-based Queries over Unstructured Data》中提出了一种通用索引解决方案，以加速对目标 DNN 诱导的模式的视频查询。
5. 概率谓词（Probabilistic Predicates or PP）
图 4 概率谓词查询计划示例
概率谓词（PP）通过在昂贵的 ML 推理的 UDF 之前插入多个离线构建的代理模型，并假设谓词之间是独立的，从而优化了各种域查询。概率谓词是代理模型的另一种形式，每个 PP 都是一个廉价的分类器，用来预测输入记录匹配谓词子句的可能性，可能性很小的简单输入将立即被丢弃，而复杂输入将由后续的 ML 推理的 UDF 进一步处理。
对于具有复杂谓词的特别查询，查询优化器将离线构建多个 PP，并利用动态规划算法在查询的独立性假设下实现最大的减少。然而，PP 中的这个假设限制了它在更广泛的应用中使用。
图 5 谓词相关性实验
与前面所描述的工作不同，概率谓词和 CORE 的级联通用代理模型适用于多种领域。CORE 遵循这一工作路线，并进一步放宽了谓词的独立性假设。文章中的实验和工作表明，在 PP 中，优化器高估了构建的独立代理模型的减少量，因此产生了次优查询计划，对于具有相关谓词的新查询，性能改进甚微。这将概率谓词的使用限制在更广泛的应用中。
PART 04
系统架构
在图 3 中，CORE 的输入是一个包含多个 ML 推理的 UDF 的查询。如前所述，这些 UDF 描述行操作符；每个输入行产生一个输出行。ML 推理的 UDF 包装了诸如特征提取或分类等操作。CORE 通过在线构建代理模型来优化输入查询，并生成一个更高效计划 q*。
同时，一个查询可以有一个或多个谓词子句。输入数据的一小部分（例如: k %）用于构建代理模型，其余数据由优化的计划 q* 处理。CORE 遵循以前的论文（如 NoScope 和 PP）的范围来关注近似选择查询。
图 6 查询优化流程
图 7 代理模型元组
代理模型的特征是一个元组，其中 d 是一个输入关系（即在原始输入上应用一个字符串序列），σ 是一个目标谓词，σ' 的目的是改进 σ；M 是一种回归模型，用于为每条输入记录生成评分函数；L 是一个从输入关系 d 中构建的标记样本；R 是从精度 a 到减少率 r 的映射。
1. 通过应用代理模型进行查询优化
图 8 代理模型中精度 a 与还原率 r 之间的关系
在线构建代理模型包括收集 L 然后是训练 M；利用输入数据的初始流 L（大约几千行），标签样品 L 通过对原始输入应用 d 中指定的分类器，然后通过谓词 σ 标记得到。如果谓词 σ 满足，则标记为 +1，否则为 -1。
CORE 使用轻量级回归模型，如线性支持向量机或浅层神经网络来训练 M。图 8 表示了代理模型中精度 A 与还原率 r 之间的关系。白圈和黑圈分别表示带有 -1 和 +1 标签的记录。
CORE 借用了《Accelerating Machine Learning Inference with Probabilistic Predicates》中 AQP 风格的查询接口。具体地说，用户发出一个查询并指定一个全局目标精度 A，该精度 A 描述了除了 UDF 引起的假阴性之外代理模型的假阴性级别。
UDF 本身会产生假阳性和阴性，文章并没有打破黑箱来提高它们的准确性和性能。A 是原始查询与优化的查询 q* 保留的输出的百分比。它的值在 0 到 1 之间。它在附加错误和查询处理加速之间设置目标。
CORE 构建代理模型，考虑它们的组合，分配它们的精度参数，并将它们注入到查询计划 q* 中。为了在加速输入查询之前减少构建代理模型的计算开销和延迟，在分类器构造期间可复用中间结果，并使用分支界定搜索删除候选计划。
图 9 代理模型优化查询过程示例
上图逐步演示插入两个代理模型的优化查询：
（a）原始查询计划；
（b）插入了 σ'1 的查询计划；
（c）插入了 σ'1 和 σ'2 的查询计划。
每条边都描述了传递推文的数量，整体查询精度为 A = 54/60。
2. 精度分配
在线构建代理模型非常耗时，原因有二个：
1. 待选计划会指数级增长；
1）搜索框架
如下例所示，目标函数是非凸的，这意味着可能存在多个局部最优解。为了全局最优解，CORE 在算法中使用穷尽搜索框架（第 3 行到 4 行）。如果用户接受局部最优解，通过替换第 3 行到 4 行，算法可以很容易地扩展到其他搜索框架。
2）重复使用样品以降低标签成本
该算法通过复用早期样本（第 5 到 7 行）来提高系统的性能。
3）复用分类器来减少训练开销
该算法采用分类器复用方案（第 8 行），以避免在前面的代理模型改变其精度分配时重复训练相同的分类器。
3. 重新排序代理模型
对于不同的订单，建立在输入关系和谓词上的代理模型是不同的，它们有不同的成本。例如，在上面例子中，对于订单状态= "CA"^ emotion = positive，谓词状态= "CA"的代理模型建立在原始输入数据上。
对于订单 emotion = positive^state = "CA"，在满足 emotion = positive 谓词的记录上建立同一谓词的代理模型。因为不同的顺序会影响到代理模型的输入数据，所以这两个代理模型对于相同的 ML 推理的 UDF 有不同的执行成本。
H 中的查询计划的数量与 UDF 的数量和查询谓词的数量成指数关系。通过合并查询计划的常见组合构造了一个搜索树来表示它们。例如，X，Y 和 Z 是三个 ML 推理的 UDF。H 中有六个可能的计划（例如，XYZ 和 ZXY 等）。
图 10 显示了搜索树片段，其中每个树节点表示一个 ML 推理的 UDF 及其对应的 σ 和 σ'。一般来说，为计划构建所有代理模型在计算上是非常困难的。为了更科学地找到最优顺序，文章提出了一种基于分支界定的搜索算法来修剪候选方案。
图 10 搜索树示意图
上图中在 a = 0.9 的节点 1 开始的树上进行两次分支定界搜索迭代。蓝色文本是在调用 update_node 函数后更新的信息，如准确性、下界和上界。
1）计算成本的界限
对于给定的顺序的代理模型，可以计算总成本的下限和上限。直观地说，初始下界对应于所有代理模型都丢弃一切数据的情况；而初始上界则对应于所有代理模型都不丢弃任何数据的情况。
2）分支界定搜索
文章给出了一个常见的剪枝框架。其主要思想是在搜索过程中，随着信息的收集，可以改进上界和下界，如选择性和约简。搜索构建必要的代理模型并修剪搜索树以减少优化开销
3）使用粒度搜索树进行改进
上面讨论的分支定界搜索涉及到生成标记样本 L，然后是训练分类器 M。为了进一步加快搜索速度，将一个节点分成两个：一个 L-node 生成有标签的样本，以及 M-node 训练分类器和生成损失率和成本。另一个 L-node 必须放在它对应的 M-node 之前，也就是说，标记发生在训练之前。
例如，图 11a 中的节点X被拆分为一个 L-node，用来生成为 σ 和 M（如图 11b）；这个新树为粒度搜索树 H +。与上一节中讨论的原始搜索树相比，H+ 提供了更多的机会来收紧成本边界。
图 11 粒度搜索树示意图
PART 05
实验结果
文章对于实验使用了文本、图像和视频三个数据集：
Twitter 文本数据集
它包含了 2017 年 1 月至 2017 年 9 月在美国使用 Twitter 采样流 API 随机抽样的 200 万条推文。每条推文都是字符串，最多 140 个字符。该数据集通过使用各种 NLP 模块（如实体识别、情感分析和词性标记器）支持文本分析和检索。
COCO 图像数据集
它一个在线收集的公共数据集。它包含 123K 图像和 80 个对象类，如“人”、“自行车”和“狗”。每张图像都用多个对象标记了它们的类标签和边框位置。该数据集用于检索包含用户查询中指定的一个或多个对象类的图像。
UCF101 视频数据集
它包含从 YouTube 收集的 13K 视频。每个视频都被标记为 101 个动作类别中的一个，比如“化妆”和“攀爬”等动作。它支持使用对象检测和动作识别模型生成的标签进行视频检索。
表 1 生成的部分查询示例
目前还没有离线的具有全面 ML 操作符和谓词的 ML 推理基准。为了解决这个问题，文章在实验中为每个数据集生成 10 个查询。表 1 说明了其中一些，图 12 显示了一个示例 workflow。工作负载检索匹配给定查询谓词的文本、图像和视频，这些谓词是具有不同选择值的多个子句的连词。每个谓词子句都是 ML 生成的标签列上的一个相等条件。
关注官方微信
