Datenbanken im Fokus des Performance Engineerings

Datenbanken gehören heute zur Standardinfrastruktur der meisten Softwarelösungen. Dies gilt umso mehr für Business-Applikationen. In dieser Stellung sind inperformante Anfragen an die Datenbanksysteme häufig die Ursache für ungenügende Applikationslaufzeiten. Es ist deshalb nicht verwunderlich, dass das Abfrage-Tunings im Kontext der Applikationsverbesserung eine zentrale Rolle einnimmt.

Vielleicht ist es genau jene Alltäglichkeit der Datenbanken, die auf Seiten der Applikationsentwickler zu einer gewissen Sorglosigkeit im Umgang geführt hat. Sie wird es schon richten, wie selbstverständlich, Informationen in schier unendlicher Menge entgegennehmen und nahezu »zeitlos« wieder auffinden. Befördert wird diese Umbekümmertheit durch zahllose Frameworks, welche die Datenbank und »deren Arbeit« vor dem Entwickler verstecken, als Strategie verborgen hinter dem Begriff des »Information Hiding«. So entstehen allzu oft Abfragemonster und Query-Feuerwerke, die zwar fachlich korrekte Ergebnisse liefern, die Performance der Anwendung aber zusammenbrechen lassen, spätestens dann, wenn sich nennenswerte Datenmengen in der Datenbank befinden.

Indizes und deren Wirkungsweise

So die ersten Performance-Schwächen in der Datenbankinteraktion sichtbar werden, erwacht schnell der Ruf nach Indizes als adäquates Mittel zum Gegensteuern. Manchmal hilft es, oft aber eben leider auch nicht. Warum ist das so?

Der Index ist eine Technologie zur semantischen Adressierung von Informationen.

»Semantische Adressierung« – ein wahres Wortungetüm und dennoch treffend:

Der Zugriff auf jedes reale Objekt, so auch auf informationstragende Datenbankobjekte, erfordert das Wissen um deren Position. »Zugriff« verbindet sich also immer mit dem Wissen um das »Wo-es-steht«. Im Umfeld der Informationstechnologie verknüpfen wir den Begriff der »Position« synonym mit der Bezeichnung »Adresse«, die in Datenbanken mit einer konkreten Zeile einer Tabelle korreliert. Soll ein Datenbankobjekt in den Zugriff genommen werden, ist zwangsläufig dessen Adresse erforderlich.

Im Ausgangspunkt der meisten Anwendungsfälle steht genau jene Adresse aber nicht zur Verfügung. Vielmehr werden die gewünschten Datenbankobjekte durch die Vorgabe von Attribut-Mustern spezifiziert.

Beispiel: Liefere alle Datensätze der Tabelle Personen, die in der Spalte »Name« den Wert »Müller« und zugleich in der Spalte »Ort« den Wert »Berlin« aufweisen.

Die Quelle der Anfrage nimmt somit eine semantische Adressierung der gewünschten Datenbankobjekte vor.

Es liegt nunmehr in der Verantwortung des Datenbanksystems, diese semantische Adresse in eine oder mehrere physische zu überführen, um so den Zugriff auf die gewünschten Datenbankobjekte vorzunehmen. In der einfachsten Form stützt es sich dabei auf eine Suchoperation. Satz für Satz erfolgt ein Abgleich gegen das Vorgabemuster. Die Größe des zu durchforstenden Raums korreliert direkt mit dem hierfür erforderlichen Aufwand. So dieser durch eine einzelne Tabelle gegeben ist, bleibt er gut abschätzbar. Sobald jedoch Tabellenverbünde (Joins) einbezogen werden, kann dies zu Suchräumen führen, die nicht oder nur mit inakzeptablen Laufzeiten verarbeitbar sind.

Einen Ausweg aus dieser Performance-Schwachstelle bieten Indizes, die faktisch eine semantische Landkarte bezüglich des Datenbestands vorhalten. Indizes stellen sowohl die Datenstrukturen, die Datenbestände und die korrespondierenden Algorithmen zur Verfügung, welche die Überführung der oben genannten Semantischen Adresse in eine oder mehrere physische Adressen ermöglichen.

Wirksamkeit von Indizes

Die genannte Adresstransformation ist leider nicht zum Nulltarif zu erhalten. Sowohl aus der Notwendigkeit der Index-Pflege bei Veränderungen am Basisdatenbestand als auch aus der eigentlichen Berechnung der physischen Adressen resultiert ein entsprechender Aufwand. Und so ist es nicht verwunderlich, dass die einfache Regel »Über einen Index geht alles schneller« nicht generell anwendbar ist. Auf die zu erzielende Gesamtlaufzeit einer Abfrage wirken sich viele Einzelfaktoren aus, vom Volumen der Basisdatenmenge, deren Datensatzbreite, den physischen Eigenschaften des Massenspeichers, den Volumina der diversen Caches, die in die Verarbeitung einbezogen werden bis hin zu den in zeitlicher Nähe vorgelagerten alternativen Abfragen. Der hierbei zu durchlaufende komplexe Optimierungsprozess liegt in der Hand des Datenbank-Optimizers und mündet in einem Zugriffsplan, der den konkreten zu beschreitenden Weg der Informationsbereitstellung im Kontext einer Abfrage vorgibt.

Die Mehrzahl der Datenbanksysteme ermöglichen das Auslesen des jeweiligen Zugriffsplans. Dessen Analyse zeigt erstaunlich oft, dass die Datenbank die Verwendung eines zur Verfügung stehenden Index bei der Abfrageausführung ausschlägt und stattdessen auf Suchoperationen zurückgreift.

Grundsätzlich gilt die Regel, dass die Nutzung eines Index für den Datenzugriff umso wahrscheinlicher wird, je selektiver eine Abfrage ist.

Mit anderen Worten: Werden im Ergebnis einer Abfrage nur sehr wenige Datensätze aus einer großen Basismenge selektiert, so ist die Nutzung eines Index zur semantischen Adressierung der Weg mit der besten Performance. Mit einem Anwachsen der Ergebnismenge wird es immer wahrscheinlicher, dass die Informationsbereitstellung per Suchoperation die leistungsfähigere Option ist.

Multi-Prädikat-Indizierung

Die meisten Datenbankhersteller setzen bei der technischen Implementierung von Indizes auf die erprobte Technologie der B-Bäume. Diese fußen auf der einfachen größer-kleiner-Relation von Schlüsselwerten sowie deren darin begründeten Sortierung. Aus diesem Vergleich resultiert der Zwang, dass der B-Baum-Index sich nur über einen Schlüsselwert aufbauen lässt, da eine umfassendere Schlüsselwertmenge nicht in eine derartig vergleichende Beziehung gebracht werden kann.

Eine auf nur einem Attribut basierende eindimensionale semantische Adressierung deckt nun aber nur sehr wenige Anwendungsfälle ab. Deshalb greifen die Datenbankhersteller »zu einem Trick«: Im Falle einer semantischen Adressierung über mehrere Attribute zur Abdeckung eines mehrdimensionalen Suchraums, werden diese Attribute in einer definierten Folge zu EINEM Schlüsselwert verkettet. Dieser neu generierte, verkette Schlüsselwert aus A1+A2+A3+…+An kann nachfolgend in analoger Weise verarbeitet werden, wie dies mit nur einem Schlüssel-Attribut geschehen würde. Landläufig ist dies unter dem Begriff »Composite Index« bekannt. Leider ist diese Indexform der Einschränkung unterworfen, dass sie nur nutzbar ist, wenn alle Vergleichs-Attribute Teil der Anfrage sind. Enthält die Anfrage nur eine Teilmenge der im Index verketteten Attribute, kann der Index nur dann zum Einsatz kommen, wenn in der Indexkette keine Lücken auftreten.

Beispiel a): Die Anfrage enthält die Attribute A1 und A2. Der Index ist somit nutzbar.
Beispiel b): Die Anfrage enthält die Attribute A3 bis An. Der Index kann nicht eingesetzt werden, da die Attribute A1 und A2 fehlen und die Kette somit unterbrochen wird.

Wird eine »echte« multidimensionale Adressierung erforderlich, bei der eine m-aus-n-Attribut-Auswahl zur semantischen Adressierung der gewünschten Datenbankobjekte herangezogen werden kann, scheiden die B-Bäume als Implementierungsbasis aus. Die etablierten Datenbankhersteller wie IBM, Oracle und Microsoft haben im Data-Warehouse-Kontext Anstrengungen unternommen, entsprechende multidimensionale Indizes bereitzustellen. Diese werden im Regelfall als Bitmap-Index implementiert. Leider sind diese Indexformen im praktischen Einsatz auf niedrigdimensionale Suchräume beschränkt. Die zu indizierenden Datenbankobjekte dürfen hinsichtlich der Index-Attribute nur eine geringe Varianz (Kardinalität) aufweisen. Die Zahl der möglichen Attributausprägungen muss folglich klar begrenzt sein. Für Anwendungsfälle, bei denen die Attribute einen faktisch unendlich großen Wertevorrat annehmen können, sind diese Implementierungsformen deshalb ungeeignet.

Alle Bestrebungen, hier einen universellen Lösungsansatz zu finden, sind bisher an der Tatsache gescheitert, dass ein multidimensionaler Index in erster Näherung den Suchraum mittels eines n-dimensionalen Arrays abbilden muss. Steigt die Dimensionalität und/oder die Kardinalität einzelner Dimensionen an, so gewinnt der Suchraum und damit das korrelierende Array sehr schnell an Volumen und die physisch verfügbaren Ressourcen, insbesondere der Arbeitsspeicher, gelangen an ihre Grenzen.

Es bedarf folglich eines Lösungsansatzes, der einen unendlich großen Suchraum in eine kompakte technische Darstellungsform überführen kann, dem Gedanken folgend, dass die Besetzung eines unendlich großen Suchraums mit realen Datenbankobjekten in der Praxis sehr schwach sein wird – vergleichbar mit der »dünnen« Belegung des unendlichen Kosmos mit Himmelskörpern. Sofern es also gelingt, die leeren Bereiche aus der Suchraumrepräsentation »herauszukomprimieren« und nur jene Teile des Raumes technisch abzubilden, welche mit möglichen Suchergebnissen besetzt sind, kann das oben genannte »Platzproblem« der multidimensionalen Indizes gelöst werden.

Im Rahmen unseres Performance-Tuning-Pakets »Callidior« steht uns erstmalig ein multidimensionaler Index zur Verfügung, welcher den oben genannten Einschränkungen nicht unterliegt. Dies gelingt, weil mittels Technologien der künstlichen Intelligenz die vorliegenden Datenbestände in den Suchraum projiziert und hier »Datenklumpen« identifiziert werden. Das Wissen um die »Datenklumpen«, deren Lokation und Ausdehnung im Suchraum ermöglicht im Umkehrschluss die Benennung datenfreier Raumsegmente und somit eine äußerst kompakte Repräsentation der relevanten Bereiche. Damit gelingt erstmals die Aufnahme von stetigen Attributen mit einem unendlich großen Wertevorrat in den Index, bei einer maximalen Dimensionszahl von weit über 1.000.

Anwendungsbereiche

Ein multidimensionaler Index – das klingt »gewaltig«. Aber was stellt man damit nun wirklich nutzbringend an?

All jenen, die sich bereits in den Bereichen des analytischen Reportings bewegt haben, wird der Gedanke der Multidimensionalität vertraut sein. Hier wird dauerhaft mit multidimensionalen Modellen, Sichtweisen und Datenbanken operiert. Jene, die hiermit noch keine Berührung hatten, stellen sich in einfacher Näherung ein dreidimensionales System in Form eines Würfels vor. Jede Kante des Würfel steht für eine Dimension. Auf den Kanten sind die möglichen Suchattributausprägungen projiziert, welche bei Anfragen die Rolle der Prädikate übernehmen. Durch die Kombination konkreter Attributausprägungen der Dimensionen können nun Punkte im Suchraum beschrieben (adressiert) werden.

Das »Tolle« daran ist, dass durch Auslassung einzelner Prädikate oder mittels Benennung von Prädikatgrenzen Punktmengen bzw. Schnitte oder Segmente des Würfels beschrieben werden können. Wird nur ein Prädikat mit einem spezifischen Wert vorgegeben, beschreibt dies eine Fläche, einen Schnitt durch den Würfel. Sind zwei Prädikate definiert, ergibt sich eine im Würfel angeordnete Linie. Auf der Linie bzw. der Fläche befinden sich wiederum Adresspunktmengen, die synonym für adressierte Objekte stehen. Dieses Wirkprinzip ist unverändert auf n Dimensionen übertragbar.

Ähnlichkeitsbasierte Selektion

Diese segmentgestützte Selektion im Such- und Analyseraum eröffnet die Option der hocheffizenten Auswahl angrenzender und damit ähnlicher Objekte, bei der das vorgegebene/erwartete Maß der Ähnlichkeit hierbei klar abgegrenzt werden kann.

Typische Anwendungsfälle hierfür sind beispielsweise bei Online-Shops im Kontext der Produktauswahl zu finden (z.B. suche ähnliche Fahrzeuge, Hotels oder Mietobjekte …). In der gleichen Weise lassen sich aber auch potenzielle Kunden mit ähnlichen Profile finden oder auch Verhaltensmuster von Personen oder Maschinen gegen »übliche« Referenzmuster abgleichen.

M-aus-N-Anfragen

Im täglichen Arbeitsumfeld begegnen uns Applikationen, welche die Selektion von Geschäftsobjekten anhand von vielfältigen Attributen zulassen. So diese komfortabel gestaltet sind, bleibt es dem Anwender überlassen, welche von diesen er für die Geschäftsobjektauswahl heranziehen möchte. Er trifft also eine echte N-aus-M-Auswahl. Ohne multidimensionale Indizes lassen sich diese Recherchen nicht effizient ausführen. Dies gilt insbesondere, wenn die Operation auf eine sehr große Grunddatenmenge auszuführen ist, da der Zugriff über einen eindimensionalen Index nicht möglich wäre und somit immer ein Suchvorgang incl. Attributvergleich über den gesamten Datenbestand notwendig würde.

Multimedia-Datenbanken

Datenbanksysteme dienen mehrheitlich der Speicherung und dem Wiederauffinden von strukturierten, relativ einfachen Daten. Seit den neunziger Jahren besteht zunehmend das Bestreben, auch komplexere Informationen wie Texte, Vektorgrafiken, Bild-, Audio- und Video-Informationen mittels sogenannter Multimedia-Datenbanken zu verwalten. In diesem Kontext entstanden und entstehen neue Anforderungen hinsichtlich des Auffindens von Datenbankobjekten. Liegt der Bedarf bei den klassischen Datenbanksystemen noch primär in der »exakten« semantischen Adressierung von Datenbankobjekten, ist dies bei Multimedia-Datenbanken im Regelfall nicht mehr möglich. Hier werden die gewünschten Datenbankobjekte in der Regel im Rahmen eines Retrieval-Prozesses über vielfältige Merkmale »unscharf« spezifiziert. Soll dies durch einen Index performance-steigernd gestützt werden, muss dieser multidimensional sein und zugleich ähnlichkeitsbehaftete Suchanfragen unterstützen.

Geo-Informationssysteme

Geo-Informationssysteme speichern Daten über reale Objekte wie Personen, Flurstücke, Straßen, Flüsse etc. Diese Objekte werden durch ausgewählte Attribute beschrieben, z.B. Objekt-Typisierungen wie Bundesland, Gemarkung, Flurstücksbenennung …, Nutzungsart usw. Diese Informationen werden um Geometriedaten ergänzt, wie Lage, Form, Orientierung … Und nicht zuletzt werden die Objekte zueinander in Beziehung gesetzt: Person ist Eigentümer eines Flurstücks; Flurstück A ist Nachbarflurstück von B und Teil einer Gemarkung …

In den meisten Fällen werden all diese Informationen in den »üblichen« relationalen Datenbanken gespeichert. Von der Sache her handelt es sich dabei aber um 2- bis 4-dimensionale Daten (Flächeninformationen, Angaben zu Körpern bzw. 2-dimensionale Zeitreihen …)

Sollen diese Angaben in der Datenbank recherchiert werden, erweisen sich die klassischen eindimensionalen Indizes als ungeeignet. Folglich können die Datenbanken hierbei nur auf Suchoperationen zurückgreifen, welche bei großen Datenbeständen zwangsläufig inperformant werden.

Ein multidimensionaler Index liefert damit die ideale Infrastruktur, diese Herausforderungen mit der erforderlichen Performance zu lösen.

Zusammenfassung

Jeder Zugriff auf Datenbankobjekte ist mit einem semantischen Adressierungsvorgang verbunden. Dieser kann datenbankintern auf Suchoperationen, Adressberechnungen oder einem Mix aus beiden abgebildet werden. Welche Adressierungsform hierbei die bessere Performance hervorbringt ist von vielen Einflussfaktoren abhängig. Die Entscheidung hierüber liegt in den meisten Fällen beim Datenbank-Optimizer.

Indizes unterschiedlicher Couleur finden bei der Transformation von semantischen in physische Adressen Anwendung. Dabei gilt, dass die Verwendung von Indizes insbesondere dann mit Laufzeitvorteilen verbunden ist, wenn die Anfragen sehr selektiv sind.

Die in den etablierten Datenbanksystemen vorhandenen »klassischen« eindimensionalen Indizes beruhen in ihrem inneren Wirkprinzip auf sehr einfachen Größer-Kleiner-Vergleichsoperationen. Dies vereinfacht die Indexerstellung und -pflege, schränkt aber zugleich dessen Einsatzspektrum ein.

Bereichsumfassende, negierende und ODER-behaftete und echte multidimensionale Operationen können durch diese Index-Form nicht oder nur sehr aufwendig abgebildet werden, was zu einem schlechten Laufzeitverhalten der betroffenen Datenbankabfragen führt.

Abhilfe können hier nur multidimensionale Indizes schaffen. Mit Callidior wird ein solcher Index bereitgestellt, der erstmalig extrem große Suchräume verwalten kann.