US Patent 8965899 Progressive indexing for improved ad-hoc query performance

The invention progressively indexes a database by building partial indexes over subsets of the data are built as the data is scanned, i.e., traversed, during execution of ad-hoc queries. Indexes are built as ad-hoc queries “touch” the data. This permits ad-hoc queries to utilize partial indexes built by other ad-hoc queries. If an ad-hoc query scans more data during execution than was previously indexed, the ad-hoc query will utilize the existing partial indexes to the extent they are relevant while adding to them or building additional partial indexes as the query executes.