US6092062A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Relational database query optimization to perform query evaluation plan, pruning based on the partition properties
Assignee: International Business Machines Corp
•
Filing: 1997-06-30
•
Granted: 2000-07-18
•
Expires: 2017-06-30
Abstract
Abstract A relational data base management system includes a query processor that uses a query operator partition property to perform QEP pruning and to ensure that data input to a query operator is partitioned appropriately for the operation. The partition property indicates the group of network nodes across which a table is distributed. The query processor also makes use of partition classes that are designated "interesting classes" to perform preoptimization planning and query pruning, and to perform look-ahead partitioning based on partition classes that are identified as being of interest to future operations, thereby more efficiently evaluating complex query statements in an MPP, shared-nothing environment.
Inventors
- 👤 Guy Maring Lohman
- 👤 Eugene Jon Shekita
- 👤 David E. Simmen
- 👤 Monica Sachiye Urata
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-02 22:13
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99935; Y10S707/99941; Y10S707/99944
Claims Analysis
Total Claims: 4
Claim 1
Independent Claim
409 words
A method of processing a query in a relational database management system that operates in a computer network to retrieve data from computer storage, the method comprising: receiving a query which is executable in connection with partitioned data tables; generating a plurality of interesting partition property values, each being indicative of a direct benefit for execution of an anticipated operator of the query; after generating the interesting partition property values, generating a plurality of alternative evaluation plans for consideration in execution of all or part of the query; generating a first set of properties, including a first partition property, associated with a first alternative evaluation plan; generating a second set of properties, including a second partition property, associated with a second alternative evaluation plan; comparing each property of the first set of properties with a corresponding property of the second set of properties; comparing a first execution cost of the first alternative evaluation plan and a second execution cost of the second alternative evaluation plan; pruning the second alternative evaluation plan from consideration in response to: determining that the second execution cost is greater than the first execution cost; and determining that, for each property of the second set of properties, the property is less general than or equivalent to a corresponding property of the first set of properties, including: wherein determining that the second partition property is less general than or equivalent to the first partition property is in response to: (1) identifying that the second partition property does not have any one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are equivalent, and wherein determining that the second partition property is not less general than or equivalent to the first partition property is in response to: (1) identifying that the first partition property does not have any one of the interesting partition property values and that the second partition property has one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are not equivalent.
Claim 2
Independent Claim
409 words
A method of processing a query in a relational database management system that operates in a computer network to retrieve data from computer storage, the method comprising: receiving a query which is executable in connection with partitioned data tables; generating a plurality of interesting partition property values, each being indicative of a direct benefit for execution of an anticipated operator of the query; after generating the interesting partition property values, generating a plurality of alternative evaluation plans for consideration in execution of all or part of the query; generating a first set of properties, including a first partition property, associated with a first alternative evaluation plan; generating a second set of properties, including a second partition property, associated with a second alternative evaluation plan; comparing each property of the first set of properties with a corresponding property of the second set of properties; comparing a first execution cost of the first alternative evaluation plan and a second execution cost of the second alternative evaluation plan; pruning the second alternative evaluation plan from consideration in response to: determining that the second execution cost is greater than the first execution cost; and determining that, for each property of the second set of properties, the property is less general than or equivalent to a corresponding property of the first set of properties, including: wherein determining that the second partition property is less general than or equivalent to the first partition property is in response to: (1) identifying that the second partition property does not have any one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are equivalent, and wherein determining that the second partition property is not less general than or equivalent to the first partition property is in response to: (1) identifying that the first partition property does not have any one of the interesting partition property values and that the second partition property has one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are not equivalent.
Claim 3
Dependent Claim
426 words
A relational database management system comprising: a central processing unit of a computer network; and a query processor that operates in the computer network to evaluate queries and retrieve data from computer storage, wherein the query processor is operative to perform query evaluation by: receiving a query which is executable in connection with partitioned data tables; generating a plurality of interesting partition property values, each being indicative of a direct benefit for execution of an anticipated operator of the query; after generating the interesting partition property values, generating a plurality of alternative evaluation plans for consideration in execution of all or part of the query; generating a first set of properties, including a first partition property, associated with a first alternative evaluation plan; generating a second set of properties, including a second partition property, associated with a second alternative evaluation plan; comparing each property of the first set of properties with a corresponding property of the second set of properties; comparing a first execution cost of the first alternative evaluation plan and a second execution cost of the second alternative evaluation plan; pruning the second alternative evaluation plan from consideration in response to: determining that the second execution cost is greater than the first execution cost; and determining that, for each property of the second set of properties, the property is less general than or equivalent to a corresponding property of the first set of properties, including: wherein determining that the second partition property is less general than or equivalent to the first partition property is in response to: (1) identifying that the second partition property does not have any one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are equivalent, and wherein determining that the second partition property is not less general than or equivalent to the first partition property is in response to: (1) identifying that the first partition property does not have any one of the interesting partition property values and that the second partition property has one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are not equivalent.
Claim 4
Dependent Claim
426 words
A relational database management system comprising: a central processing unit of a computer network; and a query processor that operates in the computer network to evaluate queries and retrieve data from computer storage, wherein the query processor is operative to perform query evaluation by: receiving a query which is executable in connection with partitioned data tables; generating a plurality of interesting partition property values, each being indicative of a direct benefit for execution of an anticipated operator of the query; after generating the interesting partition property values, generating a plurality of alternative evaluation plans for consideration in execution of all or part of the query; generating a first set of properties, including a first partition property, associated with a first alternative evaluation plan; generating a second set of properties, including a second partition property, associated with a second alternative evaluation plan; comparing each property of the first set of properties with a corresponding property of the second set of properties; comparing a first execution cost of the first alternative evaluation plan and a second execution cost of the second alternative evaluation plan; pruning the second alternative evaluation plan from consideration in response to: determining that the second execution cost is greater than the first execution cost; and determining that, for each property of the second set of properties, the property is less general than or equivalent to a corresponding property of the first set of properties, including: wherein determining that the second partition property is less general than or equivalent to the first partition property is in response to: (1) identifying that the second partition property does not have any one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are equivalent, and wherein determining that the second partition property is not less general than or equivalent to the first partition property is in response to: (1) identifying that the first partition property does not have any one of the interesting partition property values and that the second partition property has one of the interesting partition property values, and (2) identifying that the first partition property has one of the interesting partition property values, that the second partition property does not have any one of the interesting partition property values, and that the first and the second partition properties have values that are not equivalent.
References Cited (Backward Citations)
US5325525A
Cited
US5440727A
Cited
US5301317A
Cited
US5551027A
Cited
US5765146A
Cited
US5548754A
Cited
US5619692A
Cited
US5774692A
Cited
US5745746A
Cited
US5822747A
Cited
US5822750A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-07-18 | 2004-01-17 | 2004-07-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-07-18 | 2008-01-17 | 2008-07-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-07-18 | 2012-01-17 | 2012-07-18 | $7700.00 | Window Closed / Lapsed |