Oracles函数的大O是什么？

Question

Oracle MAX函数的对数是O(1)、O(log )还是O(n)相对于表中的行数？

Answer 1

如果您在列上有一个B树索引，那么查找最大值是O(log(n))，因为答案将是索引的最后(或第一)行。值存储在高度为O(log(n))的B树的最深节点中。

如果没有索引，它是O(n)，因为必须读取所有行才能确定最大值。

注意: O(n)表示法忽略了常量，但在现实世界中，这些常量是不可忽略的。从磁盘读取和从内存读取之间的差异是几个数量级。访问索引的第一个值可能主要在RAM中执行，而大表的全表扫描将需要主要从磁盘读取。

Answer 2

实际上，如果不指定查询、表定义和查询计划，就很难说。

如果您的表对要计算MAX的列没有索引，Oracle将不得不执行全表扫描。这将是O(n)，因为您必须扫描表中的每个块。您可以通过查看查询计划来了解这一点。

我们将生成一个包含100,000行的表，并使用CHAR(1000)列确保这些行相当大

SQL> create table foo( col1 number, col2 char(1000) );

Table created.

SQL> insert into foo
  2    select level, lpad('a',1000)
  3      from dual
  4   connect by level <= 100000;

100000 rows created.

现在，我们可以查看基本MAX操作的计划。这是一个全表扫描( O(n)操作)

SQL> set autotrace on;
SQL> select max(col1)
  2    from foo;

 MAX(COL1)
----------
    100000


Execution Plan
----------------------------------------------------------
Plan hash value: 1342139204

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |    13 |  4127   (1)| 00:00:50 |
|   1 |  SORT AGGREGATE    |      |     1 |    13 |            |          |
|   2 |   TABLE ACCESS FULL| FOO  |   106K|  1350K|  4127   (1)| 00:00:50 |
---------------------------------------------------------------------------

Note
-----
   - dynamic sampling used for this statement (level=2)


Statistics
----------------------------------------------------------
         29  recursive calls
          1  db block gets
      14686  consistent gets
          0  physical reads
        176  redo size
        527  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

如果在计算MAX的列上创建索引，Oracle可以对该索引执行MIN/MAX scan。如果这是优化器选择的计划，那么这是一个O(log )操作。当然，作为一个实际问题，这在功能上是一个O(1)操作，因为索引的高度实际上永远不会超过4或5--这里的常量项将占主导地位。

SQL> create index idx_foo_col1
  2      on foo( col1 );

Index created.

SQL> select max(col1)
  2    from foo;

 MAX(COL1)
----------
    100000


Execution Plan
----------------------------------------------------------
Plan hash value: 817909383

-------------------------------------------------------------------------------------------
| Id  | Operation                  | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |              |     1 |    13 |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE            |              |     1 |    13 |            |          |
|   2 |   INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 |     1 |    13 |     2   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------

Note
-----
   - dynamic sampling used for this statement (level=2)

Statistics
----------------------------------------------------------
          5  recursive calls
          0  db block gets
         83  consistent gets
          1  physical reads
          0  redo size
        527  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

但是事情变得更难了。MIN和MAX各自具有相同的O(log )行为。但是，如果您在同一查询中同时包含MIN和MAX，那么您会突然回到O(n)操作。Oracle (从11.2开始)还没有实现选项grab索引的第一个块和最后一个块

SQL> ed
Wrote file afiedt.buf

  1  select min(col1), max(col1)
  2*   from foo
SQL> /

 MIN(COL1)  MAX(COL1)
---------- ----------
         1     100000


Execution Plan
----------------------------------------------------------
Plan hash value: 1342139204

---------------------------------------------------------------------------
| Id  | Operation          | Name | Rows  | Bytes | Cost (%CPU)| Time     |
---------------------------------------------------------------------------
|   0 | SELECT STATEMENT   |      |     1 |    13 |  4127   (1)| 00:00:50 |
|   1 |  SORT AGGREGATE    |      |     1 |    13 |            |          |
|   2 |   TABLE ACCESS FULL| FOO  |   106K|  1350K|  4127   (1)| 00:00:50 |
---------------------------------------------------------------------------

Note
-----
   - dynamic sampling used for this statement (level=2)


Statistics
----------------------------------------------------------
          4  recursive calls
          0  db block gets
      14542  consistent gets
          0  physical reads
          0  redo size
        601  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

当然，在Oracle的后续版本中，可能会实现此优化，并且这将恢复为O(log )操作。当然，您也可以重写查询，以获得恢复为O(log )的不同查询计划

SQL> ed
Wrote file afiedt.buf

  1  select (select min(col1) from foo) min,
  2         (select max(col1) from foo) max
  3*   from dual
SQL>
SQL> /

       MIN        MAX
---------- ----------
         1     100000


Execution Plan
----------------------------------------------------------
Plan hash value: 3561244922

-------------------------------------------------------------------------------------------
| Id  | Operation                  | Name         | Rows  | Bytes | Cost (%CPU)| Time     |
-------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT           |              |     1 |       |     2   (0)| 00:00:01 |
|   1 |  SORT AGGREGATE            |              |     1 |    13 |            |          |
|   2 |   INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 |     1 |    13 |     2   (0)| 00:00:01 |
|   3 |  SORT AGGREGATE            |              |     1 |    13 |            |          |
|   4 |   INDEX FULL SCAN (MIN/MAX)| IDX_FOO_COL1 |     1 |    13 |     2   (0)| 00:00:01 |
|   5 |  FAST DUAL                 |              |     1 |       |     2   (0)| 00:00:01 |
-------------------------------------------------------------------------------------------


Note
-----
   - dynamic sampling used for this statement (level=2)


Statistics
----------------------------------------------------------
          7  recursive calls
          0  db block gets
        166  consistent gets
          0  physical reads
          0  redo size
        589  bytes sent via SQL*Net to client
        523  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed