create table table3 as select generate_series( 1 , 1000000000 , 15625 ) as id; create index index3 on table3 ( id );
create table table2 as select generate_series( 1 , 1000000000 , 243   ) as id; create index index2 on table2 ( id );
create table table1 as select generate_series( 1 , 1000000000 , 2     ) as id; create index index1 on table1 ( id );

select count(*) from table1 union all select count(*) from table2 union all select count(*) from table3;

explain analyze select t3.id from table3 t3 where not exists(select  1  from table1 t1 where id = t3.id) and not exists(select  1  from table2 t2 where id = t3.id);
explain analyze select t3.id from table3 t3 left join table1 t1 using (id) left join table2 t2 using(id) where t2.id is null and t1.id is null;
explain analyze select id from table3 t3 left join table1 t1 using(id) where t1.id is null
        intersect select id from table3 t3 left join table2 t2 using(id) where t2.id is null;

drop table table1;
drop table table2;
drop table table3;

nalbat=> explain analyze select t3.id from table3 t3 where not exists(select  1  from table1 t1 where id = t3.id) and not exists(select  1  from table2 t2 where id = t3.id
);
                                                           QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on table3 t3  (cost= 0 . 00 .. 4597690 . 72  rows= 16000  width= 4 ) (actual time= 105 . 554 .. 917860 . 169  rows= 31868  loops= 1 )
   Filter: ((NOT (subplan)) AND (NOT (subplan)))
   SubPlan
     ->  Index Scan using index1 on table1 t1  (cost= 0 . 00 .. 63 . 11  rows= 1  width= 0 ) (actual time= 14 . 312 .. 14 . 312  rows= 0  loops= 63736 )
           Index Cond: (id = $ 0 )
     ->  Index Scan using index2 on table2 t2  (cost= 0 . 00 .. 8 . 72  rows= 1  width= 0 ) (actual time= 0 . 076 .. 0 . 076  rows= 0  loops= 64000 )
           Index Cond: (id = $ 0 )
 Total runtime:  917947 . 083  ms
( 8  rows)

Time:  917947 . 655  ms

nalbat=> explain analyze select t3.id from table3 t3 where not exists(select  1  from table1 t1 where id = t3.id) and not exists(select  1  from table2 t2 where id = t3.id
);
                                                          QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------
 Seq Scan on table3 t3  (cost= 0 . 00 .. 4597690 . 72  rows= 16000  width= 4 ) (actual time= 0 . 147 .. 2098 . 945  rows= 31868  loops= 1 )
   Filter: ((NOT (subplan)) AND (NOT (subplan)))
   SubPlan
     ->  Index Scan using index1 on table1 t1  (cost= 0 . 00 .. 63 . 11  rows= 1  width= 0 ) (actual time= 0 . 020 .. 0 . 020  rows= 0  loops= 63736 )
           Index Cond: (id = $ 0 )
     ->  Index Scan using index2 on table2 t2  (cost= 0 . 00 .. 8 . 72  rows= 1  width= 0 ) (actual time= 0 . 007 .. 0 . 007  rows= 0  loops= 64000 )
           Index Cond: (id = $ 0 )
 Total runtime:  2163 . 381  ms
( 8  rows)

Time:  2163 . 950  ms