Apache Arrow Rust 中快速且内存高效的多列排序，第 1 部分
已发布 2022 年 11 月 7 日
作者 tustvold 和 alamb
引言
排序是现代数据库和其他分析系统中最基础的操作之一，支撑着聚合、连接、窗口函数、合并等重要运算符。据估计，数据处理系统中超过一半的执行时间都用于排序。因此，优化排序对于提高查询性能和整体系统效率至关重要。
排序也是计算机科学中研究最深入的课题之一。数据库领域的经典综述论文是 Goetz Graefe 的《在数据库系统中实现排序》（Implementing Sorting in Database Systems），该文提供了全面的学术论述，至今仍具有很强的适用性。然而，如何将该论文中描述的智慧和高级技术应用于现代系统可能并不显而易见。此外，DuckDB 关于排序的优秀博文重点介绍了许多排序技术，并提到了一种可比较的行格式，但它没有解释如何高效地排序变长字符串或字典编码数据。
在本系列文章中，我们将详细解释 Apache Arrow 的 Rust 实现中的新型行格式，以及我们如何使用它使排序速度比基于比较器的替代方法快 3 倍以上。对于字符串、字典编码数据和具有大量列的排序，其优势尤其明显。
多列/字典排序问题
大多数语言都具有用于对单列（数组）数据进行排序的原生优化操作，这些操作根据要排序的数据类型进行专门化。分析系统中排序通常更具挑战性的原因是：
- 它们必须支持多列数据
- 列类型在编译时不可知，因此编译器通常无法生成优化代码
在某些库中，多列排序也称为字典排序。
例如，给定各种客户的销售数据及其居住州，用户可能希望找到每个州订单量最低的 10 个订单。
Customer | State | Orders
—--------+-------+-------
12345 | MA | 10.12
532432 | MA | 8.44
12345 | CA | 3.25
56232 | WA | 6.00
23442 | WA | 132.50
7844 | CA | 9.33
852353 | MA | 1.30
一种方法是先按“州”然后按“订单”对数据进行排序
Customer | State | Orders
—--------+-------+-------
12345 | CA | 3.25
7844 | CA | 9.33
852353 | MA | 1.30
532432 | MA | 8.44
12345 | MA | 10.12
56232 | WA | 6.00
23442 | WA | 132.50
（注意：虽然除了对整个输入进行完全排序（例如“TopK”）之外，还有专门的方法来计算此特定查询，但它们通常需要下面描述的相同的多列比较操作。因此，虽然我们将在本系列中使用简化示例，但它更广泛地适用）
基本实现
让我们以一个基本的排序内核为例，它将一组列作为输入，并返回一个标识排序顺序的索引列表。
> lexsort_to_indices([
["MA", "MA", "CA", "WA", "WA", "CA", "MA"]
])
[2, 5, 0, 1, 6, 3, 4]
> lexsort_to_indices([
["MA", "MA", "CA", "WA", "WA", "CA", "MA"],
[10.10, 8.44, 3.25, 6.00, 132.50, 9.33, 1.30]
])
[2, 5, 6, 1, 0, 3, 4]
此函数返回索引列表而不是直接对列进行排序，因为它
- 避免在排序过程中进行昂贵的数据复制
- 允许将值的复制延迟到尽可能晚的时刻
- 可用于对不属于排序键的其他列重新排序
lexsort_to_indices 的直接实现使用比较器函数，
row
index
┌─────┐ ┌─────┐ ┌─────┐ compare(left_index, right_index)
0 │ │ │ │ │ │
┌├─────┤─ ─├─────┤─ ─├─────┤┐ │ │
│ │ │ │ │ │ ◀──────────────────┘ │
└├─────┤─ ─├─────┤─ ─├─────┤┘ │
│ │ │ │ │ │Comparator function compares one │
├─────┤ ├─────┤ ├─────┤ multi-column row with another. │
│ │ │ │ │ │ │
├─────┤ ├─────┤ ├─────┤ The data types of the columns │
│ │ │ │ │ │ and the sort options are not │
└─────┘ └─────┘ └─────┘ known at compile time, only │
... runtime │
│
┌┌─────┐─ ─┌─────┐─ ─┌─────┐┐ │
│ │ │ │ │ │ ◀────────────────────────────────┘
└├─────┤─ ─├─────┤─ ─├─────┤┘
│ │ │ │ │ │
├─────┤ ├─────┤ ├─────┤
N-1 │ │ │ │ │ │
└─────┘ └─────┘ └─────┘
Customer State Orders
UInt64 Utf8 F64
比较器函数根据列类型逐列比较每一行
┌────────────────────────────────┐
│ │
▼ │
┌ ─ ─ ─ ┐ ┌ ─ ─ ─ ┐ │
│
┌─────┐ │┌─────┐│ │┌─────┐│ │
left_index │ │ │ │ │ │ │
└─────┘ │└─────┘│ │└─────┘│ Step 1: Compare State
(UInt64)
│ │ │ │
│ │ │ │
┌─────┐ ┌─────┐ ┌─────┐
right_index│ │ ││ ││ ││ ││
└─────┘ └─────┘ └─────┘ Step 2: If State values equal
│ │ │ │ compare Orders (F64)
Customer State Orders │
UInt64 │ Utf8 │ │ F64 │ │
─ ─ ─ ─ ─ ─ ─ ─ │
▲ │
│ │
└───────────────────────┘
此操作的伪代码可能如下所示
# Takes a list of columns and returns the lexicographically
# sorted order as a list of indices
def lexsort_to_indices(columns):
comparator = build_comparator(columns)
# Construct a list of integers from 0 to the number of rows
# and sort it according to the comparator
[0..columns.num_rows()].sort_by(comparator)
# Build a function that given indexes (left_idx, right_idx)
# returns the comparison of the sort keys at the left
# and right indices respectively
def build_comparator(columns):
def comparator(left_idx, right_idx):
for column in columns:
# call a compare function which performs
# dynamic dispatch on type of left and right columns
ordering = compare(column, left_idx,right_idx)
if ordering != Equal {
return ordering
}
# All values equal
Equal
# Return comparator function
comparator
# compares the values in a single column at left_idx and right_idx
def compare(column, left_idx, right_idx):
# Choose comparison based on type of column ("dynamic dispatch")
if column.type == Int:
cmp(column[left_idx].as_int(), column[right_idx].as_int())
elif column.type == Float:
cmp(column[left_idx].as_float(), column[right_idx].as_float())
...
更详细的内容超出了本文的范围，但总的来说，代码块的行为越可预测，其性能就越好。就这段伪代码而言，显然还有改进的空间
- `comparator` 执行大量不可预测的条件分支，其中执行的路径取决于数据值
- `comparator` 和 `compare` 使用动态调度，这不仅增加了更多的条件分支，还增加了函数调用开销
- `comparator` 在不可预测的位置执行大量内存读取
您可以在 sort.rs 和 ord.rs 中找到 arrow-rs 中多列比较器构造的完整实现。
归一化键/字节数组比较
现在想象一下，我们有一种方法可以将数据的每个逻辑行表示为一个字节序列，并且该序列的逐字节比较产生的结果与使用上述代码比较实际列值的结果相同。这种表示不需要切换列类型，内核将变为
def lexsort_to_indices(columns):
rows = convert_to_rows(columns)
[0..columns.num_rows()].sort_by(lambda l, r: cmp(rows[l], rows[r]))
虽然这种方法确实需要转换为字节数组表示形式，但它具有一些主要优势
- 可以通过比较内存中的字节来比较行，现代计算机硬件非常擅长使用经过极其优化的 memcmp 来完成这项工作
- 内存访问在很大程度上是可预测的
- 没有动态调度开销
- 直接扩展到更复杂的排序策略，例如
- 基于分布的排序技术，如基数排序
- 并行归并排序
- 外部排序
- …
您可以在 DuckDB 关于该主题的博文的“二进制字符串比较”部分以及 Graefe 的论文中找到有关如何利用这种表示形式的更多信息。 然而，我们发现如何将此技术应用于变长字符串或字典编码数据并不立即显而易见，我们将在本系列的下一篇文章中对此进行解释。
下一篇：行格式
这篇文章介绍了多列排序的概念和挑战，并说明了为什么可比较的字节数组表示形式（例如引入到 Apache Arrow 的 Rust 实现中的行格式）如此引人注目。
在下一篇文章中，我们将解释这种编码的工作原理，但如果您只想使用它，请查看文档以开始使用，并在我们的错误跟踪器上报告任何问题。与往常一样，Arrow 社区非常期待看到您用它构建的内容！