SQL-Indizes erklärt, Pt. 2

In der ersten Lektion von SQL Indexes Explained haben wir gelernt, die Sortierung zu verwenden, um den Datenabruf zu beschleunigen. Während unsere Abfrageausführung nach dem Sortieren der Zeilen schneller ist, beinhaltet das Sortieren das Lesen jeder Zeile mindestens einmal und das Verschieben. Das macht die Methode langsamer und weniger effizient als das einfache sequentielle Lesen der gesamten Tabelle.

Die logische Schlussfolgerung scheint zu sein, dass wir sortierte Kopien – die wir offiziell SQL- Indizes mit dem Präfix IX_ – einer gegebenen Tabelle pflegen sollten. Dann wären die Abrufalgorithmen aus dem ersten Artikel anwendbar, und wir müssten die Tabelle vor dem Start nicht sortieren.

Der Index als sortierte Kopie der Tabelle

Werfen wir einen Blick auf die wörtliche Umsetzung dieser Idee, wiederum mit Google Sheets. Unsere Reservierungstabelle wird zu einer Sammlung von fünf Blättern, die dieselben Daten enthalten. Jedes Blatt ist nach verschiedenen Spaltensätzen sortiert.

Die Übungen hier sollen weniger anspruchsvoll sein als im vorherigen SQL-Index-Tutorial-Artikel – sie können mehr nach Gefühl als nach Timer und Zeilenanzahl durchgeführt werden. Einige Übungen werden sehr ähnlich erscheinen, aber dieses Mal erforschen wir:

1. Wie Sie Daten effizienter abrufen können, wenn Sie separate Indizes anstelle von sortierten Primärtabellen verwenden
2. So behalten Sie die Reihenfolge in jedem Index und jeder Tabelle bei, wenn Sie Daten ändern

Das vorherige Tutorial konzentrierte sich auf Lesevorgänge, aber bei vielen gängigen realen Datendynamiken – einschließlich unserer Hotelreservierungen – müssen wir die Auswirkungen der Indizierung auf die Schreibleistung berücksichtigen, sowohl beim Einfügen neuer Daten als auch beim Aktualisieren vorhandener Daten.

Vorübung: Eine Reservierung stornieren

Um ein Gefühl für die Leistung von SQL-Indizes unter Verwendung der sortierten Tabellenstrategie zu bekommen, besteht Ihre Aufgabe darin, eine Reservierung für Client 12 vom 22. August 2020 in Hotel 4 zu löschen. Denken Sie daran, dass Sie eine Zeile aus allen Kopien von entfernen müssen die Tabelle und behalten Sie die richtige Sortierung bei.

Getan? Es sollte klar sein, dass die Idee, mehrere sortierte Kopien der Tabelle aufzubewahren, nicht so gut ist, wie es schien. Wenn Sie immer noch Zweifel haben, können Sie auch versuchen, die gerade gelöschte Reservierung wieder einzufügen oder das Datum einer bestehenden Reservierung zu ändern.

Während sortierte Kopien der Tabelle einen schnelleren Abruf ermöglichen, ist die Datenänderung, wie wir gerade gelernt haben, ein Albtraum. Immer wenn wir eine vorhandene Zeile hinzufügen, löschen oder aktualisieren müssen, müssen wir alle Kopien der Tabelle abrufen, eine Zeile und/oder die Stelle finden, an der sie hinzugefügt oder verschoben werden soll, und schließlich Datenblöcke verschieben.

SQL-Indizes mit Zeilenadressen

Diese Tabelle enthält Indizes, die einen anderen Ansatz verwenden. Indexzeilen werden weiterhin nach bestimmten Kriterien sortiert, aber wir behalten nicht alle anderen Informationen in der Indexzeile. Stattdessen behalten wir nur die „Zeilenadresse“, die Adresse der Zeile im Reservierungsblatt – die die Tabelle selbst darstellt – in Spalte H.

Alle RDBMS-Implementierungen verwenden eine Funktion auf Betriebssystemebene, um den Block auf der Festplatte mithilfe einer physischen Adresse schnell zu finden. Reihenadressen bestehen typischerweise aus einer Blockadresse plus der Position der Reihe innerhalb des Blocks.

Machen wir ein paar Übungen, um zu lernen, wie dieses Indexdesign funktioniert.

Übung 1: Alle Reservierungen eines Kunden

Wie im ersten Artikel werden Sie die Ausführung der folgenden SQL-Abfrage simulieren:

 SELECT * FROM Reservations WHERE ClientID = 12;

Auch hier gibt es zwei vernünftige Ansätze. Der erste liest einfach alle Zeilen aus der Reservierungstabelle und ruft nur Zeilen ab, die den Kriterien entsprechen:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

Der zweite Ansatz besteht darin, Daten aus dem Blatt IX_ClientID zu lesen und für jedes Element, das den Kriterien entspricht, eine Zeile in der Reservierungstabelle basierend auf dem Wert von rowAddress zu finden:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Hier wird der Ausdruck Get first row from durch eine Schleife implementiert, die der im vorherigen Artikel ähnelt:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Sie können eine Zeile mit einer bestimmten rowAddress finden, indem Sie nach unten schieben, bis Sie eine Zeile finden, oder indem Sie einen Filter für die Spalte rowAddress verwenden.

Wenn nur eine Handvoll Reservierungen zurückgegeben werden müssten, wäre der Ansatz mit dem Index besser. Da jedoch Hunderte – oder manchmal sogar nur Dutzende – von Zeilen zurückgegeben werden müssen, kann die direkte Verwendung der Reservierungstabelle schneller sein.

Das Lesevolumen hängt vom Wert von ClientID ab. Für den größten Wert müssen Sie den gesamten Index lesen, für den niedrigsten Wert steht er am Anfang des Index. Der Mittelwert ist die Hälfte der Zeilenzahl.

Wir werden später auf diesen Teil zurückkommen und eine effiziente Lösung präsentieren. Konzentrieren wir uns zunächst auf den Teil, nachdem Sie die erste Zeile gefunden haben, die unseren Kriterien entspricht.

Übung 2: Die Anzahl der Reservierungen ab einem bestimmten Datum

Die Aufgabe besteht darin, die Anzahl der Check-Ins am 16. August 2020 unter Verwendung des neuen Indexdesigns zu zählen.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

Der Ansatz, den geeigneten Index zum Zählen zu verwenden, ist einem Tabellenscan überlegen, unabhängig von der Anzahl der beteiligten Zeilen. Der Grund dafür ist, dass wir überhaupt nicht auf die Reservierungstabelle zugreifen müssen – wir haben alle Informationen, die wir brauchen, im Index selbst:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

Der Algorithmus ist im Grunde derselbe wie derjenige, der sortierte Tabellen verwendet. Die Indexzeile ist jedoch viel kürzer als die Tabellenzeile, sodass unser RDBMS weniger Datenblöcke von der Platte lesen müsste.

Übung 3: Kriminalpolizei (Gästeliste mit Hotel und Datumsbereich)

Lassen Sie uns eine Liste der Gäste erstellen, die am 13. und 14. August 2020 im Hotel 3 angekommen sind.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Wir können alle Zeilen aus der Reservierungstabelle lesen oder einen der verfügbaren Indizes verwenden. Nachdem wir die gleiche Übung mit einer nach bestimmten Kriterien sortierten Tabelle durchgeführt hatten, stellten wir fest, dass der Index IX_HotelID_DateFrom am effizientesten ist.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

Können wir einen noch effizienteren Index entwerfen?

Wir greifen auf die Tabelle aufgrund des ClientID Werts zu, der einzigen Information, die wir für die Liste der von uns gemeldeten Gäste benötigen. Wenn wir diesen Wert in den SQL-Index aufnehmen, müssen wir überhaupt nicht auf die Tabelle zugreifen. Versuchen Sie, eine Liste nur aus einem solchen Index zu erstellen, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Wenn der Index alle notwendigen Informationen für die Abfrageausführung enthält, sagen wir, dass der Index die Abfrage abdeckt .

Aufgabe 4: Namensliste der Gäste statt IDs

Eine Liste mit Gastausweisen wäre für einen Polizeibeamten, der eine Straftat untersucht, nutzlos. Wir müssen Namen angeben:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Um eine Liste bereitzustellen, benötigen wir neben den Daten aus der Reservations auch eine Clients -Tabelle mit Gästeinformationen, die in diesem Google-Blatt zu finden sind.

Diese Übung ist der vorherigen ähnlich, ebenso wie die Herangehensweise.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

Der Ausdruck Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID kann per Table Scan oder über unseren Index implementiert werden. Wenn wir einen Tabellenscan verwenden, müssten wir für jede ClientID aus der While -Schleife im Durchschnitt die Hälfte der Zeilen aus der Clients -Tabelle lesen:

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

Die Indeximplementierung, die wir bisher betrachtet haben – nennen wir sie eine „flache“ Indeximplementierung – wäre nicht allzu hilfreich. Wir müssten die gleiche Anzahl von Zeilen (allerdings kleinere Zeilen) aus dem Index lesen und dann mit RowAddress zu der Zeile in Clients springen:

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Hinweis: Hier bezieht sich PK auf „Primärschlüssel“, ein Begriff, den wir später in der Serie untersuchen werden.

Gibt es eine Möglichkeit, dies zu erreichen, ohne so viele Zeilen lesen zu müssen? Ja – genau dafür sind B-Tree-Indizes da.

Balanced Tree (B-Tree)-Indizes

Lassen Sie uns die Zeilen von Clients_PK_Flat in vierzeilige Blöcke unterteilen und eine Liste erstellen, die den Wert der letzten ClientID aus dem Block und die Adresse des Blockanfangs (Spalte IndexRowAddress ) enthält. Die resultierende Datenstruktur des Datenbankindex finden Sie im Blatt Clients_PK_2Levels. Probieren Sie aus, wie Ihnen die neue Struktur hilft, einen Client mit einer ClientID von 28 zu finden. Der Algorithmus sollte folgendermaßen aussehen:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Sie haben wahrscheinlich herausgefunden, dass wir eine weitere Ebene hinzufügen können. Ebene 1 besteht aus vier Zeilen, wie Sie auf der Registerkarte IX_Clients_PK sehen können. Um den Namen des Gastes mit einer ClientID von 28 zu finden, müssen Sie drei Datenblöcke (Knoten) – einen pro Ebene – aus der Primärschlüsselstruktur lesen und schließlich zur Clients-Zeile mit der Adresse 42 springen.

Die Struktur dieses SQL-Index wird als ausgeglichener Baum bezeichnet. Der Baum ist ausgeglichen, wenn der Pfad vom Wurzelknoten zu jedem Knoten auf Blattebene dieselbe Länge hat, seine sogenannte B-Baum-Tiefe. In unserem Fall ist die Tiefe drei.

Von nun an betrachten wir jeden Index als B-Baum-Struktur, obwohl unsere Tabellenkalkulationen nur Einträge auf Blattebene enthalten. Die wichtigsten Fakten über B-Tree sind:

• Die B-Tree-Indexstruktur ist der am häufigsten verwendete Index aller großen RDBMS auf dem Markt.
• Alle Ebenen eines ausgeglichenen Baums sind nach Schlüsselspaltenwerten geordnet.
• Daten werden blockweise von der Platte gelesen.
• Ein B-Baum-Knoten enthält einen oder mehrere Blöcke.
• Der wichtigste Faktor, der die Abfrageleistung beeinflusst, ist die Anzahl der von der Festplatte gelesenen Blöcke.
• Die Anzahl der Elemente in jeder neuen B-Baum-Ebene, beginnend bei der Wurzel, endend auf der Blattebene, steigt exponentiell an.

Übung 5: Kriminalpolizei, Teil II

Nun sucht der Polizeiinspektor eine Liste mit entsprechenden Gästenamen, Ankunftsdaten und Hotelnamen aller Hotels in Stadt A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Ansatz 1

Wenn wir den Index IX_DateFrom_HotelID_ClientID verwenden, müssten wir für jede Zeile aus dem Datumsbereich auf die Tabelle Hotels zugreifen und prüfen, ob das Hotel aus Stadt A stammt. Wenn dies der Fall ist, müssten wir auch auf die Tabelle Clients zugreifen Lesen Sie den Namen des Kunden.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Ansatz 2

Die Verwendung IX_HotelID_DateFrom_ClientID gibt uns einen effizienteren Ausführungsplan.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

In der Tabelle Hotels finden wir alle Hotels aus Stadt A. Wenn wir die ID dieser Hotels kennen, können wir nachfolgende Elemente aus dem Index IX_HotelID_DateFrom_ClientID lesen. Auf diese Weise lesen wir, nachdem wir die erste Zeile in der B-Baum-Blattebene für jedes Hotel und Datum gefunden haben, nicht die Reservierungen von Hotels außerhalb der Stadt A.

Hier können wir sehen, dass ein zusätzlicher Join eine Abfrage tatsächlich beschleunigen kann, wenn wir einen Datenbankindex haben, der für unsere Ziele geeignet ist.

Die B-Baumstruktur und wie sie aktualisiert wird, wenn eine Zeile eingefügt, aktualisiert oder gelöscht wird, wird ausführlicher behandelt, wenn ich die Motivation für die Partitionierung und ihre Auswirkungen erkläre. Der Punkt ist, dass wir diese Operation schnell berücksichtigen können, wenn wir einen Index verwenden.

Die Indexabfrage in SQL: Details machen den Unterschied

Wenn es um Indizes und Datenbanken geht, verbirgt die Arbeit auf der Ebene der SQL-Sprache Implementierungsdetails in gewissem Maße. Diese Übungen sollen Ihnen helfen, ein Gefühl dafür zu bekommen, wie Ausführungspläne funktionieren, wenn Sie verschiedene SQL-Indizes verwenden. Ich hoffe, dass Sie nach dem Lesen des Artikels in der Lage sein werden, den besten Ausführungsplan angesichts der verfügbaren Indizes und Design-Indizes zu erraten, die eine Abfrage so schnell und effizient wie möglich machen würden.

Im nächsten Teil dieser Serie werden wir neu erworbene Fähigkeiten nutzen und erweitern, um die gängigsten Best Practices und Anti-Patterns bei der Verwendung von Indizes in SQL zu untersuchen und zu verstehen. Ich habe eine Liste bewährter und bewährter Verfahren, die ich im nächsten Teil ansprechen möchte, aber um den nächsten Artikel relevanter für Ihre Bedürfnisse und Erfahrungen zu machen, können Sie gerne Ihre eigenen Fragen posten, die Sie gerne beantwortet sehen möchten .

Im letzten Teil von SQL Indexes Explained lernen wir auch etwas über die Tabellen- und Indexpartitionierung, die richtigen und falschen Beweggründe für ihre Verwendung und ihre Auswirkungen auf die Abfrageleistung und Datenbankwartung.