Apache Lucene 8のTop-k クエリプロセッシング最適化

Lucene 8のTop-k クエリプロセッシング最適化

打田智子氏（以下、打田）：よろしくお願いします。イベントの最後でお疲れかもしれないんですけど、今日の発表はさらに疲れる話が出てきちゃうので、半分ぐらいの方は起きていてもらえるようにがんばりたいと思います。お付き合いください。

打田と申します。自己紹介なんですけど、Twitterはこの猫のアイコンで、役に立つかもしれないこと、役に立たないことをつぶやいています。検索エンジニアとしては、5年というとちょっとサバを読みすぎているんですけど、たぶん6〜7年ぐらいSolrとElasticsearchのエンジニアをしております。

最近転職をしまして、AI Samuraiという思い切った名前のベンチャーに転職しています。やっていることは、パテントサーチ、つまり特許検索です。ちょっとニッチな業界になります。

個人では、JanomeというPythonの形態素解析のライブラリを作っていたり、ちょっとニッチなんですけど、LuceneのGUIツールを作っていたりします。先ほど森山大朗さんからご紹介いただいた『Apache Solr入門』の3版のLead Authorというかたちでやらせていただきました。

この本ですが、今日、最初の内田さんのセッションでお話があったような精度改善のお話とかも書かれています。9章については大谷さんからも「Elasticsearchのエンジニアにも読んでもらいたいぐらい、いい」と評価をいただいたので……。

（会場拍手）

ぜひ、検索の精度改善一般について、評価の話やA／Bテストの話が書かれているので、よければお手に取ってみてください。ちょっと宣伝チックになってしまいました。

私は今、特許検索をやっている会社にいまして、「AI搭載型の特許判定システム」と言っているんですけど、中身は検索と自然言語処理と、あとは一部、グラフ分析みたいな特許業務の支援をやっています。

特許は、あんまりご存じない方が多いと思います。テラバイトクラスのインデックスとかテキストデータを扱っていて、かつ、それに対して20個ぐらい「OR」がつながった検索を投げるという、検索アンチパターンみたいなことをやっていて、とにかく重いんですね。

toCの検索だと「100msぐらいで返ってこないとユーザーを待たせちゃう」「どんなに遅くても300ms」とか、そういうラインがあると思うんですけど、特許検索の世界は「1秒で返ってきたら速い」みたいな感じで、本当に大規模なインデックスに対して、ORをいっぱいかけるみたいなことをしています。

今回話すこと

今日、私がお話しするのは、そういうヘビーな検索をやっている方に朗報かもしれません。

もうすぐLucene/Solr 8.0と、それに続いてElasticsearch 7.0がすぐ出てきます。そのときの一番の目玉と言われているのが、「Top-k query processing」です。つまり「検索クエリが速くなるよ」ということです。気まぐれで英語で作ってきちゃったんですけど、日本語で話します。すいません。

今、私が言ったように、特許で遅い原因の1つが「ORクエリをいっぱい並べる」というものです。かつ、大規模なインデックスに対しての検索ということです。そこに対する改善になります。

PhraseQueryやWildcardQueryなど、そのコンビネーションにも効いてくるんですけど、disjunctionに対して速くなる改善が入っています。

その代わりにできなくなることもあって、正確なトータルヒット検索数が返ってこなくなります。これはもう、デフォルトで返ってこなくなっちゃっているので、正確な件数が必要なときは、たぶんオプションなど必要です。バージョンアップのときはお気をつけください。

（スライドを指して）私が調べたもののロングバージョンを、今のところ5本ブログにしていて、あと1本追記するつもりです。今日は駆け足で説明して、よくわからなかったなという方は、こちらを見ていただければいいかなと思います。

また、リファレンスがありまして、実際に開発者が書いたブログやヨーロッパのカンファレンスで話しているビデオなどがあります。（スライドを指して）一番下は、坪坂（正志）さんという日本の方が書かれたスライドですごくわかりやすいので、こちらも参照してください。

どの程度早くなるのか？

「どのぐらい速くなるのか？」が一番気になるところなんですけど、まずANDクエリですね。毎晩毎晩、Lucene/Solrのマスターブランチのベンチマークで「Wikipediaの英語のデータ全件をindexingして、検索パフォーマンスを取る」ということをやっていまして、その結果です。

（スライドを指して）これがQPS（Query Per Second）ですね。QPSなので、上がったほうが性能がいいです。2018年8月7日に、急に2.3倍速くなっています。

あと、ORクエリの例1も、2.5倍速くなっています。

ORクエリの例2のほうは、高頻出のものと低頻出のものを混ぜたようなクエリなんですけど、これに関しては4.3倍速くなっています。これを見ていると、けっこう期待が持てるんじゃないかなと感じていただけるかなと思います。

あとは、Termクエリですね。これは単体で使うことはないと思うんですけど、40倍速くなっている。桁がよくわからないことになっていますが、こんなに速くなっています。

アルゴリズム

アルゴリズムということで、「実際に、なんでこんなに速くなったの？」という話を深掘りしてみたいと思います。

検索エンジンをやっている方は「転置インデックスというのがあって」というのはある程度ご存じかと思います。実際、ORクエリはどういうふうに転置インデックスを辿って結果を見つけてスコアリングしているかと言いますと、初期のナイーブな実装の検索エンジンは、posting listと言われるものを本当に1個ずつなめるんですね。

例えば「search OR engine」とすると、「engine」というposting listと「search」というposting listがあって、ドキュメントIDが下にあって……要は「ドキュメントID 1はsearchとengine両方持っています」「ドキュメントID 3はengineだけ持っています」というのがあって、これをIDの小さい順から1個1個全部なめるんです。

なので、「docid 1は両方持っているからスコア計算します」「docid 3は『engine』だけ持っているから、結果に加えます」ということをずっとやっていって、両方のposting listが枯渇するまで全部なめます。

想像したらわかると思うんですけど、posting listの長いものが1個でもあった場合、ものすごく時間がかかるんですね。ORが遅いというのは、こういう理由があります。

1995年に「MAXSCORE」という検索エンジン……検索のIR分野では有名な方が発表した古いアルゴリズムがあって、「ORを速くするぞ」というものになります。けっこう簡単なのでシンプルなんですけど、わかれば「なるほど」という感じで、1個ずつ追ってみたいと思います。

何をやっているかというと、インデックスを作るときに、各posting listで一番高いスコアのものを記録しておくんですね。例えば「engine」だと、この中で下線を引いてる「5」が一番スコアが高いので、upper boundを持っていて、インデックスに入れておきます。「search」のほうは「6」なので「6」と入れておきます。

これで、さっきのバカみたいな辿り方と同じように辿っていくんですけれども、例えば、検索結果として1位のものだけ返したいとなったときに、ドキュメントIDを辿っていくと、ドキュメントID 9のところでスコア「8」が出てきます。そうすると、それとupper boundを突き合わせるんですね。

「8」は「5」より大きいし、「6」より大きいので、なにがわかるかというと、searchかengineか、どちらか1個しか含まないドキュメントは全部無視してOKと。わかりますかね？　どちらかしか含まないものは、この1位のスコア「8」のdocid 9より上には来ようがないので、どちらかだけ持っているドキュメントはスコアを計算する必要がなく、全部まるっとスキップができるんです。

そうすると、（スライドを指して）ここからここまでは「search」はなく、これしか持っていないから、まるっとスキップして、ここに来て初めて計算して、「7」となります。これは「8」より小さいので、入れ替わりは起こらずに次に行きます。

次は「search」しか持っていないからスキップ、「engine」しか持っていないからスキップ……という感じで、かなりスコアの計算が節約できるのがMAXSCOREのベーシックな考え方になります。

ここは飛ばそうと思うんですけど、最近の検索エンジンはposting listをディスクI／O削減のために圧縮して持っていまして、ブロック化されているんですね。そこに対して対応しなければいけないので、スライドに記載のような複雑な実装が入っていたりします。

ちなみに、Luceneのほうは、最初に「これ使おうぜ」と言った人が上げたパッチがこれでした。2012年です。そこから7年かかって、やっと入ったということなんですけど、これはボツになってました。理由はチケットにいろいろ書かれていたんですけど、その時は「合わない」ということでボツになっています。

WAND

ここからが、今回Luceneに入ったアルゴリズムの話になります。「WAND」というんですけど、「Week AND」もしくは「Weighted AND」の省略形になります。「ORとANDの間」みたいな意味になっています。

ORクエリは、スコリングを考えた場合、ORでつないだ単語を含めば含むほど、スコアが高くなるんですね。なので、例えば5個の単語をORでつなげたとしたら、1個だけ持っているドキュメントより4個持っているドキュメントのほうが明らかにスコアが高い、というものです。そういうニュアンスを表現しているのが、WANDになります。

今、私が口頭でしゃべったことが一番下に書いてあります。

ちょっとどこかで聞いたことがある気がしませんか？　まぁ、しないと思うんですけど（笑）。

（会場笑）

「Minimum Should Match」と言われれば「あっ」と思う方はいると思います。Minimum Should Matchは、SolrでもElasticsearchでももちろんあるので、よく使われている方がいると思います。

「5個の単語をORでつなげるんだけど、3語以上は含んでいてほしい」とか「80パーセント以上は含んでいてほしい」とか、そういうものですね。これとすごくよく似ています。このアルゴリズムがLuceneに入れられるということで、今回、入ったという流れだったようです。

WANDのアルゴリズム

WANDのアルゴリズムなんですけど、けっこう頭を使うので、もし本当に興味があれば、論文なり、わかりやすいかわからないんですけど、私の記事なども追ってみてください。

軽く説明すると、例えば「the OR search OR engine OR lucene」というクエリがあって、4つのtermがつながったものを、MAXSCOREと同じように、それぞれupper boundをあらかじめ計算しておきます。これはMAXSCOREの亜種なので、そこまでは同じです。

ここから先が賢いんです。MAXSCOREの場合は「あるかないか」を見て飛ばしていくんですけど、WANDの場合、最初にposting listを並び替えるんですね。この各posting listで、各pointerを持っているところで、ドキュメントIDが小さいもの順に並び替えています。

何がうれしいかというと、例えばTop 10を返すのであれば、どこで10位と入れ替わるかというのが、ドキュメントを見る前に計算できます。

どういうことかというと、ある時点での転置インデックスの走査をしてる状態で、それぞれそのpointerが、「the」は27、「engine」は60、「search」は486、「lucene」は907を指しているとします。

この順番にposting listを並び替えて、上からMAXSCOREを足し算していきます。そうすると、5＋5＋8で18になります。この時点で、やっと今考えているしきい値である12を超えます。

なので、ここからここまでは全部スキップしてOK。ここからここまでは「the」と「engine」しか含まないから、ここまでは見てもしょうがないということで、ここにカーソルを移します。

カーソルを移したあと、はたしてこれとこれが存在するかを確認します。なかったら、超えようがないので、またスキップします。もし持っていたとしたら、12を超える可能性があるので、あるかないかを確認してスコアリングをして……ということをやっていきます。こういう感じでスキップ、スキップを繰り返していくかたちになります。

私は理解した時「あっ、なるほどね」と思いました。みなさんに「なるほどね」と思っていただけたかわからないんですけど、なかなか賢いスマートなやり方です。

BLOCK-MAX WAND

次ですね。

さっきMAXSCOREのblock index版ということでお話ししたんですけど、Luceneはブロック化されたインデックスになっていまして、今の素のWANDでは対応できないんです。入ったのは、こちらのWANDのブロック化インデックス版「BLOCK-MAX WAND」で、6年越しの悲願で、2018年ぐらいに入ったかたちになります。

ちょっと飛ばして、実装の話をしておきたいと思います。免責ですが、一応ソースは読んだんですけど、だいぶ低レベルで複雑なところの話になっているので、誤りがあるかもしれません。また、LuceneのAPIはだいぶサクサク変わっていくので「今時点の」ということで、ご了承ください。

Luceneのスコアリングのアーキテクチャです。低レベルなほうのスコアリングのアーキテクチャで、一番下のほうでposting listを見ているクラスたちは、ScorerとCollectorとPostingsEnumというものになります。

PostingsEnumというのが、posting listをなめるiteratorです。Scorerが、ドキュメントのスコア計算をするものです。Collectorが、Top100件だったら100、1,000だったら1,000というのを、PriorityQueueを使って集めていきます。こんな感じで、概観してみるとシンプルな構成になっています。

あと、BooleanQueryを例として出したんですけど、若干複雑です。というのも、ORをネストしたり、Minimum Should Matchをネストしたりと、いくらでも複雑なクエリが書けてしまうんです。

その中身は、AND用のScorerとかOR用のScorerとかNOT用のScorerと、Scorerがいくつかあります。ANDとORのミックスと、さっきちょっと触れましたがMinimum Should MatchのScorerがそれぞれ別にあって、これがネストされた感じで、最終的なScorerになるかたちになっています。それ以外は、さっきのものと同じです。ちょっとここも飛ばしますね。

BlOCK-MAX WANDで変わったこと

今回、全体的に変わっているんですけど、BlOCK-MAX WANDが入った時に変わったのが、indexingのところです。MAXSCOREというか、upper boundを計算して保存しておくというところで、このあたりのクラスが変わったり、追加されたりしています。

それから、もともとスキップする実装は入っていたんですけれども、posting listのスキップするというものも大きく変わったというか、追加が入って、より効率的なスキップができるようになっています。

posting listをなめるImpactsDISIという、よくわからない名前のクラスがあるんですけど、まさにこれがスキップを担当しているクラスで、スキップしながらenumerateしています。MaxScoreCacheというのが、MAXSCOREを計算して、しきい値を計算する、トラッキングするキャッシュ……キャッシュを兼ねた、Calculatorみたいなものです。

検索クエリ中で、今までと何が変わったかというと、まず一番シンプルなTermQueryのところは、PostingsEnumのところで、さっき少し見ていただいたImpactsDISIを持つようになっています。ここで効率よくスキップして、non-competitiveなブロックをスキップしていく……iteratorが変わったということです。

BooleanQueryのほうは、PostingsEnumのところで、ImpactsDISIを使ったのは同じなんです。ただ、もう1つ、ネストされている場合、サブクエリのスコアリングの合算が上位のクエリのスコアになるので、括弧の下のほうにある下位の検索式のしきい値をそれぞれトラッキングして、その合算を上位に伝播させる必要があります。このあたりはけっこう難しくて、特別なScorerが入っています。

なんでこれができたかというと、「Minimum Should Matchとすごくよく似てるよね」ということで、実装が簡易だったということでした。こんな感じで、すごくMinimum Should Matchと似ているんです。ただ、計算式がちょっと違います。

MAXSCOREを導入したきっかけ

こちらは、もしかしたらご存じの方がいらっしゃるかもしれないんですけど、私がメンテナンスしているLuceneのGUIツールです。

過去のLukeをご存じの方はわかると思うんですけど、だいぶ古風な感じのGUIだったんです。最近、ちょっと新しめに、モダンな感じで作り変わっていますので、もしデバッグとかIntrospectingとかをやりたい場合は、こちらのほうもちょっと見てみてください。Lucene/Solr/Elasticsearchのインデックスは全部開けます。

よくわからないけど、USとかEuropeとかChinaとか、海外だとすごい人気ですが、日本人で使っている人はほとんど見たことがないです。もしよかったら、使ってみてフィードバックをいただければと思います。

以上です。ありがとうございました。

（会場拍手）

司会者：ありがとうございます。なにか質問ありますか？　さっき話してた「転置インデックスとTop k-query」などは、今日は中の人がいるので……。あっ、質問ですね。

質問者1：実装の話じゃなくて、コミュニティの話みたいになっちゃうんですけれども、どういう経緯でMAXSCOREを導入する、再度チャレンジする流れになったんでしょうか？

打田：私も……このチケットは7年ぐらいかかっていて、コメントもめちゃくちゃついていて、追うのがちょっと大変だったんですけど、たぶんTF-IDFからBM25に変わったタイミングです。

BM25は、saturateするじゃないですか。上限いっぱいいかないとなると、「正確なスコアじゃなくて、その上限いっぱいのところだけ持っていればいいよね」と。インデックスを作るたびにスコアの上限は変わっていくんですけど、「そこをBM25の最大にすればいいよね」ということに気づいたのが、ElasticsearchのAdrienさんでした。「これ、いける」と言って、今お話しした内容を彼が全部実装していたんです。確か、それだと思います。

質問者2：BM25が先に入ったからこそできた感じなんですね。

打田：はい。私にはそのようにコメントは見えています。

質問者1：ありがとうございます。

司会者：ほかにありますでしょうか？　ちょっと話の途中だったんですけど、さっき言っていた「転置インデックスTop k-queryの話」というSlideShareはすごくわかりやすいです。今日、懇談会で、そのスライドを書いた人もいるので、いろいろ話が聞けるでしょう。