西部最快的表排序——重新设计 DuckDB 的排序
概要：DuckDB 是一个免费且开源的分析数据管理系统，它有一个新的高效并行排序实现，可以对远超主内存容量的数据进行排序。
数据库系统在很多地方都会用到排序，最明显的用途是用户在查询中添加 ORDER BY 子句时。排序也用于运算符中，比如窗口函数。DuckDB 最近改进了其排序实现，现在可以并行排序数据，并可以排序超出内存容量的数据。在这篇文章中，我们将了解 DuckDB 如何排序，以及它与其他数据管理系统的比较。
对实现不感兴趣？直接跳到实验！
排序关系数据
排序是计算机科学中最受研究的问题之一，也是数据管理的重要方面。整个社区都在致力于研究谁排序速度最快。对排序算法的研究往往侧重于排序大型数组或键/值对。虽然这很重要，但这并没有涵盖如何在数据库系统中实现排序。对表进行排序不仅仅是对一个大型整数数组进行排序！
考虑以下在 TPC-DS 表片段上的示例查询
SELECT c_customer_sk, c_birth_country, c_birth_year
FROM customer
ORDER BY c_birth_country DESC,
c_birth_year ASC NULLS LAST;
它会产生
| c_customer_sk | c_birth_country | c_birth_year |
|---|---|---|
| 64760 | NETHERLANDS | 1991 |
| 75011 | NETHERLANDS | 1992 |
| 89949 | NETHERLANDS | 1992 |
| 90766 | NETHERLANDS | NULL |
| 42927 | GERMANY | 1924 |
换句话说：c_birth_country 按降序排序，在 c_birth_country 相等的情况下，我们按 c_birth_year 升序排序。通过指定 NULLS LAST，空值被视为 c_birth_year 列中的最低值。因此，会对整个行重新排序，而不仅仅是 ORDER BY 子句中的列。我们把不在 ORDER BY 子句中的列称为“有效负载列”。因此，有效负载列 c_customer_sk 也必须重新排序。
使用任何排序实现都可以轻松实现评估示例查询的功能，例如，C++ 的 std::sort。虽然 std::sort 在算法上非常出色，但它仍然是一种单线程方法，无法有效地按多列排序，因为函数调用开销会迅速占据排序时间。下面我们将讨论原因。
为了在排序表时获得良好的性能，需要自定义排序实现。当然，我们不是第一个实现关系排序的人，所以我们深入研究了文献，寻找指导。
2006 年，著名的 Goetz Graefe 写了一篇关于在数据库系统中实现排序的调查报告。在这篇调查报告中，他收集了社区中已知的许多排序技术。如果你打算开始实现表的排序功能，这是一份很好的指导。
排序的成本主要在于比较值和移动数据。任何能使这两个操作更便宜的方法都会对总运行时间产生重大影响。
当我们有多个 ORDER BY 子句时，有两种明显的方法来实现比较器
- 循环遍历子句：比较列，直到我们找到一个不相等的列，或者直到我们比较了所有列。这已经相当复杂了，因为它需要一个循环，并且循环中的每个数据行都有一个 if/else。如果我们有列式存储，这个比较器必须在列之间跳转，导致内存中的随机访问。
- 首先按第一个子句对数据进行完整排序，然后按第二个子句排序，但仅在第一个子句相等的情况下，依此类推。当存在许多重复值时，这种方法尤其低效，因为它需要多次遍历数据。
二进制字符串比较
二进制字符串比较技术通过简化比较器来提高排序性能。它将 ORDER BY 子句中的所有列编码为单个二进制序列，当使用 memcmp 进行比较时，将产生正确的总体排序顺序。编码数据不是免费的，但是由于我们在排序期间使用了大量的比较器，所以这是值得的。让我们再来看看示例中的 3 行
| c_birth_country | c_birth_year |
|---|---|
| NETHERLANDS | 1991 |
| NETHERLANDS | 1992 |
| GERMANY | 1924 |
在 小端硬件上，假设年份采用 32 位整数表示，这些值在内存中的表示方式如下
c_birth_country
-- NETHERLANDS
01001110 01000101 01010100 01001000 01000101 01010010 01001100 01000001 01001110 01000100 01010011 00000000
-- GERMANY
01000111 01000101 01010010 01001101 01000001 01001110 01011001 00000000
c_birth_year
-- 1991
11000111 00000111 00000000 00000000
-- 1992
11001000 00000111 00000000 00000000
-- 1924
10000100 00000111 00000000 00000000
诀窍是将这些值转换为编码排序顺序的二进制字符串
-- NETHERLANDS | 1991
10110001 10111010 10101011 10110111 10111010 10101101 10110011 10111110 10110001 10111011 10101100 11111111
10000000 00000000 00000111 11000111
-- NETHERLANDS | 1992
10110001 10111010 10101011 10110111 10111010 10101101 10110011 10111110 10110001 10111011 10101100 11111111
10000000 00000000 00000111 11001000
-- GERMANY | 1924
10111000 10111010 10101101 10110010 10111110 10110001 10100110 11111111 11111111 11111111 11111111 11111111
10000000 00000000 00000111 10000100
二进制字符串是固定大小的，因为这使得在排序过程中移动它更容易。
字符串“GERMANY”比“NETHERLANDS”短，因此用 00000000 填充。随后反转列 c_birth_country 中的所有位，因为此列按降序排序。如果一个字符串太长，我们会对其前缀进行编码，并且仅在前缀相等时才查看整个字符串。
c_birth_year 中的字节被交换，因为我们需要大端表示来编码排序顺序。第一位也被翻转，以保留 有符号整数的正整数和负整数之间的顺序。如果存在 NULL 值，则必须使用额外的字节对其进行编码（示例中未显示）。
使用此二进制字符串，我们现在可以通过仅比较二进制字符串表示来同时比较两列。这可以使用 C++ 中的单个 memcmp 完成！编译器将为单个函数调用发出高效的汇编代码，甚至会自动生成 SIMD 指令。
此技术解决了上述问题之一，即使用复杂比较器时的函数调用开销。
基数排序
现在我们有了一个廉价的比较器，我们必须选择我们的排序算法。每个计算机科学专业的学生都会学习 基于比较的排序算法，如 快速排序和 归并排序，它们的 时间复杂度为 O (n log n)，其中 n 是要排序的记录数。
但是，也有 基于分布的排序算法，它们的典型时间复杂度为 O (n k)，其中 k 是排序键的宽度。这类排序算法随着较大的 n 的增加，扩展性更好，因为 k 是常量，而 log n 不是。
其中一种算法是 基数排序。该算法通过使用 计数排序计算数据分布来对数据进行排序，多次计算直到所有数字都被计数为止。
将排序键列编码为我们有一个廉价的比较器，然后选择一种不比较记录的排序算法，这听起来可能违反直觉。但是，编码对于基数排序是必需的：如果我们执行逐字节基数排序，则使用 memcmp 生成正确顺序的二进制字符串将生成正确的顺序。
两阶段并行排序
DuckDB 使用 Morsel 驱动的并行，这是一个用于并行查询执行的框架。对于排序运算符，这意味着多个线程并行地从表中收集大致相等的数据量。
我们使用这种并行性来进行排序，首先让每个线程使用我们的基数排序对它收集的数据进行排序。在第一个排序阶段之后，每个线程都有一个或多个排序数据块，这些数据块必须合并到最终的排序结果中。归并排序是此任务的首选算法。实现归并排序主要有两种方式：K 路合并和 级联合并。
K 路合并在一个通道中将 K 个列表合并为一个排序列表，并且传统上 用于外部排序（排序的数据超出内存容量），因为它最大限度地减少了 I/O。级联合并一次合并两个排序数据列表，直到只剩下一个排序列表，并且用于内存排序，因为它比 K 路合并更有效。我们的目标是有一个具有高性能的内存实现，随着我们超过可用内存的限制，该实现会优雅地降级。因此，我们选择级联合并。
在级联归并排序中，我们一次合并两个排序数据块，直到只剩下一个排序块。自然地，我们希望使用所有可用的线程来计算合并。如果我们排序块的数量比线程多得多，我们可以为每个线程分配合并两个块。但是，随着块被合并，我们将没有足够的块来保持所有线程的忙碌状态。当合并最后两个块时，这尤其缓慢：一个线程必须处理所有数据。
为了完全并行化这个阶段，我们实现了 Oded Green 等人的 合并路径。合并路径预先计算排序列表在合并时将在哪里相交，如下图所示（取自论文）。
可以使用 二分查找高效地计算沿合并路径的交点。如果我们知道交点在哪里，我们可以独立并行地合并排序数据的分区。这允许我们在整个合并阶段有效地使用所有可用的线程。有关改进归并排序的另一个技巧，请参阅附录。
列还是行？
除了比较之外，排序的另一个主要成本是移动数据。DuckDB 有一个矢量化执行引擎。数据以列式布局存储，一次按批处理（称为块）处理。这种布局非常适合分析查询处理，因为这些块适合 CPU 缓存，并且它为编译器提供了许多生成 SIMD 指令的机会。但是，当表被排序时，移动的是整个行，而不是列。
我们可以在排序时坚持使用列式布局：先排序键列，然后逐个重新排列有效负载列。但是，重新排序将导致每个列在内存中出现随机访问模式。如果有许多有效负载列，这将很慢。将列转换为行将使重新排序行更容易。当然，这种转换不是免费的：列需要被复制到行中，并在排序后再次从行复制回列。
因为我们想要支持外部排序，所以我们必须将数据存储在可以卸载到磁盘的 缓冲区管理块中。因为无论如何我们都必须将输入数据复制到这些块，所以将行转换为列实际上是免费的。
有一些运算符本质上是基于行的，例如连接和聚合。DuckDB 为这些运算符提供了一个统一的内部行布局，我们决定也将其用于排序运算符。到目前为止，这种布局仅在内存中使用。在下一节中，我们将解释我们如何让它在磁盘上也能工作。我们应该注意到，只有在主内存无法容纳时，我们才会将排序数据写入磁盘。
外部排序
缓冲区管理器可以将块从内存卸载到磁盘。这不是我们在排序实现中主动做的事情，而是缓冲区管理器在内存即将用完时决定要做的事情。它使用最近最少使用队列来决定要写入哪些块。有关如何正确使用此队列的更多信息，请参见附录。
当我们需要一个块时，我们会“固定”它，如果它尚未加载，则将其从磁盘读取。访问磁盘比访问内存慢得多，因此最大限度地减少读取和写入次数至关重要。
对于固定大小的列（如整数）来说，将数据卸载到磁盘很容易，但是对于可变大小的列（如字符串）来说，卸载到磁盘更困难。我们的行布局使用固定大小的行，这无法容纳任意大小的字符串。因此，字符串由一个指针表示，该指针指向单独的内存块，实际的字符串数据位于该内存块中，这被称为“字符串堆”。
我们已经更改了我们的堆，以便也按行将字符串存储在缓冲区管理块中
每一行都有一个额外的 8 字节字段 pointer，它指向该行在堆中的起始位置。这在内存表示中毫无用处，但是我们将在一秒钟内看到它为什么对磁盘表示有用。
如果数据可以容纳在内存中，则堆块保持固定，并且仅在排序时重新排列固定大小的行。如果数据无法容纳在内存中，则块需要被卸载到磁盘，并且堆也会在排序时被重新排序。当堆块被卸载到磁盘时，指向它的指针将失效。当我们将块重新加载到内存中时，指针将发生变化。
这就是我们的行式布局发挥作用的地方。8 字节的 pointer 字段被 8 字节的 offset 字段覆盖，表示可以在堆块中找到此行的字符串的位置。此技术称为 “指针调整”。当我们调整指针时，行布局和堆块如下所示
指向后续字符串值的指针也被 8 字节的相对偏移量覆盖，表示此字符串从堆中的行开始位置偏移多远（因此每个 stringA 的偏移量为 0：它是行中的第一个字符串）。在行中使用相对偏移量而不是绝对偏移量在排序期间非常有用，因为这些相对偏移量保持不变，并且在复制行时无需更新。
当需要扫描块以读取排序结果时，我们会“取消调整”指针，使其再次指向字符串。
使用这种双重用途的行式表示，我们可以轻松地复制固定大小的行和堆中的可变大小的行。除了让缓冲区管理器加载/卸载块之外，内存排序和外部排序之间的唯一区别是我们调整/取消调整指向堆块的指针，并在归并排序期间从堆块复制数据。
所有这些都减少了在内存中移入和移出块时的开销，这将导致当我们接近可用内存的限制时性能优雅地下降。
与其他系统比较
现在我们已经介绍了我们的排序实现中使用的大部分技术，我们想知道我们与其他系统的比较情况。DuckDB 通常用于交互式数据分析，因此经常与 dplyr 之类的工具进行比较。
在这种情况下，人们通常在笔记本电脑或 PC 上运行，因此我们将在 2020 MacBook Pro 上运行这些实验。此笔记本电脑具有 Apple M1 CPU，它是基于 ARM 的。M1 处理器有 8 个内核：4 个高性能（Firestorm）内核和 4 个节能（Icestorm）内核。Firestorm 内核具有非常非常快的单线程性能，因此这应该在某种程度上平衡单线程和多线程排序实现之间的竞争。MacBook 具有 16 GB 内存和 笔记本电脑中最快的 SSD 之一。
我们将与以下系统进行比较
- ClickHouse，版本 21.7.5
- HyPer，版本 2021.2.1.12564
- Pandas，版本 1.3.2
- SQLite，版本 3.36.0
ClickHouse 和 HyPer 包含在我们的比较中，因为它们是强调性能的分析 SQL 引擎。Pandas 和 SQLite 包含在我们的比较中，因为它们可以像 DuckDB 一样用于在 Python 中执行关系操作。Pandas 完全在内存中运行，而 SQLite 是一个更传统的基于磁盘的系统。这个系统列表应该能给我们提供单线程/多线程和内存/外部排序的良好组合。
ClickHouse 是使用 本指南为 M1 构建的。我们已将内存限制设置为 12 GB，并将 max_bytes_before_external_sort 设置为 10 GB，遵循 此建议。
HyPer 是 Tableau 的数据引擎，由 慕尼黑大学的数据库小组创建。它（尚未）在基于 ARM 的处理器（如 M1）上原生运行。我们将使用 Rosetta 2，macOS 的 x86 模拟器来运行它。模拟会导致一些开销，因此我们在附录中包含了一个在 x86 计算机上的实验。
对数据库系统中的排序进行基准测试并不简单。理想情况下，我们只想测量对数据进行排序所花费的时间，而不是读取输入数据和显示输出所花费的时间。并非每个系统都有分析器来精确测量排序运算符的时间，因此这不是一种选择。
为了进行公平的比较，我们将测量对数据进行排序并将结果写入临时表的查询的端到端时间，即
CREATE TEMPORARY TABLE output AS
SELECT ...
FROM ...
ORDER BY ...;
对于这个问题没有完美的解决方案，但这应该能给我们提供一个很好的比较，因为此查询的端到端时间应该主要由排序决定。对于 Pandas，我们将使用 sort_values 和 inplace=False 来模拟此查询。
在 ClickHouse 中，临时表只能存在于内存中，这对于我们的核外实验来说是有问题的。因此，我们将使用常规的 TABLE，但随后我们还需要选择一个表引擎。大多数表引擎都会应用压缩或创建索引，这不是我们想要测量的。因此，我们选择了最简单的磁盘引擎，即 File，格式为 Native。
我们为 ClickHouse 的输入表选择的表引擎是带有 ORDER BY tuple() 的 MergeTree。我们之所以选择它，是因为我们遇到了 File(Native) 输入表的奇怪行为，查询 SELECT * FROM ... ORDER BY 和 SELECT col1 FROM ... ORDER BY 之间的运行时没有差异。据推测，这是因为表中的所有列都已排序，无论选择了多少列。
为了测量稳定的端到端查询时间，我们运行每个查询 5 次，并报告中值运行时间。系统之间的读/写表存在一些差异。例如，Pandas 无法从/向磁盘读/写，因此输入和输出数据帧都将位于内存中。DuckDB 不会将输出表写入磁盘，除非没有足够的空间将其保留在内存中，因此也可能具有优势。但是，排序主导了总运行时，因此这些差异影响不大。
随机整数
我们将从一个简单的例子开始。我们生成了前 1 亿个整数并对其进行了洗牌，我们想知道这些系统如何很好地对其进行排序。此实验与其说是一个实际意义上的例子，不如说是一个微基准。
对于我们的第一个实验，我们将研究系统如何随着行数的增加而扩展。从包含整数的初始表中，我们又制作了 9 个表，每个表包含 10M、20M、…、90M 个整数。
作为一个传统的基于磁盘的数据库系统，SQLite 始终选择外部排序策略。即使中间排序块可以容纳在主内存中，它也会将中间排序块写入磁盘，因此速度要慢得多。其他系统的性能处于同一水平，DuckDB 和 ClickHouse 并驾齐驱，对 1 亿个整数的处理时间约为 ~3 秒和 ~4 秒。由于 SQLite 速度慢得多，我们将不会在下一组实验（TPC-DS）中包含它。
DuckDB 和 ClickHouse 都很好地利用了所有可用的线程，并行执行单线程排序，然后并行执行归并排序。我们不确定 HyPer 使用什么策略。对于我们的下一个实验，我们将重点关注多线程，并了解 ClickHouse 和 DuckDB 如何随着线程数的增加而扩展（我们无法为 HyPer 设置线程数）。
此图表明基数排序非常快。DuckDB 使用单个线程在不到 5 秒的时间内对 1 亿个整数进行排序，这比 ClickHouse 快得多。对于 DuckDB，添加线程并不能像以前那样提高性能，因为基数排序比归并排序快得多。在 4 个线程的情况下，两个系统的性能最终大致相同。
超过 4 个线程，由于 CPU 架构，我们看不到性能有太大提高。对于所有其他实验，我们都将 DuckDB 和 ClickHouse 设置为使用 4 个线程。
对于我们最后一个随机整数实验，我们将了解输入的排序顺序如何影响性能。这在采用快速排序的系统中尤其重要，因为快速排序在反向排序数据上的性能比在随机数据上的性能差得多。
毫不奇怪，所有系统在排序数据上的性能都更好，有时差距很大。ClickHouse、Pandas 和 SQLite 可能有一些优化：例如，在目录中跟踪排序顺序，或在扫描输入时检查排序顺序。DuckDB 和 HyPer 在输入数据已排序时的性能差异很小，没有这样的优化。对于 DuckDB，性能的略微提高可以解释为排序期间更好的内存访问模式：当数据已经排序时，访问模式大多是顺序的。
另一个有趣的结果是，DuckDB 对数据的排序速度比某些其他系统读取已排序数据的速度更快。
TPC-DS
对于下一个比较，我们临时编写了一个在标准 TPC 决策支持基准 (TPC-DS) 中两个表上的关系排序基准。TPC-DS 对排序实现具有挑战性，因为它具有宽表（具有许多列，不像 TPC-H 中的表）以及固定大小和可变大小类型的混合。行数随着比例因子的增加而增加。这里使用的表是 catalog_sales 和 customer。
catalog_sales 具有 34 列，所有固定大小的类型（整数和双精度数），并且随着比例因子的增加，行数也在增加。customer 具有 18 列（10 个整数和 8 个字符串），并且随着比例因子的增加，具有相当数量的行。下表中显示了每个比例因子下两个表的行数。
| SF | customer | catalog_sales |
|---|---|---|
| 1 | 100,000 | 1,441,548 |
| 10 | 500,000 | 14,401,261 |
| 100 | 2,000,000 | 143,997,065 |
| 300 | 5,000,000 | 260,014,080 |
我们将使用 SF100 和 SF300 上的 customer，它在每个比例因子下都可以容纳在内存中。我们将使用 SF10 和 SF100 上的 catalog_sales 表，它在 SF100 上不再可以容纳在内存中。
数据是使用 DuckDB 的 TPC-DS 扩展生成的，然后以随机顺序导出到 CSV，以撤消生成的数据中可能存在的任何排序模式。
目录销售（数值类型）
我们对 catalog_sales 表的第一个实验是选择 1 列，然后选择 2 列，…，最多选择所有 34 列，始终按 cs_quantity 和 cs_item_sk 排序。此实验将告诉我们不同的系统如何很好地重新排列有效负载列。
我们在 SF10 和 SF100 上看到了相似的趋势，但对于 SF100，在 12 个有效负载列左右时，数据不再可以容纳在内存中，ClickHouse 和 HyPer 的性能大幅下降。ClickHouse 切换到外部排序策略，这比其内存策略慢得多。因此，添加一些有效负载列会导致运行时间高出几个数量级。在 20 个有效负载列时，ClickHouse 遇到以下错误
DB::Exception: Memory limit (for query) exceeded: would use 11.18 GiB (attempt to allocate chunk of 4204712 bytes), maximum: 11.18 GiB: (while reading column cs_list_price): (while reading from part ./store/523/5230c288-7ed5-45fa-9230-c2887ed595fa/all_73_108_2/ from mark 4778 with max_rows_to_read = 8192): While executing MergeTreeThread.
HyPer 的性能也会下降，然后出现以下消息错误
ERROR: Cannot allocate 333982248 bytes of memory: The `global memory limit` limit of 12884901888 bytes was exceeded.
据我们所知，HyPer 使用 mmap，它在内存和文件之间创建映射。这允许操作系统在内存和磁盘之间移动数据。虽然有用，但这不能替代正确的外部排序，因为它创建了对磁盘的随机访问，这非常慢。
尽管数据无法容纳在内存中，但 Pandas 在 SF100 上的性能出奇地好。Pandas 只能这样做，因为 macOS 会动态增加交换空间大小。大多数操作系统都不会这样做，并且会完全无法加载数据。使用交换通常会显着降低处理速度，但 SSD 的速度非常快，因此没有明显的性能下降！
当 Pandas 加载数据时，交换空间大小增加到令人印象深刻的 ~40 GB：文件和数据帧同时完全位于内存/交换空间中，而不是流式传输到内存中。当文件读取完成后，这会降至 ~20 GB 的内存/交换空间。Pandas 能够很好地进行实验，直到它崩溃并出现以下错误
UserWarning: resource_tracker: There appear to be 1 leaked semaphore objects to clean up at shutdown
DuckDB 在内存和外部表现良好，并且没有明显可见的数据不再适合内存的点：运行时快速且可靠。
客户（字符串和整数）
现在我们已经看到了系统如何处理大量固定大小的类型，现在是时候看看一些可变大小的类型了！对于我们在 customer 表上的第一个实验，我们将选择所有列，并按 3 个整数列（c_birth_year、c_birth_month、c_birth_day）或 2 个字符串列（c_first_name、c_last_name）对它们进行排序。比较字符串比比较整数困难得多得多，因为字符串可以具有可变大小，并且需要逐字节比较，而整数始终具有相同的比较。
正如预期的那样，按字符串排序比按整数排序更昂贵，HyPer 除外，这令人印象深刻。Pandas 在按整数排序和按字符串排序之间的差异仅比 ClickHouse 和 DuckDB 略大。此差异可以通过字符串之间昂贵的比较器来解释。Pandas 使用 NumPy 的排序，它在 C 中高效实现。但是，当它对字符串进行排序时，它必须使用虚拟函数调用来比较 Python 字符串对象，这比 C 中整数之间的简单“<”慢。尽管如此，Pandas 在 customer 表上的表现良好。
在我们的下一个实验中，我们将看到payload类型如何影响性能。customer 有 10 个整数列和 8 个字符串列。我们将选择所有整数列或所有字符串列，并且每次都按 (c_birth_year, c_birth_month, c_birth_day) 排序。
正如预期的那样，重新排序字符串比重新排序整数花费的时间要多得多。 Pandas 在这里具有优势，因为它已经将字符串保存在内存中，并且很可能只需要重新排序指向这些字符串的指针。数据库系统需要复制字符串两次：一次是在读取输入表时，另一次是在创建输出表时。在 DuckDB 中进行性能分析表明，在 SF300 中实际排序花费的时间不到一秒，而大部分时间都花在了字符串的（反）序列化上。
结论
DuckDB 新的并行排序实现可以有效地排序比内存容量更多的数据，从而利用了现代 SSD 的速度。当其他系统因为内存不足而崩溃，或者切换到速度慢得多的外部排序策略时，DuckDB 的性能会随着超出内存限制而优雅地降低。
用于运行实验的代码可以在 GitHub 上找到。如果我们有任何错误，请告诉我们！
DuckDB 是一个免费且开源的数据库管理系统（MIT 许可）。它的目标是成为分析领域的 SQLite，并提供一个快速高效的数据库系统，无需任何外部依赖项。它不仅适用于 Python，还适用于 C/C++、R、Java 等。
收听 Laurens 在 Disseminate 播客上的节目
附录 A：谓词化
我们用来加速归并排序的另一种技术是谓词化。使用此技术，我们将具有 if/else 分支的代码转换为没有分支的代码。现代 CPU 尝试预测 if 或 else 分支是否将被预测。如果这很难预测，则可能会降低代码速度。请看下面带有分支的伪代码示例。
// continue until merged
while (l_ptr && r_ptr) {
// check which side is smaller
if (memcmp(l_ptr, r_ptr, entry) < 0) {
// copy from left side and advance
memcpy(result_ptr, l_ptr, entry);
l_ptr += entry;
} else {
// copy from right side and advance
memcpy(result_ptr, r_ptr, entry);
r_ptr += entry;
}
// advance result
result_ptr += entry;
}
我们通过移动指针，一次一个条目，将左侧和右侧块中的数据合并到一个结果块中。通过使用比较布尔值作为 0 或 1，可以使此代码无分支，如下面的伪代码所示。
// continue until merged
while (l_ptr && r_ptr) {
// store comparison result in a bool
bool left_less = memcmp(l_ptr, r_ptr, entry) < 0;
bool right_less = 1 - left_less;
// copy from either side
memcpy(result_ptr, l_ptr, left_less * entry);
memcpy(result_ptr, r_ptr, right_less * entry);
// advance either one
l_ptr += left_less * entry;
l_ptr += right_less * entry;
// advance result
result_ptr += entry;
}
当 left_less 为真时，它等于 1。这意味着 right_less 为假，因此等于 0。我们使用它从左侧复制 entry 字节，从右侧复制 0 字节，并相应地递增左右指针。
使用谓词化代码，CPU 不必预测要执行哪些指令，这意味着指令缓存未命中将会减少！
附录 B：之字形
减少 I/O 的一个简单技巧是在级联归并排序中之字形穿过要合并的块对。下图对此进行了说明（虚线箭头指示块合并的顺序）。
通过之字形穿过块，我们通过合并在前一次迭代中合并的最后一个块来启动迭代。这些块可能仍在内存中，从而节省了一些宝贵的读/写操作。
附录 C：x86 实验
我们还在具有 x86 CPU 架构的机器上运行了 catalog_sales SF100 实验，以便与 HyPer 进行更公平的比较（没有 Rosetta 2 模拟）。该机器有一个 Intel(R) Xeon(R) W-2145 CPU @ 3.70 GHz，它有 8 个内核（最多 16 个虚拟线程）和 128 GB 的 RAM，因此这次数据完全适合内存。我们将 DuckDB 和 ClickHouse 使用的线程数设置为 8，因为我们看到超过 8 个线程后性能没有明显提高。
Pandas 的性能比在 MacBook 上差，因为它有一个单线程实现，并且此 CPU 的单线程性能较低。同样，Pandas 崩溃并出现错误（这台机器不会动态增加交换空间）
numpy.core._exceptions.MemoryError: Unable to allocate 6.32 GiB for an array with shape (6, 141430723) and data type float64
DuckDB、HyPer 和 ClickHouse 都充分利用了更多可用线程，比在 MacBook 上快得多。
此图中的一个有趣的模式是，DuckDB 和 HyPer 随着附加的 payload 列而以非常相似的方式缩放。虽然 DuckDB 在排序方面更快，但对于两个系统来说，重新排序 payload 似乎花费的成本大致相同。因此，HyPer 也可能使用行布局。
ClickHouse 随着附加的 payload 列的缩放效果较差。ClickHouse 不使用行布局，因此必须在每次排序后重新排序每一列时付出随机访问的代价。
