UPDATING ADAPTIVE, DEFERRED, INCREMENTAL INDEXES

• US 20080005097A1
• 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,917,499 B2
• Time in Patent Office: Days
• US Class Current: 707/5
• CPC Class Codes: G06F 16/2228 Indexing structures

Abstract

An index update component updates an index of a database in response to a query to the database referencing the index. An index control record tracks the last time the index was referenced and state of the index compared to the state of the database. An index deletion component deletes indexes in the database that have not been referenced for a period of time.

Claims

1. A method for updating an index of a database in response to a query to said database comprising:

receiving a request to query the database referencing the index of the database;

comparing the state of the index to the state of the database to determine if a modification has been made to the database that has not been applied to the index;

in the event said comparing determines that a modification has been made to the database that has not been applied to the index, updating the index by applying a corresponding modification to the index; and

executing the query with the index.

2. The method of claim 1, wherein the comparing the state of the index to the state of the database comprises comparing a change number associated with the modification to the database and a change number associated with the index, said change number of the modification being a unique number associated with the modification, said change number associated with the index being the unique number associated with the last modification applied to the index.

3. The method of claim 2, wherein the change number associated with the modification is in increasing order relative to the change number of previous modifications and the index is updated with the modification when the change number associated with the index is less than the change number associated with the modification.

4. The method of claim 2, wherein the updating further comprises:

comparing the change number of the index to the change number of the modification;

applying the modification to the index if the change number of the modification is greater than the change number of the index, wherein the change number associated with the modification is a strictly increasing value;

modifying the change number of the index to the change number of the modification applied to the index.

5. The method of claim 1 further comprising:

modifying the query to utilize the updated index wherein the modified query is executed with the updated index and the updated index is independent of the database.

6. The method of claim 1, wherein the modification is associated with one or more of the following:

a transaction log, a reliable eventing queue, a recovery log and a change history.

7. The method of claim 1 further comprises updating the index with the modification during periods of low database activity, said updating occurring regardless of whether a query referencing the index was received.

8. The method of claim 1, wherein database is associated with an electronic mail application.

9. The method of claim 1, wherein the database is updated when the modification is received and wherein the index is updated when the query is received.

10. The method of claim 1, wherein the query is for a subset of the data in the database and the index is updated with the modification if the modification is to said subset of data.

11. The method of claim 10, 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.

12. A computer-readable medium having stored thereon a data structure for an index control record associated with an index of a database comprising:

an index identifier uniquely identifying the index of the database; and

an index change number representing a change number of the last modification to the index of the database identified by the index identifier, wherein the index is updated with the modification as a function of the change number of the modification.

13. The computer-readable medium of claim 12, wherein the change number associated with the modification is one or more of the following:

Messaging Application Programming Interface (MAPI) change number, log sequence number (LSN), and log relative byte offset (LRBA).

14. The computer-readable medium of claim 12 further comprising a data subset identifier identifying a subset of database data represented within the index.

15. The computer-readable medium of claim 14, wherein the subset of data is identified by one or more of the following:

a mailbox identifier, a folder identifier of the mailbox identifier, a table name and an index key range of the table.

16. The computer-readable medium of claim 14 further comprising a last referenced time indicating the time that the index identified by the index identifier for the subset of data indicated by the data subset identifier was last accessed by the query to the database;

and

wherein the subset of data of the index identified by the index identifier is deleted if said last referenced time is greater than a specified period time.

17. The computer-readable medium of claim 12 further comprising a last referenced time indicating the time that the index identified by the index identifier was last accessed by the query to the database;

and

wherein the index identified by the index identifier is deleted if said last referenced time is greater than a specified period time.

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

(a) a data structure for an index control record comprising;

(i) an index identifier uniquely identifying an index of a database;

(ii) an index change number representing a strictly increasing sequential change number of the last modification to the database for the subset of data identified by the data subset identifier that is reflected in the index identified by the index identifier, said modification being applied to the database and to the index in order of the sequential change number; and

(iii) a last referenced time indicating the time that the index identified by the index identifier was last referenced by a query to the database;

(b) an index update component for;

(i) receiving the query the database referencing the index, said referenced index being associated with the index identifier;

(ii) searching for the index control record for the index identifier associated with the requested index; and

(iii) applying a modification to the index as a function of the index change number of the index control record;

(c) an index deletion component for;

(i) selecting zero or more index control records as a function of the last referenced time;

(ii) for each selected index control record, deleting the index identified by the index identifier of the selected record.

19. The computer-readable medium of claim 18 further comprising a data subset identifier identifying a subset of database data represented within the index;

and

wherein a subset of data of the index identified by the data subset identifier is deleted.

20. The computer-readable medium of claim 18, wherein the index deletion component executes during periods of low database activity.