I received a question from a friend in Brazil related to foreign keys and join elimination in SQL Server. Yes, SQL Server can detect that some joins are not needed to return results to the user and skip them. What is this evil magic, you ask? Well, let’s walk through it before we get out our torches and pitchforks…
What’s a Foreign Key? To most users, it is something that throws errors and blocks you from inserting data where you want it. However, to SQL Server, it is a glorious thing! It lets the Query Optimizer know that the data in one table absolutely correlates to the data in another table. (So, if I have a Customers table and an Orders table, a Foreign Key from Orders to Customers tells me that every Order has a Customer). Now, when one queries the join of Orders and Customers, it might be that you only really need columns from the Orders table. Now we’re in business – the Optimizer can detect this and see that the result of the query is the same if we just skip all of the work of doing random IO lookups into the Primary Key index on Customers to make sure that they are there.
So, you should think of Foreign Keys as a great way to give the Optimizer hints to speed up your query, in most cases. The only cases where I recommend that customers NOT define Foreign Keys is in very large data warehouses (which I will save for another blog post).
So, the question from my Brazillian friend is why we DO the elimination for single-column Foreign Keys and not for multi-column cases.
(I will post the mail I got from him here – so, his example + comments)
1:
2: IF OBJECT_ID('Tab2') IS NOT NULL
3: BEGIN
4: DROP TABLE Tab2
5: END
6: IF OBJECT_ID('Tab1') IS NOT NULL
7: BEGIN
8: DROP TABLE Tab1
9: END
10: GO
11: CREATE TABLE Tab1 (Tab1_Col1 Integer NOT NULL PRIMARY KEY, Tab1_Col2 Char(200))
12: CREATE TABLE Tab2 (Tab2_Col1 Integer NOT NULL PRIMARY KEY, Tab1_Col1 Integer NOT NULL, Tab2_Col2 Char(200))
13: ALTER TABLE Tab2 ADD CONSTRAINT fk FOREIGN KEY (Tab1_Col1) REFERENCES Tab1(Tab1_Col1)
14: GO
15:
16: -- Fine, the execution plan not use Tab1
17: SELECT Tab2.*
18: FROM Tab2
19: INNER JOIN Tab1
20: ON Tab1.Tab1_Col1 = Tab2.Tab1_Col1
21: --|--Clustered Index Scan(OBJECT:([dbo].[Tab2].[PK__Tab2__993AF6027FB886E3]))
22:
23: GO
24:
25: IF OBJECT_ID('Tab2') IS NOT NULL
26: BEGIN
27: DROP TABLE Tab2
28: END
29: IF OBJECT_ID('Tab1') IS NOT NULL
30: BEGIN
31: DROP TABLE Tab1
32: END
33: GO
34: CREATE TABLE Tab1 (Tab1_Col1 Integer NOT NULL, Tab1_Col2 Integer NOT NULL, Tab1_Col3 Char(200), PRIMARY KEY(Tab1_Col1, Tab1_Col2))
35: CREATE TABLE Tab2 (Tab2_Col1 Integer NOT NULL PRIMARY KEY, Tab1_Col1 Integer NOT NULL, Tab1_Col2 Integer NOT NULL, Tab2_Col2 Char(200))
36: ALTER TABLE Tab2 ADD CONSTRAINT fk FOREIGN KEY (Tab1_Col1, Tab1_Col2) REFERENCES Tab1(Tab1_Col1, Tab1_Col2)
37: CREATE INDEX ix ON Tab2(Tab1_Col1, Tab1_Col2)
38: GO
39:
40: -- Why not use the same behavior above ? Just because the multi column foreign key?
41: SELECT Tab2.*
42: FROM Tab2
43: INNER JOIN Tab1
44: ON Tab1.Tab1_Col1 = Tab2.Tab1_Col1
45: AND Tab1.Tab1_Col2 = Tab2.Tab1_Col2
46: --|--Nested Loops(Inner Join, OUTER REFERENCES:([dbo].[Tab2].[Tab1_Col1], [dbo].[Tab2].[Tab1_Col2]))
47: -- |--Clustered Index Scan(OBJECT:([dbo].[Tab2].[PK__Tab2__993AF602084DCCE4]))
48: -- |--Clustered Index Seek(OBJECT:([dbo].[Tab1].[PK__Tab1__6D1AC6A2047D3C00]), SEEK:([dbo].[Tab1].[Tab1_Col1]=[dbo].[Tab2].[Tab1_Col1] AND [dbo].[Tab1].[Tab1_Col2]=[dbo].[Tab2].[Tab1_Col2]) ORDERED FORWARD)
49:
50: -- Why not apply the predicate at Tab1.Tab1.Col2 too? We have the trusted foreing key to be able to do that.
51: -- If we do it, in that case we could use the PK of Tab1 and the Index ix of Tab2 just filtering by Tab1_Col1(JOIN) and Tab1_Col2(WHERE)
52: SELECT Tab2.*
53: FROM Tab2
54: INNER JOIN Tab1
55: ON Tab1.Tab1_Col1 = Tab2.Tab1_Col1
56: WHERE Tab2.Tab1_Col2 = 10
57: --|--Nested Loops(Inner Join, OUTER REFERENCES:([dbo].[Tab2].[Tab1_Col1]))
58: -- |--Clustered Index Scan(OBJECT:([dbo].[Tab2].[PK__Tab2__993AF602084DCCE4]), WHERE:([dbo].[Tab2].[Tab1_Col2]=(10)))
59: -- |--Clustered Index Seek(OBJECT:([dbo].[Tab1].[PK__Tab1__6D1AC6A2047D3C00]), SEEK:([dbo].[Tab1].[Tab1_Col1]=[dbo].[Tab2].[Tab1_Col1]) ORDERED FORWARD)
Before I answer, let me just say that I love getting questions like this – it shows that people really do like to deeply understand the engine and use what we put in it to its fullest.
So, the answer is that we did the single-column case many years ago since most FKs are single-column. We haven’t seen enough cases where the multi-column FK is used to make it more important than all of the other things that we’ve been requested to add to the product. I wish the answer had more intrigue, but it’s just a case where we have lots and lots of things to code and we haven’t had time to do this one yet. The technical side of me obviously wishes we had all of these things coded into the product. The other way to look at it is that people are upset if query compilation takes too long, so we have to find a balance between what is mathematically possible and what is useful to the broadest set of customers.
If we do find that this kind of construct becomes more common, we would likely go and add this support for a future release of the product.
For the last example, predicate duplication across multi-column joins is another one of these cases where it is possible to do but does not show up as being the dominant factor in queries often enough to enable by default.
One last note – we also do not do FK join elimination on tempdb, even if you have a FK defined.
Happy Querying!
Conor Cunningham
(Not a SQL Server post)
I have been meaning to install Windows 7, and I got around to doing it last night. I usually run Windows 2003/8 Server for work, so my interest in the consumer side is perhaps not as high as some others. Nevertheless, I like Windows and I wanted to try it out.
I did not try to upgrade from Vista x64. I just bought a new hard drive and figured it was time to do a clean install – funnily, a SQL Server setup issue has prevented me from installing SQL Server on my personal machine, so I wanted that fixed. An upgrade would copy the broken registry files. (I’ve knocked on a few doors about this while up in Redmond – this is an area where we need to do better in SQL).
Impressions:
Setup: I had one hiccup last night during installation. It stopped about 9-10% through Expanding files and returned some error about not being able to read something or other and was aborting the install. So, I tried again and it seemed to make it further the second time. Within about 30 minutes or so and after a few reboots, I had a Windows 7 logon screen.
Aero Shake: Very cool. I was opening up windows left and right and just love this. It is neat.
Aero Peek: This one is interesting, but I am not sure yet whether I like it. If you hover your mouse in the lower right part of the screen (to the right of the clock in the taskbar), it will make all of your windows translucent and you can see your background. While nice for looking at the background, it doesn’t accomplish as much organizationally as I want. There are a few very cool tools that help you find the right window (Switcher), and I can see myself using something like that more often than Aero Peek.
I guess these two features replace the “Show Desktop” taskbar button from Vista, which minimized all of the active windows and gave you a clean screen. I think that the Shake is a nice addition (close all but this one) but I often want to minimize everything and then go to the start menu to start a new program. This use case isn’t handled, so I will be looking for a Windows 7 Show Desktop button for my workflow.
Start Menu: This is a sore topic for me. I am pretty old school in my use of the start menu – I keep the “Classic” start menu with the smallest text/icons possible. I really like it to be small, fast, and efficient. The newer start menu leaves me staring at the thing trying to figure out where everything is and what designers were thinking by putting this thing in this place. Unfortunately, the Start Menu in Windows 7 doesn’t let me configure things like my Windows 2008 machines, and I don’t like having to switch back and forth. (Note to Windows designers: That does NOT mean I want Win2k8 to look like Win7). Now, if I accept that the “new” start menu is good and give it a try, there are a few things that are reasonable about it:
1. open it up and type “cmd” – immediately opens a command window. good. It is the most important thing I have to do, and it seems that each release people try to move it further and further down the tree of commands
2. Find a program to open. I actually had to sit there for a minute or two looking. The right side has no All Programs. I eventually found it on the left side. So, I have to click yet another thing to get to my programs. Conor not happy.
Taskbar: This is interesting. I think that the prior model of “everyone needs a little flag down near the clock” was getting to be pretty horrible. I actually never want to see most of them. This new model seems to force everything into the taskbar and makes the taskbar more powerful with icons and stacking and such. I think that this may be a big long-term win. When combined with the window thumbnail support (an overlooked gem in Vista, IMO), I think that this gets me a mechanism to navigate through my open windows fairly effectively. I am going to have to play with this more to see if I can master it.
I got as far as installing Office, Windows Live, and Visual Studio 2008 last night. They all installed just fine, fwiw.
I am enjoying watching the Apple commercials get more and more desperate each round.
I’m a PC!
Conor
I gave a talk to the Austin-area PASS group last night on B-Tree indexing in SQL Server, and I received a question about whether to make clustered indexes UNIQUE or not (assuming the data is unique on the key columns). The expectation was that this should perform better when the index was UNIQUE.
Let’s back up a minute and see things from the perspective of the Query Processor. Someone comes in and creates an index on col1 of table1. They don’t make it UNIQUE but they put data in the column that is unique. Then you compile the query “SELECT DISTINCT col1 from Table1”. The QP generates a plan that remains valid even if other data is inserted while that plan is in the procedure cache. So, it can’t assume anything about the uniqueness of that column because you could come in and insert a value that is non-unique. If, on the other hand, you created a UNIQUE constraint/index, then things are very different! Since the generated plan is valid as long as the schema definition for the table remains the same, the QP knows that the definition of the table precludes any duplicate values from being inserted. So, it can generate a plan that doesn’t bother to do any grouping (DISTINCT is implemented using the a group by operator in SQL). Go ahead and try it – you’ll see the plan difference.
In my view, this is really more of a question about your data model – if you know something is distinct, you can get the system to enforce this rule for you and make sure that your application behaves correctly. So, when defining your tables, you should have a holistic view of how the tables relate to each other so that you can identify where you should or should not have constraints (or indexes – however you want to define them).
One case where I see customers sometimes explicitly avoiding the definition of constraints is in data warehouses. If your data is read-only and you already “know” that your data is unique, you may want to skip the space overhead or time overhead of having indexes to enforce these constraints. Now, you still have the issue with the Optimizer not being able to do fancy query rewrites based on uniqueness, but your average data warehouse query is often expensive and rarely do these kinds of rewrites apply in any meaningful way that would impact query performance (other factors dominate).
Happy Querying!
Conor
As most of you have figured out by now, I work mostly on queries :). One of the things that I often need to do is to get a statement out of a batch so that I can go look more closely at a query plan (and, in my case, the code that generates it).
I use the a query like this to read through a few DMVs and emit the text for the plan I want:
select statement_start_offset, statement_end_offset, statement_text from (
SELECT
SUBSTRING(st.text, (qs.statement_start_offset/2)+1,
((CASE qs.statement_end_offset
WHEN -1 THEN DATALENGTH(st.text)
ELSE qs.statement_end_offset
END - qs.statement_start_offset)/2) + 1)statement_text,
*
FROM sys.dm_exec_query_stats qs
CROSS APPLY sys.dm_exec_sql_text(qs.sql_handle) st) a
ORDER BY statement_text, statement_start_offset
A few notes:
1. SQL 2005 and SQL 2008 sometimes show –1 for the end offset instead of computing the real offset.
2. the offsets are actually byte offsets within a UTF-16 string (so, since SQL Server doesn’t do anything special for the fancy > 2 byte characters, this just means that you divide the offsets by 2 to find the character offsets)
Now, the DMVs were initially intended as debugging tools. While they are very useful, they have become quite a bit more popular than I had originally intended (I built much of the internal framework for what became DMVs, but I didn’t build these specific DMVs). I was talking with a few of the other developers, and we were curious how people thought about this –1 end offset business. The original intent was that these DMVs should be able to change each release, but I’d expect that people could have dependencies on nuances like this in the DMVs. If you have thoughts on this, please feel free to mail them to me at (conorc (at) microsoft (dot) com).
Happy Querying!
Conor
It’s been a busy summer. I got back from vacation and have been hard at work on new features for a future version of SQL Server. You can always still send me questions about the existing product, of course, and I will answer them here (conorc (at) microsoft (dot) com).
Today is a question that one of the MVPs asked – How do I find out if a statistics object was created with the “don’t recompute” flag? Initially, I tried dbcc show_statistics, but it isn’t stored within the statistics blob itself and doesn’t show up there. Instead, you need to look at sys.stats (2005 and above):
1: use tempdb
2: go
3: create table t1(col1 int)
4: insert into t1(col1) values (1)
5: insert into t1(col1) values (2)
6: go
7: create statistics s1 on t1(col1)
8: create statistics s2 on t1(col1) with norecompute
9: go
Which yields:
name no_recompute
------------------------
s1 0
s2 1
(2 row(s) affected)
Funnily enough, the internal build on which I first tried this had a bug and did not ever return 1… It had already been fixed, but I had not installed that build on my machine. I spent an hour trying to grok the metadata code and figure out what had gone wrong :).
Now, the auto-stats logic in SQL Server is generally good for the vast majority of our customers. It updates statistics when the data has changed, causing plans referencing those statistics to recompile when they are next used. This works great – so, why would I not want that???
Well, there could be a few cases where you want to override the default behavior of the system. Perhaps you find that your application is heavily dependent on avoiding too many recompiles in the middle of the day (recompiles take CPU resources). If you wanted all statistics to not recompute, you can just change the database-level flag for auto-update stats. However, if you want to change only specific statistics, this norecompute flag is the way to do so. Usually, I would only recommend doing something like this if you know what you are doing and have a specific reason to change this, as you would want to pair something like norecompute with your own custome stats update job that runs at night, for example.
I hope that gives you some insight into why this flag is there.
Happy Querying!
Conor
I received a question from a customer today about query plan choice for a parameterized query - specifically that different plans get picked based on where the plan is located, and sometimes one might be better than another. Apparently, for their application, a particular query plan was “better” when compiled in dynamic sql instead of a stored procedure. Others say that query plans are just as fine when compiled within a stored procedure. Which is it?
(If I were still consulting, the answer to this is “it depends” ;))
There are a lot of things necessary to answer this question, as it really isn’t about the exact location, at least not as such. It has more to do with the way different batches/procedures are compiled and also about how parameters are sniffed during plan compilation.
Let’s start at the beginning: The model for T-SQL (the procedural part of the programming surface area) is compiled in batches in SQL Server. This means that if you submit a batch of 5 queries, SQL Server will generally try to compile them all before executing any of them. (There are exceptions)
Now, let’s mix things like "set @p=5” in that query batch, and let’s have a later query reference that parameter. In this example, the whole batch is “compiled” before it is “executed”. That means that the “set @p=5” does not actually set @p=5 until that statement is executed. That means that the later query that references that parameter will sniff a NULL instead of a 5.
I wrote about the basics of this issue a few years ago in the QO team blog:
I Smell a Parameter!
So, back to our question – which one is “better”. The answer is that this problem is about scopes and not procedures vs. dynamic sql. Basically, putting the parameterized query within a nested scope (dynamic sql or another procedure) happens to impact whether the parameter gets sniffed or not. It’s the sniffing that impacts the plan choice, not from where it is hosted in T-SQL.
Now, why did the plan become “good” or “bad”:
* Sometimes when you sniff a NULL, you get a perfectly reasonable plan (if NULL is represented in similar proportions to other possible values).
* Sometimes if you sniff a NULL, you can get an absolutely horrible plan.
Generally, you want to get the Optimizer to see a good average value for your parameterized queries so that it will put a plan that works well, on average, for the average parameter case. If you never call the procedure with NULL for a parameter AND it generates a different plan than if you had compiled it with an actual value you would use, then you probably want to look at that and see how to get it to sniff a more common value – you want to get that Optimizer working for _you_ and not for that dreaded NULL :).
So, we’re done, right? Unfortunately no – it gets more complex again. There are some cases where one plan may not perform great for all parameter values (so, there is either not a good average value or there is otherwise some large performance difference based on the parameter value for the “best” plan). Let’s say that you are querying some big table for the “USA” table during the day and the “Togo” (a small island nation) data at night. These plans may be very different because their filter’s selectivities will be different. We refer to this as a plan with parameter-sensitivity.
For these parameter sensitive plans, you can also see “good” vs. ”bad” performance. By that, the performance differs, perhaps even by a lot, based on the parameter value. If you have cases like this, you have a few options.
So, there are a few different ways you can see “good” vs. “bad” plans for parameterized queries. Let’s talk about some practical guidance for how to avoid these issues.
First, you can move things to a new scope – that’s what happens when you move to dynamic sql. This likely gets the parameter sniffed and almost always will give you a good plan (at least for that parameter value). Another option is to just use an OPTIMIZE FOR hint to pass a common value to be sniffed – this is a great way to not have to worry about whether the batch compiles before it executes, etc. Another option is to use OPTION(RECOMPILE). If you have a parameter-sensitive case where sniffing the value does not work well, then you will want to consider OPTION(RECOMPILE) – when the compilation cost is smaller than the performance difference from using a suboptimal plan for the wrong parameter value, then it is a very good idea.
I’ve given you the short version :) There are some additional details around “deferred compilation” where a batch is only partially compiled before parts of it gets executed. SQL 2005+ also has statement-level recompile, an this can change the sniffing logic as well. I am not trying to give you a complete answer other than to give you the tools to ask the right questions – this stuff is tricky!
Happy Querying!
Conor Cunningham
Architect, SQL Server QP
Thanks to those of you who replied to my previous post. I spent the last week or so talking with customers, coworkers, and looking at various applications to see how recompiles are modeled today in their applications. At a high level, SQL Server doesn’t really “require” you to recompile at all. The main set of people who seemed to think about this were people having trouble with plan selection. For example, if statistics were not updated frequently enough and users were querying new data on a time-series column, this could cause the automatic algorithm to not work well until statistics were updated on the queried column. So, this is usually a more advanced topic for DBAs to consider.
As you might expect, customers who do this usually manage a somewhat larger database or set of databases. Sometimes it is an application where there are very precise performance requirements and the queries are relatively small (for example, a query that is usually a “seek” against a table instead of a scan). When the query plan selected is a scan, the query performs much more slowly than the seek plan.
In terms of frequency of mechanism, this seemed to be all over the place – people use sp_recompile, freeproccache, and update statistics for different kinds of problems. I think update statistics has an edge since it usually addresses the problems that can be fixed with a recompile, but others would do freeproccache or sp_recompile as well.
I will convey a small fact to you about sp_recompile that you may not know. Internally, SQL Server has a timestamp that is used to determine whether plans in the procedure cache are still valid – as long as the timestamp on the referenced object is the same the current timestamp in the metadata for that object, the plan is “valid”. sp_recompile works by updating that metadata timestamp for the object passed as an argument to sp_recompile. So, you are effectively making a metadata change by doing an sp_recompile. DBCC FREEPROCCACHE will drop objects from the cache without a metadata change. update statistics works on a different, secondary metadata version with slightly different semantics.
So, if I had to make a recommendation to you, I’d say to just consider whether you need to use sp_recompile or not – it is somewhat more heavyweight than the other approaches. None of them are invalid, of course, but you might find that it is a bigger hammer than you need if you want to fix one query with a plan that is not what you want. Note that DBCC FREEPROCCACHE takes arguments, and you can limit what is evicted so that you can reduce recompile load to the subset you desire.
Happy Querying (and Memorial Day, for those of you in the USA)!
Conor
I have a question for you guys about how do you force a recompile for a single query today?
There are a lots of different ways that one could cause the system to recompile a query:
a) sp_recompile <object used in a query>
b)DBCC FREEPROCCACHE (with optional arguments to restrict the set of impacted queries)
c) detach/attach db (2008+), restart server, etc.
d) use a lot of memory to force plans out of memory
e) update statistics
f) change the text of the query (add a space), which works mostly except for trivial plans (which you may not care about recompiling anyways)
I am curious what other ways people use (or what you use most frequently). If you have any interesting scenarios about how/why you recompile a plan, I’d like to hear about them, so please send them my way (conorc @ microsoft.com)
If you never have occasion to recompile queries or think it’s not useful, that’s fine too – I want to hear about those cases as well.
If there are some interesting cases, I’ll post them up anonymously if you don’t mind.
Thanks,
Conor
I received a question this week about whether filtered statistics update as frequently as regular statistics. The right way to ask the question is “Do filtered statistics become invalid as frequently as regular statistics?”, as stats are recomputed based on the queries that consume them, while stats are invalidated based on changes to the underlying data.
The basic mechanism for stats invalidation is a per-column counter in the storage engine. It’s not transacted, and it is incremented on each INSERT/UPDATE/DELETE/MERGE. When a normal statistics object is created, the current “modcounter” for that column is stored in the statistics object. As changes are made to the table, the difference between the current modcounter and the one stored in the statistics object becomes greater. Ultimately, when the difference is large enough (I will slightly oversimplify and say that it is 20% of the table changed for this blog post), the statistics object is invalidated. When a query consuming the statistic is executed again, it will determine that the statistic is out-of-date and recompile it. Once done, the query is recompiled using the new statistics object. Unfortunately, many of the details of this logic are not exposed, and this can make it somewhat difficult to understand the mechanism.
Filtered statistics do not change the fundamental mechanism – there is still one set of counters in the storage engine. The thresholds for when filtered statistics become invalid, however, are modified from the normal case based on the estimated selectivity of the filter. So, a filter that only covers 20% of the domain is updated 1/5th as frequently. The calculation is done without knowledge to whether the changes being made to the table would actually cause the statistic object to be changed.
I’ve written up an example to show that filtered stats do indeed get updated even when all of the changes to the data are outside of the range of the filter on the statistics object. In this example, the filter selectivity is very high (~90%), and the “data change” is effectively not really changing the data, but I know that it is impacting the modcounter for the column.
1: use tempdb
2:
3: --drop table testfilteredstatsrefresh
4: -- create a table for our example with values 0...999 in col2
5: create table testfilteredstatsrefresh(col1 int identity, col2 int)
6: go
7: set nocount on
8: begin transaction
9: declare @a int=0
10: while @a < 20000
11: begin
12: insert into testfilteredstatsrefresh(col2) values (@a % 1000)
13: set @a+=1
14: end
15: commit transaction
16: go
17: -- create filtered stats over a portion of the domain
18: create statistics i1 on testfilteredstatsrefresh(col2) WHERE col2 > 100
19: go
20: select * from testfilteredstatsrefresh where col2 <> 55 option(recompile)
21: go
22: set nocount off
23: -- update the table with a series of no-ops on the section of the range
24: -- not covered by the filtered stats
25: update testfilteredstatsrefresh set col2=col2 %1000 where col2<100
26: update testfilteredstatsrefresh set col2=col2 %1000 where col2<100
27: update testfilteredstatsrefresh set col2=col2 %1000 where col2<100
28: update testfilteredstatsrefresh set col2=col2 %1000 where col2<100
29: update testfilteredstatsrefresh set col2=col2 %1000 where col2<100
30: go
31: -- run the query again - auto-stats fires again
32: -- so,
33: select * from testfilteredstatsrefresh where col2 <> 55 option(recompile)
34:
I turned on sql profiler and captured the “auto stats” event to watch when it is recompiled. You will notice that this happens on the last query (after the changes), even though there have been no changes in the part of the domain covered by the filtered statistics object.
Happy Querying!
Conor
For those of you waiting for the new "Inside SQL Server" book, it is actually out now. Kalen decided to give it a name change, and the actual title is "SQL Server 2008 Internals". I've written a chapter on how the Query Optimizer works. It is currently #1 in the 3 related database/sql server categories on Amazon, so I'll say "thank you" to those who have already ordered a copy ;). Like my blog postings, there are a lot of sample scripts you can try so that you can "see" what the optimizer is doing - I find this technique to be a very good way to learn what is happening, and I hope it works for you.
http://www.amazon.com/Microsoft%C2%AE-SQL-Server%C2%AE-2008-Internals/dp/0735626243/ref=pd_bbs_sr_1?ie=UTF8&s=books&qid=1237753244&sr=8-1
Enjoy!
Conor Cunningham
A customer recently asked our support organization about an unexplained series of range locks that they were seeing on a DELETE to a table with a foreign key.
Here is the repro:
1: create table Foo (FooId int not null primary key)
2: create table Bar (FooId int not null, BarId int not null)
3:
4: alter table Bar
5: add constraint PK_Bar
6: primary key (FooId, BarId)
7:
8: alter table Bar
9: add constraint FK_Bar_Foo
10: foreign key (FooId) references Foo(FooId)
11: on delete cascade
12:
13: insert into Foo values (1)
14: insert into Bar values (1, 1)
15:
16:
17: set transaction isolation level read committed
18: begin tran
19: delete from Foo where FooId = 1
20: commit tran
So the basic idea is to delete a row from a table in such a way that it would cause a cascading delete to occur. (It would also work for updates with update cascades). The customer saw that we were taking key range locks, which is really something that is done only in the serializable isolation level (which is SQL Server’s safest but “most blocking” isolation mode).
You can read more about isolation levels and key range locking here:
http://msdn.microsoft.com/en-us/library/ms189122.aspx
http://msdn.microsoft.com/en-us/library/ms191272.aspx
Locking is a very important aspect of database applications, but it is not well understood because it happens almost entirely implicitly. If you look at the plan for this delete, you don’t see much in terms of locking being explained:
(So, I think that this is probably something we need to do a better job of documenting in the future ;)
To understand the customer problem, we need to understand how locks get taken by the system. Internally, the Storage Engine will lock all pages that are scanned by the Query Processor. So, if the QP generates a seek plan, the SE will lock each structure that is touched as part of the Seek (Index object, then each intermediate page, and then the leaf row, assuming row-level locking as the granularity is on). Likewise, a scan will acquire locks for each row it touches, but it might have a lot more. At a certain point, SQL Server will try to escalate locks to a less granular lock so it can work better on large operations.
Now, what happens when we have a delete that actually touches two tables? The semantic properties of a cascading delete are:
1. Delete from the Foo table implies that all associated rows in Bar get deleted (the cascading part)
2. At the end of the statement, the Foreign Key property is still valid
So, if we just used nice read-committed, we hold X locks on things that we modify until the transaction commits (good), but we don’t prevent someone else from inserting a row while the Delete is being processed. This is a classic definition of why you would need a SERIALIAZABLE transaction… This diagram shows what is happening on the plan temporally:
(Remember that SQL Server often has many threads executing at once. So, operations against different access paths will not happen at identical times. There is a small time gap between the operations, and this is where you can get race conditions).
So, rather than require that customers set the serialization level for operations like this, SQL Server automatically upgrades the isolation level of certain operations to block other operations from inserting a row that would violate the foreign key property. In this case, it will take some range locks as if those parts of the query were running in a serializable isolation level without upgrading the whole statement. This is one way to minimize the blocking associated with the requirement by the server to avoid data corruptions.
SERIALIZABLE locks are typically held until the end of the transaction. If you run multiple statements in the same batch, it could take awhile until those locks get released. Since the server knows that exactly why it took the locks, it happens to know that it is safe to release those serialized range locks at the end of the statement. So, these internal serialized locks are held only until the statement finishes.
This same condition applies to indexed view maintenance, but I’ll save that for another day :).
Happy Querying,
Conor
(as ANSI NULLs is one of the requirements for indexed views, I thought I’d give you some perspective on why the questions I ask you are useful and interesting to better understand queries and various query operations)
As currently designed, indexed views tries to strike a balance among:
1. query shapes that can be efficiently matched
2. query shapes that can be efficiently maintained
3. query shapes that can be efficiently created
Loosely speaking, indexed views work for basic SPJG (SELECT-PROJECT-JOIN-GROUPBY) queries. The joins must be inner joins, not self joins, and join on a key. Each operator has a series of restrictions based on (1),(2),and (3) above.
So how does the optimizer maintain these things? Well, it helps to have an understanding of what happens with views in general. Here’s a primer I wrote on the subject awhile back (http://www.sqlskills.com/BLOGS/CONOR/post/Inserts-against-views-An-introduction.aspx). Overall, the view has a tree definition, and an update against that view is decomposed by substituting the original update tree with an expanded tree for the view definition. Since the view is ultimately based on base tables, the update queries that are supported in SQL Server are ultimately operations against those base tables (in other words, the server translates your request into an equivalent operation against the base table). Then the change is performed and everyone is happy.
INDEXED views are an extension of this concept – the main difference is that the index is maintained as part of the update to the base table. (My soon-to-be-released book chapter on Query Optimization goes into more detail on the subject of wide updates). The set of changes to the base table are further streamed into a set of changes against the indexed view. The key property is that the exact set of changes to the view can be computed from the specific changes to the base table. Many of the restrictions in indexed views come from this requirement. In the academic literature, this is sometimes referred to as the delta algebra or delta logic.
Essentially, the original view definition is modified so that the source table (the one you are modifying in the UPDATE) is replaced with only the set of changes instead of the whole original table. Here’s a basic example
create table dbo.t1(col1 int primary key, col2 int, col3 int)
create table dbo.t2(col1 int primary key, col2 int, col3 int)
drop view dbo.v1
CREATE VIEW dbo.v1 with schemabinding as
select t1.col1 from dbo.t1 as t1 inner join dbo.t2 as t2 ON (t1.col1=t2.col3)
WHERE t1.col3=5 and t2.col2 = 8
create unique clustered index i1 on dbo.v1(col1)
update v1 set col1=col1+1
The update to the view is seen in the bottom branch of the query, and the delta part is the Table Spool (which replaced t1 in this case)
So, the rows being modified are joined with t2 (just like in the view definition), filtered, and projected (the SELECT list). The resulting delta stream is then applied to the persisted indexed view after some update-specific operations (collapse and a special filter that is mostly internal stuff).
Let’s talk about a few of the restrictions:
1. No Self-joins – well, the delta algebra doesn’t work for self joins. In other words, one can’t take a single update stream for the base table and substitute it into the view definition and then _efficiently_ update the view definition (remember, one of the goals is to maintain views efficiently)
2. ANSI_PADDING, ARITHABORT, ANSI_NULLs, … The main problem here is that these can impact the results returned in the query, and since customers likely don’t want to have 1 index view for each combination of these values, they are restricted.
3. Limited operator support – Finding the set of operators that can be efficiently matched, maintained, and created is a difficult problem – there are many operators, and some of them can not easily be supported in indexed views. Most of them have odd restrictions like what is described in the CREATE INDEX help page (http://msdn.microsoft.com/en-us/library/ms188783.aspx)
3a. No DISTINCT – The QP needs to be able to uniquely determine the set of rows in the indexed view to change. DISTINCT, like GROUP BY, “destroys” information in the query tree by collapsing rows. GROUP BY in indexed views requires COUNT_BIG(*), which is a way to not lose information (but it requires that you modify your query to achieve that).
3b. MIN/MAX, STDEV, VARIANCE, AVG – does not preserve enough information to allow incremental maintenance.
3c. UNION – UNION (not ALL) implicitly includes DISTINCT on the result of a UNION ALL, so it is not allowed for the same reason as DISTINCT. More generally, UNION ALL makes it hard to decompose the source table for the UPDATE to work (without more extensive modificiations to the view to track which branch of the UNION is the source of the row)
3d. fulltext, ROWSET – these include external information, and these are restricted to prevent it from changing. It is necessary to prevent a wrong results bug if the external source changes, as indexed views are designed to be kept in-sync with the source.
3e. Subquery – this is partially performance issue, but some subqueries make it impossible to determine the exact set of rows to change without also looking at rows not being changed.
…
There are lots of restrictions on indexed views, but I hope this gives you a bit of the “why” on the design.
Happy Querying,
Conor Cunningham
Technorati Tags:
SQL,
Indexed Views
I was thinking about indexed views. Well, more specifically, I was thinking about why indexed views are hard to use. One of the reasons that they are hard is that there are just so many restrictions. Anyways, one of the things I'd like to better understand is how many customers actually use ANSI NULLs OFF and specifically _why_ do you use it? The typical reason we would expect is legacy applications (and that's a fine reason), but I am curious if there is more to it than just this.
So, you know the email address - conorc (at) microsoft . com - feel free to email me. I'll anonymously summarize what I learn, but I'd like to get a feel for how customers approach this little flag. Are you planning to get rid of you use of this? Do you plan to keep using it forever? Does the packaged sql app that you bought still use this? which one?
It is in the deprecation path (http://msdn.microsoft.com/en-us/library/ms188048.aspx). So it will eventually go away, but that doesn't mean that we have nothing to learn from it :).
Happy Querying!
Conor Cunningham
MERGE is a new operation added in SQL Server 2008. It has all sorts of knobs, bells, and whistles. The primary value of this feature is to collapse multiple query statements into one query statement. Overall, this avoids the “overhead” necessary to run a query a few times and can be a big benefit, especially when running many small queries that do things like “if exists then update else insert”.
I received a natural question this week on the behavior of MERGE with respect to locks and transactions. The expressed expectation was that since MERGE was a single statement, it should be atomic transactionally and it should not be possible to get duplicate primary key errors. This expectation is not really correct – ultimately, the locking semantics for UPDATES, DELETES,INSERTS, and MERGE are more complex and require some knowledge of locking and query plans to fully understand.
Here’s the script. The initial part is created once and the second part could be run multiple times.
(running in default readcommitted, btw)
Setup:
DROP TABLE FOO
CREATE TABLE FOO (id INT PRIMARY KEY NOT NULL, name nvarchar(20) NOT NULL)
DELETE FROM FOO
INSERT INTO FOO VALUES(0, 'base')
Runtime portion:
DELETE FROM @fooChanges
INSERT INTO @fooChanges VALUES((SELECT MAX(id)+1 FROM FOO), 'induction')
MERGE FOO AS f USING @fooChanges as fc
ON ( fc.id = f.id )
WHEN MATCHED THEN
UPDATE SET name = fc.name
WHEN NOT MATCHED BY TARGET THEN
INSERT (id, name)
VALUES (fc.id, fc.name);
Effectively, MERGE is doing complex stuff under the covers for you. It is performing a join between the original table (FOO) and the table to be MERGEed (@fooChanges). It is an outer join, and the matching rows correspond to the case when the two rows match and the “not matched” rows in the join correspond to the “not matched” case in the query statement. The not matched rows have NULL on the non-matching side, and this is eventually converted into an action to INSERT instead of UPDATE in the stream of operations to be performed against the table FOO.
Here’s where this is happening in the query plan:
For non-MERGE UPDATEs and DELETEs, the common practice within most engines is to have a special “U” (Update) lock that is taken on the source rowset and then promoted to an “X” (exclusive) lock when the Update operation is actually performed later in the query tree. (Way back in the days, the read part would take an “S” (shared) lock that would not prevent other consumers from reading the row. Ultimately, this could cause all updates to fail in high transaction environments because two update queries could both get the S lock and not be able to promote to the X lock (since S locks can only be promoted if nobody else holds another S lock). Ultimately, this was solved by adding a U lock that prevented other UPDATEs but allowed other SELECTs.
In the case of MERGE WHEN NOT MATCHED, we actually don’t have a row yet, so there is no place on which to attach a lock (unless you use SERIALIZABLE isolation, which would take key range locks). So, no U lock means that there is no prevention against duplicate inserts (or PRIMARY KEY duplicate violations, in this case).
So, ultimately, the MERGE does not prevent key collisions for WHERE NOT MATCHED INSERTs.
Happy Querying!
Conor Cunningham
