One Addition: > PostgreSQL 8.1.4 (The one which is taking... a very long time...) > > Merge Join (cost=7751.81..50026810.45 rows=7364 width=4) > Merge Cond: ("outer".sid = "inner".sid) > -> Index Scan using stud_pkey on stud s (cost=7751.81..49994210.01 > rows=56607 width=4) > Filter: (NOT (subplan)) > SubPlan > -> Materialize (cost=7751.81..8497.94 rows=53613 width=4) > -> Seq Scan on stud_vera (cost=0.00..7488.20 > rows=53613 width=4) > Filter: (veraid = 2) > -> Index Scan using stud_vera_sid_veraid_idx on stud_vera v > (cost=0.00..37646.74 rows=14729 width=4) > Index Cond: (veraid = 34) The interesting thing is that (like I've written in the main post) if I remove the 'AND veraid=34' it working fine (0.3seconds). The explain for this working query is: Merge Join (cost=45500.73..46741955.20 rows=147288 width=4) Merge Cond: ("outer".sid = "inner".sid) -> Index Scan using stud_pkey on stud s (cost=7734.28..46701101.71 rows=56607 width=4) Filter: (NOT (subplan)) SubPlan -> Materialize (cost=7734.28..8431.06 rows=50078 width=4) -> Seq Scan on stud_vera (cost=0.00..7488.20 rows=50078 width=4) Filter: (veraid = 2) -> Sort (cost=37766.46..38502.90 rows=294576 width=4) Sort Key: v.sid -> Seq Scan on stud_vera v (cost=0.00..6751.76 rows=294576 width=4)