How to find rows in one table that have no corresponding row in another table

Question

I have a 1:1 relationship between two tables. I want to find all the rows in table A that don't have a corresponding row in table B. I use this query:

SELECT id 
  FROM tableA 
 WHERE id NOT IN (SELECT id 
                    FROM tableB) 
ORDER BY id desc

id is the primary key in both tables. Apart from primary key indices, I also have a index on tableA(id desc).

Using H2 (Java embedded database), this results in a full table scan of tableB. I want to avoid a full table scan.

How can I rewrite this query to run quickly? What index should I should?

Answer 1

select tableA.id from tableA left outer join tableB on (tableA.id = tableB.id)
where tableB.id is null
order by tableA.id desc

If your db knows how to do index intersections, this will only touch the primary key index

Answer 2

I can't tell you which of these methods will be best on H2 (or even if all of them will work), but I did write an article detailing all of the (good) methods available in TSQL. You can give them a shot and see if any of them works for you:

http://code.msdn.microsoft.com/SQLExamples/Wiki/View.aspx?title=QueryBasedUponAbsenceOfData&referringTitle=Home

Answer 3

You have to check every ID in tableA against every ID in tableB. A fully featured RDBMS (such as Oracle) would be able to optimize that into an INDEX FULL FAST SCAN and not touch the table at all. I don't know whether H2's optimizer is as smart as that.

H2 does support the MINUS syntax so you shou;d try this

select id from tableA
minus
select id from tableB
order by id desc

That may perform faster; it is certainly worth benchmarking.