Колко души има в кръчмата?

Задачката е следната:

Близо до офиса има една кръчма (още се спори дали се казва „Дупката“ или „Гнусното“). В нея влизат и излизат много хора. Понеже е доста голяма, има си регистър на влизащите и излизащите. В основната таблица (покрай другото) има и колонки time_in и time_out, които показват даден човек кога е влязъл и кога е излязъл. Ако се случи да дойде втори път (което е съвсем възможно, предвид че въпреки гадната обстановка, в Дупката готвят много вкусно), просто се вкарва нов запис.

Шефа на Дупката обича да знае разни неща. И като човек, обичащ да знае разни неща, иска да знае в кой момент от денонощието има най-много хора в кръчмата, и като цяло как се движи натоварването. Но понеже заведението е наистина голяма, няма начин някой да седи и д брои – трябва да се използват записите в таблицата. Въпреки че Дупката работи денонощно, натоварването е променливо.

В таблицата има около 500-600 хиляди записа на ден. Естествено, използва се partitioning, за да бъде управляем обема.

Ще представя един вариант, както и част от пътя, по който стигнах до него. Естествено, приемам всякакви предложения. Подозирам, че все някой е решавал такава задачка преди мен и аз сега откривам топлата вода.

Първата идея е да се направи pl/sql функция, която да проверява във всеки един момент колко хора е имало. Понеже колонките за дата в таблицата са от тип DATE, ще проверим всяка секунда за дадено денонощие (такава е точността на типа DATE). С един цикъл, за всяка секунда “X”, търсим посещения по следния начин:

SELECT X, COUNT(1)
  FROM client_visits 
 WHERE X BETWEEN time_in AND time_out;

Това се записва в една таблица, от която ваденето на графики става лесно.

Всичко това е хубаво, само че за дадените обеми нещото отнема абсурдно много време на тестовата система: около 30 часа за 24 часов период. И това при наличие на индекс по (time_in, time_out) – иначе няма шанс.

Тук се сещам за един въпрос, който много хора забравят: а трябва ли ни наистина толкова детайлна информация (за всяка секунда)? (виж „Oracle Insights“, глава 3: „Waste Not, Want Not“)

Полезно: Много често се оказва, че с леко облекчаване на бизнес изискванията, задачата става много по-лесно решима.

Така е и в този случай – шефа на Дупката е доволен да знае и как се движи натоварването по минути, не му трябва чак по секунди. Така цикълът (с малко променено условие) ще има 60 пъти по-малко итерации и ще пусне само 1440 заявки, вместо 86400. И (на нашата система) отнема само малко повече от половин час.

Обаче… всеки печен DB expert знае, че в общия случай ако нещо може да стане само с SQL, то е добре да се направи само с SQL. Да стане с една, пък била тя и тежка, заявка – вместо с 1440 по-леки. Естествено, има и изключения, но са много редки.

Първоначално тръгнах по грешен път. Сетих се, че не ми трябва да проверявам всяка секунда (или минута) – стига ми да проверявам за всеки момент, в който влиза някой. Ако в даден момент не влиза никой, там няма да има покачване на натоварването.

select time_in,
       (select count(1)
           from client_visits t2
          where t2.time_in < = t1.time_in
            and t2.time_out >= t1.time_in
            )
  from client_visits t1
 where time_in >= trunc(sysdate - 1) -- гледаме данните за 1 ден
   and time_in < trunc(sysdate)

Това няма да помогне на шефа на дупката да разбере кога има най-малко натоварване, но той така или иначе не се интересува от това - той си оразмерява кръчмето за максималното натоварване, а движението в натоварването му трябва за да си нагоди грубо персонала. Освен това входящите посетители са толкова много (500-600 хиляди посещения на ден), че и без това почти на всяка секунда има поне един влизащ и няма опасност да се пропусне нещо интересно.

Тук, обаче, нещата на вървяха много добре. Честно казано, не изчаках да видя колко време е необходимо, защото всичко над 15 минути ми се струваше твърде много. Тук извадих един друг коз на добрия dataabse expert:

Полезно: Често има неясни зависимости в данните, които помагат да се свърши по-малко работа. Връзки, които са естествени и ясни за нас, но не и за оптимизатора в БД.

Една такава връзка е, че никой не стои в дупката повече от един ден. Или даже и да има такива, те са твърде малко и не променят статистиката. За това направих следната малка оптимизация:

select time_in,
       (select count(1)
           from client_visits t2
          where t2.time_in < = t1.time_in
            and t2.time_out >= t1.time_in
            and t2.time_in > trunc(sysdate) - 2 -- малко оптимизация
            )
  from client_visits t1
 where time_in >= trunc(sysdate - 1) -- гледаме данните за 1 ден
   and time_in < trunc(sysdate)

Това вероятно е подобрило малко нещата, но аз отново нямах търпението да изчакам за да видя колко. Като цяло проблема на този подход е, че се правят твърде много проверки - всъщност, около 500-600 хиляди за един ден (колкото са посещенията).

Следващата идея беше да се изгонят поне повтарящите се проверки:

SELECT time_in,
       (SELECT COUNT(1)
         FROM   client_visits t2
         WHERE  t1.time_in BETWEEN t2.time_in AND t2.time_out
         AND    t2.time_in > trunc(SYSDATE - 2))
FROM   (SELECT DISTINCT time_in -- избягваме повторните проверки
         FROM   client_visits
         WHERE  time_in >= trunc(SYSDATE - 1)
         AND    time_in < trunc(SYSDATE)) t1;

Естествено, и това се оказа твърде бавно. По този начин правим близо 86400 проверки, а вече се разбрахме, че може да направим само 1440. За това се изкуших да направя така:

SELECT time_in,
       (SELECT COUNT(1)
         FROM   client_visits t2
         WHERE  t1.time_in BETWEEN t2.time_in AND t2.time_out
         AND    t2.time_in > trunc(SYSDATE - 2))
FROM   (SELECT DISTINCT trunc(time_in, 'MI') -- намиране само по един запис за всяка минута
         FROM   client_visits
         WHERE  time_in >= trunc(SYSDATE - 1)
         AND    time_in < trunc(SYSDATE)) t1;

Описах този грешен (в случая) път, защото при по-малко данни (примерно ако имахме само 500-600 посещения) би бил полезен. Иначе аз доста бързо се сетих за алтернативата. Само да кажа за последните 2 заявки:

Полезно: Операцията DISTINCT е много тежка при голям обем от данни, защото изисква сортиране на цялото множество.

Освен това с посочените заявки аз преравям 2 пъти данните, които хич не са малко. За това аз се нуждаех от начин да си генерирам всички минути в едно денонощие, без да се ровя в таблицата. Да си измисля данни, с които да направя join. За целта използвах следния трик

Полезно: Генератор за 100 реда с числата от 1 до 100:
select rownum from dual connect by level < = 100

Така стигнах до следния вариант:

SELECT time_in,
       (SELECT COUNT(1)
           FROM client_visits t2
          WHERE t1.time_in BETWEEN t2.time_in AND t2.time_out
            AND t2.time_in > trunc(SYSDATE) - 2) cnt
  FROM (select trunc(SYSDATE - 1) + rownum / 1440 time_in
           from dual
         connect by level < 1440) t1

Това нещо вече се справя за под 7 минути. За съжаление не показва в коя минута има най-много посетители в кръчмата, а в коя нулева секунда от минута. За да сравня целите минути ми трябват и посетителите, които са влезли преди началото на следващата минута. Ако гледам с разредност "секунда", този проблем не стои. Едно друго решение за заобикаляне на този проблем е да правя всички сравнения не с точната стойност на time_in и time_out, а с trunc(time_in, 'MI') и trunc(time_out, 'MI'). Но в този случай губя индекса (което пък се решава с функционален индекс). Но в настоящият вариант мога лесно да променя на колко периода да разделя денонощието - примерно на по 5 минути, или на 10 секунди, за да получа данни с различна точност.

И така, настоящият вариант е следния:

SELECT period_start,
       (SELECT COUNT(1)
           FROM client_visits t2
          WHERE ((t2.time_in < = t1.period_start and t2.time_out > t1.period_start) -- започнали преди периода
                 or -- или
                (t2.time_in > period_start and t2.time_in < period_end)) -- започнали в периода
            AND t2.time_in > SYSDATE - 2) cnt
  FROM (select trunc(SYSDATE - 1) + rownum / 1440 period_start, -- началото на периода
               trunc(SYSDATE - 1) + (rownum + 1) / 1440 period_end -- началото на следващият период
           from dual
         connect by level < 1440) t1

Не ми е трудно да се досетя, че може да има и съвсем различно, по-елегантно и ефективно решение. Ще се радвам ако някой сподели такова 🙂