# US 2019/0377809 A1 · Resolving versions in an append-only large-scale data store in distributed data management systems

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2019/0377809 A1
- Document ID: US20190377809A1
- Status: Published application
- Kind: A1
- Application number: 16/005,485
- Filed: 2018-06-11
- Published: 2019-12-12
- Earliest claimed: 2018-06-11
- Assignees: International Business Machines Corporation
- Applicants: International Business Machines Corporation
- Inventors: Yuanyuan Tian; Vijayshankar Raman; Ronald J. Barber; Richard S. Sidle; Pinar Tozun; Rene Mueller; Ronen Grosman; Adam J. Storm; Christian M. Garcia-Arellano; Guy M. Lohman
- Web page: https://patentgrep.com/patent/US20190377809A1

## CPC

- G06F 16/219: {Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477)}
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/2237: {Vectors, bitmaps or matrices}
- G06F 16/2329: {using versioning}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/254: {Extract, transform and load [ETL] procedures, e.g. ETL data flows in data warehouses}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

One embodiment provides for a method including processing transactional operations on a key used to determine whether existing data is found for that key. A first time index is updated using unique keys and a start time field of a first appearance of each key from the transactional operations. A deferred update of prior versions of the key is performed for non-recent data upon determining that recent data in the transactional operations is found for the key.

## Claims

### Claim 1

A method comprising:
processing transactional operations on a key used to determine whether existing data is found for that key;
updating a first start time index using unique keys and a start time field of a first appearance of each key from the transactional operations; and
performing a deferred update of prior versions of the key for non-recent data upon determining that the recent data in the transactional operations is found for the key.

### Claim 2 (depends on 1)

The method of claim 1, wherein the transactional operations comprise update, delete and insert operations.

### Claim 3 (depends on 2)

The method of claim 2, wherein performing the deferred update comprises:
adding the first time index using the unique keys and the start time field of the first appearance of each key from the transactional operations; and
looking up the first time index for an unknown value of an end time field of rows in non-recent data.

### Claim 4 (depends on 3)

The method of claim 3, wherein the end time field of a row in the non-recent data is not assigned upon determining the key is not in the first time index.

### Claim 5 (depends on 3)

The method of claim 3, wherein the end time field of a row in the non-recent data is not assigned upon determining the key is not in the first time index, and bitmap indexes are used to mark deleted rows.

### Claim 6 (depends on 3)

The method of claim 3, wherein the first time index maps a key to a start time field of a row for a first appearance of the key.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
retiring rows from affected current files;
outputting a history file per partition key; and
generating a new bit map for each affected file, wherein the new bit map includes marking for the retired rows.

### Claim 8 (depends on 3)

The method of claim 3, further comprising:
initializing, the first known start time index;
creating a current file and a history file for each partition key group for a partition key;
grouping all rows in a partition key group by primary key;
for each primary key group:
sorting rows by value in a begin time field of a row;
writing of a first row into the first known start time index;
for all rows except for a last row:
writing values to a history file, wherein end time is assigned as rowi.EndTime=rowi+1.BeginTime, where i is an integer indicating position of a row in a sorted order of a primary key group; and
writing the last row to the current file.

### Claim 9

A computer program product for processing updates for key values and for patch up of prior versions of updates and not yet patched updates, the computer program product comprising a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a processor to cause the processor to:
process, by the processor, transactional operations on a key used to determine whether existing data is found for that key;
update, by the processor, a first time index using unique keys and a start time of a first appearance of each key from the transactional operations; and
perform, by the processor, a deferred update of prior versions of the key for non-recent data upon determining that recent data in the transactional operations is found for the key.

### Claim 10 (depends on 9)

The computer program product of claim 9, wherein the transactional operations comprise update, delete and insert operations.

### Claim 11 (depends on 10)

The computer program product of claim 10, wherein performing the deferred update further comprises program instructions executable by the processor to cause the processor to:
add, by the processor, the first time index using the unique keys and the start time field of the first appearance of each key from the transactional operations; and
perform look ups, by the processor, for the first time index for an unknown value of an end time field of rows in non-recent data.

### Claim 12 (depends on 11)

The computer program product of claim 11, wherein:
the end time field of a row in the non-recent data is not assigned upon determining the key is not in the first time index; and
the end time field of a row in the non-recent data is not assigned upon determining the key is not in the first time index, and bitmap indexes are used to mark deleted rows.

### Claim 13 (depends on 11)

The computer program product of claim 11, wherein the first time index maps a key to a start time field of a row for a first appearance of the key.

### Claim 14 (depends on 13)

The computer program product of claim 13, further comprising program instructions executable by the processor to cause the processor to:
retire, by the processor, rows from affected current files;
output, by the processor, a history file per partition key; and
generate, by the processor, a new bit map for each affected file, wherein the new bit map includes marking for the retired rows.

### Claim 15 (depends on 13)

The computer program product of claim 13, further comprising program instructions executable by the processor to cause the processor to:
initialize, by the processor, the first known start time index;
create, by the processor, a current file and a history file for each partition key group for a partition key;
group, by the processor, all rows in a partition key group by primary key;
for each primary key group:
sort, by the processor, rows by value in a begin time field of a row;
write, by the processor, of a first row into the first known start time index;
for all rows except for a last row:
write, by the processor, values to a history file, wherein end time is assigned as rowi.EndTime=rowi+1.BeginTime, where i is an integer indicating position of a row in a sorted order of a primary key group; and
write, by the processor, the last row to the current file.

### Claim 16

An apparatus comprising:
a memory configured to store instructions; and
a processor configured to execute the instructions to:
process transactional operations on a key used to determine whether existing data is found for that key;
update a first time field upon determining recent data is found; and
perform a deferred update of potential prior versions of the key for non-recent data upon determining that the recent data is not found for the key.

### Claim 17 (depends on 16)

The apparatus of claim 16, wherein:
the transactional operations comprise update, delete and insert operations; and
the deferred update further comprises:
adding the first time index using the unique keys and the start time field of the first appearance of each key from the transactional operations; and
looking up the first time index for an unknown value of an end time field of rows in non-recent data.

### Claim 18 (depends on 17)

The apparatus of claim 17, wherein:
the end time field of a row in the non-recent data is not assigned upon determining the key is not in the first time index;
the end time field of a row in the non-recent data is not assigned upon determining the key is not in the first time index, and bitmap indexes are used to mark deleted rows; and
the first time index maps a key to a start time field of a row for a first appearance of the key.

### Claim 19 (depends on 17)

The apparatus of claim 17, wherein the processor is further configured to execute the instructions to:
retire rows from affected current files;
output a history file per partition key; and
generate a new bit map for each affected file, wherein the new bit map includes marking for the retired rows.

### Claim 20 (depends on 17)

The apparatus of claim 17, wherein the processor is further configured to execute the instructions to:
initialize the first known start time index;
create a current file and a history file for each partition key group for a partition key;
group all rows in a partition key group by primary key;
for each primary key group:
sort rows by value in a begin time field of a row;
write of a first row into the first known start time index;
for all rows except for a last row:
write values to a history file, wherein end time is assigned as rowi.EndTime=rowi+1.BeginTime, where i is an integer indicating position of a row in a sorted order of a primary key group; and
write the last row to the current file.