Efficient database undo / redo logging

Patent metadata

Field	Value
Publication number	US-9779104-B2
Application number	US-201414553833-A
Country	US
Kind code	B2
Filing date	Nov 25, 2014
Priority date	Nov 25, 2014
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

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.

First claim

What is claimed is:

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.

Assignees

• Andrei Mihnea
• Schreter Ivan
• Wein David
• Chen Shiping
• Zhou Panfeng
• Geissinger Steffen
• Sap Se

Inventors

• Andrei Mihnea
• Schreter Ivan
• Wein David
• Chen Shiping
• Zhou Panfeng
• Geissinger Steffen

Classifications

• G06F2201/835

  Timestamp · CPC title

• G06F11/1471

  involving logging of persistent data for recovery · CPC title

• G06F2201/80

  Database-specific techniques · CPC title

• G06F11/1474

  in transactions (updating of structured data in databases G06F16/23) · CPC title

• G06F16/2358 Primary

  Change logging, detection, and notification (replication G06F16/27) · CPC title