What is the algorithm behind the EXCEPT operator?
What is the internal algorithm of how the Except operator works under the covers in SQL Server?


I wouldn't say that there's a special internal algorithm for EXCEPT. For A EXCEPT B, the engine takes distinct (if needed) tuples from A and subtracts rows that match in B. There are no special query plan operators. The distinct and the subtraction are implemented through the typical operators that you would see with a sort or with a join. Nested loop join, merge join, and hash join are all supported. To show this, I'll throw 15 million rows into a pair of heaps:

DROP TABLE IF EXISTS dbo.TABLE_1;

CREATE TABLE dbo.TABLE_1 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_1 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


DROP TABLE IF EXISTS dbo.TABLE_2;

CREATE TABLE dbo.TABLE_2 (
    COL1 BIGINT NULL,
    COL2 BIGINT NULL
);

INSERT INTO dbo.TABLE_2 WITH (TABLOCK)
SELECT TOP (15000000) ROW_NUMBER() OVER (ORDER BY (SELECT NULL)), NULL
FROM master..spt_values t1
CROSS JOIN master..spt_values t2
OPTION (MAXDOP 1);


The optimizer makes it usual cost-based decisions about how to implement the sort and the join. With two heaps I get a hash join as expected. You can see other join types naturally by adding indexes or by changing the data in either table. Below I force merge and loop joins with hints just for illustrative purposes:




  Does it internally take a hash of each row and compare?


No. It is implemented as any other join. One difference is that NULLs are treated as equal. This is a special type of comparison which you can see in the execution plan: &lt;Compare CompareOp="IS"&gt;. However, you can get that same plan with T-SQL that does not include the EXCEPT keyword. For example, the following has the exact same query plan as the EXCEPT query that uses a hash join:

SELECT t1.*
FROM
(
    SELECT DISTINCT COL1, COL2
    FROM dbo.TABLE_1
) t1
WHERE NOT EXISTS (
    SELECT 1
    FROM dbo.TABLE_2 t2
    WHERE (t1.COL1 = t2.COL1 OR (t1.COL1 IS NULL AND t2.COL1 IS NULL))
    AND (t1.COL2 = t2.COL2 OR (t1.COL2 IS NULL AND t2.COL2 IS NULL))
);


Diffing the XML of the execution plans only reveals superficial differences around aliases and things like that. The probe residuals for the hash joins do the row comparison. They are the same for both queries:



If you still have doubts, I ran PerfView with the highest available sample rate to get call stacks for the query with EXCEPT and the query without it. Here are the results side by side:



There is no real difference. The call stacks there reference hashing are present because of the hash matches in the plan. If I add indexes to get a natural merge join, you won't see any references to hashing in the call stacks:



Any hashing that occurs is due to the implementation of hash match operators. There isn't anything special about EXCEPT which leads to a special, internal hashing comparison.