Solr i PhraseQuery, czyli różne sposoby premiowania fraz

W większości wdrożeń Lucene/Solr z którymi miałem do czynienia prędzej, czy później pojawiał się problem tuningu jakości wyników wyszukiwania. Jednym z prostszych sposób zwiększenia zadowolenia użytkowników z wyników wyszukiwania, a tym samym zadowolenia nas samych i naszych pracodawców jest premiowanie fraz. Mając do wyboru trzy najpopularniejsze parsery zapytań oraz szereg parametrów wpływających na ich zachowanie postanowiłem sprawdzić, jak radzi sobie Solr z  premiowaniem fraz znalezionych w dokumentach na etapie wyszukiwania oraz jaki wpływ mają te funkcjonalności na wydajność.

W obecnym trunk`u Solr, mamy dostępne trzy parsery zapytań:

• Standard Solr Query Parser, czyli domyślny parser dla Solr oparty na domyślnym parserze zapytań w Lucene
• DisMax Query Parser
• Extended DisMax Query Parser

Każdy z wyżej wymienionych parserów ma inne możliwości jeżeli chodzi premiowanie fraz na etapie zapytań. W tym wpisie nie zajmuję się kwestiami premiowania bliskości słów na etapie indeksowania, o tym napiszę innym razem. A więc wracając do parserów.

Standard Solr Query Parser

Parser oparty o standardowy parser zapytań Lucene oraz rozszerzający jego możliwości. Możliwości co do premiowania fraz nie są duże. Załóżmy, iż nasz system obsługuje dużą księgarnię internetową, gdzie użytkownicy są mogą oceniać książki, zostawiać komentarze, czy dyskutować na temat książek na forach, a my indeksujemy wszystkie te dane oraz później prezentujemy je w ramach wyników wyszukiwania. Możemy założyć także, iż użytkownik wpisując w pole wyszukiwania „Java wzorce projektowe” szuka książek dotyczących wzorców projektowych z przykładami w języku Java i takie książki chcemy mu pokazać. Żaden problem, zadajemy do Solr zapytanie:

q=java+wzorce+projektowe

I otrzymujemy listę książek. Można spocząć na laurach i stwierdzić, że nasza wyszukiwarka zachowuje się świetnie i chcemy nic więcej poprawiać. Ja jednak dodałbym do tego zapytania kolejną część – premiowanie fraz, tak aby książki, które w przeszukiwanych polach posiadają odpowiednią frazę (czyli tak naprawdę w których słowa podane przez użytkownika występują obok siebie) były pozycjonowane na początku listy wyników. Zmodyfikowane zapytanie wyglądałoby tak:

q=java+wzorce+projektowe+OR+"java+wzorce+projektowe"^30

Dodając dodatkowy fragment (+OR+”java+wzorce+projektowe”^30) na pierwszych miejscach listy wyników wyszukiwania dostaniemy dokumenty, które nie tylko mają w polach wyszukiwania termy (wyrazy) podane przez użytkownika, ale w tych polach mają te termy umiejscowione obok siebie. A tak wygląda zapytanie wygenerowane do Lucene:

<str name="parsedquery">name:java name:wzorce name:projektowe PhraseQuery(name:"java wzorce projektowe"^30.0)</str>
<str name="parsedquery_toString">name:java name:wzorce name:projektowe name:"java wzorce projektowe"^30.0</str>

Wyniki wyszukiwania dla tak skonstruowanego zapytania przedstawiają się następująco:

<?xml version="1.0" encoding="UTF-8"?>
<response>
<lst name="responseHeader">
   <int name="status">0</int>
   <int name="QTime">0</int>
   <lst name="params">
      <str name="q">java wzorce projektowe OR "java wzorce projektowe"^30</str>
      <str name="fl">score,id,name</str>
   </lst>
</lst>
<result name="response" numFound="5" start="0" maxScore="1.2399161">
   <doc>
      <float name="score">1.2399161</float>
      <str name="id">1</str>
      <str name="name">Java wzorce projektowe</str>
   </doc>
   <doc>
      <float name="score">0.010219089</float>
      <str name="id">2</str>
      <str name="name">Wzorce projektowe java</str>
   </doc>
   <doc>
      <float name="score">0.010219089</float>
      <str name="id">3</str>
      <str name="name">Wzorce java projektowe</str>
   </doc>
   <doc>
      <float name="score">0.010219089</float>
      <str name="id">4</str>
      <str name="name">Projektowe wzorce java</str>
   </doc>
   <doc>
      <float name="score">0.010219089</float>
      <str name="id">5</str>
      <str name="name">Projektowe java wzorce</str>
   </doc>
</result>
</response>

DisMax Query Parser

Oprócz możliwości skonstruowania zapytania w taki sposób, jak opisany powyżej mamy możliwość wykorzystania parametru pf oraz modyfikacji jego zachowania za pomocą parametru ps. Parametr pf przekazuje informacje o tym, w jakich polach mają być identyfikowane frazy. Parametru tego używa się w sposób analogiczny do parametru qf określając listę pól w jakich mają być identyfikowane frazy. Dodatkowo, należy dla każdego z podanych pól określić odpowiednie wartości podbicia (boost), bo jak wiemy domyślnym podbiciem jest 1. Zapytanie z wykorzystaniem DisMax`a wyglądałoby następująco:
q=java+wzorce+projektowe&defType=dismax&qf=name&pf=name^30&ps=0

Natomiast zapytanie przekazane do Lucene wygląda w sposób następujący:

<str name="parsedquery">+((DisjunctionMaxQuery((name:java)) DisjunctionMaxQuery((name:wzorce)) DisjunctionMaxQuery((name:projektowe)))~3) DisjunctionMaxQuery((name:"java wzorce projektowe"^30.0))</str>
<str name="parsedquery_toString">+(((name:java) (name:wzorce) (name:projektowe))~3) (name:"java wzorce projektowe"^30.0)</str>

Wyniki dla tak skonstruowanego zapytania przedstawiają się następująco:

<?xml version="1.0" encoding="UTF-8"?>
<response>
<lst name="responseHeader">
   <int name="status">0</int>
   <int name="QTime">0</int>
   <lst name="params">
      <str name="pf">name^30</str>
      <str name="fl">id,name,score</str>
      <str name="q">java wzorce projektowe</str>
      <str name="qf">name</str>
      <str name="defType">dismax</str>
      <str name="ps">0</str>
   </lst>
</lst>
<result name="response" numFound="5" start="0" maxScore="1.2399161">
   <doc>
      <float name="score">1.2399161</float>
      <str name="id">1</str>
      <str name="name">Java wzorce projektowe</str>
   </doc>
   <doc>
      <float name="score">0.013625451</float>
      <str name="id">2</str>
      <str name="name">Wzorce projektowe java</str>
   </doc>
   <doc>
      <float name="score">0.013625451</float>
      <str name="id">3</str>
      <str name="name">Wzorce java projektowe</str>
   </doc>
   <doc>
      <float name="score">0.013625451</float>
      <str name="id">4</str>
      <str name="name">Projektowe wzorce java</str>
   </doc>
   <doc>
      <float name="score">0.013625451</float>
      <str name="id">5</str>
      <str name="name">Projektowe java wzorce</str>
   </doc>
</result>
</response>

Warto zauważyć, iż kolejność wyników dla obu metod jest taka sama. Wynika to z tego, iż fraza została zidentyfikowana tylko w przypadku dokumentu z identyfikatorem 1. Wartość score dla tego dokumentu w obu przypadkach jest taka sama. Natomiast dokumenty znajdujące się na pozycjach od 2 do 4 mają w ramach danej metody dokładnie taką samą wartość score ze względu na zidentyfikowanie trzech termów i dokładnie taką samą długość pola name. Oczywiście istnieją różnice w wartości score tych dokumentów pomiędzy metodami, ale wynika to z różnic w składaniu zapytań.

Użyłem jednak współczynnika ps=0 nie wspominając zupełnie o tym co oznacza i do czego służy. W przypadku korzystania z parametru pf (oraz pf2, ale o tym później) parametr ps oznacza tzw. Phrase Slop, czyli maksymalną odległość słów od siebie, aby tworzyły frazę. Na przykład ps=2 będzie oznaczało, iż słowa mogą być maksymalnie dwie pozycje od siebie, aby tworzyły frazę. Należy jednak pamiętać, iż pomimo tego, że zarówno „Java przykładowe wzorce projektowe”, jak i „Java wzorce projektowe” stworzą frazę, jednak dokument o tytule „Java wzorce projektowe” będzie posiadał większy score pomimo ustawienia ps=2, ze względu na to, że termy położone są bliżej siebie.

Omówiliśmy już dwa przypadki premiowania fraz. Został nam ostatni opierający się na tzw. Enhanced Term Proximity Boosting, czyli metodzie premiowania nie tylko całych fraz, ale także ich poszczególnych części. Funkcjonalność tą oferuje jednak tylko i wyłączenie:

Extended DisMax Query Parser

Niestety bez skorzystania z trunk`a lub przeniesienia kawałka kodu nie ma możliwości skorzystania z eDisMax`a.

Zapytanie z eDisMax`em wyglądałoby następująco:

q=java+wzorce+projektowe&defType=edismax&qf=name&pf2=name^30&ps=0

Powyższe zapytanie, tworzy następujące zapytania do Lucene:

<str name="parsedquery">+(DisjunctionMaxQuery((name:java)) DisjunctionMaxQuery((name:wzorce)) DisjunctionMaxQuery((name:projektowe))) (DisjunctionMaxQuery((name:"java wzorce"^30.0)) DisjunctionMaxQuery((name:"wzorce projektowe"^30.0)))</str>
<str name="parsedquery_toString">+((name:java) (name:wzorce) (name:projektowe)) ((name:"java wzorce"^30.0) (name:"wzorce projektowe"^30.0))</str>

Jak widać oprócz standardowych DisjunctionMaxQuery charakterystycznych dla DisMax`a (a tym samym dla jego rozszerzonej wersji) które wyszukują poszczególne termy przekazane do parametru q stworzone zostały także dwa dodatkowe zapytania, które odpowiadają za funkcjonalność enhanced term proximity boosting. Polega ona na stworzeniu par ze słów występujących obok siebie. W opisywanym testowym przypadku stworzone zostały pary „java wzorce” oraz „wzorce projektowe”. Jak można się domyślić najbardziej znaczącymi dokumentami na liście wyników, będą dokumenty posiadające obie wygenerowane pary, kolejne dokument będą posiadały jedną z par, a kolejne nie będą posiadały żadnej. Na potwierdzenie przedstawiam wynik zadania powyższego zapytania do Solr:

<?xml version="1.0" encoding="UTF-8"?>
<response>
<lst name="responseHeader">
   <int name="status">0</int>
   <int name="QTime">0</int>
   <lst name="params">
      <str name="fl">id,name,score</str>
      <str name="q">java wzorce projektowe</str>
      <str name="qf">name</str>
      <str name="pf2">name^30</str>
      <str name="defType">edismax</str>
      <str name="ps">0</str>
   </lst>
</lst>
<result name="response" numFound="5" start="0" maxScore="1.1705827">
   <doc>
      <float name="score">1.1705827</float>
      <str name="id">1</str>
      <str name="name">Java wzorce projektowe</str>
   </doc>
   <doc>
      <float name="score">0.3034844</float>
      <str name="id">2</str>
      <str name="name">Wzorce projektowe java</str>
   </doc>
   <doc>
      <float name="score">0.3034844</float>
      <str name="id">5</str>
      <str name="name">Projektowe java wzorce</str>
   </doc>
   <doc>
      <float name="score">0.014451639</float>
      <str name="id">3</str>
      <str name="name">Wzorce java projektowe</str>
   </doc>
   <doc>
      <float name="score">0.014451639</float>
      <str name="id">4</str>
      <str name="name">Projektowe wzorce java</str>
   </doc>
</result>
</response>

Jak widać pierwszy dokument nie zmienił swojej pozycji i jest to dalej dokument o identyfikatorze 1. Natomiast na drugim i trzecim miejscu znajdują się dokumenty, które mają jedną z wygenerowanych przez parser par słów. Co za tym idzie dokumenty o identyfikatorach 2 i 5 mają tą samą wartość współczynnika score. Listę wyników zamykają dokumenty posiadające jedynie termy wpisane przez użytkownika. Na uwagę zasługuje również fakt, iż tak samo jak w przypadku pierwszych dwóch przykładów, tak i eDisMax wyliczył inną wartość maksymalną współczynnika score dla wynikowego zbioru dokumentów – spowodowane jest to dokładnie tym samym co w poprzednim przykładzie, a mianowicie zapytaniem wygenerowanym przez parser i złożonym do Lucene.

Wydajność

W każdym wypadku należy wziąć pod uwagę, jaki poszczególne funkcjonalności będą miały wpływ na wydajność aplikacji opartej o Solr. W tym celu postanowiłem zrobić prosty test wydajnościowy. Założenia testu są dość proste – indeksuję dane z wikipedii, i dla każdej z metod tworze zapytanie dla fraz składających się z dwóch do sześciu tokenów. Zapytania zadaje przy wyłączonych cache`ach, za każdym razem restartując Solr. Wynik to średnia arytmetyczna z 10 powtórzeń każdego z testów. Przed wynikami testu, kilka słów o samym indeksie:

• Ilość dokumentów w indeksie: 1.177.239
• Ilość segmentów: 1
• Ilość termów:  18.506.646
• Ilość par term/dokument: 230.297.212
• Ilość tokenów: 418.135.268
• Wielkość indeksu: 4.6GB (zoptymalizowany)
• Wersja Lucene wykorzystana do zbudowania: 4.0-dev 964000

Frazy jakie wybierane były dla każdej iteracji testu:

• Iteracja I: „wielki piotr”
• Iteracja II: „druga wojna światowa”
• Iteracja III: „druga wojna światowa niemcy”
• Iteracja IV: „czas zmian reformacja w polsce”
• Iteracja V: „zmiana czasu letniego na czas zimowy”

Same wyniki przedstawiają się następująco:

Należy pamiętać, iż przedstawione wyniki dotyczą tylko i wyłącznie kwestii wydajnościowej i nie są sugestią której metody premiowania fraz należy używać. Wybór metody to kwestia wymagań i danego wdrożenia. Co do samych wyników, widać, iż zgodnie z przypuszczeniami najszybsza jest metoda druga, czyli wykorzystanie term proximity boost i parsera DisMax, który okazuje się szybszy zarówno od Standard Query Parsera, jak i od eDisMax`a.