Redundant version information in history table that enables efficient snapshot querying

• US 20060161530A1
• Filed: 01/19/2005
• Published: 07/20/2006
• Est. Priority Date: 01/19/2005
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Isaac Kam-Chak, Clare, Donald Lee, Biswal, Dilip Kumar, Chu, Cecilia O., Mau, Louis S.W.
• Granted Patent: US 7,509,307 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/219 Managing data history or versioning querying versioned data G06F16/2474; querying temporal data G06F16/2477
• CPC Class Codes: G06F 16/2322 using timestamps
• CPC Class Codes: G06F 16/2329 using versioning
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

A method and system for efficient snapshot querying include: providing a first version value for each data in a history table, where the first version value indicates a beginning of a period in which the data is valid; providing at least a second version value for each data in the history table, where the second version value indicates an end of the period in which the data is valid; receiving a request for a version of a database; and retrieving the data with the first version value less than or equal to the requested version and the second version value greater than or equal to the requested version. By maintaining a history table with redundant version information, the method and system are able to provide efficient snapshot querying while also avoiding the overhead burden of conventional approaches. No aggregates, joins, or sub-queries are required to retrieve a snapshot.

Claims

1. A method for efficient snapshot querying, comprising:

providing a first version value for each data in a history table, wherein the first version value indicates a beginning of a period in which the data is valid;

providing at least a second version value for each data in the history table, wherein the second version value indicates an end of the period in which the data is valid;

receiving a request for a version of a database; and

retrieving the data with the first version value less than or equal to the requested version and the second version value greater than or equal to the requested version.

2. The method of claim 1, further comprising:

determining that a change in a row in the database has occurred; and

adding a row to the history table corresponding to the changed row, wherein the adding comprises;

setting the first version value for the added row to a current version, and

setting the second version value for the added row to a significantly large number.

3. The method of claim 2, wherein the adding further comprises:

determining that the change is a row insert; and

setting a delete Boolean value for the added row to ‘

false’

.

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

determining that the change is a row delete;

setting a delete Boolean value for the added row to ‘

true’

; and

modifying an old row in the history table for a key of the changed row by changing its second version value to a previous version.

5. The method of claim 2, wherein the adding further comprises:

determining that the change is a row update;

setting a delete Boolean value for the added row to ‘

false; and

modifying an old row in the history table for a key of the changed row by changing its second version value to a previous version.

6. The method of claim 1, wherein the retrieving comprises:

performing a first scan of rows in the history table for rows with the first version value less than or equal to the requested version;

performing a second scan of rows in the history table for rows with the second version value greater than or equal to the requested version; and

determining an intersection of the first and second scans.

7. The method of claim 6, wherein the first and second scans are indexed scans.

8. The method of claim 1, wherein the retrieved data each has a delete Boolean value of ‘

false’

.

9. A system, comprising:

a database comprising a data table and a history table, wherein for each change to the data table, a row is added to the history table; and

a mechanism for maintaining the history table, wherein the maintaining comprises;

providing a first version value for the added row in the history table, wherein the first version value indicates a beginning of a period in which a data value of the added row is valid, and

providing at least a second version value for the added row in the history table, wherein the second version value indicates an end of the period in which the data value of the added row is valid,

wherein when a request for a version of the database is received, the data values with the first version value less than or equal to the requested version and the second version value greater than or equal to the requested version are retrieved from the history table.

10. The system of claim 9, wherein the maintaining further comprises:

determining that a change in a row in the data table has occurred; and

adding the row to the history table corresponding to the changed row, wherein the adding comprises;

setting the first version value for the added row to a current version, and

setting the second version value for the added row to a significantly large number.

11. The system of claim 10, wherein the maintaining further comprises:

determining that the change is a row insert; and

setting a delete Boolean value for the added row to ‘

false’

.

12. The system of claim 10, wherein the maintaining further comprises:

determining that the change is a row delete;

setting a delete Boolean value for the added row to ‘

true’

; and

modifying an old row in the history table for a key of the changed row in the data table by changing its second version value to a previous version.

13. The system of claim 10, wherein the maintaining further comprises:

determining that the change is a row update;

setting a delete Boolean value for the added row to ‘

false; and

modifying an old row in the history table for a key of the changed row in the data table by changing its second version value to a previous version.

14. The system of claim 9, wherein the retrieving comprises:

performing a first scan of rows in the history table for rows with the first version value less than or equal to the requested version;

performing a second scan of rows in the history table for rows with the second version value greater than or equal to the requested version; and

determining an intersection of the first and second scans.

15. The system of claim 14, wherein the first and second scans are indexed scans.

16. The system of claim 9, wherein the retrieved data each has a delete Boolean value of ‘

false’

.

17. A computer readable medium with program instructions for efficient snapshot querying, comprising:

providing a first version value for each data in a history table, wherein the first version value indicates a beginning of a period in which the data is valid;

providing at least a second version value for each data in the history table, wherein the second version value indicates an end of the period in which the data is valid;

receiving a request for a version of a database; and

retrieving the data with the first version value less than or equal to the requested version and the second version value greater than or equal to the requested version.

18. The medium of claim 17, further comprising:

determining that a change in a row in the database has occurred; and

adding a row to the history table corresponding to the changed row, wherein the adding comprises;

setting the first version value for the added row to a current version, and

setting the second version value for the added row to a significantly large number.

19. The medium of claim 18, wherein the adding further comprises:

determining that the change is a row insert; and

setting a delete Boolean value for the added row to ‘

false’

.

20. The medium of claim 18, wherein the adding further comprises:

determining that the change is a row delete;

setting a delete Boolean value for the added row to ‘

true’

; and

modifying an old row in the history table for a key of the changed row by changing its second version value to a previous version.

21. The medium of claim 18, wherein the adding further comprises:

determining that the change is a row update;

setting a delete Boolean value for the added row to ‘

false; and

modifying an old row in the history table for a key of the changed row by changing its second version value to a previous version.

22. The medium of claim 17, wherein the retrieving comprises:

performing a first scan of rows in the history table for rows with the first version value less than or equal to the requested version;

performing a second scan of rows in the history table for rows with the second version value greater than or equal to the requested version; and

determining an intersection of the first and second scans.

23. The medium of claim 22, wherein the first and second scans are indexed scans.

24. The medium of claim 17, wherein the retrieved data each has a delete Boolean value of ‘

false’

.