-
- いいね！11
Kenn Ejima
@kenn
普通のSQL処理と逆に、ORDER BYするカラムにだけインデックス張って、あとはソート順にレコードを取り出しながらWHERE句を評価していく、みたいな処理ってできないの？
2013-10-20 23:34:47
Kenn Ejima
@kenn
男女のマッチングは、個人を大量の属性をもった多次元ベクトルへと正規化して、その多次元ノルム空間上での近さ順に(P)R-treeとかで取り出すのが良さそうなんだけど、MySQLでやれるかなぁ。PostgresならKNNGiSTが使えそうだけど、やっぱり処理順がネックか。。
2013-10-21 00:03:26
SH2
@sh2nd
@kenn UDFでの実装事例があるそうです。これと http://t.co/MOvFlE92F2 これ http://t.co/jzbq5bTs1x (コードへのリンクが切れてるっぽいですが)
2013-10-21 00:05:42
SH2
@sh2nd
@kenn もう少しまとまった記事、これ http://t.co/IWb74YT9Y7 と、これ http://t.co/9AHbEVGiFz
2013-10-21 00:13:01
Kenn Ejima
@kenn
@sh2nd なるほど、ORDER BYを使わずにtop-nの記憶を自前でやって1-pathにしてO(NlogN) -> O(N)にするってことですね。さすが @kazuho さん面白い。
2013-10-21 00:13:43
Kenn Ejima
@kenn
@sh2nd でも、O(N)でも厳しくなってくるので、できればORDER BY順にレコードを取り出して、必要な件数集まったら処理を中止させることで、さらにO(logN)にしたいんですよね。
2013-10-21 00:17:14
Kenn Ejima
@kenn
@sh2nd ふと思ったんですが、ソート用キーだけ持ったテーブルを別に用意して（R-tree使いたいのでMyISAM）、こいつをFROM句にORDER BY順にマテリアライズしながら本体テーブルとJOINして、本体側でWHERE句で絞れば、NLJなら処理止められる？
2013-10-21 00:20:20
Ryuta Kamizono
@kamipo
@kenn MySQLであれば、ORDER BYするカラムに張ったインデックスを使うようにFORCE INDEXでヒントを与えればソート順にレコードを取り出しながらWHERE句を評価していくことはできます。条件によって狙ったところで探索を打ちきれない場合はありますが。
2013-10-21 00:34:04
Kenn Ejima
@kenn
@kamipo まじですか、それは素晴らしい！条件によって探索を打ちきれない場合というのは、どういう場合か教えていただけませんか？
2013-10-21 00:35:32
Kenn Ejima
@kenn
@kamipo あ、もしかして、単に条件にあうレコードが見つからずに結局末尾までスキャンしてしまうことがあるっていう意味ですかね？だとしたら納得です。
2013-10-21 00:37:45
Kenn Ejima
@kenn
@sh2nd おぉ、ありがとうございます！たしかに結果の保証はないですよねぇ。Nested Loop Joinの原理的に、あえて違う結果を出すほうが難しそうだとは思うものの。。。
2013-10-21 00:43:00
SH2
@sh2nd
@kenn 測定結果 https://t.co/JNOIwEVD0I FORCE INDEXつけないと言うこと聞きませんでした。あとこの例だとordersのカラムでソートすると高速にならないので万能ではないみたいですね
2013-10-21 01:24:18
Kenn Ejima
@kenn
@sh2nd おー、詳細ありがとうございます！たしかに駆動表は固定してあげる必要ありますね。マテリアライズの時点ではcustomer_ix1 (c_first)なかったのかな？あればFORCE INDEXなくても動くような気もしますが。。
2013-10-21 01:35:24
Kenn Ejima
@kenn
@sh2nd c_sort_ix1が選択されてましたね。てことは、やっぱりORDER BY狙いのインデックスにFORCE INDEXしてやるのでFAっぽいですね。LIMIT件数に達しなければフルスキャン（＋インデックスとの往復）になっちゃいますが、現時点では一番マシな方法かも。
2013-10-21 01:42:08