MySQLのテーブル結合について整理してみる

f:id:ts0818:20210307225700j:plain

歴史上最古の現存するテーブルは、エジプト第17王朝の木製テーブルで、長方形の甲板を 4 脚の角柱で支え、脚の補強にを用い、中世になると、大型化し甲板と脚が分離できる架脚式構造になり、また、小さな丸テーブルと書見台を組合わせたようなライティング・テーブルが普及した。

テーブル (家具) - Wikipedia

⇧「エジプト第17王朝」とか言われてもね...

⇧ ほえ~、紀元前1570年~紀元前1580年頃には「テーブル」が存在したそうな。

そっちの「テーブル」くっ付けて~、とかいう文化は太古の昔から存在したかもしれないと思うと、何か不思議な気持ちになりますね、どうもボクです。 

By the way、

ospn.connpass.com

⇧ 参加して参りました。

「Neo4jを使ったクリンゴン語自然言語解析(案浦浩二さん)」のセッションを聴講して「ISO 639」の存在を知りました。

ISO 639は、言語の名称の略号を規定した国際規格である。国際標準化機構が発行。複数の巻で構成され、現在は5巻が公表されている。日本工業規格では「JIS X 0412」がほぼ相当する。

https://ja.wikipedia.org/wiki/ISO_639

⇧ ってな感じで、「言語」の名称の略称についての国際規格らしいんですが、

クリンゴン語クリンゴンご、クリンゴン語では tlhIngan Holラテン文字表記))は、SFテレビドラマスタートレック』シリーズに登場する架空の宇宙人、クリンゴン人が使用する架空の言語である。

クリンゴン語 - Wikipedia

架空の言語としては完成度も高く人気があり、ISO 639言語コードでは 「tlh」 で表されるなど、実在の言語と並ぶ扱いをされることも多い。

クリンゴン語 - Wikipedia

⇧ まさかの架空の言葉も定義されちゃってるという...

ちなみに、

ヴァリリア語群(ヴァリリアごぐん)は、ジョージ・R・R・マーティンによるファンタジー小説、「氷と炎の歌」シリーズとそのテレビ版、「ゲーム・オブ・スローンズ」に登場する架空の語族。

ヴァリリア語群 - Wikipedia

⇧「ゲーム・オブ・スローンズ」に出てくる言語「ヴァリリア語」については、「ISO 639」で定義されてないらしい、「ISO 639」の基準がよう分からんな...

ちなみに、今現在のところ「英語」にしか対応して無いようですが、

https://www.duolingo.com ってサイトで「クリンゴン語」「ヴァリリア語」が学習できるらしい...。

www.duolingo.com

「使用言語:英語」にした状態で、下の方に画面をスクロールしてみると、

f:id:ts0818:20210307191217p:plain

「高地ヴァリリア語」と「クリンゴン語」が語学学習の選択肢の中に!

f:id:ts0818:20210307191402p:plain


「Neo4j」は、

gql.today

⇧「GQL(Graph Query Language)」ってことらしいっす。

SQL(Structured Query Language)」と「GQL(Graph Query Language)」 の関係的には、

⇧ 上図のような感じらしく、「PGQ(Property Graph Queries)」って言葉があることから、「PGQL(Property Graph Query Language)」ってのがあるみたいね。

「GQL(Graph Query Language)」は「SQL(Structured Query Language)」プロジェクトが承認されて以来、初めての新しいデータベース言語プロジェクトという位置付けらしい。(「Neo4jを使ったクリンゴン語自然言語解析(案浦浩二さん)」によると35年ぶりとなるって話でした)

SQL(Structured Query Language)」のプロジェクトが、

SQL規格は1986年に統一標準規格が発表されるまでは、その統一標準規格が存在しない状況であった。

SQL - Wikipedia

⇧ 1986年以前に始まったとすると、確かに、2021年現在から見れば、35年ぶりってことになるのかな?

喫緊の課題としては、乱立してる「PGQL(Property Graph Query Language)」を

⇧ 上図のような感じに、「GQL(Graph Query Language)」に統一したいってことみたいね。

脱線しましたが、今回は「MySQL」について調査してみたなので、「SQL(Structured Query Language)」の話ってことですかね。

「NoSQL」とか「NewSQL」も「SQL(Structured Query Language)」のお仲間ってことなのかね。

レッツトライ~。

 

RDBMS(Relational Database Management System)」の歴史

Wikipediaさんに聞いてみた。

1969年、エドガー・F・コッドは画期的な論文を発表してRDBMSを提唱した。

この論文は1970年に、ACMの学術誌に「A Relational Model of Data for Large Shared Data Banks(大規模共有データバンクのデータ関係モデル)」として掲載された。コッドは、この論文とその後に発表した論文で、「リレーショナル」(「関係に基づく」)の概念とは何かを定義した。

関係データベース管理システム - Wikipedia

⇧ 1969年が「リレーショナル」の定義の始まりっぽいですね。

コッドが提唱したRDBMSが備えるべき条件として、「コッドの12の規則」が有名である。しかし関係モデルの初期の実装の多くは、コッドの12の規則の全てを満たすには至らなかった。そのためRDBMSという用語は、当初と比べてより広い意味でのデータベースシステムを対象として使われることが、多くなってきている。

関係データベース管理システム - Wikipedia

⇧「コッドの12の規則」を満たすことが「RDBMS(Relational Database Management System)」ということらしいですと。

「コッドの12の規則」はというと、

コッドの12の規則(コッドの12のきそく、英語:Codd's 12 Rules)とは、データベース管理システム (DBMS) が関係に基づいたシステム(関係データベース管理システムRDBMS)であると判断するために必要な基準として、エドガー・F・コッドが提唱した規則である。エドガー・F・コッドは、データベースにおける関係モデルを考案した人物である。

コッドの12の規則 - Wikipedia

しかし実際には、コッドの12の規則は非常に厳しい基準であり、データベース言語 SQL のみをデータベースにアクセスするインタフェースとするシステムでさえ、コッドの12の規則のいくつかを満たすことはできていない。

コッドの12の規則 - Wikipedia

⇧ どんだけシビアな規則なんだ... 

シビア過ぎて、  

現在では、RDBMSという用語は、次のようなシステムに対して使われている。

  • システムの利用者が、データをいくつかの関係 (複数のと複数のからなる) の形で、扱うことができるシステム
  • システムの利用者が、表形式のデータを参照・更新する手段として、関係演算 (制限射影結合などの関係代数関係論理) を、使うことができるシステム

関係データベース管理システム - Wikipedia

⇧ とりあえずの暫定処置として的な扱いで「RDBMS(Relational Database Management System)」について考えときましょう、ってことなんですかね?

そして、衝撃の事実... 

どのような データベース管理システム (DBMS) が、「リレーショナル」DBMSといえるのか(もしくはいえないのか)については、議論の対象となっている。データベースに携わる人の多くに受け入れられたRDBMSの定義は、まだできていない。

関係データベース管理システム - Wikipedia

現在は、RDBMSの選定を行う際は、コッドの12の規則の全てを満たすという要件は考慮されない。情報技術 (IT) を担う組織におけるデータ管理を担う人々にとってのTCO(総保有コスト)が、とても重視される。

関係データベース管理システム - Wikipedia

一部の人々は、このような現状は不幸であり皮肉であると考えている。なぜなら、コッドの12の規則の有用性を確信している人の見解では、この RDBMS としての基準を正確に満たすことにより、DBMSの信頼性と一貫性生産性処理性能を高めることができ、それゆえTCOの抑制に大きく役立つはずであった。RDBMSの基準を正確に満たすことによるこのような利点は、実際に、DBMSを真のRDBMSとしようと努めている人々にとって、とても大きな動機づけとなっている。

関係データベース管理システム - Wikipedia

⇧ まさかの「RDBMS(Relational Database Management System)」の定義については現在進行形の形という...

我々は一体、何を拠り所とすれば良いのだろう... 

現在、RDBMSの実装のほとんどが、データベース言語としてSQLを採用している。しかしSQLに代替するデータベース言語(データベース言語仕様Dに基づいたTutorial Dなどのデータベース言語)が提唱され、実装が行われている。ただしSQLに代替するデータベース言語を採用し実装している商用のRDBMSは非常に少ない。

関係データベース管理システム - Wikipedia

D は、クリス・デイトヒュー・ダーウェンが著書 (共著) The Third Manifesto で提案した、関係データベースデータベース言語が満たすべき要件の集合である。 D自体はデータベース言語ではない。 デイトとダーウェンは、2008年現在で広く使われているデータベース言語SQLを、関係モデルを正確に実装していないとして、批判している。

D (データベース言語仕様) - Wikipedia

⇧ まさかの「RDBMS(Relational Database Management System)」の「要件定義」っぽいものが存在するらしいけど、普及してないみたいね...

 

MySQLのテーブルの結合

RDBMS(Relational Database Management System)」の現状については、知りたくない情報の諸々を垣間見てしまったのですが、実業務では待ったなしで利用せざるを得ない状況ですと。(「NoSQL」とか「NewSQL」とか「データウェアハウス」とか「RDBMS(Relational Database Management System)」以外の選択肢もあるとは思いますが) 

で、「RDBMS(Relational Database Management System)」を使ってる場合に避けて通れないのが、「テーブルの結合」ですかね。  

f:id:ts0818:20210304110649p:plain

SQLで使えるテーブルの結合のやり方は、inner joinと、3通りのouter join、さらにcross joinの5つです。ただし、Webシステムでよく使われるオープンソースのデータベース管理ソフトのMySQLは、full outer join は使えません。とはいえ、他のデータベース管理ソフトから移植することもあります。SQLを使う機会のあるWebエンジニアの方は、ぜひ、理解しておきましょう。

https://style.potepan.com/articles/17010.html

⇧ 上記サイト様が「テーブルの結合」の種類について説明してくれておりました。

実際に「テーブルの結合」の実行イメージについては、

qiita.com

⇧ 上記サイト様が詳しいです。

で、一旦、脱線して、「テーブルの結合」で使用されてる「アルゴリズム」があるらしいので、どんなものがあるのか確認。

 

RDBMS(Relational Database Management System)」の「テーブルを結合するアルゴリズム」とは?

当然のことながら、「テーブルの結合」を実施する「SQL」の処理で内部的に「アルゴリズム」が存在するらしいのですが、

qiita.com

複数のテーブルを結合するSQLを実行すると、RDBは内部的にテーブルを結合する処理を実行します。そのアルゴリズムは大きく分けて3種類あり、それぞれに得意不得意な状況が異なります:

  1. Nested Loop Join(以下NLJ)
  2. Hash Join
  3. Merge Join

実例で学ぶ、JOIN (NLJ) が遅くなる理屈と対処法 - Qiita

...なのですが、実はMySQLに関していうとNLJ(とその亜種)しか実装されていません。

OraclePostgreSQLは3つとも実装されています。

実例で学ぶ、JOIN (NLJ) が遅くなる理屈と対処法 - Qiita 

xtech.nikkei.com

 まずは,テーブルを結合(JOIN)するアルゴリズムについてです。SQL文の処理には,大きく分けて,選択,射影,結合の3種類がありますが,最も負荷が大きいのがこの結合処理です。結合処理の最適化の優劣が,SQL文の高速化のカギを握っている,といっても過言ではありません。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

 RDBMSがテーブルを結合する際に利用するアルゴリズムには,「ネスト・ループ結合」「マージ結合」「ハッシュ結合」の三つがあげられます。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

⇧ 上記サイト様によりますと、大きく分けて、

  • Nested Loop Join
    ネスト・ループ結合
  • Merge Join
    マージ結合
  • Hash Join
    ハッシュ結合

の3つの「アルゴリズム」があるようです。

■Nested Loop Join(ネスト・ループ結合) 

 ネスト・ループ結合は,単純に二重ループを回してテーブルを結合する方法です。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

そのため,コストは二つのテーブルのレコード数の積に比例します。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

以下サイト様でアルゴリズムのアニメーションが確認できます。

bertwagner.com 

■Merge Join(マージ結合) 

 マージ結合は,ネスト・ループ結合の改良版と言える方法です。まず,二つのテーブルを,結合するフィールドについてあらかじめソートしておきます。そして,両方のテーブルのレコードに対して持たせたポインタを,レコードの上から下へと順に走査させながらフィールドの値が一致するものを探します。

レコードの走査が1回で済むのが特徴です。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

以下サイト様でアルゴリズムのアニメーションが確認できます。 

bertwagner.com

 

■Hash Join(ハッシュ結合) 

 これもネスト・ループ結合の改良版と言うべきものです。ネスト・ループ結合では,テーブルAの各レコードについて,テーブルBを全件走査しています。この検索処理の部分にハッシュ法を使うことで高速化を図るのがハッシュ結合です。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

以下サイト様でアルゴリズムのアニメーションが確認できます。 

bertwagner.com

 

使いどころについては、 

 これらの三つのアルゴリズムは,一般的に言って,ネスト・ループ結合<マージ結合<ハッシュ結合の順で高速になります(ハッシュ結合が最速)。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

ただし,二つのテーブルのレコードの数が極端に違う場合や,両方のレコードの数が十分小さいときには,必ずしもこの順番にならないこともあります。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

加えて,応答時間が重要なとき,すなわち「処理がすべて終了するまでの時間を短くするより,とにかく最初に検索条件に合致した1レコードを早く返したい」というような場合には,ネスト・ループが向いています。

基礎から理解するデータベースのしくみ(4) | 日経クロステック(xTECH)

⇧ よくよく吟味すべし、ってことなのかね。

 

テーブル結合はデータベースのパフォーマンスに直結することもある

というわけで、

qiita.com

DBのパフォーマンスチューニングでは大きく分けて2種類のアプローチがある。

  • DBチューニング(全体最適化)
    主にスループットを向上させる
    MySQLの設定ファイルのパラメータ等を環境に適した形に操作する
  • SQLチューニング(個別最適化)
    主にレスポンスタイムを向上させる
    テーブルの構成やクエリの最適化によってクエリ実行速度の向上を目指す

MySQLデータベースのパフォーマンスチューニング - Qiita

⇧ 上記サイト様にもありますように、「データベース」のパフォーマンスチューニングにおいて「SQLチューニング(個別最適化)」ってアプローチがあることからも、「SELECT文」の「テーブルの結合」なんかについても気を付ける必要があるってことですかね。

ちなみに、

blog.fujimisakari.com

for文とかで都度クエリーを発行するとDBへの負荷が高いです。

MySQLパフォーマンスチューニング / fujimisakari blog

⇧ アプリケーション側でも注意が必要ですかね。

ちなみに、「MySQL」で宜しくないqueryを探す方法については、

blog.cybozu.io

まず第一にスロークエリログを読みましょう。

とは言っても上から順にただ読むのではなく、統計処理をして総合的に見てどのクエリがどのくらい遅いのかを可視化すると良いです。上から遅い順に改善していきましょう。

統計処理をする際は percona-toolkit の pt-query-digest が役に立つでしょう。

サイボウズ版 MySQL パフォーマンスチューニングとその結果 - Cybozu Inside Out | サイボウズエンジニアのブログ 

⇧「サイボウズ」さん、「ヤフー」さん、どちらのエンジニアの方もアプローチは似てますね。

まぁ、「テーブルの結合」以外についても考えなきゃならないことは多いけども、「Nested Loop Join」が内部的に二重ループだったとは...

アプリケーション側で「ORM(Object-relational mapping)」なんかのライブラリを使ってる場合は「N+1問題」とかの対策も考えにゃならんしね...

何て言うか、考えにゃならんことが多いな...

今回はこのへんで。