Structural join order selection for XML query optimization
Authors:
- Y. WuYWY. Wu
- J.M. PatelJPJ.M. Patel
- H.V. JagadishHJH.V. Jagadish
- 13 May 2004
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 443-454
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.Keywords
This publication has 10 references indexed in Scilit:
- Structural join order selection for XML query optimization2004
- TIMBER: A native XML databaseThe VLDB Journal, 2002
- Multi-level operator combination in XML query processing2002
- Holistic twig joins2002
- Minimization of tree pattern queries2001
- On supporting containment queries in relational database management systems2001
- An overview of query optimization in relational systems1998
- Heuristic and randomized optimization for the join ordering problemThe VLDB Journal, 1997
- Rapid bushy join-order optimization with Cartesian productsACM SIGMOD Record, 1996
- Access path selection in a relational database management system1979