Rejecting rows when scanning a collision chain

• US 8,903,831 B2
• Filed: 09/29/2011
• Issued: 12/02/2014
• 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): Leroux, Etienne
• Assistant Examiner(s): Glasser, Dara J
• Application Number:
  US13/248,800
• Publication Number:
  US 20130086073A1
• Time in Patent Office: 1,160 Days
• Field of Search: 707/747
• US Class Current: 707/747
• 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 rejecting rows while locating a target row. For a row that is stored in a hash space, a row filter value is generated for that row, and the row filter value is stored with the row. While trying to locate the target row in a collision chain in the hash space, a row filter value is calculated for the target row. For the row in the collision chain, the stored row filter value of the row in the collision chain is compared with the computed row filter value of the target row. In response to determining that the stored row filter value does not match the computed row filter value, it is determined that the row in the collision chain is not the target row.

Claims

1. A method, comprising:

computing a hash value using a hash key value for a target row and computing a row filter value for the target row, wherein the computed row filter value for the target row is a portion of the computed hash value;

in response to determining that the target row has overflowed, storing an overflow filter value for the target row in a page filter of a page, wherein the overflow filter value is the portion of the computed hash value; and

in response to determining that the computed row filter value matches a stored row filter value for a row in a collision chain and the hash key value matches a stored hash key value for the row in the collision chain, retrieving the row from the collision chain.

2. The method of claim 1, further comprising:

computing the hash value for the target row from one or more hash key values; and

identifying the collision chain within a page using the computed hash value for the target row.

3. The method of claim 1, further comprising:

in response to determining that the computed row filter value for the target row matches the stored row filter value for the row in the collision chain, decompressing the row.

4. The method of claim 1, wherein the hash key value for the target row is unique.

5. The method of claim 1, wherein the computed row filter value for the target row is an entire computed hash value.

6. The method of claim 1, wherein the computed row filter value for the target row is part of a pointer subrecord on a first page, and wherein the pointer subrecord stores a location of a second page storing row data for the target row that has been moved from the first page to the second page.

7. 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;

computing a hash value using a hash key value for a target row and computing a row filter value for the target row, wherein the computed row filter value for the target row is a portion of the computed hash value;

in response to determining that the target row has overflowed, storing an overflow filter value for the target row in a page filter of a page, wherein the overflow filter value is the portion of the computed hash value; and

in response to determining that the computed row filter value for the target row matches a stored row filter value for a row in a collision chain and the hash key value matches a stored hash key value for the row in the collision chain, retrieving the row from the collision chain.

8. The computer program product of claim 7, wherein the computer readable program code, when executed by the processor of the computer, is configured to perform:

computing the hash value for the target row from one or more hash key values; and

identifying the collision chain within a page using the computed hash value for the target row.

9. The computer program product of claim 7, wherein the computer readable program code, when executed by the processor of the computer, is configured to perform:

in response to determining that the computed row filter value for the target row matches the stored row filter value for the row in the collision chain, decompressing the row.

10. The computer program product of claim 7, wherein the hash key value for the target row is unique.

11. The computer program product of claim 7, wherein the computed row filter value for the target row is an entire computed hash value.

12. The computer program product of claim 7, wherein the computed row filter value for the target row is part of a pointer subrecord on a first page, and wherein the pointer subrecord stores a location of a second page storing row data for the target row that has been moved from the first page to the second page.

13. 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;

computing a hash value using a hash key value for a target row and computing a row filter value for the target row, wherein the computed row filter value for the target row is a portion of the computed hash value;

in response to determining that the target row has overflowed, storing an overflow filter value for the target row in a page filter of a page, wherein the overflow filter value is the portion of the computed hash value; and

in response to determining that the computed row filter value for the target row matches a stored row filter value for a row in a collision chain and the hash key value matches a stored hash key value for the row in the collision chain, retrieving the row from the collision chain.

14. The computer system of claim 13, wherein the operations further comprise:

computing the hash value for the target row from one or more hash key values; and

identifying the collision chain within a page using the computed hash value for the target row.

15. The computer system of claim 13, wherein the operations further comprise:

in response to determining that the computed row filter value for the target row matches the stored row filter value for the row in the collision chain, decompressing the row.

16. The computer system of claim 13, wherein the hash key value for the target row is unique.

17. The computer system of claim 13, wherein the computed row filter value for the target row is an entire computed hash value.

18. The computer system of claim 13, wherein the computed row filter value for the target row is part of a pointer subrecord on a first page, and wherein the pointer subrecord stores a location of a second page storing row data for the target row that has been moved from the first page to the second page.