一个有趣的时间段重叠问题

用户1148526

发布于 2019-05-25 19:35:26

4.3K0

发布于 2019-05-25 19:35:26

一、问题描述

    某一直播业务记录了如下格式的用户进出直播间日志数据：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      1 |      1 | 2018-01-01 01:01:01 | 2018-01-01 01:10:01
      1 |      2 | 2018-01-01 01:01:02 | 2018-01-01 01:01:05
      1 |      3 | 2018-01-01 01:01:05 | 2018-01-01 01:02:05
      2 |      4 | 2018-01-01 01:03:02 | 2018-01-01 01:12:05
      2 |      5 | 2018-01-01 01:11:02 | 2018-01-01 01:12:05
      2 |      6 | 2018-01-01 01:15:02 | 2018-01-01 01:16:05
      2 |      7 | 2018-01-01 01:01:03 | 2018-01-01 01:11:05
      1 |      1 | 2018-01-01 01:01:05 | 2018-01-01 01:10:01
      1 |      1 | 2018-01-01 01:01:02 | 2018-01-01 01:11:01
      2 |      1 | 2018-01-01 01:01:03 | 2018-01-03 01:11:01
      2 |      8 | 2018-01-01 23:01:03 | 2018-01-02 01:11:01
(9 rows)

    四个字段分别表示直播间ID、用户ID、进入时间和退出时间。求每天每个活跃房间的峰值人数和总时长。活跃房间的定义是：以每秒为时间刻度，如果在某一时刻同时有两个及其以上的用户在房间内，该房间当天即为活跃房间。峰值人数是指一天内同时在一个活跃房间的最大人数。总活跃时长是指一天内活跃时长的总和。

二、问题分析

    这是一个典型的重叠时间段的统计问题。具体来说，有这样几个问题需要解决：1. 一个房间内同一用户的重叠时间段合并；2. 拆分起止时间段跨天的时段；3. 取得活跃的时段；4. 按天计算每个房间活跃时段内的不同用户数及其活跃时段的长度；4. 选取活跃时段内的最大人数，并汇总活跃时长。

1. 一个房间内同一用户的重叠时段问题

    任意给定的一个房间，用户在其内的时间存在重叠部分，而重叠又分同一用户的重叠与不同用户之间重叠两种情况。对于第一种情况，在判断房间是否活跃时，不应该对用户重复计数，因此这部分的活跃时长需要进行合并。例如，2018-01-01日，用户1在房间1有三条日志记录：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      1 |      1 | 2018-01-01 01:01:01 | 2018-01-01 01:10:01
      1 |      1 | 2018-01-01 01:01:05 | 2018-01-01 01:10:01
      1 |      1 | 2018-01-01 01:01:02 | 2018-01-01 01:11:01

    为了判断房间1在'2018-01-01 01:01:01'和'2018-01-01 01:11:01'之间是否存在活跃时间段，需要将三条记录合并为如下一条记录：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      1 |      1 | 2018-01-01 01:01:01 | 2018-01-01 01:11:01

    这步处理后，日志记录变成：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      1 |      1 | 2018-01-01 01:01:01 | 2018-01-01 01:11:01
      1 |      2 | 2018-01-01 01:01:02 | 2018-01-01 01:01:05
      1 |      3 | 2018-01-01 01:01:05 | 2018-01-01 01:02:05
      2 |      1 | 2018-01-01 01:01:03 | 2018-01-03 01:11:01
      2 |      4 | 2018-01-01 01:03:02 | 2018-01-01 01:12:05
      2 |      5 | 2018-01-01 01:11:02 | 2018-01-01 01:12:05
      2 |      6 | 2018-01-01 01:15:02 | 2018-01-01 01:16:05
      2 |      7 | 2018-01-01 01:01:03 | 2018-01-01 01:11:05
      2 |      8 | 2018-01-01 23:01:03 | 2018-01-02 01:11:01
(9 rows)

2. 起止时段跨天的问题

    由于是按天进行统计，对于进出时间点跨天的情况，要进行拆分。例如，用户1在房间2的进出时间跨越了三天：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      2 |      1 | 2018-01-01 01:01:03 | 2018-01-03 01:11:01

    为了统计'2018-01-01'、'2018-01-02'、'2018-01-03'三天的数据，需要将这条记录拆分为如下三条记录：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      2 |      1 | 2018-01-01 01:01:03 | 2018-01-01 23:59:59
      2 |      1 | 2018-01-02 00:00:00 | 2018-01-02 23:59:59
      2 |      1 | 2018-01-03 00:00:00 | 2018-01-03 01:11:01

    拆分的起止时间相差一秒，而并不相同。在后面介绍计算活跃时间段内的不同用户数及其活跃时长的算法时，会看到这点非常重要。这步处理后，日志记录变成：

 roomid | userid |          s          |          e          
--------+--------+---------------------+---------------------
      1 |      1 | 2018-01-01 01:01:01 | 2018-01-01 01:11:01
      1 |      2 | 2018-01-01 01:01:02 | 2018-01-01 01:01:05
      1 |      3 | 2018-01-01 01:01:05 | 2018-01-01 01:02:05
      2 |      4 | 2018-01-01 01:03:02 | 2018-01-01 01:12:05
      2 |      5 | 2018-01-01 01:11:02 | 2018-01-01 01:12:05
      2 |      6 | 2018-01-01 01:15:02 | 2018-01-01 01:16:05
      2 |      7 | 2018-01-01 01:01:03 | 2018-01-01 01:11:05
      2 |      1 | 2018-01-01 01:01:03 | 2018-01-01 23:59:59
      2 |      1 | 2018-01-03 00:00:00 | 2018-01-03 01:11:01
      2 |      1 | 2018-01-02 00:00:00 | 2018-01-02 23:59:59
      2 |      8 | 2018-01-02 00:00:00 | 2018-01-02 01:11:01
      2 |      8 | 2018-01-01 23:01:03 | 2018-01-01 23:59:59
(12 rows)

3. 如何取得活跃时段

    经过了前两步的数据预处理，我们就可以用一种高效的方式得到活跃时段。该算法的核心思想是：将所有的进出时间点统一排序，同时记录每个时间点的进出用户数。这样我们可以将在线时间分成多个互斥的时间段，并且利用当前时间点前面的所有累计进出用户数，作为前一个时间点到当前时间点的重叠度，也即不同用户数。算法具体步骤如下。

（1）将所有进入时间点和退出时间点合并成一列，将进入时间标记为1，退出时间标记为-1。实际上，1表示在对应的时间点有一个用户进入，-1表示在对应的时间点有一个用户退出。这步处理后的记录变为：

 roomid |         ts          | type 
--------+---------------------+------
      1 | 2018-01-01 01:01:01 |    1
      1 | 2018-01-01 01:01:02 |    1
      2 | 2018-01-01 01:01:03 |    1
      2 | 2018-01-01 01:01:03 |    1
      1 | 2018-01-01 01:01:05 |    1
      1 | 2018-01-01 01:01:05 |   -1
      1 | 2018-01-01 01:02:05 |   -1
      2 | 2018-01-01 01:03:02 |    1
      1 | 2018-01-01 01:11:01 |   -1
      2 | 2018-01-01 01:11:02 |    1
      2 | 2018-01-01 01:11:05 |   -1
      2 | 2018-01-01 01:12:05 |   -1
      2 | 2018-01-01 01:12:05 |   -1
      2 | 2018-01-01 01:15:02 |    1
      2 | 2018-01-01 01:16:05 |   -1
      2 | 2018-01-01 23:01:03 |    1
      2 | 2018-01-01 23:59:59 |   -1
      2 | 2018-01-01 23:59:59 |   -1
      2 | 2018-01-02 00:00:00 |    1
      2 | 2018-01-02 00:00:00 |    1
      2 | 2018-01-02 01:11:01 |   -1
      2 | 2018-01-02 23:59:59 |   -1
      2 | 2018-01-03 00:00:00 |    1
      2 | 2018-01-03 01:11:01 |   -1
(24 rows)

（2）按房间和时间点分组，对标志位汇总聚合，目的是去除重复的时间点。重复时间点表示在同一秒有多个用户进入、或者退出、或者进入退出同一个房间。汇总的目的就是确定在该时间点，最终进出的用户数。这一步是必须的，原因有两个：1. 我们必须保证对于一个房间每个时间点是唯一的；2. 必须确定某一时间点的进出方向和进出数量。这两个点是保证算法成立的充要条件。出于同样的理由，在拆分跨天记录时，为保持时间点的唯一性，起止时间相差一秒。这步处理后的记录变为：

--------+---------------------+------
      1 | 2018-01-01 01:01:01 |    1
      1 | 2018-01-01 01:01:02 |    1
      2 | 2018-01-01 01:01:03 |    2
      1 | 2018-01-01 01:01:05 |    0
      1 | 2018-01-01 01:02:05 |   -1
      2 | 2018-01-01 01:03:02 |    1
      1 | 2018-01-01 01:11:01 |   -1
      2 | 2018-01-01 01:11:02 |    1
      2 | 2018-01-01 01:11:05 |   -1
      2 | 2018-01-01 01:12:05 |   -2
      2 | 2018-01-01 01:15:02 |    1
      2 | 2018-01-01 01:16:05 |   -1
      2 | 2018-01-01 23:01:03 |    1
      2 | 2018-01-01 23:59:59 |   -2
      2 | 2018-01-02 00:00:00 |    2
      2 | 2018-01-02 01:11:01 |   -1
      2 | 2018-01-02 23:59:59 |   -1
      2 | 2018-01-03 00:00:00 |    1
      2 | 2018-01-03 01:11:01 |   -1
(19 rows)

（3）按房间分组，时间点排序，取得当前时间点的前一个时间点对应的进出用户数。如果没有前一个时间点，说明是该房间的第一次进入，前一个时间点对应的进出用户数设为0。这步处理后的记录变为：

 roomid |         ts          | type | prevtype 
--------+---------------------+------+----------
      1 | 2018-01-01 01:01:01 |    1 |        0
      1 | 2018-01-01 01:01:02 |    1 |        1
      1 | 2018-01-01 01:01:05 |    0 |        1
      1 | 2018-01-01 01:02:05 |   -1 |        0
      1 | 2018-01-01 01:11:01 |   -1 |       -1
      2 | 2018-01-01 01:01:03 |    2 |        0
      2 | 2018-01-01 01:03:02 |    1 |        2
      2 | 2018-01-01 01:11:02 |    1 |        1
      2 | 2018-01-01 01:11:05 |   -1 |        1
      2 | 2018-01-01 01:12:05 |   -2 |       -1
      2 | 2018-01-01 01:15:02 |    1 |       -2
      2 | 2018-01-01 01:16:05 |   -1 |        1
      2 | 2018-01-01 23:01:03 |    1 |       -1
      2 | 2018-01-01 23:59:59 |   -2 |        1
      2 | 2018-01-02 00:00:00 |    2 |       -2
      2 | 2018-01-02 01:11:01 |   -1 |        2
      2 | 2018-01-02 23:59:59 |   -1 |       -1
      2 | 2018-01-03 00:00:00 |    1 |       -1
      2 | 2018-01-03 01:11:01 |   -1 |        1
(19 rows)

（4）取当前时间点的前一个时间点作为起始时间，当前时间点作为终止时间，将房间的在线时间区间划分成互斥时段。用当前时间点前面的所有累计进出用户数，作为该时段的重叠度。这步处理后的记录变为，rn即为starttime和endtime这段时间内的不同用户数：

 roomid |      starttime      | prevtype |       endtime       | rn 
--------+---------------------+----------+---------------------+----
      1 |                     |        0 | 2018-01-01 01:01:01 |  0
      1 | 2018-01-01 01:01:01 |        1 | 2018-01-01 01:01:02 |  1
      1 | 2018-01-01 01:01:02 |        1 | 2018-01-01 01:01:05 |  2
      1 | 2018-01-01 01:01:05 |        0 | 2018-01-01 01:02:05 |  2
      1 | 2018-01-01 01:02:05 |       -1 | 2018-01-01 01:11:01 |  1
      2 |                     |        0 | 2018-01-01 01:01:03 |  0
      2 | 2018-01-01 01:01:03 |        2 | 2018-01-01 01:03:02 |  2
      2 | 2018-01-01 01:03:02 |        1 | 2018-01-01 01:11:02 |  3
      2 | 2018-01-01 01:11:02 |        1 | 2018-01-01 01:11:05 |  4
      2 | 2018-01-01 01:11:05 |       -1 | 2018-01-01 01:12:05 |  3
      2 | 2018-01-01 01:12:05 |       -2 | 2018-01-01 01:15:02 |  1
      2 | 2018-01-01 01:15:02 |        1 | 2018-01-01 01:16:05 |  2
      2 | 2018-01-01 01:16:05 |       -1 | 2018-01-01 23:01:03 |  1
      2 | 2018-01-01 23:01:03 |        1 | 2018-01-01 23:59:59 |  2
      2 | 2018-01-01 23:59:59 |       -2 | 2018-01-02 00:00:00 |  0
      2 | 2018-01-02 00:00:00 |        2 | 2018-01-02 01:11:01 |  2
      2 | 2018-01-02 01:11:01 |       -1 | 2018-01-02 23:59:59 |  1
      2 | 2018-01-02 23:59:59 |       -1 | 2018-01-03 00:00:00 |  0
      2 | 2018-01-03 00:00:00 |        1 | 2018-01-03 01:11:01 |  1
(19 rows)

（5）按天统计每个房间活跃时长（重叠度大于1的时段汇总），并求出活跃时段的峰值人数（最大重叠度）。最终结果如下，其中dur为活跃时长（单位舍入为分钟），c是峰值人数：

 roomid |     dt     | dur | c 
--------+------------+-----+---
      1 | 2018-01-01 |   1 | 2
      2 | 2018-01-01 |  71 | 4
      2 | 2018-01-02 |  71 | 2
(3 rows)

三、实现及测试

    本实验在HAWQ集群数据库上进行，使用Postgresql 8.2.15兼容的SQL语句。

1. 建立测试表并生成数据

create table test1 (roomid int, userid int, s timestamp, e timestamp);
insert into test1 values
(1, 1, '2018-01-01 01:01:01', '2018-01-01 01:10:01'),
(1, 2, '2018-01-01 01:01:02', '2018-01-01 01:01:05'),
(1, 3, '2018-01-01 01:01:05', '2018-01-01 01:02:05'),
(2, 4, '2018-01-01 01:03:02', '2018-01-01 01:12:05'),
(2, 5, '2018-01-01 01:11:02', '2018-01-01 01:12:05'),
(2, 6, '2018-01-01 01:15:02', '2018-01-01 01:16:05'),
(2, 7, '2018-01-01 01:01:03', '2018-01-01 01:11:05'),
(1, 1, '2018-01-01 01:01:05', '2018-01-01 01:10:01'),
(1, 1, '2018-01-01 01:01:02', '2018-01-01 01:11:01'),
(2, 1, '2018-01-01 01:01:03', '2018-01-03 01:11:01'),
(2, 8, '2018-01-01 23:01:03', '2018-01-02 01:11:01');

2. SQL查询语句

with c1 as  -- 合并同一房间同一用户的重叠时间段，用于统计峰值人数  
(  
   select distinct roomid,userid,min(s) s,max(e) e   
     from (select roomid,userid,s,e,  
                  sum(broken) over (partition by roomid, userid order by s,e) flag  
             from (select t.*,  
                          (case when s <= max(e) over (partition by roomid, userid order by s,e rows between unbounded preceding and 1 preceding) then 0  
                           else 1  
                            end) as broken  
                     from (select roomid,userid,s, e from test1 ) t  
                   ) t  
           ) t    
    group by roomid,userid,flag  
),  
c2 as  -- 拆分跨天的时间段  
(  
   select *   
     from (select roomid,userid,s,e   
             from c1  
            where date(s) = date(e)  -- 不跨天  
            union all  
           select roomid,userid,  
                  case when id = 1 then s else date(s)+id-1 end s,  
                  case when id = m2 then e else (date(s)+id)::timestamp + '-1 sec'  end e       
             from (select roomid,userid,s,e,id,  
                          max(id) over (partition by roomid,userid,s) m2  
                     from c1,nums  
                    where date(s) <> date(e) -- 跨天  
                      and id <= date(e)-date(s)+1) t1) t1  
),  
c3 as -- 在计算最小范围的同时,计算区间用户数  
(  
  
      select roomid,ts endtime,sum(prevType) over(partition by roomid order by ts) rn,   
      lag(ts) over (partition by roomid order by ts) starttime  
      from (  
        select a.*,coalesce(lag(type) over (partition by roomid order by ts),0) prevType  
        from (  
          select   
          roomid,ts,sum(type) type  
          from (  
              select roomid,e ts, -1 type  
              from c2  
              union all  
              select roomid,s ts, 1 type  
              from c2  
          ) t1 group by roomid,ts  
        ) a  
      ) c  
)
select roomid,dt,round(sum(dur)/60) ts,max(rn) c from (  
  select roomid,date(starttime) dt,extract(epoch from (endtime - starttime)) dur,rn   
  from c3 where rn>=2 and date(endtime)=date(starttime) and starttime is not null     
)   t
group by roomid,dt  
order by roomid,dt;

    结果：

 roomid |     dt     | ts | c 
--------+------------+----+---
      1 | 2018-01-01 |  1 | 2
      2 | 2018-01-01 | 71 | 4
      2 | 2018-01-02 | 71 | 2
(3 rows)

    说明：

使用内嵌视图技术用一条SQL语句实现。
使用窗口函数执行同一房间同一用户的合并操作。between unbounded preceding and 1 preceding表示从partition开始到当前行的前一行聚合。
由于HAWQ目前不支持递归查询，在生成C2时，使用了数字辅助表nums，目的是将一行转成多行。nums的数据是一个从1开始的序列，记录个数只需要等于最大跨越的天数加一即可。可以预先生成nums表的数据。create table nums(id); insert into nums values (1),(2),(3),(4),(5),(6),(7),(8),(9),(10);
性能考虑。只是生成C1会读一遍表，其它操作和计算在内存中执行。即使生成C3时内存中处理的记录数会翻倍，相对于自关联、或最小粒度（秒表）连接等方式，该算法的性能还是很不错的。

    核心算法的推导过程和基于MySQL的实现，参见江湖人称“书神”的系列文章“[Session重叠问题学习(二)](http://blog.itpub.net/29254281/viewspace-2150229/)”到“[Session重叠问题学习(九)](http://blog.itpub.net/29254281/viewspace-2150486/)”。