Oracle Concepts - 3 Indexes and Index-Organized Tables

B-tree Indexes

B-tree Index

- Indexes used for speeding query performance

- Work by organizing a column value into a tree structure

- Full Table scan vs index scan

- one or more columns

- ROWID

- B-tree index practice  using SQL Developer

create table location (

 location_id number(5)

, location_desc varchar2(400)

, ename varchar2(10)

, arrival_date date

);

create index location_id_idx

 on location (location_id)

tablespace users;

create index location_comp_idx

 on location (ename, arrival_date);

Bitmaps Indexes

Bitmap Index

- Special type of index for certain situations

- Cardinality - number of distinct values

- Bitmaps indexes are best with low cardinality

- Few or no updates

- Bitmap practice  using SQL Developer

create bitmap index emp_job_bidx

on scott.emp (job);

select * from scott.emp;

Index Organized Tables

Index organized table

- Typical tables - heap organized

- index-organized tables (IOT) structured in an index

- Dynamic - rows can be moved to preserve the index structure

- Good for

a. Small tables

b. Exact match

c. Reducing storage requirements

- Index Organized Table  practice  using SQL Developer

create table state_lookup_iot (
area_code number(3)
, state_name varchar2(100)
, city_name varchar2(100)
, primary key (area_code)
)

organization index tablespace users;

Function Based Indexes

Function based index

- Index for very specific situations

- ‘Book list’ example

- Optimizer will ignore a B-tree index

- Use Function Based index to query based on a function

- Function Based index  practice  using SQL Developer

select * from employees;

select hire_date from employees;

select * from employees where hire_date = '01-MAY-95';

create index emp_idx on employees (hire_date);

select * from employees where to_char(hire_date, 'YYYY') = '1997';

create index hire_fidx on employees (to_char(hire_date, 'YYYY'));

============================================================

- index is an optional structure, associated with a table or table cluster, that can sometimes speed data access. By creating an index on one or more columns of a table

- if heap-organized table has no indexes, then the database must perform a full table scan to find a value

- index can be dropped or created without physically affecting the table for the index

- index points directly to the location of the rows containing that value

- many indexes on a table degrades DML performance because the database must also update the indexes

- Consider creating an index on a column in any of the following situations:

• The indexed columns are queried frequently and return a small percentage of the total number of rows in the table.

• A referential integrity constraint exists on the indexed column or columns. The index is a means to avoid a full table lock that would otherwise be required if you update the parent table primary key, merge into the parent table, or delete from the parent table.

• A unique key constraint will be placed on the table and you want to manually specify the index and all index options.

- Making an index invisible is an alternative to making it unusable or dropping it
- key is a set of columns or expressions on which you can build an index

Indexes have the following properties:

• Usability 

- Indexes are usable (default) or unusable. An unusable index is not maintained by DML operations and is ignored by the optimizer.

- unusable index can improve the performance of bulk loads, Instead of dropping an index and later re-creating it, you can make the index unusable and then rebuild it

•  Visibility

- Indexes are visible (default) or invisible. An invisible index is maintained by DML operations and is not used by default by the optimizer

- key is a set of columns or expressions on which you can build an index

- indexes and keys are different. Indexes are structures stored in the database that users manage using SQL statements. Keys are strictly a logical concept.

$ sqlplus / as sysdba

SQL> connect oe/oracle;
Connected.
SQL> set pagesize 0
SQL> set lines 2000

- to list schemas by listing users and tablespaces

SQL> select username,account_status,default_tablespace from dba_users order by default_tablespace;

- Creates an index on the customer_id column of the sample table oe.orders:

SQL> CREATE INDEX ord_customer_ix ON orders (customer_id);

- Primary and unique keys automatically have indexes, but you might want to create an index on a foreign key.

- Composite index, also called a concatenated index, is an index on multiple columns in a table

CREATE INDEX employees_ix
   ON employees (last_name, job_id, salary);

- Multiple indexes can exist for the same table if the permutation of columns differs for each index

CREATE INDEX employee_idx1 ON employees (last_name, job_id);
CREATE INDEX employee_idx2 ON employees (job_id, last_name);

- Indexes can be unique or nonunique. Unique indexes guarantee that no two rows of a table have duplicate values in the key column or column

- nonunique indexes are sorted by the index key and rowid (ascending).

- Types of Indexes

http://en.wikipedia.org/wiki/Bitmap
Bitmap is a mapping from some domain (for example, a range of integers) to bits, that is, values which are zero or one. It is also called a bit array or bitmap index.

http://en.wikipedia.org/wiki/B-tree
 B-tree is a tree data structure that keeps data sorted and allows searches, sequential access, insertions, and deletions in logarithmic time. 

• B-tree indexes: standard index type. They are excellent for primary key and highly-selective indexes

These indexes are the standard index type. They are excellent for primary key and highly-selective indexes. Used as concatenated indexes, B-tree indexes can retrieve data sorted by the indexed columns. B-tree indexes have the following subtypes:

1. Index-organized tables

An index-organized table differs from a heap-organized because the data is itself the index. See "Overview of Index-Organized Tables".

2. Reverse key indexes

In this type of index, the bytes of the index key are reversed, for example, 103 is stored as 301. The reversal of bytes spreads out inserts into the index over many blocks.

3. Descending indexes

This type of index stores data on a particular column or columns in descending order.

4. B-tree cluster indexes

This type of index is used to index a table cluster key. Instead of pointing to a row, the key points to the block that contains rows related to the cluster key. 

• Bitmap and bitmap join indexes

In a bitmap index, an index entry uses a bitmap to point to multiple rows. In contrast, a B-tree index entry points to a single row. A bitmap join index is a bitmap index for the join of two or more tables. 

• Function-based indexes

This type of index includes columns that are either transformed by a function, such as the UPPER function, or included in an expression. B-tree or bitmap indexes can be function-based.

• Application domain indexes

This type of index is created by a user for data in an application-specific domain. The physical index need not use a traditional index structure and can be stored either in the Oracle database as tables or externally as a file

- B-tree (balanced trees) index is an ordered list of values divided into ranges. By associating a key with a row or range of rows.

Internal Structure of a B-tree Index

- B-tree index has two types of blocks: branch blocks for searching and leaf blocks that store values. The upper-level branch blocks of a B-tree index contain index data that points to lower-level index blocks.

- height of the index is the number of blocks required to go from the root block to a leaf block. The branch level is the height minus 1

- Each entry is sorted by (key, rowid). Within a leaf block, a key and rowid is linked to its left and right sibling entries, The leaf blocks themselves are also doubly linked

- Index Scans

• If the database scans the index for a value, then it will find this value in n I/Os where n is the height of the B-tree index. This is the basic principle behind Oracle Database indexes
• If a SQL statement accesses only indexed columns, then the database reads values directly from the index rather than from the table
• If the statement accesses columns in addition to the indexed columns, then the database uses rowids to find the rows in the table
• Typically, the database retrieves table data by alternately reading an index block and then a table block.

- database reads the entire index in order. A full index scan is available if a predicate (WHERE clause) in the SQL statement references a column in the index

- Fast full index scan is a full index scan in which the database accesses the data in the index itself without accessing the table

- Fast full index scans are an alternative to a full table scan when both of the following

a. The index must contain all columns needed for the query.

b. A row containing all nulls must not appear in the query result set. For this result to be guaranteed, at least one column in the index must have either:

1. A NOT NULL constraint
2. A predicate applied to it that prevents nulls from being considered in the query result set

- index range scan is an ordered scan of an index that has the following characteristics:

- One or more leading columns of an index are specified in conditions. A condition specifies a combination of one or more expressions and logical (Boolean) operators and returns a value of TRUE, FALSE, or UNKNOWN.

- 0, 1, or more values are possible for an index key

- database commonly uses an index range scan to access selective data

- Selectivity is tied to a query predicate, such as WHERE last_name LIKE 'A%', or a combination of predicates

-  index skip scan uses logical subindexes of a composite index

- Skip scanning is beneficial if there are few distinct values in the leading column of a composite index and many distinct values in the nonleading key of the index

- index clustering factor measures row order in relation to an indexed value such as employee last name. The more order that exists in row storage for this value, the lower the clustering factor.

- clustering factor is useful as a rough measure of the number of I/Os required to read an entire table by means of an index during a large index range scan:

1. random table blocks > high clustering factor > high number of I/Os
2. same data block > low clustering factor > low number of I/Os

The clustering factor is relevant for index scans because it can show:

• Whether the database will use an index for large range scans
• The degree of table organization in relation to the index key
• Whether you should consider using an index-organized table, partitioning, or table cluster if rows must be ordered by the index key

Clustering Factor Measure

Result of previous SQL statement:

1. clustering factor for EMP_NAME_IX is low, which means that adjacent index entries in a single leaf block tend to point to rows in the same data blocks

2. clustering factor for EMP_EMP_ID_PK is high, which means that adjacent index entries in the same leaf block are much less likely to point to rows in the same data blocks

- Reverse key index is a type of B-tree index that physically reverses the bytes of each index key while keeping the column order

For example, C1,15 in a standard B-tree index > Reverse key index stores the bytes as 15,C1.

- Reversing the key solves the problem especially in Oracle Real Application Clusters (Oracle RAC) database in which multiple instances repeatedly modify the same block

- Oracle Database stores data in ascending (low to high) order. By default

CREATE INDEX emp_deptid_ix ON hr.employees(department_id); 

- Descending (high to low) indexes are useful when a query sorts some columns ascending and others descending

CREATE INDEX emp_name_dpt_ix ON hr.employees(last_name ASC, department_id DESC)

- key compression to compress portions of the primary key column values in a B-tree index or an index-organized table. Key compression can greatly reduce the space consumed by the index

- index keys have two pieces, grouping piece and a unique piece, compression breaks the index key into
1. prefix entry, which is the grouping piece
2. suffix entry, which is the unique or nearly unique piece

-  prefix of a unique index consists of all key columns excluding the last one, whereas the prefix of a nonunique index consists of all key columns

CREATE INDEX orders_mod_stat_ix ON orders ( order_mode, order_status );

- bitmap index, the database stores a bitmap for each index key

B-tree index, one index entry points to a single row. 
bitmap index, each index key stores pointers to multiple rows.

- Bitmap indexes are primarily designed for data warehousing or environments in which queries reference many columns in an ad hoc fashion

- Situations that may call for a bitmap index include:

1. The indexed columns have low cardinality, that is, the number of distinct values is small compared to the number of table rows.

2. The indexed table is either read-only or not subject to significant modification by DML statements.

- For a data warehouse example, the sh.customers table has a cust_gender column with only two possible values: M and F

- With bitmap index DML on indexed data typically locks all of these rows > NOT appropriate for many OLTP applications

- Bitmap Indexes on a Single Table

Sample Bitmap

Value	Row 1	Row 2	Row 3	Row 4	Row 5	Row 6	Row 7
M	1	0	1	1	1	0	0
F	0	1	0	0	0	1	1

- How many of our female customers are single or divorced?

- bitmap join index is a bitmap index for the join of two or more tables

- bitmap join index is an efficient means of reducing the volume of data that must be joined by performing restrictions in advance

To retrieve the data from the index itself rather than from a scan of the tables, you could create a bitmap join index as follows:

CREATE BITMAP INDEX employees_bm_idx 
ON     employees (jobs.job_title) 
FROM   employees, jobs
WHERE  employees.job_id = jobs.job_id;

Join of employees and jobs Tables

- data for a bitmap index is stored in one segment. Oracle Database stores each bitmap in one or more pieces. Each piece occupies part of a single data block.

....