# US 2015/0178329 A1 · Multiple rid spaces in a delta-store-based database to support long running transactions

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

- Number: US 2015/0178329 A1
- Document ID: US20150178329A1
- Status: Published application
- Kind: A1
- Application number: 14/136,724
- Filed: 2013-12-20
- Published: 2015-06-25
- Earliest claimed: 2013-12-20
- Assignees: Sybase, Inc.
- Inventors: Mihnea Andrei; Anil Kumar Goel; Colin Florendo; Rolando Blanco; David Edward DeHaan
- Web page: https://patentgrep.com/patent/US20150178329A1

## CPC

- G06F 16/2343: {Locking methods, e.g. distributed locking or locking implementation details}
- G06F 11/1448: {Management of the data involved in backup or backup restore}
- G06F 16/219: {Managing data history or versioning (querying versioned data G06F16/2474; querying temporal data G06F16/2477)}
- G06F 16/2358: {Change logging, detection, and notification (replication G06F16/27)}
- G06F 16/2365: {Ensuring data consistency and integrity}
- G06F 16/22: Indexing; Data structures therefor; Storage structures
- G06F 16/221: {Column-oriented storage; Management thereof}
- G06F 16/2282: {Tablespace storage structures; Management thereof}
- G06F 2201/80: Database-specific techniques
- G06F 2201/825: the problem or solution involving locking
- G06F 2201/84: Using snapshots, i.e. a logical point-in-time copy of the data
- G06F 2201/87: Monitoring of transactions
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A delta store giving row-level versioning semantics to a non-row-level versioning underlying store is described. An example method includes establishing a column-based in-memory database including a main store and a delta store, where the main store allows only non-concurrent transactions on a same table and the delta store has a plurality of row-visibility bitmaps implementing a row-level versioning mechanism that allows concurrent transactions on the same table. A local RID space is established for a table fragment, that for each table in the database, the data of the table is stored in one or more main table fragment in the main store and in one or more delta table fragments in the delta store. Each table fragment has a local RID space, and the local RID space is a collection of one-based contiguous integer local RIDs (Row IDs) describing local positions of the rows of the table fragment.

## Claims

### Claim 1

A method for a database system, comprising:
establishing a column-based in-memory database including a main store and a delta store, wherein the main store implements table-level versioning mechanism allowing only non-concurrent transactions on a same table and the delta store has a plurality of row-visibility bitmaps implementing a row-level versioning mechanism that allows concurrent transactions on the same table; and
establishing a local RID space for a table fragment, wherein for each table in the database, the data of the table is stored in one or more main table fragment in the main store and in one or more delta table fragments in the delta store, wherein each table fragment has a local RID space, and wherein the local RID space is a collection of one-based contiguous integer local RIDs (Row IDs) describing local positions of the rows of the table fragment.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
establishing a global RID space for a table version, wherein the table has a plurality of table versions represented by the bitmaps, the table version providing transaction-consistent snapshots of the table visible to transactions according to transactional snapshot isolation rules in a plurality of global RID spaces, and
wherein each global RID space contains an ordered sequence of table fragments, one main table fragment followed by the one or more delta table fragments, each with its local RID space, and
wherein a last delta fragment in a global RID space is a current delta fragment, and
wherein a global RID space is a one-based collection of integer global RIDs (Row IDs) describing global positions of the rows of the table version in its underlying ordered sequence of the main table fragments and the one or more delta table fragments, and wherein a most recently created global RID space is a current global RID space.

### Claim 3 (depends on 2)

The method of claim 2, further comprising:
processing a transaction that generates data changes in a table of the column-based in-memory database, through insert, update or delete statements of the transaction,
wherein upon a start of the transaction, the transaction is attached to the current global RID space of each table that the transaction accesses and processes, until completion of processing, within the global RID space attached by the transaction, and
wherein all new rows and new row versions created by the insert and the update statements are physically inserted in the current delta table fragment and marked as valid using global RID bitmaps, and all old rows and old row versions destroyed by the delete or update statements are logically marked as invalid using the global RID bitmaps, and
wherein the global RID bitmaps of each table modified by the transaction correspond to the global RID space associated with the table and the transaction.

### Claim 4 (depends on 2)

The method of claim 2, further comprising:
periodically merging for each table the delta stare to the main store, wherein the delta store accumulates the data changes and each merge generates a new global RID space.

### Claim 5 (depends on 4)

The method of claim 4, wherein the merging occurs concurrently with the processing the transaction, without blocking the transaction, and
wherein the delta table fragment and the main table fragment which were current before the merge become merged table fragments, and
wherein the merge creates a new delta table fragment and a new main table fragment, which become new current table fragments after completion of the merge.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
generating a new delta table fragment at beginning of the merge, wherein the new delta table fragment becomes the current delta table fragment, and
wherein, from a point after the beginning of the merge, all new rows and row versions created by the insert and update statements are inserted into the new delta table fragment, and
wherein all RID spaces which exist at the beginning of the merge, including the current RID space, are extended by appending the new delta table fragment at an end of the ordered sequence of table fragments, and
wherein all transactions which are open at the beginning of the merge continue processing of the table within extended RID space where the transactions were originally attached, and
wherein all new transactions which begin after the beginning of the merge and before the completion of the merge are attached for the table within an extended current RID space.

### Claim 7 (depends on 6)

The method of claim 6, further comprising:
generating the new main table fragment at the completion of the merge,
wherein rows from the merged delta fragment, which are inserted and committed and not deleted or whose deletion is not yet committed, are transferred in the new main table fragment, and
wherein rows from the merged main fragment, which are not yet deleted or whose deletion is not yet committed, are transferred to the new main table fragment, and
wherein rows from the merged delta fragment, which are inserted and not yet committed are transferred to the new current delta fragment.

### Claim 8 (depends on 7)

The method of claim 7, further comprising:
converting the new main table fragment to the current main table fragment at the completion of the merge;
generating a new RID space, which contains two table fragments in an order of the current main table fragment and the current delta table fragment, wherein the new RID space becomes the current RID space; and
generating a mapping, from a previous global RID space to the current global RID space for all rows moved from the table fragments of the previous RID space to table fragments of the current RID space,
wherein all transactions which are open at the completion of the merge continue processing of the table within RID spaces attached by the transactions, and
wherein all new transactions which begin after the completion of the merge and before a beginning of a next merge are attached for the table to the current RID space.

### Claim 9 (depends on 3)

The method of claim 3, further comprising:
creating a new version for each table modified by the transaction, upon successful completion of the transaction, wherein each of the new version is created in the current global RID space of the table, and
translating global RID bitmaps representing inserted and deleted rows and row versions, which, during the processing of the transaction, correspond to a previous RID space attached to the table within the transaction, to the current RID space if the current RID space is different from the previous RID space attached to the table within the transaction.

### Claim 10 (depends on 2)

The method of claim 2, wherein each global RID space is maintained as long as either the global RID space is current or an active transaction is attached to the global RID space, and wherein each table fragment is maintained as long as an existing global RID space contains the table fragment.

### Claim 11

A system, comprising:
a column store establisher, configured to establish a column-based in-memory database including a main store and a delta store, wherein the main store implements table-level versioning mechanism allowing only non-concurrent transactions on a same table and the delta store has a plurality of row-visibility bitmaps implementing a row-level versioning mechanism that allows concurrent transactions on the same table; and
a local RID space establisher, configured to establish a local RID space for a table fragment, wherein for each table in the database, the data of the table is stored in one or more main table fragment in the main store and in one or more delta table fragments in the delta store, wherein each table fragment has a local RID space, and wherein the local RID space is a collection of one-based contiguous integer local Rips (Row IDs) describing local positions of the rows of the table fragment.

### Claim 12 (depends on 1)

The system of claim 1, further comprising:
a global RID space establisher, configured to establish a global RID space for a table version, wherein the table has a plurality of table versions represented by the bitmaps, the table version providing transaction-consistent snapshots of the table visible to transactions according to transactional snapshot isolation rules in a plurality of global RID spaces, and
wherein each global RID space contains an ordered sequence of table fragments, one main table fragment followed by the one or more delta table fragments, each with its local RID space, and
wherein a last delta fragment in a global RID space is a current delta fragment, and
wherein a global RID space is a one-based collection of integer global RIDs (Row IDs) describing global positions of the rows of the table version in its underlying ordered sequence of the main table fragments and the one or more delta table fragments, and
wherein a most recently created global RID space is a current global RID space.

### Claim 13 (depends on 12)

The system of claim 12, further comprising:
a transaction processor, configured to process a transaction that generates data changes in a table of the column-based in-memory database, through insert, update or delete statements of the transaction,
wherein upon the start of the transaction, the transaction is attached to the current global RID space of each table that the transaction accesses and processes, until completion of processing, within the global RID space attached by the transaction, and
wherein all new rows and new row versions created by the insert and the update statements are physically inserted in the current delta table fragment and marked as valid using global RID bitmaps, and all old rows and old row versions destroyed by the delete or update statements are logically marked as invalid using the global RID bitmaps, and
wherein the global RID bitmaps of each table modified by the transaction correspond to the global RID space associated with the table and the transaction.

### Claim 14 (depends on 12)

The system of claim 12, further comprising:
a store merger, configured to periodically merge for each table the delta store to the main store, wherein, the delta store accumulates the data changes and each merge generates a new global RID space.

### Claim 15 (depends on 14)

The system of claim 14, wherein the store merger is further configured to conduct the merge concurrently with the processing the transaction, without blocking the transaction, and
wherein the delta table fragment and the main table fragment which were current before the merge become merged table fragments, and
wherein the merge creates a new delta table fragment and a new main table fragment, which become new current table fragments after completion of the merge.

### Claim 16 (depends on 15)

The system of claim 15, further comprising:
a new delta table fragment generator, configured to generate a new delta table fragment at beginning of the merge, wherein the new delta table fragment becomes the current delta table fragment, and
wherein, from a point after the beginning of the merge, all new rows and row versions created by the insert and update statements are inserted into the new delta table fragment, and
wherein all RID spaces which exist at the beginning of the merge, including the current RID space, are extended by appending the new delta table fragment at an end of the ordered sequence of table fragments, and
wherein all transactions which are open at the beginning of the merge continue processing of the table within extended RID space where the transactions were originally attached, and
wherein all new transactions which begin after the beginning of the merge and before the completion of the merge are attached for the table within an extended current RID space.

### Claim 17 (depends on 16)

The system of claim 16, further comprising:
a new main table fragment generator, configured to generate the new main table fragment at the completion of the merge,
wherein rows from the merged delta fragment, which are inserted and committed and not deleted or whose deletion is not yet committed, are transferred in the new main table fragment, and
wherein rows from the merged main fragment, which are not yet deleted or whose deletion is not yet committed, are transferred to the new main table fragment, and
wherein rows from the merged delta fragment, which are inserted and not yet committed are transferred to the new current delta fragment.

### Claim 18 (depends on 17)

The system of claim 17, further comprising:
a main table fragment converter, configured to convert the new main table fragment to the current main table fragment at the completion of the merge;
a new RID space generator, configured to generate a new RID space, which contains two table fragments in an order of the current main table fragment and the current delta table fragment, wherein the new RID space becomes the current RID space; and
a RID space mapper, configured to generate a mapping, from a previous global RID space to the current global RID space for all rows moved from the table fragments of the previous MD space to table fragments of the current RID space,
wherein all transactions which are open at the completion of the merge continue processing of the table within RID spaces attached by the transactions, and
wherein all new transactions which begin after the completion of the merge and before a beginning of a next merge are attached for the table to the current RID space.

### Claim 19 (depends on 13)

The system of claim 13, further comprising:
a table version creator, configured to create a new version for each table modified by the transaction, upon successful completion of the transaction, wherein each of the new version is created in the current global RID space of the table, and
a RID space translator, configured to translate global RID bitmaps representing inserted and deleted rows and row versions, which, during the processing of the transaction, correspond to a previous RID space attached to the table within the transaction, to the current RID space if the current RID space is different from the previous RID space attached to the table within the transaction.

### Claim 20 (depends on 12)

The system of claim 12, wherein each global RID space is maintained as long as either the global RID space is current or an active transaction is attached to the global RID space, and wherein each table fragment is maintained as long as an existing global RID space contains the table fragment.

### Claim 21

A computer program product comprising a computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to perform operations comprising:
establishing a column-based in-memory database including a main store and a delta store, wherein the main store implements table-level versioning mechanism allowing only non-concurrent transactions on a same table and the delta store has a plurality of row-visibility bitmaps implementing a row-level versioning mechanism that allows concurrent transactions on the same table; and
establishing a local RID space for a table fragment, wherein for each table in the database, the data of the table is stored in one or more main table fragment in the main store and in one or more delta table fragments in the delta store, wherein each table fragment has a local RID space, and wherein the local RID space is a collection of one-based contiguous integer local RIDs (Row IDs) describing local positions of the rows of the table fragment.

### Claim 22 (depends on 21)

The computer program product of claim 21, wherein the processor performs operations further comprising:
establishing a global RID space for a table version, wherein the table has a plurality of table versions represented by the bitmaps, the table version providing transaction-consistent snapshots of the table visible to transactions according to transactional snapshot isolation rules in a plurality of global RID spaces, and
wherein each global RID space contains an ordered sequence of table fragments, one main table fragment followed by the one or more delta table fragments, each with its local RID space, and
wherein a last delta fragment in a global RID space is a current delta fragment, and
wherein a global RID space is a collection of one-based global RIDs (Row IDs) describing global positions of the rows of the table version in its underlying ordered sequence of the main table fragments and the one or more delta table fragments, and
wherein a most recently created global RID space is a current global RID space.
