Misskey: ユーザー名の全てのprefixを予め生成し検索スピードを向上させる

[syuilo]

例えば sy とクエリを送信したら syuilo というユーザー名のユーザーを取得するのに、現在は正規表現クエリを使っているが、それだとインデックスを活用できないので非常にパフォーマンスが悪い

このような解決策があるらしい

One solution is to precompute all (upper cased) suffixes and store them for efficient left anchored regular expression searches.

https://web.archive.org/web/20170609122132/http://jam.sg/blog/efficient-partial-keyword-searches/

要するに予めドキュメントに s sy syu syui syuil syuilo というユーザー名を分割した文字列を保存しておき、それにインデックスを張って正規表現を使わずにクエリするというもの。
確かにパフォーマンス問題は解決しそうだけど何かスマートな感じはしない...
(ただ現在も大文字小文字区別しない検索のために予めドキュメントに小文字化した文字列を保存しておくという似たようなアプローチを行っているので今更どうでもいいか)

ちなみにMongoDBのテキスト検索機能は文章などを検索することを想定していてこのようなケースでは使うことができない(syとクエリしてもsyuiloはヒットしない)

参考: https://stackoverflow.com/questions/44833817/mongodb-full-and-partial-text-search

[AyaMorisawa]

急ぎでなければ、少し考察時間が欲しいです。

[AyaMorisawa]

現行(2018/11/29)のmisskey.xyzのデータを使って、mongoシェルを叩いた結果です。

usersコレクションのドキュメント数

クエリ: db.users.aggregate([{$group:{_id:null,count:{$sum:1}}}])

結果: 56355

usernameLowerの文字列長の総和

クエリ: db.users.aggregate([{$project:{length:{$strLenCP:"$usernameLower"}}},{$group:{_id:null,total:{$sum:"$length"}}}])

結果: 466781

検索クエリの実行時間(インデックスあり)

3種類のクエリ

1. db.users.find({usernameLower:/^s/})
2. db.users.find({usernameLower:/^sy/})
3. db.users.find({usernameLower:/^syu/})

を試すと、

|クエリ|実行時間(ms)|
|-|-|
|1.|41|
|2.|1|
|3.|0|

検索クエリの実行時間(インデックスなし)

3種類のクエリ

1. db.users.find({usernameLower:/^s/})
2. db.users.find({usernameLower:/^sy/})
3. db.users.find({usernameLower:/^syu/})

を試すと、

|クエリ|実行時間(ms)|
|-|-|
|1.|56|
|2.|55|
|3.|62|

[AyaMorisawa]

usernameLowerの文字列長の平均

466781 / 56355 = 8.28

[AyaMorisawa]

これ、ユーザー名サジェストに時間がかかるのは、ユーザー名検索とは別の理由っぽい感じがあります。