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

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 至 return 进行比较，首先是 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 查询与上面的 table 来比较给定的日期和间隔与从 table 到每个日期和间隔对找到这两个重叠的下一个日期以及每个重叠实例相隔多远？

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;

db<>fiddle here - 更多测试行

可能有进一步改进的潜力。核心问题在
领域 质因数分解。由于期望相当小的间隔似乎是合理的，我通过测试周期解决了这个问题：如果在逐步向前推进时，检测到我们之前看到的日期之间的差距，并且日期还没有重叠，它们将从不重叠，我们可以停下来。这最多循环 GREATEST(m_step, t_step) 次（较大间隔中的天数），因此它不应该扩展得很厉害。

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

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

然后，虽然间隔很小，但基于 generate_series() 的 "brute force" 方法可能仍然更快。

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

Find the nearest overlap between given time series

sql

postgresql

date-math

intervals