1. A method comprising: receiving a query that specifies a particular path expression; normalizing the query to generate a normalized query, wherein normalizing the query comprises generating, based on the particular path expression, a plurality of normalized path expressions; generating, based on the particular path expression, from a subset of the plurality of normalized path expressions, one or more temporary path expressions; determining whether each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by a path-subsetted XML index that is associated with one or more subsetted path expressions that indicate a set of one or more nodes that are indexed by said path-subsetted XML index; and in response to determining that each of the one or more temporary path expressions is subsumed by a path of a node that is indexed by said path-subsetted XML index, using the path-subsetted XML index to process the plurality of normalized path expressions; wherein the method is performed by one or more computers.