Korištenje hash-indeksa kod pretraživanja MySQL baze podataka

Različite vrste sistemskog modula MySQL Storage Engine podržavaju različite tipove indeksa prema svojoj internoj strukturi. U ovom tekst ćemo se detaljnije pozabaviti hash‑indeksima i njihovom upotrebom za optimizaciju upita na vrlo velikim bazama podataka.

Nabrojimo prvo najvažnija svojstva hash-indeksa:

  1. Kao vrijednosti indeksa, umjesto originalnih vrijednosti iz tablica (ili njihovih dijelova), čuvaju se posebno izračunate (hash) vrijednosti za svaki red tablice.
  2. Budući da takve izračunate vrijednosti zauzimaju relativno malu količinu memorije, predstavljaju idealnu vrstu indeksa za modul Memory Storage Engine, gdje su upravo hash-indeksi podrazumijevana vrsta indeksa.
  3. Kod vrlo velikog skupa podataka postoji mogućnost da dva različita podatka dobiju istu hash-vrijednost.
  4. Zbog toga što ne sadrže vrijednosti originalnih podataka nego izračunate vrijednosti ti podatci ne mogu se koristiti:

a) kao covering indeksi (indeksi iz kojih se izravno preuzima traženi podatak bez potrebe za pristupom originalnom redu tablice).

b) za ubrzavanje sortiranja podataka

c) za pretraživanje po djelomičnom podudaranju traženih vrijednosti niti za traženje raspona vrijednosti u podacima.

  1. Kod ostalih tipova sistemskih modula MySQL Storage Engine mogu se simulirati upotrebom MySQL funkcije CRC32 i B-Tree indeksa.

Upravo funkcija CRC32 omogućava korištenje simuliranih hash-indeksa za optimizirano pretraživanje određene vrste podataka u sustavima koji ih ne podržavaju – na primjer InnoDB ili MyISAM.

Podaci za koje je indeksiranje vrlo nepovoljno iz aspekta veličine indeksa i performansi korištenjem B-Tree tipa indeksa (podrazumijevana vrsta indeksa za InnoDB i MyISAM) su podaci čije se početne vrijednosti vrlo često ponavljaju, a razlika između pojedinih podataka nalazi se tek na samom kraju vrijednosti podataka. Tipičan primjer takve vrste podataka su web-adrese. Kod web-adresa početni dio adrese ponavlja se u velikom broju slučajeva, a razlike između podataka pojavljuju se tek na kraju naziva konkretne web‑lokacije odnosno stranice na toj lokaciji.

Korištenje B-Tree indeksa kod takve vrste podataka rezultira vrlo velikim zauzećem prostora (jer treba indeksirati prilično veliku dužinu cjelokupne web-adrese) te nešto sporijim pretraživanjem nego u slučaju da za te iste podatke primijenimo simulirane hash-indekse.

PRIMJER KORIŠTENJA

Slijedi prikaz upotrebe simuliranih hash-indeksa u praksi. Pretpostavimo da je originalna vrijednost primjera web-stranice koju treba indeksirati:

http://www.index.hr/vijesti/clanak/infografika-koja-je-razlika-izmedju-hidrogenske-i-obicne-nuklearne-bombe/992309.aspx

Dužina prethodnog niza je 119 znakova. Ako se na istu vrijednost primijeni MySQL funkcija CRC32 dobije se rezultat 1 082 117 441 ukupne dužine 10 znakova (skoro 12 puta manja veličina). Budući da je rezultat izvođenja funkcije u stvari broj, dobiveni rezultat možemo u bazi spremiti kao tip podatka INT, što dodatno smanjuje količinu zauzetog prostora te ubrzava izvođenje operacija nad podacima.

Ako se B-Tree indeks kreira na stupcu tablice s CRC vrijednosti umjesto na stupcu s originalnim vrijednostima, kao rezultat se dobije simulirani hash-indeks koji zauzima manje prostora te istovremeno nudi veću brzinu pretraživanja. Ovakva promjena zahtijeva izmjenu originalnog oblika SQL naredbe za pronalaženje reda tablice iz primjera:

select * from testtable where webpage = 'http://www.index.hr/vijesti/clanak/infografika-koja-je-razlika-izmedju-hidrogenske-i-obicne-nuklearne-bombe/992309.aspx'

u nešto drugačiji oblik:

SET @hash = crc32('http://www.index.hr/vijesti/clanak/infografika-koja-je-razlika-izmedju-hidrogenske-i-obicne-nuklearne-bombe/992309.aspx');
select * from testtable where hash = @hash;

Problem s ovakvom prvom verzijom izmijenjenog oblika naredbe SELECT je u jednoj od karakteristika hash-indeksa istaknutom u uvodnom dijelu teksta. Kod dovoljno velikog skupa podataka postoji mogućnost da funkcija CRC32 vrati istu vrijednost za dva potpuno različita podatka, što bi u konačnici rezultiralo neispravnim radom naredbe SELECT. Zato prethodni oblik naredbe treba izmijeniti u sljedeći oblik:

SET @webpage = 'http://www.index.hr/vijesti/clanak/infografika-koja-je-razlika-izmedju-hidrogenske-i-obicne-nuklearne-bombe/992309.aspx';
SET @hash = crc32(@webpage);
select * from testtable where hash = @hash and webpage = @webpage;

Ugrađeni optimizator upita će na temelju hash-vrijednosti brzo pronaći traženi slog tablice (ili više njih), a drugi dio upita (iza AND) osigurava vraćanje točno traženog podataka u eventualnom vraćenom skupu vrijednosti.

Problem koji još treba riješiti, kako bi simulirani hash-indeksi postigli punu funkcionalnost, je automatsko ažuriranje hash-vrijednosti u tablici kod svakog dodavanja ili izmjene originalne web-adrese.

Idealno rješenje navedenog problema predstavlja dodavanje dva okidača (triggera) na istu tablicu. Prvi od njih automatski izračunava hash-vrijednost kod svakog dodavanja nove web-adrese, a drugi kod njezine izmjene.

DELIMITER //

CREATE TRIGGER urlsearch_insert BEFORE INSERT ON urlsearch FOR EACH ROW BEGIN

     SET NEW.urlcrc=crc32(NEW.url);

END;

//

CREATE TRIGGER urlsearch_update BEFORE UPDATE ON urlsearch FOR EACH ROW BEGIN

     SET NEW.urlcrc=crc32(NEW.url);

END;

//

DELIMITER ;

Sličan pristup upotrebe simuliranih hash-indeksa može se primijeniti za optimizaciju pretraživanja bilo koje vrste tekstualno orijentiranih podataka kod kojih postoji velika količina podataka s ponavljanjem početnog dijela podataka.

Kategorija: