ORDER BY (SELECT NULL) ～レコード取得順序の考察～

## 前提
DB初学者、初心者で、レコードは登録された順序で取得される、と勘違いしている人がいる。恐らく、CSVファイル等の単純なファイルシステムから連想していると思われる。
実際のところ、DB の実データもファイルに格納されている。しかしCSVファイルのような単純なものではない。
まっさらな DB に複数レコードを追加し、取得すると、登録順に出力されることを観察できるかもしれないが、それは限られたケースであり必ずそうなることが保証されている話ではない。

- 集合論
そもそも、DB が管理しているデータ、概念で「順序」というものはない。それは DB は集合論を元にした実装だから。
集合の[ベン図](https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%B3%E5%9B%B3 "ベン図 - Wikipedia")を思い出して欲しい。グループに属する要素に「順序」という概念はない。
`SELECT`文で取得した結果セット（固い言葉では射影というのかな）に対してソートをかけ、順序付けするという操作はあるが、それはあくまでも射影に対する操作。データ自体が「順序」という属性を持っているのではない。

- 管理テーブル
`Oracle`なら`ROWID`があるよね、という話はある。他の DB でもそれに類した管理情報を持っているだろうが、ユーザがそれを参照可能な`Oracle`の仕様が特殊であり一般的にはブラックボックス。通常ユーザが知り得るものではない。

- 明示的に`ORDER BY`句を指定しない全件取得は DB上の順序そのままで取得されるのでは
確かにそれは DB上の順序を示唆しているが、実際問題としてどのように取得しているのかは分からないので断言はできない。

- [クラスター化インデックス](https://docs.microsoft.com/ja-jp/sql/relational-databases/indexes/clustered-and-nonclustered-indexes-described?view=sql-server-ver15 "クラスター化インデックスと非クラスター化インデックスの概念 - SQL Server _ Microsoft Docs")って物理的にも順番で格納される仕様じゃなかったっけ？
事実それは仕様として定義されている。そして、PK がクラスター化インデックスとして定義されているテーブルから全件取得するクエリの実行プランを確認すると、クラスター化インデックスを参照していることが分かる。
これはつまりクラスター化インデックスを辿ってレコードを取得していることを示唆していて、実際`ORDER BY`句を指定しなくても PK 順に取得されるという事象を観測することができる。
これは合理的な話だが、しかしそこまで仕様として定義されている訳ではないし、これもまた限定的な話でしかない。

等々、掘れば色々と出てくるが、結局はブラックボックス。公式にある通りの話。
[ORDER BY 句 (Transact-SQL)](https://docs.microsoft.com/ja-jp/sql/t-sql/queries/select-order-by-clause-transact-sql?view=sql-server-ver15 "ORDER BY 句 (Transact-SQL) - SQL Server _ Microsoft Docs")
> ORDER BY 句が指定されていない限り、結果セットとして返される行の順序は保証されません。

そもそもこれは標準SQL の仕様じゃないのかな。というか、前述、DB は集合、という基本を考えれば当然の話。だがしかし……。

## STRING_SPLIT の憂鬱
久しぶりに`STRING_SPLIT`関数の公式を確認したら、いつの間にか第三引数が追加されていびっくり。
[STRING_SPLIT (Transact-SQL)](https://docs.microsoft.com/ja-jp/sql/t-sql/functions/string-split-transact-sql?view=sql-server-ver15 "STRING_SPLIT (Transact-SQL) - SQL Server _ Microsoft Docs")
> 構文
syntaxsql
> 
> STRING_SPLIT ( string , separator [ , enable_ordinal ] )

`STRING_SPLIT`関数の追加は 2008 だったか。当初第三引数は無く、取得されるレコードの順序は保障されない旨の記述が公式にもあった記憶が。
その仕様を巡り公式フォーラムが紛糾した。そちらも今回確認したら消滅していたので Internet Archive から発掘。
[Add row position column to STRING_SPLIT](https://web.archive.org/web/20201022225332/https://feedback.azure.com/forums/908035-sql-server/suggestions/32902852-string-split-is-not-feature-complete "Add row position column to STRING_SPLIT – Customer Feedback for ACE Community Tooling")
> これは欠陥と見なされるべきであることに同意します。ドキュメントにrow_numberが順序を保証するという保証がない場合、すべての値を取得する以外の目的でこの関数を確実に使用することはできず、いつでもランダムな順序を返すことができると想定する必要があります。追加の列としてインデックスを含めるだけです！

そうそう、揉めたよねぇ。`STRING_SPLIT`関数を利用しつつ順序を保証するクエリを発表しているブログも見かけた。（URLは失念）

ユーザ側としては、順序通りに切り出されることを期待する。しかしそれが公式で保証されないと明言されたらねぇ。
カンマ区切り文字列とは要素をカンマで連結した集合であり、要素を分割した場合、順序は保障されない。明示的に`ORDER BY`句を指定しない限りは。
これは DB（集合論）の原則として正しい。

しかし一方、現実問題として`STRING_SPLIT`関数が文字列の順序通りに結果を返さないことなんてあるのかな？
```SQL
1> SELECT * FROM STRING_SPLIT('1,2,3,4,5,6,7,8,9,0', ',');
2> GO
value
-------------------
1
2
3
4
5
6
7
8
9
0

(10 行処理されました)
```
少なくとも自分はこの反証を確認できていない。もし知っている方がいたら教えて欲しい。

そもそも論として、順序が保証されない仕様は集合論の基本であるが、DB の仕様としては、内部的なレコードの取得順序が不定であることに由来する。
冒頭で内部の話に拘ったのはその為。

一方、`STRING_SPLIT`関数はメモリ上の操作で完結する関数。の筈。実は内部的には一時テーブルに格納して、とは現実問題として考えにくい。

そして関数として考えた場合、文字列の先頭から処理する、カンマ区切りで切り出していく、と予想される。
何故ならそれが一番合理的だから。
文字列とは文字の配列であり、文字列操作は配列操作と言える。そしてもし配列の末尾から処理するとなると、まず末尾のインデックスを取得しなければならない。一方先頭から処理するのであれば、決め打ちで 0番目の配列から、で済む。
その他、実は中間から操作しているとか、有り得ないしょ。
そして先頭からカンマ区切りで切り出した要素を逐次返却していく、と考えれば、やはり文字列の順序通りに返却される筈。
これは[決定的関数](https://docs.microsoft.com/ja-jp/sql/relational-databases/user-defined-functions/deterministic-and-nondeterministic-functions?view=sql-server-ver15 "決定的関数と非決定的関数 - SQL Server _ Microsoft Docs")や[決定的アルゴリズム](https://ja.wikipedia.org/wiki/%E6%B1%BA%E5%AE%9A%E7%9A%84%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0 "決定的アルゴリズム - Wikipedia")に類似する話じゃないのかな。

とはいえ、以上は推測の域を出ない話。`STRING_SPLIT`関数の内部仕様が公開されていない以上、ブラックボックス。
順序は保証されていない、それが仕様です、が正しいことは分かっているが、釈然としないんだよなぁ。

## 共通テーブル式の憂鬱
同様の疑問が共通テーブル式。よくある使用法の説明が以下。
```SQL
1> ;WITH CTE_Seq(seq) AS (
2>     SELECT 1
3>     UNION ALL
4>     SELECT seq + 1 FROM CTE_Seq WHERE seq < 10
5> )
6> SELECT seq FROM CTE_Seq
7> ;
8> GO
seq
-----------
          1
          2
          3
          4
          5
          6
          7
          8
          9
         10

(10 行処理されました)
```
順序通りの結果が得られる。というかこちらも順序通りにならない例を自分は見たことがない。二重ループとなると話は別だが。
```SQL
1> ;WITH CTE_Num1(num1) AS (
2>     SELECT 1
3>     UNION ALL
4>     SELECT num1 + 1 FROM CTE_Num1 WHERE num1 < 5
5> )
6> , CTE_Num2(num1, num2) AS (
7>     SELECT num1, 1 FROM CTE_Num1
8>     UNION ALL
9>     SELECT num1, num2 + 1 FROM CTE_Num2 WHERE num2 < 3
10> )
11> SELECT num1, num2 FROM CTE_Num2
12> ;
13> GO
num1        num2
----------- -----------
          1           1
          2           1
          3           1
          4           1
          5           1
          5           2
          5           3
          4           2
          4           3
          3           2
          3           3
          2           2
          2           3
          1           2
          1           3

(15 行処理されました)
```
ここではあくまでも二重ループ等ではない、最初の単純な共通テーブル式が前提。そしてそのクエリの実行プランは以下。
```SQL
StmtText
----------------------------------------------------------------------------------------
  |--Index Spool(WITH STACK)
       |--Concatenation
            |--Compute Scalar(DEFINE:([Expr1004]=(0)))
            |    |--Constant Scan(VALUES:(((1))))
            |--Assert(WHERE:(CASE WHEN [Expr1006]>(100) THEN (0) ELSE NULL END))
                 |--Nested Loops(Inner Join, OUTER REFERENCES:([Expr1006], [Recr1001]))
                      |--Compute Scalar(DEFINE:([Expr1006]=[Expr1005]+(1)))
                      |    |--Table Spool(WITH STACK)
                      |--Compute Scalar(DEFINE:([Expr1002]=[Recr1001]+(1)))
                           |--Filter(WHERE:(STARTUP EXPR([Recr1001]<(10))))
                                |--Constant Scan

(11 行処理されました)
```
うーん、よくわからん。
まず共通テーブル式の仕様を整理すると以下。

- `UNION ALL`で連結する前半のクエリは 1番目のレコードの定義
- `UNION ALL`で連結する後半のクエリは 2番目以降のレコードの定義
- 後半のクエリの列の値は、一つ前のレコードの値

つまり後半のクエリは、一つ前のレコードの値を使用してカレントのレコードを構成する、と考えると理解しやすい。
`num1 + 1`の`num1`は一つ前のレコードの値であり、それを加算しカレントのレコードの値としている。

二重ループとして挙げた例の`CTE_Num2`も基本的な考え方は同じ。
但し、この場合は前半のクエリが複数レコードとなるので、その全てのレコードに対して後半のクエリでレコードが生成される、樹形図のイメージ。

そして実行プラン。
まず`Compute Scalar(DEFINE:([Expr1006]=[Expr1005]+(1)))`でループ数カウントしている模様。
そして`CASE WHEN [Expr1006]>(100)`の`100`はシステムが保持しているループ上限値。

[WITH common_table_expression (Transact-SQL)](https://docs.microsoft.com/ja-jp/sql/t-sql/queries/with-common-table-expression-transact-sql?view=sql-server-ver15 "WITH common_table_expression (Transact-SQL) - SQL Server _ Microsoft Docs")
> または SELECT ステートメントの OPTION 句に 0 から 32,767 までの値を指定したりすることにより、特定のステートメントに許可される再帰レベルの数を制限します。 これにより、無限ループが作成される原因となったコードの問題が解決されるまで、ステートメントの実行を制御できます。 サーバー全体での既定値は `100` です。 0 を指定した場合、制限は適用されません。

実際、クエリに`OPTION (MAXRECURSION 0)`を追加すると、実行プランから`CASE WHEN [Expr1006]>(100)`の行が消えることが確認できる。

`Filter(WHERE:(STARTUP EXPR([Recr1001]<(10))))`はクエリの`WHERE seq < 10`に対応。
イマイチよく分からないのが`Compute Scalar(DEFINE:([Expr1002]=[Recr1001]+(1)))`。
クエリの`seq + 1`に対応していると思うが`[Expr1002]`がここでしか出現しない。`[Recr1001]=[Recr1001]+(1)`じゃないの？
と思ったりしたが、`[Recr1001]`が一つ前のレコードの値、`[Expr1002]`がカレントのレコードの値、ということなんでしょう。
`Nested Loops`はループだろうから、単純に`seq`を加算しながら`UNION ALL`で結合していく。つまり以下と同じ。
```SQL
1>             SELECT 1
2> UNION ALL   SELECT 2
3> UNION ALL   SELECT 3
4> UNION ALL   SELECT 4
5> UNION ALL   SELECT 5
6> UNION ALL   SELECT 6
7> UNION ALL   SELECT 7
8> UNION ALL   SELECT 8
9> UNION ALL   SELECT 9
10> UNION ALL   SELECT 10
11> ;
12> GO

-----------
          1
          2
          3
          4
          5
          6
          7
          8
          9
         10

(10 行処理されました)
```
ところがこの展開したクエリの実行プランを確認すると以下。
```SQL
StmtText
------------------------------------------------------------------------------------------
  |--Constant Scan(VALUES:(((1)),((2)),((3)),((4)),((5)),((6)),((7)),((8)),((9)),((10))))

(1 行処理されました)
```
うはは、`VALUES`コンストラクタに置き換えられるというね。そりゃそうだ。つまり以下と同じであり、実行プランも同じとなる。
```SQL
SELECT * FROM (
    VALUES (1), (2), (3), (4), (5), (6), (7), (8), (9), (10)
)t(val)
;
```
そして、`VALUES`コンストラクタが返すレコードも順序は保証されていないのかな？

## 結果セットに関する考察
色々と考えていくと、結局どうやってレコードをかき集め、どう返却しているか、ということに行き着く。そこでポイントとなるのが結果セット。
結果セットに焦点を当てて考察すると内部的に以下の処理が行われていると予想される。

#### 1. 取得したレコードを結果セットに詰めていく

#### 2. `ORDER BY`句が指定されている場合は結果セットに対してソートをかける

#### 3. 結果セットを返却

結果セットとは内部的には単なるメモリ上のバッファ、動的配列と考えられる。そして取得したレコードは結果セットの先頭から詰めていくと考えられる。
ただ、冒頭で挙げた例、PK がクラスター化インデックスとして定義されているテーブルからの全件取得でもない限り、レコードの取得順は予想できない。だから結果セットの順序も不定。
しかし`ORDER BY`句が指定されていれば、結果セットに対してソートがかかるので順序が保証される、となる。
そう考えると、`STRING_SPLIT`関数にしろ、単純な共通テーブル式にしろ、`VALUES`コンストラクタにしろ、予想される順序で結果セットに詰められていくと考えられるので、順序は保証されるのでは？

## ORDER BY (SELECT NULL)
つらつらと考えを巡らしていると思い出すのがハック的なクエリ`ORDER BY (SELECT NULL)`。
初見では？？？なクエリなので実際に動作を確認してみる。
まず用意したのが以下のクエリ。
```SQL
;WITH CTE_Rand(Val) AS (
                SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
)
SELECT Val FROM CTE_Rand
;
GO
```
実行結果は以下。
```SQL
Val
-----------
          0
          6
          4
          2
          0
          3
          7
          4
          2
          2

(10 行処理されました)
```
乱数を生成する`RAND`関数を利用しているので、0～9の範囲のランダムな値を持った10個のレコードを生成する。取得順が不定な実データをイメージしている。

次はこのクエリにウィンドウ関数（順位付け関数）`ROW_NUMBER`関数を組み込んでみる。
```SQL
;WITH CTE_Rand(Val) AS (
                SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
)
SELECT Val, ROW_NUMBER() OVER(ORDER BY Val) Seq FROM CTE_Rand
;
GO
```
実行結果は以下。
```SQL
Val         Seq
----------- --------------------
          0                    1
          0                    2
          1                    3
          3                    4
          5                    5
          6                    6
          6                    7
          7                    8
          8                    9
          8                   10

(10 行処理されました)
```
`ORDER BY`句での指定に従い Val列の昇順でソートされ、Seq列に連番が振られる。仕様通りの動き。

次は`ORDER BY (SELECT NULL)`を組み込んでみる。
```SQL
;WITH CTE_Rand(Val) AS (
                SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
    UNION ALL   SELECT CONVERT(INT, RAND() * 10)
)
SELECT Val, ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) Seq FROM CTE_Rand
;
GO
```
実行結果は以下。
```SQL
Val         Seq
----------- --------------------
          1                    1
          2                    2
          9                    3
          4                    4
          2                    5
          4                    6
          9                    7
          9                    8
          0                    9
          8                   10

(10 行処理されました)
```
`ORDER BY (SELECT NULL)`はソート指定としての意味を持たないので、ソート処理はスキップされ、結果セットに対してそのまま連番が振られることになる。
この挙動は公式サイトの説明とも符合する。

[OVER 句 (Transact-SQL)](https://docs.microsoft.com/ja-jp/sql/t-sql/queries/select-over-clause-transact-sql?view=sql-server-ver15 "OVER 句 (Transact-SQL) - SQL Server _ Microsoft Docs")
> 関連するウィンドウ関数が適用される前に、行セットのパーティション処理と並べ替えを決定します。 つまり、OVER 句はクエリ結果セット内のウィンドウまたはユーザー指定の行セットを定義します。 その後、ウィンドウ関数はウィンドウ内の各行の値を計算します。

要点は以下。

#### 1. ORDER BY句の指定に従い行セットの並べ替えを行う

#### 2. 次に各行の値を計算する（`ROW_NUMBER`関数の場合は連番を振る）

つまり、`ORDER BY (SELECT NULL)`が指定された場合、上記 1. はスキップされ、2. だけが行われることになる。
そもそもウィンドウ関数は行セット内のレコードの順序に依存する。`PostgreSQL`等、ソート順の指定、`ORDER BY`句を省略できる仕様のものもあるが、`SQL Server`ではその点が厳密で省略不可の仕様となっていて、ウィンドウ関数を見たら`ORDER BY`句と思えという格言もある（嘘）。
```SQL
1> SELECT ROW_NUMBER() OVER();
2> GO
メッセージ 4112、レベル 15、状態 1、サーバー *******-*******、行 1
関数 'ROW_NUMBER' には ORDER BY 句を伴う OVER 句が必要です。
```
しかし一方、[過去投稿](https://qiita.com/god19/items/b4c1239e4b1b89469342 "【SQL Server】ソート順の昇順／降順を動的に切り替えるクエリ【ORDER BY句】 - Qiita")にもある通り、`ORDER BY`句の仕様は案外フリーダムで意味を成さない記述が文法として許されている。
`ORDER BY (SELECT NULL)`も文法エラーにはならないが、意味も成さないクエリなので結果として無視される。（実行プランに含まれない）
さる高貴な夫人も言っている。「`ORDER BY`句が省略できないのであれば意味の無い`ORDER BY`句を指定すればいいじゃない」

冗談はさておき真面目な話、このハック的テクニックは知る人ぞ知るクエリで一部では有名。その名を冠したドメイン、サイトも存在する。（それはそれで凄いのだけど）
[ORDER BY (SELECT NULL)](https://orderbyselectnull.com/ "ORDER BY (SELECT NULL)")
2019年5月9日が最後のポストのようで現在は更新されていないのが残念。

このテクニックを`STRING_SPLIT`に組み合わせたクエリが以下。
```SQL
1> SELECT value, ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) Seq FROM STRING_SPLIT('1,2,3,4,5,6,7,8,9,0', ',');
2> GO
value               Seq
------------------- --------------------
1                                      1
2                                      2
3                                      3
4                                      4
5                                      5
6                                      6
7                                      7
8                                      8
9                                      9
0                                     10

(10 行処理されました)
```
`STRING_SPLIT`関数が生成する結果セットに対して連番を振ることができる。`IDENTITY`プロパティ列をソフト的に再現しているとも言える。

とはいえこのテクニックは、公式の仕様として定められているものではない、のも事実。
Micrsoft公式「Querying Microsoft SQL Server 2012」では、明示化するという意味での有効なテクニックとして紹介されているという例は存在するらしいが。
[sql server - What does _ORDER BY (SELECT NULL)_ mean](https://stackoverflow.com/questions/10066819/what-does-order-by-select-null-mean "sql server - What does _ORDER BY (SELECT NULL)_ mean_ - Stack Overflow")
> It can also be used as a statement of intent when it's not actually required. For example, in Micrsoft's training kit book "Querying Microsoft SQL Server 2012", they advise adding it to a valid query as, "...if you are really after three arbitrary rows, it might be a good idea to add an ORDER BY clause with the expression (SELECT NULL) to let people know that your choice is intentional and not an oversight." – Matt Gibson Sep 28, 2015 at 13:00

杓子定規に「それは公式の仕様として定義されていない」と弾くのは簡単であり、特に業務の現場ではその判断が重要であることも分かる。（その「現場」で行われているのは深い思慮を持ち合わせない人々による既存ソースのコピペ、再生産というに非頭脳的な作業だったりすることも現実だったりするが）
考えれば考える程、匙加減が難しいテーマだったりする。

## 最後に余談（本文も余談だらけだが）
しかし、こうした仕様の隙間をついたテクニックは技術的にも興味深いテーマではある。
それで思い出すのが`SELECT COUNT(*);`問題。
`COUNT`関数とは説明するまでもなく、`FROM`句で指定されたテーブル（結果セット）の件数を返す関数。
しかし一方`SQL Server`は`Oracle`等と違い、`FROM`句の省略が文法として許されている。
その結果、`SELECT COUNT(*);`という矛盾したクエリが成立してしまう。これが何を返すか、あなたは答えることができますか？

## 関連投稿
[【SQL Server】ソート順の昇順／降順を動的に切り替えるクエリ【ORDER BY句】 - Qiita](https://qiita.com/god19/items/b4c1239e4b1b89469342 "【SQL Server】ソート順の昇順／降順を動的に切り替えるクエリ【ORDER BY句】 - Qiita")
[SQL Server SELECT COUNT(_);問題 - Qiita](https://qiita.com/god19/items/643baaf99a51623a7ab4 "SQL Server SELECT COUNT(_);問題 - Qiita")