¿Cuál es la gran función O de Oracles MAX?

Question

¿Es el time complexity de Oracle MAX la función O (1), O (log n) u O (n) con respecto al número de filas en una tabla?

Answer 1

Si tiene un índice B-tree en la columna, encontrar el valor máximo es O (log (n)) porque la respuesta será la última (o la primera) fila del índice. Los valores se almacenan en los nodos más profundos del árbol B que tiene una altura O (log (n)).

Sin índice, es O (n) porque todas las filas deben leerse para determinar el valor máximo.

---

Nota: La O (n) la notación hace caso omiso de las constantes, pero en el mundo real estas constantes no puede ser ignorada. La diferencia entre leer desde el disco y leer desde la memoria es de varios órdenes de magnitud. Es probable que el acceso al primer valor de un índice se realice principalmente en la memoria RAM, mientras que un escaneo completo de una tabla enorme necesitará leer principalmente del disco.

Answer 2

Realista, es difícil de decir sin especificar una consulta, una definición de tabla y un plan de consulta.

Si tiene una tabla que no tiene índice en la columna en la que está computando el MAX, Oracle tendrá que hacer un escaneo completo de la tabla. Eso va a ser O (n) ya que tienes que escanear cada bloque en la tabla. Puedes ver eso mirando el plan de consulta.

Generaremos una mesa con 100.000 filas y nos aseguramos de que las filas son razonablemente grande usando una columna

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) Ahora, podemos ver el plan para el funcionamiento básico MAX. Esto está haciendo un escaneo completo de tabla (un O (n) la operació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 

Si crea un índice en la columna que está calculando la MAX de, Oracle puede hacer un MIN/MAX scan en el índice. Esa es una operación O (log n) si ese es el plan que el optimizador elige. Por supuesto, como una cuestión práctica, esto es funcionalmente una operación O (1) porque la altura de un índice nunca va más allá de 4 o 5, los términos constantes van a dominar.

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 

Pero entonces las cosas se ponen más difíciles. Tanto MIN como MAX tienen el mismo comportamiento O (log n) individualmente. Pero si tiene ambos MIN y MAX en la misma consulta, de repente vuelve a una operación O (n). Oracle (a partir de 11,2) no ha implementado un agarre opción tanto para el primer bloque y el último bloque de un índice

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 

Por supuesto, en las versiones posteriores de Oracle, esta optimización se puede implementar y esto volvería a ser una operación O (log n). Por supuesto, también puede reescribir la consulta para obtener un plan de consulta diferente que vuelva a ser 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