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

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 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 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

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.

StackExchange Database Administrators Q#322590, answer score: 3