Review - Physical Data Independence, Constraints, and Optimization with Universal Plans.

Laura M. Haas: Review - Physical Data Independence, Constraints, and Optimization with Universal Plans. ACM SIGMOD Digital Review 1: (1999)

Review

This paper[1] proposes a novel optimization method that is well-grounded in theory, and has important practical implications. By using dictionaries (finite functions) in combination with constraints, the authors first describe a broad range of access structures, including primary and secondary indexes, join indexes, materialized views, path indexes and other access support relations, gmaps, and so on. In this way, they are able to represent physical structures relevant to a given query in the same framework as logical entities. They then show how to optimize a query in three steps: first the query is rewritten using chase with the constraints on logical and physical schemas to arrive at a "universal plan". This is basically a query representation that explicitly includes any relevant data structures (not a plan in the traditional optimizer sense). Next, backchase is used to create alternative viable representations of the query by removing different combinations of redundant accesses. For example, if the constraints say that the data needed for this query from a particular relation can be obtained from either of two indexes, the universal plan would include both indexes and the relation itself; backchase would produce alternative "plans" using only one of the paths. Finally, these alternatives are optimized conventionally, and the cheapest resulting plan is returned. This is an elegant piece of work. A single mechanism handles a broad range of physical structures and constraints, allowing a unified optimization strategy. Further, the problem it attacks is an important one, as Selinger-style bottom-up optimizers[2] are awkward when dealing with access structures that replace multiple individual table accesses (e.g., materialized views), and this approach will fit neatly with that framework (a la Starburst[3]). It will be interesting to see how the method performs in terms of optimization time.

References

[1]: Alin Deutsch, Lucian Popa, Val Tannen: Physical Data Independence, Constraints, and Optimization with Universal Plans. VLDB 1999: 459-470
[2]: Patricia G. Selinger, Morton M. Astrahan, Donald D. Chamberlin, Raymond A. Lorie, Thomas G. Price: Access Path Selection in a Relational Database Management System. SIGMOD Conference 1979: 23-34
[3]: Laura M. Haas, Johann Christoph Freytag, Guy M. Lohman, Hamid Pirahesh: Extensible Query Processing in Starburst. SIGMOD Conference 1989: 377-388