Asynchronous Database Index Maintenance

• US 20100281005A1
• Filed: 05/04/2009
• Published: 11/04/2010
• Est. Priority Date: 05/04/2009
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Carlin, Peter A., Larson, Per-Ake, Zhou, Jingren
• Granted Patent: US 8,140,495 B2
• Time in Patent Office: Days
• US Class Current: 707/696
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

Abstract

This disclosure provides techniques for asynchronously maintaining database indexes or sub-indexes. For example, a database management server may receive a data manipulation statement to modify particular data stored in a database and determine whether an index associated with executing the statement is maintained asynchronously. When the index is maintained asynchronously, maintenance of the index to reflect changes made to the particular data by executing the data manipulation statement may be delayed until an index maintenance event. The index maintenance may be based on an isolation level of a transaction including a query that triggered the index maintenance.

Claims

1. A method comprising:

receiving a query or data manipulation statement at a database management server, wherein the database management server utilizes one or more indexes to execute the statement;

determining, at the database management server, whether an index that is asynchronously maintained is to be utilized during execution of the statement;

determining, at the database management server, whether maintenance of the index is needed when the index is to be utilized during execution of the statement; and

performing maintenance of the index, at the database management server, before executing the statement.

2. The method of claim 1, wherein determining whether maintenance of the index is needed includes identifying, at the database management server, at least one row of a delta table that has not been applied to the index, wherein the delta table indicates changes to rows of the database base table.

3. The method of claim 2, wherein a control table associated with the index specifies a last row of the delta table that has been applied to the index.

4. The method of claim 3, further comprising updating the control table, at the database management server, after performing maintenance of the index to indicate a last row of the delta table that has been applied to the index during the maintenance of the index.

5. The method of claim 1, wherein the statement is a data manipulation statement, and wherein an additional index utilized to execute the statement is synchronously maintained.

6. The method of claim 1, further comprising performing maintenance of the index, at the database management server, in response to determining that the database management server has free processing resources.

7. One or more computer-readable storage media including instructions that, when executed by a processing unit of a database management server, perform acts comprising:

receiving a current statement at the database management server, wherein the current statement is included in a transaction;

identifying an index to be utilized to execute the current statement that requires maintenance, wherein the index includes at least one column of a database base table;

identifying a particular row of a delta table that has not been applied to the index, wherein the delta table indicates changes to rows of the database base table;

determining whether the particular row of the delta table is to be applied during maintenance of the index based on an isolation level of the transaction; and

updating the index according to the particular row of the delta table before executing the current statement when the particular row is to be applied during index maintenance.

8. The one or more computer-readable storage media, as recited in claim 7, wherein the particular row of the delta table that has not been applied to the index is produced by a statement included in a committed transaction.

9. The one or more computer-readable storage media, as recited in claim 7, wherein the transaction includes a plurality of statements.

10. The one or more computer-readable storage media, as recited in claim 9, wherein a respective statement of the transaction adds an additional row to the delta table before receiving the current statement.

11. The one or more computer-readable storage media, as recited in claim 10, wherein updating the index before executing the current statement includes updating the index based on the additional row added to the delta table by the respective statement.

12. The one or more computer-readable storage media, as recited in claim 7, wherein the acts comprise:

determining whether an additional index is to be utilized to execute the current statement after updating the index;

executing the current statement when an additional index is not utilized to execute the current statement; and

updating the additional index before executing the current statement when the additional index is to be utilized to execute the current statement.

13. The one or more computer-readable storage media, as recited in claim 7, wherein the acts comprise:

executing the current statement;

determining whether the transaction includes an additional statement to be executed; and

identifying an additional index to be utilized to execute the additional statement that requires maintenance after determining that the transaction includes the additional statement.

14. The one or more computer-readable storage media, as recited in claim 13, wherein the isolation level of the transaction is a serializable isolation level or a repeatable read isolation level, and wherein the acts comprise releasing a read lock on the delta table after all statements of the transaction have been executed.

15. The one or more computer-readable storage media, as recited in claim 13, wherein the isolation level of the transaction is a read committed isolation level or a read uncommitted isolation level, and wherein the acts comprise releasing a read lock on the delta in response to determining that the transaction includes the additional statement.

16. The one or more computer-readable storage media, as recited in claim 7, wherein the isolation level of the particular transaction is a snapshot isolation level, wherein the acts comprise establishing a snapshot for the transaction, and wherein a version of the particular row of the delta table that has not been applied to the index is included in the snapshot.

17. A system comprising:

a processing unit;

a database base table;

an index maintenance group including;

at least one index, wherein each index includes one or more specified columns of the database base table;

a delta table indicating changes to one or more rows of the database base table; and

an index control table indicating a last row of the delta table that has been applied to the at least one index; and

an index maintenance module executable by the processing unit to asynchronously update a particular index of the index maintenance group according to one or more rows of the delta table.

18. The system of claim 17, wherein the index maintenance group includes at least one sub-index, wherein each sub-index comprises a group of adjacent rows of a respective index

19. The system of claim 18, wherein updating the particular index of the index maintenance group includes updating a sub-index of the particular index.

20. The system of claim 18, wherein the particular index includes a plurality of columns of the database base table and the particular index includes a clustering key comprising a subset of the plurality of columns of the index, wherein division of the particular index into one or more sub-indexes is based on a prefix of the clustering key.