Группировка переменных смежных записей с временным интервалом

У меня есть последовательность прерывисто расположенных GPS-координат с отметками времени. Я использую PostGIS для рендеринга их на холст карты. Чтобы визуализировать их, точки должны быть объединены в строки с использованием агрегатной функции ST_MakeLine () в PostGIS, оставляя пробелы на карте, где отсутствуют данные GPS. Данные не обязательно поступают по порядку с устройств.

Примерная последовательность выглядит так:

ID | Timestamp | Location -------------------------------------- 1 | 2013-11-12 03:31:31 | (1,2) 3 | 2013-11-12 03:31:34 | (1,3) 7 | 2013-11-12 03:31:37 | (1,4) 4 | 2013-11-12 03:31:43 | (1,5) 2 | 2013-11-12 03:31:55 | (1,6) 16 | 2013-11-12 03:33:22 | (1,7) 22 | 2013-11-12 03:33:28 | (1,8) 18 | 2013-11-12 03:33:32 | (1,9) 

Условия группировки:

  • Если разрыв предыдущей записи составляет> 30 секунд ИЛИ
  • Если время с первой записи в этой группе <15 секунд. В этом случае точка принадлежит к обеим группам (т.е. одна группа заканчивается этой точкой, начинается следующая группа)

Функция ST_MakeLine () в PostGIS создаст необходимую строку, проблема заключается в правильной группировке строк.

Исходя из этого, вышеизложенное приведет к:

 Start | End | ST_MakeLine(?) ---------------------------------------------------------------------------- 2013-11-12 03:31:31 | 2013-11-12 03:31:43 | LINE((1,2),(1,3),(1,4),(1,5)) 2013-11-12 03:31:43 | 2013-11-12 03:31:55 | LINE((1,5),(1,6)) 2013-11-12 03:33:22 | 2013-11-12 03:33:32 | LINE((1,7),(1,8),(1,9)) 

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

В настоящее время я обрабатываю данные вне SQL, чтобы генерировать последовательности, но это требует нескольких раундов, которые я бы хотел избежать, если смогу.

SQLFiddle из данных примера: http://sqlfiddle.com/#!15/1ff93/7

Я решил использовать двухкомпонентный подход, чтобы решить эту проблему:

  • Хранимая процедура, которая добавляет «идентификатор группы» к каждой строке
  • Простой агрегирующий запрос

Производительность значительно лучше, чем внешняя по отношению к базе данных (45 с против 2,8 с)

Итак, учитывая таблицу, созданную следующим образом:

 CREATE TABLE locations ( id SERIAL PRIMARY KEY, ts TIMESTAMP WITHOUT TIME ZONE, location GEOMETRY(Point,4326) ); 

Следующая функция будет перебирать по таблице и добавлять «групповой идентификатор» к каждой строке:

 CREATE FUNCTION group_locations( IN scan_start_time TIMESTAMP WITHOUT TIME ZONE, IN max_time_gap INTERVAL, IN max_line_duration INTERVAL) RETURNS TABLE( out_geom GEOMETRY, out_ts TIMESTAMP WITHOUT TIME ZONE, out_group_id INTEGER) AS $BODY$ DECLARE r locations%ROWTYPE; gid INTEGER; lastts TIMESTAMP; startts TIMESTAMP; BEGIN gid := 0; lastts := NULL; startts := NULL; FOR r IN SELECT * FROM locations WHERE ts > scan_start_time ORDER BY ts ASC LOOP out_ts := r.ts; out_geom := r.location; out_group_id := gid; IF startts IS NULL OR lastts IS NULL THEN startts := r.ts; ELSIF r.ts - lastts >= max_time_gap THEN -- If we've hit a space in our data, bump the group id up -- and remember the start time for this group gid := gid+1; out_group_id = gid; startts := r.ts; ELSIF r.ts - startts >= max_line_duration THEN -- First, emit the current row to end the group RETURN NEXT; -- Then, bump the group id and start time, we will -- re-emit the same row with a higher group_id below gid := gid+1; out_group_id := gid; startts := r.ts; END IF; -- Emit the current row with the group_id appended RETURN NEXT; lastts := r.ts; END LOOP; RETURN; END; $BODY$ LANGUAGE plpgsql VOLATILE; 

Если вы используете мои данные примера, результат:

 out_ts | out_geom | out_group_id --------------------------------------------- 2013-11-12 03:31:31 | (1,2) | 0 2013-11-12 03:31:34 | (1,3) | 0 2013-11-12 03:31:37 | (1,4) | 0 2013-11-12 03:31:43 | (1,5) | 0 2013-11-12 03:31:43 | (1,5) | 1 2013-11-12 03:31:55 | (1,6) | 1 2013-11-12 03:33:22 | (1,7) | 2 2013-11-12 03:33:28 | (1,8) | 2 2013-11-12 03:33:32 | (1,9) | 2 

Затем выход этой процедуры можно просто сгруппировать и агрегировать:

 SELECT ST_Makeline(out_geom) AS geom,MIN(out_ts) AS start,MAX(out_ts) AS finish FROM group_locations( NOW() AT TIME ZONE 'UTC' - '10 days'::INTERVAL, -- how far back to look '30 seconds'::INTERVAL, -- maximum gap allowed before creating a break '15 seconds'::INTERVAL -- maximum duration allowed before forcing a break ) GROUP BY out_group_id; 

Функция выполняется довольно быстро, по крайней мере на порядок лучше, чем выполнение одной и той же логики извне. Недостатком является то, что результаты не индексируются, поэтому непосредственное использование их в последующих запросах не особенно эффективно. Он работает примерно за время O (2N), первое сканирование добавляет идентификатор группы, затем второе сканирование для агрегирования.

Мое окончательное решение выполняет каждую пару минут, чтобы обновить таблицу «calculate_tracks», которая полностью проиндексирована.