Dramatically improve Performance with the Teradata Nested Join

0
2283

We know that the Primary Index offers the least costly data access. When it comes to joining, most of us are familiar with merge joins, hash joins, and product joins, but the nested join is less known, as it is seldom used in a data warehouse environment where most of the workload is strategic.

 

What is the Teradata Nested Join?

The Teradata Nested Join can be the least costly way of joining two tables.

Its strength lies in the fact that it allows index access to single rows, which is a common need in OLTP environments.

The Teradata Optimizer can only use a Nested Join if the following conditions are met:

  1. There is a restriction (where clause) on the left table, which is covered by a USI, UPI or NUPI.
  2. The Join hast to be an equijoin.
  3. There is an index on the right table, covering the join columns
    The index can be a UPI, NUPI, USI, NUSI or a Join Index including the ROWID columns

The following example will carve out the technical foundation, based on below first scenario:

CREATE TABLE LEFT_TABLE
(
PK INTEGER NOT NULL,
ALT_PK INTEGER NOT NULL,
COL1 INTEGER
) UNIQUE PRIMARY INDEX (COL1);
CREATE TABLE RIGHT_TABLE
(
PK INTEGER NOT NULL,
ALT_PK INTEGER NOT NULL
) UNIQUE PRIMARY INDEX (ALT_PK);
SELECT *
FROM
LEFT_TABLE l
INNER JOIN
RIGHT TABLE r
ON
l.ALT_PK = r.ALT_PK
WHERE COL1=100;

Our example above meets all conditions for a Nested Join:

  • The restriction on the left table index column: WHERE COL1 = 100
  • The join is an equijoin: l.ALT_PK = r.ALT_PK
  • There is an index defined on the righ table, covering the join columns (l.ALT_PK = r.ALT_PK), namely the UPI.

Indeed, the Explain Plan shows, that a Nested Join is used for this query:

First, we do a single-AMP JOIN step from l by way of  the unique primary index “l.COL1 = 100” with no  residual conditions, which is joined to all partitions of  r by way of the primary index “r.ALT_PK = l.ALT_PK” with no residual conditions.  l and r are joined using a nested join, with a join  condition of (“(1=1)”).  The result goes into Spool 1 (one-amp),   which is built locally on the AMPs.  The size of Spool 1 is  estimated with low confidence to be 1 row (41 bytes). 

Although the equi-join is executed on a column which is not the Primary Index of the left table, nor the Primary Index of the right table, the execution plan is not involving a full table scan or any kind of change in data demographics (redistribution, duplication), like it would be required as preparation for a Merge Join or Hash Join.

The Explain Plan reveals, that exactly one row is accessed, and only one AMP is involved. There is no cheaper way available to execute the query like this one.

The Local Nested Join

Our example from the previous section was a so-called Local Nested Join.

This kind of Nested Join requires a unique index on the left table (UPI, USI). Furthermore, the right table index, covering the join columns, must not be an NUSI (we will explain the reason for this later).

As the unique index on the left table ensures that only one row is returned after applying the WHERE condition, the following algorithm can be used:

  1. The rowhash value over the join columns of the left table is calculated.
  2. The calculated rowhash value is used to send a message to the AMP holding the right table rows.
  3. The AMP holding the right table rows returns them to the initiating AMP.
  4. The initiating AMP assembles the last rows and returns them to the result spool.

The Nested Join is one of the fastest ways of joining on a Teradata System.

Our example query from above works in the same way, if we have an USI covering the left table WHERE condition:

CREATE TABLE LEFT_TABLE
(
PK INTEGER NOT NULL,
ALT_PK INTEGER NOT NULL,
COL1 INTEGER
) PRIMARY INDEX (PK);
UNIQUE INDEX (COL1);
CREATE TABLE RIGHT_TABLE
(
PK INTEGER NOT NULL,
ALT_PK INTEGER NOT NULL
) UNIQUE PRIMARY INDEX (ALT_PK);
SELECT *
FROM
LEFT_TABLE l
INNER JOIN
RIGHT TABLE r
ON
l.ALT_PK = r.ALT_PK
WHERE COL1=100;
First, we do a two-AMP JOIN step from l by way of unique index # 4 “l.COL1 = 100” with no residual   conditions, which is joined to all partitions of r by  way of the primary index “r.ALT_PK = l.ALT_PK” with no residual conditions.  l and r are joined using a nested join, with a join  condition of (“(1=1)”).  The result goes into Spool 1 (one-amp),  which is built locally on the AMPs.  The size of Spool 1 is   estimated with low confidence to be 1 row (41 bytes). 

The only difference is the usage of the USI (by way of index # 4) instead of an UPI access.

The Remote Nested Join

The Remote Nested Join is another nested join method which is used in the following scenarios:

  • The left table index covering the WHERE condition is not unique (NUPI) or
  • The right table index covering the join columns is an NUSI

The following process describes how the join works internally:

  1. The left table rows are distributed by the join column rowhash or duplicated to all AMPs.Which kind of distribution is required, depends on the type of index available on the right table.Whenever the right table index is an NUSI, row duplication to all AMPs is needed: NUSI index rows are not rowhash distributed, and matching rows could be available on any AMP.
    Any other kind of right table index will cause a redistribution of the left table rows by hashing on the join columns.
  2. A join between the left table rows and the right table index is executed. The base table rowids are extracted from the index and moved into a spool.
  3. The spool presents the new left table for a second physical join step, the so-called RowId Join.
  4. The extracted rowids are used to access the base table rows of the right table.
    Depending on the kind of right table index, this may need to get access to the base table rows on a different AMP (USI) or from the same AMP (NUSI)
    Remember: NUSI index rows are always co-located together with their base table rows on the same AMP!

Below example leads to a Remote Nested Join because the right table index (covering the join columns) is an NUSI:

CREATE TABLE LEFT_TABLE
(
PK INTEGER NOT NULL,
ALT_PK INTEGER NOT NULL,
COL1 INTEGER
) UNIQUE PRIMARY INDEX (COL1);
CREATE TABLE RIGHT_TABLE
(
PK INTEGER NOT NULL,
ALT_PK INTEGER NOT NULL
) UNIQUE PRIMARY INDEX (PK )
INDEX (ALT_PK);
SELECT *
FROM
LEFT_TABLE l
INNER JOIN
RIGHT TABLE r
ON
l.ALT_PK = r.ALT_PK
WHERE COL1=100;
3) We do a single-AMP RETRIEVE step from l by way of the unique primary index “l.COL1 = 100” with no residual conditions into Spool 2 (all_amps), which is duplicated on all  AMPs.  Then we do a SORT to order Spool 2 by the hash code of (l.ALT_PK).  The size of Spool 2 is estimated with high confidence to be 72 rows (1,800 bytes).  The estimated time for this step is 0.00 seconds. 4) We do an all-AMPs JOIN step from Spool 2 (Last Use) by way of an all-rows scan, which is joined to r by way of a traversal of index # 4 without accessing the base table extracting row ids only.  Spool 2 and r are joined using a nested join, with a join condition of (“ALT_PK = r.ALT_PK”).  The result goes into Spool 3 (all_amps), which is built locally on the AMPs.  Then we do a SORT to order Spool 3 by field Id 1.  The size of Spool 3 is estimated with low confidence to be 1 row (35 bytes).  The estimated time for this step is 0.02 seconds. 5) We do an all-AMPs JOIN step from Spool 3 (Last Use) by way of an all-rows scan, which is joined to r by way of an  all-rows scan with no residual conditions.  Spool 3 and  r are joined using a row id join, with a join  condition of (“(1=1)”).  The result goes into Spool 1 (group_amps),  which is built locally on the AMPs.  The size of Spool 1 is  estimated with low confidence to be 1 row (41 bytes).  The    estimated time for this step is 0.04 seconds.

As the Explain Plan reveals, there are two physical join steps involved: “using a nested join” and in a later step “using a rowid join”.

While the Remote Nested Join still is a very fast way of joining, it involves some overhead for data move and the next rowid join. Nevertheless, assuming that usually only a few rows are selected by the WHERE condition, this should not have any significant impact on the join performance.

Some Final Words

The Teradata Nested Join can be a highly effective way of joining in OLTP environments. It usually involves just a few AMPs, and it is worth to check your queries for possible Nested Join scenarios by adding more indexes (NUSI, USI) and WHERE conditions on indexed columns.

In a recent client project, I could decrease query run times dramatically, by adding only one NUSI, which allowed the optimizer to execute a Nested Join and getting rid of a full table scan. While the original query is running about 20 minutes, the improved one delivers the result set within a few seconds.

Despite the fact, that the Teradata documentation is telling us something else, a Nested Join is possible even if the WHERE condition of the left table is covered by a nonunique primary index (NUSI), uniqueness is not a must.

In this case, the Remote Nested Join variant will be used, the join process is similar to our last example (involving an NUSI on the right table), and a left table row move is required (duplication, redistribution).

Furthermore, there does not always have to be a WHERE condition available on the left table. If the Teradata Optimizer estimates only a few left table rows, it can execute a Remote Nested Join without any restriction.

In general, the Teradata Optimizer will consider a Nested Join if the estimated number of left table rows is tiny (basically, a few rows).

See also:
Tactical Workload Tuning on Teradata

Our Reader Score
[Total: 16    Average: 4.3/5]
Dramatically improve Performance with the Teradata Nested Join written by Roland Wenzlofsky on April 29, 2015 average rating 4.3/5 - 16 user ratings

LEAVE A REPLY

Please enter your comment!
Please enter your name here