データベースの結合はいつ、なぜ高価ですか？

StackOverflow https://stackoverflow.com/questions/173726

質問

データベースの調査を行っており、リレーショナルDBの制限を調べています。

大きなテーブルの結合は非常に高価であることがわかりましたが、その理由は完全にはわかりません。結合操作を実行するためにDBMSで必要なことは何ですか？
非正規化はこの費用を克服するのにどのように役立ちますか？他の最適化手法（インデックス作成など）はどのように役立ちますか？

個人的な経験は大歓迎です！リソースへのリンクを投稿する場合は、ウィキペディアを避けてください。どこにあるかはすでにわかっています。

これに関連して、BigTableやSimpleDBなどのクラウドサービスデータベースで使用されている非正規化アプローチについて疑問に思っています。 この質問を参照してください。

役に立ちましたか？

解決

パフォーマンスを改善するための非正規化？説得力があるように聞こえますが、水を保持しません。

Ted Codd博士と協力してリレーショナルデータモデルの最初の支持者だったクリスデイトは、正規化に対する誤った情報に基づく議論に忍耐を失い、科学的手法を使用して体系的に破壊しました：彼は大規模なデータベースを取得し、テストこれらのアサーション。

彼はそれを Relational Database Writings 1988-1991 に書いたと思いますが、この本は後に Introduction to Database Systems の第6版、データベースの理論と設計に関する最終的なテキスト。第8版の執筆時であり、今後数十年間は印刷され続ける可能性があります。私たちのほとんどがまだ裸足で走り回っていた頃、クリス・デイトはこの分野のエキスパートでした。

彼はそれを見つけました：

  • それらのいくつかは特別な場合のために保持します
  • それらのすべては、一般的な使用に対する支払いに失敗します
  • それらのすべては、他の特殊なケースでは著しく悪いです

すべては、ワーキングセットのサイズを緩和することに帰着します。正しく設定されたインデックスを使用して適切に選択されたキーを含む結合は、行が具体化される前に結果を大幅に削除できるため、安価で高価ではありません。

結果を具体化するには、バルクディスク読み取りが必要です。これは、演習で最もコストのかかる側面です。対照的に、結合を実行するには、論理的に keys のみを取得する必要があります。実際には、キー値さえもフェッチされません。キーハッシュ値は結合比較に使用され、複数列結合のコストを軽減し、文字列比較を含む結合のコストを根本的に削減します。キャッシュに大幅に収まるだけでなく、実行するディスク読み取りがはるかに少なくなります。

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

確かにこのタイプの最適化は非正規化されたデータベースにも適用できますが、スキーマを非正規化したい 人は通常、インデックスを設定する場合にカーディナリティを考慮しません。

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

  • リレーションに含まれる行は200未満です（この場合、スキャンのほうが安くなります）
  • 結合列に適切なインデックスがありません（これらの列で結合することが意味がある場合、なぜインデックス化されないのですか？修正してください）
  • 列を比較するには、型強制が必要です（WTF ?!修正するか、家に帰ります） ADO.NETの問題に関する注を参照
  • 比較の引数の1つは式（インデックスなし）です

操作の実行は、実行しないよりもコストがかかります。ただし、間違った操作を実行し、無意味なディスクI / Oを強制し、本当に必要な結合を実行する前にドロスを破棄することは、はるかに高価です。 「間違った」ときでも操作は事前に計算され、インデックスが適切に適用されているため、重大なペナルティが残っています。結合を事前計算するための非正規化は、更新の異常を伴うにもかかわらず、特定の結合へのコミットメントです。 別の参加が必要な場合、そのコミットメントには大きな費用がかかります。

世界が変化していることを思い出したい場合は、グルニエハードウェア上のより大きなデータセットがDateの結果の広がりを誇張していることに気付くでしょう。

請求システムまたは迷惑メールジェネレーターで働いており（恥ずかしい）キーボードにtoして手を置いて、あなたがf非正規化の方が速い、申し訳ありませんが、特別なケースの1つ、具体的には、データのすべてを順番に処理するケースに住んでいます。それは一般的なケースではなく、あなたはあなたの戦略において 正当化されます。

あなたは誤って一般化することを 正当化されていません。データウェアハウジングシナリオでの非正規化の適切な使用の詳細については、メモセクションの最後を参照してください。

私も返信したい

  

結合は、リップグロスを含む単なるデカルト製品です

大量の塊。制限はできるだけ早く適用され、最も制限の厳しいものが最初に適用されます。あなたは理論を読みましたが、あなたはそれを理解していません。結合は、「述語が適用されるデカルト積」として処理されます。クエリオプティマイザーによるのみ。これは、シンボリック分解を促進するシンボリック表現（実際には正規化）であるため、オプティマイザーは同等の変換をすべて生成し、コストと選択性によってランク付けできるため、最適なクエリプランを選択できます。

最適化プログラムを使用してデカルト積を生成する唯一の方法は、述語を指定しないことです： SELECT * FROM A、B

注意事項

David Aldridgeは、いくつかの重要な追加情報を提供しています。

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

実用的なアドバイス：外部キーとして使用できる場合はインデックスを作成し、オプティマイザーがインデックス戦略を利用できるようにします。

以前は、MSSQLオプティマイザーよりもスマートでした。それは2バージョン前に変更されました。現在では、一般的に私を教えています。非常に現実的な意味でのエキスパートシステムであり、ルールに基づいたシステムが有効であるほど十分に閉じられたドメイン内の多くの非常に賢い人々のすべての知恵を成文化します。

＆quot;ボロックス＆quot;無傷だったかもしれません。私はあまりless慢にならないように頼まれ、数学は嘘をつかないことを思い出した。これは事実ですが、数学的モデルのすべての意味を必ずしも文字通りに解釈する必要はありません。負の数の平方根は、不条理を慎重に調べることを避け（そこにしゃれ）、方程式を解釈する前にそれらをすべて取り消すことを確認する場合に非常に便利です。

私が非常に野respondに答えた理由は、言葉で述べられている文がそれを言っているからです

  

結合は デカルト積です...

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

これを呼び出したのは、読者がモデルとモデル化されたものを混同するという古代のtrapに陥ることを望まないからです。モデルは、便利な操作のために意図的に簡略化された近似です。

テーブルスキャン結合戦略の選択のカットオフは、データベースエンジンによって異なる場合があります。ツリーノードのフィルファクター、キー値のサイズ、アルゴリズムの微妙さなど、多くの実装の決定の影響を受けますが、大まかに言って、高性能な索引付けの実行時間は k log n + c 。 C項は、ほとんどがセットアップ時間で構成される固定オーバーヘッドであり、曲線の形状は、 n が数百になるまで（線形検索と比較して）利益を得られないことを意味します。

非正規化が時々良いアイデアです

非正規化は、特定の結合戦略へのコミットメントです。言及したように

他のヒント

ほとんどのコメンターが注意を怠っているのは、複雑なRDBMSで利用可能な幅広い結合方法論であり、非正規化者は非正規化データの維持コストが高いことを常に示しています。すべての結合がインデックスに基づいているわけではなく、データベースには、結合コストを削減することを目的とした、最適化された多くのアルゴリズムと結合方法があります。

いずれの場合でも、結合のコストはそのタイプといくつかの他の要因に依存します。それはまったく高価である必要はありません-いくつかの例。

  • ハッシュ結合は、バルクデータが等価結合されているため、非常に安価であり、ハッシュテーブルをメモリにキャッシュできない場合にのみコストが大きくなります。インデックスは不要です。結合されたデータセット間の等分割は大きな助けになります。
  • ソート/マージ結合のコストは、マージではなくソートのコストに左右されます。インデックスベースのアクセス方法では、ソートのコストを事実上排除できます。
  • インデックスのネストされたループ結合のコストは、bツリーインデックスの高さとテーブルブロック自体のアクセスによって決まります。高速ですが、一括結合には適していません。
  • クラスターに基づくネストされたループ結合は、結合行ごとに必要な論理IOが少なく、はるかに安価です。結合テーブルが両方とも同じクラスター内にある場合、結合行のコロケーションによって結合は非常に安くなります。

データベースは結合するように設計されており、結合方法が非常に柔軟であり、結合メカニズムが間違っていない限り、一般に非常にパフォーマンスが高くなります。

質問全体が誤った前提に基づいていると思います。大きなテーブルでの結合は、必ずしも高価ではありません 。実際、結合を効率的に行うことが、リレーショナルデータベースが存在する主な理由の1つです。大規模な sets の結合は多くの場合高価ですが、大規模なテーブルAのコンテンツ全体を大規模なテーブルBのコンテンツ全体に結合することはほとんどありません。代わりに、各テーブルの重要な行のみが使用され、結合によって保持される実際のセットは小さくなります。

さらに、最終結果セットが具体化されるまで、各レコードの重要な部分だけをメモリに格納する必要があるように、Peter Woneが述べた効率性があります。また、多くの結合を含む大規模なクエリでは、通常、小さなテーブルセットから始めて、大きなテーブルセットまで処理して、メモリ内に保持されるセットが可能な限り小さくなるようにします。

適切に行われた場合、結合は通常、大量のデータを比較、結合、またはフィルタリングするための最良の方法です。

ボトルネックはほとんど常にディスクI / Oであり、さらに具体的にはランダムディスクI / Oです（比較すると、順次読み取りはかなり高速で、先読み戦略でキャッシュできます）。

Joinsは、ランダムなシークを増加させることができます-大きなテーブルの小さな部分を読み回っている場合。しかし、クエリオプティマイザーはそれを探し、それがより良いと思う場合は、シーケンシャルテーブルスキャンに変換します（不要な行を破棄します）。

単一の非正規化テーブルにも同様の問題があります-行が大きいため、単一のデータページに収まりません。別の行から遠く離れた行が必要な場合（および行サイズが大きいと行がさらに離れます）、よりランダムなI / Oが発生します。繰り返しますが、これを避けるためにテーブルスキャンが強制される場合があります。ただし、今回は、行サイズが大きいため、テーブルスキャンでより多くのデータを読み取る必要があります。さらに、単一の場所から複数の場所にデータをコピーしているという事実に加えて、RDBMSにはさらに多くの読み取り（およびキャッシュ）があります。

2つのテーブルを使用すると、2つのクラスター化インデックスも取得できます。また、一般的に（挿入/更新のオーバーヘッドが少ないため）より多くのインデックスを作成でき、パフォーマンスが大幅に向上します（主に、インデックスが（比較的）小さく、ディスクから読み取る（またはキャッシュが安価）、ディスクから読み取る必要があるテーブル行の量を減らす）。

結合の唯一のオーバーヘッドについては、一致する行を把握することから来ます。 SQL Serverは、主にデータセットサイズに基づいて3種類の結合を使用して、一致する行を見つけます。オプティマイザーが誤った結合タイプを選択した場合（不正確な統計、不適切なインデックス、またはオプティマイザーのバグまたはエッジケースのため）、クエリ時間に大きな影響を与える可能性があります。

  • （少なくとも1つの）小さなデータセットの場合、ループ結合は非常に安価です。
  • マージ結合では、最初に両方のデータセットの並べ替えが必要です。ただし、索引付けされた列で結合する場合、索引はすでにソートされているため、追加の作業は必要ありません。そうしないと、ソート時にCPUとメモリのオーバーヘッドが発生します。
  • ハッシュ結合には、メモリ（ハッシュテーブルを格納するため）とCPU（ハッシュを構築するため）の両方が必要です。繰り返しになりますが、これはディスクI / Oに関してはかなり高速です。 ただし、ハッシュテーブルを格納するのに十分なRAMがない場合、SQL Serverはtempdbを使用してハッシュテーブルの一部と見つかった行を格納し、ハッシュテーブルの一部のみを一度に処理します。すべてのディスクと同様に、これはかなり遅いです。

最適な場合、これらはディスク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（データの最適な編成）の本質を侵害していることです

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top