PostgreSQL 13がやってくる！(5) - incremental sort

# はじめに
にゃーん。
昨晩、某社のデータベーススペシャリストの[篠田さん](https://twitter.com/nori_shinoda)が、こんなツイートしてたのをたまたま見かけた。
[PostgreSQL 13 / Incremental Sort](https://twitter.com/nori_shinoda/status/1247501712648105985)
へー、PostgreSQL 13には、こんな機能が入るのか。面白そう、ということで自分も試してみた。

# Incremental Sort is 何？
この機能は、とても雑に言うと、ORDER BYに複数列を指定したとき、ある特定の条件を満たしたときに、既存のソート方式ではなく、より効率の良いソート方式を選択してくれるというものっぽいです。
特定の条件というのは、自分の理解した範囲だと

* その列にB-treeインデックスが設定されている
* その列が既にソートされている [^1]

のようです。
[^1]: 検証してみて分かったのですが、現時点ではcorrelationの値に関わらず、インデックスが設定されていると、Incremental sortが選択されて、にゃーんなことになるケースもありそうです。

詳細はCommitfestの[Incremental sort](https://commitfest.postgresql.org/27/1124/)を見てください。と言いつつ、自分もほとんど読んでませんが・・・（英語きらーい）

# 使ってみた
こういうのは使ってみるのが理解のためには早いです。（英語読むよりは楽）
## バージョン
今回は、4/8に取り込んだcommit id = 75848bc74411130ede23995d0ab1aefb12c4c4b0 の版をビルドして試してみました。

## 検証用テーブル
こんな感じのテーブルを作成しておきます。

```sql
CREATE TABLE test (id int primary key, data1 real, data2 real, data3 real);
```
で、こんな感じのINSERT文を実行して、データを登録します。ついでにANALYZEもかけて。事前に登録した[pg_prewarm](https://www.postgresql.jp/document/11/html/pgprewarm.html)拡張機能を使ってshared_buffersにキャッシュしておきます。[^2]

[^2]: pg_prewarm拡張は事前にビルドして`CREATE EXTENSION`で登録しておきます。

## データロード
以下のようなSQLでデータをロードする。

```sql
INSERT INTO test (
  SELECT i, d1, d2, d3 FROM (
    SELECT generate_series(1, 1000000) i, random() d1, random() d2, random() d3
  ) t ORDER BY d1
);
ANALYZE test;

SELECT pg_prewarm('test');
```

`test`テーブルはこんな感じのデータが100万件入っています。

|列名|データ型|内容|
|:--|:--|:--|
|id|integer|単なるid。今回の検証では特に何かするわけでもなく。|
|data1|real|ramdom()によって生成された値が格納されている。<br>重要なポイントは、この列がソートされ、かつB-treeインデックスを設定している、ということ。
|data2|real|これもrandom()によるテキトーな値が値が設定されている。<br>重要なポイントは、この鉄はB-treeインデックスを設定している、ということ。|
|data3|real|これもrandom()によるテキトーな値が設定されている。こいつの役割はソートCostを増やすこと。そんだけ。|

テーブル定義と、統計情報ビュー(pg_stats)から、n_distinct, correlationの内容はこんな感じになっている。

```sql
                Table "public.test"
 Column |  Type   | Collation | Nullable | Default
--------+---------+-----------+----------+---------
 id     | integer |           | not null |
 data1  | real    |           |          |
 data2  | real    |           |          |
 data3  | real    |           |          |
Indexes:
    "test_pkey" PRIMARY KEY, btree (id)
    "test_data1_idx" btree (data1)
    "test_data2_idx" btree (data2)
```

```sql
SELECT attname, n_distinct, correlation FROM pg_stats WHERE tablename = 'test';
 attname | n_distinct |  correlation
---------+------------+---------------
 id      |         -1 |  0.0019892552
 data1   |  -0.954025 |             1
 data2   |   -0.97232 | -0.0062349555
 data3   |  -0.966145 | -0.0048103556
(4 rows)
```
data1 の列がクラスタ化されているのは、これで確認できる(correkationが1になっている)。[^3]

[^3]: correlationの詳細は[pg_stats](https://www.postgresql.jp/document/11/html/view-pg-stats.html)あたりを参考にしてください(リンク先はPostgreSQl 11のものだけど、たぶんPostgreSQL 13でも差はないはず)。

## 検索してみる
この状態でORDER BYつきの検索をかけてみる。以下の4パターンを試してみる。

|パターン|ソートキー|enable_incrementalsor|enable_indexscan|
|:--|:--|:-:|:-:|
|パターン1|data1, data3|on|on|
|パターン2|data1, data3|off|on|
|パターン3|data1, data3|on|off|
|パターン4|data2, data3|on|on|

はてさて、どうなるやら。

## 実行してみた
上記のパターン毎にSELECTを実行したときの実行計画を示す。

### パターン1

* enable_incrementalsor=on, enable_indexscan=on
* ソートキーの最初の列はdata1（クラスタ化済み）

```sql
EXPLAIN (ANALYZE, VERBOSE, BUFFERS) SELECT id FROM test ORDER BY data1, data3;
                                                                     QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
 Incremental Sort  (cost=0.47..74780.30 rows=1000000 width=12) (actual time=0.136..2242.577 rows=1000000 loops=1)
   Output: id, data1, data3
   Sort Key: test.data1, test.data3
   Presorted Key: test.data1
   Full-sort Groups: 31231 Sort Method: quicksort Memory: avg=26kB peak=26kB
   Buffers: shared hit=8147
   ->  Index Scan using test_data1_idx on public.test  (cost=0.42..31389.42 rows=1000000 width=12) (actual time=0.038..960.216 rows=1000000 loops=1)
         Output: id, data1, data3
         Buffers: shared hit=8141
 Planning Time: 0.298 ms
   Buffers: shared hit=48
 Execution Time: 2812.155 ms
(12 rows)
```

出たっ！謎のオペレータ`Incremental Sort`！

### パターン2

* enable_incrementalsor=off, enable_indexscan=on
* ソートキーの最初の列はdata1（クラスタ化済み）

```sql
EXPLAIN (ANALYZE, VERBOSE, BUFFERS) SELECT id FROM test ORDER BY data1, data3;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=132154.34..134654.34 rows=1000000 width=12) (actual time=2029.769..2672.005 rows=1000000 loops=1)
   Output: id, data1, data3
   Sort Key: test.data1, test.data3
   Sort Method: external merge  Disk: 21560kB
   Buffers: shared hit=5406, temp read=3510 written=3529
   ->  Seq Scan on public.test  (cost=0.00..15406.00 rows=1000000 width=12) (actual time=0.016..719.438 rows=1000000 loops=1)
         Output: id, data1, data3
         Buffers: shared hit=5406
 Planning Time: 0.100 ms
 Execution Time: 3241.542 ms
(10 rows)
```
`enable_incrementalsor`をoffると既存のSortが選択される。

### パターン3

* enable_incrementalsor=on, enable_indexscan=off
* ソートキーの最初の列はdata1（クラスタ化済み）


```sql
EXPLAIN (ANALYZE, VERBOSE, BUFFERS) SELECT id FROM test ORDER BY data1, data3;
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Sort  (cost=132154.34..134654.34 rows=1000000 width=12) (actual time=2036.130..2680.172 rows=1000000 loops=1)
   Output: id, data1, data3
   Sort Key: test.data1, test.data3
   Sort Method: external merge  Disk: 21560kB
   Buffers: shared hit=5406, temp read=3510 written=3529
   ->  Seq Scan on public.test  (cost=0.00..15406.00 rows=1000000 width=12) (actual time=0.018..724.701 rows=1000000 loops=1)
         Output: id, data1, data3
         Buffers: shared hit=5406
 Planning Time: 0.108 ms
 Execution Time: 3251.280 ms
(10 rows)
```

`enable_incrementalsor`がonであっても、IndexScanが選択されなければ、Incremental Sortオペレータは発動しない。Cost上の問題かもしれないけど。

### パターン4

* enable_incrementalsor=on, enable_indexscan=on
* ソートキーの最初の列はdata2（クラスタ化されていない）

```sql
EXPLAIN (ANALYZE, VERBOSE, BUFFERS) SELECT id FROM test ORDER BY data2, data3;
                                                                      QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------------
 Incremental Sort  (cost=0.49..95714.99 rows=1000000 width=12) (actual time=0.159..3417.495 rows=1000000 loops=1)
   Output: id, data2, data3
   Sort Key: test.data2, test.data3
   Presorted Key: test.data2
   Full-sort Groups: 31231 Sort Method: quicksort Memory: avg=26kB peak=26kB
   Buffers: shared hit=1003588
   ->  Index Scan using test_data2_idx on public.test  (cost=0.42..51683.79 rows=1000000 width=12) (actual time=0.026..2101.222 rows=1000000 loops=1)
         Output: id, data2, data3
         Buffers: shared hit=1003588
 Planning Time: 0.185 ms
   Buffers: shared hit=3
 Execution Time: 3989.650 ms
(12 rows)
```
このときには、`Incremental Sort`オペレータは指定されるものの、actual timeを見てわかるように、その効果は発揮できていない・・・にゃーん。


## 実行結果のまとめ
上記の実行計画から、SortのInitial acutual time/SortのTotal  acutual time、Execution Timeに着膜してまとめてみた。
（数値の単位はms）

|パターン|Sort方式|Initial time|Total time|Execution Time|
|:--|:--|--:|--:|--:|
|パターン1|Incremental|0.136|2242.577|2812.155|
|パターン2|通常|2029.769|2672.005|3241.542|
|パターン3|通常|2036.130|2680.172|3251.280|
|パターン4|Incremental |0.159|3417.495 |3989.650|

この結果から言えそうなのは、以下の4点だろうか。

* Incremental Sortが選択された場合、Initial actual timeが大きく減少する。これによる性能改善が期待できる。
* ソートキーの一部がインデックスになっており、かつ既に並べ替えられているときに、性能上有利になる。
* インデックス検索されないときには、Incremental Sortの恩恵は受けない。
* ソートキーの一部がインデックスになっているが、並べ替えされていない列(data2)が使われるときには、Incremental Sortは選択されるものの、ソート時間そのものの時間はかかるため、トータルでの性能改善にはならない。

また、実行計画をよくよく見てみると、（今回の環境ではwork_menを増やしていないので）

* 通常のソートの場合には、External Sortになる。
* Incremental Sortが選択されたときには、External Sortにはならない（ように見える）

# まとめ
この機能自体は、これの効果を積極的に狙ってテーブル設計や、発行するSQLの設計を行うという類のものではない気がするが、こういう特定のケースの場合に、賢く効率の良いソート方法をPostgreSQLが選択可能になる、ということなんだろう。
ちょい地味な機能かもしれないが、この機能が入ることで、知らずしらずORDER BYを含むクエリの性能が改善した！なんてケースは出てきそうだ。