在PostgreSQL中查找所有范围集的所有交集 [英] Find all intersections of all sets of ranges in PostgreSQL

问题描述

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

I'm looking for an efficient way to find all the intersections between sets of timestamp ranges. It needs to work with PostgreSQL 9.2.

让我们说这些范围代表一个人可以见面的时间。每个人都有空时有一个或多个时间范围。我想找到所有会议的召开时间（即所有人都可以使用的时间）。

Let's say the ranges represent the times when a person is available to meet. Each person may have one or more ranges of times when they are available. I want to find all the time periods when a meeting can take place (ie. during which all people are available).

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

This is what I've got so far. It seems to work, but I don't think it's very efficient, since it considers one person's availability at a time.

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;

推荐答案

我创建了 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")

这篇关于在PostgreSQL中查找所有范围集的所有交集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！