Sliding-Window Merge Join | Join Planning/Optimization | Teradata Vantage - Sliding-Window Merge Join - Advanced SQL Engine - Teradata Database

About the Sliding-Window Merge Join

A direct merge join cannot be used when one table is partitioned and the other is not, or when both tables are partitioned, but not partitioned identically, because the rows of the two tables are not ordered in the same way. The sliding-window merge join, which is PPI-aware, can be applied by the Optimizer to cover situations that the standard direct merge join cannot. Sliding-window joins can be slower than a merge join or rowkey-based merge join when there are many noneliminated nonempty combined partitions; however, a sliding-window merge join can provide roughly similar elapsed time performance (but with greater CPU utilization and memory consumption) when the number of noneliminated nonempty combined partitions is small.

Sliding-window merge joins follow the general principle of structuring each of the left and right relations into windows of appropriate sizes, appropriate in terms of the number of partitions required as determined by the Optimizer based on the available memory for making the join. The join is done as a product join between each of these left and right window pairs. The operation uses the identical algorithm to that used for a regular merge join within each window pair with the exception that the rows are not necessarily in row hash order across the multiple partitions within a window.

The obvious way to join a nonpartitioned table to a row-partitioned PI table would be to make one pass over the nonpartitioned table for each noneliminated nonempty partition of the row-partitioned PI table, executing the join as a series of subjoins. It turns out that this is an inefficient way to make the join, especially for a large nonpartitioned table. To escape the inefficiency of this method, the sliding-window merge join uses a similar concept, but minimizes the number of disk reads.

1. The system reads the first data block for the nonpartitioned table, and then reads the first data block of each noneliminated nonempty combined partition of the row-partitioned PI table into memory.
2. The rows from the nonpartitioned data block are compared to the rows of each row-partitioned PI data block.

   The join routines present the rows in row hash order, but you can think of the process as visiting the data block for each combined partition in turn.

3. As the rows of a data block are exhausted, the system reads the next data block for that combined partition.

   This results in each data block of each table being read only once. This is because of partitioning. Merge joins usually have to read some number of rows in one of the tables multiple times, either from disk or from cache. There is some additional overhead to manage the pool of data blocks, but join performance is not badly degraded when the window covers all noneliminated nonempty combined partitions.

If a non-trivial fraction of the combined partitions can be eliminated because of query conditions or because they are empty, overall performance can be improved, perhaps dramatically, over a traditional merge join, depending on the percentage of combined partitions that can be eliminated or are empty.

A limiting factor for the sliding-window merge join algorithm is the number of data blocks that can be contained in memory at the same time. The file system cache memory provides memory for the data blocks.

The DBS Control performance field PPICacheThrP controls memory usage for this purpose. The value is a number expressed in tenths of a percent of the file system cache available for each query step that needs a sliding window.

The default value for PPICacheThrP is 10, which represents 1%.

A significant degradation of join performance can occur when there are more noneliminated nonempty combined partitions than data block buffers. Assume enough memory has been allocated for 20 data blocks and a table with 100 partitions. In this case, the sliding window method is appropriate. The first 20 combined partitions are processed as they should be, and then the system reads the nonpartitioned table again as the join window slides down to combined partitions 21 through 40. A total of five passes through the nonpartitioned table are required, and, assuming the nonpartitioned table is roughly the same size as the row-partitioned PI table, the join can conceptually take five times longer than a join for which the window covers the entire table. The actual performance degradation is not as bad as a factor of five, because the output spool has exactly the same number of rows in either case, and each smaller window is more sparse with respect to the nonpartitioned table than a larger window would be. There can be an offsetting performance gain from cache usage by the nonpartitioned table, especially when it is fairly small.

In both cases, there can be a sliding-window advancing through both tables. The EXPLAIN text for such a query neither indicates that a sliding-window merge join is being used, nor indicates the number of contexts used for each table.

A larger number in PPICacheThrP allocates relatively more memory, when needed, to partition windowing steps, at the expense of other steps that might use cache for other purposes.

The default PPICacheThrP setting is low enough that steps unrelated to partition windowing are not likely to be short on cache. Assuming there is never more than a maximum of 50 concurrent sliding window joins on a given AMP, each operating on tables with many combined partitions, which could consume up to about 50% of the cache memory allocated for windowing. Even in that worst case scenario, an AMP would have the remaining half of the cache for other data blocks.

The sliding windows are based on the row partitions defined by the combined partitioning expression. For a sliding-window merge join to be cost effective, only a limited number of populated combined partitions can participate in the join; however, multilevel row partitioning usually defines many combined partitions for the combined partitioning expressions. This means using a sliding-window merge join in a multilevel row partitioning situation may be too costly.

The final cost of a sliding-window merge join is the merge join cost of a window pair multiplied by the number of window pairs involved in the join. The number of window pairs involved is a function of the number of combined partitions in the PPI relation set and the window size.

The Optimizer always estimates the cost of the join plans it evaluates to process a query; however, if an estimate differs from the actual data on the AMPs as it is revealed during processing for single-window join, the system might then choose to substitute a sliding-window merge join. Alternatively, the query plan developed by the Optimizer might specify a sliding-window merge join, but in the final result, the system might instead dynamically reoptimize the request and use a single-window merge join if there are few populated row partitions (see Product Joins With Dynamic Row Partition Elimination).

In cases where there are conditions on a partitioning column that permit row partition elimination, the Optimizer uses the number of active row partitions rather than the total number of row partitions.

In cases where there is a range constraint between the partitioning column of a PI relation and the other table that can be used to generate a partition-level constraint, the AMP software applies dynamic row partition elimination to the operation.

Sliding-window merge joins are generally not feasible for join operations on a PI table when the number of combined partitions in a window is significantly fewer than the number of populated, noneliminated combined partitions that must be joined.

CREATE TABLE orders (
  o_orderkey      INTEGER NOT NULL,
  o_custkey       INTEGER,
  o_orderstatus   CHARACTER(1) CASESPECIFIC,
  o_totalprice    DECIMAL(13,2) NOT NULL,
  o_orderdate     DATE FORMAT 'yyyy-mm-dd' NOT NULL,
  o_orderpriority CHARACTER(21),
  o_clerk         CHARACTER(16),
  o_shippriority  INTEGER,
  o_comment       VARCHAR(79))
PRIMARY INDEX (o_orderkey)
PARTITION BY (
RANGE_N(o_custkey   BETWEEN 0
                    AND 49999
                    EACH 100),
RANGE_N(o_orderdate BETWEEN DATE '2000-01-01'
                    AND     DATE '2006-12-31'
                    EACH INTERVAL '1' MONTH))
UNIQUE INDEX (o_orderkey);
CREATE TABLE lineitem (
  l_orderkey      INTEGER NOT NULL,
  l_partkey       INTEGER NOT NULL,
  l_suppkey       INTEGER,
  l_linenumber    INTEGER,
  l_quantity      INTEGER NOT NULL,
  l_extendedprice DECIMAL(13,2) NOT NULL,
  l_discount      DECIMAL(13,2),
  l_tax           DECIMAL(13,2),
  l_returnflag    CHARACTER(1),
  l_linestatus    CHARACTER(1),
  l_shipdate      DATE FORMAT 'yyyy-mm-dd',
  l_commitdate    DATE FORMAT 'yyyy-mm-dd',
  l_receiptdate   DATE FORMAT 'yyyy-mm-dd',
  l_shipinstruct  VARCHAR(25),
  l_shipmode      VARCHAR(10),
  l_comment       VARCHAR(44))
PRIMARY INDEX (l_orderkey)
PARTITION BY (
RANGE_N(l_suppkey  BETWEEN 0
                   AND  4999
                   EACH 10),
RANGE_N(l_shipdate BETWEEN DATE '2000-01-01' 
                   AND     DATE '2006-12-31'
                   EACH INTERVAL '1' MONTH));

SELECT *
FROM orders INNER JOIN lineitem
WHERE o_orderkey = l_orderkey
AND   o_orderdate BETWEEN DATE '2005-04-01'
                  AND     DATE '2006-06-30'
AND   o_custkey IN (618, 973)
AND   l_shipdate  BETWEEN DATE '2005-04-01'
                  AND     DATE '2006-10-31'
AND   l_suppkey = 4131;