インフラチームの山口です。 ゼロ年代 後半ゆるふわ情報系学生でしたが紆余曲折の末にインフラエンジニア1年目となりました。 今回は編集距離を使用して SQL のクエリを クラスタリング してみたので記事にまとめてみます。 奇しくも、 伊藤直也 さんのブログで編集距離の記事が公開されたのが2009年だったのですが、時の流れの速さを感じてしまいます。 1.背景 DBのCPU負荷のスパイク時に、DBのクエリのログを取得・人手で集計して、CPU負荷が高いクエリを改善するという運用を実施することがあります。 ログ(クエリ)の量が少ない場合は良いのですが、大きくなるにつれ、人手での集計に伴い以下のような問題が発生しています。 人手での集計には時間を要する 作業者が変わると結果が一意に決定できない場合があり、集計作業の再現性がない スクリプト に起こして作業をしようとしても、 単純な文字列一致の方法で集計を試みると、 WHERE の条件にしている id が異なっているだけといったクエリをうまく拾えないことが予想されます。 今回は、2つの文字列に対して定義される編集距離(Levenshtein Distance)を使用して、 スクリプト での結果の集計を試みます。 (「TF-IDFやNグラムを使用してやるのもちょっと……」という個人的な気持ちがあったので) 2.関連する事例 「編集距離を使用してクエリ同士の距離を測ればなんかうまくいきそうな気がする」というワンアイディアで調べもせず スクリプト の作成をしてしまったのですが既存の参考文献を調べてみます。 sql query clustering filetype:pdf などで検索してみるといくつか事例が見つかります。 詳しい書誌情報は割愛でタイトルとざっと読んでどんな事やっているかだけ記載します。 クエリの クラスタリング というタスクの論文は書かれているようです。 論文書かれているということは、おそらく他のエンジニアも同じ問題にあたった人もいるはず。 (手でクエリのログ分類して大変な思いしてるのは私だけではなさそう……。) "Similarity Metrics for SQL Query Clustering", 2018. 先行研究で提案された特徴量がまとめられている。 著者らの提案手法については、理解する時間がなかったが、クエリの クラスタリング のタスク自体の概要を知るには良さそう。 "Text Mining Applied to SQL Queries: A Case Study for the SDSS SkyServer", 2015. ↑ の文献で引用されていたもの。 クエリのTF-IDFを特徴量にしてSOMで クラスタリング 、可視化をしている。 3.方法 編集距離とは( Wikipedia 参照) 編集距離については既存で参考になる記事が複数存在するため、本記事では特に説明せず、 Wikipedia からガッツリ引用します。 端的には2つの文字列の間の距離の尺度です。 レーベンシュタイン距離(レーベンシュタインきょり、英: Levenshtein distance)は、二つの文字列がどの程度異なっているかを示す距離の一種である。 編集距離(へんしゅうきょり、英: edit distance)とも呼ばれる。 具体的には、1文字の挿入・削除・置換によって、一方の文字列をもう一方の文字列に変形するのに必要な手順の最小回数として定義される編集距離(Levenshtein distance)は2つの文字列がどの程度異なっているかを示す距離の一種。 例 kitten を sitting に変更する場合は、最低でも3回の手順が必要とされるので2単語間の編集距離は3となる。 kitten sitten(kをsに置換) sittin(eをiに置換) sitting(gを挿入して終了) 今回の方法 以下の要件を満たす、なんちゃって クラスタリング を実行する スクリプト を作成しました。 クラスタリング 結果が一意に決まらない方法は避けたい 手元のマシンですぐに結果がみたい(時間がかかる方法は避けたい) 今回の方法を説明します。 クラスタ の代表と以下で記載していますが、実際はレコード中で一番はじめに出てきたものをその クラスタ の代表にしているだけで、特に重心などをとっているわけではないです。 また、今回は、クエリの先頭からN単語分を抜き出して使用します。 これは、「人間が比較する際もクエリの先頭から末尾まで見ておらず、先頭N文字で判断しているだろうという仮定」と、「試しにクエリ全体で計算してみると思いの外時間がかかった」ためです。 今回の方法の概要 - クラスタリング対象のクエリすべてに対して以下を実行する - クラスタリング対象の1つめのクエリの場合はそのクエリをクラスタ0の代表としクラスタ0に追加する - クエリと各クラスタの代表のクエリの先頭からN単語の部分文字列との編集距離を計算 - 編集距離が閾値以下かつ、最も近いクラスタに割り当てる - 閾値以下の距離のクラスタがない場合は新しいクラスタを作成する また、編集距離を取得する際に、一旦クエリをスペースで分割して、単語単位での編集距離を取得します。 日本語だと 形態素解析 が必要ですが、雑に半角スペースで単語に分割します。 >>> import editdistance >>> q1 = 'SELECT * FROM tbl_1 WHERE id = 1;' >>> q2 = 'SELECT * FROM tbl_1 WHERE id = 50;' >>> q3 = 'UPDATE tbl_1 SET id = 40 WHERE id = 1;' >>> editdistance.eval(q1.split( ' ' ),q2.split( ' ' )) 1 >>> editdistance.eval(q1.split( ' ' ),q3.split( ' ' )) 6 >>> import Levenshtein >>> Levenshtein.distance(q1,q2) 2 >>> Levenshtein.distance(q1,q3) 22 パラメータと使用したライブラリおよび スクリプト 使用したライブラリ editdistance (0.5.3) パラメータ(パラメータは エイヤで 経験的に決定した) 同じ クラスタ と判断するための 閾値 : 10 編集距離10以下で一番近い クラスタ に所属させる 編集距離10以下の クラスタ がない場合は新しい クラスタ とする 比較に使用する単語数: 先頭から100単語 SQL の先頭100単語を切り出し編集距離を計算する スクリプト #!/usr/bin/env python3 # coding: utf8 import csv import editdistance from collections import defaultdict # ファイルを読み込む def load_file (in_fname, skip_header= False ): queries = [] with open (in_fname, newline= "" , encoding= "utf8" , errors= 'ignore' ) as f: queries = list (csv.reader(f, delimiter= " \t " , quotechar= '"' )) if skip_header: del queries[ 0 ] return queries # 結果をファイルに書き込む def write_file (out_fname, result): with open (out_fname, 'w' , newline= "" , encoding= "utf8" ) as f: writer = csv.writer(f, delimiter= " \t " ) writer.writerows(result) # 半角スペースでクエリを分割して、先頭word_len単語のlistを作る def get_substr (query, word_len): return query.split( ' ' )[ 0 :word_len] # クエリの編集距離を計算する def calc_distance (query_1, query_2): return editdistance.eval(query_1, query_2) # 編集距離を使ってクエリをグループ化する def cluster (queries, query_pos= 1 , word_len= 100 , threshold= 10 ): clusters = [] result = [] for row in queries: current_query = row[query_pos] current_query_substr = get_substr(current_query, word_len) # 1レコード目の場合は新規のクラスタに入れる if len (clusters) == 0 : clusters.append(current_query_substr) row.insert( 0 , 0 ) result.append(row) continue # 2レコード目以降 current_cluster = "" # 初期値 min_dist = float ( 'inf' ) for cluster_id, cluster_query_substr in enumerate (clusters): current_dist = calc_distance(cluster_query_substr, current_query_substr) # 閾値以下 if current_dist <= threshold: # クラスタとの距離が近ければ所属するクラスタと編集距離を更新する if current_dist <= min_dist: min_dist = current_dist current_cluster = cluster_id # 閾値以下のクラスタがなければ新規のクラスタにする if current_cluster == "" : clusters.append(current_query_substr) current_cluster = clusters.index(current_query_substr) row.insert( 0 , current_cluster) result.append(row) return clusters, result # 各クラスタのメンバー数などのサマリを出力 def cluster_summary (clustering_result, cluster_pos= 0 ): cluster_members = defaultdict( int ) for row in clustering_result: cluster_id = row[cluster_pos] cluster_members[cluster_id] += 1 # サマリ print ( "### Clustering Summary ###" ) # レコード数 print ( "#of records {}" .format( len (clustering_result))) # クラスタ数 print ( "#of clusters {}" .format( len (cluster_members.keys()))) # 要素数上位10のクラスタ print ( "### top 10 clusters ###" ) print ( "rank \t cluster_id \t #of member" ) for indx, v in enumerate ( sorted (cluster_members.items(), key= lambda x: x[ 1 ], reverse= True )): print ( "{} \t {} \t {}" .format(indx+ 1 , v[ 0 ], v[ 1 ])) if indx >= 9 : break # 各クラスタのメンバー数 print ( "### #of member in clusters ###" ) for c_id in cluster_members.keys(): print ( "{} \t {}" .format(c_id, cluster_members[c_id])) if __name__ == '__main__' : # inputfile base_fname = 'bombay_queries.tsv' base_fname_without_ext = base_fname.split( '.tsv' )[ 0 ] in_fname = "data/{}.tsv" .format(base_fname_without_ext) # parameter word_len = 100 threshold = 10 # outputfile out_fname_result = "result/{}_result_wordlen{}_threshold{}.tsv" .format(base_fname_without_ext, word_len, threshold) queries = load_file(in_fname, skip_header= True ) clusters, clustering_result = cluster(queries, query_pos= 2 , word_len=word_len, threshold=threshold) write_file(out_fname_result, clustering_result) cluster_summary(clustering_result) 4.結果 デー タセット "Similarity Metrics for SQL Query Clustering", 2018. で使用されているのと同じ データセット の中の、 bombay_queries.csv を用いました。 デー タセット には アノテーション されたラベルが付与されています。 id label query 0_1_1 1 select course.course_id,course.title from course 0_1_2 1 select course_id from course 0_1_3 1 select distinct course_id,title from course 0_1_4 1 select course_id,title from course 0_2_1 2 select course_id,title from course where dept_name='comp. sci.' 0_2_2 2 select distinct course.course_id,course.title from course where course.dept_name='comp. sci.' 0_2_3 2 select course.course_id,course.title from course where dept_name='comp. sci.' 0_2_4 2 select course_id,title from course where course.dept_name = 'comp. sci.' 0_2_5 2 select course_id,title from course where course.dept_name='comp. sci.' クラスタリング の結果と所感 クラスタリング 結果を以下に示します。 結果の評価には、 こちら の説明を参照し、PurityとInverse Purityと F値 を使用します。 purity,inverse purity, F値 は0から1の間で1に近づくほど良い値です。 purityが0.75とやや大きいですが、これは クラスタ のメンバー数1の クラスタ が多数あるためです。 参照にした資料でも説明がありますが、1 クラスタ 1レコードに クラスタリング された場合purityは1になります。 今回の結果では、 218 クラスタ 中で クラスタ のメンバー数が1の クラスタ は156個ありました。 結果を定性的に確認してうまくできていそうな箇所を無理やり見つけます。 クラスタ 108の結果を見ると意図したとおりに クラスタリング できているように見えます。 108の結果をよく見ると、同じクエリですがスペースの差異があるもの( count(*)>1 と count(*) > 1 )を同じ クラスタ にまとめられています。ただ、完全文字列一致でやっても、事前に空白除去しておけば拾える箇所なので、編集距離を使った良さとは強く言えなそうです。 また、今回使用したデー タセット はとりあえず、クエリに アノテーション されているものを見つけたので、きちんとした理由もなく使っているのですが、そもそも私が クラスタリング したい目的とデー タセット 作成時の目的があっているのかなども確認する必要がありそうです。クエリの クラスタリング がうまくできると、嬉しいものの、社内で アノテーション するメンバーを複数人集めて、ラベル付きデータ作って評価するほどのものでも無いような気もするしなという気持ちもあります。 レコード数と クラスタ 数 #of records|629 #of clusters| 218 クラスタ のメンバー数降順10 クラスタ rank cluster_id #of member 1 0 127 2 1 33 3 14 31 4 12 22 5 134 16 6 3 14 7 145 14 8 16 13 9 48 10 10 2 8 purity,inverse purity, F値 purity inverse purity F measure 0.75 0.27 0.40 クラスタ 108の結果 cluster_id label query 108 9 select student.id,count(id) from (section join takes using (course_id)) natural join student group by id,name having count(id) = 2 108 9 select id,name from section natural join takes natural join student group by id,semester,year,time_slot_id,name having count(*)>1 108 9 select id,name from section natural join takes natural join student group by id,semester,year,time_slot_id,name having count(*) > 1 5. まとめ 編集距離を使用しクエリの クラスタリング を試みました。 クラスタリング 方法や、パラメータ、テストに使用したデー タセット など、全体的にエイヤな部分が多いですが、定性的に結果をみると類似したクエリをなんとなくまとめることができたようにも思います。実業務でクエリのログの クラスタリング に使えるかはかなり怪しいのと、Datadogなどの SaaS でもログの クラスタリング はできるようなので、ローカルであえて スクリプト 準備して クラスタリング する機会はないのかなとも感じます。 かなり散漫な記事となってしまったので無理やりまとめますが、新しい仕組みがどんどん出てくるなかで、昔からのやり方と新しいやり方適材適所でうまく扱えるようになっていきたいなと思います。 あと、もっと楽に精度良くやれる方法を教えてくれる人がいれば教えてほしいです(かなり切実)。 6. 参考 編集距離 (Levenshtein Distance) レーベンシュタイン距離 python-Levenshtein editdistance jkkummerfeld/text2sql-data クラシックな機械学習の入門 8. クラスタリング 株式会社 エニグモ 正社員の求人一覧 hrmos.co