Join Algorithim - Nested Loop Join

Logical Joins (Cross, Inner & Outer joins) are internally implemented using one of the following physical joins -

1. Nested Loop Join
2. Merge Join
3. Hash Join

Optimizer decides at run time which algorithim to use for the logical joins depending upon the type of join and the nature of the inputs like the number of rows in the input, sorting of records based on the join column etc.

Here I'll discuss Nested Loop Join -

Suppose there are two tables or rather inputs T1 & T2, with size N1 and N2 and N1>N2, which we need to join.

Optimizer will take one record from T1 and will scan all the records from T2 one by one. If a record matches, based on the joining column it will be returned so for every input there would be N2 scans and then total scans would be N1*N2.

As you can see for large values of N1 and N2, the complexity of this algorithim increases drastically (N1*N2), this join is not recommended for large values of N1 and N2 rather used for smaller input size.

Unlike other join algorithims, which requires at least one predicate as equi join, Nested loop join could be used for both kind of predicates - equi or non equi joins. Nested loop join cannot be used with Right outer joins.

You can force optimizer to use any kind of join algorithims, provided logical join supports it. E.g. if you run below query,

SELECT * FROM Sales.SalesOrderDetail AS SOD INNER JOIN
Production.Product AS P ON SOD.ProductID=P.ProductID

Optimizer might use Hash join in the query execution plan, but if you want to inforce Nested Loop Join on the optimizer, you need to use below syntax -

SELECT * FROM Sales.SalesOrderDetail AS SOD INNER Loop JOIN
Production.Product AS P ON SOD.ProductID=P.ProductID

Also, following hint in the query cannot be used because Nested loop join cannot be used with Right Outer Joins -

SELECT * FROM Sales.SalesOrderDetail AS SOD RIGHT OUTER LOOP JOIN
Production.Product AS P ON SOD.ProductID=P.ProductID

and you will get error message as "Msg 8622, Level 16, State 1, Line 1Query processor could not produce a query plan because of the hints defined in this query. Resubmit the query without specifying any hints and without using SET FORCEPLAN."

2. Merge Join: Details could be found here.

3. Hash Join: Details could be found here.