SQL Server deadlock on temp tables in different connections

I'm getting occasional deadlocks on temp tables in two different connections (at least as far as I can tell, the deadlock graph shows different spids). The deadlock graph (lightly redacted, and with the rest of truncated queries added in) is below. I don't understand how this is possible, because temp tables shouldn't be shared between different connections. These are NOT global temp tables (as you can see). So they shouldn't be able to deadlock. Also confusing, and possibly related, one of the temp table names listed in the deadlock graph is a random string of letters and numbers, which isn't referenced in the stored procedure that is running, like "#B825DAD5". Also a little odd, and again possibly related, the lock mode causing the problem is Sch-M, but there are no schema modifications made to any tables or temp tables in the query. I suppose creating and dropping temp tables could count as schema modifications? But again, they are in different connections. Temp tables are created with CREATE, not SELECT INTO, if that matters. My top suspects right now are either a bug in SQL Server or something strange because there are some nolocks on some of the tables in the query. But I would think someone on the internet would have seen this issue before, and I've found nothing like this in the searches I've tried. There are some references to bugs in SQL server that caused deadlocks between temp tables, but those bus were fixed over ten years ago, and they didn't look exactly the same anyway. Has anyone seen this kind of thing? Can anyone explain those weird temp table names? Does anyone know a workaround or fix? UPDATE t SET Adv = 1 FROM dbo.SQ sq (nolock) JOIN #tmpSDTR t on t.SQUUID = sq.SQUUID and t.DeliverySequence = sq.DeliverySequence JOIN dbo.SQQMetaData m (nolock) on m.SQUUID = t.SQUUID and m.DeliverySequence = t.DeliverySequence WHERE m.Name = 'Adv' and m.Value = 1 Proc [Database Id = 7 Object Id = 1716201164] update t set SQQueueID = q.SQQueueId, SUUID = q.SUUID, SRUUID = r.SRUUID, ProjectKey = q.ProjectID, L = q.L, MQPID = q.MQPId, StatusID = q.StatusID, [Priority] = q.[Priority], CreatedDate = q.CreatedDate, RTID = r.RTID, OrdinalPosition = r.DisplayOrdinal, ProcessID = @ProcessID, SRMetaDataName = md.Name, SRMetaDataValue = md.Value --select * from #tmpSDTR t JOIN dbo.SQQueue q on q.SQUUID = t.SQUUID LEFT OUTER JOIN dbo.SRQueue r on r.SQUUID = q.SQUUID AND r.DeliverySequence = q.DeliverySequence LEFT OUTER JOIN dbo.SRQMetaData md on r.SRUUID = md.SRUUID AND md.DeliverySequence = r.DeliverySequence where t.PCId is null Proc [Database Id = 7 Object Id = 1716201164] **UPDATE 2025/04/07** It looks like we are behind a touch on cumulative updates (we're on 28, current is 32), so we'll be trying to get that upgraded ASAP, but I can't say yet when that will happen. If we get the error again after the CU, I'll post another update here. The stored proc has a bunch of different execution plans listed when I query sys.dm_exec_procedure_stats/sys.dm_exec_query_plan. There were 13 the last time I checked. I downloaded all of them, and they were all identical, EXCEPT for the table name in one small section: You can see that odd temp table name there, and it is the same in all of the plans, EXCEPT for one, where it instead said: Table = "[tmpSDTR_____________________________________________________________________________________________000000001FF8]" There were just 6 executions of this plan, compared to thousands to millions for most other plans. The query referenced in this section is not one of the two that trigger the deadlock, so I don't know if this is related. Anyway, since the plans are pretty much all identical, I don't think parameter sniffing is causing different execution plans. **UPDATE 2025/04/09** Well, we updated to the latest Cumulative Update this morning, and now we have a new mysterious deadlock, but at least it doesn't involve temp tables in different connections. Assuming we don't see this weird deadlock again soon, I'm ready to close out this chapter, and if Martin Smith feels like posting his suggestion as an answer, I'd be happy to accept it.