How does the table scan in an UPDATE WHERE predicated on an unindexed column work?

Question

I was looking into a deadlock caused by two concurrent UPDATE statements:

UPDATE [table] 
SET [column] = 0 
WHERE [unindexed_column] = @id

My understanding is that because the column the WHERE is predicated on is unindexed, a full table scan is performed. For each row, an update lock is acquired. If it matches the WHERE clause, it then upgrades to an exclusive lock and holds it until the statement completes.

The deadlock occurs when session A has an exclusive lock on row 2 and is trying to acquire an update lock on row 1, while session B has an exclusive lock on row 1 and is trying to acquire an update lock on row 2.

The reason for the deadlock makes sense, but I don't understand exactly how the table scan is performed that makes this scenario possible. If the two queries perform the scan in the same order, it seems like the worst case scenario is that one of the queries is blocked on acquiring an update lock until the other query completes and releases it's locks.

How is a table scan performed? Is the order the table rows are scanned in inconsistent? If the update statement fails to acquire an update lock, does it go to the next row and try the previous row again later? What, exactly, makes this deadlock possible?

Answer 1

Order of table scan is never guaranteed. Order in which rows are locked is not guaranteed either. In addition, SQL Server has lock escalation, so you can't really say what the engine decides to lock, row, page, or table itself.

Thus, deadlock may happen even if values of @id are different in concurrent sessions, but rows of interest happened to reside on the same pages. In SQL Server 2008 and higher you can add hint ROWLOCK which reduces chances of lock escalation (but again it's not guaranteed). If UPDATE can't acquire lock it waits (LOCK_TIMEOUT specifies how long it's gonna wait ).