Friend of mine found something that he thought looked like a bug in Pg. Very simple query: select * from table where id not in (select field from other_table) was not returning any rows, despite the fact that there definitely are some "ids" ...