Non-blocking distinct grouping of database entries with overflow

• US 7,392,359 B2
• Filed: 10/01/2003
• Issued: 06/24/2008
• 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
• Primary Examiner(s): BATAILLE, PIERRE MICHE
• Application Number:
  US10/677,398
• Publication Number:
  US 20050076029A1
• Time in Patent Office: 1,728 Days
• Field of Search: 711/170, 711/152, 711/108, 711/217, 711/218, 707/1, 707/200, 707/100, 707/202
• US Class Current: 711/170
• 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 receives a query from a user, groups entries of data according to the query, and returns distinct entries of data to the user substantially concurrently with processing following grouping of data, wherein individual rows of data that match the query are output to the user prior to receiving all data matching the query.

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. An apparatus, comprising:

a non-blocking grouping mechanism that groups entries of data, and returns distinct 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.

6. A method of providing concurrent grouping, comprising:

receiving a query from a user;

receiving input entries of data for the query;

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, wherein the distinct entries of data match the query and are returned to the user before all data matching the query is processed.

7. The method of claim 6, 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.

8. The method of claim 6, 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.

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

10. 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 a user eventually receives the correct remaining rows, wherein in the non-blocking fashion individual rows of data that match a query are output to the user prior to a processing node processing all data from the query.

11. 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 a primary memory to a secondary memory, while remaining non-transferred clusters still function in a non-blocking fashion, wherein in the non-blocking fashion data matching a query is output concurrently while data potentially matching the query is being processed.

12. 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, wherein in the non-blocking fashion data matching a query is output concurrently while data being received for the query is still being processed.