WITH RECURSIVE を利用して特定のグループ内の最大値を持つ行を射影する

## 説明用のテーブル構成

記事中のSQLステートメントでは以下のようなテーブルを操作する事を前提に書かれています。

* `product`テーブルは商品の情報を管理する
* `product_sold`は商品が売れた日付とその日に売れた数を記録している。

```sql
CREATE TABLE product (
  product_id SERIAL PRIMARY KEY,
  name TEXT NOT NULL
);

CREATE TABLE product_sold(
  product_sold_id SERIAL PRIMARY KEY,
  product_id INTEGER NOT NULL,
  sold_date DATE NOT NULL, --- 商品が売れた年月日
  number_sold INTEGER NOT NULL, --- この日に販売された商品の数。
  FOREIGN KEY (product_id) REFERENCES product (product_id) 
  	DEFERRABLE INITIALLY DEFERRED
);
```

[DB Fiddle](https://www.db-fiddle.com/f/nfdjS869yAGDbwXa3rLk1G/1)

実際はもっと業務に込み入ったテーブルとカラムで構成されていましたが、説明用に簡略化しています。

## 発端

商品画面の表示が遅いので調査と改善を保守作業で行うことになった。

いろいろと調べていくうちに、「画面から入力された検索条件」で表示された商品データの中から「選択された商品ごとに最も売れた日(`sold_date`)の行」だけを抽出するSQLステートメントの実行に時間がかかっていた。

時間がかかっていたのは以下のようなSQL。

```sql
--- 読みやすさのために WITH を使用していますが、実際はサブクエリだったはず。
WITH __sold_product_cte AS (
    SELECT product.product_id,
            product_sold.product_sold_id,
            --- `product_id`ごとに`ORDER BY product_sold.number_sold`して
            --- 行番号を割り振る。
            ROW_NUMBER() OVER (
                PARTITION BY product.product_id
                --- number_sold でソート。
                --- number_sold が同じだった場合は product_id が新しいものを優先。
                --- 実際のテーブルは優先順位はもっと工夫されていたけど、ここでは仮に product_id にする。
                ORDER BY product_sold.number_sold DESC NULLS LAST,
                         product_sold.product_id DESC NULLS LAST
            ) AS sold_count_rank_no
    FROM product
    INNER JOIN product_sold
        ON product_sold.product_id = product.product_id
        --- `$1`には「選択された商品」(`product.product_id`)の配列がバインドされるものとしてみてください。
        AND product.product_id = ANY($1)
    --- 本来はここに「画面から入力された検索条件」に対応する複雑な条件が存在していた。
    WHERE ...
)
SELECT product.product_id,
       product.name,
       product_sold.sold_date,
       product_sold.number_sold
FROM product_sold
--- 売り上げが最も多い行は`__sold_product_cte.sold_count_rank_no = 1`になることを利用して
--- 商品ごとの詳細な情報を射影する。
INNER JOIN __sold_product_cte
    ON __sold_product_cte.product_sold_id = product_sold.product_sold_id
    AND __sold_product_cte.sold_count_rank_no = 1;
```

このSQLステートメントを実行すると「選択された商品ごとに最も売れた日(`sold_date`)の行」は確かに取得できていた([DB Fiddle](https://www.db-fiddle.com/f/dz2ZxiHh8vEvYGYVhRTQnq/1))。

しかし、`EXPLAIN ANALYZE`を行うと‘`__sold_product_cte`に対応する処理のために十数MBのワーキングメモリが必要になっていた。

ワーキングメモリの倍以上のメモリを必要としていたため、
ソート処理や結果データがディスク書き出しになっているせいで遅くなっているようだった。

データ量が少ない頃はワーキングメモリが足りていたが、増えてくるにつれてワーキングメモリ不足になったもの。

## 対処

ワーキングメモリを増やせば画面表示の遅延は改善されるはず、
しかし、保守の範囲でワーキングメモリを増やしたりは出来ないということだった。

サーバーのメモリ消費量などが大きく変わるので、影響範囲が大きすぎるからだ。
とはいえ、画面表示が段々と遅くなっていくのも分かっているので対処は必要ということになった。

次に思い浮かぶ手段は「選択された商品ごとに最も売れた日(`sold_date`)の行」ごとにSQLを用意して
各SQLを`UNION`する大規模なSQLを構築する事だった。
SQLを分割して実行すれば`ROW_NUMBER`も必要なくなるし、メモリ消費量も減らせそうだ。

しかし、「画面から入力された検索条件」でバインドされるパラメーター数が多く
「選択された商品ごとに最も売れた日(`sold_date`)の行」の数だけSQLを分割すると
PostgreSQLのバインド可能なパラメーター数の上限32,767を超えることが判明して断念した。

パラメーター数の上限は https://qiita.com/tt4q/items/d0bd47be5a48108d54e3 を参照。

そのほか、いろいろ考えたが最終的に`WITH (RECURSIVE)`で「ワーキングメモリ消費量の改善」をしたうえで、
「SQLにバインドするパラメーターを大幅に増やさず」に、目的を達成できた([DB Fiddle](https://www.db-fiddle.com/f/mVDc6naWE9faDxHo9c8J5E/1)。

最終的に生成されたSQLは以下のような形になった。

```sql
--- 最初に「選択された商品」を抽出する __sold_product_cte を用意する。
WITH RECURSIVE __sold_product_cte AS (
    SELECT product.product_id,
            product_sold.product_sold_id,
            product_sold.number_sold
    FROM product
    INNER JOIN product_sold
        ON product_sold.product_id = product.product_id
    WHERE product.product_id = ANY($1)
         --- 「画面から入力された検索条件」に対応するそのほかの条件。
          ...
)
--- __recent_sold_recursive_cte は product.product_id ごとの
--- 最も商品が売れた日の行を取り出す再帰的問い合わせ。
, __recent_sold_recursive_cte (
    --- product_sold_id は再帰的問い合わせを抜けた後で関連するデータ結合するために射影する。
    product_sold_id,
    --- __product_id_array と __product_id_array_length は
    --- 再帰的問い合わせを行うための product_id の配列 と 長さ。
    --- 再帰制御の制御のために射影する。
    __product_id_array,
    __product_id_array_length
) AS (
    (
        --- 再帰的問い合わせの最初のSQL。
        --- `__product_id_array_cte.product_id_array[2:]` で
        --- 配列の先頭要素を除外した新しい配列が射影される（`(ARRAY[1,2,3])[2:]`構文）。
        --- `(ARRAY_LENGTH(__product_id_array_cte.product_id_array, 1) - 1)` で
        --- 次の再起処理に渡す配列の長さ。
        SELECT __sold_product_cte.product_sold_id,
                __product_id_array_cte.product_id_array[2:],
                (ARRAY_LENGTH(__product_id_array_cte.product_id_array, 1) - 1)
        --- `$1` にバインドされる配列を `VALUES` によって行セットに変換、
        --- `__product_id_array_cte` と名前を付けて参照可能にしている。
        FROM (VALUES ($1)) AS __product_id_array_cte (product_id_array)
        --- NOTE: 再帰的福問い合わせは直前の射影結果を利用して次の問い合わせを実施する。
        ---  つまり、一度でも射影結果が0件の問い合わせがあるとその後の問い合わせで
        ---  結果行が存在したとしても、そこで再起処理が終了してしまう。
        ---  `__product_id_array_cte`が１行射影されるため、
        ---  射影結果0件を避ける目的で`LEFT OUTER JOIN` で結合する。
        ---  結合結果が必ず0件にならないのであれば`INNER JOIN`でよい。
        LEFT OUTER JOIN __sold_product_cte
        --- `__sold_product_cte` から商品主キー配列の先頭の`product_id`と一致する行を抽出。
            ON __sold_product_cte.product_id = __product_id_array_cte.product_id_array[1]
        --- ORDER BY と LIMIT 1 で商品が最も売れた日の行だけを射影対象にする。
        ORDER BY __sold_product_cte.number_sold DESC NULLS LAST,
                __sold_product_cte.product_id DESC NULLS LAST
        LIMIT 1
    )
    UNION ALL
    (
        --- 再帰問い合わせの2回目以降のSQL。最初の再帰問い合わせとほとんど同じ内容だが、
        --- 直前の射影結果である`__recent_sold_recursive_cte`を参照している。
        SELECT __sold_product_cte.product_sold_id,
                __recent_sold_recursive_cte.__product_id_array[2:],
                (__recent_sold_recursive_cte.__product_id_array_length - 1)
        FROM __recent_sold_recursive_cte
        LEFT OUTER JOIN __sold_product_cte
            ON __sold_product_cte.product_id = __recent_sold_recursive_cte.__product_id_array[1]
        --- __recent_sold_recursive_cte.__product_id_array_length > 0 は
        --- 再帰問い合わせの無限ループ防止。
        WHERE __recent_sold_recursive_cte.__product_id_array_length > 0
        ORDER BY __sold_product_cte.number_sold DESC NULLS LAST,
                __sold_product_cte.product_id DESC NULLS LAST
        LIMIT 1
    )
)
--- WITH RECURSIVE で射影した主キーで`product_sold`テーブルと結合して、
--- 画面に表示する必要があるカラムを持つテーブルを結合する。
SELECT product.product_id,
       product.name,
       product_sold.sold_date,
       product_sold.number_sold
FROM product
INNER JOIN product_sold
    ON product_sold.product_id = product.product_id
INNER JOIN __recent_sold_recursive_cte
    ON __recent_sold_recursive_cte.product_sold_id = product_sold.product_sold_id
```

SQLステートメントが長くなってしまったが、
`WITH RECURSIVE`で再帰的問い合わせを行う際のループを
`$1`に指定された商品IDの配列で`for`文の様に制御しているというのを理解すればSQL全体を把握しやすくなる。

「特定のグループの中の最大値を持つ１行を取り出す」ようなパターンで、「特定のグループ」をSQL`Array`にできるのであれば
`WITH RECURSIVE`を利用すれば1回のSQL実行で実現できるのではないだろうか。

## 参考にしたもの

* https://qiita.com/Shoyu_N/items/f1786f99545fa5053b75
* https://qiita.com/anqooqie/items/fac5aeb74169f1634c87

## 余談

PostgreSQL 12で`WITH`のCTEが改善されたが、それ以前のバージョンではパフォーマンスに難があるらしい。

問題があった環境はPostgreSQL 12ではなかったので
今回のようなケースでは`WITH RECURSIVE`を使用したほうがWindow関数を使うより
ワーキングメモリの消費量は抑えられるはずだが、
データ量が増えた時のメモリ消費量や実行速度は監視などでメンテナンスし続けるべき。