THE SQL Server Blog Spot on the Web

Welcome to SQLblog.com - The SQL Server blog spot on the web Sign in | |
in Search

Paul White: Page Free Space

A technical SQL Server blog from New Zealand.

Join Performance, Implicit Conversions, and Residuals

You probably already know that it’s important to be aware of data types when writing queries, and that implicit conversions between types can lead to poor query performance.  Some people have gone so far as to write scripts to search the plan cache for CONVERT_IMPLICIT elements, and others routinely inspect plans for that type of thing when tuning.

Now, that’s all good, as far as it goes.  It may surprise you to learn that not all implicit conversions are visible in query plans, and there are other important factors to consider too.  To demonstrate, I’m going to use two single-column heap tables, containing a selection of pseudo-random numbers, as shown in the diagram below (there’s a script to create the test tables and data at the end of this post):

image

The first table contains 5,000 rows and the second table contains 5,000,000 rows.  The basic test query is to count the number of rows returned by a simple inner join between the two tables.  We’ll run a number of tests to explore the performance issues, using a number of tables using different data types to store the data.

Test One – INTEGER NOT NULL

The first test features two tables where both columns are typed as INTEGER, and constrained to be NOT NULL:

image

Since one table is significantly smaller than the other, the query optimizer chooses a hash join.  To avoid the (very useful) bitmap filter optimization featured in my last post, each query features a MAXDOP 1 query hint to guarantee a serial plan.  The test query gives this query plan:

image

This returns its result in 900ms.

Test Two – INTEGER to REAL

Now let’s try the same query, but where the larger table’s column uses the REAL data type (the smaller table is INTEGER as before):

image

image

There are a couple of new things here.  First, SQL Server needs to convert the data type of one of the columns to match the other before it can perform the join.  The rules for data type precedence show that REAL has a higher precedence than INTEGER, so the integer data is converted to REAL using the CONVERT_IMPLICIT operation shown in the Compute Scalar iterator.

The join then probes the hash table (built on the converted REAL values) for matches.  The possibility of hash collisions means that a residual predicate is applied to check that the values indicated as a possible match actually do match.  Nothing much new or surprising here then.  The query performs slightly less well than before, completing in 1000ms.

Test Three – INTEGER to DECIMAL

Same query again, but this time the larger table’s column is defined as a DECIMAL(7, 0):

image

image

The first surprise is that this query takes 1600ms.

The second surprise is that the query plan does not contain a Compute Scalar or a CONVERT_IMPLICIT anywhere, despite the fact that we are joining columns with different data types.  In fact there is no indication anywhere that an implicit conversion is occurring – not in the graphical plan, not even in the more detailed XML show plan representation.

This is very bad news.  Whether you are tuning the query by hand, or using a script to scan the plan cache for implicit conversions, there really is no way to see the invisible type conversion here.  Even the new implicit type conversion warnings built into Denali CTP3 do not detect the problem.

Test Four – DECIMAL to INTEGER

Now let’s reverse the situation, so the smaller table’s column is DECIMAL(7,0) and the larger table is INTEGER:

image

image

Now the query runs for 1900ms.

The data precedence rules mean each INTEGER value from the large table has to be converted to DECIMAL to compute a hash value, and converted again to check the residual.  Again, there is no Compute Scalar, no CONVERT_IMPLICIT…absolutely no visible indication anywhere why this query should run over twice as long as the original.

Adding an Explicit Conversion

Let’s see what happens if we introduce an explicit conversion here, choosing to convert the DECIMAL values to INTEGER in order to perform the conversion on the smaller table:

image

image

Ok, so now we have a Compute Scalar, an explicit CONVERT, and a Probe Residual that references the converted expression.  This query completes in 1000ms.  Compare this query plan with the one shown immediately above it – would you pick that the plan with the extra Compute Scalar would be nearly twice as fast?

Conversion Families

So what’s going on here?  Why is SQL Server hiding conversion details from us that have such a profound effect on execution speed?  It turns out that certain implicit conversions can be performed inside the join, and so do not require a separate Compute Scalar.  This is the case if the join columns have different types, but both types come from the same ‘family’.  The five families are:

image

In our example, DECIMAL and INTEGER are from family [1] so the implicit conversion can be performed inside the join, without a CONVERT_IMPLICIT or Compute Scalar.  Stop for a moment and think about how many joins you have in production code where the columns involved are INTEGER to BIGINT, or SMALLINT to INTEGER, to take just two possible examples.  Are those joins running at half speed?

The NULL Issue

There is one more subtlety to consider.  Let’s run our test query one last time, using tables with INTEGER columns, but this time the columns are declared as allowing NULLs (there are no NULLs in the test data, by the way).

image

image

This query runs in around 1000ms.  Remember that the first query we ran (where both columns were defined as INTEGER NOT NULL) completed in 900ms.  Let’s look at the first query plan again:

image

Notice the lack of a Probe Residual.  If the join is on a single column typed as TINYINT, SMALLINT or INTEGER and if both columns are constrained to be NOT NULL, the hash function is ‘perfect’ – meaning there is no chance of a hash collision, and the query processor does not have to check the values again to ensure they really match.

This optimization is the reason that the NOT NULL query performs 11% faster than when either or both join columns allow NULLs.  Also notice that this optimization does not apply to BIGINT columns.

Summary

Here’s my general advice for best join performance:

  • Be aware that conversions may occur without a CONVERT_IMPLCIT or Compute Scalar
  • Join on a single column
  • Ensure join column types match exactly
  • Constrain potential join columns to be NOT NULL
  • Use TINYINT, SMALLINT, or INTEGER types to avoid residual predicates
  • Keep reading my blog for further reasons to prefer INTEGER NOT NULL :)
  • Introduce explicit conversions where necessary, as a workaround

© 2011 Paul White

email: SQLkiwi@gmail.com
twitter: @SQL_Kiwi

Further Reading

Hash Match Probe Residual – Rob Farley

Test Script:
USE tempdb;
GO
DROP TABLE 
    #BuildInt, #BuildIntNullable, #BuildBigInt, #BuildDec, #BuildReal,
    #ProbeInt, #ProbeIntNullable, #ProbeBigInt, #ProbeDec, #ProbeReal;
GO
-- Test tables
CREATE TABLE #BuildInt
(
    col1    INTEGER NOT NULL
);
GO
CREATE TABLE #BuildIntNullable
(
    col1    INTEGER NULL
);
GO
CREATE TABLE #BuildBigInt
(
    col1    BIGINT NOT NULL
);
GO
CREATE TABLE #BuildDec
(
    col1    DECIMAL(7,0) NOT NULL
);
GO
CREATE TABLE #BuildReal
(
    col1    REAL NOT NULL
);
 
GO
CREATE TABLE #ProbeInt
(
    col1    INTEGER NOT NULL
);
GO
CREATE TABLE #ProbeIntNullable
(
    col1    INTEGER NULL
);
GO
CREATE TABLE #ProbeBigInt
(
    col1    BIGINT NOT NULL
);
GO
CREATE TABLE #ProbeDec
(
    col1    DECIMAL(7,0) NOT NULL
);
GO
CREATE TABLE #ProbeReal
(
    col1    REAL NOT NULL
);
GO
------------------------------------------------
-- Load 5,000 INTEGER rows into the build tables
------------------------------------------------
SET NOCOUNT ON;
SET STATISTICS IO, TIME, XML OFF;
 
DECLARE @I INTEGER = 1;
 
INSERT #BuildInt
    (col1) 
VALUES 
    (CONVERT(INTEGER, RAND(1) * 9999999));
 
WHILE @I < 5000
BEGIN
    INSERT #BuildInt
        (col1)
    VALUES 
        (RAND() * 9999999);
    SET @I += 1;
END;
 
-- Copy to the INT nullable build table
INSERT #BuildIntNullable
    (col1)
SELECT
    bi.col1
FROM #BuildInt AS bi;
 
-- Copy to the BIGINT build table
INSERT #BuildBigInt
    (col1)
SELECT
    CONVERT(BIGINT, bi.col1)
FROM #BuildInt AS bi;
 
-- Copy to the DECIMAL build table
INSERT #BuildDec
    (col1)
SELECT
    CONVERT(DECIMAL(7,0), bi.col1)
FROM #BuildInt AS bi;
GO
-- Copy to the REAL build table
INSERT #BuildReal
    (col1)
SELECT
    CONVERT(REAL, bi.col1)
FROM #BuildInt AS bi;
GO
----------------------------------------------------
-- Load 5,000,000 INTEGER rows into the probe tables
----------------------------------------------------
SET NOCOUNT ON;
SET STATISTICS IO, TIME, XML OFF;
 
DECLARE @I INTEGER = 1;
 
INSERT #ProbeInt
        (col1)
VALUES 
    (CONVERT(INTEGER, RAND(2) * 9999999));
 
BEGIN TRANSACTION;
 
WHILE @I < 5000000
BEGIN
    INSERT #ProbeInt
        (col1) 
    VALUES 
        (CONVERT(INTEGER, RAND() * 9999999));
        
    SET @I += 1;
    
    IF @I % 100 = 0
    BEGIN
        COMMIT TRANSACTION;
        BEGIN TRANSACTION;
    END;
END;
 
COMMIT TRANSACTION;
GO
-- Copy to the INT nullable probe table
INSERT #ProbeIntNullable
    (col1)
SELECT
    pri.col1
FROM #ProbeInt AS pri
GO
-- Copy to the BIGINT probe table
INSERT #ProbeBigInt
    (col1)
SELECT
    CONVERT(BIGINT, pri.col1)
FROM #ProbeInt AS pri
GO
-- Copy to the DECIMAL probe table
INSERT #ProbeDec
    (col1)
SELECT
    CONVERT(DECIMAL(7,0), pri.col1)
FROM #ProbeInt AS pri
GO
-- Copy to the REAL probe table
INSERT #ProbeReal
    (col1)
SELECT
    CONVERT(DECIMAL(7,0), pri.col1)
FROM #ProbeInt AS pri
GO
-----------
-- TESTS --
-----------
SET STATISTICS IO, TIME ON;
 
SELECT
    COUNT_BIG(*) 
FROM #BuildInt AS bi
JOIN #ProbeInt AS pri ON
    pri.col1 = bi.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*) 
FROM #BuildInt AS bi
JOIN #ProbeIntNullable AS pin ON
    pin.col1 = bi.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*) 
FROM #BuildIntNullable AS bin
JOIN #ProbeIntNullable AS pin ON
    pin.col1 = bin.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*) 
FROM #BuildIntNullable AS bin
JOIN #ProbeInt AS pri ON
    pri.col1 = bin.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildBigInt AS bbi
JOIN #ProbeBigInt AS pbi ON
    pbi.col1 = bbi.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildInt AS bi
JOIN #ProbeDec AS pd ON
    pd.col1 = bi.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildDec AS bd
JOIN #ProbeInt AS pri ON
    pri.col1 = bd.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildDec AS bd
JOIN #ProbeInt AS pri ON
    pri.col1 = CONVERT(INTEGER, bd.col1)
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildDec AS bd
JOIN #ProbeInt AS pri ON
    CONVERT(DECIMAL(7,0), pri.col1) = bd.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildInt AS bi
JOIN #ProbeDec AS pd ON
    pd.col1 = bi.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildInt AS bi
JOIN #ProbeReal AS pr ON
    pr.col1 = bi.col1
OPTION (MAXDOP 1);
 
SELECT
    COUNT_BIG(*)
FROM #BuildReal AS br
JOIN #ProbeInt AS pri ON
    pri.col1 = br.col1
OPTION (MAXDOP 1);
 
SET STATISTICS IO, TIME OFF;
Published Tuesday, July 19, 2011 1:17 AM by Paul White

Comment Notification

If you would like to receive an email when updates are made to this post, please register here

Subscribe to this post's comments using RSS

Comments

 

GrumpyOldDBA said:

OK I'm interested in the not null aspect. I'm aware of the size/performance issue when indexed columns are nullable ( I dislike nulls generally anyway! ) but now in joins - I am intrigued.

July 18, 2011 8:07 AM
 

Rob Farley said:

When I saw the title, I was hoping you were going to use the word "Residualiciousness", but you didn't. I'm not going to be doing too much on implicit conversions in my PASS talk, but I like the similarity in titles anyway. :)

Nice post.

Rob

July 18, 2011 8:44 AM
 

jamiet said:

Great post Paul. Here is some more advice, use datadude to write your code and turn on code analysis - it checks for sub-optimal code and may flag code that exhibits one of the issues you talk about here:

http://msdn.microsoft.com/en-us/library/dd193267.aspx

July 18, 2011 9:00 AM
 

Klaus Aschenbrenner said:

Hi Paul,

Really a nice posting :-)

2 questions:

1. What is a Probe Residual?

2. To which family belongs the REAL data type?

Thanks

-Klaus

July 18, 2011 3:00 PM
 

Paul White said:

Hi Rob,

Doh!  I was thinking while writing this that I should link to your previous post on 'residualiciousness' but forgot.  Corrected now, thanks for your comment.

Paul

July 18, 2011 6:17 PM
 

Paul White said:

Hi Jamie (and Colin),

Yes that's a good tip - I'm not too familiar with DataDude myself, but if it draws attention to common errors like the one shown in the link you gave, I'm all for it!

In this particular case, we would still need to go back and change the table definition to include NOT NULL as a constraint.  You'd think that adding a WHERE col1 IS NOT NULL condition to the WHERE clause would have the same effect - and logically it does - but the Query Optimizer is not yet smart enough to take advantage, and the residual predicate remains.

Paul

July 18, 2011 6:21 PM
 

Paul White said:

Hi Klaus,

Take a look at the link I have now added to one of Rob Farley's previous posts.  In essence, you can think of a probe residual as an extra condition that is evaluated after a join match is found.  IIRC Rob likens it to a residual predicate on an Index Seek - where the residual is applied as an extra condition to the rows qualified by the seeking condition(s).

REAL is a 4-byte floating point number.  I provided a link to the BOL topic in the text, but here it is again:

http://msdn.microsoft.com/en-us/library/ms173773.aspx

I chose REAL because it is the same size as an INTEGER.

Paul

July 18, 2011 6:25 PM
 

Greg Linwood said:

I agree this is a well written post Paul.

Your general advice for best join performance certainly make sense, but would be difficult for developers to follow post-design other than choosing to do explicit conversions.

This message really needs to reach DB modellers so they choose appropriate types / use surrogate keys (single column joins) so I hope there are few modellers reading your blog..

July 19, 2011 1:06 AM
 

Paul White said:

Klaus,

I just realized is misinterpreted your question about REAL, sorry about that, of course you know what the REAL data type is!

Types other than the ones I listed in 'families' stand alone, and always result in a CONVERT_IMPLICIT when compared with another type.  This is a little surprising - we might have expected REAL and FLOAT to share a 'family', but they do not.

Paul

July 19, 2011 2:54 AM
 

jamiet said:

"I'm not too familiar with DataDude myself, but if it draws attention to common errors like the one shown in the link you gave, I'm all for it!"

Don't worry, its all in Juneau too :)

July 19, 2011 4:09 AM
 

Davide Mauri said:

@Paul: that's why database should support custom types so that one can declare, for example, two new types, say TableAId and TableBId, both inherited from a base type (int, for example).

When someone creates a table, he will use the proper defined datatype to store that table id. Now, when you try to join two tables and you'll find yourself joining on TableAId = TableBId, the compiler can raise an error at "compile" time, even before running the query, cause you're trying to join two differnt things (the usual apples and pears...). If such equality (TableAId = TableBId) must work, the DB developer should "overload" the cast operator in order to explain how to go from one type to another.

Yes, as you may have noticed I'm asking for a full support of a full Type System :)

July 19, 2011 4:11 PM
 

Paul White said:

Hi Davide (and Greg),

I couldn't agree more.

Paul

July 19, 2011 8:46 PM
 

Paul White: Page Free Space said:

Most people know that a LIKE predicate with only a trailing wildcard can usually use an index seek: SELECT

January 17, 2012 8:57 AM
 

Alec said:

Is there no hit for a hidden conversion from int to smallint for example?  It wasn't in your test cases.

December 27, 2012 11:42 AM
 

Paul White said:

Alec,

Yes, there is a probe residual and a hidden implicit conversion. I didn't include smallint in the test script because it has too small a range for the numbers I used.

Paul

December 27, 2012 6:46 PM
 

Paul White: Page Free Space said:

This is a post for T-SQL Tuesday #43 hosted by my good friend Rob Farley . The topic this month is Plan

June 11, 2013 5:00 AM

Leave a Comment

(required) 
(required) 
Submit
Powered by Community Server (Commercial Edition), by Telligent Systems
  Privacy Statement