Запросить максимальное количество одновременных событий

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

Сортируйте события по времени начала. Прокрутите события и найдите промежутки, в которых нет событий, сгруппируйте события между этими промежутками. Проходите цикл каждый раз (с любым разрешением, в котором записано ваше время) в каждой группе и запрашивайте события, которые происходят в это время. В зависимости от скорости вашего языка программирования и скорости запросов к БД вы можете посмотреть на перекрывающиеся события и перейти к первому end_time одного из перекрывающихся событий.

В зависимости от того, что вы подразумеваете под одновременным, как отмечается в других ответах, это может быть очень похоже на этот вопрос.

К сожалению, решение, которое я предложил (который был принятым ответом), потребует от вас изменения дизайна вашей таблицы. Однако это позволит вам тривиально определить максимальное количество одновременных событий, проверив столбец «SessionCount» (или аналогично названный).

Поскольку ваши пиковые времена всегда заканчиваются в end_time, вы можете просто проверить это время, как предложил Спарр. Поэтому выполните запрос, чтобы дважды присоединиться к одной и той же таблице и подсчитать количество строк, в которых событие перекрывается в каждом end_time. Тогда возьмите максимум этого.

Это даст вам ответ, но медленно:

SELECT MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd            
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
        t1.end_time BETWEEN t2.start_time AND t2.end_time
    GROUP BY t1.event_id
) AS foo

Разделение на более мелкие группы (меньше для сравнения), а затем получение максимума из этих меньших групп значительно ускоряет его:

SELECT MAX(maxOLP)
FROM
(
    SELECT MAX(olp) AS maxOLP
    FROM
    (
        SELECT 
            MAX(overlapAtEnd) AS maxOLP,
            EXTRACT(HOUR FROM t1.end_time)  AS hr
        FROM
        (
            SELECT 
                COUNT(1) AS overlapAtEnd            
            FROM 
                your_table AS t1, 
                your_table AS t2
            WHERE 
                t1.end_time BETWEEN t2.start_time AND t2.end_time
            GROUP BY t1.event_id
        ) AS foo
        GROUP BY t1.event_id, EXTRACT(HOUR FROM t1.end_time)
    ) AS foo
    GROUP BY hr
) AS foo2

У этого более быстрого подхода есть небольшой недостаток ... если ваши события обычно охватывают более часа, события, которые заканчиваются в следующий час, могут по-прежнему перекрываться, но не учитываются. Чтобы исправить это, просто сгруппируйте по большему интервалу, например, дню или неделе. Немного волосатый, но он отлично работает и быстро дает результат, который звучит так, как будто вы ищете.

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

Первый ответ Гарри (основная логика)

SELECT MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd                        
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
        t1.end_time BETWEEN t2.start_time AND t2.end_time
    GROUP BY t1.event_id
) AS foo

Место, которое занимает больше всего времени на обработку, - это соединение.

Для каждой записи в таблице вы выбираете (время t1. End). Затем вы снова выполняете поиск в таблице для (t1.end_time> = start_time) и для всех совпадающих записей, которые вы ищете (t1.end_time <= t1.end_time)

Теперь вам очень легко создать индекс для start_time. Это значительно ускоряет первую проверку (t1.end_time> = start_time);
- Индекс - это дерево поиска для чрезвычайно быстрого поиска
- Это позволяет очень быстро найти первую совпадающую запись. - Индекс по сути упорядочен
- Это значит, что он знает, что "все после первого матча тоже совпадает".

Последняя часть, тем не менее, является ключевой, потому что это означает, что ... Даже после использования индекса для выполнения первой проверки (t1.end_time> = start_time) у нас все еще может остаться много записей для выполнения второй проверки (t1. end_time <= t1.end_time)

[включение end_time в индекс здесь не помогает и будет обсуждаться в ближайшее время]

0, '10:00', '10:04'   COUNT(*) WHERE '10:04' >= start_time  ==  4
1, '10:01', '10:06'   COUNT(*) WHERE '10:06' >= start_time  ==  4
2, '10:02', '10:09'   COUNT(*) WHERE '10:09' >= start_time  ==  5
3, '10:04', '10:07'   COUNT(*) WHERE '10:07' >= start_time  ==  4
4, '10:08', '10:12'   COUNT(*) WHERE '10:12' >= start_time  ==  6
5, '10:12', '10:17'   COUNT(*) WHERE '10:17' >= start_time  ==  7
6, '10:15', '10:18'   COUNT(*) WHERE '10:18' >= start_time  ==  8
7, '10:18', '10:22'   COUNT(*) WHERE '10:22' >= start_time  ==  10
8, '10:19', '10:24'   COUNT(*) WHERE '10:24' >= start_time  ==  10
9, '10:22', '10:25'   COUNT(*) WHERE '10:25' >= start_time  ==  10

=> leaves 68 rows to check the second condition; (t1.end_time <= t1.end_time)

Предполагая относительно плавное распределение событий, каждая запись будет (приблизительно и в среднем) соответствовать половине таблицы. Это означает, что вы выполняете (n * n / 2) проверок, где n - количество записей в таблице. Даже при 100 записях это дает 5000 проверок. При 2000 записях вы делаете около 2 миллионов проверок!

Естественно добавить в индекс поле end_time. Однако это не помогает. Индекс для (start_time, end_time) создает дерево поиска до каждого уникального start_time, затем под каждым уникальным start_time существует отдельное дерево поиска для end_times.

В моем примере выше каждое start_time уникально. Это означает, что вам все еще нужно выполнить все 68 проверок end_time. Индекс принес пользу только проверкам start_time.

Что нам нужно сделать, так это попытаться использовать единственный индекс start_time, чтобы сделать больше, чем мы сейчас. Нам нужно предоставить системе запросов больше информации.

Примером может служить использование «максимальной продолжительности события». Например, мы можем обнаружить, что ни одно событие не длится более 8 минут. Это даст нам следующий запрос ...

SELECT MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd                        
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
            t1.end_time >= t2.start_time
        AND t1.end_time <= t2.end_time
        AND t1.end_time <= t2.start_time + [max_event_duration] 
    GROUP BY t1.event_id
) AS foo

Применяя пример с 8-минутной продолжительностью к приведенному выше примеру, мы уменьшаем 68 проверок end_time до 34.

0, '10:00', '10:04'   COUNT(*) WHERE '10:04' BETWEEN start_time AND start_time + 8 == 4
1, '10:01', '10:06'   COUNT(*) WHERE '10:06' BETWEEN start_time AND start_time + 8 == 4
2, '10:02', '10:09'   COUNT(*) WHERE '10:09' BETWEEN start_time AND start_time + 8 == 4
3, '10:04', '10:07'   COUNT(*) WHERE '10:07' BETWEEN start_time AND start_time + 8 == 4
4, '10:08', '10:12'   COUNT(*) WHERE '10:12' BETWEEN start_time AND start_time + 8 == 3
5, '10:12', '10:17'   COUNT(*) WHERE '10:17' BETWEEN start_time AND start_time + 8 == 2
6, '10:15', '10:18'   COUNT(*) WHERE '10:18' BETWEEN start_time AND start_time + 8 == 3
7, '10:18', '10:22'   COUNT(*) WHERE '10:22' BETWEEN start_time AND start_time + 8 == 4
8, '10:19', '10:24'   COUNT(*) WHERE '10:24' BETWEEN start_time AND start_time + 8 == 3
9, '10:22', '10:25'   COUNT(*) WHERE '10:25' BETWEEN start_time AND start_time + 8 == 3

=> leaves 34 rows to check the second condition; (t1.end_time <= t1.end_time)
=> thats half the original 68, and on bigger tables the benefit increases...

Даже если бы мы не знали, что события никогда не превышают 8 минут, мы могли бы найти это, просто проверив 10 записей. MAX (end_time - start_time) более 10 записей все равно будет быстрее, чем проверка (t1.end_time <= t1.end_time) более 34 комбинаций записей.

А по мере увеличения размера стола выгода увеличивается. Фактически, если [max_event_duration] значительно меньше, чем весь временной интервал, охватываемый таблицей, вы меняете (nn / 2) квадратный закон во что-то более похожее на (nx + n), которое является линейным.

Dems.

SELECT
   MAX(overlapAtEnd)
FROM
(
    SELECT 
        COUNT(1) AS overlapAtEnd                        
    FROM 
        your_table AS t1, 
        your_table AS t2
    WHERE 
            t2.start_time <= t1.end_time
        AND t2.start_time >= t1.end_time - (SELECT MAX(end_time - start_time) FROM your_table)
        AND t2.end_time   >= t1.end_time
    GROUP BY t1.event_id
) AS foo