Updating adaptive, deferred, incremental indexes

• US 7,917,499 B2
• Filed: 06/30/2006
• Issued: 03/29/2011
• Est. Priority Date: 06/30/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Terek, F. Soner, Sundararajan, Narasimhan, Kleewein, James Charles
• Primary Examiner(s): Le; Debbie
• Assistant Examiner(s): Gortayo; Dangelino N
• Application Number:
  US11/427,974
• Publication Number:
  US 20080005097A1
• Time in Patent Office: 1,733 Days
• Field of Search: 707/1, 707/3, 707/5, 707/100, 707/104.1, 707/696, 707/705, 707/715, 707/711, 707/759
• US Class Current: 707/715
• 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 independent index associated with a database including data in response to a query to said database, said method comprising:

receiving a request to query the database, said request referencing an existing independent index, said independent index being separate from the database and associated with the database, said independent index containing a subset of data from the database, wherein the subset is an independent copy of selected data in the database and the selected data is less than all data in the database, wherein the independent index is updated after a modification is made to the database and is not updated at the time when the modification is made to the database so that the time at which the independent index is updated is independent of the time at which the database is modified;

in response to the received request, comparing the state of the independent index to the state of the database to determine if a modification has been made to the database that has not been updated to the independent index;

in response to said comparing, determining that a modification has been made to the database that has not been updated to the independent index, and in response to said determining, updating the independent index by applying a corresponding modification to the independent index prior to the execution of the received query and updating a last referenced time indicating the time that the independent index identified by the index identifier for the subset of data was last accessed by the received query to the database;

modifying the received query to utilize the updated independent index;

executing the modified query with the updated independent index; and

deleting the subset of data of the independent index identified by the index without user interaction if the last referenced time is greater than a specified period time.

2. The method of claim 1, wherein the comparing the state of the independent 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 independent index, said change number of the modification being a unique number associated with the modification, said change number associated with the independent index being the unique number associated with the last modification applied to the independent 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 independent index is updated with the modification when the change number associated with the independent 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 independent index to the change number of the modification;

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

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

5. 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.

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

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

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

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

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

11. A computer-readable storage medium having stored thereon a data structure for an index control record associated with an independent index associated with a database including data, said index control record comprising:

an index identifier uniquely identifying an independent index, said independent index being separate from the database and associated with the database, said independent index containing a subset of data from the database, wherein the subset is a independent copy of selected data in the database and the selected data is less than all data in the database, wherein the independent index is updated after a modification is made to the database and is not updated at the time when the modification is made to the database so that the time at which the independent index is updated is independent of the time at which the database is modified;

an index change number representing a change number of the last modification to the independent index identified by the index identifier, wherein the independent index identified by the index identifier is updated as a function of the change number of the database and the index change number at a time the independent index is accessed by a received query, the change number of the database representing the last modification to the database, wherein the independent index identified by the index identifier is updated with the modifications made to the database, in response to the received query and prior to execution of the received query, as indicated by the change number of the database that have not been applied to the independent index as indicated by the index change number;

a last referenced time indicating the time that the independent index identified by the index identifier was last accessed by the query to the database;

a last referenced time indicating the time that the independent 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 independent index identified by the index identifier is deleted without user interaction if said last referenced time is greater than a specified period time.

12. The computer-readable storage medium of claim 11, 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).

13. The computer-readable storage medium of claim 11 further comprising a data subset identifier identifying a subset of database data represented within the independent index.

14. The computer-readable storage medium of claim 13, 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.

15. A computer-readable storage medium having stored thereon computer-executable components comprising:

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

(i) an index identifier uniquely identifying an independent index, said independent index being separate from a database and associated with said database, said independent index containing a subset of data from the database, wherein the subset is an independent copy of selected data in the database and the selected data is less than all data in the database, wherein the independent index is updated after a modification is made to the database and is not updated at the time when the modification is made to the database so that the time at which the independent index is updated is independent of the time at which the database is modified;

(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 independent index identified by the index identifier, said modification being applied to the database and to the independent index in order of the sequential change number; and

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

(b) an index update component for;

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

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

(iii) in response to the received query request and prior to execution of the received query request, applying a modification to the independent index as a function of the index change number of the index control record and a change number of the database, said change number of the database indicating the last modification applied to the database;

(c) an index deletion component for;

(i) selecting zero or more index control records as a function of the last referenced time, when the last referenced time is greater than a specified period time;

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

16. The computer-readable storage medium of claim 15 further comprising a data subset identifier identifying a subset of database data represented within the independent index;

and

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

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