# キー正規化 ## 定義 キー正規化(key normalization)は、ソートキーとなる列の値を、型ディスパッチ・昇順/降順・NULL処理・複数列の辞書式順序(先頭列が優位)を考慮した比較演算の代わりに、単一の`<`比較で行順序を決定できるバイト列へ事前変換する手法である(Source: [[@2026__DiDi__Sorting Large Tables]] p.06)。ソート処理では行比較が頻出かつコストが高いため、比較の複雑さを正規化フェーズに前借りし、実際のソート・マージ中の比較を単純化する。 [[DuckDB]]はキー正規化の適用対象がとくに固定長キー(fixed-size keys)である場合、既知の長さ`n`バイトの値を`⌈n/8⌉`個の`uint64_t`にグループ化した`FixedSortKey`構造体(例: `part0`・`part1`)に格納する。CPUは可変長バイト列比較より固定長整数比較のほうが高速なため、`LessThan`は`part0`同士の比較、タイの場合のみ`part1`同士の比較という辞書式比較を1回の`<`判定に落とし込む(p.07)。SQLクエリにペイロードが無い場合(`SELECT c1, c2 FROM ... ORDER BY c1, c2`のような列そのものが出力対象のケース)は正規化キーのみを保持し、出力時に逆変換(un-normalize)できるという設計になっている(p.07 脚注4)。 正規化されたキーは、C++の`std::iterator`インターフェースを前提とした既存ソート実装(Vergesort・Ska Sort・Pattern-defeating QuickSort)にそのまま適用できる点もキー正規化の効用として挙げられている(p.08)。DuckDBではこの正規化処理はユーザレベルにもスカラSQL関数`create_sort_key()`として公開されている(p.06 脚注3)。 ## 横断的知見 (単一ソースのみのため蓄積中。2ソース目以降、突き合わせで見えた観察をここに追記する。) ## 未解決の問い - `create_sort_key()`がユーザ向けにどこまでDuckDB内部実装(`FixedSortKey`)と同一の正規化ロジックを使っているか(スライドは内部実装の説明が中心で、ユーザ関数との対応関係の詳細には踏み込んでいない)。 - 可変長キー(文字列など、`n`が固定長でないケース)の正規化がどう扱われるか。スライドp.07は「既知の長さ`n`バイト」の固定長ケースのみを扱っており、可変長ケースの具体的な正規化戦略は本資料からは確認できない。 - 正規化キーのみを保持する最適化(ペイロードなしクエリ)が、複数列・複合ソートキーのケースでどこまで適用されるか。 ## 関連 - [[@2026__DiDi__Sorting Large Tables]] — 本概念の一次ソース。 - [[外部マージソート]] — キー正規化はフェーズ➊(スレッドローカルソート)の前処理として位置づけられる。 - [[DuckDB]] — `create_sort_key()`としてユーザレベルにも公開。 ## 出典 - [[@2026__DiDi__Sorting Large Tables]](p.06-08)