Most people know that a LIKE predicate with only a trailing wildcard can usually use an index seek:
SELECT
p.Name
FROM Production.Product AS p
WHERE
p.Name LIKE N'D%';
As the execution plan shows, SQL Server determines a covering range (which depends on the collation), seeks the string index using the range as the start and end points of a partial scan, and applies the original LIKE condition as a residual predicate to just the rows that match the initial seek operation. Specifically, the Storage Engine seeks the index to locate rows in the covering range, and the Query Processor applies the residual predicate (the LIKE) to the rows it receives.
Dynamic Seeks
But what if the LIKE search term is in a variable?
DECLARE @Like NVARCHAR(50) = N'D%'
SELECT
p.Name
FROM Production.Product AS p
WHERE
p.Name LIKE @Like;
SQL Server can still perform a seek here, but it needs to determine the covering seek range for the search term at execution time, not at compilation time:
The plan now contains an extra Constant Scan, a Compute Scalar and a Nested Loops Join. These operators are interesting because they have zero cost estimates: no CPU, no I/O, nothing. That’s because they are purely architectural: a workaround for the fact that SQL Server cannot currently perform a dynamic seek within the Index Seek operator itself. To avoid affecting plan choices, this extra machinery is costed at zero.
The Constant Scan produces a single in-memory row with no columns. The Compute Scalar defines expressions to describe the covering seek range (using the runtime value of the @Like variable). Finally, the Nested Loops Join drives the seek using the computed range information as correlated values.
The upper tooltip shows that the Compute Scalar uses three internal functions, LikeRangeStart, LikeRangeEnd, and LikeRangeInfo. The first two functions describe the range as an open interval. The third function returns a set of flags encoded in an integer, that are used internally to define certain seek properties for the Storage Engine. The lower tooltip shows the seek on the open interval described by the result of LikeRangeStart and LikeRangeEnd, and the application of the residual predicate ‘LIKE @Like’.
More Dynamic Seeks
Something very similar occurs in plans that use IN or OR with variables:
DECLARE
@1 INTEGER = 320,
@2 INTEGER = 325,
@3 INTEGER = 330
SELECT
p.Name
FROM Production.Product AS p
WHERE
p.ProductID IN (@1,@2,@3);
Now we have three ranges: one for each of the variables in the original query. The Compute Scalar operators again define three columns containing the start and end of the range, and the associated informational flags (previously seen as a result of the LikeRangeInfo function). This time, we see the decimal representation of these flags, which happens to be 62 for an equality comparison. The IN expands to (ProductID = @1 OR ProductID = @2 OR ProductID = @3), so each of the ‘ranges’ here is in fact a single value, so the start and end range values are the same in each Compute Scalar.
The three dynamic ranges are concatenated, sorted (so any overlapping ranges appear next to each other in the stream) and the Merge Interval collapses these intervals into one or more disjoint (non-overlapping) ranges. This is important, because the three variables might, for example, all contain the same value, and it would be incorrect to return that value three times. Anyway, for each disjoint range produced, the Nested Loops Join drives a new seek of the Clustered Index. The overall effect is that an arbitrary number of possibly overlapping ranges are computed, merged, and then used to drive one or more seek operations. The final result of the query will be the combination of all the seek results, as you would expect.
Hidden Conversions
The following example contains a table with DATETIME2 values, and a query with a expression that at first sight seems unlikely to be able to seek on an index (the variable is typed as DATE, and there is a CONVERT function applied to the DATETIME2 column):
DECLARE @Example TABLE (date_time DATETIME2 PRIMARY KEY);
INSERT @Example (date_time)
VALUES ('20110101 12:34:56');
DECLARE @date DATE = '2011-01-01';
SELECT *
FROM @Example AS e
WHERE
@date = CONVERT(DATE, e.date_time);
Nevertheless, a query plan that uses a seek can be produced:
In this case, neither SSMS or Plan Explorer will show the contents of the Compute Scalar (this is probably just an oversight, rather than deliberate concealment!). We have to open the XML form of the execution plan to see the three familiar expressions, wrapped in a Value Vector (just a fancy container for multiple expressions).
Another internal function, GetRangeThroughConvert, is responsible for determining the the range of DATETIME2 values covered by the DATE variable @date, and the informational flags needed. In the same way the engine works out covering ranges for some LIKE predicates, this function determines ranges where certain problematic type conversions are required. Otherwise, the machinery is the same: a range description is defined by the Compute Scalar, and the Nested Loops Join driving a seek using those values.
More Hidden Conversions
There is another related internal function used when the Query Processor needs to determine a range for a comparison between different data types. This example returns rows based on a greater-than-or-equal comparison between DATE column values and the DATETIME return value of the GETDATE() intrinsic function:
DECLARE @Example TABLE (col1 date PRIMARY KEY)
SELECT * FROM @Example AS e
WHERE e.col1 >= DATEADD(DAY, -7, GETDATE());
Again, the SSMS graphical plan and Plan Explorer cannot display the contents of the Value Vector, so we have to dig into the XML again. The function evaluates the DATEADD(GETDATE()) expression, computes the open-interval start point of a DATE range accounting for the conversion from DATETIME to DATE, and specifies NULL as the end of the range (since this is a >= comparison, there is no end value). The flags value in this case is 22 (the flags for a >= seek operation).
Everything All At Once
This last example features all sorts type sloppiness, resulting in an execution plan that uses GetRangeThroughConvert on the string expression and GetRangeThroughConvert on the result of GetRangeWithMismatchedTypes applied to the result of the GETDATE function. The whole thing is then wrapped in a dynamic seek with the Merge Interval enforcing the (annoying) BETWEEN requirement that the first parameter must be less than or equal to the second. See if you can work out all the conversions necessary for this query, using the rules of data type precedence. It is really quite impressive that this example of lazy T-SQL coding results in an index seek, don’t you think?
DECLARE @Example TABLE (col1 DATETIME PRIMARY KEY)
SELECT * FROM @Example AS e
WHERE CONVERT(DATE, e.col1) BETWEEN '20000101' AND GETDATE();
Conclusion
SQL Server works quite hard sometimes to produce index seeks where they might seem unlikely. This is a good thing, and it would be great to see this capability extended further in future. The downside is that this extra effort means you are less likely to see an Index Scan when you have done something daft with data types.
Why is this a bad thing if you get a seek anyway? The problem is that these hidden implicit conversions can result in inaccurate cardinality and distribution estimations at any stage of the plan. So, even if you get a seek, the plan might be way off overall. If that isn’t persuasive enough, consider this: will having hidden nested range calculations improve your chances of getting a good query plan? Probably not, no. Be very aware of types, and in particular of the types returned by functions and expressions. If in doubt, use SELECT INTO to materialize the results of an expression or query, and check the types of the columns produced.
Note: if you have any scripts that trawl the plan cache looking for implicit conversions (CONVERT_IMPLICIT), you might want to look into updating them to check for these conversions too. Not all conversions are bad ones, of course :)
© 2012 Paul White
Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com
Further Reading:
Implicit Conversions – Craig Freedman
More on Implicit Conversions – Craig Freedman
Join Performance, Implicit Conversions, and Residuals - Me