时间戳

首页 > 解决方案 > SQL 中的高效（线性时间）嵌套查询

sql - SQL 中的高效（线性时间）嵌套查询

问题描述

从此表：

事件

ID 活动日期 event_score
12 2020-04-10
13 2020-04-11
13 2020-04-14 8
13 2020-04-13 6
12 2020-04-15
14 2020-04-16
14 2020-04-17
14 2020-04-18 11
14 2020-04-19
14 2020-04-20
14 2020-04-22
12 2020-04-25
14 2020-04-30

我试图得到这个结果

结果

ID first_score last_score
12
13 6 8
14 11 11

一种方法是通过此查询：

SELECT
    DISTINCT id,
    (
        SELECT event_score
        FROM events AS subquery
        WHERE final_table.id=subquery.id
        AND event_score IS NOT NULL
        ORDER BY event_date
        LIMIT 1
    ) AS `first score`,
    (
        SELECT event_score
        FROM events AS subquery
        WHERE final_table.id=subquery.id
        AND event_score IS NOT NULL
        ORDER BY event_date DESC
        LIMIT 1
    ) AS `last score`
FROM sensors.events as final_table

但我怀疑这需要二次时间 O(n*n) 来计算。我知道它可以用 Python 在线性时间 O(n) 内完成，但有人知道如何用 SQL 在线性时间内完成吗？

该表在 MariaDB/MySQL 中

标签： sqlmariadbpivotquery-optimizationgaps-and-islands

解决方案

使用 上的索引(id, event_date, event_sore)，那么这应该非常快：

SELECT id,
       (SELECT event_score
        FROM events AS subquery
        WHERE final_table.id = subquery.id AND event_score IS NOT NULL
        ORDER BY event_date
        LIMIT 1
       ) AS `first score`,
       (SELECT event_score
        FROM events AS subquery
        WHERE final_table.id=subquery.id AND event_score IS NOT NULL
        ORDER BY event_date DESC
        LIMIT 1
       ) AS `last score`
FROM (SELECT DISTINCT e.id
      FROM sensors.events e
     ) as final_table;

请注意，这会将 移动SELECT DISTINCT到子查询。这是为了确保 MariaDB 实际上不使用“不同的”算法SELECT DISTINCT——其他列可能会导致这种情况发生。

但是，这是 O(n log n)，因为子查询需要为每个子查询排序少量数据id——以及使用索引来到达正确的位置。

我想不出在 SQL 中执行此 O(n) 的方法。我很确定以下构造都是 O(n log n)：

  • 为每一行使用一个索引。
  • 对数据的任何部分进行排序。
  • 使用任何带有order by-- 的窗口函数，尽管如果只有正确的索引，这可能是正确的。

但是，SQL 查询仍然很快，尤其是索引。

推荐阅读