Ich recherchiere in Datenbanken und untersuche einige Einschränkungen relationaler DBs.
Ich bekomme, dass das Verknüpfen großer Tabellen sehr teuer ist, aber ich bin mir nicht ganz sicher, warum. Was muss das DBMS tun, um eine Verknüpfungsoperation auszuführen? Wo liegt der Engpass?
Wie kann die Denormalisierung helfen, diese Kosten zu überwinden? Wie helfen andere Optimierungstechniken (z. B. Indizierung)?
Persönliche Erfahrungen sind willkommen! Wenn Sie Links zu Ressourcen veröffentlichen möchten, vermeiden Sie bitte Wikipedia. Ich weiß schon, wo ich das finde.
In diesem Zusammenhang wundere ich mich über die denormalisierten Ansätze von Cloud-Service-Datenbanken wie BigTable und SimpleDB. Siehe diese Frage .
FOREGIN KEY
s FFS) zum weltweit beliebtesten "R" -DBMS (und blieb es auch), als es von PostgreSQL (keine native Windows-Version) und Firebird (Opensourcing-Fiasko) konkurrierte. oder sogar SQLite?Antworten:
Denormalisieren, um die Leistung zu verbessern? Es klingt überzeugend, hält aber kein Wasser.
Chris Date, der in Zusammenarbeit mit Dr. Ted Codd der ursprüngliche Befürworter des relationalen Datenmodells war, hatte keine Geduld mehr mit falsch informierten Argumenten gegen die Normalisierung und zerstörte sie systematisch mit wissenschaftlichen Methoden: Er erhielt große Datenbanken und testete diese Behauptungen.
Ich denke, er hat es 1988-1991 in Relational Database Writings geschrieben, aber dieses Buch wurde später in der sechsten Ausgabe von Introduction to Database Systems , dem endgültigen Text zu Datenbanktheorie und -design, in der achten Ausgabe, während ich schreibe und wahrscheinlich bleiben werde, gerollt seit Jahrzehnten im Druck. Chris Date war ein Experte auf diesem Gebiet, als die meisten von uns noch barfuß herumliefen.
Er fand das:
Es kommt alles darauf zurück, die Größe des Arbeitssatzes zu verringern. Verknüpfungen mit richtig ausgewählten Schlüsseln mit korrekt eingerichteten Indizes sind billig und nicht teuer, da sie eine erhebliche Bereinigung des Ergebnisses ermöglichen, bevor die Zeilen materialisiert werden.
Um das Ergebnis zu erzielen, werden Bulk-Disk-Reads durchgeführt, die um eine Größenordnung den teuersten Aspekt der Übung darstellen. Das Durchführen eines Joins erfordert dagegen logischerweise das Abrufen nur der Schlüssel . In der Praxis werden nicht einmal die Schlüsselwerte abgerufen: Die Schlüssel-Hash-Werte werden für Verknüpfungsvergleiche verwendet, wodurch die Kosten für mehrspaltige Verknüpfungen gesenkt und die Kosten für Verknüpfungen mit Zeichenfolgenvergleichen radikal gesenkt werden. Es passt nicht nur wesentlich besser in den Cache, es muss auch viel weniger Festplatten gelesen werden.
Darüber hinaus wählt ein guter Optimierer die restriktivste Bedingung aus und wendet sie an, bevor er eine Verknüpfung ausführt, wobei die hohe Selektivität von Verknüpfungen für Indizes mit hoher Kardinalität sehr effektiv genutzt wird.
Zwar kann diese Art der Optimierung auch auf denormalisierte Datenbanken angewendet werden, aber die Art von Personen, die ein Schema denormalisieren möchten , denken normalerweise nicht an die Kardinalität, wenn sie Indizes einrichten.
Es ist wichtig zu verstehen, dass Tabellenscans (Prüfung jeder Zeile in einer Tabelle im Verlauf der Erstellung eines Joins) in der Praxis selten sind. Ein Abfrageoptimierer wählt einen Tabellenscan nur dann aus, wenn eine oder mehrere der folgenden Bedingungen erfüllt sind.
Das Ausführen einer Operation ist teurer als das Nichtausführen. Es ist jedoch viel teurer , die falsche Operation auszuführen, in sinnlose Festplatten-E / A gezwungen zu werden und dann die Krätze zu verwerfen, bevor die wirklich benötigte Verknüpfung ausgeführt wird . Selbst wenn die "falsche" Operation vorberechnet wird und Indizes sinnvoll angewendet wurden, bleibt eine erhebliche Strafe bestehen. Die Denormalisierung zur Vorberechnung eines Joins ist - ungeachtet der damit verbundenen Aktualisierungsanomalien - eine Verpflichtung zu einem bestimmten Join. Wenn Sie einen benötigen unterschiedliche beitreten möchte, wird das Engagement Sie kosten groß .
Wenn mich jemand daran erinnern möchte, dass sich die Welt verändert, werden Sie feststellen, dass größere Datensätze auf grunzenderer Hardware die Verbreitung der Ergebnisse von Date nur übertreiben.
Für alle, die an Abrechnungssystemen oder Junk-Mail-Generatoren arbeiten (Schande über Sie) und empört die Hand auf die Tastatur legen, um mir zu sagen, dass Sie sicher wissen, dass die Denormalisierung schneller ist, tut mir leid, aber Sie leben in einem der besonderen Bereiche Fälle - insbesondere der Fall, in dem Sie alle Daten der Reihe nach verarbeiten. Es ist kein allgemeiner Fall, und Sie sind in Ihrer Strategie gerechtfertigt.
Sie sind nicht berechtigt, dies fälschlicherweise zu verallgemeinern. Weitere Informationen zur angemessenen Verwendung der Denormalisierung in Data Warehousing-Szenarien finden Sie am Ende des Anhangs.
Ich würde auch gerne antworten
Was für eine Menge Blödsinn. Einschränkungen werden so früh wie möglich angewendet, am restriktivsten zuerst. Sie haben die Theorie gelesen, aber nicht verstanden. Joins werden behandelt wie „kartesische Produkte , auf die Prädikate gelten“ nur durch die Abfrage - Optimierer. Dies ist eine symbolische Darstellung (tatsächlich eine Normalisierung), um die symbolische Zerlegung zu erleichtern, damit der Optimierer alle äquivalenten Transformationen erzeugen und sie nach Kosten und Selektivität ordnen kann, um den besten Abfrageplan auszuwählen.
Die einzige Möglichkeit, den Optimierer jemals dazu zu bringen, ein kartesisches Produkt herzustellen, besteht darin, kein Prädikat anzugeben:
SELECT * FROM A,B
Anmerkungen
David Aldridge bietet einige wichtige zusätzliche Informationen.
Neben Indizes und Tabellenscans gibt es in der Tat eine Vielzahl anderer Strategien, und ein moderner Optimierer kostet sie alle, bevor ein Ausführungsplan erstellt wird.
Ein praktischer Ratschlag: Wenn es als Fremdschlüssel verwendet werden kann, indizieren Sie es, damit dem Optimierer eine Indexstrategie zur Verfügung steht.
Früher war ich schlauer als der MSSQL-Optimierer. Das hat sich vor zwei Versionen geändert. Jetzt lehrt es mich allgemein . Es ist im wahrsten Sinne des Wortes ein Expertensystem, das die gesamte Weisheit vieler sehr kluger Leute in einem Bereich kodifiziert, der so geschlossen ist, dass ein regelbasiertes System effektiv ist.
"Bollocks" war möglicherweise taktlos. Ich werde gebeten, weniger hochmütig zu sein und daran erinnert, dass Mathe nicht lügt. Dies ist wahr, aber nicht alle Implikationen mathematischer Modelle sollten unbedingt wörtlich genommen werden. Quadratwurzeln negativer Zahlen sind sehr praktisch, wenn Sie sorgfältig vermeiden, ihre Absurdität zu untersuchen (Wortspiel dort) und verdammt sicher sind, dass Sie sie alle aufheben, bevor Sie versuchen, Ihre Gleichung zu interpretieren.
Der Grund, warum ich so wild geantwortet habe, war, dass die formulierte Aussage dies besagt
Dies ist vielleicht nicht das, was gemeint war, aber es ist das, was geschrieben wurde, und es ist kategorisch falsch. Ein kartesisches Produkt ist eine Beziehung. Ein Join ist eine Funktion. Insbesondere ist ein Join eine Funktion mit Beziehungswert. Mit einem leeren Prädikat wird ein kartesisches Produkt erstellt, und die Überprüfung ist eine Korrektheitsprüfung für eine Datenbankabfrage-Engine. In der Praxis schreibt jedoch niemand ungezwungene Verknüpfungen, da sie außerhalb eines Klassenzimmers keinen praktischen Wert haben.
Ich habe das gerufen, weil ich nicht möchte, dass Leser in die alte Falle geraten, das Modell mit dem Modell zu verwechseln. Ein Modell ist eine Annäherung, die zur bequemen Manipulation bewusst vereinfacht wurde.
Der Grenzwert für die Auswahl einer Table-Scan-Join-Strategie kann zwischen den Datenbankmodulen variieren. Es wird von einer Reihe von Implementierungsentscheidungen wie dem Baumknoten-Füllfaktor, der Schlüsselwertgröße und den Feinheiten des Algorithmus beeinflusst, aber im Großen und Ganzen hat die Hochleistungsindizierung eine Ausführungszeit von k log n + c . Der C-Term ist ein fester Overhead, der hauptsächlich aus der Einrichtungszeit besteht, und die Form der Kurve bedeutet, dass Sie keine Auszahlung (im Vergleich zu einer linearen Suche) erhalten, bis n in den Hunderten liegt.
Manchmal ist eine Denormalisierung eine gute Idee
Denormalisierung ist eine Verpflichtung zu einer bestimmten Join-Strategie. Wie bereits erwähnt, beeinträchtigt dies andere Join-Strategien. Wenn Sie jedoch über genügend Speicherplatz, vorhersehbare Zugriffsmuster und die Tendenz verfügen, viel oder alles davon zu verarbeiten, kann es sich sehr lohnen, einen Join vorab zu berechnen.
Sie können auch die Zugriffspfade ermitteln, die Ihre Operation normalerweise verwendet, und alle Verknüpfungen für diese Zugriffspfade vorberechnen. Dies ist die Voraussetzung für Data Warehouses, oder zumindest, wenn sie von Personen erstellt werden, die wissen, warum sie das tun, was sie tun, und nicht nur, um die Einhaltung von Schlagworten zu gewährleisten.
Ein ordnungsgemäß entworfenes Data Warehouse wird regelmäßig durch eine Massentransformation aus einem normalisierten Transaktionsverarbeitungssystem erstellt. Diese Trennung der Betriebs- und Berichtsdatenbanken hat den sehr wünschenswerten Effekt, dass der Konflikt zwischen OLTP und OLAP (Online-Transaktionsverarbeitung, dh Dateneingabe, und Online-Analyseverarbeitung, dh Berichterstellung) beseitigt wird.
Ein wichtiger Punkt hierbei ist, dass das Data Warehouse neben den regelmäßigen Aktualisierungen schreibgeschützt ist . Dies wirft die Frage nach Aktualisierungsanomalien auf.
Machen Sie nicht den Fehler, Ihre OLTP-Datenbank (die Datenbank, in der die Dateneingabe erfolgt) zu denormalisieren. Es kann für Abrechnungsläufe schneller sein, aber wenn Sie dies tun, erhalten Sie Aktualisierungsanomalien. Haben Sie jemals versucht, Reader's Digest dazu zu bringen, Ihnen keine Sachen mehr zu schicken?
Speicherplatz ist heutzutage billig, also schlagen Sie sich aus. Die Denormalisierung ist jedoch nur ein Teil der Geschichte für Data Warehouses. Viel größere Leistungssteigerungen ergeben sich aus vorberechneten aufgerollten Werten: monatliche Summen, so etwas. Es geht immer darum, den Arbeitssatz zu reduzieren.
ADO.NET-Problem mit Typinkongruenzen
Angenommen, Sie haben eine SQL Server-Tabelle mit einer indizierten Spalte vom Typ varchar und verwenden AddWithValue, um einen Parameter zu übergeben, der eine Abfrage für diese Spalte einschränkt. C # -Strings sind Unicode, daher ist der abgeleitete Parametertyp NVARCHAR, der nicht mit VARCHAR übereinstimmt.
VARCHAR zu NVARCHAR ist eine erweiterte Konvertierung, die implizit erfolgt - aber verabschieden Sie sich von der Indizierung und viel Glück beim Herausfinden, warum.
"Zähle die Disk-Hits" (Rick James)
Wenn alles im RAM zwischengespeichert ist,
JOINs
sind sie eher billig. Das heißt, Normalisierung hat nicht viel Leistungseinbußen .Wenn ein "normalisiertes" Schema dazu führt
JOINs
, dass die Festplatte häufig getroffen wird, das entsprechende "denormalisierte" Schema jedoch nicht auf die Festplatte trifft, gewinnt die Denormalisierung einen Leistungswettbewerb.quelle
Was die meisten Kommentatoren nicht bemerken, ist die breite Palette der in einem komplexen RDBMS verfügbaren Verknüpfungsmethoden, und die Denormalisierer beschönigen ausnahmslos die höheren Kosten für die Verwaltung denormalisierter Daten. Nicht jeder Join basiert auf Indizes, und Datenbanken verfügen über viele optimierte Algorithmen und Methoden für den Join, mit denen die Join-Kosten gesenkt werden sollen.
In jedem Fall hängen die Kosten eines Joins von seiner Art und einigen anderen Faktoren ab. Es muss überhaupt nicht teuer sein - einige Beispiele.
Datenbanken sind so konzipiert, dass sie verknüpft werden können. Sie sind sehr flexibel und im Allgemeinen sehr leistungsfähig, es sei denn, der Verknüpfungsmechanismus ist falsch.
quelle
Ich denke, die ganze Frage basiert auf einer falschen Prämisse. Joins auf großen Tischen sind nicht unbedingt teuer. Tatsächlich ist das effiziente Ausführen von Verknüpfungen einer der Hauptgründe, warum relationale Datenbanken überhaupt existieren . Verknüpfungen in großen Mengen sind oft teuer, aber sehr selten möchten Sie den gesamten Inhalt der großen Tabelle A mit dem gesamten Inhalt der großen Tabelle B verbinden. Stattdessen schreiben Sie die Abfrage so, dass nur die wichtigen Zeilen jeder Tabelle verwendet werden und Der tatsächliche Satz, der vom Join gehalten wird, bleibt kleiner.
Darüber hinaus verfügen Sie über die von Peter Wone genannten Effizienzvorteile, sodass nur die wichtigen Teile jedes Datensatzes gespeichert werden müssen, bis die endgültige Ergebnismenge vorliegt. Bei großen Abfragen mit vielen Verknüpfungen möchten Sie normalerweise mit den kleineren Tabellensätzen beginnen und sich bis zu den großen vorarbeiten, damit der im Speicher gespeicherte Satz so lange wie möglich so klein wie möglich bleibt.
Bei ordnungsgemäßer Ausführung sind Verknüpfungen im Allgemeinen die beste Methode zum Vergleichen, Kombinieren oder Filtern großer Datenmengen.
quelle
Der Engpass ist so ziemlich immer die Festplatten-E / A und insbesondere die zufällige Festplatten-E / A (im Vergleich dazu sind sequentielle Lesevorgänge ziemlich schnell und können mit Vorauslesestrategien zwischengespeichert werden).
Joins können zufällige Suchanfragen erhöhen - wenn Sie herumspringen und kleine Teile einer großen Tabelle lesen. Aber Abfrageoptimierer suchen danach und verwandeln es in einen sequentiellen Tabellenscan (Verwerfen der nicht benötigten Zeilen), wenn sie der Meinung sind, dass dies besser wäre.
Eine einzelne denormalisierte Tabelle hat ein ähnliches Problem: Die Zeilen sind groß und passen daher weniger auf eine einzelne Datenseite. Wenn Sie Zeilen benötigen, die weit voneinander entfernt sind (und aufgrund der großen Zeilengröße weiter voneinander entfernt sind), haben Sie mehr zufällige E / A. Auch hier kann ein Tabellenscan erzwungen werden, um dies zu vermeiden. Diesmal muss Ihr Tabellenscan jedoch aufgrund der großen Zeilengröße mehr Daten lesen. Hinzu kommt, dass Sie Daten von einem einzelnen Speicherort an mehrere Speicherorte kopieren und das RDBMS noch viel mehr zu lesen (und zwischenzuspeichern) hat.
Mit 2 Tabellen erhalten Sie auch 2 Clustered-Indizes - und können im Allgemeinen mehr indizieren (aufgrund des geringeren Einfügungs- / Aktualisierungsaufwands), wodurch Sie die Leistung drastisch steigern können (hauptsächlich wiederum, weil die Indizes (relativ) klein sind und sich schnell von der Festplatte ablesen lassen (oder billig im Cache) und verringern Sie die Anzahl der Tabellenzeilen, die Sie von der Festplatte lesen müssen).
Der einzige Overhead bei einem Join besteht darin, die passenden Zeilen herauszufinden. SQL Server verwendet drei verschiedene Arten von Verknüpfungen, die hauptsächlich auf der Größe der Datensätze basieren, um übereinstimmende Zeilen zu finden. Wenn der Optimierer den falschen Verknüpfungstyp auswählt (aufgrund ungenauer Statistiken, unzureichender Indizes oder nur eines Optimierungsfehlers oder eines Randfalls), kann dies die Abfragezeiten drastisch beeinflussen.
Im optimalen Fall verursachen diese keine Festplatten-E / A - und sind daher aus Sicht der Leistung vernachlässigbar.
Alles in allem sollte es im schlimmsten Fall schneller sein, die gleiche Menge an Logik zu lesen Daten aus x verknüpften Tabellen , wie dies aufgrund der kleineren Festplattenlesevorgänge aus einer einzelnen denormalisierten Tabelle der Fall ist. Um die gleiche Menge an physischen Daten zu lesen , kann ein geringfügiger Overhead entstehen.
Da die Abfragezeit normalerweise von E / A-Kosten dominiert wird und sich die Größe Ihrer Daten bei der Denormalisierung nicht ändert (abzüglich eines sehr geringen Zeilenaufwands), bietet das Zusammenführen von Tabellen keinen enormen Nutzen. Die Art der Denormalisierung, die dazu neigt, die Leistung zu steigern, IME, speichert berechnete Werte zwischen, anstatt die 10.000 Zeilen zu lesen, die zur Berechnung erforderlich sind.
quelle
Die Reihenfolge, in der Sie sich den Tischen anschließen, ist äußerst wichtig. Wenn Sie zwei Datensätze haben, versuchen Sie, die Abfrage so zu erstellen, dass der kleinste zuerst verwendet wird, um die Datenmenge zu reduzieren, an der die Abfrage arbeiten muss.
Für einige Datenbanken spielt es keine Rolle, zum Beispiel kennt MS SQL die meiste Zeit die richtige Verknüpfungsreihenfolge. Für einige (wie IBM Informix) macht die Reihenfolge den Unterschied.
quelle
Die Entscheidung, ob denormalisiert oder normalisiert werden soll, ist ziemlich einfach, wenn Sie die Komplexitätsklasse des Joins berücksichtigen. Zum Beispiel neige ich dazu, meine Datenbanken mit Normalisierung zu entwerfen, wenn die Abfragen O (k log n) sind, wobei k relativ zur gewünschten Ausgabegröße ist.
Eine einfache Möglichkeit, die Leistung zu denormalisieren und zu optimieren, besteht darin, darüber nachzudenken, wie sich Änderungen an Ihrer Normalisierungsstruktur auf Ihre denormalisierte Struktur auswirken. Dies kann jedoch problematisch sein, da möglicherweise Transaktionslogik erforderlich ist, um an einer denormalisierten Struktur zu arbeiten.
Die Debatte um Normalisierung und Denormalisierung wird nicht enden, da die Probleme groß sind. Es gibt viele Probleme, bei denen die natürliche Lösung beide Ansätze erfordert.
In der Regel habe ich immer eine normalisierte Struktur und denormalisierte Caches gespeichert, die rekonstruiert werden können. Letztendlich retten diese Caches meinen Arsch, um die zukünftigen Normalisierungsprobleme zu lösen.
quelle
Ausarbeiten, was andere gesagt haben,
Joins sind nur kartesische Produkte mit etwas Lipgloss. {1,2,3,4} X {1,2,3} würde 12 Kombinationen ergeben (nXn = n ^ 2). Diese berechnete Menge dient als Referenz, auf die Bedingungen angewendet werden. Das DBMS wendet die Bedingungen an (z. B. wenn links und rechts 2 oder 3 sind), um uns die übereinstimmenden Bedingungen zu geben. Eigentlich ist es optimierter, aber das Problem ist das gleiche. Die Änderungen der Größe der Sätze würden die Ergebnisgröße exponentiell erhöhen. Die Menge der verbrauchten Speicher- und CPU-Zyklen erfolgt exponentiell.
Wenn wir denormalisieren, vermeiden wir diese Berechnung insgesamt. Denken Sie daran, dass auf jeder Seite Ihres Buches ein farbiger Kleber angebracht ist. Sie können die Informationen ohne Verwendung einer Referenz ableiten. Die Strafe, die wir zahlen, besteht darin, dass wir die Essenz von DBMS (optimale Organisation von Daten) gefährden.
quelle