Query Plans and Read Committed Isolation Level

Last week I looked at how concurrent updates may cause a scan running at read committed isolation level to return the same row multiple times or to miss a row entirely.  This week I'm going to take a look at how concurrent updates may affect slightly more complex query plans.

Nested Loops Join

Let's begin by considering this simple query:

create table Customers (CustId int primary key, LastName varchar(30))
insert Customers values (11, 'Doe')

create table Orders (OrderId int primary key, CustId int foreign key references Customers, Discount float)
insert Orders values (1, 11, 0)
insert Orders values (2, 11, 0)

select * from Orders O join Customers C on O.CustId = C.CustId

The plan for this query uses a nested loops join:

  |--Nested Loops(Inner Join, OUTER REFERENCES:([O].[CustId]))
       |--Clustered Index Scan(OBJECT:([Orders].[PK__Orders] AS [O]))
       |--Clustered Index Seek(OBJECT:([Customers].[PK__Customers] AS [C]), SEEK:([C].[CustId]= [O].[CustId]))

Recall that the nested loops join executes its inner input once for each row from its outer input.  In this example, the Orders table is the outer table and we have two orders so we will execute two seeks of the Customers table.  Moreover, both orders were placed by the same customer.  What happens if we change the customer data between the two index seeks?  We can setup an experiment to find out.  First, lock the second order in session 1:

begin tran
update Orders set Discount = 0.1 where OrderId = 2

Now, in session 2 run the join:

select * from Orders O join Customers C on O.CustId = C.CustId

The join will scan the first order and join it with the Customers table.  Then it will try to scan the second order and block waiting for the lock held by session 1.  Finally, in session 1 update the customer name and commit the transaction to release the lock and allow the query in session 2 to complete:

update Customers set LastName = 'Smith' where CustId = 11
commit tran

Here are the results of the join:

 OrderId     CustId      Discount               CustId      LastName
----------- ----------- ---------------------- ----------- ------------------------------
1           11          0                      11          Doe
2           11          0.1                    11          Smith

Notice that the customer data is different for the two orders even though the customer id is the same!

Full Outer Join

Next, consider the following full outer join query:

create table t1 (a1 int, b1 int)
insert t1 values (1, 1)
insert t1 values (2, 2)

create table t2 (a2 int, b2 int)
insert t2 values (1, 1)

select * from t1 full outer loop join t2 on t1.a1 = t2.a2

The nested loops join does not support full outer joins directly so this query generates a two part plan (which I described in my original nested loops join post):

  |--Concatenation
       |--Nested Loops(Left Outer Join, WHERE:([t1].[a1]=[t2].[a2]))
       |    |--Table Scan(OBJECT:([t1]))
       |    |--Table Scan(OBJECT:([t2]))
       |--Compute Scalar(DEFINE:([t1].[a1]=NULL, [t1].[b1]=NULL))
            |--Nested Loops(Left Anti Semi Join, WHERE:([t1].[a1]=[t2].[a2]))
                 |--Table Scan(OBJECT:([t2]))
                 |--Table Scan(OBJECT:([t1]))

Although the original query only references each table onces, this query plan includes two scans of each table.  It is possible for the data to change between the two scans.  Let's see what happens.  Begin by locking the second row of t1 in session 1:

begin tran
update t1 set a1 = 2 where a1 = 2

Now, in session 2 run the join:

select * from t1 full outer loop join t2 on t1.a1 = t2.a2

The query plan begins by scanning the first row of t1 and joining it with t2 (where there is a matching row).  It then blocks.  Finally, in session 1 delete the first row from t1:

delete t1 where a1 = 1
commit tran

When the join query plan resumes it scans t2 and performs an anti-semi join with t1 to search for rows that exist in t2 and not in t1.  These rows are required for the full outer join result, but cannot be generated by the left outer nested loops join.  Keep in mind that by this point in the query plan we have already joined the first row of t1 with the row in t2.  However, because we deleted the row from t1, the anti-semi join finds the row in t2, cannot match it with a row in t1, and generates a null extended row.  Here is the result:

 a1          b1          a2          b2
----------- ----------- ----------- -----------
1           1           1           1
2           2           NULL        NULL
NULL        NULL        1           1

As the above analysis suggests, the result includes both a joined and a null extended row!

CLARIFICATION 8/26/2008: The above example works as I originally described if it is executed in tempdb. However, the SELECT statement in session 2 may not block as described if the example is executed in other databases due to an optimization where SQL Server avoids acquiring read committed locks when it knows that no data has changed on a page. If you encounter this problem, either run this example in tempdb or change the UPDATE statement in session 1 so that it actually changes the value of column b1. For example, try "update t1 set b1 = 12 where a1 = 2".

Index Intersection

Finally, consider the following query:

create table t (a int primary key, b int, c int, check (b = c))
create index tb on t(b)
create index tc on t(c)

insert t values (1, 1, 1)
insert t values (2, 2, 2)

select * from t with (index(tb, tc))

I've forced an index intersection plan.  The query plan scans and joins columns from both non-clustered indexes to form the final result:

  |--Hash Match(Inner Join, HASH:([t].[a])=([t].[a]))
       |--Index Scan(OBJECT:([t].[tb]))
       |--Index Scan(OBJECT:([t].[tc]))

Recall that the hash join scans its entire build input (tb) and then scans its entire probe input (tc).  What happens if the contents of the indexes change between the two scans?  Once again, let's find out.  Begin by locking the second row in session 1:

begin tran
update t set b = 4, c = 4 where a = 2

Now, in session 2 run the select statement:

select * from t with (index(tb, tc))

The inex scan of tb will read the first row and then block on the second row.  Finally, in session 1, update the first row:

update t set b = 3, c = 3 where a = 1
commit tran

The select statement resumes, finishes the scan of index tb, scans index tc where it finds the updated first row, and returns a joined row that consists partially of a row prior to the update and partially of a row after the update:

 a           b           c
----------- ----------- -----------
1           1           3
2           4           4

Notice that this result even seems to violate the check constraint!

Summary

I've demonstrated three ways that queries may behave unexpectedly when running in read committed isolation level.  I want to emphasize that these results are not incorrect.  SQL Server guarantees that the committed data is consistent at all times and does not permit any constraints to be violated.  These results are merely a consequence of running at a relatively low isolation level.  If we repeat the above experiments with snapshot read committed enabled or at a higher isolation level, we do not see these results.  The benefit of read committed is higher concurrency with less blocking and fewer deadlocks.  The disadvantage is lower consistency guarantees.

Comments

• Anonymous
  May 15, 2007
  The comment has been removed