Spajanje neprekidnih datumskih intervala

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.

Post a Comment