CREATING ADAPTIVE, DEFERRED, INCREMENTAL INDEXES

• US 20080005092A1
• Filed: 06/30/2006
• Published: 01/03/2008
• Est. Priority Date: 06/30/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Terek, F. Soner, Sundararajan, Narasimhan, Kleewein, James Charles
• Granted Patent: US 7,734,618 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99948 Application of database or data structure, e.g. distributed, multimedia, or image
• CPC Class Codes: Y10S 707/99957 Garbage collection

Abstract

A request logging component formulates an index that could have been utilized by a query to a database, if the index had existed. The request logging component stores the formulated query as an unsatisfied request. The index creation component creates the index of the database from the unsatisfied request.

Claims

1. A method for creating an index for a database comprising:

(a) receiving a query to the database having indexes;

(b) formulating a query index for the database wherein the query index is a function of the received query;

(c) searching the indexes of the database for an index that matches the formulated query index;

(d) in the event that an index of the database that matches the formulated query index is not found; and

(i) saving the formulated query index;

(ii) executing the query without the formulated query index; and

(iii) creating the saved formulated query index;

(d) in the event that an index of the database that matches the formulated query index is found, executing the query with the formulated query index.

2. The method of claim 1, wherein the query is for a subset of the data in the database and the saved formulated query indicates said subset of data.

3. The method of claim 2, wherein the index is created for the indicated subset of the data in the database.

4. The method of claim 2, wherein the subset of data is identified by one or more of the following:

a mailbox identifier and a folder identifier of the mailbox identifier;

a table name and an index key range of the table;

a property of the data;

a comparison value and comparator; and

an expression containing properties of the data, comparison values and comparators.

5. The method of claim 1, wherein the index is created during a period of low database activity.

6. The method of claim 1, wherein the database is associated with an electronic message application.

7. A computer-readable medium having stored thereon a data structure for an unsatisfied requests associated with a database comprising:

a request time indicating the time the unsatisfied request to the database was received;

an index definition for defining an index of the database, said index definition as a function of the unsatisfied request.

8. The computer-readable medium of claim 7, wherein the unsatisfied request is created in response to the query to the database, said query executing more efficiently with an index than without the index, the value of the index definition being determined by the query.

9. The computer-readable medium of claim 7, wherein an index for the database is created from the index definition of the unsatisfied request.

10. The computer-readable medium of claim 7, wherein the index is created during a period of low database activity.

11. The computer-readable medium of claim 7, wherein the index is created when a plurality of unsatisfied requests are generated by a plurality of queries to the database, each unsatisfied request containing the same index definition.

12. The computer-readable medium of claim 7 further comprising a data subset field indicating the subset of data that should be indexed.

13. The method of claim 12, wherein the subset of data is identified by one or more of the following:

a mailbox identifier and a folder identifier of the mailbox identifier;

a table name and an index key range of the table;

a property of the data;

a comparison value and comparator; and

an expression containing properties of the data, comparison values and comparators.

14. The computer-readable medium of claim 12, wherein an index for the subset of the database is created from the unsatisfied request record.

15. The computer-readable medium of claim 14, wherein the index is created if a plurality of unsatisfied request records exist, each record with the same index definition.

16. A computer-readable medium having computer-executable components comprising:

(a) a data structure for an unsatisfied request comprising;

(i) a request time indicating the time the unsatisfied request to a database was received;

(ii) an index definition for defining the index within the database, said index definition based on the unsatisfied request.

(b) an request logging component for; and

(i) receiving a request to query the database;

(ii) formulating a query index for the database as a function of the received query;

(iii) searching the database for an index that matches the formulated query index; and

(iv) in the event that the formulated query does not match an index of the database, creating an unsatisfied request, wherein the request time is equal to the time the query request was received and the index definition is equal to the formulated query index;

(c) an index creation component for creating an index of the database as a function of the index definition for each created unsatisfied request.

17. The computer-readable medium of claim 16, wherein the unsatisfied request further comprises a data subset field indicating the subset of data that should be indexed.

18. The computer-readable medium of claim 17, wherein the index is populated with the subset of data specified in the data subset field.

19. The computer-readable medium of claim 16, wherein the index is created if a plurality of unsatisfied requests exist, each unsatisfied request with the same index definition.

20. The computer-readable medium of claim 16, wherein the index creation component executes during a period of low database activity.