NUSI – The Nonunique Secondary Index in Teradata

3
1694

 

teradata nusi

The Technical Details of the Non-Unique Secondary Index in Teradata – NUSI


Many concepts of Teradata indexing are tightly coupled to the physical storage of data rows. Therefore, I highly recommended reading our article series about physical storage: http://www.dwhpro.com/teradata-physical-storage/

The Teradata Non-Unique Secondary Index (NUSI) is an alternative data access path which can help to reduce IOs.

While B+ Tree Indexes are a quite commonly used index mechanism in relational database systems, Teradata uses a different approach based on hashing.

Teradata distinguishes between unique secondary indexes (USI) and non-unique secondary indexes (NUSI). Although the naming may seduce to assume they are technically the same, they are not at all. This article is related to the non-unique Teradata secondary index or NUSI.

As opposed to the USI, index row distribution of Non-Unique secondary indexes is not based on the same hashing algorithm Teradata uses to distribute base table rows evenly across all AMPs

Non-unique secondary indexes are sub-tables; they do not show up as real objects in the DBC data dictionary tables (in contrast to Join Indexes).

Base table rows are hashed by the primary index column values, while the nonunique secondary index rows are co-located with their base table rows on the same AMP:

NUSI rows are not hash distributed.

While the USI-access is always a 2-AMP operation (on rare occasions even a single AMP operation), NUSI access typically requires an All-AMP access of the index subtable.

Only if the NUSI consists of the same columns as the Primary Index of its base table, the index rows are searched on one AMP (the Teradata Optimizer knows in this case that only one AMP contains the rows of the base table and the index subtable).

Each NUSI row contains the ROWIDs of the related base table rows and to look up the base table row if the index is not covering.

NUSI index rows are not hash distributed, NUSI access always is an All-AMP access to the NUSI sub-table. In case the Teradata optimizer decides to use an existing NUSI instead of doing an FTS on the base table (based on cost considerations), but the NUSI index is not covering, the following approach is taken (on all AMPs at the same time):

At first,  the AMPs copy qualifying index rows into an AMP-local spool. This spool file contains the extracted base table ROWIDs.
Next, this spool file is used to access the base table rows.

Hash ordering versus value ordering

The rows in a Teradata NUSI sub-table can be ordered by ROWHASH or another 4-Byte Integer value, depending on intended use.

If you need to retrieve a range of dates, a value ordered NUSI on the data column makes sense (dates can be utilized, as Teradata stores them as 4-byte integer values). Before the availability of join indexes and partitioning, this was the only method to access ranges of dates in an optimized way.

If you have equality WHERE conditions on your query columns and the same columns in your NUSI, row hash ordering is probably the way to go. In this case, the AMPs can look up the searched value by doing a binary search on the NUSI index subtable rows which is the most efficient way of finding a data row.

Value ordering can only be used on exactly one 4-byte integer column. The reason for this limitation is the data block design and how rows are stored in a data block:

Teradata Secondary Index

Inside the data block, only the array of pointers to the start of each row is kept in order while rows are inserted wherever sufficient space is available.
Rows are not kept sorted as this would require permanent defragmentation activity.

In the case of row hash ordering, each entry in the row pointer array contains the row hash value (plus uniqueness value) of the related row. The row hash sorts the array. If the index is value ordered, each pointer array entry contains the value which is used for ordering, and this value sorts the array.

By design, the pointer array can hold the 4-byte row hash or any other 4-byte integer value. Without this limitation, the block structure could not be fixed as the array values stored could be of arbitrary length. For example, imagine you could use a character (2000) column for value ordering, in this case, you would need 2000 bytes space for each entry in the pointer array.

Any data type which is stored internally as an integer of 4 bytes can be used for value ordering, including for example INTEGER, DATE, DECIMAL (n, 0) where n occupies a maximum of 4 bytes.

Having accurate statistics is important. Any row qualification condition on the NUSI columns has to be highly selective. Otherwise, the optimizer is not going to use the NUSI. In the absence of collected statistics, the optimizer will do sample statistics, but the cost advantage for an NUSI usage is estimated more conservative in this case. On the other hand, table skewing may lead to the inappropriate use of the NUSI, even increasing the costs of the data access.

Requirements for a Teradata NUSI to be considered by the Optimizer

Teradata documentation says that if more than 10% of the table rows are qualifying, an existing NUSI is not used – this is only a rule of thumb. I have seen NUSIs being used where as much as 35% of the rows qualified and I have seen NUSIs being avoided by the optimizer although less than 1% of the table rows qualified.

There are other measures available to make better estimations about index usage:

The optimizer will only use a NUSI if the costs of accessing the qualifying rows in the index sub-table plus the costs of reading the base table data blocks containing the qualifying rows together are less than the expenses of a full table scan on the base table. There are additional considerations to be done in case several NUSI indexes are combined, or NUSI Bitmapping is applied.

The optimizer estimates the number of base table data blocks accessed (without index usage) based on the estimated qualifying rows for the considered index value, the data block size, and the row length. The qualifying rows are based on statistics (collected or sampled).

Let’s assume we have an average data block size of 1.000 bytes and we store rows with an average row length of 100 bytes. On average, we can store ten rows per data block.

Only if less than 10% (1 out of 10) of the rows qualify, the NUSI access will be considered efficient by the optimizer. Otherwise, a full table scan will be done. You may ask yourself, why? Because, going back to our example,  if we have to select more than 1 row out of 10, we are on average reading about one row per data block which is equal to a full table scan.

In our example, if we have less than 10% qualifying rows, the NUSI will be considered by the optimizer as not all base table data blocks will contain qualifying rows, but definitely, would have to be read in case of a full table scan.

Data blocks on the base table can be binary searched as rows are stored in row hash order. A full table scan directly on the base table would require checking all rows in all blocks sequentially!

Let us now take a look at some practical examples to carve out in which case a NUSI will be considered by the optimizer (always assuming the needed statistics are available and selectivity is strong):

 

Example Index on columns Equality WHERE condition Index Usage
1 {A, B} A Never used
2 {A,B} A, B Used if strong selectivity is given
3 {A,B} A,B,C Used if strong selectivity is given
4 Two separate NUSI, AND combined: {A},{B} A = ‘value1’ AND B = ‘value2’ Only one NUSI will be used (the one with the stronger selectivity).
5 Two separate NUSI, OR combined: {A},{B} A = ‘value1’ OR B = ‘value2’ Both NUSI will be used if strong selectivity is given
6 {A} LIKE ‘%value%’ Used if strong selectivity is given( NUSI subtable scan is done, no binary search)


May not seem obvious at first, but there is a good reason why the optimizer never decides to use the NUSI. We just have to remember how rows are stored in the index sub-table data blocks. A hash ordered NUSI would store the array of row pointers sorted by row hash value.  As we only have a constraint on column A, we cannot use the index hash value of {A, B} to execute a binary search on the index data blocks. Only a full table scan on the index sub-table would be available, but the optimizer never considers this an option.Example 1:

Example 2:

Example 2 is a perfect setup for the NUSI usage. Assuming that selectivity is strong, the optimizer will use the NUSI. The Row hash of the index matches the row hash of the WHERE condition columns {A, B} which allows the calculation of the hash value of the WHERE condition. By knowing this hash value, the rows can easily be looked up in the index sub-table applying a binary search on the row pointer array.

Example 3:

Not as perfect as Example 2, but still worth to be considered by the optimizer: only columns {A, B} of the WHERE condition are used for hash value calculation i.e. again row hash values match with the row hash values of the NUSI sub-table.

A binary search on the row pointer array is executed, the remaining qualifier on column C is applied as the residual condition.

Example 4:

Two or more NUSI which are combined with AND may be used together in the following way (at least one has to have strong selectivity):

If several NUSI is available, the optimizer will choose exactly one of them, namely the NUSI with the greatest selectivity. Nevertheless, there is another method of combining several NUSI with weak selectivity: NUSI Bitmapping. We will talk about this soon.

Example 5:

Two or more NUSI combined with OR (all of them need high selectivity) may be used together in the following way:

The ROWIDs are retrieved from index {A} and index {B} and moved into a common spool. ROWID duplicates are removed from the spool; this requires a spool sort step. If the index is not covering, base table rows are accessed via the ROWIDs.

Some important remarks:

(1) The optimizer considers the sort step mentioned above as very costly. Even if selectivity is high, if many rows have to be sorted, the optimizer may reject NUSI usage.

(2) If you have two WHERE conditions which are OR combined, but only a NUSI on one of them, the optimizer will always choose a full table scan (which should be obvious, as the WHERE condition without NUSI anyway requires an FTS, there is no value in accessing the available NUSI)

(3) If the optimizer rejects the usage of two NUSIs because it considers the sort step too costly, the query can be rewritten to enforce the usage of both NUSI:

SELECT * FROM table WHERE colA = ‘value1’ OR colB = ‘value2’

can be rewritten to:

SELECT * FROM table WHERE colA = ‘value1’
UNION
SELECT * FROM table WHERE colB = ‘value2’

If both NUSIs have high selectivity, the optimizer will use them (as the sort step has moved to the “execution logic” and is not any more input to the optimizer cost estimation).

 

Example 6:

A full table scan accesses the index rows on the index sub-table. No binary search on the data blocks can take place; each block has to be checked (therefore full table scan). Nevertheless, the optimizer may use the index if it assumes the index sub-table FTS to take place on a much smaller table than the base table might be. Be aware, only like ‘x%’ queries will work as the optimizer can derive estimations from available statistic histograms on the index column. Something like ‘%x%’ does not operate as no statistics can be calculated.

The Value Ordered NUSI

We were already talking shortly about value ordering. A value ordered NUSI is especially useful for range scans, as the retrieval of rows in a range of dates. Master Index and Cylinder Index hold information about all NUSI data blocks containing qualifying rows. The search within a NUSI data block can be stopped as soon as the looked up value in the row pointer array moves outside the searched value;  typically is an FTS on the NUSI subtable on a limited range within the data blocks.

NUSI Bitmapping

The optimizer can use NUSI bitmapping to combine several NUSI with weak selectivity. Bitmapping is a proprietary algorithm which comes with its cost overhead, making usage for us even less predictable.  NUSI bitmapping only is available if more than one WHERE condition is combined with AND. NUSI Bitmapping is used if several NUSI with weak selectivity can be combined and the combined usage results in high selectivity.

Let me give you an example: Consider a table has two columns:

The first column is the GENDER, and the table contains 50% men and 50% women. A NUSI on gender probably would have weak selectivity.
The second column is a “has beard” flag. It is a flag with two manifestations “yes” or “no.” Let’s assume most of the men in our example table have a beard. A NUSI on “has a beard” probably has weak selectivity.

None of both NUSI alone would be used by the optimizer as an FTS would probably be cheaper.

Now, as you may know, we have a song contest in Europe. This time a lady with a beard won the song contest. As you can imagine, this is a very rare combination. If we would look up this person in our table, both NUSI could be combined, and together they would have high selectivity.

Index Coverage / The Index-Only access

NUSI full or partial coverage is possible. Full coverage means that no access to the base table rows is needed to fulfill the request. Otherwise, base table rows have to be extracted and a spool is used to access the base table rows in a second step. NUSI full coverage is given if any of the following prevails:

  • No reference to columns other than those in the NUSI
  • NUSI includes all columns in the base table referenced and upon reference to a character column is has to be either NOT CASESPECIFIC or UPPERCASE

The usual approach for testing a NUSI is:

Create the NUSI you would like to be used and check if it’s indeed used (EXPLAIN statement says something like “by traversing index #1” or “by way of index #1”). If it is used keep it, otherwise drop it (remember, secondary indexes are physical tables occupying disk space).

 

What is the appropriate Teradata NUSI Workload?

A USI allows direct access to the data records (I try to avoid the term “data rows” in times of column stores) and is appropriate for workload where direct access is an advantage (for example: looking up a single customer). NUSI access seems more useful than USI access in cases you need to access many data rows at once. The recommended workload is, therefore, decision support. OLTP environments tend to include a load of DML operations causing substantial index maintenance.

Teradata Load Utilities and the NUSI

It is not possible to load into a table with the Fastload utility if there is a NUSI defined on the table. The usual solution is to drop the NUSI before loading and recreating if afterward. This restriction is fine as Fast loads can only be run against empty tables anyway. On the other hand, Multiloads are compatible with a NUSI. You do not need to drop the NUSI before loading. Nevertheless, from a performance point of view, you may consider the same drop and recreate approach like for a Fastload.

More on indexing here:
Teradata Indexing
The Primary Index Choice

 

Our Reader Score
[Total: 16    Average: 3.8/5]
NUSI – The Nonunique Secondary Index in Teradata written by Roland Wenzlofsky on November 11, 2014 average rating 3.8/5 - 16 user ratings

3 COMMENTS

  1. There is no FTS scan required but a scan on a range. This means that not all data blocks have to be moved from the disk to the FSG cache, but only a limited range of blocks. Nevertheless, NUSI access is always an all-AMP operation, as the index rows of the NUSI are co-located with the base table rows. I like to distinguish between the following kind of access types:

    (1) all-AMP versus single-AMP or group-AMP
    (2) Sequential search versus binary search (within data blocks).

    FTS, for example, is always done via a sequential search of all data blocks (or a range of blocks like in our NUSI example above).

    We have the following combinations (leaving out partitioning for the moment and examples in brackets):

    – All-AMP sequential search (FTS)
    – All-AMP binary search (NUSI with hashed access)
    – All-AMP, sequential search (NUSI access via FTS on range of or the complete index subtable)
    – Single-AMP (group-AMP) with binary seach (indexed lookup: UPI, NUPI, USI)

    The Join Index can cover some of above combinations, depending if accessed via the primary index or FTS (for example, if the optimizer prefers to to a FTS on the smaller join index than on the base table).

    I hope these examples answered your question.

    Best Regard,

    Roland

  2. “By sorting the NUSI rows by data value, it is possible to search only a portion of the index subtable for a given range of key values. The major advantage of a value-ordered NUSI is in the performance of range queries.” – so by this statement no FTS or no All-AMP access is required right? please clarify.

LEAVE A REPLY

Please enter your comment!
Please enter your name here