Avoiding sub-query with group by

Hi,

I think the following query is O(n^2) in the number of table rows (see
details below, including "explain" output).  Is there any way to make
it linear?

Given a table like
 val | rmp | xtr
-----+-----+-----
   1 |   1 | a
   1 |   2 | b
   1 |   3 | c
   2 |   1 | d
   2 |   2 | e
   2 |   3 | f
I want to select
 val | rmp | xtr
-----+-----+-----
   1 |   2 | b
   2 |   3 | f
ie  the row where rmp > val, but just the first such value (smallest
rmp).

I can do this with:
andrew=# select * from tbl inner join (select val as v, min(rmp) as mr
from tbl where rmp > val group by val) as x on tbl.val=x.v and
tbl.rmp=x.mr;
 val | rmp | xtr | v | mr
-----+-----+-----+---+----
   1 |   2 | b   | 1 |  2
   2 |   3 | f   | 2 |  3
(2 rows)

But it requires two scans:
andrew=# create index tbl_index_val on tbl (val);
CREATE INDEX
andrew=# explain select * from tbl inner join (select val as v,
min(rmp) as mr from tbl where rmp > val group by val) as x on
tbl.val=x.v and tbl.rmp=x.mr;
                             QUERY PLAN
---------------------------------------------------------------------
 Hash Join  (cost=1.16..2.27 rows=1 width=24)
   Hash Cond: ((public.tbl.val = x.v) AND (public.tbl.rmp = x.mr))
   ->  Seq Scan on tbl  (cost=0.00..1.06 rows=6 width=16)
   ->  Hash  (cost=1.13..1.13 rows=2 width=8)
         ->  HashAggregate  (cost=1.08..1.11 rows=2 width=8)
               ->  Seq Scan on tbl  (cost=0.00..1.07 rows=2 width=8)
                     Filter: (rmp > val)
(7 rows)

Thanks,
Andrew

PS I cannot preview this message; I hope it is formatted OK.