Sql-server – Why is table variable forcing an index scan while temp table uses seek and bookmark lookup

bookmark-lookupoptimizationsql serversql-server-2008-r2user-defined-table-type

I am trying to understand why using a table variable is preventing the optimizer from using an index seek and then bookmark lookup versus an index scan.

Populating the table:

CREATE TABLE dbo.Test 
(
    RowKey INT NOT NULL PRIMARY KEY, 
    SecondColumn CHAR(1) NOT NULL DEFAULT 'x',
    ForeignKey INT NOT NULL 
) 

INSERT dbo.Test 
(
    RowKey, 
    ForeignKey
) 
SELECT TOP 1000000 
    ROW_NUMBER() OVER (ORDER BY (SELECT 0)),
    ABS(CHECKSUM(NEWID()) % 10)     
FROM sys.all_objects s1
CROSS JOIN sys.all_objects s2 

CREATE INDEX ix_Test_1 ON dbo.Test (ForeignKey)

Populate a table variable with a single record and attempt to lookup the primary key and the second column by searching on the foreign key column: 

DECLARE @Keys TABLE (RowKey INT NOT NULL) 

INSERT @Keys (RowKey) VALUES (10)

SELECT 
    t.RowKey,
    t.SecondColumn
FROM
    dbo.Test t 
INNER JOIN 
    @Keys k
ON
    t.ForeignKey = k.RowKey

Below is the execution plan:

enter image description here

Now the same query using a temp table instead:

CREATE TABLE #Keys (RowKey INT NOT NULL) 

INSERT #Keys (RowKey) VALUES (10) 

SELECT 
    t.RowKey,
    t.SecondColumn
FROM
    dbo.Test t 
INNER JOIN 
    #Keys k
ON
    t.ForeignKey = k.RowKey

This query plan uses a seek and bookmark lookup:

enter image description here

Why the optimizer is willing do the bookmark lookup with the temp table, but not the table variable?

The table variable is used in this example to represent data coming through a user-defined table type in a stored procedure.

I realize the index seek might not be appropriate if the foreign key value occurred hundreds of thousands of times. In that case, a scan would probably be a better choice. For the scenario I created, there was no row with a value of 10. I still think the behavior is interesting and would like to know if there is a reason for it.

SQL Fiddle

Adding OPTION (RECOMPILE) did not change the behavior. The UDDT has a primary key.

@@VERSION is SQL Server 2008 R2 (SP2) – 10.50.4042.0 (X64) (Build 7601: Service Pack 1) (Hypervisor)

Best Answer

The reason for the behavior is that SQL Server can't determine how many rows will match to ForeignKey, since there is no index with RowKey as the leading column (it can deduce this from statistics on the #temp table, but those don't exist for table variables/UDTTs), so it makes an estimate of 100,000 rows, which is better handled with a scan than a seek+lookup. By the time SQL Server realizes there is only one row, it's too late.

You might be able to construct your UDTT differently; in more modern versions of SQL Server you can create secondary indexes on table variables, but this syntax is not available in 2008 R2.

BTW you can get the seek behavior (at least in my limited trials) if you try to avoid the bitmap/probe by hinting a nested loops join:

DECLARE @Keys TABLE (RowKey INT PRIMARY KEY); -- can't hurt

INSERT @Keys (RowKey) VALUES (10);

SELECT 
     t.RowKey
    ,t.SecondColumn
FROM
    dbo.Test t 
INNER JOIN 
    @Keys k
ON
    t.ForeignKey = k.RowKey
    OPTION (LOOP JOIN);

I learned this trick from Paul White several years ago. Of course, you should be careful about putting any kind of join hints in production code - this can fail if people make changes to the underlying objects and that specific type of join is no longer possible or no longer most optimal.

For more complex queries, and when you move to SQL Server 2012 or above, it's possible that trace flag 2453 could help. That flag didn't help with this simple join, though. And the same disclaimers would apply - this is just an alternative thing you shouldn't generally do without a ton of documentation and rigorous regression testing procedures in place.

Also, Service Pack 1 is long out of support, you should get on Service Pack 3 + MS15-058.

Related Question