SQLにおける結果の順序について

# はじめに

## 前提

この記事でSQLという場合、特定のデータベース製品で動作するSQLのことを指し示してはいません。
しかしながら、記事を書くにあたってはPostgreSQLやApache Flinkのドキュメントを参考にしています。

* [PostgreSQL: Documentation](https://www.postgresql.org/docs/)
* [PostgreSQL 13.1 Documentation](https://www.postgresql.org/files/documentation/pdf/13/postgresql-13-A4.pdf)
* [Apache Flink 1\.11 Documentation: Detecting Patterns in Tables](https://ci.apache.org/projects/flink/flink-docs-stable/dev/table/streaming/match_recognize.html)

## 背景

SQLでは、**こういうデータがほしいというデータに関する性質**を書けば、あとはRDBMSやSQLエンジンがよしなにしてデータを取ってくれます。
このような言語は、宣言型言語に位置付けられます。
宣言型言語はあまり多くなく、この観点からSQLは一般的なプログラミング言語とは趣が異なる言語になっています。

一方、SQLはデータの扱い方(まとめ方)も、一般的なプログラミング言語とは異なります。
この記事では、SQLのデータのまとめ方について説明し、うまくやっていくにはどうすればいいかについて説明します。

## 言いたいこと

SQL(SELECT文)は、明示しない限りは**結果の順序は不定です**。
この性質のおかげで、サブクエリやジョインを、RDBMSやSQLエンジンの裁量で、処理を並列化したり効率化できます。

サブクエリでは、順序が指定できないか、特殊な条件を満たしている場合しか順序が指定できない製品が多いです。
そのため例えば、サブクエリを使っていったん集計してから、それぞれのグループの上位3件に対して処理をしたい場合に、クエリを分けたり工夫した書き方をする必要があります。

SQLには、そんなときのための**順序を扱う便利な関数や機能がある**ので、**ガンガン使っていきましょう**。


# 順序が不定とはどういうことか

## 例1

まず、SQLでは、明示しない限りは結果の順序が不定であるという例を示します。

こんなテーブル(T)があるとします。

|X|Y|
|---|---|
|1|1|
|1|2|
|1|3|
|2|1|
|2|2|
|2|3|


例えば下記のSQLであれば、**Tテーブル**から、**X=1**であるような**X列**と**Y列**を、**Y列の降順**に取って来いという命令になっています。

```sql
SELECT X, Y
FROM T
WHERE X = 1
ORDER BY Y DESC
```

実行結果は、下記のようになるはずです。

|X|Y|
|---|---|
|1|3|
|1|2|
|1|1|

さて、上記のSQLから、**ORDER BY Y DESC**を取り除いてみましょう。

```sql
SELECT X, Y
FROM T
WHERE X = 1
```

このSQLの実行結果はどうなるでしょうか？
単純に考えれば、元のテーブルの順序通りで、下記のようになるでしょう。

|X|Y|
|---|---|
|1|1|
|1|2|
|1|3|

でも実は、下記のいずれの場合も正解のはずです。
なぜなら、SQLで順序を指定していないのですから。

|X|Y|
|---|---|
|1|1|
|1|3|
|1|2|

|X|Y|
|---|---|
|1|2|
|1|1|
|1|3|

|X|Y|
|---|---|
|1|3|
|1|2|
|1|1|

このように、**ORDER BYを指定しなかった場合**、SQLの立場としては**結果がどんな順序なのかは不定**です。

## 寄り道1

不定とはいえ、RDBMSやSQLエンジンによっては、格納順だったり、インデクスがある場合などの条件付きで順序が規定されていることがあります。
しかしながら、もう一度言いますが、SQLの立場としては結果がどんな順序なのか不定です。
なぜ不定なのかを、少しだけ説明します。

SQLでは扱うデータの集合は、テーブルと呼ばれるタプルのmultiset(多重集合/重複あり集合)です。

タプルとは、行のことです。
例えばPythonでは、タプルを`(1, 1)`のように表しますが、これは表の行と同一視できますよね。

<table>
<tbody>
<td>1</td><td>1</td>
</tbody>
</table>

multisetとは、重複を許す集合とも捉えられますし、順序がないリスト(配列)とも捉えられます。
例えばPythonでは、`{(1, 1), (1, 1)}`はあり得ません。集合は重複を許さないので、`{(1, 1)}`になってしまいます。
また、`[(1, 1), (1, 2)]`と`[(1, 2), (1, 1)]`は違うリストです。
一方multisetでは、`{(1, 1), (1, 1)}`はあり得ますし、`{(1, 1), (1, 2)}`と`{(1, 2), (1, 1)}`は同じmultisetです。

multisetでの説明をテーブルで表現するとこうなります。
SQLでは下記のテーブルはあり得ます。

|X|Y|
|---|---|
|1|1|
|1|1|

SQLでは下記の二つのテーブルは同一視します。

|X|Y|
|---|---|
|1|1|
|1|2|

|X|Y|
|---|---|
|1|2|
|1|1|

テーブルに対してこの性質を要請するのが正しいかはここでは議論しません。
SQLでは多くの場合、テーブルはmultisetであると定義しています。

## 例2

次に、サブクエリ内で**ORDER BY**を指定した例を示します。

```sql
SELECT X, Y
FROM (
    SELECT X, Y
    FROM T
    WHERE X = 1
    ORDER BY Y ASC
)
ORDER BY Y DESC
```

サブクエリ内で昇順に、外側のクエリで降順に並べるように指定しているので下記の結果となります。

|X|Y|
|---|---|
|1|3|
|1|2|
|1|1|

RDBMSやSQLエンジンによっては、そもそもこのSQLが実行できないこともあります。

昇順に並び替えた後に降順に並び替えるのは無駄なので、RDBMSやSQLエンジンによっては内側のORDER BYを内部で取り除いてくれているかもしれません。
すなわち、

```sql
SELECT X, Y
FROM (
    SELECT X, Y
    FROM T
    WHERE X = 1
)
ORDER BY Y DESC
```

と同等の処理に変換してくれたり、さらには

```sql
SELECT X, Y
FROM T
WHERE X = 1
ORDER BY Y DESC
```

と同等の処理に変換してくれるかもしれません。

## 寄り道2

外側の**ORDER BY**を取り除いてみましょう。

```sql
SELECT X, Y
FROM (
    SELECT X, Y
    FROM T
    WHERE X = 1
    ORDER BY Y ASC
)
```

この場合の実行結果はどうなるでしょうか。
単純に考えると、Y列に対して昇順になると思いませんか。
私は最初そう思っていました。

|X|Y|
|---|---|
|1|1|
|1|2|
|1|3|

ですが、この場合も結果の順序は不定で、以下のいずれでも正解となります。

|X|Y|
|---|---|
|1|1|
|1|3|
|1|2|

|X|Y|
|---|---|
|1|2|
|1|1|
|1|3|

|X|Y|
|---|---|
|1|3|
|1|2|
|1|1|

外側のクエリで順序を指定していないので当然と言えば当然ですね。

ほとんどの場合、内側のクエリで並び替えたとおりに出てくるはずですが、確実にそうなるとは限りません。
極端な場合として、外側のクエリに対して「データ処理スレッドが3スレッドあり、それぞれが1行ずつ読み込んで値を返す」という実装だった場合、実行結果の並び順は実行するたびに変わる可能性があります。

ここでは、極端な例として複数スレッドで並列処理する話を持ち出しました。
こんなことができるのも、SQLがmultisetを使っているおかげです。
SQLでは、データの集まりに順序を前提としていないため、順序を前提とした処理も基本的にはありません<sup>\*1</sup>。
ということは、**RDBMSやSQLエンジンはどんな順序で計算してもいい**ということになり、**並列化や効率化がしやすくなります**。

> *\*1: この後、順序を扱う処理を紹介するのでないというわけではありません。*


# それでもやっぱり順序を扱いたい！

## 順序の必要性

SQLでは結果の順序が不定であると言いましたが、そうはいっても順序を扱いたくなるときがあります。
そんなときのために、SQLでは下記の代表的な場合について順序を扱う機能を提供しています。

1. SQLの実行結果を別のプログラミング言語で処理するとき
2. 文字列や配列に値を集約するとき
3. 途中の集計などで上位n件を取り出したいとき
4. 時系列データを扱うとき

なお、これらの機能を使わなくても、サブクエリや自己結合、SEQUENCEなどを駆使していろいろできます。
テクニックとしてはとても面白いのですが、冒頭に述べた宣言的であるという性質によるわかりやすさが失われてしまうので、この記事では解説しません。
RDBMSやSQLエンジンの実装にもよるのですが、一般には上記の機能を使った方がテクニックを駆使するより高速です。


## 1. SQLの実行結果を別のプログラミング言語で処理するとき

すでに例で示しましたが、クエリの末尾に**ORDER BY**を付けましょう。

```sql
SELECT X, Y
FROM T
WHERE X = 1
ORDER BY Y DESC
```

なお、実行結果を受け取る側がソートされてることを前提にしていないのであれば不要です。
受け取る側で好きなように加工しましょう。

同じ処理をpandasで書くとこんな感じです。

```python
df[df["X"]==1][["X", "Y"]].sort_values(["Y"], ascending=False)
```


## 2. 文字列や配列に値を集約するとき

文字列も配列もあまり変わらないので、文字列に関して説明します。

下記のようなテーブル(T)があるとします。
例えば、(サブ)クエリの実行結果が、順序(N列)と文字(C列)を保持しているイメージです。

|N|C|
|---|---|
|1|あ|
|2|い|
|3|う|
|4|え|
|5|お|

**string_agg**関数を使って下記のように書けば、`あいうえお`を得ます。

```sql
SELECT string_agg(C, '' ORDER BY N ASC) FROM T
```

同じ処理をpandasで書くとこんな感じです。pandas.DataFrameも行の順序は明記されていないので、念のため`sort_values`を呼んでいます。

```python
df.sort_values(["N"]).agg(lambda x: "".join(x))['C']
```

下記のように書けば、`おえういあ`を得ます。

```sql
SELECT string_agg(C, '' ORDER BY N DESC) FROM T
```

なお、下記のようにも書けますが、結果の並び順は不定です。

```sql
SELECT string_agg(C, '') FROM T
```

この例では、N列はなくてもC列で同じように並び替えられます。
すでに説明したように、SQLではORDER BYがないところでは順序は不定なので、一般には順序も保持しておく必要があります。

SQLには、配列型というものもあります。
配列型に値を順番に入れるときも同様の関数が使えます。


## 3. 途中の集計などで上位n件を取り出したいとき

下記のようなテーブル(graph)があるとします。
fromからtoへの重み(weight)つきグラフのテーブルによる表現です。

|from|to|weight|
|---|---|---|
|0|0|1|
|0|1|0.8|
|0|2|0.6|
|0|3|0.4|
|0|4|0.2|
|1|0|0.3|
|1|1|0.5|
|1|2|0.7|
|1|3|0.9|
|1|4|0.1|

このようなグラフに対して、各点から重みが一定以上のもののみに絞り込むのであれば、単純にWHEREで指定することができます。
一方、各点から重み順で最大N本線を引きたいとすると、各点ごとに集約して上位N件に絞り込む必要があります。

こんなときは、**Window関数**の出番です。
Window関数は、多くのRDBMSやSQLエンジンに導入されており、SQLiteでも最近使えるようになりました。

こんなSQLを書けば、

```sql
SELECT
    "from",
    "to",
    "weight",
    "rank"
FROM (
    SELECT
        "from",
        "to",
        "weight",
        RANK() OVER (PARTITION BY "from" ORDER BY "weight" DESC) AS "rank"
        
    FROM "graph"

) as T_INNER
WHERE "rank" <= 3
ORDER BY "from", "rank"
```

こんな結果が返ってきます。

|from|to|weight|rank|
|---|---|---|---|
|0|0|1|1|
|0|1|0.8|2|
|0|2|0.6|3|
|1|3|0.9|1|
|1|2|0.7|2|
|1|1|0.5|3|

WHERE句に列の別名を指定したり、Window関数が使えないので、サブクエリとなっています。
サブクエリ内の **RANK() OVER(...)** の部分がWindow関数です。
 **RANK()** 関数を使って、矢印の始点(from)ごとに順位(rank)を計算し、順位が3以下のものに絞り込んでいます。

同じ処理をpandasで書くとこんな感じでしょうか。記述量はともかく項目はだいたい一緒ですね。

```python
df["rank"] = df.groupby(["from"]).rank(ascending=False).astype('uint8')
df = df[df["rank"]<=3]
df.sort_values(["from", "rank"])
```

Window関数については、すでに素晴らしい記事がありましたのでご覧いただければと思います。

* [window関数を使いこなす 〜分析のためのSQL〜 \- Qiita](https://qiita.com/HiromuMasuda0228/items/0b20d461f1a80bd30cfc)
* [分析関数（ウインドウ関数）をわかりやすく説明してみた \- Qiita](https://qiita.com/tlokweng/items/fc13dc30cc1aa28231c5)



なお、途中ではなく最後に上位N件を取り出すのであれば、ORDER BYしてからLIMIT句を使うことで実現できます。


## 4. 時系列データを扱うとき

SQLで時系列データを扱うのは大変です。
Window関数とRecursive Query(再帰クエリ)を駆使すれば時系列データ用のSQLは書けそうですが、RDBMSやSQLエンジンが受け付けてくれるかわかりませんし、わかりにくいSQLになります。

そこで、SQLには時系列データをわかりやすく効率よく扱うためにRow Pattern Recognition(行パターンマッチング)機能があります。
RDBMSやSQLエンジンによって、機能名がMATCH_RECOGNIZEだったりMATCHだったりします。

下記のような、日々の最高気温を記録しているテーブル(T)があるとします。


|date|max_temprature|
|---|---|
|2020-12-01|15.3|
|2020-12-02|14.7|
|2020-12-03|13.0|
|2020-12-04|14.2|
|2020-12-05|13.3|
|...|...|

こんなSQLを書けば、

```sql
SELECT "date", "bottom", "bottom_prev"
FROM T 
MATCH_RECOGNIZE(
    ORDER BY "date" ASC
    MEASURES
        PREV(LAST(DOWN."max_temprature")) AS "bottom_prev",
        LAST(DOWN."max_temprature") AS "bottom"
    ONE ROW PER MATCH
    AFTER MATCH SKIP TO LAST UP
    PATTERN (START_ROW DOWN+ UP+)
    DEFINE
        DOWN AS DOWN."max_temprature" < PREV(DOWN."max_temprature"),
        UP AS UP."max_temprature" > PREV(UP."max_temprature")
) as MR
ORDER BY "date"
```

こんな結果が返ってきます。

|date|bottom|bottom_prev|
|---|---|---|
|2020-12-03|13.0|14.7|
|...|...|...|

パターンで定義した通り、谷(気温が下降してその後上昇に転じた)を検出しています。
特に寒かった日を検出するイメージですが、それなら前の日との気温差が3℃といった条件を追加したほうが適切かもしれません。

このSQLが分かりやすいかは賛否両論あるかと思いますが、自分でプログラミングするとしても条件が複雑化してきたら同じようなDSLやAPIを作ることになるのではないでしょうか。

Row Pattern Recognitionについては、Window関数で紹介した記事で触れられています。

* [分析関数（ウインドウ関数）をわかりやすく説明してみた \- Qiita](https://qiita.com/tlokweng/items/fc13dc30cc1aa28231c5)

Apache Flinkのマニュアルもわかりやすくまとまっています。

* [Apache Flink 1\.11 Documentation: Detecting Patterns in Tables](https://ci.apache.org/projects/flink/flink-docs-stable/dev/table/streaming/match_recognize.html)

Row Pattern Recognitionは、今のままだとクエリが複雑でちょっと使いにくそうなので、ACM SIGMODで話題だったこちらの論文の技術と組み合わせると面白そうです。

* [\[1811\.07977\] ShapeSearch: A Flexible and Efficient System for Shape\-based Exploration of Trendlines](https://arxiv.org/abs/1811.07977)


# 終わりに

この記事では、SQLでは結果の順序が不定であることを説明し、順序を扱う際の便利な機能を紹介しました。
便利な機能として紹介したものは、順序を扱うので当然といえば当然なのですが、**ORDER BY**句を使うという共通点があります。
SQLでは、ORDER BY句の影響範囲を関数の中などに狭めて局所化することで、RDBMSやSQLエンジンの実装自由度を高めています。
SQLで順序を扱うときは、ORDER BYをうまく使いこなして、RDBMSやSQLエンジンが効率よく高速に処理できるようにしましょう。

なお、無理してSQLを使う必要はありません。
データを処理する方法は下記に示すようにいろいろあるので、プロジェクトの要件や自分の好みで選んだほうが幸せになれます。

* 表計算ツールやその進化系
* ETLツールやBIツール
* JavaやPythonなどの汎用プログラミング言語
* PandasやSparkなどのDataFrame系API/ライブラリ
* SQL/その他クエリ言語