Semi-join Transformation

  • Article

In several of my prior posts, I’ve given examples of semi-joins.  Recall that semi-joins essentially return a row from one input if we can find at least one matching row from the other input.  Here is a simple example:

create table T1 (a int, b int)

create table T2 (a int, b int)

set nocount on

declare @i int

set @i = 0

while @i < 10000

  begin

    insert T1 values(@i, @i)

    set @i = @i + 1

  end

set nocount on

declare @i int

set @i = 0

while @i < 100

  begin

    insert T2 values(@i, @i)

    set @i = @i + 1

  end

select * from T1

where exists (select * from T2 where T2.a = T1.a)

Rows Executes
100 1   |--Hash Match(Right Semi Join, HASH:([T2].[a])=([T1].[a]), RESIDUAL:([T2].[a]=[T1].[a]))
100 1        |--Table Scan(OBJECT:([T2]))
10000 1        |--Table Scan(OBJECT:([T1]))

Note that the optimizer chooses a hash join and correctly builds a hash table on the smaller input T2 which has only 100 rows and probes with the larger input T1 which has 10,000 rows.

Transformation

Now, let’s suppose we want to create an index to speed up this query.  Perhaps we’d like to get a plan with an index nested loops join.  Should we create an index on T1 or T2?  Keep in mind that nested loops join only supports left semi-join not right semi-join.  If we get a nested loops semi-join plan, T1 will be the outer table and T2 will be the inner table.  Thus, we might be tempted to create an index on T2:

create clustered index T2a on T2(a)

Unfortunately, this index does not change the plan.  The optimizer has decided that 10,000 index lookups (one for each row of T1) is still more expensive than the hash join.  Fortunately, we have another less obvious option.  We can create an index on the larger T1 table:

create clustered index T1a on T1(a)

select * from T1

where exists (select * from T2 where T2.a = T1.a)

Now we get an index nested loops join:

Rows Executes
100 1   |--Nested Loops(Inner Join, OUTER REFERENCES:([T2].[a], [Expr1009]) WITH UNORDERED PREFETCH)
100 1        |--Stream Aggregate(GROUP BY:([T2].[a]))
100 1        | |--Clustered Index Scan(OBJECT:([T2].[T2a]), ORDERED FORWARD)
100 100        |--Clustered Index Seek(OBJECT:([T1].[T1a]), SEEK:([T1].[a]=[T2].[a]) ORDERED FORWARD)

But wait a minute!  This plan has an inner join.  What happened to the semi-join?  Remember that the semi-join simply returns each row of T1 that matches at least one row of T2.  We can use an inner join to find these matches so long as we do not return any row of T1 more than once.  In this plan, we use the ordered clustered index scan of T2 and the stream aggregate to eliminate any duplicates values of T2.a.  Then, when we join these T2 rows with T1, we know that we can match each T1 row exactly once.  Note that unlike the original hash join plan which touched all 10,000 rows of T1, this plan performs only 100 distinct index lookups on T1.

When is this transformation a good idea?

Transforming the semi-join to an inner join helps when, as in this example, we have a large number of rows on the “preserved” side of the join (T1 in this example) and the transformation enables an index seek that would have otherwise been impossible.
 
The transformation also makes sense if the number of rows on the “lookup” side of the join is very large but most of the rows are duplicates.  Since the semi-join does not depend on the duplicates, we can eliminate them.  For example, let’s drop the index on T1 and create a new 10,000 row table T3 that is all duplicates:

drop index T1.T1a

create table T3 (a int, b int)

set nocount on

declare @i int

set @i = 0

while @i < 10000

  begin

  insert T3 values(0, @i)

    set @i = @i + 1

  end

select * from T1

where exists (select * from T3 where T3.a = T1.a)

Rows Executes
1 1   |--Hash Match(Inner Join, HASH:([T3].[a])=([T1].[a]), RESIDUAL:([T3].[a]=[T1].[a]))
1 1        |--Hash Match(Aggregate, HASH:([T3].[a]), RESIDUAL:([T3].[a] = [T3].[a]))
10000 1        | |--Table Scan(OBJECT:([T3]))
10000 1        |--Table Scan(OBJECT:([T1]))

Notice that even though we have no indexes and use the hash join plan, we still transform the semi-join into an inner join.  This time, since we do not have an index, we use a hash aggregate to eliminate duplicate values of T3.a.  Without the transformation, the hash join would have built a hash table on all 10,000 rows in T3.  With the transformation, it builds a hash table on a single row.

Unique index

If we add a unique index so that duplicate values of T2.a are not possible, the optimizer no longer needs to eliminate duplicates and can always perform this transformation for free.  For example:

create unique clustered index T2a on T2(a) with (drop_existing = on)

select * from T1

where exists (select * from T2 where T2.a = T1.a)

Rows Executes
100 1   |--Hash Match(Inner Join, HASH:([T2].[a])=([T1].[a]), RESIDUAL:([T2].[a]=[T1].[a]))
100 1        |--Clustered Index Scan(OBJECT:([T2].[T2a]))
10000 1        |--Table Scan(OBJECT:([T1]))

Since we dropped the index on T1 (see above), we get the hash join plan again.  However, unlike the original right semi-join plan, now we get an inner join.  There is no need for a semi-join because the optimizer knows that there can be no duplicates in T2 and that the semi-join and inner join plans are equivalent.

Stay tuned …

This post will probably be my last of the year, but I will be back in January to continue writing about parallelism, partitioned tables, and other query processing topics.