Spajanje neprekidnih datumskih intervala
Tuesday, 07.08.2007 – SrdjanPre neki dan je Dado (kolega s posla) naiÅ¡ao na interesantan problem. Originalni problem se tiÄe generisanja M4 obrazca za zaposlene i treženja neprekidnog intervala u kome je osoba bila zaposlena.
Postavka problema
Problem se može abstrahovati na sledeći naÄin:
Neka imamo skup datumskih intervala . Interval ’I’ je odreÄ‘en poÄetnim i krajnjim datumima I = [pocetak, kraj).
Intervali se ne preklapaju. Smatramo da se dva intervala I1=[pocetak1, kraj1) i I2=[pocetak2, kraj2) neposredno nastavljaju ako je kraj1 = pocetak2.
Treba spojiti sve intervale koji se neposredno nastavljaju. Dakle ako imamo dva intervala I1 i I2 i ako je kraj1 = pocetak2 onda nam je traženi rezultat interval I3=[pocetak1, kraj2).
Intervali su nam dati u tabeli
CREATE TABLE intervali ( pocetak DATE NOT NULL, kraj DATE NOT NULL, CHECK (pocetak <> kraj) );
I imamo nekoliko test podataka:
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-01-01', '2007-01-15');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-01-15', '2007-01-21');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-01-21', '2007-01-31');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-02-02', '2007-02-15');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-02-17', '2007-02-22');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-02-22', '2007-02-25');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-03-01', '2007-03-10');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-03-10', '2007-03-15');
INSERT INTO intervali (pocetak, kraj)
VALUES ('2007-03-20', '2007-03-31');
Od ovih podataka oÄekujemo rezultat:
pocetak kraj ---------- ---------- 2007-01-01 2007-01-31 2007-02-02 2007-02-15 2007-02-17 2007-02-25 2007-03-01 2007-03-15 2007-03-20 2007-03-31
Prvi pokušaji
I Dado i ja smo imali istu ideju: grupišemo neprekidne periode, a onda za svaku grupu uzmemo MIN(pocetak) i MAX(kraj). Ostao nam je još samo problem da nađemo kriterijum grupisanja.
Nezavisno jedan od drugoga, Dado i ja smo došli do dva rešenja.
Dadino rešenje
-- Dadin upit
SELECT MIN(pocetak), MAX(kraj)
FROM (SELECT pocetak, kraj,
(SELECT MIN(pocetak)
FROM intervali
WHERE pocetak >
(SELECT MAX(kraj)
FROM intervali AS pr_d
WHERE curr.kraj > pr_d.kraj
AND NOT EXISTS
(SELECT pocetak
FROM intervali
WHERE pocetak = pr_d.kraj
)
)
) AS min_kraj
FROM intervali AS curr
) AS tmp
GROUP BY min_kraj
ORDER BY 1;
Moje rešenje
Setio sam se da je pre nekoliko meseci na forumu baza podataka EliteSecurity-ja bila interesantna SQL mozgalica u kojoj se radilo o vremenskim intervalima. Modifikovao sam rešenje te mozgalice i došao sam do rešenja našeg problema:
CREATE VIEW bitni_datumi (datum, brojac)
AS
SELECT bd2.datum, SUM(bd1.brojac) AS brojac
FROM (SELECT pocetak AS datum, 1 AS brojac
FROM intervali
UNION ALL
SELECT kraj + 1, -1
FROM intervali
) AS bd1
INNER JOIN
(SELECT pocetak AS datum
FROM intervali
UNION ALL
SELECT kraj + 1
FROM intervali
) AS bd2
ON bd2.datum >= bd1.datum
GROUP BY bd2.datum
HAVING 2 > SUM(bd1.brojac);
SELECT bd1.datum, (SELECT MIN(bd2.datum)
FROM bitni_datumi AS bd2
WHERE bd2.datum > bd1.datum)
FROM bitni_datumi AS bd1
WHERE bd1.brojac = 1
ORDER BY 1;
Oba upita su ispravna, ali kako se snalaze sa većim skupom podataka? Testirao sam upite na skupu od 500 intervala. Dadin upit se izvršio za 15 sekundi, a moj za 26. Upiti su sporo, ali se to može rešiti sa indeksima.
CREATE INDEX in_int_pocetak ON intervali (pocetak); CREATE INDEX in_int_kraj ON intervali (kraj);
Ponovo sam startovao upite… i nastalo je veliko razoÄarenje: Dadin upit nije mogao da se izvrÅ¡i (planer se pobunio), a moj nije imao koristi od indeksa.
Instant rešenje
Uopšte nisam bio zadovoljan brzinom izvršavanja upita. U potrazi za rešenjem problema, setio sam se knjige SQL Cookbook od Anthony Molinaro-a, prelistao je i u poglavlju 10 našao rešenje za naš problem 🙂 Pustio sam upit na 500 intervala i dobio rešenje ispod u vremenu ispod 2 sekunde!
Naravno, ovaj upit je imao koristi od postavljenih indeka.
Nov pokušaj
Zar je moguće da ne mogu doći do dovoljno brzog ’domaćeg’ rešenja? Neću odustati dok ne napravim jedno.
Da razmislim. Å ta je bitno u celoj priÄi? PoÄeci i krajevi intervala… PoÄeci i krajevi. Ok, naÄ‘em sve poÄetke i sve krajeve intervala, numeriÅ¡em ih po starosti (ili mladosti?) i onda uparim poÄetak sa krajem koji ima istu numeraciju.
CREATE VIEW poceci (pocetak)
AS
SELECT i1.pocetak
FROM intervali AS i1
WHERE NOT EXISTS
(SELECT i2.pocetak
FROM intervali AS i2
WHERE i1.pocetak = i2.kraj);
CREATE VIEW krajevi (kraj)
AS
SELECT i1.kraj
FROM intervali AS i1
WHERE NOT EXISTS
(SELECT i2.kraj
FROM intervali AS i2
WHERE i2.pocetak = i1.kraj);
-- moj upit br. 2
SELECT MIN(p.pocetak), MAX(k.kraj)
FROM -- numerisanje pocetaka
(SELECT p1.pocetak,
COUNT(p2.pocetak) AS redosled
FROM poceci AS p1
INNER JOIN
poceci AS p2
ON p1.pocetak >= p2.pocetak
GROUP BY p1.pocetak) AS p
INNER JOIN
-- numerisanje krajeva
(SELECT k1.kraj,
COUNT(k2.kraj) AS redosled
FROM krajevi AS k1
INNER JOIN
krajevi AS k2
ON k1.kraj >= k2.kraj
GROUP BY k1.kraj) AS k
-- uparivanje pocetaka i krajeva
ON p.redosled = k.redosled
ORDER BY p.redosled;
Testirao sam moj drugi upit na 500 intervala i dobio sam rezultat za 50 milisekundi! E to je brzina izvršavanja s kojom sam zadovoljan. Upit je definitivno koristio postavljene indekse.
Bilo je vreme da se izvrÅ¡i testiranje nad skupom od recimo 15000 intervala (ovo je broj podataka koji je veći od broja podataka kojih će biti u produkcionoj bazi). Moj prvi upit je van konkurencije i nisam ga ni testirao. Pustio sam upit iz knjige i Äekao… Äekao… Äekao… i nakon 10 minuta i 30 sekundi se upit uspeÅ¡no zavrÅ¡io.
Pustio sam svoj upit broj dva. Upit se završio za 6 i po sekundi!
Krajnje rešenje
Bio sam priliÄno zadovoljan brzinom izvrÅ¡avanja svog upita i bilo mi je jasno koji upit će se koristit u produkciji, ali… kopkala me je joÅ¡ jedna stvar. Najsporija operacija u izvrÅ¡avanju upita je numerisanje poÄetaka i numerisanje krajeva. Da li se to može nekako izbeći?
Opet mi se u glavu vratio Dadin upit. On je u svom upitu koristio logiku ’najveći među datumima manjim od’. Primenio sam tu logiku na moj upit broj 2 i kao rezultat sam dobio upit
-- moj upit br. 3
SELECT (SELECT MAX(p.pocetak)
FROM poceci AS p
WHERE k.kraj > p.pocetak) AS pocetak,
k.kraj
FROM krajevi AS k
ORDER BY k.kraj;
Testirao sam gorni upit na skupu od 15000 intervala i upit se izvršio za 350 milisekundi! Pored toga što je najbrži, upit je i najjasniji od svih prikazanih upita.
PreÅ¡ao sam priliÄan put od prvog upita koji bi sesigurno izvrÅ¡avao danima da sam ga pokrenuo na skupu od 15000 intervala, do poslednjeg upita koji istu stvar radi za manje od sekunde. Poslednji upit je na stotine hiljada puta brži od prvog upita!
Završne napomene
O Dadinom upitu
Sva testiranja su obavljena na PostgreSQL 8.1.0 serveru kojeg koristimo u produkciji. Pustio sam Dadin upit na PostgreSQL 8.2.4 serveru i upit je uspešno izvršen. Na testu od 15000 intervala se upit pokazao izuzetno uspešan sa vremenom izvršavanja od 800 milisekundi.
O upitu iz knjige SQL Cookbook
Upit iz knjige se nije pokazao efikasan na PostgreSQL-u. U knjizi postoji i specijalno reÅ¡enje za Oracle koje koristi analitiÄke funkcije. Ovo reÅ¡enje se na OracleXE 10.2g pokazalo uspeÅ¡no za brzinom od 250 milisekundi na skupu od 15000 intervala.
ZakljuÄak
1. Znatna ubrzanja u izvrÅ¡avanju upita su nastala prelaskom sa razmatranja celog skupa podataka, na razmatranje samo interesantnog podskupa (poÄeci i krajevi). Treba Å¡to pre eliminisati nebitne stvari.
2. Ne treba nekritiÄno verovati svemu Å¡to se proÄita u knjizi (Älanku, internetu). Uvek treba tražiti naÄin za unapreÄ‘enje.