使用纯 Oracle SQL 有更好的斐波那契数列生成器吗？

Question

我想知道是否有任何方法可以生成在简单性和效率方面胜过我写的这个斐波那契数列：

WITH d (seq) AS
       (SELECT     LEVEL
        FROM       DUAL
        CONNECT BY LEVEL < 195)
SELECT   seq
        ,fib
FROM     d
MODEL
  DIMENSION BY(seq)
  MEASURES(0 AS fib)
  RULES
    (fib [1] = 0,
    fib [2] = 1,
    fib [seq BETWEEN 3 AND 194] = fib[CV(seq) - 2] + fib[CV(seq) - 1],
    fib [seq > 194] = NULL)
ORDER BY 1
/
Execution Plan
----------------------------------------------------------
Plan hash value: 2245903385

---------------------------------------------------------------------------------------
| Id  | Operation                      | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT               |      |     1 |    13 |     2   (0)| 00:00:01 |
|   1 |  SQL MODEL ORDERED             |      |     1 |    13 |            |          |
|   2 |   VIEW                         |      |     1 |    13 |     2   (0)| 00:00:01 |
|*  3 |    CONNECT BY WITHOUT FILTERING|      |       |       |            |          |
|   4 |     FAST DUAL                  |      |     1 |       |     2   (0)| 00:00:01 |
---------------------------------------------------------------------------------------

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

   3 - filter(LEVEL<195)


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          0  consistent gets
          0  physical reads
          0  redo size
       4798  bytes sent via SQL*Net to client
        500  bytes received via SQL*Net from client
         14  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
        194  rows processed

SQL>

注意：LEVEL < 195 不是任意选择的，较高的值会使算法失去精度，所以我决定不包括它们以仅保持正确的结果。

Answer 1

您可以使用递归子查询分解子句：

WITH fib ( lvl, value, next ) AS (
  SELECT 1, 0, 1
  FROM DUAL
UNION ALL
  SELECT lvl + 1, next, value + next
  FROM fib
  WHERE lvl < 195
)
SELECT lvl, value FROM fib

Answer 2

像这样的东西应该（很多？）更快：

with
     constants ( x, y, z ) as (
       select 0.5 * ( 1 + sqrt(5) ),
              0.5 * ( 1 - sqrt(5) ),
              sqrt(5)
       from   dual
     )
select level as seq, round( ( power(x, level - 1) - power(y, level - 1) ) / z ) as fib
from   constants
connect by level < 195
;

重点是，你不需要使用递归公式；条款可以写成封闭形式。由于计算机不能用实数进行算术运算，只能用有理数近似值，所以我需要添加一个 ROUND(...) 但即便如此，这应该比递归方法更快。

EDIT：应 OP 的要求，我跟踪了这段代码的执行。 我没有看到 OP 在下面的评论中提到的递归调用。

Execution Plan
----------------------------------------------------------
Plan hash value: 1236776825

-----------------------------------------------------------------------------
| Id  | Operation                    | Name | Rows  | Cost (%CPU)| Time     |
-----------------------------------------------------------------------------
|   0 | SELECT STATEMENT             |      |     1 |     2   (0)| 00:00:01 |
|*  1 |  CONNECT BY WITHOUT FILTERING|      |       |            |          |
|   2 |   FAST DUAL                  |      |     1 |     2   (0)| 00:00:01 |
-----------------------------------------------------------------------------

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

   1 - filter(LEVEL<195)


Statistics
----------------------------------------------------------
          0  recursive calls
          0  db block gets
          0  consistent gets
          0  physical reads
          0  redo size
       6306  bytes sent via SQL*Net to client
        684  bytes received via SQL*Net from client
         14  SQL*Net roundtrips to/from client
          1  sorts (memory)
          0  sorts (disk)
        194  rows processed

编辑 #2

我怀疑在递归查询中简单生成级别可能很昂贵。类似生成但较小的整数序列的交叉连接可能会更快一些。代码看起来更复杂（当然）；不过，唯一的变化是我产生力量的方式。

with
     constants ( x, y, z ) as (
       select 0.5 * ( 1 + sqrt(5) ),
              0.5 * ( 1 - sqrt(5) ),
              sqrt(5)
       from   dual
     ),
     powers ( n ) as (
       select 14 * a.p + b.q
       from   (select level - 1 p from dual connect by level <= 14) a
              cross join
              (select level - 1 q from dual connect by level <= 14) b
     )
select n + 1 as seq, round( ( power(x, n) - power(y, n) ) / z ) as fib
from   constants cross join powers
where  n < 195
;

Answer 3

为了简单起见，查询可以依赖 MODEL 的内置功能（ITERATE () 和 ITERATION_NUMBER）：

select * from dual
model
  dimension by (0 seq)
  measures (0 val)
  rules iterate (195) 
  (
     val[iteration_number] = val[iteration_number-1] + val[iteration_number-2],
     val[2] = 1, 
     val[1] = 0, 
     val[0] = 0
  )
;

使用纯 Oracle SQL 有更好的斐波那契数列生成器吗？

Any better Fibonacci series generator using pure Oracle SQL?

sql

oracle

algorithm

optimization

fibonacci