text:
THE SQL Server Blog Spot on the Web
The query optimizer does not always choose an optimal strategy when joining partitioned tables. This post looks at an example, showing how a manual rewrite of the query can almost double performance, while reducing the memory grant to almost nothing.
The two tables in this example use a common partitioning partition scheme. The partition function uses 41 equal-size partitions:
CREATE PARTITION FUNCTION PFT (integer)
125000, 250000, 375000, 500000,
625000, 750000, 875000, 1000000,
1125000, 1250000, 1375000, 1500000,
1625000, 1750000, 1875000, 2000000,
2125000, 2250000, 2375000, 2500000,
2625000, 2750000, 2875000, 3000000,
3125000, 3250000, 3375000, 3500000,
3625000, 3750000, 3875000, 4000000,
4125000, 4250000, 4375000, 4500000,
4625000, 4750000, 4875000, 5000000
There two tables are:
CREATE TABLE dbo.T1
TID integer NOT NULL IDENTITY(0,1),
Column1 integer NOT NULL,
Padding binary(100) NOT NULL DEFAULT 0x,
CREATE TABLE dbo.T2
TID integer NOT NULL,
PRIMARY KEY CLUSTERED (TID, Column1)
The next script loads 5 million rows into T1 with a pseudo-random value between 1 and 5 for Column1. The table is partitioned on the IDENTITY column TID:
INSERT dbo.T1 WITH (TABLOCKX)
FROM dbo.Numbers AS N
WHERE n BETWEEN 1 AND 5000000;
In case you don't already have an auxiliary table of numbers lying around, here's a script to create one with 10 million rows:
CREATE TABLE dbo.Numbers (n bigint PRIMARY KEY);
L0 AS(SELECT 1 AS c UNION ALL SELECT 1),
L1 AS(SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),
L2 AS(SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),
L3 AS(SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),
L4 AS(SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),
L5 AS(SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),
Nums AS(SELECT ROW_NUMBER() OVER (ORDER BY (SELECT NULL)) AS n FROM L5)
INSERT dbo.Numbers WITH (TABLOCKX)
SELECT TOP (10000000) n
FROM Nums
ORDER BY n
Table T1 contains data like this:
Next we load data into table T2. The relationship between the two tables is that table 2 contains 'n' rows for each row in table 1, where 'n' is determined by the value in Column1 of table T1. There is nothing particularly special about the data or distribution, by the way.
INSERT dbo.T2 WITH (TABLOCKX)
(TID, Column1)
FROM dbo.T1 AS T
JOIN dbo.Numbers AS N
ON N.n >= 1
AND N.n <= T.Column1;
Table T2 ends up containing about 15 million rows:
The primary key for table T2 is a combination of TID and Column1. The data is partitioned according to the value in column TID alone.
The following query shows the number of rows in each partition of table T1:
PartitionID = CA1.P,
NumRows = COUNT_BIG(*)
There are 40 partitions containing 125,000 rows (40 * 125k = 5m rows). The rightmost partition remains empty. The next query shows the distribution for table 2:
FROM dbo.T2 AS T
There are roughly 375,000 rows in each partition (the rightmost partition is also empty):
Ok, that's the test data done.
The task is to count the rows resulting from joining tables 1 and 2 on the TID column:
DECLARE @s datetime2 = SYSUTCDATETIME();
FROM dbo.T1 AS T1
JOIN dbo.T2 AS T2
SELECT DATEDIFF(Millisecond, @s, SYSUTCDATETIME());
The optimizer chooses a plan using parallel hash join, and partial aggregation:
The Plan Explorer plan tree view shows accurate cardinality estimates and an even distribution of rows across threads (click to enlarge the image):
With a warm data cache, the STATISTICS IO output shows that no physical I/O was needed, and all 41 partitions were touched:
Running the query without actual execution plan or STATISTICS IO information for maximum performance, the query returns in around 2600ms.
The first step toward improving on the execution plan produced by the query optimizer is to understand how it works, at least in outline.
The two parallel Clustered Index Scans use multiple threads to read rows from tables T1 and T2. Parallel scan uses a demand-based scheme where threads are given page(s) to scan from the table as needed. This arrangement has certain important advantages, but does result in an unpredictable distribution of rows amongst threads. The point is that multiple threads cooperate to scan the whole table, but it is impossible to predict which rows end up on which threads.
For correct results from the parallel hash join, the execution plan has to ensure that rows from T1 and T2 that might join are processed on the same thread. For example, if a row from T1 with join key value '1234' is placed in thread 5's hash table, the execution plan must guarantee that any rows from T2 that also have join key value '1234' probe thread 5's hash table for matches.
The way this guarantee is enforced in this parallel hash join plan is by repartitioning rows to threads after each parallel scan. The two repartitioning exchanges route rows to threads using a hash function over the hash join keys. The two repartitioning exchanges use the same hash function so rows from T1 and T2 with the same join key must end up on the same hash join thread.
This business of repartitioning rows between threads can be very expensive, especially if a large number of rows is involved. The execution plan selected by the optimizer moves 5 million rows through one repartitioning exchange and around 15 million across the other.
As a first step toward removing these exchanges, consider the execution plan selected by the optimizer if we join just one partition from each table, disallowing parallelism:
The optimizer has chosen a (one-to-many) merge join instead of a hash join. The single-partition query completes in around 100ms. If everything scaled linearly, we would expect that extending this strategy to all 40 populated partitions would result in an execution time around 4000ms. Using parallelism could reduce that further, perhaps to be competitive with the parallel hash join chosen by the optimizer.
This raises a question. If the most efficient way to join one partition from each of the tables is to use a merge join, why does the optimizer not choose a merge join for the full query?
Let's force the optimizer to use a merge join on the test query using a hint:
This is the execution plan selected by the optimizer:
This plan results in the same number of logical reads reported previously, but instead of 2600ms the query takes 5000ms. The natural explanation for this drop in performance is that the merge join plan is only using a single thread, whereas the parallel hash join plan could use multiple threads.
We can get a parallel merge join plan using the same query hint as before, and adding trace flag 8649:
This looks promising. It uses a similar strategy to distribute work across threads as seen for the parallel hash join. In practice though, performance is disappointing. On a typical run, the parallel merge plan runs for around 8400ms; slower than the single-threaded merge join plan (5000ms) and much worse than the 2600ms for the parallel hash join. We seem to be going backwards!
The logical reads for the parallel merge are still exactly the same as before, with no physical IOs. The cardinality estimates and thread distribution are also still very good (click to enlarge):
A big clue to the reason for the poor performance is shown in the wait statistics (captured by Plan Explorer Pro):
CXPACKET waits require careful interpretation, and are most often benign, but in this case excessive waiting occurs at the repartitioning exchanges. Unlike the parallel hash join, the repartitioning exchanges in this plan are order-preserving 'merging' exchanges (because merge join requires ordered inputs):
Parallelism works best when threads can just grab any available unit of work and get on with processing it. Preserving order introduces inter-thread dependencies that can easily lead to significant waits occurring. In extreme cases, these dependencies can result in an intra-query deadlock, though the details of that will have to wait for another time to explore in detail.
The potential for waits and deadlocks leads the query optimizer to cost parallel merge join relatively highly, especially as the degree of parallelism (DOP) increases. This high costing resulted in the optimizer choosing a serial merge join rather than parallel in this case. The test results certainly confirm its reasoning.
In SQL Server 2008 and later, the optimizer has another available strategy when joining tables that share a common partition scheme. This strategy is a collocated join, also known as as a per-partition join. It can be applied in both serial and parallel execution plans, though it is limited to 2-way joins in the current optimizer.
Whether the optimizer chooses a collocated join or not depends on cost estimation. The primary benefits of a collocated join are that it eliminates an exchange and requires less memory, as we will see next.
The query optimizer did consider a collocated join for our original query, but it was rejected on cost grounds. The parallel hash join with repartitioning exchanges appeared to be a cheaper option. There is no query hint to force a collocated join, so we have to mess with the costing framework to produce one for our test query. Pretending that IOs cost 50 times more than usual is enough to convince the optimizer to use collocated join with our test query:
-- Pretend IOs are 50x cost temporarily
-- Co-located hash join
-- Reset IO costing
The estimated execution plan for the collocated join is:
The Constant Scan contains one row for each partition of the shared partitioning scheme, from 1 to 41. The hash repartitioning exchanges seen previously are replaced by a single Distribute Streams exchange using Demand partitioning. Demand partitioning means that the next partition id is given to the next parallel thread that asks for one.
My test machine has eight logical processors, and all are available for SQL Server to use. As a result, there are eight threads in the single parallel branch in this plan, each processing one partition from each table at a time. Once a thread finishes processing a partition, it grabs a new partition number from the Distribute Streams exchange…and so on until all partitions have been processed.
It is important to understand that the parallel scans in this plan are different from the parallel hash join plan. Although the scans have the same parallelism icon, tables T1 and T2 are not being co-operatively scanned by multiple threads in the same way. Each thread reads a single partition of T1 and performs a hash match join with the same partition from table T2. The properties of the two Clustered Index Scans show a Seek Predicate (unusual for a scan!) limiting the rows to a single partition:
The crucial point is that the join between T1 and T2 is on TID, and TID is the partitioning column for both tables. A thread that processes partition 'n' is guaranteed to see all rows that can possibly join on TID for that partition. In addition, no other thread will see rows from that partition, so this removes the need for repartitioning exchanges.
The collocated join has removed two expensive repartitioning exchanges and added a single exchange processing 41 rows (one for each partition id). Remember, the parallel hash join plan exchanges had to process 5 million and 15 million rows. The amount of processor time spent on exchanges will be much lower in the collocated join plan.
In addition, the collocated join plan has a maximum of 8 threads processing single partitions at any one time. The 41 partitions will all be processed eventually, but a new partition is not started until a thread asks for it. Threads can reuse hash table memory for the new partition.
The parallel hash join plan also had 8 hash tables, but with all 5,000,000 build rows loaded at the same time. The collocated plan needs memory for only 8 * 125,000 = 1,000,000 rows at any one time.
The collated join plan has disappointing performance in this case. The query runs for around 25,300ms despite the same IO statistics as usual. This is much the worst result so far, so what went wrong?
It turns out that cardinality estimation for the single partition scans of table T1 is slightly low. The properties of the Clustered Index Scan of T1 (graphic immediately above) show the estimation was for 121,951 rows. This is a small shortfall compared with the 125,000 rows actually encountered, but it was enough to cause the hash join to spill to physical tempdb:
A level 1 spill doesn't sound too bad, until you realize that the spill to tempdb probably occurs for each of the 41 partitions.
As a side note, the cardinality estimation error is a little surprising because the system tables accurately show there are 125,000 rows in every partition of T1. Unfortunately, the optimizer uses regular column and index statistics to derive cardinality estimates here rather than system table information (e.g. sys.partitions).
We will never know how well the collocated parallel hash join plan might have worked without the cardinality estimation error (and the resulting 41 spills to tempdb) but we do know:
Putting this all together, what we would really like to see is the same collocated join strategy, but using merge join instead of hash join. Unfortunately, the current query optimizer cannot produce a collocated merge join; it only knows how to do collocated hash join.
So where does this leave us?
We can try to write our own collocated join query. We can use sys.partitions to find the partition numbers, and CROSS APPLY to get a count per partition, with a final step to sum the partial counts. The following query implements this idea:
row_count = SUM(Subtotals.cnt)
-- Partition numbers
FROM sys.partitions AS p
p.[object_id] = OBJECT_ID(N'T1', N'U')
AND p.index_id = 1
-- Count per collocated join
cnt = COUNT_BIG(*)
$PARTITION.PFT(T1.TID) = p.partition_number
AND $PARTITION.PFT(T2.TID) = p.partition_number
) AS SubTotals;
The estimated plan is:
The cardinality estimates aren't all that good here, especially the estimate for the scan of the system table underlying the sys.partitions view.
Nevertheless, the plan shape is heading toward where we would like to be. Each partition number from the system table results in a per-partition scan of T1 and T2, a one-to-many Merge Join, and a Stream Aggregate to compute the partial counts. The final Stream Aggregate just sums the partial counts.
Execution time for this query is around 3,500ms, with the same IO statistics as always. This compares favourably with 5,000ms for the serial plan produced by the optimizer with the OPTION (MERGE JOIN) hint. This is another case of the sum of the parts being less than the whole – summing 41 partial counts from 41 single-partition merge joins is faster than a single merge join and count over all partitions.
Even so, this single-threaded collocated merge join is not as quick as the original parallel hash join plan, which executed in 2,600ms.
On the positive side, our collocated merge join uses only one logical processor and requires no memory grant. The parallel hash join plan used 16 threads and reserved 569 MB of memory:
Our collocated merge join plan should benefit from parallelism. The reason parallelism is not being used is that the query references a system table. We can work around that by writing the partition numbers to a temporary table (or table variable):
partition_number integer PRIMARY KEY);
INSERT #P (partition_number)
AND p.index_id = 1;
FROM #P AS p
Using the temporary table adds a few logical reads, but the overall execution time is still around 3500ms, indistinguishable from the same query without the temporary table. The problem is that the query optimizer still doesn't choose a parallel plan for this query, though the removal of the system table reference means that it could if it chose to:
In fact the optimizer did enter the parallel plan phase of query optimization (running search 1 for a second time):
Unfortunately, the parallel plan found seemed to be more expensive than the serial plan. This is a crazy result, caused by the optimizer's cost model not reducing operator CPU costs on the inner side of a nested loops join. Don't get me started on that, we'll be here all night.
In this plan, everything expensive happens on the inner side of a nested loops join. Without a CPU cost reduction to compensate for the added cost of exchange operators, candidate parallel plans always look more expensive to the optimizer than the equivalent serial plan.
We can produce the desired parallel plan using trace flag 8649 again:
) AS SubTotals
The actual execution plan is:
One difference between this plan and the collocated hash join plan is that a Repartition Streams exchange operator is used instead of Distribute Streams. The effect is similar, though not quite identical. The Repartition uses round-robin partitioning, meaning the next partition id is pushed to the next thread in sequence. The Distribute Streams exchange seen earlier used Demand partitioning, meaning the next partition id is pulled across the exchange by the next thread that is ready for more work. There are subtle performance implications for each partitioning option, but going into that would again take us too far off the main point of this post.
The important thing is the performance of this parallel collocated merge join – just 1350ms on a typical run.
The list below shows all the alternatives from this post (all timings include creation, population, and deletion of the temporary table where appropriate) from quickest to slowest:
The parallel collocated merge join requires no memory grant (aside from a paltry 1.2MB used for exchange buffers). This plan uses 16 threads at DOP 8; but 8 of those are (rather pointlessly) allocated to the parallel scan of the temporary table. These are minor concerns, but it turns out there is a way to address them if it bothers you.
This final tweak replaces the temporary table with a hard-coded list of partition ids (dynamic SQL could be used to generate this query from sys.partitions):
) AS P (partition_number)
The parallel collocated hash join plan is reproduced below for comparison:
The manual rewrite has another advantage that has not been mentioned so far: the partial counts (per partition) can be computed earlier than the partial counts (per thread) in the optimizer's collocated join plan. The earlier aggregation is performed by the extra Stream Aggregate under the nested loops join.
The performance of the parallel collocated merge join is unchanged at around 1350ms.
It is a shame that the current query optimizer does not consider a collocated merge join. The example used in this post showed an improvement in execution time from 2600ms to 1350ms using a modestly-sized data set and limited parallelism. In addition, the memory requirement for the query was almost completely eliminated – down from 569MB to 1.2MB.
The problem with the parallel hash join selected by the optimizer is that it attempts to process the full data set all at once (albeit using eight threads). It requires a large memory grant to hold all 5 million rows from table T1 across the eight hash tables, and does not take advantage of the divide-and-conquer opportunity offered by the common partitioning.
The great thing about the collocated join strategies is that each parallel thread works on a single partition from both tables, reading rows, performing the join, and computing a per-partition subtotal, before moving on to a new partition.
If you have trouble visualizing what is happening from just looking at the parallel collocated merge join execution plan, let's look at it again, but from the point of view of just one thread operating between the two Parallelism (exchange) operators.
Our thread picks up a single partition id from the Distribute Streams exchange, and starts a merge join using ordered rows from partition 1 of table T1 and partition 1 of table T2. By definition, this is all happening on a single thread. As rows join, they are added to a (per-partition) count in the Stream Aggregate immediately above the Merge Join. Eventually, either T1 (partition 1) or T2 (partition 1) runs out of rows and the merge join stops.
The per-partition count from the aggregate passes on through the Nested Loops join to another Stream Aggregate, which is maintaining a per-thread subtotal. Our same thread now picks up a new partition id from the exchange (say it gets id 9 this time). The count in the per-partition aggregate is reset to zero, and the processing of partition 9 of both tables proceeds just as it did for partition 1, and on the same thread.
From each thread's point of view, there is no parallelism in this plan. Don't be misled by the row counts shown in the execution plan – these are grant totals across all threads, and across all iterations of the nested loops join.
Each thread picks up a single partition id and processes all the data for that partition, completely independently from other threads working on other partitions. One thread might eventually process partitions (1, 9, 17, 25, 33, 41) while another is concurrently processing partitions (2, 10, 18, 26, 34) and so on for the other six threads at DOP 8.
The point is that all 8 threads can execute independently and concurrently, continuing to process new partitions until the wider job (of which the thread has no knowledge!) is done. This divide-and-conquer technique can be much more efficient than simply splitting the entire workload across eight threads all at once.
Understanding and Using Parallelism in SQL Server
Parallel Execution Plans Suck
© 2013 Paul White – All Rights Reserved
Twitter: @SQL_Kiwi
This is a post for T-SQL Tuesday #43 hosted by my good friend Rob Farley. The topic this month is Plan Operators. I haven't taken part in T-SQL Tuesday before, but I do like to write about execution plans, so this seemed like a good time to start.
This post is in two parts. The first part is primarily an excuse to use a pretty bad play on words in the title of this blog post (if you're too young to know what a telephone operator or a switchboard is, I hate you). The second part of the post looks at an invisible query plan operator (so to speak).
Allow me to present the rare and interesting execution plan operator, Switch:
Books Online has this to say about Switch:
Following that description, I had a go at producing a Fast Forward Cursor plan that used the TOP operator, but had no luck. That may be due to my lack of skill with cursors, I'm not too sure.
The only application of Switch in SQL Server 2012 that I am familiar with requires a local partitioned view:
CREATE TABLE dbo.T1 (c1 int NOT NULL CHECK (c1 BETWEEN 00 AND 24));
CREATE TABLE dbo.T2 (c1 int NOT NULL CHECK (c1 BETWEEN 25 AND 49));
CREATE TABLE dbo.T3 (c1 int NOT NULL CHECK (c1 BETWEEN 50 AND 74));
CREATE TABLE dbo.T4 (c1 int NOT NULL CHECK (c1 BETWEEN 75 AND 99));
SELECT c1 FROM dbo.T1
SELECT c1 FROM dbo.T2
SELECT c1 FROM dbo.T3
SELECT c1 FROM dbo.T4;
Not only that, but it needs an updatable local partitioned view. We'll need some primary keys to meet that requirement:
ALTER TABLE dbo.T1
PRIMARY KEY (c1);
ALTER TABLE dbo.T2
ALTER TABLE dbo.T3
ALTER TABLE dbo.T4
We also need an INSERT statement that references the view. Even more specifically, to see a Switch operator, we need to perform a single-row insert (multi-row inserts use a different plan shape):
INSERT dbo.V1 (c1)
And now…the execution plan:
The Constant Scan manufactures a single row with no columns. The Compute Scalar works out which partition of the view the new value should go in. The Assert checks that the computed partition number is not null (if it is, an error is returned). The Nested Loops Join executes exactly once, with the partition id as an outer reference (correlated parameter).
The Switch operator checks the value of the parameter and executes the corresponding input only. If the partition id is 0, the uppermost Clustered Index Insert is executed, adding a row to table T1. If the partition id is 1, the next lower Clustered Index Insert is executed, adding a row to table T2…and so on.
In case you were wondering, here's a query and execution plan for a multi-row insert to the view:
Yuck! An Eager Table Spool and four Filters! I prefer the Switch plan.
My guess is that almost all the old strategies that used a Switch operator have been replaced over time, using things like a regular Concatenation Union All combined with Start-Up Filters on its inputs. Other new (relative to the Switch operator) features like table partitioning have specific execution plan support that doesn't need the Switch operator either. This feels like a bit of a shame, but perhaps it is just nostalgia on my part, it's hard to know.
Please do let me know if you encounter a query that can still use the Switch operator in 2012 – it must be very bored if this is the only possible modern usage!
The second part of this post uses an example based on a question Dave Ballantyne asked using the SQL Sentry Plan Explorer plan upload facility. If you haven't tried that yet, make sure you're on the latest version of the (free) Plan Explorer software, and then click the Post to SQLPerformance.com button. That will create a site question with the query plan attached (which can be anonymized if the plan contains sensitive information). Aaron Bertrand and I keep a close eye on questions there, so if you have ever wanted to ask a query plan question of either of us, that's a good way to do it.
The issue I want to talk about revolves around a query issued against a calendar table. The script below creates a simplified version and adds 100 years of per-day information to it:
USE tempdb;
CREATE TABLE dbo.Calendar
dt date NOT NULL,
isWeekday bit NOT NULL,
theYear smallint NOT NULL,
CONSTRAINT PK__dbo_Calendar_dt
PRIMARY KEY CLUSTERED (dt)
-- Monday is the first day of the week for me
-- Add 100 years of data
INSERT dbo.Calendar WITH (TABLOCKX)
(dt, isWeekday, theYear)
isWeekday =
WHEN DATEPART(WEEKDAY, CA.dt) IN (6, 7)
theYear = YEAR(CA.dt)
FROM Sandpit.dbo.Numbers AS N
VALUES (DATEADD(DAY, N.n - 1, CONVERT(date, '01 Jan 2000', 113)))
) AS CA (dt)
N.n BETWEEN 1 AND 36525;
The following query counts the number of weekend days in 2013:
Days = COUNT_BIG(*)
FROM dbo.Calendar AS C
theYear = 2013
AND isWeekday = 0;
It returns the correct result (104) using the following execution plan:
The query optimizer has managed to estimate the number of rows returned from the table exactly, based purely on the default statistics created separately on the two columns referenced in the query's WHERE clause. (Well, almost exactly, the unrounded estimate is 104.289 rows.)
There is already an invisible operator in this query plan – a Filter operator used to apply the WHERE clause predicates. We can see it by re-running the query with the enormously useful (but undocumented) trace flag 9130 enabled:
Now we can see the full picture. The whole table is scanned, returning all 36,525 rows, before the Filter narrows that down to just the 104 we want. Without the trace flag, the Filter is incorporated in the Clustered Index Scan as a residual predicate. It is a little bit more efficient than using a separate operator, but residual predicates are still something you will want to avoid where possible. The estimates are still spot on though:
Anyway, looking to improve the performance of this query, Dave added the following filtered index to the Calendar table:
CREATE NONCLUSTERED INDEX Weekends
ON dbo.Calendar(theYear)
WHERE isWeekday = 0;
The original query now produces a much more efficient plan:
Unfortunately, the estimated number of rows produced by the seek is now wrong (365 instead of 104):
What's going on? The estimate was spot on before we added the index!
You might want to grab a coffee for this bit.
Using another trace flag or two (8606 and 8612) we can see that the cardinality estimates were exactly right initially:
The highlighted information shows the initial cardinality estimates for the base table (36,525 rows), the result of applying the two relational selects in our WHERE clause (104 rows), and after performing the COUNT_BIG(*) group by aggregate (1 row). All of these are correct, but that was before cost-based optimization got involved :)
When cost-based optimization starts up, the logical tree above is copied into a structure (the 'memo') that has one group per logical operation (roughly speaking). The logical read of the base table (LogOp_Get) ends up in group 7; the two predicates (LogOp_Select) end up in group 8 (with the details of the selections in subgroups 0-6). These two groups still have the correct cardinalities as trace flag 8608 output (initial memo contents) shows:
During cost-based optimization, a rule called SelToIdxStrategy runs on group 8. It's job is to match logical selections to indexable expressions (SARGs). It successfully matches the selections (theYear = 2013, is Weekday = 0) to the filtered index, and writes a new alternative into the memo structure. The new alternative is entered into group 8 as option 1 (option 0 was the original LogOp_Select):
The new alternative is to do nothing (PhyOp_NOP = no operation), but to instead follow the new logical instructions listed below the NOP.
The LogOp_GetIdx (full read of an index) goes into group 21, and the LogOp_SelectIdx (selection on an index) is placed in group 22, operating on the result of group 21. The definition of the comparison 'the Year = 2013' (ScaOp_Comp downwards) was already present in the memo starting at group 2, so no new memo groups are created for that.
The new memo groups require two new cardinality estimates to be derived. First, LogOp_Idx (full read of the index) gets a predicted cardinality of 10,436. This number comes from the filtered index statistics:
DBCC SHOW_STATISTICS (Calendar, Weekends)
The second new cardinality derivation is for the LogOp_SelectIdx applying the predicate (theYear = 2013). To get a number for this, the cardinality estimator uses statistics for the column 'theYear', producing an estimate of 365 rows (there are 365 days in 2013!):
DBCC SHOW_STATISTICS (Calendar, theYear)
This is where the mistake happens. Cardinality estimation should have used the filtered index statistics here, to get an estimate of 104 rows:
Unfortunately, the logic has lost sight of the link between the read of the filtered index (LogOp_GetIdx) in group 22, and the selection on that index (LogOp_SelectIdx) that it is deriving a cardinality estimate for, in group 21. The correct cardinality estimate (104 rows) is still present in the memo, attached to group 8, but that group now has a PhyOp_NOP implementation.
Skipping over the rest of cost-based optimization (in a belated attempt at brevity) we can see the optimizer's final output using trace flag 8607:
This output shows the (incorrect, but understandable) 365 row estimate for the index range operation, and the correct 104 estimate still attached to its PhyOp_NOP. This tree still has to go through a few post-optimizer rewrites and 'copy out' from the memo structure into a tree suitable for the execution engine. One step in this process removes PhyOp_NOP, discarding its 104-row cardinality estimate as it does so.
To finish this section on a more positive note, consider what happens if we add an OVER clause to the query aggregate. This isn't intended to be a 'fix' of any sort, I just want to show you that the 104 estimate can survive and be used if later cardinality estimation needs it:
Days = COUNT_BIG(*) OVER ()
The estimated execution plan is:
Note the 365 estimate at the Index Seek, but the 104 lives again at the Segment! We can imagine the lost predicate 'isWeekday = 0' as sitting between the seek and the segment in an invisible Filter operator that drops the estimate from 365 to 104.
Even though the NOP group is removed after optimization (so we don't see it in the execution plan) bear in mind that all cost-based choices were made with the 104-row memo group present, so although things look a bit odd, it shouldn't affect the optimizer's plan selection. I should also mention that we can work around the estimation issue by including the index's filtering columns in the index key:
ON dbo.Calendar(theYear, isWeekday)
WHERE isWeekday = 0
There are some downsides to doing this, including that changes to the isWeekday column may now require Halloween Protection, but that is unlikely to be a big problem for a static calendar table ;) With the updated index in place, the original query produces an execution plan with the correct cardinality estimation showing at the Index Seek:
That's all for today, remember to let me know about any Switch plans you come across on a modern instance of SQL Server!
Finally, here are some other posts of mine that cover other plan operators:
Segment and Sequence Project
Common Subexpression Spools
Why Plan Operators Run Backwards
Row Goals and the Top Operator
Hash Match Flow Distinct
Top N Sort
Index Spools and Page Splits
Singleton and Range Seeks
Hash Join Performance
Compute Scalar
You might have noticed the SQL Intersection logo appearing in my recent blog posts. This is a brand new event focussed on tuning and troubleshooting the SQL Server core engine (including Windows SQL Azure Database). If you read and enjoy at least some of the things I write about, this conference is one you should seriously consider attending.
For my part, I'll be presenting three sessions: two on Interpreting Execution Plans, and one on Parallel Query Execution. I have to promote my sessions, because just look at the other speakers you have to choose from:
As well as speaking, all these people will be around to chat to over the four conference days, and some are offering complete days of training at pre- and post-conference workshops as well.
Personally, I'm particularly excited about talking to the following people and attending their sessions:
Each of the main conference days has three tracks to choose from:
The full schedule is available here as a PDF document, or you can visit the conference website for all the details.
The conference pricing is very competitive (especially so, considering the location and speaker line-up):
When registering, quote the Discount Code WHITE to receive an extra $50 off these prices.
I really hope to see you in Las Vegas – please feel free to come and talk to me about anything concerning execution plans or the query optimizer :)
Paul White SQL Server MVP 2011, 2012 Twitter: @SQL_Kiwi
I love SQL Server execution plans. It is often easy to spot the cause of a performance problem just by looking at one. The task is considerably easier if the plan includes run-time information (a so-called 'actual' execution plan), but even a compiled plan can be very useful. Nevertheless, there are still times where the execution plan does not tell the whole story, and we need to think more deeply about query execution to really understand a performance problem. This post looks at one such example, based on a recent question posted on the SQL Performance Q & A site.
This plan is reasonably large (20MB cached plan size) but not massively complex once you break it down (click on the image above to view it full-size in a new window). The context of the question is that this query usually executes in less than a minute, but sometimes it runs for nearly twenty minutes – though the plan appears identical.
There are many different things to look for in execution plans. What you choose to look at first is as much a matter of personal preference as anything, but many people are drawn to high-cost operators, so I will start there. In this plan, the cost of one operator dominates all others, shown as being responsible for 100% of the cost of the query. It is highlighted in red in Plan Explorer; I have expanded the relevant plan section (the top right) below:
There is no doubt that this seek is busy little thing. It is executed 249,484 times, though it only produces a grand total of 167,813 rows over all iterations of the loop join – an average of just 0.7 rows per seek. There are all sorts of interesting details in the plan about this seek – I could write a whole blog post about it – but two details that stand out are the "Force Seek: True" and "Partitioned: True" attributes. These tell us that the base table is partitioned, and the query writer had to use a FORCESEEK table hint to get this plan.
Without this hint, the optimizer would almost certainly choose a Hash Match or Merge Join rather than Nested Loops. This is understandable given the optimizer's cost model and the simplifying assumptions it makes (such as assuming every query starts with a cold buffer cache). That's fine, but we can see from the query plan that the inner-side table has 643 million rows. Left to its own devices, the optimizer would estimate that it would be faster to perform a sequential scan of 643 million rows (with large-block read-ahead) than it would be to run a quarter-million randomly-distributed seeks driven by a Nested Loops join.
I doubt that the optimizer's reasoning here is sound (at least on any reasonably modern hardware) but there we go. The query author probably knows that a good fraction of this table is likely to be in cache, so with all that in mind, I think we can reasonably assume at this stage that the FORCESEEK hint is genuinely needed here, and this part of the plan is at least reasonably optimal.
Important note: The seek certainly does not account for 100% of the runtime cost of this query. Remember cost percentages are always estimates – even in 'actual' plans. It can be useful to check the reasons for high-estimated-cost operators, but they should never be used as a primary tuning metric.
This query was executed on SQL Server 2012, so there is a handy warning triangle on the Sort operator indicating that one or more sort runs had to be spilled to physical tempdb disk. The plan clearly shows this spilling is a result of an inaccurate cardinality estimate at the Filter operator (the estimates are not bad at all prior to this). The Sort expects 9,217 rows totalling approximately 5MB, but actually encountered 61,846 rows in 35MB. As you may know, memory for sorts and hashes is allocated before execution starts, and generally cannot expand dynamically at run time.
The spilled sort is undesirable, of course, but it is unlikely to be a major cause of the occasional poor performance given the small size of the spilled data. Nevertheless, this might be a good place to split this query up. The idea would be to write the results of the query (up to and including the Filter) to a temporary heap table using SELECT INTO, and then create a clustered index with the same keys as the Sort operator. The temporary table would not be large, and may well perform better overall than the spilled sort, including the cost of creating the clustered index. Of course, creating this index will involve a sort, but it will be one based on the known cardinality of the temporary heap table. The part of the plan that could be replaced by a temporary table is shown below:
I am a big fan of simplifications like this. Smaller execution plans tend to optimize better for all sorts of reasons, and the source code usually becomes easier to maintain as well. I should mention there is another warning triangle in the 2012 execution plan (shown on the root icon), which relates to some implicit conversions that I will mention later.
The execution plan was captured with Plan Explorer, so we can also easily see I/O statistics for the two executions. The first is for a fast (sub-60-second) run:
Overall, these I/O numbers show pretty much what we would expect: a decent number of logical reads associated with the seeks into the Trans table (but certainly not 100% of the total, ha ha), a very small number of physical reads, and a small amount of read-ahead activity on a couple of tables.
The second set of I/O data is from a slow run (18 minutes or so):
The very obvious difference is the appearance of a work table, with 178 million logical reads and 130 million LOB logical reads. It seems very likely this work table, and its 300 million logical reads, is responsible for the dramatic decrease in query performance. But given that the execution plans are identical (right down to the XML) what is causing this?
My answer to that question (on the Q & A site) was that it is related to the increased level of read-ahead activity, but to see why that is the case, we will need to reproduce the issue and dig a bit deeper.
Before we really get going on this, it will be useful to take a look at what the execution plan is doing in outline. We saw the first part of the plan earlier when looking at the spilling sort. The data set at that point (which we would like to write to a temporary table, remember) essentially represents source data for a second query, which uses a series of Nested Loops Left Joins to lookup information from other tables:
The inner side of each join involves some reasonably involved logic, which is thankfully not important to the present discussion. What is important is that the result of each lookup is a LOB data type. This begins to shed some light on the LOB logical reads reported against the work table, but it does not explain why the work table (and the 300 million associated reads) do not appear when the query runs quickly (with the same execution plan).
The first part of the repro involves creating six tables that represent the lookup tables in the original query plan. Each table will have 10,000 rows, consisting of a sequential reference number and a second column containing a 2048 single-byte-character string. The source table used to drive the lookups will be a regular Numbers table containing just a single integer column.
CREATE TABLE dbo.T1 (id integer IDENTITY PRIMARY KEY, d char(2048));
CREATE TABLE dbo.T2 (id integer IDENTITY PRIMARY KEY, d char(2048));
CREATE TABLE dbo.T3 (id integer IDENTITY PRIMARY KEY, d char(2048));
CREATE TABLE dbo.T4 (id integer IDENTITY PRIMARY KEY, d char(2048));
CREATE TABLE dbo.T5 (id integer IDENTITY PRIMARY KEY, d char(2048));
CREATE TABLE dbo.T6 (id integer IDENTITY PRIMARY KEY, d char(2048));
FROM dbo.Numbers AS n WHERE n BETWEEN 1 AND 10000;
INSERT dbo.T3 WITH (TABLOCKX)
INSERT dbo.T4 WITH (TABLOCKX)
INSERT dbo.T5 WITH (TABLOCKX)
INSERT dbo.T6 WITH (TABLOCKX)
The next step is to ensure that each lookup table is optimally organized for read-ahead:
ALTER TABLE dbo.T1 REBUILD WITH (MAXDOP = 1);
ALTER TABLE dbo.T2 REBUILD WITH (MAXDOP = 1);
ALTER TABLE dbo.T3 REBUILD WITH (MAXDOP = 1);
ALTER TABLE dbo.T4 REBUILD WITH (MAXDOP = 1);
ALTER TABLE dbo.T5 REBUILD WITH (MAXDOP = 1);
ALTER TABLE dbo.T6 REBUILD WITH (MAXDOP = 1);
The original query translates into our simplified test rig as:
DECLARE @d nvarchar(max) = NCHAR(10000);
SELECT n.n,
(SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T1 AS t WHERE t.id = n.n),
(SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T2 AS t WHERE t.id = n.n),
(SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T3 AS t WHERE t.id = n.n),
(SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T4 AS t WHERE t.id = n.n),
(SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T5 AS t WHERE t.id = n.n),
(SELECT CONCAT(t.d, t.d, t.d, t.d, t.d, t.d, @d) FROM dbo.T6 AS t WHERE t.id = n.n)
FROM dbo.Numbers AS n
WHERE n.n BETWEEN 1 AND 10000
ORDER BY n.n
The broad idea there is to concatenate our 2048-character column to itself five times and include a Unicode character that was used in the original query as a delimiter that could not appear in the source data. Each lookup performs the same basic operation against its target table, and the final result is the result of concatenating all the intermediate results. The query hints are necessary to get the right plan shape, just because my test rig tables are so much smaller than the real ones.
Note that the Unicode delimiter means the 2048-character single-byte data is implicitly converted to Unicode, doubling in size. It is not a crucial feature of the test, but it did appear in the original query and explains the type conversion warnings in the execution plan I mentioned earlier. The execution plan for the test query is (click to enlarge if necessary):
I should also stress that the CONCAT operator (new in SQL Server 2012) is not crucial either. If you are using an earlier version of SQL Server, an equivalent query (for present purposes) is shown below. I'm going to stick with CONCAT for the remainder of the post, however.
(SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T1 AS t WHERE t.id = n.n) +
(SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T2 AS t WHERE t.id = n.n) +
(SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T3 AS t WHERE t.id = n.n) +
(SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T4 AS t WHERE t.id = n.n) +
(SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T5 AS t WHERE t.id = n.n) +
(SELECT @d+t.d+t.d+t.d+t.d+t.d+t.d FROM dbo.T6 AS t WHERE t.id = n.n)
With all data in memory, the test query (in either form) completes in about 1.6 seconds on my laptop. The result shows that each output row contains 147,468 bytes of Unicode character data. A typical set of I/O statistics follows:
Nothing too exciting to see there, but this is just our baseline.
With no data in memory, the test query now runs for 18.6 seconds – almost 12x slower. The I/O statistics show the expected (but still mysterious!) work table and its associated reads:
The Extended Events wait statistics show SQL Server spent very little of that time waiting on my laptop's slow hard drive – just 402 ms:
The are a number of factors in play here that we will look at in turn.
One of the reasons the optimizer prefers Hash Match and Merge Join for larger inputs is that the data access patterns tend to favour large sequential read-ahead. Both hash and merge tend to scan (range-scan in the case of a seek) their inputs, and the SQL Server Storage Engine automatically issues read-ahead when it detects this type of access. There is nothing in the execution plan to show that a base table will be read with read-ahead, it just happens.
A very basic implementation of Nested Loops join would not benefit from read-ahead at all on its inner side. The outer (driving) side of the loops join might well be a scan or range-scan of an index, and so benefit from automatic read-ahead, of course. The inner side is executed once per outer row, resulting in a rapid succession of small index seeks for different values. These small seeks will typically not be large enough to trigger the automatic read-ahead mechanism. Indeed, in our test, each inner side seek is for precisely one value.
SQL Server improves on this by implementing a second read-ahead mechanism especially for Nested Loops joins (not all N-L joins, it is a cost-based decision the optimizer makes). The basic idea is to buffer extra rows from the outer side of the join, and to use the row values in the buffer to drive read-ahead for the inner side. The effect is that the Nested Loops join becomes a partly blocking operator as outer-side rows are read into the buffer and read-ahead issued based on buffered index key values.
This read-ahead may be either order-preserving or not, and is indicated in the execution plan by the Nested Loop attributes With Ordered Prefetch and With Unordered Prefetch, respectively. When unordered prefetch occurs, the inner side is processed in whatever order the asynchronous reads happen to complete. With ordered prefetching, the mechanism is careful to ensure that the order of rows entering the join is preserved on the output.
In the test rig, the ORDER BY clause means there is a need to preserve row order, so Ordered Prefetch is used:
The issue described in this post is not specific to ordered prefetching – the same behaviour is just as likely with unordered prefetching. The point is that Nested Loops prefetching is one of the requirements.
Documented trace flags 652 and 8744 may be used (with care, and after serious testing) to disable automatic read-ahead and Nested Loops prefetching respectively. This is sometimes beneficial where all data is expected to be in memory (in which case read-ahead processing consumes resources better used by query execution) or where the I/O subsystem is extremely fast. In case you were wondering, there is no background thread for prefetching – all the work of checking whether the data is in memory, and issuing I/O if not, is performed by the worker thread executing the query.
I should stress that read-ahead and Nested Loops prefetching is generally A Very Good Thing with typical storage solutions (e.g. SANs) and both work best (or at all) when indexes have low logical fragmentation.
The issue described here also requires that a large object data type is manufactured before prefetching. The Compute Scalar operators in the test execution plan perform that function:
By 'manufactured', I mean that the source columns are not LOB types, but the expression output is – notice the implicit conversion to nvarchar(max). To be clear about it, the issue we are analysing here does not occur when Nested Loops prefetching occurs with an expression that was a LOB type to begin with.
The optimizer is quite good, generally speaking, at moving scalar expressions around. If the query had featured inner joins (whether by query design or through optimizer activities) the chances are quite good that the problematic expressions (the LOB manufacturers) would have moved beyond the prefetching, and so out of harm's way. It is quite tricky to preserve NULL-extension and other outer-join semantics properly when moving expressions above an outer join, so the optimizer generally does not even try. In essence, the outer join represents an optimization barrier to the LOB-manufacturing expressions.
When Nested Loops prefetching occurs with a manufactured LOB, the question arises of where to store the created LOBs when buffering rows for prefetch. If the source data were already a LOB type, the execution engine would already have memory structures in place to handle them. When prefetching encounters a manufactured LOB, it needs to store it somewhere, since the engine is no longer processing a stream of one row at a time. It turns out that there is a small memory buffer set aside for this eventuality, which empirical tests show to be 24KB.
However, this 24KB (directly allocated, not via workspace memory grant) is shared across all concurrently executing prefetching joins in the query. With six such joins in the test rig plan and large manufactured LOBs, the buffer stands no chance. As a result, query execution engages a bail-out option: a work table created in tempdb. Though the pages of the worktable may in fact remain memory-resident, overheads (including latching and using general-purpose code interfaces for access to the buffered rows) mean this is very much slower than using the direct-memory cache.
As with most internal work tables, the logical reads reported on this work table indicate the number of rows processed (not 8KB pages, as for regular I/O statistics). This fact, together with the large number of items processed via the worktable in our test, accounts for the millions of reads reported.
The creation and use of the work table depends on run time conditions and timing. If execution finds the data it needs is already in memory, the prefetch checks are still performed, but no asynchronous read requests end up being posted. The 24KB buffer is never filled, so the need to create a work table never arises. The more prefetch that actually occurs, the higher the chances that the buffer will fill. It is quite possible to experience a low level of prefetch with manufactured LOBs without the engine needing to bail out to a work table, especially if the LOBs are not very big and the I/O system is quite fast.
We can rewrite the query to avoid feeding manufactured LOB data to the prefetch buffer. The idea is to use OUTER APPLY to return the data that contributes to the concatenation, rather than the result of the concatenation. We can then perform the CONCAT operation (which handles NULLs nicely without extra work) after the join, avoiding the prefetch buffer issue completely. In SQL Server versions prior to 2012, we would need to use direct string concatenation, and handle rows that are NULL-extended explicitly using ISNULL or COALESCE.
CONCAT(oa1.i0, oa1.i1, oa1.i2, oa1.i3, oa1.i4, oa1.i5, oa1.i6),
CONCAT(oa2.i0, oa2.i1, oa2.i2, oa2.i3, oa2.i4, oa2.i5, oa2.i6),
CONCAT(oa3.i0, oa3.i1, oa3.i2, oa3.i3, oa3.i4, oa3.i5, oa3.i6),
CONCAT(oa4.i0, oa4.i1, oa4.i2, oa4.i3, oa4.i4, oa4.i5, oa4.i6),
CONCAT(oa5.i0, oa5.i1, oa5.i2, oa5.i3, oa5.i4, oa5.i5, oa5.i6),
CONCAT(oa6.i0, oa6.i1, oa6.i2, oa6.i3, oa6.i4, oa6.i5, oa6.i6)
OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T1 AS t WHERE t.id = n.n) AS oa1
OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T2 AS t WHERE t.id = n.n) AS oa2
OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T3 AS t WHERE t.id = n.n) AS oa3
OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T4 AS t WHERE t.id = n.n) AS oa4
OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T5 AS t WHERE t.id = n.n) AS oa5
OUTER APPLY (SELECT i0 = @d, i1 = t.d, i2 = t.d, i3 = t.d, i4 = t.d, i5 = t.d, i6 = t.d FROM dbo.T6 AS t WHERE t.id = n.n) AS oa6
The execution plan for the rewritten query looks visually similar to the problematic one:
However, the Compute Scalars no longer manufacture a LOB data type, they just emit column and variable references:
All the concatenation work (and LOB manufacture) is performed by the final top-level Compute Scalar in a single monster expression [Expr1056]:
With all data in memory, the new query completes in 1.8 seconds (very slightly up on 1.6 seconds before):
When all data must be fetched from disk, the query issues optimal prefetching and completes in 7.3 seconds (down from 18.6 seconds) with no work table:
The Extended Events wait statistics now show 3.8 seconds spent waiting for my laptop's slow spinning disk (which is a good thing!)
Work tables can appear in STATISTICS IO output for a wide range of reasons, but if you encounter one with a very large number of reads – particularly LOB reads – you may be encountering this issue. The rewrite proposed above may not always be possible, but you should be able to refactor your query to avoid the issue now you know it exists.
I am not a fan of doing large amounts of string manipulation in SQL Server. I am always particularly suspicious of the perceived need to split or concatenate large volumes of strings.
I am, however, a fan of always using explicit data types (rather than relying on implicit conversions) and generating relatively small query plans that offer the query optimizer clear and obvious choices. By necessity, this often means writing small SQL queries in logical steps (and no, long chains of common table expressions do not count!)
The real world does not always make these things possible, of course, but it is good to have goals :)
© 2013 Paul White – All Rights Reserved email: email@example.com twitter: @SQL_Kiwi
Screenshots acquired using SnagIt by TechSmith Query plan details obtained using Plan Explorer PRO by SQLSentry
I have just published a four-part series for SQLPerformance.com on the Halloween Problem. Some of you will never have heard of this issue, and those that have might associate it only with T-SQL UPDATE queries. In fact, the Halloween problem affects execution plans for INSERT, UPDATE, DELETE and MERGE statements.
This is a topic I have been meaning to write about properly for years, ever since I read Craig Freedman's 2008 blog post on the topic, which ended with the cryptic comment:
"…although I've used update statements for all of the examples in this post, some insert and delete statements also require Halloween protection, but I'll save that topic for a future post."
That future post never materialized, sadly, so I thought I would have a go. The four parts of the series are summarized and linked below, I hope you find the material interesting.
As always, I appreciate your comments and feedback.
Paul White @SQL_Kiwi email@example.com
Microsoft have released a fix for incorrect results returned when querying an indexed view. The problem applies to:
The Knowledge Base article does not go into much detail, or provide a reproduction script, but this blog entry does :)
The KB does say that reproducing the bug requires these features:
There are two important details I would like to add right away:
The fix is available in the following cumulative update packages:
Cumulative Update 2 for SQL Server 2012 SP1 [build 11.0.3339] Cumulative Update 5 for SQL Server 2012 RTM [build 11.0.2395] Cumulative Update 4 for SQL Server 2008 R2 SP2 [build 10.50.4270] Cumulative Update 10 for SQL Server 2008 R2 SP1 [build 10.50.2868] Cumulative Update 8 for SQL Server 2008 SP3 [build 10.00.5828]
No service pack contains this fix, you must apply one of the hotfix packages above.
The first thing we will need is two tables:
CREATE TABLE dbo.Parent
parent_id integer IDENTITY NOT NULL,
value varchar(20) NOT NULL,
CONSTRAINT PK_Parent_id
PRIMARY KEY CLUSTERED (parent_id)
CREATE TABLE dbo.Child
child_id integer IDENTITY NOT NULL,
parent_id integer NOT NULL,
CONSTRAINT PK_Child_id
PRIMARY KEY CLUSTERED (child_id)
And a few rows of data:
INSERT dbo.Child (parent_id)
SELECT New.parent_id
INSERT Parent
OUTPUT inserted.parent_id
) AS New;
The tables now look like this (parent first):
We can now add the required FOREIGN KEY relationship:
ALTER TABLE dbo.Child
ADD CONSTRAINT FK_Child_Parent
FOREIGN KEY (parent_id)
REFERENCES dbo.Parent (parent_id);
Next, a very simple indexed view that joins the two tables (the view could contain more complex features like aggregates):
CREATE VIEW dbo.ParentsAndChildren
FROM dbo.Parent AS p
JOIN dbo.Child AS c ON
c.parent_id = p.parent_id;
CREATE UNIQUE CLUSTERED INDEX cuq
ON dbo.ParentsAndChildren (child_id);
The final step is to use a MERGE statement to make some changes to the Parent table:
DECLARE @ParentMerge AS TABLE
parent_id integer PRIMARY KEY,
value varchar(20) NOT NULL
INSERT @ParentMerge
(parent_id, value)
(1, 'Kiwi Fruit'),
(4, 'Dragon Fruit');
MERGE dbo.Parent AS p
USING @ParentMerge AS s ON
s.parent_id = p.parent_id
UPDATE SET value = s.value
INSERT (value) VALUES (s.value)
deleted.value AS old_value,
inserted.value AS new_value;
This MERGE performs two actions:
The statement includes an OUTPUT clause to show the changes it makes (this is not required for the repro):
This confirms that the changes have been made as we requested: parent row 1 has changed; and row 4 has been added. The changes are reflected in the base tables:
SELECT * FROM dbo.Parent AS p;
SELECT * FROM dbo.Child AS c;
As highlighted, row 1 has changed from Apple to Kiwi Fruit and row 4 has been added.
We do not expect to see row 4 in the indexed view because there are no child records for that row, and the indexed view uses an inner join. Checking the indexed view using the NOEXPAND table hint (required in non-Enterprise SKUs to use indexes on a view):
FROM dbo.ParentsAndChildren
The results are incorrect. They show the old value of the data for parent row 1.
Now we try using the EXPAND VIEWS query hint to force SQL Server to access the base tables rather than reading view indexes:
This query produces correct results.
On SQL Server Enterprise Edition, the optimizer chooses whether to access the indexed view or the base tables. For following query, without any hints, the optimizer chooses not to expand the view. It reads the view index and produces incorrect results:
-- Enterprise Edition ONLY
FROM dbo.ParentsAndChildren;
Perhaps adding a child row to match the new parent row 4 will somehow fix things up?
INSERT dbo.Child (parent_id) VALUES (4);
SELECT * FROM dbo.ParentsAndChildren WITH (NOEXPAND);
SELECT * FROM dbo.ParentsAndChildren OPTION (EXPAND VIEWS);
No. The query plan that accesses the view index still returns an incorrect value for row 1. It seems MERGE has corrupted our indexed view.
Checking the view with DBCC CHECKTABLE returns no errors:
DBCC CHECKTABLE (ParentsAndChildren);
Unless we use the EXTENDED_LOGICAL_CHECKS option:
DBCC CHECKTABLE (ParentsAndChildren) WITH EXTENDED_LOGICAL_CHECKS;
The damage is repairable:
ALTER DATABASE Sandpit
DBCC CHECKTABLE (ParentsAndChildren, REPAIR_REBUILD) WITH EXTENDED_LOGICAL_CHECKS;
ALTER DATABASE Sandpit SET MULTI_USER;
You probably do not want to set your database to SINGLE_USER mode and run a DBCC repair after every MERGE statement, however. We could also rebuild the indexed view's clustered index manually, of course.
For the MERGE statement above, the query optimizer builds a plan that does not update the indexed view (click to enlarge):
In a version of SQL Server with the fix applied, the same MERGE statement produces a plan that does maintain the indexed view:
The plan operators used to keep the view index in step with the base tables are highlighted. Without these operators, the changes to the base table are not correctly written to any indexes defined on the view. The root cause is related to the same simplification that allows the optimizer to remove the reference to the Parent table in this query:
The FOREIGN KEY relationship and NOT NULL constraints on the referencing column together mean that the join to Parent cannot affect the result of the query, so the join is simplified away. In SQL Server 2012, we can see when this simplification is performed because the following message appears when undocumented trace flags 8619 and 3604 are enabled during compilation:
The same message is emitted when a MERGE statement contains a WHEN MATCHED THEN UPDATE clause and either a WHEN NOT MATCHED THEN INSERT or WHEN MATCHED … THEN DELETE clause. These conditions combine such that the optimizer incorrectly concludes that a table reference can be removed, when in fact it is needed later on when the update side of the plan is built.
Other details of the query and database can affect whether the simplification can be misapplied. For example, if the FOREIGN KEY constraint contains an ON DELETE CASCADE clause, and the MERGE contains a DELETE clause, the simplification is not performed, the TF 8619 message does not appear, and the bug does not manifest.
The key to determining whether a particular query is vulnerable to this bug (TF 8619 aside) is to check whether the query plan includes operators to maintain the indexed view. At a minimum, you should see a update operator for the view:
SQL Sentry Plan Explorer identifies the operator as applying to a view explicitly, in SSMS you need to click on the graphical operator and inspect the Properties window.
The updated conditions for incorrect results are:
Under these conditions, the indexes on the view do not reflect the state of the base tables and incorrect results are returned. Once the hot fix is applied, the optimizer does not misapply the simplification so the correct indexed view maintenance features are built into execution plans.
Update: I am adding this based on Ian Yates' great question in the comments: my expectation is that applying this hotfix will not remove any existing indexed view corruption. You would need to test the hotfix as usual, apply it, and then either rebuild all affected indexed views manually, or run DBCC CHECKDB with the EXTENDED_LOGICAL_CHECKS option (which could take a long time).
Twitter: @SQL_Kiwi Email: email@example.com
Let's say you have a big table with a clustered primary key, and an application that inserts batches of rows into it. The nature of the business is that the batch will inevitably sometimes contain rows that already exist in the table.
The default SQL Server INSERT behaviour for such a batch is to throw error 2627 (primary key violation), terminate the statement, roll back all the inserts (not just the rows that conflicted) and keep any active transaction open:
CREATE TABLE #Big (pk int NOT NULL CONSTRAINT PK_Big PRIMARY KEY);
-- Start with values 1 & 5 in the table
INSERT #Big (pk) VALUES (1), (5);
-- Our batch transaction
-- Insert a batch containing some pre-existing rows
INSERT #Big (pk) VALUES (1), (2), (3), (4), (5);
-- Show the contents of the table after the insert statement
SELECT pk FROM #Big;
-- Show the transaction count
SELECT tran_count = @@TRANCOUNT;
-- Rollback
-- Final table contents
-- Tidy up
DROP TABLE #Big;
The output is:
Let us further imagine that the desired behaviour is that new rows in a batch should be inserted, and any duplicates silently rejected. Most importantly, no error messages should be returned to the client. Ideally, this would be achieved without immediate application changes, and without impacting concurrent users of the table (the instance is Enterprise Edition, so online operations are available).
This seems like an ideal use for the IGNORE_DUP_KEY option:
CREATE TABLE dbo.Big
pk int NOT NULL,
CONSTRAINT PK_Big
PRIMARY KEY (pk)
-- Unique values
INSERT dbo.Big (pk)
-- key 3 already exists
That script executes successfully with just a warning (not an error!) about the duplicate key:
We would like to add the IGNORE_DUP_KEY option to the existing primary key constraint, but the ALTER TABLE command does not have an ALTER CONSTRAINT clause. We do not want to drop the existing primary key and recreate it with the new option, because the table is large and we want to avoid disrupting concurrent users. Dropping and recreating would result in rebuilding the entire table first as a heap and then as a clustered table again.
Although there is no ALTER CONSTRAINT syntax, we do know that certain constraint modifications can be performed using ALTER INDEX REBUILD on the index used to enforce the constraint. We can, for example, change the type of compression used, the index fill factor, and whether row locking is enabled:
CREATE TABLE dbo.Big (pk int NOT NULL CONSTRAINT PK_Big PRIMARY KEY);
ALTER INDEX PK_Big ON dbo.Big
DROP TABLE dbo.Big;
Unfortunately, we cannot use the same trick to add the IGNORE_DUP_KEY option to the underlying index for the primary key:
The same error message results even if the ONLINE = ON option is not specified. There will be a range of views about how accurate the error message text is here, but we cannot avoid the fact that the operation we want to perform is not supported by SQL Server.
One idea is to add a new UNIQUE constraint (or index) on the same columns as the primary key, but with the IGNORE_DUP_KEY option added. This operation can be performed ONLINE:
-- Existing table
-- Existing data
INSERT dbo.Big (pk) VALUES (1), (2), (3);
-- New constraint (or index) with IGNORE_DUP_KEY, added ONLINE
ALTER TABLE dbo.Big
ADD CONSTRAINT UQ_idk
UNIQUE NONCLUSTERED (pk)
--CREATE UNIQUE NONCLUSTERED INDEX UQ_idk
--ON dbo.Big (pk)
-- Key 3 is a duplicate, just a warning now
INSERT dbo.Big (pk) VALUES (3), (4), (5);
SELECT pk FROM dbo.Big;
The new arrangement results in the correct final state of the database, without throwing an error. The effect is the same as if we had been able to modify the existing primary key constraint to add IGNORE_DUP_KEY:
There are some drawbacks to this idea, which we will explore in some detail. The drawbacks are significant, so adding the extra index with IGNORE_DUP_KEY is only really suitable as a temporary solution, as we will see. The first INSERT in the previous script (without the extra constraint or index with IGNORE_DUP_KEY) is pretty trivial; it just shows the constants from the VALUES clause being inserted to the clustered index:
The second INSERT (with the IGNORE_DUP_KEY index) is rather more complex (click to enlarge):
One fairly obvious consequence of adding the new index is that the Clustered Index Insert operator now has to maintain the new nonclustered index too. I used Plan Explorer above because it shows the per-row nonclustered index insert more explicitly than SSMS, where you have to dig into the Object node in the Properties window with the relevant graphical operator selected:
Another way to see the nonclustered index maintenance explicitly is to run the query again with undocumented trace flag 8670 to produce a wide update plan:
Besides maintaining the extra index, the IGNORE_DUP_KEY plans seem to be doing a lot of extra work: there are lots of new operators compared with the simple insert. As you would expect, all the new operators are associated with ignoring duplicate keys, and there are two distinct cases to consider.
The first case relates to checking for INSERT rows that already exist in the base table. This checking is implemented in the execution plan by the Left Semi Join, Index Seek, and Assert operators:
The Index Seek looks for the key value of the current row we are looking to insert. The Semi Join cannot be an Inner Join because that would reject rows where a match was not found (and we need to insert a row in that case). Nevertheless, the query processor needs to know if an existing row was found with the same key value. The Semi Join sets a value to indicate this, which is stored in the Probe Column:
The Assert operator (known internally as a Stream Check) tests a condition and raises an error if the test fails. Assert operators are often seen in plans that affect columns with CHECK constraints, for example. In this case, however, the Assert does not raise an error, it emits the 'Duplicate key was ignored.' message instead, and only passes a row on to its parent (the Sort operator) if the condition passes. The check performed by the Assert is based on the Probe value stored in the expression labelled [Expr1013] above:
The Asset passes rows where the predicate evaluates to anything other than NULL. If a match was found by the Index Seek (so the Probe Column, Expr1013 is not NULL) the Assert does not pass on the row and raises a warning instead. The following TF 8607 output fragment for the INSERT statement shows the option (there is nothing equivalent in regular show plan output unfortunately):
The first check only looks for rows from the insert set that already exist in the base table. The query processor also needs to check for duplicates within the set of values we are inserting. The Segment and Top operators in the plan combine to meet this requirement:
The Segment requires a stream ordered by the index keys, and adds a flag to indicate the start of a new group of key values. The Top operator returns only one row from each group. The overall effect is to remove rows with duplicate index key values.
The Top and Segment execution operators together implement a single physical query processor operator called a "Group-By Top". I mention this detail because we need to be familiar with the internal name to understand the TF 8607 output, which indicates that this operator also emits a `Duplicate key was ignored.' warning when it encounters a group with more than one key value:
Adding the new index means that locks will now be taken on the nonclustered index when checking for existing rows:
It might surprise you to learn that the index seek acquires Range S-U locks on the nonclustered index (extract from the Books Online link below):
Key-range locks like this are only taken under the SERIALIZABLE isolation level, but our INSERT statement uses them whatever isolation level the user runs the query under (for example, range locks are still taken if the session is running under the default READ COMMITTED isolation level).
SQL Server raises the effective isolation level to SERIALIZABLE for the Index Seek (and just that operator) because it needs to be sure that if it does not find a match in the index, that situation remains the same until it inserts the new row. The Index Seek is looking for a key value that does not exist, so a range lock is necessary to prevent a concurrent transaction inserting a row with that key value before we do. There is no existing key in the index to lock (because the row does not exist) so a range lock is the only option. If SQL Server did not do this, our INSERT query might fail with a duplicate key error despite the IGNORE_DUP_KEY setting (we check for a row, don't find it, someone else inserts it, then we try to).
The optimizer adds a SERIALIZABLE hint for the Index Seek operator (internally, a physical Range operator) as we can see using another extract from the TF 8607 output:
The execution plan is also forced to use the nonclustered index with the IGNORE_DUP_KEY setting for this seek (FORCEDINDEX) and an update lock (UPDLOCK) hint is also given to help prevent conversion deadlocks. Nevertheless, you may find increased deadlocking if you choose to add an extra IGNORE_DUP_KEY index like this.
Adding a nonclustered unique index with the IGNORE_DUP_KEY option and the same key as the clustered primary key allowed us to solve an immediate problem without code changes, while keeping the table online, but it does come at a price. The execution plan is much more complex (and expensive) than the original INSERT, and there is a chance of deadlocks. The biggest performance impact of adding the extra index is of course the cost of maintaining it, meaning we need to look at a more permanent solution via a code change.
The (trivial) test I am going to run inserts 5000 unique rows from my table of numbers into the table we have been using so far. To establish a baseline, we will first look at the execution plan for an INSERT to the table with a nonclustered IGNORE_DUP_KEY index:
SELECT n FROM dbo.Numbers
WHERE n BETWEEN 1 AND 5000;
This plan is very similar to the one we analysed earlier, though a Merge is used to perform the Left Semi Join, and a wide update plan has been chosen, making the nonclustered index insert easier to see. The other main feature is an Eager Table Spool, required for Halloween Protection. The estimated cost of this execution plan is 0.363269 cost units on my installation.
The first code alternative to the extra index is to modify the INSERT statement to check that rows do not already exist in the destination. There are a number of SQL syntaxes for this, each with different characteristics and performance in different circumstances. To keep things simple, and because I only want to make a couple of specific points here, I have chosen my simple example to produce the same execution plans for all the common syntax variants. The first thing to do is to drop our extra constraint:
DROP CONSTRAINT UQ_idk;
Now we can evaluate the modified INSERT statement:
-- I prefer this syntax
WHERE n BETWEEN 1 AND 5000
AND NOT EXISTS (SELECT * FROM dbo.Big WHERE pk = n);
-- With EXCEPT
-- Not recommended
AND n NOT IN (SELECT pk FROM dbo.Big);
All three produce this execution plan:
This has an estimated cost of 0.0981188 units – much cheaper than the 0.363269 cost seen previously. The Halloween Protection spool still features in the plan, but there is a weakness in our queries that you might have already spotted. We are not doing anything to protect against duplicate key violation errors in case someone else inserts a row after we have checked to see if it exists, but before we insert it. The query optimizer added a SERIALIZABLE hint when it added an existence check, so if avoiding errors is important to us, we need to do the same:
AND NOT EXISTS (SELECT * FROM dbo.Big WITH (SERIALIZABLE) WHERE pk = n);
We do not need the UPDLOCK hint for two reasons. First, the engine automatically takes update locks for us when reading the source table. Second, we are reading from the same index we are inserting to (not reading from a nonclustered index and inserting to the clustered index) so the previous deadlock scenario is not applicable.
Another option is to use the WHEN NOT MATCHED feature of the Merge statement. This time we will add the necessary SERIALIZABLE hint up front:
MERGE dbo.Big WITH (SERIALIZABLE) AS b
USING (SELECT n FROM dbo.Numbers WHERE n BETWEEN 1 AND 5000) AS s
ON s.n = b.pk
INSERT (pk) VALUES (s.n);
This plan has an estimated cost of 0.0950127 units – slightly less than the 0.0981188 units for the modified INSERT plans. Some of this improvement is due to the lack of a Halloween Protection spool, for interesting reasons I cover in depth in a short series of articles to be published shortly (update: part one is out).
These are not meant to be performance tests by any stretch of the imagination. There are any number of subtle factors that will affect the execution plans and run times for different numbers of rows, different distributions, and so on. I should stress that I normally find MERGE plans perform less well than separate INSERT/UPDATE/DELETE more often than not. Anyway, in case you are interested, typical performance results on my machine for this specific test are (INSERT first, then MERGE), timings in milliseconds:
When IGNORE_DUP_KEY is specified for a unique clustered index (primary key or otherwise), duplicates are handled by the storage engine rather than the query processor. For example:
CREATE TABLE dbo.T (pk int CONSTRAINT PK_idk PRIMARY KEY WITH (IGNORE_DUP_KEY = ON));
The execution plan shows none of the complexity of the nonclustered index case:
The TF 8607 output contains none of the query processor hints to ignore duplicates and raise warnings:
The IGNORE_DUP_KEY side of things is handled entirely by the storage engine – if it finds a row in the unique index where it was going to insert one, it flags a warning but does not try to insert (which would cause an error). The estimated cost of this query plan is identical whether the unique clustered index has IGNORE_DUP_KEY or not – there is no extra work for the query processor.
If you are wondering why the same mechanism is not used for a nonclustered unique index with the IGNORE_DUP_KEY option, my understanding is it is because the Clustered Index is always updated before the nonclustered ones (even in a narrow plan). By the time the storage engine detected a duplicate in the nonclustered index, it would have already added the row to the base table. So, the query processor handles IGNORE_DUP_KEY for nonclustered indexes.
This is my understanding of the mechanics of IGNORE_DUP_KEY, I don't know for sure and will happily correct any details I may have wrong. Any storage engine experts reading this please contact me if so.
This post was inspired by a post by Daniel Adeniji and our subsequent discussion of it. My thanks to him for permission to analyse the issue further here, and for allowing me to reference his original. The issue described here may not accurately reflect Daniel's original problem – I used a certain amount of artistic licence. Even if the specific issue is not particularly interesting to you, I hope you enjoyed some aspects of the analysis and maybe picked up some new information along the way.
© 2013 Paul White – All rights reserved twitter: @SQL_Kiwi email: email@example.com
Most tuning efforts for data-changing operations concentrate on the SELECT side of the query plan. Sometimes people will also look at important storage engine considerations like locking and transaction log throughput that can have dramatic effects. As a consequence, a number of common practices have emerged, such as avoiding large numbers of row locks and lock escalation, splitting large changes into smaller batches of a few thousand rows and combining a number of small changes into a single transaction in order to optimize log flushes.
This is all good of course, but what about the data-changing side of the query plan – the INSERT, UPDATE, DELETE or MERGE operation itself – are there any query processor considerations we should take into account? The short answer is yes. The query optimizer considers different plan options for the write-side of an I/U/D/M query, though there isn't a huge amount of T-SQL language support that allows us to affect these choices directly. Nevertheless, there are things to be aware of, and things we can look to change.
Side note: In this post I am going to use the term update (lower case) to apply to any operation that changes the state of the database (INSERT, UPDATE, DELETE and MERGE in T-SQL). This is a common practice in the literature, and is used inside SQL Server too as we will see.
First a bit of background. All query plans execute using a demand-driven iterator model, and updates are no exception. Parent operators drive child operators (to the right of the parent) to do work by asking them for a row at a time. Take the following simple AdventureWorks INSERT for example:
DECLARE @T AS TABLE (ProductID int);
INSERT @T (ProductID)
SELECT p.ProductID
FROM Production.Product AS p;
Plan execution starts at the far left, where you can think of the green T-SQL INSERT icon as representing rows returned to the client. This root node asks its immediate child operator (the Table Insert) for a row. The Table Insert requests a row from the Index Scan, which provides one. This row is inserted into the heap, and an empty row is returned to the root node (if the INSERT query contained an OUTPUT clause, the returned row would contain data). This row-by-row process continues until all source rows have been processed. Notice that the XML show plan output shows the Heap Table Insert is performed by an Update operator internally. Ok, on to the matter at hand:
Wide per-index update plans have a separate update operator for each clustered and nonclustered index. It is always possible for the optimizer to produce this type of plan; the options described later have not been (or cannot be) implemented when certain engine features are used. For example, if the update target has an indexed view defined on it, a wide update plan has to be used to maintain the indexed view. An example per-index update plan is shown below:
This plan updates the base table using a Clustered Index Delete operator. This operator may also read and output extra column values necessary to find and delete rows from nonclustered indexes. The iterative delete activity on the base table is driven by the Eager Table Spool on the top branch. The spool is eager because it stores all the rows from its input in a worktable before returning the first row to its parent operator (the Index Delete on the top branch). The effect is that all qualifying base table rows are deleted before any nonclustered index changes occur.
The spool in this plan is a common subexpression spool. It is populated once and then acts as a row source for multiple consumers. In this case, the contents of the spool are consumed first by the top-branch Index Delete, which removes index entries from one of the nonclustered indexes. When the Sequence operator switches to asking for rows from the lower branch, the spool is rewound and replays its rows for the second nonclustered index. Note that the spool contains the UNION of all columns required by nonclustered index changes.
Narrow per-row updates have a single update operator which maintains the base table (heap or clustered) and one or more nonclustered indexes. Each row arriving at the update operator updates all indexes associated with the operator before processing the next row. An example:
DECLARE @T AS TABLE (pk int PRIMARY KEY, col1 int UNIQUE, col2 int UNIQUE);
DECLARE @S AS TABLE (pk int PRIMARY KEY, col1 int, col2 int);
INSERT @T (pk, col1)
FROM @S AS s;
The execution plan viewed using SQL Sentry Plan Explorer shows the nonclustered index maintenance explicitly (hover over the Clustered Index Insert for a tooltip showing the names of the nonclustered indexes involved):
In SQL Server Management Studio, there is no information about the nonclustered index maintenance in the graphical plan or tooltips, we need to click on the update operator (Clustered Index Insert) and then check the Properties window:
This shows the clustered index and two nonclustered indexes being maintained. Because all indexes are updated for each row streaming through the update operator, this plan shape is also known as a per-row update plan.
The query optimizer uses cost-based reasoning to decide whether to update each nonclustered index separately (per-index) or as part of the base table changes (per-row). An example that updates one nonclustered index per-row, and another per-index is shown below:
CREATE TABLE #T (pk int IDENTITY NOT NULL, col1 int, col2 varchar(8000) DEFAULT '');
ALTER TABLE #T ADD CONSTRAINT PK_T PRIMARY KEY (pk);
CREATE INDEX nc1 ON #T (col1);
CREATE INDEX nc2 ON #T (col1) INCLUDE (col2);
The combination strategy can be seen with Plan Explorer (click to expand in a new tab):
The details are also displayed in the SSMS Properties window when the Clustered Index Insert operator is selected as well.
The third form of update is an optimization of the per-row update plan for very simple operations. The cost-based optimizer still emits a per-row update plan, but a rewrite is subsequently applied to collapse the reading and writing operations into a single operator:
-- Simple operations
DECLARE @T AS TABLE (pk int PRIMARY KEY, col1 int);
INSERT @T (pk, col1) VALUES (1, 1000);
UPDATE @T SET col1 = 1234 WHERE pk = 1;
DELETE @T WHERE pk = 1;
The complete execution plans (and extracts from the XML plans) are shown below:
The UPDATE and DELETE plans have been collapsed to a `Simple Update` operation, while the INSERT is simplified to a `Scalar Insert`. We can see the original optimizer output tree with trace flags 3604 and 8607:
INSERT @T (pk, col1) VALUES (1, 1000) OPTION (RECOMPILE);
UPDATE @T SET col1 = 1234 WHERE pk = 1 OPTION (RECOMPILE);
DELETE @T WHERE pk = 1 OPTION (RECOMPILE);
The trace output for the INSERT statement shown above is:
Notice the two physical operators: a constant scan (in-memory table) containing the literal values specified in the query; and a stream update operator that performs the database changes per row. All three statements produce a similar optimizer tree output (and all use a stream update). We can prevent the single-operator optimization being applied with undocumented trace flag 8758:
This exposes the expanded per-row update plans produced by the optimizer before the single-operator rewrite:
Single operator plans can be significantly more efficient than the original multiple-operator form in the right circumstances, for example if the plan is executed very frequently.
From this point forward, I'm going to use simple AdventureWorks DELETE examples, but the general points apply equally well to INSERT, UPDATE and MERGE as well. The examples will not have a complicated SELECT component, because I want to concentrate on the update side of the plan rather than the reading side.
It's worth emphasising again that per-row update plans are an optimization that is not available for every update query. The optimizer favours a per-row plan if the expected number of rows at the update operator is low. In the example below, the optimizer expects to delete 25 rows:
This plan updates the base table (a clustered index in this case) and all nonclustered indexes in sequence per row. The row source here is an ordered scan of a nonclustered index, which means rows will not generally be presented in clustered index key order to the update operator.
An unordered stream like this tends to result in random I/O (assuming physical I/O is required at all, of course). If the plan is expected to process only a small number of rows, the optimizer decides it is not worth adding extra operations to encourage sequential I/O.
If the expected number of rows is a bit larger, the optimizer may decide to build a plan that applies prefetching to one or more update operators. The basic idea is the same as ordinary prefetching (a.k.a read-ahead) for scans and range seeks. The engine looks ahead at the keys of the incoming stream and issues asynchronous IOs for pages that will be needed by the update operator soon. Prefetching helps reduce the impact of the random I/O mentioned a moment ago. An example of prefetching on the update operator is shown below for the same query and an expected cardinality of 50 rows:
The prefetching is unordered from the perspective of the clustered index. Neither SSMS nor Plan Explorer show the prefetch information prominently. In Plan Explorer, we need to have the With Unordered Prefetch optional column selected. To do this, switch to the Plan Tree tab, open the Column Chooser, and drag the column to the grid. The unordered prefetch property is ticked for the Clustered Index Delete operator in the screenshot below:
In SSMS, click on the Clustered Index Delete icon in the graphical plan, and then look in the Properties window:
If the query plan were reading from the clustered index, the read operation would issue regular read-ahead, so there would be no point prefetching from the Clustered Index Delete as well. The example below shows the expected cardinality increased to 100, where the optimizer switches from scanning the nonclustered index with unordered prefetching to scanning the clustered index. No prefetching occurs on the update operator in this plan:
Where the plan property With Unordered Prefetch is not set, it is simply omitted – it does not appear set to False as you might expect.
Where rows are expected to arrive at an update operator in non-key order, the optimizer might consider adding an explicit sort. The idea is that presenting rows in key order will encourage sequential I/O for the index pages. The optimizer weighs the cost of the sort against the expected benefits of avoiding random I/O. The execution plan below shows an example of a sort being added for this reason:
The sort is on Transaction ID, the clustering key for this table. With the incoming stream now sorted, the update operator can use ordered prefetching. The plan is still scanning the nonclustered index on the read side, so read-ahead issued by that operator does not bring in the clustered index pages needed by the update operator. Ordered prefetching tends to result in sequential I/O, compared with the mostly random I/O of unordered prefetching. The With Ordered Prefetch column is also not shown by default by Plan Explorer, so it needs to be added as we did before:
Not every update operator with ordered prefetching requires a sort. If the optimizer finds a plan that naturally presents keys in nonclustered index order, an update operator may still use ordered prefetching.
When the optimizer decides to explore a plan alternative that requires ordered input to an update operator, it will set the DML Request Sort property for that operator. Plan Explorer shows this setting in the update operator tooltip:
SSMS shows With Ordered Prefetch and DML Request Sort in the Properties window:
Sorting and ordered prefetching may also be considered for the nonclustered indexes in a per-index update plan.
This plan shows all three update operators with DML Request Sort set. The Clustered Index Delete does not require an explicit sort because rows are being read (with internal ordering guarantees) from the Clustered Index Scan. The two non-clustered indexes do require explicit sorts, however. Both nonclustered index update operators also use ordered prefetching; the clustered index update does not because the scan automatically invokes read-ahead for that index.
The next example shows that each update operator is considered separately for the various optimizations:
That plan features unordered prefetching on the Clustered Index Delete (because the row source is a scan of a nonclustered index), an explicit sort with ordered prefetching on the top branch Index Delete, and unordered prefetching on the bottom branch Index Delete.
Is the following a per-index or per-row update plan?
It appears to be a per-index plan because there are two separate update operators, but there is no blocking operator (eager spool or sort) between the two. This plan is a pipeline: each row returned from the seek will be processed first by the Clustered Index Delete and then by the Index Delete. In that sense, the both updates (clustered and nonclustered) are certainly per-row.
The important thing is not the terminology, it is being able to interpret the plan. Now we know what the various optimizations are for, we can see why the optimizer chose the plan above over the seemingly equivalent but more efficient-looking narrow plan:
The narrow plan has no prefetching. The Seek provides read-ahead for the clustered index pages, but the single non-clustered index has nothing to prefetch any pages from disk it might need. By contrast, the previous wide update plan has two update operators. The Clustered Index Delete has no prefetching for the same reason as in the narrow plan, but the Index Delete has unordered prefetching enabled.
So, although the smaller narrow plan looks like it ought to be more efficient, it might perform less well if nonclustered index pages are required from disk and unordered prefetching proves effective. On the other hand, if all required nonclustered index pages are in memory at the time the query is executed, the wide plan might perform less well since it features an extra operator and has to perform all the work associated with prefetching (even though ultimately no physical reads are issued).
You may have noticed a lack of performance numbers (I/O statistics, elapsed times and so on) in this post. There is a good reason for this. The optimizations presented here are quite dependent on SQL Server configuration and hardware. I don't want you drawing general conclusions based on the performance of the rather ordinary single SATA drive in my laptop, the 256MB of RAM I have allowed for my SQL Server 2012 instance, and some rather trivial AdventureWorks examples.
It depends, naturally.
If the data structures you are changing are very likely to be in memory, and/or if you have a very fast random I/O system, the optimizer's goal of minimizing random I/O and enhancing sequential I/O may not make much sense for you. The strategies the optimizer employs may well end up costing you much more than they save.
On the other hand, if your system has a much smaller buffer pool than database working set size, and your I/O system works very much faster with large sequential I/O than with smaller random I/O requests, you should generally find the optimizer makes reasonable choices for you, subject to the usual caveats about useful up-to-date statistics and accurate cardinality estimation, of course.
If your system fits the optimizer's model, at least to a first approximation, you will usually find that narrow update plans are best for low cardinality update operations, unordered prefetching helps a bit when more rows are involved, ordered prefetching helps more, and explicit sorts before nonclustered index updates helps most of all for the largest sets. That is the theory, anyway.
The problem I see most often is with the optimization that is supposed to help most: the explicit sort before a nonclustered index update. The idea is that sorting the input to the index update in key order promotes sequential I/O, and often it does. The problem occurs if the workspace memory allocated to the sort at execution time proves to be too small to perform the sort entirely in memory. The memory grant is fixed based on cardinality estimation and row size estimates, and may be reduced if the server is under memory pressure at the time.
In any case, however it occurs, a sort that runs out of memory spills whole sort runs to physical tempdb disk, often repeatedly. Unsurprisingly, this is not at all good for performance, and can result in queries that complete very much slower than if the sort had not been introduced at all. SQL Server reuses the general Sort operator for sorting index keys – it does not have a sort specially optimized for index updates which could make a best effort to sort within the memory allocated, but never spill to disk. Perhaps I should suggest this on Connect :)
The narrow plan optimization can cause problems where it is selected due to a low cardinality estimate, where several nonclustered indexes need to be maintained, the necessary pages are not in memory, and the I/O system is slow at random reads.
The ordered and unordered prefetch options cause problems much more rarely. For a system with all data in memory, there is a small but possibly measurable impact due to the prefetch overhead (finding pages to consider read-ahead for, checking to see if they are already in the buffer pool, and so on). Even if no asynchronous I/O is ever issued by the worker, it still spends time on the task that it could spend doing real work.
The usual answer to deal with poor execution plan choices due to a system's configuration or performance characteristics not matching the optimizer's model is to try different T-SQL syntax, and/or to try query hints. There are times when it is possible to rewrite the query to get a plan that performs better, and other times where rethinking the problem a bit can pay dividends. Various creative uses of partitioning, minimal logging, and bulk loading are possible in some cases, for example.
There are very few hints that can help with the update side of a plan that does not respond to the usual tricks, however. The two I use most often affect the optimizer's cardinality estimation - OPTION (FAST n) and a trick involving TOP and the OPTIMIZE FOR query hint. OPTION (FAST n) affects cardinality estimates in a plan by setting a final row goal, but its effects can be difficult to predict, and may not have much of an effect if the plan contains blocking operators. Anyway, the general idea is to vary the value of 'n' in the hint until the optimizer chooses the desired plan shape or optimization options as described in this post. Best of luck.
The idea with TOP is similar, but tends to work better in my experience. The trick is to declare a bigint variable with the number of rows the query should return (or a very large value such as the maximum value of a bigint if all rows are required), use that as the parameter to a TOP, and then use the OPTIMIZE FOR hint to set a value for 'n' that the optimizer should use when considering alternative plans. This option is particularly useful for encouraging a narrow plan.
Most of the examples in this post used the TOP trick in the following general form:
DECLARE @n bigint = 9223372036854775807;
DELETE TOP (@n)
FROM Production.TransactionHistory
OPTION (OPTIMIZE FOR (@n = 50));
Sure there are trace flags that affect the optimizations in this post. They are undocumented and unsupported of course, and may only work on some versions, but they can be handy to validate a performance analysis, or to generate a plan guide for a particularly crucial query. They can also be fun to play with on a personal system to explore their effects. The main ones that affect the optimizations described here are:
2332 : Force DML Request Sort (CUpdUtil::FDemandRowsSortedForPerformance)
8633: Enable prefetch (CUpdUtil::FPrefetchAllowedForDML and CPhyOp_StreamUpdate::FDoNotPrefetch)
8744 : Disable prefetch (CUpdUtil::FPrefetchAllowedForDML)
8758 : Disable rewrite to a single operator plan (CPhyOp_StreamUpdate::PqteConvert)
8790 : Force a wide update plan (CUpdUtil::PexprBuildWideUpdatePlan)
8795 : Disable DML Request Sort (CUpdUtil::FDemandRowsSortedForPerformance)
9115 : Disable prefetch (CUpdUtil::FPrefetchAllowedForDML)
These trace flags can all be manipulated using the usual DBCC commands or enabled temporarily for a particular query using the OPTION (QUERYTRACEON xxxx) hint.
The optimizer has a wide range of choices when building the writing side of an update plan. It may choose to update one or more indexes separately, or as part of the base table update. It may choose to explicitly sort rows as part of a per-index update strategy, and may elect to perform unordered or ordered prefetching as well. As usual, these decisions are made based on costs computed using the optimizer's model. This model may not always produce plans that are optimal for your hardware (and as usual the optimizer's choices are only as good as the information you give it).
If a particular update query is performance critical for you, make sure cardinality estimates are reasonably accurate. Test with alternate syntax and/or trace flags to see if an alternative plan would perform significantly better in practice. It is usually possible to use documented techniques like TOP clauses and OPTIMIZE FOR hints to produce an execution plan that performs well. Where that is not possible, more advanced tricks and techniques like plan guides may be called for.
Thanks for reading today, I hope this post was interesting and provided some new insights into update query optimization.
© 2013 Paul White – All rights reserved email: email@example.com twitter: @SQL_Kiwi
A MERGE statement can fail, and incorrectly report a unique key violation when:
Say we have two tables, one that is the target of a MERGE statement, and another that contains updates to be applied to the target. The target table contains three columns, an integer primary key, a single character alternate key, and a status code column. A filtered unique index exists on the alternate key, but is only enforced where the status code is 'a':
CREATE TABLE #Target
pk integer NOT NULL,
ak character(1) NOT NULL,
status_code character(1) NOT NULL,
CREATE UNIQUE INDEX uq1
ON #Target (ak)
INCLUDE (status_code)
WHERE status_code = 'a';
The changes table contains just an integer primary key (to identify the target row to change) and the new status code:
CREATE TABLE #Changes
The sample data for the example is:
INSERT #Target
(pk, ak, status_code)
(1, 'A', 'a'),
(2, 'B', 'a'),
(3, 'C', 'a'),
(4, 'A', 'd');
INSERT #Changes
(pk, status_code)
(1, 'd'),
(4, 'a');
Target Changes ╔════╦════╦═════════════╗ ╔════╦═════════════╗ ║ pk ║ ak ║ status_code ║ ║ pk ║ status_code ║ ╠════╬════╬═════════════╣ ╠════╬═════════════╣ ║ 1 ║ A ║ a ║ ║ 1 ║ d ║ ║ 2 ║ B ║ a ║ ║ 4 ║ a ║ ║ 3 ║ C ║ a ║ ╚════╩═════════════╝ ║ 4 ║ A ║ d ║ ╚════╩════╩═════════════╝
The target table's alternate key (ak) column is unique, for rows where status_code = 'a'. Applying the changes to the target will change row 1 from status 'a' to status 'd', and row 4 from status 'd' to status 'a'. The result of applying all the changes will still satisfy the filtered unique index, because the 'A' in row 1 will be deleted from the index and the 'A' in row 4 will be added.
Let's now execute a MERGE statement to apply the changes:
MERGE #Target AS t
USING #Changes AS c ON
c.pk = t.pk
AND c.status_code <> t.status_code
THEN UPDATE SET status_code = c.status_code;
The MERGE changes the two target rows as expected. The updated target table now contains:
╔════╦════╦═════════════╗ ║ pk ║ ak ║ status_code ║ ╠════╬════╬═════════════╣ ║ 1 ║ A ║ d ║ <—changed from 'a' ║ 2 ║ B ║ a ║ ║ 3 ║ C ║ a ║ ║ 4 ║ A ║ a ║ <—changed from 'd' ╚════╩════╩═════════════╝
Now let's repopulate the changes table to reverse the updates we just performed:
TRUNCATE TABLE #Changes;
(1, 'a'),
(4, 'd');
This will change row 1 back to status 'a' and row 4 back to status 'd'. As a reminder, the current state of the tables is:
Target Changes ╔════╦════╦═════════════╗ ╔════╦═════════════╗ ║ pk ║ ak ║ status_code ║ ║ pk ║ status_code ║ ╠════╬════╬═════════════╣ ╠════╬═════════════╣ ║ 1 ║ A ║ d ║ ║ 1 ║ a ║ ║ 2 ║ B ║ a ║ ║ 4 ║ d ║ ║ 3 ║ C ║ a ║ ╚════╩═════════════╝ ║ 4 ║ A ║ a ║ ╚════╩════╩═════════════╝
We execute the same MERGE statement:
However this time we receive the following message:
Msg 2601, Level 14, State 1, Line 1 Cannot insert duplicate key row in object 'dbo.#Target' with unique index 'uq1'. The duplicate key value is (A). The statement has been terminated.
Let's now rewrite the MERGE to use UPDATE instead:
UPDATE t
SET status_code = c.status_code
FROM #Target AS t
JOIN #Changes AS c ON
t.pk = c.pk
c.status_code <> t.status_code;
This query succeeds where the MERGE failed. The two rows are updated as expected:
╔════╦════╦═════════════╗ ║ pk ║ ak ║ status_code ║ ╠════╬════╬═════════════╣ ║ 1 ║ A ║ a ║ <—changed back to 'a' ║ 2 ║ B ║ a ║ ║ 3 ║ C ║ a ║ ║ 4 ║ A ║ d ║ <—changed back to 'd' ╚════╩════╩═════════════╝
In this test, the MERGE query execution happens to apply the changes in the order of the 'pk' column.
In test one, this was not a problem: row 1 is removed from the unique filtered index by changing status_code from 'a' to 'd' before row 4 is added. At no point does the table contain two rows where ak = 'A' and status_code = 'a'.
In test two, however, the first change was to change row 1 from status 'd' to status 'a'. This change means there would be two rows in the filtered unique index where ak = 'A' (both row 1 and row 4 meet the index filtering criteria 'status_code = a').
The storage engine does not allow the query processor to violate a unique key (unless IGNORE_DUP_KEY is ON, but that is a different story, and doesn't apply to MERGE in any case). This strict rule applies regardless of the fact that if all changes were applied, there would be no unique key violation (row 4 would eventually be changed from 'a' to 'd', removing it from the filtered unique index, and resolving the key violation).
The query optimizer usually detects when this sort of temporary uniqueness violation could occur, and builds a plan that avoids the issue. I wrote about this a couple of years ago in my post Beware Sneaky Reads with Unique Indexes (you can read more about the details on pages 495-497 of Microsoft SQL Server 2008 Internals or in Craig Freedman's blog post on maintaining unique indexes). To summarize though, the optimizer introduces Split, Filter, Sort, and Collapse operators into the query plan to:
The effect of all this is that only net changes are applied to an index (as one or more insert, update, and/or delete operations). In this case, the net effect is a single update of the filtered unique index: changing the row for ak = 'A' from pk = 4 to pk = 1. In case that is less than 100% clear, let's look at the operation in test two again:
Target Changes Result ╔════╦════╦═════════════╗ ╔════╦═════════════╗ ╔════╦════╦═════════════╗ ║ pk ║ ak ║ status_code ║ ║ pk ║ status_code ║ ║ pk ║ ak ║ status_code ║ ╠════╬════╬═════════════╣ ╠════╬═════════════╣ ╠════╬════╬═════════════╣ ║ 1 ║ A ║ d ║ ║ 1 ║ d ║ ║ 1 ║ A ║ a ║ ║ 2 ║ B ║ a ║ ║ 4 ║ a ║ ║ 2 ║ B ║ a ║ ║ 3 ║ C ║ a ║ ╚════╩═════════════╝ ║ 3 ║ C ║ a ║ ║ 4 ║ A ║ a ║ ║ 4 ║ A ║ d ║ ╚════╩════╩═════════════╝ ╚════╩════╩═════════════╝
From the filtered index's point of view (filtered for status_code = 'a' and shown in nonclustered index key order) the overall effect of the query is:
Before After ╔════╦════╗ ╔════╦════╗ ║ pk ║ ak ║ ║ pk ║ ak ║ ╠════╬════╣ ╠════╬════╣ ║ 4 ║ A ║ ║ 1 ║ A ║ ║ 2 ║ B ║ ║ 2 ║ B ║ ║ 3 ║ C ║ ║ 3 ║ C ║ ╚════╩════╝ ╚════╩════╝
The single net change there is a change of pk from 4 to 1 for the nonclustered index entry ak = 'A'. This is the magic performed by the split, sort, and collapse. Notice in particular how the original changes to the index key (on the 'ak' column) have been transformed into an update of a non-key column (pk is included in the nonclustered index). By not updating any nonclustered index keys, we are guaranteed to avoid transient key violations.
The estimated MERGE execution plan that produces the incorrect key-violation error looks like this (click to enlarge in a new window):
The successful UPDATE execution plan is (click to enlarge in a new window):
The MERGE execution plan is a narrow (per-row) update. The single Clustered Index Merge operator maintains both the clustered index and the filtered nonclustered index. The UPDATE plan is a wide (per-index) update. The clustered index is maintained first, then the Split, Filter, Sort, Collapse sequence is applied before the nonclustered index is separately maintained.
There is always a wide update plan for any query that modifies the database. The narrow form is a performance optimization where the number of rows is expected to be relatively small, and is not available for all operations. One of the operations that should disallow a narrow plan is maintaining a unique index where intermediate key violations could occur.
The MERGE can be made to work (producing a wide update plan with split, sort, and collapse) by:
Undocumented trace flag 8790 forces a wide update plan for any data-changing query (remember that a wide update plan is always possible). Either change will produce a successfully-executing wide update plan for the MERGE that failed previously.
The optimizer fails to spot the possibility of transient unique key violations with MERGE under the conditions listed at the start of this post. It incorrectly chooses a narrow plan for the MERGE, which cannot provide the protection of a split/sort/collapse sequence for the nonclustered index maintenance.
The MERGE plan may fail at execution time depending on the order in which rows are processed, and the distribution of data in the database. Worse, a previously solid MERGE query may suddenly start to fail unpredictably if a filtered unique index is added to the merge target table at any point.
Connect bug filed here
Bug reproduced on the following SQL Server versions (all x64 Developer Edition):
2012 SP1 CUI (build 11.0.3321 – November 2012) 2008 R2 SP2 CU3 (build 10.50.4266 – October 2012) 2008 SP3 CU8 (build 10.0.5828 – November 2012)
© 2012 Paul White – All Rights Reserved
Twitter: @SQL_Kiwi Email: email@example.com
Estimated row counts on key or RID lookups where a filtering predicate is applied can be wrong in SSMS execution plans. This error does not affect the optimizer's ultimate plan selection, but it does look odd. There are other cases where estimated row counts are inconsistent (for defensible reasons) but the behaviour shown in this post in certainly a bug.
The following AdventureWorks sample query displays TransactionHistory information for ProductID #1 and the last three months of 2003 (if you are using a more recent version of AdventureWorks, you will need to change the year from 2003 to 2007):
FROM Production.TransactionHistory AS th
th.ProductID = 1
AND th.TransactionDate BETWEEN '20030901' AND '20031231';
The query plan is:
The execution flow is pretty straightforward. The plan seeks a non-clustered index on the ProductID column to find rows where ProductID = 1. This non-clustered index is keyed on ProductID alone, but the index also includes the TransactionID clustering key (to point to the parent row in the base table). The index does not cover the query (the TransactionDate column is not present in the index) so a Key Lookup is required for the TransactionDate column. The nested loops join drives a look up process such that each row from the Index Seek on ProductID = 1 results in a lookup in the clustered index to find the TransactionDate value for that row. A final Filter operator passes only rows that meet the date range condition.
The next diagram shows the same plan with cardinality estimates and extra details for the Key Lookup:
The cardinality estimate at the Index Seek is exactly correct. The table is not very large, there are up-to-date statistics associated with the index, so this is as expected. If you run a query to find all rows in the TransactionHistory table for ProductID #1, 45 rows will indeed be returned.
The estimate for the Key Lookup is exactly correct. Each lookup into the Clustered Index to find the Transaction Date is guaranteed to return exactly one row (each non-clustered index entry is associated with exactly one base table row). The Key Lookup is expected to be executed 45 times (shown circled).
The estimate for the Inner Join is exactly correct – 45 rows from the seek joining to one row each time from the lookup, gives a total of 45 rows.
The Filter estimate is also good: SQL Server estimates that of the 45 rows entering the filter, 16.9951 rows will match the specified range of transaction dates. In reality, only 11 rows are produced by this query, but that small difference in estimates is quite normal and certainly nothing to worry about here. You might like to keep that estimate of 16.9951 rows in mind, however.
The same query executed against an identical copy of AdventureWorks on SQL Server 2008 (or R2, or 2012) produces a quite different execution plan:
Instead of an explicit Filter to find rows with the requested date range, the optimizer has pushed the date predicate down to the Key Lookup (the Key Lookup now has a predicate on Transaction Date). This is a good optimization in general terms; it makes sense to filter rows as early as possible. Unfortunately, it has made a bit of a mess of the cardinality estimates in the process. The post-Filter estimate of 16.9951 rows seen in the 2005 plan has been moved to the Key Lookup. Instead of estimating one row per lookup, the plan now suggests that 16.9951 rows will be produced by each clustered index lookup – clearly not right!
To my way of thinking, the execution plan cardinality estimates should look something like this:
As shown, I personally prefer to see the inner side of a nested loops join estimate the number of rows per execution, but I understand I may be in a minority on this point. If the estimate were aggregated over the expected number of executions, the inner-side estimate would be also be 16.9951 (45 executions * 0.37767 per execution).
The query tree produced by the 2008+ optimizer looks much the same as the 2005 version – the explicit Filter is still present. However, a post-optimization rewrite occurs in the 'copy out' phase that removes the Filter and incorporates it in the Key Lookup seek, resulting in a residual predicate on that operator. This rewrite applies to regular scans and seeks too (so all residual predicates on scans and seeks are a result of this late rewrite).
I would like to thank Dima Piliugin (twitter | blog) for introducing me to undocumented trace flag 9130, which disables the rewrite from Filter + (Scan or Seek) to (Scan or Seek) + Residual Predicate. Enabling this flag retains the Filter in the final execution plan, resulting in a SQL Server 2008+ plan that mirrors the 2005 version, with correct estimates.
The bug is that this rewrite that does not correctly update cardinality estimates when the filter is pushed down to a lookup. I should stress that the rewrite occurs after all cost-based decisions have been made, so the incorrect estimate just looks odd and makes plan analysis harder than it ought to be. Cardinality estimates with regular scans and seeks appear to work correctly, as far as I can tell. The bug applies to both RID lookups and Key Lookups where a residual predicate is applied.
Using the trace flag is not a workaround because (a) it is (very) undocumented and unsupported; and (b) it results in a less efficient plan where rows are filtered much later than is optimal. One genuine workaround is to provide a covering non-clustered index (avoiding the lookup avoids the problem):
CREATE INDEX nc1
ON Production.TransactionHistory (ProductID)
INCLUDE (TransactionDate);
With the Transaction Date filter applied as a residual predicate in the same operator as the seek, the final estimate is again as expected:
We could also force the use of the ultimate covering index (the clustered one) with a suitable table index hint:
FROM Production.TransactionHistory AS th WITH (INDEX(1))
Again, the estimate is 16.9951 as expected.
After this post was published on October 15 2012 I was contacted by the SQL Sentry people to see if a good workaround could be incorporated in their free Plan Explorer product. I was happy to provide a little testing and general feedback during a process that ultimately resulted in a new build being released on 31 October 2012. If only SSMS limitations could be addressed so quickly! Once you upgrade to the new version, the plan displayed for our test query is:
This is exactly the representation we would expect if the SQL Server bug did not exist (note that Plan Explorer aggregates estimated inner-side executions for you, and rounds to integer). Well done to the SQL Sentry team, especially Brooke Philpott (@MacroMullet).
Providing a covering non-clustered index to avoid lookups for all possible queries is not always practical, and scanning the clustered index will rarely be the optimal choice either. Nevertheless, these are the best workarounds we have today in SSMS.
Watch out for poor cardinality estimates when a predicate is applied as part of a lookup.
This particular cardinality estimation issue does not affect the final plan choice (the internal estimates are correct) but it does look odd and will confuse people when analysing query plans in SSMS. If you think this situation should be improved, please vote for this Connect item. It will be interesting to see how long it takes to catch up with Plan Explorer.
© 2012 Paul White – All Rights Reserved twitter: @SQL_Kiwi email: firstname.lastname@example.com
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?
The following script creates a table, partitioned on the char(3) column 'Div', and populates it with 100,000 rows of data:
USE Sandpit;
CREATE PARTITION FUNCTION PF (char(3))
'1', '2', '3', '4', '5', '6', '7', '8', '9',
CREATE TABLE dbo.Test
Div char(3) NOT NULL,
Data char(50) NOT NULL,
ON PS(Div);
INSERT dbo.Test WITH (TABLOCKX)
(Div, Data)
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:
PartitionID = F.PartitionID,
RowCnt = COUNT_BIG(*)
FROM dbo.Test AS t WITH (TABLOCK)
CROSS APPLY (VALUES($PARTITION.PF(t.Div))) AS F (PartitionID)
(The partition function defines a total of 36 partitions but only 16 are used by the sample data.)
FROM dbo.Test AS t
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?
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
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:
t.Div = 'ABF'
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 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.
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)):
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:
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:
We can see the implicit type of the string literal 'ABF' using a query:
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.
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);
BaseType = SQL_VARIANT_PROPERTY(CONVERT(sql_variant, t.col1), 'BaseType'),
MaxLength = SQL_VARIANT_PROPERTY(CONVERT(sql_variant, t.col1), 'MaxLength'),
SELECT col1 FROM @T1
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.
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);
Note the lack of an implicit conversion in the predicate.
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).
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:
ID integer IDENTITY NOT NULL,
CONSTRAINT PK__dbo_Test_Div_ID
PRIMARY KEY CLUSTERED (Div, ID)
ON PS(Div)
-- Show the distribution of data
-- Seek on all 36 partitions
-- Static elimination = 1 hard-coded partition ID
-- Cached plan unlikely to be reused
-- Static elimination
-- Compilation overhead
-- Dynamic elimination with convert to char(3)
-- Reusable plan
t.Div = CONVERT(char(3), 'ABF');
-- 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)
t.Div = CONVERT(varchar(3), 'ABF');
-- char(4) means truncation could occur when
-- comparing with the char(3) partition function
-- No partition elimination, seek on 36 partitions
t.Div = CONVERT(char(4), 'ABF');
-- Clean up
DROP TABLE dbo.Test;
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.
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: email@example.com
© 2012 Paul White – All rights reserved
The humble Compute Scalar is one of the least well-understood of the execution plan operators, and usually the last place people look for query performance problems. It often appears in execution plans with a very low (or even zero) cost, which goes some way to explaining why people ignore it.
Some readers will already know that a Compute Scalar can contain a call to a user-defined function, and that any T-SQL function with a BEGIN…END block in its definition can have truly disastrous consequences for performance (see this post by Rob Farley for details). This post is not about those sorts of concerns.
The Books Online description of this operator is not very detailed:
This leads people to think that Compute Scalar behaves like the majority of other operators: as rows flow through it, the results of whatever computations the Compute Scalar contains are added to the stream. This is not generally true. Despite the name, Compute Scalar does not always compute anything, and does not always contain a single scalar value (it can be a vector, an alias, or even a Boolean predicate, for example). More often than not, a Compute Scalar simply defines an expression; the actual computation is deferred until something later in the execution plan needs the result.
Compute Scalars are not the only operators that can define expressions. You can find expression definitions with labels like [Expr1008] in many query plan operators, including Constant Scans, Stream Aggregates and even Inserts.
Deferred expression evaluation was introduced in SQL Server 2005 as a performance optimization. The idea is that the number of rows tends to decrease in later parts of the plan due to the effects of filtering and joining (reducing the number of expression evaluations at runtime). To be fair to the Books Online entry, it does mention this behaviour in a note:
The take away from this first section is that a Compute Scalar is most often just a placeholder in the execution plan. It defines an expression and assigns a label to it (e.g. [Expr1000]) but no calculations are performed at that point. The defined expression may be referenced by multiple operators later in the execution plan. This makes counting the number of 'executions' more complex than for a regular plan operator., and goes some way to explaining why Compute Scalar operators only ever show estimated row counts (even in an 'actual' execution plan).
The execution plans you see in Management Studio (or Plan Explorer) are a highly simplified representation that is nevertheless useful for many kinds of plan analysis. The XML form of show plan has a more detail than the graphical representation, but even that is a shallow depiction of the code that actually runs inside SQL Server when a query is executed. It is easy to be seduced into thinking that what we see as an 'execution plan' is more complete than it actually is. As a tool for high-level analysis, it is excellent, but do not make the mistake of taking it too literally. More detail on this later.
One more thing to appreciate before we get into a concrete example: the SQL Server engine contains a component known as the Expression Service. This is used by components such as the query optimizer, query execution, and the storage engine to perform computations, conversions and comparisons. It is the call to the expression service in the execution plan that can be deferred and performed by a plan operator other than the source Compute Scalar (or other expression-defining operator).
I came across a forum thread recently which demonstrated the concepts I want to explore in this post really well. The topic of discussion was delimited string-splitting (an old favourite of a topic, for sure) but I want to emphasise that the particular code is not at all important – it is the query plan execution I want to focus on. The particular string-splitting method employed was one I first saw written about by Brad Shultz; it replaces the delimiters with XML tags, and then uses XML shredding to return the results. I should say that I am not a fan of this technique because it is (a) a strange use of XML; and (b) it does not work for all possible inputs. Anyway, I said the example was not that important in itself, so let's get on to the first example:
@ItemID bigint,
@Item varchar(8000),
@Input varchar(8000);
SET @Input = REPLICATE('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', 32);
@ItemID = ROW_NUMBER() OVER (ORDER BY (SELECT NULL)),
@Item = x.i.value('./text()[1]', 'varchar(8000)')
'<r>' +
REPLACE(@Input, ',', '</r><r>') +
'</r>', 0
) AS ToXML (result)
CROSS APPLY ToXML.result.nodes('./r') AS x(i);
The code above creates a single comma-delimited string containing the letters of the alphabet, repeated 32 times (a total string length of 1632 characters). The string-splitting SELECT statement replaces the commas with XML tags, fixes up the start and end of the string, and then uses the nodes() XML method to perform the actual splitting. There is also a ROW_NUMBER call to number the elements returned in whatever order the nodes() method spits them out. Finally, two variables are used to 'eat' the output so returning results to the client does not affect execution time. The execution plan is as follows (click to enlarge):
The Constant Scan operator defines an expression labelled as [Expr1000] which performs the string replacement and conversion to the XML type. There are four subsequent references to this expression in the query plan:
The query takes 3753ms to execute on my laptop. This seems a rather long time to shred a single string containing just 801 elements.
The following code makes one small modification to the test one script:
'</r>' +
, 0)
The only difference in the execution plan is in the definition of [Expr1000] (click to enlarge):
This plan returns the same correct results as the first test, but it completes in 8ms (quite an improvement over 3753ms).
There is nothing in the query plan to explain why the second form of the query runs 500 times faster than the first. To see what is going on under the covers of the execution engine when executing the slow query, we can attach a debugger and look closer at the code SQL Server is really running. Using SQL Server 2012 and setting a breakpoint on the CXMLTypeProvider::ConvertStringToXMLForES method (as the name suggests, it converts a string to XML for the Expression Service) the first debugger break occurs with this stack trace:
I know that not everyone reading this post will routinely analyse stack traces, so for this first example I will describe the interesting calls from the bottom up (the currently executing code is on top, each line below is the method that called that routine):
The stack trace illustrates two things nicely:
Continuing execution with the debugger, the next break occurs when the Table-valued Function to the right of the filter is initialised:
Another break when the Table-valued Function on the lowest branch of the plan initialises:
And finally, a break from the Stream Aggregate, when it needs to evaluate [Expr1016] (which contains a reference to [Expr1000]):
The last two breaks (lowest table-valued function and stream aggregate) execute a total of 801 times. The reason for the slow performance of this query is now clear: [Expr1000] is being computed more than 1604 times. Yes, that means the REPLACE and CONVERT to XML really does run 1604 times on the same value – no wonder performance is so poor!
If you are inclined to test it, the expression service method that performs the REPLACE is sqlTsEs!BhReplaceBhStrStr. It turns out that the string REPLACE is very much faster than conversion to XML (remember XML is a LOB type and also has complex validation rules) so the dominant performance effect is the conversion to XML.
Running test two with the debugger attached reveals that only one call is made to CXMLTypeProvider::ConvertStringToXMLForES:
Reading down the stack trace we see that execution of the plan (as we know it) has not started yet. The call to convert the string to XML is called from InitForExecute() and SetupQueryScanAndExpression. The conversion to XML is evaluated once and cached in the execution context (CQueryExecContext::FillExprCache). Once the iterative part of plan execution begins, the cached result can be retrieved directly without calling ConvertStringToXMLForES() 1604 times.
Before you go off adding LEFT(@@DBTS, 0) to all your expressions (!) look what happens when we use a table to hold the input data rather than a variable:
@Item varchar(8000);
DECLARE @Table AS TABLE (Input varchar(8000) NOT NULL);
INSERT @Table (Input)
VALUES (REPLICATE('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', 32));
FROM @Table AS t
REPLACE(t.Input, ',', '</r><r>') +
Instead of the Constant Scan we saw when using a variable, we now have a table scan and a Compute Scalar that defines the expression:
[Expr1003] = Scalar Operator( CONVERT(xml,'<r>'+replace(@Table.[Input] as [t].[Input],',','</r><r>')+'</r>'+ substring(CONVERT_IMPLICIT(varchar(8),@@dbts,0),(1),(0)),0))
The other plan details are the same as before; the expression label [Expr1003] is still referenced by the Filter, two Table-valued functions and the Stream Aggregate. The test three query takes 3758ms to complete. Debugger analysis shows that CXMLTypeProvider::ConvertStringToXMLForES is again being called directly by the Filter, Table-valued Functions, and Stream Aggregate.
This final test replaces @@DBTS with the CRYPT_GEN_RANDOM function:
The execution plan shows an extra Compute Scalar next to the Table Scan:
[Expr1018] = Scalar Operator('<r>'+replace(@Table.[Input] as [t].[Input],',','</r><r>')+'</r>')
The Compute Scalar to the left of that is the same one seen previously, though it now references the new expression in its definition:
[Expr1003] = Scalar Operator( CONVERT(xml,[Expr1018]+ substring(CONVERT_IMPLICIT(varchar(8000),Crypt_Gen_Random((1)),0),(1),(0)),0))
The remainder of the query plan is unaffected; the same operators reference [Expr1003] as before. As you might have been expecting, this query executes in 8ms again.
In test one, there is nothing to stop the query processor deferring execution of the expression, which results in the same expensive computation being performed 1604 times (once each for the filter and first table-valued function, and 801 times each for the second function and the stream aggregate). As an interesting aside, notice that even with OPTION (RECOMPILE) specified, constant-folding only applies to the REPLACE and string concatenation; constant-folding cannot produce a LOB type (including XML).
In test two, we introduced the non-deterministic function @@DBTS. This is one of the functions (like RAND and GETDATE) that are implemented to always return the same value per query (despite being non-deterministic, see the links in the Further Reading section below for more details). These runtime constants are evaluated before the query starts processing rows and the result is cached. There are some hints (ConstExpr labels) in the execution plan that may indicate a runtime constant but I have not found this to be reliable.
In test three, we changed the game again by replacing the reference to a variable with a column reference from a table. The value of this column reference could change for each table row so the engine can no longer treat the expression as a runtime constant. As a consequence, the result is no longer cached and we see the same behaviour (and slow performance) as in test one.
In test four, we replaced the @@DBTS function with the side-effecting function CRYPT_GEN_RANDOM (the other such function is NEWID). One of the effects of this is to disable the deferred evaluation of the expression defined by the Compute Scalar. The result is a XML LOB and a second optimization occurs where handles to the same LOB (evaluated by the defining operator) can be shared by other operators that reference the LOB. This combination of effects means the expensive computation is only performed once in test four, even though the runtime constant caching mechanism is not used. By the way, there was a bug with CRYPT_GEN_RANDOM which meant it was incorrectly assessed by the optimizer in early versions of SQL Server 2008. If you encounter this issue when running the scripts above, apply a later service pack (or use the NEWID function for SQL Server 2005).
I would like to particularly thank Usman Butt and Chris Morris from SQL Server Central for their contributions and thoughts which helped me write this entry.
When a Function is indeed a Constant – Andrew Kelly Runtime Constant Functions – Conor Cunningham RAND() and other runtime constant functions – Conor again Scalar Operator Costing – Guess who
© 2012 Paul White twitter: @SQL_Kiwi email: email@example.com
Can DELETE operations cause pages to split? Yes. It sounds counter-intuitive on the face of it; deleting rows frees up space on a page, and page splitting occurs when a page needs additional space. Nevertheless, there are circumstances when deleting rows causes them to expand before they can be deleted. The mechanism at work here is row versioning (extract from Books Online below):
The relationship between row-versioning isolation levels (the first bullet point) and page splits is reasonably clear. Any data that existed before either of the isolation levels was enabled will need to have the 14 bytes added by future data modifications, perhaps causing pages to split. In this scenario, tables will likely contain a mix of records to start with, but over time (particularly as index maintenance is performed) the database will end up with row versions on most records, reducing the chances of a page split for that particular reason.
There is nevertheless a window of opportunity where adding the 14 bytes to an existing record could cause a page split. No doubt there's a recommendation out there somewhere to rebuild all tables and indexes when enabling or disabling a row-versioning isolation level on a database. This is not all that interesting though, so let's look at the second bullet point instead:
The documentation says that versioning information is added if the table has a trigger. What it doesn't say is:
SQL Server can still avoid adding the row-versioning information even where an enabled AFTER TRIGGER exists (the remainder of this post assumes that both row-versioning isolation levels are OFF, by the way).
To explore this behaviour in a bit of detail, we'll need a test rig:
IF OBJECT_ID(N'dbo.Test', N'U') IS NOT NULL
-- Test table
ID integer IDENTITY PRIMARY KEY,
Column01 nvarchar(20) NULL,
Column02 nvarchar(4000) NULL,
-- Add some rows
CONVERT(nvarchar(20), N'X')
CROSS JOIN sys.columns AS c3
-- A trigger that does nothing
CREATE TRIGGER trg
ON dbo.Test
-- Write any dirty pages to disk
-- Physical storage before any changes
FROM sys.dm_db_index_physical_stats(
DB_ID(), OBJECT_ID(N'dbo.Test', N'U'), NULL, NULL, 'DETAILED') AS ddips
ddips.index_level = 0;
-- Buffer pool pages before any changes
JOIN sys.allocation_units AS au
ON au.container_id = p.hobt_id
JOIN sys.dm_os_buffer_descriptors AS dobd ON
dobd.allocation_unit_id = au.allocation_unit_id
p.[object_id] = OBJECT_ID(N'dbo.Test', N'U')
-- Delete 1 in 10 rows
DELETE dbo.Test
[Page Splits] = COUNT_BIG(*)
FROM sys.fn_dblog(NULL,NULL) AS fd
fd.[Transaction Name] = N'SplitPage';
-- Ensure ghosted records are processed so
-- we see accurate per-page row counts
-- Physical storage after the delete operation
-- Buffer pool pages after the delete operation
--DBCC PAGE (tempdb, 1, 4720, 3);
The script performs the following actions:
Typical output:
There are 235 data pages with a maximum physical record size of 17 bytes before and after the delete. Before the delete, each data page contains 426 rows with 2 bytes of free space. After the DELETE:
No surprises there.
Now, run the script again with the only change being that Column01 is defined as nvarchar(22) instead of nvarchar(20). The before picture is the same as before, but the situation after the DELETE is very different:
There have been 234 page splits, increasing the data page count from 235 pages to 469 pages, and halving the number of rows on each data page. The number of reads reported has also blown out from 237 previously to 2342 logical reads in this run (a factor of ten worse).
The cause of the page splitting is that the deleted records must be versioned. SQL Server 2005 and later uses the version store to build the inserted and deleted pseudo-tables used by AFTER triggers. Where the data has no pre-existing versioning data, adding the 14 bytes will result in a clustered index page split if the page contains insufficient free space to accommodate this expansion.
Temporarily turning off ghost record clean-up using global trace flag 661 and examining an affected data page using DBCC PAGE shows the following (remember to turn the trace flag off afterward if you try this):
Slots 8 and 10 on this page hold records that were unaffected by the DELETE; the physical row length is 17 bytes as displayed previously. The record that was in slot 9 has been deleted. It is a ghost record with versioning information added. The record size is 17 + 14 = 31 bytes, and this expansion with only 2 bytes of free space on the page caused it to split.
This explains why the nvarchar(22) DELETE test caused page splitting, but why didn't the original nvarchar(20) script behave the same?
There is a performance optimization that can avoid adding row versioning information, but only if the table cannot generate ROW_OVERFLOW or LOB allocation units. This means that the definition of the table must not allow for LOBs or for the possibility of variable length columns moving off row. The actual size of the data stored is immaterial – it is the potential size that matters.
In our test, the nvarchar(22) column definition caused the maximum possible INROW size to just exceed the 8060 byte limit. (The exact INROW limit also depends on the table definition; marking one of the data columns SPARSE would reduce the limit to 8015-8019 bytes – whatever the right number is).
"Page splitting only occurs in index structures, are heap structured tables affected by this issue too?"
It is true that heap pages do not split, but when a heap row needs to expand, the engine will move the row to another page if insufficient free space exists on the current page. When the storage engine does this, it leaves a forward pointer behind to avoid updating all non-clustered indexes to reflect the new physical row locator.
For a heap table with an active AFTER trigger, and a LOB column (or the possibility of row-overflow) the row has to be versioned and ghosted. If the page contains insufficient free space to accommodate the versioning, the row moves to another page leaving a forwarding stub behind. This results in a forwarded ghost record. Ghost clean-up will normally remove this record pretty quickly, so we will need to disable that process temporarily. The following script creates the very special circumstances necessary to produce a forwarded ghost record this way (note this script is for test systems only should not be run in tempdb):
-- Heap test
ID integer IDENTITY PRIMARY KEY NONCLUSTERED,
Column01 nvarchar(16) NULL,
Column02 nvarchar(4000) NULL
-- Add some all-NULL rows
-- Ensure rows are tightly packed
ALTER TABLE dbo.Test REBUILD;
ddips.alloc_unit_type_desc = N'IN_ROW_DATA'
AND ddips.index_level = 0;
AND dobd.page_type = N'DATA_PAGE'
-- Disable ghost clean-up
-- Delete three records on the same page
AND dobd.is_modified = 1
-- View the appropriate page
-- Enable ghost clean-up
Example output, showing page 453648 receiving a versioned forwarded ghost record (click to enlarge in a new tab):
Partial DBCC PAGE output for the highlighted page:
If you ever wonder why your deletes are so slow, it is worth checking to see if you are suffering from page splitting due to an enabled trigger and a table definition that allows for LOB allocations or ROW_OVERFLOW. Any table with a LOB column (including the max data types) qualifies, as does one with even a surprisingly small number of variable-length columns, as shown in the examples in this post. This is a great reason to avoid using 'max' or old-style LOB data types unnecessarily, and to be careful about the maximum length of 'normal' variable-length data types too. Remember, it is the potential maximum row size that is important, not the actual row size.
On a related note, remember that deletes on a heap can only deallocate empty pages if a table lock is acquired? A table definition that allows for LOB or ROW_OVERFLOW prevents that optimization too. So, if your heaps are growing despite DELETE WITH (TABLOCKX), check the maximum possible row length! You could also convert them to clustered tables as well, of course, but that's a quite different debate.
I would like to acknowledge and thank SQL Server MVP Dmitri V. Korotkevitch who first brought the basic issue to my attention with UPDATE queries. I would strongly encourage you to also read his blog entry showing how this behaviour also affects UPDATE queries, resulting in slow performance and excessive fragmentation.
Thanks for reading.
© 2012 Paul White Twitter: @SQL_Kiwi Email: email@example.com
SQL Server 2005 onward caches temporary tables and table variables referenced in stored procedures for reuse, reducing contention on tempdb allocation structures and catalogue tables. A number of things can prevent this caching (none of which are allowed when working with table variables):
Temporary objects are often created and destroyed at a high rate in production systems, so caching temporary objects can be an important optimization. The temporary object cache is just another SQL Server cache (using the general framework) though it's entries are a bit more visible than most. The sys.dm_os_performance_counters DMV exposes a number of counters under the 'Temporary Tables & Table Variables' instance of the Plan Cache object. The cache is also visible through the usual cache DMVs, for example as CACHESTORE_TEMPTABLES in sys.dm_os_memory_cache_counters.
The cached objects themselves are visible in tempdb.sys.tables, named with a single # character followed by the 8-character hexadecimal representation of the object id. This is different from the names of ordinary temporary tables, which have the user-supplied name followed by a bunch of underscores and an id.
The following procedure shows a total of nine cache objects created using CREATE TABLE #xyz syntax, table variables, and SELECT…INTO:
CREATE PROCEDURE dbo.Demo
CREATE TABLE #T1 (dummy int NULL);
CREATE TABLE #T2 (dummy int NULL);
CREATE TABLE #T3 (dummy int NULL);
DECLARE @T1 AS TABLE (dummy int NULL);
DECLARE @T2 AS TABLE (dummy int NULL);
DECLARE @T3 AS TABLE (dummy int NULL);
EXECUTE dbo.Demo;
FROM tempdb.sys.tables AS t
t.name LIKE N'#[0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f][0-9a-f]';
The results show nine separate cached objects:
Notice the relationship between object id and the name e.g. –1383692523 = hex AD868715.
If any of the temporary objects in a procedure are not cacheable for any reason, the others may still be cached. So, for example, if we modify the test above to create an index on table #T5, that particular table will not be cached, but the other temporary objects will be:
-- Prevents caching of #T5
CREATE INDEX nc1 ON #T5 (dummy);
There are now only eight cached objects:
Dropping a temporary table in a procedure does not count as DDL, and neither does TRUNCATE TABLE, nor UPDATE STATISTICS. None of these things prevent temporary table caching (so it does not matter whether you explicitly drop a temporary table at the end of a procedure or not).
-- Does not prevent caching
There are nine cached objects again:
If a stored procedure is executed concurrently, multiple separate cached objects may be created in tempdb. There is one cached plan for the procedure but one cached temporary object per execution context derived from that cached plan. Recall that execution contexts are relatively lightweight instances of a cached plan, populated with execution-specific data such as temporary object ids and parameter values (image reproduced from the plan caching white paper):
The runtime contents of a temporary object (table or variable) are obviously specific to a particular execution, so it makes sense for the cached object to be associated with execution contexts rather than the parent plan. There may also be more than one cached plan for a procedure in cache (for example due to compilations with different SET options) and each parent plan will have its own collection of execution contexts, so there can be one cached tempdb object per execution context per plan.
There does not appear to be a fixed limit on the number of these cached objects; I was able to quickly create 2,000 of them using the test procedures above and Adam Machanic's SQL Query Stress tool running 200 threads. This is the reason for the 1 second delay in the procedure – to make sure the procedure runs for a little while so new execution contexts are generated for each execution rather than reused. The contents of tempdb after that test were as follows:
Any auto-stats created are linked to the cached temporary table:
DECLARE @dummy int;
-- Trigger auto-stats
SELECT @dummy = dummy
WHERE dummy > 0;
JOIN tempdb.sys.stats AS s ON
s.[object_id] = t.[object_id];
In the case of multiple execution contexts, you might be wondering if each of the tempdb objects can have auto-created statistics associated with them. The answer is no: auto-stats are used to compile the parent plan, and execution contexts are derived from that same plan as needed. The metadata looks a little odd though; the statistics are explicitly linked to the object id of the cached temporary object that caused the auto-stats to be created. Other cached tables for the same plan have different ids, and so do not link to the sys.stats entry.
Statistics created using an explicit CREATE STATISTICS statement are not linked to a cached temporary object, for the simple reason that CREATE STATISTICS is considered DDL, and prevents caching from occurring in the first place.
The first time a procedure containing a cacheable temporary object is executed, the temporary object is created as normal, then renamed to the hexadecimal internal form described previously when the object is dropped (explicitly or implicitly at the end of the procedure). On subsequent executions, the cached object is renamed to the normal user-visible name when 'created' in the procedure, and renamed back to the internal form when it is 'dropped'. The following script demonstrates the creation and renaming of cached temporary objects:
CREATE TABLE #Demo (i int);
FROM sys.tables AS t
t.name LIKE N'#Demo%';
DROP TABLE #Demo;
t.name LIKE N'#________';
fd.[Current LSN],
fd.[Transaction Name],
fd.[Transaction ID],
CONVERT(sysname, SUBSTRING(fd.[RowLog Contents 0], 3, 256)),
CONVERT(sysname, SUBSTRING(fd.[RowLog Contents 1], 3, 256))
FROM sys.fn_dblog(NULL, NULL) AS fd;
The first time it is run the first part of the output is:
Notice that the object ids are the same, and the object has familiar external name while in scope, but is renamed after the DROP TABLE statement. The transaction log entries displayed are (click to enlarge):
The highlighted section shows the table being renamed in the internal catalogue tables from the user-visible name to the internal name. On the second run, there is an extra renaming log entry in the CREATE TABLE system transaction, as the object is renamed from the internal form to the user-visible name:
The demonstration shows that CREATE TABLE and DROP TABLE for a cached temporary object are replaced by renaming operations.
The cached object is scoped to the query plan that references it. If the plan is evicted from cache for any reason (perhaps by ALTER or DROP PROCEDURE or an explicit DBCC FREEPROCCACHE command) a background thread removes the tempdb object. This is not synchronous to the command that causes the eviction; the delay seems to be 5 seconds or less on current SQL Server versions, and is performed by a system process id. The following code shows the link between the cached temporary table and the cached plans for the stored procedure: