PostgreSQLで多次元配列を1次元配列に展開したい

この記事は PostgreSQL Advent Calendar 2016 の8日目の記事です。

PostgreSQL では配列型がサポートされており、多次元配列を扱うことができます。
データ集計などを行う際に配列型を利用することで多少難しいロジックの実現や速度の向上といった恩恵を得ることができる場合があります。

ところがマニュアルの配列関数と演算子の項目を眺めてみるとお気づきになると思うのですが、多次元配列を1次元配列に一発で展開するような関数は用意されていません。
以前、ARRAY_FLATTEN が欲しいなぁと思って調べてみたのですが、現時点では何らかの方法で自前で実現してやるしかないようです。

今回、次の3種類の方法を検討しパフォーマンスについて調査してみました。他には自前で集約関数を実装するという方法もあると思いますが、今回は標準の機能で実現できる方法に絞っています。
  1. UNNEST & ARRAY_AGG
  2. ARRAY_TO_STRING & STRING_TO_ARRAY
  3. LATERAL & UNNEST & ARRAY_AGG
結果としてはどうやら3の方法が、そこそこ安定した速度が出て、気をつける点も少ないため扱いやすそうでした。

追記:あとで気づいたけどスカラサブクエリでも良かった。

検証に使った環境は以下の通りです。
  • PostgreSQL 9.5.3
  • Mac OS X El Capitan

方法1. UNNEST & ARRAY_AGG

まず考え付くのは UNNEST で行に展開後、ARRAY_AGG で集約する方法です。UNNEST で多次元配列を展開すると配列の次元数に関係なく配列中の1要素を行に展開することができます。
mohya=# with src(id, val) as (values(1, array[array[1, 2], array[3, 4]]), (2, array[array[1, 2]])) select id, array_agg(val) from (select id, unnest(val) from src) as sub(id, val) group by id;

 id | array_agg
----+-----------
  1 | {1,2,3,4}
  2 | {1,2}
(2 rows)

ただし、これは行に展開してからキーごとにまとめて集約する都合上、メモリの消費が大きくあまり効率的でない方法と考えられます。

また、知らなかったのですが UNNEST した行を集約する場合、UNNEST をサブクエリ内で先に実行しておかないといけないようです。
mohya=# with src(id, val) as (values(1, array[array[1, 2], array[3, 4]]), (2, array[array[1, 2]])) select id, array_agg(unnest(val)) from src group by id;
ERROR:  set-valued function called in context that cannot accept a set


方法2. ARRAY_TO_STRING & STRING_TO_ARRAY

ARRAY_TO_STRING 関数を利用すると多次元配列を1次元配列を表す文字列に展開できます。反対に STRING_TO_ARRAY という関数もあり、これらを利用して多次元配列を文字列に変換、その後文字列を1次元配列に直すという方法もあります。
mohya=# with src(id, val) as (values(1, array[array[1, 2], array[3, 4]]), (2, array[array[1, 2]])) select id, string_to_array(array_to_string(val, ','), ',')::integer[] from src;
 id | string_to_array
----+-----------------
  1 | {1,2,3,4}
  2 | {1,2}
(2 rows)
以下の点に気をつける必要はありますが、うまく展開できるようです。

  • 文字列配列の場合、文字列中に含まれる文字を区切り文字とできない
  • 文字列以外の配列の場合、キャストが必要となる

この方法については配列の要素数が増えた場合、一時的に長大な文字列を生成するはずなので速度面でどうなのかという点が気になります。

方法3. LATERAL & UNNEST & ARRAY_AGG

これは1の方法の改良版になります。
PostgreSQL では LATERAL 副問い合わせというものを利用することができ、サブクエリ中で、それ以前に定義済みの FROM 句の内容を参照することができます。
mohya=# with src(id, vals) as (values(1, array[array[1, 2], array[3, 4]]), (2, array[array[1, 2]])) select id, val from src, lateral (select array_agg(v) from unnest(vals) as v) as sub(val);
 id |    val
----+-----------
  1 | {1,2,3,4}
  2 | {1,2}
(2 rows)

後ほど実行計画を見てみますが、LATERAL が指定されたサブクエリは参照する FROM 句で導出された各行に対してループ実行されます。
1と比べて、一時的に行に展開するのが1列だけで済むこと、一度に集約する行数が少なくなること、キーを指定した集約でなくなることから1の方法よりパフォーマンスが良いことが期待できそうです。

なお、これを考えるにあたってはこちらのStackoverflowの内容を参考にしました。それにしても Implisit LATERAL という挙動があるのは知らなかった。。。

パフォーマンスの比較調査

1〜3の方法についてどの程度パフォーマンスに違いが出るのかを確認してみたいと思います。

ざっくり10万行くらいのレコードで計測してみました。データは以下のように用意しました。
mohya=# create table src(id, val, optional) as select generate_series(1, 100000), array[array[1, cast(random() * 1000 as integer)], array[2, cast(random() * 1000 as integer)]], random();
SELECT 100000

mohya=# select * from src limit 10;
 id |        val        |      optional
----+-------------------+-------------------
  1 | {{1,705},{2,316}} | 0.654498992487788
  2 | {{1,436},{2,401}} | 0.775149736087769
  3 | {{1,43},{2,520}}  | 0.854071325156838
  4 | {{1,144},{2,556}} | 0.949878746643662
  5 | {{1,79},{2,446}}  |  0.67902524350211
  6 | {{1,988},{2,198}} | 0.653656270820647
  7 | {{1,207},{2,835}} | 0.160206186585128
  8 | {{1,52},{2,866}}  | 0.373904585372657
  9 | {{1,45},{2,175}}  | 0.520811752881855
 10 | {{1,967},{2,677}} | 0.599950326606631
(10 rows)

EXPLAIN ANALYZE により実行計画と実際の実行時間(Planning time + Execution time)を見てみましょう。

方法1の実行計画。行数 x 配列の要素数に展開されている。
ディスクを利用したソートが発生している。ここを解消できればよりパフォーマンス向上が期待できるはず。


方法2の実行計画。配列を行に展開しないためシンプルな計画になっている。
ちなみにキャストしない場合、さらに実行速度は速かった。


方法3の実行計画。各行ごとにループして配列を展開する計画になっていることが確認できる。
キーによる集約でないためソートが必要ない分だけ方法1より速くなっていると考えられる。
方法2が一番速度的に優れていました。それより方法3が少し遅く、方法1が最も遅いという結果になりました。方法1が他よりパフォーマンスが悪いのは推測通りでした。

配列の要素数を増やして再度比較してみる

続けて配列の要素数が多い場合を試してみました。以下の方法で先ほど利用したデータを元に配列の要素数を増やしたデータを用意しました。

mohya=# create table src2 as select * from src;
SELECT 100000

mohya=# update src2 set val = val || val;
UPDATE 100000
-- update を数回繰り返しました
mohya=# select * from src2 limit 1;

 id |                                                                                                                                                                                                                                       val                                                                                                                                                                                                  |      optional
----+-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------
  1 | {{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355},{1,795},{2,355}} | 0.0923215881921351
(1 rows)

方法1。一度にまとめてソートする行数が増えるためかなりパフォーマンスが悪化する。

方法2。1の約1/3の実行時間となっている。


方法3。方法2より実行時間が短くなっている。

配列の要素数が多い場合、方法3の方が2よりパフォーマンスが良い結果となりました。
恐らく文字列の生成コストの増加によりパフォーマンスが逆転したのだろうなぁと推測されます。

まとめ

標準の機能で多次元配列を1次元配列に展開する場合、方法3として紹介した LATERAL & UNNEST & ARRAY_AGG を利用してやると、配列の要素数によらずそこそこ安定した速度が出て、利用にあたって気をつける点も少なくて済みそうだなぁということがわかりました。


付録

そういえば自前で関数を作成すれば実質的には方法3と同じものの、プラン上は NL Join が消えるよなぁ。コスト的にはどうなんだろうというのが気になったので試してみました。

ざっくり関数を書いて実行計画を取ってみる。入力データは配列の要素数を増やす前のものです。

約2,600ms。関数呼び出しのオーバーヘッドが大きいのだろうか

方法3が約1,000msに対して自前の関数を利用した場合、2,600ms・・・
関数を10万回呼び出すとそこそこのオーバーヘッドがあるらしいということが伺えます。

ものは試しに sql ではなく plpgsql で関数定義してみました。

約3,300ms。plpgsql の場合さらにオーバーヘッドが大きいようだ

なるほど、さらにオーバーヘッドが大きいと。。。


2016/12/8追記

あれ、そういえばこれって1行に対して1行を返すのでスカラサブクエリで良いのでは?ということに気づいたので試してみました。

LATERAL の方法と数回実行して比較してみましたが、速度的にはほぼ同等のようでした。実行計画に違いはあるけど、まあ実際の計算内容は同じだものね。

コメント

このブログの人気の投稿

inotify でファイル監視しようず!

ジャックパーセルのかかとの内側を直した