16.10 - NUSI Bit Mapping - Teradata Database

Teradata Database Design

Teradata Database
Release Number
Release Date
June 2017
Content Type
User Guide
Publication ID
English (United States)

Bit mapping is a technique used by the Optimizer to effectively link several weakly selective indexes in a way that creates a result that drastically reduces the number of base rows that must be accessed to retrieve the desired data. The process determines common rowIDs among multiple NUSI values by means of the logical intersection operation. The method is explained in more detail in the following sections.

Performance Advantages of NUSI Bit Mapping

Bit mapping is significantly faster than the three-part process of copying, sorting, and comparing rowID lists. Additionally, the technique dramatically reduces the number of base table I/Os required to retrieve the requested rows.

Restrictions for When Bit Mapping Is Used

Teradata Database only performs NUSI bit mapping when weakly selective indexed conditions are ANDed. When WHERE conditions are connected by a logical OR, the Optimizer typically performs a full-table scan and applies the ORed conditions to every row without considering an index.

Note that this is not always the case. If the weakly selective ORed conditions are ANDed with other weakly selective conditions, but the composite selectivity is high, the Optimizer may choose to use a composite NUSI or a single-column NUSI.

IF all conditions are ANDed together and … AND their composite selectivity is … THEN the Optimizer…
one index is strongly selective   selects it alone and applies the remaining constraints to the selected rows as residual constraints.
all of the indexes are weakly selective also weakly selective performs a full-table scan and applies the conditions to every row.
all of the indexes are weakly selective strongly selective can instruct each AMP to construct bit maps to determine which rowIDs their local NUSI rows have in common and then access just those rows, applying the conditions to them exclusively.

For example, consider the following SELECT statement with three WHERE conditions, each of which has a weakly selective NUSI defined on its column.

     SELECT *
     FROM employee_table
     WHERE salary_amount > 20000
     AND   sex_code = ‘M’
     AND   full_time = ‘FT’;

Suppose that the index on salary_amount has 30% selectivity, the index on sex_code 50% selectivity, and the index on full_time 70% selectivity. The individual selectivity of these indexes is very weak.

If the overlap among their selectivities is such that the effect of combining their relative weaknesses results in a significant strength, then the Optimizer instructs the AMPs to use bit mapping to do just that, and the end result is vastly improved performance of the retrieval in comparison with a full-table scan.

In this example, the overlap selectivity is 9%, which is both significantly better than any of the individual selectivities of the NUSIs in the query and typically better than a full-table scan. This assumes fewer than 10 rows per data block. The figure must be adjusted for larger data blocks that can contain many more rows.

Using NUSIs For Complex Conditional Expressions

Complex conditional expressions can be based on nonunique secondary indexes. Bit mapping is often used to solve such expressions when they are applied to a very large table. NUSI bit mapping can be used if the following statements are both true for the conditions under consideration.

  • There are at least two NUSI equality conditions.
  • All the NUSI conditions are ANDed.

Take the following request as an example.

     FROM LargeTable
     WHERE NUSI_1 = ’condition_1’
     AND   NUSI_2 = ’condition_2’
     AND   NUSI_3 = ’condition_3’
     AND   NUSI_4 = ’condition_4’;

To resolve this request, a bit map is built for n-1 referenced indexes (see stage 2 in the process documented on the following page). For this example, n=4, so the system builds three bit maps. In each bit map, every qualifying data row bit is turned ON.

The bit maps are ANDed to form one large bit map, which is held in a spool. The ON bits are used to access the result data rows directly.

The most selective index of the four accesses rows based on whether the bit is ON for the rowID in the ANDed bit map for the rowID from the previous NUSI.

Computing NUSI Bit Maps

We use the following previously described query to example how NUSI bit maps are computed.

     SELECT *
     FROM employee_table
     WHERE salary_amount > 20000
     AND   sex_code = ‘M’
     AND   full_time = ‘FT’;

Recall the truth table for the AND operator.

    0 + 0 = 0
    0 + 1 = 0
    1 + 0 = 0
    1 + 1 = 1

The following process illustrates the method for computing NUSI bit maps. The actions described occur concurrently on all AMPs.

  1. The literals 20,000, M, and FT are used to access the corresponding rows from the index subtables.
  2. For n-1 indexes, each AMP creates separate bit maps of all 0 values.

    In this case, n-1 is 2 because there are three NUPIs defined, one for each condition in the WHERE clause.

  3. Using a proprietary algorithm, the AMPs equate each base table rowID in each qualifying NUPI row with a single bit in the map, and each such map bit is turned ON.
  4. The resulting bit maps are ANDed together to form the final bit map.
  5. Each base table rowID in the remaining NUSI is equated to a single bit in the final bit map, and the state of that map is checked.
IF the map bit is … THEN …
OFF (0) no action is taken and the next map bit is checked.
ON (1) the rowID is used to access the table row and all remaining, or residual, conditions are applied to that row.

Determining If Bit Mapping Is Being Used

To determine whether bit mapping is being used for your NUSIs, use the EXPLAIN request modifier and examine the reports it produces for your queries.

Example: Bit-Mapping Process

The table queried contains the following set of rows.

Example table
Base Table      
RowID column_1 column_2 column_3
12,07 A B C
22,03 A C C
48,12 A B D
63,15 B B C

The query ANDs three equality conditions on three NUSI columns in the WHERE clause.

     SELECT *
     FROM Base_Table
     WHERE column_1 = ‘A’
     AND   column_2 = ‘B’
     AND   column_3 = ‘C’;

The Optimizer evaluates the query and determines that bit mapping over the three columns is the least costly access plan.

The truth table looks like this.

NUSI Column     Number Value Required To        Satisfy Condition Base Table RowID List
12,07 22,03 48,12 63,15
1 A 1 1 1 0
2 B 1 0 1 1
3 C 1 0 0 0
ANDed Sum: 1 0 0 0

Of the four rows examined in the example, only the row identified by RowID 12,07 qualifies and is returned to the requesting application.

Related Topics

Also see the topic “EXPLAIN Request Modifier” in SQL Data Manipulation Language ,the chapter “Interpreting the Output of the EXPLAIN Request Modifier” in SQL Request and Transaction Processing, and Teradata Visual Explain User Guide.