昨天講完一批多大、一批什麼形狀，結尾丟了一個反骨設計：DataFusion 從頭到尾吃 Arrow 欄式，排序時卻偷偷轉列式。
欄式適合「同一欄、一次一批」；排序要做的是「同一列、兩列互相比」。
這兩件事對記憶體的胃口不一樣，所以排序這一段換表示法。
它有三個環節：比同一列、把複合鍵編成能 memcmp 的 bytes、payload 只搬一次。

先看這句 SQL 在搬什麼

SELECT name, region, amount
FROM sales
ORDER BY region, amount DESC

手上這三列：

排完應該是 Bob（JP 50）、Ada（TW 100）、Cara（TW 80），先比 region 一樣再比 amount，這種兩欄以上的排序鍵叫複合鍵。
引擎反覆做兩件事：比兩列的鍵誰比較小，再決定整列換到哪裡。

問題來了～
Arrow 裡 region、amount、name 各住一塊 buffer，所謂「第 0 列」在記憶體裡根本不是一排

動機：要比的是同一列，不是同一欄

左邊是昨天的 RecordBatch：同一欄連續，正好給 SIMD 吃。
要比 Ada 和 Bob，CPU 得去 region 抓 TW / JP，再去 amount 抓 100 / 50。欄越多，一次比較跳越多次。
payload 欄（這裡的 name）就算不是 sort key，你若真的去搬整列，一樣得碰。

右邊那條短 bytes 才是排序真正要搬的東西。name 先別動。

怎麼做：這塊 bytes 長什麼樣

這套編碼有名字：RowFormat，arrow-rs 把它放在 arrow_row。

純欄式每次比較都是一串分支：這一欄是不是 null、型別怎麼比、ASC 還 DESC、這一欄打平了才看下一欄。複合鍵每多一欄，就多一輪完整的檢查，而且每比一次兩列都要重跑。

比大小這種事，CPU 其實有現成的 memcmp：給兩塊連續記憶體，從左往右掃，沒有任何分支
問題是 Arrow 的資料餵不進去，region 和 amount 各住一塊 buffer，「第 0 列」在記憶體裡不是一排，memcmp 的參數根本填不出來。

就算硬把它們湊在一起也還不行，x86 上 -5 和 3 的 little-endian 長這樣：

-5  →  FB FF FF FF
 3  →  03 00 00 00  

memcmp 先看第一個 byte，03 < FB，結論變成 3 < -5。排反了。

所以編碼要動手腳：非 null 先寫 0x01，有號整數翻掉最高位（讓負數跑到正數前面），再改成大端序。同一個例子變成：

-5  →  01 7F FF FF FB
 3  →  01 80 00 00 03

7F < 80，-5 < 3，這次對了。

浮點走同一條路，多一步：先依 IEEE 754 的 totalOrder 改成有號整數（負數把符號位以外的 bits 翻掉），再套上面的大端序。DESC 把該欄編碼反相（null 旗標那一 byte 除外）；NULLS LAST 把 null 旗標從 0x00 改成 0xFF，規則都編進 key 裡，比較迴圈就不必再問 SQL 的排序選項。

字串更煩，不能把 UTF-8 直接接在後面，否則下一個欄位會黏進字串尾巴一起比。
Arrow 用 block encoding，讓變長欄接起來之後的字典序仍然等於 SQL 的排序序。細節今天不展開，記住一件事就好：每個欄位編完，接在一起就能 memcmp。

範圍：哪些欄該進去，哪些不該

ORDER BY region, amount，吐出去的仍是 (name, region, amount)。sort key 跟輸出列不是同一件事。ORDER BY a + b 更明顯：要比的是 a + b，吐出去的還是原來那些欄。

如果把 name 這種 payload 也塞進 Row，排完再轉回 Arrow，大欄會被拷兩次。實際路徑是：

1. 只把 sort key 編成 Rows
2. memcmp 排出索引
3. 用 Arrow 的 take kernel，按索引把原欄一次重排

所以「排序時轉成列式」不是整張表搬家
是排序這一段借一塊連續的 key，用完就丟轉換成本是刻意的，而且是資料還在 cache 裡時

資料大到要 spill 到磁碟時，這塊已經正規化的 key 比較好寫出去，那是後話，D15 會碰到。

一句話串起來

排序需要「同一列連續」（1），這塊連續的 bytes 順便把比較規則燒進去讓 memcmp 直接可用（2），而且它只裝 sort key、不裝 payload（3）。

明天預告

明天要來介紹有些查詢連「一批一批算」都划不來，code-gen 把資料留在暫存器裡反而比較快。

那就明天見～

Reference:
https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-1/
https://arrow.apache.org/blog/2022/11/07/multi-column-sorts-in-arrow-rust-part-2/
https://arrow.apache.org/rust/arrow_row/index.html