US6647386B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method, system, and program for reverse index scanning
Assignee: Google LLC
•
Filing: 2000-12-14
•
Granted: 2003-11-11
•
Expires: 2020-12-14
Abstract
Abstract Provided is a system, method, and program for performing a reverse scan of an index implemented as a tree of pages. Each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively. The scan is searching for keys in the leaf pages that satisfy the search criteria. If a current index key is a first key on a current page, then a request is made for a conditional shared latch on a previous page prior to the current page. If the requested conditional shared latch is not granted, then the latch on the current page is released and a request is made for unconditional latches on the previous page and the current page. After receiving the latches on the previous and current pages, a determination is made of whether the current index key is on the current page if the current page was modified since the unconditional latch was requested. The current index key is located on the current page if the current index key is on the current page. A determination is then made of whether the located current index key satisfies the search criteria.
Inventors
- 👤 Robert J. Hollines, III
- 👤 Christina Marie Lee
- 👤 David L. Levish
- 👤 Michael R. Shadduck
- 👤 Yufen Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-08 18:41
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/22; G06F16/2228; G06F16/2246; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99933; Y10S707/99938
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
186 words
A method for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, and wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, comprising: if a current index key is a first key on a current page, then requesting a conditional shared latch on a previous page prior to the current page; if the requested conditional shared latch is not granted, then releasing the latch on the current page and requesting unconditional latches on the previous page and the current page; after receiving the latch on the previous and current pages in response to requesting the unconditional latches, then determining whether the current index key is on the current page if the current page was modified since the unconditional latch was requested; locating the current index key on the current page if the current index key is on the current page; and determining whether the located current index key satisfies the search criteria.
Claim 2
Independent Claim
186 words
A method for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, and wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, comprising: if a current index key is a first key on a current page, then requesting a conditional shared latch on a previous page prior to the current page; if the requested conditional shared latch is not granted, then releasing the latch on the current page and requesting unconditional latches on the previous page and the current page; after receiving the latch on the previous and current pages in response to requesting the unconditional latches, then determining whether the current index key is on the current page if the current page was modified since the unconditional latch was requested; locating the current index key on the current page if the current index key is on the current page; and determining whether the located current index key satisfies the search criteria.
Claim 3
Dependent Claim
59 words
The method of claim 1 , wherein each key is associated with a location identifier of a record in a database table the key represents, further comprising: determining whether each accessed key satisfies a search criteria; and returning the location identifier associated with each key that satisfies the search criteria when reverse scanning through the pages of the index.
Claim 4
Dependent Claim
74 words
The method of claim 1 , further comprising: if the requested shared latch on the previous page is returned in response to the request for the conditional shared latch, then performing: (i) accessing the previous page prior to the current page; (ii) accessing a last key on the previous page, wherein the accessed previous page becomes the current page and the accessed last key becomes the current key in continuing the reverse index scan.
Claim 5
Dependent Claim
59 words
The method of claim 1 , if the current index key is not the first key on the current page, then after determining whether the current index key satisfies the search criteria, accessing the key prior to the current key on the current page, wherein the accessed prior key becomes the current key in continuing the reverse index scan.
Claim 6
Dependent Claim
71 words
The method of claim 1 , further comprising: determining whether the previous page was involved in a structural modification if the current page was not modified; and if the previous page was not involved in a structural modification, then accessing a last key on the previous page, wherein the accessed previous page becomes the current page and the accessed Last key becomes the current key in continuing the reverse index scan.
Claim 7
Dependent Claim
108 words
The method of claim 5 , further comprising: after the shared latch is not returned in response to the conditional shared latch and before requesting the unconditional shared latches on the current page and the previous page, saving a sequence number for the current page and page numbers of the current page and previous page, wherein determining whether the current page was modified comprises determining whether the sequence number for the current page has changed, and wherein determining whether the previous page was involved in a structural modification comprises determining whether the next pointer for the previous page points to the saved page number of the current page.
Claim 8
Dependent Claim
75 words
The method of claim 5 , further comprising: if the previous page was involved in a structural modification, then saving the current index key and requesting a tree latch to prevent another process from structurally modifying pages in the tree; after receiving the tree latch, determining a prior non-leaf page that includes the saved current index key; and traversing forward from the determined non-leaf node to a leaf page including the saved current index key.
Claim 9
Dependent Claim
79 words
The method of claim 7 , further comprising: when initially traversing the tree to access the current page, saving in a page stack information on the non-leaf pages traversed including key bounds of the non-leaf pages, wherein a relationship of the non-leaf pages can be determined from the page stack, and wherein determining the prior non-leaf node that includes the current index key comprises using the page stack to determine a closest non-leaf page including the saved current index.
Claim 10
Dependent Claim
43 words
The method of claim 7 , further comprising: after traversing forward to the leaf page including the current index page, accessing a previous key in the leaf page or a previous leaf page; and releasing the tree latch after accessing the previous key.
Claim 11
Dependent Claim
37 words
The method of claim 1 , wherein the tree comprises a B-tree with one or more levels of non-leaf pages that include keys and pointers to a path to one or more leaf pages including the keys.
Claim 12
Dependent Claim
25 words
The method of claim 1 , wherein the unconditional latch on the current page is requested after receiving the unconditional latch on the previous page.
Claim 13
Independent Claim
194 words
A system for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, and wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, comprising: means for requesting a conditional shared latch on a previous page prior to the current page if a current index key is a first key on a current page; means for releasing the latch on the current page and requesting unconditional latches on the previous page and the current page if the requested conditional shared latch is not granted; means for determining whether the current index key is on the current page after receiving the latch on the previous and current pages in response to requesting the unconditional latches and if the current page was modified since the unconditional latch was requested; means for locating the current index key on the current page if the current index key is on the current page; and means for determining whether the located current index key satisfies the search criteria.
Claim 14
Independent Claim
194 words
A system for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, and wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, comprising: means for requesting a conditional shared latch on a previous page prior to the current page if a current index key is a first key on a current page; means for releasing the latch on the current page and requesting unconditional latches on the previous page and the current page if the requested conditional shared latch is not granted; means for determining whether the current index key is on the current page after receiving the latch on the previous and current pages in response to requesting the unconditional latches and if the current page was modified since the unconditional latch was requested; means for locating the current index key on the current page if the current index key is on the current page; and means for determining whether the located current index key satisfies the search criteria.
Claim 15
Dependent Claim
63 words
The system of claim 12 , wherein each key is associated with a location identifier of a record in a database table the key represents, further comprising: means for determining whether each accessed key satisfies a search criteria; and means for returning the location identifier associated with each key that satisfies the search criteria when reverse scanning through the pages of the index.
Claim 16
Dependent Claim
78 words
The system of claim 12 , further comprising: means for performing the following steps when the requested shared latch on the previous page is returned in response to the request for the conditional shared latch; (i) accessing the previous page prior to the current page; (ii) accessing a last key on the previous page, wherein the accessed previous page becomes the current page and the accessed last key becomes the current key in continuing the reverse index scan.
Claim 17
Dependent Claim
63 words
The system of claim 12 , further comprising: means for accessing the key prior to the current key on the current page after determining whether the current index key satisfies the search criteria and if the current index key is not the first key on the current page, wherein the accessed prior key becomes the current key in continuing the reverse index scan.
Claim 18
Dependent Claim
74 words
The system of claim 12 , further comprising: means for determining whether the previous page was involved in a structural modification if the current page was not modified; and means for accessing a last key on the previous page if the previous page was not involved in a structural modification, wherein the accessed previous page becomes the current page and the accessed last key becomes the current key in continuing the reverse index scan.
Claim 19
Dependent Claim
116 words
The system of claim 16 , further comprising: means for saving a sequence number for the current page and page numbers of the current page and previous page after the shared latch is not returned in response to the conditional shared latch and before requesting the unconditional shared latches on the current page and the previous page, wherein the means for determining whether the current page was modified comprises determining whether the sequence number for the current page has changed, and wherein the means for determining whether the previous page was involved in a structural modification comprises determining whether the next pointer for the previous page points to the saved page number of the current page.
Claim 20
Dependent Claim
79 words
The system of claim 16 further comprising: means for saving the current index key and requesting a tree latch to prevent another process from structurally modifying pages in the tree if the previous page was involved in a structural modification; means for determining a prior non-leaf page that includes the saved current index key after receiving the tree latch; and means for traversing forward from the determined non-leaf node to a leaf page including the saved current index key.
Claim 21
Dependent Claim
84 words
The system of claim 18 , further comprising: means for saving in a page stack information on the non-leaf pages traversed including key bounds of the non-leaf pages when initially traversing the tree to access the current page, wherein a relationship of the non-leaf pages can be determined from the page stack, and wherein the means for determining the prior non-leaf node that includes the current index key comprises using the page stack to determine a closest non-leaf page including the saved current index.
Claim 22
Dependent Claim
47 words
The system of claim 18 , further comprising: means for accessing a previous key in the leaf page or a previous leaf page after traversing forward to the leaf page including the current index page; and means for releasing the tree latch after accessing the previous key.
Claim 23
Dependent Claim
37 words
The system of claim 12 , wherein the tree comprises a B-tree with one or more levels of non-leaf pages that include keys and pointers to a path to one or more leaf pages including the keys.
Claim 24
Dependent Claim
25 words
The system of claim 12 , wherein the unconditional latch on the current page is requested after receiving the unconditional latch on the previous page.
Claim 25
Dependent Claim
207 words
A program for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, wherein the program comprises code implemented in a computer readable medium, wherein the program code is capable of causing a processor to perform: if a current index key is a first key on a current page, then requesting a conditional shared latch on a previous page prior to the current page; if the requested conditional shared latch is not granted, then releasing the latch on the current page and requesting unconditional latches on the previous page and the current page; after receiving the latch on the previous and current pages in response to requesting the unconditional latches, then determining whether the current index key is on the current page if the current page was modified since the unconditional latch was requested; locating the current index key on the current page if the current index key is on the current page; and determining whether the located current index key satisfies the search criteria.
Claim 26
Dependent Claim
207 words
A program for performing a reverse scan of an index implemented as a tree of pages, wherein each leaf page includes one or more ordered index keys and previous and next pointers to the previous and next pages, respectively, wherein the scan is searching for keys in the leaf pages that satisfy the search criteria, wherein the program comprises code implemented in a computer readable medium, wherein the program code is capable of causing a processor to perform: if a current index key is a first key on a current page, then requesting a conditional shared latch on a previous page prior to the current page; if the requested conditional shared latch is not granted, then releasing the latch on the current page and requesting unconditional latches on the previous page and the current page; after receiving the latch on the previous and current pages in response to requesting the unconditional latches, then determining whether the current index key is on the current page if the current page was modified since the unconditional latch was requested; locating the current index key on the current page if the current index key is on the current page; and determining whether the located current index key satisfies the search criteria.
Claim 27
Dependent Claim
70 words
The program of claim 23 , wherein each key is associated with a location identifier of a record in a database table the key represents, wherein the program code is further capable of causing the processor to perform: determining whether each accessed key satisfies a search criteria; and returning the location identifier associated with each key that satisfies the search criteria when reverse scanning through the pages of the index.
Claim 28
Dependent Claim
85 words
The program of claim 23 , wherein the program code is further capable of causing the processor to perform: if the requested shared latch on the previous page is returned in response to the request for the conditional shared latch, then performing: (i) accessing the previous page prior to the current page; (ii) accessing a last key on the previous page, wherein the accessed previous page becomes the current page and the accessed last key becomes the current key in continuing the reverse index scan.
Claim 29
Dependent Claim
72 words
The program of claim 23 , wherein the program code is further capable of causing the processor to perform: if the current index key is not the first key on the current page, then after determining whether the current index key satisfies the search criteria, accessing the key prior to the current key on the current page, wherein the accessed prior key becomes the current key in continuing the reverse index scan.
Claim 30
Dependent Claim
82 words
The program of claim 23 , wherein the program code is further capable of causing the processor to perform: determining whether the previous page was involved in a structural modification if the current page was not modified; and if the previous page was not involved in a structural modification, then accessing a last key on the previous page, wherein the accessed previous page becomes the current page and the accessed last key becomes the current key in continuing the reverse index scan.
Claim 31
Dependent Claim
119 words
The program of claim 27 , wherein the program code is further capable of causing the processor to perform: after the shared latch is not returned in response to the conditional shared latch and before requesting the unconditional shared latches on the current page and the previous page, saving a sequence number for the current page and page numbers of the current page and previous page, wherein determining whether the current page was modified comprises determining whether the sequence number for the current page has changed, and wherein determining whether the previous page was involved in a structural modification comprises determining whether the next pointer for the previous page points to the saved page number of the current page.
Claim 32
Dependent Claim
86 words
The program of claim 27 , wherein the program code is further capable of causing the processor to perform: if the previous page was involved in a structural modification, then saving the current index key and requesting a tree latch to prevent another process from structurally modifying pages in the tree; after receiving the tree latch, determining a prior non-leaf page that includes the saved current index key; and traversing forward from the determined non-leaf node to a leaf page including the saved current index key.
Claim 33
Dependent Claim
54 words
The program of claim 29 , wherein the program code is further capable of causing the processor to perform: after traversing forward to the leaf page including the current index page, accessing a previous key in the leaf page or a previous leaf page; and releasing the tree latch after accessing the previous key.
Claim 34
Dependent Claim
90 words
The program of claim 23 , wherein the program code is further capable of causing the processor to perform: when initially traversing the tree to access the current page, saving in a page stack information on the non-leaf pages traversed including key bounds of the non-leaf pages, wherein a relationship of the non-leaf pages can be determined from the page stack, and wherein determining the prior non-leaf node that includes the current index key comprises using the page stack to determine a closest non-leaf page including the saved current index.
Claim 35
Dependent Claim
37 words
The program of claim 23 , wherein the tree comprises a B-tree with one or more levels of non-leaf pages that include keys and pointers to a path to one or more leaf pages including the keys.
Claim 36
Dependent Claim
25 words
The program of claim 23 , wherein the unconditional latch on the current page is requested after receiving the unconditional latch on the previous page.
References Cited (Backward Citations)
US5123104A
Cited
US5594899A
Cited
US5574902A
Cited
US5758146A
Cited
US5717918A
Cited
US5826253A
Cited
US5918224A
Cited
US5717919A
Cited
US5835904A
Cited
US5832484A
Cited
US6363387B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2006-11-10 | 2007-05-12 | 2007-11-11 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2010-11-10 | 2011-05-12 | 2011-11-11 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2014-11-10 | 2015-05-12 | 2015-11-11 | $7700.00 | Window Closed / Lapsed |