Introduction to Partitioned Tables

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:

PtnId	Values
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.

Comments

• Anonymous
  July 15, 2008
  In this post , I introduced how SQL Server 2005 implements query plans on partitioned tables. If you've

• Anonymous
  December 13, 2009
  After implementing table partition (in SQL 2K5), the actual table size has increased dramatically. Why it is taking more space? Where exactly the space is allocated? How to calculate the table size for partitioned table?

• Anonymous
  January 12, 2010
  The only reason that I can think of why a table would substantially increase in size due to partitioning is if the table has very few rows.  In this case, each partition will take a minimum of one extent.

• Anonymous
  August 11, 2010
  The comment has been removed

• Anonymous
  August 16, 2010
  First, why partition on a column that has only two values?  That limits the table to only two partitions. Second, note that it is not necessary to explicitly include the partition column in an index.  If you leave it off, SQL Server automatically adds it. Third, the answer to a question like this depends to a great extent on the partitioning function and the queries that you will be running.  If each partition contains a single value (as would have to be true in this example), you will not gain any further benefit from indexing on this column.  On the other hand, if you partition on a date column and if each partition has many dates, but if you query on a much narrower date range, it might pay to include the date column as the first column.  If you query on a date range but also have another column with an equality predicate, it might pay to put the column with the equality predicate first so that the index seek can use both columns.