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

Question

У меня есть простая таблица событий:

event_id | start_time | end_time

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

Answer 1

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

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

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

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

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

[включение 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 комбинаций записей. </p>

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

Демс.

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

Answer 2

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

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

Answer 3

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

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

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

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

Answer 4

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

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