Geek asks and answers

What is the great feature of Oracles MAX?

Is the time complexity of the Oracle MAX function O (1), O (log n), or O (n) relative to the number of rows in a table?

+5
source share
2 answers

If you have a B-tree index in a column, then to find the maximum value is O (log (n)), since the answer will be the last (or first) row of the index. Values ​​are stored in the deepest nodes of the B-tree with height O (log (n)).

Without an index, this is O (n), because all rows must be read to determine the maximum value.

: O (n) , . . , , , .

+9

, , .

, , 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
+7

More articles:


All Articles