sql - 找到给定时间序列之间最近的重叠

Question

我正在构建一个调度系统，在其中存储初始约会及其重复频率。我的 table 看起来像这样:

CREATE TABLE (
    id serial primary key,
    initial_timestamp timestamp not null,
    recurring interval
);

id        initial_timestamp          recurring
27        2020-06-02                 3 weeks
24        2020-06-03                 10 days

假设我可以处理时间部分，并且我们将运行的唯一间隔是几天和几周，我如何才能找到这两个约会重叠的时间？例如，上一个示例将在 6 月 23 日重叠。从6月2日开始是3周，从6月3日开始是20天，所以第一次约会将在当天重复一次，第二次约会将在13日和23日重复。

在我的程序中，我还有另一个日期，比如 6 月 7 日，重复间隔为 12 天。我可以使用什么查询来查找从 6 月 7 日开始的定期约会与每个现有的定期约会重叠所需的时间？例如，此约会将在 6 月 19 日、7 月 1 日和 7 月 13 日重复。如果我的数学正确，上表中的约会 #24 将在 6 月 13 日、6 月 23 日、7 月 3 日和 7 月 13 日重复。我希望我的查询将这次约会与约会 #24 进行比较，首先返回 7 月 13 日，然后再重复一次需要多长时间，我认为这就像找到两个间隔的最小公倍数，在这种情况下，60 天(LCM 为 12 和 10)。所以我可以预期它会在 7 月 13 日 + 60 天 = 9 月 11 日再次重复。

我尝试使用 generate_series，但由于我不知道间隔的大小，该系列将不得不无限地继续，对吗？这可能不是这里的最佳选择。我认为答案更多地与以某种方式相乘间隔的数学有关。

请注意 recurring可以为空，所以我认为必须有类似 WHERE recurring IS NOT NULL 的东西在那里某处。另一件需要注意的事情:初次约会没有重叠。我已经对此有所防范。搜索词也不与任何约会的初始时间重叠。

如果它有帮助，我正在使用 PHP 5.3 向 Postgres 9.4 发送查询(我知道，这是一个古老的设置)。我更喜欢在 SQL 中完成大部分工作，因为大多数其他逻辑现在都在 SQL 中，所以我可以运行查询并开始使用 PHP 处理结果。

所以总而言之，如果我的数学是正确的，我应该使用什么 Postgres 查询和上表来比较给定的日期和间隔与表中的每个日期和间隔对，以找到这两个重叠的下一个日期以及每个重叠的距离实例会是？

Answer 1

这是 硬 .

WITH RECURSIVE moving_target(initial_timestamp, recurring) AS (
   VALUES (timestamp '2020-06-07', interval '12 days')  -- search term
   )
,  x AS (         -- advance to the closest day before or at moving target
   SELECT t.id
        , t_date + ((m_date - t_date) / t_step) * t_step AS t_date
        , t_step
        , m.*
   FROM  (        -- normalize table data
      SELECT id
           , initial_timestamp::date AS t_date
           , EXTRACT ('days' FROM recurring)::int AS t_step
      FROM   tbl
      WHERE  recurring IS NOT NULL  -- exclude!
      ) t
   CROSS  JOIN (  -- normalize input
      SELECT initial_timestamp::date AS m_date
           , EXTRACT ('days' FROM recurring)::int AS m_step
      FROM   moving_target
      ) m
   )
, rcte AS (       -- recursive CTE
   SELECT id, t_date, t_step, m_date, m_step
        , ARRAY[m_date - t_date] AS gaps        -- keep track of gaps
        , CASE
            WHEN t_date = m_date     THEN true  -- found match
            WHEN t_step % m_step = 0 THEN false -- can never match
            WHEN (m_date - t_date) % 2 = 1      -- odd gap ...
             AND t_step % 2 = 0                 -- ... but even steps
             AND m_step % 2 = 0      THEN false -- can never match
         -- WHEN <stop conditions?>  THEN false -- hard to determine!
         -- ELSE                          null  -- keep searching
          END AS match
   FROM   x

   UNION ALL
   SELECT id, t_date, t_step, m_date, m_step
        , gaps || m_date - t_date
        , CASE
            WHEN t_date = m_date                THEN true
            WHEN (m_date - t_date) = ANY (gaps) THEN false  -- gap repeated!
         -- ELSE                                     null   -- keep searching
          END AS match
   FROM  (
      SELECT id
           , t_date + (((m_date + m_step) - t_date) / t_step) * t_step AS t_date
           , t_step
           , m_date + m_step AS m_date -- + 1 step
           , m_step
           , gaps
      FROM   rcte
      WHERE  match IS NULL
      ) sub
   )
SELECT id, t.initial_timestamp, t.recurring
     , CASE WHEN r.match THEN r.t_date END AS match_date
FROM   rcte r
JOIN   tbl  t USING (id)
WHERE  r.match IS NOT NULL;

分贝<> fiddle here - 有更多的测试行

可能有进一步改进的潜力。核心问题在于
质因数分解 .由于期望相当小的间隔似乎是合理的，因此我通过测试周期来解决它:如果在逐步向前推进时，检测到我们之前见过的日期之间的差距，并且日期尚未重叠，则它们将永远不会重叠并且我们可以停下来。这最多循环 GREATEST(m_step, t_step)次(较大间隔中的天数)，所以它不应该非常严重。

我确定了一些基本的数学停止条件，以避免先验地在无望的情况下循环。可能还有更多...

解释这里发生的一切比设计查询更重要。我添加了应该解释基础知识的评论......

再说一次，虽然间隔很小，但基于 generate_series() 的“蛮力”方法可能仍然更快。