WebエンジニアのLoL日記

LoLをプレイしたりLJLの試合を見たりするのが好きなエンジニア。LoLのイベントやパッチノートなど気になった点を記事にしたり、LJLについの記事をかいたりしています。某社でWeb系のエンジニアとして働いているので、技術系の記事もたまに書きます。コンタクトを取りたい場合はtwitterまで。

「検索」って簡単そうだけど中身はすごく複雑なんだよっていう話

もくじ

f:id:yoshiki_utakata:20180426235544j:plain

ある日

こんなことを言っている人がいました。

「検索なんてDBをselectした結果を表示するだけなのになんでこんなに不具合があったり反映が遅れたりするんだ」

もしこの方がエンジニアであったなら将来が心配なのでこの記事を書くことにしました。

はじめに

検索はみんな*1が思っている以上に大変です。

DBのselectで検索を書くとしたらどうなるのか

例えばtwitterのツイートを検索することを考えます。

DBのテーブル定義はこうなります。

tweet(id, user_id, text)

idはツイートのid, user_idはツイートした人のユーザーID, textがツイートの本文だとします。

ここで「プログラミング」を含むツイートを検索しようと思ったらこういったクエリになります。

select * from tweet where text like "%プログラミング%";

やっぱselectでできるじゃん

できるけどいろいろと問題点があります。その中でも一番大きいのが「結果が出てくるのがめっちゃ遅い」ということです。

そんなに遅くない気がするんだけど?

tweetの数が数万程度ならまだ耐えるかもしれません。ただ、10万とか100万とかになってくるとめちゃくちゃ遅くなるかと思います。*2 twitterのツイートは当然100万とか1000万とかそういう単位のものではないので、selectなんて使っていたら検索結果が返ってくるまえに地球は滅亡してしまいます。

じゃあどうするの?

転置インデックスという方法を使います。転置インデックスについての詳細は最後に紹介する本を参照してください。

簡単に説明すると、「プログラミング」という単語を含むツイートを予めリストアップしておくのです。検索キーワードで「プログラミング」ときたらそのリストを表示するだけでいい、というわけです。

「インデックス」とは「目次」のことです。まさに目次というわけです。

しかし目次を作るのも大変

しかし目次を作るのは大変です。検索の時どういうキーワードで検索されるかは使っている人によりますので、かなりの数の目次を用意しておく必要があります。

具体例

例えばこういったツイートをしたとします。

プログラミングを勉強中!

このツイートがされた時に、「プログラミング」「勉強」「勉強中」といった目次に、このツイートを追加します。そして、ユーザーが「勉強」で検索したらこのツイートが出てくるというわけです。

なんか思ったより簡単そう

ですがそうでもありません。この例だと追加する目次は3つでしたが、実際にはもっと大量に目次に追加されます。すると、目次に追加されるのに時間がかかってしまい、検索結果にツイートが出るまで少し時間がかかる時があります。「投稿した直後は検索結果に出てこない!」というのはこういう所からきているわけです。

他にも問題が

他にも、「ツイートを消した時は目次から消してまらわないといけない」という点もあります。検索結果として出てきたけど実際に開いたらツイートが消えていた、みたいなことは、この「目次から消す」という作業がまだ終わっていないから起こるわけです。

おわかりいただけましたか?

さて、検索がそんなに簡単ではないということがおわかりいただけたでしょうか。

何故検索は簡単だと思われてしまうのか

Google検索をいつも使っていてめっちゃ簡単に検索できているかのように見えるからだと思います。しかし、実際Google検索の裏側は凄い事になっていると思います。検索1回でサーバー数百台とか数千台とかが動いているのかもしれません。とにかく考えられない規模のサーバーが裏にあるのだと思います。

もっと知りたい場合

「大規模サービス技術入門」という本が参考になります。普段「プログラムのパフォーマンス」「プログラムの実行時間」などを意識してプログラムを書いていない人は一度読んでみると良いと思います。検索のインデックスの話もありますし、大規模サービスになって大規模なデータを処理するようになると、どういう所がネックになってくるかということが分かります。

*1:プログラムを書かない人たち

*2:ちゃんと計算していないのでもしかしたらもっとデータ多くても大丈夫かもしれません