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:

ZapytanieŚredni czas odpowiedzi (ms)
q=*:*&sort=price+asc&rows=100&start=0146
q=*:*&sort=price+asc&rows=100&start=9999003184

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.

ZapytanieŚredni czas odpowiedzi (ms)
q=*:*&sort=price+asc&rows=100&start=0&fq=price:[0+TO+1000]128
q=*:*&rows=0&fq=price:[9000+TO+10000]
q=*:*&sort=price+asc&rows=100&start=100037&fq=price:[9000+TO+10000]
422

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.

This post is also available in: angielski

This entry was posted on poniedziałek, Lipiec 18th, 2011 at 08:51 and is filed under Solr. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

5 komentarzy to “Problem „głębokiego” stronicowania”

  1. GZyl Says:

    Jeśli „price” będzie z zakresu 0-10000 ale 99% wartości wypadnie w zakresie price:[9000+TO+10000]

    To zapytanie:
    q=*:*&sort=price+asc&rows=100&start=100037&fq=price:[9000+TO+10000]
    dostarczy nam krotki od 110.037 do 110.137

    Zapytanie:
    q=*:*&sort=price+asc&rows=100&start=999900
    dostarczy nam krotki od 999.900 do 1.000.000

    IMO: Bez przeczytania wszystkich dokumentów i wiedzy na temat rozkładu pola „price” ta optymalizacja nie ma sensu i w praktyce jest nie do zastosowania.

  2. gr0 Says:

    Słuszna uwaga, natomiast nie zgodzę się do końca ze stwierdzeniem, że optymalizacja w praktyce jest nie do zastosowania. Przykład, który pokazałeś, jest jednym z „ekstremalnych”, równie dobrze, możemy mieć sytuację, że wszystkie dokumenty będą miały cenę równą 1, ale to znów ekstremum. Znając dane, jesteśmy w stanie znaleźć odpowiedni przedział dla danych, nawet w dużym przybliżeniu. Chyba, że nie znamy danych, wtedy pojawia się duży problem i działamy na ślepo (ale wtedy stosowanie tej metody jest średnio sensowne). Tak jak napisałem, sprowadza się to tak naprawdę do kwestii danych. Należy też pamiętać, iż filtr po cenie jest tylko przykładem. Może inne filtrowanie będzie rozwiązaniem, może użytkownik trafił w pojedynczy dział, kategorię i w ramach tego posiadamy dodatkowe informacje pozwalające na filtrowanie ?

    Podsumowując, do nas i naszej wiedzy o danych należy decyzja czy ta metoda się sprawdzi, czy nie.

  3. virus Says:

    przykład dobry … zawsze można wziąć najmniejszą i najwiekszą wartość … sprawdzać co zapytanie czy czasem zakres nie jest zbyt szczelnie ustawiony i dociagnąć dane robiąc kolejne zapytanie z kolejnym filtrem.
    Mnie ciekawi jak SOLR ma sie do np. jakiś PrimaryKey… istnieje tutaj w ogóle takie pojęcie ?
    Pytam bo parę lat głównie siedziałem nad optymalizacja MySQL-a i tutaj mogę sie przyczepic ;> do artykułu o jedno.
    W MySQL (MyISAM) spokojnie można zrobić stronnicowanie do ostatniej strony i wydajność tego bedzie taka sama jak na 10 stronie.

  4. gr0 Says:

    Istnieje, jako taki klucz główny, ale nie jest to taki sam klucz jak w przypadku relacyjnych baz danych. Na szczęście od wersji 3.5 Lucene zostało wzbogacone o metodę searchAfter, która mocno optymalizuje zachowanie opisane w artykule.

  5. Solr 4.7 – wydajne stronicowanie | Solr Enterprise Search Says:

    […] dawno temu, opisywaliśmy problem tzw. głębokiego stronicowania. W skrócie – im dalszą stronę wyników chcemy pobrać, tym wolniejsze będzie zapytanie. […]