Optimise XOR search on int list

Question

I have a large table (TableA) with approx. 120 mio. datasets. This table contains a single primary key column (type: int).

Another large table (TableB) contains the same ID column with some other fields. Currently there is no foreign key constraint or unique index defined on this table (although I'm thinking about adding a primary key constraint here in any case).

The key task is to determine if any of the ID values in TableA do NOT appear in TableB.

SELECT * FROM TableA WHERE Id NOT IN (SELECT Id FROM TableB)  

I timed this task on our database server to take approx. 4 minutes. Now I was wondering if there was a way to improve this.

From what I understand the lists may not be ordered BUT it's guaranteed that the Id is Unique for both tables. Is there a method I can first sort these fields (or even better have a sorted index of some kind) and then just compare those sorted lists or is there another approach to this?

Answer 1

Is there a method I can first sort these fields (or even better have a sorted index of some kind) and then just compare those sorted lists or is there another approach to this?

although I'm thinking about adding a primary key constraint here in any case)

Yes. A Primary Key constraint is implemented by creating a unique BTree index on the target column(s). A BTree has, at its leaf level, a doubly-linked list of pages that is maintained in index key order. And all the index key values are stored on these leaf pages. There are also non-leaf pages that enable efficiently seeking a page containing a particular key value. You can read all about this here: SQL Server Index Architecture.

So, when comparing two tables on their PKs SQL Server can either

• Scan one table and perform cheap lookups on either table (~4 Logical IOs per lookup), using a Nested Loop Join.

or

• Perform a Merge Join, where the sorted indexes are scanned in tandem matching rows.

If the PK is Clustered then scanning the just the key values is more expensive, as the rest of the columns are present on the leaf level of the index. So a non-clustered primary key constraint is probably the best table design. And a handy complement to a non-clustered PK is to store the rest of the table in a Clustered Columnstore.