調べてみたら、分散検索(Distributed Searchの機能)ではおろか、単体のSolrでもちゃんとサポートされてなかったっていう。
Deep paging問題とは
Deep paging問題の概要については、以下のブログエントリが参考になる。Deep paging problem | Solr Enterprise Search
例えば、以下のようなSolrクエリを想像してみよう。
q=*:*&sort=price+asc&rows=100&start=50000
このクエリは、Luceneインデックスに対して50,001件目から50,100件目までの100件の結果を取得しようとしている。
しかし、SolrはLuceneインデックスから50,100件のドキュメントを読み込んで最後の100件を返すという動作をする。
このやり方は（予想される通り）非常に効率が悪く、Deep pagingなクエリに対して応答時間は以下のようになる：
| Query | Average response time (ms) |
| q=*:*&sort=price+asc&rows=100&start=0 | 146 |
| q=*:*&sort=price+asc&rows=100&start=999900 | 3184 |
2つ目のクエリでは100万件のドキュメントをインデックスから読み込むことになる。
Googleではこの問題に対して、91ページ目（このページによると75ページ目）以降は見せないというアプローチを取っている。
もちろん問題は解決しておらず回避しているだけだが、Web検索というシチュエーションでは問題になる場面は少ないのかもしれない。
フィルタによるDeep paging問題の解決方法
このエントリでは、フィルタによる解決方法を示している。検索結果の対象となる文書群をあらかじめファセットで絞り込んでおくことで、Deep pagingの影響を抑え込むというアプローチ。
ただし、この方法には問題もある。
理想的には、フィルタをかけた後の文書数が、rowsで指定した数（上の例では100件）になっているのが望ましい。
しかし実際には、クエリを実行するまで検索結果の件数は分からない。
この問題を解決するために、2つのクエリを使う。
1つ目のクエリは、rows=0そしてstart=0を指定する。このクエリの結果でヒットした件数がわかる。
2つ目のクエリで、「自分で」ページングを行う。startパラメータは、前もって計算しておく必要がある。
（おそらく実際には、startパラメータを計算するため、例えばクエリq=*:*&rows=0&fq=price:[0+TO+9000]のヒット数が必要になる）
この方法でテストしてみると、応答時間は以下のようになる：
| Query | Average response time (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 |
LuceneにおけるDeep Paging問題の解決方法
IndexSearcher.searchAfter()メソッドが実装される
[#LUCENE-2215] paging collectorこのチケットでLuceneにIndexSearcher.searchAfter()メソッドがサポートされた。
（正確には、[#LUCENE-2127] Improved large result handlingでAaronさんによってこのアイデアが提唱された）
Lucene 3.5.0でFixされている。
CHANGES.txtには以下のように書かれている：
* LUCENE-2215: Added IndexSearcher.searchAfter which returns results after a specified ScoreDoc (e.g. last document on the previous page) to support deep paging use cases. (Aaron McCurry, Grant Ingersoll, Robert Muir)
詳細は、このパッチを書いたAaron McCurryさんのブログポストを参照：
http://www.nearinfinity.com/blogs/aaron_mccurry/making_lucene_hit_results_pagi.html
Paging Hit Collector (TopDocsCollector)というのを作ったらしい。ユーザが検索した結果の次のページをメモリ上のPriorityQueueにキャッシュしておいて、実際に次のページが要求されたらそれを渡す仕組みっぽい（違ってたらごめんなさい）。
IndexSearcher.searchAfter()メソッドでscore以外のソート順のサポート
[#LUCENE-3514] deep paging with SortsearchAfter()ではスコア以外のソート順がサポートされていなかった。
コンパレータを実装して、ソートの際にもdeep pagingが可能になった。
Lucene 4.0.0-ALPHA
* LUCENE-3514: Added IndexSearcher.searchAfter when Sort is used, returning results after a specified FieldDoc for deep paging. (Mike McCandless)
* LUCENE-3514: IndexSearcher.setDefaultFieldSortScoring was removed and replaced with per-search control via new expert search methods that take two booleans indicating whether hit scores and max score should be computed. (Mike McCandless)
ただし、function queryを使ったソーティングでsearchAfter()がうまく働かないバグがあり、LUCENE-4504で解決されている。Lucene 4.1.0でFixしたようだ。
[#LUCENE-4504] Empty results from IndexSearcher.searchAfter() when sorting by FunctionValues
* LUCENE-4504: Fix broken sort comparator in ValueSource.getSortField, used when sorting by a function query. (Tom Shally via Robert Muir)
SolrでのDeep Paging問題の取り扱い
CommonQueryParameters - Solr Wiki[#SOLR-1726] Deep Paging and Large Results Improvements
Grantさんは、LuceneのIndexSearcher.searchAfter()メソッドを使った解決をしようとパッチ SOLR-1726.patch を書き、Trunkにコミットされた。
https://issues.apache.org/jira/secure/attachment/12512422/SOLR-1726.patch
しかし、YonikさんがSOLR-1726で以下のような問題を指摘している：
- Luceneが内部的に使用しているdocidを使っていること
- the optimization doesn't work if the docset is also requested (i.e. if facet=true) since it's only added in one place.
- maxScoreがNaNを返すことがある
- when using pageDoc, the results get incorrectly cached as a non-paged query (and hence other requests that use the same query will be incorrect)
- when using pageDoc, any previous cached queries will be incorrectly used and hence incorrect results will be returned
- NullPointerExceptionが簡単に起こりうる
以上より、deep-pagedでない場合の検索結果にも悪影響を及ぼす可能性があるため、Yonikさんがこのパッチの機能をTrunkのコードで利用できないように修正した。
例えば、Solrへのリクエストをパースするクラス、org.apache.solr.search.QParserでは、pagingパラメータをパースするためにgetPaging()メソッドが上記パッチ SOLR-1726.patch で追加されているが、Trunkのコードでは以下のようにコメントアウトされている。
/**
* use common params to look up pageScore and pageDoc in global params
* @return the ScoreDoc
*/
public ScoreDoc getPaging() throws SyntaxError
{
return null;
/*** This is not ready for prime-time... see SOLR-1726
String pageScoreS = null;
String pageDocS = null;
pageScoreS = params.get(CommonParams.PAGESCORE);
pageDocS = params.get(CommonParams.PAGEDOC);
if (pageScoreS == null || pageDocS == null)
return null;
int pageDoc = pageDocS != null ? Integer.parseInt(pageDocS) : -1;
float pageScore = pageScoreS != null ? new Float(pageScoreS) : -1;
if(pageDoc != -1 && pageScore != -1){
return new ScoreDoc(pageDoc, pageScore);
}
else {
return null;
}
***/
}
CHANGES.txtからもSOLR-1726に関する以下の記述は削除された：
* SOLR-1726: Added deep paging support to search (sort by score only) which should use less memory when paging deeply into results by keeping the priority queue small. (Manojkumar Rangasamy Kannadasan, gsingers)
結局、このチケットのステータスは Reopend になったまま。
誰かこの記事を見た優秀な方、解決してください;)
関係あるかどうか分からないけど。。
[#SOLR-2092] Use a native priority queue to order facet results
facet.limit（facet.offsetの間違い？）が大きいとき、ordからtermを引くのにコストがかかっているという予想。
このパッチでは、ファセットをBoundedTreeSetから優先度付きキュー(新たに追加されたorg.apache.solr.util.LongPriorityQueueクラス)で管理するように変更したようだ。使用メモリも少なくてすむとのこと。
Yonikさんが実験したところ、facet.offsetが10万の場合、10倍近く速くなったようだ。
0 件のコメント:
コメントを投稿