DuckDB公式ブログ:Flying Through Windowsを読み解く
以前もDuckDBのブログ記事を読んで自分なりにメモをあげたがその道の専門家が書いていて学びが多いので今回も記事にしてみました。
[引用元]
Flying Through Window
今回は機能追加についてというより、メモリリソース他内部の改善に関しての記事
2023年の夏にセグメントツリーの評価コードを、単一値評価からベクトル化された評価へと変換
🫠という感じなので調べる。
-
セグメントツリー:
セグ木とか略されているのはよく聞いたことある。
ある範囲のデータの計算をするためのデータ構造。
これを使えば[2, 5, 1, 4] に対し、「区間 [2,5] の最小値は？」に高速に答えられる。
ducdkbではsumとかmaxとか集約関数に対応するために使われている? -
評価コード(Evaluation Code):
セグメントツリーを使って値をどうやって計算（評価）するかのプログラムのコード -
単一値評価（Single-Value Evaluation):
例えば[2, 5, 1, 4] の合計を求めるときに、
2 + 5 → 7 + 1 → 8 + 4 1個ずつ足していく方法 -
ベクトル化（Vectorized Evaluation:
先ほどのデータ [2, 5, 1, 4] の合計を求めるときに、
2+5, 1+4 を 同時に 計算 → [7, 5]
まとめてCPU処理するので、単一値評価と比べて速度⬆️
旧バージョンでは、こういう計算の時に集約処理の update（更新） や combine（統合） のAPIを使用してたが、対象は 一個の行の値とツリーの状態 だけだった。(だから遅かったらしい)
新バージョンでは
セグメントツリーの集約処理(計算)を葉ノードの値(元データ)とツリーの状態(計算途中データ)をベクトルで貯める。→ 2048行のベクトル容量に達した時点で各出力行の状態に出力(フラッシュ)
という流れでデータ処理するようにしたらしいです。
単純に一個づつ計算していく方法ではなくて、ベクトル化で並列処理していくということだと思います。
(このあたりのソースコードとかも理解したいですが...割愛します)
FILTER や EXCLUDE 他計算順序が大事な集約関数もあったが、それらも含めてセグメントツリーがベクトル化されて並列処理できるようになった。→パフォーマンスは約4倍向上!
またDISTINCTの実装する際にマージソートツリーを使い速度向上したとのこと。
- マージソートツリー
各ノードに、その下の区間のソート済みデータを格納してるようなセグメントツリー
各値がソート済みのためDISTINCTの重複削除操作をする時にその処理が速くなるということだろうか...
今後は
分位数（quantile）、中央値の絶対偏差（mad）、最頻値（mode）など）ベクトル化して処理が高速になるかも...!ということでした。
これが実装されれば統計処理がさらに高速化しますね...
定数集約（Constant Aggregation）
直近7日間の平均売上と全期間の平均売上を比べるような計算について
旧実装では、たった 1 つの値を求めるだけのためにセグメントツリー（Segment Tree）を構築していて遅かった。セグメントツリーで集約処理を サブクエリで計算し、パーティションキーで結合(joinをその度するということ?)する、という流れだったらしいです。(なので遅かった。)
新バージョンではパーティション全体の集約値を一度だけ計算して計算結果を定数ベクトルとして保存し、すべての行で共有して再利用...つまり例えば全期間の平均売上は当然どこの行で計算しても同じ値になるのでそれを一回だけ計算して結果を使い回す...ということだと思います。
Streaming Windows
ウィンドウ関数は「全体のデータを見ながら、一部のデータだけ計算する」という計算処理。
この処理は実は結構重い処理らしい。
具体的には以下のような感じだと思う。
- 1データ全体をメモリにロード
ウィンドウ関数を使うテーブル全体を一度メモリに読み込む（materialized）。
例えば、データが100万行あるなら、そのすべてを一度メモリに展開する。 - 2各パーティションごとに分割
PARTITION BY がある場合、パーティション単位にデータを分ける。
例えば、「店舗ごとの売上ランキング」を計算するときは、店舗ごとにデータをグループ化する。
-3 各パーティション内でソート
ORDER BY を指定した場合、そのパーティション内でデータを並び替える。
例えば、「購入日時順に累積売上を計算」するなら、日付順にデータを並べ直す。
逆に言えば2と3がなければその分処理が速くなる。
例えば以下のような計算
行番号（row_number）を割り振る→ROW NUMBER OVER
累積合計（running sum）を計算...などなど
こういった計算はストリーミング処理（streaming evaluation） によって、1スレッドで効率的に処理できるので速い。
論理ウィンドウオペレーター
DuckDB ではすべてのウィンドウ関数を1つの論理ウィンドウオペレーターに紐づけるとのこと。
同じパーティション（PARTITION BY）を持つ関数や、順序（ORDER BY）が互換性のある関数をそれぞれグループ化して計算する...順序があるやつは並べ替えしなければいけないし、パーティション分けしないといけないものはパーティション分けする必要がある。それらを別々の論理ウィンドウオペレーターに結びつけるということだと思う。
それが完了した後に物理的なウィンドウオペレーターに割り当ててそれが実際の処理を行う。
ただしStreaming Window(オーダーやパーティション処理がないやつ)は先に処理される。(ソートなどしてしまうといけないので)
Streaming Windowとして使えるもの(速い処理):
集約関数（Aggregates）
-
BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW
先頭から現在の行までの計算 -
first_value
最初の値 -
orderbyのないrank計算
percent_rank
rank（ランク）
dense_rank（密なランク）
orderbyなしでrankを使用するとrank計算せず全ての行が1位ということになり計算不要のため。 -
row_number（行番号）
行数をカウントのみ -
lead / lag
leadは次の値、lagは前の値(時系列データの特徴量などで使用)
これらはバッファで保持?するらしいので速い
Streaming Windowとして使えないものと制限:
IGNORE NULLS や EXCLUDE、ORDER BY は使用不可
lead / lag の距離は ±2048 行以内に制限（通常 1 なので問題なし）
LEAD のストリーミング最適化による劇的な改善
特に LEAD 関数のストリーミング処理の最適化によって 大幅なパフォーマンス向上
今後「現在の行から1つ前」までのデータだけバッファに保持する最適化 が可能かも?
パーティション単位の評価（Partition Major Evaluation）
パーティションのサイズに偏りがあったり、パーティションが1つしかない（よくあるケース）場合の処理について
バージョン1.1で
パーティションを 大きいものから小さいものの順 に評価し、
分散させながら、共有データ構造へのアクセスを同期する仕組みを導入しました。
(具体的な処理については不明)
パーティション分割されていないデータ でのコア利用率の大幅改善
未解決：サブパーティションの粒度
コピー処理を避けるために ソート処理で生成されたブロック単位でパーティションを管理しているが
これではサブパーティションの粒度が粗すぎるらしいのでこれが今後の課題とのこと。
メモリ不足（Out of Memory）対策
ウィンドウ関数の計算では データ全体をメモリ上に保持するクエリのメモリ
v1.2 ではページング可能なコレクション（pageable collection）を使用して各々のパーティションを保持しているらしい。
ウィンドウ処理の複雑さとメモリ負荷の課題
ウィンドウ処理は非常に複雑で大規模なデータ構造 がメモリに残る問題がある。
(セグメントツリーやマージソートツリー、中間状態などなど...)
こういう時にメモリではなくディスクにシリアライズ（書き出し）する汎用的な仕組みが必要...だが現時点では未実装
式の共有によるメモリ削減
DuckDB v1.2 で、新たな最適化が追加され、式の評価(計算結果)を関数間で共有可
ORDER BY の ソート引数
ウィンドウ関数の 範囲指定（Range Expressions）
lead(), lag(), nth_value() のような 値参照関数
フレーム境界（Frame Boundaries）
セグメントツリー（Segment Trees）
などなど...
まとめ
ちょっと長かったのでどちらかというと調べながらまとめた私的なメモになりました。
どこかで検証もまたやりたい。
英単語補足
原文の英語について調べてみた。
①TL;DR
TL;DRって原文であるけどこれ何?と思って調べてみました。
"Too Long; Didn't Read" の略らしく、直訳すると「長すぎて読めなかった」みたいな意味。
これでなぜか要約という意味らしい...こういった使い方は日本語にはあまり無い気がする。
②over time
which showed great performance improvements over time. という部分があるがどうもover timeにピンと来なかったので調べてみました。
「時間が経つにつれて大幅なパフォーマンス改善」ということらしい、意味は言われてみればまあ確かにそうかという感じ。as とかがついていないのでピンと来なかったがover time で副詞句でshowedにかかる。
③optimization
最適化。忘れがち。
④aggregate's
集約処理の という意味SQLの集約関数の処理などで使われる単語?aggregateはなかなかパッと意味が出てこないのでこれで覚えられそう。
⑤Accumulate
蓄積する バッファ（メモリ内）に一時的に保存する...か 正直単語帳などで覚えようとするとイメージが沸かない単語が多いが、めちゃくちゃよい
⑥Fanout
1つの入力が複数の出力に広がる（分散する）...今回だとセグメントツリーをベクトル単位で並列処理し、処理のスループットを向上?
扇（fan）のように、1箇所から放射状に広がる
Discussion