In this post, I’m going to take a look at how query plans involving partitioned tables work. Note that there is a big difference between partitioned tables (available only in SQL Server 2005) and partitioned views (available both in SQL Server 2000 and in SQL Server 2005). I will look at the query plans for partitioned views in a future post.
Table Scan
Let’s begin by creating a simple partitioned table:
create partition function pf(int) as range for values (0, 10, 100)
create partition scheme ps as partition pf all to ([primary])
create table t (a int, b int) on ps(a)
This creates a table with four partitions. SQL Server assigns sequential partition ids to each of the four partitions as follows:
| 1 | t.a <= 0 |
| 2 | 0 < t.a <= 10 |
| 3 | 10 < t.a <= 100 |
| 4 | 100 < t.a |
Now let’s examine the query plan for a simple table scan:
select * from t
|--Nested Loops(Inner Join, OUTER REFERENCES:([PtnIds1004]) PARTITION ID:([PtnIds1004]))
|--Constant Scan(VALUES:(((1)),((2)),((3)),((4))))
|--Table Scan(OBJECT:([t]))
SQL Server explicitly enumerates the partition ids that the table scan must touch using the constant scan and nested loops join operators. Recall that a nested loops join executes its second or inner input (in this case the table scan) once for each value from its first or outer input (in this case the constant scan). Thus, we run the table scan four times; once for each partition id.
Note also that the nested loops join explicitly identifies the partition id column as [PtnIds1004]. Although it is not immediately obvious from the text showplan (unfortunately, we omit this information in some though not all cases), the table scan uses the partition id column and checks it on each execution to determine which partition to scan. This information is always available in the graphical showplan (via the table scan tool tip and properties) and in the XML showplan:
<TableScan Ordered="0" ForcedIndex="0" NoExpandHint="0">
...
<Object Database="[master]" Schema="[dbo]" Table="[t]" />
<PartitionId>
<ColumnReference Column="PtnIds1004" />
</PartitionId>
</TableScan>
Static Partition Elimination
Consider the following query:
select * from t where a < 100
|--Nested Loops(Inner Join, OUTER REFERENCES:([PtnIds1005]) PARTITION ID:([PtnIds1005]))
|--Constant Scan(VALUES:(((1)),((2)),((3))))
|--Table Scan(OBJECT:([t]), WHERE:([t].[a]<(100)) PARTITION ID:([PtnIds1005]))
The predicate “a < 100” clearly eliminates all rows from partition id 4. There is no point in scanning this partition as none of the rows in this partition can possibly qualify for the predicate. The optimizer recognizes this fact and eliminates that partition from the plan. The constant scan now enumerates only three partitions. We refer to this as “static partition elimination” because we know the exact list of partitions to scan statically at compile time.
If we can statically eliminate all but one partition, we do not need the constant scan or join at all:
select * from t where a < 0
|--Table Scan(OBJECT:([t]), WHERE:([t].[a]<(0)) PARTITION ID:((1)))
Note that the exact partition id that we must scan (partition id 1) is now part of the table scan itself.
Dynamic Partition Elimination
In some cases, even though it is not possible for SQL Server to determine statically at compile time which partitions need to be scanned, the optimizer may be able to determine that some partition elimination is still possible.
declare @i int
select @i = 0
select * from t where a < @i
|--Nested Loops(Inner Join, OUTER REFERENCES:([PtnIds1004]) PARTITION ID:([PtnIds1004]))
|--Filter(WHERE:([PtnIds1004]<=RangePartitionNew([@i],(0),(0),(10),(100))))
| |--Constant Scan(VALUES:(((1)),((2)),((3)),((4))))
|--Table Scan(OBJECT:([t]), WHERE:([t].[a]<[@i]) PARTITION ID:([PtnIds1004]))
The above query is parameterized. Since we do not get the actual parameter value until run time (that I’ve provided a constant value for the parameter in the batch does not change things), there is no way to determine at compile time which partition ids to scan. We may scan just partition id 1, or we might scan partition ids 1 and 2, and so forth. Thus, the constant scan enumerates all four partition ids and we use a filter to eliminate partitions ids at run time. We refer to this as “dynamic partition elimination.”
The filter compares each partition id to the results of a special function “RangePartitionNew.” This function computes the results of applying the partition function to the parameter value. The arguments to this function (in left to right order) are: the value (in this case the parameter @i) that we want to map to a partition id, a Boolean flag that indicates whether the partition function maps boundary values to the left (0) or right (1), and the actual partition boundary values (in this case 0, 10, and 100).
In this example, since @i has the value 0, the result of RangePartitionNew is 1. Thus, we scan only partition id 1. Note that unlike the static partition elimination example, even though we scan only a single partition, we still have the constant scan and join. Again, we need these operators since we do not know how many partitions we will scan until run time.
In some cases, the optimizer can determine at compile time that we will scan only one partition even though it cannot determine which partition. For example, if we have an equality predicate on the partition key, we know that only partition can match. In this case, even though we have dynamic partition elimination, we do not need the constant scan and join. For example:
declare @i int
select @i = 0
select * from t where a = @i
|--Table Scan(OBJECT:([t]), WHERE:([t].[a]=[@i]) PARTITION ID:(RangePartitionNew([@i],(0),(0),(10),(100))))
Combining Static and Dynamic Partition Elimination
SQL Server can combine static and dynamic partition elimination in a single query plan:
declare @i int
select @i = 0
select * from t where a > 0 and a < @i
|--Nested Loops(Inner Join, OUTER REFERENCES:([PtnIds1004]) PARTITION ID:([PtnIds1004]))
|--Filter(WHERE:([PtnIds1004]<=RangePartitionNew([@i],(0),(0),(10),(100))))
| |--Constant Scan(VALUES:(((2)),((3)),((4))))
|--Table Scan(OBJECT:([t]), WHERE:([t].[a]<[@i] AND [t].[a]>(0)) PARTITION ID:([PtnIds1004]))
Note that we statically eliminated partition id 1 from the constant scan and we may dynamically eliminate additional partition ids via a filter.
$partition
You can explicitly invoke the RangePartitionNew function using $partition:
select *, $partition.pf(a) from t
|--Compute Scalar(DEFINE:([Expr1004]=RangePartitionNew([t].[a],(0),(0),(10),(100))))
|--Nested Loops(Inner Join, OUTER REFERENCES:([PtnIds1005]) PARTITION ID:([PtnIds1005]))
|--Constant Scan(VALUES:(((1)),((2)),((3)),((4))))
|--Table Scan(OBJECT:([t]))
This query plan is identical to the table scan plan above except that we compute and output the partition id for each row.
For More Information
This post from the SQL Server Development Customer Advisory Team blog includes more partition elimination examples. The post includes some examples of where partition elimination does not work if you have predicates with disjunctions and parameters (such as “a > 0 or a < @i”) and some workarounds. One of the workarounds is to use a “union all” statement to eliminate the disjunction. If you use this workaround, beware that you must be sure that the or’ed predicates will not overlap and return duplicates. In some cases, a duplicate eliminating union (be sure to include a unique key in the select list) may be safer.
Microsoft