Dynamically adjust duplicate skipping method for increased performance

Patent metadata

Field	Value
Publication number	US-9928274-B2
Application number	US-201414557010-A
Country	US
Kind code	B2
Filing date	Dec 1, 2014
Priority date	Jan 31, 2014
Publication date	Mar 27, 2018
Grant date	Mar 27, 2018

Abstract

Embodiments presented herein provide techniques for setting different methods of skipping duplicate values when executing a query statement in a relational database. A distance between a two distinct keys in an index, a current index key and a next distinct index key, are estimated. Based on the estimated distance, an appropriate duplicate-skipping method is determined. If the proximity between the distinct keys is relatively far apart (e.g., the keys reside in index pages that are at least an index page apart), then a “big skip” method is performed. Otherwise, if the proximity between the distinct keys is relatively near (e.g., the keys reside in the same index page), then a “little skip” method is performed.

First claim

What is claimed is:

1. A computer-implemented method to dynamically adjust a granularity with which to skip duplicate index keys in a database index when identifying records in a database that satisfy a database query, the computer-implemented method comprising:
estimating a first distance in the database index between a first index key and a next, distinct index key relative to the first index key
upon determining that the estimated first distance satisfies a first criterion, identifying a second index key by operation of one or more computer processors and by performing a coarser duplicate-skipping operation comprising a binary search from a root of a tree of the database index, the second index key comprising the next, distinct index key relative to the first index key;
estimating a second distance in the database index between the second index key and a next, distinct index key relative to the second index key; and
upon determining that the estimated second distance satisfies a second criterion, identifying a third index key by performing a finer duplicate-skipping operation comprising a binary search within a leaf page where the second index key resides, the third index key comprising the next, distinct index key relative to the second index key.

2. The computer-implemented method of claim 1 , wherein the first criterion comprises the first index key and its next index key residing in index leaf pages that is at least one index page apart, wherein the second criterion comprises the second index key and its next index key residing in the same index leaf page.

3. The computer-implemented method of claim 1 , further comprising:
performing a get-next operation in order to identify a fourth index key.

4. The computer-implemented method of claim 3 , further comprising:
disabling at least one of the coarser duplicate-skipping operation and the finer duplicate-skipping operation when, while executing the database query, the get-next operation is performed consecutively for a specified amount of times.

5. The computer-implemented method of claim 1 , further comprising:
inserting a database record corresponding to a given index key into a result set, wherein the given key is selected from the second and third index keys.

6. The computer-implemented method of claim 1 , wherein the granularity with which to skip duplicate index keys in the database index is dynamically adjusted in order to reduce a processing overhead associated with identifying the records in the database that satisfy the database query, wherein the computer-implemented method further comprises:
estimating a third distance in the database index between the third index key and a next, distinct index key relative to the third index key; and
upon determining that the estimated third distance satisfies a third criterion, identifying a fourth index key by performing a get-next operation, which does not skip any duplicates, the fourth index key comprising the next, distinct index key relative to the third index key, wherein the first, second, and third criteria are distinct.

7. The computer-implemented method of claim 6 , wherein estimating the first distance between the first index key and the next, distinct index key relative to the first index key comprises:
generating a search index key, wherein the search index key is given the highest value in the database index of the first index key; and
determining whether the first index key and the search index key are stored in the same index page.

8. The computer-implemented method of claim 7 , further comprising:
for each of the second, third, and fourth index keys, inserting a database record corresponding to the respective index key into a result set;
outputting the result set responsive to the database query; and
upon determining that the get-next operation is performed consecutively for a predefined number of times, automatically disabling at least one operation, selected from the coarser duplicate-skipping operation and the finer duplicate-skipping operation, from being performed.

9. The computer-implemented method of claim 8 , wherein the coarser duplicate-skipping operation is used to skip duplicate index keys only upon determining that the estimated first distance satisfies the first criterion, the first criterion comprising a current index key and a next index key residing in index leaf pages at least one index page apart;
wherein the finer duplicate-skipping operation is used to skip duplicate index keys only upon determining that the estimated second distance satisfies the second criterion, the second criterion comprising the current index key and the next index key residing in the same index leaf page.

10. The computer-implemented method of claim 9 , wherein the granularity with which to skip duplicate index keys in the database index is dynamically adjusted by a database management system for the database, wherein the coarser and finer duplicate-skipping operations and the get-next operation are performed by the database management system;
wherein the get-next operation is used to avoid skipping any duplicate index keys, only upon determining that the estimated third distance satisfies the third criterion, the third criterion being satisfied only upon satisfaction of both: (i) the leaf index page having below a threshold count of index keys; and (ii) the current index key being located near a higher bound of the leaf index page.

11. The computer-implemented method of claim 1 , wherein the granularity with which to skip duplicate index keys in the database index is dynamically adjusted in order to reduce a processing overhead associated with identifying the records in the database that satisfy the database query.

12. The computer-implemented method of claim 1 , further comprising:
estimating a third distance in the database index between the third index key and a next, distinct index key relative to the third index key.

13. The computer-implemented method of claim 12 , further comprising:
upon determining that the estimated third distance satisfies a third criterion, identifying a fourth index key by performing a get-next operation, which does not skip any duplicates, the fourth index key comprising the next, distinct index key relative to the third index key.

14. The computer-implemented method of claim 1 , wherein estimating the first distance between the first index key and the next, distinct index key relative to the first index key comprises:
generating a search index key, wherein the search index key is given the highest value in the database index of the first index key.

15. The computer-implemented method of claim 14 , wherein estimating the first distance between the first index key and the next, distinct index key relative to the first index key further comprises:
determining whether the first index key and the search index key are stored in the same index page.

16. The computer-implemented method of claim 1 , further comprising:
inserting a database record corresponding to a given index key into a result set, wherein the given key is selected from the second and third index keys.

17. The computer-implemented method of claim 1 , further comprising:
for each of the second and third index keys, inserting a database record corresponding to the respective index key into a result set.

18. The computer-implemented method of claim 17 , further comprising:
outputting the result set responsive to the database query.

19. The computer-implemented method of claim 1 , further comprising:
upo

Assignees

• IBM

Inventors

• Purcell Terence P
• Beavin Thomas A
• Xia Li
• Shadduck Michael R
• Desai Paramesh S
• Yu Qianyang

Classifications

• G06F16/2453 Primary

  Query optimisation · CPC title

• G06F16/2228

  Indexing structures · CPC title

• G06F16/2272

  Management thereof · CPC title

• G06F16/22

  Indexing; Data structures therefor; Storage structures · CPC title

• G06F17/30336

  Physics · mapped topic