1. A method to estimate a cost for computing a query on XML documents stored in a database, the method comprising the steps of: maintaining a plurality of statistics about nodes in said XML documents; based upon said plurality of statistics, estimating a cost for computing at least one path expression in said query on said XML documents, said cost comprising an estimated CPU cost and an estimated I/O cost; wherein the cost of computing the at least one path expression is determined based on a mathematical function of the estimated CPU cost and the estimated I/O cost; wherein computing said at least one path expression is performed using streaming evaluation; wherein estimating a cost for computing a path expression of the at least one path expression includes: estimating an input-size of said XML documents, said input-size being based on units of bytes; based on a portion of said plurality of statistics about said nodes, estimating an output-size associated with said path expression; wherein the steps are performed by one or more computing devices.