Patent US5414810A successfully refreshed from Google Patents.
Patent US5797000A successfully refreshed from Google Patents.
US5797000A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method of performing a parallel relational database query in a multiprocessor environment
Assignee: International Business Machines Corp
•
Filing: 1996-06-20
•
Granted: 1998-08-18
•
Expires: 2016-06-20
Abstract
Abstract A method of performing a parallel join operation on a pair of relations R1 and R2 in a system containing P processors organized into Q clusters of P/Q processors each. The system contains disk storage for each cluster, shared by the processors of that cluster, together with a shared intermediate memory (SIM) accessible by all processors. The relations R1 and R2 to be joined are first sorted on the join column. The underlying domain of the join column is then partitioned into P ranges of equal size. Each range is further divided into M subranges of progressively decreasing size to create MP tasks T m ,p, the subranges of a given range being so sized relative to one another that the estimated completion time for task T m ,p is a predetermined fraction that of task T m-1 ,p. Tasks T m ,p with larger time estimates are assigned (and the corresponding tuples shipped) to the cluster to which processor p belongs, while tasks with smaller time estimates are assigned to the SIM, which is regarded as a universal cluster (cluster 0). The actual task-to-processor assignments are determined dynamically during the join phase in accordance with the dynamic longest processing time first (DLPT) algorithm. Each processor within a cluster picks its next task at any given decision point to be the one with the largest time estimate which is owned by that cluster or by cluster 0.
Inventors
- 👤 Partha Pratim Bhattacharya
- 👤 Jen-Yao Chung
- 👤 Mir Hamid Pirahesh
- 👤 Patricia G. Selinger
- 👤 Marisa S. Viveros
- 👤 Yun Wang
- 👤 Lawrence Peter Zaino
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 10:34
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24532; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
136 words
In a database system having a plurality of processing units, a method of performing a parallel query on a plurality of tables of a database, each of said tables comprising a set of one or more tuples, at least some of said tables permitting partitioned access, said query having an overall cost associated therewith, said method comprising the steps of: determining the estimated contribution of each of said tables to the overall cost of said query; selecting the table with the greatest estimated contribution to the overall cost of said query that also permits partitioned access; partitioning the selected table into a plurality of subsets of one or more tuples; dividing said query into a plurality of subqueries restricted to respective subsets of the selected table; and transmitting said subqueries to respective processing units for processing.
Claim 2
Dependent Claim
136 words
In a database system having a plurality of processing units, a method of performing a parallel query on a plurality of tables of a database, each of said tables comprising a set of one or more tuples, at least some of said tables permitting partitioned access, said query having an overall cost associated therewith, said method comprising the steps of: determining the estimated contribution of each of said tables to the overall cost of said query; selecting the table with the greatest estimated contribution to the overall cost of said query that also permits partitioned access; partitioning the selected table into a plurality of subsets of one or more tuples; dividing said query into a plurality of subqueries restricted to respective subsets of the selected table; and transmitting said subqueries to respective processing units for processing.
Claim 3
Dependent Claim
18 words
The method of claim 1, comprising the initial step of: determining the estimated overall cost of said query.
Claim 4
Dependent Claim
64 words
The method of claim 1 wherein said step of selecting said table comprises the steps of: constructing a list of said tables in order of their estimated contribution to the overall cost of said query; identifying the tables in said list that permit partitioned access; and choosing as the table to be split the first table in said list that also permits partitioned access.
Claim 5
Dependent Claim
31 words
The method of claim 1 wherein said step of partitioning the selected table comprises the step of: determining the number of subsets into which the selected table is to be partitioned.
Claim 6
Dependent Claim
26 words
The method of claim 1 wherein said step of partitioning the selected table comprises the step of: determining a partition scope for each of said subsets.
Claim 7
Dependent Claim
56 words
The method of claim 5 wherein said step of dividing said query into a plurality of subqueries restricted to respective subsets of the selected table comprises the steps of: generating a plurality of copies of said query; and modifying each of said copies by attaching a predicate portion restricting the query to the corresponding partition scope.
Claim 8
Dependent Claim
142 words
In a database system having a plurality of processing units, apparatus for performing a parallel query on a plurality of tables of a database, each of said tables comprising a set of one or more tuples, at least some of said tables permitting partitioned access, said query having an overall cost associated therewith, said apparatus comprising: means for determining the estimated contribution of each of said tables to the overall cost of said query; means for selecting the table with the greatest estimated contribution to the overall cost of said query that also permits partitioned access; means for partitioning the selected table into a plurality of subsets of one or more tuples; means for dividing said query into a plurality of subqueries restricted to respective subsets of the selected table; and means for transmitting said subqueries to respective processing units for processing.
Claim 9
Dependent Claim
142 words
In a database system having a plurality of processing units, apparatus for performing a parallel query on a plurality of tables of a database, each of said tables comprising a set of one or more tuples, at least some of said tables permitting partitioned access, said query having an overall cost associated therewith, said apparatus comprising: means for determining the estimated contribution of each of said tables to the overall cost of said query; means for selecting the table with the greatest estimated contribution to the overall cost of said query that also permits partitioned access; means for partitioning the selected table into a plurality of subsets of one or more tuples; means for dividing said query into a plurality of subqueries restricted to respective subsets of the selected table; and means for transmitting said subqueries to respective processing units for processing.
Claim 10
Dependent Claim
17 words
The apparatus of claim 7, further comprising: means for determining the estimated overall cost of said query.
Claim 11
Dependent Claim
67 words
The apparatus of claim 7 wherein said means for selecting said table comprises: means for constructing a list of said tables in order of their estimated contribution to the overall cost of said query; means for identifying the tables in said list that permit partitioned access; and means for choosing as the table to be split the first table in said list that also permits partitioned access.
Claim 12
Dependent Claim
30 words
The apparatus of claim 7 wherein said means for partitioning the selected table comprises: means for determining the number of subsets into which the selected table is to be partitioned.
Claim 13
Dependent Claim
25 words
The apparatus of claim 7 wherein said means for partitioning the selected table comprises: means for determining a partition scope for each of said subsets.
Claim 14
Dependent Claim
57 words
The apparatus of claim 11 wherein said means for dividing said query into a plurality of subqueries restricted to respective subsets of the selected table comprises: means for generating a plurality of copies of said query; and means for modifying each of said copies by attaching a predicate portion restricting the query to the corresponding partition scope.
Claim 15
Dependent Claim
156 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing a parallel query on a plurality of tables of a database in a database system having a plurality of processing units, each of said tables comprising a set of one or more tuples, at least some of said tables permitting partitioned access, said query having an overall cost associated therewith, said method comprising the steps of: determining the estimated contribution of each of said tables to the overall cost of said query; selecting the table with the greatest estimated contribution to the overall cost of said query that also permits partitioned access; partitioning the selected table into a plurality of subsets of one or more tuples; dividing said query into a plurality of subqueries restricted to respective subsets of the selected table; and transmitting said subqueries to respective processing units for processing.
Claim 16
Dependent Claim
156 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for performing a parallel query on a plurality of tables of a database in a database system having a plurality of processing units, each of said tables comprising a set of one or more tuples, at least some of said tables permitting partitioned access, said query having an overall cost associated therewith, said method comprising the steps of: determining the estimated contribution of each of said tables to the overall cost of said query; selecting the table with the greatest estimated contribution to the overall cost of said query that also permits partitioned access; partitioning the selected table into a plurality of subsets of one or more tuples; dividing said query into a plurality of subqueries restricted to respective subsets of the selected table; and transmitting said subqueries to respective processing units for processing.
Claim 17
Dependent Claim
22 words
The program storage device of claim 13, said method comprising the initial step of: determining the estimated overall cost of said query.
Claim 18
Dependent Claim
66 words
The program storage device of claim 13 wherein said step of selecting said table comprises the steps of: constructing a list of said tables in order of their estimated contribution to the overall cost of said query; identifying the tables in said list that permit partitioned access; and choosing as the table to be split the first table in said list that also permits partitioned access.
Claim 19
Dependent Claim
33 words
The program storage device of claim 13 wherein said step of partitioning the selected table comprises the step of: determining the number of subsets into which the selected table is to be partitioned.
Claim 20
Dependent Claim
28 words
The program storage device of claim 13 wherein said step of partitioning the selected table comprises the step of: determining a partition scope for each of said subsets.
Claim 21
Dependent Claim
58 words
The program storage device of claim 17 wherein said step of dividing said query into a plurality of subqueries restricted to respective subsets of the selected table comprises the steps of: generating a plurality of copies of said query; and modifying each of said copies by attaching a predicate portion restricting the query to the corresponding partition scope.
References Cited (Backward Citations)
US5091852A
Cited
US4956774A
Cited
US4920487A
Cited
US5179699A
Cited
US5361362A
Cited
GB2235798A
Cited
US5121494A
Cited
US5335345A
Cited
US5307485A
Cited
US5345585A
Cited
US5392430A
Cited
US5437032A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-08-17 | 2002-02-16 | 2002-08-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-08-17 | 2006-02-16 | 2006-08-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-08-17 | 2010-02-16 | 2010-08-18 | $7700.00 | Window Closed / Lapsed |