用SQL計算100以內的質數
?
??? 蠻有意思的一段SQL，拿來看一下。
?
?
??? 以前寫過一篇文章，描述如何使用PL/SQL來計算100以內的質數，今天重翻那篇文章的時候，突然想到，能不能用SQL來實現同樣的功能。
?
?
?
?
?
??? 其實這個功能用PLSQL實現最簡單，思路也很清晰，判斷一個數是否是質數，只需要檢查這個數能否被比它小的質數整除就可以了。但是這種操作通過SQL來實現就十分的困難，因此這里通過另外一種方式來實現這個功能——構造。
?
通過查詢100以內的數，去掉所有的合數，剩下的就是質數了：
?
SQL> WITH T
? 2 AS
? 3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 100)
? 4 SELECT RN FROM T
? 5 WHERE RN > 1
? 6 MINUS
? 7 SELECT A.RN * B.RN FROM T A, T B
? 8 WHERE A.RN <= B.RN
? 9 AND A.RN > 1
?10 AND B.RN > 1;
?
??????? RN
----------
???????? 2
???????? 3
???????? 5
???????? 7
??????? 11
??????? 13
??????? 17
??????? 19
??????? 23
??????? 29
??????? 31
??????? 37
??????? 41
??????? 43
??????? 47
??????? 53
??????? 59
??????? 61
??????? 67
??????? 71
??????? 73
??????? 79
??????? 83
??????? 89
??????? 97
?
25 rows selected.
?
?
?
但是這種方法的效率明顯要比PL/SQL的效率要低，如果取10000以內的質數：
?
?
SQL> SET TIMING ON
SQL> SET AUTOT TRACE STAT
SQL> WITH T
? 2 AS
? 3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
? 4 SELECT RN FROM T
? 5 WHERE RN > 1
? 6MINUS
? 7 SELECT A.RN * B.RN FROM T A, T B
? 8 WHERE A.RN <= B.RN
? 9 AND A.RN > 1
?10AND B.RN > 1;
?
1229 rows selected.
?
Elapsed: 00:02:41.54
?
Statistics
----------------------------------------------------------
??????? 511 recursive calls
???????? 81 db block gets
???? 180002 consistent gets
????? 65131 physical reads
??????? 648 redo size
????? 17139 bytes sent via SQL*Net to client
?????? 1276 bytes received via SQL*Net from client
???????? 83 SQL*Net roundtrips to/from client
????????? 2 sorts (memory)
????????? 1 sorts (disk)
?????? 1229 rows processed
?
?
這個SQL執行了2分半種以上，當然這個SQL還可以進行一下優化，比如A的取值可以小于10000的開方，而B的取值可以小于10000除以最小的質數：
?
?
SQL> WITH T
? 2 AS
? 3 (SELECT ROWNUM RN FROM DUAL CONNECT BY LEVEL < 10000)
? 4 SELECT RN FROM T
? 5 WHERE RN > 1
? 6 MINUS
? 7 SELECT A.RN * B.RN FROM T A, T B
? 8 WHERE A.RN <= B.RN
? 9AND A.RN > 1
?10 AND A.RN <= 100
?11 AND B.RN > 1
?12 AND B.RN <= 5000;
?
1229 rows selected.
?
Elapsed: 00:00:00.78
?
Statistics
----------------------------------------------------------
????????? 2 recursive calls
???????? 23 db block gets
?????? 1820 consistent gets
???????? 16 physical reads
??????? 692 redo size
????? 17139 bytes sent via SQL*Net to client
?????? 1276 bytes received via SQL*Net from client
???????? 83 SQL*Net roundtrips to/from client
????????? 3 sorts (memory)
????????? 0 sorts (disk)
?????? 1229 rows processed
?
?
優化后，SQL的執行效率提高了3個數量級，其實這個SQL仍然是可以優化的，考慮除了2以外，所有的質數均為奇數：
?
?
SQL> WITH T
? 2 AS
? 3 (SELECT ROWNUM * 2 + 1 RN FROM DUAL CONNECT BY LEVEL < 4999)
? 4 SELECT 2 FROM DUAL
? 5 UNION ALL
? 6 (
? 7 SELECT RN FROM T
? 8 WHERE RN > 1
? 9 MINUS
?10 SELECT A.RN * B.RN FROM T A, T B
?11 WHERE A.RN <= B.RN
?12 AND A.RN > 1
?13 AND A.RN <= 100
?14 AND B.RN > 1
?15 AND B.RN <= 5000
?16 )
?17 ;
?
1229 rows selected.
?
Elapsed: 00:00:00.25
?
Statistics
----------------------------------------------------------
????????? 2 recursive calls
???????? 15 db block gets
??????? 512 consistent gets
????????? 8 physical reads
??????? 648 redo size
????? 17138 bytes sent via SQL*Net to client
?????? 1276 bytes received via SQL*Net from client
???????? 83 SQL*Net roundtrips to/from client
????????? 3 sorts (memory)
????????? 0 sorts (disk)
?????? 1229 rows processed
?
雖然通過SQL優化已經將極大的提高了效率，但是和PLSQL比，效率仍然相去甚遠：
?
?
?
SQL> DECLARE
? 2 TYPE T_RECORD IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
? 3 V_RESULT T_RECORD;
? 4 I NUMBER DEFAULT 3;
? 5 N NUMBER DEFAULT 0;
? 6 BEGIN
? 7 --DBMS_OUTPUT.PUT_LINE(2);
? 8 V_RESULT(1) := 3;
? 9 WHILE(I < 10000) LOOP
?10 FOR J IN 1..V_RESULT.COUNT LOOP
?11 IF V_RESULT(J) * V_RESULT(J) > I THEN
?12 --DBMS_OUTPUT.PUT_LINE(I);
?13 V_RESULT(V_RESULT.COUNT + 1) := I;
?14 EXIT;
?15 END IF;
?16 IF TRUNC(I/V_RESULT(J)) = I/V_RESULT(J) THEN
?17 EXIT;
?18END IF;
?19 END LOOP;
?20 IF N = 2 THEN
?21 I := I + 4;
?22 N := 1;
?23 ELSE
?24 I := I + 2;
?25 N := N + 1;
?26 END IF;
?27 END LOOP;
?28 V_RESULT(0) := 2;
?29 END;
?30 /
?
PL/SQL procedure successfully completed.
?
Elapsed: 00:00:00.04
?
這說明使用SQL并不一定就是最佳選擇，有的時候使用PLSQL效率反而會更高。使用合適的方法做適合的事情，一味追求使用單條SQL實現很可能會損失性能。
?
?