Apache Arrow Rust 中快速且記憶體效率高的多欄排序，第 1 部分
已發布 2022 年 11 月 7 日
作者 tustvold 和 alamb
簡介
排序是現代資料庫和其他分析系統中最基本的操作之一，是諸如聚合、聯結、視窗函數、合併等重要運算子的基礎。據估計，資料處理系統中超過一半的執行時間都花在排序上。因此，最佳化排序對於提高查詢效能和整體系統效率至關重要。
排序也是電腦科學中研究最透徹的主題之一。關於資料庫的經典綜述論文是 Goetz Graefe 的在資料庫系統中實作排序，該論文提供了詳盡的學術處理，至今仍然非常適用。然而，如何將該論文中描述的智慧和先進技術應用於現代系統可能並不明顯。此外，關於排序的優秀 DuckDB 部落格 強調了許多排序技術，並提到了可比較的列格式，但它沒有解釋如何有效地排序變長字串或字典編碼資料。
在本系列中，我們詳細解釋了 列格式 在 Rust 實作 的 Apache Arrow 中的應用，以及我們如何使用它使排序速度比基於替代比較器的途徑快 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執行大量在不可預測位置讀取記憶體的操作
您可以在 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 中的）是如此引人注目的基本要素。
在 下一篇文章 中，我們將解釋這種編碼的工作原理，但如果您只想使用它，請查看 文件 以開始使用，並在我們的 bugtracker 上報告任何問題。一如既往，Arrow 社群 非常期待看到您使用它構建的成果！