Automated optimization for in-memory data structures of column store databases

Patent metadata

Field	Value
Publication number	US-11520763-B2
Application number	US-202016830645-A
Country	US
Kind code	B2
Filing date	Mar 26, 2020
Priority date	Mar 26, 2020
Publication date	Dec 6, 2022
Grant date	Dec 6, 2022

Abstract

There is provided a method for compressing a first tree data structure. The method includes determining, by a processor, to compress a first tree data structure associated with a dictionary of a database management system. The method further includes compressing the first tree data structure to generate a compressed tree data structure. The compressing includes traversing, by the processor and in response to the determining, the first tree data structure on a lowest level. The compressing further includes identifying, by the processor and in response to traversing, empty nodes on the lowest level. The compressing further includes removing the identified empty nodes to compress the lowest level. The compressing further includes constructing, in response to the removing, a second level of the compressed tree data structure based on the compressed lowest level, the second level higher in the compressed tree data structure than the compressed lowest level.

First claim

What is claimed is:

1. 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, cause operations comprising:
determining, by a database management system, to compress a first tree data structure associated with a dictionary of the database management system, wherein the first tree data structure comprises a cache sensitive B-tree used during read operations to search the dictionary, which is unsorted;
compressing, by the database management system, the first tree data structure to generate a compressed tree data structure, wherein the compressed tree data structure comprises a compressed cache sensitive B-tree, the compressing comprising:
traversing, in response to the determining, the first tree data structure on a lowest level;
identifying, in response to traversing, empty nodes on the lowest level;
removing the identified empty nodes to compress the lowest level; and
constructing, in response to the removing, a second level of the compressed tree data structure based on the compressed lowest level, the second level higher in the compressed tree data structure than the compressed lowest level;

receiving a read operation request;
searching, in response to receiving the read operation request and using the compressed tree data structure, a database associated with the database management system; and

returning a value associated with the read operation request, wherein searching the database using the compressed tree data structure is faster than searching the database based on the first tree data structure.

2. The system of claim 1 , the operations further comprising:
receiving a write operation request;
determining, in response to the write operation request, a location to write a value in the compressed tree data structure;
splitting, in response to the determining, a node of the compressed tree data structure into two nodes; and
inserting, in response to the splitting, the value across the split two nodes.

3. The system of claim 1 , wherein determining to compress the first tree data structure comprises:
obtaining information regarding the first tree data structure, the information including a quantity of values included in the first tree data structure, a quantity of nodes in the first tree data structure, and a quantity of read operations and a quantity of write operations,
comparing, in response to the obtaining, the quantity of values to the quantity of nodes and the quantity of write operations to a threshold, and
determining, in response to the comparing, to compress the first tree data structure.

4. The system of claim 3 , wherein the determining, in response to the comparing, to compress the first tree data structure comprises:
determining that a ratio of the quantity of values to the quantity of nodes satisfies a threshold, and
determining that the quantity of write operations satisfies a threshold.

5. The system of claim 1 , wherein the traversing comprises traversing the first tree data structure from left to right on the lowest level.

6. The system of claim 1 , wherein determining to compress the first tree data structure is based on a system load.

7. The system of claim 1 , wherein removing the identified empty nodes to compress the lowest level comprises:
removing a subset of the identified empty nodes on a portion of the first tree data structure.

8. The system of claim 1 , the operations further comprising:
executing a background process, the background process collecting information regarding the first tree data structure.

9. A method comprising:
determining, by a processor, to compress first tree data structure associated with a dictionary of a database management system, wherein the database management system comprises the processor and at least one memory, wherein the first tree data structure comprises a cache sensitive B-tree used during read operations to search the dictionary, which is unsorted;
compressing, by the processor, the first tree data structure to generate a compressed tree data structure, wherein the compressed tree data structure comprises a compressed cache sensitive B-tree, the compressing comprising:
traversing, by the processor and in response to the determining, the first tree data structure on a lowest level;
identifying, by the processor and in response to traversing, empty nodes on the lowest level;
removing, by the processor, the identified empty nodes to compress the lowest level; and
constructing, in response to the removing, a second level of the compressed tree data structure based on the compressed lowest level, the second level higher in the compressed tree data structure than the compressed lowest level;
receiving a read operation request;

searching, in response to receiving the read operation request and using the compressed tree data structure, a database associated with the database management system; and
returning a value associated with the read operation request, wherein searching the database using the compressed tree data structure is faster than searching the database based on the first tree data structure.

10. The method of claim 9 , further comprising:
receiving a write operation request;
determining, in response to the write operation request, a location to write a value in the compressed tree data structure;
splitting, in response to the determining the location, a node of the compressed tree data structure into two nodes; and
inserting, in response to the splitting, the value across the split two nodes.

11. The method of claim 10 , further comprising:
executing a background process, the background process collecting information regarding the first tree data structure.

12. The method of claim 11 , wherein executing the background process is based on a time interval, a system load, an availability of computing resources, and/or a predicted impact of the compressing of the first tree data structure.

13. The method of claim 9 , wherein determining to compress the first tree data structure comprises:
obtaining information regarding the first tree data structure, the information including a quantity of values included in the first tree data structure, a quantity of nodes in the first tree data structure, and a quantity of read operations and a quantity of write operations,
comparing, in response to the obtaining, the quantity of values to the quantity of nodes and the quantity of write operations to a threshold, and
determining, in response to the comparing, to compress the first tree data structure.

14. The method of claim 13 , wherein the determining, in response to the comparing, to compress the first tree data structure comprises:
determining that a ratio of the quantity of values to the quantity of nodes satisfies a threshold, and
determining that the quantity of write operations satisfies a threshold.

15. The method of claim 9 , wherein values of the second level correspond to first values of blocks in the lowest level.

16. The method of claim 9 , wherein the traversing comprises traversing the first tree data structure from left to right on the lowest level, and wherein determining to compress the first tree data structure is based on a system load.

17. The method of claim 9 , wherein removing the identified empty nodes to compress the lowest level comprises removing a subset of the identified empty nodes on a portion of the first tree data structure.

18. A non-transitory computer readable medium storing instructions which, when

Assignees

• Sap Se

Inventors

• Legler Thomas

Classifications

• G06F16/221

  Column-oriented storage; Management thereof · CPC title

• G06F16/2246 Primary

  Trees, e.g. B+trees · CPC title

• G06F16/252

  between a Database Management System and a front-end application · CPC title

• G06F16/2458

  Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries · CPC title

• G06F16/2457

  with adaptation to user needs · CPC title