In an environment where it is desire to perform information extraction over a large quantity of textual data, methods, tools and structures are provided for building a relational text index from the textual data and performing searches using the relational text index.