2017年1月24日

コサイン類似度に基づくソート処理の実装方法とその性能比較

文書の類似度を計算する方法に「コサイン類似度」を用いる方法があります。

これは、出現する単語を出現回数などで数値化して、空間ベクトルに変換した上でベクトル同士の類似度を計算する、という手法です。
最近、このコサイン類似度を使って、似ているデータを検索するWebアプリを試しに作っていたのですが、ふと、

「このコサイン類似度を使ったソート処理をPostgreSQLでどのように実装するともっとも高速な実装になるのだろうか。また、現実的なパフォーマンスを考えた時にデータ量や次元のサイズはどこまで増やせるのだろうか」

ということが気になりました。

PostgreSQLは、その拡張性の高さがウリの一つですが、そのため「UDFを作る」ということを考えても、実装方法にもいろいろあります。

今回は、PostgreSQL内部でデータ処理を実装するに当たって、どのような実装方法があるのか、それぞれどのように性能が違うのか、そしてその時にデータサイズがどのように影響するのかを見てみます。

■前提条件


今回は以下の前提条件で実装と性能比較を行います。
  • ソート処理するデータはPostgreSQLに蓄積されているものを対象とする
  • 空間ベクトルを表すデータは、PostgreSQL の float8 の配列で1カラムに保持する
  • コサイン類似度による類似度を計算し、もっとも類似度の高いレコードをN件取得する