WINDOW JOINを並列化・ベクトル化する方法
How we made WINDOW JOIN parallel and vectorized (questdb.com)
要約
QuestDBは、要求の厳しいワークロードに対応するオープンソースの時系列データベースです。この記事では、QuestDBがどのようにWINDOW JOIN操作を並列化・ベクトル化し、大幅なパフォーマンス向上を実現したかを解説しています。従来のSQLクエリが複雑で非効率だったのに対し、専用のWINDOW JOIN演算子を導入し、データ並列性とSIMD処理を組み合わせることで、競合他社と比較して25倍速い実行速度を達成しました。
全文翻訳
WINDOW JOIN を並列化・ベクトル化して実現した方法
QuestDB は、要求の厳しいワークロードに対応するオープンソースの時系列データベースです。取引フロアからミッションコントロールまで、超低レイテンシ、高スループットの取り込み、マルチティアストレージエンジンを提供します。Parquet と SQL のネイティブサポートにより、データはベンダーロックインなしでポータブルかつ AI レディです。
取引デスクで常に発生するワークロードを考えてみましょう。実行された各取引に対して、その取引を中心とした 1 秒間のウィンドウ内の平均ビッドとアスクを付与します。専用オペレーターがない場合、これは 2 つの JOIN、ウィンドウ開始時のキャリーフォワード引用のための ASOF JOIN、およびウィンドウ内の行のためのレンジ JOIN、UNION ALL による結合、GROUP BY による折りたたみが必要になります。
-- QuestDB のタイムスタンプはマイクロ秒単位なので、1_000_000 は 1 秒です。
WITH prevailing AS (
-- ウィンドウの開始時刻(取引時刻 - 1 秒)に対して ASOF マッチを行います。
-- 取引時刻そのものではありません。
SELECT t.orig_ts ts, t.symbol, p.bid, p.ask
FROM (
(SELECT (timestamp - 1000000) AS ts, symbol,
timestamp AS orig_ts
FROM trades)
TIMESTAMP(ts)
) t
ASOF JOIN prices p ON p.sym = t.symbol
),
in_window AS (
SELECT t.timestamp ts, t.symbol, p.bid, p.ask
FROM trades t
JOIN prices p ON p.sym = t.symbol
WHERE p.ts > t.timestamp - 1000000
AND p.ts <= t.timestamp + 1000000
)
SELECT ts, symbol, avg(bid) avg_bid, avg(ask) avg_ask
FROM (SELECT * FROM prevailing UNION ALL SELECT * FROM in_window)
GROUP BY ts, symbol;
これは機能しますが、単純な操作にしては SQL が多すぎます。ASOF JOIN とレンジ JOIN は、同じ質問の 2 つの部分を回答しているにもかかわらず、prices テーブルを独立してウォークします。また、レンジ JOIN はプランナーに sym でハッシュし、その後、すべてのマッチしたペアを BETWEEN 述語に対して再フィルタリングすることを強制します。ts に対する外部 GROUP BY はハッシュ集計であり、(ts, symbol) ペアごとに 1 行をマテリアライズする必要があり、テストデータでは 5000 万グループになります。オプティマイザーが融合、クリーンに並列化、またはベクトル化できる要素は何もありません。
WINDOW JOIN は、別のテーブルの各行を中心とした時間ウィンドウで 1 つのテーブルを集計するための QuestDB の専用構文です。同じクエリが、専用オペレーターで実現されます。
SELECT t.*, avg(p.bid) avg_bid, avg(p.ask) avg_ask
FROM trades t
WINDOW JOIN prices p
ON p.sym = t.symbol
RANGE BETWEEN 1 second PRECEDING AND 1 second FOLLOWING;
これでオペレーターは何をしているか理解できます。左側 (LHS - ここでは trades) の各行に対して、タイムスタンプが LHS タイムスタンプを中心とした [lo, hi] ウィンドウ内にある右側 (RHS - ここでは prices) の行を見つけ、一致するシンボルキーに制限し、集計関数のバッチで削減します。
それを高速化するには、2 つの要素が重要です。LHS に対するデータレベルの並列処理、および低カーディナリティの高速パスで、値を連続バッファにコピーして、SIMD 集計カーネル(SAMPLE BY 用に既に提供しているもの)をウィンドウスライスで変更なく実行できるようにします。Timescale、DuckDB、ClickHouse とのベンチマークでは、5000 万行の trades テーブルと 1億5000万行の prices テーブルを結合した結果、並列 + SIMD パスは QuestDB のシングルスレッドフォールバックよりも 5.0 倍、ClickHouse の最良の書き換えよりも 25 倍高速でした。
データレベルの並列処理
QuestDB は、時間でパーティション化された追記専用カラムファイルにデータを格納します。クエリエンジンは、これを ページフレーム のシーケンスとして読み取ります。これは、ファイルページに直接マッピングされる、連続したカラム形式のメモリ領域です。フィルタリングと集計は両方ともこの粒度で機能します。ページフレームは、ワーカー スレッドへのディスパッチの単位です。
WINDOW JOIN も同じモデルに従います。LHS テーブルはページフレームにスライスされ、各ワーカーはフレームを取得し、そのフレーム内のすべての LHS 行の集計結果を生成する責任を負います。そのためには、フレームがカバーするすべてのウィンドウに含まれる RHS 行が必要です。具体的には、LHS タイムスタンプが tLo から tHi まで実行され、[-w_lo, +w_hi] ウィンドウを持つフレームの場合、ワーカーは [tLo - w_lo, tHi + w_hi] 内の RHS 行を必要とします。このスライスを低コストで見つけることが、並列プランを可能にする鍵であり、QuestDB のストレージレイアウトがその実現を助けています。両方のテーブルの行は、ディスク上で 指定されたタイムスタンプ 順に保持されているため、任意の時間範囲に対する RHS スライスは、ワーカーごとのスキャンではなく、ワーカーごとの単一のバイナリ検索に収束します。
次に、LHS フレームに存在する結合キー について、ワーカーは RHS スライスから小さなインメモリインデックスを構築します。これは、キーごとの RHS タイムスタンプのリストと、集計する値のキーごとの配列です。インデックスが構築されたら、LHS 行に対する内部ループは、行ごとに 2 回のバイナリ検索で済みます。1 回はウィンドウのローバウンド用、もう 1 回はハイバウンド用で、その後、結果の連続範囲に対して集計を行います。両方のバイナリ検索は単調に前方にウォークするため、同じフレーム内の行全体で償却されます。
大まかには以下のようになります。
LHS page frames ┌─────┬─────┬─────┬─────┬─────┐ │ F0 │ F1 │ F2 │ F3 │ ... │ └──┬──┴──┬──┴──┬──┴──┬──┴─────┘ │ │ │ │ ┌──────┴┐ ┌──┴───┐ │ │ │worker0│ │worker1│ ... │ workers pulled from a shared pool └───┬───┘ └──┬────┘ │ one frame at a time │ │ │ ┌───────┴───────┐│ ┌───────┴───────┐ │ RHS slice + ││ │ RHS slice + │ │ per-key ││ │ per-key │ │ value arrays ││ │ value arrays │ └───────┬───────┘│ └───────┬───────┘ │ │ │ ▼ ▼ ▼ ┌───────────────────────────────────┐ │ for each LHS row in frame: │ │ bsearch lo, bsearch hi, │ │ aggregate(value_array[lo:hi]) │ └───────────────────────────────────┘
削減ステップはフレームごとでロックフリーです。ワーカーはフレーム間で可変状態を共有しません。これで外部並列処理は完了です。内部ループ、つまり各 LHS 行が RHS スライスを集計する部分で SIMD が活用されます。
低カーディナリティキーの高速パス
低カーディナリティの等価結合とベクトル化可能な集計の場合、RHS 値をキーごとの連続バッファにコピーするため、SAMPLE BY 用に既に提供している SIMD カーネルをウィンドウスライスで変更なく実行できます。
SIMD カーネルは、sum、avg、min、max およびその他のいくつかの関数を手作業でチューニングしたもので、ループイテレーションごとに 8 つの倍精度浮動小数点数を処理しますが、連続した 配列でのみ機能します。ウィンドウ内の RHS 行は連続していません。それらはページフレームに散らばっており、混合カラムを介してスレッド化されています。最初の試みでは、一致する行を 1 つずつウォークし、各行に対して computeBatch を呼び出していました。これは正しかったのですが、カーネルを十分に活用できていませんでした。
追加のパスをかける価値があるクエリの形状は、実際には最も一般的です。低カーディナリティの等価結合(典型的な p.sym = t.symbol ケース)と集計された数値カラムです。キーの数が少ない場合、キーごとの値バッファはキャッシュに収まり、それらをマテリアライズするコストは、各ウィンドウスライスをベクトル化された集計に渡すことで十分に回収されます。
高速パスは 2 つの条件によってゲートされます。クエリは、ベクトル化された実装がある集計(数値型に対する sum / avg / min / max / count ファミリ)を使用する必要があり、結合条件は、プランナーが認識する低カーディナリティの形状(現在は単一シンボルの等価結合)に適合する必要があります。両方が満たされる場合、ワーカーは RHS スライスを 1 回反復して、キーごとのタイムスタンプインデックスを構築し、かつ、集計対象カラムの値をキーごとの値バッファに同じパスでコピーします。バッファは型付けされ、パックされています。シンボル AAPL のすべての bid 値は、RHS タイムスタンプ順に、倍精度の連続ブロックに格納されます。適合しないクエリの場合、バッファコピーを完全にスキップし、スカラー computeBatch ループにフォールバックします。
内部ループが LHS 行に到達すると、キーごとの値バッファは既に SIMD が望む形式で配置されています。2 つのバイナリ検索により、バッファ内 の [rowLo, rowHi) が得られ、そのスライスを直接ベクトル化された集計に渡します。
for (int i = 0; i < groupByFuncCount; i++) {
groupByFunctions.getQuick(i).computeBatch(
value, // running aggregate state
bufferStart(i) + typeSize * rowLo, // pointer into the per-key buffer
(int) (rowHi - rowLo), // slice length
0
);
}
RHS スライスに対する追加のパスは無料ではありません。各 RHS カラムを 2 回読み取ります(1 回は値をキーごとのバッファに格納するため、もう 1 回は集計が消費するため)。一般的なプランでは、これはさらに悪化します。しかし:
- QuestDB の集計ループは、入力が連続している場合は入力で SIMD バウンドであり、そうでない場合は行ごとの
computeBatchの呼び出しバウンドです。倍精度浮動小数点数では、AVX2 はここで約 10 倍の性能向上をもたらします。 - RHS カラムは、プリフェッチングとともに順次読み取られ、これはメモリサブシステムが最も得意とするケースです。
- キーごとの値バッファは、現在の LHS フレームの RHS スライスに合わせてサイズ設定されているため、ワーキングセットは L2/L3 に収まります。
セカンドパスが正しい判断であることを確信するには、フレイムグラフをいくつか確認する必要がありました。それが完了すると、高速パスは小さなフレームでもスカラーパスよりも優れており、LHS フレームが大きくなるにつれてギャップは広がり、より多くの LHS 行が同じインデックス付きバッファを共有しました。
高速パスが利用できないクエリには、汎用述語パスが引き続き存在します。これは、バッファコピー手順なしでスカラー computeBatch ループを実行します。EXPLAIN は、クエリがどのパス上にあるかを示します。
Async Window Fast Join workers: 23 vectorized: true symbol: symbol=sym window lo: 1000000 preceding (include prevailing) window hi: 1000000 following PageFrame Row forward scan Frame forward scan on: trades PageFrame Row forward scan Frame forward scan on: prices
高速バリアントは Async Window Fast Join (並列) または Window Fast Join (シリアル) で、vectorized: true は SIMD カーネルが集計に使用されている場合です。ベクトル化不可能な集計を追加すると、同じオペレーターで vectorized: false になります。結合キーをシンボルカラムから切り替えると、完全に Async Window Join にフォールバックします。
SIMD (AVX2) ホットループ
スライスが連続すると、集計は SAMPLE BY が使用するものと同じ C++ カーネルになります。オペレーターが設計された典型的なクエリを見てみましょう。
SELECT t.timestamp, avg(p.bid)
FROM trades t
WINDOW JOIN prices p
ON p.sym = t.symbol
RANGE BETWEEN 1 second PRECEDING AND 1 second FOLLOWING;
キーごとの値バッファが構築されると、LHS 行ごとの作業は、その連続スライスに対する avg(double) のみになります。avg は、合計と非 NULL 値の数に分解されます(avg = sum / count、QuestDB では NULL は NaN としてエンコードされます)。そのため、実際に実行されるのは、sumDoubleAcc と呼ばれる融合された合計 + NaN カウントカーネルです。ホットループは AVX2 上で 1 イテレーションあたり 8 つの倍精度浮動小数点数を処理します。
; sumDoubleAcc, AVX2 hot loop body (rax = &d[i+8], rcx = i)
.Lloop:
vmovupd ymm3, [rax-0xfa0] ; load d[i+4..i+7]
vcmpunordpd ymm1, ymm3, ymm3 ; NaN mask, lane 1
vmovupd ymm2, [rax-0xfc0] ; load d[i..i+3]
vcmpunordpd ymm0, ymm2, ymm2 ; NaN mask, lane 0
vpcmpgtq ymm3, ymm8, ymm1 ; widen mask, lane 1
add rcx, 0x8 ; i += 8
vandpd ymm1, ymm1, ymm9 ; mask & 1 (count step), lane 1
add rax, 0x40 ; ptr += 8 doubles
vpcmpgtq ymm2, ymm8, ymm0 ; widen mask, lane 0
vandnpd ymm3, ymm3, [rax-0xfe0] ; (~mask) & d -> zero NaNs, lane 1
vandnpd ymm2, ymm2, [rax-0x1000] ; (~mask) & d -> zero NaNs, lane 0
vandpd ymm0, ymm0, ymm9 ; mask & 1, lane 0
vpaddq ymm4, ymm4, ymm1 ; nan_count += 1 per NaN, lane 1
vaddpd ymm5, ymm5, ymm3 ; sum += value, lane 1
vaddpd ymm6, ymm6, ymm2 ; sum += value, lane 0
vpaddq ymm7, ymm7, ymm0 ; nan_count += 1 per NaN, lane 0
cmp rcx, r8
jl .Lloop
1 イテレーションあたり 8 つの倍精度浮動小数点数、分岐なし、散布なし。各イテレーションは、2 つの 4 倍精度浮動小数点数レーンをロードし、レーンごとに NaN マスクを構築し、マスクを使用して NaN をゼロアウトしてから値を実行中の合計に追加し、同じマスクを使用して実行中の NaN カウンターをインクリメントします。ループの後、水平削減により 8 つのレーンがスカラー合計とスカラー NaN カウントに折りたたまれ、スカラーテールが < 8 要素の残りを処理します。avg が必要とする非 NULL カウントは、入力サイズから NaN カウントを引いたものです。
min および max の構造は同一です。同じロードおよび NaN マスクパターンで、vaddpd の代わりに vminpd / vmaxpd が使用されます。count はさらに単純です。実行中の NaN カウンターを入力サイズから引いただけです。
他のデータベースとの比較
ベンチマークしたクエリは、WINDOW JOIN をトップ 10 でラップしており、すべての結合出力行がヒープで考慮される必要がありますが、クライアントには 10 個の小さな行のみが返されます。これにより、エンジンコストと 5000 万件の結果行をワイヤー経由でストリーミングするコストが分離されます。
SELECT ts, symbol,
avg_bid, min_bid, max_bid,
avg_ask, min_ask, max_ask
FROM (
SELECT t.timestamp ts, t.symbol,
avg(p.bid) avg_bid, min(p.bid) min_bid, max(p.bid) max_bid,
avg(p.ask) avg_ask, min(p.ask) min_ask, max(p.ask) max_ask
FROM trades t
WINDOW JOIN prices p
ON p.sym = t.symbol
RANGE BETWEEN 1 second PRECEDING AND 1 second FOLLOWING
EXCLUDE PREVAILING
)
ORDER BY avg_bid + avg_ask DESC
LIMIT 10;
スケール: 5000 万件の取引(1000 のジップフィアンシンボル)が 1 日にわたってステップされ、同じウィンドウでマイクロ秒スケールのジッターでステップされた 1億5000万件の価格に対して行われます。導入部分とは異なり、ここでは INCLUDE PREVAILING をデフォルトで使用していましたが、ここでは EXCLUDE PREVAILING を使用します。なぜなら、INCLUDE PREVAILING は他のエンジンですべての書き換えでウィンドウ開始時刻より厳密に前の最後の RHS 行を特定することを強制し、取引ごとに 2 番目のルックアップを追加するだけで、基盤となる操作は変更されないためです。集計セットも公平性のために選択されています。min および max はプレフィックスサム分解可能ではないため、他のエンジンは avg のみのバリアントをエンジンで偽装するのをはるかに安価にする累積差分 ASOF JOIN トリックに頼ることができません。
Timescale、DuckDB、ClickHouse には直接的な WINDOW JOIN の同等物がないため、それぞれに私たちが発見した最も効率的な書き換えが与えられます。Timescale はレンジ JOIN + GROUP BY、DuckDB と ClickHouse は UNION ALL に対するウィンドウ関数です。それぞれに最善を尽くしました(イディオマティックな形状、適切なインデックスとクラスタリング、役立つ場所での並列処理ノブの最大化)が、試さなかったより高速な形状が存在する可能性があります。完全なスクリプト が利用可能であり、エンジンごとのクエリテキストは以下の ワークロードの実行方法 にあります。これらのエンジンのいずれかでより良い数値を達成できる場合は、ぜひお聞かせください。
結果
ワークステーションで実行: AMD Ryzen 9 7900 (12 コア / 24 スレッド)、64 GB RAM、NVMe SSD、Ubuntu 24.04。エンジンごとに 3 回から 5 回の実行のベストウォールタイム(秒)。DNF 行は 30 分の制限に達しました。実行が制限に達したら、それ以降の実行に時間を無駄にしませんでした。
[画像: 30 分の制限時間内に完了した 3 つのベンチマーク実行のログスケール棒グラフ: QuestDB 並列 + SIMD は 13.69 秒、QuestDB シングルスレッドは 67.97 秒、ClickHouse ウィンドウ関数は UNION ALL 上で 347.63 秒]
| Engine | Wall time (s) | vs QuestDB |
|---|---|---|
| QuestDB (WINDOW JOIN, parallel + SIMD) | 13.69 | 1.00x |
| QuestDB (WINDOW JOIN, single-thread + SIMD) | 67.97 | 4.96x |
| ClickHouse (window function over UNION ALL) | 347.63 | 25.4x |
| DuckDB (window function over UNION ALL) | DNF (>30 m) | n/a |
| Timescale (range join + GROUP BY, parallel) | DNF (disk) | n/a |
結果の読み方
最も情報量の多い比較は、QuestDB 内の比較です。並列およびシングルスレッドの数値は、同じプラン形状、同じベクトル化された内部カーネル、同じクエリを共有しています。唯一の違いは、データレベルの並列処理が有効になっているかどうかです。したがって、それらの間の 5.0 倍のギャップは、ワーカープール並列処理が何をもたらすかの直接的な測定値です。ワーカー数に対して線形ではなく、その理由は、外部の ORDER BY avg_bid + avg_ask DESC LIMIT 10 です。ソート + リミットは両方の構成でシリアルであり、このスケールでは並列 WINDOW JOIN フェーズ自体と比較可能な時間を要します。ジョインフェーズが並列実行によって縮小すると、ソート + リミットはそのまま残り、ウォールクロック番号の増加する割合を支配するようになります。23 個のワーカー スレッドを使用すると、アムダールの法則 の上限により、コア数に近いものではなく 5.0 倍の速度向上が見られます。ジョインは期待どおりにスケールしますが、プランの残りの部分はそうではありません。(クエリを INCLUDE PREVAILING に切り替えると、QuestDB では通常、これらの数値に 5〜10% が追加されます。これは、LHS 行ごとの追加の厳密に前のルックアップのためです。書き換えベースのプランでは、同じ切り替えははるかに重い変更です。優勢な価格は、ウィンドウ関数全体またはレンジ JOIN + GROUP BY 形状に折りたたまれない取引ごとのルックアップであり、2 番目のパスとして追加する必要があります。)
QuestDB の並列パスと他のエンジンとの比較は、3 つの複合効果によってギャップを埋めます。ウィンドウ構造を理解している専用オペレーター(汎用レンジ JOIN から再構築するのではなく)、LHS テーブルに対するデータレベルの並列処理、および連続スライスをベクトル化されたカーネルに渡して内部集計を行うことです。
ClickHouse は、制限時間内にベンチマークを完了した唯一の他のエンジンであり、UNION ALL のウィンドウ関数を使用していました。単一のソート + スライディングウィンドウ集計を結合ストリーム全体に適用することは、このワークロードの正しいプラン形状であり、QuestDB のシングルスレッドベースライン(347.63 秒対 67.97 秒)と同じオーダーになります。
それでも、並列 + SIMD 数値の 25 倍であり、QuestDB のオペレーター固有の作業が成果を上げているところです。正しいプラン形状であっても、結合ストリームに対する汎用ウィンドウオペレーターは、専用オペレーターが当然のように利用できるデータレベルの並列処理と連続スライス SIMD には及びません。
DuckDB は UNION ALL に対する同じウィンドウ関数書き換えを実行しましたが、制限時間内に完了しませんでした。初期の並列パーティションソートフェーズは、22 コアと約 22 GB の RSS を 50 GB のメモリ予算(スピルなし)で快適に使用しましたが、パーティションごとのウィンドウ集計は、パーティションごとに 1 つのスレッドによって提供されます。1000 のジップフィアンシンボルと 24 コアでは、大きなパーティションのロングテールはもはやワーカーに十分なデータを供給できず、最も重い数個のパーティションがクエリのテールをシリアル化することになります。
Timescale も完了しませんでした。そのレンジ JOIN + GROUP BY 書き換えは、プランナーノブを最大にした状態で 12 方向の並列処理を取得し、プランは正しい形状の作業を行います。Parallel Index Scan を prices に適用し、各ワーカーに Partial HashAggregate を供給します。しかし、約 5000 万グループに対する Partial HashAggregate は work_mem を超え、ボックス上の 541 GB の空きディスクを過ぎる一時ファイルをスピルし、約 6 分後に実行をクラッシュさせます。根本原因は DuckDB のテールと同じ形状です。汎用レンジ JOIN は、GROUP BY がそれらを折りたたむ前にすべての重複するペアをマテリアライズする必要がありますが、ウィンドウ形状の JOIN オペレーターは、範囲をウォークしながら行を折りたたみ、中間結果をまったく生成しません。
ワークロードの実行方法
エンジンバージョン: QuestDB 9.3.5、TimescaleDB 2.26.x (PostgreSQL 17 上)、DuckDB 1.5.2、ClickHouse 26.4。これはワークステーションクラスの再現環境です。スケールは、このボックスの RAM に収まるようにサイズ設定されています。結果の相対的な形状は、より大きなハードウェアでも維持されるはずです。絶対的な数値は、エンジンの並列効率とともにスケールします。すべてのエンジンは、特に指定がない限り、デフォルト設定で実行されます。TimescaleDB は timescaledb-tune によって自動調整され、ClickHouse は MergeTree で ORDER BY チューニングが必要であり、QuestDB のシリアルベースラインは server.conf で並列 WINDOW JOIN スイッチをオフにする必要があります。
完全なスキーマ定義、データジェネレーター、およびエンジンごとのクエリスクリプトは、ベンチマークリポジトリ にあります。各スクリプトは、スキーマを作成し、データが存在しない場合はロードしてから、クエリを 3 回から 5 回実行し(QuestDB の並列スイープは 5 回、その他は 3 回)、ベストウォールタイムを出力します。
QuestDB は、他のデータベースとの比較の冒頭に示した WINDOW JOIN クエリをそのまま使用します。
TimescaleDB は、すべての並列処理ノブを最大にした(parallel_setup_cost = 0、parallel_tuple_cost = 0、min_parallel_table_scan_size = 0、max_parallel_workers_per_gather = 12)レンジ JOIN + GROUP BY 書き換えを実行します。そのプランは Parallel Index Scan を取得しますが、ワーカーごとの Partial HashAggregate(約 5000 万グループ)は work_mem を超え、ディスクがいっぱいになるまで一時ファイルをスピルします。
SELECT ts, symbol,
avg_bid, min_bid, max_bid,
avg_ask, min_ask, max_ask
FROM (
SELECT t.ts, t.symbol,
avg(p.bid) AS avg_bid, min(p.bid) AS min_bid, max(p.bid) AS max_bid,
avg(p.ask) AS avg_ask, min(p.ask) AS min_ask, max(p.ask) AS max_ask
FROM trades t
LEFT JOIN prices p
ON p.sym = t.symbol
AND p.ts >= t.ts - INTERVAL '1 second'
AND p.ts <= t.ts + INTERVAL '1 second'
GROUP BY t.ts, t.symbol
) sub
ORDER BY (avg_bid + avg_ask) DESC
LIMIT 10;
prices に対する (sym, ts DESC) インデックスに対するラテラルサブクエリ形状は、ハイパーテーブルではよりイディオマティックに見えますが、設計上シングルスレッドである PostgreSQL のラテラルネストループに依存しています。パリティスケールでは、レンジ JOIN + 並列ハッシュ集計プランよりも 1 オーダー低速だったため、フルランでは除外しました。
DuckDB では、ウィンドウジョインの構造的に最も近いアナロジーは、取引と価格を 1 つのストリームにタグ付けする UNION ALL に対するウィンドウ関数です。これは sym でパーティション化され ts で順序付けされた bid と ask のウィンドウ集計を実行し、取引行のみを保持します。取引行はストリームで bid/ask を NULL として運びます。そのため、ウィンドウ内に価格が存在しない場合、NULL に対するウィンドウ集計は NULL と評価され、QuestDB の EXCLUDE PREVAILING 出力と一致します。DuckDB は INTERVAL レンジオフセットをネイティブで受け入れるため、マイクロ秒キャストは不要です。
WITH stream AS (
SELECT ts, sym, bid, ask, FALSE AS is_trade FROM prices
UNION ALL
SELECT ts, symbol AS sym, NULL::DOUBLE AS bid, NULL::DOUBLE AS ask, TRUE FROM trades
)
SELECT ts, symbol,
avg_bid, min_bid, max_bid,
avg_ask, min_ask, max_ask
FROM (
SELECT ts, sym AS symbol, is_trade,
avg(bid) OVER w AS avg_bid,
min(bid) OVER w AS min_bid,
max(bid) OVER w AS max_bid,
avg(ask) OVER w AS avg_ask,
min(ask) OVER w AS min_ask,
max(ask) OVER w AS max_ask
FROM stream
WINDOW w AS (
PARTITION BY sym
ORDER BY ts
RANGE BETWEEN INTERVAL 1 SECOND PRECEDING AND INTERVAL 1 SECOND FOLLOWING
)
)
WHERE is_trade
ORDER BY (avg_bid + avg_ask) DESC
LIMIT 10;
ClickHouse は、DuckDB 書き換えと同じウィンドウ関数オーバー UNION ALL の形状を実行します。両方のテーブルの MergeTree ORDER BY (sym, ts) クラスタリングは、パーティションごとのソートとウィンドウ集計が線形にストリーミングできるようにするために不可欠です。ClickHouse のウィンドウ関数は数値レンジオフセットを必要とするため、タイムスタンプはマイクロ秒に事前に変換されます。
WITH stream AS (
SELECT toUnixTimestamp64Micro(ts) AS ts_us, sym, bid, ask, 0 AS is_trade
FROM prices
UNION ALL
SELECT toUnixTimestamp64Micro(ts) AS ts_us, symbol AS sym,
CAST(NULL AS Nullable(Float64)) AS bid,
CAST(NULL AS Nullable(Float64)) AS ask,
1 AS is_trade
FROM trades
)
SELECT ts_us, symbol,
avg_bid, min_bid, max_bid,
avg_ask, min_ask, max_ask
FROM (
SELECT ts_us, sym AS symbol, is_trade,
avg(bid) OVER w AS avg_bid,
min(bid) OVER w AS min_bid,
max(bid) OVER w AS max_bid,
avg(ask) OVER w AS avg_ask,
min(ask) OVER w AS min_ask,
max(ask) OVER w AS max_ask
FROM stream
WINDOW w AS (
PARTITION BY sym
ORDER BY ts_us
RANGE BETWEEN 1000000 PRECEDING AND 1000000 FOLLOWING
)
)
WHERE is_trade = 1
ORDER BY (avg_bid + avg_ask) DESC
LIMIT 10;
その他の WINDOW JOIN のユースケース
取引と引用のパターンは典型的な例ですが、オペレーターは他の形状も処理します。
- ウィンドウ境界は定数、LHS カラム、または式にすることができます。
- 片側ウィンドウ(PRECEDING AND PRECEDING、FOLLOWING AND FOLLOWING)がサポートされています。
INCLUDE PREVAILING/EXCLUDE PREVAILINGは、ウィンドウ開始時刻以前の最新の RHS 行が、ウィンドウ内の行が既にカバーしていない場合にウィンドウの開始を埋めるかどうかを制御します。- サポートされている集計は
sum、avg、count、min、max、first、last、first_not_null、last_not_nullです。
片側ウィンドウの例として、ニュースの到着に取引カウントをアンカーします。
SELECT n.ts, n.headline, count(*) trades_5m
FROM news n
WINDOW JOIN trades t
ON t.symbol = n.symbol
RANGE BETWEEN 0 FOLLOWING AND 5 minutes FOLLOWING
EXCLUDE PREVAILING;
市場データパターンの詳細については、Capital Markets Recipes を参照してください。
今後の展望
これは、QuestDB で時間演算子をファーストクラスにするための広範な取り組みの 1 つです。WINDOW JOIN は ASOF JOIN の後の明白な次のステップでした。HORIZON JOIN(イベントごとに複数の固定ホライゾンでの P&L スタイルのマークアウトを取得できる)は既に 9.3.5 に含まれており、このシリーズの次の投稿では、その構築と最適化方法について説明します。
完全な文法とより長い例のリストについては、ドキュメントページ を参照してください。また、WINDOW JOIN を ASOF または HORIZON JOIN よりも優先すべき場合については、どの時系列 JOIN を使用すべきか を参照してください。そして、上記のパターンに適合しないウィンドウ形状のクエリがある場合は、ぜひお聞かせください。
いつものように、最新の QuestDB リリース を試して、コミュニティフォーラム でフィードバックを共有することをお勧めします。また、ライブデモ でクエリがどれだけ高速に実行されるかを確認することもできます。