Why is SQL Server using a clustered index scan for a self referencing FK cascade delete

Question

I have made an example to allow me to show what my issue is:

Setup:

CREATE TABLE [dbo].[Test](
    [TestId] [bigint] IDENTITY(1,1) NOT NULL,
    [ParentTestId] [bigint] NULL,
 CONSTRAINT [PK_Test] PRIMARY KEY CLUSTERED ([TestId] ASC)
)
GO

ALTER TABLE [dbo].[Test]  WITH CHECK ADD  CONSTRAINT [FK_Test_ParentTest] 
      FOREIGN KEY([ParentTestId])
REFERENCES [dbo].[Test] ([TestId])
GO

ALTER TABLE [dbo].[Test] CHECK CONSTRAINT [FK_Test_ParentTest]
GO

DECLARE @iter INT
SET @iter = 1
WHILE @iter < 1000
BEGIN
    INSERT INTO dbo.Test ( ParentTestId )
    VALUES  ( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),
    ( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),
    ( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),
    ( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),
    ( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null ),( null )
    SET @iter = @iter + 1
END
go

This creates a self referencing table and adds over 40,000 rows to it.

Action:

DELETE FROM dbo.Test WHERE TestId = 200

I then want to delete a row from this table. If you turn on the actual query plan and run the above statement you can see that 20% of the cost is taken in a Clustered Index Scan for the self referencing key.

This is not a big deal in this scenario, but my real scenario has over 25 million rows in a large table.

So, I have two questions:

1. Why is it doing an Index Scan? It has a Primary Key/Clustered Index value. Why would it not do a Index Seek?
2. How can I make it do an Index Seek? (It is taking about 1 min to delete a row.)

Edit: I thought that this could be due SQL Server looking to see if other rows were referencing the one I was deleting. But I set "Enforce Foreign Key Constraint" to "No" and it still took the same cost do a clustered index scan.

Answer 1

It needs to validate that the row you are trying to delete is not a parent of an existing row.

You don't have an index on ParentTestId.

So it must do the scan.

CREATE NONCLUSTERED INDEX ix ON  [dbo].[Test](ParentTestId)

Then you see a seek.

BTW: The 20% estimated cost of the scan is likely to be an underestimate in this case.

The FK validation is under a left semi join and SQL Server costs it as though only a partial scan will be needed and it will find a matching row and the delete will fail.

Presumably the rows you are actually deleting will succeed more often than not and so a full scan will be required in order to validate that there are no conflicting rows.

Using trace flag 4138 to turn off row goals

DELETE FROM dbo.Test
WHERE  TestId = 200 
OPTION (querytraceon 4138 )

The re-costed plan shows the CI scan at 100% rather than 20% (as it now assumes a full scan will be needed)

This difference in estimated cost is sufficient for the missing index suggestion to show up.

The costs shown in this plan are still not very representative however. You might notice that they add up to 219%.

Also the overall plan cost of the queries with and without the trace flag are both identical at 0.0168268. The full CI scan ought, in fact, to be costed at 0.152373 (0.0485075 + 0.103866)

but it seems to be capped at no more than the original plan cost (and the overall plan cost doesn't get adjusted upwards either hence incorrect percentages)