CockroachDB的矢量化执行引擎中的磁盘溢出

工程部去年年底，我们交付了我们的矢量化执行引擎的v1。它支持基于列的查询执行，并加快了复杂的联接和聚合，从而提高了CockroachDB的分析能力(它首先针对OLTP工作负载进行了优化)。该引擎的V1不支持磁盘溢出，这意味着如果没有足够的内存可用，它将无法执行某些内存密集型查询。从CockroachDBv20.1开始，这些查询回退到磁盘(也称为“溢出”到磁盘)。

在这篇文章中，我们自上而下地解释了如何将磁盘溢出添加到矢量化执行引擎中，首先描述了针对不同类型查询的磁盘上算法，最后描述了所有这些算法使用的单个构建块。请注意，磁盘溢出是默认的一次一行执行引擎的现有功能。这篇文章专门介绍了最近向向量化执行引擎添加的磁盘溢出。

要了解更多关于我们为什么以及如何创建矢量化引擎的信息，请参阅我们从2019年10月开始发布的我们如何构建矢量化执行引擎的博客文章。

让我们从介绍排序及其内存使用开始。当发出具有ORDER BY关键字的查询时，计划使用排序运算符。作为输入，操作符接受任意顺序的一组元组和一个列索引列表作为排序依据。然后，它输出按列索引列表排序的元组。

请注意，操作符必须在发出元组之前缓冲整个输入，因为首先排序的元组可能在输入的末尾。因此，必须缓冲的输入大小可能超过允许操作员使用的内存量。该内存也称为“工作”内存，在CockroachDB中默认限制为64MB。当达到工作内存限制时，排序必须能够溢出到磁盘，才能对输入进行完全排序。

为了解决这个问题，我们采取了分而治之的方法，采用了外部合并排序算法，当输入无法在内存中完全缓冲时，该算法使用磁盘内存。该算法分为两个阶段：排序和合并。

在排序阶段，操作员在内存(前面提到的“工作”内存)中缓冲尽可能多的输入数据，逐列执行内存中的排序，然后将排序后的分区写入磁盘。重复此阶段，直到不再有要处理的元组。

一旦排序阶段结束，磁盘上将有N个排序分区。然后合并这些分区以产生排序的输出。

散列联接是一种基于一组相等列联接两个输入流的联接算法。它使用哈希表存储较小的流，然后使用较大的流探查表。

例如，假设用户发出SELECT*FROM CUSTOMERS，ORDERS WHERE orders.cust_id=customers.id来获得结果，其中每一行都包含客户数据和他们发出的订单。在执行此查询期间，哈希连接运算符会构建Customers表(较小的那个)的内存中的哈希表，其中关键字是客户ID。然后，它使用Orders表执行查找，并发出结果。

本例中的内存使用量随着Customers表的增长而增长，因为整个表需要存储在内存中。为了遵守64MB的工作内存限制，散列连接在溢出到磁盘时还使用分而治之的方法。这种类型的散列联接称为Grace散列联接。

在GRACE散列联接中，通过根据客户ID对每个元组进行散列，可以将ORDERS和CUSTOMERS表中的所有元组分配给N个磁盘分区中的一个。因此，具有相同客户ID的所有ORDER和CUSTOMER元组将最终位于同一分区中。然后，可以使用原始的内存中算法从磁盘读取和连接分区，以产生相同的输出。这将原始问题分为N个子问题。

请注意，只有当单个分区的大小不超过操作员的工作内存时，Grace散列连接才有效，因为分区必须完全读取到内存中。要解决此限制，如果大分区变得太大(即，重新分区)，算法可以简单地将相同的分而治之方法应用于大分区。在边缘情况下，可能存在具有相同联接列的元组，这使得分区不可能减小大小，而不管重新分区尝试的次数如何。在这种情况下，对分区进行排序并使用合并联接。

合并联接输出与散列联接相同的结果，但仅在输入已按相等列排序时使用。正如散列联接示例中对Customers所做的那样，合并联接避免了使用一侧输入构造散列表的需要，从而提高了运算符的效率。合并联接操作符可以简单地前进两个输入流，直到元组在相等列上匹配，输出联接这些元组的结果，然后移动到在相等列上匹配的下一组元组。

合并联接操作符通常被认为是一种流式算法，因为在合并联接期间不需要缓冲太多状态。然而，在两个输入流都有许多具有相同相等列值的元组的情况下，操作符需要在至少一侧缓冲所有这些元组，因为结果将是两组元组的叉积。在这种情况下，溢出到磁盘非常简单，因为唯一需要的是将被多次重放的仅附加日志。

到目前为止涉及的所有算法都有一个共同的磁盘使用访问模式：它们将数据附加到磁盘上的队列(也称为仅附加日志)，并按顺序(可能不止一次)从该队列读取数据。

在较高级别上，调用方可以将列批次的元组入队和出队。它还可以将队列重置为从队列前面返回出队。在幕后，批次被序列化、压缩并附加到文件中。如果文件超过特定大小，队列将转到新文件。当调用方读取这些文件时，内存中的游标将保持并递增。这种设计，包括替代方案，在本RFC中有更深入的介绍。

批处理使用Apache Arrow IPC文件格式写入磁盘，该文件格式是关于如何序列化列数据的规范。虽然我们没有使用Arrow Batch直接表示矢量化执行引擎中的物理数据，但我们使用了非常类似的表示，可以轻松高效地将其转换为Arrow Batch并进行序列化。

例如，假设我们有一批使用平面字节表示法表示的字符串，由三个缓冲区组成：

附带的偏移量缓冲区，表示字节缓冲区中各个字符串的开始和结束索引。

这三个缓冲区被转换为字节，被视为箭头缓冲区，然后使用相同的平面缓冲区规范进行序列化，该规范通常由一些指向这些缓冲区和缓冲区本身的元数据组成。

使用此物理表示通过使用O(1)强制转换为字节来避免复制，因为数据在内存中已经是连续的。如果字符串表示为二维数组，则需要为序列化做好数据准备，方法是分配一个新缓冲区，然后迭代并将每个元素复制到其中。

在这篇文章中，我们介绍了如何使用单个构造块在CockroachDBv20.1的矢量化执行引擎中实现各种磁盘算法。以前可能使用无限内存量的查询现在最多使用恒定数量的工作内存，如果这个数量不够用，则会溢出到磁盘。

添加了磁盘溢出功能后，我们将实验性_ON矢量化模式重命名为ON，因为我们现在认为矢量化执行引擎已准备好投入生产使用，尽管它在默认情况下尚未完全启用。需要提醒的是，在v20.1中，默认情况下只运行使用流(非缓冲)运算符并且可能读取的行数超过VECTORIZE_ROW_COUNT_THRESHOLD设置(默认为1,000)的查询。通过在会话中运行set Vector torize=on或设置集群设置sql.defaults.Vector torize=on，所有支持的查询(包括溢出到磁盘的查询)都将通过矢量化执行引擎运行。

我希望您喜欢了解我们是如何将磁盘溢出添加到矢量化执行引擎中的，我敦促您尝试启用它来加速任何复杂的连接或聚合。