# DBSP：流上的增量计算及其在数据库中的应用 **DBSP: Incremental Computation on Streams and Its Applications to Databases** Mihai Budiu, Tej Chajed, Frank McSherry, Leonid Ryzhyk, Val Tannen *SIGMOD Record, Vol. 53, No. 1, March 2024*（SIGMOD Research Highlights 专栏） 原文 PDF： --- ## 译者说明 - 本文是上述论文（§1–§7）的中文全译，段落逐段对应，章节编号与原文一致；§8 参考文献未翻译。 - 这是 VLDB 2023 最佳论文《DBSP: Automatic Incremental View Maintenance for Rich Query Languages》的**精简改写版**：内容同源，但行文被重写、篇幅约为原文一半，并新增了 §6 中关于查询计划质量、启动成本与工业采用的讨论。建议与本项目里的 VLDB 2023 全译本对照阅读。 - 版权归原作者所有，本译文仅供学习研究使用。 - 原文中的电路图已重绘为文字示意图，表格重画为 Markdown 表格；公式为 LaTeX 记号，配套的 `.html` 文件可在浏览器中自动渲染（首次打开需联网加载 MathJax）。 - **关于符号还原**：这份 PDF 的文本层缺失了大量数学符号——减号、希腊字母、$\Sigma$、$\cong$、$\uparrow$、$\int$ 等会直接消失，`↵` 则是 `ff` 连字。译文中的这些符号是依据 VLDB 2023 版正文与 arXiv 版 LaTeX 源码逐处核对后还原的；极少数无法确证之处采用了最保守的读法，正文中未作臆测性补充。 --- ## 目录 - [摘要](#摘要) - [1 引言](#1-引言) - [1.1 增量计算](#1-1-增量计算) - [1.2 电路与流](#1-2-电路与流) - [1.3 流](#1-3-流) - [1.4 数据库即流](#1-4-数据库即流) - [1.5 贡献](#1-5-贡献) - [2 流算子](#2-流算子) - [3 增量视图维护](#3-增量视图维护) - [4 关系代数的 IVM](#4-关系代数的-ivm) - [4.1 ℤ-集合](#4-1-ℤ-集合) - [4.2 关系算子的实现](#4-2-关系算子的实现) - [4.3 增量视图维护](#4-3-增量视图维护) - [4.4 关系查询示例](#4-4-关系查询示例) - [4.5 SQL](#4-5-sql) - [6 实现](#6-实现) - [7 结论](#7-结论) --- **DBSP：流上的增量计算及其在数据库中的应用**（DBSP: Incremental Computation on Streams and Its Applications to Databases）[^1] - Mihai Budiu，Feldera，mbudiu@feldera.com - Tej Chajed，Univ. of Wisconsin-Madison，chajed@wisc.edu - Frank McSherry，Materialize Inc.，mcsherry@materialize.com - Leonid Ryzhyk，Feldera，leonid@feldera.com - Val Tannen，University of Pennsylvania，val@seas.upenn.edu ## 摘要 我们介绍 DBSP，一个用于增量计算的框架。增量计算会反复地对某些“不断变化”的输入值求值一个函数。高效实现的目标是“复用”此前已经计算出的结果。理想情况下，当输入出现新的变化时，增量计算只应花费与输入变化的大小成正比的工作量，而不是与整个数据集的大小成正比。 在数据库领域，“增量计算”被称为增量视图维护（incremental view maintenance, IVM）；IVM 长期以来一直是数据库理论与实践中的核心问题。针对受限的计算类别或变化类别，人们已经提出了许多解决方案，但我们寻求的是一种通用的解决方案。 我们首先借鉴数字信号处理（Digital Signal Processing, DSP）的思想，把增量计算定义为数据流上的计算——数据流即数据值构成的序列。 借助这些工具，我们分 4 步给出增量计算问题的一个通用解决方案：(1) 我们描述一种称为 DBSP 的简单而富有表达力的语言，用于描述数据流上的计算；(2) 我们给出 DBSP 程序上增量计算的一个新的数学定义；(3) 我们给出一个通用算法，把任意 DBSP 程序转换为增量程序。该算法把“对复杂查询增量化”的问题，归约为“对组成该查询的各基本操作分别增量化”的问题。最后，(4) 我们说明，实用的数据库查询语言（例如 SQL 与 Datalog）可以直接构建在 DBSP 之上，所用原语都具有高效的增量实现。因此，我们得到了一个通用配方，可为用所有这些语言编写的、本质上任意的查询给出高效的 IVM。 ## 1 引言 ### 1.1 增量计算 增量视图维护（incremental view maintenance, IVM）是数据库中一个重要且已被深入研究的问题 [14]。IVM 问题可以表述如下：给定一个大型数据库 $DB$（比如说 10 亿条记录）和一个视图 $V$，$V$ 由查询 $Q$ 描述。IVM 的目标是在数据库发生变化时保持 $V$ 的内容最新。 作为一个具体例子，考虑下面这条定义视图的 SQL 语句：`CREATE VIEW V AS SELECT * FROM T WHERE Age >= 10`。在这个例子中，定义视图 $V$ 的查询 $Q$ 就是 `SELECT * FROM T WHERE Age >= 10`。视图 $V$ 始终包含表 $T$ 中 `Age` 列的取值大于或等于 10 的所有行。 一般地，查询是施加于数据库状态的函数：$V = Q(DB)$。一种朴素的解法是：每当数据库发生变化，就重新执行一次查询 $Q$，如下图所示。图中水平轴是时间；标有 $\Delta$ 的水平箭头表示对数据库的变化，我们假定这些变化远小于数据库本身（例如，一次变化可能只触及约 100 条记录）。竖直的“向上”箭头表示对每个数据库快照重新求值 $Q$。 ``` V[1] V[2] V[3] V[4] ▲ ▲ ▲ ▲ │Q │Q │Q │Q ← 竖直箭头：对每个快照重新求值 Q │ │ │ │ DB[1] ───▶ DB[2] ───▶ DB[3] ───▶ DB[4] ← 数据库快照（约 1B 行） ΔDB[1] ΔDB[2] ΔDB[3] ← 水平箭头：变化（约 100 行） 时间 ────────────────────────────────────────────▶ ``` 这种朴素解法的开销很大。在视图的第一个版本构造出来之后，理想的算法应当只计算视图的变化 $\Delta V$，所做的工作量为 $O(|\Delta DB|)$。理想情况下，我们希望构造一个新的查询 $Q^\Delta$，它具有性质 $\Delta V = Q^\Delta(\Delta DB)$，即 $Q^\Delta$ 能够由数据库的变化算出视图的变化： ``` ΔDB[0] ΔDB[1] ΔDB[2] ΔDB[3] │ │ │ │ ▼ ▼ ▼ ▼ [ Q ] [ Q^Δ ] [ Q^Δ ] [ Q^Δ ] │ │ │ │ ▼ ▼ ▼ ▼ V[1] ΔV[1] ΔV[2] ΔV[3] ``` 图中第一个输入（初始的整个数据库）需要完整求值 $Q$ 才能得到 $V[1]$；此后每一步只需用 $Q^{\Delta}$ 由该步的变化 $\Delta DB[t]$ 算出视图的变化 $\Delta V[t]$，再把它累加到前一个视图快照上，即得 $V[t+1]$。 我们把 $Q^\Delta$ 称为 $Q$ 的增量版本。如果把 $Q^\Delta$ 看作 $\Delta DB$ 的函数，则可以证明：上面所描述的那种理想方案是无法达到的。 本文提出一种定义 $Q^\Delta$ 的新方式，即把它视为流上的一种计算。我们的模型受数字信号处理（Digital Signal Processing, DSP）[16] 的启发并应用于数据库，DBSP 由此得名。$Q^\Delta$ 可以非常高效。与传统数据库查询一样，$Q^\Delta$ 的性能既取决于查询 $Q$，也取决于该查询实际作用的数据。粗略地说，由我们的算法构造的 $Q^\Delta$ 比 $Q$ 快 $O(|DB|/|\Delta DB|)$ 倍。在实践中，这可能是若干个数量级的改进。就上面的例子而言，$|DB| \approx 10^9$、$|\Delta DB| \approx 10^2$，这可以使 $Q^\Delta$ 快一千万倍！ 我们不把数据库看作一个不断变化的大对象，而是把它建模为数据库快照构成的序列（即流）。类似地，相继的视图快照也构成一个流。DBSP 是一种在流上计算的简单编程语言；其输入与输出都是取任意值的流。DBSP 语言只有 4 个算子。然而，它可以表达丰富的流计算，包括重复计算（类似于上面重复出现的查询 $Q$）、计算不动点的递归计算（如 Datalog 程序）、流式计算，以及增量计算（我们稍后定义）。完整论文 [5] 给出了 DBSP 的精确数学描述，本文的呈现为传达主要直觉做了简化。本文省略了相关工作一节。 本文的核心结果是算法 4.1：给定一个在值流上计算的 DBSP 程序，它能机械地把该程序转换为一个在变化流上计算的增量 DBSP 程序。 DBSP 与数据库没有任何绑定；事实上它是一种图灵完备的语言，可用于许多其他目的。但它在数据库领域表现得特别好，原因有两个： - DBSP 作用于来自交换群（阿贝尔群）的值。数据库可以建模为一个交换群。 - DBSP 把“对复杂程序增量化”的问题，归约为“对程序中出现的每个基本操作分别增量化”的问题。对于数据库，所有基本操作都有已知的高效增量实现。 ### 1.2 电路与流 本文用电路图来描绘程序。在电路中，矩形表示一个函数，箭头表示一个输入或输出值。下图给出一个函数 $f$，它消费两个输入 $i$（第 0 个输入）与 $j$（第 1 个输入），产生一个输出 $o = f(i, j)$： ``` i ──▶ 0 ┐ ├──▶ [f] ──▶ o j ──▶ 1 ┘ ``` 我们处理的大多数函数都是可交换的（即与参数的顺序无关），因此可以省略输入标号，把上面的电路画成： ``` i ──┐ ├──▶ [f] ──▶ o j ──┘ ``` 函数及其电路可以复合，例如下面这个函数 $o = g(s) + (f(s) \times s)$： ``` s ──▶ [f] ──▶ f(s) ──┐ ├──▶ [×] ──▶ f(s)×s ──┐ s ───────────────────┘ ├──▶ (+) ──▶ o s ──▶ [g] ──▶ g(s) ────────────────────────┘ ``` 如果两个电路计算相同的函数，我们就说它们是等价的。我们用符号 $\cong$ 表示电路等价。例如，我们有如下电路等价（其中 $\circ$ 表示函数复合）： ``` s ──▶ [g] ──▶ [f] ──▶ o ≅ s ──▶ [f ∘ g] ──▶ o (*) ``` ### 1.3 流 DBSP 的核心概念是流。给定一个集合 $A$，一个取值为 $A$ 中值的流是 $A$ 中值构成的无限序列。$\mathcal{S}_A$ 表示所有取值为 $A$ 中值的流构成的集合。我们把流 $s$ 的第 $t$ 个元素写成 $s[t]$。把 $t$ 看作“时间”，把 $s[t] \in A$ 看作流 $s$ “在时刻” $t$ 的值。我们把流画成一串方框，时间自右向左递增：例如，流 $s[t] = t$ 是： ``` …… ┌───┬───┬───┬───┐ │ 3 │ 2 │ 1 │ 0 │ └───┴───┴───┴───┘ 时间 ◀──────────────（越靠左越晚） ``` 流算子是作用在流上、并产生流的函数。一般地，我们用“算子”指流上的函数，用“函数”指“标量”值上的计算。我们用双箭头表示流。下图给出一个流算子 $T$，它消费两条输入流 $s_0$ 与 $s_1$，产生一条输出流 $s$： ``` s0 ══▶ 0 ┐ ├──▶ [T] ══▶ s s1 ══▶ 1 ┘ ``` 我们写 $s = T(s_0, s_1)$。给定函数 $f : A \to B$，我们通过把函数 $f$ 独立地作用于每个输入值，定义一个流算子 ${\uparrow}f : \mathcal{S}_A \to \mathcal{S}_B$（读作“$f$ 的提升”）： ``` · · · d c b a ══▶ [↑f] ══▶ · · · f(d) f(c) f(b) f(a) ``` 为简化记号，对两个流 $a$、$b$，我们写 $a + b$，而不写 $a\,(+)\,b$；同样，我们把 $(-)a$ 写成 $-a$。 ### 1.4 数据库即流 我们通常把流看作“小”值的序列，例如数据库中的插入或删除。不过，我们也把整个数据库看作数据库快照构成的流。我们把数据库建模为一条流 $DB$。时间不是墙钟时间，而是对施加于数据库的事务的计数。由于事务是可线性化的，它们具有全序。$DB[t]$ 是已施加 $t$ 个事务之后数据库内容的快照。这一记号在 §1.1 的图中可以看出来。 数据库事务也构成一条流 $\Delta DB$，这一次是施加于数据库的变化（delta）的流。该流的值定义为 $(\Delta DB)[t] = DB[t] - DB[t-1]$，其中“$-$”表示两个数据库之间的差，我们很快就会更精确地刻画这一概念。$\Delta DB$ 流可以由 $DB$ 流经流微分算子（stream differentiation operator）$\mathcal{D}$ 产生；该算子把其输入流的变化流作为输出；因此有 $\mathcal{D}(DB) = \Delta DB$。 反过来，时刻 $t$ 的数据库快照是施加截至 $t$ 的全部事务的累积结果：$DB[t] = \Delta DB[0] + \Delta DB[1] + \cdots + \Delta DB[t]$。流算子 $\mathcal{I}$ 定义为把此前所有输入累加起来产生每个输出。我们称 $\mathcal{I}$ 为流积分，它是流微分的逆。下图给出流 $\Delta DB$ 与 $DB$ 之间的关系： ``` ΔDB ──▶ [ I ] ──▶ DB ──▶ [ D ] ──▶ ΔDB ``` 在这个模型中，视图也是一条流。设查询 $Q$ 定义一个视图 $V$。数据库流的每个快照都对应视图的一个快照：$V[t] = Q(DB[t])$。因此，视图只是一个提升后的查询：$V = ({\uparrow}Q)(DB)$。 有了这些基本定义，我们就可以精确地定义 IVM。增量地维护一个视图意味着什么？一个维护算法需要在给定数据库变化的情况下，计算视图的变化。给定查询 $Q$，本文的一个关键贡献是利用流积分与流微分定义它的增量版本 $Q^\Delta$，其图形表示如下： ``` ΔDB ──▶ [ I ] ──▶ [ ↑Q ] ──▶ [ D ] ──▶ ΔV DB V ``` 图中 $[I]$ 与 $[D]$ 分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$；导线上标注的 $DB$ 与 $V$ 是中间流；整个电路即 $Q^{\Delta}$。 用数学写出来：$Q^\Delta = \mathcal{D} \circ ({\uparrow}Q) \circ \mathcal{I}$。查询 $Q$ 的增量版本是一个流式算子 $Q^\Delta$，它直接在变化上计算并产生变化。因此，查询的增量版本总是良定义的。上述定义给出了增量地计算一个查询的一种方式，但朴素地应用它会产生低效的执行（因为它会在每一步重建数据库）。事实上，它和朴素解法一样糟糕。在 §3 中我们说明如何优化 $Q^\Delta$ 的实现。关键性质是：我们可以把 $\cdot^\Delta$ 算子“下推”到查询计划中：$(Q_1 \circ Q_2)^\Delta = Q_1^\Delta \circ Q_2^\Delta$。 借助这套一般性的增量计算理论，我们在 §4 中说明如何在 DBSP 中建模关系查询。这立即给出一个计算任意关系查询增量版本的通用算法。这些结果此前已为人所知，但 DBSP 为它们提供了简洁的建模。§5 说明包含递归的程序如何能在 DBSP 中实现并增量化。例如，给定以自然递归方式实现的传递闭包，我们的算法能生成一个程序，在节点与边被添加和删除时高效地维护该图的传递闭包。 ### 1.5 贡献 本文作出如下贡献： 1. 我们引入 DBSP，一种简单而富有表达力的流式计算语言。DBSP 给出了一个优雅的形式基础，统一了对流式计算与增量计算的处理。 2. 一个算法，用于将 DBSP 中表达的任何流式计算增量化，并且能处理来自任意数据源的任意插入与删除。 3. 说明 DBSP 如何建模各类实用查询，例如关系代数、嵌套关系、聚合，以及 Datalog。 4. 第一个通用的、经过机器检查的 IVM 理论。本文原始版本 [5] 中的所有理论结果，都已使用 Lean 证明助手 [8] 在 [7] 中检查过。 5. 把该理论实现为一个运行时与一个 SQL 编译器，构成一个实用的开源实现。 [^1]: 版权归作者所有。出版权授予 VLDB Endowment。本文是论文《DBSP: Automatic Incremental View Maintenance for Rich Query Languages》的简化版，该文发表于 PVLDB 第 16 卷第 7 期，ISSN 2150-8097 [5]。DOI: https://doi.org/10.14778/3587136.3587137 ## 2 流算子 在本文余下的部分，我们要求流 $\mathcal{S}_A$ 的取值集合 $A$ 构成一个交换群（阿贝尔群），其运算为 $+$、$-$，以及一个 $0$（零）值。加法定义了“加入新数据”的含义，而减法使我们能够计算差（增量）。我们稍后会说明，这一要求对于在数据库语境中使用 DBSP 并不构成问题。 流算子在数学上非常强大，但在 DBSP 中我们把自己限制在一个很小的子集上。所有 DBSP 计算都是因果的（causal）[4]：时刻 $t$ 的输出在时刻 $t$ 的所有输入都被接收之后立即产生；时刻 $t$ 的输出不能依赖于在 $t$ 之后到达的输入。 下面的电路等价告诉我们，可以通过分别提升电路中的每个函数来提升整个电路： ``` s ──▶ [↑g] ──▶ [↑f] ──▶ o ≅ s ──▶ [↑(f ∘ g)] ──▶ o (**) ``` 延迟算子 $z^{-1}$ 通过把输入延迟一步来产生输出流（并以 0 起始）[^1]： ``` · · · d c b a ──▶ [z⁻¹] ──▶ · · · c b a 0 ``` 延迟算子有一个非常重要的性质：它在收到第一个输入之前就产生第一个输出，在收到第二个输入之前就产生第二个输出，依此类推。 我们把微分算子定义为若干其他算子的复合：$\mathcal{D}(s) \overset{\mathrm{def}}{=} s - z^{-1}(s)$，图示如下： ``` s ──┬──────────▶ ( + ) ──▶ D(s) │ ▲ └─▶ [z⁻¹] (−) ─┘ ``` 若 $s$ 是一个流，则 $\mathcal{D}(s)$ 是 $s$ 的变化流；输出中的每个值是输入中两个相邻值之差。例如： ``` D( · · · 1 2 1 0 ) = · · · 1 2 1 0 − z⁻¹( · · · 1 2 1 0 ) = · · · 1 2 1 0 − · · · 2 1 0 0 = · · · −1 1 1 0 ``` 积分算子由下面的电路给出： ``` s ──▶ ( + ) ──▶ I(s) = o ▲ │ └──[z⁻¹]◀────────┘ ``` 虽然这个定义看起来有些奇怪，因为输出流被用来计算它自己，但“反馈”环中延迟算子的使用保证了：在计算当前值时只用到输出的先前值。为便于阅读公式，我们使用记号 $o = \mathcal{I}(s)$，于是可以看到流 $o$ 的内容是逐步产生的： $$o[0] = s[0] + (z^{-1}(o))[0] = s[0] + 0 = s[0]$$ $$o[1] = s[1] + (z^{-1}(o))[1] = s[1] + o[0] = s[1] + s[0]$$ $$o[2] = s[2] + (z^{-1}(o))[2] = s[2] + o[1] = s[2] + (s[1] + s[0])$$ 一般地，$\mathcal{I}(s)[t] = o[t] = \sum_{i \leq t} s[i]$。例如： ``` I( · · · 3 2 1 0 ) = · · · 6 3 1 0 I( · · · −1 1 1 0 ) = · · · 1 2 1 0 . ``` 积分与微分互为逆运算：$\mathcal{D}$ 计算一个流的变化，而 $\mathcal{I}$ 在给定变化流的情况下重构出原来的流。把 $\mathcal{I}$ 与 $\mathcal{D}$ 依次施加时，二者会“相互抵消”： ``` s ──▶ [I] ──▶ [D] ──▶ o ≅ s ──▶ o ≅ s ──▶ [D] ──▶ [I] ──▶ o ``` ## 3 增量视图维护 本节的结果并不专属于数据库：它们对任何流计算都成立，但我们仍会提示它们在数据库中的适用性。 给定流算子 $S : \mathcal{S}_A \to \mathcal{S}_B$，我们如下定义 $S$ 的增量版本： ``` Δs ──▶ [I] ──s──▶ [S] ──o──▶ [D] ──▶ Δo ``` 图中 $[I]$ 与 $[D]$ 分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$；导线上标注的 $s$ 与 $o$ 是中间流。整个电路即 $S^{\Delta}$。 若 $S$ 在一个流 $s$ 上计算，则 $S^{\Delta}$ 在 $s$ 的变化流上计算。若 $S$ 产生一个流 $o$，则 $S^{\Delta}$ 产生 $o$ 的变化流。注意，这个定义并不要求 $S$ 是提升函数。 对于有多个输入与输出的算子，我们通过对每个输入施加 $\mathcal{I}$、对每个输出施加 $\mathcal{D}$ 来定义增量版本，例如：$T^{\Delta}(a, b) \overset{\mathrm{def}}{=} \mathcal{D}(T(\mathcal{I}(a), \mathcal{I}(b)))$。 $S^{\Delta}$ 有许多很好的性质： **链式法则（chain rule）**指出 $(Q_1 \circ Q_2)^{\Delta} = Q_1^{\Delta} \circ Q_2^{\Delta}$，即下面这些电路等价： ``` Δi ──▶ [I] ──▶ [Q₁] ──▶ [Q₂] ──▶ [D] ──▶ Δo ≅ Δi ──▶ [I] ──▶ [Q₁] ──▶ [D] ──▶ [I] ──▶ [Q₂] ──▶ [D] ──▶ Δo ≅ Δi ──▶ [Q₁^Δ] ──▶ [Q₂^Δ] ──▶ Δo ``` 在数据库领域，这句话可以这样理解：要对一个复合查询做增量化，你可以分别对每个子查询做增量化。这给了我们一个简单的、确定性的配方，把任意查询的增量版本归约为其基本算子的增量版本。 **循环法则（cycle rule）**指出下面这些电路等价： ``` Δs ──▶ [I] ──▶ [T] ──┬──▶ [D] ──▶ Δo └──[z⁻¹]──▶（回送到 [T] 的输入） ≅ Δs ──▶ [T^Δ] ──┬──▶ Δo └──[z⁻¹]──▶（回送到 [T^Δ] 的输入） ``` （我们省略了 $T$ 各输入上的标号。）换言之，一个查询周围反馈环的增量版本，就是把环体换成该查询的增量查询之后的同一个反馈环。这个结果对于递归查询会很有用。 我们称算子 $S$ 是**线性的（linear）**，如果它具有性质 $S(a + b) = S(a) + S(b)$（其中 $+$ 是流的加法）。对线性算子 $S$，有 $S^{\Delta} = S$。这非常有用，因为许多基本的数据库操作都可以实现为线性算子：选择、投影、过滤、分组，以及聚合的一部分，都是线性的。此外，下列算子也是线性的：$+$、$z^{-1}$、$\mathcal{I}$、$\mathcal{D}$，以及 ${\uparrow}f$（若 $f$ 是线性函数）。 我们称有两个输入的算子 $T$ 是**双线性的（bilinear）**，如果它对流的加法满足分配律：$T(a + b, c) = T(a, c) + T(b, c)$，且 $T(a, c + d) = T(a, c) + T(a, d)$。（这类似于乘法对加法的分配律。）在数据库中，交、连接与笛卡尔积都是双线性的。 采用中缀记号，对双线性算子 $\times$ 我们有： $$(\Delta a \times \Delta b)^{\Delta} = \Delta a \times \Delta b + z^{-1}(\mathcal{I}(\Delta a)) \times \Delta b + \Delta a \times z^{-1}(\mathcal{I}(\Delta b)) = \Delta a \times \Delta b + z^{-1}(a) \times \Delta b + \Delta a \times z^{-1}(b)$$ 如果忽略该等式中的延迟算子，我们就得到众所周知的连接增量查询（join delta query）公式，例如见 [15]。 ``` 电路 1（定义）： Δa ──▶ [I] ───┐ ├──▶ [×] ──▶ [D] ──▶ Δo Δb ──▶ [I] ───┘ ≅ 电路 2（展开）： 第 1 项 Δa ──▶ [×] ◀── Δb ⇒ Δa × Δb 第 2 项 Δa ──▶ [I] ──▶ [z⁻¹] ──▶ [×] ◀── Δb ⇒ z⁻¹(I(Δa)) × Δb 第 3 项 Δb ──▶ [I] ──▶ [z⁻¹] ──▶ [×] ◀── Δa ⇒ Δa × z⁻¹(I(Δb)) 三项在 ( + ) 处相加 ──▶ Δo ``` 图中 $[\times]$ 表示双线性算子（笛卡尔积或连接），$(+)$ 把三个乘积相加；输入 $\Delta a$ 与 $\Delta b$ 均有多路扇出。 这个图背后的直觉是什么？让我们考虑笛卡尔积 $a \times b$ 的情形。增量乘积的输入是 $\Delta a = \mathcal{D}(a)$ 与 $\Delta b = \mathcal{D}(b)$。当我们向关系 $a$ 加入一行 $x$ 时（即 $\Delta a = x$）会发生什么？新行 $x$ 会与完整关系 $b$ 的先前版本中的每一行组合，出现在输出的变化中。算子 $\mathcal{I}(b)$ 实际上从变化流 $\Delta b$ 计算出关系 $b$，而对它施加 $z^{-1}$ 就得到它的先前版本。因此底部的 $\times$ 算子计算 $x \times z^{-1}(b) = \Delta a \times z^{-1}(\mathcal{I}(b))$，即新行 $x$ 所产生的变化。顶部的 $\times$ 算子对 $b$ 关系的变化执行对称的操作。中间的 $\times$ 算子产生两个输入的变化所共同导致的结果。 ## 4 关系代数的 IVM 本节我们把关于增量计算的结果应用到关系数据库上。正如引言所述，我们的目标是高效地计算任意关系查询 $Q$ 的增量版本。 然而，我们面临一个技术问题：我们说过流要求其取值属于交换群，而关系数据库一般并不是交换群，因为它们操作的是集合。幸运的是，数据库文献中有一个著名的工具，它通过用 ℤ-集合（Z-set，也称为 z-关系 [12]）表示集合，把集合运算转换为群运算。 ### 4.1 ℤ-集合 ℤ-集合推广了数据库表：可以把 ℤ-集合想成一张表，其中每一行都关联一个整数权重，该权重可能为负。这个权重表明该行属于该表多少次。 下面的表给出了一个有三行的 ℤ-集合的例子。第一行的值为 joe，权重为 1。我们不显示权重为 0 的行。 | 行 | 权重 | |---|---| | joe | 1 | | mary | 2 | | anne | −1 | ℤ-集合推广了集合与多重集：一个集合可以这样表示为 ℤ-集合——给每个元素关联权重 1。多重集（数据库文献中也称为“包”）是所有权重都为正的 ℤ-集合。关键在于，ℤ-集合还能表示对集合与包的变化。负权重表示正在被删除的行。 我们可以对取给定类型的值的 ℤ-集合定义三个运算：(1) 零（所有权重都为 0 的 ℤ-集合）；(2) 取负：把所有权重取负；(3) 加：把具有相同值的行的权重相加。借助这些运算，ℤ-集合构成一个交换群。 我们在 ℤ-集合上定义函数 $\mathit{distinct}$。该函数的输出是一个 ℤ-集合，其中输入中所有权重为负的行都被去掉，而所有正的权重都变为 1。例如，上述 ℤ-集合的 $\mathit{distinct}$ 为： | 行 | 权重 | |---|---| | joe | 1 | | mary | 1 | 注意，$\mathit{distinct}$ 从多重集中“去掉”重复项，它同时也消去了权重为负的行。 [^1]: 这个古怪的名称来自数字信号处理（digital signal processing）。 ### 4.2 关系算子的实现 关系代数可以用 ℤ-集合（Z-set）上的计算来实现，这一点此前已有工作表明，例如 [13]。关系算子到 ℤ-集合上函数的翻译见表 1。函数（$\pi$、$\sigma$、$\bowtie$、$\times$）即标准关系算子：投影、选择、连接、笛卡尔积。表 1 的第一行表明，复合查询是递归地翻译的：先实现各个子查询，再用箭头把它们连接起来。这就给出了把任意关系查询计划翻译成电路的配方。 **表 1**：把 SQL 关系集合算子实现为在 ℤ-集合上计算的电路。 | 操作 | SQL 示例 | DBSP 电路 | 说明 | |---|---|---|---| | 复合
（composition） | `SELECT ... FROM`
`( SELECT ... FROM I )` | `I ──▶ [C_I] ──▶ [C_O] ──▶ O` | $C_I$ 是内层查询的电路，
$C_O$ 是外层查询的电路。 | | 并
（union） | `( SELECT * FROM I1 )`
`UNION`
`( SELECT * FROM I2 )` | `I1 ──┐`
` ├──▶ [+] ──▶ [distinct] ──▶ O`
`I2 ──┘` | $\mathit{distinct}$ 消除重复。
`UNION ALL` 的实现不需要 $\mathit{distinct}$。 | | 投影
（projection） | `SELECT DISTINCT I.c`
`FROM I` | `I ──▶ [π_c] ──▶ [distinct] ──▶ O` | 每一行连同其权重原样投影，
再把相同行的权重相加。 | | 过滤
（filtering） | `SELECT * FROM I`
`WHERE P(...)` | `I ──▶ [σ_P] ──▶ O` | $P$ 是作用于每一行的谓词。
逐行单独选择：若该行被选中则保留其权重，
否则令权重为 0。 | | 笛卡尔积
（Cartesian product） | `SELECT I1.*, I2.*`
`FROM I1, I2` | `I1 ──┐`
` ├──▶ [×] ──▶ O`
`I2 ──┘` | 二元组 $(a,b)$ 的权重是 $a$ 的权重与 $b$ 的权重之积。 | | 等值连接
（equi-join） | `SELECT I1.*, I2.*`
`FROM I1 JOIN I2`
`ON I1.c1 = I2.c2` | `I1 ──┐`
` ├──▶ [⋈_{c1=c2}] ──▶ O`
`I2 ──┘` | 把出现在输出中的行的权重相乘。 | | 交
（intersection） | `( SELECT * FROM I1 )`
`INTERSECT`
`( SELECT * FROM I2 )` | `I1 ──┐`
` ├──▶ [⋈] ──▶ O`
`I2 ──┘` | 两个关系具有相同模式时等值连接的特例。 | | 差
（difference） | `SELECT * FROM I1`
`EXCEPT`
`SELECT * FROM I2` | `I1 ──┐`
` ├──▶ [+] ──▶ [distinct] ──▶ O`
`I2 ──▶ [−] ──┘` | $\mathit{distinct}$ 把权重为负的行从结果中移除。 | 这一翻译相当直接，但许多算子都需要施加一次 $\mathit{distinct}$ 才能产生集合。例如，$a \cup b = \mathit{distinct}(a + b)$，$a \setminus b = \mathit{distinct}(a - b)$。在 ℤ-集合上做过滤与在集合上做过滤完全一样，只是保留了每个值的权重。在 ℤ-集合上做选择与在集合上做选择类似，但也保留权重。 这是用 ℤ-集合对关系代数——现代数据库所依赖的基础数学理论——的一个忠实实现。这种实现会产生大量的 $\mathit{distinct}$ 算子，但已有一些已知的优化可以去掉其中一部分。 表 1 中的以下函数是线性的：$\sigma$、$\pi$、$-$、$+$。以下函数是双线性的：$\times$、$\bowtie$。事实上，唯一的非线性函数是 $\mathit{distinct}$。因此，这些函数（提升后）都有非常高效的增量版本。 为了解释这些函数为什么是线性的，考虑引言中的过滤查询（`WHERE`）。当我们向输入中加入一行时，输出的变化是什么？只需检查新行的谓词即可。如果谓词返回真，新行就被加入输出。因此输出的变化只依赖于输入的变化，而不依赖于输入的实际内容。这正是该运算线性的原因。 ### 4.3 增量视图维护 让我们考虑定义视图 $V$ 的关系查询 $Q$。下面的算法为 $Q^{\Delta}$ 构造一个 DBSP 电路： **算法 4.1**（增量视图维护）： 1. 使用表 1 中的规则把 $Q$ 翻译成电路。 2. [可选] 去掉一些 $\mathit{distinct}$ 运算。 3. 提升整个电路，把它转换为一个作用于流的电路，使用 §2 中的公式 (**)。 4. 对整个电路做增量化，即用 $\mathcal{I}$ 和 $\mathcal{D}$ 把它“包围”起来。 5. 递归地应用链式法则，产生一个只使用基本增量算子的电路。 该算法是确定性的；运行时间与查询中算子的数量成正比。第 (2) 步产生一个等价电路，其中的 $\mathit{distinct}$ 算子更少。第 (3) 步得到一个电路，它消费完整数据库快照流并输出视图快照流。第 (4) 步得到一个电路，它消费数据库变化流并输出视图变化流；然而该电路的内部运算是非增量的，因为它使用积分重建完整的数据库。第 (5) 步通过把每个基本算子替换为其增量版本，对电路进行优化。它本质上在电路的每条边上加一对 $\mathcal{I} \to \mathcal{D}$，然后用链式法则把每个 $\mathcal{I} \to Q \to \mathcal{D}$ 替换为 $Q^{\Delta}$。 运行该算法之后，所有基本运算都被替换为其增量版本。表 1 中唯一的非线性运算是 $\mathit{distinct}$。然而，$\mathit{distinct}$ 有一个高效的增量实现（这个构造此前也已为人所知，但我们用流算子的形式给出），如下图所示： ``` Δd ──▶ [(↑distinct)^Δ] ──▶ Δo ≅ Δd ──┬──▶ [I] ──▶ [z⁻¹] ──┐ │ ├──▶ [↑H] ──▶ Δo └────────────────────┘ ``` 函数 $H$ 有两个输入：左侧输入是变化 $\Delta d$，上方输入是由变化积分得到的完整集合。当某一行出现在新的变化中时，$H$ 检测该行在完整集合中的权重是否改变符号（插入行时从负变正，删除行时从正变负）。下面是 $\mathit{distinct}$ 可以被高效增量化的直觉：只有出现在输入变化 $\Delta d$ 中的元组才可能出现在输出变化 $\Delta o$ 中，因此所做的工作量为 $O(|\Delta d|)$。该实现需要维护整个输入集合（与连接类似），以判断某个元素是否是新的。这正是 $\mathcal{I}$ 算子的用途。 该算法把查询计划的增量执行问题归约为子计划/基本算子的增量执行。然而，即使我们使用的基本算子 $P$ 没有已知的高效增量版本，这个算法仍然有效：我们总可以使用低效的“暴力”实现 $P^{\Delta} = \mathcal{D} \circ ({\uparrow}P) \circ \mathcal{I}$。 ### 4.4 关系查询示例 让我们把增量视图维护（incremental view maintenance, IVM）算法应用到这个 SQL 查询上： ```sql CREATE VIEW v AS SELECT DISTINCT a.x, b.y FROM ( SELECT t1.x, t1.id FROM t1 WHERE t1.a > 2 ) a JOIN ( SELECT t2.id, t2.y FROM t2 WHERE t2.s > 5 ) b ON a.id = b.id ``` **第 1 步**：使用表 1 中的规则创建一个 DBSP 电路来表示这个查询；该电路本质上是该查询的一个数据流实现： ``` t1 ──▶ [σ_a>2] ──▶ [distinct] ──▶ [π_x,id] ──▶ [distinct] ──┐ ├──▶ [⋈_id=id] ──▶ [π_x,y] ──▶ [distinct] ──▶ V t2 ──▶ [σ_s>5] ──▶ [distinct] ──▶ [π_y,id] ──▶ [distinct] ──┘ ``` **第 2 步**：消除 $\mathit{distinct}$ 算子，产生一个等价电路（为节省空间我们省略下标）： ``` t1 ──▶ [σ] ──▶ [π] ──┐ ├──▶ [⋈] ──▶ [π] ──▶ [distinct] ──▶ V t2 ──▶ [σ] ──▶ [π] ──┘ ``` 这一步被一些传统数据库优化器所使用。注意，在原电路中表示集合的一些箭头，在优化后的电路中可能表示多重集。 **第 3 步**：提升电路使之在流上计算；所有箭头都被加倍，所有函数都被提升： ``` t1 ──▶ [↑σ] ──▶ [↑π] ──┐ ├──▶ [↑⋈] ──▶ [↑π] ──▶ [↑distinct] ──▶ V t2 ──▶ [↑σ] ──▶ [↑π] ──┘ ``` **第 4 步**：对电路做增量化，得到一个在变化上计算的电路；该电路接收对关系 `t1` 和 `t2` 的变化，并对每个这样的变化产生输出视图 `V` 中相应的变化： ``` Δt1 ──▶ [I] ──▶ [↑σ] ──▶ [↑π] ──┐ ├──▶ [↑⋈] ──▶ [↑π] ──▶ [↑distinct] ──▶ [D] ──▶ ΔV Δt2 ──▶ [I] ──▶ [↑σ] ──▶ [↑π] ──┘ ``` **第 5 步**：应用链式法则，把电路重写为增量算子的复合；注意所有算子都使用了 ${\cdot}^{\Delta}$ 记号： ``` Δt1 ──▶ [(↑σ)^Δ] ──▶ [(↑π)^Δ] ──┐ ├──▶ [(↑⋈)^Δ] ──▶ [(↑π)^Δ] ──▶ [(↑distinct)^Δ] ──▶ ΔV Δt2 ──▶ [(↑σ)^Δ] ──▶ [(↑π)^Δ] ──┘ ``` 利用 $\sigma$ 和 $\pi$ 的线性来化简该电路（注意所有线性算子不再带有 ${\cdot}^{\Delta}$）： ``` Δt1 ──▶ [↑σ] ──▶ [↑π] ──┐ ├──▶ [(↑⋈)^Δ] ──▶ [↑π] ──▶ [(↑distinct)^Δ] ──▶ ΔV Δt2 ──▶ [↑σ] ──▶ [↑π] ──┘ ``` 最后，用它们的增量实现替换增量连接与增量 $\mathit{distinct}$，得到以下电路（对连接我们采用了与前面稍有不同的展开方式；这种展开只包含两个积分器）： ``` Δt1 ──▶ [↑σ] ──▶ [↑π] ──┬──────────────▶ Δa └──▶ [I] ──▶ a Δt2 ──▶ [↑σ] ──▶ [↑π] ──┬──────────────▶ Δb └──▶ [I] ──▶ [z⁻¹] ──▶ b⁻¹ [↑⋈]₁: a ⋈ Δb ──┐ [↑⋈]₂: Δa ⋈ b⁻¹ ──┘ ├──▶ [+] ──▶ [↑π] ──┬──▶ [I] ──▶ [z⁻¹] ──▶ i ──┐ └───── d ──────────────────┴──▶ [↑H] ──▶ ΔV ``` 其中 $a = \mathcal{I}(\Delta a)$ 与 $b = \mathcal{I}(\Delta b)$ 是两个子查询输出的当前值，$b^{-1} = z^{-1}(\mathcal{I}(\Delta b))$ 是 $b$ 延迟一步的旧值；两个连接实例之和即双线性算子的增量展开，$z^{-1}$ 是延迟算子，${\uparrow}H$ 是 $\mathit{distinct}$ 增量电路中的符号变化检测函数。 注意，所得电路包含三个积分运算：两个来自连接，一个来自 $\mathit{distinct}$。它还包含两个连接算子。然而，每个算子对每个新输入所做的工作量与其输入变化的大小成正比。 ### 4.5 SQL SQL 比关系代数更丰富。它可以对多重集执行运算，并提供 `GROUP BY` 和聚合等运算。所有这些都可以建模为对类 ℤ-集合结构的运算。此外，`GROUP BY` 是一个线性运算。有些聚合“几乎”是线性的，但另一些聚合（例如 `MIN`）需要维护完整的输入集合（类似于 $\mathit{distinct}$），才能正确处理删除。更多细节见完整论文与技术报告 [6]。 ## 5 递归查询 递归查询在许多应用中非常有用。例如，图可达性或传递闭包这类图算法，天然就可以用递归查询来表达。我们引入两个简单的 DBSP 流算子，用于表达递归查询的求值。这些算子使我们能够构造实现循环结构的电路，而循环结构用于反复迭代计算，直到到达一个不动点（即某个算子的输出不再发生变化）。 ### 5.1 创建与销毁流 delta 函数 $\delta_0 : A \to \mathcal{S}_A$ 由一个标量值产生一个流。给定一个输入值 $x$，输出流是 $x$ 后面跟着无穷多个 0。$\delta_0$ 的输入是单箭头，而输出是双箭头。 ``` x ──▶ [δ₀] ══▶ · · · 0 0 0 x ``` 我们定义函数 $\int : \mathcal{S}_A \to A$。它要求输入流最终到达值 0，并且此后不再变化。该函数只是把输入流中的所有值求和，并在遇到输入流中第一个 0 时返回一个单一结果。注意输入是双箭头，而输出是单箭头。例如： ``` · · · 0 3 2 1 ══▶ [∫] ──▶ 6 ``` （该函数也是一个积分器；它与 $\mathcal{I}$ 算子的关系，等同于数学中定积分 [1] 与不定积分 [2] 之间的关系。） $\delta_0$ 与 $\int$ 都是线性的。 到目前为止，我们默认程序中的所有流共享同一个“时间”。例如，当我们把两个流相加时，我们假设它们使用同一个“时钟”。然而，$\delta_0$ 算子会创建一个带有“新的”、独立时间维的流。我们要求良构电路把嵌套时间域“隔离”开，办法是用 $\delta_0$ 与 $\int$ 算子把它们“括”起来： ``` i ──▶ [δ₀] ══▶ [S] ══▶ [∫] ──▶ o ``` $S$ 是一个流式算子，但整个电路实现的是一个标量函数，正如单箭头所示。 ### 5.2 递归查询的实现 我们描述 DBSP 中递归查询的实现。SQL 只能表达非常有限的递归查询，因此我们在这里以 Datalog 查询为模型。一般而言，一个 Datalog 程序定义一组相互递归的关系。 我们针对单输入、单输出递归查询这一简单情形，描述构造 DBSP 电路的算法。算法的输入是形如 $O = R(x, O)$ 的 Datalog 查询，其中 $R$ 是一个关系型、非递归的查询，它产生一个集合作为结果，但它的输出 $O$ 同时也是一个输入。算法的输出是一个 DBSP 电路，该电路在给定输入 $x$ 时求值这个递归查询并产生输出 $O$。本节我们构造的是非增量电路，它求值该 Datalog 查询；在 5.3 节中我们推导该电路的增量版本。 **算法 5.1**（递归查询）。 1. 按第 4 节与表 1 所述，把非递归的关系查询 $R$ 实现出来；这会产生一个无环电路，其输入与输出都是 ℤ-集合： ``` x ──┐ ├──▶ [ R ] ──▶ O O ──┘ ``` 在所有这些图中，我们把算子 $R$ 的输入 0 画在左侧，把输入 1 画在底部。 2. 把该电路提升为在流上运算： ``` x ──┐ ├──▶ [ ↑R ] ──▶ O O ──┘ ``` 我们利用第 2 节中的式 (\*\*) 逐个提升每个算子来构造 $\uparrow R$。 3. 构造一个环，通过一个延迟把输出连接到相应的递归输入： ``` x ──────────▶ [ ↑R ] ──┬──▶ O └──[z⁻¹]──▶（回送到 [↑R] 的输入 1） ``` 4. 按如下方式把电路“括”起来： ``` x ──▶ [δ₀] ──▶ [I] ──▶ [↑R] ──┬──▶ [D] ──▶ [∫] ──▶ O └──[z⁻¹]──▶（回送到 [↑R] 的输入 1） ``` 图中 [I] 与 [D] 两个方框分别是积分算子 $\mathcal{I}$ 与微分算子 $\mathcal{D}$。 $\uparrow R$ 的左侧输入是一个由相同值构成的无限流 $\cdots x\ x\ x\ x$。该电路中的反馈环是一个 while 循环，它反复迭代直到观察不到任何变化（即到达 $R$ 的一个不动点）；$\uparrow R$ 产生的输出依次将是：$R(x, 0)$、$R(x, R(x, 0))$、$R(x, R(x, R(x, 0)))$，等等。$\mathcal{D}$ 算子给出循环每一轮迭代所计算出的新变化集合。当新变化的集合变为零时，不动点就已经到达。 请注意，这不是一个流式电路：输入与输出箭头都是单箭头。这是一个接收单个输入值并产生单个对应输出的电路。该电路在内部使用流来实现不动点迭代。 关于传递闭包查询的一个具体例子见我们技术报告 [6] 的第 8.2 节。 当 $R$（即循环体）实现的是一个在有限数据域上计算的 Datalog 程序时，可以证明该程序总是终止，并计算出包含 $x$ 的最小不动点。对于一个任意的函数 $R$，所得到的电路对某些输入可能会永远循环。 事实上，该电路实现了标准的 Datalog 朴素求值算法（例如见 [11] 中的算法 1）。注意该电路的内层部分是另一个电路的增量形式，因为它被夹在 $\mathcal{I}$ 与 $\mathcal{D}$ 算子之间。利用循环规则，我们可以把该电路重写为： ``` x ──▶ [δ₀] ──▶ [(↑R)^Δ] ──┬──▶ [∫] ──▶ O └──[z⁻¹]──▶（回送到 [(↑R)^Δ] 的输入 1） ``` 该电路实现了半朴素求值（[11] 中的算法 2）。我们刚刚证明了半朴素求值的正确性，它正是循环规则的一个直接推论！ ### 5.3 增量递归程序 在第 2–4 节中，我们展示了如何通过把一个关系查询编译成电路、把该电路提升为在流上计算，再施加 $(\cdot)^\Delta$ 算子，来对它做增量化。在第 5 节中，我们展示了如何把一个递归查询编译成一个电路，该电路在内部使用增量计算来计算不动点。这里我们把这两个结果结合起来，构造一个增量地求值递归查询的电路。该电路接收输入关系上的更新流，并对每一次更新重新计算不动点。为了增量地做到这一点，它保留迭代式不动点计算所产生的、递归关系的变化流，并根据被修改的输入调整这个流。于是，借助嵌套流，输入流的每一个元素都产生一个对不动点计算的调整流。 正如流是无限向量，流之流是无限矩阵。在图中我们用三箭头表示流之流。 正如我们把函数提升为流算子，我们也可以把流算子提升为流之流上的算子。一个标量函数 $f$ 可以提升两次，产生一个流之流之间的算子 $\uparrow\uparrow f : \mathcal{S}_{\mathcal{S}_A} \to \mathcal{S}_{\mathcal{S}_B}$： ``` i ═══▶ [ ↑↑f ] ═══▶ o ``` 嵌套流上的算子 $z^{-1}$ 延迟矩阵的“行”，而 $\uparrow z^{-1}$ 延迟“列”。 我们在式 (\*\*) 中已经看到，提升一个图意味着提升其中所有算子。这一点可以推广到带环的图，例如： ``` i ═══▶ [ ↑I ] ═══▶ o ``` 与（$\cong$）： ``` i ═══▶ ( + ) ═══┬══▶ o └──[↑z⁻¹]──▶（回到 ( + ) 的另一个输入） ``` 左图是用 $\uparrow\mathcal{I}$ 表示的电路，右图是它的等价展开：用一个加法器和一条经过 $\uparrow z^{-1}$ 的反馈边实现同一个累加器。 这使我们能够提升整个电路，包括在流上计算并且带反馈边的电路。有了这套机制，我们现在可以把算法 4.1 应用于任意电路，甚至是为递归关系而构造的电路。 **步骤 1**：从“半朴素”电路出发： ``` x ──▶ [δ₀] ──▶ [(↑R)^Δ] ──┬──▶ [∫] ──▶ O └──[z⁻¹]──▶（回送到 [(↑R)^Δ] 的输入 1） ``` **步骤 2**：就 distinct 而言无需做任何事。 **步骤 3 与步骤 4**：提升该电路并增量化： ``` Δx ──▶ [I] ──▶ [↑δ₀] ──▶ [↑((↑R)^Δ)] ──┬──▶ [↑∫] ──▶ [D] ──▶ ΔO └──[↑z⁻¹]──▶（回送到 [↑((↑R)^Δ)] 的输入 1） ``` **步骤 5**：应用链式法则以及 $\uparrow\delta_0$ 与 $\uparrow\int$ 的线性性： ``` Δx ──▶ [↑δ₀] ──▶ [(↑((↑R)^Δ))^Δ] ──┬──▶ [↑∫] ──▶ ΔO └──[↑z⁻¹]──▶（回送到 [(↑((↑R)^Δ))^Δ] 的输入 1） ``` 这就是递归查询的增量版本。关于传递闭包查询的一个具体例子见我们技术报告 [6] 的第 9.1 节。 ## 6 实现 DBSP 不做任何会使其不实用的简化假设。事实上，Feldera 公司（Feldera Inc.）已用 Rust 构建了 DBSP 的一个开源实现，作为查询引擎 [9]；此外还构建了一个从 SQL 到 DBSP 的编译器 [10]。该编译器基本上处理整个 SQL 语言。该编译器生成执行计划，用于增量地维护任意数量的、用 SQL 定义的视图。 **计划质量。** 一个关系代数查询可以由多个计划实现，每个计划具有不同的、依赖于数据的代价。算法 4.1 的输入是一个非增量查询计划，由查询规划器生成。该算法产生一个与输入计划“相似”的增量计划。标准查询规划器使用基于代价的启发式方法和数据统计信息来优化计划。通用的 IVM 规划器没有这种便利，因为计划必须在任何数据被馈送到查询之前生成。尽管如此，所有标准的查询优化技术——也许基于历史统计信息——都可以用来生成提供给我们的算法的查询计划。在 IVM 计划的语境下，最优性问题比即席（ad-hoc）查询的优化困难得多，因为选定的 IVM 计划将针对未来所有的数据库更新持续执行。 **权衡。** 增量计算并非没有代价。它实际上是时间与空间之间的权衡。在代价分析中，我们必须同时考虑每个算子所用的时间和空间。虽然许多增量数据库操作可以用与变化大小成正比的工作量、且没有存储开销来实现，但有几类数据库操作——例如连接、“去重”与聚合——只有借助以索引形式存在的额外存储才能高效实现。这些索引的大小与数据库中全部数据的大小成正比（而不只是与变化的大小成正比）——并且由于有些索引是建立在中间关系之上的，它们甚至可能超过原始数据库的大小。在 DBSP 中，索引由延迟算子 $z^{-1}$ 表示。事实上，延迟算子（及其提升变体 ${\uparrow}z^{-1}$）是唯一维护状态的算子。这也是为使 DBSP 计算具备容错性而需要持久化、建立检查点或迁移的唯一状态。 DBSP 是一种“急切”（eager）或“自顶向下”（top-down）的执行模型：它持续维护任意数量视图的全部内容，即使并没有人真的想查看这些视图。相比之下，“惰性”（lazy）或“自底向上”（bottom-up）模型只在视图被查看时才构建视图的一部分。这类模型有可能更为高效。如果对将要针对视图执行的操作类别有所了解，就可以把急切模型转换为惰性模型。 **启动成本。** 当安装一个新视图时，IVM 系统必须计算第一个变化，它等同于该视图的初始内容。这一计算与整个数据库的大小成正比。这被称为“回填”（backfill）问题。同样，对视图定义或数据模式的更改需要从头重新计算受影响的查询。 **采用 DBSP。** 传统数据库并不为任意查询提供高效的 IVM 实现。原则上可以对数据库进行改造以使用本文的算法，但现有查询引擎并不是围绕能够表示负向变化（如 ℤ-集合）的结构构建的，因此这一工作将需要一次重大的重新设计。 此外，我们认为数据库不仅应当增量地计算视图，还应当把“变化”作为与其环境通信的基本数据结构：数据库服务应当提供如下 API：用户注册以接收一个或多个视图变化的通知。然后，对于每个已提交的事务，每个用户都会收到一条通知，其中包含他们所注册的所有视图的变化列表。当今的数据库没有向外报告变化的便利机制。事实上，围绕变更数据捕获（Change Data Capture）[3] 的概念已经发展出成规模的产业，它们构建从数据库中提取变化的专用方案，通常是通过检查预写事务日志。 ## 7 结论 我们提出了 DBSP，一种基于交换群（commutative groups）上无限流的计算模型。在该模型中，流用于 3 个目的：(1) 为数据库的连续快照建模；(2) 为施加到数据库上的连续变化（增量或事务）以及被维护视图的变化建模；(3) 为递归计算中循环携带变量的连续取值建模。 我们定义了流上增量计算的抽象概念，并定义了增量化算子 ${\cdot}^{\Delta}$，它把任意流计算 $Q$ 变换为其增量版本 $Q^{\Delta}$。增量化算子具有一些非常好的代数性质，这些性质为我们提供了一个通用算法，可对许多类复杂查询（包括任意递归查询）进行增量化。 我们相信，DBSP 能够为流式增量计算的理论与实践奠定坚实的基础。