Patent US6785684B2 successfully refreshed from Google Patents.
US6785684B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Apparatus and method for determining clustering factor in a database using block level sampling
Assignee: International Business Machines Corp
•
Filing: 2001-03-27
•
Granted: 2004-08-31
•
Expires: 2021-03-27
Abstract
Abstract An apparatus and method perform block-level sampling on a database, process the data to generate one or more matrices, and process the one or more matrices to generate a clustering factor for a selected index. In addition, the apparatus and method of the preferred embodiments allow the distribution of the clustering factor to be determined across a range, thereby allowing the identification of ranges where the clustering factor is high and ranges where the clustering factor is low. The clustering factor distribution can then be used to predict the memory paging performance of a search that uses an existing or a potential index that corresponds to the sampled data, and can therefore be used to predict the performance of searching the database using an existing or potential index for a particular database query.
Inventors
- 👤 Abdo Esmail Adbo
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-27 22:46
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/28; G06F16/284; G06F16/285; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/913; Y10S707/915; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99935; Y10S707/99936; Y10S707/99937; Y10S707/99941; Y10S707/99942
Claims Analysis
Total Claims: 34
Claim 1
Independent Claim
118 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a database residing in the memory, the database including a database manager that manages queries to the database; a clustering factor computation mechanism residing in the memory and executed by the at least one processor, wherein the clustering factor computation mechanism performs block sampling of a plurality of random physical data pages from the database, generates at least one matrix from the information in the block sampling, and processes the at least one matrix to determine clustering factor for a specified range in the database; wherein the database manager estimates performance of a query to the database based on the clustering factor.
Claim 2
Independent Claim
118 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a database residing in the memory, the database including a database manager that manages queries to the database; a clustering factor computation mechanism residing in the memory and executed by the at least one processor, wherein the clustering factor computation mechanism performs block sampling of a plurality of random physical data pages from the database, generates at least one matrix from the information in the block sampling, and processes the at least one matrix to determine clustering factor for a specified range in the database; wherein the database manager estimates performance of a query to the database based on the clustering factor.
Claim 3
Dependent Claim
128 words
The apparatus of claim 1 wherein the database includes a plurality of indexes that each have at least one key and a reference to at least one corresponding record in the database that satisfies the key, and wherein the clustering factor computation mechanism determines the clustering factor for a first range in a first index and determines the clustering factor for a second range in a second index, wherein the database manager determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on relative efficiencies indicated by the respective clustering factors.
Claim 4
Dependent Claim
33 words
The apparatus of claim 2 wherein the database manager selects one of the first and second indexes for a query of the database based on relative efficiencies indicated by the respective clustering factors.
Claim 5
Dependent Claim
25 words
The apparatus of claim 1 wherein the clustering factor computation mechanism further determines the distribution of the clustering factor over different ranges of the database.
Claim 6
Dependent Claim
34 words
The apparatus of claim 1 wherein the clustering factor computation mechanism generates the at least one matrix from an ordered list of keys generated from the block sampling and pages corresponding to the keys.
Claim 7
Dependent Claim
28 words
The apparatus of claim 1 wherein the clustering factor computation mechanism reduces the size of the at least one matrix using at least one digital image compression technique.
Claim 8
Dependent Claim
15 words
The apparatus of claim 6 wherein the digital image compression technique comprises singular value decomposition.
Claim 9
Independent Claim
270 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a database residing in the memory, the database including a plurality of indexes that each have at least one key and a reference to at least one corresponding record in the database that satisfies the key, the database further including a database manager that manages queries to the database; a clustering factor computation mechanism residing in the memory and executed by the at least one processor, wherein the clustering factor computation mechanism performs block sampling of a plurality of random physical data pages from a selected index in the database, generates an ordered list of keys from the block sampling with pages corresponding to the keys, generates a two-dimensional bitmap from the ordered list, processes the two-dimensional bitmap to generate at least one matrix, reduces the size of the at least one matrix using at least one digital image compression technique, and processes the reduced matrix to determine clustering factor for a specified range of the selected index, the clustering factor computation mechanism determining the clustering factor for a first range in a first index for the database and determining the clustering factor for a second range in a second index for the database; wherein the database manager determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on relative efficiencies indicated by the respective clustering factors.
Claim 10
Independent Claim
270 words
An apparatus comprising: at least one processor; a memory coupled to the at least one processor; a database residing in the memory, the database including a plurality of indexes that each have at least one key and a reference to at least one corresponding record in the database that satisfies the key, the database further including a database manager that manages queries to the database; a clustering factor computation mechanism residing in the memory and executed by the at least one processor, wherein the clustering factor computation mechanism performs block sampling of a plurality of random physical data pages from a selected index in the database, generates an ordered list of keys from the block sampling with pages corresponding to the keys, generates a two-dimensional bitmap from the ordered list, processes the two-dimensional bitmap to generate at least one matrix, reduces the size of the at least one matrix using at least one digital image compression technique, and processes the reduced matrix to determine clustering factor for a specified range of the selected index, the clustering factor computation mechanism determining the clustering factor for a first range in a first index for the database and determining the clustering factor for a second range in a second index for the database; wherein the database manager determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on relative efficiencies indicated by the respective clustering factors.
Claim 11
Independent Claim
65 words
A method for determining clustering factor for a specified range in a database, the method comprising the steps of: (A) block sampling a plurality of random physical data pages from the specified range; (B) generating at least one matrix from the information in the block sampling; and (C) processing the at least one matrix to determine clustering factor for the specified range of the database.
Claim 12
Independent Claim
65 words
A method for determining clustering factor for a specified range in a database, the method comprising the steps of: (A) block sampling a plurality of random physical data pages from the specified range; (B) generating at least one matrix from the information in the block sampling; and (C) processing the at least one matrix to determine clustering factor for the specified range of the database.
Claim 13
Dependent Claim
23 words
The method of claim 9 wherein the specified range in the database comprises at least a portion of an index for the database.
Claim 14
Dependent Claim
23 words
The method of claim 9 further comprising the step of determining the distribution of the clustering factor over different ranges of the database.
Claim 15
Dependent Claim
51 words
The method of claim 9 wherein step (B) comprises the steps of: (B1) generating an ordered list of keys from the block sampling with pages corresponding to the keys; (B2) generating a two-dimensional bitmap from the order list; and (B3) processing the two-dimensional bitmap to generate the at least one matrix.
Claim 16
Dependent Claim
27 words
The method of claim 9 further comprising the step of reducing the size of the at least one matrix using at least one digital image compression technique.
Claim 17
Dependent Claim
15 words
The method of claim 13 wherein the digital image compression technique comprises singular value decomposition.
Claim 18
Dependent Claim
73 words
The method of claim 9 wherein: steps (A), (B) and (C) are performed a first time to determine clustering factor for a first index; steps (A), (B) and (C) are performed a second time to determine clustering factor for a second index; and further comprising the step of selecting based on the clustering factors of the first and second indexes one of the first and second indexes for a query of the database.
Claim 19
Independent Claim
128 words
A method for determining clustering factor distribution for a plurality of ranges in a database, the method comprising the steps of: (A) block sampling a plurality of random physical data pages from the database; (B) generating an ordered list of keys from the block sampling with pages corresponding to the keys; (C) generating a two-dimensional bitmap from the order list; (D) processing the two-dimensional bitmap to generate at least one matrix; (E) reducing the size of the at least one matrix using at least one digital image compression technique; (F) processing the at least one matrix to determine clustering factor for a specified range in the database; and (G) repeating steps (A) through (F) to determine clustering factor for each of the plurality of ranges in the database.
Claim 20
Independent Claim
128 words
A method for determining clustering factor distribution for a plurality of ranges in a database, the method comprising the steps of: (A) block sampling a plurality of random physical data pages from the database; (B) generating an ordered list of keys from the block sampling with pages corresponding to the keys; (C) generating a two-dimensional bitmap from the order list; (D) processing the two-dimensional bitmap to generate at least one matrix; (E) reducing the size of the at least one matrix using at least one digital image compression technique; (F) processing the at least one matrix to determine clustering factor for a specified range in the database; and (G) repeating steps (A) through (F) to determine clustering factor for each of the plurality of ranges in the database.
Claim 21
Dependent Claim
67 words
A program product comprising: (A) a clustering factor computation mechanism that performs block sampling of a plurality of random physical data pages in a database, generates at least one matrix from the information in the block sampling, and processes the at least one matrix to determine clustering factor for a specified range of the database; and (B) computer-readable signal bearing media bearing the clustering factor computation mechanism.
Claim 22
Dependent Claim
67 words
A program product comprising: (A) a clustering factor computation mechanism that performs block sampling of a plurality of random physical data pages in a database, generates at least one matrix from the information in the block sampling, and processes the at least one matrix to determine clustering factor for a specified range of the database; and (B) computer-readable signal bearing media bearing the clustering factor computation mechanism.
Claim 23
Dependent Claim
14 words
The program product of claim 17 wherein the signal bearing media comprises recordable media.
Claim 24
Dependent Claim
14 words
The program product of claim 17 wherein the signal bearing media comprises transmission media.
Claim 25
Dependent Claim
67 words
The program product of claim 17 wherein the clustering factor computation mechanism determines the clustering factor for a first range in a first index and determines the clustering factor for a second range in a second index, and determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index.
Claim 26
Dependent Claim
42 words
The program product of claim 20 further comprising a database manager residing on the signal bearing media that selects one of the first and second indexes for a query of the database based on relative efficiencies indicated by the respective clustering factors.
Claim 27
Dependent Claim
26 words
The program product of claim 17 wherein the clustering factor computation mechanism further determines the distribution of the clustering factor over different ranges of the database.
Claim 28
Dependent Claim
35 words
The program product of claim 17 wherein the clustering factor computation mechanism generates the at least one matrix from an ordered list of keys generated from the block sampling and pages corresponding to the keys.
Claim 29
Dependent Claim
29 words
The program product of claim 17 wherein the clustering factor computation mechanism reduces the size of the at least one matrix using at least one digital image compression technique.
Claim 30
Dependent Claim
16 words
The program product of claim 24 wherein the digital image compression technique comprises singular value decomposition.
Claim 31
Dependent Claim
208 words
A program product comprising: (A) a database comprising: (A1) a clustering factor computation mechanism that performs block sampling of a plurality of random physical data pages from a selected index in a database, generates an ordered list of keys from the block sampling with pages corresponding to the keys, generates a two-dimensional bitmap from the ordered list, processes the two-dimensional bitmap to generate at least one matrix, reduces the size of the at least one matrix using at least one digital image compression technique, and processes the reduced matrix to determine clustering factor for a specified range of the selected index, the clustering factor computation mechanism determining the clustering factor for a first range in a first index for the database and determining the clustering factor for a second range in a second index for the database; (A2) a database manager that determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on the relative efficiencies indicated by the respective clustering factors; and (B) computer-readable signal bearing media bearing the database.
Claim 32
Dependent Claim
208 words
A program product comprising: (A) a database comprising: (A1) a clustering factor computation mechanism that performs block sampling of a plurality of random physical data pages from a selected index in a database, generates an ordered list of keys from the block sampling with pages corresponding to the keys, generates a two-dimensional bitmap from the ordered list, processes the two-dimensional bitmap to generate at least one matrix, reduces the size of the at least one matrix using at least one digital image compression technique, and processes the reduced matrix to determine clustering factor for a specified range of the selected index, the clustering factor computation mechanism determining the clustering factor for a first range in a first index for the database and determining the clustering factor for a second range in a second index for the database; (A2) a database manager that determines relative efficiencies of the first index compared to the second index by comparing the clustering factor of the first index with the clustering factor of the second index, the database manager selecting one of the first and second indexes for a query of the database based on the relative efficiencies indicated by the respective clustering factors; and (B) computer-readable signal bearing media bearing the database.
Claim 33
Dependent Claim
14 words
The program product of claim 26 wherein the signal bearing media comprises recordable media.
Claim 34
Dependent Claim
14 words
The program product of claim 26 wherein the signal bearing media comprises transmission media.
References Cited (Backward Citations)
US6233571B1
Cited
US5926812A
Cited
US6529891B1
Cited
US6389436B1
Cited
US6374251B1
Cited
US6049797A
Cited
US6347313B1
Cited
US6591007B1
Cited
US6633882B1
Cited
US6728728B2
Cited
US6654743B1
Cited
US6519591B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-08-31 | 2008-03-01 | 2008-08-31 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-08-31 | 2012-03-01 | 2012-08-31 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-08-31 | 2016-03-01 | 2016-08-31 | $7700.00 | Window Closed / Lapsed |