自己紹介なんですけど、Twitterはこの猫のアイコンで、役に立つかもしれないこと、役に立たないことをつぶやいています。検索エンジニアとしては、5年というとちょっとサバを読みすぎているんですけど、たぶん6〜7年ぐらいSolrとElasticsearchのエンジニアをしております。Samuraiという思い切った名前のベンチャーに転職しています。やっていることは、パテントサーチ、つまり特許検索です。ニッチな業界になります。個人では、JanomeというPythonの形態素解析のライブラリを作っていたり、ちょっとニッチなんですけど、LuceneのGUIツールを作っていたりします。Authorというかたちでやらせていただきました。この本ですが、今日、最初の内田さんのセッションでお話があったような精度改善のお話とかも書かれています。9章については大谷さんからも「Elasticsearchのエンジニアにも読んでもらいたいぐらい、いい」と評価をいただいたので......。(会場拍手)ぜひ、検索の精度改善一般について、評価の話やA/Bテストの話が書かれているので、よければお手に取ってみてください。宣伝チックになってしまいました。私は今、特許検索をやっている会社にいまして、「AI搭載型の特許判定システム」と言っているんですけど、中身は検索と自然言語処理と、あとは一部、グラフ分析みたいな特許業務の支援をやっています。特許は、あんまりご存じない方が多いと思います。テラバイトクラスのインデックスとかテキストデータを扱っていて、かつ、それに対して20個ぐらい「OR」がつながった検索を投げるという、検索アンチパターンみたいなことをやっていて、とにかく重いんですね。toCの検索だと「100msぐらいで返ってこないとユーザーを待たせちゃう」「どんなに遅くても300ms」とか、そういうラインがあると思うんですけど、特許検索の世界は「1秒で返ってきたら速い」みたいな感じで、本当に大規模なインデックスに対して、ORをいっぱいかけるみたいなことをしています。今回話すこと今日、私がお話しするのは、そういうヘビーな検索をやっている方に朗報かもしれません。7.0がすぐ出てきます。processing」です。「検索クエリが速くなるよ」ということです。気まぐれで英語で作ってきちゃったんですけど、日本語で話します。今、私が言ったように、特許で遅い原因の1つが「ORクエリをいっぱい並べる」というものです。大規模なインデックスに対しての検索ということです。そこに対する改善になります。PhraseQueryやWildcardQueryなど、そのコンビネーションにも効いてくるんですけど、disjunctionに対して速くなる改善が入っています。その代わりにできなくなることもあって、正確なトータルヒット検索数が返ってこなくなります。これはもう、デフォルトで返ってこなくなっちゃっているので、正確な件数が必要なときは、たぶんオプションなど必要です。バージョンアップのときはお気をつけください。(スライドを指して)私が調べたもののロングバージョンを、今のところ5本ブログにしていて、あと1本追記するつもりです。今日は駆け足で説明して、よくわからなかったなという方は、こちらを見ていただければいいかなと思います。リファレンスがありまして、実際に開発者が書いたブログやヨーロッパのカンファレンスで話しているビデオなどがあります。(スライドを指して)一番下は、坪坂(正志)さんという日本の方が書かれたスライドですごくわかりやすいので、こちらも参照してください。どの程度早くなるのか?「どのぐらい速くなるのか?」が一番気になるところなんですけど、まずANDクエリですね。毎晩毎晩、Lucene/Solrのマスターブランチのベンチマークで「Wikipediaの英語のデータ全件をindexingして、検索パフォーマンスを取る」ということをやっていまして、その結果です。Second)ですね。QPSなので、上がったほうが性能がいいです。2018年8月7日に、急に2.3倍速くなっています。あと、ORクエリの例1も、2.5倍速くなっています。ORクエリの例2のほうは、高頻出のものと低頻出のものを混ぜたようなクエリなんですけど、これに関しては4.3倍速くなっています。これを見ていると、けっこう期待が持てるんじゃないかなと感じていただけるかなと思います。あとは、Termクエリですね。これは単体で使うことはないと思うんですけど、40倍速くなっている。桁がよくわからないことになっていますが、こんなに速くなっています。アルゴリズムアルゴリズムということで、「実際に、なんでこんなに速くなったの?」という話を深掘りしてみたいと思います。検索エンジンをやっている方は「転置インデックスというのがあって」というのはある程度ご存じかと思います。listと言われるものを本当に1個ずつなめるんですね。3はengineだけ持っています」というのがあって、これをIDの小さい順から1個1個全部なめるんです。listが枯渇するまで全部なめます。listの長いものが1個でもあった場合、ものすごく時間がかかるんですね。ORが遅いというのは、こういう理由があります。1995年に「MAXSCORE」という検索エンジン......検索のIR分野では有名な方が発表した古いアルゴリズムがあって、「ORを速くするぞ」というものになります。簡単なのでシンプルなんですけど、わかれば「なるほど」という感じで、1個ずつ追ってみたいと思います。listで一番高いスコアのものを記録しておくんですね。boundを持っていて、インデックスに入れておきます。「search」のほうは「6」なので「6」と入れておきます。9のところでスコア「8」が出てきます。boundを突き合わせるんですね。「8」は「5」より大きいし、「6」より大きいので、なにがわかるかというと、searchかengineか、どちらか1個しか含まないドキュメントは全部無視してOKと。9より上には来ようがないので、どちらかだけ持っているドキュメントはスコアを計算する必要がなく、全部まるっとスキップができるんです。すると、(スライドを指して)ここからここまでは「search」はなく、これしか持っていないから、まるっとスキップして、ここに来て初めて計算して、「7」となります。これは「8」より小さいので、入れ替わりは起こらずに次に行きます。次は「search」しか持っていないからスキップ、「engine」しか持っていないからスキップ......という感じで、かなりスコアの計算が節約できるのがMAXSCOREのベーシックな考え方になります。listをディスクI/O削減のために圧縮して持っていまして、ブロック化されているんですね。そこに対して対応しなければいけないので、スライドに記載のような複雑な実装が入っていたりします。ちなみに、Luceneのほうは、最初に「これ使おうぜ」と言った人が上げたパッチがこれでした。そこから7年かかって、やっと入ったということなんですけど、これはボツになってました。理由はチケットにいろいろ書かれていたんですけど、その時は「合わない」ということでボツになっています。WANDここからが、今回Luceneに入ったアルゴリズムの話になります。AND」の省略形になります。「ORとANDの間」みたいな意味になっています。ORクエリは、スコリングを考えた場合、ORでつないだ単語を含めば含むほど、スコアが高くなるんですね。5個の単語をORでつなげたとしたら、1個だけ持っているドキュメントより4個持っているドキュメントのほうが明らかにスコアが高い、というものです。いうニュアンスを表現しているのが、WANDになります。今、私が口頭でしゃべったことが一番下に書いてあります。しないと思うんですけど(笑)。Match」と言われれば「あっ」と思う方はいると思います。Matchは、SolrでもElasticsearchでももちろんあるので、よく使われている方がいると思います。「5個の単語をORでつなげるんだけど、3語以上は含んでいてほしい」とか「80パーセント以上は含んでいてほしい」とか、そういうものですね。これとすごくよく似ています。このアルゴリズムがLuceneに入れられるということで、今回、入ったという流れだったようです。WANDのアルゴリズムWANDのアルゴリズムなんですけど、けっこう頭を使うので、もし本当に興味があれば、論文なり、わかりやすいかわからないんですけど、私の記事なども追ってみてください。boundをあらかじめ計算しておきます。これはMAXSCOREの亜種なので、そこまでは同じです。ここから先が賢いんです。listを並び替えるんですね。listで、各pointerを持っているところで、ドキュメントIDが小さいもの順に並び替えています。10を返すのであれば、どこで10位と入れ替わるかというのが、ドキュメントを見る前に計算できます。いうことかというと、ある時点での転置インデックスの走査をしてる状態で、それぞれそのpointerが、「the」は27、「engine」は60、「search」は486、「lucene」は907を指しているとします。listを並び替えて、上からMAXSCOREを足し算していきます。すると、5+5+8で18になります。この時点で、やっと今考えているしきい値である12を超えます。ここからここまでは全部スキップしてOK。ここからここまでは「the」と「engine」しか含まないから、ここまでは見てもしょうがないということで、ここにカーソルを移します。カーソルを移したあと、はたしてこれとこれが存在するかを確認します。なかったら、超えようがないので、またスキップします。持っていたとしたら、12を超える可能性があるので、あるかないかを確認してスコアリングをして......ということをやっていきます。いう感じでスキップ、スキップを繰り返していくかたちになります。私は理解した時「あっ、なるほどね」と思いました。みなさんに「なるほどね」と思っていただけたかわからないんですけど、なかなか賢いスマートなやり方です。index版ということでお話ししたんですけど、Luceneはブロック化されたインデックスになっていまして、今の素のWANDでは対応できないんです。WAND」で、6年越しの悲願で、2018年ぐらいに入ったかたちになります。飛ばして、実装の話をしておきたいと思います。免責ですが、一応ソースは読んだんですけど、だいぶ低レベルで複雑なところの話になっているので、誤りがあるかもしれません。LuceneのAPIはだいぶサクサク変わっていくので「今時点の」ということで、ご了承ください。Luceneのスコアリングのアーキテクチャです。listを見ているクラスたちは、ScorerとCollectorとPostingsEnumというものになります。listをなめるiteratorです。Scorerが、ドキュメントのスコア計算をするものです。Collectorが、Top100件だったら100、1,000だったら1,000というのを、PriorityQueueを使って集めていきます。こんな感じで、概観してみるとシンプルな構成になっています。あと、BooleanQueryを例として出したんですけど、若干複雑です。Matchをネストしたりと、いくらでも複雑なクエリが書けてしまうんです。その中身は、AND用のScorerとかOR用のScorerとかNOT用のScorerと、Scorerがいくつかあります。MatchのScorerがそれぞれ別にあって、これがネストされた感じで、最終的なScorerになるかたちになっています。それ以外は、さっきのものと同じです。WANDが入った時に変わったのが、indexingのところです。boundを計算して保存しておくというところで、このあたりのクラスが変わったり、追加されたりしています。listのスキップするというものも大きく変わったというか、追加が入って、より効率的なスキップができるようになっています。listをなめるImpactsDISIという、よくわからない名前のクラスがあるんですけど、まさにこれがスキップを担当しているクラスで、スキップしながらenumerateしています。MaxScoreCacheというのが、MAXSCOREを計算して、しきい値を計算する、トラッキングするキャッシュ......キャッシュを兼ねた、Calculatorみたいなものです。検索クエリ中で、今までと何が変わったかというと、まず一番シンプルなTermQueryのところは、PostingsEnumのところで、さっき少し見ていただいたImpactsDISIを持つようになっています。ここで効率よくスキップして、non-competitiveなブロックをスキップしていく......iteratorが変わったということです。BooleanQueryのほうは、PostingsEnumのところで、ImpactsDISIを使ったのは同じなんです。1つ、ネストされている場合、サブクエリのスコアリングの合算が上位のクエリのスコアになるので、括弧の下のほうにある下位の検索式のしきい値をそれぞれトラッキングして、その合算を上位に伝播させる必要があります。このあたりはけっこう難しくて、特別なScorerが入っています。Matchとすごくよく似てるよね」ということで、実装が簡易だったということでした。Matchと似ているんです。計算式がちょっと違います。MAXSCOREを導入したきっかけこちらは、もしかしたらご存じの方がいらっしゃるかもしれないんですけど、私がメンテナンスしているLuceneのGUIツールです。過去のLukeをご存じの方はわかると思うんですけど、だいぶ古風な感じのGUIだったんです。最近、ちょっと新しめに、モダンな感じで作り変わっていますので、もしデバッグとかIntrospectingとかをやりたい場合は、こちらのほうもちょっと見てみてください。Lucene/Solr/Elasticsearchのインデックスは全部開けます。わからないけど、USとかEuropeとかChinaとか、海外だとすごい人気ですが、日本人で使っている人はほとんど見たことがないです。よかったら、使ってみてフィードバックをいただければと思います。ありがとうございました。(会場拍手)司会者:ありがとうございます。k-query」などは、今日は中の人がいるので......。質問者1:実装の話じゃなくて、コミュニティの話みたいになっちゃうんですけれども、どういう経緯でMAXSCOREを導入する、再度チャレンジする流れになったんでしょうか?打田:私も......このチケットは7年ぐらいかかっていて、コメントもめちゃくちゃついていて、追うのがちょっと大変だったんですけど、たぶんTF-IDFからBM25に変わったタイミングです。BM25は、saturateするじゃないですか。上限いっぱいいかないとなると、「正確なスコアじゃなくて、その上限いっぱいのところだけ持っていればいいよね」と。インデックスを作るたびにスコアの上限は変わっていくんですけど、「そこをBM25の最大にすればいいよね」ということに気づいたのが、ElasticsearchのAdrienさんでした。「これ、いける」と言って、今お話しした内容を彼が全部実装していたんです。質問者2:BM25が先に入ったからこそできた感じなんですね。私にはそのようにコメントは見えています。質問者1:ありがとうございます。k-queryの話」というSlideShareはすごくわかりやすいです。今日、懇談会で、そのスライドを書いた人もいるので、いろいろ話が聞けるでしょう。Talkに関する記事をまとめています。Talkに関する新着記事が公開された際に、通知を受け取ることができます。