Выберите диапазоны дат, где периоды не перекрываются

Question

У меня есть две таблицы, каждая из которых содержит даты начала и окончания нескольких периодов. Мне нужен эффективный способ найти периоды (диапазоны дат), где даты находятся в пределах диапазонов первой таблицы, но не находятся в пределах диапазонов второй таблицы.

Например, если это моя первая таблица (с датами, которые Я хочу)

start_date  end_date
2001-01-01  2010-01-01
2012-01-01  2015-01-01

И это моя вторая таблица (с датами, которые я не хочу)

start_date  end_date
2002-01-01  2006-01-01
2003-01-01  2004-01-01
2005-01-01  2009-01-01
2014-01-01  2018-01-01

Тогда вывод выглядит как

start_date  end_date
2001-01-01  2001-12-31
2009-01-02  2010-01-01
2012-01-01  2013-12-31

Мы могу смело предположить, что периоды в первой таблице не перекрываются, но не могу предположить, что периоды во второй таблице перекрываются.

У меня уже есть метод для этого, но он на порядок медленнее, чем я могу принять. Поэтому надеемся, что кто-то может предложить более быстрый подход.

Мой нынешний метод выглядит следующим образом:

1. объединить таблицу 2 в непересекающиеся периоды
2. найти обратную таблицу 2
3. объединить перекрывающиеся периоды из таблицы 1 и перевернутой таблицы-2

Я уверен, что есть быстрый путь, если некоторые из этих шагов можно объединить вместе.

Более подробно

/* (1) merge overlapping preiods */
WITH
spell_starts AS (
    SELECT [start_date], [end_date]
    FROM table_2 s1
    WHERE NOT EXISTS (
        SELECT 1
        FROM table_2 s2
        WHERE s2.[start_date] < s1.[start_date] 
        AND s1.[start_date] <= s2.[end_date]
    )
),
spell_ends AS (
    SELECT [start_date], [end_date]
    FROM table_2 t1
    WHERE NOT EXISTS (
        SELECT 1 
        FROM table_2 t2
        WHERE t2.[start_date] <= t1.[end_date] 
        AND t1.[end_date] < t2.[end_date]
    )
)
SELECT s.[start_date], MIN(e.[end_date]) as [end_date]
FROM spell_starts s
INNER JOIN spell_ends e
ON s.[start_date] <= e.[end_date]
GROUP BY s.[start_date]

/* (2) inverse table 2 */
SELECT [start_date], [end_date]
FROM (
    /* all forward looking spells */
    SELECT DATEADD(DAY, 1, [end_date]) AS [start_date]
          ,LEAD(DATEADD(DAY, -1, [start_date]), 1, '9999-01-01') OVER ( ORDER BY [start_date] ) AS [end_date]
    FROM merge_table_2

    UNION ALL

    /* back looking spell (to 'origin of time') created separately */
    SELECT '1900-01-01' AS [start_date]
          ,DATEADD(DAY, -1, MIN([start_date])) AS [end_date]
    FROM merge_table_2
) k
WHERE [start_date] <= [end_date]
AND '1900-01-01' <= [start_date] 
AND [end_date] <= '9999-01-01'

/* (3) overlap spells */
SELECT IIF(t1.start_date < t2.start_date, t2.start_date, t1.start_date) AS start_date
      ,IIF(t1.end_date < t2.end_date, t1.end_date, t2.end_date) AS end_date
FROM table_1 t1
INNER JOIN inverse_merge_table_2 t2
ON t1.start_date < t2.end_date
AND t2.start_date < t1.end_date

Answer 1

Надеюсь, это поможет. У меня есть комментарий к двум ящикам, которые я использую в целях объяснения. Здесь вы go:

drop table table1

select cast('2001-01-01' as date) as start_date, cast('2010-01-01' as date) as end_date into table1
union select '2012-01-01',  '2015-01-01' 

drop table table2

select cast('2002-01-01' as date) as start_date, cast('2006-01-01' as date) as end_date into table2
union select '2003-01-01',  '2004-01-01'
union select '2005-01-01',  '2009-01-01'
union select '2014-01-01',  '2018-01-01'

/ ***** Решение ***** /

-- This cte put all dates into one column
with cte as
(
    select t
    from
    (
        select start_date as t
        from table1
        union all
        select end_date
        from table1

        union all

        select dateadd(day,-1,start_date) -- for table 2 we bring the start date back one day to make sure we have nothing in the forbidden range
        from table2
        union all
        select  dateadd(day,1,end_date) -- for table 2 we bring the end date forward one day to make sure we have nothing in the forbidden range
        from table2
    )a
),
-- This one adds an end date using the lead function
cte2 as (select t as s, coalesce(LEAD(t,1) OVER ( ORDER BY t ),t) as e from cte a)
-- this query gets all intervals not in table2 but in table1
select s, e
from cte2 a 
where not exists(select 1 from table2 b where s between dateadd(day,-1,start_date) and dateadd(day,1,end_date) and e between dateadd(day,-1,start_date) and dateadd(day,1,end_date) )
and exists(select 1 from table1 b where s between start_date and end_date and e between start_date and end_date)
and s <> e

Answer 2

Если вам нужна производительность, то вы хотите использовать оконные функции.

Идея состоит в том, чтобы:

• Объединить даты с флагами входа и выхода из две таблицы.
• Используйте кумулятивные суммы, чтобы определить, где даты начинают входить и выходить.
• Тогда возникает проблема с пробелами и островками, когда вы хотите объединить результаты.
• Наконец, отфильтруйте нужные вам периоды.

Это выглядит следующим образом:

with dates as (
      select start_date as dte, 1 as in1, 0 as in2
      from table1
      union all
      select dateadd(day, 1, end_date), -1, 0
      from table1
      union all
      select start_date, 0, 1 as in2
      from table2
      union all
      select dateadd(day, 1, end_date), 0, -1
      from table2
     ),
     d as (
      select dte,
             sum(sum(in1)) over (order by dte) as ins_1,
             sum(sum(in2)) over (order by dte) as ins_2
      from dates
      group by dte
     )
select min(dte), max(next_dte)
from (select d.*, dateadd(day, -1, lead(dte) over (order by dte)) as next_dte, 
             row_number() over (order by dte) as seqnum,
             row_number() over (partition by case when ins_1 >= 1 and ins_2 = 0 then 'in' else 'out' end order by dte) as seqnum_2
      from d
     ) d
group by (seqnum - seqnum_2)
having max(ins_1) > 0 and max(ins_2) = 0
order by min(dte);

Здесь - это db <> скрипка.

Answer 3

Спасибо @zip и @Gordon за ответы. Оба превосходили мой первоначальный подход. Однако следующее решение было быстрее, чем оба их подхода в моей среде и контексте:

WITH acceptable_starts AS (
    SELECT [start_date] FROM table1 AS a
    WHERE NOT EXISTS (
        SELECT 1 FROM table2 AS b
        WHERE DATEADD(DAY, 1, a.[end_date]) BETWEEN b.[start_date] AND b.
    UNION ALL
    SELECT DATEADD(DAY, 1, [end_date]) FROM table2 AS a
    WHERE NOT EXISTS (
        SELECT 1 FROM table2 AS b
        WHERE DATEADD(DAY, 1, a.[end_date]) BETWEEN b.[start_date] AND b.[end_date]
    )
),
acceptable_ends AS (
    SELECT [end_date] FROM table1 AS a
    WHERE NOT EXISTS (
        SELECT 1 FROM table2 AS b
        WHERE DATEADD(DAY, -1, a.[start_date]) BETWEEN b.[start_date] AND b.[end_date]
    )
    UNION ALL
    SELECT DATEADD(DAY, -1, [start_date]) FROM table2 AS a
    WHERE NOT EXISTS (
        SELECT 1 FROM table2 AS b
        WHERE DATEADD(DAY, -1, a.[start_date]) BETWEEN b.[start_date] AND b.[end_date]
    )
)
SELECT s.[start_date], MIN(e.[end_date]) AS [end_date]
FROM acceptable_starts
INNER JOIN acceptable_ends
ON s.[start_date] < e.[end_date]