Deadlocks caused by Missing Indexes in SQL Server

In today’s blog posting I want to demonstrate how missing indexes on tables can cause deadlocks in SQL Server. For the preparation of the test scenario the following code creates 2 tables and populates both tables with 4 records.

-- Create a table without any indexes
CREATE TABLE Table1
(
	Column1 INT,
	Column2 INT
)
GO

-- Insert a few record
INSERT INTO Table1 VALUES (1, 1)
INSERT INTO Table1 VALUES (2, 2)
INSERT INTO Table1 VALUES (3, 3)
INSERT INTO Table1 VALUES (4, 4)
GO

-- Create a table without any indexes
CREATE TABLE Table2
(
	Column1 INT,
	Column2 INT
)
GO

-- Insert a few record
INSERT INTO Table2 VALUES (1, 1)
INSERT INTO Table2 VALUES (2, 2)
INSERT INTO Table2 VALUES (3, 3)
INSERT INTO Table2 VALUES (4, 4)
GO

Before I show you the actual deadlock repro, the following code shows a simple UPDATE statement that updates a specific row in the first table.

-- Acquires an Exclusive Lock on the row
UPDATE Table1 SET Column1 = 3 WHERE Column2 = 1

Because we have no index defined on Column2, the Query Optimizer has to choose a Table Scan operator in the execution plan to find the qualifying rows for our UPDATE statement:

This means that we have to scan the complete heap table to find the one row we want to update. In that case SQL Server locks the first row in the table with an Exclusive Lock. When you run in a different session a SELECT statement where you reference another “later occurring” row in the heap table, the Table Scan operator will block, because first you have to read all the “earlier occurring” rows of the heap table to actually get to the row that you have logically requested in your query.

-- This query now requests a Shared Lock, but get's blocked, because the other session/transaction has an Exclusive Lock on one row, that is currently updated
SELECT Column1 FROM Table1
WHERE Column2 = 4

A Table Scan by default means that you have to scan the whole table, and therefore you have to acquire a Shared Lock on every record – even on records that you have not logically requested. This situation can lead now to a deadlock situation if you access the 2 tables in the 2 different sessions in a different order, and when you try to write and read from both tables. The following code shows the transaction from the first query:

BEGIN TRANSACTION

-- Acquires an Exclusive Lock on the row
UPDATE Table1 SET Column1 = 3 WHERE Column2 = 1

-- Execute the query from Session 2...
-- This query acquires an Exclusive Lock on one row from Table2...

-- This query now requests a Shared Lock, but get's blocked, because the other session/transaction has an Exclusive Lock on one row, that is currently updated
SELECT Column1 FROM Table2
WHERE Column2 = 3

ROLLBACK TRANSACTION
GO

And the following listing shows the code from the 2nd transaction:

BEGIN TRANSACTION

-- Acquires an Exclusive Lock on the row
UPDATE Table2 SET Column1 = 5 WHERE Column2 = 2

-- Continue with the query from Session 2...
-- This query now requests a Shared Lock, but get's blocked, because the other session/transaction has an Exclusive Lock on one row, that is currently updated

-- This query now requests a Shared Lock, but get's blocked, because the other session/transaction has an Exclusive Lock on one row, that is currently updated
SELECT Column1 FROM Table1
WHERE Column2 = 4

ROLLBACK TRANSACTION
GO

As you can see from both transactions, the two tables are accessed in a different order. If the timing is now right, running both transactions at the same time can lead to a deadlock situation. Imagine the following execution sequence:

1. The first transaction runs the UPDATE statement on Table1.
2. The second transaction runs the UPDATE statement on Table2.
3. The first transaction runs the SELECT statement on Table2. This SELECT statement will block, because the Table Scan operator wants to acquire a Shared Lock on a row that is already exclusively locked by the second transaction.
4. The second transaction runs the SELECT statement on Table1. This SELECT statement will block, because the Table Scan operator wants to acquire a Shared Lock on a row that is already exclusively locked by the first transaction.

The following picture illustrates this deadlock situation.

Both transaction are now blocking each other, therefore you cause a deadlock in SQL Server. In that case the Deadlock Monitor background process kicks in, and performs a rollback of the cheapest transaction (based on the number of bytes that the transaction has written to the Transaction Log).

You can resolve this deadlock very easily by providing an index for the Column2 in both tables. In that case SQL Server can perform a Seek operation to find the qualifying rows, and can therefore bypass already locked rows in the leaf level of the index when you perform the SELECT statement:

CREATE NONCLUSTERED INDEX idx_Column2 ON Table1(Column2)
CREATE NONCLUSTERED INDEX idx_Column2 ON Table2(Column2)
GO

The following picture illustrates how the locking situation looks now:

With a Seek operation you can just bypass locked rows in the leaf level of the index, and you can avoid the deadlock that we have been talking about. Therefore it’s always very important that you have a detailed look at your indexing strategy when you see deadlock situations in your database. Indexing is one of the most important things in SQL Server – always remember that!

Thanks for your time,

-Klaus