“f.d. CW ist der Text nix”. Na danke. Ist also nix brauchbares drin. 20.000 Anschläge, genau wie gefordert und dann kommt die Pressefraktion mit soetwas. Aber eigentlich mag ich die Pressefraktion und es war auch nicht mein Ziel für die CW zu schreiben. Zumal, wenn es keine Vorgaben über den Stil gibt.

Ich puste den Text über MaxDB gerade auf für eine Veröffentlichung im Web. Eines der Standardargumente für MaxDB konnte ich natürlich nicht auslassen. Reorganisationsfreiheit. Klingt gut. Doch was meint das? Kurz und knapp und auf die MySQL Welt übertragen bedeutet es, es gibt kein OPTIMIZE TABLE gibt, weil es nicht benötigt wird. Als ich einen kleinen Exkurs geschrieben habe, bin ich über ein paar Details gestolpert, die mir zuvor noch nie aufgefallen sind. Es sind eigentlich nur zwei Kleinigkeiten: DYNAMIC und eine Sortierung. Doch zunächst der Werbespot.

Grundlagen zur Wiederholung

Ein verbreitetes Verfahren zur Datenablage bei Datenbanken sind B[ayer]-Baum Strukturen. MaxDB verwendet einen B-Baum für jede Tabelle, einen B-Baum pro Sekundärindex und einen B-Baum für jede LONG (BLOB, …) Spalte einer Tabelle. MaxDB verwendet eine B*-Baum Variante für die Bäume.

Zwei Eigenschaften von B*-Bäumen sollte man sich merken: der Baum ist hohl und der Füllgrad ist hoch. B+ und B*-Bäume legen nur in den Blattseiten die zu speichernden Daten ab. Alle inneren Knoten speichern nur Verweise auf andere Knoten, sie sind hohl. Bei einem B-Baum werden in den inneren Knoten bereits Nutzdaten abgelegt. Weil besonders viele Verweise in den inneren Knoten eines hohlen Baumes abgelegt werden können, neigt der Baum dazu eher in die Breite als in die Höhe zu wachsen.

Ein hoher Füllgrad in B*-Bäumen wird durch die Bevorzugung der Verteilung von Daten auf Nachbarseiten gegenüber der Erzeugung von neuen Seiten erzielt. Wenn eine Blattseite in einem B*-Baum überläuft, d.h. wenn die Datenbelegung einen Schwellenwert überschreitet, dann wird nicht sofort eine neue Blattseite allokiert und in den Baum eingehängt. B*-Baum Varianten versuchen zunächst die Daten auf ein Nachbarseite zu verteilen. Unterm Strich sagt man B-Bäumen, die zufällige Schlüsselwerte speichern, einen mittleren Füllgrad von etwa 50% nach. B*-Baum Implementierungen erzielen üblicherweise Werte von über 66%, Sedgewick nennt sogar Zahlen bis zu 77% in “Algorithms in C”.

Ein kleines Beispiel macht die Zahlen zum Füllgrad anschaulicher. Als Eckdaten gilt: eine Seite soll zu mindestens 25% und zu maximal 75% gefüllt sein, bevor eine Ausgleichsoperation durchgeführt wird. Eine Seite in einem B-Baum erreicht einen Füllstand von 76%. Eine Ãœberlaufbehandlung wird notwendig. Wie beschrieben, wird eine neue Seite allokiert und die Daten sollen zu gleichen Teilen verteilt werden. Es entstehen zwei Seiten mit 76% / 2 = 38% Füllgrad. Bei einem B*-Baum würde zunächst geprüft werden ob der Nachbarknoten noch Daten aufnehmen kann. Der Nachbarknoten sei zu 54% gefüllt und kann demnach noch etwas aufnehmen. Wie zuvor beim B-Baum werden die Daten der überlaufenden Seite und die Daten der noch auffüllbaren Seite zu gleichen Teilen verteilt auf beide Seiten verteilt. Es entstehen zu zwei Seiten mit (76% + 54%) / 2 = 65% Füllgrad. 38% gegen 65%, gar nicht übel.

Ganz so einfach sind die Milchmädchen Rechnungen in der Praxis natürlich leider nicht und die wirkliche Datenlage und die Seitengröße sind noch gar nicht beachtet worden, aber die Tendenz ist klar. MaxDB versucht Speicherplatz zu sparen. Das ist eine schlaue Idee. Datenseiten sind die kleinste I/O-Einheit von MaxDB. Teure Hauptspeicherpuffer und preisweitere persistente Speicher können nur eine bestimmte Menge an Datenseiten aufnehmen. Es ist den Medien egal ob in den Datenseiten jeweils kaum etwas drin ist oder nicht. MaxDB versucht viel in die einzelnen Datenseiten reinzupacken und hofft darauf, die teuren Ressourcen besser zu nutzen. Doch nicht nur für den die Speichereffizient ist eine kompakte Storage sinnvoll. Desto mehr Datensätze auf eine Datenseite passen, desto weniger I/O-Zugriffe bedarf es um eine bestimmte Anzahl von Seiten zu lesen. Es ist also auch performanter.

Wie machen es die anderen? MyISAM: B-Baum, InnoDB: B+-Baum. Aber, das ist eine gaanz andere Geschichte, besonders MyISAM.

MaxDB’s Reorganisationsfreiheit

Die Berliner MaxDB Entwickertruppe, mehr Leute als man zunächst glauben mag, ist immer stolz wie Oskar auf die Reorganisationsfreiheit. Streng gesehen ist das Wort verwirrend. Auch MaxDB muß seine Speicherstrukturen reorganisieren und aufräumen, weil jede Änderungsoperation zu Degenerierungen führen kann. Deshalb gibt sich MaxDB als Streber und Kleingeist. Statt das Chaos zu überblicken, wird immer gleich aufgeräumt.

Wann immer notwendig werden die B*-Bäume zur Laufzeit neu ausbalanziert. Es gibt keine Indizes, keine Tabellen, nichts was man irgendwie mit Wartungskommandos behandeln muß. Das bedeut, daß man sich nicht mit den Kommandos rumschlagen muß, keine Wartungsfenster ein planen muß in denen es zu Lastspitzen kommt durch die Reorganisation und letztlich heißt das: MaxDB macht arbeitslos. Der Harken ist, daß eine permanente Reorganisation eine permanente Last erzeugt. Das drückt die Spitzenleistung. Dramatisch ist dieser Effekt jedoch in aller Regel nicht, wie Praxiserfahrungen zeigen. Doch dazu morgen mehr.

MaxDB macht drei Dinge neben dem permanenten ausbalanzieren der B*-Bäume: Sort by Insertion, Delete in Place, Update in Place. Alle Operationen versuchen die bewegte Masse möglichst klein zu halten. Wo immer es geht, wird nur auf einer Datenseite ausgeglichen. Für das Verständnis der drei Algorithmen ist es notwendig zu wissen, wie MaxDB Daten auf einer Datenseite anordnet. MaxDB verwendet Seiten mit einer Größe von 8kB (InnoDB: 16kB). Die Größe kann durch eine Neukompilierung geändert werden. Eine Seite ist aufgeteilt in drei Bereiche: einen unsortierten Datenbereich, freien Speicher und eine sortierte Zeigerliste. Das erste Element in der Datenseite ist der Datenbereich mit den Nutzdaten. Der Datenbereich wächst vom Anfang der Datenseite ausgehend. Am Ende der Datenseite ist eine sortierte Zeigerliste abgelegt, die Zeiger auf die in der Datenseite gespeicherten, einzelnen Datensätze enthält. Die Zeigerliste wächst vom Ende der Seite ausgehend. Nutzdaten und Zeigerliste wachsen also aufeinander zu. Zwischen den zwei Bereichen kann freier Speicher vorhanden sein.

Die Zeigerliste auf einer Datenseite hält MaxDB stets in der Reihenfolge der Primärschlüssel sortiert. MaxDB macht dies, um bei einem sequentiellen Scan einer Tabelle in Primärschlüsselreihenfolge, keine Sortieraktionen ausführen zu müssen. So weit keine Ãœberraschungen.

Eine Frage kam bei mir auf als ich die entsprechende Dokumentation von MaxDB las. Die Dokumentation läßt offen wie innerhalb einer Datenseite ein Datensatz gesucht wird. Dokumentiert ist lediglich, daß die Positionsliste durchsucht wird. Die Positionsliste enthält Zeiger zu den Datensätzen nicht jedoch die Schlüsselwerte. Bei einer Suche anhand des Schlüsselwertes wird MaxDB deshalb die Positionsliste auslesen und zum Datensatz springen müssen, um den Schlüsselwert des Datensatzes zu erhalten und mit dem gesuchten Wert vergleichen zu können. Unklar ist, ob die Positionsliste sequentiell durchsucht wird oder eine binäre Suche erfolgt.

Zurück zur Reorganisationsfreiheit.

Sort by Insertion

Das ist einfach. Datensatz an die unsortierte Liste von Daten auf der Seite anhängen, Zeigerliste aktualisieren und sortieren fertig. Die große und damit nur aufwendig zu sortierende Datenliste wächst ungeordnet. Die kleine und damit schneller sortierbare Zeigerliste wird aktualisert. Bislang ist mir noch nie aufgefallen, daß MaxDB die Datenliste sortiert, wenn eine Ausgleichsoperation notwendig ist. Begründet wird dies damit, daß man beim Kopieren von einer Datenseite in die andere in diesem Fall mit Blockoperationen arbeiten kann, also gleich ganze Bereiche statt nur einzelner Datensätze zu kopieren. Was mich hier wundert, ist daß die Sortierung günstiger sein soll als einige memcpy()/memmove() Aufrufe mehr. Als jemand der keine C-Programme schreibt, ist mir diese Jagd auf Funktionsaufrufe, die möglicherweise noch einen Context Switch zwischen User und Kern benötigen, fremd.

Delete in Place

Beim Delete in Place löscht MaxDB einen Datensatz aus dem Datenbereich und entfernt den Zeiger aus der Positionsliste. Die im Datenbereich entstandene Lücke wird sofort geschlossen. Hierfür werden Datensätze verschoben und die Positionsliste aktualisiert. Wie bereits eingangs gesagt, wird MaxDB implizit Ausgleichsoperationen ausführen, falls eine Seite zu wenig Daten enthält. Sollte die Seite unter den Schwellenwert für den Minimalfüllstand fallen, wird MaxDB die Seite auflösen und ggf. auch den B*-Baum neu balanzieren.

Update in Place

Update in Place ist etwas aufwändiger zu beschreiben, weil drei Fälle betrachtet werden müssen. Es können sich der Schlüssel eines Datensatzes und/oder die Größe des Datums verändern. Im einfachsten Fall wird ein Datensatz aktualisert ohne, daß sich Schlüssel oder Datensatzlänge ändern. Wenn dies der Fall ist kann der Datensatz an seinem aktuellen Speicherplatz verbleiben und muß einfach nur überschrieben werden. In der Zeigerliste, ist keine Änderung notwendig, weil sich der Datensatz nicht verschoben hat.

Mehr aufzuräumen gibt es, wenn sich die Länge des Datensatzes ändert. MaxDB beläßt in diesem Fall den Datensatz an seinem aktuellen Speicherort aber verschiebt alle nachfolgenden Datensätze auf der Seite, sofern möglich. Wird der geänderte Datensatz kürzer dann werden alle nachfolgenden Datensätze in Richtung Anfang der Datenseite verschoben, um die entstandene Lücke zu schließen. Wächst der geänderte Datensatz, werden alle nachfolgenden Datensätze in die Richtung der Positionsliste, also in Richtung des Endes der Datenseite verschoben. Da sich hierbei viele Positionen ändern, müssen die Einträge in der Zeigerliste aktualisiert werden, die nach den Verschiebungen nicht mehr korrekt sind.

Falls sich der Schlüsselwert eines Datensatzes ändert, dann versucht MaxDB gar nicht erst die Operation auf einer Datenseite ausgeführt werden kann. MaxDB testet nicht ob der neue Schlüsselwerte in dem Bereich von Schlüsselwerten liegt, die auf der aktuellen Datenseite gespeichert werden können. MaxDB nimmt an, daß sich der Schlüsselwert signifikant ändert und nur selten eine Aktualisierung auf derselben Datenseite möglich ist, die den geänderten Datensatz bislang aufgenommen hat. Folgerichtig wird die Aktualisierung als Löschung mit anschließendem Neuanlegen ausgeführt.

DYNAMIC

Mann kann MaxDB anweisen weniger Ausgleichsoperationen auszuführen. Was das genau bedeutet ist leider nicht dokumentiert. Ich werde mal nachfragen. Wenn eine Tabelle mit dem AttributDYNAMIC angelegt wird, dann soll zwar etwas Speicherplatz vergeudet werden und der Fullgrad sinken, aber es ist weniger Rechnenleistung notwendig. Rechnenleistung deshalb, weil natürlich alle Operationen auf den Datenseiten im Hauptspeicher ablaufen. Eine Seite wird natürlich in den Puffer geladen, bevor das Jonglieren mit den Inhalten passiert. Und jonglieren mit Speicher kostet CPU Zeit.

Empfohlen wird DYNAMIC für Tabellen mit stark schwankender Größe und zufälligen Zugriffsmustern. Wie groß der Geschwindigkeitsvorteil ist, der durch vereinfachte Ausgleichsoperationen entsteht, ist nicht dokumentiert. Ich werde es bei Gelegenheit einmal ausmessen.

Leider fehlt DYNAMIC in der aktuellen Online-Dokumentation. Hier ein Syntaxbeispiel: CREATE TABLE t1 (col1 INTEGER) DYNAMIC.

Ja, und wie steht InnoDB im Vergleich zu MaxDB da? Gar nicht übel! Details ein anderes Mal.

Ende der Werbepause.