The Beatles versus the Stones – the explanation

On December 31 of last year, I posted this brain teaser, promising to post the answer “in a few days”. Apparently, 15 is a few J.

 

In case you have forgotten what the puzzle was about and are too lazy to click the link above, the bottom line is that I created and populated two tables, with the same schema but different content. One held the first and last name of each of the Beatles, the other held first and last name of each of the Rolling Stones. I then queried both tables, using the same query in both cases. The query did not include an ORDER BY clause. It turned out that the results from the Beatles table were always returned in order of the clustered index, whereas the results from the Stones table was unordered. And that was the question I left you with – how can two tables that have the same schema show so different behavior?

 

The answer to this is that, of course, the two tables don’t display different behavior at all. In fact, they behave exactly the same – the results looked different but were not!

 


If you rerun the code to create the two tables and then issue the two SELECT statements again with the option to show the execution plan turned on, you will get this execution plan:

 

As you can see, both queries were executed with an identical plan: a scan of the nonclustered index that was created to check the UNIQUE constraint on the FirstName column. If you now change the original queries to include this column as well, you should not only see that the execution plan remains the same, but you should also see the explanation for the different behavior.

 

SELECT FirstName, LastName FROM Beatles;

SELECT FirstName, LastName FROM Stones;

go

 

FirstName            LastName

——————– ——————–

George               Harrison

John                 Lennon

Paul                 McCartney

Ringo                Starr

 

 

FirstName            LastName

——————– ——————–

Bill                 Wyman

Brian                Jones

Charlie              Watts

Keith                Richards

Mick                 Jagger

 

As you see, both result sets are alphabetically ordered by first name. It is a shear coincidence that the alphabetic ordering of the Beatles by first name exactly matches the ordering by last name. So the results have never been returned in the order of the clustered index, but always in the order of the nonclustered index, for both tables. These orders just happen to be indistinguishable for one of the two tables.

 

Of course, this still leaves us with the question why the optimizer chooses to scan the nonclustered index for this query. That question is easily answered. You just have to consider which columns are included in each of the indexes.

 

A clustered index will always have the indexed columns in the root and intermediate pages, and all columns in the table in the leaf pages. A nonclustered index will also have the indexed columns in the root and intermediate pages, but its leaf pages contain only the indexed columns plus the columns of the clustered index (if any). For the Beatles and Stones tables, this means that the clustered indexes have LastName in the non-leaf pages, and all columns (both LastName and FirstName) in the leaf pages; the nonclustered indexes have FirstName in the non-leaf pages and add the clustered index key of LastName in the leaf pages.

 

Since the queries issued don’t have a WHERE clause, the optimizer can only consider plans using a scan operator. A scan will only touch the leaf pages of an index. In this particular case, all rows used in the query (just LastName) happen to be available in the leaf pages of both indexes. That means that the nonclustered index is a covering index for this query, and an extra lookup operator is not required to get the data. So the choice is between scanning either the clustered index or the nonclustered index.

 

In this case, both indexes have exactly the same amount of data in their leaf pages, so there is no reason to prefer one over the other. But that is very unusual – in 99% of all normal situations, a nonclustered index will have less data in its leaf pages than the clustered index. (Remember that a clustered index always includes ALL columns in the leaf pages!), and a nonclustered index will never have more data in its leaf pages. For that reason, the query optimizer will always favor an execution plan that uses a covering nonclustered index over a plan that uses a clustered index.

 


One interesting comment was made by Denis The SQL Menace: if you add WHERE LastName > ” to the queries, the order will match the clustered index for both queries. That makes sense. Remember that there is no constraint that disallows us from setting LastName equal to the empty string in one of the rows of the table, so there might be a row that doesn’t satisfy the WHERE clause. The nonclustered index scan used previously would still have to process that row; a clustered index seek would enable the engine to bypass that row. So I’m not surprised to see the execution plan change to a clustered index seek.

 

An even more intriguing observation was pointed out by Ahmed Charles. He added a computed column to the table and replaced the UNIQUE constraint with a UNIQUE INDEX, with the computed column as included column. Here’s how the Stones table looks after Ahmed’s modification:

 

CREATE TABLE Stones

    (LastName varchar(20) NOT NULL PRIMARY KEY CLUSTERED,

     FirstName varchar(20),

     LastNameAgain AS CAST(LastName AS char(1597)));

CREATE UNIQUE INDEX IX_FirstName

       ON Stones(FirstName)

       INCLUDE (LastNameAgain);

 

Ahmed found that if the computed column is defined as char(1597) or more, the engine scans the clustered index, resulting in the last names being lasted alphabetically; as long as the computed column in char(1596) or less, the engine prefers to scan the nonclustered index. Why does the execution plan suddenly change if the computed column gets one additional character? Computed columns are not even supposed to be persisted, right?

 

Well, yes and no. Computed columns are indeed normally not stored, but computed when queried. But there are two things that can change that: adding the PERSISTED keyword to the column’s definition, or using the column in an index. In the first case, the value of the column is physically stored in the clustered index (or in the heap); in the latter case, the value is physically stored in each index that is defined on or includes the column. The latter is what happens here.

 

If you look at the data in the IX_FirstName index in a bit more details, we see that each leaf page entry will hold one char(1597) column (always 1597 bytes), two varchar(20) columns (number of bytes equal to actual length, plus 2 bytes each for length), plus 8 bytes of overhead per row (one byte for status flags, one byte for the NULL bitmap, two bytes for the total number of columns, two bytes for the number of variable-length columns, and two bytes for the row offset). So for each row, the amount of bytes used is equal to 1609 (1597 + (2 * 2) + 8) + the number of characters in the first and last name. That’s 1618 bytes for Bill Wyman, 1619 for Brian Jones, 1621 for Charlie Watts, 1622 for Keith Richards, and 1619 for Mick Jagger, making a grand total of 8099 bytes. Now each page can hold 8192 bytes, but 96 of them are reserved for the page header, so that leaves 8096 bytes for data. Three less than the number of bytes required to store the index data – so the index requires a second page. But if I reduce the length of the computed column by 1, the required amount per row drops 1 bytes; for all 5 rows combined, we need 5 bytes less – 8094 bytes, which does fit in a single page.

 

Just in case you want to check this for yourself without doing the calculations or running the DBCC PAGE commands, you can also execute

 

SELECT dpages FROM sysindexes WHERE name = ‘IX_FirstName’;

 

to see the number of leaf pages used by the index.

 

With this knowledge, I can new explain why the computed column changes the behavior of the query when the computed column exceeds 1596 bytes – an index scan will now require more page reads than a clustered index scan, so the optimizer will surely choose the latter.

 

With this knowledge, I can also predict some other interesting things:

·        If I change the definition of the FirstName and LastName columns to char(20), I can reduce the computed column to 1574 bytes and I still get a clustered index scan;

·        If I reduce the initial load of the table to just four of the five band members (for instance by omitting Brian Jones), I have to increase the length of the computed column to 2002 before I get a clustered index scan;

·        But on the other hand, if I add all five band members to the table, then delete Brian Jones again, I still get the clustered index scan even with a computed column of 1597 bytes length. Once the second page has been allocated to the nonclustered index, it will stay allocated even if the data could in theory be compressed on a single page again. Reorganizing the index won’t change this, but rebuilding will.

The Beatles versus the Stones

Here’s a nice brain teaser, just before the end of the year. Despite the title, it is related to SQL Server, not to music!

 

A common misconception amongst SQL Server users is that a clustered index on a table will ensure that data is returned in the order implied by that index. I have lost count of the number of times I had to disprove this notion.

 

Of course, there are many cases where the rows returned by a query will be in the order of the clustered index. Here’s a quick illustration, using the lineup that The Beatles had during most of the 60s.

 

CREATE TABLE Beatles

     (LastName varchar(20) NOT NULL PRIMARY KEY CLUSTERED,

      FirstName varchar(20) NOT NULL UNIQUE NONCLUSTERED);

INSERT INTO Beatles (LastName, FirstName)

SELECT ‘Lennon’, ‘John’

UNION ALL

SELECT ‘McCartney’, ‘Paul’

UNION ALL

SELECT ‘Harrison’, ‘George’

UNION ALL

SELECT ‘Starr’, ‘Ringo’;

SELECT LastName FROM Beatles;

DROP TABLE Beatles;

go

 

LastName

——————–

Harrison

Lennon

McCartney

Starr

 

The results of this query are in alphabetical order of last name, the column used in the clustered index. Apparently, this is one of the very many cases where the order of the rows is implied by the clustered index, allowing the misconception that this is always the case to spread even further.

 

But an interesting thing happens if I use the exact same table definition to old and query the lineup of that other famous rock group of the 60s:

 

CREATE TABLE Stones

     (LastName varchar(20) NOT NULL PRIMARY KEY CLUSTERED,

      FirstName varchar(20) NOT NULL UNIQUE NONCLUSTERED);

INSERT INTO Stones (LastName, FirstName)

SELECT ‘Jagger’, ‘Mick’

UNION ALL

SELECT ‘Jones’, ‘Brian’

UNION ALL

SELECT ‘Richards’, ‘Keith’

UNION ALL

SELECT ‘Watts’, ‘Charlie’

UNION ALL

SELECT ‘Wyman’, ‘Bill’;

SELECT LastName FROM Stones;

DROP TABLE Stones;

go

 

LastName

——————–

Wyman

Jones

Watts

Richards

Jagger

 

In this case, the names are returned in random order. That makes this a great example to really disprove the notion of a clustered index guaranteeing any output order. (Dare I say that we now finally have solid proof that the Stones are better than the Beatles? Or will that make me subject to loads of flames?)

 

What’s intriguing in this case is the difference in behaviour for the two examples. Apart from the table name, the two code snippets are exactly the same – and even renaming the tables won’t change the results. So here’s the brain teaser that I’ll leave you to ponder over your glass of champagne: what is the reason that the Beatles are, but the Stones are not returned in clustered index order?

 

I’ll post the answer in a few days.

 

 

On a more personal note, I want to apologize for not posting any new stuff during the last two months. I still have some good ideas in my scratchpad, but I need some time to polish them up to blog quality – and time is the one thing I have been lacking for the past two months. The bad news is that I will probably be short on time for the next month as well, but things are looking more sunny after that.

 

And with this being my last post of the year, I’ll also grab this opportunity to wish all readers of sqlblog.com a very great 2007, with lots of love and luck in your personal lifes, and lots of interesting SQL challenges and enticing performance gains at work.

The table scan from hell

Greg Linwood, a fellow SQL Server MVP, has started a series of articles in which he attempts to prove that having a clustered index on each table is not a good practice. However, he has failed to include the effects of fragmentation into account, so I decided to run some tests for myself. One of those test had rather upsetting results.

 

First a bit of background, for those of you who have never read a book by Kalen Delaney. A table without clustered index (also known as a “heap”) can be read in two ways: using a bookmark lookup or a table scan.

 

A bookmark lookup is used when a nonclustered index can first be used to narrow down the number of rows to read. Each entry in the nonclustered index holds a pointer to the row in the heap; this pointer is called the RID (short for Row ID), and consists of a file number, a page number, and a slot number. Using the RID, the storage engine can directly fetch the required page and read the row.

 

A table scan is used when there is no nonclustered index or when statistics indicate that the nonclustered index is not selective enough. A table scan is driven by the IAM (Index Allocation Map), basically a bitmap that indicates which pages in the database are allocated for this table. Table scans always tend to be slow, because each page in the table has to be read and each row processed. This is offset somewhat by the fact that the pages are read in order of page number, so if there is no file fragmentation, movement of the disk heads will be minimal and SQL Server can use the highly efficient read-ahead technology rather than the usual random I/O. Or at least, that’s what I (and many others) always assumed.

 

Before moving on to the issue of fragmentation, let’s first see this in action:

 

IF EXISTS (SELECT FROM sys.objects WHERE object_id = OBJECT_ID(N’dbo.Persons’) AND type = N’U’)

  DROP TABLE dbo.Persons;

go

CREATE TABLE dbo.Persons

            (PersonID int NOT NULL IDENTITY,

             FName varchar(20) NOT NULL,

             LName varchar(30) NOT NULL,

             Email varchar(7000) NOT NULL);

go

— Insert approx. 20,000 rows

INSERT INTO dbo.Persons (FName, LName, Email)

SELECT LEFT(FirstName, 20), LEFT(LastName, 30), EmailAddress

FROM   AdventureWorks.Person.Contact;

go

— Dummy table scan to force creation of statistics

DECLARE @Dummy int;

SELECT @Dummy = COUNT()

FROM   dbo.Persons

WHERE  Email LIKE ‘brenda20@adventure-works.com%’;

go

— Completely clear out the cache

CHECKPOINT;

DBCC DROPCLEANBUFFERS WITH NO_INFOMSGS;

DBCC FREEPROCCACHE WITH NO_INFOMSGS;

go

— Do table scan and show pages read, then show #pages in table.

SET STATISTICS IO ON;

SELECT *

FROM   dbo.Persons

WHERE  Email LIKE ‘brenda20@adventure-works.com%’;

SET STATISTICS IO OFF;

DBCC CHECKTABLE(‘dbo.Persons’);

go

 

In case you are wondering about the “dummy table scan” – on my first tests, I got only logical reads, which was odd considering I had just forced the cache to be cleaned. Fellow MVP Steve Kass found the cause: the first time the Email column is used in a search condition, statistics have to be computed, which is done by scanning the table. The dummy scan ensures that the statistics are created before I clear out the cache.

 

On my SQL Server 2005 server, I got this output (edited for readability):

 

PersonID    FName                LName                          Email

———– ——————– —————————— —————————–

14575       Brenda               Lopez                          brenda20@adventure-works.com

 

Table ‘Persons’. Scan count 1, logical reads 149, physical reads 0, read-ahead reads 165, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

DBCC results for ‘Persons’.

There are 19972 rows in 149 pages for object “Persons”.

DBCC execution completed. If DBCC printed error messages, contact your system administrator.

 

There are 149 pages used by the table, and 149 pages are read. This is as expected. I must admit that I don’t know why there are 16 extra read-ahead reads, though.

 

Updates of rows with variable-length columns are one of the main causes of fragmentation in a heap. SQL Server will try to perform an update in place. This is always possible if the new data occupies less or the same number of bytes as the old data, but if the new data needs more room and there’s not enough space left in the page, the row has to move. SQL Server finds a page with enough free space or allocates a new page, then stores the new data of the row in that page. The data at the original location is replaced with a so-called “forwarding pointer”: a RID that points to the new location of the row. Because of this forwarding pointer, there is no need to change RID pointers to the row in existing nonclustered indexes; when trying to read this row, they can simply follow the forwarding pointer to its new location. And at the new location, a “back pointer” to the original location is added, so that if the row has to move again, the original forwarding pointer can be updated rather than forming an endless chain of forwarding pointers.

 

Run this code now to simulate how a table might get fragmented over time as its contents are regularly updated. Note that this code does 5,000 random updates; one out of four rows on average will be updated, many rows will never be touched, and a few might even be updated twice or more.

 

— Simulate update activity to create fragmentation.

— Temporarily add index to improve performance.

CREATE UNIQUE NONCLUSTERED INDEX ix_PersonID ON dbo.Persons(PersonID);

— Do 5,000 random updates to email column, increasing it’s length.

DECLARE @cnt int;

SET @cnt = 1;

WHILE @cnt < 5000

  BEGIN;

  SET @cnt = @cnt + 1;

  UPDATE dbo.Persons

  SET    Email = LEFT(Email + Email, 7000)

  WHERE  PersonID = CAST(RAND() * 20000 AS int);

  END;

— Drop the index, we no longer need it.

DROP INDEX dbo.Persons.ix_PersonID;

go

 

There now should be plenty of forwarding pointers in the table. This means that many bookmark lookups will now take two reads instead of just one. But how are table scans affected by these forwarding pointers? I see two possible methods:

 

1.      Follow the IAM from start to finish. Ignore forwarding pointers. Process all rows, both with and without back pointers. Processing is still completely sequential.

2.      Follow the IAM from start to finish. When encountering a forwarding pointer, immediately fetch the page that the pointer points to and process that row. When encountering a row with a back pointer, ignore it (it is already or will be processed when the corresponding forwarding pointer is read).

 

If the table is read WITH (NOLOCK) or in TRANSACTION ISOLATION LEVEL READ UNCOMMITTED, the second method has to be used. Otherwise, a row that is moved during the scan might be included twice or not at all (Paul Randal explains this in a bit more detail in his post about heaps). But in all other cases, method 1 can safely be used since the table lock issued by the table scan effectively prevents any modification while the scan is running.

 

So let’s see what method SQL Server picks:

 

— Do table scan and show pages read, then show #pages in table.

CHECKPOINT;

DBCC DROPCLEANBUFFERS WITH NO_INFOMSGS;

SET STATISTICS IO ON;

SELECT *

FROM   dbo.Persons

WHERE  Email LIKE ‘brenda20@adventure-works.com%’;

SET STATISTICS IO OFF;

DBCC CHECKTABLE(‘dbo.Persons’);

go

 

The relevant part of the output on my system (note that numbers vary slightly between runs, due to the use of RAND() in the simulated updates):

 

Table ‘Persons’. Scan count 1, logical reads 1892, physical reads 0, read-ahead reads 222, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

DBCC results for ‘Persons’.

There are 19972 rows in 174 pages for object “Persons”.

 

The number of pages occupied by the table has grown a fair bit, but that was to be expected after doubling 5,000 email addresses. The troubling part of the output is the number of logical reads. Apparently, the average page in the table is read 10 times! This shows that, even though the default READ COMMITTED isolation level makes it unnecessary, SQL Server will follow method 1.

 

Reading the same page will of course significantly impact performance. This gets even worse when the size of the table exceeds the available server memory so that not all pages fit in the data cache. Since the order in which pages are accessed will be completely random (for instance, the first page holds forwarding pointers to pages 6632, 91, 93055, 17, 494, and 220568; the second page holds forwarding pointers to pages 902, 14, 6632, 1905408, and 3, etc.), pages requested will probably just have been removed from cache so that they have to be read from disk once more. Because of the forwarding pointers (and an apparent oversight from Microsoft), a table scan on a heap might come with an amount of physical I/O that is a multiple of the actual size of the table. And there is no easy way to fix or prevent this, since heaps (unlike table scans) can not be unfragmented. The only option is to periodically copy over all data to a new table, as that is the only way to get rid of the fragmentation.

 

Bottom line: Beware of table scans, and beware of the effects of fragmentation on a heap. Even though I agree with Greg that some tables don’t need a clustered index, those are the exception. So if you choose to use rules of thumb, make sure that having a clustered index for each table is one of them. It might not be optimal, but it’s a lot better than not having a clustered index for any table!

Just stuff it!

I’m sure you’ve all heard it, and probably even said it, many times: “SQL Server sucks at string manipulation”. And with good reason – it is true. But not quite as true as many seem to believe.

 

I notice that many people who complain about SQL Server lacking string manipulation are themselves unaware of the string functions that SQL Server does have. Most know LIKE, LEFT, RIGHT, and SUBSTRING. Some also know CHARINDEX, maybe even REPLACE. But how many of you know and use PATINDEX, REVERSE, QUOTENAME, and LTRIM, to name just a few?

 

The string function that appears to be the most overlooked has to be STUFF. And yet, this function can prove to be an invaluable tool. I’ll give a short description first, then show some examples of how STUFF can be used for string manipulation that would otherwise be much harder to achieve.

 

What STUFF does, basically, is cut a specified portion from a string and replace it with a new string. The replacement string can be shorter, longer, or exactly as long as the part that has been cut out. The STUFF function takes four arguments, none of which is optional. The first is of character data type and specifies the input string; the second and third are integers specifying the starting position and length of the substring to remove, and the fourth is the replacement string. Here are some examples to illustrate the use of STUFF:

 

DECLARE @Test varchar(15)

SET @Test = ‘Hugo Kornelis’

SELECT STUFF (@Test, 1, 4, ‘I am’),   — Basic usage example

       STUFF (@Test, 6, 0, ‘SQL ‘),   — Replaced string can be empty

       STUFF (@Test, 2, 10, ”)       — Replacement string can be empty

 

                                   

————— ——————- ——

I am Kornelis   Hugo SQL Kornelis   His

 

 

The first real world example of using STUFF is based on a newsgroup question. The question was how to replace a substring of a string. Here’s the simplified and non-working example given by the poster (based on the pubs sample database):

 

UPDATE authors

SET    SUBSTRING(phone,5,3) = ‘888’

WHERE  SUBSTRING(phone,5,3) = ‘826’;

 

One of the regulars in the group replied with this suggestion:

 

UPDATE authors

SET    phone = REPLACE(phone, ‘826’, ‘888’)

WHERE  SUBSTRING(phone,5,3) = ‘826’;

 

That looks clean and tidy, and runs fine on the data in pubs – but what if one of the authors in pubs has phone number ‘801 826-0826’? Indeed, it would be changed to ‘801 888-0888’ instead of ‘801 888-0826’, as requested.

 

Another way to do this that I often see recommended (though not in this particular thread) is to use LEFT and SUBSTRING to cut the string in pieces, then mend them together after making the change. Like this:

 

UPDATE authors

SET    phone = LEFT(phone, 4) + ‘888’ + SUBSTRING(phone, 8, LEN(phone) – 7)

WHERE  SUBSTRING(phone,5,3) = ‘826’;

 

That works – but ugh!, how ugly. This would be a lot easier with STUFF:

 

UPDATE authors

SET    phone = STUFF(phone, 5, 3, ‘888’)

WHERE  SUBSTRING(phone,5,3) = ‘826’;

 

 

Here’s another example. A common question in the newsgroups is how to find individual parts in a string. For instance, a bulk import results in a table of names in the form “Lastname, Firstname”. How to get individual Lastname and Firstname values from this?

For the first part of the string (Lastname in this case), this is easy. Use POSINDEX to find the starting position of the separator, use that to calculate the argument for the LEFT function.

The second part is harder. Answers typically given in the groups to these questions use techniques such as finding the starting position, calculating remaining length and feeding those as parameters to the SUBSTRING (version 1 below); using REVERSE to change the task to another task of finding the first part in a string (version 2 below) or using RIGHT instead of LEFT, with again the use of REVERSE to calculate length (version 3). However, with STUFF (version 4), this becomes much easier! See version 4, below:

 

CREATE TABLE BadData (FullName varchar(20) NOT NULL);

INSERT INTO BadData (FullName)

SELECT ‘Clinton, Bill’ UNION ALL

SELECT ‘Johnson, Lyndon’ UNION ALL

SELECT ‘Bush, George’;

— Version 1, using SUBSTRING

SELECT LEFT(FullName, CHARINDEX(‘, ‘, FullName) – 1) AS LastName,

       SUBSTRING(FullName,

                 CHARINDEX(‘, ‘, FullName) + 2,

                 LEN(FullName) – CHARINDEX(‘, ‘, FullName) – 1) AS FirstName

FROM   BadData

— Version 2, using REVERSE, LEFT, and REVERSE again

SELECT LEFT(FullName, CHARINDEX(‘, ‘, FullName) – 1) AS LastName,

       REVERSE(LEFT(REVERSE(FullName),

              CHARINDEX(‘ ,’, REVERSE(FullName)) – 1)) AS FirstName

FROM   BadData

— Version 3, using RIGHT and REVERSE

SELECT LEFT(FullName, CHARINDEX(‘, ‘, FullName) – 1) AS LastName,

       RIGHT(FullName, CHARINDEX(‘ ,’, REVERSE(FullName)) – 1) AS FirstName

FROM   BadData

— Version 4, using STUFF

SELECT LEFT(FullName, CHARINDEX(‘, ‘, FullName) – 1) AS LastName,

       STUFF(FullName, 1, CHARINDEX(‘, ‘, FullName) + 1, ”) AS FirstName

FROM   BadData

 

You might say that there’s not actually that much difference between versions 3 and 4 above, so why am I so enthusiastic about STUFF? To see that, let’s take this to the next level. What if the names in the imported data are of the form “Lastname, Firstname MiddleInitial”, with MiddleInitial being optional? Below, you’ll find the best I was able to do without STUFF, and than a version with STUFF – still not pretty, but not quite as awful as the first version, I’d say. If anyone is able to write a shorter version, I’d love to hear it!

 

CREATE TABLE BadData (FullName varchar(20) NOT NULL);

INSERT INTO BadData (FullName)

SELECT ‘Clinton, Bill’ UNION ALL

SELECT ‘Johnson, Lyndon, B.’ UNION ALL

SELECT ‘Bush, George, H.W.’;

— Version 1, without STUFF

SELECT FullName,

       LEFT(FullName, CHARINDEX(‘, ‘, FullName) – 1) AS LastName,

       SUBSTRING(FullName,

                 CHARINDEX(‘, ‘, FullName) + 2,

                 CHARINDEX(‘, ‘, FullName + ‘, ‘,

                           CHARINDEX(‘, ‘, FullName) + 2)

               – CHARINDEX(‘, ‘, FullName) – 2) AS FirstName,

       CASE WHEN FullName LIKE ‘%, %, %’

            THEN RIGHT(FullName, CHARINDEX(‘ ,’, REVERSE(FullName)) – 1)

            ELSE ” END AS MiddleInitial

FROM   BadData

— Version 2, with STUFF

SELECT FullName,

       LEFT(FullName, CHARINDEX(‘, ‘, FullName) – 1) AS LastName,

       STUFF(LEFT(FullName, CHARINDEX(‘, ‘, FullName + ‘, ‘,

                                      CHARINDEX(‘, ‘, FullName) + 2) – 1),

             1, CHARINDEX(‘, ‘, FullName) + 1, ”) AS FirstName,

       STUFF(FullName, 1,

             CHARINDEX(‘, ‘, FullName + ‘, ‘,

                       CHARINDEX(‘, ‘, FullName) + 2), ”) AS MiddleInitial

FROM   BadData

 

As you have seen, learning to use STUFF when appropriate can make hard tasks easy, complex queries simple, and extremely complicated queries somewhat less complicated. This string function is a tool that every SQL Server developer should know. So the next time someone complains how SQL Server is severely lacking adequate string manipulation tools, you know what to do – just tell’m to stuff it!

The prime number challenge – great waste of time!

No sane person would even consider using SQL Server to construct a list of prime numbers. So just to prove that I’m not sane (as if there could be any doubt!), this post will be about finding prime numbers.

 

First a bit of history. Ward Pond wrote about efficient ways to populate a table with one million GUIDs. I posted a comment with a slightly more efficient algorithm. And that was quickly followed by a new post from Ward, tweaking my syntax even further. And that’s when Denis the SQL Menace lived true to his name by posting this comment:

 

“How about the next challenge is to return all 78498 prime numbers between 1 and 1000000?”

 

Now of course, this is a silly challenge. Not because prime numbers are silly, mind you. They are very useful to mathematicians, and many encryption algorithms wouldn’t even be possible without (large) prime numbers. The silly part is using SQL Server, a data manipulation tool, to calculate prime numbers. If you really need them, code a quick algorithm in a C++ program. Or buy a ready-made list with the first million or so prime numbers. So I attempted to resist the challenge.

 

Alas – the flesh is weak. So when I saw Ward’s reply to Denis’ challenge, I was no longer able to resist temptation. After all, Ward’s attempt is not only interesting – it is also very long, and apparently (with an estimated completion time of 1 to 2 days!!) not very efficient. I decided that I should be able to outperform that.

 

My assumptions are that a table of numbers is already available, and that this table holds at least all numbers from 1 to 1,000,000. (Mine holds numbers from 1 to 5,764,801), and that the challenge is to create and populate a table with the prime numbers from 1 to 1,000,000, in as little speed as possible. Displaying the prime numbers is not part of the challenge. For testing purposes, I replaced the upper limit of 1,000,000 with a variable @Limit, and I set this to a mere 10,000. That saves me a lot of idle waiting time!

 

As a first attempt, I decided to play dumb. Just use one single set-based query that holds the definition of prime number. Here’s the SQL:

 

DROP TABLE dbo.Primes

go

CREATE TABLE dbo.Primes

           (Prime int NOT NULL PRIMARY KEY)

go

DECLARE @Start datetime, @End datetime

SET     @Start = CURRENT_TIMESTAMP

DECLARE @Limit int

SET     @Limit = 10000

 

INSERT INTO dbo.Primes (Prime)

SELECT      n1.Number

FROM        dbo.Numbers AS n1

WHERE       n1.Number > 1

AND         n1.Number < @Limit

AND NOT EXISTS

 (SELECT   

  FROM      dbo.Numbers AS n2

  WHERE     n2.Number > 1

  AND       n2.Number < n1.Number

  AND       n1.Number % n2.Number = 0)

 

SET     @End = CURRENT_TIMESTAMP

SELECT  @Start AS Start_time, @End AS End_time,

        DATEDIFF(ms, @Start, @End) AS Duration,

        COUNT() AS Primes_found, @Limit AS Limit

FROM    dbo.Primes

go

–select * from dbo.Primes

go

 

This ran in 1,530 ms on my test system. (And in case you ask – I also tested the equivalent query with LEFT JOIN; that took 11,466 ms, so I quickly discarded it). With @Limit set to 20,000 and 40,000, execution times were 5,263 and 18,703 ms – so each time we double @Limit, execution time grows with a factor 3.5. Using this factor, I can estimate an execution time of one to two hours.

 

That’s a lot better than the one to two days Ward estimates for his version – but not quite fast enough for me. So I decided to try to convert the Sieve of Eratosthenes to T-SQL. This algorithm is known to be both simple and fast for getting a list of prime numbers. Here’s my first attempt:

 

DROP TABLE dbo.Primes

go

CREATE TABLE dbo.Primes

           (Prime int NOT NULL PRIMARY KEY)

go

DECLARE @Start datetime, @End datetime

SET     @Start = CURRENT_TIMESTAMP

DECLARE @Limit int

SET     @Limit = 10000

 

— Initial fill of sieve;

— filter out the even numbers right from the start.

INSERT  INTO dbo.Primes (Prime)

SELECT  Number

FROM    dbo.Numbers

WHERE  (Number % 2 <> 0 OR Number = 2)

AND     Number <> 1

AND     Number <= @Limit

 

— Set @Current to 2, since multiples of 2 have already been processed

DECLARE @Current int

SET     @Current = 2

WHILE   @Current < SQRT(@Limit)

BEGIN

  — Find next prime to process

  SET @Current =

             (SELECT TOP (1) Prime

              FROM     dbo.Primes

              WHERE    Prime > @Current

              ORDER BY Prime)

  DELETE FROM dbo.Primes

  WHERE       Prime IN (SELECT n.Number @Current

                        FROM   dbo.Numbers AS n

                        WHERE  n.Number >= @Current

                        AND    n.Number <= @Limit / @Current)

END

 

SET     @End = CURRENT_TIMESTAMP

SELECT  @Start AS Start_time, @End AS End_time,

        DATEDIFF(ms, @Start, @End) AS Duration,

        COUNT() AS Primes_found, @Limit AS Limit

FROM    dbo.Primes

go

–select * from dbo.Primes

 

The time that Eratosthenes takes to find the prime numbers up to 10,000 is 7,750 ms – much longer than the previous version. My only hope was that the execution time would not increase with a factor of 3.5 when doubling @Limit – and indeed, it didn’t. With @Limit set to 20,000 and 40,000, execution times were 31,126 and 124,923 ms, so the factor has gone up to 4. With @Limit set to 1,000,000, I expect an execution time of 15 to 20 hours.

 

Time to ditch the sieve? No, not at all. Time to make use of the fact that SQL Server prefers to process whole sets at a time. Let’s look at the algorithm in more detail – after the initial INSERT that fills the sieve and removes the multiples of 2, it finds 3 as the next prime number and removes multiples of 3. It starts removing at 9 (3 squared) – so we can be pretty sure that numbers below 9 that have not yet been removed will never be removed anymore. Why process them one at a time? Why not process them all at once? That’s what the algorithm below does – on the first pass of the WHILE loop, it takes the last processed number (2), finds the first prime after that (3), then uses the square of that number (9) to define the range of numbers in the sieve that are now guaranteed to be primes. It then removes multiples of all primes in that range. And after that, it repeats the operation, this time removing multiples in the range between 11 (first prime after 9) and 121 (11 square). Let’s see how this affects performance.

 

DROP TABLE dbo.Primes

go

CREATE TABLE dbo.Primes

           (Prime int NOT NULL PRIMARY KEY)

go

DECLARE @Start datetime, @End datetime

SET     @Start = CURRENT_TIMESTAMP

DECLARE @Limit int

SET     @Limit = 10000

 

— Initial fill of sieve;

— filter out the even numbers right from the start.

INSERT  INTO dbo.Primes (Prime)

SELECT  Number

FROM    dbo.Numbers

WHERE  (Number % 2 <> 0 OR Number = 2)

AND     Number <> 1

AND     Number <= @Limit

 

— Set @Last to 2, since multiples of 2 have already been processed

DECLARE @First int, @Last int

SET     @Last = 2

WHILE   @Last < SQRT(@Limit)

BEGIN

  — Find next prime as start of next range

  SET @First =

             (SELECT TOP (1) Prime

              FROM     dbo.Primes

              WHERE    Prime > @Last

              ORDER BY Prime)

  — Range to process ends at square of starting point

  SET @Last = @First @First

  DELETE FROM dbo.Primes

  WHERE       Prime IN (SELECT     n.Number * p.Prime

                        FROM       dbo.Primes  AS p

                        INNER JOIN dbo.Numbers AS n

                              ON   n.Number >= p.Prime

                              AND  n.Number <= @Limit / p.Prime

                        WHERE      p.Prime  >= @First

                        AND        p.Prime  <  @Last)

END

 

SET     @End = CURRENT_TIMESTAMP

SELECT  @Start AS Start_time, @End AS End_time,

        DATEDIFF(ms, @Start, @End) AS Duration,

        COUNT() AS Primes_found, @Limit AS Limit

FROM    dbo.Primes

go

–select * from dbo.Primes

 

The time taken for the 1,229 primes between 1 and 10,000? A mere 266 ms!! With execution times like that, I saw no need to rely on extrapolation – I set @Limit to 1,000,000, hit the Execute button, sat back – and get the following result after 19 seconds:

 

Start_time              End_time                Duration    Primes_found Limit

———————– ———————– ———– ———— ———–

2006-09-24 00:42:22.780 2006-09-24 00:42:41.750 18970       78498        1000000

 

From 1-2 days to just under 20 seconds – and this time, I didn’t even have to add an index!

 

Finally, to top things off, I tried one more thing. I have often read that SQL Server won’t optimize an IN clause as well as an EXISTS clause, especially if the subquery after IN returns a lot of rows – which is definitely the case here. So I rewrote the DELETE statement in the heart of the WHILE loop to read like this:

 

  DELETE FROM dbo.Primes

  WHERE EXISTS

   (SELECT    *

    FROM       dbo.Primes  AS p

    INNER JOIN dbo.Numbers AS n

          ON   n.Number >= p.Prime

          AND  n.Number <= @Limit / p.Prime

    WHERE      p.Prime  >= @First

    AND        p.Prime  <  @Last

    AND        Primes.Prime = n.Number * p.Prime)

 

And here are the results:

 

Start_time              End_time                Duration    Primes_found Limit

———————– ———————– ———– ———— ———–

2006-09-24 00:47:42.797 2006-09-24 00:48:01.903 19106       78498        1000000

 

Which just goes to prove that you shouldn’t believe everything you read, I guess. <g>

Snapshot isolation: A threat for integrity? (Part 4)

In the previous parts of this series, I have shown how SQL Server prevents violations of foreign key constraints by silently disabling snapshot isolation. I have also demonstrated how you can use the same technique inside your trigger code, to keep snapshot isolation from damaging your custom integrity rules. Now, in the final part of this series, I will investigate some less common techniques for preserving integrity. Note that I would normally not recommend any of these techniques, but I do see them often enough in newsgroup postings. Apparently, they are used.

 

First, I’ll set up the tables again. I’ll just continue to use the script from part 2, so no need to repeat it here. I’ll also use the same business rule: orders of type A must refer to an existing customer. Instead of implementing this rule with a trigger, I use a trick I often see recommended in the newsgroups: use a CHECK constraint, based on  a user-defined function.

 

CREATE FUNCTION dbo.CustExists (@CustID int)

RETURNS char(1)

AS

BEGIN

  DECLARE @retval char(1)

  IF EXISTS (SELECT *

             FROM   dbo.Customers

             WHERE  CustID = @CustID)

     SET @retval = ‘Y’

  ELSE

     SET @retval = ‘N’

  RETURN @retval

END;

go

ALTER TABLE dbo.Orders

ADD CONSTRAINT TypeAMustExist

    CHECK (OrderType <> ‘A’ OR

           dbo.CustExists(CustID) = ‘Y’);

go

 

Note that this constraint offers only partial protection: nothing prevents you from deleting rows from the Customers table, even if they are referenced by type A orders – you will have to take additional steps to prevent that. Only insertions and updates in the Orders table are checked with this constraint – but with snapshot isolation, not even that is reliable anymore.

 

To test this, I opened two connections from SQL Server Management Studio. In the first, I entered and executed this code:

 

USE SnapshotTest;

SET TRANSACTION ISOLATION LEVEL SNAPSHOT;

BEGIN TRANSACTION;

— Check to see that the customer has no orders

SELECT *

FROM   Orders

WHERE  CustID = 1;

— Remove the customer

DELETE Customers

WHERE  CustID = 1;

— Twiddle thumbs for 10 seconds before commiting

WAITFOR DELAY ‘0:00:10’;

COMMIT TRANSACTION;

go

— Check results

SELECT * FROM Customers;

SELECT * FROM Orders;

go

 

In the second window, I entered this code, and I ensured that I started this some 5 seconds after starting the query in the first window.

 

USE SnapshotTest;

SET TRANSACTION ISOLATION LEVEL SNAPSHOT;

BEGIN TRANSACTION;

— Check to see that the customer exists

SELECT *

FROM   Customers

WHERE  CustID = 1;

— Insert an order for the customer

INSERT INTO Orders (OrderID, OrderType, CustID)

VALUES (‘Order01’, ‘A’, 1);

— No need to wait here. COMMIT right now.

COMMIT TRANSACTION;

go

— Check results

SELECT * FROM Customers;

SELECT * FROM Orders;

go

 

The second transaction finished directly, indicating that the reader (the user-defined function) was not blocked by the writer (the other connection). The results indicated that the order was inserted just fine, and that customer 1 still existed (after all, the DELETE from the other transaction was not yet committed and snapshot isolation hides those uncommitted changes from me). However, five seconds later the other transaction was finished as well, and now I did have a type A order with a non existing customer!

 

To fix this, I should probably try to have the function disable snapshot isolation, just as I did in the trigger in the previous instalment. Here’s the changed code:

 

CREATE FUNCTION dbo.CustExists (@CustID int)

RETURNS char(1)

AS

BEGIN

  IF (SELECT transaction_isolation_level

      FROM   sys.dm_exec_session

      WHERE  session_id = @@SPID) = 5

    SET TRANSACTION ISOLATION LEVEL READ COMMITTED

  DECLARE @retval char(1)

  IF EXISTS (SELECT *

             FROM   dbo.Customers

             WHERE  CustID = @CustID)

     SET @retval = ‘Y’

  ELSE

     SET @retval = ‘N’

  RETURN @retval

END;

 

And here’s the output. Ouch!

 

Msg 443, Level 16, State 15, Procedure CustExists, Line 8

Invalid use of side-effecting or time-dependent operator in ‘SET TRANSACTION ISOLATION LEVEL’ within a function.

 

Does that means I’m busted? No, not quite. Instead of using SET to force a different isolation level, I can also use table hints. The catch is that I can’t make the chosen isolation level dependant on the existing level, so if the function is called from a transaction that uses SERIALIZABLE isolation, it will also be overridden. Also note that the hint must be repeated for each table used. In this example, it’s only needed once:

 

CREATE FUNCTION dbo.CustExists (@CustID int)

RETURNS char(1)

AS

BEGIN

  DECLARE @retval char(1)

  IF EXISTS (SELECT *

             FROM   dbo.Customers WITH (READCOMMITTEDLOCK)

             WHERE  CustID = @CustID)

     SET @retval = ‘Y’

  ELSE

     SET @retval = ‘N’

  RETURN @retval

END;

 

With this version of the function, the snapshot isolation level will again be effectively negated. Repeating the tests above, I now see that the second transaction has to wait for the first to commit its changes, and after that it throws a constraint violation error.

 

Another quite (ahem!) “interesting” method of maintaining integrity is the use of a view WITH CHECK OPTION. The idea is to filter “illegal” data out of the view, remove modification access to the table and give modification access to the view instead. The WITH CHECK OPTION makes SQL Server throw an error when a row is inserted that would not be included in the view, or when a row is modified such that it would fall out of the view. This is a pretty creative way to enforce constraints; I’d never have thought of it until I saw this as a suggestion in a newsgroup posting by Alexander Kuznetsov (thanks, Alexander!). Here’s how I used this technique to enforce the “Type A must be existing customer” constraint in my example. Note that this technique, like the user-defined function, only works to prevent violations when inserting into or updating the orders table – you can still delete all customers and get no complaints from SQL Server!

 

CREATE VIEW LegalOrders

AS

SELECT OrderID, OrderType, CustID

FROM   dbo.Orders AS o

WHERE  OrderType <> ‘A’

OR EXISTS (SELECT *

           FROM   dbo.Customers AS c

           WHERE  c.CustID = o.CustID)

WITH CHECK OPTION;

 

After defining this view, I can still violate the business constraint when inserting into the base table Orders, but not when inserting into the view LegalOrders. Just as we wanted. And, not entirely unexpected, inserting into LegalOrders even works if I refer to a customer that has just been removed in a different, uncommitted transaction, thanks to the wonders of snapshot isolation.

 

Since a view can only consist of a single SELECT statement, I won’t even try to use SET to change the transaction isolation level. But I will try what happens if I add locking hints:

 

CREATE VIEW LegalOrders

AS

SELECT OrderID, OrderType, CustID

FROM   dbo.Orders AS o WITH (READCOMMITTEDLOCK)

WHERE  OrderType <> ‘A’

OR EXISTS (SELECT *

           FROM   dbo.Customers AS c WITH (READCOMMITTEDLOCK)

           WHERE  c.CustID = o.CustID)

WITH CHECK OPTION;

 

And sure enough, we again lose the concurrency advantage of snapshot isolation, but data integrity is preserved.

 

And that brings me to the end of this four-part series on snapshot isolation. The most important conclusions, for me, are:

 

·        SQL Server will automatically temporarily disable snapshot isolation when checking FOREIGN KEY constraints. This is basically a good thing, since it ensures the integrity of my data, but it does severely limit the concurrency benefit that snapshot isolation is supposed to deliver.

 

·        If you use triggers, user-defined functions or any other technique to check integrity of your data, then you must be aware of the potential damage that snapshot isolation can do to your database. You should use either SET TRANSACTION ISOLATION LEVEL or locking hints to force at least read committed isolation. Even though this will reduce your database’s concurrency, it will at least ensure that integrity is maintained.

 

Fun with ambiguous table names

Earlier today, I realised that Microsoft has forgotten to include some keywords in the list of reserved keywords. Now, a wise developer will still take care to omit those names when naming tables – but a bored developer can have loads of fun exploring the effects!

 

The keywords I am referring to are inserted and deleted. Everyone who ever coded a trigger knows that they refer to the pseudo-tables that hold the before and after image of all rows affected by the triggering DML statement. But since they’re not reserved keywords, it’s perfectly legal to name a column “inserted”.

 

Of course, things get confusing when you name your table “inserted” and create a trigger on that table – how is SQL Server supposed to know what you mean when you write “inserted”? As an example, look at the following code. Quiz question: try to predict the results before executing the code; let me know if your prediction was right.

 

CREATE TABLE inserted (a int PRIMARY KEY);

INSERT INTO inserted VALUES(1);

go

CREATE TRIGGER tst

ON inserted AFTER INSERT

AS SELECT * FROM inserted;

go

INSERT INTO inserted VALUES(2);

SELECT * FROM inserted;

DROP TABLE inserted;

go

 

My prediction was an error message because of the ambiguous table name. Boy was I wrong!

 

The results of the code above prove that SQL Server will use the pseudo-table if I write “inserted” in the inside of a trigger, even if there is a table with the same name. So what do I do if I need to refer to the rows in that table from a trigger?

 

Actually, that’s a lot easier than it sounds – just follow long-standing best practice: prefix all table names with owner (SQL Server 2000) or schema (SQL Server 2005). Change the example above to the one below to see how both the “real” table “inserted” and the pseudo-table can be used within the trigger:

 

CREATE TABLE inserted (a int PRIMARY KEY);

INSERT INTO inserted VALUES(1);

go

CREATE TRIGGER tst ON inserted AFTER INSERT

AS

SELECT * FROM inserted;

SELECT * FROM dbo.inserted;

go

INSERT INTO inserted VALUES(2);

SELECT * FROM inserted;

DROP TABLE inserted;

go

 

Intriguingly, you can even join inserted and dbo.inserted in a single query and refer to columns from both tables, as long as you keep repeating the dbo qualifier each time you refer to a column from the real table. How’s that for hard to grasp coding, huh?

 

However, things get even more interesting if we leave SQL Server 2000 behind and explore one of the new features SQL Server 2005 has to offer: the OUTPUT clause for INSERT, UPDATE and DELETE statements. Since the SQL Server development team decided to overload the (still unreserved) keywords inserted and deleted with a second meaning, things start to get really interesting here!

 

The real problem in SQL Server 2005 (and the exact issue that caused me to start investigating this issue) is that you don’t even need to choose your table names badly to run into trouble. Regardless of table name, you are challenged by the ambiguity of the inserted keyword as soon as you have to use the OUTPUT clause within a trigger. (In fact, exactly that happened to me at work yesterday; this was what prompted me to do some further investigation today). Here’s a simplified example – anyone care to take a bet on the outcome?

 

CREATE TABLE testtab (pk int NOT NULL PRIMARY KEY,

                      a char(1) NOT NULL,

                      b char(1) NOT NULL);

go

CREATE TRIGGER testtrig

ON testtab AFTER INSERT

AS UPDATE     testtab

   SET        a = inserted.b,

              b = inserted.a

   OUTPUT     inserted.a, inserted.b

   FROM       inserted

   INNER JOIN testtab

         ON   testtab.pk = inserted.pk;

go

INSERT INTO testtab (pk, a, b) VALUES (1, ‘a’, ‘b’);

go

DROP TABLE testtab;

go

 

Running the code above shows that in this OUTPUT clause, the inserted keyword is taken to refer to the new version of the rows affected by the UPDATE statement, not to the trigger’s pseudo-table that holds the newly inserted rows. Now, what should I do if I actually wanted to output data from the trigger’s pseudo-table here? I can’t use dbo.inserted here, since that would refer to a real table. And yet I should be able to refer to the pseudo-table, as the documentation of the OUTPUT clause clearly states that tables used in the FROM clause can also be used in the OUTPUT clause.

 

The only solution I could find is to use an alias in the FROM clause, so that we can use the alias to refer to the inserted pseudo-table in the OUTPUT clause:

 

CREATE TABLE testtab (pk int NOT NULL PRIMARY KEY,

                      a char(1) NOT NULL,

                      b char(1) NOT NULL);

go

CREATE TRIGGER testtrig

ON testtab AFTER INSERT

AS UPDATE     testtab

   SET        a = i.b,

              b = i.a

   OUTPUT     i.a, i.b

   FROM       inserted AS i

   INNER JOIN testtab

         ON   testtab.pk = i.pk;

go

INSERT INTO testtab (pk, a, b) VALUES (1, ‘a’, ‘b’);

go

DROP TABLE testtab;

go

 

Now to get really overboard with ambiguity, I decided to create an example that refers to three versions of inserted on a single line – the new rows in the UPDATE statement, the rows in the trigger’s pseudo-table and the rows in the permanent table named “inserted”. Please, don’t ever try to do this at home, and even less at work – unless you are writing a blog or if you want to see your code on The Daily WTF.

 

CREATE TABLE inserted (pk int NOT NULL PRIMARY KEY,

                       a char(1) NOT NULL,

                       b char(1) NOT NULL,

                       c int NOT NULL);

CREATE TABLE other (pk int NOT NULL PRIMARY KEY,

                    a char(1) NOT NULL,

                    b char(1) NOT NULL,

                    c int NOT NULL)

INSERT INTO other (pk, a, b, c) VALUES (1, ‘a’, ‘b’, 1)

go

CREATE TRIGGER ugly

ON inserted AFTER INSERT

AS UPDATE     dbo.inserted

   SET        c = 5;

   UPDATE     other

   SET        a = i.b,

              b = i.a,

              c = dbo.inserted.c + 1

   OUTPUT     inserted.a, i.b, dbo.inserted.c

   FROM       other

   INNER JOIN inserted AS i

         ON   i.pk = other.pk

   INNER JOIN dbo.inserted

         ON   inserted.pk = i.pk;

go

INSERT INTO inserted (pk, a, b, c) VALUES (1, ‘a’, ‘b’, 1);

go

DROP TABLE inserted;

DROP TABLE other;

go

Snapshot isolation: A threat for integrity? (Part 3)

Last month, I showed how snapshot integrity can really mess up your triggers, promised you a workaround, and then went on holiday. Some events in my life kept me from posting the promised workaround for longer than intended, so I hope that you haven’t been holding your breath for it! J

 

The workaround is actually quite simple. Just remember the first part of this series, where I showed how SQL Server 2005 prevents violation of foreign key constraints when using snapshot isolation – it automatically and silently switches to a less concurrent isolation level. Of course, if Microsoft can do it, then so can I!

 

I’ll use the same sample I did in the previous part, so there’s no need to repeat them here. You can copy the DDL from my last post. To mimic what Microsoft does when checking FOREIGN KEY constraints (i.e. automatically disable snapshot integrity) I added the command below as the very first command in both triggers:

 

SET TRANSACTION ISOLATION LEVEL READ COMMITTED;

 

This change is all I need to fix last month’s bad data. I don’t even have to reset the isolation level to snapshot at the end of the trigger code: since changing the isolation level in a trigger or stored procedure never affects the isolation level of the calling procedure, resetting the isolation level at the end of the trigger would do nothing but waste a few CPU cycles.

 

Now, when I rerun my tests, the second connection waits for the first one to finish, then aborts with an error message. Just as when I tested the FOREIGN KEY constraint, except that the error message is now different from the awfully non-descriptive error message from my first tests:

 

Msg 50000, Level 16, State 1, Procedure Customers_d, Line 13

Customers with type A orders can’t be deleted

Msg 3609, Level 16, State 1, Line 9

The transaction ended in the trigger. The batch has been aborted.

 

That’s it. Just one simple modification to fix the problems, and no catch, right? No, of course not – there is a catch. There always is. You see, these triggers will also execute if customers are deleted and if orders are inserted or updated from a procedure that uses a higher isolation level. If I set my isolation level to repeatable read, I expect the code in the trigger to honour that isolation level, not to disregard it!

 

To ensure that the isolation level is only changed to read committed if it was snapshot isolation, I’ll have to enclose the SET command in an IF statement that tests the current isolation level. Unfortunately, that’s not as straightforward as it sounds. The current isolation level is available from DBCC USEROPTIONS, which doesn’t return a parameter or return code, but produces a table. I’ll have to catch that output into a temporary table, then find the row with the isolation level and use that in my IF statement. Here is the code that has to go at the beginning of booth triggers, instead of the single line above:

 

CREATE TABLE #Options

        (OptName varchar(128) PRIMARY KEY,

         Value varchar(50));

INSERT INTO #Options (OptName, Value)

EXEC (‘DBCC USEROPTIONS WITH NO_INFOMSGS;’);

IF (SELECT Value

    FROM   #Options

    WHERE  OptName = ‘isolation level’) = ‘snapshot’

BEGIN;

   SET TRANSACTION ISOLATION LEVEL READ COMMITTED;

END;

 

Repeating my tests shows that this code still escapes from snapshot isolation to read committed isolation to ensure that my data integrity can not be violated. But I now also know that the isolation level will not be changed if the trigger was invoked with any isolation level other than snapshot isolation.

 

The downside of this workaround is that improved data integrity goes hand in hand with reduced concurrency. The whole reason why snapshot isolation has been added to the product is to ensure that people who have to read data and people who have to change data won’t block each other. But since Microsoft will automatically disable snapshot isolation when checking foreign key constraints, and I disable snapshot isolation in my triggers, then there are not too many situations left for readers and writers to co-exist without blocking.

 

In the last part of this series, I’ll look at some other, less obvious methods that can be used to guard data integrity, and check how they are affected by snapshot integrity.

Snapshot isolation: A threat for integrity? (Part 2)

In the first part of this series, I showed how SQL Server 2005 prevents violation of foreign key constraints when using snapshot isolation by automatically and silently using a less concurrent isolation level. In this part, I’ll show how snapshot isolation can be used to really mess up your data.

 

I’ll use the same sample tables I did in the first part, with one difference: only type A orders have to be for an existing customer; type B orders still need to have a customer ID included, but it doesn’t have to refer to an existing row in the Customers table. This business rule can’t be enforced by a foreign key constraint (at least not without changing the schema to include a computed column), so we’ll have to use something else. But first, let’s create the test database, the tables, and some test customers.

 

USE master;

go

IF EXISTS (SELECT FROM sys.databases WHERE name = ‘SnapshotTest’)

  BEGIN;

  ALTER DATABASE SnapshotTest

    SET SINGLE_USER

    WITH ROLLBACK IMMEDIATE;

  DROP DATABASE SnapshotTest;

  END;

go

CREATE DATABASE SnapshotTest;

go

ALTER DATABASE SnapshotTest

SET ALLOW_SNAPSHOT_ISOLATION ON;

go

USE SnapshotTest;

go

CREATE TABLE Customers

      (CustID int NOT NULL PRIMARY KEY,

       CustName varchar(40) NOT NULL

      );

CREATE TABLE Orders

      (OrderID char(7) NOT NULL PRIMARY KEY,

       OrderType char(1) NOT NULL CHECK (OrderType IN (‘A’, ‘B’)),

       CustID int NOT NULL

      );

INSERT INTO Customers (CustID, CustName)

VALUES (1, ‘First test customer’);

INSERT INTO Customers (CustID, CustName)

VALUES (2, ‘Second test customer’);

go

 

One way to enforce this constraint is through triggers. New and updated type A orders should be checked to see if they refer to an existing customer, and deleted customers have to be checked for any type A orders referring to them. Actually, updated customers should be checked as well since SQL Server allows the change of columns included in the primary key, but for brevity sake, I’ll leave that out for this example. I’ll also use the bare minimum of error handling – don’t consider the triggers below as good examples for error handling in real-life applications!

 

USE SnapshotTest;

go

CREATE TRIGGER Orders_iu

ON Orders

AFTER INSERT, UPDATE

AS

IF EXISTS

  (SELECT   

   FROM      inserted AS i

   WHERE     i.OrderType = ‘A’

   AND NOT EXISTS

     (SELECT

      FROM   Customers AS c

      WHERE  c.CustID = i.CustID))

BEGIN;

   RAISERROR (‘Type A orders must refer to existing customers’, 16, 1);

   ROLLBACK TRANSACTION;

END;

go

CREATE TRIGGER Customers_d

ON Customers

AFTER DELETE

AS

IF EXISTS

  (SELECT    

   FROM       deleted AS d

   INNER JOIN Orders AS o

         ON   o.CustID = d.CustID

   WHERE      o.OrderType = ‘A’)

BEGIN;

   RAISERROR (‘Customers with type A orders can”t be deleted’, 16, 1);

   ROLLBACK TRANSACTION;

END;

go

 

With those triggers installed, it’s time to check if enabling snapshot isolation manages to mess up our integrity. I’ll use the same tests I did in the first part. Here’s the SQL for connection 1.

 

USE SnapshotTest;

SET TRANSACTION ISOLATION LEVEL SNAPSHOT;

BEGIN TRANSACTION;

— Check to see that the customer exists

SELECT *

FROM   Customers

WHERE  CustID = 1;

— Insert an order for the customer

INSERT INTO Orders (OrderID, OrderType, CustID)

VALUES (‘Order01’, ‘A’, 1);

— Twiddle thumbs for 10 seconds before commiting

WAITFOR DELAY ‘0:00:10’;

COMMIT TRANSACTION;

go

— Check results

SELECT * FROM Customers;

SELECT * FROM Orders;

go

 

And here’s the SQL for connection 2.

 

USE SnapshotTest;

SET TRANSACTION ISOLATION LEVEL SNAPSHOT;

BEGIN TRANSACTION;

— Check to see that the customer has no orders

SELECT *

FROM   Orders

WHERE  CustID = 1;

— Remove the customer

DELETE Customers

WHERE  CustID = 1;

— Twiddle thumbs for 10 seconds before commiting

WAITFOR DELAY ‘0:00:10’;

COMMIT TRANSACTION;

go

— Check results

SELECT * FROM Customers;

SELECT * FROM Orders;

go

 

I start executing the SQL in both connections. They don’t block each other (as was to be expected since we’re using snapshot isolation) – and the end result is a violation of our business rules. Regardless of which connection starts first, the end result after executing both connections is always this:

 

CustID      CustName

———– —————————————-

2           Second test customer

 

OrderID OrderType CustID

——- ——— ———–

Order01 A         1

 

Indeed – we now have a type A order referring to a non-existing customer, exactly the scenario that we wanted to avoid.

 

For now, the bottom line is that snapshot isolation and triggers don’t match. But don’t tear down and re-build your code yet – there is a workaround. I’ll get to that in the next part of this series.

Snapshot isolation: A threat for integrity? (Part 1)

One of the great new features of SQL Server 2005 is the snapshot isolation level. But exactly how safe is that feature? Can you still guarantee your data integrity if you use snapshot isolation level?

 

With most forms of data integrity, this is not an issue. But with referential integrity, it might be – after all, checking referential integrity usually requires the database to read data in other tables than the one being updated. Since readers and writers are supposed not to block each other if you use snapshot isolation, it’s easy to imagine a scenario where two concurrent data modifications try to make changes that collide with each other, yet both are allowed because of the snapshot isolation level.

 

Since this is quite a broad subject, I’ll write at least two blog entries about it. In this first instalment, I’ll look into how SQL Server handles this potential thread to integrity for the most common form of referential integrity: the foreign key constraint. Since testing is the only way to find out, I used the following code to create a test database with two tables and one foreign key constraint.

 

USE master;

go

IF EXISTS (SELECT * FROM sys.databases WHERE name = ‘SnapshotTest’)

  BEGIN;

  DROP DATABASE SnapshotTest;

  END;

go

CREATE DATABASE SnapshotTest;

go

ALTER DATABASE SnapshotTest

SET ALLOW_SNAPSHOT_ISOLATION ON;

go

USE SnapshotTest;

go

CREATE TABLE Customers

      (CustID int NOT NULL PRIMARY KEY,

       CustName varchar(40) NOT NULL

      );

CREATE TABLE Orders

      (OrderID char(7) NOT NULL PRIMARY KEY,

       OrderType char(1) CHECK (OrderType IN (‘A’, ‘B’)),

       CustID int NOT NULL REFERENCES Customers (CustID)

      );

INSERT INTO Customers (CustID, CustName)

VALUES (1, ‘First test customer’);

INSERT INTO Customers (CustID, CustName)

VALUES (2, ‘Second test customer’);

go

 

With these two tables all set up, it’s time to start some testing. Let’s see if we are able to add an order for our only customer in one connection and at the same time remove that customer in another connection. Here’s the SQL for connection 1.

 

USE SnapshotTest;

SET TRANSACTION ISOLATION LEVEL SNAPSHOT;

BEGIN TRANSACTION;

— Check to see that the customer exists

SELECT *

FROM   Customers

WHERE  CustID = 1;

— Insert an order for the customer

INSERT INTO Orders (OrderID, OrderType, CustID)

VALUES (‘Order01’, ‘A’, 1);

— Twiddle thumbs for 10 seconds before commiting

WAITFOR DELAY ‘0:00:10’;

COMMIT TRANSACTION;

go

— Check results

SELECT * FROM Customers;

SELECT * FROM Orders;

go

 

And here’s the SQL for connection 2.

 

USE SnapshotTest;

SET TRANSACTION ISOLATION LEVEL SNAPSHOT;

BEGIN TRANSACTION;

— Check to see that the customer has no orders

SELECT *

FROM   Orders

WHERE  CustID = 1;

— Remove the customer

DELETE Customers

WHERE  CustID = 1;

— Twiddle thumbs for 10 seconds before commiting

WAITFOR DELAY ‘0:00:10’;

COMMIT TRANSACTION;

go

— Check results

SELECT * FROM Customers;

SELECT * FROM Orders;

go

 

If I first start the SQL for connection 1, then (using less than 10 seconds) switch to connection 2 and start that SQL, the results are both encouraging and disencouraging at the same time. The SELECT statement at the beginning of the transaction is not blocked by the INSERT from the other transaction and shows the stale data, as expected in the snapshot isolation level. However, the DELETE statement (that, under the covers, uses the exact same read operation to check the foreign key constraint), is blocked.

 

The good news is that this means that even with snapshot isolation, it is impossible to violate a foreign key constraint. Considering the importance and value of the data that is sitting in our databases and the enormous costs involved with cleaning up bad data in databases that fail to guard integrity, this is Very Good News indeed.

 

But there’s bad news as well. Keeping our data integrity safe does come at a price. It means that the entire commercial blurb about how snapshot isolation improves concurrency because readers and writers no longer block each other has to be taken with a grain of salt. Apparently, writers do block readers if those readers are tasked with checking a foreign key constraint. And that’s not limited to situations that might lead to a violation of referential integrity – change the SQL for connection 2 to remove the second test customer instead of the first and you’ll see two transactions that should be able to execute simultaneously, yet still are blocking each other. Using snapshot isolation might not yield the concurrency gain you are hoping for!

 

Another bad thing is the choice of error messages. If you run the SQL above, you’ll get this error message from the second connection once the first connection has committed the changes:

 

Msg 3960, Level 16, State 1, Line 2

Snapshot isolation transaction aborted due to update conflict. You cannot use snapshot isolation to access table ‘dbo.Orders’ directly or indirectly in database ‘SnapshotTest’ to update, delete, or insert the row that has been modified or deleted by another transaction. Retry the transaction or change the isolation level for the update/delete statement.

 

If you change the SQL in the second connection to delete the second test customer, or if you change the SQL in the first transaction to ROLLBACK rather than COMMIT the changes, the second connection will still be blocked, but after the first connection finishes, the second connection continues, and you’ll never see any warning or error message to explain why this connection was blocked. If you ever get called in to investigate slowness in a database that uses snapshot isolation, would you consider that updates to different tables might be blocking each other? Until performing the tests above, I would have started looking elsewhere! My suggestion to Microsoft would be to change the error messages – in both cases, a warning message stating that snapshot isolation has temporarily been put out of effect should be given as soon as the second connection is blocked. Once the first connection ends, the second connection should either receive the normal foreign key constraint violation error, or it should continue without further messages.

 

To wrap it up, we can conclude that Microsoft’s SQL Server team has been smart enough to make sure that snapshot isolation won’t allow violation of foreign key constraints, but at the price of temporarily disabling snapshot isolation and thereby reducing concurrency. And unfortunately, they have failed to make trouble-shooting easier by causing SQL Server to send a warning message to the client if this happens.

 

That concludes the first part of this series. In the next part, I’ll be looking at some other, more obscure sorts of referential integrity in conjunction with snapshot isolation. Feel free to experiment with the sample code above while waiting – and if you see anything worth mentioning, be sure to post a comment!

 

By continuing to use the site, you agree to the use of cookies. more information

The cookie settings on this website are set to "allow cookies" to give you the best browsing experience possible. If you continue to use this website without changing your cookie settings or you click "Accept" below then you are consenting to this.

Close