Rejecting rows when scanning a collision chain that is associated with a page filter

• US 9,361,307 B2
• Filed: 11/05/2014
• Issued: 06/07/2016
• Est. Priority Date: 09/29/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lyle, Robert W.
• Primary Examiner(s): Mofiz, Apu
• Assistant Examiner(s): Glasser, Dara J
• Application Number:
  US14/533,929
• Publication Number:
  US 20150058356A1
• Time in Patent Office: 580 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/137 Hash-based content-based indexing of textual data G06F16/31
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/24553 of query operations

Abstract

Provided are techniques for locating a row. A page filter in a page is stored, wherein the page filter is associated with a collision chain and includes a portion of a hash value of the row in the collision chain that has overflowed to an overflow area. In response to a request to locate a target row, the page filter is used to determine that the row has overflowed based on a portion of a hash value of the target row matching the portion of the hash value of the row that has overflowed.

Claims

1. A method, comprising:

storing, using a processor of a computer, a page filter in a page, wherein the page filter is associated with a collision chain and includes a portion of a hash value of a row in the collision chain that has overflowed to an overflow area;

dynamically adjusting the page filter to store different portions of the hash value for the overflowed row as a number of overflowed rows increases; and

in response to a request to locate a target row, using the page filter to determine that the row has overflowed based on a portion of a hash value of the target row matching the portion of the hash value of the row that has overflowed.

2. The method of claim 1, wherein the page filter comprises entries, and

wherein each of the entries stores an overflow filter.

3. The method of claim 2, wherein a size of the entries changes dynamically as more overflows occur.

4. The method of claim 1, wherein the page filter comprises an array of n-indicators, wherein each of the n-indicators comprises an overflow filter, and wherein each of the n-indicators is associated with a particular hash value.

5. The method of claim 1, wherein each of different collision chains has a different, associated page filter.

6. A computer program product, comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code, when executed by a processor of a computer, configured to perform;

storing a page filter in a page, wherein the page filter is associated with a collision chain and includes a portion of a hash value of a row in the collision chain that has overflowed to an overflow area;

dynamically adjusting the page filter to store different portions of the hash value for the overflowed row as a number of overflowed rows increases; and

in response to a request to locate a target row, using the page filter to determine that the row has overflowed based on a portion of a hash value of the target row matching the portion of the hash value of the row that has overflowed.

7. The computer program product of claim 6, wherein the page filter comprises entries, and wherein each of the entries stores an overflow filter.

8. The computer program product of claim 7, wherein a size of the entries changes dynamically as more overflows occur.

9. The computer program product of claim 6, wherein the page filter comprises an array of n-indicators, wherein each of the n-indicators comprises an overflow filter, and wherein each of the n-indicators is associated with a particular hash value.

10. The computer program product of claim 6, wherein each of different collision chains has a different, associated page filter.

11. A computer system, comprising:

a processor; and

a storage device coupled to the processor, wherein the storage device has stored thereon a program, and wherein the processor is configured to execute instructions of the program to perform operations, wherein the operations comprise;

storing a page filter in a page, wherein the page filter is associated with a collision chain and includes a portion of a hash value of a row in the collision chain that has overflowed to an overflow area;

dynamically adjusting the page filter to store different portions of the hash value for the overflowed row as a number of overflowed rows increases; and

in response to a request to locate a target row, using the page filter to determine that the row has overflowed based on a portion of a hash value of the target row matching the portion of the hash value of the row that has overflowed.

12. The computer system of claim 11, wherein the page filter comprises entries, and wherein each of the entries stores an overflow filter.

13. The computer system of claim 12, wherein a size of the entries changes dynamically as more overflows occur.

14. The computer system of claim 11, wherein the page filter comprises an array of n-indicators, wherein each of the n-indicators comprises an overflow filter, and wherein each of the n-indicators is associated with a particular hash value.

15. The computer system of claim 11, wherein each of different collision chains has a different, associated page filter.