Method, Apparatus and Data Structure for Copying Values of a Table of a Database

Abstract

A method for copying values of a table of a database between a primary memory and a secondary memory comprises selecting one or more segments, wherein the table is organized in a plurality of stripes and a plurality of vertical partitions, wherein a stripe comprises at least two rows of the table, wherein a vertical partition comprises one or more columns of the table, wherein each of the plurality of segments comprises values at a cross-section of a stripe and a vertical partition, and wherein each of the plurality of segments stores adjacent column values in adjacent locations of the primary or the secondary memory, and copying the one or more selected segments between the primary memory and the secondary memory.

Claims

1. A method for copying values of a table of a database between a primary memory and a secondary memory, comprising: selecting one or more segments of the table, wherein the table is stored as a plurality of segments, wherein the table is organized in a plurality of stripes and a plurality of vertical partitions, wherein a stripe comprises at least two rows of the table, wherein a vertical partition comprises one or more columns of the table, wherein each of the plurality of segments comprises values at a cross-section of a stripe and a vertical partition, and wherein each of the plurality of segments stores adjacent column values in adjacent locations of the primary or the secondary memory; and copying the one or more selected segments between the primary memory and the secondary memory.

2. The method of claim 1, wherein the one or more segments are segments that have changed.

3. The method of claim 1, further comprising: selecting the one or more segments in the primary memory that have changed; freezing the one or more selected segments such that a state of the one or more selected segments is preserved; copying the one or more frozen segments to the secondary memory; and releasing the frozen segments.

4. The method of claim 3, wherein freezing the one or more selected segments comprises at least one of shadowing, copying on write, or locking of the one or more selected segments.

5. The method of claim 1, further comprising: detecting a need for data eviction; determining an extent of the needed data eviction; selecting the one or more segments to be evicted; determining whether each of the one or more selected segments has been checkpointed; copying each of the one or more selected segments that has not been checkpointed from the primary memory to the secondary memory; and deleting the one or more selected segments from the primary memory.

6. The method of claim 5, wherein selecting the one or more segments to be evicted comprises: selecting one or more least recently used segments; and selecting one or more full columns that are not likely to be used.

7. The method of claim 5, wherein selecting the one or more segments to be evicted comprises: selecting one or more least recently used segments; and selecting one or more segments based on a selection criterion that is based on an age of the data.

8. An apparatus for copying values of a table of a database between a primary memory and a secondary memory, comprising: a processor configured to: select one or more segments of the table, wherein the table is stored as a plurality of segments, wherein the table is organized in a plurality of stripes and a plurality of vertical partitions, wherein a stripe comprises at least two rows of the table, wherein a vertical partition comprises one or more columns of the table, wherein each of the plurality of segments comprises values at a cross-section of a stripe and a vertical partition, and wherein each of the plurality of segments stores adjacent column values in adjacent locations of the primary or the secondary memory; and copy the one or more segments between the primary memory and the secondary memory.

9. The apparatus of claim 8, wherein the one or more segments are segments that have changed.

10. The apparatus of claim 8, wherein the processor is further configured to: selecting the one or more segments in the primary memory that have changed; freezing the one or more selected segments such that a state of the one or more selected segments is preserved; copying the one or more frozen segments to the secondary memory; and releasing the frozen segments.

11. The apparatus of claim 10, wherein freezing the one or more selected segments comprises at least one of shadowing, copying on write, or locking of the one or more selected segments.

12. The apparatus of claim 10, wherein the processor is further configured to: detecting a need for data eviction; determining an extent of the needed data eviction; selecting the one or more segments to be evicted; determining whether each of the one or more selected segments has been checkpointed; copying each of the one or more selected segments that has not been checkpointed from the primary memory to the secondary memory; and deleting the one or more selected segments from the primary memory.

13. The apparatus of claim 10, wherein the processor is further configured to: select one or more least recently used segments; and select one or more full columns that are not likely to be used.

14. A computer-readable storage medium, comprising program code for: selecting one or more segments of a table of a database, wherein the table is stored as a plurality of segments, wherein the table is organized in a plurality of stripes and a plurality of vertical partitions, wherein a stripe comprises at least two rows of the table, wherein a vertical partition comprises one or more columns of the table, wherein each of the plurality of segments comprises values at a cross-section of a stripe and a vertical partition, and wherein each of the plurality of segments stores adjacent column values in adjacent locations of the primary or the secondary memory; and copying the one or more selected segments between a primary memory and a secondary memory.

15. The computer-readable storage medium of claim 14, wherein the one or more segments are segments that have changed.

16. The computer-readable storage medium of claim 14, further comprising program code for: selecting the one or more segments in the primary memory that have changed; and freezing the one or more selected segments such that a state of the one or more selected segments is preserved.

17. The computer-readable storage medium of claim 16, further comprising program code for: copying the one or more frozen segments to the secondary memory; and releasing the frozen segments.

18. The computer-readable storage medium of claim 14, wherein freezing the one or more selected segments comprises at least one of shadowing, copying on write, or locking of the one or more selected segments.

19. The computer-readable storage medium of claim 14, further comprising program code for: detecting a need for data eviction; determining an extent of the needed data eviction; and selecting the one or more segments to be evicted.

20. The computer-readable storage medium of claim 19, further comprising program code for: determining whether each of the one or more selected segments has been checkpointed; copying each of the one or more selected segments that has not been checkpointed from the primary memory to the secondary memory; and deleting the one or more selected segments from the primary memory.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0037] To illustrate the technical features of embodiments of the present disclosure more clearly, the accompanying drawings provided for describing the embodiments are introduced briefly in the following. The accompanying drawings in the following description are merely some embodiments of the present disclosure, but modifications on these embodiments are possible without departing from the scope of the present disclosure as defined in the claims.

[0038] FIG. 1 shows a high level diagram of a system for copying values of a table of a database that is not in accordance with the present disclosure.

[0039] FIG. 2 shows a schematic illustration of a table that is organized according to embodiments of the disclosure.

[0040] FIG. 3 shows a schematic illustration of a table of a database and a method for checkpointing values of the table in an embodiment of the disclosure that is related to checkpointing.

[0041] FIG. 4 shows a flow chart of a method for checkpointing a database according to an embodiment of the disclosure.

[0042] FIG. 5 shows a schematic illustration of a table of a database and a method for evicting segments of that table to a secondary memory in accordance with the present disclosure.

[0043] FIG. 6 shows a flow chart of a method for evicting segments of a table according to an embodiment of the disclosure.

[0044] FIG. 7 shows a schematic illustration of a table of a database and a method for restoring segments from the secondary memory in accordance with the present disclosure.

[0045] FIG. 8 shows a flow chart of a method for restoring segments of a table according to an embodiment of the disclosure.

DETAILED DESCRIPTION OF THE EMBODIMENTS

[0046] FIG. 1 is a high level diagram of a system for copying data that is not part of the present disclosure. The system 100 shown in FIG. 1 comprises a primary memory 110 and a secondary memory 120. The primary memory 110 is organized in a plurality of rows 10a that are indexed by an index 112. On the secondary memory 120, rows 10b are stored that were evicted from the primary memory 110. On a row miss, i.e., when access is required to a row that is missing in primary memory 110, the corresponding evicted row 10b is restored to primary memory 110. No column-wise eviction and restore is possible.

[0047] FIG. 2 shows a schematic representation of a table 200 that is organized according to embodiments of the disclosure. This schematic representation also indicates the layout of a data structure according to an aspect of the present disclosure. The table 200 comprises rows 10 and columns 20. The table 200 is organized in stripes 12 that comprise a plurality of rows 10. In the example shown in FIG. 2 the first, second and third stripe 12 each comprises five rows. The table 200 is furthermore organized in vertical partitions 22 that comprise one or more columns 20. In the example shown in FIG. 2, the first vertical partition comprises one column, the second vertical partition comprises two columns, the third vertical partition 22 comprises three columns and the fourth and fifth vertical partition each comprise one column. Each cell of the table stores one column value 40.

[0048] In embodiments of the disclosure, the organization of the table is reflected in the physical storage of the table such that the segments of the table are stored subsequently on a physical storage. Furthermore, the segments are units of database checkpointing and data migration. The segments adhere to the principles of a columnar database in that they contain sequences of column values of one or more columns of the table.

[0049] FIG. 3 illustrates an apparatus and a method for checkpointing data of an in-memory database in accordance with the present disclosure. A database checkpoint is a persistent storage representing a consistent state of a database. Database checkpoints are used e.g. upon recovery from computer system failures. The operation of creating a checkpoint is called checkpointing. In an embodiment, one way to do checkpointing is to store only the data that has changed since the previous checkpointing. This is called incremental checkpointing. An execution of an incremental checkpointing using the disclosure method is illustrated in FIG. 3.

[0050] The system 300 shown in FIG. 3 comprises a table 310 that comprises rows 10 and columns 20 and that is organized in stripes 12 and vertical partitions 22. The plurality of stripes 12 and vertical partitions 22 define segments 30, wherein each segment 30 comprises the column values 40 that are contained in a cross section of a stripe 12 and a vertical partition 22.

[0051] Whenever a change to a segment is detected, the one or more changed segments 31a, 31b, 31c are copied to the secondary memory 320. In that way, the secondary memory 320 functions as a checkpoint storage for changed segments. On a subsequent segment restore, demand paging can be used whereby segments are actually loaded to primary memory 310 when they are needed. For example, the primary memory 310 can be the working memory of a computing device which is hosting the database and a database management system managing the database.

[0052] FIG. 4 shows a flow chart of a checkpointing method in accordance with the present disclosure. In a first step S410, a new checkpoint is begun (e.g. by starting the time interval corresponding to a new checkpoint). Then, in step S420, one or more changed segments are identified and freezed, i.e. a further modification of the changed segments is prevented. There are various methods to implement freezing, like shadowing, copy on write, or locking. With a copy-on-write freezing method, the frozen segments are “forgotten” (i.e. removed from memory) and replaced with changed copies.

[0053] In step S430, the changed segments are copied to a checkpoint storage, which can be a persistent storage. In step S440, the frozen segments are released, i.e. the frozen segments are made available for future modifications. In step S450, the method ends. In other embodiments, instead of the method ending in step S450, the method can be executed iteratively, i.e. a new checkpoint is begun.

[0054] A further embodiment of the present disclosure is related to an implementation of the operation of data migration from primary memory to persistent storage by way of segment eviction. A special case of a segment eviction is an eviction of a full column, as illustrated in FIG. 5.

[0055] The system 500 shown in FIG. 5 comprises a table 510 of an in-memory database that is primarily stored in a primary memory. Furthermore, the system 500 comprises a secondary memory 520 that acts as a segment storage for one or more segments 32a, 32b, 32c that are evicted from the primary memory.

[0056] The steps of carrying out the segment eviction are illustrated in the flow chart in FIG. 6. When there is a need for data eviction (for example, when there is no room in the primary memory for new data), the eviction method is invoked. In step S610, the method is invoked. In step S620, a need for eviction is detected, and an extent (in terms of the amount of free space needed) is evaluated. In this step, a selection method can be chosen, for example by selecting full columns for eviction. In step S630, the segments to be evicted are selected. As a special case, the whole column can be indicated for eviction. Once the segments are identified, in step S640, for each evicted segment, a check is done whether that segment has been checkpointed in its current state. If so, no storing to persistent storage is needed. The segment is removed from the primary memory. If the segment has not been checkpointed, in step S650 it is moved to the secondary memory, e.g. a persistent storage such as a hard disk. In step S660, the method ends. In other embodiments of the disclosure, the previous steps can be carried out iteratively, i.e., instead of ending the method in step S660, execution of the method is continued at step S620.

[0057] In embodiments of the disclosure, as indicated in FIG. 6, steps S640 and S650 are performed for each segment of the table.

[0058] A third embodiment of the disclosure is an implementation of an operation of segment restore, after the segments have been evicted before. The need for restore can result from a query that accesses the evicted data, for example an evicted column. FIG. 7 illustrates a system 700 where a plurality of segments 33a, 33b, 33c are restored from a segment storage 720 to a table 710 that is stored in a primary memory.

[0059] The corresponding method steps are illustrated in the flow chart shown in FIG. 8. Execution of the method begins in step S810. The need for restore (e.g. caused by a query requesting the evicted data) is evaluated in step S820. The segments to be restored are identified in step S830. In step S840, a check is performed whether there is enough memory space for restoring the segments. If not, in step S850, the necessary memory space is freed by evicting segments from the primary memory. In step S860, the identified segments are restored from the secondary memory to the primary memory. In step S870, the method terminates.

[0060] The foregoing descriptions are only implementation manners of the present disclosure, but the protection of the scope of the present disclosure is not limited to this. Any variations or replacements can be easily made through the person skilled in the art. Therefore, the protection scope of the present disclosure should be subject to the protection scope of the attached claims.