DataFusion 排序 Row 编码探索笔记 本文基于本地源码阅读与手算推导，主要对应当前工作区里的 DataFusion 与 Arrow 版本。示例编码来自本机 arrow-row-56.2.0 代码实现，若版本变化编码细节可能略有差异。背景 我在阅读 DataFusion 的排序优化时，看到 datafusion/physical-plan/src/sorts/stream.rs 中的 convert_batch 把多列排序键转换成 arrow::row::Rows。这让我产生了疑问：为什么要把多列转换为“行格式”的 bytes？直接用 bytes 比较怎么保证排序顺序正确？既然最终排序还是按字段优先级，那这样做到底比逐列比较有什么优势？ 带着这些问题，我继续追踪源码：从 DataFusion 的 RowCursorStream 一路进入 Arrow 的 arrow-row，最终确认 RowConverter 生成的是“保序编码”的行字节，它保证了字节序比较等价于多列排序比较，从而将多列比较简化为一次 memcmp。本文记录关键发现与具体示例。DataFusion 中的入口：convert_batch 关键逻辑在：datafusion/physical-plan/src/sorts/stream.rsfn convert_batch(&mut self, batch: &RecordBatch, stream_idx: usize) -> Result<RowValues> { let cols = self .column_expressions .iter() .map(|expr| expr.evaluate(batch)?.into_array(batch.num_rows())) .collect::<Result<Vec<_>>>()?; let mut rows = self.rows.take_next(stream_idx)?; rows.clear(); self.converter.append(&mut rows, &cols)?; let rows = Arc::new(rows); self.rows.save(stream_idx, Arc::clone(&rows)); Ok(RowValues::new(rows, rows_reservation)) } 这里的核心是：把排序列数组交给 RowConverter，产出 Rows（行格式 bytes）。 后续排序比较发生在：datafusion/physical-plan/src/sorts/cursor.rsimpl CursorValues for RowValues { fn compare(l: &Self, l_idx: usize, r: &Self, r_idx: usize) -> Ordering { l.rows.row(l_idx).cmp(&r.rows.row(r_idx)) } } Row::cmp 只是对 &[u8] 做字节序比较。这意味着 “列排序顺序”已经被编码进 bytes。Arrow RowConverter：保序编码的核心 RowConverter 位于 arrow-row crate：~/.cargo/registry/src/.../arrow-row-56.2.0/src/lib.rs 它的文档明确说明：Row 格式经过 排序归一化，保证字节序比较等价于多列 lexicographic 排序。编码总原则 每一列会先被编码成一个“保序字节序列”，然后按 sort key 顺序串联成整行。这样整行 bytes 的字典序比较，就等价于逐列比较。关键点一：固定长度类型 统一格式：[validity(1 byte)] [encoded bytes...] valid=0x01 表示非 NULLNULL sentinel：nulls_first 用 0x00；nulls_last 用 0xFF有符号整数（i8/i16/i32…）大端序翻转最高位（符号位） 为什么翻转符号位能保序？ 原始补码表示（以 i8 为例）：值 二进制 十六进制 -128 1000 0000 0x80 -1 1111 1111 0xFF 0 0000 0000 0x00 1 0000 0001 0x01 127 0111 1111 0x7F 问题：负数的最高位是 1，正数是 0。按无符号字节序比较会得到错误结果：-128 (0x80) > 127 (0x7F) ❌ 错误！ 翻转符号位后：值 原始 翻转后 -128 1000 0000 0000 0000 (0x00) -1 1111 1111 0111 1111 (0x7F) 0 0…