ヒープ作成だけで時間かかり、ソートは取り止め
とりあえずINT4型の配列をヒープに組み換える部分だけ作ってテストしたら、要素数1万を越えるあたりから急に遅く、昨日までのブラウザ + JavaScriptとの差が大き過ぎるのでソートは止めました。
JavaScriptは要素数100万の配列のヒープ化で10～20ミリ秒だったのに対し、PL/pgSQLは要素数10万で約1000倍（10～20秒）かかるという…。PostgreSQLが未チューニング（デフォルト設定のまま）のせいもあると思いますが、それを割り引いてもPL/pgSQLはちょっと厳しい感じ。
実行環境とストアド関数のソース
Windows7 32bit + PostreSQL Portable 9.2.9で、下記のテスト用ストアドを作成・実行しました。INT4型の乱数で配列を作ってヒープに組み換え、その部分だけの実行時間を測るもの。PCは昨日までと同じノートパソコンで、Core i5-4300M、メモリはOSで可能な上限の3.5GB。postgresql.confは前項に書いたとおりデフォルトのまま。
今回、元の配列をいったんヒープ用の配列にコピーしてから入れ替えてますが、コピーせず元配列を直接入れ替えても、所要時間はほとんど変わりませんでした。
結果
まず配列の要素数が1万の場合、ほぼ0.1秒。これが線形で増加していくなら、まだ良いけど…
agg_test=# SELECT test_array2heap(10000, 10);
INFO: time 125 ms
agg_test=# SELECT test_array2heap(10000, 10);
INFO: time 109 ms
agg_test=# SELECT test_array2heap(10000, 10);
INFO: time 124 ms
agg_test=# SELECT test_array2heap(10000, 10);
INFO: time 109 ms
agg_test=# SELECT test_array2heap(10000, 10);
INFO: time 109 ms
↓ 要素数を2.5万に増やすと、途端に約1.5秒かかりました。
agg_test=# SELECT test_array2heap(25000, 10);
INFO: time 1498 ms
agg_test=# SELECT test_array2heap(25000, 10);
INFO: time 1498 ms
agg_test=# SELECT test_array2heap(25000, 10);
INFO: time 1529 ms
agg_test=# SELECT test_array2heap(25000, 10);
INFO: time 1498 ms
agg_test=# SELECT test_array2heap(25000, 10);
INFO: time 1513 ms
↓ 要素数5万では7～8秒、ただし最初の1回は特に遅く10秒近く。これはヒープ化の部分だけの処理時間で、全体のクエリ実行は乱数で配列を作る部分もあるので数十秒かかってます。
agg_test=# SELECT test_array2heap(50000, 10);
INFO: time 9547 ms
agg_test=# SELECT test_array2heap(50000, 10);
INFO: time 7660 ms
agg_test=# SELECT test_array2heap(50000, 10);
INFO: time 7691 ms
agg_test=# SELECT test_array2heap(50000, 10);
INFO: time 7706 ms
agg_test=# SELECT test_array2heap(50000, 10);
INFO: time 7707 ms
↓ 最後に要素数10万。初回に特に時間がかかる傾向がいっそう強まり（25秒）、2回目以降は概ね10秒。でも要素数1万の時（約0.1秒）に比べ100倍かかってます。
agg_test=# SELECT test_array2heap(100000, 10);
INFO: time 25132 ms
agg_test=# SELECT test_array2heap(100000, 10);
INFO: time 10312 ms
agg_test=# SELECT test_array2heap(100000, 10);
INFO: time 10437 ms
agg_test=# SELECT test_array2heap(100000, 10);
INFO: time 10327 ms
agg_test=# SELECT test_array2heap(100000, 10);
INFO: time 10358 ms
そもそもの動機と、今後
PostgreSQL 9.4より前はパーセンタイルを出す集約関数がなく、何か自作できないかなというのが元々のきっかけ。対象列をいったん配列にし、ヒープソートしてパーセンタイルを出せるかと思ったけど、PL/pgSQLでは実用にならなそう。一応PL/V8も試す予定ですが、要素数が多い配列はどうしても作るまでに時間かかるので、あくまで実験という感じ。諦めてORDER BYとウィンドウ関数を使うのが現実的かも知れません。
蛇足だけどRで処理時間の増加を非線型回帰してみた
今回試した要素数1万、2.5万、5万および10万での各5回試行のうち、初回は条件が違うと考え残り4回についてRのnls関数（非線型最小二乗法）でロジスティック回帰してみました。これだけ見ると要素数が10万より増えてもまるで10秒程度に落ち着きそうですが、そんなことないはず。もっと要素数を増やせば違う結果になると思います。また初回の処理時間（赤い点）がぐっと増えているのが、実用上は大きな問題。
