0

I have an employee table which has index on name. I want to understand how Oracle works at high level

My understanding based on resources mentioned below:-

DB constructs the index table/map where it will keep the name in sorted fashion with memory location as the value.

Question :-

  1. My question is will oracle bring all index table/map entries in memory from disc and then do the binary search or is it the search at disc level without bringing all index table records in memory?

  2. If I compare this approach with Java based data structures, Oracle is maintaining the TreeMap of column where key is employee name and value is memory location of that entry. So to find any entry, look up time will be log(n). My question why not DB/oracle takes hash based approach where it keeps the hashtable where it calculate the memory location based on name value and put the entry there. So lookup time to find entry will be O(1) .

Resources I referred

  1. "Indexes and Index-Organized Tables" from the Oracle manual

  2. How does database indexing work

5
  • Hi emily. BobC has basically answered your question but if you are asking this sort of question you will benefit from the resources in our "Where to start with Oracle" post. Mar 4, 2017 at 7:26
  • I don't think you can compare the BTree index in a database with a TreeMap in Java. Those are two very different implementations
    – user1822
    Mar 4, 2017 at 8:43
  • 2
    @JackDouglas - A collection of valuable links is a great thing to have but it cannot be qualified as an answer. This question should not be marked as duplicate. Mar 4, 2017 at 10:13
  • @Dudu it's not a 'normal' duplicate — see the discussion here on meta for 'too basic' questions. This would be closed 'too localized' but closing as a dupe helps the OP and future visitors get started with the RDBMS in question. Mar 4, 2017 at 12:11
  • A related question -- Why did MySQL choose not to implement Hash? Because BTree is the best all-around indexing mechanism. Anyway, Hash is slightly worse than O(1) due to collisions; and the 'log' in BTree's O(log n) is small.
    – Rick James
    Jul 23, 2017 at 14:57

1 Answer 1

2

Oracle will not read all the index; only the index blocks needed to satisfy the particular query. The number of blocks will depend on the depth of the index; rarely more than three have I seen in practice, for a single lookup.

Here is an example, using a big version of the EMP table. BIGEMP contains just under 2M rows:

select count(*) from bigemp
;

  COUNT(*)
----------
   1835008

I have created a unique index, called IDX1 on empno. Now I can examine the BLEVEL (which is what I was referring to as depth above) and the number of leaf blocks:

 select index_name, blevel, leaf_blocks
 from user_indexes
 where index_name = 'IDX1'
 ;

INDEX_NAME               BLEVEL LEAF_BLOCKS
-------------------- ---------- -----------
IDX1                          2        3947

So this tells me that this index has a root node, and then two level below that. So this mean that to find a unique row from the table, it should only take 4 IO's. That is the index root block, the two leaf blocks, and then another IO to the table to get the actual rows. This can be verified using autotrace

SQL> set autotrace on
SQL> select empno, ename, sal
  2  from bigemp
  3  where empno = 12345
  4  /

     EMPNO ENAME             SAL
---------- ---------- ----------
     12345 Scott            3000


Execution Plan
----------------------------------------------------------
Plan hash value: 3460625844

--------------------------------------------------------------------------------------
| Id  | Operation                   | Name   | Rows  | Bytes | Cost (%CPU)| Time     |
--------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT            |        |     1 |    15 |     3   (0)| 00:00:01 |
|   1 |  TABLE ACCESS BY INDEX ROWID| BIGEMP |     1 |    15 |     3   (0)| 00:00:01 |
|*  2 |   INDEX UNIQUE SCAN         | IDX1   |     1 |       |     2   (0)| 00:00:01 |
--------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

   2 - access("EMPNO"=12345)


Statistics
----------------------------------------------------------
          1  recursive calls
          0  db block gets
          4  consistent gets
          1  physical reads
          0  redo size
        682  bytes sent via SQL*Net to client
        551  bytes received via SQL*Net from client
          2  SQL*Net roundtrips to/from client
          0  sorts (memory)
          0  sorts (disk)
          1  rows processed

Sure enough, 4 consistent gets.

Oracle does also support "hash indexing" - called hash clusters. However, for transactional systems, there is a big maintenance penalty on them, so they are rarely used in these systems.

7
  • Note that there are execution plan steps that do read the entire index e.g. "Index Full Scan" or "Index Fast Full Scan"
    – user1822
    Mar 4, 2017 at 8:39
  • @BobC Thanks. I am still amused how(which algorithm) DB can find unqiue value even in your case in just 4 IO's from million of records. Coming from java background in tree, I can think of only log(n) complexity to find any node like in binary search.
    – emilly
    Mar 5, 2017 at 2:00
  • @emilly Which is why we use a database store, retrieve and process large volumes of data :) Anyway, is there a particular problem or issue you are trying to solve, or is this just curiosity ?
    – BobC
    Mar 5, 2017 at 2:20
  • Thanks Bob . This is just out of curiosity.One quick thing, when I looked for particular index through select * from user_constraints; select index_name, blevel, leaf_blocks from user_indexes where index_name = 'SYS_C002708446' , I found Blevel and Leaf_Blocks value as null ?
    – emilly
    Mar 5, 2017 at 6:22
  • 1
    @emilly A B-tree index uses a balanced tree, not a binary tree. In example 2, with 18 records per index block, the calculation should be log 277778 with the base being 18 and not 2, which is ~= 4,33. Oracle indexes often contain hundreds of index entries per block, so we are talking of logarithm using a base of not 2, but hundreds. For your other question: blevel and leaf_blocks are null, because that view returns the values from object statistics, and not the actual data. Without statistics, you get no values. Collect statistics on the index, and you will get the values. Mar 5, 2017 at 22:15

Not the answer you're looking for? Browse other questions tagged or ask your own question.