US5978792A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating dynamic and hybrid sparse indices for workfiles used in SQL queries
Assignee: Google LLC
•
Filing: 1998-01-13
•
Granted: 1999-11-02
•
Expires: 2018-01-13
Abstract
Abstract A method and apparatus for generating static, dynamic and hybrid sparse indices for use with workfiles used by SQL queries in a relational database management system.
Inventors
- 👤 Gautam Bhargava
- 👤 Paramesh Sampatrai Desai
- 👤 Piyush Goel
- 👤 Peter Hoa
- 👤 Fen-Ling Lin
- 👤 Balakrishna Raghavendra Iyer
- 👤 Jerry Mukai
- 👤 William Samuel Perlman
- 👤 Hong Sang Tie
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-29 19:12
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934; Y10S707/99936; Y10S707/99937
Claims Analysis
Total Claims: 48
Claim 1
Independent Claim
119 words
A method of performing a query in a computer-implemented database management system, comprising: (a) probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation; (b) returning an entry from the sparse index without performing the next search when the entry matches the key value; and (c) performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.
Claim 2
Independent Claim
119 words
A method of performing a query in a computer-implemented database management system, comprising: (a) probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation; (b) returning an entry from the sparse index without performing the next search when the entry matches the key value; and (c) performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.
Claim 3
Dependent Claim
27 words
The method of claim 1 above, wherein the performing step (c) further comprises inserting a new entry into the sparse index based on the next search results.
Claim 4
Dependent Claim
17 words
The method of claim 1 above, further comprising removing one or more entries from the sparse index.
Claim 5
Dependent Claim
16 words
The method of claim 1 above, wherein the static part of sparse index is never changed.
Claim 6
Dependent Claim
30 words
The method of claim 1, wherein the static part of the sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.
Claim 7
Dependent Claim
17 words
The method of claim 1, further comprising eliminating duplicate entries during the merge phase of file creation.
Claim 8
Dependent Claim
23 words
The method of claim 1 above, further comprising creating a dynamic part of the sparse index during a search phase of file access.
Claim 9
Dependent Claim
17 words
The method of claim 7, further comprising updating the dynamic part of the sparse index as required.
Claim 10
Dependent Claim
31 words
The method of claim 1, further comprising determining an exact location of the data record in the file using an auxiliary search and the approximate location provided by the sparse index.
Claim 11
Dependent Claim
21 words
The method of claim 1, wherein each entry in the sparse index comprises a key value and a record id (RID).
Claim 12
Dependent Claim
19 words
The method of claim 10, wherein the RID provides a location of a data record matching the key value.
Claim 13
Independent Claim
137 words
An apparatus for performing a query in a computer-implemented database management system, comprising: (a) means, performed by a computer, for probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation; (b) means, performed by a computer, for returning an entry from the sparse index without performing the next search when the entry matches the key value; and (c) means, performed by a computer, for performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.
Claim 14
Independent Claim
137 words
An apparatus for performing a query in a computer-implemented database management system, comprising: (a) means, performed by a computer, for probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation; (b) means, performed by a computer, for returning an entry from the sparse index without performing the next search when the entry matches the key value; and (c) means, performed by a computer, for performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.
Claim 15
Dependent Claim
30 words
The apparatus of claim 12 above, wherein the means for performing (c) further comprises means for inserting a new entry into the sparse index based on the next search results.
Claim 16
Dependent Claim
19 words
The apparatus of claim 12 above, further comprising means for removing one or more entries from the sparse index.
Claim 17
Dependent Claim
15 words
The apparatus of claim 12, wherein the static part of sparse index is never changed.
Claim 18
Dependent Claim
30 words
The apparatus of claim 12, wherein the static part of the sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.
Claim 19
Dependent Claim
19 words
The apparatus of claim 12, further comprising means for eliminating duplicate entries during the merge phase of file creation.
Claim 20
Dependent Claim
25 words
The apparatus of claim 12 above, further comprising means for creating a dynamic part of the sparse index during a search phase of file access.
Claim 21
Dependent Claim
19 words
The apparatus of claim 18, further comprising means for updating the dynamic part of the sparse index as required.
Claim 22
Dependent Claim
33 words
The apparatus of claim 12, further comprising means for determining an exact location of the data record in the file using an auxiliary search and the approximate location provided by the sparse index.
Claim 23
Dependent Claim
21 words
The apparatus of claim 12, wherein each entry in the sparse index comprises a key value and a record id (RID).
Claim 24
Dependent Claim
19 words
The apparatus of claim 21, wherein the RID provides a location of a data record matching the key value.
Claim 25
Dependent Claim
136 words
A program storage device readable by a computer, tangibly embodying one or more instructions executed by the computer to perform a query a computer-implemented database management system, the method comprising: (a) probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation; (b) returning an entry from the sparse index without performing the next search when the entry matches the key value; and (c) performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.
Claim 26
Dependent Claim
136 words
A program storage device readable by a computer, tangibly embodying one or more instructions executed by the computer to perform a query a computer-implemented database management system, the method comprising: (a) probing a sparse index to determine a starting location of a next search of a key value in the query, wherein the sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of a static part that is created during a merge phase of file creation; (b) returning an entry from the sparse index without performing the next search when the entry matches the key value; and (c) performing the next search using a closest starting entry from the sparse index when no entry in the sparse index matches the key value.
Claim 27
Dependent Claim
29 words
The article of manufacture of claim 23 above, wherein the performing step (c) further comprises inserting a new entry into the sparse index based on the next search results.
Claim 28
Dependent Claim
19 words
The article of manufacture of claim 23 above, further comprising removing one or more entries from the sparse index.
Claim 29
Dependent Claim
17 words
The article of manufacture of claim 23, wherein the static part of sparse index is never changed.
Claim 30
Dependent Claim
32 words
The article of manufacture of claim 23, wherein the static part of the sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.
Claim 31
Dependent Claim
19 words
The article of manufacture of claim 23, further comprising eliminating duplicate entries during the merge phase of file creation.
Claim 32
Dependent Claim
25 words
The article of manufacture of claim 23 above, further comprising creating a dynamic part of the sparse index during a search phase of file access.
Claim 33
Dependent Claim
19 words
The article of manufacture of claim 29, further comprising updating the dynamic part of the sparse index as required.
Claim 34
Dependent Claim
33 words
The article of manufacture of claim 23, further comprising determining an exact location of the data record in the file using an auxiliary search and the approximate location provided by the sparse index.
Claim 35
Dependent Claim
23 words
The article of manufacture of claim 23, wherein each entry in the sparse index comprises a key value and a record id (RID).
Claim 36
Dependent Claim
21 words
The article of manufacture of claim 32, wherein the RID provides a location of a data record matching the key value.
Claim 37
Dependent Claim
84 words
A data structure for use by a query performed by a database management system, comprising a hybrid sparse index stored in an electronic memory, wherein the hybrid sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of: (1) a static part that is built during a merge phase of file creation and is never changed, and (2) a dynamic part that is created during a search phase of file access.
Claim 38
Dependent Claim
84 words
A data structure for use by a query performed by a database management system, comprising a hybrid sparse index stored in an electronic memory, wherein the hybrid sparse index stores entries containing key values indicating only an approximate location of data records stored in an associated file and is comprised of: (1) a static part that is built during a merge phase of file creation and is never changed, and (2) a dynamic part that is created during a search phase of file access.
Claim 39
Dependent Claim
29 words
The data structure of claim 34, wherein the hybrid sparse index is probed to determine a starting location of a next search of a key value in the query.
Claim 40
Dependent Claim
28 words
The data structure of claim 34, wherein an entry is returned from the hybrid sparse index without performing the next search when the entry matches the key value.
Claim 41
Dependent Claim
34 words
The data structure of claim 34, wherein the next search is performed using a closest starting entry from the hybrid sparse index when no entry in the hybrid sparse index matches the key value.
Claim 42
Dependent Claim
24 words
The data structure of claim 37 above, wherein a new entry is inserted into the hybrid sparse index based on the next search results.
Claim 43
Dependent Claim
32 words
The data structure of claim 34, wherein the static part of the hybrid sparse index comprises a fixed number of the key values along with their record identifiers (RIDs) in a file.
Claim 44
Dependent Claim
18 words
The data structure of claim 34, wherein duplicate entries are eliminated during the merge phase of file creation.
Claim 45
Dependent Claim
18 words
The data structure of claim 34, wherein the dynamic part of the sparse index is updated as required.
Claim 46
Dependent Claim
33 words
The data structure of claim 34, wherein an exact location of the data record in the file is determined using an auxiliary search and the approximate location provided by the hybrid sparse index.
Claim 47
Dependent Claim
23 words
The data structure of claim 34, wherein each entry in the hybrid sparse index comprises a key value and a record id (RID).
Claim 48
Dependent Claim
20 words
The data structure of claim 34, wherein the RID provides a location of a data record matching the key value.
References Cited (Backward Citations)
US4606002A
Cited
US4817036A
Cited
US5386556A
Cited
US5197005A
Cited
US5369762A
Cited
US5261093A
Cited
US5315709A
Cited
US5550971A
Cited
US5560007A
Cited
US5664172A
Cited
JPH09206440A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-11-01 | 2003-05-03 | 2003-11-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-11-01 | 2007-05-03 | 2007-11-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-11-01 | 2011-05-03 | 2011-11-02 | $7700.00 | Window Closed / Lapsed |