Structural join order selection for XML query optimization

Authors:
  • YWY. Wu
    Y. Wu
  • JPJ.M. Patel
    J.M. Patel
  • HJH.V. Jagadish
    H.V. Jagadish

Abstract
Structural join operations are central to evaluating queries against XML data, and are typically responsible for consuming a lion's share of the query processing time. Thus, structural join order selection is at the heart of query optimization in an XML database, just as (value-based) join order selection is central to relational query optimization. In this paper, we introduce five algorithms for structural join order optimization for XML tree pattern matching and present an extensive experimental evaluation. Our experi- ments demonstrate that many relational rules of thumb are no longer appropriate: for instance, using dynamic pro- gramming style optimization is not efficient; limiting con- sideration to left-deep plans usually misses the best solu- tion. Our experiments also show that a Dynamic Program- ming optimization with Pruning (DPP) algorithm can find the optimal solution, with low cost relative to the tradi- tional Dynamic Programming (DP) algorithm; and an opti- mization technique that only considers Fully Pipelined (FP) plans can very quickly choose a plan that in most cases is close to optimal. Our recommendation is that DPP should be used in XML query optimizers where query execution time is expected to be significant, and that FP should be used where it is important to find a good (but not necessar- ily the best) plan quickly.