Максимальное пересечение диапазона отсчета (в T-SQL) - PullRequest
Новая
       59

Максимальное пересечение диапазона отсчета (в T-SQL)

3 голосов
/ 19 сентября 2009

Допустим, у меня есть таблица с кучей дат, например:

. 
declare @tbl table {
    idx int primary key,
    startdate datetime,
    enddate datetime
}

И я хочу найти самый большой набор строк, где пересекаются начальная и конечная даты (в реальном мире дата начала и дата окончания представляют время начала и окончания событий, и мне нужно найти максимальное количество событий, происходящих одновременно ).

На другом языке программирования я мог бы отсортировать все записи по начальной дате, а затем перебрать каждую запись один раз, создавая временный набор пересечений (отслеживая самый большой сгенерированный набор). Но я не уверен, что это самый эффективный способ выразить это в T-SQL. помощь!

Да, и это SQL Server 2000.: (

Ответы [ 4 ]

3 голосов
/ 19 сентября 2009

Обновлено, чтобы удалить объединение всех 

declare @tbl table (
idx int identity(1,1) primary key,    
startdate datetime,    
enddate datetime);

insert into @tbl (startdate, enddate) 
select '2009-01-01', '2009-01-05'
union all select '2009-01-02', '2009-01-04'
union all select '2009-01-01', '2009-01-03'
union all select '2009-01-03', '2009-01-06'
union all select '2009-01-04', '2009-01-07'
union all select '2009-01-05', '2009-01-08'

select idx, startdate
   , (select sum(in_or_out) 
from (
   select case when startdate<=all_events.startdate then 1 else 0 end
     + case when enddate <= all_events.startdate then -1 else 0 end as in_or_out
   from @tbl 
   where startdate <= all_events.startdate
     or enddate <= all_events.startdate) as previous
) as concurent
from @tbl all_events
order by startdate

Это дает график начала сеанса с количеством параллельных сеансов на момент начала нового сеанса: 

idx startdate   concurent
3   2009-01-01 00:00:00.000 2
1   2009-01-01 00:00:00.000 2
2   2009-01-02 00:00:00.000 3
4   2009-01-03 00:00:00.000 3
5   2009-01-04 00:00:00.000 3
6   2009-01-05 00:00:00.000 3

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

Обновлено

ОК, вот один запрос, который извлекает максимальное количество одновременных сеансов. Я изменил тестовые данные, чтобы удалить двойные совпадения конца и начала: 

declare @tbl table (
idx int identity(1,1) primary key,    
startdate datetime,    
enddate datetime);

insert into @tbl (startdate, enddate) 
select '2009-01-01', '2009-01-04 23:59:59'
union all select '2009-01-02', '2009-01-03 23:59:59'
union all select '2009-01-01', '2009-01-02 23:59:59'
union all select '2009-01-03', '2009-01-03 23:59:59'
union all select '2009-01-04', '2009-01-04 23:59:59'
union all select '2009-01-05', '2009-01-05 23:59:59'


select max_concurent_starts.startdate as concurentdate
  , session.*
from (
  select *
  ,(
        select sum(in_or_out) 
        from (
            select case when startdate<=all_events.startdate then 1 else 0 end
                + case when enddate <= all_events.startdate then -1 else 0 end 
                as in_or_out
          from @tbl 
          where startdate <= all_events.startdate
              or enddate <= all_events.startdate) as previous
    ) as concurent
  from @tbl all_events) as max_concurent_starts
  join @tbl as session 
     on session.startdate <= max_concurent_starts.startdate 
     and session.enddate >= max_concurent_starts.startdate
  where concurent = (
  select top 1 concurent
  from (
      select (
          select sum(in_or_out) 
          from (
              select case when startdate<=all_events.startdate then 1 else 0 end
                  + case when enddate <= all_events.startdate then -1 else 0 end 
                  as in_or_out
            from @tbl 
            where startdate <= all_events.startdate
                or enddate <= all_events.startdate) as previous
      ) as concurent
    from @tbl all_events) as all_events_with_concurent
    order by concurent desc)
  order by concurentdate, startdate;

Это дает результат как: 

concurentdate   idx startdate   enddate
2009-01-02 00:00:00.000 3   2009-01-01 00:00:00.000 2009-01-02 23:59:59.000
2009-01-02 00:00:00.000 1   2009-01-01 00:00:00.000 2009-01-04 23:59:59.000
2009-01-02 00:00:00.000 2   2009-01-02 00:00:00.000 2009-01-03 23:59:59.000
2009-01-03 00:00:00.000 1   2009-01-01 00:00:00.000 2009-01-04 23:59:59.000
2009-01-03 00:00:00.000 2   2009-01-02 00:00:00.000 2009-01-03 23:59:59.000
2009-01-03 00:00:00.000 4   2009-01-03 00:00:00.000 2009-01-03 23:59:59.000

, который гласит: на 2009-01-02 00:00:00 было 3 параллельных сеанса (3, 1 и 2) с соответствующими началами и окончаниями. Есть связь, на 2009-01-03 00:00:00 также было 3 параллельных сеанса (1, 2 и 4) с соответствующими началами и окончаниями.

Производительность может варьироваться. Запрос может быть написан в миллион раз проще в SQL 2005 с использованием CTE.

2 голосов
/ 19 сентября 2009

попробуйте это (это близко к тому, что вы хотите, я думаю ... 

Select Distinct EventId 
From EventTable Et
Join  (Select Top 1 RunDate, Count(*) DateCount
       From 
          (Select Distinct StartDate RunDate
           From EventTable
               Union  
           Select Distinct EndDate RunDate
           From EventTable) A
         Join EventTable E
            On A.RunDate Between E.StartDate And E.EndDate
       Group By RunDate
       Order By Count(*) Desc) Z
   On Z.RunDate Between Et.StartDate and Et.EndDate

о, если в ваших датах есть дата и время, тогда замените все даты в этом документе только на часть фактической даты (исключите время) 

Select Distinct EventId 
From EventTable Et
Join  (Select Top 1 RunDate, Count(*) DateCount
       From 
          (Select Distinct DateAdd(day, 0, DateDiff(day, 0, StartDate)) RunDate
           From EventTable
               Union  
           Select Distinct DateAdd(day, 0, DateDiff(day, -1, EndDate)) RunDate
           From EventTable) A
         Join EventTable E
            On A.RunDate Between DateAdd(day, 0, DateDiff(day, 0, E.StartDate))
                             and DateAdd(day, 0, DateDiff(day, -1, E.EndDate))
       Group By RunDate
       Order By Count(*) Desc) Z
   On Z.RunDate Between DateAdd(day, 0, DateDiff(day, 0, Et.StartDate))
                    and DateAdd(day, 0, DateDiff(day, -1, Et.EndDate))
0 голосов
/ 19 сентября 2009

Это довольно короткий, простой для понимания и отлично работает: 

CREATE PROCEDURE FindEvents
AS
BEGIN
    DECLARE dates_cursor CURSOR FOR 
        SELECT
            startdate AS thedate, 1 AS change
        FROM
            dates
        UNION
        SELECT
            enddate AS thedate, - 1 AS change
        FROM
            dates
        ORDER BY 
            thedate ASC;

        DECLARE @max INT;
        DECLARE @thedate DATETIME;
        DECLARE @change INT;
        DECLARE @current INT;

        SET @max = 0;
        SET @current = 0;

    OPEN dates_cursor

    FETCH NEXT FROM dates_cursor INTO @thedate, @change

    WHILE @@FETCH_STATUS = 0
    BEGIN
        SET @current = @current + @change;
        IF (@current > @max)
        BEGIN
            SET @max = @current;
        END
        FETCH NEXT FROM dates_cursor INTO @thedate, @change
    END

    CLOSE dates_cursor
    DEALLOCATE dates_cursor

    SELECT @max;
END
0 голосов
/ 19 сентября 2009

Другой подход: 

DECLARE @idx INT,
        @startdate DATETIME,
    @enddate DATETIME,  
        @prev_enddate DATETIME,
        @counter INT,
    @counter_max INT

DECLARE db_cursor CURSOR FOR  
SELECT idx, startdate,enddate 
FROM @tbl
ORDER BY startdate,enddate

OPEN db_cursor   

FETCH NEXT FROM db_cursor INTO @idx, @startdate, @enddate
SET @prev_enddate = @enddate
SET @counter = 0
SET @counter_max = 0

WHILE @@FETCH_STATUS = 0   
BEGIN   
IF @startdate < @prev_enddate
BEGIN
    SET @counter = @counter + 1 
    IF @counter > @counter_max
    BEGIN
        SET @counter_max = @counter
    END
END
ELSE
BEGIN
    SET @counter = 1
END

SET @prev_enddate = @enddate
FETCH NEXT FROM db_cursor INTO @idx, @startdate, @enddate           
END   

CLOSE db_cursor   
DEALLOCATE db_cursor

SELECT @counter_max
...