表の行数に関して、Oracle MAX関数の時間計算量はO（1）、O（log n）、またはO（n）ですか？
質問する
2116 次
2 に答える
10
列にBツリーインデックスがある場合、答えはインデックスの最後（または最初）の行になるため、最大値の検索はO（log（n））です。値は、高さO（log（n））を持つBツリーの最も深いノードに格納されます。
最大値を決定するにはすべての行を読み取る必要があるため、インデックスがない場合はO（n）になります。
注：O（n）表記は定数を無視しますが、現実の世界ではこれらの定数を無視することはできません。ディスクからの読み取りとメモリからの読み取りの違いは、数桁です。インデックスの最初の値へのアクセスは主にRAMで実行される可能性がありますが、巨大なテーブルの全表スキャンは主にディスクから読み取る必要があります。
于 2012-06-28T17:01:53.060 に答える
7
現実的には、クエリ、テーブル定義、およびクエリ プランを指定せずに言うのは困難です。
計算している列にインデックスがないテーブルがある場合MAX、Oracle は完全なテーブル スキャンを実行する必要があります。テーブル内のすべてのブロックをスキャンする必要があるため、これは O(n) になります。これは、クエリ プランを見ればわかります。
CHAR(1000)100,000 行のテーブルを生成し、列を使用して行が適度に大きくなるようにします。
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インデックスに対して a を実行できます。それがオプティマイザーが選択する計画である場合、それは 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
于 2012-06-28T17:20:49.727 に答える