10 分間コーディングで 30 分かかった SQL を読み下す

再帰 CTE の入門が済んだところで、10 分間コーディングで 30 分かかった・・・ - ぐるぐる〜を読んでみましょう！

読み方

上の CTE (Input) から下に向かって読んできます。

Input

Input は簡単。

Input(id, numPlayers, deck) AS (
  SELECT 1, 3, '123123123'
  UNION ALL SELECT 2, 4, '123123123'
  UNION ALL SELECT 3, 6, '012345012345012345'
  UNION ALL SELECT 4, 4, '111122223333'
  UNION ALL SELECT 5, 1, '012345012345012345'
  UNION ALL SELECT 6, 6, '01234'
  UNION ALL SELECT 7, 2, ''
  UNION ALL SELECT 8, 0, ''
  UNION ALL SELECT 9, 0, '123'
)

id がついているので、複数の入力を処理できるようになっている。

Cards

Cards は Input.deck で与えられた文字列を一文字毎の行に分割する CTE で、同時に各カードに連番を付けていく。

Cards(id, i, card, deck) AS (
  SELECT
      id
    , 0
    , LEFT(deck, 1)
    , SUBSTRING(deck, 2, LEN(deck))
  FROM
      Input
  WHERE
      deck <> ''
  UNION ALL
  SELECT
      id
    , i + 1
    , LEFT(deck, 1)
    , SUBSTRING(deck, 2, LEN(deck))
  FROM
      Cards
  WHERE
      deck <> ''
)

Cards は再帰 CTE になっていて、deck の先頭一文字を card とし、残りを次の deck として分割していき、deck が空になったら再帰を終了する。
終了条件を UNION ALL より上の SELECT にも記述しているため、deck がはじめから空の場合には結果は空となる。

どのように処理が行われるのかが分かりにくい場合は、CTE を SELECT してみるといい。

-- 略
, Deal(id, player, cards) AS (
    SELECT
        id
      , player
      , LEFT(cards, (SELECT MIN(LEN(cards)) FROM Deal_ C WHERE P.id = C.id))
    FROM
        Deal_ P
  )
--SELECT * FROM Deal ORDER BY id, player
SELECT * FROM Cards ORDER BY id, i

このように、元の SELECT をコメントアウトしておき、表示したい CTE の SELECT に置き換える。

Players

Players はプレイヤーの人数から、各プレイヤーを識別するための数値を 1 から連番で振っていく。

Players(id, player, n, total) AS (
  SELECT
      id
    , 1
    , numPlayers
    , numPlayers
  FROM
      Input
  WHERE
      numPlayers <> 0
  UNION ALL
  SELECT
      id
    , player + 1
    , n - 1
    , total
  FROM
      Players
  WHERE
      n <> 1
)

Players も Cards と同様、再帰 CTE となっている。
Cards の場合は文字列を先頭から取っていって縮めていったが、Players では n を減らしていく。
そして、n が 1 になった時点で再帰が終了する。
また、Input の numPlayers が 0 の場合は Players は空になる。

Cards の連番 (i) は 0 からはじまるのに、Players の連番 (player) は 1 からはじまている点に注意。
player の最大値は total、つまり Input.numPlayers と同じになり、Cards.i の最大値は Input.numPlayers - 1 と同じになる。
これはちょうど、Java 等の配列のサイズと添え字の関係と同じになっている。

DealSrc

DealSrc は Players と Cards を結合して、手札算出の元にする。

DealSrc(id, i, player, card, total) AS (
  SELECT
      Player.id
    , COALESCE(Card.i + 1, Player.player)
    , Player.player
    , COALESCE(Card.card, '')
    , Player.total
  FROM
      Players Player
        LEFT OUTER JOIN Cards Card ON
          Player.id = Card.id AND  Player.player = (Card.i % Player.total + 1)
)

DealSrc では再帰 CTE ではなく、通常の CTE となっている。
ただし、JOIN が少し複雑になっているので、少し詳しく見ていくことにする。

まずは Players と Cards を、Players を左側にして外部結合している。
結合条件の Player.id と Card.id が等しい部分はいいだろう。
問題は、Player.player = (Card.i % Player.total + 1) の部分だ。

Card.i は 0 からはじまる連番なので、Player.player と直接 = で結合することはできない (1 ずれる)。
そのため、+ 1 することが必要となる。
また、1 人のプレーヤーに 2 枚以上のカードを配る場合、Cards.i が Players.player を突き抜けてしまうので、プレーヤーの数で剰余を取っている。
total を Players に持たせずに、(SELECT MAX(player) FROM Players C WHERE Player.id = C.id) とすることもできるが、Players に持たせておくと読みやすくなる。

カードが足りずにプレーヤーに 1 枚も配れないような場合でも、プレイヤーの行は欲しいため、INNER JOIN ではなく LEFT OUTER JOIN にしている。

そして SELECT 句では、Cards 由来のカラムに COALESCE をかませることで NULL を回避している。

Concated

Concated は DealSrc の結果を id 毎、player 毎にカードを連結した文字列を生成する。

Concated(id, i, player, cards) AS (
  SELECT
      id
    , i
    , player
    , CAST(card AS varchar(max))
  FROM
      DealSrc
  WHERE
      i = 1
  UNION ALL
  SELECT
      Concated.id
    , Concated.i + Src.total
    , Concated.player
    , Concated.cards + Src.card
  FROM
      Concated
        INNER JOIN DealSrc Src ON Concated.id = Src.id
                                    AND Concated.player = Src.player
  WHERE
      Concated.i + Src.total = Src.i
)

Concated では再帰 CTE を使用して、文字列を連結している。
これまでに再帰 CTE は十分説明していると思うので、詳細は追わない。

一つだけ注意が必要なのは、再帰 CTE は処理の途中段階も保持しているということ。
これは重要なので、理解してから次に進むこと。
下の SQL を実行してみるのもいいだろう。

SELECT * FROM Concated ORDER BY id, i, player

Deal_

Deal_ は Concated から必要なものだけを取ってくる。

Deal_(id, player, cards) AS (
  SELECT
      id
    , player
    , cards
  FROM
      Concated P
  WHERE
      LEN(cards) = (SELECT MAX(LEN(cards)) FROM Concated C
                    WHERE P.id = C.id AND P.player = C.player)
)

Deal_ は再帰ではない普通の CTE で、Concated の中から、id と player が同じで cards が一番長い行のみを取ってくる。
上で言ったように、再帰 CTE は途中段階も保持しているため、結果のみを取り出す SQL も書く必要がある。

複数行を単一の行にまとめ上げるため、再帰 CTE (この例では Concated) と、必要な行のみを抽出する SQL (この例では Deal_) は、集約を行っているとも言える。
その最たる例が、上のエントリで紹介した総積を求める SQL だ。

また、必要な行のみを抽出する方法には他にもいくつも方法がある。
例えば、NOT EXISTS を使った方法、ALL を使った方法、TOP 1 と ORDER BY を使った方法等が考えられる。
さらに、cards の長さを取らずに、再帰 CTE 側で終了データに終了フラグを立てておき、抽出側は単純な WHERE 句にするといった方法もある。

Deal

Deal は、手札の長さを揃える。

Deal(id, player, cards) AS (
  SELECT
      id
    , player
    , LEFT(cards, (SELECT MIN(LEN(cards)) FROM Deal_ C WHERE P.id = C.id))
  FROM
      Deal_ P
)

Deal も再帰ではない普通の CTE で、Deal_ を元にして全プレーヤーの手札を一番少ないプレーヤーと同じになるように調整する。
これで、Deal を SELECT するだけで結果が取得できる。

全体

一応全体を載っけておきますね。

WITH
  Input(id, numPlayers, deck) AS (
    SELECT 1, 3, '123123123'
    UNION ALL SELECT 2, 4, '123123123'
    UNION ALL SELECT 3, 6, '012345012345012345'
    UNION ALL SELECT 4, 4, '111122223333'
    UNION ALL SELECT 5, 1, '012345012345012345'
    UNION ALL SELECT 6, 6, '01234'
    UNION ALL SELECT 7, 2, ''
    UNION ALL SELECT 8, 0, ''
    UNION ALL SELECT 9, 0, '123'
  )
, Cards(id, i, card, deck) AS (
    SELECT
        id
      , 0
      , LEFT(deck, 1)
      , SUBSTRING(deck, 2, LEN(deck))
    FROM
        Input
    WHERE
        deck <> ''
    UNION ALL
    SELECT
        id
      , i + 1
      , LEFT(deck, 1)
      , SUBSTRING(deck, 2, LEN(deck))
    FROM
        Cards
    WHERE
        deck <> ''
  )
, Players(id, player, n, total) AS (
    SELECT
        id
      , 1
      , numPlayers
      , numPlayers
    FROM
        Input
    WHERE
        numPlayers <> 0
    UNION ALL
    SELECT
        id
      , player + 1
      , n - 1
      , total
    FROM
        Players
    WHERE
        n <> 1
  )
, DealSrc(id, i, player, card, total) AS (
    SELECT
        Player.id
      , COALESCE(Card.i + 1, Player.player)
      , Player.player
      , COALESCE(Card.card, '')
      , Player.total
    FROM
        Players Player
          LEFT OUTER JOIN Cards Card ON
            Player.id = Card.id AND  Player.player = (Card.i % Player.total + 1)
  )
, Concated(id, i, player, cards) AS (
    SELECT
        id
      , i
      , player
      , CAST(card AS varchar(max))
    FROM
        DealSrc
    UNION ALL
    SELECT
        Concated.id
      , Concated.i + Src.total
      , Concated.player
      , Concated.cards + Src.card
    FROM
        Concated
          INNER JOIN DealSrc Src ON Concated.id = Src.id
                                      AND Concated.player = Src.player
    WHERE
        Concated.i + Src.total = Src.i
  )
, Deal_(id, player, cards) AS (
    SELECT
        id
      , player
      , cards
    FROM
        Concated P
    WHERE
        LEN(cards) = (SELECT MAX(LEN(cards)) FROM Concated C
                      WHERE P.id = C.id AND P.player = C.player)
  )
, Deal(id, player, cards) AS (
    SELECT
        id
      , player
      , LEFT(cards, (SELECT MIN(LEN(cards)) FROM Deal_ C WHERE P.id = C.id))
    FROM
        Deal_ P
  )
SELECT * FROM Deal ORDER BY id, player

もう読めるはず！