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

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

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

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

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

О, и это SQL Server 2000. :(

Jen A 18.09.2009 источник

comment

Перекрестки, что вам нужно, и что вы придумали - Adriaan Stander 19.09.2009

comment

Я думаю, что мои требования выше довольно ясны. Мне нужен самый большой набор событий, которые происходят одновременно. Две строки a и b пересекаются, когда a.startdate ‹= b.enddate и a.enddate ›= b.startdate. каждое решение, которое я пробовал до сих пор, было своего рода хакерским. вот почему я спрашиваю дорогой lazyweb. :) - Jen A 19.09.2009

comment

хорошо, исходя из вопроса, если вы погуглили, sqlhacks.com/index.php/Dates/ Даты были бы там - Adriaan Stander 19.09.2009

comment

Не хочу показаться грубым, но ни по одной из этих ссылок нет ответа на мой вопрос. И да, я гуглил. - Jen A 19.09.2009

comment

Покажите немного любви, дайте небольшой набор данных, структуру таблицы и потенциальный запрос, который вы пробовали (как я вижу из сообщений ниже (да???), которые вы пробовали раньше), и мы постараемся помочь... - Adriaan Stander 19.09.2009

comment

какова используемая точность ваших столбцов даты и времени? день, час, минута, секунды, ... меньше? - van 19.09.2009

Ответы (4)

arrow_upward
3
arrow_downward

Обновлено: объединение всех удалено

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) с их соответствующими началами и окончаниями.

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

Remus Rusanu 18.09.2009

comment

sweet: хорошая идея свести диапазоны к простому списку - van; 19.09.2009

comment

если вам интересно, почему мой такой толстый по сравнению с Чарльзом, то это из-за обращения с галстуками. - Remus Rusanu; 19.09.2009

arrow_upward
2
arrow_downward

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

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))

Charles Bretana 18.09.2009

arrow_upward
0
arrow_downward

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

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

Lukasz Lysik 18.09.2009

arrow_upward
0
arrow_downward

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

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

Marek Musielak 18.09.2009

comment

Я думаю, что зацикливание с курсором медленнее, чем выполнение запроса. - MaxiWheat; 19.09.2009

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

Ответы (4)

Похожие вопросы