Incorporating Other Physical Structures - Automated Physical Database Design and Tuning - page 163

account. The inclusion of horizontal partitioning raises new challenges
during merging. One reason is that partitioning and indexing columns
can be interchangeably used. For instance, an index on columns

)
that is used to evaluate a predicate like (a=10 AND b=20) can be re-
placed by an index on

( ,

a b

partitioned by column a . When merging two
partitioned indexes, we need to consider rearranging index keys and
partitioning columns in addition to the more standard index merging. If
indexes on the same vertical partition are horizontally partitioned on the
same columns, we merge the respective partitioning methods to arrive
at a more generic partitioning method, similar to the case of merging
range predicates in a view. More details on merging can be found in the
references at the end of this chapter.
Enumeration. After we define the search space by candidate enumera-
tion and merging of physical structures, we can use any of the strate-
gies discussed in Section 6.1 to conduct the enumeration step. In fact,
such strategies are suciently agnostic to the considered physical design
structures that they can be adapted with minor changes. For instance,
greedy(m,B) starts by evaluating all configurations with at most m struc-
tures (e.g., horizontally partitioned indexes) and then continues consi-
dering the remaining structures greedily. Certain problem formulations,
however, require slightly different approaches. For instance, a common
requirement when partitioning a database is that all indexes of a given
table share the same partitioning function. This requirement simplifies
database management, since database operations such as backup and re-
store become much easier to plan and execute. In this situation, unless
we eagerly generate candidates with all combinations of partitioning for
every candidate index, we might end up searching in an overconstrained
space of physical structures. At the same time, generating all combi-
nations of indexes and partitioning schemes can result in much larger
search spaces. To overcome these diculties, there are adaptations to
the basic greedy(m,B) strategy that lazily generate useful horizontal par-
titions on demand and can eciently traverse the full space of aligned
configurations.

( b )

9.2 Data Cube Selection
Users of data warehouses typically need to manipulate and analyze data from
multiple perspectives, and some environments handle this requirement by pre-
senting data as a multidimensional data cube . Users can then explore two-,
three-, or even higher-dimensional subcubes to discover interesting informa-
tion, a task also known as business intelligence . In this section we introduce