ASOF結合のスケーリング

Daft はネイティブの ASOF 結合をサポートするようになりました。これは、異なるレートで刻むセンサーストリームなどの時系列データを整列させるために不可欠な操作です。この記事では、ASOF 結合を実装し、6倍の高速化とメモリ使用量の半減を達成した方法を説明します。最適化（ハッシュグループ化、二分探索、マルチスレッド並列化）の3つを掘り下げ、同じアーキテクチャが分散クラスタにどのようにスケールアウトするかを示します。

まず、ASOF 結合とは何か？ASOF 結合は、あるテーブルの各タイムスタンプを別のテーブルの最新のタイムスタンプと照合して、2つのデータセットをリンクします。以下の例では、左右のテーブルのデータが完全に一致しておらず、ASOF 結合は「各ビデオフレームについて、ロボットの最新の関節角度とグリッパー状態は何か？」という質問に答えます。

Daft で ASOF 結合を実行するには、.join_asof() メソッドを使用します。on パラメータは照合する列（通常はタイムスタンプ）、by パラメータはパーティション分割する列で、同じエンティティ（例：robot_id）内でのみ行が一致します。

V1 の構築：ソート＋2ポインタ 最初の実装は、ソートされた2ポインタ探索でした。左右のテーブルを複合キー (by, on) でソートし、2つのポインタで走査します。各左行について、右のテーブルで左のタイムスタンプを超えない最後の行を見つけます。複雑度は O(N log N + N)。 V2：ハッシュグループ化＋インデックス探索 データを by キーでハッシュテーブルにグループ化し、各グループ内でタイムスタンプをソートします。各左行について、対応するグループ内で二分探索を使用して最も近い右行を見つけます。複雑度は O(N log K)、K はグループサイズ。 V3：マルチタスク並列化 V3 は V2 を再設計し、タスク並列性を導入しました。ハッシュマップの各パーティションは独立したタスクとなり、V1 と V2 と同じハッシュグループ化アプローチを使用します。各タスクは自身の結果を保存し、並列実行を可能にします。完了後、マージステップで各左行に最適な一致を選択します。V3 の並列度はデータのカーディナリティに依存せず、2つの by キーしかなくてもマルチコアを活用できます。さらに、メモリ最適化：不必要な列を早期に剪定し、軽量ポインタで候補結果を追跡します。結果：ネイティブの ASOF 結合は速度を最適化し、メモリフットプリントを最小化します。

分散 ASOF 結合 一部のデータセットはシングルマシンのRAMに収まりません。1日分のロボットデータには1～10TBのビデオデータと5～500GBのセンサーデータが含まれます。そのため、V4 範囲分割 ASOF 結合を開発しました。まずキーをサンプリングしてグローバル分布を推定し、N-1 個の範囲境界を計算して、データを各ワーカーに均等に分散します。パーティションをまたぐ by キーを処理するために「キャリーオーバー」概念を導入：各ワーカーは前のパーティションの最新レコードを先頭に追加し、正確性を保証します。これにより、データが歪んでいても水平方向にスケールし、ホットスポットやテールレイテンシが発生しません。

ベンチマークでは、中規模（左テーブル1000万行、右テーブル1億行）で、V3 は V2 より1.7倍高速で、メモリは半分以下になりました。分散ベンチマークでは、2ノードから8ノードへの拡張で速度が線形に向上しました。

ぜひお試しください！コード例を含みます。フィードバックをお待ちしています。