SQL（Sosuu reQuest Language）

#はじめに

この記事は社内用 Advent Calendar 2013 の12/11分の記事です。
特に社外秘な情報を扱うこともないので公開してみようと思います。

ゆるふわっとした内容なので、気軽に読んでいただけたら幸いです。

なお、画像は12/9のちんたくくんの記事、素人が Surface Pro でお絵描きしてみましたを読んで、素人がマウスでお絵かきしたときのクオリティと個人的に比較してみた時のものです。
なんか私の絵は邪悪なオーラを放ってますね。やっぱりSurface Proすごい！(｡￫‿◕｡)☆

#割れない強さ 変わらぬ想い

先日、高校時代の友人と飲みに行ったときの話です。

その友人はちょっと前に結婚をしたのですが、
ご祝儀に30011円という謎の金額が入っていたそうです。
一般的にはお札の枚数を二つに割れないよう奇数にするため、
30000円や50000円が多いかと思います。
さて、勘が良い方はお気づきでしょう。

そう。"素数"です。

30000は2で割れるじゃないか！
決して他の数で割ることの出来ない数、"素数"で二人をお祝いしようじゃないか！
という優しさの伝わってくる数字ですね。
素数。素敵ですね。

ん…？30011って本当に素数なのでしょうか。
ここは調べてみましょう。

というところから始まったこの企画。
SQL(Sosuu reQuest Language)

#どうせやるなら…

30011が素数かどうか調べるだけじゃもったいないので、
素数の一覧のテーブルを作って、どんな数字でも調べることが出来るようにしよう！

というわけで、素数の一覧テーブルを作ることにします。

今回の場合はおそらく小さい方から10000個の素数一覧を作れば十分でしょう。
足りなかったら増やせるようにしておけばいいでしょう。

#とりあえずやってみた

ある数字が素数か否かは、
「その数字が自身より小さい素数で割れるものがあるかどうかを調べ、
割れるものが1つもなかったら、その数字は素数である。」
として、判断していきます。

なので、

• 素数は結果用テーブルにINSERT
• 小さい順に数字をカウントアップしながら検証を行う
• そこまででリストアップされた結果用テーブルを使用して検証を行う

これでできるのではないかと。

…
そこまででリストアップされた結果用テーブルを使用して検証を行う…？

…最初の１つ目どうするの？

さ…最初の１つは"2”ってわかってるし、あらかじめ結果用テーブルに入れておきましょう！

と、言うわけで、何も考えずに書き始めてみましょう。

--素数一覧結果用テーブル
CREATE TABLE #PrimeNumbers
(
    SEQ             int   
,   PrimeNumber     bigint
)

--最初の素数である2は入れておく
INSERT INTO #PrimeNumbers VALUES(1, 2)

DECLARE 
    @RequiredPrimeNumberCount   int     = 10000
,   @PrimeNumberCount           int     = 1
,   @Number                     bigint  = 3
,   @TestNumber                 bigint
,   @HasFound                   bit    

--取得できた素数のカウントが要求された件数に達するまでループする
WHILE @PrimeNumberCount < @RequiredPrimeNumberCount
BEGIN
    
    --FLG初期化
    SET @HasFound = 0
    
    --これまでに見つけた素数で割れるかを順に検証する為にカーソルを回す
    DECLARE Cur CURSOR FOR
        SELECT
            PrimeNumber
        FROM #PrimeNumbers
        ORDER BY 
            SEQ
    
    OPEN Cur
    
    FETCH NEXT FROM Cur INTO @TestNumber
    
    -- ココから検証
    --割り切れる数が見つかるか、素数カーソルを最後まで回しきったら検証終了
    WHILE @HasFound = 0 AND @@FETCH_STATUS = 0 
    BEGIN
        IF @Number % @TestNumber = 0
        BEGIN
            --割り切れちゃったらFLGを立てる
            SET @HasFound = 1
        END
   
        FETCH NEXT FROM Cur INTO @TestNumber
    END
    
    CLOSE Cur
    DEALLOCATE Cur

    --検証した結果、割り切れる数が見つからなかった場合は素数の件数をカウントアップして、結果用テーブルにINSERT
    IF @HasFound = 0
    BEGIN
        SET @PrimeNumberCount += 1
        INSERT INTO #PrimeNumbers VALUES(@PrimeNumberCount, @Number)
    END
    --そして、また次の数字の検証へ…
    SET @Number += 1

END

--全件取得
SELECT
    *
FROM #PrimeNumbers
ORDER BY
    SEQ

--30011の確認
SELECT
    *
FROM #PrimeNumbers
WHERE
    PrimeNumber = 30011

DROP TABLE #PrimeNumbers

できました！
確かに30011は素数です！！
素敵！！！

#いや、素敵じゃないでしょ…

結果が取れたことに喜んでいましたが、

処理時間： 00：21:03 (hhss)

…待ってる間にへそでお茶が沸かせるレベルですね。

なんとかして普通に耐えられるくらいのパフォーマンスは発揮したいところ…
検証をいかに高速化するかが鍵ですね。

そもそもループの中でカーソルとか遅くなるの当たりまえですね。
だんだん件数増えていきますし。

カーソルを使わずに…

「その数字を割り切れる素数を見つけられたらそれは素数じゃない」

…あれ？WHEREで取得すればいいのでは…？

と、言うわけで、

ここにめちゃくちゃ重いクエリがあるじゃろ。

    --これまでに見つけた素数で割れるかを順に検証する為にカーソルを回す
    DECLARE Cur CURSOR FOR
        SELECT
            PrimeNumber
        FROM #PrimeNumbers
        ORDER BY 
            SEQ
    
    OPEN Cur
    
    FETCH NEXT FROM Cur INTO @TestNumber
    
    -- ココから検証
    --割り切れる数が見つかるか、素数カーソルを最後まで回しきったら検証終了
    WHILE @HasFound = 0 AND @@FETCH_STATUS = 0 
    BEGIN
        IF @Number % @TestNumber = 0
        BEGIN
            --割り切れちゃったらFLGを立てる
            SET @HasFound = 1
        END
   
        FETCH NEXT FROM Cur INTO @TestNumber
    END
    
    CLOSE Cur
    DEALLOCATE Cur

この部分を…

    SELECT
        @HasFound = 1
    FROM #PrimeNumbers MAIN
    WHERE
        @Number % MAIN.PrimeNumber = 0

こうじゃ！

見た目もかなりすっきりしましたね。

最初のアレは何だったのでしょうか。

これの結果は…

処理時間： 00：00:58 (hhss)

よし！！！
これならカップラーメン作るよりは早く結果が返ってきますね！

#まだまだ速くできるのでは

検証は
「その数字が自身より小さい素数で割れるものがあるかどうかを調べ、
割れるものが1つもなかったら、その数字は素数である。」
で行ってます。

…割れるものが 1つもなかったら …？

…EXISTSだ！！！

なんで最初はカーソルなんて使ったのでしょう。
私って、ほんとバカ。

WHEREのときは結果用テーブルを全件走査してましたが、
EXISTSを使えば一件取得できた時点で処理を抜けられるので、パフォーマンスアップが期待できますね。

というわけで…

    SELECT
        @HasFound = 1
    FROM #PrimeNumbers MAIN
    WHERE
        @Number % MAIN.PrimeNumber = 0

この部分を…

    
    SELECT
        @HasFound = 1
    WHERE EXISTS
    (
        SELECT
            *
        FROM #PrimeNumbers MAIN
        WHERE
            @Number % MAIN.PrimeNumber = 0
    )

こうじゃ！！！

結果は…

処理時間： 00：00：07 (hhss)

なんと！
先ほどのクエリの8倍速くらいですか！！
ここまで差が出るのですね！！！

なんで最初にあんな方法をとってしまったのか…

出来ると知らずに試してみたのですが、
FROM句を使わないでSELECT ○○ WHERE EXISTS～ってできるんですねー
まさか今回、こんな発見をできるとは思ってもいませんでしたが。
この記事書くことにしてよかった。

#最終的にこんなクエリが完成

GetPrimeNumbers.sql

CREATE TABLE #PrimeNumbers
(
    SEQ             int   
,   PrimeNumber     bigint
)

INSERT INTO #PrimeNumbers VALUES(1, 2)

DECLARE 
    @RequiredPrimeNumberCount   int     = 10000
,   @PrimeNumberCount           int     = 1
,   @Number                     bigint  = 3
,   @HasFound                   bit    

WHILE @PrimeNumberCount < @RequiredPrimeNumberCount
BEGIN

    SET @HasFound = 0
    
    SELECT
        @HasFound = 1
    WHERE EXISTS
    (
        SELECT
            *
        FROM #PrimeNumbers MAIN
        WHERE
            @Number % MAIN.PrimeNumber = 0
    )
       
    IF @HasFound = 0
    BEGIN
        SET @PrimeNumberCount += 1
        INSERT INTO #PrimeNumbers VALUES(@PrimeNumberCount, @Number)
    END
    
    SET @Number += 1

END

SELECT
    *
FROM #PrimeNumbers
ORDER BY
    SEQ
    
DROP TABLE #PrimeNumbers

これで素数の一覧を取得できます！

長い道のりでした。

おっと、そもそもご祝儀の30011円が素数の金額かどうかを調べていたのでしたね。

結果…

30011は3246番目の素数でした！

#まとめ

今回、これをやって感じたことですが、

• 意外とクエリでも数学ができるものだなぁ
• クエリでカーソル使うときはやっぱりパフォーマンスに注意しよう
• FROM句なくてもWHERE EXISTS～使えるなんて知らなかった
• WHERE句をちょっと変えるだけでパフォーマンスは格段に上がり得る
• 考えれば色々と案はでてくるものだ
• 正解を見つけたその先で得られるものがある

と言った感じでしょうか。
最後の方かっこいいですね。

クエリって実は思っている以上に色々なことが出来て、
こんなアホな使い方もあるんだなぁ。位に思っていただければ幸いです。

今回は何も調べず、思いついたこのアルゴリズムで素数判定を行いましたが、調べてみると、もっと賢い方法がたくさんあるみたいです。

Wikipedia - 素数判定

連番テーブル作ってエラトステネスの篩をクエリでやってみるっていうのも面白そうですね。
そのうち挑戦してみます。

また、「こんな面白くてアホで凄いクエリ書いたよ！」みたいな情報がありましたら、
是非情報共有をお願いします！
ここまで読んでくださってありがとうございました！

##追伸

ちなみに、本当はProject Eulerをクエリでやる。といった謎のチャレンジをしているところから始まりました。
もし、興味がある方はSQLやらC#やらで挑戦してみてください。

なお、7問目の「10001番目の素数を求める」という問題で正解しているので、
今回のクエリで取得できている結果セットは正しいはずです！

##さらに追伸

せっかくなので、ついでに素因数分解するクエリも書いてみましたが、
それを書くには余白が狭すぎる。