Abstract
A method is provided for selecting a query execution plan, including: receiving an XML document including a plurality of root nodes and a plurality of leaf nodes; determining root-to-leaf paths based on the plurality of root nodes and the plurality of leaf nodes; generating a prime number for each unique root-to-leaf path; calculating a number of instances in which each prime number appears; generating an XML synopsis based on the prime numbers and the number of instances; determining a comparison between a query tree pattern and the XML synopsis; determining a type of the query tree pattern; calculating for each query tree pattern plan, a selectivity estimate based on the comparison and the type of the query tree pattern; determining an optimal query execution plan based on the selectivity estimate; and selecting the optimal query execution plan for performing a query of the XML document based on the determination.