如果列上有B树索引,则查找最大值为O(log(n)),因为答案将是索引的最后一行(或第一行).值存储在B树的最深节点中,其具有高度O(log(n)).
如果没有索引,则为O(n),因为必须读取所有行以确定最大值.
注意:O(n)表示法忽略常量,但在现实世界中,这些常量不能被忽略.从磁盘读取和从内存读取之间的差异是几个数量级.访问索引的第一个值可能主要在RAM中执行,而大表的全表扫描需要主要从磁盘读取.
实际上,如果不指定查询,表定义和查询计划,很难说.
如果您有一个没有索引的表,那么您需要对其进行计算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 n)操作.当然,作为一个实际问题,这在功能上是一个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 n)的行为独立.但是如果你有两个MIN并且MAX在同一个查询中,突然你又回到了O(n)操作.Oracle(截至11.2)尚未实现选项同时获取索引的第一个块和最后一个块
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 n)操作.当然,您也可以重写查询以获得不同的查询计划,该计划可以追溯到O(log n)
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