ウィンドウ関数の実行内部とフレーム計算

ウィンドウ関数は「畳まない集約」である

SUM(...) OVER (...) のようなウィンドウ関数は、集約に似ていながら決定的に違う性質を持ちます。GROUP BY がグループを1行へ畳むのに対し、ウィンドウ関数は入力の行数をそのまま保ったまま、各行に「その行から見た集約値」を付け足します。この「行を消さずに各行ごとへ集約を配る」という要求が、実行エンジンに特有の物理戦略を強います。本稿は PARTITION BY / ORDER BY / フレーム指定がどう物理実行へ落ち、累積・スライディングをどう増分計算し、ソートをどう共有して速くするかを原理から解説します。

論理的には、各出力行 i に対して「フレーム」と呼ばれる行範囲 frame(i) が定まり、関数はその範囲に適用されます。素朴に書けば各行ごとにフレームを舐め直す O(N^2) ですが、実エンジンはこれを増分計算で O(N) 付近へ落とします。その鍵が、パーティション分割と整列、そしてフレームの単調性です。

三層構造：パーティション・整列・フレーム

ウィンドウ指定 OVER (PARTITION BY p ORDER BY o frame_clause) は、独立した三つの層に分解できます。

• PARTITION BY: 行を p の値ごとに互いに独立なパーティションへ分ける。パーティション間に計算依存はなく、各パーティションは完全に分離して処理できる。GROUP BY と同じ分割だが、畳まずに保持する点が違う。
• ORDER BY: 各パーティション内の行に順序を与える。ROW_NUMBER や LAG のような位置依存関数、および RANGE/ROWS フレームの「前／後」はこの順序が前提。
• フレーム指定: 整列済みパーティション内で、現在行を基準にどの行範囲を集約対象とするかを定める。ROWS BETWEEN ... AND ... は物理的な行数で、RANGE BETWEEN ... AND ... は順序キーの値で範囲を切る。

物理プランの基本形は、この三層をそのまま反映して Sort（p, o で整列）→ WindowAgg（パーティション境界を検出しフレーム計算） の二段になります。

-- 物理プランの基本形
WindowAgg                       -- パーティション境界を検出し各行へ関数適用
  └─ Sort (PARTITION BY 列, ORDER BY 列)   -- p で寄せ、その中で o に整列
       └─ Scan / 下位プラン

WindowAgg は整列済み入力を1パスで流し、p の値が変わった点をパーティション境界として検出します。境界をまたいで集約状態を持ち越さないことが正しさの条件で、境界で running 状態をリセットします。

フレームの種類：ROWS と RANGE の決定的な違い

フレームは「現在行から見て集約に含める行範囲」です。指定の二大様式が ROWS と RANGE で、ピーク（同順位行）の扱いが本質的に異なります。

• ROWS BETWEEN a PRECEDING AND b FOLLOWING: 物理的な行数でフレーム端を決める。現在行の前 a 行・後 b 行という、順序キーの値に依存しない固定幅。
• RANGE BETWEEN a PRECEDING AND b FOLLOWING: 順序キーの値でフレーム端を決める。a PRECEDING は「現在行のキー値マイナス a 以上」の行すべてを含むため、同じキー値の行（ピア）は一括で入る。

この差が顕著に出るのが RANGE のデフォルト、すなわち RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW です。ここで CURRENT ROW は「現在行のキー値と等しい行すべて（ピア群）の末尾まで」を意味し、同順位の行は全員が同じ累積値を共有します。ROWS で同じ書き方をすると、ピアを区別して1行ずつ進むため値が変わります。

-- 同じ ORDER BY o でもフレーム様式で結果が変わる
ROWS  UNBOUNDED PRECEDING AND CURRENT ROW : 物理行で1行ずつ累積（ピアを区別）
RANGE UNBOUNDED PRECEDING AND CURRENT ROW : ピア群末尾まで累積（同値は同じ値）

増分計算：累積とスライディングをどう O(N) で回すか

各行でフレームを舐め直せば O(N^2) ですが、フレームには単調性があります。ORDER 整列済みなら、行を1つ進めるとフレームの両端も前方へしか動きません。これを使うと、前の行のフレーム状態から差分だけ更新できます。

累積（UNBOUNDED PRECEDING AND CURRENT ROW）は最も単純で、入ってくる行を集約状態へ足し込むだけです。フレーム左端は固定なので「引く」操作が要らず、純粋な running 集約になります。

-- 累積 SUM（フレーム左端は固定、入る行を足すだけ）
state = 初期値(0)
for row in partition (o 順):
    state += row.val          -- 右端が進む：1行を取り込む
    出力[row] = state         -- ROWS なら毎行、RANGE ならピア末尾で確定

固定幅のスライディングウィンドウ（例 ROWS BETWEEN 3 PRECEDING AND CURRENT ROW）は、右端が入るたびに左端から出る行を引くことで一定状態を保ちます。SUM・COUNT・AVG は加算の逆である減算で「出る行」を打ち消せるため、ウィンドウ幅に依存しない O(1) 更新で回せます。

-- スライディング SUM（出る行を引き、入る行を足す：O(1)/行）
for row in partition:
    state += 入る行.val       -- 右端を1つ進める
    if 左端が範囲外:
        state -= 出る行.val   -- 左端を1つ進める（逆操作で打ち消す）
    出力[row] = state

問題は 逆操作を持たない集約です。MAX / MIN は、現在の最大値が「出ていく行」だったとき、残りからの最大を引き算では復元できません。エンジンはこれを、フレーム内の候補を保つ**単調デック（monotonic deque）で O(1) 償却に保つか、状態を保持できない実装ではフレーム再走査（O(幅)）**にフォールバックします。DISTINCT を伴う集約や中央値系も逆操作不可で、コストが跳ねやすい領域です。

位置依存関数とピア検出

ROW_NUMBER / RANK / DENSE_RANK / LAG / LEAD / NTILE は集約ではなく位置（順序）に依存する関数で、フレームではなく ORDER の順序そのものを使います。整列済み入力を流しながら、行カウンタやピア境界で値を決めます。

• ROW_NUMBER: 行ごとに +1。ピアを区別する。
• RANK: 直前のピア群の行数ぶん飛ばす（同順位は同じ値、次は飛ぶ）。
• DENSE_RANK: ピア群を1つずつ詰める（飛ばさない）。
• LAG(x, k) / LEAD(x, k): 整列順で k 行前／後の値を引く。

これらの正しさはピア（順序キーが等しい行群）の検出にかかっています。WindowAgg は ORDER キーの値が変わった点をピア境界として捉え、RANK 系や RANGE フレームの確定タイミングに使います。だから ORDER の整列はフレーム計算だけでなくランク付けの前提でもあります。

ソート共有：複数ウィンドウを1回の整列でさばく

ウィンドウクエリが重くなる最大の要因はソートです。WindowAgg 自体は整列済み入力に対し基本1パス O(N) ですが、その前段のソートは O(N log N) で、メモリを超えれば外部ソートのスピルが走ります。だから最適化の主戦場は「ソートを何回やるか」です。

鍵は、複数のウィンドウ関数が同じ PARTITION BY と ORDER BY を共有するなら、ソートは1回でよい点です。同じ並びの上に複数の WindowAgg を積み重ね（あるいは1つの WindowAgg 内で複数関数を評価し）、整列を共有できます。

-- 同じ OVER を共有：ソート1回で2関数を評価
SUM(x) OVER (PARTITION BY p ORDER BY o)
ROW_NUMBER() OVER (PARTITION BY p ORDER BY o)
   → Sort(p,o) 1回 → WindowAgg で両方を一緒に計算

逆に、並び順の異なるウィンドウが混在すると、エンジンはウィンドウごとに別のソートを入れざるを得ません。OVER (ORDER BY a) と OVER (ORDER BY b) が同一クエリにあれば、最低でも2回ソートが走ります。オプティマイザはソート回数が減るよう WindowAgg の評価順を並べ替えますが、根本的に並びが両立しなければソートは増えます。

実行計画の読み方とチューニング

PostgreSQL の EXPLAIN ANALYZE では、WindowAgg ノードと、その下の Sort ノードに Sort Method（quicksort＝in-memory、external merge＝スピル）が出ます。WindowAgg が複数積まれていれば、それは並びの異なるウィンドウを別々に処理している合図です。チューニングの着眼点は次の通りです。

• Sort の数: WindowAgg 直下の Sort を数える。同じ p, o に揃えられないか、評価順の見直しで共有できないかを検討する。
• Sort Method: external merge が出たらスピル。work_mem を増やして in-memory に収まれば桁で速くなることがあるが、同時実行時のメモリ枯渇に注意。
• インデックス順スキャン: ウィンドウの ORDER BY に一致するインデックスがあれば Sort ごと消える。WindowAgg が Index Scan に直結していれば理想形。
• フレームと集約の相性: 非可逆集約（MAX/MIN/DISTINCT 系）の固定幅スライディングは幅依存コストが出やすい。可逆集約への置き換えやフレーム様式の見直しを検討する。

ウィンドウ関数は論理的にはベクトル化実行のようなバッチ処理とも組み合わさり、整列済みパーティションをバッチで流して関数適用を償却するエンジンもあります。実行モデル全体の位置づけはクエリ実行モデル、ソートを消す計画選択はオプティマイザの内部もあわせて参照してください。

まとめ

• ウィンドウ関数は GROUP BY と違い行を畳まず、各行へ「その行から見た集約・順位」を配る。物理形は Sort → WindowAgg の二段で、ソートが PARTITION（寄せ）と ORDER（整列）の二層を一挙に満たす。
• フレームは集約対象の行範囲。ROWS は物理行数、RANGE は順序キーの値で端を切り、RANGE はピア（同順位）を一括で含むため同値行が同じ値になる。ORDER 付きでフレーム省略時の既定は RANGE UNBOUNDED PRECEDING AND CURRENT ROW。
• 累積は左端固定で足すだけ O(1)。固定幅スライディングは可逆集約（SUM/COUNT/AVG）なら出入りの差分で O(1)、非可逆（MAX/MIN/DISTINCT 系）は単調デックや再走査で幅依存コストが出る。
• RANK/LAG 等の位置依存関数は順序とピア境界だけで決まり、フレームを使わない。
• 重いウィンドウクエリの主因は並びの異なる OVER ごとのソート。PARTITION/ORDER を揃えてソートを共有する、インデックス順でソートを消す、work_mem を見直してスピルを避ける、が基本対策。実行計画では WindowAgg 直下の Sort の数と Sort Method を見る。