InferDB—空间换时间！

date

Mar 16, 2025

slug

ml in db

status

Published

Background

将ML Inference和AP相结合是数据分析中常见的应用场景（因为Inference的数据通常都存储在数据库中），但是这样的组合方式下得到的系统却成为了数据分析场景下的瓶颈。当前的ML in data analysis的场景主要包含两个步骤：

预处理（Preprocess）

预测（Predict）

Prior Work

在DBMS中实现一个preprocess和predict的Operator

🤔

具体有以下两种具体实施方案：

将Operator转换为SQL或者user-defined function

在database中实现全新的算子

由于不同数据集的预处理流程大不相同，因此对于这种方案来说，可能需要针对不同的场景实现许多定制化的算子。同时，对于数据库内部的优化器来说，要么将这些Operator视为黑盒，要么需要针对这些Operator进行扩展，这种方案的可扩展性实在不强。

在数据库中访问ML runtime

需要在Database和ML runtime之间不同进行数据交换。同时无法和query optimizer进行整合。

Motivation

我们知道ML的训练和推理过程本质上可以理解为：用计算来换存储。那么我们能不能反过来，用存储来换计算呢（所谓的空间换时间？）

我们用一个例子来辅助理解，下面这个例子要求模型根据输入的信息预测房产价格

Prior Work

之前的架构中包含我们前面提到的两个步骤：Preprocess和Predict。预处理阶段对数据进行处理后进行encoding操作。比如对图中NaN值的特殊处理等等。

Strawman-1：Brute force index

直接对对所有train data建立索引。在推理时使用K-NN算法找到K个最近邻点，将这些预测结果通过某种aggregate方法聚合起来得到最后的预测结果。

🤔

这里需要预处理吗？不进行预处理的话怎么使用K-NN算法呢？

这样的方案缺陷也很明显：

索引数据的大小和训练数据大小成正比，可能需要大量存储空间，可行性降低

相比于simple index lookup操作，K-NN操作性能实在是太差了

但是我们观察到，有些feature不会影响所要预测的结果，比如说手机是红色还是黑色大部分时候并不会影响到手机的价格，但是手机的商标是苹果还是菊花确实会影响手机的价格的。那么我们能不能把这些会影响预测结果的feature找出来，用找出来的这些feature进行索引呢？

InferDB

Prune

我们前面提到，我们可以把对预测结果没有贡献的feature分为两部分：

in feature-prune: 部分feature没用，比如说如果两个城市的房价水平差不多，那么事实上city这个feature中的关于这两个城市的取值可以统一为一个，这样也可以减小索引的大小。

feature-prune: 整个feature都没用，比如电子商品的颜色。

In Feature-Prune

对于给定的一个feature，我们想要对feature可能的取值进行合并，将feature从连续值变为离散取值（这样可以大大减小Index的大小）。论文采用信息值（IV，一种衡量分类变量对目标变量区分能力的统计量）来作为评判分类方法的指标。采用开源工具OptBinng工具完成feature离散化的工作。经过这一步骤，我们可以合并一些冗余的feature值。

Feature-Prune

离散化的feature数量和处理前的feature数量一样，我们只是对单个feature的值域做了“减法”而已。但是正如刚才提到的，可能有些feature对最后的预测没有效用。我们可以将这些feature找出来，进一步减小Index的大小。但是枚举所有可能的feature选择情况是一种指数级别的算法，于是本文设计了一种启发式算法（基于贪心思想）。如下：

首先根据IV值对feature进行排序，依次遍历每个feature，判断将新的feature加入后是否可以是的整体的IV值提升，如果加入新的feature可以提高IV指标，则将这个feature加入结果集中。最后根据每个feature中分类数量进行降序排序（这样可以减小索引的大小）。

Index Building

构建过程其实很简单，其实就是创建一个数据库表（Predict Table），主键是pruned-feature represented input，值则是索引的结果。那么我们如何得到这个结果呢？

Aggregation

我们知道，经过我们的prune，许多不同的输入可能会被映射到相同的pruned-feature。比如代表商标的feature中，苹果和菊花可能都会被映射到相同的feature取值（都是高端产品啊）。那么对于不同的输入，模型预测的结果可能也会不同，那么我们应该如何决定在Predict Table中写入的值呢？

这篇工作采用的方法是将训练集中所有映射到相同pruned-feature的值对应的model predicted value都取出来，使用一个aggregate function将这些结果聚合成一个最后的结果放入predict table。根据任务的不同，aggregate funtion的取值也不同：

regression：取平均值

分类任务：取majority

具体定义如下：

其中

Inference

推理过程包含两个步骤：

mapping

Index Search

Mapping步骤中，

对于numerical的输入，则

对于多类别输入，则可以采用下面的处理方式

Index Search步骤中，则将Mapping步骤得到的表和Predict表做Join操作即可。

Advantage

可以做到数据库无感知（不需要修改数据库），可以直接使用现有的query engine进行查询优化

相比传统方法，性能提升两到三个量级

🤔

评价：这是一个还算不错的工作，从效果来看似乎很亮眼，性能提升了几个量级同时还不需要修改数据库内部代码。但是这个工作最本质的思想其实是通过存储换取计算，然后通过一些方法对模型进行压缩。其实是将一个模型压缩成一个类似于决策树的结构。对于如今浩浩荡荡的大模型应用场景来说，这种优化方法无法直接产生作用。一方面是因为大模型的预测不再是简单的回归或者说分类，而是生成式任务，搜索空间相比于几年前的ML场景已经大有不同。但是用存储换取计算的思想却值得学习，最近（2025年）仍有工作通过存储换取计算（比如MoonCake），效果也是不错的。所以对待比较早的论文，我想更重要的是学习其思想而不是生硬地了解具体的解决方案。