Provided are techniques for processing a query. The query is received, and the query is formed by one or more paths, where each path includes one or more steps. A hierarchical document is received that includes one or more document nodes. While processing the query and traversing the hierarchical document to find document nodes described by at least one of the one or more steps of the query, a match graph is constructed that includes one or more match nodes. Each of the match nodes identifies a step instance and is associated with step instances that are ancestors and descendants of the identified step instance. Also, each of the match nodes is associated with a level. In addition, the match graph includes zero or more edges between the match nodes indicating relationships between the match nodes. The match nodes in the match graph are traversed from lower levels to higher levels to construct results for the query.