Как найти разрыв в упорядоченной по времени таблице, в которой заданный столбец не имеет определенного значения в течение указанного интервала

Question

У меня есть большая таблица (миллионы строк), где мне нужно найти группы записей, основываясь на наличии определенного значения столбца и где указанное «время ожидания» не произошло. Я полагаю, что один из подходов заключается в том, чтобы найти по всей таблице, где произошли эти промежутки времени ожидания.

Пример таблицы:

+----------------+------+
| time           | base |
+----------------+------+
| 1245184797.064 | a    |
| 1245184802.020 | a    |
| 1245184807.103 | b    |
| 1245184812.089 | b    |
| 1245184816.831 | b    |
| 1245184821.856 | a    |
| 1245184821.856 | a    |
| 1245184855.903 | a    |
| 1245184855.903 | b    |
| 1245184858.362 | b    |
| 1245184858.362 | b    |
| 1245184860.360 | a    |
| 1245184860.360 | a    |
| 1245184862.174 | a    |
| 1245184862.174 | b    |
| 1245185001.480 | b    |
| 1245185417.556 | a    |
| 1245185417.844 | a    |
| 1245185419.960 | b    |
| 1245185420.181 | b    |
+----------------+------+

Учитывая этот набор, как бы я быстро нашел точки в таблице, где base = a не произошло в течение заданного количества секунд (скажем, 5).

Чтобы свести это к минимуму, моя цель состоит в том, чтобы найти диапазоны записей, в которых база = HAS происходила постоянно без истечения времени ожидания.

Answer 1

Я думаю, это поможет вам:

SELECT * FROM (
    SELECT t1.[time],
           t1.time - (SELECT MAX(time) FROM my_table t2 WHERE t2.time < t1.time and t2.base = 'a') AS timeout
    FROM my_table t1
    WHERE t1.base = 'a') d
WHERE timeout > 5

И не забудьте создать индекс для того, чтобы этот запрос был более эффективным:

CREATE INDEX idx_my_table_time_base ON my_table (time, base)

Answer 2

Одна из возможностей, если вы используете базу данных, которая поддерживает оконные / аналитические функции, выглядит примерно так:

select * from (
    select time,
           base,
           time - lag(time) over(partition by base order by time) as interval
    from example) w
where w.interval > 5

Это должно быть в состоянии работать с одного сканирования индекса (базы, времени). Он работает на PostgreSQL 8.4, и я думаю, что он также должен работать на SQL Server 2008 и Oracle 10.

Answer 3

Один из способов подойти к этому - проверить наличие «растягивающихся головок», то есть вхождений базы более 5 секунд с момента ее последнего вхождения. Этот пример запроса объединяет таблицу сам по себе, чтобы отфильтровать не заголовки:

select    head.* 
from      @t head
left join @t nohead 
on        head.base = nohead.base 
and       head.time - 5 < nohead.time and nohead.time < head.time
where     nohead.base is null
order by  head.[time]

Для каждой строки left join ищет одну и ту же базу в течение последних 5 секунд. Предложение where nohead.base is null говорит, что такая строка может не существовать. Эффект представляет собой список, когда происходит 5+ секундный промежуток без базы.

В нем не будет указан последний разрыв: вы можете явно добавить строки «время окончания» для каждой базы:

<end time>     a
<end time>     b
...

для проверки запроса на разрыв.