Damn slow query

Hello, i've got this query that's really slow...
Figure this:

testdb=> select now() ; select gid from bs where gid not in ( select x
from z2test ); select now();
now
-------------------------------
2002-10-09 22:37:21.234627+02
(1 row)

gid
----------
<lotsa rows>
(524 rows)
now
-------------------------------
2002-10-09 23:20:53.227844+02
(1 row)

That's 45 minutes i don't wanna spend in there...
I got indexes:

testdb=> \d bs_gid_idx
Index "bs_gid_idx"
Column | Type
--------+-----------------------
gid | character varying(16)
online | smallint
btree

testdb=> \d z2test_x_idx;
Index "z2test_x_idx"
Column | Type
--------+-----------------------
x | character varying(16)
btree

Rowcounts are:

testdb=> select count(*) from bs ; select count(*) from z2test ;
count
-------
25376
(1 row)

count
-------
19329
(1 row)

The bs table have many other columns besides the gid one, the z2test
table only has the x column.

How can i speed this query up?
It never scans by the indexes.
I know it's a lot of iterations anyway i do it, but this is too damn
slow.

I can't profile anything at this box, because it's in production state,
but if you really want me to, i'll do it tomorrow on another box.

Magnus

--
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
Programmer/Networker [|] Magnus Naeslund
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-