sql - 使用间距阈值对可变连续的带时间戳的记录进行分组

Question

我有一系列带有时间戳的间歇性间隔 GPS 坐标。我正在使用 PostGIS 将它们渲染到 map Canvas 上。要渲染它们，需要使用 PostGIS 中的 ST_MakeLine() 聚合函数将这些点聚合成线，从而在 map 上留下缺少 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 秒。在这种情况下，该点属于两组(即一组以该点结束，下一组开始)

PostGIS 中的 ST_MakeLine() 函数将生成必要的线，问题是正确地对线进行分组。

基于此，以上将产生:

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

Answer 1

我最终采用了两部分的方法来解决这个问题:

• 将“组 ID”附加到每一行的存储过程
• 一个简单的聚合查询

性能明显优于在数据库外部执行(45 秒对 2.8 秒)

因此，给定一个由以下内容创建的表:

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

以下函数将遍历表并将“组 ID”附加到每一行:

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) 时间，第一次扫描附加组 ID，然后第二次扫描聚合。

我的最终解决方案每隔几分钟执行一次上述操作，以刷新完全索引的“calculated_tracks”表。