2017-10-24

Elasticsearchでtoo_many_clauseに遭遇した時のメモ

Elasticsearchで特定の条件で検索を行うときに too_many_clause に遭遇したときに調べた時のメモ。

indexの定義とデータは以下の感じとする

$ curl "localhost:9200/tests?pretty"
{
  "tests" : {
    "aliases" : { },
    "mappings" : {
      "test" : {
        "properties" : {
          "title" : {
            "type" : "text"
          }
        }
      }
    },
    "settings" : {
      "index" : {
        "number_of_shards" : "5",
        "provided_name" : "tests",
        "creation_date" : "1508801834006",
        "analysis" : {
          "filter" : {
            "ngram" : {
              "type" : "nGram",
              "min_gram" : "3",
              "max_gram" : "25"
            }
          },
          "analyzer" : {
            "default" : {
              "filter" : [
                "ngram"
              ],
              "type" : "custom",
              "tokenizer" : "keyword"
            }
          }
        },
        "number_of_replicas" : "1",
        "uuid" : "Fsi43Wx2S8uyyf8wtn59Xg",
        "version" : {
          "created" : "5060199"
        }
      }
    }
  }
}

$ curl "localhost:9200/tests/_search?pretty"
{
  "took" : 1,
  "timed_out" : false,
  "_shards" : {
    "total" : 5,
    "successful" : 5,
    "skipped" : 0,
    "failed" : 0
  },
  "hits" : {
    "total" : 3,
    "max_score" : 1.0,
    "hits" : [
      {
        "_index" : "tests",
        "_type" : "test",
        "_id" : "2",
        "_score" : 1.0,
        "_source" : {
          "title" : "fugafuga"
        }
      },
      {
        "_index" : "tests",
        "_type" : "test",
        "_id" : "1",
        "_score" : 1.0,
        "_source" : {
          "title" : "hogehoge"
        }
      },
      {
        "_index" : "tests",
        "_type" : "test",
        "_id" : "3",
        "_score" : 1.0,
        "_source" : {
          "title" : "foobar"
        }
      }
    ]
  }
}

curl だけで色々やるの面倒臭いので Elasticsearchのclientとして elasticsearch-ruby を使う。

まず、上記のindexの定義で普通に検索できることを確認

[29] pry(main)> client.search index: "tests",
[29] pry(main)* body: {
[29] pry(main)*   query: {
[29] pry(main)*     match: { title: "hoge" }
[29] pry(main)*   }
[29] pry(main)* }
=> {"took"=>2,
 "timed_out"=>false,
 "_shards"=>{"total"=>5, "successful"=>5, "skipped"=>0, "failed"=>0},
 "hits"=>{"total"=>1, "max_score"=>0.59868973, "hits"=>[{"_index"=>"tests", "_type"=>"test", "_id"=>"1", "_score"=>0.59868973, "_source"=>{"title"=>"hogehoge"}}]}}

ところが、極端に長い文字列で検索をかけると too_many_clause エラーが発生する

[30] pry(main)> client.search index: "tests",
[30] pry(main)* body: {
[30] pry(main)*   query: {
[30] pry(main)*     match: { title: "hoge" * 20 }
[30] pry(main)*   }
[30] pry(main)* }
Elasticsearch::Transport::Transport::Errors::BadRequest: [400] {"error":{"root_cause":[{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests"}],"type":"search_phase_execution_exception","reason":"all shards failed","phase":"query","grouped":true,"failed_shards":[{"shard":0,"index":"tests","node":"8ggISAxpTti1T1y_YxqBIQ","reason":{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"hogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehogehoge\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests","caused_by":{"type":"too_many_clauses","reason":"maxClauseCount is set to 1024"}}}]},"status":400}
from /Users/syuta.ogido/works/minne/minne-app/vendor/bundle/ruby/2.4.0/gems/elasticsearch-transport-5.0.4/lib/elasticsearch/transport/transport/base.rb:202:in `__raise_transport_error'

まずはエラーメッセージがどういう意味なのか調べる

Elasticsearch の基盤である lucene のページでエラーメッセージの意味を見つけた https://lucene.apache.org/core/6_0_0/core/org/apache/lucene/search/BooleanQuery.TooManyClauses.html

Thrown when an attempt is made to add more than BooleanQuery.getMaxClauseCount() clauses. This typically happens if a PrefixQuery, FuzzyQuery, WildcardQuery, or TermRangeQuery is expanded to many terms during search.

BooleanQuery.getMaxClauseCount() 以上のboolean query を組み立てたときに投げられる例外らしい。

今回、自分で組み立てたqueryには明示的にboolean queryを使ってないので、match query で内部的にboolean query が生成されているのだろう。エラーメッセージにmaxClauseCount is set to 1024 と書かれているのでmatch query が内部的に組み立てたboolean query が1024 個を超えたっぽい。

次にmatch queryがどんな動作をするのか調べる。 match queryの説明を読んでみると以下のことがか書かれている。 https://www.elastic.co/guide/en/elasticsearch/reference/current/query-dsl-match-query.html#query-dsl-match-query-boolean

The match query is of type boolean. It means that the text provided is analyzed and the analysis process constructs a boolean query from the provided text

match query は検索ワードをアナライザにかけて、その結果を元にboolean query を組み立ててるよという感じ。

token filterに nGram を設定しているのでそれで、検索ワードが大量に分割されていそう。どのくらいのワードに分割されているのか調べてみる

[37] pry(main)> client.indices.analyze(index: 'tests', text: "hoge" * 20)["tokens"].count
=> 1541

エラーになった時の検索ワードだと1541ワードに分割されている

じゃあ、どのくらいの長さの検索ワードなら大丈夫なの？というのを調べる

[56] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 100)["tokens"].count
=> 2001
[57] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 900)["tokens"].count
=> 20401
[58] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 100)["tokens"].count
=> 2001
[59] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 90)["tokens"].count
=> 1771
[60] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 80)["tokens"].count
=> 1541
[61] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 70)["tokens"].count
=> 1311
[62] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 60)["tokens"].count
=> 1081
[63] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 59)["tokens"].count
=> 1058
[64] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 58)["tokens"].count
=> 1035
[65] pry(main)> client.indices.analyze(index: 'tests', text: "h" * 57)["tokens"].count
=> 1012

予想が正しければ、57 文字まで大丈夫で58文字からエラーになるはずなので試してみる

[67] pry(main)> client.search index: "tests",
[67] pry(main)* body: {
[67] pry(main)*   query: {
[67] pry(main)*     match: { title: "a" * 57 }
[67] pry(main)*   }
[67] pry(main)* }
=> {"took"=>55, "timed_out"=>false, "_shards"=>{"total"=>5, "successful"=>5, "skipped"=>0, "failed"=>0}, "hits"=>{"total"=>0, "max_score"=>nil, "hits"=>[]}}
[68] pry(main)> client.search index: "tests",
[68] pry(main)* body: {
[68] pry(main)*   query: {
[68] pry(main)*     match: { title: "a" * 58 }
[68] pry(main)*   }
[68] pry(main)* }
Elasticsearch::Transport::Transport::Errors::BadRequest: [400] {"error":{"root_cause":[{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests"}],"type":"search_phase_execution_exception","reason":"all shards failed","phase":"query","grouped":true,"failed_shards":[{"shard":0,"index":"tests","node":"8ggISAxpTti1T1y_YxqBIQ","reason":{"type":"query_shard_exception","reason":"failed to create query: {\n  \"match\" : {\n    \"title\" : {\n      \"query\" : \"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa\",\n      \"operator\" : \"OR\",\n      \"prefix_length\" : 0,\n      \"max_expansions\" : 50,\n      \"fuzzy_transpositions\" : true,\n      \"lenient\" : false,\n      \"zero_terms_query\" : \"NONE\",\n      \"boost\" : 1.0\n    }\n  }\n}","index_uuid":"Fsi43Wx2S8uyyf8wtn59Xg","index":"tests","caused_by":{"type":"too_many_clauses","reason":"maxClauseCount is set to 1024"}}}]},"status":400}
from /Users/syuta.ogido/works/minne/minne-app/vendor/bundle/ruby/2.4.0/gems/elasticsearch-transport-5.0.4/lib/elasticsearch/transport/transport/base.rb:202:in `__raise_transport_error'

57文字のやつはエラーにならず58文字のやつは too_many_clauses になった。今回は nGramでanalyzeしていて、min_gram が 3 max_gram が25 だから、57文字まで大丈夫だけど、許容できる文字数はanalyzerの設定によって変わってくる。

analyzerの設定とqueryによってはこの辺も気をつけないといけなさそう。

2017-10-21

searchkickのコードリーディング

ruby

普段、ElasticsearchとDBの関連付け兼Elasticsearchのクライアントとして searchkickをよく使っている。

searchkickは便利で、

Model.search('term', options).results

のようにメソッドを呼ぶだけで、Elasticsearchに検索をかけて、取得したドキュメントの_idフィールドを元にDBに検索をかける。その結果をModel オブジェクトの配列として受け取ることができる。

searchkickはoptionに並び並び順を指定することができる。例えば

Model.search('term', order: { hoge: :desc }).results

といった感じに指定すれば、最終的に得られるModelオブジェクトの配列は hoge の降順に整列されている。

そこで少し疑問に思ったことがあった。searchkickが発行するsqlにはorder byなどは指定されていなかった。

Elasticsearchに検索でパフォーマンスを出すために非正規化されたデータが入っているので order by column はできないにせよ、 order by field(id, ids)のようなsqlが発行されるのだろうと思っていた。

少し気になったのでどうやってソートしているのかsearchkickのコードを読んでみた。

searchkickがelasticsearchへの検索結果を元にDBにクエリを投げるのは resultsメソッドなのでそのあたり読んだ。 resultsメソッドが定義されているのはこの辺。

まず

hits.group_by { |hit, _| hit["_type"] }.each do |type, grouped_hits|
  results[type] = results_query(type.camelize.constantize, grouped_hits).to_a.index_by { |r| r.id.to_s }
end

でDBに問い合わせを行い、その結果をresults変数に以下のような形式で格納している

{
  type: {
    id1: model_object1,
    id2: model_object2
  }
}

(id*は対になっているmodel_objectが保持しているrecordのidです。)

ここではまだソートは行っていない。コードを追っていくとModel.where(id: ids) を呼んでいるだけだ。

その下の方にご丁寧に sortとと書かれたコメントとともに以下のような処理が書かれている

hits.map do |hit|
  result = results[hit["_type"]][hit["_id"].to_s]
  if result && !(options[:load].is_a?(Hash) && options[:load][:dumpable])
    unless result.respond_to?(:search_hit)
      result.define_singleton_method(:search_hit) do
        hit
      end
     end

     if hit["highlight"] && !result.respond_to?(:search_highlights)
       highlights = Hash[hit["highlight"].map { |k, v| [(options[:json] ? k : k.sub(/\.#{@options[:match_suffix]}\z/, "")).to_sym, v.first] }]
         result.define_singleton_method(:search_highlights) do
           highlights
         end
     end
  end
  result
end.compact

なんか長々と書かれているが、大半はoptionによってmethodを定義するみたいなやつなので純粋にソートに関する部分を切り出したら以下のようになる

hits.map do |hit|
  results[hit["_type"]][hit["_id"].to_s]
end.compact

めちゃくちゃシンプルで、Elasticsearchへの検索の結果からどの順番でソートすれば良いかは分かっているので、DBへの問い合わせ結果をその順序で抜き出して配列にしているだけ。下手にorder by field(id, ids) みたいなクエリでもindexでソートを解決できずにfilesortが発生することもあるが、この方法だとO(n)のコストでソートできるので、不特定多数の人に使われるgemと考えると、DBでソートせずrubyでソートするのが正しいのだろうと思った。

また、order by field(id, ids) をしているクエリでfilesortが発生したらsearchkickのようにruby側でソートするのも手だと思った。 gem のコードたまにしか読まないけど、読むと毎回何かしらの学びがある。

2017-06-19

コンソールで動くインベーダーゲームっぽいやつ作った

プログラミング ruby

何か急にゲームっぽいものを作りた衝動にかられて、インベーダーゲームくらいならシュッと作れるかなと思ってインベーダーゲームっぽい何かを作ってみた。

本物のインベーダーゲームはやったことありません。

f:id:ogidow:20170619082203p:plain

工夫したところというか、この手のものを作る時には当たり前だけど、画面がチラつかないように毎回、画面を全体を再描画という方法ではなく動きがある部分だけを描画するようにしています。

作るかと思って3時間くらいで動くもの作れたので満足(バグだらけだけど)。

2017-02-20

微分について

機械学習確率統計

微分をご存知でしょうか？

関数 ${f(x)}$ に対する微分は次の式で定義できますね
${ \frac{df(x)}{dx} = \lim_{h \to 0}\frac{f(x+h)-f(x)}{h} }$

微分はでは関数 ${f(x)}$ の点 ${x}$ における接線の傾きを表します。
例えば、 ${f(x) = x^2}$ の関数を考えます。図で表すと以下のようになります。

f:id:ogidow:20170220084146p:plain

ここで ${x=4}$ の点に接線を引きます。
f:id:ogidow:20170220085549p:plain

この緑の線の傾きが微分によって求めることができます。

では、任意の ${x}$ の傾きを求めることができると何が嬉しいのでしょうか？

例えば、 ${f(x) = x^2}$ が体重とかコストとかを近似できると仮定します。体重もコスト小さいに越したことはないでしょう。
何らかのパラメータxが4の時、微分の値は ${\frac{df(x)}{dx} = 8 > 0}$ となりパラメータを小さくすれば、 ${f(x)}$ が最小になりそうだなと推測することができます。また、 ${f(x)}$ が最小の点で接線はx軸に水平になるので。 ${\frac{df(x)}{dx} = 0}$ となり、 ${f(x)}$ は(厳密には違いますが)最小だと推測することができます。

何となく微分ができれば関数の最小値を求めることができて便利そうだなということがわかりました。
でもなぜ、微分で接線の傾きを求めることができるのでしょうか。直線の式といえば ${y = ax + b}$ で表されます。
直線の傾きと呼ばれる部分は ${a}$ です。中学校などで ${(x1,y1),(x2, y2)}$ を通る直線の傾きは ${a = \frac{yの増加量}{xの増加量} = \frac{y2 - y1}{x2 - x1}}$ と習ったと思います。
しかし、部分ではある1点における傾きを求めるので上記の方法は使うことができません。

ではどうするのでしょうか。 ${f(x) = x^2}$ として、
${(x1,y1),(x2, y2)}$ ではなく ${(x,f(x)), (x + h, f(x + h)}$ と考えてみます。すると、2点を通る直線の傾きは ${a = \frac{f(x + h) - f(x)}{x + h - x} = \frac{f(x + h) - f(x)}{h}}$ と書けます。求めたいのは2点を通る直線の傾きではなく1点を通る直線の傾きです。 ${h}$ が限りなく0になれば2点ではなく1点を通る直線になりそうです。
${\lim_{h \to 0}\frac{f(x+h)-f(x)}{h}}$ としてhを限りなく0に近づけると、微分の定義戻りました。
微分によって、関数の最小値を求めることができると単回帰分析などでサンプルしたデータ群を元にデータを近似したモデルを作ることができるようになるのですがそれは別の記事で書きます。

2016-12-10

若手エンジニアLT大会で登壇した

登壇してからかなり時間が経ちましたが書きます。

11月22日にドリコムさん主催の若手エンジニアLT大会で登壇させていただきました。

きっかけ

社内で@june29さんから声をかけていただき、登壇経験もなかったのでチャンスだと思い若手エンジニアLT大会に参加することを決めました。

内容

僕は、学生時代にコードレビューという文化が存在しなかったので、社会人になって初めてコードレビューというものを行いました。コードレビューをやってもらったり、やったりした中で感じたことを発表しました。

感想

各社の若手の皆さんはどうやって会社に技術貢献してきたかや入社して何をやってきたかなどを発表していました。すべての発表においてレベルが高く、ポジティブな意味で自分ももっと頑張らないとなと思いました。

とても緊張しましたが参加してとてもよかったと思います。あと、ドリコムさんのオフィスがめちゃくちゃお洒落でした。

2016-09-21

お産ウィークがありました

お産ウィークとは

お産ウィークとはエンジニア、デザイナ研修の一環で、新卒エンジニアと新卒デザイナが、1週間でWebサービスを協働開発を行います。新卒エンジニアが5人、新卒デザイナが1人なのでエンジニア3人のチームとエンジニア2人、デザイナ1人の2チームに分かれて開発を行いました。

僕はエンジニア2人、デザイナ1人のチームになりした。

作ったもの

お産ウィークではチームにそれぞれテーマが与えられ、そのテーマに沿ったwebサービスを開発します。僕のチームは「旅行の思い出をもっと残せるサービス」というテーマが与えられました。

チームであれこれ話し合ったり、方向転換したりしながらなんとか動くサービスを作れました。(イケてない仕様だったりバグも多く見れらますが...)

反省

最初にサービスの方針を決める段階でチーム内だけで盛り上がってしまい、自分たちが考えたサービスを客観的に見ることができませんでした。その結果、お産ウィーク3日目で「あれ、このサービスを使いたい人っているのかな？」と疑問が出て、結局サービスの方針を練り直しますことになりました。サービスの方針を練り直すと今度はメインの機能を作り直すことになり時間に追われることになりました。

結果論かもしれませんが、サービスの方向性が決まった時点でチーム外の誰かにサービスの方向性についてレビューしてもらってたら後戻りすることもなくもう少し機能の部分を詰めたり、バグを潰したり出来なのかなと感じます。

最後に

とはいえ、サービスを動く状態にできたのは良かったです。また、同期のエンジニアやデザイナもすごい人ばかりだなと実感することができました。祝日を挟んで木曜日からモバイル研修が再開します。そちらも頑張っていきたいです！

2016-09-05

完全独習ベイズ統計学入門を読んだ

完全独習ベイズ統計学入門

作者: 小島寛之
出版社/メーカー: ダイヤモンド社
発売日: 2015/11/20
メディア: 単行本（ソフトカバー）
この商品を含むブログ (6件) を見る

この本のコンセプトは四則演算のみでベイズ推定を基本を理解するところにある。第1部は確率を長方形の面積に見立て、確率記号を一切使わずに設定した問題に対してベイズ推定を行っている。本当に簡単な四則演算のみでベイズの更新や事後確率の意味、逐次合理性、従来の統計学(ネイマン・ピアソン統計学)との違いなどが説明されている。

第2部では、より汎用的に推定を可能にするために確率分布を用いた推定方法が解説されている。まずは、ベータ分布と正規分布などのよく利用される確率分布の説明から始まり、問題に対して確率分布を選択するために「共役事前分布」の説明を行って最後に実際に確率分布を用いた推定を行う、という流れだった。さすがに、確率分布の導入あたりから四則演算のみでは説明が難しく、多くの結論を天下り的に与えている。しかし、冒頭で作者が

完璧に解説しようとすると大学レベルの微分・積分が必要になってしまいます。 ... そこで本書ではやむなく、これらの解説は簡易的に済ませることにしました。

や

完璧な理解を欲する人も、本書を読んでから専門書に挑戦したほうが得策だと思います。

と述べているように、この本の目的は厳密な理解ではなく、ベイズ統計学を勉強する足がかりとなることだと思う。そういう意味では、僕のような全くない人がベイズ統計学とは何なのかということを知るためには最適な本だと思う。

次はこの本の文献にもあった「入門ベイズ統計学」を読みたい。