Asking advice on speeding up a big table

I have a simple benchmark which runs too slow on a 100M row table, and
I am not sure what my next step is to make it faster.

It's a simple setup, part of a larger system.  There are three data
tables, each with a BIGINT id and a data column of dofferent types.
There is a fourth table with BIGINT foreign key references to the
other three tables' id columns.

    felix=> \d key
        Table "oddtimes.key"
     Column |  Type  | Modifiers
    --------+--------+-----------
     id     | bigint | not null
     data   | text   | not null
    Indexes:
        "key_pkey" PRIMARY KEY, btree (id)
        "key_data_key" UNIQUE, btree (data)

    felix=> \d val
         Table "oddtimes.val"
     Column |  Type   | Modifiers
    --------+---------+-----------
     id     | bigint  | not null
     data   | integer | not null
    Indexes:
        "val_pkey" PRIMARY KEY, btree (id)
        "val_data_key" UNIQUE, btree (data)

    felix=> \d sid
            Table "oddtimes.sid"
     Column |     Type      | Modifiers
    --------+---------------+-----------
     id     | bigint        | not null
     data   | character(40) | not null
    Indexes:
        "sid_pkey" PRIMARY KEY, btree (id)

    felix=> \d glue
        Table "oddtimes.glue"
     Column |  Type  | Modifiers
    --------+--------+-----------
     key    | bigint |
     val    | bigint |
     sid    | bigint |
    Indexes:
        "glue_key_idx" btree ("key")
        "glue_key_val_idx" btree ("key", val)
        "glue_val_idx" btree (val)
        "glue_val_key_idx" btree (val, "key")
    Foreign-key constraints:
        "glue_key" FOREIGN KEY ("key") REFERENCES "key"(id)
        "glue_val" FOREIGN KEY (val) REFERENCES val(id)
        "glue_sid" FOREIGN KEY (sid) REFERENCES sid(id)

Usage is to match data from the key and val tables to fetch the data
value from the sid table.  It's sort of a glorified Berkeley db, but
you can do compare ranges, not just exact matches.  If I can make it
fast enough, I may add two more types, date and text.

The key table has 1K rows, val has 100K, and sid and glue have 100M
rows.  They take about 31G space, last time I checked.

     felix=> SELECT relname, relpages FROM pg_class ORDER BY relpages DESC LIMIT 20;
                  relname             | relpages
     ---------------------------------+----------
      sid                             |  1086957
      glue                            |   735295
      glue_key_val_idx                |   385042
      glue_val_key_idx                |   385042
      sid_pkey                        |   274194
      glue_key_idx                    |   274194
      glue_val_idx                    |   274194
      val                             |      589
      val_pkey                        |      382
      val_data_key                    |      283


My benchmark times SQL matches like this.  This example was a repeat
and has reasonable speed.  But fresh values take around 3-4 seconds.
This is 8.0.3 on a dual Opteron dual core machine with only 2G RAM (it
is meant for compute intensive work and was idle while I ran these
tests).  The disks are plain vanilla IDE, maybe SATA, but nothing at
all special.

    felix=> explain analyze SELECT sid.data, val.data FROM key, val, sid, glue WHERE key.data =
'UajzAQjTJPevVJBuuerjU4pcl8eJcyrIxzkC'AND key.id = glue.key AND val.data = 1984186373 AND val.id = glue.val AND
glue.sid= sid.id; 
                                                                       QUERY PLAN
                            

------------------------------------------------------------------------------------------------------------------------------------------------
     Nested Loop  (cost=5.84..4480.89 rows=1 width=48) (actual time=32.157..32.157 rows=0 loops=1)
       ->  Hash Join  (cost=5.84..4477.87 rows=1 width=12) (actual time=32.149..32.149 rows=0 loops=1)
             Hash Cond: ("outer"."key" = "inner".id)
             ->  Nested Loop  (cost=0.00..4467.01 rows=1001 width=20) (actual time=0.205..28.304 rows=1000 loops=1)
                   ->  Index Scan using val_data_key on val  (cost=0.00..6.01 rows=1 width=12) (actual
time=0.059..0.066rows=1 loops=1) 
                         Index Cond: (data = 1984186373)
                   ->  Index Scan using glue_val_idx on glue  (cost=0.00..4447.15 rows=1108 width=24) (actual
time=0.131..20.670rows=1000 loops=1) 
                         Index Cond: ("outer".id = glue.val)
             ->  Hash  (cost=5.84..5.84 rows=1 width=8) (actual time=0.123..0.123 rows=0 loops=1)
                   ->  Index Scan using key_data_key on "key"  (cost=0.00..5.84 rows=1 width=8) (actual
time=0.100..0.105rows=1 loops=1) 
                         Index Cond: (data = 'UajzAQjTJPevVJBuuerjU4pcl8eJcyrIxzkC'::text)
       ->  Index Scan using sid_pkey on sid  (cost=0.00..3.01 rows=1 width=52) (never executed)
             Index Cond: ("outer".sid = sid.id)
     Total runtime: 32.293 ms
    (14 rows)


I realize these indices and tables take a lot of space and that is
at least mostly the reason for the slow speed.  But still, several
seconds seems like an eternity.  Are there things I can do to speed
this up?  Or this time way out of line and ought to be faster, meaning
I have some bug somewhere?

--
            ... _._. ._ ._. . _._. ._. ___ .__ ._. . .__. ._ .. ._.
     Felix Finch: scarecrow repairman & rocket surgeon / felix@crowfix.com
  GPG = E987 4493 C860 246C 3B1E  6477 7838 76E9 182E 8151 ITAR license #4933
I've found a solution to Fermat's Last Theorem but I see I've run out of room o