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: storing the collection of XML documents in one or more base database structures managed by a database system for storing the collection of XML documents; creating a table, separate from the one or more base database structures, that indexes the collection of XML documents, wherein the table includes a plurality of columns, wherein each column is associated with one or more criteria and contains values of nodes that are in the collection of XML documents and that satisfy the one or more criteria; and maintaining a domain index on a first column of the plurality of columns; 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.