Efficiency of sub-query with "order by"

I tried posting this earlier, but received an email error indicating I
wasn't subscribed.  At the same time, I see the original post on
Google groups.  So I am reposting; apologies if this now a duplicate.

Hi,

I worry the following query may be 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)

It's not clear to me whether these scans are effectively nested, or
what the complexity of the query is.  I am worried it is O(n^2) rather
than O(n) - in practice this will be used on large tables.  So my
basic question is whether there is a similar way to do this in a
single select.

Thanks,
Andrew