Upsert Deadlock for non-trivial where clause

Question

I'm trying to write some SQL that does an upsert on a fairly complex criteria:

BEGIN TRAN;

  UPDATE LocationLog WITH(SERIALIZABLE)
  SET StartTime = CASE
      WHEN StartTime > @StartTime THEN @StartTime
      ELSE StartTime
    END,
    EndTime = CASE
      WHEN EndTime < @EndTime THEN @EndTime
      ELSE EndTime
    END,
    Updated = GETUTCDATE()
  WHERE Who = @Who
    AND (
        StartTime BETWEEN @RangeStart and @RangeEnd
        or
        EndTime BETWEEN @RangeStart and @RangeEnd
    )
    AND cast(Latitude as decimal(8,5)) = cast(@Latitude as decimal(8, 5))
    AND cast(Longitude as decimal(8,5)) = cast(@Longitude as decimal(8, 5))
    AND (Accuracy = @Accuracy or COALESCE(Accuracy, @Accuracy) is NULL)
    AND (Altitude = @Altitude or COALESCE(Altitude, @Altitude) is NULL)
    AND (AltitudeAccuracy = @AltitudeAccuracy or COALESCE(AltitudeAccuracy, @AltitudeAccuracy) is NULL)
    AND (Heading = @Heading or COALESCE(Heading, @Heading) is NULL)
    AND (Speed = @Speed or COALESCE(Speed, @Speed) is NULL);

  IF @@ROWCOUNT = 0
  BEGIN
    INSERT Position(UUID, Who, StartTime, EndTime, Latitude, Longitude, Accuracy, Altitude, AltitudeAccuracy, Heading, Speed, CreatedTime, Updated)
    VALUES (NEWID(), @Who, @StartTime, @EndTime, @Latitude, @Longitude, @Accuracy, @Altitude, @AltitudeAccuracy, @Heading, @Speed, GETUTCDATE(), GETUTCDATE())
  END

COMMIT TRAN

I'm using the standard "update, if @@rowcount = 0 insert" with a transaction and serializable, which is (near as I can tell) the same as Sam Saffron's "Insert or Update pattern for Sql Server" Blog post, except instead of using a single column ID, I'm using a large set of candidate columns, since there's no way to programmatically produce a single candidate key.

I'm getting deadlock when this is called concurrently, and I can't figure out why. Just to help complete the picture, here's the table definition:

CREATE TABLE LocationLog (
    [UUID] [uniqueidentifier] NOT NULL CONSTRAINT [PK_Position] PRIMARY KEY NONCLUSTERED ,
    [Who] [uniqueidentifier] NOT NULL INDEX [IX_Who],
    [StartTime] [datetime] NOT NULL,
    [EndTime] [datetime] NULL,
    [Latitude] [decimal](9, 6) NOT NULL,
    [Longitude] [decimal](9, 6) NOT NULL,
    [Accuracy] [float] NULL,
    [Altitude] [float] NULL,
    [AltitudeAccuracy] [float] NULL,
    [Heading] [float] NULL,
    [Speed] [float] NULL,
    [CreatedUtc] [datetime] NOT NULL,
    [UpdatedUtc] [datetime] NOT NULL
)

And here's a script that will cause a lot of deadlocks using the above sql: https://dotnetfiddle.net/xkze6l

I'm hoping for two things in an answer:

1. An explanation of why that deadlocks. (I've walked through the code, and I'm not understanding what I got wrong).
2. A fix for the code that will let me do this.

Answer 1

I recommend to read Conditional INSERT/UPDATE Race Condition by Dan Guzman.

Most likely you need to add HOLDLOCK hint to your UPDATE statement. HOLDLOCK is needed to ensure that the lock is held until the end of the transaction.

As far I understand, your WITH(SERIALIZABLE) hint applies only to the UPDATE statement and doesn't affect the next INSERT statement.

This explains why you are getting deadlocks - the lock is held only for the duration of the UPDATE statement, then it is released, which allows another session to squeeze in, before the INSERT.

Maybe you'll need UPDLOCK as well, because even though it is an UPDATE statement, it has to find the rows to update first and the lock should be placed during this SELECT phase, before the UPDATE phase.