Query slow after VACUUM ANALYZE

Hi all

I'm having a strange problem with a query which looks like this:

SELECT id FROM orders WHERE id NOT IN (SELECT order_id FROM orders_items);

The id fields are varchars (32), both indexed. The number of rows in the
tables are about 60000.

Now, the really strange part is if I delete all data from orders_items,
run VACUUM ANALYZE, then import all the data, the query finshes in about 3
seconds. Then I run VACUUM ANALYZE, and *after* the vacuum, the query
takes
about 30 minutes to run. The data is the same and this is the only query
running, and the machine load is effectively none.

EXPLAIN'ng the query shows, before VACUUM ANALYZE, shows this:

QUERY PLAN
-------------------------------------------------------------------------
Seq Scan on orders (cost=0.00..12184.14 rows=29526 width=33)
Filter: (NOT (hashed subplan))
SubPlan
-> Seq Scan on orders_items (cost=0.00..0.00 rows=1 width=33)

After the vacuum, the plan is like this:

QUERY PLAN
--------------------------------------------------------------------------------
Seq Scan on fsi_orders (cost=0.00..40141767.46 rows=29526 width=33)
Filter: (NOT (subplan))
SubPlan
-> Seq Scan on fsi_orders_items (cost=0.00..1208.12 rows=60412
width=33)

Any ideas what I can do to make the query running in < 10 seconds?

Thanks,
Guðmundur.