Problem „głębokiego” stronicowania

Wyobraźmy sobie następujący problem – mamy aplikację, która oczekuje od Solr zwracania posortowanych po pewnym polu wyników, które będą następnie stronicowane. Jednak, jeżeli osoba korzystająca z aplikacji wybierze od razu dziesiątą, dwudziestą, czy pięćdziesiątą stronę wyników wyszukiwania pojawia się problem długiego oczekiwania na wyniki wyszukiwania. Czy jest coś co możemy z tym zrobić ? Tak, możemy trochę pomóc Solr.

Kilka liczb na początek

Zacznijmy od zapytania i statystyk. Wyobraźmy sobie, że mamy następujące zapytanie, które jest wysyłane do Solr, aby pobrać pięćsetną stronę wyników wyszukiwania:

q=*:*&sort=price+asc&rows=100&start=50000

Co musi zrobić Solr, aby pobrać i zaprezentować wyniki ? Oczywiście odczytać dokumenty z Lucene. Pojawia się oczywiście pytanie, jak dużo dokumentów ma być odczytanych z indeksu ? Czyżby 100 ? Niestety nie. Z indeksu Lucene musi być pobrane 50,100 dokumentów posortowanych po autorze, ze względu na to, że chcemy 100 dokumentów zaczynając od tego, podanego jako wartość parametru start. Troche przerażające. Spójrzmy teraz na porównanie, ile czasu zajmuje dla Solr pobranie pierwszej strony wyników wyszukiwania (czyli zapytania q=*:*&sort=price+asc&rows=100&start=0) oraz ile zajmie pobranie ostatniej strony wyników wyszukiwania (czyli zapytania q=*:*&sort=price+asc&rows=100&start=999900). Test wykonany był na indeksie zawierającym milion dokumentów, składających się z czterech pól: id (string), name (text), description (text), price (long). Sam test to uruchomienie Solr, zadanie zapytania i wyłączenie Solr. Te czynności były powtarzane 100 razy dla każdego z zapytań, a czas widziany w tabeli to średnia arytmetyczna uzyskanych czasów. A oto wyniki testu:

[table “16” not found /]

Typowe rozwiązania

Oczywiście możemy próbować z ustawieniem cache’u, czy z wielkością queryResultWindowSize, ale jak tego nie ustawimy, może zdarzyć się sytuacja, gdzie będzie to niewystarczające, albo nie będzie odpowiedniego wpisu w pamięci Solr i wtedy czas oczekiwania na n-tą stronę wyszukiwania będzie bardzo długi. Dochodzą do tego zapytania rozgrzewające, ale tutaj także nie przygotujemy wszystkich kombinacji, a i cache musiałby być duży. Zatem żadne z przedstawionych rozwiązań nie przyniesie oczekiwanego rezultatu.

Filtry, filtry i jeszcze raz filtry

Takie zachowanie Solr (a także innych aplikacji opartych o Lucene) spowodowane jest kolejką dokumentów, tzw. priority queue, która aby wyświetlić ostatnią stronę wyników musi pobrać wszystkie dokumenty pasujące do zapytania i zwrócić tyle te, które chcemy. Oczywiście, w naszym przypadku, jeżeli chcemy pierwszą stronę wyników wyszukiwania kolejka będzie miała 100 wpisów. Natomiast jeżeli będziemy chcieli ostatnią stronę wyszukiwania Solr będzie musiał umieścić w kolejce milion dokumentów. To tak w dużym uproszczeniu.

Pomysł polega na tym, aby ograniczyć ilość dokumentów, jakie Solr musi umieścić w kolejce. Jak to zrobić ? Z pomocą przyjdą nam filtry, czyli parametr fq. Za pomocą filtru ograniczymy ilość wyników wyszukiwania. Idealną wielkością byłaby taka jak wartość parametru rows, który przekazujemy w zapytaniu. Jednak to jest sytuacja idealna i mało realna w rzeczywistości. Dodatkowym problemem jest to, iż zadając zapytanie z filtrem nie jesteśmy w stanie określić liczby wyników, ponieważ nie wiemy jak dużym ograniczeniem jest filtr. Rozwiązaniem tego problemu jest zadanie dwóch zapytań, pierwszego z samym filtrem oraz parametrami rows=0 i start=0, aby pobrać ilość wyników jaką zwraca filtr, a drugie już odpowiednio obliczone (przykład poniżej).

W danych testowych przygotowanych na potrzebny wpisu maksymalna cena produktu to 10.000, a minimalna to 0. Zatem do pierwszego zapytania dodamy przedział <0; 1000>, a do drugiego zapytania (a tak naprawdę dwóch zapytań) dodamy przedział <9000; 10000>.

Minus rozwiązania opartego o filtry

Jest jeden minus rozwiązania opartego o filtry i jest on dość duży. Może się zdarzyć tak, że liczba wyników do jakiej ogranicza nas filtr jest za mała. Co wtedy ? Należy zwiększyć przedział dla filtra, a ponieważ część danych o które będziemy się „pytać” została już odczytana, będzie ona pobrana bardzo szybko. Możemy oczywiście wyliczać optymalne parametry wielkości przedziałów, gdzie zawsze znajdzie się odpowiednia ilość danych, ale zależy to od danych i zapytań i dlatego nie będziemy się tym zajmować w tym momencie.

Jak wygląda wydajność po zmianie ?

Przyjrzyjmy się zatem, jak wygląda to po zmianie, kiedy ograniczamy ilość wyników za pomocą filtra. Tak samo jak powyżej, będziemy korzystać sprawdzamy wyniki dla pierwszej strony wyszukiwania (czyli zapytania q=*:*&sort=price+asc&rows=100&start=0&fq=price:[0+TO+1000]) oraz ostatniej (czyli dwa zapytania: q=*:*&sort=price+asc&rows=0&start=0&fq=price:[9000+TO+10000] oraz q=*:*&sort=price+asc&rows=100&start=100037&fq=price:[9000+TO+10000]). Warto zauważyć, że zmienił się parametr start w zapytaniu, ze względu na to, że dostajemy mniej wyników wyszukiwania. Sam test był przeprowadzany analogicznie tego tego bez filtrów, czyli: uruchomienie Solr, zadanie zapytania (bądź zapytań), zatrzymanie Solr i tak sto powtórzeń. Liczba widziana w tabeli to średnia arytmetyczna czasów wykonania zapytań przypadających na dany test.

[table “17” not found /]

Jak widać, Solr przyspieszył i to znacznie. Możemy zatem uznać, że osiągnęliśmy sukces. Oczywiście moglibyśmy się pokusić o kolejne optymalizacje (jak np. usunięcie sortowania z zapytania pomocniczego), ale uznajmy, że na razie jesteśmy zadowoleni z wyników. Podejrzewam jednak, że możecie zadać następujące pytanie:

Jak to robią inne wyszukiwarki ?

Dobre pytanie, ale odpowiedź jest w sumie banalna – jedną z metod jest zabronienie bardzo głębokiego stronicowania. Taką metodę stosuje m.in. Google. Spróbujcie wpisać słowo „ask” do wyszukiwarki i przejść dalej, niż 91 strona wyników wyszukiwania. Mi Google nie pozwolił 😉

Podsumowanie

Jak widać wydajność głębokiego stronicowania po naszych zmianach wzrosła i to znacznie. Możemy teraz pozwolić użytkownikowi na przeszukiwanie wyników wyszukiwania bez obaw, że zabije nam to Solr i maszynę na której pracuje. Oczywiście metoda ta nie jest bez wad, ze względu na to, że musimy znać pewne parametry (np. w naszym przypadku maksymalną cenę dla sortowania malejącego), natomiast jest to już jakieś rozwiązanie, które pozwala na dostarczenie wyników wyszukiwania w relatywnie niskim czasie porównując do tego sprzed optymalizacji.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *