PostgreSQL-如何找到两个间隔的最近重叠？

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天（LCM为12和10）。因此，我希望它会在7月13日+ 60天= 9月11日再次重复。

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

请注意，recurring可以为null，因此我认为某处必须有类似WHERE recurring IS NOT NULL的内容。需要注意的另一件事：没有任何初始约会重叠。我已经对此保持警惕。搜索字词也不与约会的任何初始时间重叠。

[如果有帮助，我正在使用PHP 5.3将查询发送到Postgres 9.4（我知道，这是一个古老的设置）。我宁愿在SQL中执行大部分操作，因为其他大多数逻辑现在都在SQL中，因此我可以运行查询并开始使用PHP处理结果。

因此，总的来说，如果我的数学正确，那么我应该对上表使用哪种Postgres查询，以将给定的日期和间隔与表中的每个日期和间隔对进行比较，以查找下两个重叠的日期以及相隔多远的下一个日期每个重叠实例都是？

Answer 1

这是hard。

WITH RECURSIVE moving_target(initial_timestamp, recurring) AS (
   VALUES (timestamp '2020-06-07', interval '12 days')  -- search term
   )
,  x AS (
   SELECT t.id
          -- advance to the closest day before or at moving target:
        , t_date + ((m_date - t_date) / t_days) * t_days AS t_date
        , t_days
        , m.*
   FROM  (  -- normalize table data
      SELECT id
           , initial_timestamp::date AS t_date
           , EXTRACT ('day' FROM recurring)::int AS t_days
      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_days
      FROM   moving_target
      ) m
   )
, rcte AS (
   SELECT id, t_date, t_days, m_date, m_days
        , ARRAY[m_date - t_date] AS gaps        -- keep track of gaps
        , CASE
            WHEN t_date = m_date     THEN true  -- found match
            WHEN t_days % m_days = 0 THEN false -- can never match
            WHEN (m_days - t_days) % 2 = 1
             AND t_days % 2 = 0
             AND m_days % 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_days, m_date, m_days
        , 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_days) - t_date) / t_days) * t_days AS t_date
           , t_days
           , m_date + m_days AS m_date -- + 1 step
           , m_days
           , 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 <>小提琴here

可能有进一步改进的潜力。核心问题在于素数分解。期望有相当小的间隔数似乎是合理的。我通过测试周期来解决它：如果在逐步前进的过程中，检测到我们之前见过的日期之间存在间隙（日期迄今为止从未重叠），日期将never重叠并且我们可以停止走圈。这最多循环GREATEST(m_days, t_days)（较大间隔中的天数），因此它不应可怕地扩展。

解释这里发生的所有事情比设计查询要多。我添加了一些注释，这些注释应该解释基本知识...