US6169983B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Index merging for database systems
Assignee: Microsoft Technology Licensing LLC
•
Filing: 1998-05-30
•
Granted: 2001-01-02
•
Expires: 2018-05-30
Abstract
Abstract An index merge tool helps form, for use by a database server in accessing a database in accordance with a workload of queries, an index configuration or set of indexes that consumes relatively less storage space. The index merge tool identifies from an initial set of indexes one or more combinations of two or more indexes on the same table of the database and merges each identified combination of indexes to form a merged set of indexes. The index merge tool identifies and merges each combination of indexes by identifying and merging one pair of indexes at a time. The index merge tool uses the merged set of indexes as the index configuration for use in executing queries against the database so long as the storage saved by the merged set of indexes exceeds a threshold amount and so long as any increase in the cost to execute queries against the database using the merged set of indexes is limited. Otherwise, the index merge tool uses the initial set of indexes as the index configuration.
Inventors
- 👤 Surajit Chaudhuri
- 👤 Vivek Narasayya
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-24 16:12
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2272; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935
Claims Analysis
Total Claims: 43
Claim 1
Independent Claim
62 words
A method form merging indexes for use in executing queries against a database, the method comprising the steps of: (a) identifying at least two indexes that meet a merge criteria from an initial set of indexes; and (b) merging the identified at least two indexes to form a merged index set consuming less storage space than for the initial set of indexes.
Claim 2
Independent Claim
62 words
A method form merging indexes for use in executing queries against a database, the method comprising the steps of: (a) identifying at least two indexes that meet a merge criteria from an initial set of indexes; and (b) merging the identified at least two indexes to form a merged index set consuming less storage space than for the initial set of indexes.
Claim 3
Dependent Claim
47 words
The method of claim 1 , comprising the step of: (c) using the merged index set to execute queries against the database if the storage space consumed by the merged index set is at least a predetermined percentage less than that for the initial set of indexes.
Claim 4
Dependent Claim
61 words
The method of claim 1 , comprising the step of: (c) using the merged index set to execute queries against the database if an estimated cost to execute queries of a workload for the merged index set is less than a predetermined percentage greater than an estimated cost to execute the queries of the workload for the initial set of indexes.
Claim 5
Dependent Claim
87 words
The method of claim 1 , comprising the step of: (c) using the merged index set to execute queries against the database if the storage space consumed by the merged index set is at least a predetermined percentage less than that for the initial set of indexes and if an estimated cost to execute queries of a workload for the merged index set is less than a predetermined percentage greater than an estimated cost to execute the queries of the workload for the initial set of indexes.
Claim 6
Dependent Claim
54 words
The method of claim 1 , wherein the identifying step (a) comprises the step of identifying from the initial set of indexes one or more combinations of two or more indexes on the same table of the database; and wherein the merging step (b) comprises the step of merging each identified combination of indexes.
Claim 7
Dependent Claim
52 words
The method of claim 5 , wherein the identifying step (a) and the merging step (b) comprise the steps of identifying and merging each identified combination of indexes by identifying and merging one pair of indexes on the same table of the database at a time to form a respective merged index.
Claim 8
Dependent Claim
53 words
The method of claim 6 , wherein the merging step (b) comprises the step of merging each identified pair of indexes such that all columns of one index of the identified pair are ordered ahead of any different columns of the other index of the identified pair to form the respective merged index.
Claim 9
Dependent Claim
57 words
The method of claim 6 , wherein the merging step (b) comprises the steps of determining how the indexes of each identified pair rank against one another and determining an order of columns for each respective merged index based on the determined ranking for the indexes of the identified pair used to form the respective merged index.
Claim 10
Dependent Claim
49 words
The method of claim 6 , wherein the identifying step (a) comprises the step of identifying only pairs of indexes that will form a merged index having a width less than a predetermined percentage greater than that for each index of the pair used to form the merged index.
Claim 11
Dependent Claim
81 words
The method of claim 6 , wherein the identifying step (a) comprises the step of identifying only pairs of indexes: (i) where the initial set of indexes comprises a single-column index on a leading column of both indexes of the pair and the leading column of each index of the pair are the same, or (ii) where the initial set of indexes comprises a single-column index on only one or none of the leading columns of the indexes of the pair.
Claim 12
Dependent Claim
53 words
The method of claim 1 , wherein the identifying step (a) comprises the steps of (i) identifying, from the initial set of indexes a subset of indexes each having a width of at least a predetermined number of column(s), and (ii) identifying the at least two indexes from the identified subset of indexes.
Claim 13
Dependent Claim
44 words
The method of claim 1 , wherein the identifying step (a) comprises the steps of (i) identifying from the initial set of indexes a subset of indexes for index-only access, and (ii) identifying the at least two indexes from the identified subset of indexes.
Claim 14
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 1 .
Claim 15
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 2 .
Claim 16
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 3 .
Claim 17
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 5 .
Claim 18
Independent Claim
113 words
A method for merging indexes for use in executing queries against a database, the method comprising the steps of: (a) identifying from an initial set of indexes a subset of indexes that meet a merge criteria on one table of the database; (b) merging each of one or more combinations of indexes from the identified subset of indexes to form a set of one or more respective merged indexes; (c) selecting a merged index from the set of one or more merged indexes; (d) replacing the combination of indexes used to form the selected merged index with the selected merged index; and (e) repeating steps (b), (c), and (d) one or more times.
Claim 19
Independent Claim
113 words
A method for merging indexes for use in executing queries against a database, the method comprising the steps of: (a) identifying from an initial set of indexes a subset of indexes that meet a merge criteria on one table of the database; (b) merging each of one or more combinations of indexes from the identified subset of indexes to form a set of one or more respective merged indexes; (c) selecting a merged index from the set of one or more merged indexes; (d) replacing the combination of indexes used to form the selected merged index with the selected merged index; and (e) repeating steps (b), (c), and (d) one or more times.
Claim 20
Dependent Claim
34 words
The method of claim 17 , wherein the selecting step (c) comprises the step of selecting from the set of one or more merged indexes the merged index that saves the most storage space.
Claim 21
Dependent Claim
45 words
The method of claim 17 , comprising the step of: (f) repeating steps (a), (b), (c), (d), and (e) for each of one or more other tables of the database on which the initial set of indexes are indexed to form a merged index set.
Claim 22
Dependent Claim
46 words
The method of claim 19 , comprising the step of: (g) using the merged index set to execute queries against the database if storage space consumed by the merged index set is at least a predetermined percentage less than that for the initial set of indexes.
Claim 23
Dependent Claim
61 words
The method of claim 19 , comprising the step of: (g) using the merged index set to execute queries against the database if an estimated cost to execute queries of a workload for the merged index set is less than a predetermined percentage greater than an estimated cost to execute the queries of the workload for the initial set of indexes.
Claim 24
Dependent Claim
86 words
The method of claim 19 , comprising the step of: (g) using the merged index set to execute queries against the database if storage space consumed by the merged index set is at least a predetermined percentage less than that for the initial set of indexes and if an estimated cost to execute queries of a workload for the merged index set is less than a predetermined percentage greater than an estimated cost to execute the queries of the workload for the initial set of indexes.
Claim 25
Dependent Claim
16 words
The method of claim 17 , wherein each combination of indexes is a pair of indexes.
Claim 26
Dependent Claim
50 words
The method of claim 17 , wherein the merging step (b) comprises the step of merging each combination of indexes such that all columns of one index of the combination are ordered ahead of any different columns of the other index(es) of the combination to form the respective merged index.
Claim 27
Dependent Claim
57 words
The method of claim 17 , wherein the merging step (b) comprises the steps of: (i) determining how the indexes of each combination rank against one another, and (ii) determining an order of columns for each respective merged index based on the determined ranking for the indexes of the combination used to form the respective merged index.
Claim 28
Dependent Claim
44 words
The method of claim 25 , wherein the determining step (b)(i) comprises the step of determining how the indexes of each combination rank against one another based on how a leading column of each index of the combination appears in one or more queries.
Claim 29
Dependent Claim
106 words
The method of claim 26 , wherein the determining step (b)(i) comprises the step of ranking each index of each combination with a highest rank if one or more queries have a condition on the leading column of the index, with a second highest rank if one or more queries have an order by clause on the leading column of the index, with a third highest rank if one or more queries have a group by clause on the leading column of the index, and with a fourth highest rank if one or more queries use the leading column of the index as a projection column.
Claim 30
Dependent Claim
48 words
The method of claim 17 , wherein the merging step (b) comprises the step of merging only combinations of indexes that form a merged index having a width less than a predetermined percentage greater than that for each index of the combination used to form the merged index.
Claim 31
Dependent Claim
86 words
The method of claim 17 , wherein the merging step (b) comprises the step of merging only combinations of indexes: (i) where the initial set of indexes comprises a single-column index on a leading column of at least two indexes of the combination and the leading column of those at least two indexes of the combination are the same, or (ii) where the initial set of indexes comprises a single-column index on only one or none of the leading columns of the indexes of the combination.
Claim 32
Dependent Claim
59 words
The method of claim 17 , wherein the identifying step (a) comprises the steps of: (i) identifying from the initial set of indexes an initial subset of indexes each having a width of at least a predetermined number of column(s), and (ii) identifying the subset of indexes on one table of the database from the initial subset of indexes.
Claim 33
Dependent Claim
50 words
The method of claim 17 , wherein the identifying step (a) comprises the steps of: (i) identifying from the initial set of indexes an initial subset of indexes for index-only access, and (ii) identifying the subset of indexes on one table of the database from the initial subset of indexes.
Claim 34
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 17 .
Claim 35
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 19 .
Claim 36
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 20 .
Claim 37
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 21 .
Claim 38
Independent Claim
83 words
A method for merging a pair of indexes that meet a merge criteria to form a merged index for use in executing queries against a database, the method comprising the steps of (a) selecting one of the indexes of the pair to precede the other index of the pair; and (b) merging the pair of indexes such that all columns of the selected index are ordered ahead of any different columns of the other index of the pair to form the merged index.
Claim 39
Independent Claim
83 words
A method for merging a pair of indexes that meet a merge criteria to form a merged index for use in executing queries against a database, the method comprising the steps of (a) selecting one of the indexes of the pair to precede the other index of the pair; and (b) merging the pair of indexes such that all columns of the selected index are ordered ahead of any different columns of the other index of the pair to form the merged index.
Claim 40
Dependent Claim
45 words
The method of claim 36 , wherein the selecting step (a) comprises the steps of: (i) determining how the indexes of the pair rank against one another, and (ii) selecting the index of the pair that ranks higher against the other index of the pair.
Claim 41
Dependent Claim
44 words
The method of claim 37 , wherein the determining step (a)(i) comprises the step of determining how the indexes of the pair rank against one another based on how a leading column of each index of the pair appears in one or more queries.
Claim 42
Dependent Claim
106 words
The method of claim 38 , wherein the determining step (a)(i) comprises the step of ranking each index of the pair with a highest rank if one or more queries have a condition on the leading column of the index, with a second highest rank if one or more queries have an order by clause on the leading column of the index, with a third highest rank if one or more queries have a group by clause on the leading column of the index, and with a fourth highest rank if one or more queries use the leading column of the index as a projection column.
Claim 43
Dependent Claim
15 words
A computer readable medium having computer-executable instructions for performing the steps of claim 36 .
References Cited (Backward Citations)
US5440730A
Cited
US5737732A
Cited
US5685003A
Cited
US5644763A
Cited
US5835959A
Cited
US6014663A
Cited
US5950186A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2004-01-02 | 2004-07-03 | 2005-01-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-02 | 2008-07-03 | 2009-01-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-02 | 2012-07-03 | 2013-01-02 | $7700.00 | Window Closed / Lapsed |