プロンプトとコンテキスト
これは、カラムナーメモリフォーマットおよび実行エンジンに関する判断力を問う質問です。Apache ArrowのRun-End Encoding（REE）は、連続する同一値の論理配列を、単調増加するrun endsと対応するvalues配列によって表現します。親配列は独立したデータバッファを持ちません。このテストでは、あらゆる場所で圧縮を有効化するのではなく、データの分布に基づいて表現形式を選択できるかどうかが問われます。
このカラムは複数の言語実装間でやり取りされ、リーダー側でスライシング、フィルタリング、集約、ランダム位置の読み取りが必要になると想定してください。一部のシーケンスは何千行にもわたって同一のステータスを保持しますが、他のシーケンスではほぼ行ごとにステータスが変化します。エンコーディングの選択基準、計測ゲート、デコード境界、結果の検証方法を指定する必要があります。
面接官が評価するポイント
- run endはランの長さ（run length）ではなく論理位置であることを説明しつつ、valuesとrunsの対応関係を維持できているか。
- 隣接する重複、非隣接の重複、ランダムアクセスについて、REE、フラット配列、ディクショナリエンコーディングを比較できるか。
- null、スライス、連結、フィルタリング、および言語実装間の差異を適切に扱えるか。
- エンコーディングの選択を、安全なフォールバックを備えた測定可能なポリシーに落とし込めるか。
- メモリ削減量、デコードCPU、キャッシュ局所性、エンドツーエンドのクエリレイテンシを切り分けて評価できるか。
明確化のための質問
- ラン長の分布、値の型、null率はどのようになっていますか？これにより、run endsが論理行数よりも大幅に少なくなるかどうかが決まります。
- ワークロードはシーケンシャルスキャン、ランダム位置読み取り、あるいは多数のスライスやフィルタのいずれですか？アクセスパターンによってインデックスのコストが決まります。
- データは頻繁に変更（ミューテーション）されますか、それとも作成後は読み取り専用ですか？Arrowは読み取りとデータ交換を得意としており、頻繁なインプレース変更はトレードオフを変化させます。
- すべてのコンシューマがREEをサポートしていますか？サポートしていない場合、境界でデコードしますか、それともその物理エンコーディングを拒否しますか？
- メモリ予算とレイテンシSLOのどちらが厳しいですか？圧縮バイト数だけで設計を決定することはできません。
30秒の回答
「まずラン数と長さの分布を測定します。長いラン、シーケンシャルスキャン、メモリの制約がある場合は、処理する値とrun endsが少なくなるためREEが有利になります。値が激しく変化するデータや大量のランダムアクセスがある場合はフラット配列が適しており、非隣接の重複にはディクショナリエンコーディングが適している場合があります。この表現形式は論理長、単調増加するrun ends、値、nullセマンティクスを維持し、制御されたインデックスによって頻繁なランダム読み取りに対応できます。実際のクエリにおけるスライス、フィルタ、集約をベンチマークしてメモリ、p95レイテンシ、CPUを測定し、ラン比率やコンシューマの対応状況が判定基準を満たさない場合はフォールバックします。」
ステップごとの解説
ステップ 1: 論理モデルと物理モデルを定義する
各論理位置は、その位置より大きい最初のrun endに関連付けられた値に属します。run endsは単調増加し、最後のrun endは論理長と等しくなり、valuesの要素数は行数ではなくラン数と等しくなります。nullはvalues配列のセマンティクスの一部であり、個別の『nullラン』ルールは不要です。
例えば、論理値 A A A B B C C C C は、run ends 3, 5, 9 と values A, B, C を使用して表現できます。これはメモリレイアウトを説明するものであり、すべての実装における正確なメモリサイズを主張するものではありません。
ステップ 2: 分布に基づいて選択する
論理長をN、ラン数をRとすると、REEの主要なデータサイズはRとvaluesの型に依存します。フラット配列のサイズはNに比例します。RがNを大幅に下回る場合、メモリとスキャン量を削減できます。値が交互に変化する場合、REEは依然として多数のランを生成します。同一の値が離れて存在する場合、ディクショナリエンコーディングは値を共有しますが、行ごとに1つのインデックスを保持し続けます。
単一の圧縮比率をすべての型に適用してはいけません。文字列、幅の広い構造体、nullの多いカラムは、run ends、values、ビットマップ、アライメント、デコードコストを含めて個別に測定してください。カーディナリティが低いからといってランが長いとは限らず、カーディナリティが高くても局所的に長いランが存在することがあります。
ステップ 3: ランダムアクセス、スライシング、連結を処理する
フラット配列は位置を直接アドレス指定します。REEは単調増加するrun endsの中から対象のランを特定します。実装によっては線形スキャン、キャッシュ、または二分探索を使用するため、コストはライブラリとアクセスパターンに依存します。長いランとシーケンシャルスキャンにはカーソルが適しています。頻繁なランダム読み取りには、追加のメモリコストを払って疎インデックス（sparse index）を使用できます。
スライスは論理長と境界セマンティクスを維持しなければなりません。スライスの開始位置がランの途中にある可能性があるため、最初の出力ランには相対的な境界が必要であり、元のrun endsをそのまま再利用することはできません。2つのREE配列を連結するには、隣接する境界の同一値をマージし、最終的な論理位置が連続していることを確認する必要があります。
ステップ 4: nullと計算セマンティクスを確定する
Arrowの仕様では、親配列のnullは厳密にvalues配列内で表現されます。隣接するnullは1つのnull値を使用し、nullと非null値が交互に現れるとラン数が増加します。フィルタリング、比較、集約には明示的なnullの伝播が必要です。nullを通常の文字列としてデコードすると結果が変わってしまいます。
エンジンは、カウントや区間の累積など、ランごとに1回適用される演算を最適化できますが、その関数が行の順序に依存するかどうかを確認する必要があります。1行ごとに1つの結果を出力するオペレータは、デコードされたビューまたはカーソルビューを使用した方が単純な場合があります。すべての最適化は、論理的なフラット結果と照合して検証されなければなりません。
ステップ 5: 言語間およびフォールバックの境界を定義する
Arrowは言語横断的ですが、サポートされる計算関数やゼロコピーパスは実装によって異なります。交換境界では、物理型、論理長、run-end型、nullセマンティクス、およびデコードが許可されているかどうかを宣言する必要があります。コンシューマがREEをサポートしていない場合は、個々のビジネスコンシューマに中途半端なルールを実装させるのではなく、境界で一度だけデコードします。
送信側はカラム統計からREEを選択するか、両方の物理形式をキャッシュできます。1回のデコードを回避するためだけに、すべてのオペレータにREE分岐を持たせることは避けてください。ランダムアクセスが多いクエリ、サポートされていないコンシューマ、またはラン比率が高い場合は、フラット表現を使用する強い理由になります。
ステップ 6: 実際のワークロードで判定ゲートを設定する
少なくとも4つのベンチマークを構築します：ロングランのシーケンシャルスキャン、交互値スキャン、ランダム位置読み取り、スライス後の集約です。ピークメモリ、デコードCPU、キャッシュミスのプロキシ指標、p50/p95レイテンシ、出力の検証結果を記録します。小さなサンプルによって圧縮効果が過大評価されないよう、値の幅、null率、バッチサイズごとにセグメント化します。
ラン比率のサンプリングポリシーから開始し、クエリレイテンシのフィードバックを使用して調整します。REEによるメモリ削減量が目標に達しない場合や、ランダム読み取りのp95が予算を超える場合は、フラット配列にフォールバックします。フォールバック時もスキーマ、論理長、null結果を維持し、リプレイのためにエンコーディングバージョンを記録します。
設計上のトレードオフと境界
#### REE 対 フラット配列
REEは、長い隣接ランおよびメモリ制約のあるスキャンに適しています。フラット配列は、ランダムアクセス、単純なSIMD処理、幅広いコンシューマサポートに適しています。フォーマットの好みではなく、R/N、アクセスパターン、エンドツーエンドのメトリクスに基づいて選択してください。
#### REE 対 ディクショナリエンコーディング
REEは隣接する重複を圧縮します。ディクショナリエンコーディングは非隣接の重複を圧縮しますが、行ごとに1つのインデックスを保持します。カラムの値をディクショナリエンコードした上で、隣接するインデックスをREEエンコードすることも可能ですが、この組み合わせは実装とテストの複雑さを増すため、ベンチマークで正当性が証明された場合にのみ使用すべきです。
#### 一度デコードする 対 圧縮状態を維持する
一度デコードすると、多くのオペレータが単純化されランダム読み取りが向上しますが、メモリピークが発生します。圧縮状態を維持するとメモリを節約できますが、オペレータがラン境界を理解する必要があります。クエリプランに応じて選択し、必要に応じてホットなカラムに対して短寿命のフラットキャッシュを実体化します。
模範回答
「まずR/Nとラン長分布を測定し、次にスキャン、ランダム読み取り、スライスの比率を調査します。長いラン、シーケンシャルスキャン、メモリの制約がある場合はREEが有利です。単調増加するrun endsが論理境界を定義し、valuesはランごとに1つの値を格納し、values内でnullセマンティクスが維持されます。ランダムアクセスが多い場合やラン比率が1に近い場合はフラット配列が有利であり、非隣接の重複にはディクショナリとの比較を検討します。ランの途中から始まるスライスには相対境界が必要であり、連結処理では同一の境界ランをマージします。ロングラン、交互値、ランダム読み取り、集約についてメモリ、CPU、p95をベンチマークし、コンシューマの非互換性やSLO違反が発生した場合は、論理結果の一致を保ちながら境界でデコードします。」
よくある間違い
- run endsをランの長さ（run length）として扱う → 位置のルックアップやスライス境界が狂ってしまう → 各値が論理的な終了位置まで有効であることを明記する。
- カーディナリティが低いという理由だけでREEを選択する → 同一値が隣接していない可能性があり、ラン数がNに近くなる → 隣接性とアクセスパターンを測定する。
- values内のnullセマンティクスを無視する → デコードによってnull数や集約結果が変化する → Arrowの親配列nullルールをテストする。
- スライスに対して元のrun endsを再利用する → 相対長と最初の境界が狂ってしまう → スライスの境界と論理長を再計算する。
- 圧縮メモリのみを報告する → デコードCPU、ランダム読み取り、またはコンシューマのサポート状況がボトルネックになる可能性がある → エンドツーエンドのワークロードとp95を基準に判定する。
フォローアップと回答
すべての値が異なる場合でもREEは有用ですか？
通常は有用ではありません。RがNに近づくと、run endsによって境界情報のオーバーヘッドが増加し、ランダムアクセスも複雑になるため、フラット配列を使用します。それでも理論上のバイト数だけに頼るのではなく、実際の値の型とバッチサイズで測定してください。
スライスが長いランの途中から始まる場合、どのように正確性を維持しますか？
開始位置を含むランを見つけ、0から始まる相対境界にトリミングし、以降のrun endsからスライスの開始位置を減算し、最後の終了位置がスライスの長さと等しくなるようにします。フラットデコードと比較し、空のスライスや範囲外のスライスもテストします。
集約処理において、すべてのランを行ごとにデコードするのを避けるにはどうすればよいですか？
値と区間の長さのみに依存する場合は、値をそのラン長で乗算して累積するなど、ランレベルで計算します。行の順序、ウィンドウ、または行ごとの述語に依存する場合は、カーソルまたはデコードされたビューを使用します。各最適化は、nullおよびオーバーフローのルールに照らして検証します。
REEをサポートしていないリモートコンシューマ向けのデコードは誰が行いますか？
送信側または共有Arrowアダプターがフォーマット境界でデコードし、物理表現の変更を宣言します。コンシューマが独自にrun endsを推測してはいけません。デコード回数と展開後のメモリを記録し、必要に応じて互換性を保つためのフラットキャッシュを提供します。