Wirkungsweise

Callidior basiert auf einem multidimensionalen Index, der Suchräume in bisher nicht gekonnter Größe abbilden kann und so extrem flexible und zugleich performante Abfragen auf sehr große Datenbestände ermöglicht.

Suchen und Finden

Eigentlich sind wir alle am Suchen. Ständig! Fast unser ganzes Leben lang, nach dem »Richtigen«, den verschwundenen Schlüsseln, der Telefonnummer der besten Freundin, dem Auto, der neuen Postanschrift des Bruders, einem neuen und besseren Job, den aktuellen Nachrichten vom Tage.

Suchen, suchen, suchen, nach Ob- und Subjekten selbst, oder auch nach Informationen zu und über diese.

In einigen Fällen wissen wir, wo »ES« ist. Dann wird nicht gesucht, wir adressieren einfach. Beispielsweise unser Auto, das nicht irgendwo herumsteht, sondern wohlgeordnet in der bekannten Garage.

Oft fehlen uns diese Informationen aber. Dann wird es aufwendig! Nun gilt es zu suchen.

Wissend um die damit verbundenen Mühen, bedienen wir uns seit jeher Hilfsmitteln, die den Vorgang erträglicher gestalten. Seien es das Telefonbuch zum Auffinden der Rufnummer des Kollegen, die Patientenkartei, welche Schwester Gerda den einfachen Zugriff auf die Krankenhistorie von Herrn Meyer ermöglicht oder auch das Inhalt- und Stichwortverzeichnis der Bedienungsanleitung einer Kaffeemaschine, um auf direktem Weg zur Dokumentation der Mahlwerk-Konfiguration zu gelangen.

Index, der Turbolader des Datenzugriffs

Patientenakten im Gesundheitswesen

All diese Hilfsmittel fassen wir unter dem Begriff »Index« zusammen.

Der Index dient einem einzigen Zweck: der Senkung des Aufwands zur Suche nach Objekten und deren Informationen.

Die Frage seiner Nutzbarkeit zu Suchzwecken ist dabei kontextbezogen.

Schwester Gerda, am Empfang der Arztpraxis stehend, wird einen anderen Index zum Auffinden von Herrn Meyer benötigen, als ihr Chef, der auf Basis der Krankenakten eine Studie über alle zuckerkranken Patienten seiner Praxis erstellen möchte. Schwester Gerda recherchiert per Name und Vorname des Patienten, ihr Chef fragt bestimmte Krankheitsbilder ab.

Indizes »verorten« also Ob- oder auch Subjekte in einem Betrachtungsraum. Bei Schwester Gerda ist es der Raum der Namen und Vornamen, bei ihrem Chef der Suchraum der Krankheitsbilder. Zugleich weisen Indizes den Weg zur physischen Position des gewünschten Ob- oder Subjekt und deren Daten, hier die Krankenakte.

Einer für alle, alle für einen

Der Aufbau anwendungs- und damit suchpfadspezifischer Indizes besitzt eine lange Tradition und führt bis in die Zeit der Karteikartensysteme zurück. Diese lange Historie liegt aber weniger darin begründet, dass Spezial-Indizes sonderlich erstrebenswert wären. Die Entscheidung für spezialisierte Formen als Konterpart ihrer universellen Geschwister begründet sich vielmehr in deren leichten Implementierbarkeit.

So kann der zweidimensionale Suchraum unseres Praxisbeispiels aus Name und Vorname durch eine Verkettung der beiden Merkmale sehr einfach auf einen Vektor projiziert werden. Die Krankenakten werden dabei zuerst nach dem Namen und innerhalb gleicher Familiennamen nach dem Vornamen sortiert abgelegt. Dieses einfache Wirkprinzip lässt sich auf zusätzliche Attribute erweitern, z.B. den Geburtsort, das Geburtsjahr usw.

Und weil das Wirkprinzip so schön einfach ist, findet es auch noch heute bei den elektronischen Datenbanken in technologischer Nachfolgerschaft der Karteikästen Anwendung. Wir kennen es unter der Bezeichnung »B-Tree-Index«.

Weil einfach eben nur einfach, nicht immer aber gut ist

randlochkarte2
Randlochkarte
Quelle: Wikimedia

Dass die mit der Suchraumprojektion verbundene technische Vereinfachung zuweilen ein zu enges Nutzungskorsett erzeugt, spürten schon die Anwender der vergangenen Papp-Datenbanken. Wollte der Praxis-Chef aus seiner Patientenkartei die Zuckerkranken eines bestimmten Jahrgangs ermitteln, benötigte er einen neuen spezialisierten Index, wenn Krankheitsbild und Geburtsjahr dem Namen und Vornamen im bestehenden Index nachgeordnet waren. Alternativ blieb ihm nur die Option, den gesamten Datenbestand nach der Methode »Wühlkiste«, Karte für Karte, zu durchsuchen.

Hegte er gar den Wunsch, im Index nicht nur ein primäres Krankheitsbild, sondern gegebenenfalls mehrere abzubilden, war das Ende der Möglichkeiten einer projektionsbasierten Vorgehensweise erreicht.

Findige Köpfe haben deshalb schon im Vor-Computer-Zeitalter eine Alternative erfunden, welche die Einschränkungen des projektionsbasierten Index auflöste und beliebige Index-Attribute in frei wählbarer Kombination als Selektionskriterium zuließ. Sie wurde unter der Bezeichnung »Randlochkarte« bekannt. Nun konnten Name, Vorname, Geburtsjahr und Krankheitsbild auf jeweils eine Kante der Karteikarte abgebildet und zu beliebigen Anfragen kombiniert oder auch singulär verwendet werden. Zugleich konnte der Index mehrere Krankheitsbilder zu einem Patienten ausweisen.

Auch die Randlochkarte hat zwischenzeitlich ihr elektronisches Pendant gefunden, den Bitmap-Index.

Randlochkarte wie Bitmap-Index können als »echte« multidimensionale Indizes im Gegensatz zu den projektionsbasierten »unechten« Varianten auch dann eingesetzt werden, wenn mit einer deutlich höheren Varianz in der Abfrage-Gestaltung zu rechnen ist. Echte multidimensionale Indizes sind in ihrer Nutzbarkeit deshalb deutlich variabler als ihre »unechten« Geschwister.

Dieses hohe Maß an Flexibilität kommt heute insbesondere Business-Intelligence-Anwendungen zugute, zu deren Kerneigenschaften die flexible Abfrage-Gestaltung gehört.

Bei der nun sichergestellten flexiblen Indexnutzung könnte man meinen, dass alle Wünsche erfüllt seien, wäre da nicht ein verbleibendes Problem:

Die Löcher der Randlochkarte wie die Bits des Bitmap-Index stehen jeweils synonym für eine mögliche Ausprägung des Suchattributs, also beispielsweise für das Geburtsjahr oder den Anfangsbuchstaben des Namens. Ist das Loch bei »N« gestanzt oder das Bit auf der N-Position gesetzt, bedeutet dies, dass der Name mit »N« beginnt. Ist es nicht gesetzt, beginnt der Namen nicht mit »N«. Gleichwohl ist der Platz für Löcher auf dem Kartenrand ebenso wie für die Bits in der Bitmap deutlich beschränkt. Es können also nur wenige Ausprägungen der Selektionsattribute abgebildet werden, wenn der Ressourcenbedarf nicht unermesslich gesteigert werden soll. Zugleich ist die Zahl der Kartenkanten bzw. die verfügbare Bitmap-Länge an physikalische Restriktionen gebunden. Der durch diese Indexform abbildbare Suchraum ist deshalb hinsichtlich seiner Kapazität deutlichen Einschränkungen unterworfen.

Dies ist ein Manko, mit welchem projektionsbasierte Indizes nicht behaftet sind. Hieraus begründet sich, dass sich der Einsatz echter multidimensionaler Indizes bisher auf die Business Intelligence Applikationen beschränkt, da hier das Volumen der Suchräume entsprechend klein gefasst werden kann.

Die Definition einer »sinnvollen Rasterung« des Suchraums, welche auf der einen Seite das Indexvolumen begrenzt und andererseits eine gleichbleibende Selektivität gewährleistet, ist deshalb eine »große Kunst«.

randlochkarten_verschluesselungskarte
Verschlüsselungskarte
Quelle: Wikimedia

In der Vergangenheit lag diese bei den Designern der Randloch-Schlüsselkarten. Diese haben beispielsweise in Kenntnis des Bestandes deutscher Namen beim Design der Schlüsselkarte für die Patientendatei die Entscheidung getroffen, den Startbuchstabensequenzen »S«, »Sch« und »St« in der Dimension der Familiennamen jeweils gesonderte Löcher zuzuweisen, »X«, »Y« und »Z« aber nur auf ein gemeinsames Loch zu legen.

Beim Entwurf von Business-Intelligence-Lösungen der Gegenwart liegt die analoge Verantwortung beim Designer des Data Warehouse, welcher die auf den Dimensionen befindlichen Kategorien zu bestimmen und das Volumen der resultierenden multidimensionalen Data Marts abzuschätzen hat.

Derartige Einschränkungen sind für klassische operative Anwendungen nicht hinnehmbar. Sie verwenden deshalb primär projektionsbasierte Indizes und müssen hierbei deren geringere Flexibilität im Zugriff akzeptieren. Werden unterschiedliche Objekt-Zugriffspfade benötigt, gelangen im Bedarfsfall mehrere spezialisierte Indizes zum Einsatz. Dies ist eine gute Alternative, solange die Varianz »im Rahmen« bleibt und die möglichen alternativen Zugriffspfade zum Zeitpunkt der Systementwicklung erkennbar sind. Ist dies nicht gegeben, verbleibt schlussendlich nur noch die hochflexible aber rechen- wie zeitaufwendige Suchoperation über den gesamten Datenbestand. In der Zeit der Karteikästen war das mit der Beschau jeder einzelnen Karte der gesamten Kartei gleichzusetzen.

Mit wachsendem Volumen des Basisbestands werden die so erzielbaren Antwortzeiten natürlich immer weniger befriedigend. Deshalb wird die Strategie verfolgt, die Leistungsfähigkeit der Datenhaltungssysteme durch Parallelisierung der Suchoperationen nahezu beliebig zu steigern. Dieser Ansatz steht als zentraler Gedanke bei allem, was heute unter dem Schlagwort »Big Data« firmiert.

Callidior kann es besser

 

Cluster-Bildung innerhalb des Suchraums
Cluster-Bildung innerhalb des Suchraums

Callidior greift nun die Idee des echten multidimensionalen Index wieder auf und bietet einen Weg, der die bekannte Abfrage-Flexibilität des Bitmap-Index gewährleistet, hierbei aber die bisher bekannten Volumengrenzen des Suchraums aufbricht, analog zum projektionsbasierten Index. Damit werden die Vorteile beider Vorgehensweisen vereint und zugleich deren Nachteile aufgehoben.

Dies wird möglich, weil es gelungen ist, die Kunst der Designer von Randlochkarten in einen entsprechenden Algorithmus zu fassen. Dieser kann zu indizierende Datenbestände in multidimensionalen Suchräumen »verorten«. Er erstellt hierbei eine entsprechende »kosmische Karte« in welcher die Daten-Cluster ebenso zu erkennen sind, wie die unbesetzten Leerräume.  Somit können automatisiert sehr effiziente »Randloch-Schlüsselkarten« erstellt werden, die schonend mit den Ressourcen (hier die Bitmap-Ketten) umgehen, da für die leeren Suchraumbereiche keine Index-Ressourcen »vergeudet« werden. Im Verbindung mit der rekursiven Anwendung dieser Technik zur stufenweisen Verfeinerung der Cluster lassen sich unendlich große multidimensionale Suchräume über beliebige Datenbestände aufbauen und effizient verwalten.

Mehr draus machen

Callidior an sich ist »nur« eine Basistechnologie, die aus sich heraus noch keinen Nutzen bringt. Dieser entsteht erst, wenn die Technologie in den geeigneten Anwendungskontext gesetzt wird.

Es sollte selektiv zugehen!

Dabei gilt es zu beachten, dass ein Index, egal welcher Couleur, nur dann seine Stärken in die Waagschale werfen kann, wenn die Anfragen an diesen sehr selektive Ergebnismengen bewirken. Liefert eine Anfrage 50% des Basisdatenbestand im Ergebnis zurück, dann ist die Strategie des klassischen »Durchwühlens« im Regelfall performanter. Indexbasierte Anfragen sollten Ergebnismengen in einem Umfang von < 1% des Basisdatenbestands hervorbringen. Besonders effizient kann ein Index wirken, wenn die Ergebnismenge leer bleibt.

Zudem gilt: »Big is Beautiful!«

Das heißt: Je umfangreicher die absolute Basisdatenmenge ist, um so eher bewirkt der Indexeinsatz eine Leistungsverbesserung.

Multidimensional ist super!

Es ist naheliegend, dass Callidior überall dort besonders wirkungsvoll ist, wo die zu indizierenden Objekte selbst bereits einen multidimensionalen Charakter aufweisen. Dann leitet sich für den Suchraum mehr oder weniger zwangsläufig die Notwendigkeit einer Multidimensionalität ab. Dies trifft beispielsweise auf alle Anwendungsfälle zu, bei denen die zu betrachtenden Objekte geometrisch dargestellt oder modelliert werden, zu finden in CAD-Systemen des Maschinenbaus und der Architektur, aber auch in kartographierenden GEO-Informationssystemen. Für all diese Systeme scheiden die klassischen projektionsbasierten Indizes aus, da diese Anfragen wie:

  • »Welche Rechtecke Y1 bis Yn werden von einem Rechteck X vollständig umschlossen?«

oder

  • »Welche Rechtecke Y1 bis Yn schneiden das Rechteck X?«

nicht beantworten können. Callidior besitzt hierfür die Fähigkeiten.

Schüsse in den leeren Raum

Zuweilen ist auch die Information, dass im vorliegenden Datenbestand keine objektbezogenen Informationen vorliegen genau das, was von Interesse ist. Geht es beispielsweise darum, die Qualität von Erzeugnissen zu überwachen, sind Abweichungen von der Norm zu erkennen. Solange »die Norm« in Worte und Regeln gefasst werden kann, ist alles noch relativ leicht abzuhandeln. Schwieriger wird es, wenn »das Normale« nicht mehr formal beschreibbar ist.

Hier kann ein hochdimensionaler »Such-Raum« hilfreich werden, in dem jede Dimension für eine Messgröße steht, die von Sensoren »überwachend« mit Daten versorgt werden. Für den »Normalfall« werden so im Such-Raum sukzessive Cluster der Normalität entstehen. Treten nach einer Lernphase Treffer außerhalb der Cluster auf, sind diese zumindest verdächtig und bedürfen einer näheren Fehlerbetrachtung.

Tune up my App

Callidior-Integration
Callidior zur Beschleunigung von Datenbankabfragen

Das Jammern über die schlechte Performance von Anwendungen gehört heute fast schon zum guten Ton eines Anwenders. Nun laufen sicher unsere Wünsche immer den aktuellen Möglichkeiten davon und nicht jede Klage ist wirklich berechtigt. Trotzdem existieren genügend Beispiele, für welche die kritischen Bemerkungen zurecht geäußert werden. Dies gilt insbesondere dann, wenn Geschäftsabläufe im Unternehmen durch zu lange Reaktionszeiten von Applikationen negativ beeinflusst werden.

Die Ursachen für ein schlechtes Laufzeitverhalten von Anwendungen können ebenso vielfältig sein, wie beim Stottern des Motors in einem alten Auto. In einer deutlichen Überzahl der Fälle erweist sich jedoch die Interaktion der Applikation mit ihrer Datenbank als der Schwachpunkt.

Nun ist auch hier noch der Strauß möglicher Fehlerquellen von erheblichem Umfang, und nicht bei allen Problemen ist der Einsatz eines Index die probate Medizin.

Gelegentlich lassen sich aber einzelne Datenbankabfragen als die zeitfressenden Störenfriede im Applikations-Getriebe lokalisieren. Und dann ist die Zeit für den Indexeinsatz gekommen.

Kann bei der Analyse der kritischen Abfragen festgestellt werden, dass die klassischen Indizes zur Beschleunigung des Zugriffs nicht befähigt sind und der Datenbank-Optimizer deshalb auf das Durchsuchen des gesamten Tabelleninhalts zurückgreifen muss, kann Callidior als Vorschalteinheit vor den Datenbankserver platziert werden und die originären SQL-Abfragen soweit modifizieren, dass massive Geschwindigkeitsgewinne zu erzielen sind. Im produktiven Einsatz wurden hierbei Laufzeitverkürzungen bis auf das Eintausendstel des Originalwertes nachgewiesen.

Callidior ist einzigartig!

  • multidimenional,
  • hochleistungsfähig und
  • trotzdem leichtgewichtig