Moim skromnym zdaniem, żeby w pełni świadomie używać jakiegoś narzędzia należy chociaż w minimalnym stopniu dowiedzieć się co znajduje się pod maską i co z czym się łączy. W poprzednich wpisach wspominałem już, że Elasticsearch został oparty o Javową bibliotekę Apache Lucene dostarczającą pełnotekstowe wyszukiwanie. Dziś chciałbym przekazać Ci jedno podstawowe zagadnienie, związane właśnie z Lucene, którego zapamiętanie może niejednokrotnie uratować Ci dupę podczas dostrajania Elasticsearcha.

Części wspólne

Kiedy przyjrzymy się na listę podstawowych pojęć obydwu narzędzi, to zobaczymy, że zarówno Elasticsearch, jak i Apache Lucene mają coś takiego jak index oraz document. Te dwa pojęcia są ze sobą powiązane – dokument jest podstawową jednostką, która jest do indeksu wrzucana, a później (podczas wyszukiwania) z niego wyciągana. Raczej nie trudno jest się domyślić, że Elasticsearch czerpie w tym miejscu z Apache Lucene i pod maską wynikowym indeksem jest właśnie indeks tej biblioteki.

Jak działa Apache Lucene?

Indeks i dokumenty nie są jedynymi elementami dostarczanymi przez Lucene, z których korzysta Elasticsearch. Jest ich znacznie więcej. Nie chciałbym teraz jednak poruszać tego tematu zbyt dogłębnie bo zajęłoby to więcej czasu, niż cała seria artykułów, którą tu zaplanowałem 😉 Podobnie byłoby zresztą z opisaniem dokładnie jak działa Apache Lucene, jak wygląda struktura indeksu na dysku, czy to w jaki sposób optymalizowany jest jego rozmiar. Być może kiedyś powstaną odrębne wpisy na ten temat, ale na razie odsyłam Cię do dokumentacji i innych „internetów”. Dziś chciałbym przekazać Ci jedną wskazówkę, bez której sam się na początku kilka razy przejechałem.

Chciałbym, żebyś dowiedział(a) się i zapamiętał(a) w jaki sposób budowany jest indeks i jak wygląda jego wynikowa struktura. Zrozumienie tej koncepcji i trzymanie jej „z tyłu głowy” podczas projektowania zapytań pozwoli Ci zaoszczędzić naprawdę sporo czasu w dochodzeniu do tego dlaczego to działa tak wolno 😉

Cykl artykułów "Uczymy się Elasticsearch"

Ten wpis jest częścią cyklu, w którym staram się pokazać w jaki sposób możesz zbudować przyjazną dla użytkownika wyszukiwarkę, wykorzystując do tego celu potężny silnik wyszukiwania jakim jest Elasticsearch.

Do tej pory w ramach cyklu ukazały się następujące artykuły:

  1. instalacja, uruchomienie i pierwsze zapytanie
  2. kilka słów na temat Elastic Stack
  3. przydatne narzędzia
  4. indeks odwrócony Apache Lucene
  5. wyszukiwanie pełnotekstowe
  6. trafność
  7. przygotowanie tekstu do optymalnego wyszukiwania
  8. coś poszło nie tak, czyli seria moich fackupów
  9. ...

Indeks odwrócony

Generalnie rzecz biorąc struktura indeksu w Apache Lucene, a co za tym idzie i w Elasticsearchu oparta jest o koncepcję indeksu odwróconego (ang. inverted index). Idea jest bardzo podobna do indeksu, który znajduje się na końcu niektórych książek. Zawiera on alfabetyczny spis jakichś zagadnień (np. nazwisk) oraz spis stron, na których dane zagadnienie występuje.

indeks odwrócony w książkach

indeks odwrócony w książkach

Struktura indeksu w Elasticsearchu wygląda analogicznie. Prześledźmy na przykładzie jak taki indeks powstaje. Załóżmy, że mamy trzy dokumenty, które wysyłamy do Elasticsearcha:

Po wrzuceniu pierwszego dokumentu indeks będzie wyglądał mniej więcej tak:

Dorzucając drugi dokument dostaniemy:

Dorzucając trzeci mamy:

Na pewno łapiesz już o co chodzi.

W rzeczywistości indeks w Apache Lucene, w zależności od konfiguracji, przechowuje znacznie więcej informacji. Zawiera choćby licznik wystąpień danego tokenu (tak nazywa się poszczególny element w indeksie) w dokumencie (w naszym przykładzie słowa the, forcewith w trzecim pliku wystąpiły dwukrotnie), czy informację o umiejscowieniu danego tokenu.

Dodatkowo wraz z każdym tokenem przechowywana jest informacja o polu, z którego ten token pochodzi. U nas każdy z tokenów miałby prefix sentence, np. sentence:always, czy sentence:am. Takie rozróżnienie wykorzystywane jest w wielu zapytaniach Elasticsearcha.

To, że u nas w magiczny sposób wszystkie tokeny zostały zapisane małymi literami jest również uproszczeniem. Zresztą tak samo jak fakt, że do indeksu wpadły wszystkie tokeny. To co i jak tam ostatecznie wpada zależne jest od tego jakie tokenizery użyjemy.

Żadne z tych uproszczeń nie ma dla nas w tej chwili najmniejszego znaczenia. Bez tego wszystkiego powyższy przykład pokazuje to co najbardziej chciałbym Ci dzisiaj przekazać.

Do zapamiętania

Najważniejsza wskazówka na dziś: pamiętaj, że indeks jest alfabetyczny! Dlaczego jest to aż tak ważne? Ano dlatego, że zapytanie, w którym znamy początek słowa i chcemy, żeby Elasticsearch dopasował nam końcówkę jest dla niego „naturalne”, podczas gdy dopasowanie początku słowa przy znajomości końcówki już nie.

Załóżmy, że w powyższym indeksie chcemy wyszukać wszystkie słowa pasujące do wzorca th*. Upraszczając cały proces, Lucene weźmie sobie pierwszą literę (t) i (dzięki temu, że indeks jest alfabetyczny) przeskoczy pierwsze 12 elementów, a także pominie trzy ostanie czym zawęzi szukanie do trzech elementów zaczynających się na szukaną literę. W następnym kroku weźmie drugą literę (h) i powtórzy działanie z poprzedniego kroku. W ten sposób wykorzystując wiedzę o posortowaniu indeksu efektywnie przeskanowanych zostanie tylko część elementów.

Co się stanie w momencie kiedy będziemy chcieli poszukać wszystkie słowa pasujące do teoretycznie analogicznego wzorca *th? W tym przypadku alfabetyczna struktura indeksu na nic się nie zda. Lucene będzie musiało przeskanować każdy element indeksu po kolei i sprawdzić czy pasuje do naszego wzorca. Widzisz już do czego zmierzam? W naszym indeksie mamy tylko 18 elementów. Co się stanie gdy będą ich miliony?

The End

Wiedza o alfabetycznej strukturze indeksu wykorzystywanego przez Elasticsearch powinna uświadomić Ci, że zapytania, które choćby w najmniejszym stopniu podpowiadają silnikowi jaką część indeksu może pominąć będę zawsze o wiele wydajniejsze od tych każących mu skanować całość. Na szczęście twórcy Elasticsearcha w dużej mierze pomyśleli o tym za nas. Są jednak takie miejsca, w których nieświadomie możemy coś zepsuć.

Jeżeli Twoje zapytanie jest zaskakująco wolne lub spowalnia wraz z wydłużaniem się szukanej frazy, to jest duża szansa, że właśnie zapomniał[a|e]ś jak wygląda struktura indeksu siedzącego pod spodem. W dalszych częściach cyklu pokarzę Ci gdzie ja nieświadomie się na to nadziałem.

Bądź na bieżąco!

Podobają Ci się treści publikowane na moim blogu? Nie chcesz niczego pominąć? Zachęcam Cię do subskrybowania kanału RSS, polubienia fanpage na Facebooku, zapisania się na listę mailingową:




Uwaga! Jeżeli w ciągu 24-godzin od zapisania się na listę mailingową nie otrzymasz wybranego przez siebie prezentu to skontaktuj się ze mną.

Zgoda? Zapisując się do newslettera wyrażasz zgodę na przesyłanie Ci starannie wyselekcjonowanych informacji marketingowych. Powyższe dane są przechowywane w systemie MailChimp i nie są udostępniane nikomu więcej.

lub śledzenia mnie na Twitterze. Generalnie polecam wykonanie wszystkich tych czynności, bo często zdarza się tak, że daną treść wrzucam tylko w jedno miejsce. Zawsze możesz zrobić to na próbę, a jeśli Ci się nie spodoba – zrezygnować :)

Chcesz więcej? W takim razie zapraszam Cię do dołączenia do powiązanych grup na Facebooku, gdzie znajdziesz dodatkowe informacje na poruszane tutaj tematy, możesz podzielić się własnymi doświadczeniami i przemyśleniami, a przede wszystkim poznasz ludzi interesujących się tą samą tematyką co Ty.

W grupie Programista Na Swoim znajdziesz wiele doświadczonych osób chętnych do porozmawiania na tematy krążące wokół samozatrudnienia i prowadzenia programistycznej działalności gospodarczej. Vademecum Juniora przeznaczone jest zaś do wymiany wiedzy i doświadczeń na temat życia, kariery i problemów (niekoniecznie młodego) programisty.

1 000 000 zł

Milion złotych. Tak, milion złotych. Milion złotych to cel, który sobie postawiłem jakiś czas temu. Chcę zarobić milion złotych na tym blogu. Do tej pory zebrało się 34 228,77 zł, więc jak widzisz jest już co pokazać, ale do celu nadal sporo brakuje. Jeszcze nie wiem do końca jak, ale to zrobię. Na pewno nigdy nie będę pobierał żadnych opłat za dostęp do treści, bo tymi chcę się po prostu dzielić.

Wysoko ponad ten milion stawiam na szerzenie wiedzy i dotarcie do jak największej liczby osób. I tu mam prośbę do Ciebie: jeśli uważasz, ten artykuł za wartościowy, to udostępnij go proszę swoim znajomym. Przy lewej lub dolnej (na małych wyświetlaczach) krawędzi ekranu znajdziesz przyciski, które Ci to ułatwią. Jeżeli ich nie widzisz, to najprawdopodobniej zostały zablokowane przez Twój program do blokowania reklam. Niezależnie od tego, czy prześlesz ten wpis dalej, czy nie, to ja i tak dziękuję Ci serdecznie za doczytanie do tego miejsca! Do przeczytania niebawem.

PS. Jeśli mój blog przypadł Ci do gustu tak bardzo, że chciał(a)byś mi się w jakiś sposób odwdzięczyć, to mam dla Ciebie kilka ciekawych propozycji, z których możesz skorzystać. Szczególnie gorąco zachęcam do wsparcia poprzez serwis Patronite, ale jeżeli zdecydujesz się na którąkolwiek z wymienionych opcji, to serdecznie Ci za to DZIĘKUJĘ!

Picture Credits
Tribute to Patrons