Redundant version information in history table that enables efficient snapshot querying

• US 7,509,307 B2
• Filed: 01/19/2005
• Issued: 03/24/2009
• Est. Priority Date: 01/19/2005
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Cheng, Isaac Kam-Chak, Clare, Donald Lee, Biswal, Dilip Kumar, Mau, Louis S. W., Chu, Cecilia O.
• Primary Examiner(s): Vy; Hung T
• Assistant Examiner(s): HO, BINH VAN
• Application Number:
  US11/039,528
• Publication Number:
  US 20060161530A1
• Time in Patent Office: 1,525 Days
• Field of Search: 707/3
• 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 querying for a database snapshot with more than one version without requiring a query having aggregates, joins, and sub-queries, comprising:

providing a first version value for each data in a history table having redundant version information, 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;

retrieving the data by;

performing a series of indexed scans including;

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

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, wherein the retrieved data each has a Boolean value;

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’

;

determining that the change is a row delete; and

setting a delete Boolean value for the added row to ‘

true’

;

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;

determining that the change is a row update; and

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 and, providing a response to the request received.

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

4. The method of claim 3, wherein the first and second scans are indexed scans.

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

false’

.