US5655080A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Distributed hash group-by cooperative processing
Assignee: International Business Machines Corp
•
Filing: 1995-08-14
•
Granted: 1997-08-05
•
Expires: 2015-08-14
Abstract
Abstract A method is provided for parallel and cooperative processing of data in a system wherein a coordinator process cooperates with one or more agent processes to which portions of the data processing function is off loaded. The agent processes read and process the data and accumulate a partial result. Each agent process, responsive to statistics collected on the content of the data processed, returns a partial result of the processing to the coordinator process. These steps are repeated iteratively until the processing has been completed. In a specific application, the performance of data processing systems is improved by speeding up database group-by queries. The group-by operation processing is distributed between the host central processing unit (CPU) and the input/output (I/O) processors (IOPs). Essentially, the IOPs are sent group-by requests to be performed on a set of disk blocks (extents), along with a predicate for tuples to be selected for query. The IOPs build a hash table with entries of the group-by element and a running aggregation function (sum for example). The IOPs retrieve the extents, extract the records, select records using the predicate specified, enter the element in the hash table if it is not already there, and perform the corresponding aggregation function.
Inventors
- 👤 Daniel Manual Dias
- 👤 Randy Lynn Egan
- 👤 Roy Louis Hoffman
- 👤 Richard Pervin King
- 👤 Kurt Walter Pinnow
- 👤 Christos Alkiviadis Polyzois
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-25 12:45
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5005; G06F9/5027; G06F16/00; G06F16/20; G06F16/24; G06F16/242; G06F16/2433; G06F16/244; G06F2209/00; G06F2209/50; G06F2209/509
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
198 words
A computer-implemented method for parallel and cooperative processing of data in a distributed data processing system having at least one host central processing unit (CPU) and one or more input/output processors (IOPs), wherein the data is a table of a relational database and wherein a coordinator process on the on the host CPU cooperates with one or more agent processes on the IOPs, comprising the steps of: off loading by the coordinator process a portion of a data processing function to the agent processes; responding to the portion of the data processing function off loaded by the coordinator process by reading and processing data from the table of relational database by the agent processes; accumulating, by each of the agent processes, partial results of the processing performed by the particular agent process; responsive to statistics collected on the content of the data processed, returning some of the partial results from the agent processes to the coordinator process; and iteratively repeating the previous steps until the portion of the data processing function off loaded by the coordinator process has been completed and all partial results of the off loaded data processing function have been returned to the coordinator process.
Claim 2
Dependent Claim
198 words
A computer-implemented method for parallel and cooperative processing of data in a distributed data processing system having at least one host central processing unit (CPU) and one or more input/output processors (IOPs), wherein the data is a table of a relational database and wherein a coordinator process on the on the host CPU cooperates with one or more agent processes on the IOPs, comprising the steps of: off loading by the coordinator process a portion of a data processing function to the agent processes; responding to the portion of the data processing function off loaded by the coordinator process by reading and processing data from the table of relational database by the agent processes; accumulating, by each of the agent processes, partial results of the processing performed by the particular agent process; responsive to statistics collected on the content of the data processed, returning some of the partial results from the agent processes to the coordinator process; and iteratively repeating the previous steps until the portion of the data processing function off loaded by the coordinator process has been completed and all partial results of the off loaded data processing function have been returned to the coordinator process.
Claim 3
Dependent Claim
47 words
The method of claim 1, wherein the result of the processing is a set of elements determined by a group-by query, and wherein the statistics include a partial count of a number of tuples corresponding to each of the elements in the set to be finally returned.
Claim 4
Dependent Claim
19 words
The method of claim 2, wherein the elements with the smallest partial counts are returned to the coordinator process.
Claim 5
Dependent Claim
21 words
The method of claim 1, wherein at least some of the agent processes are executed on different nodes of the system.
Claim 6
Dependent Claim
23 words
The method of claim 4, wherein at least one of the agent processes is executed on a different node than the coordinator process.
Claim 7
Dependent Claim
29 words
The method of claim 5, wherein the coordinator process is executed on a central processing unit and the agent processes are executed on one or more input/output processing units.
Claim 8
Dependent Claim
233 words
A distributed data processing system for parallel and cooperative processing of data in the system, wherein a coordinator process on the system cooperates with one or more agent processes, comprising: one or more input/output processors (IOPs), each said input/output processor including an input/output central processing unit and an input/output memory, an agent process running on said input/output processor; a host central processing unit (CPU) on which a coordinator process is run, said coordinator process cooperating with each said agent process, said coordinator process off loading a portion of a data processing function to the agent processes running on the input/output processors; an input/output bus connecting said main central processing unit with said plurality of input/output processors; and at least one direct access storage device connected to each of said plurality of input/output processors, said direct access storage device storing the data as a table of a relational database, each said agent process reading and processing data, accumulating partial results of the processing, and responsive to statistics collected on the content of the data processed, returning some of the partial results from the agent process to the coordinator process, each said agent process iteratively repeating the reading and processing data, accumulating partial results and returning some of the partial results until the processing has been completed and all partial results of the off loaded data processing function have been returned to the coordinator process.
Claim 9
Dependent Claim
233 words
A distributed data processing system for parallel and cooperative processing of data in the system, wherein a coordinator process on the system cooperates with one or more agent processes, comprising: one or more input/output processors (IOPs), each said input/output processor including an input/output central processing unit and an input/output memory, an agent process running on said input/output processor; a host central processing unit (CPU) on which a coordinator process is run, said coordinator process cooperating with each said agent process, said coordinator process off loading a portion of a data processing function to the agent processes running on the input/output processors; an input/output bus connecting said main central processing unit with said plurality of input/output processors; and at least one direct access storage device connected to each of said plurality of input/output processors, said direct access storage device storing the data as a table of a relational database, each said agent process reading and processing data, accumulating partial results of the processing, and responsive to statistics collected on the content of the data processed, returning some of the partial results from the agent process to the coordinator process, each said agent process iteratively repeating the reading and processing data, accumulating partial results and returning some of the partial results until the processing has been completed and all partial results of the off loaded data processing function have been returned to the coordinator process.
Claim 10
Dependent Claim
56 words
The distributed computer system as recited in claim 1 wherein the result of the processing by each said agent process is a set of elements determined by a group-by query, and wherein the statistics include a partial count of a number of tuples corresponding to each of the elements in the set to be finally returned.
Claim 11
Dependent Claim
28 words
The distributed computer system as recited in claim 8 wherein the elements with the smallest partial counts are returned to the coordinator process by each said agent process.
Claim 12
Dependent Claim
29 words
The distributed computer system recited in claim 7 wherein there are a plurality of input/output processors, each said input/output processor running an agent process cooperating with said coordinator process.
References Cited (Backward Citations)
US4989131A
Cited
US5557798A
Cited
US5321816A
Cited
US5317568A
Cited
US5369570A
Cited
US5546584A
Cited
US5548724A
Cited
US5550962A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-08-04 | 2001-02-03 | 2001-08-05 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-08-04 | 2005-02-03 | 2005-08-05 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-08-04 | 2009-02-03 | 2009-08-05 | $7700.00 | Window Closed / Lapsed |