Why does SQL Server use INDEX SPOOL when there is already a relevant index during FK check?

Question

I've got two tables in SQL SERVER 2019: Condition table with 2 FK on Reference table. Condition table has appropriate indexes on FK columns. The schema screenshot and SQL script to generate it are given below.

DB Schema

CREATE TABLE [dbo].[Condition](
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [LeftReferenceId] [int] NULL,
    [RightReferenceId] [int] NULL,
PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]

CREATE TABLE [dbo].[Reference](
    [Id] [int] IDENTITY(1,1) NOT NULL,
    [DataType] [int] NULL,
PRIMARY KEY CLUSTERED 
(
    [Id] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
) ON [PRIMARY]
GO
SET IDENTITY_INSERT [dbo].[Condition] ON 
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47458, 94915, 94916)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47459, 94917, 94918)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47460, 94919, 94920)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47461, 94921, 94922)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47462, 94923, 94924)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47463, 94925, 94926)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47464, 94927, 94928)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47465, 94929, 94930)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47466, 94931, 94932)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47467, 94933, 94934)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47468, 94935, 94936)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47469, 94937, 94938)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47470, 94939, 94940)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47471, 94941, 94942)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47472, 94943, 94944)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47473, 94945, 94946)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47474, 94947, 94948)
GO
INSERT [dbo].[Condition] ([Id], [LeftReferenceId], [RightReferenceId]) VALUES (47475, 94949, 94950)
GO
SET IDENTITY_INSERT [dbo].[Condition] OFF
GO
SET IDENTITY_INSERT [dbo].[Reference] ON 
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94915, 0)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94916, 1)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94917, 2)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94918, 3)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94919, 4)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94920, 5)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94921, 0)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94922, 1)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94923, 2)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94924, 3)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94925, 4)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94926, 5)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94927, 0)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94928, 1)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94929, 2)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94930, 3)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94931, 4)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94932, 5)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94933, 0)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94934, 1)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94935, 2)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94936, 3)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94937, 4)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94938, 5)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94939, 0)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94940, 1)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94941, 2)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94942, 3)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94943, 4)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94944, 5)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94945, 0)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94946, 1)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94947, 2)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94948, 3)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94949, 4)
GO
INSERT [dbo].[Reference] ([Id], [DataType]) VALUES (94950, 5)
GO
SET IDENTITY_INSERT [dbo].[Reference] OFF
GO

CREATE NONCLUSTERED INDEX [ix_Condition_LeftReferenceId] ON [dbo].[Condition]
(
    [LeftReferenceId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
GO

CREATE NONCLUSTERED INDEX [ix_Condition_RightReferenceId] ON [dbo].[Condition]
(
    [RightReferenceId] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, SORT_IN_TEMPDB = OFF, DROP_EXISTING = OFF, ONLINE = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON, OPTIMIZE_FOR_SEQUENTIAL_KEY = OFF) ON [PRIMARY]
GO

ALTER TABLE [dbo].[Condition]  WITH CHECK ADD FOREIGN KEY([LeftReferenceId])
REFERENCES [dbo].[Reference] ([Id])
GO

ALTER TABLE [dbo].[Condition]  WITH CHECK ADD FOREIGN KEY([RightReferenceId])
REFERENCES [dbo].[Reference] ([Id])
GO

I've got 3 transactions running in parallel:

Transaction 1

begin transaction

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47458;

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47459;

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47460;

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47461;

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47462;

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47463;

    DELETE [t1]
    FROM
        [Reference] [t1]
    WHERE
        [t1].[Id] IN (94915, 94916, 94917, 94918, 94919, 94920, 94921, 94922, 94923, 94924, 94925, 94926)
    OPTION(LOOP JOIN);

rollback;

Transaction 2

begin transaction

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47464;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47465;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47466;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47467;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47468;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47469;
        
    DELETE [t1]
    FROM
        [Reference] [t1]
    WHERE
        [t1].[Id] IN (94927, 94928, 94929, 94930, 94931, 94932, 94933, 94934, 94935, 94936, 94937, 94938)
    OPTION(LOOP JOIN);

rollback;

Transaction 3

begin transaction

    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47470;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47471;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47472;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47473;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47474;
    
    DELETE [t1]
    FROM
        [Condition] [t1]
    WHERE
        [t1].[Id] = 47475;
    
    DELETE [t1]
    FROM
        [Reference] [t1]
    WHERE
        [t1].[Id] IN (94939, 94940, 94941, 94942, 94943, 94944, 94945, 94946, 94947, 94948, 94949, 94950)
    OPTION(LOOP JOIN);

rollback;

Most of the time the execution plan of the last **DELETE ** statement during parallel execution is the following: https://www.brentozar.com/pastetheplan/?id=HJ2tOfyhi

But sometimes (it happens quite rarely) the execution plan contains INDEX SPOOL (With exectly the same predicate as was used during INDEX SEEK in the previous execution plan): https://www.brentozar.com/pastetheplan/?id=SkIz9GJ3i.

NOTE: The execution plan above contains additional nested loop join with WeighEvent table which can be ignored, because I simplified the actual DB schema for this question and the same issue was reproduced without WeighEvent table. I just don't have this execution plan. Guess it won't be a problem.

The INDEX SCAN before INDEX SPOOL in this case causes deadlock during parallel execution of transctions above.

And my question is: Why does it happen and how to avoid this INDEX SPOOL? I don't know but can it be related to the index sort order?

Answer 1

Why does it happen?

SQL Server uses a cost-based optimizer. It generates different alternatives for different areas of the plan and chooses one that seems best, or at least 'good enough'.

An index scan plus eager index spool is a valid alternative. An index seek in this case would always be better, but the optimizer doesn't know that until both physical alternatives are generated and costed.

In the normal course of events—and in all the test cases I have been able to generate—the SQL Server optimizer reliably chooses the seek option. This is despite the plan being low enough cost to qualify for an early end to optimization activity due to 'good enough plan found'.

In your case, it seems something means SQL Server either cannot generate the seek plan, or it appears to be more expensive than the scan plus spool plan. There are too many possible (weird, edge-case) causes to enumerate in an answer.

Avoiding the scan and spool

Not being able to reproduce your plan*, I can't be certain of the cause. That said, I notice you are following the GDR SQL Server servicing option (you're on build 15.0.2095.3).

This means you only get the most critical security updates, not the regular bugs fixes and improvements released in Cumulative Updates.

There have been several optimizer and cardinality estimation bugs in the 2019 release related to foreign keys. None of these exactly match your stated problem, but they are close enough and in the right general product area to make this well worth pursuing as a potential fix.

You could either:

• Apply the latest 2019 Cumulative Update (CU 18 at the time of writing, build 15.0.4261.1). This will permanently move you off the GDR track; or

• Use an additional query hint to specify an earlier version of the model, or use the original cardinality estimator

  USE HINT ('FORCE_LEGACY_CARDINALITY_ESTIMATION')
  USE HINT ('QUERY_OPTIMIZER_COMPATIBILITY_LEVEL_xxx')
  

This still leaves a small risk that the optimizer will choose and cache a 'bad' plan one day. The supported solution to this is to use a plan guide or forced query store plan. How achievable that is for your specific use is something only you can determine at this stage.

Switching to the original CE for the problem delete is the easiest fix to try. I would still encourage you to get onto the latest CU unless you have a specific reason for being on the GDR track.

---

* I was able to generate the plan on 2019 CU18 by modifying the plan xml you supplied to work in a USE PLAN hint, but I couldn't get the plan via other means.