US4829427A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database query code generation and optimization based on the cost of alternate access methods
Assignee: EMC Corp
•
Filing: 1984-05-25
•
Granted: 1989-05-09
•
Expires: 2004-05-25
Abstract
Abstract An optimizer-code generator for use in a data base system. The optimizer-code generator employs a component called a scan analyzer for performing implementation-dependent analysis and providing implementation-dependent query code. The optimizer-code generator receives a query in logical tree form. It first optimizes the logical tree. In so doing, it provides information from the logical tree to the scan analyzer, which specifies what methods are available for accessing information required for the query and what each of the available methods costs. The optimizer-code generator uses the cost information in its optimization of the logical tree and specifies the access methods to be used in the logical tree. The code generator then uses the logical tree to generate query code. In so doing, it provides the specifications of the access methods to the scan analyzer, which returns query code for the access method. The code generator then incorporates the query code for the access method in the query code which it generates from the logical tree.
Inventors
- 👤 Nancy L. Green
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 11:20
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2452; G06F16/24524; G06F16/2453; G06F16/24534; G06F16/24542; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 16
Claim 1
Independent Claim
126 words
In a digital computer system employing a data base system for accessing stored data, means for transforming logical query data representing a query to be performed by said data base system into query code executable by said data base system comprising: (1) implementation-dependent analysis means for receiving certain said logical query data representing a said query and responding thereto by providing a cost data specifying the cost of an operation in said data base system specified by certain said logical query data and implementation-dependent portions of said query code required to perform said specified operation; and (2) implementation-independent transformation means for modifying said logical query data in response to said cost data and producing said executable query code containing said implementation-dependent portions from said analysis means.
Claim 2
Dependent Claim
126 words
In a digital computer system employing a data base system for accessing stored data, means for transforming logical query data representing a query to be performed by said data base system into query code executable by said data base system comprising: (1) implementation-dependent analysis means for receiving certain said logical query data representing a said query and responding thereto by providing a cost data specifying the cost of an operation in said data base system specified by certain said logical query data and implementation-dependent portions of said query code required to perform said specified operation; and (2) implementation-independent transformation means for modifying said logical query data in response to said cost data and producing said executable query code containing said implementation-dependent portions from said analysis means.
Claim 3
Dependent Claim
104 words
In the logical query data transformation means of claim 1, and wherein: said data base system includes a plurality of means for accessing said stored data; said implementation-dependent analysis means comprises a plurality of scan analyzing means, each one of said scan analyzing means corresponding to certain of said plurality of means for accessing said stored data; each one of said scan analyzing means provides said cost data for said means for accessing said stored data corresponding thereto; and each one of said scan analyzing means provides said implementation-dependent portions of said query code specifying said means for accessing said stored data corresponding thereto.
Claim 4
Dependent Claim
93 words
In the logical query data transformation means of claim 2, and wherein: each one of said scan analyzing means further provides preliminary information specifying a certain said means for accessing said stored data to said implementation-independent transformation means together with said cost data; said implementation-independent transformation means incorporates said preliminary information into said modified logical query data and returns said incorporated preliminary information to said scan analyzing means which provided said preliminary information; and each said scan analyzing means receiving said preliminary information produces said implementation-dependent portions of said executable query code therefrom.
Claim 5
Dependent Claim
97 words
In a digital computer system employing a data base system for accessing stored data by means of a plurality of access methods, improved query code generation means for generating query code executable by said data base system from logical query data representing a query wherein the improvement comprises: (1) preliminary information in said logical query data specifying certain of said plurality of access methods as are required for said query; and (2) a scan analyzer for receiving said preliminary information and providing therefor said executable query code for said access methods as are required for said query.
Claim 6
Dependent Claim
97 words
In a digital computer system employing a data base system for accessing stored data by means of a plurality of access methods, improved query code generation means for generating query code executable by said data base system from logical query data representing a query wherein the improvement comprises: (1) preliminary information in said logical query data specifying certain of said plurality of access methods as are required for said query; and (2) a scan analyzer for receiving said preliminary information and providing therefor said executable query code for said access methods as are required for said query.
Claim 7
Dependent Claim
66 words
In the improved query code generation means of claim 4, and wherein: said improved query code generation means further comprises a plurality of said scan analyzers, each one of said scan analyzers corresponding to a certain one of said plurality of access methods and receiving said preliminary information for said corresponding access method and providing said executable code for said certain one of said access methods.
Claim 8
Dependent Claim
85 words
In the improved query code generation means of claim 5, and wherein: said data base system further includes pluralities of access execution means, each one of said pluralities corresponding to one of said plurality of access methods; said preliminary informations specifies one of said plurality of access execution means corresponding to a given one of said plurality of access methods; and said scan analyzer corresponding to said given one of said plurality of access methods provides said executable code specifying said one access execution means.
Claim 9
Dependent Claim
91 words
In a digital computer system employing a data base system for accessing stored data by means of a plurality of access methods, improved means for optimizing logical query data corresponding to queries comprising: (1) a scan analyzer for determining the cost of any certain of said plurality of access methods and returning cost data specifying said cost; and (2) means responsive to said cost data for altering said logical query data for a given said query to employ said access methods having the lowest said cost for the given said query.
Claim 10
Dependent Claim
91 words
In a digital computer system employing a data base system for accessing stored data by means of a plurality of access methods, improved means for optimizing logical query data corresponding to queries comprising: (1) a scan analyzer for determining the cost of any certain of said plurality of access methods and returning cost data specifying said cost; and (2) means responsive to said cost data for altering said logical query data for a given said query to employ said access methods having the lowest said cost for the given said query.
Claim 11
Dependent Claim
55 words
In the improved means for optimizing logical query data of claim 7, and wherein: said improved means for optimizing logical query data further comprises a plurality of said scan analyzers, each one of said scan analyzers corresponding to one of said plurality of access methods and returning said cost data for said corresponding access method.
Claim 12
Dependent Claim
75 words
In the improved means for optimizing logical query data of claim 8, and wherein: said data base system further includes pluralities of access execution means, each one of said pluralities corresponding to one of said plurality of access methods; and said scan analyzer corresponding to one certain of said plurality of access methods determines said cost data for said plurality of access execution means corresponding to said one certain of said plurality of access methods.
Claim 13
Dependent Claim
102 words
In a data base system implemented in a digital computer system, the method of transforming logical query data representing a query to be performed by said data base system into logical query data representing a more efficient form of said query comprising the steps of: (1) providing said logical query data to a scan analyzer for determining the cost of employing certain ones of a plurality of access methods; (2) comparing the relative cost of said certain access methods; and (3) selecting the most cost-efficient one of said certain access methods and altering said logical query data to employ said selectled one.
Claim 14
Dependent Claim
102 words
In a data base system implemented in a digital computer system, the method of transforming logical query data representing a query to be performed by said data base system into logical query data representing a more efficient form of said query comprising the steps of: (1) providing said logical query data to a scan analyzer for determining the cost of employing certain ones of a plurality of access methods; (2) comparing the relative cost of said certain access methods; and (3) selecting the most cost-efficient one of said certain access methods and altering said logical query data to employ said selectled one.
Claim 15
Dependent Claim
104 words
In a data base system implemented in a digital computer system, the method of transforming logical query data into query code executable by said data base system comprising the steps of: (1) providing preliminary information concerning one of a plurality of access methods from said logical query data to a scan analyzer corresponding to said access method; (2) receiving portions of said executable query code specific to said access method specified in said preliminary information from said scan analyzer; and (3) generating, from said logical query data, said executable query code incorporating said portions of said executable query code specific to said access method.
Claim 16
Dependent Claim
104 words
In a data base system implemented in a digital computer system, the method of transforming logical query data into query code executable by said data base system comprising the steps of: (1) providing preliminary information concerning one of a plurality of access methods from said logical query data to a scan analyzer corresponding to said access method; (2) receiving portions of said executable query code specific to said access method specified in said preliminary information from said scan analyzer; and (3) generating, from said logical query data, said executable query code incorporating said portions of said executable query code specific to said access method.
References Cited (Backward Citations)
US3916387A
Cited
US3906455A
Cited
US4130867A
Cited
US4384325A
Cited
US4504907A
Cited
US4468728A
Cited
US4497039A
Cited
US4531186A
Cited
US4506326A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1992-05-08 | 1992-11-07 | 1993-05-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 1996-05-08 | 1996-11-07 | 1997-05-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2000-05-08 | 2000-11-07 | 2001-05-09 | $7700.00 | Window Closed / Lapsed |