Database variable size entry container free space handling based on use patterns

• US 10,642,756 B2
• Filed: 05/19/2017
• Issued: 05/05/2020
• Est. Priority Date: 05/19/2017
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Thomsen, Dirk
• Primary Examiner(s): Chan, Tracy C.
• Application Number:
  US15/600,633
• Publication Number:
  US 20180335949A1
• Time in Patent Office: 1,082 Days
• Field of Search: None
• CPC Class Codes: G06F 12/123 with age lists, e.g. queue, most recently used [MRU] list or least recently used [LRU] list
• CPC Class Codes: G06F 16/22 Indexing; Data structures therefor; Storage structures

Abstract

Allocation of an entry in a variable size entry container is initiated in an in-memory database system. The variable size entry container includes a plurality of pages forming a chain. Thereafter, it is determined whether free space is found within the pre-existing pages. If free space is found, the entry is allocated in the free space. Otherwise, a new page is created and appended to the chain so that the entry can be allocated on such new page.

Claims

1. A computer-implemented method for minimizing fragmentation in a database comprising:

initiating, in an in-memory database system, allocation of an entry in a variable size entry container, the variable size entry container comprising a plurality of pages loaded into memory of the in-memory database system and forming a chain, the entries stored within the variable size entry container having different sizes;

determining whether free space is found within the pre-existing pages using a transient data structure storing information about pages in a persistence layer of the in-memory database system with free space and with deleted entries that can be reused;

allocating the entry in free space of a pre-existing page if free space is found;

creating a new page and appending it to the chain and allocating the entry on the new page if free space is not found;

loading either the pre-existing page in which free space was found or the newly created page into the memory of the in-memory database system;

deleting pages in the page chain when all entries on such pages are de-allocated; and

selectively bypassing the determining, allocating, creating, and loading based on a usage pattern of the variable sized entry container;

wherein the determining comprises measuring an amount of fragmentation within the page based on whether the usage pattern of the container is configured such that new entries are added and oldest entries are deleted when space is needed.

2. The method of claim 1, wherein the entry is allocated to the new page prior to the page being appended to the chain.

3. The method of claim 1, wherein the entry is allocated to the new page subsequent to the page being appended to the chain.

4. A system for minimizing fragmentation in a database comprising:

at least one data processor; and

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

initiating, in an in-memory database system, allocation of an entry in a variable size entry container, the variable size entry container comprising a plurality of pages loaded into memory of the in-memory database system and forming a chain, the entries stored within the variable size entry container having different sizes;

determining whether free space is found within the pre-existing pages using a transient data structure storing information about pages in a persistence layer of the in-memory database system with free space and with deleted entries that can be reused;

allocating the entry in free space of a pre-existing page if free space is found;

creating a new page and appending it to the chain and allocating the entry on the new page if free space is not found;

loading either the pre-existing page in which free space was found or the newly created page into the memory of the in-memory database system;

deleting pages in the page chain when all entries on such pages are de-allocated; and

selectively bypassing the determining, allocating, creating, and loading based on a usage pattern of the variable sized entry container;

wherein the determining comprises measuring an amount of fragmentation within the page based on whether the usage pattern of the container is configured such that new entries are added and oldest entries are deleted when space is needed.

5. The system of claim 4, wherein the at least one data processor and memory form part of the in-memory database system.

6. The system of claim 4, wherein the entry is allocated to the new page prior to the page being appended to the chain.

7. The system of claim 4, wherein the entry is allocated to the new page subsequent to the page being appended to the chain.

8. 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 for minimizing fragmentation in a database comprising:

initiating, in an in-memory database system, allocation of an entry in a variable size entry container, the variable size entry container comprising a plurality of pages loaded into memory of the in-memory database system and forming a chain, the entries stored within the variable size entry container having different sizes;

determining whether free space is found within the pre-existing pages using a transient data structure storing information about pages in a persistence layer of the in-memory database system with free space and with deleted entries that can be reused;

allocating the entry in free space of a pre-existing page if free space is found;

creating a new page and appending it to the chain and allocating the entry on the new page if free space is not found;

loading either the pre-existing page in which free space was found or the newly created page into the memory of the in-memory database system;

deleting pages in the page chain when all entries on such pages are de-allocated; and

selectively bypassing the determining, allocating, creating, and loading based on a usage pattern of the variable sized entry container;

wherein the determining comprises measuring an amount of fragmentation within the page based on whether the usage pattern of the container is configured such that new entries are added and oldest entries are deleted when space is needed.

9. The computer program product of claim 8, wherein the entry is allocated to the new page prior to the page being appended to the chain.

10. The computer program product of claim 8, wherein the entry is allocated to the new page subsequent to the page being appended to the chain.