Efficient database undo / redo logging

• US 9,779,104 B2
• Filed: 11/25/2014
• Issued: 10/03/2017
• Est. Priority Date: 11/25/2014
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Andrei, Mihnea, Schreter, Ivan, Wein, David, Chen, Shiping, Zhou, Panfeng, Geissinger, Steffen
• Primary Examiner(s): Trujillo, James
• Assistant Examiner(s): TESSEMA, AIDA Z
• Application Number:
  US14/553,833
• Publication Number:
  US 20160147786A1
• Time in Patent Office: 1,043 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1402 Saving, restoring, recovering or retrying
• CPC Class Codes: G06F 11/1471 involving logging of persistent data for recovery
• CPC Class Codes: G06F 11/1474 in transactions G06F16/20 takes precedence
• CPC Class Codes: G06F 16/1756 based on delta files
• CPC Class Codes: G06F 16/1805 Append-only file systems, e.g. using logs or journals to store data
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/2358 Change logging, detection, and notification replication G06F16/27
• CPC Class Codes: G06F 2201/80 Database-specific techniques
• CPC Class Codes: G06F 2201/835 Timestamp

Abstract

Log records are accessed as part of a database operation in a database. The log records log insert, update, and delete operations in the database and include, for each row, a row position, a fragment identifier (ID), and a row ID. Thereafter, as part of the database operation, rows specified by the log records are located by: using the fragment identifier and the row position within the corresponding record of the log if the fragment with the corresponding fragment identifier is still available, otherwise, using the row identifier within the corresponding record of the log to look up the row position in an index of a corresponding row identifier column. The database operation is then finalized using the located rows. Related apparatus, systems, techniques and articles are also described.

Claims

1. A method comprising:

accessing, as part of a database operation in a database, log records logging insert, update, and delete operations in the database, the log records including a row position, a fragment identifier (ID), and a row ID of a row in a table, the row position representing an offset where the row is stored in an array of a fragment of a table, the fragment ID representing an immutable identifier of the fragment at which the row is stored, and the row ID representing an immutable identifier of the row;

in response to a determination that the fragment having the fragment ID is available in the database, using the fragment ID and the row position of the row to locate the row as part of the database operation;

in response to a determination that the fragment having the fragment ID is unavailable in the database, using the row ID of the row to determine a new row position of the row, the new row position being determined based on an index that maps row IDs to corresponding row positions; and

finalizing the database operation using the located rows.

2. The method of claim 1, wherein the database operation comprises a redo operation, an undo operation, a post-commit operation, and/or a cleanup operation.

3. The method of claim 2, wherein the database operation is performed on a delta fragment and/or a main fragment of the table.

4. The method of claim 3, wherein each fragment comprises a plurality of columns comprising:

a row ID column, user data columns, and multi-version concurrency control (MVCC) information.

5. The method of claim 4, wherein each fragment comprises, for each column, an array of column values, and at least one array comprising the MVCC information.

6. The method of claim 4, wherein the row ID column comprises the index mapping the row ID to the corresponding row positions.

7. The method of claim, 3 further comprising:

performing an insert operation by at least appending one or more new rows to the delta fragment of the table.

8. The method of claim 3, further comprising:

performing a delete operation by at least invalidating one or more old rows in a corresponding fragment of the table.

9. The method of claim 8, wherein the invalidated old rows are in the main fragment and/or the delta fragment of the table.

10. The method of claim 1, wherein the new row position is assigned to the row during append time for an insert operation and/or update operation in the delta fragment of the table, the new row position corresponding to new offset where the row is stored.

11. The method of claim 3, further comprising:

initiating a merge operation moving a plurality of rows from an old delta fragment to a new main fragment.

12. The method of claim 11, further comprising:

generating a new delta fragment; and

dropping the old delta fragment and an old main fragment after the plurality of rows are completely moved to the old delta fragment to the new main fragment.

13. The method of claim 12, further comprising:

assigning a respective fragment ID to each of the new delta fragment and the new main fragment.

14. The method of claim 12, further comprising:

assigning a new row position to each of the plurality of rows moved from the old delta fragment to the new main fragment, the new row position corresponding to a new array offset where each row is stored in the new main fragment, each row maintaining the same row ID.

15. The method of claim 6, wherein the determining of the new row position comprises:

searching the index based at least on the row ID, the index being an inverted index within the delta fragment or the main fragment of the table; and

then

using the new row position as an offset within an array of a corresponding fragment to locate the row.

16. The method of claim 15, wherein the row position specified in the log records cannot be used if a merge operation completes between creation of the log records and the database operation.

17. The method of claim 1, wherein if a merge operation does not complete between creation of the log records and the database operation, using the fragment ID and the row position to locate the row is faster than using the row identifier to look up the row position in the index to locate the row.

18. The method of claim 1, wherein the database is an in-memory column-oriented database.

19. A non-transitory computer program product storing instructions which, when executed by at least one data processor forming part of at least one computing device, result in operations comprising:

accessing, as part of a database operation in a database, log records logging insert, update, and delete operations in the database, the log records including a row position, a fragment identifier (ID), and a row ID of a row in a table, the row position representing an offset where the row is stored in an array of a fragment of a table, the fragment ID representing an immutable identifier at which the row is stored, and the row ID representing an immutable identifier of the row;

in response to a determination that the fragment having the fragment ID is available in the database, using the fragment ID and the row position of the row to locate the row as part of the database operation;

in response to a determination that the fragment having the fragment ID is unavailable in the database, using the row ID of the row to determine a new row position of the row, the new row position being determined based on an index that maps row IDs to row positions; and

finalizing the database operation using the located rows.

20. A system comprising:

at least one data processor; and

at least one memory storing instructions which, when executed by the at least one data processor, result in operations comprising;

accessing, as part of a database operation in a database, log records logging insert, update, and delete operations in the database, the log records including a row position, a fragment identifier (ID), and a row ID of a row in a table, the row position representing an offset where the row is stored in an array of a fragment, the fragment ID representing an immutable identifier of the fragment at which the row is stored, and the row ID representing an immutable identifier of the row;

in response to a determination that the fragment having the fragment ID is available in the database, using the fragment ID and the row position of the row to locate the row as part of the database operation;

in response to a determination that the fragment having the fragment ID is unavailable in the database, using the row ID of the row to determine a new row position of the row, the new row position being determined based on an index that maps row IDs to corresponding row positions; and

finalizing the database operation using the located rows.