Oracle Essentials Oracle Database 11g (20 page)

Leaf

Brown

Howard

Klein

Porter

Thomas

Wagner

blocks

Culver

Isis

Main

Sikes

Topper

Yanks

Deal - ROWID

Howard - ROWID

Detail of leaf node

Isis - ROWID

Figure 4-1. A B*-tree index

The B*-tree index structure doesn’t contain many blocks at the higher levels of branch blocks, so it takes relatively few I/O operations to read quite far down the B*-

tree index structure. All leaf blocks are at the same depth in the index, so all retrievals require essentially the same amount of I/O to get to the index entry, which evens out the performance of the index.

Oracle allows youto create
index organized tables
(IOTs), in which the leaf blocks store the entire row of data rather than only the ROWID that points to the associated row. Index organized tables reduce the total amount of space needed to store an index and a table by eliminating the need to store the ROWID in the leaf page. But index organized tables cannot use a UNIQUE constraint or be stored in a cluster. In addition, index organized tables don’t support distribution, replication, and partitioning (covered in greater detail in other chapters), although IOTs can be used with Oracle Streams for capturing and applying changes with Oracle Database 10
g
and later releases.

There were a number of enhancements to index organized tables as of Oracle9
i
, including a lifting of the restriction against the use of bitmap indexes as secondary indexes for an IOT and the ability to create, rebuild, or coalesce secondary indexes on an IOT. Oracle Database 10
g
continued this trend by allowing replication and all types of partitioning for index organized tables, as well as providing other enhancements.

Basic Data Structures

|

93

Reverse key indexes

Reverse key indexes
, as their name implies, automatically reverse the order of the bytes in the key value stored in the index. If the value in a row is “ABCD”, the value for the reverse key index for that row is “DCBA”.

To understand the need for a reverse key index, you have to review some basic facts about the standard B*-tree index. First and foremost, the depth of the B*-tree is determined by the number of entries in the leaf nodes. The greater the depth of the B*-

tree, the more levels of branch nodes there are and the more I/O is required to locate and access the appropriate leaf node.

The index illustrated in
Figure 4-1
is a nice, well-behaved, alphabetic-based index.

It’s balanced, with an even distribution of entries across the width of the leaf pages.

But some values commonly used for an index are not so well behaved. Incremental values, such as ascending sequence numbers or increasingly later date values, are always added to the right side of the index, which is the home of higher and higher values. In addition, any deletions from the index have a tendency to be skewed toward the left side as older rows are deleted. The net effect of these practices is that over time the index turns into an unbalanced B*-tree, where the left side of the index is more sparsely populated than the leaf nodes on the right side. This unbalanced growth has the overall effect of having an unnecessarily deep B*-tree structure, with the left side of the tree more sparsely populated than the right side, where the new, larger values are stored. The effects described here also apply to the values that are automatically decremented, except that the left side of the B*-tree will end up holding more entries.

Youcan solve this problem by periodically dropping and re-creating the index. However, you can also solve it by using the reverse value index, which reverses the order of the value of the index. This reversal causes the index entries to be more evenly distributed over the width of the leaf nodes. For example, rather than having the values 234, 235, and 236 be added to the maximum side of the index, they are translated to the values 432, 532, and 632 for storage and then translated back when the values are retrieved. These values are more evenly spread throughout the leaf nodes.

The overall result of the reverse index is to correct the imbalance caused by continually adding increasing values to a standard B*-tree index. For more information about reverse key indexes and where to use them, refer to your Oracle documentation.

Bitmap indexes

In a standard B*-tree index, the ROWIDs are stored in the leaf blocks of the index. In a
bitmap index
, each bit in the index represents a ROWID. If a particular row contains a particular value, the bit for that row is “turned on” in the bitmap for that value. A mapping function converts the bit into its corresponding ROWID. Unlike other index types, bitmap indexes include entries for NULL values.

94

|

Chapter 4: Oracle Data Structures

Youcan store a bitmap index in much less space than a standard B*-tree index if there aren’t many values in the index.
Figure 4-2
shows an illustration of how a bitmap index is stored.
Figure 10-3
in
Chapter 10
shows how a bitmap index is used in a selection condition.

PARTS table

partno

color

size

weight

1

GREEN

MED

98.1

2

RED

MED

1241

3

RED

SMALL

100.1

4

BLUE

LARGE

54.9

5

RED

MED

124.1

6

GREEN

SMALL

60.1

...

...

...

...

Bitmap index on 'color'

color =

'BLUE'

0 0 0 1 0 0 ...

color =

'RED'

0 1 1 0 1 0 ...

color =

'GREEN' 1 0 0 0 0 1 ...

Part number
1 2 3 4 5 6

Figure 4-2. Bitmap index

The functionality provided by bitmap indexes is especially important in data warehousing applications in which each dimension of the warehouse contains many repeating values, and queries typically require the interaction of several different

dimensions. For more about data warehousing, see Chapter 10.

Function-based indexes

Function-based indexes
were introduced in Oracle8
i
. A function-based index is just like a standard B*-tree or bitmap index, except that youcan base the index on the result of a SQL function, rather than just on the value of a column or columns.

Prior to Oracle8
i
, if you wanted to select on the result of a function, Oracle retrieved every row in the database, executed the function, and then accepted or rejected each row. With function-based indexes you can simply use the index for selection, without having to execute the function on every row, every time.

For example, without a function-based index, if you wanted to perform a case-insensitive selection of data you would have to use the UPPER function in the WHERE clause, which would retrieve every candidate row and execute the function. With a function-based index based on the UPPER function, you can select directly from the index.

Basic Data Structures

|

95

As of Oracle Database 10
g
, youcan perform case- or accent-insensitive queries; these queries provide another way to solve this problem.

This capability becomes even more valuable when you consider that you can create your own functions in an Oracle database. You can create a very sophisticated function and then create an index based on the function, which can dramatically affect the performance of queries that require the function.

Invisible indexes

Oracle Database 11
g
introduces a new option for all of the index types we’ve discussed in previous sections—the
invisible index
. Normally, all indexes are used by the optimizer, which is described later in this chapter. Youcan eliminate an index from optimizer consideration by taking the index offline or by deleting the index. But with both of these methods youwill have to take some actions to bring the index up to date when you bring it back into the database environment.

But what if you want to just remove the index from optimizer consideration for a limited time, such as when you are testing performance? With the invisible option, an index is not considered as a possible step in an access path, but updates and deletes to the underlying data are still applied to the index.

Partitioning

With the Enterprise Editions of Oracle8 and beyond, youcan purchase the Partitioning Option. As the name implies, this option allows youto partition tables and indexes. Partitioning a data structure means that you can divide the information in the structure among multiple physical storage areas. A partitioned data structure is divided based on column values in the table. You can partition tables based on the range of column values in the table (often date ranges), or as the result of a hash function (which returns a value based on a calculation performed on the values in one or more columns). As of Oracle9
i
you can also use a list of values to define a partition, which can be particularly useful in a data warehouse environment. Oracle Database 11
g
adds
interval partitioning
, providing the ability to automatically generate a new partition of a fixed interval or range when data to be inserted does not fit into existing partition ranges.

Youcan also have two levels of partitions, called
composite partitions
, using a combination of partition methods. Prior to Oracle Database 11
g
, you could partition using a composite of range and hash partitioning. Oracle Database 11
g
adds the ability to combine list partitioning with list, range, or hash partitioning, or range partitioning with a different range partitioning scheme.

96

|

Chapter 4: Oracle Data Structures

Oracle is smart enough to take advantage of partitions to improve performance in two ways:

• Oracle won’t bother to access partitions that won’t contain any data to satisfy the query.

• If all the data in a partition satisfies a part of the WHERE clause for the query, Oracle simply selects all the rows for the partition without bothering to evaluate the clause for each row.

Partitioned tables are especially useful in a data warehouse, in which data can be partitioned based on the time period it spans.

Equally important is the fact that partitioning substantially reduces the scope of maintenance operations and increases the availability of your data. You can perform all maintenance operations, such as backup, recovery, and loading, on a single partition. This flexibility makes it possible to handle extremely large data structures while still performing those maintenance operations in a reasonable amount of time. In addition, if youmust recover one partition in a table for some reason, the other partitions in the table can remain online during the recovery operation.

If youhave been working with other databases that don’t offer the same type of partitioning, youmay have tried to implement a similar functionality by dividing a table into several separate tables and then using a UNION SQL command to view the data in several tables at once. Partitioned tables give youall the advantages of having several identical tables joined by a UNION command without the complexity that implementation requires.

To maximize the benefits of partitioning, it sometimes makes sense to partition a table and an index identically so that both the table partition and the index partition map to the same set of rows. Youcan automatically implement this type of partitioning, which is called
equipartitioning
, by specifying an index for a partitioned table as a LOCAL index. Local indexes simplify maintenance, since standard operations, such as dropping a partition, will work transparently with both the index partition and the table partition.

Oracle has continued to increase the functionality of partitioning features. Since Oracle Database 10
g
Release 2, youcan reorganize individual partitions online, the maximum number of partitions increased from 64 KB – 1 to 128 KB – 1, and query optimization using partition pruning improved.

Oracle Database 11
g
further improves partition pruning, enables applications to control partitioning, and adds a Partition Advisor that can help youto understand when partitioning might improve the performance of your Oracle database.

For more details about the structure and limitations associated with partitioned tables, refer to your Oracle documentation.