Dr. Götz Graefe

(HP-Fellow, Palo Alto)

"Adaptive Merging"

In a relational data warehouse with many tables, the number of possible and promising indexes exceeds human comprehension and requires automatic index tuning. Unpredictable ad-hoc queries exacerbate the problem. Consideration of partial indexes and materialized views further expands the search space. While monitoring and reactive index tuning have been proposed, we focus on adapting the physical database layout for and by actual queries.

"Database cracking" is one such technique. Only if and when a column is used in query predicates, an index for the column is created; and only if and when a key range is queried, the index is optimized for this key range. The effect is akin to a sort that is adaptive and incremental. This sort is, however, very inefficient, in particular when applied to databases on block-access devices. In contrast, traditional index creation sorts everything with an efficient merge sort optimized for block-access devices, but it is neither adaptive nor incremental.

We propose adaptive merging, an adaptive, incremental, and efficient technique for index creation. Index optimization efforts focus on key ranges used in actual queries. The resulting index adapts more quickly to new data and to new query patterns than database cracking. Sort efficiency is comparable to that of traditional index creation. Nonetheless, the new technique enables better query performance than database cracking, both in memory and on block-access storage.

Zeit:	Montag, 09.11.2009, 17.15 Uhr
Ort:	Gebäude 48, Raum 210