Abstract? Several systems have recently been proposed for the evaluation of XPath expressions. However, none of these systems have demonstrated both scalability with large document sizes and robust support for the XPath language. Many of the scalability problems can be attributed to inadequate use of indexing during query evaluation. While poor support for the XPath language is often a consequence of an architecture overly optimized for certain queries. Finally, the proposed systems fail to adequately address costing with respect to query optimizations.

We present VAMANA as a solution for a cost driven and scalable evaluation of ad-hoc XPath expressions. VAMANA's index-oriented query plans allow queries to be evaluated while reading only a fraction of the data. VAMANA's pipelined query framework minimizes the cost of intermediate query processing while providing cost-based transformations to further improve performance. Our experimental study con?rms that VAMANA's cost-driven optimization approach for optimizing queries achieves a substantial performance improvement with negligible optimization overhead compared to non-optimized queries. Our study comparing VAMANA against several leading XML query engines demonstrates that VAMANA's query engine is signi?cantly faster than these existing solutions in all considered cases.