Oracle Database - (B|Balanced) Tree - BTree indexes

> Database > Oracle Database

1 - About

Index - Btree structure (Balanced Tree) in the Oracle database.

2 - Article

3 - Statistics

Advertising

3.1 - Height Balanced Structure

To get to the leaf block to retrieve the first row of a query of the form

 SELECT INDEXED-COL FROM T WHERE INDEX_COL = :X

will take the same number of I/Os regardless of the value :X that is used. In other words, the index is height balanced

Most of B*Tree indexes will have a height of 2 or 3 even for millions of record. This means that it will take in general, two or three I/Os to find your key in the index which is not too bad.

Example

[email protected]>SELECT index_name,blevel, num_rows
  2  FROM user_indexes
  3  WHERE TABLE_NAME = 'BIG_TABLE';
 
INDEX_NAME                         BLEVEL   NUM_ROWS
------------------------------ ---------- ----------
BIG_TABLE_PK                            2    9542757
 
[email protected]>SET autotrace ON;
[email protected]>SELECT id FROM big_table WHERE id = 42;
 
----------------------------------------------------------------------------------
| Id  | Operation         | Name         | ROWS  | Bytes | Cost (%CPU)| TIME     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |              |     1 |     6 |     2   (0)| 00:00:01 |
|*  1 |  INDEX UNIQUE SCAN| BIG_TABLE_PK |     1 |     6 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------------
 
Statistics
----------------------------------------------------------
          3  consistent gets
          1  ROWS processed
 
[email protected]>SELECT id FROM big_table WHERE id = 5000000;
 
Execution Plan
----------------------------------------------------------------------------------
| Id  | Operation         | Name         | ROWS  | Bytes | Cost (%CPU)| TIME     |
----------------------------------------------------------------------------------
|   0 | SELECT STATEMENT  |              |     1 |     6 |     2   (0)| 00:00:01 |
|*  1 |  INDEX UNIQUE SCAN| BIG_TABLE_PK |     1 |     6 |     2   (0)| 00:00:01 |
----------------------------------------------------------------------------------
 
Statistics
----------------------------------------------------------
          3  consistent gets
          1  ROWS processed

Whenever the value selected 42 of 5000000, you will have always the same statistics :

  • 3 consistent gets (three I/Os)
  • 1 rows processed

4 - Non Unique Index

In a nonunique index, Oracle simply stores the rowid by appending it to the key as an extra column with a length byte to make the key unique. For example, an index such as

CREATE INDEX I ON T(X,Y)

is conceptually

CREATE UNIQUE INDEX I ON T(X,Y, ROWID)

In a nonunique index, you will find that the data is sorted first by index key values (in the order of the index key) and then by rowid ascending. In a unique index, the data is sorted only by the index key values.

Advertising

5 - Index Key Compression

This is not compression in the same manner that ZIP files are compressed; rather, this is compression that removes redundancies from concatenated (multi-column) indexes.

5.1 - Concept

The basic concept behind a compressed key index is that every entry is broken into two pieces :

  • a prefix component . It's build on the leading columns of the concatenated index and will have many repeating values.
  • and a suffix component. It's built on the trailing columns in the index key and is the unique component of the index entry within the prefix.

Index block with owner colomn repeated

Sys.Package.Dbms_Alert
Sys.Package.Dbms_Application_info
Sys.Package.Dbms_Aq
Sys.Package.Dbms_Aqadm
Sys.Package.Dbms_Aqadm_Sys
Sys.Package.Dbms_Alert_Syscalls
...

become

Index block with owner colomn factored out

**Sys** //<- prefix//
Package.Dbms_Alert //<- suffix ...//
Package.Dbms_Application_info
Package.Dbms_Aq
Package.Dbms_Aqadm
Package.Dbms_Aqadm_Sys
Package.Dbms_Alert_Syscalls
...

5.2 - Example

[email protected]>CREATE TABLE t
  2  AS
  3  SELECT * FROM all_objects;
 
TABLE created.
 
[email protected]>CREATE INDEX t_idx ON t(owner, object_type, object_name);
 
INDEX created.
 
[email protected]>analyze INDEX t_idx validate STRUCTURE;
 
INDEX analyzed.
 
[email protected]>CREATE TABLE idx_stats
  2  AS
  3  SELECT 'noncompressed' what, a.*
  4  FROM index_stats a;
 
TABLE created.
 
[email protected]>define 1=1;
[email protected]>DROP INDEX t_idx;
 
INDEX dropped.
 
[email protected]>CREATE INDEX t_idx ON t(owner,object_type,object_name) compress &1;
OLD   1: CREATE INDEX t_idx ON t(owner,object_type,object_name) compress &1
NEW   1: CREATE INDEX t_idx ON t(owner,object_type,object_name) compress 1
 
INDEX created.
 
[email protected]>analyze INDEX t_idx validate STRUCTURE;
 
INDEX analyzed.
 
[email protected]>INSERT INTO idx_stats SELECT 'compress &1', a.* FROM index_stats a;
OLD   1: INSERT INTO idx_stats SELECT 'compress &1', a.* FROM index_stats a
NEW   1: INSERT INTO idx_stats SELECT 'compress 1', a.* FROM index_stats a
 
1 ROW created.
 
........................................
FOR compress 2 AND 3 same PROCEDURE ....
........................................
 
[email protected]>SELECT what, height, lf_blks, br_blks, btree_space, opt_cmpr_count, opt_cmpr_pctsave
  2  FROM idx_stats;
 
WHAT              HEIGHT    LF_BLKS    BR_BLKS BTREE_SPACE OPT_CMPR_COUNT OPT_CMPR_PCTSAVE
------------- ---------- ---------- ---------- ----------- -------------- ----------------
noncompressed          3        407          3     3280096              2               29
compress 1             3        354          3     2854680              2               19
compress 2             3        287          3     2318948              2                0
compress 3             3        455          3     3662276              2               36
  • LF_BLKS = Leaf Blocks
  • BR_BLKS = Branch Blocks
  • OPT_CMPR_PCTSAV = Optimum compression percent saved (or the expected saving from compression)
  • OPT_CMPR_COUNT = Optimum compression factor

We see for COMPRESS 1 :

  • Comparing BTREE_SPACE, that the index is about 89 percent the size of the noncompressed index.
  • the number of leaf blocks has decreased measurably

Further, we see for COMPRESS 2 :

  • the saving are even more impressive. The resulting index is about 70 percent the size of the original, and so much data is able to be placed on individual blocks

The ANALYZE command against the noncompressed index populated the OPT_CMPR_PCTSAVE/OPT_CMPR_COUNT columns and estimated a 29 percent saving with COMPRESS 2.

[email protected]>SELECT  3280096*(1-0.29) FROM dual;
 
3280096*(1-0.29)
----------------
      2328868.16

Not so bad compare to the value of 2318948

What happen for COMPRESS 3 :

  • The resulting index is actually larger: 110 percent the size of the original index.

This is due to the fact that each repeated prefix we remove saves the space of N copies, but add 4 bytes of overhead on the leaf block as part of the compression scheme. By adding the OBJECT_NAME column to the compressed key, we made that key unique, meaning there were no duplicate copies to factor out. Therefore, we ended up adding 4 bytes to every single index key entry and factoring out no repeating data.

The column OPT_CMPR_COUNT is dead accurate at providing the best compression count to be used and OPT_CMPR_PCTSAVE will tell you exactly how much saving to expect.

Advertising

5.3 - Compression is not free

The compressed index structure is more complex than it used to be. Oracle will spend more time processing the data in this structure, both :

  • while maintaining the index during modifications
  • when you search the index during the query

What we search is the tradeoff between CPU time and I/O time.

With compression :

  • our block buffer cache will be able to hold more index entries than before,
  • our cache hit-ratio might go up
  • our physical I/Os should go down (half)

BUT

  • it will take a little more CPU

6 - Subtypes

B*Tree index has several subtypes :

7 - Reference

db/oracle/btree.txt · Last modified: 2017/09/13 16:16 by gerardnico