US6609131B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Parallel partition-wise joins
Assignee: Oracle International Corp
•
Filing: 1999-09-27
•
Granted: 2003-08-19
•
Expires: 2019-09-27
Abstract
Abstract Techniques are disclosed for expanding the concept of partitioning in variety of ways. In particular techniques are provided for performing multiple-dimension partitioning. In multiple-dimension partitioning, a database object is divided into partitions based on one criteria, and each of those resulting partitions is divided into sub-partitions based on a second criteria. The process of partitioning partitions based on different criteria may be repeated across any number of dimensions. Entirely different partitioning techniques may be used for each level of partitioning. The database server takes advantage of partitions when processing queries that include joins. In particular, techniques are provided for performing a full parallel partitioned-wise join, and a partial parallel partition-wise join. In a partial parallel partition-wise join, one of the join tables is statically partitioned on the join key and another join table is dynamically partitioned in a way that corresponds to the partition criteria of the statically partitioned table. In a full parallel partition-wise join, both of the tables involved in the join have already been statically partitioned based on the same criteria. The join operation is performed in parallel in a way that takes advantage of that static partitioning.
Inventors
- 👤 Mohamed Zait
- 👤 Beniot Dageville
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 21:43
CPC Classifications
G; G06; G06F; G06F9/00; G06F9/06; G06F9/46; G06F9/50; G06F9/5061; G06F9/5066; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99938; Y10S707/99941; Y10S707/99943
Claims Analysis
Total Claims: 12
Claim 1
Independent Claim
339 words
A method for processing a statement that specifies a join between a first object and a second object based on a join key, the method comprising the steps of: performing multi-level static partitioning of the first object, including performing the steps of: statically partitioning the first object at a first level by applying a first partitioning criteria to the first object to produce a first set of partitions; and statically partitioning the first object at a second level based on said join key, wherein the static partitioning based on said join key is performed by applying a second partitioning criteria to each partition in said first set of partitions to produce a second set of partitions; during execution of said statement, using the second level of static partitioning of said first object as a basis for distributing data of said first object, including performing the steps of: inspecting partitioning metadata based on said statement to determine that the second level of static partitioning of said first object, and not said first level of static partitioning, should be used as a basis for distributing data from said first object to a plurality of slave processes; distributing data from said first and second objects to each slave process of said plurality of slave processes based on said second partitioning criteria, including distributing to each slave process of said plurality of slave processes a first subset of data from said first object, wherein the first subset of data that is distributed to each slave process is established based on said second set of partitions; distributing to each slave process of said plurality of slave processes a second subset of data from said second object, wherein the second subset of data that is distributed to each slave process is established based on said second partitioning criteria; and causing each slave process of said plurality of slave processes to perform a join between the first subset of data assigned to the slave process and the second subset of data assigned to the slave process.
Claim 2
Independent Claim
339 words
A method for processing a statement that specifies a join between a first object and a second object based on a join key, the method comprising the steps of: performing multi-level static partitioning of the first object, including performing the steps of: statically partitioning the first object at a first level by applying a first partitioning criteria to the first object to produce a first set of partitions; and statically partitioning the first object at a second level based on said join key, wherein the static partitioning based on said join key is performed by applying a second partitioning criteria to each partition in said first set of partitions to produce a second set of partitions; during execution of said statement, using the second level of static partitioning of said first object as a basis for distributing data of said first object, including performing the steps of: inspecting partitioning metadata based on said statement to determine that the second level of static partitioning of said first object, and not said first level of static partitioning, should be used as a basis for distributing data from said first object to a plurality of slave processes; distributing data from said first and second objects to each slave process of said plurality of slave processes based on said second partitioning criteria, including distributing to each slave process of said plurality of slave processes a first subset of data from said first object, wherein the first subset of data that is distributed to each slave process is established based on said second set of partitions; distributing to each slave process of said plurality of slave processes a second subset of data from said second object, wherein the second subset of data that is distributed to each slave process is established based on said second partitioning criteria; and causing each slave process of said plurality of slave processes to perform a join between the first subset of data assigned to the slave process and the second subset of data assigned to the slave process.
Claim 3
Dependent Claim
40 words
The method of claim 1 wherein: the second object is statically partitioned based on the second partitioning criteria; and no dynamic partitioning is performed to establish the first and second subsets of data that are distributed to each slave process.
Claim 4
Dependent Claim
50 words
The method of claim 1 wherein: the second object is not statically partitioned based on the second partitioned criteria; and the method further comprises the step of, in response to said statement, dynamically partitioning the second object based on the same partitioning criteria used to statically partition said first object.
Claim 5
Dependent Claim
33 words
The method of claim 1 wherein the method further includes the step of establishing said first and second subsets of data to distribute to each slave process based on said second partitioning criteria.
Claim 6
Dependent Claim
62 words
The method of claim 1 wherein the method further includes the steps of: performing partition pruning based on one partitioning criteria of said first partitioning criteria and said second partitioning criteria; and establishing said first and second subsets of data to distribute to each slave process based on the other partitioning criteria of said first partitioning criteria and said second partitioning criteria.
Claim 7
Dependent Claim
346 words
A computer readable medium bearing instructions for processing a statement that specifies a join between a first object and a second object based on a join key, the instructions including instructions for performing the steps of: performing multi-level static partitioning of the first object, including performing the steps of: statically partitioning the first object at a first level by applying a first partitioning criteria to the first object to produce a first set of partitions; and statically partitioning the first object at a second level based on said join key, wherein the static partitioning based on said join key is performed by applying a second partitioning criteria to each partition in said first set of partitions to produce a second set of partitions; during execution of said statement, using the second level of static partitioning of said first object as a basis for distributing data of said first object, including performing the steps of: inspecting partitioning metadata based on said statement to determine that the second level of static partitioning of said first object, and not said first level of static partitioning, should be used as a basis for distributing data from said first object to a plurality of slave processes; distributing data from said first and second objects to each slave process of said plurality of slave processes based on said second partitioning criteria, including distributing to each slave process of said plurality of slave processes a first subset of data from said first object, wherein the first subset of data that is distributed to each slave process is established based on said second set of partitions; distributing to each slave process of said plurality of slave processes a second subset of data from said second object, wherein the second subset of data that is distributed to each slave process is established based on said second partitioning criteria; and causing each slave process of said plurality of slave processes to perform a join between the first subset of data assigned to the slave process and the second subset of data assigned to the slave process.
Claim 8
Dependent Claim
346 words
A computer readable medium bearing instructions for processing a statement that specifies a join between a first object and a second object based on a join key, the instructions including instructions for performing the steps of: performing multi-level static partitioning of the first object, including performing the steps of: statically partitioning the first object at a first level by applying a first partitioning criteria to the first object to produce a first set of partitions; and statically partitioning the first object at a second level based on said join key, wherein the static partitioning based on said join key is performed by applying a second partitioning criteria to each partition in said first set of partitions to produce a second set of partitions; during execution of said statement, using the second level of static partitioning of said first object as a basis for distributing data of said first object, including performing the steps of: inspecting partitioning metadata based on said statement to determine that the second level of static partitioning of said first object, and not said first level of static partitioning, should be used as a basis for distributing data from said first object to a plurality of slave processes; distributing data from said first and second objects to each slave process of said plurality of slave processes based on said second partitioning criteria, including distributing to each slave process of said plurality of slave processes a first subset of data from said first object, wherein the first subset of data that is distributed to each slave process is established based on said second set of partitions; distributing to each slave process of said plurality of slave processes a second subset of data from said second object, wherein the second subset of data that is distributed to each slave process is established based on said second partitioning criteria; and causing each slave process of said plurality of slave processes to perform a join between the first subset of data assigned to the slave process and the second subset of data assigned to the slave process.
Claim 9
Dependent Claim
49 words
The computer readable medium of claim 6 wherein: the second object is statically partitioned based on the same partitioning criteria used to statically partition said first object, and no dynamic partitioning is performed to establish the first and second subsets of data that are distributed to each slave process.
Claim 10
Dependent Claim
62 words
The computer readable medium of claim 6 wherein: the second object is not statically partitioned based on the same partitioning criteria used to statically partition said first object; and the instructions further include instructions for performing the step of, in response to said statement, dynamically partitioning the second object based on the same partitioning criteria used to statically partition said first object.
Claim 11
Dependent Claim
38 words
The computer readable medium of claim 6 wherein the instructions further include instructions for performing the step of establishing said first and second subsets of data to distribute to each slave process based on said second partitioning criteria.
Claim 12
Dependent Claim
67 words
The computer readable medium of claim 6 wherein the instructions further include instructions for performing the steps of: performing partition pruning based on one partitioning criteria of said first partitioning criteria and said second partitioning criteria; and establishing said first and second subsets of data to distribute to each slave process based on the other partitioning criteria of said first partitioning criteria and said second partitioning criteria.
References Cited (Backward Citations)
US5675791A
Cited
US5970495A
Cited
US6092062A
Cited
US6112198A
Cited
US6240428B1
Cited
US6003036A
Cited
US6223182B1
Cited
US6263331B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-08-18 | 2007-02-17 | 2007-08-19 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-08-18 | 2011-02-17 | 2011-08-19 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-08-18 | 2015-02-17 | 2015-08-19 | $7700.00 | Window Closed / Lapsed |