本文介绍了研究人员如何巧妙地使用Bloom过滤器使SQLite的分析查询速度提高了10倍。

**背景**

SQLite是一个基于磁盘的B树，基于行的存储。它内部使用一个名为VDBE的虚拟机来执行查询。它跨平台、单线程，几乎可以在任何地方运行。

SQLite是一个通用数据库，但在OLTP工作负载方面表现出色。然而，布法罗大学的研究人员在2015年发现，大多数查询都是简单的键值查找和复杂的OLAP查询。因此，威斯康星大学麦迪逊分校的研究人员着手使其对于分析查询更快，因为趋势正在发生变化。为了建立基线，他们使用了DuckDB。他们使用了行业标准的OLAP基准测试——星型模式基准测试（SSB）。

SSB包含一堆称为星型查询的分析查询，其中您有一个大型的事实表和多个较小的维度表。例如，事实表=客户订单，维度表=客户、商家信息、配送合作伙伴等。

**原因**

让我们弄清楚为什么SQLite速度慢；然后，我们可以确定如何使其更快。SQLite有一个编译时选项VDBE_PROFILE，它测量每个指令在VDBE中花费的CPU周期数。当他们重新运行基准测试时，他们发现了两个操作码：

* SeekRowID：给定一个rowId，在B树中探测该行。

* Column：从给定记录中提取一个列。

由于分析查询主要包含联接操作，因此让我们了解它们是如何实现的。

**数据库联接**

以下是数据库实现联接的一些方法：

* 嵌套循环联接

* 哈希联接

* 排序合并联接

SQLite执行嵌套循环联接，这是三种方法中最简单的一种。下面是一个动画（来源）显示嵌套循环联接的工作原理：

假设您有两个表：订单和客户。这里的代码描述了使用order_id列联接这两个表。外循环遍历客户表中的每个项目，并且对于每个项目，它都会遍历订单表中的每个项目。

对于每个匹配的id，它都会追加到结果列表中。循环操作等同于在B树中探测，这非常昂贵。

您的目标是减少B树探测。现在，停下来思考一下为什么这不好。你能想出一些可以改进的方法吗？

**联接顺序**

接下来，联接操作中表的顺序很重要。这是一个简单的说明：

假设有三个表：订单、客户、日期。我们的查询在客户中匹配20个项目，在日期中匹配10个项目。每当一行匹配时，我们都会探测B树。

O、C、D：10000 * 20 * 200 = 4M

O、D、C：10000 * 10 * 100 = 1M

仅仅通过翻转顺序，它就减少到1M次操作！但这对于想出一个优化的查询计划来说非常困难。这是一个NP难问题。

**优化**

我们如何优化联接？其他两种联接算法都优于嵌套循环联接。但是，作者认为哈希联接需要大量的内存，而SQLite大多在内存受限的环境中运行。其次，添加另一种联接算法会使查询计划变得复杂。

以下是一种方法：在运行这两个循环之前，您首先构建客户数据缓存。然后，在内部循环中，首先检查此缓存。只有在匹配的情况下，您才会遍历循环。

这就是研究人员所做的！他们使用了Bloom过滤器，它非常节省空间并且适合于CPU缓存行。它也很容易实现。

他们添加了两个操作码：Filter和FilterAdd。在联接操作开始时，我们遍历维度表的所有行，并设置匹配查询谓词的Bloom过滤器中的位。操作码是FilterAdd。在联接操作期间，我们首先检查每一阶段的行是否存在于Bloom过滤器中。如果存在，则执行B树探测。这是Filter操作码。

**结果**

这是优化的查询计划。

这是优化后的CPU周期分析。您可以看到大型蓝色条几乎消失了！

结果？SQLite的速度提高了7到10倍！

这项研究的结果已经应用于SQLite，并在v3.38.0中发布。

**总结**

Bloom过滤器之所以很棒，是因为：

* 最小的内存开销

* 与SQLite的简单实现非常契合

* 在现有的查询引擎中工作。