sql求解200万内质数各种算法点评

〇〇 · 发表于 2014-3-10 09:56

lastwinner 发表于 2014-3-10 03:08
7、挑战200万
正当我们信心满满的将参数改为200万，准备泡上一杯奶茶边品边等结果时……

with nr as (select 2000000 r from dual),
*
第 1 行出现错误:
ORA-01013: 用户请求取消当前的操作

已用时间: 00: 03: 06.66

还是工具不力

oracle_cj · 发表于 2014-3-10 10:01

nice job

〇〇 · 发表于 2014-3-10 10:01

〇〇发表于 2014-3-10 09:56
with nr as (select 2000000 r from dual),
*
第 1 行出现错误:

奇怪,20万也不行
with nr as (select 200000 r from dual),
*
第 1 行出现错误:
ORA-01013: 用户请求取消当前的操作

已用时间: 00: 02: 37.42

SQL> show rel
release 1102000200

lastwinner · 发表于 2014-3-10 12:13

〇〇发表于 2014-3-10 09:56
with nr as (select 2000000 r from dual),
*
第 1 行出现错误:

可能和数据库的版本有关，我的是11.2.0.1

lastwinner · 发表于 2014-3-11 01:53

〇〇发表于 2014-3-10 10:01
奇怪,20万也不行
with nr as (select 200000 r from dual),
*

又想了想，可能和你内存大小设定有关

newkid · 发表于 2014-3-11 02:22

7楼的在我这里倒不会报内存不足的错误，但是跑了36秒。

lastwinner · 发表于 2014-3-11 12:42

newkid 发表于 2014-3-11 02:22
7楼的在我这里倒不会报内存不足的错误，但是跑了36秒。

嗯，你内存分配得多吧，我的分配得少，算100万以内没问题，200万就内存不足了
connect by构造较大序列的效率实在是不高

〇〇 · 发表于 2014-3-11 20:14

lastwinner 发表于 2014-3-10 03:08
7、挑战200万
正当我们信心满满的将参数改为200万，准备泡上一杯奶茶边品边等结果时……

找了一台256G内存的服务器，也不快，你的执行计划如何
我的如下：

SQL> conn system/abcABC123456@10.6.109.87/wf
已连接。
SQL> show rel
release 1201000100
SQL> set autot on
SQL> var n number
SQL> exec :n:=2000000

PL/SQL 过程已成功完成。

SQL> with b as (select 1 r from dual union all select 2 from dual),
  2  c as (select rownum from b,b,b,b,b),
  3  d as (select rownum from c,c,c,c),
  4  e as (select rownum rn from d), --只需要一半
  5  t0 AS (
  6    SELECT 2*rn+1 rn FROM e where rn <= (:n)/2-1 --原SQL为(:n)/2-1-1有误，特做此更正——by lastwinner
  7    ),
  8  t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0 and mod(rn,11)<>0 and mod(rn,13)<>0 and mod(rn,17)<>0 and mod(rn,19)<>0)
  9  SELECT COUNT(*)+1+7 --2，3，5，7，11，13，17，19
10    FROM (SELECT rn from t
11          MINUS
12          SELECT t1.rn * t2.rn
13          FROM t t1, t t2
14          WHERE t1.rn <= t2.rn
15                AND t1.rn BETWEEN 21 AND (SELECT SQRT(:n) FROM DUAL)
16                AND t1.rn * t2.rn <:n
17       )
18  ;

COUNT(*)+1+7--2，3，5，7，11，13，17，19
----------------------------------------
                              148933

执行计划
----------------------------------------------------------
Plan hash value: 1273601935

------------------------------------------------------------------------------------------------------------------
| Id  | Operation                   | Name                   | Rows  | Bytes |TempSpc| Cost (%CPU)| Time |
------------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT          |                         |    1 |    |    | 27M  (1)| 00:18:02 |
| 1 |  TEMP TABLE TRANSFORMATION |                         |    |    |    |          |  |
| 2 | LOAD AS SELECT          | SYS_TEMP_0FD9D660B_C88BEC |    |    |    |          |  |
| 3 | UNION-ALL                |                         |    |    |    |          |  |
| 4 |    FAST DUAL             |                         |    1 |    |    |    2 (0)| 00:00:01 |
| 5 |    FAST DUAL             |                         |    1 |    |    |    2 (0)| 00:00:01 |
| 6 | LOAD AS SELECT          | SYS_TEMP_0FD9D660C_C88BEC |    |    |    |          |  |
| 7 | COUNT                   |                         |    |    |    |          |  |
| 8 |    MERGE JOIN CARTESIAN    |                         | 32 |    |    | 62 (0)| 00:00:01 |
| 9 |    MERGE JOIN CARTESIAN |                         | 16 |    |    | 30 (0)| 00:00:01 |
|  10 |    MERGE JOIN CARTESIAN |                         |    8 |    |    | 14 (0)| 00:00:01 |
|  11 |       MERGE JOIN CARTESIAN  |                         |    4 |    |    |    6 (0)| 00:00:01 |
|  12 |       VIEW                |                         |    2 |    |    |    2 (0)| 00:00:01 |
|  13 |       TABLE ACCESS FULL | SYS_TEMP_0FD9D660B_C88BEC |    2 | 26 |    |    2 (0)| 00:00:01 |
|  14 |       BUFFER SORT       |                         |    2 |    |    |    6 (0)| 00:00:01 |
|  15 |       VIEW             |                         |    2 |    |    |    2 (0)| 00:00:01 |
|  16 |          TABLE ACCESS FULL  | SYS_TEMP_0FD9D660B_C88BEC |    2 | 26 |    |    2 (0)| 00:00:01 |
|  17 |       BUFFER SORT          |                         |    2 |    |    | 12 (0)| 00:00:01 |
|  18 |       VIEW                |                         |    2 |    |    |    2 (0)| 00:00:01 |
|  19 |       TABLE ACCESS FULL | SYS_TEMP_0FD9D660B_C88BEC |    2 | 26 |    |    2 (0)| 00:00:01 |
|  20 |    BUFFER SORT          |                         |    2 |    |    | 28 (0)| 00:00:01 |
|  21 |       VIEW                |                         |    2 |    |    |    2 (0)| 00:00:01 |
|  22 |       TABLE ACCESS FULL | SYS_TEMP_0FD9D660B_C88BEC |    2 | 26 |    |    2 (0)| 00:00:01 |
|  23 |    BUFFER SORT          |                         |    2 |    |    | 60 (0)| 00:00:01 |
|  24 |    VIEW                |                         |    2 |    |    |    2 (0)| 00:00:01 |
|  25 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D660B_C88BEC |    2 | 26 |    |    2 (0)| 00:00:01 |
|  26 | LOAD AS SELECT          | SYS_TEMP_0FD9D660D_C88BEC |    |    |    |          |  |
|* 27 | VIEW                   |                         |  1048K| 13M|    | 67660 (1)| 00:00:03 |
|  28 |    COUNT                   |                         |    |    |    |          |  |
|  29 |    VIEW                   |                         |  1048K|    |    | 67660 (1)| 00:00:03 |
|  30 |    COUNT                |                         |    |    |    |          |  |
|  31 |       MERGE JOIN CARTESIAN  |                         |  1048K|    |    | 67660 (1)| 00:00:03 |
|  32 |       MERGE JOIN CARTESIAN |                         | 32768 |    |    |  2114 (0)| 00:00:01 |
|  33 |       MERGE JOIN CARTESIAN|                         |  1024 |    |    | 66 (0)| 00:00:01 |
|  34 |          VIEW             |                         | 32 |    |    |    2 (0)| 00:00:01 |
|  35 |          TABLE ACCESS FULL | SYS_TEMP_0FD9D660C_C88BEC | 32 | 416 |    |    2 (0)| 00:00:01 |
|  36 |          BUFFER SORT       |                         | 32 |    |    | 66 (0)| 00:00:01 |
|  37 |          VIEW             |                         | 32 |    |    |    2 (0)| 00:00:01 |
|  38 |          TABLE ACCESS FULL| SYS_TEMP_0FD9D660C_C88BEC | 32 | 416 |    |    2 (0)| 00:00:01 |
|  39 |       BUFFER SORT       |                         | 32 |    |    |  2112 (0)| 00:00:01 |
|  40 |          VIEW             |                         | 32 |    |    |    2 (0)| 00:00:01 |
|  41 |          TABLE ACCESS FULL | SYS_TEMP_0FD9D660C_C88BEC | 32 | 416 |    |    2 (0)| 00:00:01 |
|  42 |       BUFFER SORT       |                         | 32 |    |    | 67658 (1)| 00:00:03 |
|  43 |       VIEW             |                         | 32 |    |    |    2 (0)| 00:00:01 |
|  44 |          TABLE ACCESS FULL  | SYS_TEMP_0FD9D660C_C88BEC | 32 | 416 |    |    2 (0)| 00:00:01 |
|  45 | SORT AGGREGATE          |                         |    1 |    |    |          |  |
|  46 | VIEW                   |                         |  1048K|    |    | 27M  (1)| 00:17:59 |
|  47 |    MINUS                   |                         |    |    |    |          |  |
|  48 |    SORT UNIQUE          |                         |  1048K| 13M| 20M|  5484 (1)| 00:00:01 |
|  49 |    VIEW                |                         |  1048K| 13M|    | 507 (1)| 00:00:01 |
|  50 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D660D_C88BEC |  1048K| 13M|    | 507 (1)| 00:00:01 |
|  51 |    SORT UNIQUE          |                         |  2748M| 66G| 82G| 27M  (1)| 00:17:59 |
|  52 |    MERGE JOIN          |                         |  2748M| 66G|    | 151K (93)| 00:00:06 |
|  53 |       SORT JOIN          |                         |  1048K| 13M| 40M|  5484 (1)| 00:00:01 |
|* 54 |       VIEW                |                         |  1048K| 13M|    | 507 (1)| 00:00:01 |
|  55 |       TABLE ACCESS FULL | SYS_TEMP_0FD9D660D_C88BEC |  1048K| 13M|    | 507 (1)| 00:00:01 |
|  56 |       FAST DUAL          |                         |    1 |    |    |    2 (0)| 00:00:01 |
|* 57 |       FILTER             |                         |    |    |    |          |  |
|* 58 |       SORT JOIN          |                         |  1048K| 13M| 40M|  5484 (1)| 00:00:01 |
|* 59 |       VIEW             |                         |  1048K| 13M|    | 507 (1)| 00:00:01 |
|  60 |          TABLE ACCESS FULL  | SYS_TEMP_0FD9D660D_C88BEC |  1048K| 13M|    | 507 (1)| 00:00:01 |
------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

  27 - filter(MOD(2*"RN"+1,3)<>0 AND MOD(2*"RN"+1,5)<>0 AND MOD(2*"RN"+1,7)<>0 AND MOD(2*"RN"+1,11)<>0
            AND MOD(2*"RN"+1,13)<>0 AND MOD(2*"RN"+1,17)<>0 AND MOD(2*"RN"+1,19)<>0 AND "RN"<=TO_NUMBER(:N)/2-1)
  54 - filter("T1"."RN">=21 AND "T1"."RN"<= (SELECT SQRT(TO_NUMBER(:N)) FROM "SYS"."DUAL" "DUAL"))
  57 - filter("T1"."RN"*"T2"."RN"<TO_NUMBER(:N))
  58 - access("T1"."RN"<="T2"."RN")
   filter("T1"."RN"<="T2"."RN")
  59 - filter("T2"."RN">=21)

统计信息
----------------------------------------------------------
      29  recursive calls
      551  db block gets
   1626  consistent gets
      522  physical reads
   1848  redo size
      381  bytes sent via SQL*Net to client
      472  bytes received via SQL*Net from client
      2  SQL*Net roundtrips to/from client
      11  sorts (memory)
      0  sorts (disk)
      1  rows processed

SQL> SQL>

〇〇 · 发表于 2014-3-11 20:15

这个写法是故意的吗？
AND (SELECT SQRT(:n) FROM DUAL)

〇〇 · 发表于 2014-3-11 20:28

〇〇发表于 2014-3-11 20:15
这个写法是故意的吗？
AND (SELECT SQRT(:n) FROM DUAL)

相当于no merge?

SQL> with
  2  t0 AS (
  3    SELECT 2*level+1 rn FROM dual connect by level <= (:n)/2-1 --原SQL为(:n)/2-1-1有误，特做此更正——by lastwinner
  4    ),
  5  t as(SELECT rn from t0 where mod(rn,3)<>0 and mod(rn,5)<>0 and mod(rn,7)<>0 and mod(rn,11)<>0 and mod(rn,13)<>0 and mod(rn,17)<>0 and mod(rn,19)<>0)
  6  SELECT COUNT(*)+1+7 --2，3，5，7，11，13，17，19
  7    FROM (SELECT rn from t
  8          MINUS
  9          SELECT t1.rn * t2.rn
10          FROM t t1, t t2
11          WHERE t1.rn <= t2.rn
12                AND t1.rn BETWEEN 21 AND (SELECT SQRT(:n) FROM DUAL)
13                AND t1.rn * t2.rn <:n
14       )
15  ;

COUNT(*)+1+7--2，3，5，7，11，13，17，19
----------------------------------------
                              148933

已用时间:  00: 00: 16.55

执行计划
----------------------------------------------------------
Plan hash value: 1960010894

-------------------------------------------------------------------------------------------------------------
| Id  | Operation                      | Name                   | Rows  | Bytes | Cost (%CPU)| Time    |
-------------------------------------------------------------------------------------------------------------
| 0 | SELECT STATEMENT             |                         |    1 |    | 10 (0)| 00:00:01 |
| 1 |  TEMP TABLE TRANSFORMATION    |                         |    |    |          |       |
| 2 | LOAD AS SELECT             | SYS_TEMP_0FD9D6616_C88BEC |    |    |          |       |
|*  3 | VIEW                      |                         |    1 | 13 |    2 (0)| 00:00:01 |
|*  4 |    CONNECT BY WITHOUT FILTERING|                         |    |    |          |       |
| 5 |    FAST DUAL                |                         |    1 |    |    2 (0)| 00:00:01 |
| 6 | SORT AGGREGATE             |                         |    1 |    |          |       |
| 7 | VIEW                      |                         |    1 |    |    8 (0)| 00:00:01 |
| 8 |    MINUS                      |                         |    |    |          |       |
| 9 |    SORT UNIQUE             |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  10 |    VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  11 |       TABLE ACCESS FULL       | SYS_TEMP_0FD9D6616_C88BEC |    1 | 13 |    2 (0)| 00:00:01 |
|  12 |    SORT UNIQUE             |                         |    1 | 26 |    6 (0)| 00:00:01 |
|  13 |    NESTED LOOPS             |                         |    1 | 26 |    4 (0)| 00:00:01 |
|* 14 |       VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  15 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D6616_C88BEC |    1 | 13 |    2 (0)| 00:00:01 |
|  16 |       FAST DUAL             |                         |    1 |    |    2 (0)| 00:00:01 |
|* 17 |       VIEW                   |                         |    1 | 13 |    2 (0)| 00:00:01 |
|  18 |       TABLE ACCESS FULL    | SYS_TEMP_0FD9D6616_C88BEC |    1 | 13 |    2 (0)| 00:00:01 |
-------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

3 - filter(MOD("RN",3)<>0 AND MOD("RN",5)<>0 AND MOD("RN",7)<>0 AND MOD("RN",11)<>0 AND
            MOD("RN",13)<>0 AND MOD("RN",17)<>0 AND MOD("RN",19)<>0)
4 - filter(LEVEL<=TO_NUMBER(:N)/2-1)
  14 - filter("T1"."RN">=21 AND "T1"."RN"<= (SELECT SQRT(TO_NUMBER(:N)) FROM "SYS"."DUAL" "DUAL"))
  17 - filter("T1"."RN"<="T2"."RN" AND "T1"."RN"*"T2"."RN"<TO_NUMBER(:N) AND "T2"."RN">=21)

统计信息
----------------------------------------------------------
      13  recursive calls
      535  db block gets
124484  consistent gets
      520  physical reads
      660  redo size
      381  bytes sent via SQL*Net to client
      472  bytes received via SQL*Net from client
      2  SQL*Net roundtrips to/from client
      3  sorts (memory)
      0  sorts (disk)
      1  rows processed

[精华] sql求解200万内质数各种算法点评