Contents

ヒープ作成だけで時間かかり、ソートは取り止め

とりあえず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は前項に書いたとおりデフォルトのまま。

test_array2heap.sqlSelect Rawtext Bitbucket

CREATE OR REPLACE FUNCTION test_array2heap(IN len int, IN print int)
RETURNS setof void
LANGUAGE plpgsql IMMUTABLE AS $BODY$
/*
    -- e.g.
    SELECT test_array2heap(10000, 10);
*/
DECLARE
    ord int;
    ord2 int;
    below int;
    below_r int;
    vc int; -- value current
    vb int; -- value below
    vr int; -- value below right
    ary int[];
    heap int[];
    ts timestamp[];
BEGIN
    ary = array_agg((random() * len) :: int)
        FROM generate_series(1, len);

    /* slow
    FOR i IN 1..len LOOP
        ary[i] = (random() * len) :: int;
    END LOOP;
    */

    ts[1] = clock_timestamp();
    heap = ary;
    ord = len / 2;
    WHILE ord > 0 LOOP
        ord2 = ord;
        WHILE ord2 <= len LOOP
            below = 2 * ord2;
            IF len < below THEN EXIT; END IF;

            below_r = below + 1;
            vc = heap[ord2];
            vb = heap[below];

            IF below < len THEN
                vr = heap[below_r];
                IF vb < vr THEN
                    below = below_r;
                    vb = vr;
                END IF;
            END IF;

            IF vc < vb THEN
                heap[ord2] = vb;
                heap[below] = vc;
            END IF;
            ord2 = below;
        END LOOP;
        ord = ord - 1;
    END LOOP;
    ts[2] = clock_timestamp();

    -- Check
    RAISE INFO 'array %,...', left(ary[1:print] :: text, -1);
    RAISE INFO 'heap  %,...', left(heap[1:print] :: text, -1);
    RAISE INFO 'time  % ms', extract(milliseconds FROM ts[2] - ts[1]);
    RAISE INFO '';
    FOR i IN 1..len / 2 LOOP
        IF heap[i] < heap[2 * i] OR
            (heap[2 * i + 1] IS NOT NULL AND heap[i] < heap[2 * i + 1]) THEN
            RAISE 'at %', i;
        END IF;
    END LOOP;
END;
$BODY$;

今回、元の配列をいったんヒープ用の配列にコピーしてから入れ替えてますが、コピーせず元配列を直接入れ替えても、所要時間はほとんど変わりませんでした。

結果

まず配列の要素数が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秒程度に落ち着きそうですが、そんなことないはず。もっと要素数を増やせば違う結果になると思います。また初回の処理時間（赤い点）がぐっと増えているのが、実用上は大きな問題。

nls_sslogis_example.RSelect Rawtext Bitbucket

len = c(1, 2.5, 5, 10) * 10^4
dat_init = data.frame(
    ary_length = len,
    times = c(125, 1498, 9547, 25132))
dat = data.frame(
    ary_length = rep(len, each=4),
    times = c(
        109, 124, 109, 109,
        1498, 1529, 1498, 1513,
        7660, 7691, 7706, 7707,
        10312, 10437, 10327, 10358))

nls = nls(times ~ SSlogis(ary_length, Asym, xmid, scal), dat)
prm = nls$m$getPars()
fun = function(x) { prm[1] / (1 + exp((prm[2] - x) / prm[3])) }

# plot points
par(cex=0.8, plt=c(15, 98, 12, 98)/100)
plot(dat_init$ary_length, dat_init$times, col='red',
    xlim=c(0, max(len)), xlab='ary_length',
    ylab='times (milliseconds)')
points(dat$ary_length, dat$times)

# plot logistic curve
usr = par('usr')
curve(add=T, col='red', expr=fun, from=usr[1], to=usr[2])

# plot summary
options(show.signif.stars=F)
str = paste(collapse='\n', capture.output(summary(nls)))
text(adj=c(0, 1), x=0, y=max(dat_init$times), lab=str)