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 😉
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
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:
|
|
{ "id": 1, "sentence": "The Force will be with you. Always." } |
|
|
{ "id": 2, "sentence": "Do. Or do not. There is no try." } |
|
|
{ "id": 3, "sentence": "I am one with the Force. The Force is with me." } |
Po wrzuceniu pierwszego dokumentu indeks będzie wyglądał mniej więcej tak:
|
|
always -> 1 be -> 1 force -> 1 the -> 1 will -> 1 with -> 1 you -> 1 |
Dorzucając drugi dokument dostaniemy:
|
|
always -> 1 be -> 1 do -> 2 force -> 1 is -> 2 no -> 2 not -> 2 or -> 2 the -> 1 there -> 2 try -> 2 will -> 1 with -> 1 you -> 1 |
Dorzucając trzeci mamy:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
always -> 1 am -> 3 be -> 1 do -> 2 force -> 1 | 3 i -> 3 is -> 2 | 3 me -> 3 no -> 2 not -> 2 one -> 3 or -> 2 the -> 1 | 3 there -> 2 try -> 2 will -> 1 with -> 1 | 3 you -> 1 |
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, force i with 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ą:
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ć 
Dołącz do grup na Facebooku
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.
Wesprzyj mnie
Jeżeli znalezione tutaj treści sprawiły, że masz ochotę wesprzeć moją działalność online, to zobacz na ile różnych sposobów możesz to zrobić. Niezależnie od tego co wybierzesz, będę Ci za to ogromnie wdzięczny.
Na wsparciu możesz także samemu zyskać. Wystarczy, że rzucisz okiem na listę różnych narzędzi, które używam i polecam. Decydując się na skorzystanie z któregokolwiek linku referencyjnego otrzymasz bonus również dla siebie.
Picture Credits
Dodaj komentarz