Qual è la funzione O grande di Oracle MAX?

Question

della funzione Oracle MAX O (1), O (log n) o O (n) rispetto al numero di righe in una tabella?

Answer 1

Se nella colonna è presente un indice B-tree, la ricerca del valore massimo è O (log (n)) poiché la risposta sarà l'ultima (o prima) riga dell'indice. I valori sono memorizzati nei nodi più profondi dell'albero B che ha un'altezza O (log (n)).

Senza un indice è O (n) perché tutte le righe devono essere lette per determinare il valore massimo.

---

Nota: la notazione O (n) ignora le costanti ma nel mondo reale queste costanti non possono essere ignorate. La differenza tra leggere dal disco e leggere dalla memoria è di diversi ordini di grandezza. È probabile che l'accesso al primo valore di un indice venga eseguito principalmente nella RAM, mentre una scansione completa della tabella di una tabella enorme dovrà essere letta principalmente dal disco.

Answer 2

Realisticamente, è difficile dire senza specificare una query, una definizione di tabella e un piano di query.

Se si dispone di una tabella che non ha indice sulla colonna su cui si sta calcolando il MAX, Oracle dovrà eseguire una scansione completa della tabella. Questo sarà O (n) dal momento che devi scansionare ogni blocco nella tabella. Puoi vederlo guardando il piano di query.

Ci generare una tabella con 100.000 righe e garantire che le file sono abbastanza grandi utilizzando una colonna

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. 

CHAR(1000) Ora, siamo in grado di guardare il piano per la MAX funzionamento di base. Questo sta facendo una scansione completa della tabella (un'operazione 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 

Se si crea un indice sulla colonna si sta calcolando il MAX di, Oracle può fare MIN/MAX scan sull'indice. Questa è un'operazione O (log n) se questo è il piano scelto dall'ottimizzatore. Naturalmente, dal punto di vista pratico, si tratta di un'operazione di tipo O (1) perché l'altezza di un indice non supererà mai in modo realistico i 4 o 5 - i termini costanti qui stanno per dominare.

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 

Ma poi le cose diventano più difficili. Entrambi MIN e MAX hanno lo stesso comportamento di O (log n) singolarmente. Ma se hai entrambi MIN e MAX nella stessa query, all'improvviso torni ad un'operazione O (n). Oracle (come del 11.2), non ha implementato un grab opzione sia il primo blocco e l'ultimo blocco di un indice

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 

Naturalmente, nelle versioni successive di Oracle, questa ottimizzazione può essere implementata e questo sarebbe tornare indietro ad essere un'operazione O (log n). Naturalmente, puoi anche riscrivere la query per ottenere un piano di query diverso che risulti 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