SEO

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