Why is the SQLServerCE query scanning the table, and is this a problem?

Question

I am trying to optimize a query for a SQLServerCE database running on a Windows Mobile device. The query is used to identify rows for deletion in one table based on the absence of a link to another table. The original query uses DISTINCT to determine matching rows:

SELECT TestGroupId, TestNameId, ServiceTypeId FROM ServiceTypeInspection WHERE ServiceTypeId NOT IN (SELECT DISTINCT ServiceTypeId FROM PurchaseOrder) 

Quick Google suggested using EXISTS instead of:

 SELECT TestGroupId, TestNameId, ServiceTypeId FROM ServiceTypeInspection AS STI WHERE NOT EXISTS (SELECT PurchaseOrderId FROM PurchaseOrder AS PO WHERE (ServiceTypeId = STI.ServiceTypeId)) 

But then I also found suggestions for SO and MSDN to replace both LEFT JOIN options, which sounded promising:

 SELECT TestGroupId, TestNameId, STI.ServiceTypeId ServiceTypeId FROM ServiceTypeInspection STI LEFT JOIN PurchaseOrder PO ON STI.ServiceTypeId = PO.ServiceTypeId WHERE PO.ServiceTypeId IS NULL 

When I run these queries in the form of a package showing the execution plan, the cost compared to the batch of the original query is 21%, the NOT EXISTS version is 11%, while the LEFT JOIN is responsible for the balance of 68%. SSMS does not indicate that there are any missing indexes, but the fastest NOT EXISTS query has 25% cost when scanning the table. I have unique indexes on ServiceTypeId in both tables. Am I reading the conclusion of the execution plan correctly that, in this case, the NOT EXISTS version is the best approach? Does the table crawl a potential bottleneck or is this normal for a non-unique index?

Table definition:

 CREATE TABLE [PurchaseOrder]( [PurchaseOrderId] [uniqueidentifier] NOT NULL, [ServiceTypeId] [nvarchar](8) NOT NULL, CONSTRAINT [PK_PurchaseOrder] PRIMARY KEY ( [PurchaseOrderId] ) ); CREATE TABLE [ServiceTypeInspection]( [TestGroupId] [int] NOT NULL, [TestNameId] [nvarchar](10) NOT NULL, [ServiceTypeId] [nvarchar](8) NOT NULL, CONSTRAINT [PK_ServiceTypeInspection] PRIMARY KEY ( [TestGroupId],[TestNameId] ) ); CREATE INDEX IX_PurchaseOrder_ServiceTypeId ON [PurchaseOrder] (ServiceTypeId); CREATE INDEX IX_ServiceTypeInspection_ServiceTypeId ON [ServiceTypeInspection] (ServiceTypeId); 

Answer 1

I assume that the size of your NC indexes is relatively large compared to the size of the table (the large primary key, which I assume is also the default clustered index, which means that you have large NC indexes), so the optimizer decides to scan the table.

In addition, if the indices IX_PurchaseOrder_ServiceTypeId and IX_ServiceTypeInspection_ServiceTypeId have a selectivity of less than 10%, the optimizer will probably not use them.