sql - 在 PostgreSQL 中查找所有范围集的所有交集

Question

我正在寻找一种有效的方法来查找时间戳范围集之间的所有交集。它需要与 PostgreSQL 9.2 配合使用。

假设范围表示某人可以见面的时间。每个人可能有一个或多个可用时间范围。我想找到可以举行 session 的所有时间段(即，在此期间所有人都有空)。

这就是我到目前为止所得到的。它似乎有效，但我认为它不是很有效率，因为它一次考虑一个人的可用性。

WITH RECURSIVE td AS
(
    -- Test data. Returns:
    -- ["2014-01-20 00:00:00","2014-01-31 00:00:00")
    -- ["2014-02-01 00:00:00","2014-02-20 00:00:00")
    -- ["2014-04-15 00:00:00","2014-04-20 00:00:00")
    SELECT 1 AS entity_id, '2014-01-01'::timestamp AS begin_time, '2014-01-31'::timestamp AS end_time
    UNION SELECT 1, '2014-02-01', '2014-02-28'
    UNION SELECT 1, '2014-04-01', '2014-04-30'
    UNION SELECT 2, '2014-01-15', '2014-02-20'
    UNION SELECT 2, '2014-04-15', '2014-05-05'
    UNION SELECT 3, '2014-01-20', '2014-04-20'
)
, ranges AS
(
    -- Convert to tsrange type
    SELECT entity_id, tsrange(begin_time, end_time) AS the_range
    FROM td
)
, min_max AS
(
    SELECT MIN(entity_id), MAX(entity_id)
    FROM td
)
, inter AS
(
    -- Ranges for the lowest ID
    SELECT entity_id AS last_id, the_range
    FROM ranges r
    WHERE r.entity_id = (SELECT min FROM min_max)

    UNION ALL

    -- Iteratively intersect with ranges for the next higher ID
    SELECT entity_id, r.the_range * i.the_range
    FROM ranges r
    JOIN inter i ON r.the_range && i.the_range
    WHERE r.entity_id > i.last_id
        AND NOT EXISTS
        (
            SELECT *
            FROM ranges r2
            WHERE r2.entity_id < r.entity_id AND r2.entity_id > i.last_id
        )
)
-- Take the final set of intersections
SELECT *
FROM inter
WHERE last_id = (SELECT max FROM min_max)
ORDER BY the_range;

Answer 1

我创建了 tsrange_interception_agg 聚合

create function tsrange_interception (
    internal_state tsrange, next_data_values tsrange
) returns tsrange as $$
    select internal_state * next_data_values;
$$ language sql;

create aggregate tsrange_interception_agg (tsrange) (
    sfunc = tsrange_interception,
    stype = tsrange,
    initcond = $$[-infinity, infinity]$$
);

然后这个查询

with td (id, begin_time, end_time) as
(
    values
    (1, '2014-01-01'::timestamp, '2014-01-31'::timestamp),
    (1, '2014-02-01', '2014-02-28'),
    (1, '2014-04-01', '2014-04-30'),
    (2, '2014-01-15', '2014-02-20'),
    (2, '2014-04-15', '2014-05-05'),
    (3, '2014-01-20', '2014-04-20')
), ranges as (
    select
        id,
        row_number() over(partition by id) as rn,
        tsrange(begin_time, end_time) as tr
    from td
), cr as (
    select r0.tr tr0, r1.tr as tr1
    from ranges r0 cross join ranges r1
    where
        r0.id < r1.id and
        r0.tr && r1.tr and
        r0.id = (select min(id) from td)
)
select tr0 * tsrange_interception_agg(tr1) as interseptions
from cr
group by tr0
having count(*) = (select count(distinct id) from td) - 1
;
                 interseptions                 
-----------------------------------------------
 ["2014-02-01 00:00:00","2014-02-20 00:00:00")
 ["2014-01-20 00:00:00","2014-01-31 00:00:00")
 ["2014-04-15 00:00:00","2014-04-20 00:00:00")