システムアーキテクト通訳案内士のブログ

JOINのパフォーマンスについての考察2（リレーションとの関係2）

ちょっと間があきましたが、JOINのパフォーマンス関連の続きになります。
前回、JOINのパフォーマンスについての考察（リレーションとの関係）でJOINを行った結果、データが非正規化するとその非正規化の度合いによってパフォーマンスが下がるという話をしました。
前回の記事では、1対ｎの結合ではJOINを外す（単純なSQLに分割してホスト言語側で結合させる）ということで、定性的な話しかしていませんでしたが、幾つか実験を通して、もう少し定量的な話をしてみます。
『たかがJOINで、なぜこねくり回すのか？』と思われるかもしれませんが、こういう実験＆考察というのは意外に行われていないかと思います。私自身定性的なことは理解していたつもりでしたが、実際に実験を行うと色々と発見がありますので、記事にしてみます。
大切なことは解った気になることではなく真実を追究する姿勢で、先入観を持たずにきちんと実験を行いパフォーマンスに対する感性をみがくことは大切かと思います。

今回、調査するアルゴリズムについて

今まで何回か実験してきましたが、実験で使用してきたアルゴリズムについて説明します。

１．SQLでJOINを行う。

SELECT Price.CODE, RDATE, OPEN, CLOSE, NAME
FROM Price INNER JOIN Company ON (Price.CODE = Company.CODE)

という風にSQLでJOINを行います。普通の処理になります。

２．ホスト言語側でJOINを行う（キャッシュ付のネステッドループJOINを行う）

　１．のSQLを以下のように分割します。

(1) SELECT CODE,RDATE,OPEN,CLOSE FROM Price
(2) SELECT NAME FROM Company WHERE CODE = ?

(1)のSQLを実行して結果を取得しますが、NAMEについては(2)のように再度SQLを発行します。
ここで、単純にPriceテーブルの全ての行に対して(2)SQLを発行するのではなく同じ結果をキャッシュして同じCODEの場合はキャッシュからデータを取得するようにします。
　

３．ホスト言語側でJOINを行う（ハッシュJOINを行う）

１．のSQLを以下のように分割します。

(１) SELECT CODE,NAME FROM Company
(２) SELECT CODE,RDATE,OPEN,CLOSE FROM Price

（２）のPriceテーブルからのデータの取得に先立ちまして、（１）でComapnyテーブルから全てのデータを取得しておきます。
多くのDBMSで行っているハッシュ結合を真似ています。

1対ｎの2つのテーブルのJOINにおけるパフォーマンスモデル式

続いて、各アルゴリズムのパフォーマンス（実行時間）のモデル式を示します。
ここで、
n ： Priceテーブルの行数
m ： Companyテーブルの行数
c10,c10,c20,c21,c22,c23,c30,c31,c32 ：　比例定数
になります。

１．SQLでJOINを行う

１．のパフォーマンスのモデル式は以下のようになります。

c11 * n + c10

　Priceテーブルの行数に比例した時間で結果を取得できます。ここでc11は比例定数であり、C10はオーバーヘッドにあたります。

２．　ホスト言語側でJOINを行う（キャッシュ付のネステッドループJOINを行う）

　２．のパフォーマンスのモデル式は以下のようになります。

c21 * n + c22 * m + c20

　Priceテーブルの行数に比例した時間と、Companyテーブルの行数に比例した時間およびオーバーヘッドの合計になります。
　『c22 * m は　c22 * n * m になるのでは？』と思われるかと思いますが、キャッシュのおかげでこのようになります。
また、「１．SQLでJOINを行う」と比べますと、c22 * m と余計な項が付いていますので、

SQLでJOINした方が速い

と早合点される方がいらっしゃるかと思いますが、JOINのパフォーマンスについての考察（リレーションとの関係）で述べたことは、c11とc22の定数値の差異となって現れてきます。

３．ホスト言語側でJOINを行う（ハッシュJOINを行う）

　３．のパフォーマンスのモデル式は以下のようになります。

c31 * n + c32 * m + c30

　面白いことですが、形式的には「２．　ホスト言語側でJOINを行う（キャッシュ付のネステッドループJOINを行う）」と同じになります。
ちなみに、[ADP開発日誌]SQL（JOIN）の実行パフォーマンスについて２０１１ にあります、「SQLの発行回数のオーバヘッドはどこにいったんや？」と思われるかもしれませんが、それはc32とc22の差異に出てくるということになります。

実験と結果

　今回の実験では、nの値を変えながら実行時間を計測することにより、各モデル式の定数を求めます。求めるといってもグラフを書いて状況を観測します。厳密には回帰分析とかを行うことになるでしょうが、グラフが直線になることと、ｎが増えたときの傾向をつかめればよろしいかと思います。
アルゴリズムの教科書ではオーダーという概念があり、オーダーでは定数を求めることは無意味とされています。つまり上記のアルゴリズムは論理的には違いがなくどれも一緒ということになります。
つまり、2倍や3倍の差はあまり意味がないということですが、もっとも、実際の現場ではこのような差にも敏感になるので、きちんと計測して値を出すことになります。
また、今回はｍは固定（約2000）で行っています。ｍが変動したときにどう変わるのかも興味深いですが今回は、m << n ということで結果にはあまり影響しません。

先ずは、結果から、

Priceテーブルから取得する行数を変えながらSQLを実行（単位ms）

	0行	373,740行	1,172,191行	2,002,749行	4,671,568行
１．SQLでJOIN	718	10,015	29,938	52,329	119,192
２．キャッシュ付のネステッドループJOINを行う	671	10,469	30,172	49,814	116,770
３．ハッシュJOINを行う	2,828	11,422	29,797	49,845	110,988

つづいて、グラフを以下に示します。

縦軸が時間で、横軸が行数（ｎ）になります。グラフをみますとPriceテーブルの行数（ｎ）が増えると「１．SQLでJOIN」より、「２．キャッシュ付のネステッドループJOINを行う」や「３．ハッシュJOINを行う」の方が速くなっていくことが解るかと思います。

パフォーマンスにシビアになる時は、往々にしてｎの行数が増えるような場合にあたるということになります。その場合は１より２や３を選択した方がよいということになります。

もっともグラフを見て解るとおり差はあまりないので、通常はやはり普通にSQLでJOINを行い、パフォーマンスを稼ぎたくなったら２や３を検討するということになるでしょう。

[ADP開発日誌 ]Ver 0.75 リリース バグフィックス

　ブログの方ですが、一周年記念記事の追加やSQLのパフォーマンスの記事等ちょっととっちらかった感がありますが、ADPのVer 0.75をリリースします。

基本的にバグフィックスになります。
・insert / update / delete でメモリリークのバグフィックス
・組込み述語(_table_quote)を削除し、組込み述語(_db_quote / _db_default_quote)を追加した。

SQLのパフォーマンスの記事のアップに際して環境を整えましたが、その際にデータのコピーをADPでやらせてみたところバグが発覚したので修正しました。
またSQLServerからMySQLにデータをコピーするに際してクオート文字の指定が_table_quoteだと不完全なので整理しました。

ちなみに、insertの性能ですが、悪いです。
MySQLやSQLServer2008以降では、多数の行をインサートするために、マルチプルインサート、Oracleではマルチテーブルインサートが使えるので、検討してみたい（専用の述語の追加になるか？）。

JOINのパフォーマンスについての考察（リレーションとの関係）

コメントを頂いたのですが、ちょっと返し方が悪かったのか音信普通になりましたので、改めてJOINのパフォーマンスについて考察してみます。

1対ｎ結合の場合、JOINとは正規化データから非正規化データを作り出す操作になる

RDBのテーブルは、きちんと設計されていれば、正規化されています。つまりデータに重複がなく容量の面で効率的になっています。ここで正規化データとはあくまでもRDBにとって効率的というだけでそれ以上のものではありません。一方で人間が理解しやすいデータ形式は必ずしも正規化データというわけではなく、往々にして非正規化されたデータの場合があります。
JOINを行うということは正規化されたデータを非正規化データに戻す操作ということに相当します。つまり、効率のよいデータから人間にとって理解しやすいデータ形式に戻す操作になります。JOINは正規化されたデータから非正規化という効率の悪いデータ形式に変換する操作になります。
SQLでJOINを行い、その結果を取得するということは何らかの非効率な行為が行われているということがわかるかと思います。
RDBのコピーを行おうと考えた場合、わざわざJOINなどせずに、テーブル毎にコピーを行おうとするでしょう。RDBからデータを取り出すとき同様に正規化された単位でデータを取得した方が有利な場合があるということは理解できるかと思います。

RDBでは正規化データから非正規化データを作り出す方が非正規化データから正規化データを取り出すより効率的

先ほど、JOINは非効率といいましたが、なぜRDBでは効率の悪いJOINが行われるのでしょうか？
理由は簡単で、RDBの理論では、
・非正規データ から 正規データ を作る
操作より
・正規データ から 非正規データ を作る
操作の方が効率的と考えられているからです。非正規データから正規データを得るにはグループ化を行います。つまりGROUP BYを行う必要がありますがこれはつまりソートを行った上に重複したデータを圧縮することに相当します。一方でJOINはデータの検索に相当します。例外はありますが検索の方がソート＆圧縮より効率的なのは理解できるでしょう。
さらに、正規化データは非正規化データより更新が容易ということもあります。
つまり、関係データベースの世界では正規化されたデータは非正規化されたデータより効率がよいと考えられています。ちなみに、この認識が間違って拡大解釈され、『SQLは効率がよい』という誤解が生まれたと想像されます。

1対ｎの結合で一方のレコードサイズが小さいとき、2つのテーブル間の単純なJOINは効率的、だがデータの出力が非効率

FROM table_a INNOR JOIN table_b ON (table_a.table_b_ID = table_b.ID)
のSQLがあるときに、
table_aがマスターを参照するテーブルで、table_bがマスターテーブルと仮定します。つまりtalbe_aとtable_bが1対ｎで結合されており、さらにtable_bがメモリに入る場合、JOIN自体のコストはほとんどかかりません。
2011年現在、サーバーに搭載されるメモリ容量が数十GBのオーダーになります。一方でマスターテーブルの容量は多く見積もっても数百万件のオーダーになり、各データを多く見積もって１KBとしてもマスターテーブルのデータ容量は数GBのオーダーとなります。実際にはJOINに必要なデータのみメモリにおいた場合、必要なデータは1桁も2桁も減ることになります。結果として1対ｎの結合ではほどんどの場合、マスターテーブル側はメモリに乗ることになり、JOINにおいてマスター表の操作は高速に行えます。
しかし、1対ｎの結合では、結果を取得する場合に、結果データが非正規になる為に非効率になります。
この場合、JOINを分割して、呼び出し言語側でJOINした方が理論的には効率的になります。実際どこまで効率的になるかは分割による複数回のSQLの呼び出しのオーバヘッドと繰り返しデータの量に左右されます。

1対1結合の場合は、JOINは出力も含めて効率的になる

1対1結合の場合は、結果データも正規化しているのでJOINは効率的になります。JOIN自体が効率的に行えるかどうかはデータ量やデータ（または結合キーのインデックス）が整列されているかどうかによります。

結論

以上のように、扱うデータの性質によってSQLでJOINさせる方がよい場合とSQLではJOINさせない場合の方が理論的に速くなる例を示しました。
結合の種類が1対ｎの場合、JOINを行うとデータ非正規化し、容量が増えるので出来るだけJOINを遅らせるテクニックが有効になる場合があります。
実際にどのような状況のときにJOINを遅らせたほうがよいかですが、マシンのスペック、ネットワークの環境等に依存しますが、傾向として行数が増えた場合や1対ｎのJOINの数が増えるとJOINを遅らせる方が有利になります。このような場合でパフォーマンスに問題が発生した場合にJOINを遅らせるテクニックを検討されると上手くいく可能性が高まります。
一方で、結合の種類が1対1の場合、データは非正規化しないので、SQLの発行の段階でJOINを行えば有利になります（JOIN自体のコストはまた別の話になります）。

対峙

一周年記念記事とかLLの感想とか書くネタはあるのですが、某読者より『最近、猫感が足りないですね。』とご指摘を受けたので久しぶりの猫ネタです。
うちには、ミミとチャチャで2匹の猫が居るのですが、この2匹は非常に仲が悪く目を離すと直ぐに喧嘩をします。

不穏な空気が出始めます。
　
ちょっかいを出し始めるのはチャチャ（茶色）の方になります。
　
さしずめ、川中島で対峙する、武田信玄と上杉謙信のようです。

通訳案内士試験

先週のLL Planetsに引き続き、今週末は通訳案内士の試験で、来週末、さ来週末とこのところ予定が目白押しですが、
去年に引き続き、28日に通訳案内士の一次試験に挑戦しました（このブログを書いているのは30日）。
今年は、昨年受かった地理と一般常識が免除になり、英語と歴史を受験しました。
通訳案内士の試験ですが、地理、歴史、一般常識がマークシートで問題用紙を持ち帰ることができます。
地理、歴史、一般常識は平均点を取ればよいので甘く考えていたのですが、今年の歴史はだいぶレベルが高く私の得点も微妙で、『また来年』ということになりそうです。

一方で、英語の試験ですが、記述式で試験終了後問題用紙も回収されますのではっきりしたことはいえませんが結構出来が良かったです。
もっとも、問題が去年と比べて易しくなったようで、例えば英作文の場合、『バレンタインデーとは何か？』を80ワード程度の英語で書かせる問題だったのですが、今年は『女性専用車を3,4行（恐らく30~40ワード程度）で説明せよ』、『こいのぼりを3,4行で説明せよ』とかだいぶ問題の難易度が下がったかと思います。80ワードでの作文と40ワード程度×２だと、当然80ワードで書く方が深く説明しなければならないので難易度が高いかと思います。もっとも簡潔に必要事項をまとめるということであれば逆に難易度が高くなりますが問題文からはそう深堀も出来ないかと思うので簡単になったかと思われます。
英語の合格基準は『平均点を60点とした場合に70点を合格とする』とよく解らない基準で、平均点より10点以上上回ると合格というイメージのようなので、私の英語力を鑑みるとこちらも通るかどうかは微妙です。しかし、2年も英語の勉強を続けているとさすがにそれなりに上達するもので、来年は合格に手が届きそうです。と手ごたえを感じただけでも良かったです。

場合によっては歴史が落ちて、英語が通るということもありえるのですが、そうなると歴史の方をだいぶ軽視し英語の勉強ばかりをしていたので少し悔いが残ります。