DELTA STORE GIVING ROW-LEVEL VERSIONING SEMANTICS TO A NON-ROW-LEVEL VERSIONING UNDERLYING STORE

• US 20150046413A1
• Filed: 08/06/2013
• Published: 02/12/2015
• Est. Priority Date: 08/06/2013
• Status: Active Grant

• Current Assignee: Sybase Incorporated (SAP SE)
• Original Assignee: SAP AG (SAP SE)
• Inventors: Florendo, Colin, Goel, Anil, ANDREI, Mihnea
• Granted Patent: US 9,659,050 B2
• Time in Patent Office: Days
• US Class Current: 707/695
• CPC Class Codes: G06F 11/1448 Management of the data involved in backup or backup restore
• 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/22 Indexing; Data structures therefor; Storage structures
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2343 Locking methods, e.g. distributed locking or locking implementation details
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/825 the problem or solution involving locking
• CPC Class Codes: G06F 2201/84 Using snapshots, i.e. a logical point-in-time copy of the data
• CPC Class Codes: G06F 2201/87 Monitoring of transactions

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 does not allow 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 transaction associated with the column-based in-memory database is received. For each table read by the transaction, a version of the table in the delta store that represents a transaction-consistent snapshot of the database visible to the transaction is determined. Each table is represented in the main store and the delta store; and each version of the table is represented by one or more bitmaps. Upon execution of a DML as part of the transaction, for each table written by the transaction, the data changes generated by the transaction is recorded in the one or more bitmaps that represent a private version of the table. Upon commit of the transaction, for each table written by the transaction, a new public version of the table is generated based on the private version of the table, and the public version represents a new transaction-consistent snapshot of the database visible to subsequent transactions.

Claims

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 does not allow 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;

receiving a transaction associated with the column-based in-memory database;

for each table read by the transaction, determining a version of the table in the delta store that represents a transaction-consistent snapshot of the database visible to the transaction, wherein each table is represented in the main store and the delta store, and each version of the table is represented by one or more bitmaps;

upon execution of a Data Manipulation Language (DML) as part of the transaction, for each table written by the transaction, recording data changes generated by the transaction in the one or more bitmaps that represent a private version of the table; and

upon commit of the transaction, for each table written by the transaction, generating a new public version of the table based on the private version of the table, wherein the public version represents a new transaction-consistent snapshot of the database visible to subsequent transactions.

2. The method of claim 1, further comprising:

accumulating, for each table, the data changes of a plurality of transactions in the delta store; and

merging the delta store with the main store to apply the data changes generated by the plurality of the transactions accumulated in the delta store to the main store.

3. The method of claim 1, wherein the one or more bitmaps representing the each version of the table include an insertion bitmap.

4. The method of claim 1, wherein the one or more bitmaps representing the each version of the table includes a deletion bitmap.

5. The method of claim 4, wherein the deletion map includes a delta store section corresponding to a delta store portion of the table and a main store section corresponding to a main store portion of the table.

6. The method of claim 5, wherein the main store section of the deletion bitmap provides the row-level versioning semantics of the main store.

7. The method of claim 1, wherein the delta store provides row-level versioning semantics to the main store, so that the database behaves as having row-level versioning mechanism to a database client.

8. The method of claim 1, wherein the recording further comprises:

inserting both new data in the delta store and corresponding entries in the insertion bitmap of the delta store, when the transaction is an inserting operation.

9. The method of claim 1, wherein the recording further comprises:

invalidating corresponding entries in the deletion bitmap of the delta store, either in the delta store section or in the main store of the deletion bitmap, when the transaction is a deleting operation.

10. The method of claim 5, wherein the recording further comprises:

inserting both new data in the delta store of the table and corresponding entries in an insertion bitmap of the delta store and invalidating the corresponding entries in the deletion bitmap of the delta store, either in the delta store section or in the main store section of the deletion bitmap, when the transaction is an updating operation.

12. The system of claim 1, further comprising:

a transaction accumulator, configured to accumulate, for each table, the data changes of a plurality of transactions in the delta store; and

a store merger, configured to merge the delta store with the main store to apply the data changes generated by the plurality of the transactions accumulated in the delta store to the main store.

13. The system of claim 1, wherein the one or more bitmaps representing the each version of the table include an insertion bitmap.

14. The system of claim 1, wherein the one or more bitmaps representing the each version of the table includes a deletion bitmap.

15. The system of claim 14, wherein the deletion map includes a delta store section corresponding to a delta store portion of the table and a main store section corresponding to a main store portion of the table.

16. The system of claim 15, wherein the main store section of the deletion bitmap provides the row-level versioning semantics of the main store.

17. The system of claim 1, wherein the delta store is configured to provide row-level versioning semantics to the main store, so that the database behaves as having row-level versioning mechanism to a database client.

18. The system of claim 1, wherein the transaction recorder is further configured to:

insert both new data in the delta store and corresponding entries in an insertion bitmap of the delta store, when the transaction is an inserting operation.

19. The system of claim 1, wherein the transaction recorder is further configured to:

invalidate corresponding entries in a deletion bitmap of the delta store, either in the delta store section or in the main store of the deletion bitmap, when the transaction is a deleting operation.

20. The system of claim 15, wherein the transaction recorder is further configured to:

insert both new data in the delta store of the table and corresponding entries in an insertion bitmap of the delta store and invalidate the corresponding entries in the deletion bitmap of the delta store, either in the delta store section or the main store section of the deletion bitmap, when the transaction is an updating operation.

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 does not allow 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 transaction receiver, configured to receive a transaction associated with the column-based in-memory database;

a version determiner, for each table read by the transaction, configured to determine a version of the table in the delta store that represents a transaction-consistent snapshot of the database visible to the transaction, wherein each table is represented in the main store and the delta store, and each version of the table is represented by one or more bitmaps;

a transaction recorder, upon execution of a Data Manipulation Language (DML) as part of the transaction, for each table written by the transaction, configured to record data changes generated by the transaction in the one or more bitmaps that represent a private version of the table; and

a public version generator, upon commit of the transaction, for each table written by the transaction, configured to generate a new public version of the table based on the private version of the table, wherein the public version represents a new transaction-consistent snapshot of the database visible to subsequent transactions.

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 does not allow 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;

receiving a transaction associated with the column-based in-memory database;

for each table read by the transaction, determining a version of the table in the delta store that represents a transaction-consistent snapshot of the database visible to the transaction, wherein each table is represented in the main store and the delta store, and each version of the table is represented by one or more bitmaps;

upon execution of a Data Manipulation Language (DML) as part of the transaction, for each table written by the transaction, recording data changes generated by the transaction in the one or more bitmaps that represent a private version of the table; and

upon commit of the transaction, for each table written by the transaction, generating a new public version of the table based on the private version of the table, wherein the public version represents a new transaction-consistent snapshot of the database visible to subsequent transactions.