Building a hash table using vectorized instructions

Patent metadata

Field	Value
Publication number	US-9256631-B2
Application number	US-201313956343-A
Country	US
Kind code	B2
Filing date	Jul 31, 2013
Priority date	Jul 31, 2013
Publication date	Feb 9, 2016
Grant date	Feb 9, 2016

Abstract

Techniques for performing database operations using vectorized instructions are provided. In one technique, a hash table build phase involves executing vectorized instructions to determine whether a bucket in a hash table includes a free slot for inserting a key. A number of data elements from the bucket are loaded in a register. A vectorized instruction is executed against the register may be used to determine a position, within the register, that contains the “smallest” data element. If the data element at that position is zero (or negative), then it is determined that the corresponding position in the bucket is an available slot for inserting a key and corresponding data value.

First claim

What is claimed is:

1. A method comprising:
in response to receiving a database operation, generating a hash table based on a relation;
wherein generating the hash table comprises:
identifying a key and a data value to insert into the hash table, wherein the key and data value are from the relation;
generating a hash value based on the key;
identifying, based on the hash value, a bucket in the hash table, wherein the bucket includes a plurality of slots;
loading, from the bucket, into a first register, a first plurality of data elements;
causing, to be executed against the first register, one or more vectorized instructions to determine whether the bucket includes a slot, of the plurality of slots, that is available for inserting the key and the data value, wherein a vectorized instruction, of the one or more vectorized instructions, when executed, causes a single operation to be performed on the first plurality of data elements in the first register;
in response to determining that the bucket includes a slot that is available, inserting the key and the data value into the slot of the bucket in the hash table;

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

2. The method of claim 1 , wherein:
the one or more vectorized instructions includes a value instruction;
causing the one or more vectorized instructions to be executed comprises:
causing, to be executed against a second register, the value instruction that causes a first particular data element of a second plurality of data elements, that correspond to the first plurality of data elements, to be determined;
determining whether the first particular data element is a particular value;

determining that the bucket includes a slot that is available comprises determining that the first particular data element is the particular value.

3. The method of claim 2 , wherein:
the particular value is zero;
the value instruction, when executed, causes the minimum value in the second register to be determined.

4. The method of claim 3 , wherein:
the one or more vectorized instructions includes an extract instruction;
generating the hash table further comprises, after causing the value instruction to be executed and prior to determining whether the first particular data element is the particular value:
causing, to be executed against a third register, the extract instruction that causes the minimum value to be extracted.

5. The method of claim 3 , wherein the value instruction, when executed, further causes a position of the minimum value in the second register to be determined.

6. The method of claim 5 , wherein the slot that is available within the bucket is determined based on the position of the minimum value.

7. The method of claim 1 , wherein:
the one or more vectorized instructions includes a shuffle instruction;
causing the one or more vectorized instructions to be executed comprises causing the shuffle instruction to be executed;
the shuffle instruction takes, as input, the first plurality of data elements in the first register and contents of a mask register;
causing the shuffle instruction to be executed causes shuffled content to be generated.

8. The method of claim 7 , wherein:
the one or more vectorized instructions includes an add instruction;
generating the hash table further comprises causing the add instruction to be executed, wherein the add instruction takes, as input, the first plurality of data elements and the shuffled content;
causing the add instruction to be executed causes modified content to be generated;
determining whether the bucket includes a slot that is available is based on the modified content.

9. The method of claim 7 , wherein determining whether the bucket includes a slot that is available is based on the shuffled content.

10. The method of claim 1 , wherein generating the hash table comprises:
identifying a second key and a second data value to insert into the hash table, wherein the second key and the second data value are from the relation;
generating a second hash value based on the second key;
identifying, based on the second hash value, a second bucket in the hash table;
loading, from the second bucket, into a second register that is capable of storing multiple data elements, a second plurality of data elements, each of which corresponds to a different key of a second plurality of keys;
causing, to be executed against the second register, the one or more vectorized instructions to determine whether the second bucket includes a slot that is available;
in response to determining that the second bucket does not include a slot that is available:
identifying, in the hash table, based on a third hash value that is based on the second key and that is different than the second hash value, a third bucket that is different than the second bucket;
loading, from the third bucket, into a third register that is capable of storing multiple data elements, a third plurality of data elements, each of which corresponds to a different key of a third plurality of keys;
causing, to be executed against the third register, the one or more vectorized instructions to determine whether the third bucket includes a slot that is available.

11. The method of claim 10 , wherein generating the hash table further comprises:
performing a plurality of evictions, each of which comprises evicting a data element that is located in the same relative position within a bucket.

12. The method of claim 11 , wherein performing an eviction further comprises:
shifting each non-evicted data element in the bucket one slot position.

13. The method of claim 11 , wherein evicting a particular data element from the third bucket comprises:
identifying a particular key that corresponds to the particular data element;
determining that a fourth bucket that is identified based on a fourth hash value that is based on the particular key does not include a slot that is available;
storing the particular key and the particular data element in an auxiliary data structure that is different than the hash table.

14. One or more storage media storing instructions which, when executed by one or more processors cause:
in response to receiving a database operation, generating a hash table based on a relation;
wherein generating the hash table comprises:
identifying a key and a data value to insert into the hash table, wherein the key and data value are from the relation;
generating a hash value based on the key;
identifying, based on the hash value, a bucket in the hash table, wherein the bucket includes a plurality of slots;
loading, from the bucket, into a first register, a first plurality of data elements;
causing, to be executed against the first register, one or more vectorized instructions to determine whether the bucket includes a slot, of the plurality of slots, that is available for inserting the key and the data value, wherein a vectorized instruction, of the one or more vectorized instructions, when executed, causes a single operation to be performed on the first plurality of data elements in the first register;
in response to determining that the bucket includes a slot that is available, inserting the key and the data value into the slot of the bucket in the hash table.

15. The one or more storage media of claim 14 , wherein:
the one or more vectorized instructions includes a value instruction;
causing the one or more vectorized instructions to be executed comprises:
causing, to be executed against a second register, the value instruction that causes a first particular data element of a se

Assignees

• Oracle Int Corp

Inventors

• Sen Rajkumar
• Agarwal Nipun

Classifications

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F16/24544

  Join order optimisation · CPC title

• G06F9/30021 Primary

  Compare instructions, e.g. Greater-Than, Equal-To, MINMAX · CPC title

• G06F9/30032

  Movement instructions, e.g. MOVE, SHIFT, ROTATE, SHUFFLE · CPC title

• G06F16/2456

  Join operations · CPC title