Tuesday, 07.08.2007 – Srdjan
Pre 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.
Objavljeno u: Best practice, PostgreSQL, SQL | Nema komentara »
