The Teradata NUSI or Nonunique Secondary Index

The Technical Details of the Nonunique Secondary Index in Teradata – NUSI

Like any index of a relational database system, the Teradata NUSI provides an alternative access path to the rows of a table. Indexes serve to keep the resource consumption (especially IOs) as low as possible. While historical databases such as Oracle use B+ trees for indexing, Teradata uses hashing. By the way, hashing is one of the most widespread indexing methods for shared-nothing database systems and is also used, for example, in Amazon Redshift and similar Postgres-based database systems.

In Teradata, the secondary index comes in two flavors. The USI or Unique Secondary Index and the NUSI or Non-Unique Secondary Index. You might think that they are very similar but in fact, they are two very different implementations. In this article, we will look at the Teradata NUSI but also explain the differences to the USI so you know when to use which index.

The most important difference between the Teradata NUSI to the USI but also all other indexes (UPI, NUPI, etc.) is how the rows of a table are assigned to the AMPs. As with the USI, the NUSI is also stored as a separate sub-table to the base table. While the rows of the USI are distributed according to the hash which is calculated over the USI columns, the NUSI rows are always on the same AMP as the corresponding rows of the base table. This is the main difference that has a big influence on the use of the NUSI.

By the way, it should be mentioned that information about the NUSI is not available in the data dictionary for us users. For the join index, for example, we can query information in the database DBC.

If we look at the design of the NUSI, it becomes clear that the Teradata Optimizer cannot determine by hashing on which AMP a NUSI Row is located. Therefore, the NUSI access is almost always an all-AMP operation. It should be noted that this is often a problem for tactical queries. There is one exception for which the NUSI access can be done via a single AMP operation: When the NUSI columns match the primary index of the table. In this particular case, the NUSI can also be useful for tactical queries. By placing a NUSI over the primary index of a row partitioned table it can be achieved that partition probing is not necessary. This can bring performance advantages for large tables with many partitions if not all partition columns are part of the primary index.

Normally the USI is a 2 AMP access (in exceptional cases also Single-AMP), and the NUSI is All-AMP access.

The NUSI can be used by the optimizer in many ways. The Index Row consists of the columns of the index and all ROWIDs of the associated base tables rows. The optimizer can therefore fetch missing information from the base table if the index is not covering. To do this, first, an AMP local spool is created with relevant index rows, then the ROWIDs are used to access the corresponding base table rows.

Hash ordering versus value ordering

Depending on the intended use, the rows in a Teradata NUSI sub-table can be ordered by ROWHASH or any 4-Byte INTEGER value.

If we need to retrieve a range of dates, a value ordered NUSI on the DATE column is efficient (DATES can be used, as Teradata stores them internally as 4-byte INTEGER values). Before the availability of join indexes and partitioning, the value-ordered NUSI was the only method to access ranges of dates efficiently.

Let’s assume that we use an equality condition in our SQL in the WHERE clause and have defined a NUSI on exactly these columns. In this case, a hash-ordered NUSI (which is the default method) is more suitable. The searched rows can be efficiently found by a binary search in the NUSI sub-table.

Teradata can only use value order on precisely one 4-byte integer column. This limitation is given by the data block design and how rows are stored inside a data block:

Inside the data block, only the array of pointers to each row’s start is kept in order, while the row’s data itself is 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 sorted row hash values (including uniqueness value) of the corresponding row. If the index is value ordered, each pointer array entry contains the sorted INTEGER values used for ordering.

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 we were allowed to use a character (2000) column for value ordering. In this case, we would need 2000 bytes of space for each entry in the pointer array.

We can use any data type stored internally as an integer of 4 bytes for value ordering, including INTEGER, DATE, DECIMAL (n, 0), where n occupies a maximum of 4 bytes.

Having accurate statistics is essential. 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 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 data access costs.

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 when as much as 35% of the rows qualified, and I have witnessed NUSIs being avoided by the OOptimizer, 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 accessing the qualifying rows in the index sub-table. The costs of reading the base table data blocks containing the qualifying rows together are less than a full table scan expense on the base table. Additional considerations should be made if several NUSI indexes are combined or NUSI Bit mapping 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 keep ten rows per data block.

Only if less than 10% (1 out of 10) of the rows qualify for the NUSI access will it be considered efficient by the OOptimizer. Otherwise, Teradata will do a full table scan. 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 Optimizer will consider the NUSI 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 sequentially checking all rows in all blocks!

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):

It may not seem evident at first, but there is a good reason why the Optimizer never uses the NUSI. We must remember how rows are stored in the index sub-table data blocks. A hash-ordered NUSI would hold 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 OOptimizer never considers this an option. Example 1:

Example 2:

Example 2 is a perfect setup for 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, Teradata can quickly look up the rows in the index sub-table by 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 combined with AND may be used together in the following way (at least one has to have strong selectivity):

If several NUSIs are available, the Optimizer will choose precisely one of them, the NUSI, with the greatest selectivity. Nevertheless, another method of combining several NUSI with weak selectivity is NUSI Bit mapping. 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 very costly. Even if selectivity is high, if many rows have to be sorted, the OOptimizer may reject NUSI usage.

(2) If you have two WHERE conditions that 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, we can rewrite the query to enforce the use of both NUSIs:

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 no more input to the optimizer cost estimation).

Example 6:

A full table scan accesses the index rowson the index sub-table. No binary search on the data blocks can occur; each block must be checked (therefore, full table scan). Nevertheless, the Optimizer may use the index if it assumes the index sub-table FTS on a much smaller table than the base table. Be aware that only like ‘x%’ queries will work as the OOptimizer can estimate 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. The master and Cylinder Index contain information about all NUSI data blocks containing qualifying rows. The AMP can stop the search within a NUSI data block as soon as the looked-up value in the row pointer array moves outside the searched value; typically, an FTS on the NUSI subtable on a limited range within the data blocks.

NUSI Bit mapping

The Optimizer can use NUSI bit mapping to combine several NUSIs with weak selectivity. Bitmapping is a proprietary algorithm with cost overhead, making usage even less predictable for us. NUSI bit mapping only is available in more than one WHERE condition is combined with AND. NUSI Bit mapping 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.

The Optimizer would use neither NUSI alone, as an FTS would probably be cheaper.

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 scarce combination. If we looked up this person in our table, both NUSI could be combined, and they would have high selectivity.

Index Coverage / The Index-Only access

NUSI full or partial coverage is possible. Complete coverage means 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, it 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 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 workloads where immediate access is an advantage (for example: looking up a single customer). NUSI access seems more practical than USI access if 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 impossible 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 recreate it afterward. This restriction is acceptable as Teradata can only run fast loads against empty tables. On the other hand, Multiloads are compatible with a NUSI. You do not need to drop the NUSI before loading. Nevertheless, you may consider the same drop and recreate approach from a performance point like for a Fastload.

More on indexing here:
Teradata Indexing
The Primary Index Choice