OracleのSQLIDを調べてみた（アルゴリズム解説）

はじめに

フューチャーアーキテクト Advent Calendar 2016のテーマを考える時期になりました。大規模データの分散処理に興味があるので、「分散処理」をキーワードにテーマを探していました。

• 大規模分散処理と言えば、スケールアウトアーキテクチャ
• スケールアウト構成というとAmazon Dynamoを使いたいという人がいたな…。調べてみるか。
• 巨大なKey-Valueを管理するためには分散ハッシュテーブル(Distributed Hash Table)がコア技術　参考資料
• ハッシュ関数自体はMD5アルゴリズム使っていて、2^128個(128bit)のハッシュ値が扱えると。衝突（別のインプットに対して同じハッシュ値を利用してしまう）は実務的にはあり得ないと。ゼロではないのでセキュリティ目的では脆弱性として扱われている。参考資料:wiki
• とりあえずMD5の適用例をいろいろ検索していたら、OracleにあるSQLIDについてもMD5を利用しているのが分かりました。そういえば、OracleにはSQLIDというSQL識別文字があったけど、あれも衝突しないのかちょっと疑問に思っていたんだよね…。

というわけで、当初の思いから大きく外れてテーマをOracleのSQLIDとしました。
別にOracleに興味がない方もアルゴリズムの解説として読んでいただければと思います。

OracleにおけるSQLIDとは

Oracleは実行されたSQL文を13桁の「文字列」で管理しています。この文字列のことをSQLID（要するにSQL識別するIDです)と呼ばれています。SQL実行統計の確認、パフォーマンス確認、実行されたSQL全文の確認などあらゆるところでSQLIDは利用されます。
SQLがキャシュされる共有プール内のSQLIDは以下のようにV$SQLを利用して確認できます。

SQL> select a.SQL_ID,substr(a.SQL_TEXT,1,40) from v$sql a where rownum < 5;

SQL_ID        SUBSTR(A.SQL_TEXT,1,40)
------------- ----------------------------------------
7h35uxf5uhmm1 select sysdate from dual
a4krtprr5b6fm select * from dba_users a order by a.USE
f6p0p23pz3h4v select  A.* from  DBA_USERS A where 1 =
656rwmhbk7h4w select    SQL_TEXT,           SQL_FULLTE

SQLID(SQL_ID)がSQLごとに付与されているのが分かります。
1行目のSQLを具体的な例として以降、使用していきますのでSQLIDを覚えておいてください。

SQLテキスト：select sysdate from dual
SQLID：7h35uxf5uhmm1

SQLIDについて、今のところ言えるのは以下です。（コレが結論ではないので最後まで読んでください）
* 13ケタの文字列である。
* [0-9]と[a-z]の組み合わせからなっている。10+26=36種類の文字列からなっている。
* 組み合わせとしては、13^36個ありそう。

SQLIDはどのように求めることができるのか

MD5関数でハッシュ値を求める

前から疑問だったのですが、ググると素晴らしい解説ページがありました。神解説です。
All These Oracle SQL Statement

まず、SQLIDはMD5を利用しているのが分かりますが、そこから具体的にどのようにSQLIDを求めるのかを上記サイトを参考にしつつ、わかりやすいようにコメントを加えて解き進めていきます。

まずSQL文をmd5sumコマンドを利用してハッシュ値を求めます。shellコマンドで実施していますので、SQL文の末尾にはNULL終端を付加しています。md5sumの戻り値の128bitは16進文字列([0-9][a-f])を使うと4bitを表記できるので32文字となります。

$ cat /etc/redhat-release
Red Hat Enterprise Linux Server release 6.6 (Santiago)
$ echo -en 'select sysdate from dual\x00'>a.txt
$ md5sum a.txt
abd4dbb3096b15f1ebba0c78614ea88b  a.txt

Oracle 9iまで利用されていたHASH_VALUE

SQLIDの話をする前に、「HASH_VALUE」というSQL識別IDについてみていきます。HASH_IDはOracle 9iまで利用されていました。「SQLID」は10gから利用されています。なぜHASH_VALUEからSQLIDに切り替わったのかをウォーミングアップとしてみていきます。参考サイトには以下のように書かれています。

HASH_VALUEはMD5の末尾4バイトを利用する。

なんでこんなの知ってるんだよと思いますが、これはマニアの間では既に知られた話のようです。実際にOracleで使われているHASH_VALUEと合わせて、16進表記の値を求めておきます。

select a.SQL_ID,a.HASH_VALUE,to_char(HASH_VALUE,'FMXXXXXXXX') HASH_HEX,substr(a.SQL_TEXT,1,40) from v$sql a where a.SQL_ID ='7h35uxf5uhmm1';

SQL_ID        HASH_VALUE HASH_HEX  SUBSTR(A.SQL_TEXT,1,40)
------------- ---------- --------- ----------------------------------------
7h35uxf5uhmm1 2343063137 8BA84E61  select sysdate from dual

この結果と、md5sumの戻り値を比較していきます。

• md5sum戻り値の末尾4バイト →[614ea88b]
• HASH_VALUEの16進表記(HASH_HEX)　→[8BA84E61]

md5アルゴリズムではエンディアンで扱われるためリトルエンディアン(Linux)では(32bit=4byte)のワード長ごとに反転させる必要があります。参考

[8B A8 4E 61]これを反転させると[61 4E A8 8B]となり、md5sumの値と一致しました。
ここでのポイントはHASH_VALUEは4バイトです。つまり、2^32=4,294,967,296個存在することになるのですが、40億という数値だとまったく異なるSQL文が同一のHASH_VALUEとなってしまう（衝突）という可能性があるのではないかという点で問題がありました。そのためOracle 10gからSQLIDを利用するように変更になりました。
実際問題になったのでしょうか…。当時を知る人に聞いてみたいものです。

Oracle 10gから利用されているSQLID

次にもともとやりたかったSQLIDについてみていきます。参考サイトには以下のように書かれています。

SQLIDはMD5の末尾8バイトを利用する。

なんでこんなの知ってるのですかね。これもマニアの中では知られた話なのでしょうか。
さておきmd5sumの値からSQLIDを作成していきます。

• md5sum戻り値の末尾8バイトを取得 → [ebba0c78 614ea88b]　※4バイトで区切ります。
• エンディアンを考慮して反転　→[780cbaeb 8ba84e61]　※先ほどと同じく4バイト単位反転させです。

ここで求めた値をビット変換(2進数)します。

0x780cbaeb8ba84e61 =
0b111100000001100101110101110101110001011101010000100111001100001

この2進値を右から5ビットごとに区切っていきます。最後（一番左）は4ビットになります。
全部で13個のに分割できます（SQLIDが13文字なのはここから来ています）
5ビットなので、32種類の値を取りうることになります。

0111 10000 00011 00101 11010 11101 01110 00101 11010 10000 10011 10011 00001

後で詳細を補足しますが、32種類のマッピングテーブルは以下になります。
なんでこんなの知ってるのでしょうか？output(SQLID)が分かるので推測できなくはないのですが…。
[0-9][a-z]だと本来36文字ですが5ビット32文字のため4文字分多いため「e, i, l, o」が無いです。なぜこれを選んだかは謎ですね。

2進数	10進数	文字列	2進数	10進数	文字列	2進数	10進数	文字列
00000	0	0	01011	11	b	10110	22	q
00001	1	1	01100	12	c	10111	23	r
00010	2	2	01101	13	d	11000	24	s
00011	3	3	01110	14	f	11001	25	t
00100	4	4	01111	15	g	11010	26	u
00101	5	5	10000	16	h	11011	27	v
00110	6	6	10001	17	j	11100	28	w
00111	7	7	10010	18	k	11101	29	x
01000	8	8	10011	19	m	11110	30	y
01001	9	9	10100	20	n	11111	31	z
01010	10	a	10101	21	p	-	-	-

上記のマッピングテーブルを利用して先ほど区切った13個の２進数を順番に並べて13個の文字列を組み立てます。

md5sumで求めた2進数	10進数	文字列
0111	7	7
10000	16	h
00011	3	3
00101	5	5
11010	26	u
11101	29	x
01110	14	f
00101	5	5
11010	26	u
10000	16	h
10011	19	m
10011	19	m
00001	1	1

組み立てた文字列：7h35uxf5uhmm1
この文字列は、OracleでSQLIDと一致しているのが分かります。すなわちSQLIDはMD5関数を利用しているのが分かりました。

ここまでで、SQLIDがどのように作成されるかを見ていくことが出来ました。

SQLIDは衝突が発生する可能性はあるのか

ここでようやく当初の目的であるOracleのSQLIDは全く別のSQL文で同一のIDをとる可能性があるのかというのを検討できることになります。

今まで見てきたように「SQLIDはMD5の末尾8バイトを利用する」というロジックで作成されていました。8バイトの取りうる範囲は2^64となります。
この数値が現実的には衝突の発生しない必要十分な値であることが分かります。参考

64ビット（英: 64-bit）は、連続した64個（桁）のビット（8オクテット）であり、バイナリで最大18,446,744,073,709,551,616(16E)までの数を表現できる。

おまけ

先ほどSQLIDを作成する際に利用するマッピングテーブルに「e, i, l, o」は存在していませんでした。約800,000個のSQLが保存されていた実際に業務で利用されている環境を見てみたのが以下の結果になります。

select b."character",count(*)
from
(
select distinct a."keta",a."character"
from (
select '01' "keta" ,substr(sql_id,1,1) "character" from dba_hist_sqltext
union all
select '02' "keta" ,substr(sql_id,2,1) "character" from dba_hist_sqltext
union all
select '03' "keta" ,substr(sql_id,3,1) "character" from dba_hist_sqltext
union all
select '04' "keta" ,substr(sql_id,4,1) "character" from dba_hist_sqltext
union all
select '05' "keta" ,substr(sql_id,5,1) "character" from dba_hist_sqltext
union all
select '06' "keta" ,substr(sql_id,6,1) "character" from dba_hist_sqltext
union all
select '07' "keta" ,substr(sql_id,7,1) "character" from dba_hist_sqltext
union all
select '08' "keta" ,substr(sql_id,8,1) "character" from dba_hist_sqltext
union all
select '09' "keta" ,substr(sql_id,9,1) "character" from dba_hist_sqltext
union all
select '10' "keta" ,substr(sql_id,10,1) "character" from dba_hist_sqltext
union all
select '11' "keta" ,substr(sql_id,11,1) "character" from dba_hist_sqltext
union all
select '12' "keta" ,substr(sql_id,12,1) "character" from dba_hist_sqltext
union all
select '13' "keta" ,substr(sql_id,13,1) "character" from dba_hist_sqltext) a
) b
group by b."character"
order by 1;

char   COUNT(*)
---- ----------
0            13
1            13
2            13
3            13
4            13
5            13
6            13
7            13
8            13
9            13
a            13
b            13
c            13
d            13　←「e」がない
f            13
g            13
h            12
j            12　←「i」がない
k            12
m            12　←「l」がない
n            12
p            12　←「o」がない
q            12
r            12
s            12
t            12
u            12
v            12
w            12
x            12
y            12
z            12

この結果から以下が分かります。

• 「e, i, l, o」は確かに使われていない。
• 1番先頭の文字だけ4ビットのため、文字の範囲が[0-9][a-g]となっている。

終わりに

OracleのSQLIDを求めるアルゴリズムについてみていきました。こういうちょっとしたところを少し興味を持って調べるだけで知識の幅が広がります。当記事がその助けになればと思います。

あと、もしわかる方がいたら以下について誰か教えていただけると嬉しいです！

• 本来であればMD5は128bitの値を戻すのですが、SQLIDはMD5の末尾8バイト(64bit)を利用しています。この範囲で本当に一様に分布されているのでしょうか？
• 「e, i, l, o」が使われていないのはなぜ。

それではまた！