查询引擎：推Push与拉Pull

本文讨论了“推”和“拉”查询引擎的区别。

  • 推式查询引擎是指生产者主动将数据传递给下游操作符，
  • 而拉式查询引擎是指消费者主动请求数据。

推式查询引擎能够高效处理有向无环图(DAG)的查询计划，并提高缓存效率。文章还解释了为什么推式系统能够处理DAG计划以及如何提高缓存效率。

要点

  • 拉取式和推送式查询引擎是两种不同的数据查询模式，它们在数据流向和操作逻辑上存在差异。
  • 推送式查询引擎能够高效处理有向无环图(DAG)形式的查询计划，并能够共享和流水线中间结果。
  • 推送式查询引擎通过将控制流逻辑从紧密循环中移除，提高了缓存效率。

比较：
在基于拉动的系统中，操作者一直处于闲置状态，直到有人向他们索要数据行。

  • 这意味着如何从系统中获得结果是很容易：你向它要一行，它就给你一行。
  • 然而，这也意味着系统的行为与其消费者紧密相连；如果有人要求，你就工作，否则就不工作。

在基于推送的系统中，系统处于闲置状态，直到有人告诉它有一行。因此，系统所做的工作和它的消耗索要是脱钩的。

你可能已经注意到，与基于拉动的系统相比，在基于推动的系统中，我们不得不在创建缓冲区（结果）时做一些奇怪的动作，以便指示查询将其结果塞入缓冲区。这就是基于推送的系统给人的感觉，它们的存在与其指定的消费者无关，它们只是存在，当事情发生时，它们会做出响应。

为什么基于推送的系统 "能让 Snowflake 高效处理 DAG 形计划"，而基于拉动的系统却不支持这种方式？
所谓 "DAG 形计划"，是指将数据输出给多个下游运算符的运算符。事实证明，这比听起来更有用，即使是在我们通常认为本质上是树形结构的 SQL 中也是如此。

SQL 有一种名为 WITH 的结构，允许用户在查询中多次引用结果集。这意味着下面的查询是有效的 SQL：

WITH foo as (<some complex query>)
SELECT * FROM
    (SELECT * FROM foo WHERE c) AS foo1
  JOIN
    foo AS foo2
  ON foo1.a = foo2.b

除了这个明确的例子之外，智能查询规划器通常还可以利用 DAG 的特性来重用结果。例如，杰米-布兰登（Jamie Brandon）在一篇文章中描述了一种在 SQL 中装饰子查询的通用方法，该方法广泛使用 DAG 查询计划以提高效率。正因为如此，能够在不简单重复计划树分支的情况下处理这些情况是非常有价值的。

在拉动模型中，有两件主要的事情会造成这种困难：调度和生命周期。

调度
在每个运算符只有一个输出的情况下，何时运行运算符以产生某个输出是显而易见的：当用户需要时。但如果有多个输出，这至少会变得更加混乱，因为 "对行的请求 "和 "产生行的计算 "不再是一对一的关系。

相比之下，在基于推送的系统中，运算操作符的调度原本就与它们的输出无关，因此失去这一信息并没有什么区别。

生命周期
在基于拉的模型中使用 DAG 的另一个棘手问题是，这种系统中的操作符受其下游操作符的支配：必须保留将来可能被其任何消费者读取的记录（或必须能够重新计算）。

解决这个问题的一般方法是，操作符缓冲所有输出的记录，这样就可以重新输出，但在每个操作符边界引入可能无限制的缓冲是不可取的（但 Postgres 和 CockroachDB 不得不这样做，因为 WITH 有多个消费者）。

在基于推送的系统中，这个问题就不那么严重了，因为操作者现在可以在其消费者处理记录时进行驱动，从而有效地迫使消费者掌握记录的所有权并对其进行处理。

在大多数情况下：

  • 这要么会导致某种必要的缓冲，即使在没有 DAG 的情况下也需要这种缓冲（例如，对于区分或散列连接操作），
  • 要么就会被立即处理和传递。

为什么这能提高缓存效率？"从紧密循环中移除控制流逻辑 "是什么意思？
我们希望将查询编译成机器代码，以提高缓存效率，为此，基于推送的范例更可取。

编译基于推送的查询会使代码更简单。

let result = [];
Scan(
  customer,
  Select(
    (c) => c.balance > 0,
    Map(
      (c) => c.firstName,
      Distinct((r) => result.push(r))
    )
  )
);

console.log(result);

这就很自然地展开了：
let result = [];
let seen = new Set();
for (let c of customer) {
  if (c.balance > 0) {
    if (!seen.has(c.firstName)) {
      seen.add(c.firstName);
      result.push(c.firstName);
    }
  }
}

console.log(result);

如果您尝试展开等效的基于拉的查询，您会发现生成的代码要得多。

我认为很难就此得出 "更好 "的结论，最明智的做法是根据特定查询引擎的需求做出选择。

考虑因素
1、阻抗失配
这些系统可能出现的一个问题是它们的边界不匹配。从拉式系统到推式系统的边界转换需要轮询其状态，而从推式系统到拉式系统的边界转换需要将其状态具体化。这两种情况都不会造成问题，但都会产生一定的成本。

这就是为什么在 Flink 或 Materialize 等流式系统中，你通常会看到使用基于推送的系统：这种系统的输入本质上是基于推送的，因为你正在监听传入的 Kafka 流或类似内容。

在流式设置中，如果你希望你的终端消费者能够以基于拉的方式与系统交互（例如，在需要时对系统运行查询），你就需要引入某种物化层，从结果中建立索引。


相反，如果系统不提供某种流/尾机制，那么如果你想知道某些数据何时发生了变化，唯一的选择就是定期轮询。

2、算法
有些算法根本不适合在推送系统中使用。正如 Shaikhha 论文中讨论的那样：合并连接算法的工作原理是以同步遍历两个迭代器的能力为基础，这在消费者几乎无法控制的推送系统中并不实用。

同样，LIMIT 运算符在推送模型中也会出现问题。如果不引入双向通信，或将 LIMIT 融合到底层运算符中（这并不总是可行的），生产运算符就无法知道，一旦消费者满足了，它们就可以停止工作。在拉动系统中，这不是问题，因为当消费者不再需要更多结果时，就可以停止要求更多结果。

3、循环
在这些模型中，不仅要有 DAG，还要有完整的循环图，这并非易事。
但解决这个问题的最著名系统是 Naiad，它是一个及时数据流系统，其现代版本是及时数据流。这两个系统都是推送系统，与 DAG 一样，在推送模型中，很多事情都能做得更好。

结论
绝大多数数据库入门教材都侧重于迭代器模型，但现代系统，尤其是分析系统，开始更多地探索推送模型。正如 Shaikhha 的论文所指出的，很难找到苹果与苹果之间的比较，因为很多向推送模型迁移的动机都是希望将查询编译为较低级别的代码，而这样做所带来的好处会使结果变得模糊不清。

尽管如此，还是存在一些量化差异，这使得每种模型都适用于不同的场景，如果你对数据库感兴趣，值得对它们的工作原理有一个大致的了解。今后，我想更详细地介绍这些系统是如何构建的，并尝试揭示使它们发挥作用的一些奥妙。