Postgres full-text search korak po korak

April 5, 2021

Nikola Kadić

Čak ni danas većina sajtova nema funkciju za kvalitetnu pretragu sadržaja.

Sajtovi koji su bogati sadržajem imaju težak zadatak da funkciju pretrage učine kvalitetnom. Glavne metrike koje uzimamo su brzina odgovora i relevantnost rezultata.

Problem je čest, a u rješavanju se najčešće pribjegava nekim ugrađenim mogućnostima frameworka u kojem se radi. Druga česta opcija su third-party rješenja poput Elasticsearch-a ili search as a service platforme Algolia. Ovakva rješenja, pored slučajeva u kojima su odlično rješenje, znaju da budu overkill, zahtijevaju vrijeme za razvoj, izmjenu arhitekture, održavanje, dodaju zavisnost, koštaju.

U nastavku ću baš za proizvode kategorije malih i srednje velikih sistema predložiti jedno pragmatično open source rješenje za search funkcionalnost. Uzmimo za primjer CMS – registar gradova, čiji je sadržaj skladišten u relacionu bazu podataka. Imamo želju da za taj CMS napravimo i mogućnost pretrage.

 

SQL LIKE OPERATOR

Prvi korak kojem se obično pristupi je korišćenje LIKE operatora, ukoliko ga sistem za upravljanje bazama podataka podržava. Naravno, sljedeći spisak važi i za ORM ekvivalenta LIKE operatoru.

Ovakav pristup rješava problem, ali stvara i nove – uglavnom povezane sa performansama:

  1. Wildcard %, pri korišćenju na početku čini indekse neupotrebljivim
  2. Obično je case sensitive, pa upit ‘Django’ neće dati rezultate sa ‘django’ u sadržaju
  3. LIKE operator nema podršku za prepoznavanje riječi. Ovo utiče na relevantnost rezultata pretrage, jer će upit ‘ngo’ dati rezultate koji sadrže ‘Django’
  4. Nemoguće je vršiti rangiranje po brojevima pojavljivanja u sadržaju. Stranica sa jednim pojavljivanjem riječi po kojoj se pretražuje se može pojaviti prije one gdje se ta riječ pojavljuje više puta.
  5. Kolona po kolona. Ukoliko vaša pretraga podrazumijeva traženje po više kolona (naziv, opis, kategorija) ova operacija će naglo pasti u performansama
  6. Lingvističko korjenovanje riječi – LIKE operator nema podršku za pretragu po istom korijenu riječi. Npr. riječ programiranje neće dati rezultate koji sadrže riječ programiranja.

Neke od ovih problema možemo riješiti – doduše ne tako lijepo i bez gubitaka. Na primjer – treći problem sa spiska bi se mogao riješiti ILIKE operatorom koji se mnogo sporije evaluira i nema podršku kod svih SUBP. Osim problema sa performansama, nemamo ništa za mjerenje relevantnosti rezultata – rangiranje.

 

Napraviću brzu implementaciju i pokazati prednosti Postgresovog FTS na primjerima u Django Web Development frameworku.

Uzmimo Django model gradovi (biće konvertovano u tabelu relacione baze):

class Cities(models.Model):
    city = models.CharField(max_length=128)
    country = models.CharField(max_length=128)
    shortcode = models.CharField(max_length=2)
    zipcode = models.CharField(max_length=10)


Važnost indeksiranja

Ne želimo da search prolazi sekvencijalno kroz bazu podataka. Ne postoji bolja i lakša optimizacija od pravljenja indeksa na kolone po kojima se pretražuje.

CREATE INDEX city_name_idx ON city (city_name);

Indeks će kreirati B stablo koje će pretragu sa vremenske složenosti O(n) svesti na O(log n).

 

Koristeći Djangov ORM pravimo pretragu po imenu grada i države:

results = Cities.objects.filter(city__contains=query).values('name', 'country')

Prevedeno u SQL:

SELECT city, country FROM cities WHERE city LIKE '%Podgorica%';

Ovim wildcard-om % prije Podgorica onemogućavamo rad indeksa i značajno gubimo na performansama.

Ukoliko se odlučimo da zanemarimo taj wildcard, imaćemo indeks ali nećemo imati pretragu po “sredini” riječi.

Konačno, dolazimo do full text searcha.

Kako je Postgres u podrazumijevanom steku sa Djangom, uz minimalni uloženi trud, imaćemo prvi full text search query.

results = Cities.objects.filter(city__search=query).values('city', 'country')

U raw SQL obliku:

SELECT city, country
FROM cities
WHERE to_tsvector(COALESCE(city, '')) @@ (plainto_tsquery('Podgorica')) = true;

Da bi izvršio pretragu, ORM koristi to_tsvector i plainto_tsquery funkcije. Ove funkcije prilagođavaju tip podataka riječi po kojoj se pretražuje i ispituje poklapanja. plainto_tsquery funkcija uzima riječi ako su razdvojene whitespace-om i pravi konjunkciju tako da rezultati sadrže svaku od riječi iz pretrage.

Postgres EXPLAIN ANALYZE query plan analiza pokazuje da ovaj query uzima 10x više vremena od prvog primjera, kada smo koristili LIKE %QUERY%. Nismo zadovoljni ovakvim rezultatima.

Prva optimizacija koju treba uraditi je naravno indeks – pravljenjem Generalized Inverted Index (GIN) po upravo ovim funkcijama.

Ovim indeksom se osjetno povećava brzina izvršavanja pretrage. A sa full text search-om smo dobili još neke dobre mogućnosti:

Pretraga po jednoj koloni je često ograničavajuća – zato koristimo SearchVector (niz kolona u kojima vršimo pretragu – iz iste ili različitih tabela).
Istu fleksibilnost dobijamo i sa druge strane – sa SearchQuery koji prevodi query u objekat koji kasnije SUBP upoređuje sa SearchVector-om. Usput vrši obradu unesenih riječi – odsijecanje krajeva, korjenovanje, varijacije.  Ovo out-of-the-box rješava mnoge probleme pretrage – za naš jezik karakteristično, otpornost na padežne oblike (deklinaciju).

 

Relevantnost rezultata

Na početku teksta smo pomenuli da kvalitet pretrage mjerimo po brzini i relevantnosti podataka. O brzini je bilo riječi, a za relevantnost se možemo pobrinuti Postgres-ovim SearchRank-om. Možemo pojasniti primjerom:

vector = SearchVector('city')
query = SearchQuery('podgorici')
Cities.objects.annotate(rank=SearchRank(vector, query)).order_by('-rank')

Iskoristićemo sve što nam pružaju SearchVector , SearchQuery ali i SearchRank. Naravno moguće je i kombinovanje kolona i složeno sortiranje, kao i filtriranje po relevantnosti u SearchRank-u.

rank = SearchRank(vector, query, weights=[0.2, 0.4, 0.6, 0.8])
Cities.objects.annotate(rank=rank).filter(rank__gte=0.3).order_by('-rank')

Osim ovoga interesantno je i upoređivanje sličnosti po TrigramSimilarity.

 

Zaključak

Postgres nudi širok spektar alata za full text search, a mi smo u ovom tekstu vidjeli nekoliko njih. Osim toga, pomenuli smo potencijalne optimizacije sa GIN indeksima. Iako je i dalje sam zahtjev za dobar pretraživač sadržaja veoma izazovan, dobro poznavanje FTS može pomoći ukoliko je to najbolja opcija za vaš use case.

 

Nikola Kadić

Linkedin

Student Računarskih nauka na PMF-u u Podgorici
Softver inženjer i Product Owner u Coinis DOO
Predavač u Developers lab

 

Reference:
https://www.postgresql.org/docs/9.5/textsearch.html
https://docs.djangoproject.com/en/3.1/ref/contrib/postgres/search/