trouble with (lack of) indexing

Hello

I am currently involved in a rather large project relying heavily on the use of
postgresql[1], but we have run into a rather annoying snag.
We currently have two databases set up. One for testing, and one for production.
Both run on FreeBSD, and perform very well since the last upgrade.
However, here is the problem. When executing a certain select statement (shown
below) on the production database, we get a sequential table scan (of a rather
large table), which causes the machine on which it runs to max out all possible
disk I/O. However, when the excact same query is executed on the test
database, we get an index scan instead of a sequential one. Obviously,
something differes between the two databases, but we simply cannot track down
what it is. I would greatly appreciate any input you might be able to offer.
Here are the queries and their accompanying query plans:

On the development/testing database:


--------------8<-----------
=> explain SELECT ht.id,
->                      hq.ip,
->                      hq.id
->               FROM   hostsqueue as hq,
->                      hoststests as ht
->               WHERE  ht.hostsqueue_id=hq.id
-> ;
NOTICE:  QUERY PLAN:

Merge Join  (cost=0.00..121.50 rows=1000 width=44)
  ->  Index Scan using hostsqueue_pkey on hostsqueue hq  (cost=0.00..52.00 rows=1000 width=36)
  ->  Index Scan using idx_htsts_hq on hoststests ht  (cost=0.00..52.00 rows=1000 width=8)

EXPLAIN
=>
--------------8<-----------
That looks fine and dandy, and performance is ok.

This however is on the production database:
--------------8<-----------

=> explain SELECT ht.id,
->                      hq.ip,
->                      hq.id
->               FROM   hostsqueue as hq,
->                      hoststests as ht
->               WHERE  ht.hostsqueue_id=hq.id;
NOTICE:  QUERY PLAN:

Merge Join  (cost=134514.31..136541.15 rows=129756 width=44)
  ->  Sort  (cost=76196.94..76196.94 rows=32200 width=36)
        ->  Seq Scan on hostsqueue hq  (cost=0.00..73786.00 rows=32200 width=36)
  ->  Sort  (cost=58317.37..58317.37 rows=129756 width=8)
        ->  Seq Scan on hoststests ht  (cost=0.00..47297.56 rows=129756 width=8)

EXPLAIN
=>

--------------8<-----------

Obviously something differs.
The table definitions are rather large, so I have made them available at:
http://tb.tolkien.dk/~boll/devel-definition.txt
and
http://treebeard.tolkien.dk/~boll/production-definition.txt

Any input, be it suggestions or otherwise, as to how we may fix this, would be
greatly appreciated.

Since I am a relatively new subscriber to the list, could you possibly cc me
with any suggestions, since I am not entirely sure if I actually receive mail
sent to the list yet.

Thanks.

[1] We choose postgresql over others because we liked the many features it
offers beyond its closest competitors.
--
Søren O.                                       ,''`.
                                              : :' :
public key: finger boll <at> db.debian.org    `. `'
                                                `-