NaryNestedLoopJoin operator

The NaryNestedLoopJoin strategy is never evaluated or chosen by the optimizer. It is an operator that is constructed during code generation. If the compiler finds series of two or more left-deep NestedLoopJoins, it attempts to transform them into an NaryNestedLoopJoin operator. Two additional requirements allow for transformation scan; each NestedLoopJoin operator has an “inner join” type and the right child of each NestedLoopJoin is a scan operator. A restrict operator is permitted above the scan operator.

NaryNestedLoopJoin execution has a performance benefit over the execution of a series of NestedLoopJoin operators. The example below demonstrates this. There is one fundamental difference between the two methods of execution. With a series of NestedLoopJoin, a scan may eliminate rows based on searchable argument values initialized by an earlier scan. That scan may not be the one that immediately preceded the failing scan. With a series of NestedLoopJoins, the previous scan would be completely drained although it has no effect on the failing scan. This could result in a significant amount of needless I/O. With NaryNestedLoopJoins, the next row fetched comes from the scan that produced the failing searchable argument value, which is far more efficient.

1> -- Collect the author id and name for all authors with the
2> -- last name "Bloom" and who have a listed title and the
3> -- author id is the same as the title_id.
4> select a.au_id, au_fname, au_lname
5>     from titles t, titleauthor ta, authors a
6> where a.au_id = ta.au_id
7>     and ta.title_id = t.title_id
8>     and a.au_id = t.title_id
9>     and au_lname = "Bloom"

5 operator(s) under root

The type of query is SELECT.

ROOT:EMIT Operator

	|NARY NESTED LOOP JOIN Operator has 3 children.
	|
	|   |SCAN Operator
	|   |  FROM TABLE
	|   |  authors
	|   |  a
	|   |  Index : aunmind
	|   |  Forward Scan.
	|   |  Positioning by key.
	|   |  Keys are:
	|   |    au_lname ASC
	|   |  Using I/O Size 2 Kbytes for index leaf pages.
	|   |  With LRU Buffer Replacement Strategy for index leaf pages.
	|   |  Using I/O Size 2 Kbytes for data pages.
	|   |  With LRU Buffer Replacement Strategy for data pages.
	|
	|   |RESTRICT Operator
	|   |
	|   |   |SCAN Operator
	|   |   |  FROM TABLE
	|   |   |  titleauthor
	|   |   |  ta
	|   |   |  Index : auidind
	|   |   |  Forward Scan.
	|   |   |  Positioning by key.
	|   |   |  Keys are:
	|   |   |    au_id ASC
	|   |   |  Using I/O Size 2 Kbytes for index leaf pages.
	|   |   |  With LRU Buffer Replacement Strategy for index leaf pages.
	|   |   |  Using I/O Size 2 Kbytes for data pages.
	|   |   |  With LRU Buffer Replacement Strategy for data pages.
	|
	|   |SCAN Operator
	|   |  FROM TABLE
	|   |  titles
	|   |  t
	|   |  Using Clustered Index.
	|   |  Index : titleidind
	|   |  Forward Scan.
	|   |  Positioning by key.
	|   |  Keys are:
	|   |    title_id ASC
	|   |  Using I/O Size 2 Kbytes for data pages.
	|   |  With LRU Buffer Replacement Strategy for data pages.

Figure 2-3 depicts a series of NestedLoopJoins.

Figure 2-3: Emit operator tree with NestedLoopJoins

Graphic showing a query plan for a nested loop join with the Emit operator as the root.

All query processor operators are assigned a virtual address. The lines in Figure 2-3 with VA = report the virtual address for a given operator.

The effective join order is authors, titleauthor, titles. A restrict operator is the parent operator of the scan on titleauthors. This plan is transformed into the NaryNestedLoopJoin plan below:

Figure 2-4: NaryNestedLoopJoin operator

Graphis showing a query plan for a Nary Nested Loop Join with the Emit operator as the root.

The transformation retains the original join order of authors, titleauthor, and titles. In this example, the scan of titles has two searchable arguments on it—ta.title_id = t.title_id and a.au_id = t.title_id. So, the scan of titles fails because of the searchable argument value established by the scan of titleauthor or it fails because of the searchable argument value established by the scan of authors. If no rows are returned from a scan of titles because of the searchable argument value set by the scan of authors, there is no point in continuing the scan of titleauthor. For every row fetched from titleauthor, the scan of titles fails. It is only when a new row is fetched from authors that the scan of titles might succeed. This is why NaryNestedLoopJoins have been implemented; they eliminate the useless draining of tables that have no impact on the rows returned by successive scans. In the example, the NaryNestedLoopJoin operator closes the scan of titleauthor, fetches a new row from authors, and repositions the scan of titleauthor based on the au_id fetched from authors. Again, this can be a significant performance improvement as it eliminates the needless draining of the titleauthor table and the associated I/O that could occur.