課題とスコープ
状態カラムには、デバイスのステータスやパーティション ラベルのように、同じ値が長く連続して繰り返される（ラン）ことがよくあります。チームは、メモリと転送コストを削減するために Arrow の Run-End Encoded（REE）レイアウトの導入を検討しています。run_ends、values、アクセス計算量、null の取り扱い、選定基準、検証方法について説明してください。
面接官が見ているポイント
- REE が各ランの長さではなく、ランの終了インデックスを保持していることを理解しているか。
- 論理長、ランダム アクセス コスト、圧縮効果を正しく計算できるか。
- null、空配列、隣接する同一ラン、交互に出現するデータを正しく処理できるか。
- Arrow IPC、複数の実装系、および明示的なフォールバックを考慮できているか。
確認すべき質問
- ラン長の分布と読み取りパターンはどのようになっていますか？
- 主なコスト要因はメモリ、IPC 転送、計算中のランダム アクセスのどれですか？
- コンシューマー側は REE をサポートしていますか、それとも通常の配列を受け取る必要がありますか？
- null は 1 つの状態ですか、連続する欠落ランですか、それとも空の値とは区別されるものですか？
30秒での回答
REE は 2 つの子配列を持つ論理配列として表現されます。run_ends に各ランの論理終了インデックスが格納され、values にランごとに 1 つの値が格納されます。親の長さは最後の終了インデックスとなります。ランが長ければ値バッファを削減できますが、ランダム アクセスは通常 run_ends に対する二分探索（O(log n)）になります。REE を採用する前に、実際のラン長とアクセス頻度の比率をベンチマークしてください。REE をサポートしていないコンシューマー向けには明示的にデコードする必要があり、物理的な子配列は通常のカラムではありません。
ステップごとの設計
1. レイアウトの不変条件を定義する
run_ends[i] は狭義の単調増加となる累積論理インデックスであり、values[i] はそのランの値です。ランの長さは現在の終了インデックスから直前の終了インデックスを引いた値であり、親の長さは最終の終了インデックスです。空配列は子を持たず、架空の終了インデックスを使用してはなりません。
2. メモリ削減効果を見積もる
通常の配列は 1 行につき 1 つの値を格納しますが、REE は 1 つのランにつき 1 つの値と 1 つの整数終了インデックスを格納します。インデックスと子配列のオーバーヘッドは、ランが十分に長い場合にのみ償却されます。カーディナリティが高いデータや交互に変化するデータでは、逆にサイズが増加する可能性があります。ベンチマークには null ビットマップ、アライメント、IPC メタデータも含めてください。
values = ["idle", "busy"]
run_ends = [4, 7]
logical = [idle, idle, idle, idle, busy, busy, busy]3. シーケンシャル アクセスとランダム アクセスを処理する
シーケンシャル スキャンは、現在のランへのポインタを保持することで、償却計算量 O(1) に近づけることができます。論理インデックスへのアクセスは、通常、二分探索によってそのインデックスより大きい最初の終了インデックスを見つける必要があります。バッチのスライシングでは、すべての要素を検索するのではなく、ランの境界を再利用する必要があります。ランダム アクセスが支配的である場合は、デコード コストと比較検討してください。
4. null と隣接ランのセマンティクスを維持する
null は論理的な親の値であり、対応する values のランに現れる必要があります。欠落ビットマップのみから推測することはできません。隣接するランは、セマンティクスが等しい場合にのみマージしてください。不明（unknown）、空文字列、デフォルト値が異なるビジネス状態である場合は、異なる値としてエンコードします。デコード後に、null ビットマップと値を要素ごとに比較検証してください。
5. 相互運用性を確認する
C++、Python、Java、および IPC コンシューマーが REE を読み取り、スライシング、フィルタリング、シリアライズ時に論理長を維持できるか確認します。通常の配列しかサポートしていないコンシューマーに対しては、明示的な境界でデコードし、変換コストと結果のハッシュを記録します。
6. 検証とフォールバック
全要素同一、全要素異なる、交互パターン、長いラン、null、空、非常に大きなインデックスを含むフィクスチャを生成します。論理長、要素値、ランダム インデックス、IPC ラウンドトリップを比較します。ランが短い場合、コンシューマーがサポートしていない場合、またはランダム アクセスのデコード コストが高すぎる場合は、通常のレイアウトにフォールバックします。
模範的な高水準の回答
まずラン長とアクセス パターンを計測します。REE の run_ends は累積終了インデックスであり、values はランごとに 1 つの値を持ち、親の長さは最終終了インデックスになります。シーケンシャル スキャンはラン ポインタを維持し、ランダム アクセスは通常二分探索を行います。長いランはスペースを節約しますが、交互データや高カーディナリティのデータではサイズが増加する可能性があります。実装では null を保持し、隣接する同一ランをマージし、空配列、スライス、IPC ラウンドトリップをテストします。サポートされていないコンシューマー向けには明示的にデコードし、ベンチマークに基づいて通常レイアウトと REE レイアウトのどちらを採用するかを決定します。
よくある間違い
run_endsを長さとして扱う → 累積インデックスが誤読される → 隣接する終了インデックスの差分から長さを導出する。- 値の数だけでメリットを見積もる → インデックス、null ビットマップ、アライメントが無視される → メモリ全体と IPC コストをベンチマークする。
- ランダム インデックスごとにランを線形スキャンする → 大規模配列で処理が遅くなる → 終了インデックスを二分探索するか事前にデコードする。
- null をデフォルト値として扱う → 不明な状態と実際の空の状態が混同される → 論理的な null セマンティクスを維持する。
- すべての Arrow 実装が REE をサポートしていると仮定する → IPC や言語間連携で障害が発生する → 機能マトリックスとフォールバックを維持する。
追加の質問と回答
REE のランダム アクセスの計算量はどのくらいですか？
論理インデックスより大きい最初の終了インデックスを見つける処理は、通常 O(log r)（r はラン数）です。シーケンシャル スキャンはポインタを維持しますが、ランダム アクセスが支配的であれば先行デコード（eager decoding）との比較を検討してください。
なぜラン長ではなく累積終了インデックスを格納するのですか？
このフォーマットでは、スライシングや二分探索で境界を直接特定するために累積論理インデックスを使用します。ラン長は隣接する終了インデックスの差分として得られます。
通常の配列の方が適しているのはどのような場合ですか？
ランが短い場合、値が交互に現れる場合、コンシューマーが REE をサポートしていない場合、またはランダム アクセスによりデコードが頻繁に発生する場合は、通常のレイアウトの方がサイズが小さく高速になることがあります。代表的なデータによるベンチマークと同等性チェックによって判断します。