素数を単一SQLステートメントで計算するというよくある話。ただしオラクル限定。

はじめに

素数の難しい話はおいといて、SQLで普通に素数計算しようとすると「行間参照」かまたは計算途中での「結果の蓄積」がどうしても必要となってきますので、PL/SQL等でループしたり最初からSQL以外で記述するのが常套かと思われます。しかしSQL単体でも計算することは可能です。またオラクル特有の機能をつかえば、パフォーマンスを十分に向上させることもできます。

ここでは、それぞれ以下の方法で計算しパフォーマンスを考察しています。

自己結合
MODEL
再帰WITH

自己結合

まずは行間参照のための自己結合です。このSQLも自己結合の多分にもれずパフォーマンスはよくありません。しかし補助テーブルで、2,3,5の倍数を弾いて対象行数を1/3以下に減らした上で各値の平方根の事前準備をしているため、パフォーマンスはかなり改善されています。実行時間は環境によって変わるとは思いますが十万までを対象として30秒程です¹。ちなみに平方根をサブクエリ内で適宜計算すると2分ほどかかるので、SQRTは結構負荷のかかるファンクションといえます。

自己結合

WITH
    nums AS
        (SELECT     LEVEL + 1 n, TRUNC (SQRT (LEVEL + 1)) + 1 rt
         FROM       DUAL
         WHERE      (MOD (LEVEL + 1, 2) > 0 AND MOD (LEVEL + 1, 3) > 0 AND MOD (LEVEL + 1, 5) > 0) OR LEVEL + 1 IN (2, 3, 5)
         CONNECT BY LEVEL < 100000)
SELECT n
FROM   nums n1
WHERE  NOT EXISTS
           (SELECT 1
            FROM   nums n2
            WHERE  n2.n < n1.rt AND MOD (n1.n, n2.n) = 0);

Elapsed: 00:00:29.68

MODEL

次に行間参照最強のMODELです。MODEL句を使うと「エラトステネスの篩（ふるい）」が実現できるためかなり高速化できます。同じく十万までを対象にして3秒程度となりました。ITERATEに指定できる繰り返し回数は実数値のみであり、ここでは柔軟性のため、あらかじめ大きめの数値を与えた上でUNTILで打ち切っています。最大値の平方根を直接指定すれば、平方根計算やUNTILは不要です。非常にシンプルで分かりやすいSQLだと思います。

エラトステネスの篩(MODEL)

SELECT n
FROM   (SELECT n, flg
        FROM   (SELECT     LEVEL + 1 n, SQRT (MAX (LEVEL + 1) OVER ()) mx
                FROM       DUAL
                WHERE      (MOD (LEVEL + 1, 2) > 0 AND MOD (LEVEL + 1, 3) > 0 AND MOD (LEVEL + 1, 5) > 0) OR LEVEL + 1 IN (2, 3, 5)
                CONNECT BY LEVEL < 100000)
        MODEL
            DIMENSION BY (n)
            MEASURES (0 flg, mx)
            RULES UPDATE
                ITERATE (1000) UNTIL (ITERATION_NUMBER + 3 > mx[2])
                (flg [MOD (n, ITERATION_NUMBER + 2) = 0 AND n > ITERATION_NUMBER + 2] = 1))
                -- condition of flg[ITERATION_NUMBER+2]=0 is omitted due to slow performance
WHERE  flg = 0;

Elapsed: 00:00:02.84

ちなみにMODELで補助テーブルを使わない方法もあります。上記のアルゴリズムが使えずほぼ総当りとなるためパフォーマンス的にはダメダメですが、短いワンライナーで少数の素数を出したいときなどに使えるかもしれません。

補助テーブルなし(MODEL)

SELECT n
FROM (SELECT n, flg FROM dual
      MODEL DIMENSION BY (2 n) MEASURES (0 flg)
      RULES (flg[FOR n FROM 2 TO 10000 INCREMENT 1] = COUNT(*)[n < LEAST(cv(), SQRT(10000)) AND MOD(cv(),n) = 0])
      -- LEAST(...) is an alternation of SQRT(cv()) which faces significant slowness in loops
WHERE  flg = 0;

再帰WITH

さて、MODEL以外でいい方法はないかと考えてみたところ、再帰WITH内でコレクション型を受け渡せば「結果の蓄積」を利用しながら計算できるんじゃないか、と思いつきました。再帰WITHの制限をしらべてみると、コレクション型の利用は問題なさげです。

The DISTINCT keyword or a GROUP BY clause

The model_clause

An aggregate function. However, analytic functions are permitted in the select list.

Subqueries that refer to query_name.

Outer joins that refer to query_name as the right table.

まずは、再帰WITHとコレクションを使って素直に作ってみます。この例では、「素数」を保持するためにコレクションを利用しています。動きとしてはコレクションの素数を用いて素数判定し、素数であればコレクションに追加する、を繰返します。シンプルなSQLですが、十万の対象で43秒となり、よいパフォーマンスとはいえません。

ちなみに、ここでは新しいタイプを作っていますが、すでに定義されているパプリックなテーブル型を見つけて使用すれば定義は不要となります²（KU$_OBJNUMSET とか ORA_MINING_NUMBER_NTなど）。

再帰＋コレクション(11gR2～)

create or replace type num_tbl as table of number;
/

WITH
    prime (n, c) AS
        (SELECT 2, num_tbl (2) FROM DUAL
         UNION ALL
         SELECT n + 1,
                CASE
                    WHEN    ((MOD (n + 1, 2) > 0 AND MOD (n + 1, 3) > 0 AND MOD (n + 1, 5) > 0) OR n + 1 IN (2, 3, 5))
                         AND (SELECT 1 FROM TABLE (c)
                              WHERE  MOD (n + 1, COLUMN_VALUE) = 0 AND ROWNUM = 1) IS NULL
                    THEN      c MULTISET UNION num_tbl (n + 1)
                    ELSE      c
                END
         FROM   prime
         WHERE  n < 100000)
SELECT n FROM prime, TABLE (c) WHERE n = COLUMN_VALUE;

Elapsed: 00:00:43.01

だいたい使い所がわかったところで、再帰WITHをエラトステネスの篩で作り変えてみます。ここでは、逆に「非素数」の保持にコレクションを利用しています。素数でない数値を重複を気にせずコレクションに追加していき、最終的に元の数値補助テーブルからMINUSで除外して素数リストを作成します³。COLLECT関数を含むサブクエリ部分は負荷が高いため、MEMBER OFで素数でないリストにすでにある数値を確認しスキップすることで不要な呼び出しを避けています。

結果、十万の対象で３秒半程度というMODELに匹敵するパフォーマンスとなりました。いやぁ何事もトライしてみるもんですねぇ。

エラトステネスの篩(再帰)

WITH
    nums AS
        (SELECT     LEVEL + 1 n
         FROM       DUAL
         WHERE      (MOD (LEVEL + 1, 2) > 0 AND MOD (LEVEL + 1, 3) > 0 AND MOD (LEVEL + 1, 5) > 0) OR LEVEL + 1 IN (2, 3, 5)
         CONNECT BY LEVEL < 100000),
    recur (c, nt, mx) AS
        (SELECT 1, num_tbl (1), CEIL (SQRT (MAX (n))) FROM nums
         UNION ALL
         SELECT c + 1,
                CASE
                    WHEN c + 1 MEMBER OF nt
                    THEN nt
                    ELSE nt MULTISET UNION (SELECT CAST (COLLECT (n) AS num_tbl)
                                            FROM   nums
                                            WHERE  n > c + 1 AND MOD (n, c + 1) = 0)
                END,
                mx
         FROM   recur
         WHERE  c < mx)
SELECT n FROM nums
MINUS
SELECT DISTINCT COLUMN_VALUE FROM recur, TABLE (nt) WHERE  c = mx;

Elapsed: 00:00:03.54

おわりに

やはり、言わずもがな行間参照ではMODELがフレキシブルかつシンプルです。再帰WITH+コレクションは、計算途中の結果の蓄積を利用できる点で非常に魅力的でやり方によっては使い勝手が良いかもしれません。ただしちょっとBuggyなのでHandle with careというところでしょうか。

以上です。

VMware上のCentOS7上の12gR2でかなり非力です。 ↩
探索SQL: select TYPE_NAME from all_coll_types where COLL_TYPE = 'TABLE' and ELEM_TYPE_NAME = 'NUMBER'; ↩
NOT EXISTSでももちろんいいですが、強制UNNESTが必要だったのでわかりやすくMINUSにしました。 ↩

素数を単一SQLクエリで計算するいくつかの方法とパフォーマンス(Oracle)

はじめに

自己結合

MODEL

再帰WITH

おわりに