Apache Arrow Rust 中快速且内存高效的多列排序，第 1 部分
已发布 2022 年 11 月 07 日
作者： tustvold 和 alamb
简介
排序是现代数据库和其他分析系统中最基本的操作之一，支撑着诸如聚合、连接、窗口函数、合并等重要运算符。据估计，数据处理系统中超过一半的执行时间都用于排序。因此，优化排序对于提高查询性能和整体系统效率至关重要。
排序也是计算机科学中研究最深入的主题之一。数据库的经典调查论文是 Goetz Graefe 的在数据库系统中实现排序，该论文提供了透彻的学术处理，并且至今仍然非常适用。但是，如何将该论文中描述的智慧和高级技术应用于现代系统可能并不明显。此外，优秀的 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
一种方法是先按 State 排序数据，然后按 Orders 排序
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在不可预测的位置执行大量内存读取
您可以在 arrow-rs 的 sort.rs 和 ord.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 的论文中找到有关如何利用这种表示形式的更多信息。但是，我们发现如何将此技术应用于可变长度字符串或字典编码数据并不容易，我们将在本系列的下一篇文章中对此进行解释。
下一步：行格式
这篇文章介绍了多列排序的概念和挑战，并展示了为什么可比较的字节数组表示形式（例如引入到 Rust 实现的 Apache Arrow 的 行格式）是如此引人注目的原语。
在 下一篇文章中，我们将解释此编码的工作原理，但如果您只想使用它，请查看 docs 以开始使用，并在我们的 bugtracker 上报告任何问题。与往常一样，Arrow 社区非常期待看到您使用它构建什么！