Building a hash table

Patent metadata

Field	Value
Publication number	US-9779123-B2
Application number	US-201614990589-A
Country	US
Kind code	B2
Filing date	Jan 7, 2016
Priority date	Jul 31, 2013
Publication date	Oct 3, 2017
Grant date	Oct 3, 2017

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 first key and a first data value to insert into the hash table, wherein the first key and the first data value are from the relation;
generating a first hash value based on the first key;
identifying, based on the first hash value, a first bucket in the hash table, wherein the first bucket includes a plurality of slots;
determining that the first bucket does not include an available slot to insert the first key and the first data value;
in response to determining that the first bucket does not include an available slot, determining whether a current process to insert the first key and the first data value is a result of an eviction of the first key and the first data value from another bucket in the hash table;
in response to determining that the current process to insert the first key and the first data value is the result of an eviction of the first key and the first data value from another bucket in the hash table, storing the first key and the first data value into a second data structure that is outside the hash table;

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

2. The method of claim 1 , wherein the first hash value is generated based on a first hash function, the method further comprising, prior to identifying the first bucket:
generating, using a second hash function that is different than the first hash function, a second hash value based on the first key, wherein the second hash value is different than the first hash value;
identifying, based on the second hash value, a second bucket in the hash table, wherein the second bucket includes a second plurality of slots;
determining that the second bucket does not include an available slot to insert the first key and the first hash value;
wherein generating the first hash value comprises generating the first hash value in response to determining that the second bucket does not includes an available slot.

3. The method of claim 1 , further comprising:
identifying a particular bucket in the hash table;
selecting a particular slot from the particular bucket;
identifying, within the particular slot, the first key and the first data value;
removing the first key and the first data value from the particular bucket;
inserting, into the particular bucket, a second key that is different than the first key and second data value that is different than the first data value.

4. The method of claim 3 , further comprising:
updating a value of a parameter to indicate that an eviction occurred.

5. The method of claim 4 , wherein determining whether the current process to insert the first key and the first data value is the result of an eviction of the first key and the first data value from another bucket in the hash table comprises determining whether the value of the parameter is equal to a particular value.

6. The method of claim 1 , further comprising, prior to generating the first hash value:
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, using a first hash function, a second hash value based on the second key;
identifying, based on the second hash value, a second bucket in the hash table, wherein the second bucket includes a second plurality of slots;
determining that the second bucket does not include an available slot to insert the second key and the second data value;
in response to determining that the second bucket does not includes an available slot, generating, using a second hash function that is different than the first hash function, a third hash value based on the second key;
identifying, based on the third hash value, a third bucket in the hash table, wherein the third bucket includes a third plurality of slots;
determining whether the third bucket includes an available slot to insert the second key and the second data value.

7. The method of claim 6 , further comprising:
in response to determining that the third bucket includes an available slot to insert the second key and the second data value, inserting the second key and the second data value into the available slot of the third bucket.

8. The method of claim 6 , further comprising:
in response to determining that the third bucket does include an available slot to insert the second key and the second data value, determining whether a current process to insert the second key and the second data value is a result of an eviction of the second key and the second data value from another bucket in the hash table;
in response to determining that the current process to insert the second key and the second data value is not the result of an eviction of the second key and the second data value from another bucket in the hash table, determining a particular bucket from which to evict a key-data value pair.

9. The method of claim 8 , wherein determining the particular bucket from which to evict a key-data value pair comprises selecting only from among the second bucket and the third bucket.

10. The method of claim 8 , further comprising:
storing a position indicator that indicates a relative position within any bucket of the hash table;
identifying a first particular slot, in the particular bucket, that corresponds to the position indicator;
selecting a particular key-data value pair from the first particular slot;
removing the particular key-data value pair from the first particular slot;
shifting each of the remaining key-data value pairs in the particular bucket, wherein shifting causes a second particular slot in the particular bucket to become available;
inserting the second key and the second data value into the second particular slot of the particular bucket.

11. 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 first key and a first data value to insert into the hash table, wherein the first key and the first data value are from the relation;
generating a first hash value based on the first key;
identifying, based on the first hash value, a first bucket in the hash table, wherein the first bucket includes a plurality of slots;
determining that the first bucket does not include an available slot to insert the first key and the first data value;
in response to determining that the first bucket does not include an available slot, determining whether a current process to insert the first key and the first data value is a result of an eviction of the first key and the first data value from another bucket in the hash table;
in response to determining that the current process to insert the first key and the first data value is the result of an eviction of the first key and the first data value from another bucket in the hash table, storing the first key and the first data value into a second data structure that is outside the hash table.

12. The one or more storage media of claim 11 , wherein the first hash value is generated based on a first hash function, wherein the instructions, when executed by the one or more processors, further cause, prior to identifying the first bucket:
generating, using a second hash function that is different than the first hash function, a second hash value based on the first key, wherein the second hash value is different than the first hash value;
identi

Assignees

• Oracle Int Corp

Inventors

• Sen Rajkumar
• Agarwal Nipun

Classifications

• G06F16/24544

  Join order optimisation · CPC title

• G06F9/30021 Primary

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

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F9/30032

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

• G06F16/2456

  Join operations · CPC title