MySQLでの128次元ベクトルの距離計算高速化

質問

MySQLで128次元ベクトルの距離計算をしたいと考えています。
※　距離と書いていますが、見つけたいのは最も近くにあるデータなので厳密な距離である必要はありません。

ただし、登録されているデータ量やクエリの工夫のなさにより速度が出ない（タイムアウトするレベル）状態です。
そこで、高速化する方法についてご享受ください。

【環境】
OS：CentOS
mysql：mysql Ver 14.14 Distrib 5.1.58, for redhat-linux-gnu (x86_64) using readline 5.1
DBに登録されているデータ件数：150万件
総データサイズ：1.6GByte（1レコードあたり1k程度と思われます）
カラム数：130
　　　　　id1,id2,pt1,pt2,…,pt128
　　　　　int(11),int(11),float,float…,float
　　　　　近似値計算はfloat部分で行います
クエリ：
select id1, MIN(POWER(pt1-dat1,2) + POWER(pt2-dat2,2) + … POWER(pt128-dat128,2) ) as 'nearest' from testDB group by id1 order by nearest limit 1
※dat1は実数です

実行時はCPU使用率が100%であるため、計算量がボトルネックになっているのかなと思っています。

これをなんとか高速化する方法はないでしょうか。
SQLのチューニングや設定の見直し、はたまた次元数を減らす方法等なんでも構いません。

不明、不足な点についてはご指摘いただければ追記させて頂きます。

以上です、よろしくお願い致します。

回答No.8

ki073

No.5のお礼欄について
メモリにデータを読み込んで計算する時ですよね。　データが1GBytes以上ありますので、どうしても読み込むのに時間がかなりかかってしまいます。Webアプリケーション側で計算処理するのでしたら、アプリケーションを立ち上げるときに読み込んでじっとメモリ上に抱えておく方法でしょうねえ。
Rubyなどで計算部分を別アプリケーションにするのであれば、計算アプリケーションを常時立ち上げておき、Webアプリケーション側から計算アプリケーションに対して計算をリクエストすればどうでしょうか。データさえ読み込んでおけばすぐに答えがかえってきます。泥臭いやり方ですが、named pipeなどを使ってリクエストを送って、答えももらえばできるように思います。もっと良い方法があるように思いますが、今ちょっと思いつきません。

回答No.7

ki073

No.5でありましたRubyのプログラムを載せておきます。
2つの方法計算しており、その時間を測定するようにしていますので、だいぶ長くなっています。
メモリが3GBytesで仮想メモリを使わずにぎりぎり下の計算ができます。上はもう少し少なくても大丈夫です。
こちらでの結果は、上が10秒、下が2秒程度です。メモリさえあれば下がだいぶ速いです。最近8GBytes増設して4000円弱でしたので、メモリを奮発すれば良いと思います。

narrayという行列計算ライブラリを使っていますので、rubygemsでインストールしておいてください。行列計算がかなり速くなります。
--------------

require "rubygems"
require "narray"
require "benchmark"
# 乱数でデータ作成
dat1=NArray.sfloat(128).random!(100)
pt=NArray.sfloat(128, 1500000).random!(100)
distance_sq=NArray.sfloat(pt.shape[1])

puts Benchmark::CAPTION
puts Benchmark.measure{
# メモリ節約計算
(0...pt.shape[1]).each{|i|
distance_sq[i]=((pt[true, i]-dat1)**2).sum
}
nearest_index1=distance_sq.sort_index[0]
puts "nearest_id: #{nearest_index1} distnce: #{Math.sqrt(distance_sq[nearest_index1])}"
}
puts Benchmark.measure{
# 高速計算？？
nearest_index2=((pt-dat1)**2).sum(0).sort_index[0]
puts "nearest_id: #{nearest_index2} distnce: #{Math.sqrt(((pt[true, nearest_index2]-dat1)**2).sum)}"
}

回答No.6

ki073

No.3,5です。
No2のお礼欄の
＞また、pt1～pt128はid1,id2を複合主キーとして持つデータなので固定
が少し気になるのですが、id1,id2+少数のデータからpt1～pt128が作られるのでしょうか？もしそうであればメモリ上で展開すればメモリ節約になるかも。

さて、三次元程度なら、よくやる方法として、
適当な大きさのセルに分割し、そのなかに入っているデータのリストを作って、隣接するセルを含めて検索する方法があります。三次元の場合は、自分自身と隣接セルで９個ですので効率的なのですが、128次元だと、各次元4分割でも4の128乗でデータ数を遥かに越えてしましますので、全然だめですね。インデックス法も同じ様なことになり非常に難しそうです。（勧めておきながらすみません）

多次元でもできる方法として、クラスタに分けて、各クラスタのデータの中心座標と、中心からの最大距離を求めておき、それを手がかにに検索する方法もあります。しかしこれも塊があちこちにあり、塊自体が独立しているようなものでないと難しそうです。（宇宙の星団のようにスカスカの空間のなかに集団があるようなものに適している）

他には、次元を減らす方法もあります。例えば三次元空間中の直線を考えると、座標軸を回転させることにより一次元目に直線がくるようにすると、残りの次元は無視できます。そんなふうにうまくいけば良いが、通常のデータだと全次元を調べないと答えがでないことが殆どなので、これも難しそうです。

結果的には、メモリ上で全部計算した方が速そうなように思います。

回答No.5

ki073

No.3です。

SQLを使わずに普通にプログラムを組んで150万件の128次元のデータを乱数で発生されて試験をしてみましたが、最短距離を見つける部分は10秒もかからず計算できましたが、この方が合理的だと思いますが。
5分くらいの瞬間芸で作ったものでメモリをふんだんに使うものですが(2GBytesは多分必要)、もし良ければ書き込みますが。
(Rubyで書いたもので数行のものです)

お礼

ご回答ありがとうございます。

ちょうどRubyも勉強中ですので、ぜひお願い致します。

1点教えていただきたいのですが、Webアプリケーションとして現在実装を進めています。（インタフェース部分はPHP）
その場合には、クライアントから要求（クエリ）があるたびにHDD内の内容をメモリに展開して検索を行なってしまい、I/O部分がボトルネックになるのでは？と考えています。
このような場合はどういった対処方法があるのでしょうか？

回答No.4

mpro-gram

まずは、質問文の SQL で気付く点
１．２乗するだけなら、power(x,2) よりも、x*x の方がずーっと早いのは、どのプログラミング言語もおなじなはず。
２．group by してるけど、どのみち全件で計算がおこなわれるから、よけいな作業が入って遅くなるだけでは？最終的に最短の１件取り出してるだけの様だし。
３．いずれにしても、150万件全部計算してはいられないから、絞る必要がありますね。
一回の SQL文では難しいと思います。

近そうなものを割り出すには、No.3　ki073　さん　の方法を、さらに mysql での最適化をするなら、 between を使った方が確実に index を利用します。
とはいえ、128カラム全部の複合index では、本体となんら代わりがない可能性が高いので、1カラムごと128個かな、実際の検索に使われるindexは１個だし、複合indexにするか悩みどころかも。
count(*) の場合には、一番効率のよさそうなindex が使われるらしいです（これは、MySQL 5 以降でinnodb の場合についてだったかな、以下参照）
http://nippondanji.blogspot.jp/2010/03/innodbcount.html
あと、insert,updateが頻繁にあるなら OPTIMIZE TABLE は、行っておいた方がよさそうです。

で、本題、まずはあたりをつけるSQL文 pt1,pt2 はカラム名、 dat1,dat2 は座標値、 d はその座標からの距離値
select count(*) from `testDB` where ( `pt1` between dat1-d and dat1+d ) and (`pt2` between dat2-d and dat2+d) and ... ;

これで、dを変更しつつ、適当な件数（ま、１００件くらいは許容範囲として、もし１件だったら、正方形の対角線距離より近いけど正方形の外というのと同じ状況がありうるので、d*2 で絞り直す,次元数が大きいので２倍でよいかは不明）に絞れたら、
この条件をつけたもので距離計算する。power は遅いので、地道に かけ算をする
select `id1`, (`pt1`-dat1)*(`pt1`-dat1) + (`pt2`-dat2)*(`pt2`-dat2) + ()*() + ...
as `nearest`
from `testDB`
where (`pt1` between dat1-d and dat1+d) and (`pt2` between dat2-d and dat2+d) and () and ...
order by `nearest` limit 1 ;

128カラムもあるとすごく長くなるけど、SQL文の最大長は何バイトだったかな？？
識別子に予約語を使っていなければ、 `` は省略可能、これで770バイトも違ってくる。

http://nippondanji.blogspot.jp/2009/05/mysql.html
によれば、「MySQLサーバーが実行出来るSQL文の最大長は、max_allowed_packetシステム変数で表され、max_allowed_packetの最大値は1GB」
そのシステムでの制限値を調べる必要はあるけど、そうとう長くても、全然問題ないようですね。データの桁数にもよるけど、１カラム用の計算式と条件文で100byte 近く必要になったとして、全文で 13KB くらい。
それでもちょっとやそっとでない時間もかかりそうだけど、15万件全部計算するのに比べれば、タイムアウトはしないんじゃないかな？

お礼

ご回答ありがとうございます。

インデックスはあまり使ったことがなかったので、大変勉強になります。

どの程度の速度が実際に出るものなのか教えていただいた方法を試してみたいと思います。

補足

補足です。
updateは基本的にはありません。
（deleteもあまりありません）
が、insertについてはそれなりに発生します。

抽象的な言葉での申し訳ありません。
なにぶんまだシステムの検討段階でして、技術的な検証を進めている状態です。
ご容赦ください。

回答No.3

ki073

調べたい点は1つではなく、複数あるとして考えます。
質問欄にあるのでは、インデックスは効かずに端から端までデータを読んでいるのでものすごく時間がかかるのだと思います。

やり方として
1)まず、pt1～128までのインデックスを作成するようにしておきます。
2)次に調べたい点dat2の近くに1点以上は存在するであろう距離dを適当な値に決めます。
3) （pt1<dat1,2+dかつpt1>dat1,2-d）かつ(pt2<dat2,2+dかつpt2>dat2,2-d)かつ.....
のように全ての次元がdat2の±dの範囲にあるデータを探します。これだとインデックスの効果があるはずです。
4) 上の条件を満たす点を集め、全部の距離を計算し、一番近いものを探します。もしdより近いものがなければ,一番近いものが3)の中に必ず有る保証はありませんので、dの値を少し大きくしてもう一度やりなおします。

上記3)で条件式が256個も並ぶので、適当な次元、例えば1～10次元目までで調べ、条件を満たしたもののなかで、1～10次元目だけで距離を計算しdを超える場合には外して、残っているのを対象に次の次元から調べ始めるというのも効率が良いかもしれません。

お礼

ご回答ありがとうございます。

インデックスをはって誤差範囲内にあるものを探すのは有効と思いました。
データの特性を考えつつ誤差範囲を決めて試してみたいと思います。

回答No.2

Siegrune

## POWERって結構CPUのPowerが必要なんですよね。。。
## って冗談はさておき、
## ベクトル計算は、普通のコンピュータ、あるいはSQLではあまり得意じゃないんですよね。
## スパコンとかが向いているし、言語もFORTRANとかが向いているのじゃなかったかな。
## という今の時点ではどうにもならない感想レベルの話は置いておいて、

「タイムアウトするレベル」を防ぎたいのなら

select id1,id2, pt1-dat1 as w1001,pt2-dat2 as w1002, … ,pt128-dat128 as w1128 from testDB
を作業用テーブル(w1000)に一度格納して、
select id1,id2, power(w1001,2) as w2001,power(w1002,2) as w2002, … ,power(w1128,2) as w2128 from w1000
## このSQLは危ない（タイムアウトしそう）かもしれません。
を作業用テーブル(w2000)に格納して、
select id1, MIN(w2001 + w2002 + … ,w2128) as 'nearest' from w2000
group by id1 order by nearest limit 1
とするしかないかと思いますが。

id2毎にデータを持っているのがどういう意図かわからないので、
その意図が分かれば多少効率化できるのかもしれませんが。

お礼

ご回答ありがとうございます。

id2はid1のデータ順（番号）となります。
イメージとしては、以下の様な感じです。
id1:1,1,2,2,3,4
id2:1,2,1,2,1,1

また、pt1～pt128はid1,id2を複合主キーとして持つデータなので固定（クエリのたびに変動しない）ですが、dat1～128についてはクエリを投げるごとに変わります。
こういった、動的？なものに対しても有効でしょうか？

回答No.1

原沢 信道（@nharasawa）

POWER(pt1-dat1,2)からPOWER(pt128-dat128,2)までの値をテーブル上に持つ方法ではだめですか。

お礼

ご回答ありがとうございます。
dat128は可変であるため、テーブル上に持つのは難しいと思っています。