はじめに

にゃーん。
昨晩、某社のデータベーススペシャリストの篠田さんが、こんなツイートしてたのをたまたま見かけた。
PostgreSQL 13 / Incremental Sort
へー、PostgreSQL 13には、こんな機能が入るのか。面白そう、ということで自分も試してみた。

Incremental Sort is 何？

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

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

のようです。
詳細はCommitfestのIncremental sortを見てください。と言いつつ、自分もほとんど読んでませんが・・・（英語きらーい）

使ってみた

こういうのは使ってみるのが理解のためには早いです。（英語読むよりは楽）

バージョン

今回は、4/8に取り込んだcommit id = 75848bc74411130ede23995d0ab1aefb12c4c4b0 の版をビルドして試してみました。

検証用テーブル

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

CREATE TABLE test (id int primary key, data1 real, data2 real, data3 real);

で、こんな感じのINSERT文を実行して、データを登録します。ついでにANALYZEもかけて。事前に登録したpg_prewarm拡張機能を使ってshared_buffersにキャッシュしておきます。²

データロード

以下のような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()によって生成された値が格納されている。重要なポイントは、この列がソートされ、かつB-treeインデックスを設定している、ということ。
data2	real	これもrandom()によるテキトーな値が値が設定されている。重要なポイントは、この鉄はB-treeインデックスを設定している、ということ。
data3	real	これもrandom()によるテキトーな値が設定されている。こいつの役割はソートCostを増やすこと。そんだけ。

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

                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)

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になっている)。³

検索してみる

この状態で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（クラスタ化済み）

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（クラスタ化済み）

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（クラスタ化済み）

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（クラスタ化されていない）

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を含むクエリの性能が改善した！なんてケースは出てきそうだ。

検証してみて分かったのですが、現時点ではcorrelationの値に関わらず、インデックスが設定されていると、Incremental sortが選択されて、にゃーんなことになるケースもありそうです。 ↩
pg_prewarm拡張は事前にビルドしてCREATE EXTENSIONで登録しておきます。 ↩
correlationの詳細はpg_statsあたりを参考にしてください(リンク先はPostgreSQl 11のものだけど、たぶんPostgreSQL 13でも差はないはず)。 ↩

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