Über unsMediaKontaktImpressum
Lothar Flatz 24. Februar 2015

Faktenbasierte Indexierung

Die Idee einer grundlegenden faktenbasierten Indexierung wurde in einem lockeren Gespräch bei einer Tasse Kaffee geboren. Ich war als Oracle-Berater mit einem Tuning Auftrag bei einem Stammkunden. Mein Kontaktmann bei meinem Kunden, ein erfahrener DBA war wieder einmal bei seinem Lieblingsthema angelangt. "Ich wette, mindestens 30% unserer Indexe sind überflüssig. Dadurch sind unsere Ausführungspläne auch so instabil. Und es braucht Platz. Am liebsten würde ich die Indexierung einmal komplett überprüfen lassen."

Im Inneren musste ich ihm Recht geben. Tatsächlich werden bei eingekauften Applikationen die Indexe in der Regel von den Entwicklern erstellt. Die Entwickler erleben das System selten unter Volllast. Außerdem ist die Indexierung nie an die Bedürfnisse eines bestimmten Kunden angepasst. In der Regel müssen wir dann nachindexieren. Die Grundlage, die die Entwickler geschaffen haben, wird aber nicht mehr infrage gestellt. Es kommen lediglich neue Indexe dazu. Das Resultat ist dann meist ein unübersichtlicher Dschungel aus Indexen.

Wie wäre es, die Sache einmal von Grund auf neu und richtig zu machen? Die Fakten dazu haben wir ja in der Hand. Die Oracle Datenbank ist eine unerschöpfliche Quelle von Informationen. Über die Informationen die im Shared Pool und in AWRs gespeichert sind, müsste es doch möglich sein, eine geeignete Indexierung zu erstellen.

Einige Monate später war ich tatsächlich in der Lage, eine solche große Aufgabe anzugehen. Einer meiner Kunden hatte genug von halbherzigen Lösungen und wollte endlich die Indexstruktur seiner wichtigsten Applikation in Ordnung wissen. Am Anfang brauchte ich relativ viel Überredung, um den Kunden zu überzeugen, dass wir die Indexierung von Grund auf neu machen müssten. Ich war nämlich der Meinung, dass wir uns bei Verbesserungen auf Basis der bestehenden Indexierung nur verzetteln würden. Die Entscheidung, ob wir einen Index jetzt löschen sollten oder eben doch nicht, würde uns lähmen. Solche fruchtlosen Diskussionen hatte ich andernorts schon gehabt.

Endlich fiel ein Entscheid. Wir löschten auf unserer Testdatenbank alle Indexe und fingen von Grund auf neu an. Natürlich hätten wir nun einfach einen grossen SQL Tuning Set erstellen und diesen durch den SQL Tuning Adviser abarbeiten lassen können. An diesem Vorgehen missfiel uns aber, dass wir uns blind auf die Entscheidungen SQL Tuning Adviser verlassen müssten. Auch würden wir das Wissen und die Erfahrungen der Entwickler und der DBAs nicht verwenden können. Ganz klar werden die Argumente hier noch einmal zusammengefasst: "First, while the automated tools reduce the complexity of the physical design process, it is still non trivial to identify a representative workload that can be used to drive the physical design in its entirety. Second, automated tools do not consider all factors that impact physical design (e. g., the impact of replication architectures)" [1]. Tatsächlich weisen neue Schweizer Forschungen darauf hin, dass die automatische Lösung mittels Tools für große Gesamtaufgaben problematisch ist [2][3].

Wir entschlossen uns stattdessen, ein halbautomatisches Vorgehen zu wählen, bei dem jeder Schritt erklärt und verstanden werden kann. Jedes Teammitglied konnte seine Gedanken einbringen. Am Schluss hatten wir eine klar begründete Lösung, zu der jeder stehen konnte.

Hinweis: Der folgende Text bezieht sich auf die Indexierung einer Onlinedatenbank. Daher ist, wenn in diesem Artikel von Index die Rede ist, der konventionelle B* Index gemeint. Für ein Data Warehouse gelten natürlich andere Indexierungsregeln, welche den Rahmen des Artikels sprengen würden.

Vorbereitende Überlegungen

Verlangsamung von DML Operationen

In technischen Publikationen findet man manchmal den folgenden Satz: ein Index verlangsamt eine Insert Operation um 100%. Das stimmt aber nur, wenn nur ein Satz eingefügt wird. Sind es viele Sätze in einem Insert ... Select Operation, so ist die gemessene Verlangsamung wesentlich höher. Ich konnte in Tests mit 1 Million Datensätzen und mehr einen Verlangsamungsfaktor von 200-300% messen. Diese zusätzliche Verlangsamung entsteht dadurch, das der B*Baum reorganisiert werden muss.

Noch schlimmer ist ein Update auf Indexspalten, welches in seinen Auswirkungen einen Delete mit nachfolgendem Insert entspricht. Dies erzeugt also den doppelten Aufwand im Vergleich zu einem Insert, aber nur für die Indexe mit den von der Änderung betroffenen Spalten. Die ultimative Verlangsamung durch Index Wartung tritt bei einem Row Movement zwischen zwei Partitionen auf. Dies entspricht einem Update auf allen lokalen Indexen.

Das Fazit und eine der wichtigsten Regeln für eine gute Indexierung ist also: man sollte so wenige Indexe wie möglich anlegen. Bei Onlineapplikationen mit einem Schwerpunkt auf einen Einzelsatz Insert kann man etwas liberaler sein, bei Data Warehouse sollte man im Interesse der ETL Verarbeitung mit Indexen eher sparsamer sein.

Ein oder mehrspaltige Indexe

Manchmal sieht man in Applikationen nur einspaltige Indexe. Das ist ein schlimmer Fehler. Wenn ein Index bereits existiert und den Overhead in die DML aufgenommen hat, dann sollte man ihn auch nutzen und möglichst alle sinnvollen Suchspalten kombinieren. Auch eine wenig selektive Spalte mit nur zwei unterschiedlichen Werten kann als zusätzliche Spalte in einem Index immerhin eine Verbesserung um Faktor zwei bewirken.

Ein Beispiel: Der dreispaltige Index {Nachname, Vorname, Alter} kann drei verschiedene Suchen unterstützen:

  • {Nachname, Vorname, Alter}
  • {Nachname, Vorname}
  • {Nachname}

Die folgenden Suchen können nicht unterstützt werden.

  • {Vorname, Alter}
  • {Alter}
  • {Vorname}

Die klassischen B* Indexe unterliegen leider solchen Beschränkungen.
Wer die ultimative Flexibilität und Performance haben möchte, kann den mehrdimensionalen Index der Firma Dimesio verwenden, der beliebige Kombinationen von Suchkriterien parallel auswerten und verknüpfen kann.

Fazit: Es ist besser einen bestehenden Index um eine Spalte zu erweitern, als einen zusätzlichen Index zu erzeugen.

Reihenfolge der Spalten im Index

Ein hartnäckiger Mythos der Indexierung ist, dass man selektive Spalten an den Anfang des Index stellen soll. Dies würde es ermöglichen, im Indexbaum schneller die relevanten Blöcke zu finden. In der Regel sind die Verbesserungen dafür marginal [4]. Eine wenig selektive Spalte am Anfang des Index hat sogar einen kleinen Vorteil gegenüber einer selektiven Spalte: der Index komprimiert besser.

Entscheidend für die Reihenfolge der Spalten im Index ist die Häufigkeit, mit der nach einer bestimmten Spalte gesucht wird. Habe ich beispielsweise einen Index über den Vor- und Nachnamen einer Person, so ist {Nachnamen, Vorname} einem Index mit der Reihenfolge {Vorname, Nachname} vorzuziehen, wenn häufiger nach Nachname alleine gesucht wird.

Eine Ausnahme kann hier eine sehr selektive Spalte am Anfang sein. Der Index I1 {Nachname, Geschlecht} ist auch dann besser als der Index I2{Geschlecht, Nachname} wenn häufiger nach Geschlecht als nach Nachname gesucht wird, solange nur auch relativ häufig nach Nachnamen allein gesucht wird. In diesem Falle kann der Index I1 verwendet werden. Der Index I2 wird für eine Suche nach Geschlecht alleine nicht verwendet werden, da das Geschlecht in der Regel zu wenig selektiv ist.

Fazit: Die Wahl der besten Reihenfolge der Spalten ist der schwierigste Teil im Designprozess des B* Indexes. Wer dies allerdings richtig macht, kann mit einem Index mehrere Suchen unterstützen.

Foreign Keys Indexieren?

Ich denke es ist unumstritten, dass der Primary Key in aller Regel indexiert werden wird. Im Fall der Foreign Key ist das nicht ganz so klar, aber ich würde dennoch empfehlen, die Foreign Keys zu indizieren. Dies aus zwei Gründen:

  • da es beim Löschen eines Satzes zu unangenehmen Sperren der abhängigen Sätze kommen kann, sofern ein Foreign Key Constraint existiert.
  • Damit ein nested loop join in jede bestimmte Richtung möglich ist und somit der Optimizer in der Wahl des optimalen Zugriffspfades nicht zusätzlich eingeschränkt wird.

Fazit: Grundsätzlich hat es Vorteile, einen Foreign Key zu indexieren. Zumindest sollte man, wenn man mit einer Komplettindexierung produktiv geht, das Risiko eines nicht indexierten Foreign Keys scheuen. Später kann man bei reibungslosem Betrieb vereinzelte nicht benötigte Foreign Keys löschen.

Zieldefinition

Die vorangegangen Überlegungen erlauben uns die Definition von Qualitätskriterien welche für die Beurteilung der Lösung und des Vorgehens herangezogen werden:

  1. Vollständigkeit: Alle wesentlichen Abfragen sollen, so ferne die Abfragecharakteristik eine Index sinnvoll macht durch einen Index unterstützt werden.
  2. Minimalität: Die vollständige Unterstützung der Abfragen soll mit der kleinstmöglichen Anzahl von Indexen erreicht werden.
  3. Effizienz: Alle Filterkriterien, welche die Indexwirkung maßgeblich verbessern sollen im Index enthalten sein

Die Ausprägungen der Zielkriterien können und sollen in jedem Projekt neu definiert werden. Es ist schwer, hier allgemeine Richtlinien zu geben, da die einzelnen Applikationen unter Umständen stark abweichende Bedürfnisse haben können. So könnte man beispielsweise festlegen, dass eine Abfrage dann als wesentlich gilt, wenn sie pro Woche mindestens 5-mal im Online-Betrieb vorkommt oder aber in einem regelmäßig ablaufenden Batchjob enthalten ist.

Chronik einer Gesamtindexierung

Vorbereitungsphase

Zunächst wurde ein Team aus allen Beteiligten gebildet. Da war einmal ich selbst als externer Berater für den Datenbankhersteller. Dann zwei Vertreter aus dem Entwicklungsteam des Applikationsherstellers und zwei DBAs als Vertreter des Softwarebetreibers. In zwei Sitzungen wurde das grobe Vorgehen bestimmt und die Grundregeln der Indexierung festgelegt:

  • Primär- und Fremdschlüssel sollten grundsätzlich automatisch ein Index bekommen.
  • Namenskonventionen wurden festgelegt.
  • Dem Design der Applikation wurde Rechnung getragen.
  • Die Art der physischen Speicherung (zum Beispiel tablespace) wurde festgelegt.

Datensammlungsphase

In dieser Phase versuchte man, möglichst viele Informationen über die Abfragebedingungen auf der Datenbank zu speichern. Dabei war es wichtig, möglichst alle wichtigen Verarbeitungen in die Auswertung mit ein zu beziehen. Also nicht nur tägliche Verarbeitungen, sondern auch wöchentliche und monatliche Aktivitäten mussten Berücksichtigung finden. Dadurch zog sich diese Phase über mehrere Monate hin. Jedoch wurde die Arbeit von automatischen Sammeltools geleistet und von Seiten des Teams war relativ wenig zu tun. Im Wesentlichen wurden folgende Informationen gesammelt:

  • Die Häufigkeit und die Vergleichsoperatoren mit der nach einer bestimmten Spalte gesucht wir.
  • Die Kombination von Spalten, nach denen gleichzeitig gesucht wird und die Häufigkeit mit der dies geschieht.

Dies sind im Wesentlichen die gleichen Informationen, die die Datenbank zur Unterstützung der automatischen Statistikgeneriereung in der sys.col_usage$ sammelt. Ab der Version 11.2.0.2 werden auch Spaltenkombinationen unterstützt.

Das entsprechende Verfahren beschreibt Maria Colgan, eine Kollegin aus dem Oak Table Net und bis vor kurzem die Produktmanagerin des Optimizers, in ihrem Blog [5]. In früheren Datenbankversionen werden die Spaltenkombinationen nicht unterstützt und müssen daher aus den anderen Quellen hochgerechnet werden. Als Quellen kommen in Frage:

  • Die aktuellen Abfragen Shared Pool. Hier kann man die Suchkriterien ganz einfach aus den Filter und Access Predicates entnehmen.
  • Die top Statements aus dem AWR (dafür muss man leider einen reparse durchführen, da die Filter- und Access-Predicates in der  DBA_HIST_SQL_PLAN Tabelle leer sind).

Diese Möglichkeiten sind auch deshalb wichtig, weil man sich auf den Inhalt der col_usage$ nicht hundertprozentig verlassen kann. Ich habe schon Datenbanken gesehen, bei denen der Inhalt der col_usage$ nicht brauchbar war. Dies vermutlich aufgrund von Memorymangel. Es ist klar, dass dann natürlich auch die Statistikgenerierung in Mitleidenschaft gezogen wird. Ausserdem werden Informationen aus dem Dictionary verwendet:

  • Die Selektivität der einzelnen Spalten sowie die der verwendeten Kombinationen.
  • Primary Key und Foreign Key constraints.

Auswertungsphase

In dieser Phase werden die gesammelten Informationen zu einem fertigen Index Design verdichtet. Dies geschieht über mehrere Schritte, die tool-unterstützt aber halbautomatisch ablaufen. Bei schwierigen Design-Entscheidungen wird immer noch das menschliche Wissen als letzte Instanz hinzugezogen. Das Vorgehen folgt grob dem Muster des als Merge and Reduction bekannten Algorithmus [1].

Als Grundlage für die Arbeit dienen uns die in der Vorphase gefundenen Spaltenkombinationen. Im Grunde genommen könnte man aus jeder Spaltenkombination, die in Suchen auftaucht, einen Index machen. Das würde aber zu einem Überangebot an Indexen führen. Da jeder Index die DML Operationen verlangsamen kann [z.B. 5], sollen nur so viele Indexe wie nötig und so wenige wie möglich erstellt werden. In den folgenden Schritten wird also versucht, die Index Struktur hinsichtlich Preis/Leistung zu optimieren.

Grundindexierung

Meist wird man von einer Basisindexierung ausgehen können. Primary Keys bekommen in der Regel wie schon erwähnt ohne große Überlegung ebenfalls einen Index.

Eliminination

In dieser Phase nimmt man alle Suchkombinationen aus der Betrachtung, die man ohne große Leistungseinbußen weglassen kann. Das sind insbesondere:

  1. Alle Foreign- und Primary-Keys, die bereits im vorigen Schritt indexiert worden sind.
  2. Alle Suchkombinationen, die so wenig selektiv sind, dass sich kein Index lohnt.
  3. Alle Suchkombinationen, die bereits in anderen Suchkombinationen gleichwertig enthalten sind.

Betrachten wir einige Beispiele aus dem allgemein bekannten Bereich der Adress- und Personendaten:

Zu 2.: ein Index {Geschlecht} lohnt sich auf der Tabelle Person nicht, da die Suchspalte zu wenig selektiv ist. (Eine Ausnahme wäre hier eine Anwendung für Frauenfragen beim Militär, da hier häufig nach einem seltenen Wert gesucht wird. Dieses Beispiel zeigt, dass selbst scheinbar einfache Fälle nicht ohne Nachdenken entschieden werden können. Wieder einmal wird klar, vor welchen Schwierigkeiten eine vollautomatische Indexierung steht.)

Zu 3.: der Indexkandidat {Ort} auf der Tabelle Adresse wird eliminiert, wenn es eine andere häufige Suchkombination gibt, zum Beispiel {Ort, Straße} in der {Ort} bereits enthalten ist.

Dies kann man natürlich noch weiterführen. Der dreispaltige Index {Nachname, Vorname, Alter} auf der Tabelle Person kann drei verschiedene Suchen unterstützen:

{Nachname, Vorname, Alter}
{Nachname, Vorname}
{Nachname}

Die beiden letzten Suchkombinationen können also eliminiert werden.

An diesen Beispielen erkennt man, dass die Wahl der richtigen Reihenfolge der Spalten entscheidend für die Qualität eines flexiblen Indexdesigns ist. Eine optimale Indexierung unabhängig von der Spaltenreihenfolge ist mit dem konventionellen B*Index nicht möglich.

Synthese

In diesem Schritt versucht man die übrig gebliebenen Suchkombinationen zusammenzulegen und dadurch weitere Index-Kandidaten zu eliminieren. So kann man beispielsweise einen Foreign Key um weitere Suchkriterien erweitern. Wenn zum Beispiel in der Tabelle Umsatz häufig nach {Artikelnummer, Verkaufsdatum} gesucht wird, ist es sinnvoll, einen bestehenden Foreign Key Index auf der Artikelnummer um das Feld  Verkaufsdatum zu erweitern.

Manchmal kann man auch durch eine leichte Verschlechterung des Index Design einen zusätzlichen Index-Kandidaten eliminieren. Als Beispiel seien die Suchkombinationen gegeben:

{Ort, Nachname, Vorname} und {Ort, Nachname, Geburtsdatum}

Der Indexkandidat {Ort, Nachname, Vorname, Geburtsdatum} kann die beiden oben gezeigten Kombinationen ersetzen. Zwar ist die Suche nach {Ort, Nachname, Geburtsdatum} nicht mehr so optimal, wie bei einem eigenen Index, jedoch kann die Verschlechterung wahrscheinlich in Kauf genommen werden, weil {Ort, Nachname} für sich gesehen bereits gute Suchkriterien sind. Man sieht, dass in diesem Schritt die Vernunft gesteuerte Entscheidung des menschlichen Designers besonders wichtig ist.

Tests und Umsetzung

Hat man alle diese Schritte durchlaufen, ist es relativ einfach, aus dem Ergebnis ein Index create Script zu bilden. Natürlich muss man das Ergebnis jetzt ausführlich testen. RAT bietet sich dabei als Mittel der Wahl an. Wenn man produktiv geht, sollte man auch Überwachungsmechanismen im Einsatz haben, die schnell in der Lage sind fehlende Indexe zu finden. Wir hatten ein eigenes Überwachungsskript, welches Ausführungspläne finden kann, welche durch suboptimale Indexierung entstehen und entsprechende Verbesserungsvorschläge macht. Natürlich kann man auch den Oracle Index Advisor verwenden, der für meinen Geschmack für diesen spezialisierten Zweck etwas umständlicher in der Handhabung ist. Die neue Indexstruktur zeigte sich in der Produktion erstaunlich stabil. In den ersten Monaten musste nur eine einstellige Anzahl Indexe nacherzeugt werden.

Resultate

In dem hier geschilderten Fall handelt es sich um eine Applikation, die spezialisierte Consultants der Firma Oracle schon seit Monaten optimiert hatten. Umso erfreulicher war es, das die Gesamtindexierung zusätzlich eine Platzersparnis von 30% und eine Performanceverbesserung von ebenfalls 30% erbrachte. Die Platzersparnis konnte im Folgenden noch verbessert werden, in dem man nicht benutzte Foreign Key Indexe löschen konnte.

Ein sehr erfreulicher Nebeneffekt der etwas überraschend kam, war eine verbesserte Stabilität der Execution Pläne. Da für einen bestimmten Zweck nur noch ein Index zur Verfügung steht und nicht mehrere, bleiben die Pläne stabiler und verändern sich nicht so leicht in Abhängigkeit von den Werten der Bindevariablen. Zudem erleichterte die neue Indexstruktur mit ihren klaren Regeln und ihrer einheitlichen Namensgebung die tägliche Arbeit der DBAs.

Ein Leiter einer DBA-Gruppe, welche dieselbe Applikation betrieb, überzeugte sich selbst bei einem Besuch von dem Resultat der Komplettindexierung. Er fasste seinen Eindruck wie folgt zusammen: „Die DBAs hier wirken so entspannt. Das will ich auch.“

Quellen

[1] Bruno, N. and Chaudhuri, S., 2007: "Physical design refinement: The ‘merge-reduce’ approach". ACM Trans. Database Syst. 32, 4, 28.
[2] Borovica,  Alagiannis, Ailamaki, 2012: „Automated Physical Designers: What You See is (Not) What You Get“, DBTest’12, Scottsdale, AZ, U.S.A.
[3] Weikum,  Moenkeberg, Hasse, Zabback, 2002: „Self-tuning Database Technology and Information Services: from Wishful Thinking to Viable Engineering“, Proceedings of the 28th VLDB Conference, Hong Kong, China
[4] richardfoote.wordpress.com
[5] Oracle® Database 2 Day DBA 12c Release 1 (12.1), Kapitel 8. managing Indexes

Autor

Lothar Flatz

Lothar Flatz war 15 Jahre Mitarbeiter der Oracle Corp., u.a. als Mitglied der Real World Performance Group. 2012 wurde er in das anerkannte Oak Table Net aufgenommen. In seiner beruflichen Tätigkeit behandelt er alle Aspekte der...
>> Weiterlesen
botMessage_toctoc_comments_9210