The role of the workload, including queries and updates, in physical design was widely recognized. Therefore, at a high level, the problem of physical database design was - for a given workload, find a configuration, . a set of indexes that minimize the cost. However, early approaches did not always agree on what constitutes a workload, or what should be measured as cost for a given query and configuration. Papers on physical design of databases started appearing as early as 1974. Early work such as by Stonebraker [63] assumed a parametric model of the workload and work.