Optimierung der Datenbanken: Hashing aller Werte

Question

Normalerweise sind die Datenbanken so konzipiert, dass sie mehrere Typen für eine Entität zulassen.

Name der Entität Typ Zusätzliche Informationen

Der Name der Entität kann so etwas wie eine Kontonummer sein, und der Typ könnte z. B. in einer Bankdatenbank wie Sparen, Girokonto usw. lauten.

Meistens handelt es sich bei type um eine Zeichenkette. Einem Entitätstyp können zusätzliche Informationen zugeordnet sein.

Normalerweise werden die Fragen so gestellt. Finden Sie Kontonummern dieses bestimmten Typs? Finden Sie Kontonummern des Typs X, deren Saldo größer als 1 Million ist?

Um diese Abfragen zu beantworten, wird der Query Analyzer den Index scannen, wenn der Index mit einer bestimmten Spalte verbunden ist. Andernfalls führt er einen vollständigen Scan aller Zeilen durch.

Ich denke über die folgende Optimierung nach. Warum speichern wir nicht den Hash- oder Integralwert der einzelnen Spaltendaten in der eigentlichen Tabelle, so dass die Ordnungseigenschaft beibehalten wird, so dass es für den Vergleich einfach ist.

Es hat folgende Vorteile. 1. Die Tabellengröße wird viel geringer sein, weil wir kleine Werte für jede Spalte speichern werden. 2. Wir können einen geclusterten B+-Baumindex auf den Hash-Werten für jede Spalte erstellen, um die entsprechenden Zeilen abzurufen, die mit einem bestimmten Wert übereinstimmen oder größer oder kleiner als dieser sind. 3. Die entsprechenden Werte können leicht abgerufen werden, indem der B+ Baumindex im Hauptspeicher abgelegt wird und die entsprechenden Werte abgerufen werden. 4. Seltene Werte müssen nie abgerufen werden.

Ich habe noch weitere Optimierungen im Kopf. Ich werde diese auf der Grundlage des Feedbacks zu dieser Frage veröffentlichen.

Ich bin nicht sicher, ob dies bereits in der Datenbank implementiert ist, dies ist nur ein Gedanke.

Vielen Dank, dass Sie dies gelesen haben.

-- Bala

Aktualisierung:

Ich versuche nicht zu emulieren, was die Datenbank tut. Normalerweise werden Indizes vom Datenbankadministrator erstellt. Ich versuche, ein physisches Schema vorzuschlagen, indem ich Indizes für alle Felder in der Datenbank habe, so dass die Größe der Datenbanktabelle reduziert wird und es einfach ist, einige Abfragen zu beantworten.

Aktualisierungen:(Joes Antwort)

Wie lässt sich die Größe der Datenbank durch Hinzufügen von Indizes zu jedem Feld verringern? Sie müssen immer noch alle wahren Werte zusätzlich zum Hash speichern; wir wollen nicht nur nach der Existenz abfragen, sondern die tatsächlichen Daten zurückgeben.

In einer typischen Tabelle werden alle physischen Daten gespeichert. Indem ich nun aber für jede Spalte einen Hash-Wert generiere, speichere ich nur den Hash-Wert in der eigentlichen Tabelle. Ich stimme zu, dass die Größe der Datenbank nicht verringert wird, aber die Größe der Tabelle wird verringert. Es wird nützlich sein, wenn Sie nicht brauchen, um alle Spaltenwerte zurückzugeben.

Die meisten RDBMS beantworten heute die meisten Abfragen effizient (insbesondere mit Schlüsselindizes). Es fällt mir schwer, Szenarien zu formulieren, in denen Ihre Datenbank effizienter wäre und Platz sparen würde.

Es kann nur einen geclusterten Index auf einer Tabelle geben und alle anderen Indizes müssen unclusterte Indizes sein. Mit meinem Ansatz werde ich einen geclusterten Index für alle Werte der Datenbank haben. Das wird die Abfrageleistung verbessern.

Indizes innerhalb der physischen Daten zu platzieren - das macht nicht wirklich Sinn. Der Schlüssel zur Leistung von Indizes ist, dass jeder Index in sortierter Reihenfolge gespeichert wird. Wie wollen Sie das für alle möglichen Felder erreichen, wenn sie nur einmal in ihrem physischen Layout gespeichert werden? Letztendlich müssen die eigentlichen Zeilen nach irgendetwas sortiert werden (in SQL Server ist das zum Beispiel der Cluster-Index)?

Der Grundgedanke ist, dass wir für einen effizienten Zugriff nicht für jede Spalte eine eigene Tabelle erstellen, sondern dies auf der physischen Ebene tun.

Die Tabelle sieht nun wie folgt aus.

Zeile1 - OrderedHash(Spalte1),OrderedHash(Spalte2),OrderedHash(Spalte3)

Answer 1

Googeln Sie nach "Hash-Index". In SQL Server wird ein solcher Index zum Beispiel mit der Funktion CHECKSUM erstellt und abgefragt.

Dies ist vor allem dann nützlich, wenn Sie eine Spalte indizieren müssen, die lange Werte enthält, z. B. varchars, die im Durchschnitt mehr als 100 Zeichen lang sind oder ähnliches.

Answer 2

Wie lässt sich durch das Hinzufügen von Indizes zu jedem Feld die Größe der Datenbank verringern? Sie müssen immer noch alle wahren Werte zusätzlich zum Hash speichern. Wir wollen ja nicht nur nach der Existenz abfragen, sondern die tatsächlichen Daten zurückgeben.

Die meisten RDBMS beantworten heute die meisten Abfragen effizient (insbesondere mit Schlüsselindizes). Es fällt mir schwer, Szenarien zu formulieren, in denen Ihre Datenbank effizienter wäre und Platz sparen würde.

Indizes innerhalb der physischen Daten zu platzieren - das macht nicht wirklich Sinn. Der Schlüssel zur Leistung der Indizes ist, dass jeder Index in sortierter Reihenfolge gespeichert wird. Wie wollen Sie das für alle möglichen Felder erreichen, wenn sie nur einmal in ihrem physischen Layout gespeichert werden? Letztendlich müssen die eigentlichen Zeilen nach irgendetwas sortiert werden (in SQL Server ist das zum Beispiel der Cluster-Index)?

Answer 3

Ich glaube nicht, dass Ihr Ansatz sehr hilfreich ist.

Hash-Werte helfen nur bei Vergleichen von Gleichheit/Ungleichheit, aber nicht bei Vergleichen von kleiner als/größer als, verglichen mit so ziemlich jedem Datenbankindex.

Selbst bei (Un-)Gleichheit bieten Hash-Funktionen keine 100-prozentige Garantie, dass sie die richtige Antwort liefern, da Hash-Kollisionen auftreten können, so dass Sie immer noch den ursprünglichen Wert abrufen und vergleichen müssen - und schon haben Sie verloren, was Sie speichern wollten.

Sie können die Zeilen einer Tabelle jeweils nur auf eine Weise ordnen lassen. Wenn Sie also eine Anwendung haben, in der Sie Zeilen in verschiedenen Abfragen unterschiedlich anordnen müssen (z. B. Abfrage A benötigt eine Liste von Kunden, die nach ihrem Namen geordnet sind, Abfrage B benötigt eine Liste von Kunden, die nach ihrem Umsatz geordnet sind), muss eine dieser Abfragen auf die Tabelle in ungeordneter Reihenfolge zugreifen.

Wenn Sie nicht möchten, dass die Datenbank mit Spalten arbeiten muss, die Sie in einer Abfrage nicht verwenden, dann verwenden Sie Indizes mit zusätzlichen Datenspalten - wenn Ihre Abfrage nach diesem Index geordnet ist und Ihre Abfrage nur Spalten verwendet, die im Index enthalten sind (es sei denn, der Index basiert auf zusätzlichen Spalten, die Sie ausdrücklich in den Index aufgenommen haben), liest das DBMS die ursprüngliche Tabelle nicht.

Etc.