主页 / coding / 问题 / 79489212
Accepted
gherkins
Asked: 2025-03-06 19:38:05 +0800 CST

按跨多个类别的重叠时间范围查询对象

  • 772
  • 10M+ 标记（特定时间范围）
  • 300k+ 引用对象（视频）

具有如下结构的标记：

{
  id: 123,
  category: 2,
  object: 'A',
  start: 10,
  end: 25
}

...产生不同类别的范围，如下所示：

category-1: ----------[===========]---------------------------- ref-object: A
category-1: --------------------------[====================]--- ref-object: A
category-1: ------------------[============================]--- ref-object: A
category-1: -----------------[==========================]------ ref-object: C
category-1: ------------------------------[================]--- ref-object: C

category-2: ----[===================]-------------------------- ref-object: A
category-2: -----[==========================]------------------ ref-object: B
category-2: -----[====================]------------------------ ref-object: C
category-2: -------------------------[=================]------- ref-object: C
category-2: ------------[===================================]-- ref-object: C

category-3: ----------------[=============]-------------------- ref-object: A
category-3: ----[===================================]---------- ref-object: A
category-3: -------[=======================================]--- ref-object: B
category-3: ----------------------------[====]----------------- ref-object: C
category-3: -------------[=================]------------------- ref-object: C

现在回答这样的问题：

查找所有具有重叠范围的对象， 最好按重叠时间总和category 1排序category 2

我能想到这些步骤

  • 查询：从一个类别开始，获取该类别中的所有标记
  • 代码：将范围缩小到几个更大的时间跨度（删除多余的时间跨度）
  • 查询：获取与这些时间跨度之一匹配的下一个类别的标记
  • 代码：将组合范围减少到几个更大的时间跨度（删除多余的时间跨度）
  • [...]
  • 代码：计算每个项目覆盖的时间跨度并进行相应排序

这是您想要用 SQL 做的事情吗？

这种类型的查询有名字吗？（它们不完全是范围查询，是吗？）

在这种情况下，考虑到数据量，是否存在具有内置功能的数据库？

目前，所有数据都存储在 Apache SOLR 索引中，但也可能存储在 Elasticsearch、InfluxDB 等中

sql

1 个回答

  1. Best Answer

    这是您想要用 SQL 做的事情吗？

    当然！而且很简单，为什么不尝试一下呢？

    with
    -- Where do segments intersect each other? 
    cuts as
    (
        select category, object, start t from m
        union -- Without "all" to deduplicate.
        select category, object, "end" from m
    ),
    -- Give those cuts an index, and compute the stop of the subsegment they start
    -- (the last cut having no next cut, will get a null stop:
    --  thus it's the only one that will not be considered a segment in the following joins)
    icuts as
    (
        select
            row_number() over () id,
            category, object,
            t ts, lead(t) over w te, lead(t) over w - t + 1 len
        from cuts
        window w as (partition by category, object order by t)
    ),
    -- Atomic marker segments: parts of markers that cannot be split anymore.
    mseg as
    (
        select m.id mid, m.category, m.object, s.id sid
        from m join icuts s on (s.category, s.object) = (m.category, m.object) and m.start <= s.ts and m.end >= s.te
    ),
    overl as
    (
        select sid, count(1) noverlaps
        from mseg
        group by sid
        having count(1) > 1
    )
select category, object, sum(len) totaloverlap
from overl o join icuts s on s.id = o.sid
group by 1, 2
order by 3 desc, 1, 2;

    将从您的示例返回（计算标记中的[和]，因此示例的最后一个标记[====]被认为持续时间为 6）：

    类别 目的 总重叠
    2 碳 三十四
    1 一个 二十七
    1 碳 15
    3 一个 15
    3 碳 4

    （如果你想玩的话这里有小提琴）

    对于 PostgreSQL 服务器来说，1000 万并不算多，但如果不进行测试就无法知道（……我会让 DBFiddle 免受这种负载）。不过，我相信它比从数据库到应用程序的往返运行速度更快。

    仍有改进的空间：所有(category, object)对都可以减少为单个integer；
    并且可以将 CTE 转储到表中然后进行索引。

    • 1

相关问题