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.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についてはそれなりに発生します。

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