Probing a hash table using vectorized instructions

Patent metadata

Field	Value
Publication number	US-9659046-B2
Application number	US-201313956350-A
Country	US
Kind code	B2
Filing date	Jul 31, 2013
Priority date	Jul 31, 2013
Publication date	May 23, 2017
Grant date	May 23, 2017

Abstract

Techniques for performing database operations using vectorized instructions are provided. In one technique, a hash table probe phase involves executing vectorized instructions to determine where in a bucket a particular key is located. This determination may be preceded by one or more vectorized instructions that are used to determine whether the bucket contains the particular key.

First claim

What is claimed is:

1. A method comprising:
while executing a join operation, probing a hash table based on keys from a second relation that is different than a first relation upon which the hash table is based;
wherein probing the hash table comprises:
identifying a first key from the second relation;
generating a hash value based on the first key;
identifying, based on the hash value, in the hash table, a bucket that contains a plurality of keys;
loading the plurality of keys into a first register;
determining whether the first key matches a key in the plurality of keys;
in response to determining that the first key matches a particular key in the plurality of keys, using one or more vectorized instructions to determine a position, within the bucket, where the particular key is located;

wherein the one or more vectorized instructions includes:
(a) a minimum position instruction that, when executed against a second register that contains a plurality of values, generates output that indicates a position, within the second register, that contains a minimum value of the plurality of values, or
(b) a maximum position instruction that, when executed against the second register that contains the plurality of values, generates output that indicates a position, within the second register, that contains a maximum value of the plurality of values;

wherein the method is performed by one or more computing devices.

2. The method of claim 1 , wherein probing the hash table further comprises identifying, based on the position, within the bucket, a data value that corresponds to the particular key.

3. The method of claim 1 , wherein:
using the one or more vectorized instructions comprises using a vectorized instruction to extract a position value from a third register;
the position within the bucket is based on the position value.

4. The method of claim 1 , wherein:
the one or more vectorized instructions includes the minimum position instruction that, when executed against the second register that contains the plurality of values, generates output that indicates the position, within the second register, that contains the minimum value of the plurality of values.

5. A method comprising:
while executing a join operation, probing a hash table based on keys from a second relation that is different than a first relation upon which the hash table is based;
wherein probing the hash table comprises:
identifying a first key from the second relation;
generating a hash value based on the first key;
identifying, based on the hash value, in the hash table, a bucket that contains a plurality of keys;
loading the plurality of keys into a first register;
determining whether the first key matches a key in the plurality of keys;
in response to determining that the first key matches a particular key in the plurality of keys, using one or more vectorized instructions to determine a position, within the bucket, where the particular key is located;

wherein the one or more vectorized instructions includes an instruction that, when executed against a second register that contains a plurality of values and a third register that contains all one bits or zero bits, generates output that contains, for each value of the plurality of values, a value that is opposite of said each value.

6. The method of claim 5 , wherein the one or more vectorized instructions includes a compare instruction that, when executed against a fourth register that contains multiple copies of the first key, generates output that is stored in the third register.

7. The method of claim 1 , wherein probing the hash table further comprises:
identifying a second key from the second relation;
generating a second hash value based on the second key;
identifying, based on the second hash value in the hash table, a second bucket that contains a second plurality of keys;
loading the second plurality of keys into a third register that is capable of storing multiple data elements;
determining whether the second key matches a key in the second plurality of keys;
in response to determining that the second key does not match any key in the second plurality of keys:
generating a third hash value based on the second key;
identifying, based on the third hash value in the hash table, a third bucket that contains a third plurality of keys that are different than the second plurality of keys;
loading the third plurality of keys into a fourth register;
determining whether the second key matches a key in the third plurality of keys.

8. The method of claim 7 , wherein probing the hash table further comprises:
in response to determining that the second key does not match any key in the third plurality of keys, determining whether the second key is found in a second data structure that is different than the hash table.

9. The method of claim 1 , wherein determining whether the first key matches a key in the plurality of keys is performed using one or more second vectorized instructions.

10. The method of claim 9 , wherein:
the one or more second vectorized instructions includes a compare instruction;
determining whether the first key matches a key in the plurality of keys comprises:
causing a third register that is different than the first register to contain multiple copies of the first key;
using the compare instruction to compare contents of the first register with contents of the third register.

11. One or more non-transitory storage media storing instructions which, when executed by one or more processors, cause:
while executing a join operation, probing a hash table based on keys from a second relation that is different than a first relation upon which the hash table is based;
wherein probing the hash table comprises:
identifying a first key from the second relation;
generating a hash value based on the first key;
identifying, based on the hash value, in the hash table, a bucket that contains a plurality of keys;
loading the plurality of keys into a first register;
determining whether the first key matches a key in the plurality of keys;
in response to determining that the first key matches a particular key in the plurality of keys, using one or more vectorized instructions to determine a position, within the bucket, where the particular key is located;

wherein the one or more vectorized instructions includes:
(a) a minimum position instruction that, when executed against a second register that contains a plurality of values, generates output that indicates a position, within the second register, that contains a minimum value of the plurality of values, or
(b) a maximum position instruction that, when executed against the second register that contains the plurality of values, generates output that indicates a position, within the second register, that contains a maximum value of the plurality of values.

12. The one or more storage media of claim 11 , wherein probing the hash table further comprises identifying, based on the position, within the bucket, a data value that corresponds to the particular key.

13. The one or more storage media of claim 11 , wherein:
using the one or more vectorized instructions comprises using a vectorized instruction to extract a position value from a third register;
the position within the bucket is based on the position value.

14. The one or more storage media of claim 11 , wherein:
the one or more vectorized instructions includes the minimum position instruction that, when executed against the second register that contains the plurality of values, generates output that indicates the position, within the seco

Assignees

• Oracle Int Corp
• Oracle Inernational Corp

Inventors

• Sen Rajkumar
• Petride Sabina
• Agarwal Nipun

Classifications

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F17/3033 Primary

  Physics · mapped topic