Apache Arrow Rust 中快速且内存高效的多列排序，第 1 部分
发布 2022 年 11 月 7 日
作者： 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 的论文中找到有关如何利用此类表示的更多信息。然而，我们发现如何将此技术应用于变长字符串或字典编码数据并不立即显而易见，我们将在本系列的下一篇文章中解释这一点。
接下来：行格式
本文介绍了多列排序的概念和挑战，并展示了为什么可比较的字节数组表示，例如引入到 Apache Arrow Rust 实现中的行格式，是一个如此引人注目的基本数据类型。
在下一篇文章中，我们将解释这种编码的工作原理，但如果您只是想使用它，请查看文档以开始使用，并在我们的错误跟踪器上报告任何问题。一如既往，Arrow 社区非常期待看到您用它构建什么！