Apache Arrow Rust 中快速且記憶體效率高的多欄排序，第 2 部分
已發布 2022 年 11 月 07 日
作者 tustvold 和 alamb
簡介
在本篇貼文的第 1 部分中，我們描述了多欄排序的問題以及有效率地實作它所面臨的挑戰。這第二篇貼文將說明 Rust 實作的 row 格式在 Apache Arrow 中如何運作和建構。
Row 格式
Row 格式是一種可變長度的位元組序列，藉由串連每個欄位的編碼形式而建立。每個欄位的編碼取決於其資料類型（和排序選項）。
┌─────┐ ┌─────┐ ┌─────┐
│ │ │ │ │ │
├─────┤ ┌ ┼─────┼ ─ ┼─────┼ ┐ ┏━━━━━━━━━━━━━┓
│ │ │ │ │ │ ─────────────▶┃ ┃
├─────┤ └ ┼─────┼ ─ ┼─────┼ ┘ ┗━━━━━━━━━━━━━┛
│ │ │ │ │ │
└─────┘ └─────┘ └─────┘
...
┌─────┐ ┌ ┬─────┬ ─ ┬─────┬ ┐ ┏━━━━━━━━┓
│ │ │ │ │ │ ─────────────▶┃ ┃
└─────┘ └ ┴─────┴ ─ ┴─────┴ ┘ ┗━━━━━━━━┛
Customer State Orders
UInt64 Utf8 F64
Input Arrays Row Format
(Columns)
編碼經過仔細設計，因此不需要跳脫字元：位元組是否為 sentinel（例如 null）或值的一部分，永遠不會模稜兩可。
無號整數
若要編碼非 null 無號整數，會寫入位元組 0x01，然後依序寫入整數的位元組，從最高有效位元開始，即 big endian。Null 編碼為 0x00 位元組，後接整數零值的編碼位元組
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
3 │03│00│00│00│ │01│00│00│00│03│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
258 │02│01│00│00│ │01│00│00│01│02│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
23423 │7F│5B│00│00│ │01│00│00│5B│7F│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
NULL │??│??│??│??│ │00│00│00│00│00│
└──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
32-bit (4 bytes) Row Format
Value Little Endian
有號整數
在 Rust 和大多數現代電腦架構中，有號整數使用二補數進行編碼，其中數字的負數是藉由翻轉所有位元並加 1 來計算。因此，翻轉最高位元並將結果視為無號整數可以保留順序。然後，可以使用前一節中描述的無號整數相同編碼來編碼此無號整數。例如
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
5 │05│00│00│00│ │05│00│00│80│ │01│80│00│00│05│
└──┴──┴──┴──┘ └──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
┌──┬──┬──┬──┐ ┌──┬──┬──┬──┐ ┌──┬──┬──┬──┬──┐
-5 │FB│FF│FF│FF│ │FB│FF│FF│7F│ │01│7F│FF│FF│FB│
└──┴──┴──┴──┘ └──┴──┴──┴──┘ └──┴──┴──┴──┴──┘
Value 32-bit (4 bytes) High bit flipped Row Format
Little Endian
浮點數
浮點數值可以根據 IEEE 754 totalOrder 謂詞（在 Rust 中由 f32::total_cmp 實作）排序。此排序將浮點數值的位元組解譯為對應大小的有號 little-endian 整數，在負數的情況下，翻轉除了符號位元以外的所有位元。
因此，浮點數值會轉換為適當大小的有號整數表示法，然後使用前一節中描述的有號整數相同編碼，來編碼為 row 格式。
位元組陣列（包括字串）
與上面的基本類型不同，位元組陣列是可變長度的。對於短字串，例如上面範例中的 state，可以將所有值填充到最長值的長度，並使用諸如 0x00 之類的固定值，並產生固定長度的 row。這是 DuckDB 部落格中描述的用於編碼 c_birth_country 的方法。
但是，字串欄位中的值長度通常差異很大，或者在執行開始時不知道最大長度，因此將字串填充到固定長度是不明智和/或不切實際的。因此，Rust Arrow row 格式使用可變長度編碼。
我們需要一種編碼，可以明確地終止位元組陣列的結尾。這不僅允許從 row 格式還原原始值，還可以確保在與包含較短位元組陣列的 row 進行比較時，不會將較長位元組陣列的位元組與不同欄位的位元組進行比較。
Null 位元組陣列編碼為單個 0x00 位元組。同樣地，空位元組陣列編碼為單個 0x01 位元組。
若要編碼非 null、非空的陣列，首先寫入單個 0x02 位元組。然後以 32 位元組區塊寫入陣列，每個完整的區塊後接一個 0xFF 位元組作為繼續符記。最後一個區塊會以 0x00 填充到 32 位元組，然後在繼續符記的位置，後接這個最後區塊的未填充長度（以單個位元組表示）
請注意，以下範例編碼使用 4 個位元組的區塊大小，而不是 32 個位元組，以求簡潔
┌───┬───┬───┬───┬───┬───┐
"MEEP" │02 │'M'│'E'│'E'│'P'│04 │
└───┴───┴───┴───┴───┴───┘
┌───┐
"" │01 |
└───┘
NULL ┌───┐
│00 │
└───┘
"Defenestration" ┌───┬───┬───┬───┬───┬───┐
│02 │'D'│'e'│'f'│'e'│FF │
└───┼───┼───┼───┼───┼───┤
│'n'│'e'│'s'│'t'│FF │
├───┼───┼───┼───┼───┤
│'r'│'a'│'t'│'i'│FF │
├───┼───┼───┼───┼───┤
│'o'│'n'│00 │00 │02 │
└───┴───┴───┴───┴───┘
這種方法鬆散地受到 COBS 編碼的啟發，並且選擇它而不是更傳統的 位元組填充，因為它更適合向量化，特別是具有 AVX-256 的硬體可以在單個指令中複製 32 位元組區塊。
字典陣列
字典編碼資料（在 pandas 中稱為類別型）越來越重要，因為它們可以非常有效率地儲存和處理低基數資料。
編碼字典陣列的簡單方法是直接使用先前描述的基本值編碼來編碼邏輯值。但是，這會失去字典編碼在減少記憶體和 CPU 消耗方面的優勢。
更複雜的是，字典編碼的 Arrow 實作非常通用，我們無法對字典的內容做出任何假設。特別是，我們不能假設字典值已排序，也不能假設同一個字典用於欄位中的所有陣列
以下範例顯示如何使用兩個不同的字典在兩個陣列中編碼字串欄位。第一個批次中的字典鍵 0、1 和 2 對應於與第二個字典中相同鍵不同的值。
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─
┌───────────┐ ┌─────┐ │
│ │"Fabulous" │ │ 0 │
├───────────┤ ├─────┤ │
│ │ "Bar" │ │ 2 │
├───────────┤ ├─────┤ │ ┌───────────┐
│ │ "Soup" │ │ 2 │ │"Fabulous" │
└───────────┘ ├─────┤ │ ├───────────┤
│ │ 0 │ │ "Soup" │
├─────┤ │ ├───────────┤
│ │ 1 │ │ "Soup" │
└─────┘ │ ├───────────┤
│ │"Fabulous" │
Values │ ├───────────┤
│ Dictionary (indexes in │ "Bar" │
dictionary) │ ├───────────┤
│ │ "ZZ" │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘ ├───────────┤
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ │ "Bar" │
│ ├───────────┤
│ ┌───────────┐ ┌─────┐ │ "ZZ" │
│"Fabulous" │ │ 1 │ │ ├───────────┤
│ ├───────────┤ ├─────┤ │"Fabulous" │
│ "ZZ" │ │ 2 │ │ └───────────┘
│ ├───────────┤ ├─────┤
│ "Bar" │ │ 1 │ │
│ └───────────┘ ├─────┤
│ 0 │ │ Logical column
│ └─────┘ values
Values │
│ Dictionary (indexes in
dictionary) │
─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┘
允許我們有效率地為這類資料建立 row 格式的關鍵觀察是，給定位元組陣列，始終可以藉由新增一個額外的位元組來建立在排序順序中位於其之前或之後的新位元組陣列。
因此，我們可以逐步建立從字典值到可變長度位元組陣列的保序映射，而無需事先知道所有可能的字典值，而是隨著我們遇到新的字典值而引入映射。
┌──────────┐ ┌─────┐
│ "Bar" │ ───────────────▶│ 01 │
└──────────┘ └─────┘
┌──────────┐ ┌─────┬─────┐
│"Fabulous"│ ───────────────▶│ 01 │ 02 │
└──────────┘ └─────┴─────┘
┌──────────┐ ┌─────┐
│ "Soup" │ ───────────────▶│ 05 │
└──────────┘ └─────┘
┌──────────┐ ┌─────┐
│ "ZZ" │ ───────────────▶│ 07 │
└──────────┘ └─────┘
Example Order Preserving Mapping
用於產生此映射的資料結構細節超出了本篇部落格文章的範圍，但可能是未來文章的主題。您可以在此處找到程式碼。
資料結構還確保沒有值包含 0x00，因此我們可以使用 0x00 作為結束分隔符直接編碼陣列。
Null 值編碼為單個 0x00 位元組，非 null 值編碼為單個 0x01 位元組，後接由保序映射確定的 0x00 終止的位元組陣列。
┌─────┬─────┬─────┬─────┐
"Fabulous" │ 01 │ 03 │ 05 │ 00 │
└─────┴─────┴─────┴─────┘
┌─────┬─────┬─────┐
"ZZ" │ 01 │ 07 │ 00 │
└─────┴─────┴─────┘
┌─────┐
NULL │ 00 │
└─────┘
Input Row Format
排序選項
到目前為止，我們忽略的一個細節是如何支援升序和降序排序（例如 SQL 中的 ASC 或 DESC）。Arrow Rust row 格式藉由簡單地反轉編碼表示法的位元組來支援這些選項，除了用於 null 性編碼的初始位元組之外，每個欄位都這樣做。
同樣地，支援 SQL 相容排序也需要一種可以指定 NULL 值順序的格式（在所有非 NULL 值之前或之後）。Row 格式藉由選擇性地將 null 編碼為 0xFF 而不是 0x00 來支援此選項，每個欄位都可以設定。
結論
希望這兩篇文章讓您對可比較的 row 格式的可能性及其運作方式有所了解。請隨時查看文件以取得入門說明，並在我們的錯誤追蹤器上報告任何問題。
將此格式用於詞彙排序比基於比較器的舊方法快超過 3 倍，對於字串、字典和具有大量欄位的排序，優勢尤其明顯。
我們也已經使用它將 DataFusion 專案中保留排序的合併效能提高了一倍以上 double，並且預期在我們將其應用於排序、分組、聯結和視窗函數運算子時，效能提升會相似或更高。
一如既往，Arrow 社群非常期待看到您用它構建什麼！