
Enumerating the Search Space 109
0
2000
4000
6000
8000
0 1000 2000 3000
Required Space (MB)
Estimated Execution Time
FIGURE 6.5 Top-down search output for a TPC-H database.
until a stopping condition is satisfied (typically a time bound). Each iteration
during enumeration consists of the following steps. First, we evaluate the
current configuration and store it in the global cache of configurations (step 2
in the figure). Then, we consider transformations that generate new candidate
configurations from the current one (step 3 in the figure). We transform a
Pruned? Retrieve New
Pick Best
Generate
Current
Configuration
Candidate
Configuration
Initial
Configuration
Best
Configuration ...