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.

Or maybe those scans are not nested and so it's O(n), not O(n^2)?

Sorry, I am not experienced using "explain".

Andrew

> 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)