select version();
PostgreSQL 7.4.7 on i686-pc-linux-gnu, compiled by GCC gcc (GCC) 3.3.4 (pre 3.3.5 20040809)

create table test (
id integer,
time timestamp,
primary key (id,time)
);

time perl -e "printf \"begin;\n\"; for ( my \$i=1; \$i<=1_000_000; \$i++ ) { printf \"insert into test values ( %d, '%04d-%02d-%02d %02d:%02d:%02d' );\n\", 1+rand(5), 2000+rand(5), 1+rand(12), 1+rand(28), rand(24), rand(60), rand(60); unless ( \$i % 1_000 ) { printf \"end;\n\"; printf \"begin;\n\"; } } printf \"end;\n\";" | psql 1>/dev/null 2>/dev/null

select count(*) from test;
count
--------
608000
(1 row)

vacuum analyze test;

set enable_seqscan to off;
set enable_mergejoin to off;
set enable_hashjoin to off;

-- ПЕРВЫЙ ЗАПРОС

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
id,
time as time1,
(
select
time
from
test as test2
where
test2.id=test1.id and
test2.time>test1.time
order by
id, time
limit 1
) as time2
from
test as test1
) as A
where
time2<=time1+' 10:00:00 '
group by
id
order by
id
;
GroupAggregate (cost=0.00..3723865.62 rows=2 width=12) (actual time=30615.110..154604.042 rows=5 loops=1)
-> Index Scan using test_pkey on test test1 (cost=0.00..3722846.14 rows=202667 width=12) (actual time=0.760..97825.603 rows= 607715 loops=1)
Filter: ((subplan) <= ("time" + '10:00:00'::interval))
SubPlan
-> Limit (cost=0.00..3.07 rows=1 width=12) (actual time=0.129..0.131 rows=1 loops=608000)
-> Index Scan using test_pkey on test test2 (cost=0.00..124342.47 rows=40534 width=12) (actual time=0.117..0.117 rows=1 loops=608000)
Index Cond: ((id = $0) AND ("time" > $1))
SubPlan
-> Limit (cost=0.00..3.07 rows=1 width=12) (actual time=0.068..0.070 rows=1 loops=607715)
-> Index Scan using test_pkey on test test2 (cost=0.00..124342.47 rows=40534 width=12) (actual time=0.056..0.056 rows=1 loops=607715)
Index Cond: ((id = $0) AND ("time" > $1))
Total runtime: 154 605.676 ms

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
id,
time as time1,
(
select
time
from
test as test2
where
test2.id=test1.id and
test2.time>test1.time
order by
id, time
limit 1
) as time2
from
test as test1
) as A
where
time2<=time1+' 00:01:00 '
group by
id
order by
id
;
GroupAggregate (cost=0.00..3723865.62 rows=2 width=12) (actual time=20272.304..101391.404 rows=5 loops=1)
-> Index Scan using test_pkey on test test1 (cost=0.00..3722846.14 rows=202667 width=12) (actual time=4.825..98375.592 rows= 29956 loops=1)
Filter: ((subplan) <= ("time" + '00:01:00'::interval))
SubPlan
-> Limit (cost=0.00..3.07 rows=1 width=12) (actual time=0.130..0.131 rows=1 loops=608000)
-> Index Scan using test_pkey on test test2 (cost=0.00..124342.47 rows=40534 width=12) (actual time=0.118..0.118 rows=1 loops=608000)
Index Cond: ((id = $0) AND ("time" > $1))
SubPlan
-> Limit (cost=0.00..3.07 rows=1 width=12) (actual time=0.072..0.073 rows=1 loops=29956)
-> Index Scan using test_pkey on test test2 (cost=0.00..124342.47 rows=40534 width=12) (actual time=0.058..0.058 rows=1 loops=29956)
Index Cond: ((id = $0) AND ("time" > $1))
Total runtime: 101 391.911 ms

-- ВТОРОЙ ЗАПРОС

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
test1.id,
test1.time as time1,
min(test2.time) as time2
from
test as test1
join
test as test2
on
test2.id=test1.id and
test2.time>test1.time and
test2.time<=test1.time+' 10:00:00 '
group by
test1.id, test1.time
) as A
group by
id
order by
id
;
GroupAggregate (cost=0.00..25683107233.67 rows=200 width=20) (actual time=105348.725..529269.218 rows=5 loops=1)
-> Subquery Scan a (cost=0.00..25683104192.67 rows=608000 width=20) (actual time=5.952..524120.843 rows=607715 loops=1)
-> GroupAggregate (cost=0.00..25683098112.67 rows=608000 width=20) (actual time=5.925..519606.949 rows=607715 loops=1)
-> Nested Loop (cost=0.00..25621411652.70 rows=8224658663 width=20) (actual time=0.765..411766.216 rows= 18207105 loops=1)
-> Index Scan using test_pkey on test test1 (cost=0.00..1854699.74 rows=608000 width=12) (actual time=0.511..5737.652 rows=608000 loops=1)
-> Index Scan using test_pkey on test test2 (cost=0.00..41867.21 rows=13511 width=12) (actual time=0.049..0.425 rows=30 loops=608000)
Index Cond: ((test2.id = "outer".id) AND (test2."time" > "outer"."time") AND (test2."time" <= ("outer"."time" + '10:00:00'::interval)))
Total runtime: 529 269.720 ms

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
test1.id,
test1.time as time1,
min(test2.time) as time2
from
test as test1
join
test as test2
on
test2.id=test1.id and
test2.time>test1.time and
test2.time<=test1.time+' 00:01:00 '
group by
test1.id, test1.time
) as A
group by
id
order by
id
;
GroupAggregate (cost=0.00..25683107233.67 rows=200 width=20) (actual time=16781.895..84480.085 rows=5 loops=1)
-> Subquery Scan a (cost=0.00..25683104192.67 rows=608000 width=20) (actual time=12.730..84152.745 rows=29956 loops=1)
-> GroupAggregate (cost=0.00..25683098112.67 rows=608000 width=20) (actual time=12.713..83876.243 rows=29956 loops=1)
-> Nested Loop (cost=0.00..25621411652.70 rows=8224658663 width=20) (actual time=4.139..83243.735 rows= 30713 loops=1)
-> Index Scan using test_pkey on test test1 (cost=0.00..1854699.74 rows=608000 width=12) (actual time=0.403..42454.685 rows=608000 loops=1)
-> Index Scan using test_pkey on test test2 (cost=0.00..41867.21 rows=13511 width=12) (actual time=0.049..0.050 rows=0 loops=608000)
Index Cond: ((test2.id = "outer".id) AND (test2."time" > "outer"."time") AND (test2."time" <= ("outer"."time" + '00:01:00'::interval)))
Total runtime: 84 480.563 ms

-- ТЕСТОВЫЙ ЗАПРОС

explain
analyze
select
id,
min(time)
from
test
group by
id
order by
id
;
GroupAggregate (cost=0.00..1857739.76 rows=5 width=12) (actual time=9679.683..48503.539 rows=5 loops=1)
-> Index Scan using test_pkey on test (cost=0.00..1854699.74 rows=608000 width=12) (actual time=0.549..43460.582 rows=608000 loops=1)
Total runtime: 48 503.782 ms

drop table test;

-- РЕЗЮМЕ

Второй запрос может оказаться как быстрее первого, так и медленнее, в зависимости от того, каково среднее кол-во временных отметок, попадающих в ограничивающий интервал. Мне кажется, что скорости быстрее 48 секунд, показанной тестовым запросом с full index scan, достичь для вашей задачи нельзя. Вам нужны более быстрые запросы, чем работающие 84-154 секунды? (Вместо второго запроса, работающего 529 секунд в первом примере, нужно использовать первый запрос.)

P.S.: Пример ХМ не попробовал, потому что на 7.4 он не заработал. :-(

P.P.S.: В моем посте от 5-ого мая ошибка: в самом внутруннем селекте должен быть еще order by id, time.

select version();
PostgreSQL 8.0.1 on x86_64-unknown-linux-gnu, compiled by GCC gcc (GCC) 3.3.5 20050117 (prerelease) (SUSE Linux)

create table test (
id integer,
time timestamp,
primary key (id,time)
);

time perl -e "printf \"begin;\n\"; for ( my \$i=1; \$i<=1_000_000; \$i++ ) { printf \"insert into test values ( %d, '%04d-%02d-%02d %02d:%02d:%02d' );\n\", 1+rand(5), 2000+rand(5), 1+rand(12), 1+rand(28), rand(24), rand(60), rand(60); unless ( \$i % 1_000 ) { printf \"end;\n\"; printf \"begin;\n\"; } } printf \"end;\n\";" | psql 1>/dev/null 2>/dev/null

select count(*) from test;
count
--------
637000
(1 row)

vacuum analyze test;

-- ПЕРВЫЙ ЗАПРОС

-- БЕЗ ТЮНИНГА

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
id,
time as time1,
(
select
time
from
test as test2
where
test2.id=test1.id and
test2.time>test1.time
order by
id, time
limit 1
) as time2
from
test as test1
) as A
where
time2<=time1+'00:01:00'
group by
id
order by
id
;
Sort (cost=2314124.86..2314124.86 rows=2 width=12) (actual time=17523.181..17523.182 rows=5 loops=1)
Sort Key: test1.id
-> HashAggregate (cost=2314118.48..2314124.85 rows=2 width=12) (actual time=17523.130..17523.135 rows=5 loops=1)
-> Seq Scan on test test1 (cost=0.00..2312914.99 rows=240697 width=12) (actual time=0.163..17105.726 rows=32868 loops=1)
Filter: ((subplan) <= ("time" + '00:01:00'::interval))
SubPlan
-> Limit (cost=0.00..3.18 rows=1 width=12) (actual time=0.025..0.025 rows=1 loops=637000)
-> Index Scan using test_pkey on test test2 (cost=0.00..153131.78 rows=48140 width=12) (actual time=0.023..0.023 rows=1 loops=637
000)
Index Cond: ((id = $0) AND ("time" > $1))
SubPlan
-> Limit (cost=0.00..3.18 rows=1 width=12) (actual time=0.008..0.008 rows=1 loops=32868)
-> Index Scan using test_pkey on test test2 (cost=0.00..153131.78 rows=48140 width=12) (actual time=0.006..0.006 rows=1 loops=32868)
Index Cond: ((id = $0) AND ("time" > $1))
Total runtime: 17523.506 ms

-- С ТЮНИНГОМ

set enable_seqscan to off;
set enable_mergejoin to off;
set enable_hashjoin to off;

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
id,
time as time1,
(
select
time
from
test as test2
where
test2.id=test1.id and
test2.time>test1.time
order by
id, time
limit 1
) as time2
from
test as test1
) as A
where
time2<=time1+'00:01:00'
group by
id
order by
id
;
GroupAggregate (cost=0.00..4589167.57 rows=2 width=12) (actual time=2121.001..10593.881 rows=5 loops=1)
-> Index Scan using test_pkey on test test1 (cost=0.00..4587957.71 rows=240697 width=12) (actual time=0.595..10275.768 rows=32868 loops=1)
Filter: ((subplan) <= ("time" + '00:01:00'::interval))
SubPlan
-> Limit (cost=0.00..3.18 rows=1 width=12) (actual time=0.014..0.014 rows=1 loops=637000)
-> Index Scan using test_pkey on test test2 (cost=0.00..153131.78 rows=48140 width=12) (actual time=0.013..0.013 rows=1 loops=637000)
Index Cond: ((id = $0) AND ("time" > $1))
SubPlan
-> Limit (cost=0.00..3.18 rows=1 width=12) (actual time=0.007..0.007 rows=1 loops=32868)
-> Index Scan using test_pkey on test test2 (cost=0.00..153131.78 rows=48140 width=12) (actual time=0.005..0.005 rows=1 loops=32868)
Index Cond: ((id = $0) AND ("time" > $1))
Total runtime: 10593.973 ms

set enable_seqscan to on;
set enable_mergejoin to on;
set enable_hashjoin to on;

-- ВТОРОЙ ЗАПРОС

-- БЕЗ ТЮНИНГА

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
test1.id,
test1.time as time1,
min(test2.time) as time2
from
test as test1
join
test as test2
on
test2.id=test1.id and
test2.time>test1.time and
test2.time<=test1.time+'00:01:00'
group by
test1.id, test1.time
) as A
group by
id
order by
id
;
Cancel request sent
ERROR: производится отмена запроса по запросу пользователя
-- не дождался! :(

-- С ТЮНИНГОМ

set enable_seqscan to off;
set enable_mergejoin to off;
set enable_hashjoin to off;

explain
analyze
select
id,
sum( time2-time1 )
from
(
select
test1.id,
test1.time as time1,
min(test2.time) as time2
from
test as test1
join
test as test2
on
test2.id=test1.id and
test2.time>test1.time and
test2.time<=test1.time+'00:01:00'
group by
test1.id, test1.time
) as A
group by
id
order by
id
;
GroupAggregate (cost=0.00..37412563346.64 rows=200 width=20) (actual time=1833.255..9164.470 rows=5 loops=1)
-> Subquery Scan a (cost=0.00..37412562984.59 rows=72209 width=20) (actual time=1.051..9122.915 rows=32868 loops=1)
-> GroupAggregate (cost=0.00..37412562262.50 rows=72209 width=20) (actual time=1.048..9078.568 rows=32868 loops=1)
-> Nested Loop (cost=0.00..37325550208.17 rows=11601583174 width=20) (actual time=0.375..9006.674 rows=33692 loops=1)
-> Index Scan using test_pkey on test test1 (cost=0.00..2287405.61 rows=722089 width=12) (actual time=0.085..5150.053 rows=637000 l
oops=1)
-> Index Scan using test_pkey on test test2 (cost=0.00..51366.96 rows=16047 width=12) (actual time=0.005..0.005 rows=0 loops=637000
)
Index Cond: ((test2.id = "outer".id) AND (test2."time" > "outer"."time") AND (test2."time" <= ("outer"."time" + '00:01:00'::int
erval)))
Total runtime: 9164.557 ms

set enable_seqscan to on;
set enable_mergejoin to on;
set enable_hashjoin to on;

-- ЧЕРЕЗ ФУНКЦИЮ ГРУППИРОВКИ (by XM)

create type time_accum as (
the_time timestamp,
the_interval interval
);
create function add_time(_state time_accum, _data_time time_accum) returns time_accum as $$
declare _temp interval;
begin
_temp := _data_time.the_time - _state.the_time;
if _temp <= '1 min'::interval then
_state.the_interval := _state.the_interval + _temp;
end if;
_state.the_time := _data_time.the_time;
return _state;
end
$$ language 'plpgsql';
create aggregate work_time (
basetype = time_accum,
sfunc = add_time,
stype = time_accum,
initcond = '("1970-01-01",0)'
);

create function time_accum(_time timestamp) returns time_accum as $$
declare _data time_accum;
begin
_data.the_time := _time;
_data.the_interval := '0'::interval;
return _data;

end
$$ language 'plpgsql';

explain
analyze
select id, work_time(time_accum(time)) from
(select id, time from test order by time) as ttt
group by id;
HashAggregate (cost=134575.27..134576.27 rows=200 width=12) (actual time=10980.302..10980.306 rows=5 loops=1)
-> Subquery Scan ttt (cost=121938.71..130964.82 rows=722089 width=12) (actual time=3237.633..3990.972 rows=637000 loops=1)
-> Sort (cost=121938.71..123743.93 rows=722089 width=12) (actual time=3237.624..3517.254 rows=637000 loops=1)
Sort Key: "time"
-> Seq Scan on test (cost=0.00..12362.89 rows=722089 width=12) (actual time=0.039..263.376 rows=637000 loops=1)
Total runtime: 11013.862 ms

-- ТЕСТОВЫЙ ЗАПРОС

explain
analyze
select
id,
min(time)
from
test
group by
id
order by
id
;
GroupAggregate (cost=0.00..2291016.06 rows=5 width=12) (actual time=1166.705..5853.179 rows=5 loops=1)
-> Index Scan using test_pkey on test (cost=0.00..2287405.61 rows=722089 width=12) (actual time=0.077..5507.108 rows=637000 loops=1)
Total runtime: 5853.241 ms

--

drop function time_accum(timestamp);
drop aggregate work_time(time_accum);
drop function add_time(time_accum,time_accum);
drop type time_accum;

drop table test;

--

2 XM:

В вашем тесте ограничение в 5 секунд наверное выбрано не очень правильно, так как ему соответствует всего лишь 75 строк из миллиона.

С таким ограничением лучше использовать не мой первый незатюненый запрос, а второй затюненый запрос.

Пробовал пинать планы в вашем запросе (через group aggregate, index scan), более быстрого выполнения добиться не получилось. :(