Building a hash table using vectorized instructions

摘要

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.

主权项

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.