找出给定时间序列之间最接近的重合点。

Question

我正在建立一个日程安排系统，我在这里存储一个初始预约和重复的频率。我的表看起来像这样。

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天（12和10的LCM）。所以我可以预期它在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;

db<>小提琴 此处 - 有更多的测试行

可能还有进一步改进的潜力。核心问题是在以下领域： 质因式分解. 由于期望相当小的间隔似乎是合理的，我通过测试周期来解决它。如果在前进的过程中，发现日期之间有差距 我们以前也见过，而且日期还没有重叠，那么它们就会被发现 从来没有 重叠，我们可以停止。这个循环最多 GREATEST(m_step, t_step) 次（较大区间的天数），所以应该不会有太大的规模。

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

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

话又说回来，虽然区间很小，但基于 "蛮力 "的方法，在 generate_series() 可能还是比较快的。