Tiered index management

Patent metadata

Field	Value
Publication number	US-10061792-B2
Application number	US-201314145453-A
Country	US
Kind code	B2
Filing date	Dec 31, 2013
Priority date	Dec 31, 2013
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

Abstract

Disclosed herein are methods for retrieving data from a database. An embodiment operates searching for a key in a first index. The method determines that the searching will require a storage access request and issues the storage access request. The method continues searching for the key in a second index.

First claim

What is claimed is:

1. A computer implemented method for retrieving data from a database, comprising:
receiving, by at least one processor, an insert load, wherein the insert load comprises a first key and a second key;
performing, by the at least one processor, a first traversal of a sub-index of a tier of a tiered index to find the first key in an entry of the sub-index, wherein the tiered index comprises a plurality of tiers;
dynamically tuning, by the at least one processor, sizing parameters of at least one tier of the plurality of tiers, in response to learning, by the at least one processor, usage patterns of the at least one tier of the plurality of tiers, wherein the dynamically tuning the sizing parameters of the at least one tier of the plurality of tiers comprises limiting a size of the at least one tier of the plurality of tiers to fit entirely in prefetch memory, wherein the limiting the size of the at least one tier of the plurality of tiers to fit entirely in the prefetch memory comprises moving at least one data entry to a lower tier of the plurality of tiers upon determining that a condition has been met;
determining, by the at least one processor, that the first traversal requires a storage access request, wherein the determining comprises:
issuing, by the at least one processor, the storage access request,
caching, by the at least one processor, the first key, and

performing, by the at least one processor, a second traversal of the sub-index to find the second key before the storage access request has been completed;
comparing, by the at least one processor, a number of keys searched to a threshold value, wherein the number of keys searched depends at least in part on the dynamically tuning the sizing parameters of the at least one tier of the plurality of tiers;
updating, by the at least one processor, a distinct key count when the storage access request has been completed, wherein the distinct key count represents a number of distinct keys within a data structure; and
selecting, by the at least one processor, a query plan to execute a query based upon the distinct key count.

2. The method of claim 1 , further comprising:
returning to search for the first key in the sub-index after the storage access request has completed.

3. The method of claim 2 , further comprising merging results of the search from multiple sub-indices of the tiered index after the storage access request has completed.

4. The method of claim 1 , wherein the tiered index comprises a group of sub-indices.

5. The method of claim 4 , wherein the group of sub-indices comprises a plurality of tiers of the tiered index.

6. The method of claim 4 , further comprising:
determining, by the at least one processor, that all sub-indices in the group of sub-indices have been searched.

7. The method of claim 1 , further comprising:
executing, by at least one processor, the selected query plan.

8. The method of claim 1 , wherein the condition comprises at least one of whether a predetermined period of time has lapsed and whether a predetermined number of data inserts has been reached.

9. A computer implemented method for retrieving data from a database, comprising:
traversing, by at least one processor, a tree of a tiered index in a top-down direction to find a first key, wherein the tiered index comprises a plurality of tiers;
determining, by the at least one processor, that the first key has been found in a first tree node, wherein determining that the first key has been found in the first tree node comprises storing a position of the first tree node;
dynamically tuning, by the at least one processor, sizing parameters of at least one tier of the plurality of tiers, in response to learning, by the at least one processor, usage patterns of the at least one tier of the plurality of tiers, wherein the dynamically tuning the sizing parameters of the at least one tier of the plurality of tiers comprises limiting a size of the at least one tier of the plurality of tiers to fit entirely in prefetch memory, wherein the limiting the size of the at least one tier of the plurality of tiers to fit entirely in the prefetch memory comprises moving at least one data entry to a lower tier of the plurality of tiers upon determining that a condition has been met;
updating, by the at least one processor, a distinct key count when the first key has been found, wherein the distinct key count represents a number of distinct keys within the tree;
traversing, by the at least one processor, the tree in a bottom-up direction to find a second key starting at the position of the first tree node;
selecting, by the at least one processor, a query plan to execute a query based upon the distinct key count; and
executing, by the at least one processor, the selected query plan.

10. The method of claim 9 , the traversing the tree in the bottom-up direction further comprising:
comparing the second key with a current key in a current node, the current node being the node where the first key was found.

11. The method of claim 10 , further comprising:
performing a next comparison of the second key with a next key as a result of the second key being greater than the current key.

12. The method of claim 11 , further comprising:
performing a last comparison of the second key with a last key as a result of the second key being greater than the next key.

13. The method of claim 10 , the traversing the tree in the bottom-up direction further comprising:
performing a binary search for the second key in a set of remaining keys in the current node, the remaining keys being keys between a next key and a last key, as a result of the second key not being equal to the last key.

14. The method of claim 13 , the performing the search for the second key further comprising performing a traversal of at least one conjugate tree before probing a main tree of the sub-index.

15. The method of claim 13 , the traversing the tree in the bottom-up direction further comprising:
traversing the tree in the bottom-up direction from a parent node to the current node, as a result of the second key not being found in the remaining keys.

16. The method of claim 10 , further comprising:
performing a next comparison of the second key with a next key, the next key being adjacent to the current key in the current node, as a result of the second key not being equal to the current key.

17. The method of claim 16 , further comprising:
performing a next comparison of the second key with a last key, the last key being in a last position of the current node, as a result of the second key not being equal to the next key.

18. The method of claim 9 , wherein the condition comprises at least one of whether a predetermined period of time has lapsed and whether a predetermined number of data inserts has been reached.

Assignees

• Agarwal Anant
• Kirk Steven A
• French Blaine
• Marathe Nandan
• Mungikar Shailesh
• Mittal Kaushal
• Sybase Inc

Inventors

• Agarwal Anant
• Kirk Steven A
• French Blaine
• Marathe Nandan
• Mungikar Shailesh
• Mittal Kaushal

Classifications

• G06F17/30327

  Physics · mapped topic

• G06F17/30336 Primary

  Physics · mapped topic

• G06F16/2246

  Trees, e.g. B+trees · CPC title

• G06F16/2272 Primary

  Management thereof · CPC title