こんにちは！新人エンジニアの宮本です。
みなさんはアルゴリズムを使ってプログラムを高速化していますか？
アルゴリズムを工夫するだけでこれまで長時間かかっていた処理が一瞬で終わると感動しますよね。
PostgreSQLでは、与えられたクエリに対してプランナが実行計画を立てますが、ここでもアルゴリズムを使った高速化が行われています。
この記事では、その1つである 移動集約モード について紹介します。
移動集約モードとは？
移動集約モードは、集約関数を含むある種のクエリを高速化する機能です。
対象となるクエリ
key カラムと value カラムをもつ10行のテーブル test を用意します。
CREATE TABLE test (key int, value int);
INSERT INTO test(key, value)
SELECT
i
,random()*100
FROM generate_series(1,10) as i;
test テーブルは次の表のようになるでしょう。
| key | value |
|---|---|
| 1 | 46 |
| 2 | 61 |
| 3 | 13 |
| 4 | 80 |
| 5 | 0 |
| 6 | 14 |
| 7 | 50 |
| 8 | 29 |
| 9 | 18 |
| 10 | 74 |
次のクエリを考えてみましょう。
SELECT
key
,value
,sum(value) OVER (ORDER BY key rows 3 preceding) as sum
FROM test;
これは、各 key に対し、 key - 3 <= i <= key を満たす i の value を足し合わせた値を求めるクエリです。
「1時間当たりの降水量から過去4時間の降水量を求めたいとき」や「1日あたりに食べたお寿司の数から過去4日間に食べたお寿司の数を求めたいとき」など、様々な場面で使えそうなクエリですね。
以下の表が実行結果です。
| key | value | sum |
|---|---|---|
| 1 | 46 | 46 |
| 2 | 61 | 107 (46+61) |
| 3 | 13 | 120 (46+61+13) |
| 4 | 80 | 200 (46+61+13+80) |
| 5 | 0 | 154 (61+13+80+0) |
| 6 | 14 | 107 (13+80+0+14) |
| 7 | 50 | 144 (80+0+14+50) |
| 8 | 29 | 93 (0+14+50+29) |
| 9 | 18 | 111 (14+50+29+18) |
| 10 | 74 | 171 (50+29+18+74) |
移動集約モードでは、このようなクエリの実行を高速化できます。
クエリの一般化
上のクエリは、テーブルの件数10を文字 N、足し合わせる長さ3を文字 K に置き換えることで、次の問題とみなせます。
長さ
Nの数列a_0 ... a_{N-1}と 1 以上N以下の整数Kが与えられます。 各整数x (0 <= x < N)に対し、a_{x-K} + a_{x-K+1} + ... + a_xの値を求めてください。ただし、i < 0に対しa_i=0とします。
この問題を、遅い解法と高速な解法の2通りの解法で解いてみましょう。
遅い解法
各整数 x に対し、a_{x-K} + a_{x-K+1} + ... + a_xの値を愚直に計算します。Pythonで書くと次のコードになります。
for i in range(N):
sum = 0
for j in range(K + 1):
if i - j >= 0:
sum += a[i-j]
print(sum)
この解法の計算量はO(NK)です。たとえば、N=10000, K=1000のときに長さ N の配列 a に対して上記のプログラムの実行すると、終了までに1秒以上かかります。
高速な解法
実は、直前に計算した結果を使うことにより合計値を高速に計算できます。
つまり、
a_{x-K} + a_{x-K+1} + ... + a_x = (a_{x-K-1} + a_{x-K+1} + ... + a_{x-1}) - a_{x-K-1} + a_x
が成り立っていることを利用し、前から順番に値を求めていきます。
pythonで書くと次のコードになります。
sum = 0
for i in range(N):
if i <= K:
sum = sum + a[i]
else:
sum = sum - a[i - K - 1] + a[i]
print(sum)
この解法の計算量は O(N) です。例えば、N=10000, K=1000 のときに長さ N の配列 a に対して上記のプログラムの実行した場合、0.1秒以内に処理が終わります。
PostgreSQLの集約関数には、内部に 前方状態遷移関数 と 逆状態遷移関数 が定義されているものがあります。
- 前方状態遷移関数
msfunc... 集約関数の要素に値を1つ追加する - 逆状態遷移関数
minvfunc... 集約関数の要素から値を1つ取り除く
これらの2つの関数が内部的に定義されている集約関数に対しては、移動集約モードを使うことができ、上記のようなクエリを高速に計算することができます。
テスト
さて、実際のDBで移動集約モードをためしてみましょう。
先ほどはテーブルのレコード件数が10件でしたが、高速化がわかるようにするため、レコード件数を10000件に増やします。
CREATE TABLE test (key int, value int);
INSERT INTO test(key, value)
SELECT
i
,random()*100
FROM generate_series(1,10000) as i;
次のクエリをexplain analyzeしてみましょう。移動集約モードが使われていれば処理が一瞬で終わるはずです。
SELECT
key
,value
,sum(value) OVER (ORDER BY key rows 1000 preceding) as sum
FROM test;
実行結果は次のようになります。
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
WindowAgg (cost=809.39..984.39 rows=10000 width=16) (actual time=1.394..5.552 rows=10000 loops=1)
-> Sort (cost=809.39..834.39 rows=10000 width=8) (actual time=1.369..1.723 rows=10000 loops=1)
Sort Key: key
Sort Method: quicksort Memory: 853kB
-> Seq Scan on test (cost=0.00..145.00 rows=10000 width=8) (actual time=0.010..0.521 rows=10000 loops=1)
Planning Time: 0.855 ms
Execution Time: 5.980 ms
わずか5.980msで処理が終わることが確認できました！非常に高速に計算できていてありがたいですね。
移動集約モードが適用されない場合
集約関数に移動集約モードが適用されるためには、前方状態遷移関数 msfunc と逆状態遷移関数 minvfunc が定義されていなければなりません。
なおかつ、これらの関数がお互いに逆操作(一方を適用した後他方を適用すると元に戻る)でないと、正確な計算ができません。
たとえば、float8型に対する足し算や引き算は桁落ち誤差を含むため正確な計算ができず、float8 型に対する 集約関数 sum は移動集約モードをサポートしていません。
実際、上のクエリで value の型を float8 に変えて同じようにテーブルを作り、同じクエリを実行すると、処理が終わるまでに1秒以上かかってしまいます。
- 作成したテーブル
CREATE TABLE test (key int, value float8);
INSERT INTO test(key, value)
SELECT
i
,random()*100
FROM generate_series(1,10000) as i;
- 実行したクエリ
SELECT
key
,value
,sum(value) OVER (ORDER BY key rows 1000 preceding) as sum
FROM test;
- explain analyzeした結果
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
WindowAgg (cost=921.96..1118.31 rows=11220 width=20) (actual time=1.710..1156.310 rows=10000 loops=1)
-> Sort (cost=921.96..950.01 rows=11220 width=12) (actual time=1.702..2.547 rows=10000 loops=1)
Sort Key: key
Sort Method: quicksort Memory: 853kB
-> Seq Scan on test (cost=0.00..167.20 rows=11220 width=12) (actual time=0.019..0.811 rows=10000 loops=1)
Planning Time: 0.084 ms
Execution Time: 1157.192 ms
おわりに
フォルシアでは、エンジニアの新卒採用や中途採用を行っています！
私のように未経験でも技術に興味のある人や、自分の経験を社会に役立てたい人はぜひご応募ください！
また、私を含むフォルシアの新卒メンバーのインタビュー記事があるので、下記のリンクからぜひご覧ください！
参考にした記事
移動集約モードに関する日本語の記事は以下の2本のみだと思います。この記事は3本目ですね。
Discussion