Non-blocking distinct grouping of database entries with overflow

• US 20050076029A1
• Filed: 10/01/2003
• Published: 04/07/2005
• Est. Priority Date: 10/01/2003
• Status: Active Grant

• Current Assignee: Hewlett Packard Enterprise Development LP (Hewlett-Packard Enterprise Company)
• Original Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Inventors: Ben-Zvi, Boaz
• Granted Patent: US 7,392,359 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: Y10S 707/99931 Database or file accessing

Abstract

A grouping mechanism is provided which can return distinct groups of entries of data that satisfy a users query in a non-blocking fashion. Each distinct group can normaly be returned to the user substantially concurrently with the following entries being received and processed. The grouping mechanism supports an overflow mechanism which can transfer parts of the data between a primary memory to a secondary memory to alleviate shortage of primary memory. This non-blocking mechanism is useful as a part of a dataflow model data processing system.

Claims

1. An apparatus, comprising:

a non-blocking grouping mechanism that groups entries of data, and returns the groups of entries of data substantially concurrently with processing following grouping of data.

2. The apparatus of claim 1, further comprising an overflow mechanism by which data that includes the groups of entries of data that were grouped by the non-blocking grouping mechanism can be written from a primary memory to a secondary memory when the primary memory reaches an overflow condition.

3. The apparatus of claim 1, further comprising:

an overflow mechanism by which data that includes the groups of entries of data that were grouped by the non-blocking grouping mechanism can be written from a primary memory to a secondary memory when the primary memory reaches an overflow condition; and

a return mechanism by which the data can be returned from the secondary memory back to the primary memory, and whereupon the data is being returned to the user substantially concurrently with the rest of the data being processed by the non-blocking grouping mechanism.

4. The apparatus of claim 1, wherein the primary memory includes a primary Random Access Memory (RAM).

5. A method of providing concurrent grouping, comprising:

receiving input entries of data;

filtering out recurring entries of data from the input entries of data; and

returning distinct entries of data from the input entries of data to the user substantially concurrently with the receiving input entries of data.

6. The method of claim 5, wherein the method accommodates memory overflow by selected portions of the entries of data in a primary memory being flushed to a secondary memory to alleviate memory pressure.

7. The method of claim 5, wherein the method accommodates a memory overflow, wherein clusters of entries of data are written from a primary memory to a secondary memory when the primary memory runs out of memory, and wherein the primary memory overflows into the secondary memory by flushing one of its clusters of entries of data into the secondary memory and releasing certain ones of its in-memory buffers.

8. The method of claim 5, further comprising returning entries of data in a non-blocking fashion concurrently with other entries of data being processed.

9. A method of grouping entries of data, comprising:

prior to a potential overflow within a primary memory, grouping each input row of data and returning the data in a non-blocking fashion; and

in case of the overflow, ensuring that the user eventually receives the correct remaining rows.

10. A method of grouping entries of data, comprising:

segmenting the groups into clusters that limit a potential overflow to one cluster at a time;

prior to the potential overflow, all clusters perform work in a non-blocking fashion; and

in case of the overflow, transferring clusters one at a time from the primary memory to the secondary memory, while the remaining non-transferred clusters can still function in a non-blocking fashion.

11. A method of grouping entries of data, comprising:

prior to a potential overflow within a primary memory, grouping each input row of data and returning the data in a non-blocking fashion; and

in case of the overflow in which at least some of the data is transferred from the primary memory to a secondary memory, this data on the secondary memory is later processed in a non-blocking fashion concurrently with processing the remaining data.

12. An apparatus, comprising:

a non-blocking grouping mechanism that groups entries of data, and returns the groups of entries of data substantially concurrently with processing following entries of data to be grouped.

an overflow mechanism by which data that includes the groups of entries of data that were grouped by the non-blocking grouping mechanism can be written from a primary memory to a secondary memory when the primary memory reaches an overflow condition; and

a return mechanism by which the data can be returned from the secondary memory back to the primary memory, and whereupon the data is being returned to the user substantially concurrently with the rest of the data being processed by the non-blocking grouping mechanism;

a select mechanism by which a prescribed number of output groups are requested by the user, wherein operation of all of the non-blocking grouping mechanism, the overflow mechanism, and the return mechanism are halted when the requested prescribed number of output groups is reached.