Book excerpt: Due to the increasing complexity in application workloads and query engines, database administrators are turning to automated tuning tools that systematically explore the space of physical design alternatives. A critical element of such tuning is physical database design since the choice of physical structures has a significant impact on the perfor