US6182079B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Specifying indexes by evaluating costs savings for improving operation in relational databases
Assignee: RPX Corp
•
Filing: 1996-12-16
•
Granted: 2001-01-30
•
Expires: 2016-12-16
Abstract
Abstract An index set for a databse is specified by analyzing a sample ( 718 ) of SQL statements applied to the database ( 701 ). Indexes ( 707 ) are identified that could assist in the execution of the analyzed statements and levels of improved operation are evaluated for each of said indexes. The evaluated levels are then processed ( 708 ) to specify an index set for inclusion on the database. The database may not include sufficient storage ( 702 ) for all of the specified indexes to be included, therefore the available storage space is allocated and indexes are selected on a prioritized basis.
Inventors
- 👤 Robert Stephen Lenzie
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-23 19:15
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2458; G06F16/2462; G06F16/22; G06F16/2228; G06F16/2272; Y; Y10; Y10S; Y10S707/00; Y10S707/99941; Y10S707/99942; Y10S707/99944; Y10S707/99945
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
66 words
A method of specifying a set of indexes for a database, comprising the steps of: analysing a plurality of statements supplied to said database to identify indexable predicates; deriving indexes from the indexable predicates identified in said analysing step; evaluating levels of improved operation achievable with said indexes by evaluating costs savings; processing said evaluated levels to specify a preferred set of indexes for said database.
Claim 2
Independent Claim
66 words
A method of specifying a set of indexes for a database, comprising the steps of: analysing a plurality of statements supplied to said database to identify indexable predicates; deriving indexes from the indexable predicates identified in said analysing step; evaluating levels of improved operation achievable with said indexes by evaluating costs savings; processing said evaluated levels to specify a preferred set of indexes for said database.
Claim 3
Dependent Claim
32 words
A method according to claim 1 , wherein levels of improved operation are evaluated by creating a scaled-down model of database tables derived from information relating to the nature of said tables.
Claim 4
Dependent Claim
24 words
A method according to claim 2 , wherein said model database is populated with representative data entries taken from the live database being modelled.
Claim 5
Dependent Claim
24 words
A method according to claim 3 , wherein said model is populated by considering the cardinality of an existing index of the live database.
Claim 6
Dependent Claim
27 words
A method according to claim 3 , wherein said model database is populated by considering the distribution of entries within an existing index of the live database.
Claim 7
Dependent Claim
20 words
A method according to claim 2 , wherein database statistics are copied from the live database to the database model.
Claim 8
Dependent Claim
21 words
A method according to claim 1 wherein possible indexes are ordered in terms of potentiality for being specified as preferred indexes.
Claim 9
Dependent Claim
35 words
A method according to claim 7 , wherein index combinations are identified by randomly combining existing possible indexes and measuring cost savings for said potential index combinations to produce a revised list of preferred indexes.
Claim 10
Dependent Claim
20 words
A method according to claim 8 , wherein said random selection is weighted in terms of previously calculated cost savings.
Claim 11
Dependent Claim
21 words
A method according to claim 9 , wherein weighting values are recalculated when new indexes are added to the preferred list.
Claim 12
Dependent Claim
54 words
A method according to claim 1 wherein, in said steps of evaluating levels of improved operation, a base cost is calculated for executing statements without additional indexes being present, new costs are calculated for executing statements for new possible indexes, and the old cost is compared with the new costs to obtain cost savings.
Claim 13
Dependent Claim
22 words
A method according to claim 11 , wherein each cost saving is calculated by subtracting the new cost from the old cost.
Claim 14
Dependent Claim
29 words
A method according to claim 12 , wherein cost savings are calculated for database tables by considering each new possible index in turn with reference to its respective table.
Claim 15
Dependent Claim
13 words
A method according to claim 11 wherein cost calculation includes estimating execution time.
Claim 16
Dependent Claim
14 words
A method according to claim 11 wherein cost calculation including assessing index maintenance overheads.
Claim 17
Dependent Claim
102 words
A database comprising a plurality of data tables stored in machine readable form, processing means for processing said data tables in response to statements and for generating indexes to facilitate the processing of said data tables, further comprising instructions executable by said processing means for specifying a preferred index set, wherein said instructions are configured to analyse a plurality of statements supplied to said database to identify indexable predicates, derive indexes from said indexable predicates, evaluate levels of improved operation achievable with said indexes by evaluating cost savings and process said evaluated levels to specify a preferred index set for said database.
Claim 18
Dependent Claim
102 words
A database comprising a plurality of data tables stored in machine readable form, processing means for processing said data tables in response to statements and for generating indexes to facilitate the processing of said data tables, further comprising instructions executable by said processing means for specifying a preferred index set, wherein said instructions are configured to analyse a plurality of statements supplied to said database to identify indexable predicates, derive indexes from said indexable predicates, evaluate levels of improved operation achievable with said indexes by evaluating cost savings and process said evaluated levels to specify a preferred index set for said database.
Claim 19
Independent Claim
77 words
An apparatus for specifying an index set for a database comprising: analysing means for analysing a plurality of statements supplied to the database to identify indexable predicates; deriving means operable to derive indexes from the indexable predicates identified by said analysing means; evaluating means for evaluating levels of improved operation achievable with said indexes by evaluating cost savings; and specifying means operable to process said evaluated levels and specify a preferred set of indexes for said database.
Claim 20
Independent Claim
77 words
An apparatus for specifying an index set for a database comprising: analysing means for analysing a plurality of statements supplied to the database to identify indexable predicates; deriving means operable to derive indexes from the indexable predicates identified by said analysing means; evaluating means for evaluating levels of improved operation achievable with said indexes by evaluating cost savings; and specifying means operable to process said evaluated levels and specify a preferred set of indexes for said database.
Claim 21
Dependent Claim
32 words
Apparatus according to claim 17 in which levels of improved operation are evaluated by creating a scaled down model of database tables derived from information relating to the nature of said tables.
Claim 22
Dependent Claim
24 words
Apparatus according to claim 18 in which said model database is populated with representative data and is taken from the live database being modelled.
Claim 23
Dependent Claim
23 words
Apparatus according to claim 19 in which said model is populated by considering the cardinality of an existing index of the live database.
Claim 24
Dependent Claim
26 words
Apparatus according to claim 19 in which said model database is populated by considering the distribution of entries within an existing index of the live database.
Claim 25
Dependent Claim
19 words
Apparatus according to claim 18 in which database statistics are copied from the live database to the database model.
Claim 26
Dependent Claim
21 words
Apparatus according to claim 17 in which possible indexes are ordered in terms of potentiality for being specified as preferred indexes.
Claim 27
Dependent Claim
34 words
Apparatus according to claim 23 in which index combinations are identified by randomly combining existing possible indexes and measuring cost savings for said potential index combinations to produce a revised list of preferred indexes.
Claim 28
Dependent Claim
19 words
Apparatus according to claim 24 in which said random selection is waited in terms of previously calculated cost savings.
Claim 29
Dependent Claim
20 words
Apparatus according to claim 25 in which waiting values are recalculated when new indexes are added to the preferred list.
Claim 30
Dependent Claim
42 words
Apparatus according to claim 17 in which a base cost is calculated for executing statements without additional indexes being present, new costs are calculated for new possible indexes and the old cost is compared with the new costs to obtain cost savings.
Claim 31
Dependent Claim
93 words
Data processing apparatus arranged to specify an index set for a database, said apparatus comprising data storage means, data processing means and program instructions readable from said data storage means, wherein said processing means is configured, in response to said instructions, to provide means for: analysing a plurality of statements supplied to said database to identify indexable predicates; deriving indexes from the indexable predicates identified; evaluating levels of improved operation achievable with said indexes by evaluating cost savings; and processing said evaluated levels to specify a set of preferred indexes for said database.
Claim 32
Dependent Claim
93 words
Data processing apparatus arranged to specify an index set for a database, said apparatus comprising data storage means, data processing means and program instructions readable from said data storage means, wherein said processing means is configured, in response to said instructions, to provide means for: analysing a plurality of statements supplied to said database to identify indexable predicates; deriving indexes from the indexable predicates identified; evaluating levels of improved operation achievable with said indexes by evaluating cost savings; and processing said evaluated levels to specify a set of preferred indexes for said database.
Claim 33
Dependent Claim
109 words
A data processing apparatus for specifying an index set for a database, said apparatus comprising at least one disc storage device for storing data, a computer for processing data, and program instructions readable from said at least one disc storage device, wherein said computer is comprised of at least one processor, said at least one processor, in response to said instructions: analysing a plurality of statements supplied to said database to identify indexable predicates; deriving indexes from the indexable predicates identified; evaluating levels of improved operation achievable with said indexes by evaluating cost savings; and processing said evaluated levels to specify a set of preferred indexes for said database.
Claim 34
Dependent Claim
109 words
A data processing apparatus for specifying an index set for a database, said apparatus comprising at least one disc storage device for storing data, a computer for processing data, and program instructions readable from said at least one disc storage device, wherein said computer is comprised of at least one processor, said at least one processor, in response to said instructions: analysing a plurality of statements supplied to said database to identify indexable predicates; deriving indexes from the indexable predicates identified; evaluating levels of improved operation achievable with said indexes by evaluating cost savings; and processing said evaluated levels to specify a set of preferred indexes for said database.
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) | 2004-01-30 | 2004-07-31 | 2005-01-30 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2008-01-30 | 2008-07-31 | 2009-01-30 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2012-01-30 | 2012-07-31 | 2013-01-30 | $7700.00 | Window Closed / Lapsed |