New Challenges in Physical Database Design - Automated Physical Database Design and Tuning - page 220

IF clause is true half of the time on average, and thus the SQL query
over table R would execute twice as often as the SQL query over table S .

•

We can rely on actual execution profiles to capture the actual number
of executions of each SQL query. This alternative is the most accurate
one but requires executing workloads, which might not be feasible in all
scenarios.

These alternatives introduce an explicit tradeoff between the overhead of the
estimation procedures and the quality of the resulting recommendations.

12.2 Other Aspects of Physical Database Design
The different techniques discussed in this topic are mainly concerned with
recommending a set of physical design structures. In a real system, there are
additional issues to address in fully tuning the physical design of a database.
We next summarize some of these challenges.

12.2.1 Fragmentation
Complex decision support queries usually require scanning large portions of
tables (via their corresponding indexes). When data are updated, indexes can
get fragmented due to B + -tree page splits or simply as a consequence of re-
ordering data within pages. There are two kinds of index fragmentation, both
of which can have a significant impact on input/output (I/O) performance of
a query. Internal fragmentation occurs when a leaf page of an index is only
partially filled, thus increasing the number of pages that need to be scanned.
External fragmentation occurs when the logical order of leaf pages in the B + -
tree differs from the physical order in which the pages occur in the data file,
therefore increasing the number of random seeks required to traverse the index
in order. Thus, compared with an index that is not fragmented, both internal
and external fragmentation can result in more I/Os for scan-based queries.
As anecdotal evidence, during an experimental evaluation of a tuning tool,
we noticed that the actual execution cost of a plan under the base configura-
tion was twice as fast as the corresponding plan under a recommended con-
figuration. This was odd because the recommended configuration contained a
strict superset of the indexes in the base configuration, and the query did not
do any updates. Even more puzzling, a closer inspection of both plans revealed
that they were indeed identical (the plan under the recommended configura-
tion used only indexes that were present in the base configuration as well).
After a long debugging session, we realized that the root cause of the problem
was index fragmentation. In fact, the query required a sequential scan over a