1. A method for determining a cost of evaluating a query, the method comprising: analyzing one or more XML documents to generate statistics about a plurality of elements in the one or more XML documents; storing, in persistent storage, XML data that represents the one or more XML documents; wherein the statistics are separate from the XML data; wherein the statistics include skip length information that indicates, for each element in a subset of the plurality of elements, an amount of data in the persistent storage that said each element requires for storage, wherein said each element represents a subtree in one or more of the one or more XML documents and the amount of data indicates a size of the subtree; after storing the XML data in the persistent storage and generating the statistics, receiving a particular query that is to be evaluated against the XML data that is stored in the persistent storage; and in response to receiving the particular query and before evaluating the particular query against the XML data, analyzing at least a portion of the skip length information to estimate a I/O cost of reading at least a portion of the XML data; wherein the method is performed by one or more computing devices.