| Evaluation of the UB-Tree with consideration of sorting |
Schlüsselwörter:
UB-Baum, Indexierung, mehrdimensionale Zugriffsmethoden, Sortierung, CUBE-Operator, Verbund-Operator, Gruppierung, Massenladen, Anfrageverarbeitung, Anfrageoptimierung, Datenstrukturen, B-Baum, Relationales Datenverwaltungssystem, Data-Warehouse, OLAP, Benchmark, TPC-H-Benchmark
UB-Tree, indexing, multidimensional access methods, sorting, CUBE operator, join operator, grouping, bulk loading, query processing, data structure, B-Trees, relational database system, data warehousing, OLAP, Benchmark, TPC-H benchmark
SchlagwortnormdateiAbstract in English
Complex business applications like SAP R/3, statistical databases, data warehousing and data mining have created a strong demand for efficiently processing complex queries on huge relational databases. By using the multidimensional index UB-tree as access structure to execute range queries a performance enhancement of factor 10 could be achieved. Additional improvements were carried out by integration in the database system Transbase of TransAction. This thesis analyses the usability of the Z-partitioning of the UB-Tree for query processing and bulk loading. The author of this thesis develops several algorithms that process efficiently a Z-order to a one dimensional order or reverse. The result is an efficient bulk load algorithm (TempTris-Algorithm) as well as a join and group algorithm (Tetris-Algorithm, UBG-Algorithm). These algorithms reduce the I/O-cost for the sort phase at least of 50% according to the external sorting. For each algorithm a cost model is presented. The author presents performance measurements that proved our predicted speed up factor. The performance measurements are conducted on artificial data as well as on the TPC-H benchmark. To show the potential impact on real database scenarios, measurements were performed on a real data warehouse from the Gesellschaft für Konsumforschung (GfK). This thesis concludes with a new processing technique of the CUBE-operator and the impact on the relational algebra. The author develops the results of this thesis as a member of the research group MISTRAL at FORWISS.
Abstract in Deutsch
Der Einsatz der mehrdimensionalen Zugriffsstruktur UB-Baum in komplexen Geschäfts-Anwendungen (z.B. SAP R/3), statistischen Datenbanken, Data-Warehouse und Data-Mining haben gezeigt, dass Leistungssteigerungen bis zum Faktor 10 für die Verarbeitung von Bereichsanfragen möglich sind. Weitere Verbesserungen wurden durch die Integration in den Datenbankkern Transbase von TransAction erzielt. Diese Arbeit untersucht die Möglichkeit der Ausnutzung der Z-Partitionierung des UB-Baums für die Verwendung in der Anfrageverarbeitung und beim Massenladen. Hierzu entwickelte der Autor mehrere neue Algorithmen, die entweder aus der Z-Ordnung effizient eine Zielordnung oder aus einer 1-dimensionalen Quellordnung die Z-Ordnung erzeugen. Dies führt zu einem effizienten Massenlade-Algorithmus (TempTris-Alogrithmus) sowie zu einem Verbunds- und Gruppierungs-Operator (Tetris-Algorithmus, UBG-Algorithmus). Die Algorithmen reduzieren die E/A-Kosten in der Sortierphase um mindestens 50% gegenüber dem externen Sortieren. Für die einzelnen Algorithmen wurden Kostenmodelle entwickelt, die durch Leistungsmessungen auf künstlichen Datenverteilungen und durch Teile des TPC-H Benchmark belegt werden. Um die Anwendungstauglichkeit im realen Datenbankumfeld zu zeigen, wurden Messungen auf dem Data-Warehouse der Gesellschaft für Konsumforschung (GfK) gemacht. Die Arbeit schließt mit einer neuen Verarbeitungstechnik des CUBE-Operators und dem Einfluss der neuen Techniken auf die relationale Algebra. Der Autor erstellte die Ergebnisse dieser Arbeit als Mitglied der Mistralgruppe bei FORWISS.
| Betreuer | Bayer, R.; Univ.-Prof. Ph. D. |
| Gutachter | Bayer, R.; Univ.-Prof. Ph. D. |
| Gutachter | Kemper,A.; Univ.-Prof. Alfons Ph. D. |