Online Reorganization of Hybrid In-Memory Databases

• US 20130232176A1
• Filed: 03/05/2013
• Published: 09/05/2013
• Est. Priority Date: 03/05/2012
• Status: Active Grant

• Current Assignee: Hasso-Plattner-Institut für Softwaresystemtechnik GmbH
• Original Assignee: Hasso-Plattner-Institut für Softwaresystemtechnik GmbH
• Inventors: Plattner, Hasso, Krueger, Jens, Grund, Martin
• Granted Patent: US 9,424,282 B2
• Time in Patent Office: Days
• US Class Current: 707/803
• CPC Class Codes: G06F 16/20 of structured data, e.g. relational data
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/213 with details for schema evolution support
• CPC Class Codes: G06F 16/217 Database tuning G06F16/2282 takes precedence; database performance monitoring G06F11/3409

Abstract

A system and method that dynamically adapts to workload changes and adopts the best possible physical layout on the fly—while allowing simultaneous updates to the table. A process continuously and incrementally computes the optimal physical layout based on workload changes and determines whether or not switching to this new layout would be beneficial. The system can perform online reorganization of hybrid main memory databases with a negligible overheard, leading up to three orders of magnitude performance gains when determining the optimal layout of dynamic workloads and providing guarantees on the worst case performance of our system.

Claims

1. A computer-implemented database online reorganization method for dynamically adapting a database layout of a database containing tables, wherein the tables are vertically partitioned into containers, each container containing one or more attributes of one table, the method comprising:

analyzing, by a workload analysis tool of a computer system, a workload on a set of tables of the database, the workload comprising queries;

detecting, by the workload analysis tool of the computer system, a workload change of the workload;

analyzing, by a workload evaluation tool of the computer system, if a new layout for the set of tables is considered optimal in view of the workload change; and

deciding, by the workload evaluation tool of the computer system, whether the layout of the set of tables is switched to the new layout.

2. The method of claim 1, wherein detecting a workload change of the workload comprises:

determining a difference query indicative of the difference between a new workload and a previous workload.

3. The method of claim 2, wherein analyzing if a new layout for the set of tables is considered optimal in view of the workload change comprises:

determining a set of containers consisting of all containers of the set of tables that are accessed by the difference query;

determining a set of queries consisting of all queries of the previous workload that access any container of the set of containers;

determining a set of attributes consisting of all attributes of the set of containers that are accessed by any query of the set of queries; and

determining an optimal layout for the set of attributes.

4. The method of claim 3, wherein determining an optimal layout for the set of attributes comprises:

determining a set of primary partitions consisting of all primary partitions for the set of tables;

determining the workload costs of the new workload for every candidate partition of a first set of candidate partitions, the first set of candidate partitions consisting of all partitions obtained by merging two or more primary partitions of the set of primary partitions;

discarding a candidate partition from the first set of candidate partitions if the workload costs of the candidate partition is equal to or greater than the sum of the individual workload costs of the primary partitions forming the candidate partition, resulting in a second set of candidate partitions; and

determining the workload costs of the new workload for all possible layouts obtained by combining candidate partitions from the second set of candidate partitions.

5. The method of claim 1, wherein deciding whether the layout of the set of tables is switched to the new layout comprises:

determining the workload costs of the current layout, the workload costs of the layout that is considered optimal in view of the workload change, and the penalty costs as the difference between the workload costs of the current layout and the workload costs of the layout that is considered optimal in view of the workload change;

determining the transition costs for changing the current layout to the layout that is considered optimal in view of the workload change;

determining weighted penalty costs by multiplying the penalty costs with a weight factor;

determining new accumulated penalty costs by adding the weighted penalty costs to previously accumulated penalty costs; and

triggering the switching of the layout of the set of tables from the current layout to the layout that is considered optimal in view of the workload change if the new accumulated penalty costs is larger than the transition costs.

6. The method of claim 5, wherein determining the workload costs of the current layout is performed repeatedly, wherein the time interval between one determination of workload cost and the next determination of workload costs defines an epoch.

7. The method of claim 6, further comprising:

resetting the previously accumulated penalty costs if the layout that is considered optimal in view of the workload change in the present epoch is different from the layout that was considered optimal in view of the workload change in the previous epoch.

8. The method of claim 6, further comprising:

increasing the weight factor in each epoch.

9. The method of claim 6, further comprising:

storing the number of epochs in which each layout was considered optimal; and

when a new layout is considered optimal in view of the workload change, using the stored value of number of epochs in which the new layout was considered optimal as weight factor.

10. The method of claim 9, further comprising:

storing statistical information about the executed queries for each workload.

13. A non-transitory computer readable medium for use on a computer system containing computer-executable programming instructions for performing, when executed on the computer system the method according to claim 1.

11. A computer system for dynamically adapting a database layout of a database stored on the computer system, the database containing tables, wherein the tables are vertically partitioned into containers, each container containing one or more attributes of one table, the computer system comprising:

a workload analysis tool configured to analyze a workload on a set of tables of the database, the workload comprising queries; and

to detect a workload change of the workload; and

a workload evaluation tool configured to analyze if a new layout for the set of tables is considered optimal in view of the workload change; and

to decide whether the layout of the set of tables is switched to the new layout.

12. The computer system of claim 11, further comprising:

a storage manager tool configured to switch the layout of the set of tables to the new layout, according to the workload evaluation tool.