Oracles MAXの大きな機能は何ですか？

Question

Oracle MAXのtime complexityは、テーブルの行数に対してO（1）、O（log n）または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操作するための計画を見ることができます。あなたはの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 

をやっている、OracleがインデックスにMIN/MAX scanを行うことができます。オプティマイザが選択する計画であれば、これはO（log n）操作です。実際の問題として、インデックスの高さが決して現実的に4または5を超えることはないので、これは機能的にはO（1）操作です。ここでの定数項が支配的になるでしょう。

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）操作に戻ります。 （11.2のように）Oracleは、Oracleの後続バージョンでは、この最適化が実装されるかもしれないし、これが戻って行くだろう、最初のブロックとインデックスもちろん

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 

の最後のブロックの両方のオプションのグラブを実装していませんO（log n）操作になる。もちろん、クエリを再作成して、別のクエリプランを取得してO（ログ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