SQL:找到最长的日期差距

Question

我有一个包含2个字段的表:唯一ID,用户ID(外键)和日期时间.这是服务的访问日志.我在SQL Server工作,但我会欣赏不可知的答案.

我想使用SQL为某个用户查找最长间隙开始的ID.

例如,假设我的值如下(一个用户的简化):

ID |  User-ID |  Time
----------------------------------
1  |  1       |  11-MAR-09, 8:00am
2  |  1       |  11-MAR-09, 6:00pm
3  |  1       |  13-MAR-09, 7:00pm
4  |  1       |  14-MAR-09, 6:00pm

如果我为用户1搜索最长的间隙,我将获得ID 2(在那里得到间隙的长度也很好,然后,但更不重要).

在SQL中实现这一目标的最有效方法是什么？

注意:ID不一定是顺序的.

谢谢

Answer 1

与数据库无关,属于richardtallent的变体,但没有限制.

从这个设置开始:

create table test(id int, userid int, time datetime)
insert into test values (1, 1, '2009-03-11 08:00')
insert into test values (2, 1, '2009-03-11 18:00')
insert into test values (3, 1, '2009-03-13 19:00')
insert into test values (4, 1, '2009-03-14 18:00')

(我在这里是SQL Server 2008,但它应该没关系)

运行此查询:

select 
  starttime.id as gapid, starttime.time as starttime, endtime.time as endtime, 
  /* Replace next line with your DB's way of calculating the gap */
  DATEDIFF(second, starttime.time, endtime.time) as gap
from 
  test as starttime
inner join test as endtime on 
  (starttime.userid = endtime.userid) 
  and (starttime.time < endtime.time) 
left join test as intermediatetime on 
  (starttime.userid = intermediatetime.userid) 
  and (starttime.time < intermediatetime.time) 
  and (intermediatetime.time < endtime.time) 
where 
  (intermediatetime.id is null)

给出以下内容:

gapid  starttime                endtime                  gap
1      2009-03-11 08:00:00.000  2009-03-11 18:00:00.000  36000
2      2009-03-11 18:00:00.000  2009-03-13 19:00:00.000  176400
3      2009-03-13 19:00:00.000  2009-03-14 18:00:00.000  82800

然后,您可以按顺序删除间隙表达式,然后选择顶部结果.

一些解释:像richardtallent的回答一样,你加入表格以找到一个'后来'的记录 - 这基本上将所有记录与他们后来的记录中的任何一对(所以对1 + 2,1 + 3,1 + 4,2 +) 3,2 + 4,3 + 4).然后是另一个自连接,这次是左连接,找到之前选择的两个之间的行(1 + 2 + null,1 + 3 + 2,1 + 4 + 2,1 + 4 + 3,2 + 3 + null,2 + 4 + 3,3 + 4 + null).但是,WHERE子句将这些过滤掉(仅保留没有中间行的行),因此只保留1 + 2 + null,2 + 3 + null和3 + 4 + null.TAA-DAA!

如果可能的话,可能会在那里有两次相同的时间('间隙'为0)那么你需要一种方法来打破关系,正如Dems指出的那样.如果你可以使用ID作为决胜局,那么改变例如

and (starttime.time < intermediatetime.time) 

至

and ((starttime.time < intermediatetime.time) 
  or ((starttime.time = intermediatetime.time) and (starttime.id < intermediatetime.id)))

假设'id'是打破关系的有效方式.

事实上,如果你知道 ID会单调增加(我知道你说'不顺序' - 不清楚这是否意味着它们不会随着每一行增加,或者只是两个相关条目的ID可能不是顺序因为例如另一个用户之间有条目),你可以在所有比较中使用ID而不是时间来使这更简单.

Answer 2

加入一次性排名的时间以获得差距：

with cte_ranked as (
select *, row_number() over (partition by UserId order by Time) as rn
from table)
select l.*, datediff(minute, r.Time, l.Time) as gap_length
from cte_ranked l join cte_ranked r on l.UserId = r.UserId and l.rn = r.rn-1

然后，您可以使用多种方法来确定最大间隙、何时开始等。

更新

我最初的答案是从 Mac w/oa 数据库编写的，用于测试。我有更多的时间来解决这个问题，并实际测试和测量它在 1M 记录表上的性能。我的测试表定义如下：

create table access (id int identity(1,1)
    , UserId int not null
    , Time datetime not null);
create clustered index cdx_access on access(UserID, Time);
go

对于选择任何信息的记录，到目前为止我的首选答案是：

with cte_gap as (
    select Id, UserId, a.Time, (a.Time - prev.Time) as gap
    from access a
    cross apply (
        select top(1) Time 
        from access b
        where a.UserId = b.UserId
            and a.Time > b.Time
        order by Time desc) as prev)
, cte_max_gap as (
    select UserId, max(gap) as max_gap
    from cte_gap
    group by UserId)
select g.* 
    from cte_gap g
    join cte_max_gap m on m.UserId = g.UserId and m.max_gap = g.gap
where g.UserId = 42;

从 1M 记录到约 47k 个不同用户，在我的测试小实例（热缓存）上，结果在 1 毫秒内返回，读取 48 个页面。

如果删除 UserId=42 过滤器，则每个用户的最大间隙和发生时间（多个最大间隙有重复项）需要 6379139 次读取，相当繁重，在我的测试机器上需要 14 秒。

如果只需要 UserId 和最大间隙（最大间隙发生时没有信息），时间可以减少一半：

select UserId, max(a.Time-prev.Time) as gap
    from access a
    cross apply (
        select top(1) Time 
        from access b
        where a.UserId = b.UserId
            and a.Time > b.Time
        order by Time desc
    ) as prev
group by UserId

这只需要 3193448 次读取，只有之前的一半，并且在 1M 条记录上 6 秒内完成。之所以会出现这种差异，是因为以前的版本需要对每个间隙进行一次评估以找到最大间隙，然后再次评估它们以找到与最大值相等的间隙。请注意，对于此性能结果，我建议在 (UserId, Time) 上建立索引的表结构至关重要。

至于 CTE 和“分区”（更广为人知的名称是排名函数）的使用：这都是 ANSI SQL-99，并且大多数供应商都支持。唯一的 SQL Server 特定构造是该函数的使用datediff，现已删除。我有一种感觉，一些读者将“不可知论”理解为“我最喜欢的供应商也理解的最小公分母 SQL”。另请注意，公共表表达式和交叉应用运算符的使用仅用于提高查询的可读性。两者都可以使用简单的机械替换来替换为派生表。这是完全相同的查询，其中 CTE 替换为派生表。我会让你根据它与基于 CTE 的可读性进行比较来判断：

select g.*
    from (    
        select Id, UserId, a.Time, (a.Time - (
            select top(1) Time 
            from access b
            where a.UserId = b.UserId
                and a.Time > b.Time
            order by Time desc
        )) as gap
        from access a) as g
    join (
        select UserId, max(gap) as max_gap
            from (
                select Id, UserId, a.Time, (a.Time - (
                   select top(1) Time 
                   from access b
                   where a.UserId = b.UserId
                     and a.Time > b.Time
                   order by Time desc
                   )) as gap
            from access a) as cte_gap
        group by UserId) as m on m.UserId = g.UserId and m.max_gap = g.gap
    where g.UserId = 42

该死，我希望最终会更加复杂，哈哈。这是非常可读的，因为它只有两个 CTE 可供开始。尽管如此，对于具有 5-6 个派生表的查询，CTE 形式的可读性要高得多。

为了完整起见，以下是应用于我的简化查询的相同转换（仅最大间隙，没有间隙结束时间和访问 ID）：

select UserId, max(gap)
    from (
        select UserId, a.Time-(
            select top(1) Time 
            from access b
            where a.UserId = b.UserId
                and a.Time > b.Time
            order by Time desc) as gap
    from access a) as gaps
group by UserId