[解決済み】データベースの結合はいつ、なぜ高くつくのですか？

質問

データベースについて研究しているのですが、リレーショナルDBの制限について調べています。

大きなテーブルの結合は非常にコストがかかるということは分かったのですが、その理由がよく分かりません。DBMSは結合操作を実行するために何をする必要があるのか、ボトルネックはどこにあるのか？

非正規化は、この出費をどのように克服するのに役立つのでしょうか？他の最適化技術（例えばインデックス作成など）はどのように役立つのでしょうか？

個人の経験談も大歓迎です もし、資料のリンクを貼るのであれば、Wikipediaは避けてください。どこに何があるかはもう知っています。

これに関連して、BigTableやSimpleDBなどのクラウドサービスデータベースが採用している非正規化アプローチも気になりますね。参照 この質問 .

解決方法を教えてください。

非正規化でパフォーマンスアップ？説得力があるようでいて、説得力がない。

テッド・コッド博士と共同でリレーショナル・データ・モデルの最初の提案者であるクリス・デイトは、正規化に対する誤った情報に基づいた議論に我慢できなくなり、科学的な方法を用いてそれらを体系的に打ち破りました。 テスト という主張があります。

で書き上げたのだと思います。 リレーショナルデータベース著作集 1988-1991 の第6版に収録されました。 データベースシステム入門 である。 その データベースの理論と設計に関する決定的なテキストで、現在第8版が出版されており、今後何十年も版を重ねると思われます。クリス・デイトは、私たちの多くがまだ裸足で走りまわっていた頃、この分野の専門家でした。

彼はそれを発見したのです。

• 特殊なケースで成立するものもある
• 一般的な用途では、すべてペイできない
• その他の特殊なケースでは、いずれも大幅に悪化する

すべては、作業セットのサイズを小さくすることに帰結します。適切に選択されたキーと適切に設定されたインデックスを含む結合は、結果の大幅な刈り込みを可能にするため、高価ではなく安価です。 前に 行が実体化されます。

この結果、ディスクの一括読み込みが発生し、この処理で最もコストがかかるのは、桁外れに高い。対照的に、joinの実行では、論理的には キー . 実際には、キー値さえも取得されません。キーハッシュ値は結合の比較に使用され、複数列の結合のコストを軽減し、文字列比較を含む結合のコストを根本的に削減します。キャッシュに収まる量が大幅に増えるだけでなく、ディスクの読み込みもかなり少なくなります。

さらに、優れたオプティマイザは最も厳しい条件を選択し、それを結合を実行する前に適用します。これは、カーディナリティの高いインデックスに対する結合の高い選択性を非常に効果的に活用するためです。

確かにこの種の最適化は、非正規化されたデータベースにも適用できますが、この種の最適化を行うのは 欲しい スキーマを非正規化する場合、通常、インデックスを設定する際にカーディナリティのことは考えません（もしそうなら）。

テーブルスキャン（結合を生成する過程でテーブルのすべての行を調べること）は実際にはまれであることを理解することが重要です。クエリオプティマイザがテーブルスキャンを選択するのは、以下のうちの1つ以上が成立する場合のみです。

• リレーション内の行数が200行未満(この場合、スキャンの方が安価になる)
• 結合カラムに適切なインデックスがない（これらのカラムで結合することに意味があるのであれば、なぜインデックスがないのでしょうか？）
• カラムを比較する前に型強制が必要です (WTF?! fix it or go home) ado.netの問題については、エンドノートを参照してください。
• 比較の引数の1つが式（インデックスなし）です。

ある操作を実行すると、実行しない場合よりもコストが高くなります。しかし いけない を実行し、無意味なディスクI/Oを強いられ、本当に必要な結合を実行する前にゴミを捨てることになります。 多く より高価になります。間違った操作が事前計算され、インデックスが賢明に適用されたとしても、大きなペナルティが残ります。結合を事前計算するために非正規化することは、それに伴う更新の異常にもかかわらず、特定の結合にコミットすることになります。もし 異なる を使用する場合、そのコミットメントがコストになります。 大きい .

もし誰かが、世界は変化しているのだと私に思い出させたいなら、より不機嫌なハードウェア上のより大きなデータセットは、Dateの発見の広がりを誇張するだけだと分かると思います。

課金システムやジャンクメールジェネレータに勤めていて（恥）、非正規化の方が速いという事実を知っていると言って憤慨してキーボードを叩いている皆さん、残念ですが、あなたは特殊なケースに住んでいるのです。 すべて のデータを順番に処理します。一般的なケースではありませんし、あなたは は その戦略は正当なものです。

あなたは ではない それを誤って一般化することは正当化されます。データウェアハウスのシナリオにおける非正規化の適切な使用については、ノートセクションの最後を参照してください。

また、次のようなことにも対応したいと思います。

<ブロッククオート

ジョインはリップグロスを塗っただけのカルテシアン製品です

なんてことはない。制限はできるだけ早く、最も制限の多いものから適用される。理論を読んでも、理解できていないようですね。ジョインとは 扱われる を述語が適用されるカルテジアン積として扱います。 のみ は、クエリオプティマイザによって これは、オプティマイザが等価な変換を全て生成し、コストと選択性によってランク付けし、最適な問い合わせ計画を選択できるように、記号的な分解を容易にするための記号表現（実際には正規化）です。

オプティマイザーがカルテジアン積を生成する唯一の方法は、述語を提供しないことです。 SELECT * FROM A,B

---

注意事項

---

David Aldridgeが重要な追加情報を提供しています。

インデックスやテーブルスキャン以外にも様々な戦略があり、最新のオプティマイザは実行計画を作成する前にそれらをすべてコスト計算します。

実用的なアドバイスとして、外部キーとして使用できるのであればインデックスを作成し、インデックス戦略として 使用可能 オプティマイザーに

以前はMSSQLオプティマイザーより賢かった。それが2バージョン前に変わりました。今では一般的に 私 . ルールベースのシステムが有効なほど十分に閉じた領域で、多くの非常に賢い人々の知恵をすべてコード化した、本当の意味でのエキスパートシステムなのです。

---

Bollocks"は無粋だったかもしれませんね。数学は嘘をつかないと、高慢にならないようにと念を押されているのです。これは事実だが、数理モデルの含意のすべてが必ずしも文字通りに受け取られる必要はない。負の数の平方根は、その不条理さを慎重に検証することを避け、方程式を解釈しようとする前にそれらをすべて打ち消すことを確認すれば、非常に便利です（ダジャレです）。

私がここまで野蛮に反応した理由は、言葉通りの文言では

接合部 は デカルト積...

これは意図したものではないかもしれませんが、それは は と書かれており、断固として事実と異なる。デカルト積は関係である。結合は関数です。より具体的には、結合は関係値を持つ関数です。空の述語ではデカルト積を生成し、それをチェックすることはデータベースクエリーエンジンの1つの正しさチェックです。しかし、制約のない結合は教室の外では実用的価値がないため、実際には誰も書きません。

このように呼びかけたのは、読者がモデルとモデル化されたものを混同してしまうという古くからの罠にはまらないようにするためである。モデルとは、操作に便利なように意図的に単純化された近似値なのです。

---

テーブルスキャン結合戦略を選択するための切り口は、データベースエンジンによって異なる場合があります。これは、ツリー・ノードのフィルファクター、キーバリューのサイズ、アルゴリズムの微妙さなど、多くの実装上の決定に影響されますが、一般的に高性能なインデックス作成では、実行時間が k ログ n + c . C項は、ほとんどがセットアップ時間からなる固定オーバーヘッドで、曲線の形状から、（線形探索と比較して）以下の期間まで見返りが得られないことを意味します。 n が数百になる。

---

時には非正規化するのも良いアイデア

非正規化は、特定の結合戦略にコミットすることです。前述したように、これは その他 のジョイン戦略です。しかし、バケットのディスクスペースがあり、アクセスパターンが予測可能で、その大部分またはすべてを処理する傾向がある場合、joinを事前に計算することは非常に有意義なことです。

また、通常業務で使用するアクセスパスを把握し、そのアクセスパスのすべての結合を事前に計算することもできます。これは、データウェアハウスを構築する際の前提であり、少なくとも、バズワードの遵守のためだけでなく、なぜそのようなことをするのかを理解している人たちによって構築された場合の前提です。

適切に設計されたデータウェアハウスは、正規化されたトランザクション処理システムからの一括変換により、定期的に作成されます。このように運用データベースと報告データベースを分離することで、OLTPとOLAP（オンライントランザクション処理＝データ入力、オンライン分析処理＝報告）の間の衝突をなくすという非常に望ましい効果が得られます。

ここで重要なのは、定期的な更新を除けば、データウェアハウスは 読み取り専用 . このため、更新の異常の問題は無意味になります。

間違ってもOLTPデータベース（データ入力が行われるデータベース）の非正規化を行わないようにしましょう。課金処理は速くなるかもしれませんが、そうすると、更新の異常が発生します。Reader's Digestが送られてくるのを止めようとしたことがありますか？

最近はディスクの容量が安いので、ご自由にどうぞ。しかし、非正規化はデータウェアハウスのストーリーの一部でしかありません。もっと大きな性能向上は、事前に計算されたロールアップ値（月別の合計値など）から得られます。それは 常に 作業セットを減らすことです。

---

ADO.NETで型の不一致が発生する問題

SQL Server テーブルに varchar 型のインデックス付き列があり、AddWithValue を使用して、この列に対するクエリを制約するパラメータを渡すとします。C#の文字列はUnicodeなので、推測されるパラメータタイプはNVARCHARとなり、VARCHARと一致しません。

VARCHARからNVARCHARへの変換は、拡大変換なので、暗黙のうちに行われます。

---

ディスクヒットを数えよう（リック・ジェームス）

全てがRAMにキャッシュされている場合。 JOINs はむしろ安い。 つまり、正規化ではあまり パフォーマンス・ペナルティ .

正規化されたスキーマによって JOINs しかし、同等の "denormalized" スキーマではディスクをヒットする必要がないため、非正規化は性能競争に勝つことになります。

<ブロッククオート

原作者のコメント 最近のデータベースエンジンは、結合操作時のキャッシュミスを最小化するために、アクセスの順序を整理するのが非常にうまいです。上記は真実ですが、大規模データでは結合が必ずしも問題なく高価であることを意味するように誤解されるかもしれません。これは、経験の浅い開発者の側で誤った意思決定を引き起こすことになります。