Sql-server – Why does the optimizer choose nested loops over merge joins here

database-internalsjoin;optimizationsql server

I have 3 tables. #a is main one and two secondary tables, #b and #c.

create table #a (a int not null, primary key (a asc)) ;
create table #b (b int not null, primary key (b asc)) ;
create table #c (c int not null, primary key (c asc)) ;

insert into #a (a)
select x*10 + y
from (values(0),(1),(2),(3),(4),(5),(6),(7),(8),(9))x(x)
cross join (values(0),(1),(2),(3),(4),(5),(6),(7),(8),(9))y(y) ;

insert into #b (b)
select a from #a where a % 5 > 0 ;

insert into #c (c)
select a from #a where a % 4 > 0 ;

If I join main table #a with only one secondary table, there will be Merge Join in query plan.

select *
from #a a
inner join #b b on a = b ;

enter image description here

But if I join main table #a with both secondary tables, there will be only Nested Loops.

select *
from #a a
inner join #b b on a = b
inner join #c c on a = c ;

enter image description here

Why does it work like that and what should I do to get two Merge Joins?

Without inner merge join hint.

Best Answer

Why does it work like that and what should I do to get two Merge Joins?

With three table references (the minimum required), the query qualifies for the Transaction Processing (aka search 0) stage of cost-based optimization.

This stage is aimed at OLTP queries, which normally benefit from a navigational (index-based) strategy. Nested Loops Join is the main physical join type available (hash and merge are only considered if no valid nested loops plan can be found in this stage).

If this stage finds a low cost (good enough) plan, cost-based optimization stops there. This prevents spending more time in optimization that we can expect to save over the best solution found so far. If the cost exceeds a threshold, the optimizer moves on to the Quick Plan (search 1), parallel Quick Plan, and Full Optimization (search 2) phases.

The query with two table references did not qualify for Transaction Processing, and went straight into Quick Plan, where Merge and Hash joins are available.

See my Query Optimizer Deep Dive series for more information.

Without inner merge join hint.

If you absolutely must hint a physical join type, strongly prefer OPTION (MERGE JOIN). This allows the optimizer to still consider changing the join order.

Join hints like INNER MERGE JOIN come with an implied OPTION (FORCE ORDER), which severely limits the optimizer's freedom, with consequences most people (including experts) do not appreciate.

Related Question