Progressive indexing for improved ad-hoc query performance

• US 8,965,899 B1
• Filed: 12/30/2011
• Issued: 02/24/2015
• Est. Priority Date: 12/30/2011
• Status: Active Grant

• Current Assignee: EMC Corporation (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Van Rotterdam, Jeroen
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/341,423
• Time in Patent Office: 1,152 Days
• Field of Search: 707/708, 707/737, 707/741, 707/743, 707/744, 707/736
• US Class Current: 707/741
• CPC Class Codes: G06F 16/2453 Query optimisation

Abstract

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.

Claims

1. A method of enhancing query performance of ad-hoc queries executed on data stored in a database, comprising

executing an ad-hoc query on said data in said database;

traversing a first subset of said data in said database during said executing said ad-hoc query;

indexing categories of content of said data in said first subset during said traversing to create a first partial index of said categories of data content of said first subset; and

repeating said foregoing steps while traversing a second subset of data in said database to create a second partial index of the categories of data content of said second subset of data;

wherein said first and second partial indexes progressively index said database to reduce the amount of data traversed and the execution time of subsequent ad-hoc queries executed on said database.

2. The method of claim 1 further comprising progressively adding to said partial indexes by subsequently executing one or more additional ad-hoc queries to increase the data content indexed in said partial indexes of the categories of data content.

3. The method of claim 1, wherein said database comprises a hierarchical data structure, and said method further comprises applying an index definition to a top level container of data in said hierarchical data structure, said index definition being used to create said first partial index.

4. The method of claim 3 further comprising creating additional partial indexes of data content in sub-containers at different levels lower than said top level container of said hierarchical data structure.

5. The method of claim 4, wherein said ad-hoc queries use partial indexes to identify sub-containers within said hierarchical data structure to scan for data content relevant to said ad-hoc queries.

6. The method of claim 4 further comprising associating metadata with each sub-container to indicate whether indexing of data content in said sub-container is complete.

7. The method of claim 1, wherein said database comprises a partitioned database that stores unstructured data.

8. The method of claim 1, wherein said databases is an unpartitioned database that stores data that comprises structured content.

9. The method of claim 8, wherein said structured content data comprises one or more of XML data and JSON data.

10. A method of enhancing query performance of ad-hoc queries executed on data stored in a database, comprising:

executing an ad-hoc query on said data in said database;

indexing categories of data content of subsets of said data stored in said database while traversing said data content during said executing said ad-hoc query to create one or more partial indexes of said categories of data content of one or more of said subsets of the data, and

repeating said executing and indexing to progressively build on said partial indexes of said categories of data content while executing one or more ad-hoc queries on said data.

11. The method of claim 10, wherein said progressively building comprises using an index definition to define the content in a subset of the data to be indexed by said one or more ad-hoc queries to create said partial indexes.

12. The method of claim 11, wherein said index definition is defined by an ad-hoc query.

13. The method of claim 10, wherein data in said database is organized in hierarchically structured containers, and said partially indexing comprises applying an index definition that defines the data content to be indexed in said hierarchically structured containers.

14. The method of claim 13, wherein each hierarchically structured container has an associated administration module, and the method further comprises indicating by said administration module whether indexing of the data content of said container is complete.

15. The method of claim 10, wherein said partially indexing said categories of data content comprises executing an ad-hoc query, and creating said one or more partial indexes at different container levels of said hierarchically-structured containers while executing said ad-hoc query.

16. Non-transitory computable readable media storing executable instructions for controlling the operation of a computer to:

execute an ad-hoc query on data in a database;

traverse a first subset of said data in said database during executing said ad-hoc query;

index categories of the content of said data in said first subset during traversing the first subset to create a first partial index of said categories of the content of said data of said first subset;

repeat said foregoing steps while traversing a second subset of data in said database to create a second partial index of categories of the data content of said second subset of data; and

wherein said first and second partial indexes progressively index said database to reduce the amount of data traversed and the execution time of subsequent ad-hoc queries executed on said database.

17. The non-transitory computer readable media of claim 16 further comprising instructions for progressively adding to said partial indexes by executing one or more subsequent ad-hoc queries to increase the data content in said partial indexes.

18. The non-transitory computer readable media of claim 16, further comprising instructions to progressively add to said partial indexes and instructions for applying index definitions to said subsets of data, and said instructions to execute said ad-hoc queries comprise instructions that use said index definitions to identify the subsets of data traversed by said ad-hoc queries.

19. The non-transitory computer readable media of claim 16, wherein said database comprises a hierarchical data structure, and further comprising instructions for creating partial indexes for data containers at different levels of said data structure.

20. The non-transitory computer readable media of claim 19 further comprising instructions for providing information for each said data container to indicate whether indexing of such data container is complete.