Kostenbasierte, datenbankexterne Optimierung für anfragegenerierende Informationssysteme
Final Report Abstract
Innerhalb des CEOPS-Projekts wurden Konzepte für eine kostenbasierte, datenbankexterne Optimierung von generierten Anfragesequenzen entwickelt. Um Kosten für Anfragesequenzen zu ermitteln wurde eine Kostenkomponente entworfen, die die Möglichkeit des darunter liegenden Datenbanksystems, Kosten für einzelne SQLAnweisungen zu ermitteln, nutzt, um Kosten für eine gesamte Sequenz von SQLAnweisungen zu berechnen. Um verwertbare Kostenwerte vom darunter liegenden Datenbanksystem zu erhalten, war es notwendig, für die Tabellen, die temporär von der Sequenz zur Speicherung von Zwischenergebnisse erstellt werden, Statistiken zur Verfügung zu stellen. Hierzu wurde von der Histogramm-Propagati on Gebrauch gemacht. Die Propagation von Histogrammen durch Anfragen ist eine aus dem Approximate Query Answering bekannte Technik. Innerhalb des Projekts wurden die bestehenden Ansätze modifiziert und erweitert. Insbesondere ist hier die Erweiterung um Heuristiken für die Gruppierung und Aggregatberechnung sowie die Verwendung der Intervallarithmetik zur Propagation von Histogrammen durch arithmetische Terme zu nennen. Um auf die im Katalog des darunter liegenden Datenbanksystems gespeicherten Histogramme zugreifen zu können und die Kostenschätzwerte für eine SQL-Anweisung von dessen Optimierer erfragen zu können wurde unter dem Namen "Statistics API" eine entsprechende Schnittstelle definiert. Es handelt sich hierbei um eine DBVS-unabhängige Schnittstelle, die einen lesenden wie auch schreibenden Zugriff auf Statistiken in einem Datenbanksystem, lesenden Zugriff auf Metadaten in einem Datenbanksystern sowie lesenden Zugriff auf die vom Optimierer eines Datenbanksystems ermittelten Kosten- und Kardinalitätsschätzwerte für beliebige SQL-Anweisungen ermöglicht. Diese Schnittstelle wurde für IBM DB2, Oracle und Microsoft SQL Server implementiert. Um Aussagen über die Qualität bzw. Verlässlichkeit der ermittelten Kostenwerte treffen zu können, wurden theoretische Arbeiten geleistet, um eine Verlässlichkeitsmetrik zu konzipieren, die eine Beurteilung der Qualität der Kostenschätzwerte ermöglicht. Die mit Hilfe des Prototyps und den bereits aus Vorarbeiten gegebenen Anfragesequenzen durchgeführte Evaluation ergab, dass die mit der entwickelten Kostenkomponente ermittelten Kostenschätzwerte ein guter Indikator für die Laufzeit einer Sequenz sind. Des Weiteren konnte gezeigt werden, dass die Histogramm-Propagation notwendig ist, um qualitativ gute Kostenschätzwerte zu erhalten und auch bei der Ausführung der Anfragesequenz sinnvoll eingesetzt werden kann, um den Optimierer des darunter liegenden Datenbanksystems bei der Wahl eines möglichst guten Plans zu unterstützen.
Publications
- Kraft, Tobias: A Cost-Estimation Component for Statement Sequences. In Proc. of the International Conference on Very Large Data Bases (VLDB), 2007.
- Kraft, Tobias; Mitschang, Bernhard: Statistics API: DBMS-independent Access and Management of DBMS Statistics in Heterogeneous Environments. In Proc. of the International Conference on Enterprise Information Systems (ICEIS), 2007.
- Kraft, Tobias; Schwarz, Holger; Mitschang, Bernhard: A Statistics Propagation Approach to Enable Cost-Based Optimization of Statement Sequences, hi Proc. of the East-European Conference on Advances in Databases and Information Systems (ADBIS), 2007.
- Vrhovnik, Marko; Schwarz, Holger; Ewen, Stephan; Suhre, Oliver: PGMOF: A Framework for the Optimization of Data Processing in Business Processes. In Proc. of the International Conference on Data Engineering (ICDE), 2008.
- Vrhovnik, Marko; Schwarz, Holger; Mitschang, Bernhard; Radeschuetz, Sylvia: An Overview of SQL Support in Workflow Products. In Proc. of the International Conference on Data Engineering (ICDE), 2008.
- Vrhovnik, Marko; Schwarz, Holger; Suhre, Oliver; Mitschang, Bernhard; Markl, Volker; Maier, Albert; Kraft, Tobias: An Approach to Optimize Data Processing in Business Processes. In Proc. of the International Conference on Very Large Data Bases (VLDB), 2007.
