Ein Artikel von Lothar Flatz, Senior Principal Consultant, Diso AG

Im zweiten Teil seines Artikels, wie man eine gesalzene Banane vermeidet, zeigt Lothar Flatz den Weg zur Lösung auf. Lothar Flatz ist Mitglied des Oak Tables und Oracle ACE sowie Inhaber des Oracle ACE Ehrentitels der Oracle Corp.

Auf dem Weg zur Lösung

Ich stiess in meiner beruflichen Laufbahn gelegentlich auf diesen Typ Abfrage, da es sich um eine typische Call-Center-Abfrage handelt. Jedes Mal, wenn mir jemand sagte „Unsere Call-Center-Software ist maximal optimiert und reagiert sofort“, regte ich an, nach „Müller“ in „Bern“ oder nach „Meier“ in „Zürich“ zu suchen.
Das Ergebnis waren immer lange Gesichter und eine lange Wartezeit.

Nachdem ich mich immer wieder mit diesem Typ Abfrage beschäftigt hatte, kam ich zu dem Schluss, dass die Abfrage tatsächlich von dem Problem der „Throw-away“-Datensätze beherrscht, also „throw-away“-dominiert ist, wie ich dies im Rest des Textes nennen werde.

Lassen Sie uns Abbildung 4 erneut ansehen. Nur der orange Teil ist das Ergebnis. Der Rest ist „throw-away“.

Abb. 4: Mengendiagramm für die Müller-in-Bern-Suche zum Zweiten.

Tatsächlich ist der “Throw-away”-Anteil weit grösser als das Ergebnis. Das heisst also, die Abfrage ist „throw-away“-dominiert.

Ich kam nicht umhin, mich zu fragen: Warum sollte man den zusätzlichen Aufwand des Lesens eines Datensatzes aus der Tabelle betreiben, wenn man schon mit hoher Wahrscheinlichkeit weiss, dass man den Datensatz wegwerfen wird. Die Idee der gesalzenen Bananen entstand in meinem Kopf als eine Art Metapher für den Tabellenzugriff. Noch einmal, wenn Sie Ihre Banane wegwerfen wollen, warum sollten Sie sie zuerst schälen und salzen?

Ein Testszenario

Um meine Überlegungen im Zusammenhang mit der Müller-in-Bern-Abfrage zu testen, habe ich ein kleines Beispiel erzeugt und versucht, diesem eine ähnliche Datenverteilung zu geben, wie sie in der Realität vorhanden ist.

Ich habe das folgende Schema mit zwei Tabellen erzeugt:

Create table address (city_name      varchar2(30) not null,

             person_id               number(7) not null,

             data                    varchar2(200))

/

create Table person (person_id number(7) not null,

                    last_name varchar2(15) not null,

                    data         varchar2(200))

/

Wie Sie sehen können, ist das Schema stark vereinfacht. Es muss nicht realistisch sein, sondern nur im Sinne der  Diskussion ausreichen.

Ich habe ausreichende Indexe erzeugt, damit der Optimizer nicht in seiner Wahl eingeschränkt ist.

create Index city_idx1 on address (city_name, person_id) compress;

create Index city_idx2 on address (person_id, city_name) compress;

create Index person_idx1  on person(last_name, person_id) compress;

create Index person_idx2  on person(person_id, last_name) compress;

Unten sehen Sie nun die Abfrage, um die es im Beispiel geht.  Unter der Annahme, dass sie in einem OLTP-System abläuft, reicht es aus, nur die ersten zehn Datensätze zu lesen.

select * from (

select a.city_name, p.last_name, substr(p.data,1,1) p_data, substr(a.data,1,1) a_data

  from ibj.address a,

       ibj.person p

where p.person_id = a.person_id

  and a.city_name = ‚Bern‘

  and p.last_name = ‚Müller‘)

where rownum < 11

/

Ausführungspläne

Der klassische Ausführungsplan wäre nested loop join.

Abb. 5: Klassischer Ausführungsplan.

Wie wir schon wissen, ist die Achillesferse des Planes der teure Zugriff auf die beiden Tabellen.

Wie nicht anders zu erwarten, hat Oracle das Problem bereits erkannt und Gegenmassnahmen eingeleitet.

Oak Table Mitglied Randolf Geist schreibt:

Oracle introduced in recent releases various enhancements in that area – in particular in 9i the „Table Prefetching“ and in 11g the Nested Loop Join Batching using „Vector/Batched I/O“. 

The intention of Prefetching and Batching seems to be the same – they both are targeted towards the usually most expensive part of the Nested Loop Join: The random table lookup as part of the inner row source. By trying to „prefetch“ or „batch“ physical I/O operations caused by this random block access Oracle attempts to minimize the I/O waits. [3]

Beim “Table prefetch” wird der Zugriff auf die nicht treibende Tabelle ausserhalb des Nested Loops gemacht, wie in der Abbildung unten ersichtlich. Die Rowids der Zieltabelle werden innerhalb des Nested Loops gesammelt und zwischengespeichert. Die Rowids werden sortiert, und benachbarte Datenblöcke werden mit einem kleinen Vektor I/O gelesen.

Abb. 6: Table prefetching.

Nested Loop batching in Version 11 geht noch einen Schritt weiter, da der Zugriff auf die äussere Tabelle in einem kompletten separaten Verarbeitungsschritt erfolgt.

Ich zitiere aus [1], Abschnitt 11.6.3.1.2:

Oracle Database 11g Release 1 (11.1) introduces a new implementation for nested loop joins to reduce overall latency for physical I/O. When an index or a table block is not in the buffer cache and is needed to process the join, a physical I/O is required. In Oracle Database 11g Release 1 (11.1), Oracle Database can batch multiple physical I/O requests and process them using a vector I/O instead of processing them one at a time. As part of the new implementation for nested loop joins, two NESTED LOOPS join row sources might appear in the execution plan where only one would have appeared in prior releases. In such cases, Oracle Database allocates one NESTED LOOPS join row source to join the values from the table on the outer side of the join with the index on the inner side. A second row source is allocated to join the result of the first join, which includes the rowids stored in the index, with the table on the inner side of the join. 

Abb. 7: Nested Loop batching.

Wie Sie sehen werden, folgt unsere patentierte Lösung (siehe unten) – von uns der “Index Backbone Join”

genannt – demselben Grundgedanken, aber für sämtliche Tabellen in einer Abfrage.

Aber bevor es soweit ist, lassen Sie uns zunächst untersuchen, welchen Plan der Optimizer standardmässig wählt. Die Güte des Planes können wir anhand der Runtime-Statistiken beurteilen. Der Optimizer wählt Nested Loop batching.

Abb. 8: Runtime-Statistiken für Nested Loop batching.

Wie wir klar erkennen können, nimmt der Zugriff auf die Tabelle Adresse die meiste Zeit in Anspruch. Warum also sollten wir die Datensätze von der Tabelle lesen, von denen wir wissen, dass sie wahrscheinlich weggeworfen werden? Alle notwendigen Informationen zur Auswahl der korrekten Datensätze können bereits im Index gefunden werden. Was stört, ist, dass die Datenbank zwingend einen Zugriff auf die innere Tabelle einschaltet, wenn von dieser Tabelle Spalten benötigt werden, die nicht im Index stehen.

Man könnte jetzt alle benötigten Spalten in den Index schreiben, aber alles hat seine Grenzen. Ein Index, der zu groß wird, ist nicht mehr effizient. Und wie soll man wissen, welche Spalten zukünftige Abfragen benötigen werden?

Man muss also den intervenierenden Tabellenzugriff ausschalten und die beiden Indexe direkt verknüpfen. Das ist die Idee des “Index Backbone Join”. Der “Index Backbone Join” besteht aus zwei Phasen: In der ersten Phase werden nur die Indizes verknüpft, um die Rowids der Datensätze zu finden, die das Endergebnis bilden werden. Haben wir die Ergebnismenge in Form von Rowids, machen wir einen verzögerten Tabellenzugriff für beide Tabellen. Das ist der Hauptunterschied zu Nested Loop batching. Hier wird der Zugriff auf eine Tabelle  verzögert.

Der Optimizer ist nicht in der Lage, einen „Index Backbone Join” von sich aus vorzunehmen, aber wir können ihn mit einem manuellen Rewrite simulieren (siehe unten). Beachten Sie bitte, dass der NO_MERGE Hint im Beispiel zwingend erforderlich ist, um den Optimizer daran zu hindern, mittels eines Rewrite auf seinen Standardplan zu kommen.

select * from (

select a.city_name, p.last_name, substr(p.data,1,1) p_data,

       substr(a.data,1,1) a_data

  from ibj.person p,

       ibj.address a,

       (select /*+ NO_MERGE  */ p.rowid p_rowid, – phase 1

               a.rowid a_rowid

           from ibj.address a,

                ibj.person p

           where p.person_id = a.person_id

            and a.city_name = ‚Bern‘

            and p.last_name = ‚Müller‘

         ) i

where p_rowid = p.rowid

  and a_rowid = a.rowid)

where rownum < 11

/

Vor jedem Lauf wurde der Buffer-Cache geleert. Daher sind die Ergebnisse vergleichbar.

Fig. 9: Runtime statistics für einen simulierten „Index Backbone Join“.

Wenn wir den enormen Beschleunigungsfaktor betrachten, erübrigt sich jeder Kommentar.

Schlussfolgerungen

Die Idee des “Index Backbone Join” erlaubt es, Ausführungspläne aus einem anderen Blickwinkel zu betrachten.

Es gibt Spalten, die für einen Ausführungsplan essentiell sind. Zum Beispiel solche, die in der where-Klausel  oder in Joins verwendet werden.

Im obigen Beispiel werden nur zwei Tabellen verknüpft.

Allerdings lässt sich der Ansatz leicht verallgemeinern, so dass in einer ersten Phase so viele Indizes, die für den wesentlichen Teil der Abfrage erforderlich sind, verknüpft werden. Diese Verknüpfung mehrerer Indexe bildet das Rückgrat des Ausführungsplans. Daher der Name „Index Backbone Join“.

Eine Grundvoraussetzung ist eine geeignete Indexierung. Es werden jedoch keine zusätzlichen Indizes benötigt, sondern vorhandene Indizes müssen lediglich um zusätzliche Spalten erweitert werden.

Im Gegenzug winken schnellere und robustere Ausführungspläne.

Danksagung

Ich danke meinen Freund und Miterfinder Björn Engsig, der das US-Patent 2011/0119249 A1 mit mir zusammen hält. Björn hat wertvolle Verbesserungen zum Konzept des „Index Backbone Join“ beigetragen. Ich schätze seinen scharfen Verstand und seine klare Sicht der Dinge.

Auch bei Tim Gorman und Randolf Geist möchte ich mich für die freundliche und professionelle Kritik bedanken. Alle Fehler in diesem Dokument gehen natürlich ausschließlich zu meinen Lasten. Randolf wies mich darauf hin, dass Jonathan Lewis eine ähnliche Idee in seinem Blog beschrieben hat [4].

Nebenbei bemerkt war es Jonathans wegweisende “Fan hit ratio”-Präsentation, die mich zu dem Titel dieses Textes inspiriert hat.

Quellverweise:

[1] Oracle® Database Performance Tuning Guide

[2] http://afatkulin.blogspot.ch/2009/01/consistent-gets-from-cache-fastpath.html

[3] http://oracle-randolf.blogspot.ch/2011/07/logical-io-evolution-part-2-9i-10g.html

[4] http://jonathanlewis.wordpress.com/2010/05/18/double-trouble/

[5] http://fritshoogland.wordpress.com/2013/07/07/the-oracle-db-file-parallel-read-wait-event/

Fragen? Senden Sie Lothar Flatz eine E-Mail: lflatz@diso.ch.

Diso AG – Der Daten- und Cloud-Experte

Die Diso AG ist ein renommierter IT-Dienstleister und langjähriger Oracle-Vertriebspartner in der Schweiz mit Schwerpunkten in den Bereichen Datenbanken und Cloud-Lösungen. Diso bietet ihren Kunden beispielsweise die Oracle Plattform as a Service-Lösung und die dazugehörige Datenmigration an. Kunden profitieren des Weiteren vom Komplettlösungsangebot im Sinne von Planung, Integration, Support inklusive Betrieb und Überwachung von IT-Infrastrukturen und Datenbanksystemen.
Im Bereich Software-Engineering entwickelt Diso massgeschneiderte IT und Software-Lösungen für unternehmensspezifische Anwendungen, wann immer sinnvoll mit einem mobile-first Ansatz. Zudem ist Diso Spezialist wenn es um die Software-basierte Optimierung von Performance geht. Auf die Kompetenz des traditionsreichen IT-Dienstleisters und Mittelständlers vertrauen bereits namhafte Kunden aus den Schwerpunktbranchen Banken, Versicherungen Detailhandel und öffentliche Verwaltung.
Die Diso designt wandlungsfähige IT-Systeme, entwickelt massgeschneiderte Software und ermöglicht die performante Verwendung und Auswertung von Informationen.