Performing an aggregation operation using vectorized instructions

Patent metadata

Field	Value
Publication number	US-9292558-B2
Application number	US-201313956354-A
Country	US
Kind code	B2
Filing date	Aug 1, 2013
Priority date	Jul 31, 2013
Publication date	Mar 22, 2016
Grant date	Mar 22, 2016

Abstract

Techniques for performing database operations using vectorized instructions are provided. In one technique, an aggregation operation involves executing vectorized instructions to update a data value that corresponds to a particular key. The aggregation operation may be one of count, sum, minimum, maximum, or average.

First claim

What is claimed is:

1. A method comprising:
in response to determining to perform an aggregation operation, generating a hash table based on data from a relation;
wherein generating the hash table comprises:
identifying a key that originates from the relation;
generating a hash value based on the 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 key matches a key in the plurality of keys;
loading a plurality of data values into a particular register, wherein the plurality of data values includes a particular data value;
in response to determining that the key matches a key in the plurality of keys, using one or more vectorized instructions to update, based on a data value, the particular data value to generate an updated data value, wherein a vectorized instruction, of the one or more vectorized instructions, when processed, causes a single operation to be performed on the plurality of data values in the particular register;

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

2. The method of claim 1 , wherein generating the hash table further comprises updating the bucket to include the updated data value.

3. The method of claim 1 , wherein updating the particular data value comprises summing the particular data value and the data value to generate the updated data value, wherein the data value originates from the relation.

4. The method of claim 1 , wherein:
the particular data value is an integer value;
the data value is the value one;
updating the particular data value comprises increasing the particular data value by one.

5. The method of claim 1 , wherein:
the data value originates from the relation;
using the one or more vectorized instructions comprises determining whether the data value is less than the particular data value; and
the updated data value is generated only in response to determining that the data value is less than the particular data value.

6. The method of claim 1 , wherein:
the data value originates from the relation;
using the one or more vectorized instructions comprises determining whether the data value is greater than the particular data value; and
the updated data value is generated only in response to determining that the data value is greater than the particular data value.

7. The method of claim 1 , wherein using the one or more vectorized instructions comprises:
determining a position, within in a second register, that corresponds to a particular key, of the plurality of keys, that matches the key;
based on the position, identifying a shuffle mask from among a plurality of shuffle masks;
performing a shuffle operation using the shuffle mask and a second mask.

8. One or more storage media storing instructions which, when executed by one or more processors, cause:
in response to determining to perform an aggregation operation, generating a hash table based on data from a relation;
wherein generating the hash table comprises:
identifying a key that originates from the relation;
generating a hash value based on the 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 key matches a key in the plurality of keys;
loading a plurality of data values into a particular register, wherein the plurality of data values includes a particular data value;
in response to determining that the key matches a key in the plurality of keys, using one or more vectorized instructions to update, based on a data value, the particular data value to generate an updated data value, wherein a vectorized instruction, of the one or more vectorized instructions, when processed, causes a single operation to be performed on the plurality of data values in the particular register.

9. The one or more storage media of claim 8 , wherein generating the hash table further comprises updating the bucket to include the updated data value.

10. The one or more storage media of claim 8 , wherein updating the particular data value comprises summing the particular data value and the data value to generate the updated data value, wherein the data value originates from the relation.

11. The one or more storage media of claim 8 , wherein:
the particular data value is an integer value;
the data value is the value one;
updating the particular data value comprises increasing the particular data value by one.

12. The one or more storage media of claim 8 , wherein:
the data value originates from the relation;
using the one or more vectorized instructions comprises determining whether the data value is less than the particular data value; and
the updated data value is generated only in response to determining that the data value is less than the particular data value.

13. The one or more storage media of claim 8 , wherein:
the data value originates from the relation;
using the one or more vectorized instructions comprises determining whether the data value is greater than the particular data value; and
the updated data value is generated only in response to determining that the data value is greater than the particular data value.

14. The one or more storage media of claim 8 , wherein using the one or more vectorized instructions comprises:
determining a position, within in a second register, that corresponds to a particular key, of the plurality of keys, that matches the key;
based on the position, identifying a shuffle mask from among a plurality of shuffle masks;
performing a shuffle operation using the shuffle mask and a second mask.

15. The method of claim 1 , wherein each data value of the plurality of data values is the same as each other data value of the plurality of data values.

16. The method of claim 1 , wherein determining whether the key matches a key in the plurality of keys comprises:
loading multiple copies of the key into a second register that is different than the first register;
using a particular vectorized instruction to compare contents of the first register with contents of the second register.

17. The method of claim 16 , further comprising:
storing a result of the particular vectorized instruction in a third register;
loading multiple copies of the data value or of the value one into a fourth register that is different than the third register;
wherein using the one or more vectorized instructions comprises executing a vectorized AND instruction based on contents of the third register and contents of the fourth register.

18. The one or more storage media of claim 8 , wherein each data value of the plurality of data values is the same as each other data value of the plurality of data values.

19. The one or more storage media of claim 8 , wherein determining whether the key matches a key in the plurality of keys comprises:
loading multiple copies of the key into a second register that is different than the first register;
using a particular vectorized instruction to compare contents of the first register with contents of the second register.

20. The one or more storage media of claim 19 , wherein the instructions, when executed by the one or more processors, further cause:
storing a result of the particular vectorized instruction in a third register;
loading multiple copies of the data value or of the value one into a fourth register that is different than

Assignees

• Oracle Int Corp

Inventors

• Sen Rajkumar
• Petride Sabina
• Agarwal Nipun

Classifications

• G06F9/30032

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

• G06F9/30021 Primary

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

• G06F16/2255 Primary

  Hash tables · CPC title

• G06F16/2456

  Join operations · CPC title

• G06F16/24544

  Join order optimisation · CPC title