インフラチームの山口です。
ゼロ年代後半ゆるふわ情報系学生でしたが紆余曲折の末にインフラエンジニア1年目となりました。
今回は編集距離を使用してSQLのクエリをクラスタリングしてみたので記事にまとめてみます。
奇しくも、伊藤直也さんのブログで編集距離の記事が公開されたのが2009年だったのですが、時の流れの速さを感じてしまいます。
1.背景
DBのCPU負荷のスパイク時に、DBのクエリのログを取得・人手で集計して、CPU負荷が高いクエリを改善するという運用を実施することがあります。
ログ(クエリ)の量が少ない場合は良いのですが、大きくなるにつれ、人手での集計に伴い以下のような問題が発生しています。
- 人手での集計には時間を要する
- 作業者が変わると結果が一意に決定できない場合があり、集計作業の再現性がない
スクリプトに起こして作業をしようとしても、
単純な文字列一致の方法で集計を試みると、WHERE の条件にしている id が異なっているだけといったクエリをうまく拾えないことが予想されます。
今回は、2つの文字列に対して定義される編集距離(Levenshtein Distance)を使用して、スクリプトでの結果の集計を試みます。
(「TF-IDFやNグラムを使用してやるのもちょっと……」という個人的な気持ちがあったので)
2.関連する事例
「編集距離を使用してクエリ同士の距離を測ればなんかうまくいきそうな気がする」というワンアイディアで調べもせずスクリプトの作成をしてしまったのですが既存の参考文献を調べてみます。
sql query clustering filetype:pdf などで検索してみるといくつか事例が見つかります。
詳しい書誌情報は割愛でタイトルとざっと読んでどんな事やっているかだけ記載します。
クエリのクラスタリングというタスクの論文は書かれているようです。
論文書かれているということは、おそらく他のエンジニアも同じ問題にあたった人もいるはず。
(手でクエリのログ分類して大変な思いしてるのは私だけではなさそう……。)
3.方法
編集距離については既存で参考になる記事が複数存在するため、本記事では特に説明せず、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
パラメータと使用したライブラリおよびスクリプト
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)
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)
if len(clusters) == 0:
clusters.append(current_query_substr)
row.insert(0, 0)
result.append(row)
continue
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())))
print("### top 10 clusters ###")
print("rank\tcluster_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__':
base_fname = 'bombay_queries.tsv'
base_fname_without_ext = base_fname.split('.tsv')[0]
in_fname = "data/{}.tsv".format(base_fname_without_ext)
word_len = 100
threshold = 10
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. 参考
株式会社エニグモ 正社員の求人一覧
hrmos.co
