Why Doesn’t Partition Elimination Work?

Paul White — Tue, 11 Sep 2012 20:52:00 GMT

Given a partitioned table and a simple SELECT query that compares the partitioning column to a single literal value, why does SQL Server read all the partitions when it seems obvious that only one partition needs to be examined?

Sample Data

The following script creates a table, partitioned on the char(3) column ‘Div’, and populates it with 100,000 rows of data:

     USE Sandpit;

    GO

    CREATE PARTITION FUNCTION PF (char(3))

    AS RANGE RIGHT FOR VALUES

    (

        '1', '2', '3', '4', '5', '6', '7', '8', '9',

        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',

        'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',

        'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'

    );

    GO

    CREATE PARTITION SCHEME PS

    AS PARTITION PF

    ALL TO ([PRIMARY]);

    GO

    CREATE TABLE dbo.Test

    (

        Div     char(3) NOT NULL,

        Data    char(50) NOT NULL,

    )

    ON PS(Div);

    GO

    INSERT dbo.Test WITH (TABLOCKX)

        (Div, Data)

    SELECT TOP (100000)

        CONVERT(char(3), CONVERT(char(36), NEWID())),

        CONVERT(char(50), REPLICATE('X', 50))

    FROM sys.columns AS c

    CROSS JOIN sys.columns AS c2

    CROSS JOIN sys.columns AS c3;

Sample data:

The ‘Div’ column is pseudo-random so your results will be slightly different, but this is the distribution across partitions I saw:

    SELECT

        PartitionID = F.PartitionID,

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t WITH (TABLOCK)

    CROSS APPLY (VALUES($PARTITION.PF(t.Div))) AS F (PartitionID)

    GROUP BY

        F.PartitionID

    ORDER BY

        F.PartitionID;

(The partition function defines a total of 36 partitions but only 16 are used by the sample data.)

The Test Query

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF';

Since ‘Div’ is the partitioning column, the expectation is that only one partition will be scanned to count the rows that match the WHERE clause predicate. However, the execution plan shows that query execution scans all 36 partitions (a full table scan):

Why did SQL Server not just look at the one partition it knows the value ‘ABF’ must lie in?

Here’s Why:

The answer lies in the predicate:

The value ‘ABF’ is nowhere to be seen; it has been replaced by [@1]. This means the query has been considered for simple parameterization by SQL Server to promote query plan reuse. The presence of the [@1] does not mean that simple parameterization was successful (considered safe for all possible values by the optimizer). We have to check the plan cache to see if an associated prepared plan exists and is reused for different ‘parameter’ values. It turns out that this time the simple parameterization attempt is considered safe, so a prepared plan is created and is reused for different values. The full parameterized text is:

(@1 varchar(8000))SELECT COUNT_BIG(*) [RowCnt] FROM [dbo].[Test] [t] WHERE [t].[Div]=@1

Static Partition Elimination

The reason SQL Server cannot apply static partition elimination (determining the partition number at compile time) is that the plan now contains a parameter. Subsequent executions that reuse the plan might specify a different value for the parameter, so static elimination would not be safe. It is not possible to disable simple parameterization, but we can prevent it applying to this query in a number of ways. One way is to incorporate an inequality predicate of the form expression <> constant:

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF'

        AND 1 <> 2;

The redundant 1 <> 2 predicate is completely removed by the optimizer, and the query still qualifies for TRIVIAL optimization as it did previously:

There are a number of interesting things to notice here:

The query is no longer parameterized (the literal value ‘ABF’ appears)
Only one partition is touched (partition 11)
This unindexed heap table has a seek predicate
The ‘ordered’ property has changed from False to True

The problem with this plan is that it cannot be reused for different predicate values – so you could end up with a separate cached plan for each possible literal value.

Adding OPTION (RECOMPILE) also defeats simple parameterization and therefore achieves static elimination. In an ad-hoc SQL batch, OPTION (RECOMPILE) also means the query plan will not be cached (stored procedures are not so lucky). The downside is a fresh trip through the optimizer on each call. This query does qualify for trivial plan, so optimization time is minimal, but more complex queries with the same desire for partition elimination might well require full optimization.

Dynamic Partition Elimination

Ideally, we would like a query plan that is reusable but still only touches one partition for any given string literal value. What we need is dynamic partition elimination. In case the concept is new to you, the optimizer can produce plans that determine the correct partition at execution time (rather than at compile-time, as for static elimination). To achieve this, the optimizer builds a plan that uses an internal function called RangePartitionNew(). One might think the original simple-parameterized plan ought to have included this feature; the reason it didn’t is quite interesting.

When SQL Server parameterizes a query using simple or forced parameterization, it has to decide on a data type for the parameter. For string literals, it always chooses varchar(8000) for non-Unicode strings and nvarchar(4000) for Unicode strings. If it chose a specific type like varchar(3), we could end up with the same plan cache bloating and non-reuse problem as for the non-parameterized case – and there are potentially 8000 different lengths for varchar. Also, prior to SQL Server 2005 SP2, the parameter-declaration part of the query text was not included in the hash value used to decide in which cache bucket to store the plan. This could result in hundreds of same-text plans (with different parameters) occupying the same hash bucket (this does not work well).

Anyway, faced with the parameterized predicate Div = [@1], where Div is char(3) and [@1] is varchar(8000), dynamic partition elimination does not occur because the value of [@1] might be truncated. One way to address this is to explicitly convert the to-be-parameterized string literal to the same type as the target column (char(3)):

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(char(3), 'CDC');

Now we have a parameterized query plan that uses dynamic partition elimination:

This plan has all the interesting features of the static elimination plan, but the heap seek no longer selects a hard-coded partition ID. The single partition searched is the one returned at runtime by the call to RangePartitionNew(). The explicit convert prevents data truncation when the parameterized value is compared with the partition boundary values (defined as char(3) in the partition function). The extra CONVERT_IMPLICIT to char(3) is required for internal reasons, and only appears with non-Unicode partition function types.

If we explicitly convert to char(4) instead of char(3), the possibility of truncation arises again and we are back to scanning all 36 partitions:

Using varchar(3) instead of char(3) also results in dynamic elimination, which surprises some people:

Implicit Conversions and Precedence

An alternative explanation I have seen for the original behaviour is that the string literal ‘ABF’ is implicitly typed as a varchar(3) by SQL Server and data type precedence means the char(3) ‘Div’ column has to be implicitly converted to varchar(3) to perform the comparison. This is incorrect, but it is interesting to look at why that is so:

Literal Types

We can see the implicit type of the string literal ‘ABF’ using a query:

    SELECT

        BaseType = SQL_VARIANT_PROPERTY(V.v, 'BaseType'),

        MaxLength = SQL_VARIANT_PROPERTY(V.v, 'MaxLength')

    FROM (VALUES(CONVERT(sql_variant, 'ABF'))) AS V (v);

The implied type of ‘ABF’ does seem to be varchar(3), so that checks out.

Type Precedence

The data type precedence table in Books Online shows that varchar does indeed have a higher precedence than char:

Also, from the Books Online topic Data Types (Transact-SQL):

The example below uses a UNION ALL over char(5) and varchar(3) columns:

    DECLARE @T1 AS TABLE (col1 char(5) NOT NULL);

    DECLARE @T2 AS TABLE (col1 varchar(3) NOT NULL);

    INSERT @T1 VALUES ('12345');

    INSERT @T2 VALUES ('123');

    SELECT

        BaseType = SQL_VARIANT_PROPERTY(CONVERT(sql_variant, t.col1), 'BaseType'),

        MaxLength = SQL_VARIANT_PROPERTY(CONVERT(sql_variant, t.col1), 'MaxLength'),

        t.col1

    FROM

    (

        SELECT col1 FROM  @T1 

        UNION ALL

        SELECT col1 FROM @T2

    ) AS t;

The result column ‘col1’ has to have a well-defined type. As expected, the result is varchar(5) since varchar has a higher precedence than char and 5 is the maximum length of the result. All good so far.

Strings Are Special

We get used to seeing (and preferably avoiding) implicit conversions in query plans where two mismatched types are compared:

    DECLARE @T1 AS TABLE (col1 integer NULL);

    DECLARE @v tinyint;

    SELECT col1 FROM @T1 AS t WHERE col1 = @v;

The plan shows the tinyint variable being implicitly converted to the higher-precedence integer data type, as expected. Now let’s do the same thing with varchar and char (perhaps expecting char to be converted to the higher-precedence varchar):

    DECLARE @T1 AS TABLE (col1 varchar(5) NULL);

    DECLARE @v char(3);

    SELECT col1 FROM @T1 AS t WHERE col1 = @v;

Note the lack of an implicit conversion in the predicate.

Important

SQL Server can compare char with varchar without performing a conversion. They are fundamentally the same type, it’s just that one is fixed-length and the other is variable-length. The SQL standard requires padding for the character strings used in comparisons so that their lengths match before comparing, thereby removing the only distinction between char and varchar. The same optimization can apply to a comparison between nchar and nvarchar (though not to Unicode versus non-Unicode comparisons, since they are genuinely different types of course).

The present case involves a predicate “WHERE Div = ‘ABF’”. This is a comparison that can use this optimization, so there is no implicit conversion. This is the reason the explicit conversion to varchar(3) works in the main example – the precedence rules do not need to be invoked, and the data column is not converted from char(3) to varchar(3).

Why Use a Partitioned Heap?

In case you were wondering, the only reason I chose a partitioned heap for this post is just because I could (it’s more interesting in many ways). All the demonstrations work just as well for a partitioned clustered table. A complete script using a clustered partitioned table is below:

    USE Sandpit;

    GO

    CREATE PARTITION FUNCTION PF (char(3))

    AS RANGE RIGHT FOR VALUES

    (

        '1', '2', '3', '4', '5', '6', '7', '8', '9',

        'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I',

        'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R',

        'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'

    );

    GO

    CREATE PARTITION SCHEME PS

    AS PARTITION PF

    ALL TO ([PRIMARY]);

    GO

    CREATE TABLE dbo.Test

    (

        ID      integer IDENTITY NOT NULL,

        Div     char(3) NOT NULL,

        Data    char(50) NOT NULL,

        CONSTRAINT PK__dbo_Test_Div_ID

        PRIMARY KEY CLUSTERED (Div, ID)

        ON PS(Div)

    );

    GO

    INSERT dbo.Test WITH (TABLOCKX)

        (Div, Data)

    SELECT TOP (100000)

        CONVERT(char(3), CONVERT(char(36), NEWID())),

        CONVERT(char(50), REPLICATE('X', 50))

    FROM sys.columns AS c

    CROSS JOIN sys.columns AS c2

    CROSS JOIN sys.columns AS c3;

    GO

    -- Show the distribution of data

    SELECT

        PartitionID = F.PartitionID,

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t WITH (TABLOCK)

    CROSS APPLY (VALUES($PARTITION.PF(t.Div))) AS F (PartitionID)

    GROUP BY

        F.PartitionID

    ORDER BY

        F.PartitionID;

    GO

    -- Seek on all 36 partitions

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF';

    GO

    -- Static elimination = 1 hard-coded partition ID

    -- Cached plan unlikely to be reused

    SELECT

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF'

        AND 1 <> 2;

    GO

    -- Static elimination

    -- Compilation overhead

    SELECT

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = 'ABF'

    OPTION (RECOMPILE);

    GO

    -- Dynamic elimination with convert to char(3)

    -- Reusable plan

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(char(3), 'ABF');

    GO

    -- Dynamic elimination with convert to varchar(3)

    -- Data type precedence not applied:

    -- varchar(3) convert does not cause the char(3)

    -- column Div to be converted (would prevent a seek)

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(varchar(3), 'ABF');

    GO

    -- char(4) means truncation could occur when

    -- comparing with the char(3) partition function

    -- No partition elimination, seek on 36 partitions

    SELECT 

        RowCnt = COUNT_BIG(*)

    FROM dbo.Test AS t 

    WHERE 

        t.Div = CONVERT(char(4), 'ABF');

    GO

    -- Clean up

    DROP TABLE dbo.Test;

    DROP PARTITION SCHEME PS;

    DROP PARTITION FUNCTION PF;

This post applies to SQL Server 2008, 2008 R2 and 2012 only (partitioned table query execution was very different in 2005). As far as I can tell, SQL Server 2005 did not attempt simple parameterization on a partitioned table. I’m in two minds whether the SQL Server 2008+ behaviour is a bug, an oversight, or an undesirable consequence of fixing something else…so I opened a Connect item for it. Update: fixing this is under consideration for the next release.

Sean Broadley raises an important practical point in the comments below – the issue highlighted in this post only occurs when a literal value is used. By correctly parameterizing your queries (including application code and dynamic SQL) you will avoid simple parameterization, achieve dynamic partition elimination, and cache a more reusable query plan.

Acknowledgement

Thanks to Jonathan Kehayias (blog | twitter) who first altered me to the MSDN forum question that prompted this post.

Paul White
Twitter: @SQL_Kiwi
Email: SQLkiwi@gmail.com

Search results matching tags 'partitioning' and 'Query Plans'