私はデータベースについて調査しており、リレーショナル DB のいくつかの制限について調べています。
大きなテーブルの結合は非常にコストがかかることは理解していますが、その理由がよくわかりません。結合操作を実行するために DBMS が行う必要があることは何ですか。ボトルネックはどこにありますか。
非正規化はこのコストを克服するのにどのように役立ちますか。他の最適化手法 (たとえば、インデックス作成) はどのように役立ちますか。
個人的な体験談は大歓迎です! リソースへのリンクを投稿する場合は、Wikipedia は避けてください。Wikipedia がどこにあるかは既にわかっています。
これに関連して、BigTableやSimpleDBなどのクラウドサービスデータベースで使用されている非正規化アプローチについて疑問に思っています。この質問。
ベストアンサー1
パフォーマンスを向上させるために非正規化しますか? 説得力があるように聞こえますが、根拠がありません。
テッド・コッド博士とともにリレーショナル・データ・モデルの最初の提唱者であったクリス・デイトは、正規化に反対する誤った主張に我慢できなくなり、科学的手法を用いて体系的にそれらを打ち破りました。彼は大規模なデータベースを入手し、これらの主張をテストしました。
彼はそれをRelational Database Writings 1988-1991にまとめたと思いますが、この本は後に、データベースの理論と設計に関する決定的なテキストであるIntroduction to Database Systemsの第 6 版にまとめられました。私がこれを書いている時点では第 8 版になっており、今後数十年は印刷され続けると思われます。Chris Date は、私たちのほとんどがまだ裸足で走り回っていたころから、この分野の専門家でした。
彼は次のことを発見しました:
- いくつかは特別なケースに当てはまる
- どれも一般的な用途には役に立たない
- これらすべては、他の特殊なケースでは著しく悪化する。
結局は、ワーキング セットのサイズを緩和することにつながります。適切に選択されたキーと正しく設定されたインデックスを含む結合は、行が実現される前に結果を大幅に削減できるため、コストは高くなく、安価です。
結果の実現には、大量のディスク読み取りが伴いますが、これは桁違いにコストのかかる作業です。対照的に、結合を実行するには、論理的にはキーのみの取得が必要です。実際には、キー値さえも取得されません。キー ハッシュ値が結合比較に使用され、複数列結合のコストが軽減され、文字列比較を含む結合のコストが大幅に削減されます。キャッシュに収まる量が大幅に増えるだけでなく、ディスク読み取りも大幅に減ります。
さらに、優れたオプティマイザーは、最も制限の厳しい条件を選択し、結合を実行する前にそれを適用して、カーディナリティの高いインデックスでの結合の高い選択性を非常に効果的に活用します。
確かに、このタイプの最適化は非正規化データベースにも適用できますが、スキーマを非正規化したいタイプの人は、通常、インデックスを設定するときに（設定する場合）、カーディナリティについて考えません。
テーブル スキャン (結合を生成する過程でテーブル内のすべての行を調べること) は実際にはまれであることを理解することが重要です。クエリ オプティマイザーは、次の 1 つ以上の条件が当てはまる場合にのみテーブル スキャンを選択します。
- リレーションの行数が 200 未満の場合 (この場合、スキャンの方が安価になります)
- 結合列に適切なインデックスがありません (これらの列を結合することに意味があるのなら、なぜインデックスが付けられていないのでしょうか? 修正してください)
- 列を比較する前に型の強制変換が必要です (何だって?! 修正するか、家に帰るか) ADO.NET の問題については、END NOTE を参照してください
- 比較の引数の1つが式（インデックスなし）である
操作を実行することは、実行しないよりもコストがかかります。ただし、間違った操作を実行して、無意味なディスク I/O を強制し、本当に必要な結合を実行する前に不要なデータを破棄することは、はるかにコストがかかります。「間違った」操作が事前に計算され、インデックスが適切に適用されている場合でも、大きなペナルティが残ります。結合を事前計算するために非正規化することは、更新の異常を伴うにもかかわらず、特定の結合に対するコミットメントです。別の結合が必要な場合、そのコミットメントには大きなコストがかかります。
世の中は変化し続けているということを私に思い出させたい人がいるなら、より高性能なハードウェア上でより大きなデータセットを扱うと、Date 氏の調査結果の広がりが誇張されるだけだということに気づくだろう。
課金システムや迷惑メール生成システム (恥を知れ) に携わっている皆さん、そして非正規化の方が速いことは事実だと憤慨しながらキーボードに手を置いて私に言う皆さん、残念ですが、あなたは特殊なケースの 1 つ、具体的には、すべてのデータを順番に処理するケースに陥っています。これは一般的なケースではなく、あなたの戦略は正当です。
それを誤って一般化することは正当化されません。データ ウェアハウス シナリオでの非正規化の適切な使用の詳細については、注記セクションの最後を参照してください。
私も回答したいのですが
ジョイントはリップグロスを使った直積に過ぎない
まったくのナンセンスです。制限は可能な限り早く、最も制限の厳しいものから適用されます。理論は読んでいますが、理解していません。結合は、クエリ オプティマイザーによってのみ「述語が適用される直積」として扱われます。これは、記号分解を容易にするための記号表現 (実際には正規化) であり、オプティマイザーは同等の変換をすべて生成し、コストと選択性によってランク付けして、最適なクエリ プランを選択できます。
オプティマイザに直積を生成させる唯一の方法は、述語を指定しないことです。SELECT * FROM A,B
ノート
David Aldridge が重要な追加情報を提供しています。
実際、インデックスやテーブルスキャン以外にもさまざまな戦略があり、最新のオプティマイザーは実行プランを作成する前にそれらすべてを計算します。
実用的なアドバイス: 外部キーとして使用できる場合は、インデックスを作成して、オプティマイザーがインデックス戦略を利用できるようにします。
かつては、私は MSSQL オプティマイザーよりも賢かったのですが、2 バージョン前にそれが変わりました。今では、オプティマイザーが私に教えてくれることが多いのです。これは、非常に現実的な意味ではエキスパート システムであり、ルールベースのシステムが効果的であるほど十分に閉じられたドメインで、非常に賢い多くの人々の知恵をすべてコード化しています。
「馬鹿げた話」は無神経だったかもしれない。私はもっと傲慢にならないように、そして数学は嘘をつかないことを思い出すように求められている。これは真実だが、数学モデルの意味を必ずしもすべて文字通りに受け取る必要はない。負の数の平方根は、その不合理さを慎重に調べないようにし（しゃれだ）、方程式を解釈する前に必ずすべてを相殺すれば、非常に便利だ。
私がこれほど激しく反応した理由は、声明文に次のように書かれているからです。
結合は直積です...
これは意図されたことではないかもしれませんが、実際に書かれたもので、完全に誤りです。直積は関係です。結合は関数です。より具体的には、結合は関係値関数です。空の述語を使用すると直積が生成され、それが生成されることを確認することはデータベース クエリ エンジンの正当性チェックの 1 つですが、教室以外では実用的な価値がないため、実際には制約のない結合を書く人はいません。
私がこれを指摘したのは、読者がモデルとモデル化されたものを混同するという昔からの罠に陥ってほしくないからです。モデルは近似値であり、操作しやすいように意図的に単純化されています。
テーブルスキャン結合戦略の選択のカットオフは、データベース エンジンによって異なる場合があります。これは、ツリー ノードのフィル ファクター、キー値のサイズ、アルゴリズムの微妙な違いなど、実装上のさまざまな決定によって左右されますが、一般的に、高性能インデックスの実行時間はk log n + cです。C 項は、主にセットアップ時間で構成される固定オーバーヘッドであり、曲線の形状から、 nが数百になるまで (線形検索と比較して) メリットが得られないことがわかります。
非正規化は時には良いアイデアである
非正規化とは、特定の結合戦略へのコミットメントです。前述のように、これは他の結合戦略に干渉します。しかし、ディスク スペースが大量にあり、アクセスのパターンが予測可能で、そのほとんどまたはすべてを処理する傾向がある場合は、結合を事前計算することは非常に価値があります。
また、操作で通常使用されるアクセス パスを把握し、それらのアクセス パスのすべての結合を事前に計算することもできます。これがデータ ウェアハウスの前提であり、少なくとも、流行語に従うためだけではなく、なぜそれを実行しているかを理解している人々によって構築されている場合は前提となります。
適切に設計されたデータ ウェアハウスは、標準化されたトランザクション処理システムからの一括変換によって定期的に生成されます。操作データベースとレポート データベースを分離することで、OLTP と OLAP (オンライン トランザクション処理、つまりデータ入力とオンライン分析処理、つまりレポート) 間の衝突がなくなるという非常に望ましい効果が得られます。
ここで重要な点は、定期的な更新を除き、データ ウェアハウスは読み取り専用であるということです。これにより、更新の異常に関する問題は無意味になります。
OLTP データベース (データ入力が行われるデータベース) を非正規化するという間違いをしないでください。課金の実行は速くなるかもしれませんが、そうすると更新の異常が発生します。Reader's Digest からのメールの送信を停止しようとしたことがありますか?
最近はディスク容量が安いので、どうぞご自由にお使いください。ただし、データ ウェアハウスの場合、非正規化はほんの一部にすぎません。はるかに大きなパフォーマンスの向上は、月間合計などの事前に計算されたロールアップ値から得られます。常に重要なのは、作業セットを減らすことです。
ADO.NET の型の不一致の問題
varchar 型のインデックス付き列を含む SQL Server テーブルがあり、AddWithValue を使用してこの列のクエリを制限するパラメーターを渡すとします。C# 文字列は Unicode であるため、推定されるパラメーターの型は NVARCHAR になり、VARCHAR と一致しません。
VARCHAR から NVARCHAR への変換は拡大変換なので暗黙的に行われますが、インデックス作成は不要です。その理由を解明するのは難しいでしょう。
「ディスクヒット数を数える」（リック・ジェームス）
すべてが RAM にキャッシュされている場合、JOINsコストはかなり低くなります。つまり、正規化によるパフォーマンスの低下はそれほど大きくありません。
「正規化された」スキーマでJOINsはディスクへの書き込みが多くなるが、同等の「非正規化された」スキーマではディスクへの書き込みが不要な場合は、パフォーマンス競争では非正規化が勝ちます。
原作者からのコメント: 現代のデータベース エンジンは、結合操作中のキャッシュ ミスを最小限に抑えるためにアクセス シーケンスを整理するのに非常に優れています。上記は事実ですが、結合は大きなデータでは必ず問題となるほど高価であることを意味すると誤解される可能性があります。これは、経験の浅い開発者による不適切な意思決定につながります。