 |
Goetz Graefe. Ph.D.: 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.
Falls dieser Text Formeln enthält, die nicht dargestellt werden können,
finden Sie hier die dvi- bzw. die
pdf-Version.
|
HV) |
© Universität Stuttgart |
Impressum