I agree with you. As originally posted, a NOT EXISTS should have to table scan the entire tblRecipeAllergens table. Trivially fixed with the index Michael L John applied.

"knutpet" - since there is a relatively small list of Allergens and they recur a lot, I would recommend creating a separate "Allergens" table as:

create table Allergens (

AllergenID int identity(1,1),

AllergenName varchar(32) not null);

Then - use the AllergenID in the tblRecipeAllergen table instead of the Allergen name. That will make that table (and associated indexes) much more compact and faster to search, as the search will be on integer values instead of string matches. Assuming that there are less than 32,000 distinct allergens, you could even declare AllergenID as a "smallint" in both tables to further reduce the table sizes.

I am not sure how many distinct allergens exist, but that table is probably so small as to not need any indexes, although you could define AllergenID as the primary key for safety.