私はデータベースについていくつかの調査を行っており、リレーショナル DB のいくつかの制限を調べています。
大きなテーブルの結合は非常にコストがかかると思いますが、その理由は完全にはわかりません。結合操作を実行するために DBMS は何をする必要がありますか?ボトルネックはどこですか?
非正規化は、この費用を克服するためにどのように役立つでしょうか? 他の最適化手法 (インデックス作成など) はどのように役立ちますか?
個人体験も大歓迎！リソースへのリンクを投稿する場合は、ウィキペディアを避けてください。私はすでにそれを見つける場所を知っています。
これに関連して、BigTable や SimpleDB などのクラウド サービス データベースで使用される非正規化アプローチについて疑問に思っています。この質問を参照してください。
パフォーマンスを向上させるために非正規化しますか？説得力があるように聞こえますが、水を保持していません。
テッドコッド博士と一緒にリレーショナルデータモデルの最初の支持者であったクリスデイトは、正規化に対する誤った情報に基づく議論で忍耐力を使い果たし、科学的方法を使用してそれらを体系的に破壊しました。彼は大規模なデータベースを取得し、これらの主張をテストしました。
彼は1988-1991年のRelationalDatabaseWritingsでそれを書いたと思いますが、この本は後にデータベース理論と設計の決定的なテキストであるデータベースシステム入門の第6版に巻き込まれ、私が書いている第8版で、今後も続く可能性があります。今後数十年にわたって印刷されます。クリス・デイトは、私たちのほとんどがまだ裸足で走り回っていたとき、この分野の専門家でした。
彼はそれを見つけました：
それはすべて、ワーキングセットのサイズを軽減することに戻ります。正しく選択されたキーと正しく設定されたインデックスを含む結合は、行が実体化される前に結果を大幅にプルーニングできるため、安価であり、高価ではありません。
結果の具体化には、演習の最も費用のかかる側面であるバルクディスク読み取りが含まれます。対照的に、結合を実行するには、論理的にはキーのみを取得する必要があります。実際には、キー値もフェッチされません。キーハッシュ値は結合の比較に使用され、複数列の結合のコストを軽減し、文字列の比較を伴う結合のコストを大幅に削減します。キャッシュにはるかに収まるだけでなく、実行するディスク読み取りがはるかに少なくなります。
さらに、優れたオプティマイザーは、最も制限の厳しい条件を選択し、結合を実行する前にそれを適用します。これにより、カーディナリティの高いインデックスでの結合の高い選択性を非常に効果的に活用できます。
確かに、このタイプの最適化は非正規化データベースにも適用できますが、スキーマを非正規化したい種類の人々は、通常、インデックスを設定するときにカーディナリティについて考えません。
テーブルスキャン（結合を生成する過程でテーブル内のすべての行を調べる）は実際にはまれであることを理解することが重要です。クエリオプティマイザーは、次の1つ以上が成立する場合にのみテーブルスキャンを選択します。
操作を実行すると、実行しないよりもコストがかかります。ただし、間違った操作を実行し、無意味なディスクI / Oに強制されてから、本当に必要な結合を実行する前にドロスを破棄すると、はるかにコストがかかります。「間違った」操作が事前に計算され、インデックスが適切に適用されている場合でも、重大なペナルティが残ります。結合を事前計算するための非正規化は、更新の異常が伴うにもかかわらず、特定の結合へのコミットメントです。別の参加が必要な場合、そのコミットメントはあなたに大きなコストをかけることになります。
変化する世界であることを誰かに思い出させたいのであれば、より大きなハードウェア上のより大きなデータセットは、Dateの調査結果の広がりを誇張していることに気付くと思います。
課金システムや迷惑メールジェネレーター（恥ずかしい）に取り組んでいて、非正規化の方が速いという事実を知っていることを私に伝えるために憤慨してキーボードに手を設定しているすべての人にとって、申し訳ありませんが、あなたは特別なものの1つに住んでいますケース-具体的には、すべてのデータを順番に処理する場合。それは一般的なケースではなく、あなたはあなたの戦略において正当化されます。
あなたはそれを誤って一般化することは正当化されません。データウェアハウジングシナリオでの非正規化の適切な使用の詳細については、注記セクションの最後を参照してください。
返信したいのですが
結合は、リップグロスを備えた単なるデカルト積です。
なんてたくさんのbollocks。制限はできるだけ早く適用され、最も制限が最初に適用されます。あなたは理論を読みましたが、それを理解していません。結合は、クエリオプティマイザーによってのみ「述語が適用されるデカルト積」として扱われます。これは、シンボリック分解を容易にするシンボリック表現（実際には正規化）であるため、オプティマイザーは同等の変換をすべて生成し、コストと選択性でランク付けして、最適なクエリプランを選択できます。
オプティマイザーにデカルト積を生成させる唯一の方法は、述語の提供に失敗することです。SELECT * FROM A,B
David Aldridgeは、いくつかの重要な追加情報を提供しています。
実際、インデックスとテーブルスキャン以外にもさまざまな戦略があり、最新のオプティマイザーは実行プランを作成する前にそれらすべてにコストをかけます。
実用的なアドバイス：外部キーとして使用できる場合は、インデックスを作成して、オプティマイザーがインデックス戦略を利用できるようにします。
以前は、MSSQLオプティマイザーよりも賢いものでした。それは2つのバージョン前に変更されました。今では一般的に教えてくれます。それは、非常に現実的な意味で、エキスパートシステムであり、ルールベースのシステムが効果的であるほど十分に閉じられたドメイン内の多くの非常に賢い人々のすべての知恵を成文化しています。
「Bollocks」は無知だったかもしれません。私は傲慢ではないように頼まれ、数学は嘘をつかないことを思い出させます。これは真実ですが、数学モデルのすべての意味が必ずしも文字通りに解釈されるべきではありません。負の数の平方根は、それらの不条理を注意深く調べることを避け（そこでしゃれ）、方程式を解釈しようとする前にそれらをすべてキャンセルすることを気にしない場合に非常に便利です。
私がとても野蛮に答えた理由は、言葉通りの声明が次のように言っているからです
結合はデカルト積です...
これは意図されたものではないかもしれませんが、書かれたものであり、断固として真実ではありません。デカルト積は関係です。結合は関数です。より具体的には、結合は関係値関数です。空の述語を使用すると、デカルト積が生成されます。これをチェックすることは、データベースクエリエンジンの1つの正しさチェックですが、教室の外では実用的な価値がないため、実際には制約のない結合を記述しません。
読者がモデルとモデル化されたものを混同するという古代の罠に陥ってほしくないので、私はこれを呼びました。モデルは近似値であり、操作を便利にするために意図的に簡略化されています。
テーブルスキャン結合戦略の選択のカットオフは、データベースエンジンによって異なる場合があります。これは、ツリーノードのフィルファクター、キー値のサイズ、アルゴリズムの微妙さなど、多くの実装上の決定の影響を受けますが、大まかに言えば、高性能インデックスの実行時間はk log n + cです。C項は、主にセットアップ時間で構成される固定オーバーヘッドであり、曲線の形状は、 nが数百になるまで（線形検索と比較して）見返りが得られないことを意味します。
非正規化は、特定の参加戦略への取り組みです。前述のように、これは他の結合戦略を妨害します。ただし、ディスクスペースのバケット、予測可能なアクセスパターン、およびその大部分またはすべてを処理する傾向がある場合は、結合を事前に計算することは非常に価値があります。
また、操作で通常使用されるアクセスパスを把握し、それらのアクセスパスのすべての結合を事前計算することもできます。これはデータウェアハウスの背後にある前提です。少なくとも、流行語に準拠するためだけでなく、自分がやっていることをなぜやっているのかを知っている人々によって構築されている場合です。
適切に設計されたデータウェアハウスは、正規化されたトランザクション処理システムからの一括変換によって定期的に生成されます。オペレーションとレポートデータベースのこの分離は、OLTPとOLAPの間の衝突を排除するという非常に望ましい効果をもたらします（オンライントランザクション処理、つまりデータ入力、およびオンライン分析処理、つまりレポート）。
ここで重要な点は、定期的な更新とは別に、データウェアハウスは読み取り専用であるということです。これにより、更新の異常の問題が浮き彫りになります。
OLTPデータベース（データ入力が行われるデータベース）の非正規化を間違えないでください。請求の実行は高速になる可能性がありますが、そうすると更新の異常が発生します。リーダーズダイジェストにあなたに物を送るのをやめさせようとしたことがありますか？
最近のディスク容量は安いので、ノックアウトしてください。しかし、非正規化はデータウェアハウスの話の一部にすぎません。事前に計算されたロールアップ値、つまり月間合計などから、はるかに大きなパフォーマンスの向上が得られます。それは常にワーキングセットを減らすことです。
varchar型のインデックス付き列を含むSQLServerテーブルがあり、AddWithValueを使用して、この列のクエリを制約するパラメーターを渡すとします。C＃文字列はUnicodeであるため、推測されるパラメータタイプはNVARCHARになりますが、これはVARCHARとは一致しません。
VARCHARからNVARCHARへの変換は拡大するため、暗黙的に発生しますが、インデックス作成に別れを告げ、その理由を理解してください。
すべてがRAMにキャッシュされている場合は、JOINsかなり安価です。つまり、正規化にはパフォーマンスの低下はあまりありません。
「正規化された」スキーマによってJOINsディスクが頻繁にヒットするが、同等の「非正規化された」スキーマがディスクにヒットする必要がない場合、非正規化はパフォーマンスの競争に勝ちます。
元の作成者からのコメント：最新のデータベースエンジンは、アクセスシーケンスを整理して、結合操作中のキャッシュミスを最小限に抑えるのに非常に優れています。上記は真実ですが、結合が大規模なデータでは必然的に問題のあるコストがかかることを意味すると誤解される可能性があります。これは、経験の浅い開発者の意思決定の質を低下させることにつながります。
ほとんどのコメント提供者が気付かないのは、複雑なRDBMSで利用できる幅広い結合方法論であり、非正規化機能は、非正規化データを維持するためのより高いコストを常に覆い隠します。すべての結合がインデックスに基づいているわけではありません。データベースには、結合コストを削減することを目的とした、結合のための最適化されたアルゴリズムと方法論が多数あります。
いずれにせよ、結合のコストはそのタイプと他のいくつかの要因に依存します。高価である必要はまったくありません-いくつかの例。
データベースは参加するように設計されており、参加方法に非常に柔軟性があり、参加メカニズムを間違えない限り、一般的に非常にパフォーマンスが高くなります。
質問全体が誤った前提に基づいていると思います。大きなテーブルでの結合は必ずしも高価ではありません。実際、結合を効率的に行うことは、リレーショナル データベースが存在する主な理由の 1 つです。大規模なセットでの結合は多くの場合コストがかかりますが、大規模なテーブル A の内容全体を大規模なテーブル B の内容全体と結合することはほとんどありません。代わりに、各テーブルの重要な行のみが使用され、結合によって保持される実際のセットは小さいままです。
さらに、最終的な結果セットが具体化されるまで、各レコードの重要な部分のみをメモリに保持する必要があるなど、Peter Wone によって言及された効率性があります。また、多くの結合を伴う大規模なクエリでは、通常、小さなテーブル セットから始めて、大きなテーブル セットに徐々に移行していき、メモリ内に保持されるセットが可能な限り小さく保たれるようにします。
適切に行われた場合、結合は通常、大量のデータを比較、結合、またはフィルター処理するための最良の方法です。
ボトルネックはほぼ常にディスク I/O であり、さらに具体的には、ランダム ディスク I/O です (比較すると、シーケンシャル読み取りはかなり高速であり、先読み戦略でキャッシュできます)。
結合により、ランダム シークが増加する可能性があります。大きなテーブルの小さな部分を読み込んでいる場合です。しかし、クエリ オプティマイザーはそれを探し、それがより良いと思われる場合は、それを順次テーブル スキャン (不要な行を破棄する) に変えます。
単一の非正規化テーブルにも同様の問題があります。行が大きいため、単一のデータ ページには収まりません。別の行から離れた場所にある行が必要な場合 (行のサイズが大きいため、行がさらに離れている場合)、より多くのランダム I/O が発生します。この場合も、これを回避するためにテーブル スキャンが強制される場合があります。ただし、今回は、行サイズが大きいため、テーブル スキャンでより多くのデータを読み取る必要があります。それに加えて、1 つの場所から複数の場所にデータをコピーしているという事実があり、RDBMS にはさらに多くの読み取り (およびキャッシュ) が必要です。
2 つのテーブルを使用すると、2 つのクラスター化されたインデックスも取得できます。また、通常は (挿入/更新のオーバーヘッドが少ないため) より多くのインデックスを作成できます。これにより、パフォーマンスが大幅に向上します (主に、インデックスが (比較的) 小さく、ディスクからすばやく読み取ることができるため)。 （またはキャッシュするのが安価です）、ディスクから読み取る必要があるテーブル行の量を減らします）。
結合による唯一のオーバーヘッドは、一致する行を見つけることです。Sql Server は、主にデータセットのサイズに基づいて、3 つの異なるタイプの結合を使用して、一致する行を見つけます。オプティマイザーが間違った結合タイプを選択すると (不正確な統計、不十分なインデックス、またはオプティマイザーのバグやエッジ ケースが原因で)、クエリ時間に大幅に影響する可能性があります。
最適なケースでは、これらはディスク I/O を引き起こさないため、パフォーマンスの観点からは無視できます。
全体として、最悪の場合、x 結合テーブルから同じ量の論理データを読み取る方が、ディスクの読み取りが少ないため、単一の非正規化テーブルから読み取る場合と同じように、実際には高速になるはずです。同じ量の物理データを読み取るには、わずかなオーバーヘッドが発生する可能性があります。
通常、クエリ時間は I/O コストによって支配され、データのサイズは非正規化によって変化しないため (ごくわずかな行のオーバーヘッドを差し引いて)、テーブルをマージするだけでは大きなメリットはありません。パフォーマンスを向上させる傾向がある非正規化のタイプである IME は、計算に必要な 10,000 行を読み取るのではなく、計算された値をキャッシュします。
テーブルを結合する順序は非常に重要です。2 つのデータ セットがある場合は、最小のデータ セットが最初に使用され、クエリが処理する必要があるデータの量を減らす方法でクエリを作成してみてください。
データベースによっては問題にならないものもあります。たとえば、MS SQL はほとんどの場合、適切な結合順序を知っています。一部 (IBM Informix など) では、順序によってすべてが異なります。
結合の複雑さのクラスを考慮すると、非正規化するか正規化するかを決定するのはかなり簡単なプロセスです。たとえば、クエリが O(k log n) である場合、正規化を使用してデータベースを設計する傾向があります。ここで、k は目的の出力の大きさに関連しています。
非正規化してパフォーマンスを最適化する簡単な方法は、正規化構造への変更が非正規化構造にどのように影響するかを考えることです。ただし、非正規化された構造で機能するにはトランザクションロジックが必要になる場合があるため、問題が発生する可能性があります。
問題が膨大であるため、正規化と非正規化の議論は終わりません。自然な解決策が両方のアプローチを必要とする多くの問題があります。
原則として、再構築可能な正規化された構造と非正規化されたキャッシュを常に保存してきました。最終的に、これらのキャッシュは私のお尻を救い、将来の正規化の問題を解決します.
他の人が言ったことを詳しく説明すると、
ジョインは、リップグロスを含む単なるデカルト積です。{1,2,3,4}X{1,2,3} は 12 通りの組み合わせ (nXn=n^2) になります。この計算されたセットは、条件が適用される基準として機能します。DBMS は条件 (左と右の両方が 2 または 3 の場合など) を適用して、一致する条件を提供します。実際にはより最適化されていますが、問題は同じです。セットのサイズを変更すると、結果のサイズが指数関数的に増加します。消費されるメモリ量と CPU サイクルはすべて、指数関数的に影響を受けます。
非正規化するとき、この計算を完全に回避します。本のすべてのページに色付きの付箋を添付することを考えてください。参照を使用せずに情報を推測できます。私たちが支払う代償は、DBMS の本質 (データの最適な編成) を損なうことです。