David Hayes

This is probably the simplest and most robust approach for joining two tables.
Lets take the query

SELECT * FROM emp, dept WHERE emp.deptno = dept.deptno

as an example that should be familiar to those with an Oracle background.

1. emp is chosen as the driving table for this query
2. Since there is no where clause on emp a full table scan is required
3. “For each row in emp look-up the corresponding department”
4. This look-up will be carried out with a unique index scanon the primary key of dept
5. The rowid from the previous step can then be used to retrieve the actual row from dept
6. The database then combines the rows from emp with the joined rows from dept and returns the result

In pseudo-code this would look like:-

For Each emprow in emp
  For Each key in dept.primary_key_index
    If emprow.deptno equals key.deptno
       Fetch deptrow from dept
       Combine columns from emprow and deptrow
       Return combined row to client
       Exit For
    End If
  End For
End For

Hopefully that should make it fairly obvious how this join method got it’s name.

As can be seen from the pseudo-code a nested-loop join only needs to know about the current row it’s processing so it doesn’t need to make use of any temporary space on disk and it requires very little memory. This makes nested-loop joins very robust and scalable to very large resultsets.

The choice of join order will obviously make a huge difference to how quickly the query will execute. Given a choice it is always best to drive from a small set of rows (whether from a small table or from the results of a very selective filter) since that will limit the number of iterations in the outer loop.

You can also see in this simple example how a unique index scan can improve efficiency since the inner loop can be terminated when a matching row is found

/Technology /Databases, /Technology