Memory-constrained aggregation using intra-operator pipelining

• US 10,114,866 B2
• Filed: 02/10/2016
• Issued: 10/30/2018
• Est. Priority Date: 12/23/2010
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP SE
• Inventors: Mueller, Ingo, Lacurie, Arnaud
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US15/040,501
• Publication Number:
  US 20170228319A1
• Time in Patent Office: 993 Days
• Field of Search: 707747, 707698, 707704
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 12/0864 using pseudo-associative means, e.g. set-associative or hashing
• CPC Class Codes: G06F 12/0895 of parts of caches, e.g. directory or tag array
• CPC Class Codes: G06F 12/1018 involving hashing techniques, e.g. inverted page tables
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24552 Database cache management
• CPC Class Codes: G06F 16/24575 using context
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning
• CPC Class Codes: G06F 2212/604 Details relating to cache allocation

Abstract

Disclosed herein are system, method, and computer program product embodiments for constraining the amount of memory used during data aggregation. An embodiment operates by separating input data into a plurality of partitions. The embodiment then inserts portions of the input data into blocks from a free list at a given level of a pipeline. The embodiment then inserts the blocks into buffers for processing at a subsequent level of the pipeline. The embodiment processes the inserted blocks at the subsequent level of the pipeline and concatenates the intermediate results into a final aggregate result.

Claims

1. A computer implemented method for aggregating tuples, comprising:

separating, by at least one processor, the tuples into a plurality of partitions using a hash function;

first processing, by the at least one processor, a portion of the tuples associated with a partition in the plurality of partitions based on the separating;

reserving, by the at least one processor, a first block for the partition from a free list based on a minimum number of blocks in the free list to perform a second processing and a third inserting;

first inserting, by the at least one processor, the processed portion of the tuples into the first block;

second inserting, by the at least one processor the first block into a buffer associated with the partition;

performing the second processing, by the at least one processor, the first block in the buffer; and

performing the third inserting, by the at least one processor, the processed first block into the free list,

wherein at least one of the separating, first processing, first inserting, second inserting, second processing, and third inserting is performed by one or more computers.

2. The method of claim 1, further comprising:

reserving, by the at least one processor, a second block for the partition from the free list.

3. The method of claim 1, wherein the free list contains less than a fixed number of blocks.

4. The method of claim 1, further comprising:

selecting, by the at least one processor, the partition from the plurality of partitions to perform the first processing based on a priority value, wherein the priority value is based on a number of blocks in the partition.

5. The method of claim 1, further comprising:

assigning, by the at least one processor, a thread to perform either the separating, first processing, first inserting, and second inserting or the second processing and the third inserting, wherein the assigning is based on a number of reserved blocks in the free list.

6. The method of claim 1, wherein the separating, first processing, first inserting, and second inserting are performed using a first thread and the second processing and the third inserting are performed using a second thread.

7. The method of claim 1, the separating further comprising:

separating the tuples into the plurality of partitions based on a size of a cache.

8. The method of claim 1, wherein a size of the partition is less than a size of a cache.

9. The method of claim 1, further comprising:

sorting the portion of the tuples associated the partition based on the separating.

10. A system, comprising:

a memory; and

at least one processor coupled to the memory and configured to;

separate tuples into a plurality of partitions using a hash function;

first process a portion of the tuples associated with a partition in the plurality of partitions based on the separation;

reserve a first block for the partition from a free list based on a minimum number of blocks in the free list to perform a second process and a third insert;

first insert the processed portion of the tuples into the first block;

second insert the first block into a buffer associated with the partition;

perform the second process the first block in the buffer; and

perform the third insert the processed first block into the free list.

11. The system of claim 10, the at least one processor further configured to:

reserve a second block for the partition from the free list.

12. The system of claim 10, wherein the free list contains less than a fixed number of blocks.

13. The system of claim 10, the at least one processor further configured to:

select the partition from the plurality of partitions to perform the first process based on a priority value, wherein the priority value is based on a number of blocks in the partition.

14. The system of claim 10, the at least one processor further configured to:

assign a thread to perform either the separate, first process, first insert, and second insert or the second process and the third insert, wherein the assignment is based on a number of reserved blocks in the free list.

15. The system of claim 10, wherein the at least one processor is configured to perform the separate, first process, first insert, and second insert using a first thread and the second process and the third insert using a second thread.

16. A tangible computer-readable device having instructions stored thereon that, when executed by at least one computing device, causes the at least one computing device to perform operations comprising:

separating tuples into a plurality of partitions using a hash function;

first processing a portion of the tuples associated with a partition in the plurality of partitions based on the separating;

reserving a first block for the partition from a free list based on a minimum number of blocks in the free list to perform a second processing and a third inserting;

first inserting the processed portion of the tuples into the first block;

second inserting the first block into a buffer associated with the partition;

performing the second processing the first block in the buffer; and

performing the third inserting the processed first block into the free list.

17. The computer-readable device of claim 16, the operations further comprising:

reserving a second block for the partition from the free list.

18. The computer-readable device of claim 16, wherein the free list contains less than a fixed number of blocks.

19. The computer-readable device of claim 16, the operations further comprising:

selecting the partition from the plurality of partitions to perform the first processing based on a priority value, wherein the priority value is based on a number of blocks in the partition.

20. The computer-readable device of claim 16, the operations further comprising:

assigning a thread to perform either the separating, first processing, first inserting, and second inserting or the second processing and the third inserting, wherein the assigning is based on a number of reserved blocks in the free list.