EP0421408A2
Expired / Lapsed
EP
⏱️ 0.0 years remaining
Joining two database relations on a common field in a parallel relational database field
Assignee: International Business Machines Corp
•
Filing: 1990-10-04
•
Granted: —
•
Expires: 2010-10-04
Abstract
Abstract A technique for performing joins in parallel on a multiple processor database system effectively deals with data skew. The join operation is performed in three stages with an optional fourth stage. The first stage is a preparatory stage, the detail of which depends on the underlying join algorithm used. This preparatory stage provides pre-processing the results of which are used in the following stage as the basis for defining subtasks for the final join operation. The data provided in the first stage is used in the second stage to both define subtasks and to optimally allocate these subtasks to different processors in such a manner that the processors are close to equally loaded in the final join operation, even in the presence of data skew. This second stage is an assignment stage the details of which depend on the underlying join algorithm. Once the second stage has completed its processing of the subtasks, the subtasks are shipped to their assigned processors for processing and the final join of the two relations in the third stage. The method used in the final join operation depends on the underlying join algorithm used. Optionally, during the actual join as performed in the third stage, there could be a dynamic re-assignment of the subtasks should the join operation become unbalanced.
Inventors
- 👤 Daniel Manuel Dias
- 👤 Joel Leonard Wolf
- 👤 Philip Shi-Lung Yu
Bibliographic Details
Application Number
—
Jurisdiction
EP
Data Source
google_patents
Last Synchronized
2026-10-26 20:32
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24532; G06F16/2455; G06F16/24553; G06F16/24558; G06F16/2456; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932
Claims Analysis
Total Claims: 11
Claim 1
Independent Claim
228 words
A method of joining two database relations on a common field in a parallel relational database environment having P processors, said method comprising the steps of: (a) partitioning the first relation into a multiplicity of partitions and the second relation into a corresponding multiplicity of partitions such that each individual value in the common field corresponds uniquely to one of the partitions of the first relation and uniquely to the corresponding one of the partitions of the second relation, thereby defining a current set of jobs, each consisting of the task of joining a partition of the first relation with the corresponding partition of the second relation, said step of partitioning reducing each of the jobs to less than or equal to 1/P of the total execution time so that the jobs will fit on a processor; (b) scheduling a current set of jobs among P processors using a minimum makespan optimization technique; (c) estimating the amount of completion time skew which would result if P processors were to perform the current set of jobs as scheduled in step (b); (d) comparing the estimated amount of skew with a skew standard; and (e) if the estimated skew meets the skew standard, executing the current set of jobs as last scheduled using P processors, thereby joining said two database relations on a common field with minimum completion time skew.
Claim 2
Independent Claim
228 words
A method of joining two database relations on a common field in a parallel relational database environment having P processors, said method comprising the steps of: (a) partitioning the first relation into a multiplicity of partitions and the second relation into a corresponding multiplicity of partitions such that each individual value in the common field corresponds uniquely to one of the partitions of the first relation and uniquely to the corresponding one of the partitions of the second relation, thereby defining a current set of jobs, each consisting of the task of joining a partition of the first relation with the corresponding partition of the second relation, said step of partitioning reducing each of the jobs to less than or equal to 1/P of the total execution time so that the jobs will fit on a processor; (b) scheduling a current set of jobs among P processors using a minimum makespan optimization technique; (c) estimating the amount of completion time skew which would result if P processors were to perform the current set of jobs as scheduled in step (b); (d) comparing the estimated amount of skew with a skew standard; and (e) if the estimated skew meets the skew standard, executing the current set of jobs as last scheduled using P processors, thereby joining said two database relations on a common field with minimum completion time skew.
Claim 3
Dependent Claim
207 words
The method recited in claim 1 wherein if the estimated skew does not meet the skew standard, further comprising the steps of: (f) replacing one of the largest partitions of the first and second relations with at least two smaller partitions, thereby defining replacement jobs for the job defined by the replaced partitions, each such replacement job consisting of the task of joining one of the smaller replacing partitions of the first relation with the corresponding smaller replacing partition of the second relation; (g) updating a current set of execution time estimates by replacing the execution time estimates of the replaced jobs with execution time estimates for the replacement jobs; (h) updating the scheduling of the current set of jobs among P processors so as to minimize the estimated completion time skew; (i) estimating the amount of completion time skew which would result if P processors were to perform the current set of jobs as scheduled in step (h); (j) comparing the amount of completion time skew estimated in step (i) with the skew standard; and (k) iteratively performing steps (e) through (j) until either the amount of skew meets the skew standard in step (j) or all partitions have been subpartitioned to a predetermined maximum extent.
Claim 4
Dependent Claim
136 words
The method recited in claim 2 wherein the step of partitioning further comprises the steps of: (I) estimating the time it will take for a single processor to accomplish each of said jobs, said estimates forming a current set of execution time estimates; (m) subpartitioning any partitions which correspond to jobs having an execution time estimate which is greater than the sum of the execution time estimates divided by P; (n) updating the current set of execution time estimates by replacing the execution time estimates of the replaced jobs with execution time estimates for the replacement jobs; and (o) iteratively performing the steps (m) and (n) until there is no execution time estimate for any job in the current set of jobs which is greater than the sum of the execution time estimates divided by P.
Claim 5
Dependent Claim
241 words
The method recited in claim 3 wherein the step of subpartitioning further comprises the steps of: (p) replacing any such partition of the first relation and corresponding partition of the second relation which include more than one distinct value in the common field with at least two smaller partitions, each individual value in the common field corresponding uniquely to one of the smaller partitions of the first relation and uniquely to the corresponding one of the smaller partitions of the second relation, thereby defining replacement jobs for any step (p) jobs in the current set of jobs, each such replacement job consisting of the task of joining one of such smaller partitions of the first relation with the corresponding smaller partition of the second relation; and (q) with respect to any such job where the corresponding partitions of the first and second relations include only one distinct value in the common field, replacing the larger of such corresponding partitions with X smaller partitions, where X is the minimum integer which when divided into the execution time estimate for such job results in a time less than the sum of the execution time estimates divided by P, thereby defining replacement jobs for any such step (q) jobs in the current set of jobs, each such replacement job consisting of the task of joining one of the X smaller partitions of the one relation with the unchanged corresponding partition of the other relation.
Claim 6
Dependent Claim
125 words
The method recited in claim 2 wherein V, and V 2 are two values in the domain of join columns of said first and second relations and a pair (V,,V 2 ) satisfying V l <V 2 is defined as a type 1 pair and a pair (V I ,V 2 ) satisfying V 1 = V2 is defined as a type 2 pair, further comprising prior to step (f) the steps of: (r) selecting the largest type 1 pair for replacing with at least two smaller partitions; but (s) if there are no type 1 pairs, then executing the current set of jobs as last scheduled using P processors, thereby joining said two database relations on a common field with minimum completion time skew.
Claim 7
Dependent Claim
128 words
The method recited in claim 3 wherein V 1 and V 2 are two values in the domain of join columns of said first and second relations and a pair (V 1 ,V 2 ) satisfying V 1 <V 2 is defined as a type 1 pair and a pair (V 1 ,V 2 ) satisfying V 1 =V 2 is defined as a type 2 pair, and wherein when a time estimate for one of said jobs is greater than 1/P of the total execution time in step (m) further comprising the steps of: (t) determining if said one job is a type 1 pair; and (u) if a type 1 pair, then replacing it with at least two partitions, one of which is of type 2.
Claim 8
Dependent Claim
53 words
The method recited in claim 6 wherein if said one job is a type 2 pair, then performing the following steps: (v) determining if the multiplicity of the type 2 pair can be increased; and (w) if the multiplicity can be increased, finding the smallest multiplicity and revising the current set of jobs.
Claim 9
Dependent Claim
45 words
The method recited in claim 7 wherein if the multiplicity of the type 2 pair cannot be increased, then performing the steps of: (x) assigning the type 2 pair to have a multiplicity P; and (y) assigning each of the P jobs to distinct processors.
Claim 10
Dependent Claim
44 words
The method recited in claim 1 wherein step (a) is performed by a hierarchical double hashing technique using two hash functions H 1 and H 2 where H 2 is used to further divide each hash partition created by H 1 into finer partitions.
Claim 11
Dependent Claim
39 words
The method recited in claim 1 wherein during step (e) monitoring the progress of said processors in the join operation, and if the progress of the join operation becomes unbalanced exceeding a predetermine threshold, repeating steps (b) to (d).
References Cited (Backward Citations)
No citation records indexed.
USPTO Annuity & Maintenance Windows
Maintenance schedule is calculated for granted US utility patents.