=Paper=
{{Paper
|id=None
|storemode=property
|title=Auffinden von Spaltenkorrelationen mithilfe proaktiver und reaktiver Verfahren
|pdfUrl=https://ceur-ws.org/Vol-1020/paper_09.pdf
|volume=Vol-1020
|dblpUrl=https://dblp.org/rec/conf/gvd/Buchse13
}}
==Auffinden von Spaltenkorrelationen mithilfe proaktiver und reaktiver Verfahren==
https://ceur-ws.org/Vol-1020/paper_09.pdf
Auffinden von Spaltenkorrelationen mithilfe proaktiver und
reaktiver Verfahren
Katharina Büchse
Friedrich-Schiller-Universität
Institut für Informatik
Ernst-Abbe-Platz 2
07743 Jena
katharina.buechse@uni-jena.de
KURZFASSUNG Keywords
Zur Verbesserung von Statistikdaten in relativen Datenbank- Anfrageoptimierung, Spaltenkorrelation, Feedback
systemen werden seit einigen Jahren Verfahren für das Fin-
den von Korrelationen zwischen zwei oder mehr Spalten 1. EINFÜHRUNG
entwickelt. Dieses Wissen über Korrelationen ist notwen-
dig, weil der Optimizer des Datenbankmanagementsystems Die Verwaltung großer Datenmengen benötigt zunehmend
(DBMS) bei der Anfrageplanerstellung sonst von Unabhän- leistungsfähigere Algorithmen, da die Verbesserung der Tech-
gigkeit der Daten ausgeht, was wiederum zu groben Fehlern nik (Hardware) nicht mit dem immer höheren Datenauf-
bei der Kostenschätzung und somit zu schlechten Ausfüh- kommen heutiger Zeit mithalten kann. Bspw. werden wis-
rungsplänen führen kann. senschaftliche Messergebnisse aufgrund besserer Messtech-
Die entsprechenden Verfahren gliedern sich grob in proak- nik immer genauer und umfangreicher, sodass Wissenschaft-
tive und reaktive Verfahren: Erstere liefern ein gutes Ge- ler sie detaillierter, aber auch umfassender analysieren wol-
samtbild über sämtliche vorhandenen Daten, müssen dazu len und müssen, oder Online-Shops speichern sämtliche ihrer
allerdings selbst regelmäßig auf die Daten zugreifen und be- Verkaufsdaten und werten sie aus, um dem Benutzer passend
nötigen somit Kapazität des DBMS. Letztere überwachen zu seinen Interessen zeitnah und individuell neue Angebote
und analysieren hingegen die Anfrageergebnisse und liefern machen zu können.
daher nur Korrelationsannahmen für bereits abgefragte Da- Zur Verwaltung dieser wie auch anderer Daten sind (im
ten, was einerseits das bisherige Nutzerinteresse sehr gut wi- Datenbankbereich) insbesondere schlaue Optimizer gefragt,
derspiegelt, andererseits aber bei Änderungen des Workloads weil sie für die Erstellung der Anfragepläne (und somit für
versagen kann. Dafür wird einzig bei der Überwachung der die Ausführungszeit einer jeden Anfrage) verantwortlich sind.
Anfragen DBMS-Kapazität benötigt, es erfolgt kein eigen- Damit sie in ihrer Wahl nicht völlig daneben greifen, gibt
ständiger Zugriff auf die Daten. es Statistiken, anhand derer sie eine ungefähre Vorstellung
Im Zuge dieser Arbeit werden beide Ansätze miteinan- bekommen, wie die vorhandene Datenlandschaft aussieht.
der verbunden, um ihre jeweiligen Vorteile auszunutzen. Da- Hierbei ist insbesondere die zu erwartende Tupelanzahl von
zu werden die sich ergebenden Herausforderungen, wie sich Interesse, da sie in hohem Maße die Ausführungszeit einer
widersprechende Korrelationsannahmen, aufgezeigt und als Anfrage beeinflusst. Je besser die Statistiken die Verteilung
Lösungsansatz u. a. der zusätzliche Einsatz von reaktiv er- der Daten wiedergeben (und je aktueller sie sind), desto bes-
stellten Statistiken vorgeschlagen. ser ist der resultierende Ausführungsplan. Sind die Daten
unkorreliert (was leider sehr unwahrscheinlich ist), genügt
es, pro zu betrachtender Spalte die Verteilung der Werte
Categories and Subject Descriptors innerhalb dieser Spalte zu speichern. Treten in diesem Fall
später in den Anfragen Kombinationen der Spalten auf, er-
H.2 [Information Systems]: Database Management; H.2.4 gibt sich die zu erwartende Tupelanzahl mithilfe einfacher
[Database Management]: Systems—Query processing statistischer Weisheiten (durch Multiplikation der Einzel-
wahrscheinlichkeiten).
Leider versagen diese ab einem bestimmten Korrelations-
General Terms grad (also bei korrelierten Daten), und zwar in dem Sinne,
Theory, Performance dass die vom Optimizer berechneten Schätzwerte zu stark
von der Wirklichkeit abweichen, was wiederum zu schlech-
ten Ausführungszeiten führt. Diese ließen sich u.U. durch die
Wahl eines anderen Plans, welcher unter Berücksichtigung
der Korrelation vom Optimizer erstellt wurde, verringern
oder sogar vermeiden.
Zur Veranschaulichung betrachten wir eine Tabelle, wel-
th che u. a. die Spalten A und B besitzt, und eine Anfrage,
25 GI-Workshop on Foundations of Databases (Grundlagen von Daten-
banken), 28.05.2013 - 31.05.2013, Ilmenau, Germany. welche Teile eben dieser Spalten ausgeben soll. Desweiteren
Copyright is held by the author/owner(s). liege auf Spalte B ein Index, den wir mit IB bezeichnen wol-
len, und es existiere ein zusammengesetzter Index IA,B für Daher gibt es zwei grundsätzliche Möglichkeiten: Entwe-
beide Spalten. Beide Indizes seien im DBMS mithilfe von der schauen wir dem Benutzer auf die Finger und suchen
Bäumen (bspw. B∗ -Bäume) implementiert, sodass wir auch in den von ihm abgefragten Daten nach Korrelationen (das
(etwas informell) von flachen“ oder hohen“ Indizes spre- entspricht einer reaktiven Vorgehensweise), oder wir suchen
” ” ”
chen können. uns selbst“ ein paar Daten der Datenbank aus“, die wir
”
Sind beide Spalten unkorreliert, so lohnt sich in der Regel untersuchen wollen (und gehen somit proaktiv vor). Beide
die Abfrage über IA,B . Bei einer starken Korrelation bei- Vorgehensweisen haben ihre Vor- und Nachteile. Während
der Spalten dagegen könnte die alleinige Verwendung von im reaktiven Fall keine Daten speziell zur Korrelationsfin-
IB vorteilhaft sein, und zwar wenn die Werte aus Spalte A dung angefasst“ werden müssen, hier aber alle Daten, die
”
i.d.R. durch die Werte aus Spalte B bestimmt werden (ein bis zu einer bestimmten Anfrage nie abgefragt wurden, als
typisches Beispiel, welches auch in CORDS [7] anzutreffen unkorreliert gelten, müssen wir für die proaktive Methode
ist, wäre eine Tabelle Auto“ mit den Spalten A = Firma“ (also nur zum Feststellen, ob Korrelation vorherrscht) extra
” ”
und B = Marke“, sodass sich für A Werte wie Opel“ oder Daten lesen, sind aber für (fast) alle Eventualitäten gewapp-
” ”
Mercedes“ und für B Werte wie Zafira“ oder S-Klasse“ er- net.
” ” ”
geben). Statt nun im vergleichsweise hohen Index IA,B erst Interessanterweise kann es vorkommen, dass beide Metho-
passende A- und dann passende B-Werte zu suchen, werden den für ein und dieselbe Spaltenkombination unterschied-
sämtliche Tupel, welche die gewünschten B-Werte enthalten, liche Ergebnisse liefern (der Einfachheit halber beschrän-
über den flacheren Index IB geladen und überprüft, ob die ken wir uns hierbei auf die möglichen Ergebnisse korre-
”
jeweiligen A-Werte der Anfrage entsprechen (was aufgrund liert“ oder unabhängig“). Für den Fall, dass die reaktive
”
der Abhängigkeit der Regelfall sein sollte). Methode eine Spaltenkombination gar nicht betrachtet hat,
sollte das klar sein. Aber nehmen wir an, dass die Kombi-
Das Wissen über Korrelationen fällt aber natürlich nicht nation von beiden Methoden analysiert wurde. Da für die
vom Himmel, es hat seinen Preis. Jeder Datenbänkler hofft, Analyse höchstwahrscheinlich jeweils unterschiedliche Tupel
dass seine Daten unkorreliert sind, weil sein DBMS dann we- (Wertekombinationen) verwendet wurden, können sich na-
niger Metadaten (also Daten über die Daten) speichern und türlich auch die Schlüsse unterscheiden. Hier stellt sich nun
verwalten muss, sondern auf die bereits erwähnten statis- die Frage, welches Ergebnis besser“ ist. Dafür gibt es kei-
”
tischen Weisheiten zurückgreifen kann. Sind die Daten da- ne allgemeine Antwort, gehen wir aber von einer modera-
gegen (stark) korreliert, lässt sich die Erkenntnis darüber ten Änderung des Anfrageverhaltens aus, ist sicherlich das
nicht so einfach wie die Unabhängigkeit mit (anderen) sta- reaktive Ergebnis“ kurzfristig entscheidender, während das
”
tistischen Weisheiten verbinden und somit abarbeiten“. proaktive Ergebnis“ in die längerfristige Planung der Sta-
” ”
Nicht jede (eher kaum eine) Korrelation stellt eine (schwa- tistikerstellung mit aufgenommen werden sollte.
che) funktionale Abhängigkeit dar, wie es im Beispiel der
Fall war, wo wir einfach sagen konnten Aus der Marke folgt
”
die Firma (bis auf wenige Ausnahmen)“. Oft liebäugeln be- 2. GRUNDLAGEN
stimmte Werte der einen Spalte mit bestimmten Werten an- Wie in der Einleitung bereits angedeutet, können Korrela-
derer Spalten, ohne sich jedoch in irgendeiner Weise auf diese tionen einem Datenbanknutzer den Tag vermiesen. Um dies
Kombinationen zu beschränken. (In Stuttgart gibt es sicher- zu verhindern, wurden einige Methoden vorgeschlagen, wel-
lich eine Menge Porsches, aber die gibt es woanders auch.) che sich auf verschiedene Art und Weise dieser Problematik
Außerdem ändern sie möglicherweise mit der Zeit ihre Vor- annehmen (z. B. [7, 6]) oder sie sogar ausnutzen (z. B. [4, 8]),
lieben (das Stuttgarter Porschewerk könnte bspw. nach Chi- um noch an Performance zuzulegen. Letztere sind allerdings
na umziehen) oder schaffen letztere völlig ab (wer braucht mit hohem Aufwand oder der Möglichkeit, fehlerhafte An-
schon einen Porsche? Oder überhaupt ein Auto?). frageergebnisse zu liefern1 , verbunden. Daher konzentrieren
Deswegen werden für korrelierte Daten zusätzliche Sta- wir uns hier auf das Erkennen von Korrelationen allein zur
tistiken benötigt, welche nicht nur die Werteverteilung ei- Verbesserung der Statistiken und wollen hierbei zwischen
ner, sondern die Werteverteilung mehrerer Spalten wiederge- proaktiven und reaktiven Verfahren unterscheiden.
ben. Diese zusätzlichen Statistiken müssen natürlich irgend-
wo abgespeichert und, was noch viel schlimmer ist, gewartet 2.1 Proaktive (datengetriebene) Verfahren
werden. Somit ergeben sich zusätzlicher Speicherbedarf und Proaktiv zu handeln bedeutet, etwas auf Verdacht“ zu
”
zusätzlicher Aufwand, also viel zu viel von dem, was keiner tun. Impfungen sind dafür ein gutes Beispiel – mithilfe ei-
so richtig will. ner Impfung ist der Körper in der Lage, Krankheitserreger
zu bekämpfen, aber in vielen Fällen ist unklar, ob er die-
Da sich ein bisschen statistische Korrelation im Grunde se Fähigkeit jemals benötigen wird. Da Impfungen auch mit
überall findet, gilt es, die Korrelationen ausfindig zu ma- Nebenwirkungen verbunden sein können, muss jeder für sich
chen, welche unsere statistischen Weisheiten alt aussehen entscheiden, ob und wogegen er sich impfen lässt.
lassen und dazu führen, dass das Anfrageergebnis erst nach Auch Datenbanken können geimpft“ werden, allerdings
”
einer gefühlten halben Ewigkeit ausgeben wird. Ob letzte- handelt es sich bei langen Anfrageausführungszeiten (die
res überhaupt passiert, hängt natürlich auch vom Anfrage- wir ja bekämpfen wollen) eher um Symptome (wie Bauch-
verhalten auf die Datenbank ab. Wenn die Benutzer sich schmerzen oder eine laufende Nase), die natürlich unter-
in ihren (meist mithilfe von Anwendungsprogrammen abge- schiedliche Ursachen haben können. Eine davon bilden ganz
setzten) SQL-Anfragen in der WHERE-Klausel jeweils auf
1
eine Spalte beschränken und auf jedwede Verbünde (Joins) Da die Verfahren direkt in die Anfrageplanerstellung ein-
verzichten, dann ist die Welt in Ordnung. Leider lassen sich greifen und dabei auf ihr Wissen über Korrelationen aufbau-
Benutzer nur ungern so stark einschränken. en, muss, für ein korrektes Anfrageergebnis, dieses Wissen
aktuell und vollständig sein.
klar Korrelationen zwischen den Daten, wobei natürlich erst 2.2 Reaktive (anfragegetriebene) Verfahren
ein gewisses Maß an Korrelation überhaupt als krankhaft“ Während wir im vorherigen Abschnitt Vermutungen auf-
”
anzusehen ist. (Es benötigt ja auch eine gewisse Menge an gestellt und auf Verdacht gehandelt haben, um den Daten-
Bakterien, damit eine Krankheit mit ihren Symptomen aus- bankbenutzer glücklich zu machen, gehen wir jetzt davon
bricht.) Der grobe Impfvorgang“ gegen“ Korrelationen um- aus, dass den Benutzer auch weiterhin das interessieren wird,
” ”
fasst zwei Schritte: wofür er sich bis jetzt interessiert hat.
Wir ziehen also aus der Vergangenheit Rückschlüsse für
1. Es werden Vermutungen aufgestellt, welche Spalten-
die Zukunft, und zwar indem wir den Benutzer bei seinem
kombinationen für spätere Anfragen eine Rolle spielen
Tun beobachten und darauf reagieren (daher auch die Be-
könnten.
zeichnung reaktiv“). Dabei achten wir nicht allein auf die
”
2. Es wird kontrolliert, ob diese Kombinationen von Kor- gestellten SQL-Anfragen, sondern überwachen viel mehr die
relation betroffen sind oder nicht. von der Datenbank zurückgegebenen Anfrageergebnisse. Die-
se verraten uns nämlich alles (jeweils 100-prozentig aktuell!)
Entscheidend dabei ist, dass die Daten bzw. ein Teil der über den Teil der vorhandenen Datenlandschaft, den der Be-
Daten gelesen (und analysiert) werden, und zwar ohne da- nutzer bis jetzt interessant fand.
mit konkrete Anfragen zu bedienen, sondern rein zur Aus- Auf diese Weise können bspw. Statistiken erzeugt werden
führung des Verfahrens bzw. der Impfung“ (in diesem Fall [5, 11, 3] (wobei STHoles [5] und ISOMER [11] sogar in
”
gegen“ Korrelation, wobei die Korrelation natürlich nicht der Lage sind, mehrdimensionale Statistiken zu erstellen)
”
beseitigt wird, schließlich können wir schlecht den Datenbe- oder es lassen sich mithilfe alter Anfragen neue, ähnliche
stand ändern, sondern die Datenbank lernt, damit umzuge- Anfragen in ihrer Performance verbessern [12]. Sinnvoll kann
hen). Das Lesen und Analysieren kostet natürlich Zeit, wo- auch eine Unterbrechung der Anfrageausführung mit damit
mit klar wird, dass auch diese Impfung“ Nebenwirkungen“ verbundener Reoptimierung sein [9, 2, 10]. Zu guter letzt
” ”
mit sich bringt. lässt sich mithilfe dieses Ansatzes zumindest herausfinden,
Eine konkrete Umsetzung haben Ilyas et al., aufbauend welche Statistikdaten entscheidend sein könnten [1].
auf BHUNT [4], mit CORDS [7] vorgestellt. Dieses Verfah- In [1] haben Aboulnaga et al. auch schon erste Ansätze für
ren findet Korrelationen zwischen Spaltenpaaren, die Spal- eine Analyse auf Spaltenkorrelation vorgestellt, welche spä-
tenanzahl pro Spaltenkombination wurde also auf zwei be- ter in [6] durch Haas et al. ausgebaut und verbessert wurden.
grenzt.2 In Analogie zu CORDS werden in [1] und [6] nur Spaltenpaa-
Es geht folgendermaßen vor: Im ersten Impfschritt“ sucht re für die Korrelationssuche in Betracht gezogen. Allerdings
”
es mithilfe des Katalogs oder mittels Stichproben nach Schlüs- fällt die Auswahl der infrage kommenden Spaltenpaare we-
sel-Fremdschlüssel-Beziehungen und führt somit eine Art sentlich leichter aus, weil einfach alle Spaltenpaare, die in
Rückabbildung von Datenbank zu Datenmodell durch (engl. den Anfragen (mit hinreichend vielen Daten3 ) vorkommen,
reverse engineering“) [4]. Darauf aufbauend werden dann potentielle Kandidaten bilden.
”
nur solche Spaltenkombinationen als für die Korrelationssu- Während in [1] pro auftretendes Wertepaar einer Spalten-
che infrage kommend angesehen, deren Spalten kombination ein Quotient aus Häufigkeit bei Unabhängig-
”
keit“ und tatsächliche Häufigkeit“ gebildet und das Spal-
a) aus derselben Tabelle stammen oder ”
tenpaar als korreliert“ angesehen wird, sobald zu viele die-
”
b) aus einer Verbundtabelle stammen, wobei der Verbund ser Quotienten von einem gewissen Wert abweichen, setzen
( Join“) mittels (Un-) Gleichung zwischen Schlüssel- Haas et al. in [6] einen angepassten Chi-Quadrat-Test ein,
” um Korrelationen zu finden. Dieser ist etwas aufwendiger als
und Fremdschlüsselspalten entstanden ist.
die Vorgehensweise von [1], dafür jedoch nicht so fehleranfäl-
Zudem gibt es zusätzliche Reduktionsregeln (engl. pruning lig [6]. Zudem stellen Haas et al. in [6] Möglichkeiten vor, wie
”
rules“) für das Finden der Beziehungen und für die Aus- sich die einzelnen Korrelationswerte“ pro Spaltenpaar mit-
”
wahl der zu betrachtenden Spaltenkombinationen. Schließ- einander vergleichen lassen, sodass, ähnlich wie in CORDS,
lich kann die Spaltenanzahl sehr hoch sein, was die Anzahl eine Rangliste der am stärksten korrelierten Spaltenpaare
an möglichen Kombinationen gegebenenfalls ins Unermess- erstellt werden kann. Diese kann als Entscheidungshilfe für
liche steigert. das Anlegen zusätzlicher Statistikdaten genutzt werden.
Im zweiten Impfschritt“ wird für jede Spaltenkombinati-
”
on eine Stichprobe entnommen und darauf aufbauend eine
Kontingenztabelle erstellt. Letztere dient dann wiederum als
3. HERAUSFORDERUNGEN
Grundlage für einen Chi-Quadrat-Test, der als Ergebnis eine In [6] wurde bereits vorgeschlagen, dieses Verfahren mit
Zahl χ2 ≥ 0 liefert. Gilt χ2 = 0, so sind die Spalten voll- CORDS zu verbinden. Das reaktive Verfahren spricht auf-
ständig unabhängig. Da dieser Fall aber in der Praxis kaum grund seiner Effizienz für sich, während das proaktive Ver-
auftritt, muss χ2 einen gewissen Schwellwert überschreiten, fahren eine gewisse Robustheit bietet und somit bei Lern-
damit die entsprechende Spaltenkombination als korreliert phasen von [6] (wenn es neu eingeführt wird oder wenn sich
angesehen wird. Zum Schluss wird eine Art Rangliste der die Anfragen ändern) robuste Schätzwerte zur Erstellung
Spaltenkombinationen mit den höchsten χ2 -Werten erstellt eines Anfrageplans berechnet werden können [6]. Dazu soll-
und für die obersten n Kombinationen werden zusätzliche te CORDS entweder in einem gedrosselten Modus während
Statistikdaten angelegt. Die Zahl n ist dabei u. a. durch die des normalen Datenbankbetriebs laufen oder während War-
Größe des Speicherplatzes (für Statistikdaten) begrenzt. tungszeiten ausgeführt werden. Allerdings werden in [6] kei-
ne Aussagen darüber getroffen, wie die jeweiligen Ergebnis-
2
Die Begrenzung wird damit begründet, dass auf diese Weise
3
das beste Aufwand-Nutzen-Verhältnis entsteht. Das Verfah- Um aussagefähige Ergebnisse zu bekommen, wird ein ge-
ren selbst ist nicht auf Spaltenpaare beschränkt. wisses Mindestmaß an Beobachtungen benötigt, insb. in [6].
se beider Verfahren miteinander kombiniert werden sollten. ders interessant sein könnten, die möglicherweise eben gera-
Folgende Punkte sind dabei zu bedenken: de mit Korrelation einhergehen, spricht wiederum für eine
Art Hinweis“ an den Optimizer.
• Beide Verfahren liefern eine Rangliste mit den als am ”
stärksten von Korrelation betroffenen Spalten. Aller-
dings sind die den Listen zugrunde liegenden Korrela- 4. LÖSUNGSANSATZ
”
tionswerte“ (s. bspw. χ2 im Abschnitt über proaktive Da CORDS wie auch das Verfahren aus [6] nur Spalten-
Verfahren) auf unterschiedliche Weise entstanden und paare betrachten und dies mit einem sich experimentell erge-
lassen sich nicht einfach vergleichen. Liefern beide Lis- benem Aufwand-Nutzen-Optimum begründen, werden auch
ten unterschiedliche Spaltenkombinationen, so kann es wir uns auf Spaltenpaare begrenzen. Allerdings wollen wir
passieren, dass eine Kombination, die in der eine Lis- uns für die Kombination von proaktiver und reaktiver Kor-
te sehr weit unten erscheint, stärker korreliert ist, als relationssuche zunächst nicht auf diese beiden Verfahren be-
Kombinationen, die auf der anderen Liste sehr weit schränken, müssen aber doch gewisse Voraussetzungen an
oben aufgeführt sind. die verwendeten Verfahren (und das Datenmodell der Da-
tenbank) stellen. Diese seien hier aufgezählt:
• Die Daten, welche zu einer gewissen Entscheidung bei
den beiden Verfahren führen, ändern sich, werden aber 1. Entscheidung über die zu untersuchenden Spaltenkom-
in der Regel nicht gleichzeitig von beiden Verfahren ge- binationen:
lesen. Das hängt damit zusammen, dass CORDS zu ei-
nem bestimmten Zeitpunkt eine Stichprobe entnimmt • Das proaktive Verfahren betreibt reverse engi-
und darauf seine Analyse aufbaut, während das Ver- ”
neering“, um zu entscheiden, welche Spaltenkom-
fahren aus [6] die im Laufe der Zeit angesammelten binationen untersucht werden sollen.
Anfragedaten auswertet.
• Das Datenmodell der Datenbank ändert sich nicht,
• Da zusätzliche Statistikdaten Speicherplatz benötigen bzw. sind nur geringfügige Änderungen zu erwar-
und vor allem gewartet werden müssen, ist es nicht ten, welche vom proaktiven Verfahren in das von
sinnvoll, einfach für alle Spaltenkombinationen, die in ihm erstellte Datenmodell sukzessive eingearbei-
der einen und/oder der anderen Rangliste vorkommen, tet werden können. Auf diese Weise können wir
gleich zu verfahren und zusätzliche Statistiken zu er- bei unseren Betrachtungen den ersten Impfschritt“
”
stellen. vernachlässigen.
Zur Verdeutlichung wollen wir die Tabelle aller Firmen- 2. Datengrundlage für die Untersuchung:
wagen eines großen, internationalen IT-Unternehmens be-
trachten, in welcher zu jedem Wagen u. a. seine Farbe und • Das proaktive Verfahren entnimmt für jegliche zu
die Personal- sowie die Abteilungsnummer desjenigen Mitar- untersuchende Spaltenkombination eine Stichpro-
beiters verzeichnet ist, der den Wagen hauptsächlich nutzt. be, welche mit einem Zeitstempel versehen wird.
Diverse dieser Mitarbeiter wiederum gehen in einem Dres- Diese Stichprobe wird solange aufbewahrt, bis das
dener mittelständischen Unternehmen ein und aus, welches Verfahren auf Unkorreliertheit“ plädiert oder für
nur rote KFZ auf seinem Parkplatz zulässt (aus Kapazitäts- ”
die entsprechende Spaltenkombination eine neue
gründen wurde eine solche, vielleicht etwas seltsam anmu- Stichprobe erstellt wird.
tende Regelung eingeführt). Da die Mitarbeiter sich dieser
Regelung bei der Wahl ihres Wagens bewusst waren, fahren • Das reaktive Verfahren bedient sich eines Que-
sie alle ein rotes Auto. Zudem sitzen sie alle in derselben ry-Feedback-Warehouses, in welchem die Beob-
Abteilung. achtungen ( Query-Feedback-Records“) der An-
”
Allerdings ist das internationale Unternehmen wirklich fragen notiert sind.
sehr groß und besitzt viele Firmenwagen sowie unzählige
Abteilungen, sodass diese roten Autos in der Gesamtheit der 3. Vergleich der Ergebnisse:
Tabelle nicht auffallen. In diesem Sinne würde das proaktive
Verfahren CORDS also (eher) keinen Zusammenhang zwi- • Beide Verfahren geben für jede Spaltenkombinati-
schen der Abteilungsnummer des den Wagen benutzenden on, die sie untersucht haben, einen Korrelations-
”
Mitarbeiters und der Farbe des Autos erkennen. wert“ aus, der sich innerhalb des Verfahrens ver-
Werden aber häufig genau diese Mitarbeiter mit der Farbe gleichen lässt. Wie dieser genau berechnet wird,
ihres Wagens abgefragt, z. B. weil sich diese kuriose Rege- ist für uns unerheblich.
lung des mittelständischen Unternehmens herumspricht, es • Aus den höchsten Korrelationswerten ergeben sich
keiner so recht glauben will und deswegen die Datenbank zwei Ranglisten der am stärksten korrelierten Spal-
konsultiert, so könnte ein reaktives Verfahren feststellen, tenpaare, die wir unterschiedlich auswerten wol-
dass beide Spalten korreliert sind. Diese Feststellung tritt len.
insbesondere dann auf, wenn sonst wenig Anfragen an beide
betroffenen Spalten gestellt werden, was durchaus möglich Zudem wollen wir davon ausgehen, dass das proaktive Ver-
ist, weil sonst die Farbe des Wagens eine eher untergeordnete fahren in einem gedrosselten Modus ausgeführt wird und
Rolle spielt. somit sukzessive seine Rangliste befüllt. (Zusätzliche War-
Insbesondere der letztgenannte Umstand macht deutlich, tungszeiträume, bei denen das Verfahren ungedrosselt lau-
dass es nicht sinnvoll ist, Statistikdaten für die Gesamtheit fen kann, beschleunigen die Arbeit und bilden somit einen
beider Spalten zu erstellen und zu warten. Aber die Tat- schönen Zusatz, aber da heutzutage viele Datenbanken quasi
sache, dass bestimmte Spezialfälle für den Benutzer beson- dauerhaft laufen müssen, wollen wir sie nicht voraussetzen.)
Das reaktive Verfahren dagegen wird zu bestimmten Zeit- in der Rangliste des reaktiven Verfahrens, dann löschen wir
punkten gestartet, um die sich bis dahin angesammelten Be- die reaktiv erstellten Statistiken und erstellen neue Statis-
obachtungen zu analysieren, und gibt nach beendeter Ana- tiken mittels einer Stichprobe, analog zum ersten Fall. (Die
lyse seine Rangliste bekannt. Da es als Grundlage nur die Kombination beider Statistiktypen wäre viel zu aufwendig,
Daten aus dem Query-Feedback-Warehouse benötigt, kann u. a. wegen unterschiedlicher Entstehungszeitpunkte.) Wenn
es völlig entkoppelt von der eigentlichen Datenbank laufen. das proaktive Verfahren dagegen explizit unkorreliert“ aus-
”
gibt, bleibt es bei den reaktiv erstellten Statistiken, s. oben.
Ist die reaktive Rangliste bekannt, kann diese mit der (bis
dahin angefertigten) proaktiven Rangliste verglichen wer- Wenn jedoch nur das proaktive Verfahren eine bestimmte
den. Tritt eine Spaltenkombination in beiden Ranglisten auf, Korrelation erkennt, dann ist diese Erkenntnis zunächst für
so bedeutet das, dass diese Korrelation für die bisherigen An- die Benutzer unerheblich. Sei es, weil der Nutzer diese Spal-
fragen eine Rolle gespielt hat und nicht nur auf Einzelfälle tenkombination noch gar nicht abgefragt hat, oder weil er
beschränkt ist, sondern auch mittels Analyse einer repräsen- bis jetzt nur den Teil der Daten benötigt hat, der scheinbar
tativen Stichprobe an Wertepaaren gefunden wurde. unkorreliert ist. In diesem Fall markieren wir nur im Daten-
Unter diesen Umständen lassen wir mittels einer Stichpro- bankkatolog (wo die Statistiken abgespeichert werden) die
be Statistikdaten für die betreffende Spaltenkorrelation er- beiden Spalten als korreliert und geben dem Optimizer somit
stellen. Dabei wählen wir die Stichprobe des proaktiven Ver- ein Zeichen, dass hier hohe Schätzfehler möglich sind und
fahrens, solange diese ein gewisses Alter nicht überschritten er deswegen robuste Pläne zu wählen hat. Dabei bedeutet
hat. Ist sie zu alt, wird eine neue Stichprobe entnommen.4 robust“, dass der gewählte Plan für die errechneten Schätz-
”
werte möglicherweise nicht ganz optimal ist, dafür aber bei
Interessanter wird es, wenn nur eines der Verfahren auf stärker abweichenden wahren Werten“ immer noch akzep-
”
Korrelation tippt, während das andere Verfahren die ent- table Ergebnisse liefert. Zudem können wir ohne wirklichen
sprechende Spaltenkombination nicht in seiner Rangliste ent- Einsatz des reaktiven Verfahrens die Anzahl der Anfragen
hält. Die Ursache dafür liegt entweder darin, dass letzteres zählen, die auf diese Spalten zugreifen und bei denen sich
Verfahren die Kombination noch nicht analysiert hat (beim der Optimizer stark verschätzt hat. Übersteigt der Zähler
reaktiven Verfahren heißt das, dass sie nicht oder zu selten einen Schwellwert, werden mithilfe einer neuen Stichprobe
in den Anfragen vorkam), oder bei seiner Analyse zu dem (vollständige, also insb. mit Werteverteilung) Statistikdaten
Ergebnis nicht korreliert“ gekommen ist. erstellt und im Katalog abgelegt.
”
Diese Unterscheidung wollen wir insbesondere in dem Fall
vornehmen, wenn einzig das reaktive Verfahren die Korre- Der Vollständigkeit halber wollen wir hier noch den Fall
lation entdeckt“ hat. Unter der Annahme, dass weitere, erwähnen, dass eine Spaltenkombination weder in der einen,
”
ähnliche Anfragen folgen werden, benötigt der Optimizer noch in der anderen Rangliste vorkommt. Es sollte klar sein,
schnell Statistiken für den abgefragten Bereich. Diese sol- dass diese Kombination als unkorreliert“ angesehen und so-
”
len zunächst reaktiv mithilfe der Query-Feedback-Records mit für die Statistikerstellung nicht weiter betrachtet wird.
aus der Query-Feedback-Warehouse erstellt werden (unter
Verwendung von bspw. [11], wobei wir nur zweidimensionale
Statistiken benötigen). Das kann wieder völlig getrennt von 5. AUSBLICK
der eigentlichen Datenbank geschehen, da nur das Query-
Die hier vorgestellte Vorgehensweise zur Verbesserung der
Feedback-Warehouse als Grundlage dient.
Korrelationsfindung mittels Einsatz zweier unterschiedlicher
Wir überprüfen nun, ob das proaktive Verfahren das Spal-
Verfahren muss weiter vertieft und insbesondere praktisch
tenpaar schon bearbeitet hat. Dies sollte anhand der Ab-
umgesetzt und getestet werden. Vor allem muss ein passen-
arbeitungsreihenfolge der infrage kommenden Spaltenpaare
des Datenmodell für die reaktive Erstellung von Spalten-
erkennbar sein.
paarstatistiken gefunden werden. Das vorgeschlagene Ver-
Ist dem so, hat das proaktive Verfahren das entsprechen-
fahren ISOMER [11] setzt hier auf STHoles [5], einem Da-
de Paar als unkorreliert“ eingestuft und wir bleiben bei den
” tenmodell, welches bei sich stark überschneidenden Anfra-
reaktiv erstellten Statistiken, die auch nur reaktiv aktuali-
gen schnell inperformant werden kann. Für den eindimen-
siert werden. Veralten sie später zu stark aufgrund fehlender
sionalen Fall wurde bereits von Informix-Entwicklern eine
Anfragen (und somit fehlendem Nutzerinteresse), können sie
performante Lösung vorgestellt [3], welche sich aber nicht
gelöscht werden.
einfach auf den zweidimensionalen Fall übertragen lässt.
Ist dem nicht so, geben wir die entsprechende Kombina-
tion an das proaktive Verfahren weiter mit dem Auftrag,
Eine weitere, noch nicht völlig ausgearbeitete Herausfor-
diese zu untersuchen.5 Beim nächsten Vergleich der Ranglis-
derung bildet die Tatsache, dass das proaktive Verfahren im
ten muss es für das betrachtete Spaltenpaar eine konkrete
gedrosselten Modus läuft und erst sukzessive seine Rangliste
Antwort geben. Entscheidet sich das proaktive Verfahren für
erstellt. Das bedeutet, dass wir eigentlich nur Zwischener-
korreliert“ und befindet sich das Spaltenpaar auch wieder
” gebnisse dieser Rangliste mit der reaktiv erstellten Ranglis-
4
te vergleichen. Dies kann zu unerwünschten Effekten füh-
Falls die betroffenen Spalten einen Zähler besitzen, der bei ren, z. B. könnten beide Ranglisten völlig unterschiedliche
Änderungsoperationen hochgezählt wird (vgl. z. B. [1]), kön- Spaltenkombinationen enthalten, was einfach der Tatsache
nen natürlich auch solche Daten mit in die Wahl der Stich- geschuldet ist, dass beide Verfahren unterschiedliche Spal-
probe einfließen, allerdings sind hier unterschiedliche Aus-
gangszeiten“ zu beachten. ” tenkombinationen untersucht haben. Um solche Missstände
5
Dadurch stören wir zwar etwas die vorgegebene Abarbei- zu vermeiden, muss die proaktive Abarbeitungsreihenfolge
tungsreihenfolge der infrage kommenden Spaltenpaare, aber der Spaltenpaare überdacht werden. In CORDS wird bspw.
der Fall ist ja auch dringend. als Reduktionsregel vorgeschlagen, nur Spaltenpaare zu be-
trachten, die im Anfrageworkload vorkommen (dazu müssen [9] V. Markl, V. Raman, D. Simmen, G. Lohman,
von CORDS nur die Anfragen, aber nicht deren Ergebnis- H. Pirahesh, and M. Cilimdzic. Robust query
se betrachtet werden). Würde sich dann aber der Workload processing through progressive optimization. In ACM,
dahingehend ändern, dass völlig neue Spalten oder Tabel- editor, Proceedings of the 2004 ACM SIGMOD
len abgefragt werden, hätten wir dasselbe Problem wie bei International Conference on Management of Data
einem rein reaktiven Verfahren. Deswegen muss hier eine 2004, Paris, France, June 13–18, 2004, pages 659–670.
Zwischenlösung gefunden werden, die Spaltenkombinationen ACM Press, 2004.
aus Anfragen bevorzugt behandelt“, sich aber nicht darauf [10] T. Neumann and C. Galindo-Legaria. Taking the edge
”
beschränkt. off cardinality estimation errors using incremental
Außerdem muss überlegt werden, wann wir Statistikda- execution. In BTW, pages 73–92, 2013.
ten, die auf Stichproben beruhen, wieder löschen können. [11] U. Srivastava, P. J. Haas, V. Markl, M. Kutsch, and
Im reaktiven Fall fiel die Entscheidung leicht aus, weil feh- T. M. Tran. ISOMER: Consistent histogram
lender Zugriff auf die Daten auch ein fehlendes Nutzerinter- construction using query feedback. In ICDE, page 39.
esse widerspiegelt und auf diese Weise auch keine Aktuali- IEEE Computer Society, 2006.
sierung mehr stattfindet, sodass die Metadaten irgendwann [12] M. Stillger, G. Lohman, V. Markl, and M. Kandil.
unbrauchbar werden. LEO - DB2’s learning optimizer. In Proceedings of the
Basieren die Statistiken dagegen auf Stichproben, müs- 27th International Conference on Very Large Data
sen sie von Zeit zu Zeit aktualisiert werden. Passiert diese Bases(VLDB ’01), pages 19–28, Orlando, Sept. 2001.
Aktualisierung ohne zusätzliche Überprüfung auf Korrelati-
on (welche ja aufgrund geänderten Datenbestands nachlas-
sen könnte), müssen mit der Zeit immer mehr zusätzliche
Statistikdaten über Spaltenpaare gespeichert und gewartet
werden. Der für Statistikdaten zur Verfügung stehende Spei-
cherplatz im Katalog kann so an seine Grenzen treten, au-
ßerdem kostet die Wartung wiederum Kapazität des DBMS.
Hier müssen sinnvolle Entscheidungen über die Wartung und
das Aufräumen“ nicht mehr benötigter Daten getroffen wer-
”
den.
6. REFERENCES
[1] A. Aboulnaga, P. J. Haas, S. Lightstone, G. M.
Lohman, V. Markl, I. Popivanov, and V. Raman.
Automated statistics collection in DB2 UDB. In
VLDB, pages 1146–1157, 2004.
[2] S. Babu, P. Bizarro, and D. J. DeWitt. Proactive
re-optimization. In SIGMOD Conference, pages
107–118. ACM, 2005.
[3] E. Behm, V. Markl, P. Haas, and K. Murthy.
Integrating query-feedback based statistics into
informix dynamic server, Apr. 03 2008.
[4] P. Brown and P. J. Haas. BHUNT: Automatic
discovery of fuzzy algebraic constraints in relational
data. In VLDB 2003: Proceedings of 29th International
Conference on Very Large Data Bases, September
9–12, 2003, Berlin, Germany, pages 668–679, 2003.
[5] N. Bruno, S. Chaudhuri, and L. Gravano. Stholes: a
multidimensional workload-aware histogram.
SIGMOD Rec., 30(2):211–222, May 2001.
[6] P. J. Haas, F. Hueske, and V. Markl. Detecting
attribute dependencies from query feedback. In
VLDB, pages 830–841. ACM, 2007.
[7] I. F. Ilyas, V. Markl, P. Haas, P. Brown, and
A. Aboulnaga. CORDS: automatic discovery of
correlations and soft functional dependencies. In
ACM, editor, Proceedings of the 2004 ACM SIGMOD
International Conference on Management of Data
2004, Paris, France, June 13–18, 2004, pages 647–658,
pub-ACM:adr, 2004. ACM Press.
[8] H. Kimura, G. Huo, A. Rasin, S. Madden, and S. B.
Zdonik. Correlation maps: A compressed access
method for exploiting soft functional dependencies.
PVLDB, 2(1):1222–1233, 2009.