SolrとランキングとRankQuery

この記事は Solr Advent Calendar 2016 の 25日目です。
今回はSolrのRankQueryについてテキトーに話します。
(なお、この記事の時点でのSolrのバージョンは6.3.0です)

# Solrとランキング
Solrのランキングでは大きく分けて以下の3つのコンポーネントが関係します。

- `Query`/`Weight`/`Scorer`
    - 検索クエリから`QueryParser`を介して生成される部分
    - `Query`=>`Weight`=>`Scorer`の順番で生成
    - 先に行くほど担当範囲が狭くなり、`Scorer`では単一のセグメント (`LeafReaderContext`)
- `Similarity`/`SimWeight`/`SimScorer`
    - クエリとドキュメントの類似度の計算方法の定義
    - Solr6系だと[BM25](https://lucene.apache.org/core/6_3_0/core/org/apache/lucene/search/similarities/BM25Similarity.html)が、Solr5系以前だと[TFIDF](https://lucene.apache.org/core/6_3_0/core/org/apache/lucene/search/similarities/TFIDFSimilarity.html)がデフォルト
    - 3つは関係は`Query`/`Weight`/`Scorer`と同じ感じ
- `Collector`
    - 検索でヒットした文書セットから最終候補を選別する部分
    - 前述の`Scorer`でヒットした文書のスコア計算をしていき、そのスコアに応じて文書セットの優先度キューを更新
    - sort条件に依ってインスタンスが切り替わり、scoreのみのソートなら`TopScoreDocCollector`が、fieldも加味するソートなら`TopFieldCollector `が生成

ランキングは実際に文書に触る箇所で行われるため、上記だとセグメントレベルの粒度で動作する`Scorer`、`SimScorer`、`Collector`がランキングのコア部分になります。

![solr_ranking_components.png](https://qiita-image-store.s3.amazonaws.com/0/153717/5ec82f68-4d3d-9eac-7961-96b4e6de2318.png)

### ランキングの例: TopScoreDocCollector
単純な検索の場合、スコア計算の起点は`DefaultBulkScorer`になります。`DefaultBulkScorer`では以下のようにコンストラクタの中で`Scorer`から`DocIdSetIterator`と`TwoPhaseIterator`を取得します。

- [Weight.java#L154-L161](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/lucene/core/src/java/org/apache/lucene/search/Weight.java#L154-L161)

`DocIdSetIterator`と`TwoPhaseIterator`は実際にクエリとのマッチしたドキュメントを返すイテレータで、前者が単純なIDの走査に、後者がより複雑なマッチ条件の判定に対応しています (だったはず)。これらの実装は対応する`Scorer`によって違い、例えばフレーズ検索に対応する`ExactPhraseScorer`なら対象の単語列が隣接して出現するかの判定が実装されています。

`DefaultBulkScorer`ではこのイテレータを使ってヒットしたドキュメントを走査していき、得られたdocIDを`Collector`に引き渡していきます。

- [Weight.java#L217-L233](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/lucene/core/src/java/org/apache/lucene/search/Weight.java#L217-L233)

`TopScoreDocCollector` (正確には`SimpleTopScoreDocCollector`) の`collect`メソッドは以下のようになります。

- [TopScoreDocCollector.java#L63-L80](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/lucene/core/src/java/org/apache/lucene/search/TopScoreDocCollector.java#L63-L80)

処理中で参照されている`pq`が優先度キューのことで、`pqTop` (優先度キューの末尾) とスコア比較をして、スコアが高い場合はドキュメントを入れ替えて優先度キューを更新という流れを繰り返していきます。なお、このスコア計算の部分に前述の`SimScorer`が利用されるという感じです。


# RankQuery

先程までの話では、Solrのスコア計算は`Similarity`で最終的に行われるため、独自の`Similarity`を実装すればランキングの挙動を簡単に変更できることがわかります。一方で、この方式だと以下のような事ができない問題があります。

- `Similarity`のAPIに従った実装しか出来ないため、より複雑なこと (例えば実行時にfield値を参照するとか) がやりずらい
- `Collector`ではマッチした全ての文書に対してスコア計算を行うため、計算コストが大きい複雑なロジックを入れづらい

これらの問題を解決する仕組みとして、Solrでは`RankQuery`が用意されています。

### RankQueryの仕組み

`RankQuery`はざっくり言うと「元の検索クエリをラッピングして動作を変える」ことができる仕組みになります。前述の通り、検索クエリは`QueryParser`によって`Query`というクラスに変換しますが、`RankQuery`が指定されている場合、以下のように実際の検索コマンドを生成するときに`Query`が`RankQuery`でラッピングされます。

- [ResponseBuilder.java#L426-L446](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/handler/component/ResponseBuilder.java#L426-L446)

この結果、本来`Query`が呼ばれるはずだった処理が`RankQuery`に委譲され、`RankQuery`で好き勝手改変することができるようになります。例えば、`Query`から`Weight`を生成する箇所 (`createWeight`) も`RankQuery`を経由するため、独自のスコアリングロジックを実装した`Scorer`を生成する`Weight`に差し替えることができるわけです。

[`RankQuery`の実装](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/RankQuery.java)を見てみると、以下のように3つのAPIが定義されていることがわかります。

- `TopDocsCollector getTopDocsCollector(int len, QueryCommand cmd, IndexSearcher searcher)`
- `MergeStrategy getMergeStrategy()`
- `RankQuery wrap(Query mainQuery)`

このうち`wrap`は前述のラッピングのタイミングで呼び出されるものです。この中でランキングで重要なのは`getTopDocsCollector`です (`getMergeStratedy`は分散計算で検索結果をマージするときの挙動を変えるだった気がする)。`getTopDocsCollector`では独自の`Collector` (i.e., `TopDocsCollector`) を返すことができ、ランキング時のスコアリングの挙動を変更することが可能となります (具体的には[ここ](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/SolrIndexSearcher.java#L1707-L1710)で差し替わる)。

先程のランキングのところで`Collector`がスコアリングとドキュメントのランキングを行うと説明しましたが、実際に利用される`Collector`のベース実装である`TopDocsCollector`には`TopDocs topDocs(int start, int howMany)`という初めのランキング後の優先度キューから上位n件を取得するためのメソッドが存在します。`getTopDocsCollector`で独自の`Collector`を用意できるようになったお陰で、この`TopDocs`の処理を上書きできます。

ところで、なぜ`TopDocs`の変更がポイントとなるのでしょうか。`TopDocs`はモダンな検索エンジンで実装されている[two-phase ranking](http://olivier.chapelle.cc/pub/wsdm2010.pdf)を実現する上で、two-phase目の高精度高コストなリランキングに相当する箇所になります。`TopDocs`では事前に収集して足切りされたドキュメントセットがリランクの対象となるため、スコア計算する対象が絞り込まれ、より複雑な計算ロジックも適用できるようになるわけです。


### RankQueryの例: ReRankQuery

RankQueryの実際の例として[ReRankQuery](https://cwiki.apache.org/confluence/display/solr/Query+Re-Ranking)を見てみます。

ReRankQueryは以下のように使うプラグインの一つ (`ReRankQParserPlugin`) で、reRankQueryで指定されたクエリでドキュメントを再評価し、スコアに補正をかけるものになります。

```
q=greetings&rq={!rerank reRankQuery=$rqq reRankDocs=1000 reRankWeight=3}&rqq=(hi+hello+hey+hiya)
```

実際の実装は以下のようになっています (6.3.0から主要な処理が`AbstractReRankQuery`に集約されたみたい)。

- [ReRankQParserPlugin.java#L93-L133](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/ReRankQParserPlugin.java#L93-L133)
    - [AbstractReRankQuery.java](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/AbstractReRankQuery.java)

`ReRankQuery`では`TopDocsCollector`を`ReRankCollector`に差し替えることでリランキングを実現しています。`ReRankCollector`では元の`Collector` (`mainCollector`) をラッピングしていて、基本的なAPIは処理を`mainCollector`側に委譲しつつ、`topDocs`を書き換えるような実装となっています。

- [ReRankCollector.java](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/ReRankCollector.java)

`TopDocs`の実装において、リランクのコア処理は[この部分](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/ReRankCollector.java#L103-L104)になります。ここでは、初めのランキング後のドキュメントセットを以下の`ReRankQueryRescorer`に渡すことでリランキングを行っています。

- [ReRankQParserPlugin.java#L74-L91](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/solr/core/src/java/org/apache/solr/search/ReRankQParserPlugin.java#L74-L91)
    - [QueryRescorer.java](https://github.com/apache/lucene-solr/blob/releases/lucene-solr/6.3.0/lucene/core/src/java/org/apache/lucene/search/QueryRescorer.java)

リランキングのコア処理は親クラスの`QueryRescorer`側の`rescore`メソッドに実装されています。処理の流れをざっくりまとめると以下のようになります。

1. リランク対象のドキュメントをdocID順にソート (セグメント順にするため)
2. 検索時に指定されたreRankQuery対応する`Query`から`Weight`を生成
3. リランク対象のドキュメントに対して以下を繰り返し
    1. ドキュメントのdocIDに対応するセグメント (`LeafReaderContext`) を取得
    2. セグメントに対応するリランク用の`Scorer`を生成
    3. `Scorer`を用いてドキュメントのリランクスコアを計算
    4. 得られたスコアを元のスコアに検索時に指定されたreRankWeightで重み付けして加算
4. 最終的なスコア順にドキュメントセットを再ソートして結果を返却

`ReRankQuery`の処理の流れをざっくりまとめると以下のような感じになります。

![rerank_query.png](https://qiita-image-store.s3.amazonaws.com/0/153717/552ddd4c-0258-7126-3e92-3c2dad27c963.png)


### Bloombergのltr-plugin 

Solr6.4からBloombergのltr-pluginが取り込まれるそうです ([Solr6.4 Features](http://yonik.com/solr-6-4/))。ltr-pluginはLucene/Solr Revolution 2015でBloombergの技術者が発表していた機能のことで、詳細は[発表スライド](http://www.slideshare.net/lucidworks/learning-to-rank-in-solr-presented-by-michael-nilsson-diego-ceccarelli-bloomberg-lp)にまとめられています。

- [ltr-plugin](https://github.com/apache/lucene-solr/tree/jira/solr-8542-v2/solr/contrib/ltr) (マージされたらmaster側見てください)

ltr-pluginのltrは"Learning To Rank"の略で、機械学習を用いてドキュメントのスコアを計算するモデルを学習することを意味しています。ltr-pluginではこのような機械学習モデルを使うために、以下のような機能を提供しています。

1. モデルで利用する素性 (特徴、`Feature`) の展開
2. 線形モデルや回帰木モデルを用いたリランキング

ltr-pluginによって、前述の`ReRankQuery`に比べ、より複雑かつ高精度なモデルをリランキングに使うことが可能となるため、ランキングの精度向上が見込めるわけです。線形モデルや回帰木モデルの学習には、例えば[liblinear](https://www.csie.ntu.edu.tw/~cjlin/liblinear/)や[xgboost](https://xgboost.readthedocs.io/en/latest/)といった機械学習ライブラリが使えるかと思います (教師データは別途準備が必要ですが)。

ltr-pluginもここまで話してきた`RankQuery`を利用して実装されています。複雑なモデルを扱うために内部で利用されるスコア計算はかなり作り込まれた実装となっていますが、表面上の大雑把な流れは`ReRankQuery`と大きくは変わりません。


# まとめ
この記事ではSolrのランキングとそのカスタマイズで利用される`RankQuery`について紹介しました。

ランキングの精度は検索結果へのユーザの印象に直結するので、特にドキュメント数が多くて絞込が難しい環境では重要になるかと思います。今までのSolrは正直ランキング周りが貧弱な印象でしたが、Solr6.4からltr-pluginが導入されるとのことなので、ランキング問題が解消されてこのあたりの話題がコミュニティでも賑わってくるのかなぁ、と期待します。

一方で、「もっとヤングでナウい俺様ランキングをSolrで使いたい！」という稀有な人は`RankQuery`を使って機能を実装することになるかと思います。そんな時にこの記事の内容が少しは役に立てば幸いです。