US5950186A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Database system index selection using cost evaluation of a workload for multiple candidate index configurations
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1997-08-15
•
Granted: 1999-09-07
•
Expires: 2017-08-15
Abstract
Abstract An index selection tool helps reduce costs in time and memory in selecting an index configuration or set of indexes for use by a database server in accessing a database in accordance with a workload of queries. The index selection tool attempts to reduce the number of indexes to be considered, the number of index configurations to be enumerated, and the number of invocations of a query optimizer in selecting an index configuration for the workload.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Vivek Narasayya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 16:30
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99941; Y10S707/99942; Y10S707/99951; Y10S707/99952; Y10S707/99953; Y10T; Y10T156/00; Y10T156/10; Y10T156/1052; Y10T156/1062
Claims Analysis
Total Claims: 27
Claim 1
Independent Claim
150 words
A method for determining an estimated cost to execute a query of a workload against a database for a given index configuration of one or more indexes, wherein the database comprises a plurality of tables, the method comprising the steps of: (a) determining one or more atomic index configurations of one or more indexes for the query such that each determined atomic index configuration comprises only indexes on at most a predetermined number of the tables of the database; (b) determining an estimated cost to execute the query against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute the query against the database; and (c) determining an estimated cost to execute the query against the database for the given index configuration based on the estimated cost for each determined atomic index configuration as determined for the determining step (b).
Claim 2
Independent Claim
150 words
A method for determining an estimated cost to execute a query of a workload against a database for a given index configuration of one or more indexes, wherein the database comprises a plurality of tables, the method comprising the steps of: (a) determining one or more atomic index configurations of one or more indexes for the query such that each determined atomic index configuration comprises only indexes on at most a predetermined number of the tables of the database; (b) determining an estimated cost to execute the query against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute the query against the database; and (c) determining an estimated cost to execute the query against the database for the given index configuration based on the estimated cost for each determined atomic index configuration as determined for the determining step (b).
Claim 3
Dependent Claim
17 words
The method of claim 1, wherein the predetermined number of the tables of the database is two.
Claim 4
Dependent Claim
42 words
The method of claim 1, wherein the determining step (a) comprises the step of determining one or more atomic index configurations such that each determined atomic index configuration comprises at most a predetermined number of indexes for each table of the database.
Claim 5
Dependent Claim
21 words
The method of claim 3, wherein the predetermined number of indexes for each table of the database is one or two.
Claim 6
Dependent Claim
18 words
The method of claim 1, wherein the given index configuration is an atomic index configuration for the query.
Claim 7
Dependent Claim
43 words
The method of claim 1, wherein the determining step (b) comprises the step of simulating one or more indexes of the determined one or more atomic index configurations in determining the estimated cost for each determined atomic index configuration using the query optimizer.
Claim 8
Dependent Claim
37 words
The method of claim 6, wherein the simulating step comprises the steps of gathering a sample of data of a table of the database and generating statistical information to simulate an index based on the data sample.
Claim 9
Dependent Claim
41 words
The method of claim 1, wherein the determining step (c) comprises the step of determining the estimated cost to execute the query against the database for the given index configuration as the minimum estimated cost determined for the determining step (b).
Claim 10
Dependent Claim
35 words
The method of claim 1, comprising the step of selecting a set of candidate indexes, wherein the given index configuration and each determined atomic index configuration each comprise one or more of the candidate indexes.
Claim 11
Dependent Claim
36 words
The method of claim 9, comprising the step of performing steps (a), (b), and (c) to determine estimated costs of queries of the workload for other index configurations comprising one or more of the candidate indexes.
Claim 12
Dependent Claim
36 words
The method of claim 10, comprising the step of selecting an index configuration of one or more of the candidate indexes for use by the database server to execute queries of the workload against the database.
Claim 13
Dependent Claim
14 words
A computer readable medium having computer-executable instructions for performing the steps of claim 1.
Claim 14
Dependent Claim
14 words
A computer readable medium having computer-executable instructions for performing the steps of claim 3.
Claim 15
Dependent Claim
14 words
A computer readable medium having computer-executable instructions for performing the steps of claim 6.
Claim 16
Independent Claim
165 words
A method for determining an estimated cost to execute a query of a workload against a database for a given index configuration of one or more indexes, wherein the database comprises a plurality of tables, the method comprising the steps of: (a) determining one or more atomic index configurations of one or more indexes for the query such that each determined atomic index configuration comprises at most a predetermined number of indexes for each table of the database, wherein the predetermined number of indexes for each table of the database is greater than one; (b) determining an estimated cost to execute the query against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute the query against the database; and (c) determining an estimated cost to execute the query against the database for the given index configuration based on the estimated cost for each determined atomic index configuration as determined for the determining step (b).
Claim 17
Independent Claim
165 words
A method for determining an estimated cost to execute a query of a workload against a database for a given index configuration of one or more indexes, wherein the database comprises a plurality of tables, the method comprising the steps of: (a) determining one or more atomic index configurations of one or more indexes for the query such that each determined atomic index configuration comprises at most a predetermined number of indexes for each table of the database, wherein the predetermined number of indexes for each table of the database is greater than one; (b) determining an estimated cost to execute the query against the database for each determined atomic index configuration using a query optimizer of a database server that is to execute the query against the database; and (c) determining an estimated cost to execute the query against the database for the given index configuration based on the estimated cost for each determined atomic index configuration as determined for the determining step (b).
Claim 18
Dependent Claim
19 words
The method of claim 15, wherein the predetermined number of indexes for each table of the database is two.
Claim 19
Dependent Claim
18 words
The method of claim 15, wherein the given index configuration is an atomic index configuration for the query.
Claim 20
Dependent Claim
43 words
The method of claim 15, wherein the determining step (b) comprises the step of simulating one or more indexes of the determined one or more atomic index configurations in determining the estimated cost for each determined atomic index configuration using the query optimizer.
Claim 21
Dependent Claim
37 words
The method of claim 18, wherein the simulating step comprises the steps of gathering a sample of data of a table of the database and generating statistical information to simulate an index based on the data sample.
Claim 22
Dependent Claim
41 words
The method of claim 15, wherein the determining step (c) comprises the step of determining the estimated cost to execute the query against the database for the given index configuration as the minimum estimated cost determined for the determining step (b).
Claim 23
Dependent Claim
35 words
The method of claim 15, comprising the step of selecting a set of candidate indexes, wherein the given index configuration and each determined atomic index configuration each comprise one or more of the candidate indexes.
Claim 24
Dependent Claim
36 words
The method of claim 21, comprising the step of performing steps (a), (b), and (c) to determine estimated costs of queries of the workload for other index configurations comprising one or more of the candidate indexes.
Claim 25
Dependent Claim
36 words
The method of claim 22, comprising the step of selecting an index configuration of one or more of the candidate indexes for use by the database server to execute queries of the workload against the database.
Claim 26
Dependent Claim
14 words
A computer readable medium having computer-executable instructions for performing the steps of claim 15.
Claim 27
Dependent Claim
14 words
A computer readable medium having computer-executable instructions for performing the steps of claim 18.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-09-06 | 2003-03-08 | 2003-09-07 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-09-06 | 2007-03-08 | 2007-09-07 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-09-06 | 2011-03-08 | 2011-09-07 | $7700.00 | Window Closed / Lapsed |