2013年1月5日土曜日

Lucene/SolrにおけるDeep paging問題

以前から興味があった、LuceneとSolrでのDeep paging関連のチケットを整理してみました。
調べてみたら、分散検索(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 Sort

searchAfter()ではスコア以外のソート順がサポートされていなかった。
コンパレータを実装して、ソートの際にも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で以下のような問題を指摘している:
  1. Luceneが内部的に使用しているdocidを使っていること
  2. the optimization doesn't work if the docset is also requested (i.e. if facet=true) since it's only added in one place.
  3. maxScoreがNaNを返すことがある
  4. 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)
  5. when using pageDoc, any previous cached queries will be incorrectly used and hence incorrect results will be returned
  6. 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倍近く速くなったようだ。

2013年1月4日金曜日

アルゴリズムイントロダクション2章まとめ(1) 2.1まで


アルゴリズムイントロダクション第3版、2章のまとめです。
長くなりそうなので 2.1 までを先に記事にします。

自分が重要だと思った部分、興味のある部分に絞っていますが、省いた部分は教科書の該当ページを示しています。
基本的には教科書からの抜粋・引用が多いですが、理解した範囲で、自分の言葉を使って一部書き換えています。


2. さあ、始めよう

この章では、挿入ソートとマージソートを題材に、アルゴリズムの実行時間の解析方法を学ぶ。

具体的には、以下のテーマを扱う。
・ループ不変式を用いたアルゴリズムの正当性の証明
・疑似コードの定義
・RAM計算モデル
・入力サイズ
・マージソートを題材にした分割統治アルゴリズムの解析


2.1. 挿入ソート

この節では、ソーティング問題を解くアルゴリズムである挿入ソートを紹介する。
・ソーティング問題の定式化
・挿入ソートの疑似コード
・挿入ソートのループ不変式
・ループ不変式を用いた挿入ソートの正当性の証明
・疑似コードの定義

まず、ソーティング問題(sorting problem)を定式化する。

入力:n 個の数の列<a1, a2, ..., an>
出力:a1' <= a2' <= ... <= an' である入力列の置換 <a1', a2', ..., an'>

挿入ソートは、トランプで手札をソートする時のことを思い浮かべると理解しやすい(教科書p.14)。

挿入ソートに対する疑似コード INSERTION-SORT を示す。
INSERTION-SORT は、長さ n の配列 A[1..n] を引数として取る(疑似コード中では n を A.length で表現している)。
このアルゴリズムは、入力された数列を「その場でソート」する。すなわち、Aを記憶する以外に必要な記憶領域は、高々定数でしかない(必要な記憶領域が n に依存しない)。

INSERTION-SORT(A)
for j = 2 to A.length
    key = A[j]
    // A[j] をソート済みの列 A[1..j-1]に挿入する
    i = j - 1
    while i > 0 かつ A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key


ループ不変式と挿入ソートの正当性

今まさにソートしようとしている要素をキー(key)と呼ぶ。
配列のj番目にあるキーを挿入しようとしているとき、1番目からj-1番目までにあった A[1..j-1] はすでにソートされている。この性質をループ不変式(loop invariant)として定式化する。

挿入ソートのループ不変式:
第1~8行のfor文の各繰り返し開始されるときには、部分配列 A[1..j-1] には開始時点で A[1..j-1]に格納されていた要素がソートされた状態で格納されている。

アルゴリズムの正当性を容易に証明するためにループ不変式を利用する。
ループ不変式に対して3つの性質を示す必要がある:

初期条件:ループの実行開始直前ではループ不変式は真である
ループ内条件:ループの何回目かの繰り返しの直前でループ不変式が真ならば、次の繰り返しの直前でも真である。
終了条件:ループが停止したとき、アルゴリズムの正当性の証明に繋がる有力な性質が不変式から得られる。

最初の2つの性質が成立するならば、すべての繰り返しの直前でループ不変式は真である。
このやり方は、数学的帰納法と似ている。
ただし、3つ目の停止性を用いた証明方法が、普通の数学的帰納法との大きな相違点である。
多くの場合、ループ不変式を、ループを停止に導いた条件と一緒に用いる。

挿入ソートについてこれらの性質が成立しており、このアルゴリズムが正当であることを証明しよう。

初期条件:j=2のとき、部分配列は A[1] のみから構成され、これは元々 A[1] に格納されていた要素である。よって、明らかにソート済みであるから、最初の繰り返しの直前においてループ不変式は真である。

ループ内条件:for分の本体が行っているのは、A[j](キー)を入れるべき場所が見つかるまで、A[j-1], A[j-2], A[j-3],... を1つずつ右に移し(4~7行)、空いた場所にその値(キー)を挿入する(8行)ことである。これにより、部分配列 A[1..j] は元々 A[1..j] に格納されていた要素から構成されており、かつソート済みである。for分の次の繰り返し時にはjに1が加えられ、ループ不変式が維持される。
厳密には、while文(5~7行)に対するループ不変式を記述し、それが実際にループ不変式であることを証明する必要がある。ここでは形式的な取り扱いを追求せず、上記の簡単な解析を信頼し、ループ不変式が外側のループに対して成立していることが証明できたと考えることにする。

終了条件:for文が停止するのは条件 j > A.length = n を満たすときである。ループの各繰り返しでは、jを1だけ増加させるから、停止時に j = n + 1 が成立する。このとき、部分配列 A[1..n]には、開始時に A[1..n] に格納されていた要素が、ソートされて格納されている。部分配列 A[1..n] が入力された配列全体であることに注意すると、配列全体がソート済みであると結論できる。

以上より、アルゴリズムは正当である。


疑似コードに関する約束

教科書p.p.16-18を参照