I can reproduce this and the short 'quick fix' answer is: add the HASH JOIN hint to the query, eg
select divn_nbr, dept_nbr, vendorNumber, pid, nrfcolorNumber, periodcode
from ##tmpSFA a
where periodCode = '201512'
and not exists
(
select 1 from ##tmpSFA b
where ISNULL(a.divn_nbr, -99) = isnull(b.divn_nbr, -99)
and isnull(a.dept_nbr, -99) = isnull(b.dept_nbr, -99)
and isnull(a.vendorNumber, -99) = isnull(b.vendorNumber, -99)
and isnull(LTRIM(rtrim(upper(a.pid))), -99) = isnull(LTRIM(rtrim(upper(b.pid))), -99)
and isnull(a.nrfcolorNumber, -99) = isnull(b.nrfColorNumber, -99)
and b.periodCode IN ('201507', '201508', '201509', '201510', '201511')
)
OPTION ( HASH JOIN )
Hints should only normally be used as a last resort, so review carefully before you apply. The longer answer is to do with your table design and the additional NULL checking you have to do as a consequence. You should ask yourself why are all the columns nullable? What does a record where all columns are null except the period really mean? That's what your design allows. Note you can also fix the performance of this query by making all the columns in the table NOT NULL.
Just a few other notes: it's unlikely you need to use the UPPER function as most SQL Server installations use case-insensitive collations. Use LTRIM and RTRIM when the data is inserted into the table, not during joins. Generally, do not join on functions at all. Your periodCode column looks like a smart integer (ie a number that knows something) representing yyyymm, so it definitely does not need unicode and is unlikely to be variable in length. Therefore the correct datatype is CHAR(6). You could also store this as INT or DECIMAL(6,0). These small changes will not transform performance but are generally best practice and demonstrate that you understand SQL Server fundamentals such as datatypes and collations.
My complete test rig and results:
USE tempdb
GO
IF OBJECT_ID('##tmpSFA') IS NOT NULL DROP TABLE ##tmpSFA
CREATE TABLE ##tmpSFA
(
DIVN_NBR INT NULL,
DEPT_NBR SMALLINT NULL,
VendorNumber INT NULL,
PID NVARCHAR(50) NULL,
NrfColorNumber INT NULL,
PeriodCode NVARCHAR(6) NULL
)
GO
;WITH cte AS (
SELECT TOP 1000000 ROW_NUMBER() OVER ( ORDER BY ( SELECT 1 ) ) rn
FROM master.sys.columns c1
CROSS JOIN master.sys.columns c2
CROSS JOIN master.sys.columns c3
)
, periods AS
(
SELECT *
FROM ( VALUES
( 201501 ), ( 201502 ), ( 201503 ), ( 201504 ), ( 201505 ), ( 201506 ),
( 201507 ), ( 201508 ), ( 201509 ), ( 201510 ), ( 201511 ), ( 201512 ) ) x ( period )
)
INSERT INTO ##tmpSFA ( DIVN_NBR, DEPT_NBR, VendorNumber, PID, NrfColorNumber, PeriodCode )
SELECT TOP (200000)
rn % 9 DIVN_NBR,
rn % 3 DEPT_NBR,
rn % 33 VendorNumber,
rn % 44 PID,
rn % 13 NrfColorNumber,
periods.period AS PeriodCode
FROM cte c
CROSS JOIN periods
GO
-- Make some NULLs
UPDATE ##tmpSFA
SET DIVN_NBR = NULLIF( DIVN_NBR, 0 ),
DEPT_NBR = NULLIF( DEPT_NBR, 0 ),
VendorNumber = NULLIF( VendorNumber, 0 ),
PID = NULLIF( PID, 0 ),
NrfColorNumber = NULLIF( NrfColorNumber, 0 )
GO
-- Delete some of the older rows
;with cte as
(
SELECT *
FROM ##tmpSFA
TABLESAMPLE ( 50 PERCENT )
WHERE periodCode IN ('201507', '201508', '201509', '201510', '201511')
)
DELETE cte
GO
/*
SELECT PeriodCode, COUNT(*)
FROM ##tmpSFA
GROUP BY PeriodCode
ORDER BY PeriodCode
GO
*/
DECLARE @startTime DATETIME = GETDATE()
select divn_nbr, dept_nbr, vendorNumber, pid, nrfcolorNumber, periodcode
from ##tmpSFA a
where periodCode = '201512'
and not exists
(
select 1 from ##tmpSFA b
where ISNULL(a.divn_nbr, -99) = isnull(b.divn_nbr, -99)
and isnull(a.dept_nbr, -99) = isnull(b.dept_nbr, -99)
and isnull(a.vendorNumber, -99) = isnull(b.vendorNumber, -99)
and isnull(LTRIM(rtrim(upper(a.pid))), -99) = isnull(LTRIM(rtrim(upper(b.pid))), -99)
and isnull(a.nrfcolorNumber, -99) = isnull(b.nrfColorNumber, -99)
and b.periodCode IN ('201507', '201508', '201509', '201510', '201511')
)
OPTION ( LOOP JOIN ) -- Force loop join
SELECT DATEDIFF( second, @startTime, GETDATE() ) diff1
GO
DECLARE @startTime DATETIME = GETDATE()
select divn_nbr, dept_nbr, vendorNumber, pid, nrfcolorNumber, periodcode
from ##tmpSFA a
where periodCode = '201512'
and not exists
(
select 1 from ##tmpSFA b
where ISNULL(a.divn_nbr, -99) = isnull(b.divn_nbr, -99)
and isnull(a.dept_nbr, -99) = isnull(b.dept_nbr, -99)
and isnull(a.vendorNumber, -99) = isnull(b.vendorNumber, -99)
and isnull(LTRIM(rtrim(upper(a.pid))), -99) = isnull(LTRIM(rtrim(upper(b.pid))), -99)
and isnull(a.nrfcolorNumber, -99) = isnull(b.nrfColorNumber, -99)
and b.periodCode IN ('201507', '201508', '201509', '201510', '201511')
)
OPTION ( HASH JOIN )-- Force hash join
SELECT DATEDIFF( second, @startTime, GETDATE() ) diff2
GO
I have product sales by month temporary table.(subset of much larger historical table) I'm running query to find new product not previously sold in the previous months for a specified 6 month range. So take January as base, in Feb show me all new product sold that wasn't in Jan sales. In March all new product not sold in Jan or Feb sales, etc. For first 5 months query returns sub second. On 6th month, it takes ~5 minutes. Comparing execution plans, on that 6th month, it's showing Top operator in my execution plan that's taking the extra time. But I'm not sorting or using Top X in select. What in my query is causing this? I can wait 5 mins since it's one-off request, but I'm more asking from a learning perspective, I want to understand the why it added to Top operator. Thanks in advance. 
