More performant SQL Delete than using NOT EXISTS?

I have a query that is deleting a lot of data from a table as follows. It uses a while loop based on trying to not destroy the transaction log but the Customers table has about 200 million records in it and it is deleting approx. 2 million. I was wondering if replacing the NOT EXISTS would help at all.

WHILE (1=1)
BEGIN
  DELETE TOP(10000) FROM Customers
  WHERE NOT EXISTS (SELECT * FROM CustomerInvoices WHERE CustomerInvoices.CustomerId = 
  Customers.CustomerId)
  IF (@@ROWCOUNT = 0)
  BREAK
END

Your problem is that the number of rows in Customers it needs to check before finding 10000 matching the NOT EXISTS grows every batch.

The ratio of matching rows will steadily drop until by the final batch you are scanning the whole 198 million remaining rows to find the last 10,000.

You are doing 200 batches. On average each batch reads 100 million in Customers rows (the earliest batches much less and the later ones more more) - this totals to 20 billion rows read over all just from that table and a similar amount in CustomerInvoices.

If the execution plan is a serial scan then likely every batch this will go over all the ones already processed in every previous batch and found to be not eligible before finally getting to the ones of interest.

You can create a temp table with a sequential integer column...

DECLARE @LastRow INT

CREATE TABLE #DeleteCandidates(Id int PRIMARY KEY, CustomerId INT);

INSERT #DeleteCandidates
SELECT ROW_NUMBER()
         OVER (
           ORDER BY (SELECT 0)) AS Id,
       Customers.CustomerId
FROM   Customers
WHERE  NOT EXISTS (SELECT *
                   FROM   CustomerInvoices
                   WHERE  CustomerInvoices.CustomerId = Customers.CustomerId)

SET @LastRow = @@ROWCOUNT 

Then write some code to process that temp table in <batch_size> chunks of Id ranges.

e.g. as below

DECLARE @BatchSize INT = 10000
DECLARE @MinId INT = 1

WHILE @MinId <= @LastRow
  BEGIN

      DELETE FROM Customers
      WHERE  Customers.CustomerId IN (SELECT dc.CustomerId
                                      FROM   #DeleteCandidates dc
                                      WHERE  dc.Id >= @MinId
                                             AND dc.Id < @MinId + @BatchSize)
             AND NOT EXISTS (SELECT *
                             FROM   CustomerInvoices/*WITH (HOLDLOCK )*/
                             WHERE  CustomerInvoices.CustomerId = Customers.CustomerId)

      SET @MinId = @MinId + @BatchSize
  END 

You still need a NOT EXISTS on the actual DELETE in case there were inserts since the identification that means a delete candidate is no longer eligible.

You might also consider the HOLDLOCK hint to deal with the possibility of truly concurrent inserts whilst the DELETE query itself is running.