Postgres ANTI-JOIN needs Table-Scan?

Question

I need an ANTI-JOIN (not exists SELECT something from table.../ left join table WHERE table.id IS NULL) on the same table. Acutally I have an index to serve the not exists question, but the query planner chooses to use a bitmap heap scan.

The table has 100 Million rows, so doing a heap scan is messed up...

It would be really fast if Postgres could compare to the indicies. Does Postgres have to visit the table for this ANTI-JOIN?

I know the table has to be visited at some point to serve the MVCC, but why so early? Can NOT EXISTS only be fixed by the table, because it could miss something otherwise?

Answer 1

You'll need to provide version details, and as jmz says EXPLAIN ANALYSE output to get any useful advice.

Franz - don't think whether it's possible, test and know.

This is v9.0:

CREATE TABLE tl (i int, t text);
CREATE TABLE tr (i int, t text);
INSERT INTO tl SELECT s, 'text ' || s FROM generate_series(1,999999) s;
INSERT INTO tr SELECT s, 'text ' || s FROM generate_series(1,999999) s WHERE s % 3 = 0;
ALTER TABLE tl add primary key (i);
CREATE INDEX tr_i_idx ON tr (i);
ANALYSE;
EXPLAIN ANALYSE SELECT i,t FROM tl LEFT JOIN tr USING (i) WHERE tr.i IS NULL;
                                                         QUERY PLAN                                                      
-----------------------------------------------------------------------------------------------------------------------------
 Merge Anti Join  (cost=0.95..45611.86 rows=666666 width=15) (actual time=0.040..4011.970 rows=666666 loops=1)
   Merge Cond: (tl.i = tr.i)
   ->  Index Scan using tl_pkey on tl  (cost=0.00..29201.32 rows=999999 width=15) (actual time=0.017..1356.996 rows=999999 lo
   ->  Index Scan using tr_i_idx on tr  (cost=0.00..9745.27 rows=333333 width=4) (actual time=0.015..439.087 rows=333333 loop
 Total runtime: 4602.224 ms

What you see will depend on your version, and the stats the planner sees.