我有一个简单的事件表:

event_id | start_time | end_time

如何查询最大同时事件数？

最佳答案

我的回答与哈利的第一个回答非常相似。不过，我会尝试进行稍微不同的性能优化……跳到最后以避免对原因的漫无边际的解释……

Harry的第一个答案(核心逻辑)

SELECT MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd                        
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
        t1.end_time BETWEEN t2.start_time AND t2.end_time
    GROUP BY t1.event_id
) AS foo

处理时间最长的地方是连接。

对于表中的每条记录，您选择 (t1.end time)。然后，您再次在表中搜索 (t1.end_time >= start_time) 以及您搜索的所有匹配记录 (t1.end_time <=>

现在，您很容易在 start_time 上创建索引。这使得第一次检查 (t1.end_time >= start_time) 更快；
- 索引是一种用于极速搜索的搜索树
- 这使得找到第一个匹配记录非常快
- 索引本质上是有序的
- 这意味着它知道“第一场比赛之后的所有比赛也比赛”

虽然最后一部分很关键，因为它意味着......即使在使用索引进行第一次检查(t1.end_time >= start_time)之后，我们仍然可以留下很多记录来进行第二次检查(t1.end_time <=>

[在索引中包含 end_time 在这里没有帮助，很快就会讨论]

0, '10:00', '10:04'   COUNT(*) WHERE '10:04' >= start_time  ==  4
1, '10:01', '10:06'   COUNT(*) WHERE '10:06' >= start_time  ==  4
2, '10:02', '10:09'   COUNT(*) WHERE '10:09' >= start_time  ==  5
3, '10:04', '10:07'   COUNT(*) WHERE '10:07' >= start_time  ==  4
4, '10:08', '10:12'   COUNT(*) WHERE '10:12' >= start_time  ==  6
5, '10:12', '10:17'   COUNT(*) WHERE '10:17' >= start_time  ==  7
6, '10:15', '10:18'   COUNT(*) WHERE '10:18' >= start_time  ==  8
7, '10:18', '10:22'   COUNT(*) WHERE '10:22' >= start_time  ==  10
8, '10:19', '10:24'   COUNT(*) WHERE '10:24' >= start_time  ==  10
9, '10:22', '10:25'   COUNT(*) WHERE '10:25' >= start_time  ==  10

=> leaves 68 rows to check the second condition; (t1.end_time <= t1.end_time)

假设事件分布相对平稳，每条记录将(大致和平均)与表的一半匹配。这意味着您正在执行 (n*n/2) 检查，其中 n 是表中的记录数。即使有 100 条记录，这也会产生 5000 张支票。在 2000 条记录下，您将进行大约 200 万次检查!

自然倾向于将 end_time 字段添加到索引中。但是，这无济于事。 (start_time, end_time) 的索引创建一个向下到每个唯一的 start_time 的搜索树，然后在每个唯一的 start_time 下有一个单独的 end_times 搜索树。

在我上面的示例中，每个 start_time 都是唯一的。这意味着您仍然需要执行所有 68 个 end_time 检查。只有 start_time 检查从索引中受益。

我们需要做的是尝试使用单一的“start_time”索引来做比现在更多的事情。我们需要为查询引擎提供更多信息。

一个例子是使用“最大事件持续时间”。例如，我们可能会发现没有任何事件持续超过 8 分钟。这将为我们提供以下查询...

SELECT MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd                        
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
            t1.end_time >= t2.start_time
        AND t1.end_time <= t2.end_time
        AND t1.end_time <= t2.start_time + [max_event_duration] 
    GROUP BY t1.event_id
) AS foo

在我上面给出的示例中应用 8 分钟持续时间的示例，我们将 68 次 end_time 检查减少到 34 次。

0, '10:00', '10:04'   COUNT(*) WHERE '10:04' BETWEEN start_time AND start_time + 8 == 4
1, '10:01', '10:06'   COUNT(*) WHERE '10:06' BETWEEN start_time AND start_time + 8 == 4
2, '10:02', '10:09'   COUNT(*) WHERE '10:09' BETWEEN start_time AND start_time + 8 == 4
3, '10:04', '10:07'   COUNT(*) WHERE '10:07' BETWEEN start_time AND start_time + 8 == 4
4, '10:08', '10:12'   COUNT(*) WHERE '10:12' BETWEEN start_time AND start_time + 8 == 3
5, '10:12', '10:17'   COUNT(*) WHERE '10:17' BETWEEN start_time AND start_time + 8 == 2
6, '10:15', '10:18'   COUNT(*) WHERE '10:18' BETWEEN start_time AND start_time + 8 == 3
7, '10:18', '10:22'   COUNT(*) WHERE '10:22' BETWEEN start_time AND start_time + 8 == 4
8, '10:19', '10:24'   COUNT(*) WHERE '10:24' BETWEEN start_time AND start_time + 8 == 3
9, '10:22', '10:25'   COUNT(*) WHERE '10:25' BETWEEN start_time AND start_time + 8 == 3

=> leaves 34 rows to check the second condition; (t1.end_time <= t1.end_time)
=> thats half the original 68, and on bigger tables the benefit increases...

即使我们不知道事件不会超过 8 分钟，我们也可以通过检查 10 条记录来找到它。 MAX(end_time - start_time) 超过 10 条记录仍然比 check (t1.end_time <= t1.end_time)="" 超过="" 34="">

并且随着表的大小增加， yield 也会增加。事实上，在 [max_event_duration] 明显小于表格涵盖的整个时间跨度的情况下，您可以将 (nn/2) 平方律更改为更类似于 (nx + n) 的东西是线性的。

民主党。

SELECT
   MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd                        
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
            t2.start_time <= t1.end_time
        AND t2.start_time >= t1.end_time - (SELECT MAX(end_time - start_time) FROM your_table)
        AND t2.end_time   >= t1.end_time
    GROUP BY t1.event_id
) AS foo

关于sql - 查询同时事件的最大数量，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/452499/