【新機能】作り忘れたまとめはありませんか?31日前まで期間指定してまとめが作れる高度な検索ができました。有料APIだからツイートの漏れはありません!

ORDER BY 狙いのキーの話2

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

ブックマークしたタグ

あなたの好きなタグをブックマークしておこう!話題のまとめを見逃さなくなります。
ログインして広告を非表示にする
ログインして広告を非表示にする