Index Structures for Data Warehouses

Abstract

This thesis investigates which index structures support query processing in typical data warehouse environments most efficiently. Data warehouse applications differ significantly from traditional transaction-oriented operational applications. Therefore, the techniques applied in transaction- oriented systems cannot be used in the context of data warehouses and new techniques must be developed. The thesis shows that the time complexity for the computation of optimal tree-based index structures prohibits its use in real world applications. Therefore, we improve heuristic techniques (e. g., R*-tree) to process range queries on aggregated data more efficiently. Experiments show the benefits of this approach for different kinds of typical data warehouse queries. Performance models estimate the behavior of standard index structures and the behavior of the extended index structures. We introduce a new model that considers the distribution of data. We show experimentally that the new model is more precise than other models known from literature. Two techniques compare two tree-based index structures with two bitmap indexing techniques. The performance of these index structures depends on a set of different parameters. Our results show which index structure performs most efficiently depending on the parameters.

In dieser Arbeit wird untersucht, welche Indexstrukturen Anfragen in typischen Data Warehouse Systemen effizient unterstützen. Indexstrukturen, seit mehr als zwanzig Jahren Forschungsgegenstand im Datenbankbereich, wurden in der Vergangenheit für transaktionsorientierte Systeme optimiert. Ein Kennzeichen dieser Systeme ist die effiziente Unterstützung von Einfüge-, Änderungs- und Löschoperationen auf einzelnen Datensätzen. Typische Operationen in Data Warehouse Systemen sind dagegen komplexe Anfragen auf großen relativ statischen Datenmengen. Aufgrund dieser veränderten Anforderungen müssen Datenbankmanagementsysteme, die für Data Warehouses eingesetzt werden, andere Techniken nutzen, um komplexe Anfragen effizient zu unterstützen. Zunächst wird ein Ansatz untersucht, der mit Hilfe eines gemischt ganzzahligen Optimierungsproblems eine optimale Indexstruktur berechnet. Da die Kosten für die Berechnung dieser optimalen Indexstruktur mit der Anzahl der zu indizierenden Datensätze exponentiell steigen, wird in anschließenden Teilen der Arbeit heuristischen Ansätzen nachgegangen, die mit der Größe der zu indizierenden Datensätze skalieren. Ein Ansatz erweitert auf Bäumen basierende Indexstrukturen um aggregierte Daten in den inneren Knoten. Experimentell wird gezeigt, daß mit Hilfe der materialisierten Zwischenergebnisse in den inneren Knoten Bereichsanfragen auf aggregierten Daten wesentlich schneller bearbeitet werden. Um das Leistungsverhalten von Indexstrukturen mit und ohne materialisierte Zwischenergebnisse zu untersuchen, wird das PISA Modell (Performance of Index Structures with and without Aggregated Data) entwickelt. In diesem Modell wird die Verteilung der Daten und die Verteilung der Anfragen berücksichtigt. Das PISA Modell wird an gleich-, schief- und normalverteilte Datensätze angepaßt. Experimentell wird gezeigt, daß das PISA Modell mit einer höheren Präzision als die bisher aus der Literatur bekannten Modelle arbeitet. Die Leistung von Indexstrukturen hängt von unterschiedlichen Parametern ab. In dieser Arbeit werden zwei Techniken vorgestellt, die abhängig von einer bestimmten Menge von Parametern Indexstrukturen vergleichen. Mit Hilfe von Klassifikationsbäumen wird z. B. gezeigt, daß die Blockgröße die relative Leistung weniger beeinflußt als andere Parameter. Ein weiteres Ergebnis ist, daß Bitmap-Indexstrukturen von den Verbesserungen neuerer Sekundärspeicher stärker profitieren als heute übliche auf Bäumen basierende Indexstrukturen. Bitmap-Indexierungstechniken bieten noch ein großes Potential für weitere Leistungssteigerungen im Datenbankbereich.