Merge Join | Join Planning/Optimization | Teradata Vantage - Merge Join - Analytics Database - Teradata Vantage

A merge join retrieves rows from two tables by processing equality joins that probe one table using row key or row hash values from the qualified rows in the other table. A merge join assumes that the probed table is sorted either by row key or row hash. The operation then puts the joined rows onto a common AMP based on the row key or row hash of the join columns. The database sorts the rows into join column row key or row hash sequence, then joins those rows that have matching join column row key or row hash values.

In a merge join, the columns on which tables are matched are also the columns on which both tables, or redistributed spools of tables, are ordered. Merge join is generally more efficient than a product join (see Product Join) because merge join requires fewer comparisons and because blocks from both tables are read only once.

Merge Join Methods

Dynamic row partition elimination is not supported for merge joins of multilevel partitioned tables. For more information, see Product Joins With Dynamic Row Partition Elimination and Teradata Vantage™ - Database Design, B035-1094.

Approaches to Merge Joining Row-partitioned PI Table to Unmatched Relation

In all cases, the Optimizer considers all reasonable join strategies and selects the one with the least estimated cost.

Generic Merge Join Strategy

The following is the high level process applied by the merge join algorithm:

1. Identify the smaller relation of the pair to be joined.
2. The Optimizer pursues the following steps only if necessary to place qualified rows into a spool.
   1. Place the qualifying rows from one or both relations into separate spools.

      As the qualified rows are placed into spool, relocate those rows to their target AMPs based on the rowkey or hash of the join column set.

   2. Sort the qualified spool rows on their join column rowkey or row hash values.
3. Compare the relocated row set with matching join column row hash values in the other relation.

Dynamic Row Partition Elimination for Merge Join with Equality Join Terms

When there are equality join terms on all primary index columns of a single-level row-partitioned PI table plus certain forms of range join terms on the partitioning column, then the Optimizer may use a merge join with dynamic row partition elimination to make the join.

You can think of this as a form of sliding window merge join (see Sliding-Window Merge Join) with the row-partitioned PI table in which the other table being joined is partitioned the same way as the row-partitioned PI table, and a subset of the partitions in one table is joined to a subset of the row partitions in the other table as determined by the specified range terms.

Dynamic row partition elimination-applicable join terms must be specified in one the following forms:

{ ppi_t1.partitioning_column_1 + C1 operator  ppi_t2.partitioning_column_2 |
  ppi_t2.partitioning_column_2 operator   ppi_t1.partitioning_column_1 + C2 |
  ppi_t1.partitioning_column_1 + C1 operator ppi_t2.partitioning_column_2 |
  ppi_t2.non_partitioning_column_2 operator ppi_t1.ppi_column_1 + C2
}

ppi_t1.partitioning_column_1

A partitioning column for table ppi_t1.

C1

C2

A constant.

operator

One of the following join operators:

• <
• <=
• =>
• >

ppi_t2.partitioning_column_2

A partitioning column for table ppi_t2.

ppi_t2.non_partitioning_column_2

A nonpartitioning column for table ppi_t2.

ppi_t1.ppi_column_1

A column for table ppi_t1.

Merge Join with Dynamic Row Partition Elimination Not Supported for Character-Partitioned Tables

Because you cannot arithmetically add strings together, and because string intervals are not defined, merge join dynamic row partition elimination is not supported for character-partitioned tables.

Slow Path Inner Merge Join

The process applied by the slow path merge join algorithm is as follows:

1. Read each row from the left table.
2. Join each left table row with the right table rows having the same hash value.

Fast Path Inner Merge Join

The process applied by the fast path merge join algorithm is as follows:

1. Read a row from the left table and record its hash value.
2. Read the next row from the right table that has a row hash >= to that of the left table row.

The following graphic illustrates the generic fast path merge join process:

Merge Join Distribution Strategies

Merge joins use one of the following distribution strategies:

Merge Join Examples

The following SELECT request determines who works in what location by merge joining the employee and department tables on the condition that the dept_no values in both tables are equal:

SELECT name, dept_name, loc
FROM employee INNER JOIN department
WHERE employee.dept_no = department.dept_no;

The following list presents the stages of processing this merge join.

1. Because department rows are distributed according to the hash code for dept_no (the unique primary index of the department table), employee rows are themselves redistributed by the hash code of their own dept_no values.
2. The redistributed employee rows are stored in a spool on each AMP and sorted by the hash value for dept_no.

   This puts the redistributed rows in the same order as the department rows on the AMP.

3. The hash value of the first row from the department table is used to read the first row with the same or bigger row hash from the employee spool.

   That is, rows from either table of a merge join are skipped where possible.

4. If there is a hash codes match, an additional test is performed to verify that the matched rows are equivalent in dept_no value as well as hash value.
5. If there is no hash code match, then the larger of the two hash codes is used to position to the other table.

   The hash code and value comparisons continue until the end of one of the tables is reached.

6. On each AMP the name, dept_no, and loc values from each of the qualifying rows are placed in a result spool.
7. When the last AMP has completed its merge join, the contents of all result spools are merged and returned to the user.

When multiple rows fail to meet a constraint, the hash-match-reposition process may skip multiple rows. Skipping disqualified rows can speed up the merge join execution, especially if the tables are large.

The following graphic illustrates this merge join process:

The next merge join example uses the following table definitions:

Column e_num is the UPI and PK of the table, and dept is a FK.

Column dept is the UPI and PK of the table.

One of the merge join row redistribution methods is used if you perform the following SELECT request against these tables:

SELECT *
FROM employee INNER JOIN department
WHERE employee.dept = department.dept;

Merge Join Row Distribution (Hash Redistribution)

The following graphic shows a merge join row distribution using hash redistribution:

Merge Join Row Distribution (Duplicate Table)

The following graphic shows a merge join row distribution by duplicating a table:

This example uses the following employee and employee_phone table definitions:

Column e_num is the UPI and PK of the table.

Column e_num is the NUPI and a FK of the table, and all three columns constitute the PK.

The matching indexes row distribution strategy is used if you perform the following SELECT request against these tables.

SELECT *
FROM employee INNER JOIN employee_phone
WHERE employee.e_num = employee_phone.e_num;