Wie funktionieren Datenbanken intern?

Question

Ich habe in den letzten Jahren mit Datenbanken gearbeitet und ich würde gerne denken, dass ich ziemlich kompetent bin, sie zu benutzen. Allerdings habe ich kürzlich über Joels Law of Leaky Abstractions gelesen und festgestellt, dass obwohl ich eine Abfrage schreiben kann, um so ziemlich alles, was ich will, aus einer Datenbank zu bekommen, habe ich keine Ahnung, wie die Datenbank die Abfrage tatsächlich interpretiert. Kennt jemand gute Artikel oder Bücher, die erklären, wie Datenbanken intern arbeiten?

einige spezielle Dinge, die ich in interessiert bin:

• Was ist eine Datenbank tatsächlich tun, um herauszufinden, was eine select-Anweisung übereinstimmt?
• Wie interpretiert eine Datenbank einen Join anders als eine Abfrage mit mehreren Anweisungen "where key1 = key2"?
• Wie speichert die Datenbank ihren gesamten Speicher?
• Wie werden Indizes gespeichert?

Answer 1

Was macht eine Datenbank tatsächlich zu herauszufinden, was eine ausgewählte Anweisung übereinstimmt?

Um ehrlich zu sein, ist es eine Frage der rohen Gewalt. Es liest einfach jeden Kandidaten-Datensatz in der Datenbank durch und passt den Ausdruck den Feldern an. Wenn Sie also "* aus der Tabelle auswählen, in der name = 'fred'" ist, durchläuft es buchstäblich jeden Datensatz, ruft das Feld "name" ab und vergleicht es mit "fred".

Nun, wenn das Feld "table.name" indiziert ist, wird die Datenbank (wahrscheinlich, aber nicht unbedingt) den Index zuerst verwenden, um die Kandidaten-Datensätze zu finden, auf die der eigentliche Filter angewendet wird.

Dies reduziert die Anzahl der Kandidaten-Datensätze, auf die der Ausdruck angewendet werden soll, sonst wird es einfach das tun, was wir einen "Tabellen-Scan" nennen, d.h. jede Zeile lesen.

Aber im Grunde, aber es findet die Kandidaten Datensätze getrennt von, wie es den tatsächlichen Filterausdruck anwendet, und offensichtlich gibt es einige schlaue Optimierungen, die getan werden können.

Wie funktioniert eine Datenbank ein anders auf eine Abfrage mit mehreren „wo key1 = key2“ Aussagen kommen interpretieren?

Nun, ein Join wird verwendet, um eine neue "Pseudo-Tabelle" zu erstellen, auf die der Filter angewendet wird. Sie haben also die Filterkriterien und die Verknüpfungskriterien. Die Join-Kriterien werden verwendet, um diese "Pseudo-Tabelle" zu erstellen, und dann wird der Filter darauf angewendet. Nun, bei der Interpretation des Joins, ist es wieder das gleiche Problem wie beim Filter - Brute-Force-Vergleiche und Index-Lesevorgänge, um die Teilmenge für die "Pseudo-Tabelle" zu erstellen.

Wie speichert die Datenbank alle ihre Speicher?

Einer der Schlüssel zu einer guten Datenbank ist, wie es seine I/O-Puffer verwaltet. Aber es entspricht im Wesentlichen RAM-Blöcke mit Festplattenblöcken. Mit den modernen virtuellen Speichermanagern kann eine einfachere Datenbank fast auf die VM als ihren Speicherpuffermanager zurückgreifen. Die High-End-DBs machen das alles selbst.

Wie werden Indizes gespeichert?

B + Bäume normalerweise sollten Sie nachschlagen. Es ist eine geradlinige Technik, die es seit Jahren gibt. Der Vorteil liegt in den meisten ausgeglichenen Strukturen: Der konsistente Zugriff auf die Knoten und alle Blattknoten sind miteinander verknüpft, sodass Sie in der Reihenfolge der Schlüssel von Knoten zu Knoten navigieren können. Mit einem Index können die Zeilen für bestimmte Felder in der Datenbank als "sortiert" betrachtet werden, und die Datenbank kann diese Informationen für Optimierungen nutzen. Dies unterscheidet sich von der Verwendung einer Hashtabelle für einen Index, mit der Sie nur schnell zu einem bestimmten Datensatz gelangen. In einem B-Tree können Sie schnell nicht nur zu einem bestimmten Datensatz gelangen, sondern zu einem Punkt innerhalb einer sortierten Liste.

Die eigentliche Mechanik des Speicherns und Indexierens von Zeilen in der Datenbank ist wirklich ziemlich geradlinig und gut verstanden. Das Spiel verwaltet Puffer und konvertiert SQL in effiziente Abfragepfade, um diese grundlegenden Speicher-Idiome zu nutzen.

Dann gibt es die gesamte Multi-User-, Sperr-, Protokollierungs- und Transaktionskomplexität auf dem Speicher-Idiom.

Answer 2

• Was ist eine Datenbank tatsächlich tun, um herauszufinden, was eine select-Anweisung übereinstimmt?

  DBs verwenden Indizes (siehe unten)

• Wie funktioniert eine Datenbank ein anders auf eine Abfrage mit mehreren „wo key1 = key2“ Aussagen kommen interpretieren? Join-Operationen können durch Zusammenführen von Bäumen in Binärbaum-Operationen übersetzt werden.

• Wie speichert die Datenbank all ihren Speicher?

  memorymapped Dateien für einen schnelleren Zugriff ihrer Daten

• Wie Indizes gespeichert?

  Intern arbeiten DBs mit B-Trees für Indexierung.

Dies sollte ..

http://en.wikipedia.org/wiki/B-tree

http://en.wikipedia.org/wiki/Database

Answer 3

Saif, ausgezeichneten Link in mehr Details zu wikipedia erläutert. Eine Vogelperspektive, die es ermöglicht, die meisten Themen zu behandeln und Details zu spezifischen Implementierungen von Anbietern zu liefern.

Ich habe drei Versuche gemacht, eine Erklärung zu schreiben, aber das ist wirklich ein zu großes Thema. Schau dir den Hellerstein-Artikel an (den auf dem Berkeley-Server, mit dem Saif verbunden war) und frage nach Besonderheiten.

Es ist erwähnenswert, dass nur ein Teil der "bekannten guten Ideen" in einem beliebigen DBMS implementiert ist. Zum Beispiel führt SQLite nicht einmal Hash-Joins durch, es macht nur verschachtelte Schleifen (ack !!). Aber es ist ein leicht integrierbares dbms, und es macht seine Arbeit sehr gut, also gibt es etwas für die fehlende Komplexität zu sagen.

Informationen darüber, wie ein DBMS Statistiken sammelt und wie diese verwendet werden, um Abfragepläne zu erstellen und zu lernen, wie die Abfragepläne gelesen werden, ist eine unschätzbare Fähigkeit - wenn Sie eine "Datenbank" auswählen müssen Interna "Thema zu lernen, lerne dies. Es wird einen Unterschied machen (und Sie werden nie wieder versehentlich ein kartesisches Produkt schreiben ... ;-)).

Answer 4

Zusätzlich zum Lesen kann es hilfreich sein, mit den DB-Tools den Ausführungsplan zu überprüfen, den die Datenbank für Ihre Abfragen verwendet. Zusätzlich zum Einblick in die Funktionsweise können Sie mit Techniken experimentieren, um die Abfragen mit einer besseren Rückkopplungsschleife zu optimieren.

Answer 5

Wenn Sie mehr im Detail wissen möchten, würde ich empfehlen, die SQLite-Quellen zu bekommen und einen Blick darauf werfen, wie es funktioniert. Es ist vollständig, wenn auch nicht im Umfang der größeren Open-Source- und kommerziellen Datenbanken. Wenn Sie mehr im Detail wissen wollen, empfehle ich The Definitive Guide to SQLite das ist nicht nur eine großartige Erklärung von SQLite, sondern auch eines der am besten lesbaren technischen Bücher, die ich kenne. Auf der MySQL-Seite können Sie von MySQL Performance Blog sowie auf der Buchfront des O'Reilly High Performance MySQL (V2) lernen, von dem der Blog einer der Autoren ist.