1. A method comprising performing a machine-executed operation involving instructions, wherein said instructions are instructions which, when executed by one or more processors, cause the one or more processors to perform certain steps including: intercepting, by a database system, a query for first information from the collection of XML documents, wherein the collection of XML documents is stored in one or more data structures in the database system and indexed by a first table and a second table; wherein the first table comprises a plurality of columns, each column of the plurality of columns being associated with one or more criteria and containing values of nodes which nodes (i) are in the collection of XML documents and (ii) satisfy one or more criteria; wherein the second table comprises a set of entries, each entry in the set of entries being associated with a given node and including location data for locating XML content associated with the given node and path data that corresponds to a path, through the structure of the XML document that contains the given node, to the given node; and wherein the query comprises a plurality of predicates, which plurality of predicates can be evaluated using the values of nodes contained in the plurality of columns in the first table; and generating a first query plan using both the first table and the second table, wherein the first query plan, when executed by the database system, causes the database system to perform: identifying one or more first entries from the first table, each of the one or more first entries from the first table satisfying the plurality of predicates; identifying second information from the one or more first entries identified from the first table; extracting the first information from one or more second entries in the second table using the second information; wherein the machine-executed operation is at least one of (a) sending said instructions over transmission media, (b) receiving said instructions over transmission media, (c) storing said instructions onto a machine-readable storage medium, and (d) executing the instructions.