概述
数据库主要有三种物理连接方式：nested join, merge join ,hash join。 这次主要说说nested join(NL).在NL中，两个相连的集合分别是outertable,innertable.
SELECT * FROM OrderDetails AS OD INNER JOIN [Order] AS O ON OD.order_id=O.id
其中，Order表为outertable,OrderDetaiils 表为innertable.但数据库优化器会选择较小的表作为outertable
简单算法描述
首先，outertable中取出一行，然后分别与innertable中的每一行比较，如果符合条件，则返回。然后outertable继续取出下一行，与innertable中的每行比较…
伪代码如下（摘自http://blogs.msdn.com/b/craigfr/archive/2006/07/26/nested-loops-join.aspx）
for each row R1 in the outer table
for each row R2 in the inner table if R1 joins with R2 return (R1, R2)在最原始下，算法的成本=outertable行数*innertable行数
SQL SERVER中应用无优化的nested join
测试数据
View Code IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[Order]'))DROP TABLE [dbo].[Order]GO--订单表CREATE TABLE dbo.[Order]( id int, cus_name nvarchar(50));INSERT INTO [Order] SELECT 1,'Mike'UNION ALLSELECT 2,'Ben'UNION ALLSELECT 3,'Clare'IF EXISTS (SELECT * FROM sys.objects WHERE object_id = OBJECT_ID(N'[dbo].[OrderDetails]'))DROP TABLE [dbo].[OrderDetails]GO--订单详细表CREATE TABLE dbo.[OrderDetails]( id int, order_id int, good_name nvarchar(50));INSERT INTO OrderDetailsSELECT 1,1,'硬盘'UNION ALLSELECT 2,1,'显示器'UNION ALLSELECT 3,2,'IPOD'UNION ALLSELECT 4,4,'食物'
执行SQL
--SET STATISTICS PROFILE ON:显示分析、编译和执行查询所需的时间--详细解释见http://www.cnblogs.com/qanholas/archive/2011/05/06/2038543.htmlSET STATISTICS PROFILE ONSELECT O.id,O.cus_name,OD.good_nameFROM OrderDetails AS OD INNER JOIN [Order] AS O ON O.id=OD.order_idOPTION(loop join) --强制优化器使用nested join
结果
从图中可以看出
1>在SQL SERVER(测试时用的是SQL 2008)执行时会自动选择小表作为outertable,大表作为innertable；
2>第三行显示的是outertable信息：表明outertalbe只需要扫描一次即可；第四行显示的是innertable信息：表明innertable需要执行n（n=outertable行数）次，并返回n*m(m=innertalbe行数)
SQL SERVER中应用索引优化后的nested join
测试数据：继续使用上一部的测试数据
创建索引：CREATE CLUSTERED INDEX ODOID ON [OrderDetails](order_id)
执行SQL:
SET STATISTICS PROFILE ONSELECT O.id,O.cus_name,OD.good_nameFROM OrderDetails AS OD INNER JOIN [Order] AS O ON O.id=OD.order_idOPTION(loop join) --强制优化器使用nested join
结果：
从图中可以看出
当innertable在连接字段上加了索引之后，虽然outertable也执行了n次，但是每一次的outertable循环时，innertable仅返成立的一行。而在没有加索引之前，每一次的outertable循环时，innertable需要返回所有行，然后再比较是否符合连接条件。
总结
Nested join 适用于，一个小集合（小于2000行。。。从网上看到的，具体大家自己实践吧）作为outertable，一个大集合（可以大于百万，同时大集合要在连接条件上加上索引），当这样的两个集合相连接时，可以采用nested join
参考：
http://www.cnblogs.com/RicCC/archive/2007/06/26/SQL-Server-Performance-Tuning-Nested-Loop-Merge-Hash-Join.html
http://blogs.msdn.com/b/craigfr/archive/2006/07/26/nested-loops-join.aspx