Query Optimization for Semistructured Data
Jason McHugh, Jennifer Widom · 1997
With the emerging prevalence of semistructured data -- data that may be irregular or incomplete -- it is important to develop efficient query processing techniques for such data. This paper describes the query processor of Lore, a DBMS for semistructured data, and focuses particularly on the cost-based query optimization techniques we have developed and implemented for a semistructured environment. While all of the usual problems associated with cost-based query optimization apply to semistructured data as well, a number of additional problems arise, suchasvastly different query execution strategies for different semistructured databases, more complicated notions of database statistics, and novel uses of indexing. Weintroduce very flexible logical query plans that can be transformed into a wide varietyofphysical plans, define appropriate database statistics and a cost model, and describe plan enumeration including heuristics for reducing the search space. Our optimizer is fully implemented for most of the Lore query language, and preliminary performance results are reported.