Techniques for maintaining column vectors of relational data within volatile memory

• US 8,521,788 B2
• Filed: 12/07/2012
• Issued: 08/27/2013
• Est. Priority Date: 12/08/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Ellison, Lawrence J., Ganesh, Amit, Marwah, Vineet, Kamp, Jesse, Patthak, Anindya C., Chavan, Shasank K., Gleeson, Michael J., Holloway, Allison L., Bhattacharyya, Manosiz
• Primary Examiner(s): Vy, Hung T
• Application Number:
  US13/708,060
• Publication Number:
  US 20130151568A1
• Time in Patent Office: 263 Days
• Field of Search: 707/714, 707/802, 707/745, 712/22
• US Class Current: 707/802
• CPC Class Codes: G06F 16/221 Column-oriented storage; Management thereof
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 9/3887 controlled by a single instruction for multiple data lanes [SIMD]

Abstract

Techniques are provided for more efficiently using the bandwidth of the I/O path between a CPU and volatile memory during the performance of database operation. Relational data from a relational table is stored in volatile memory as column vectors, where each column vector contains values for a particular column of the table. A binary-comparable format may be used to represent each value within a column vector, regardless of the data type associated with the column. The column vectors may be compressed and/or encoded while in volatile memory, and decompressed/decoded on-the-fly within the CPU. Alternatively, the CPU may be designed to perform operations directly on the compressed and/or encoded column vector data. In addition, techniques are described that enable the CPU to perform vector processing operations on the column vector values.

Claims

1. A method comprising:

maintaining, within volatile memory of a particular computing device, a plurality of column vectors for a relational table of a relational database;

wherein each column vector, of the plurality of column vectors, corresponds to a distinct column of the relational table;

wherein each column vector, of the plurality of column vectors, is a contiguous array of values;

wherein, within a particular column vector of the plurality of column vectors, values for the corresponding column are represented in a byte-comparable format;

wherein the values in the particular column vector are of a data type that is not binary numeric;

during execution of a database command, transferring, from the volatile memory of the particular computing device, a contiguous series of values in the byte-comparable format from the particular column vector to a CPU of the particular computing device; and

within the CPU of the particular computing device, concurrently performing at least one operation on each value in the contiguous series of values;

wherein the method is performed by the particular computing device.

2. The method of claim 1 wherein the step of concurrently performing is performed by the CPU in response to a single instruction sent to the CPU.

3. The method of claim 1 wherein:

the database command specifies a comparison operation;

the step of concurrently performing the at least one operation comprises performing the comparison operation specified in the database command;

wherein performing the comparison operation specified in the database command comprises comparing a first value from the particular column vector to a second value;

the second value is of the data type;

the first value is compared to the second value by executing a binary number comparison operation that compares bytes that represent the first value in the byte-comparable format with bytes that represent the second value in the byte-comparable format.

4. The method of claim 3 wherein the values in the particular column vector are strings.

5. The method of claim 3 wherein the values in the particular column vector are dates.

6. The method of claim 3 wherein the first value is represented by a different number of bytes than the second value.

7. The method of claim 1 wherein the at least one operation includes a comparison operation specified in a predicate of the database command.

8. The method of claim 1 wherein:

transferring the contiguous series of values includes loading the contiguous series of values into a single register within the CPU; and

concurrently performing at least one operation on each value in the contiguous series of values includes concurrently performing the at least one operation on each value, in the contiguous series of values, loaded in the single register.

9. A non-transitory computer-readable medium storing instructions which, when executed by one or more processors, cause performance of a method comprising:

maintaining, within volatile memory of a particular computing device, a plurality of column vectors for a relational table of a relational database;

wherein each column vector, of the plurality of column vectors, corresponds to a distinct column of the relational table;

wherein each column vector, of the plurality of column vectors, is a contiguous array of values;

wherein, within a particular column vector of the plurality of column vectors, values for the corresponding column are represented in a byte-comparable format;

wherein the values in the particular column vector are of a data type that is not binary numeric;

during execution of a database command, transferring, from the volatile memory of the particular computing device, a contiguous series of values in the byte-comparable format from the particular column vector to a CPU of the particular computing device; and

within the CPU of the particular computing device, concurrently performing at least one operation on each value in the contiguous series of values.

10. The non-transitory computer-readable medium of claim 9 wherein the step of concurrently performing is performed by the CPU in response to a single instruction sent to the CPU.

11. The non-transitory computer-readable medium of claim 9 wherein:

the database command specifies a comparison operation;

the step of concurrently performing the at least one operation comprises performing the comparison operation specified in the database command;

wherein performing the comparison operation specified in the database command comprises comparing a first value from the particular column vector to a second value;

the second value is of the data type;

the first value is compared to the second value by executing a binary number comparison operation that compares bytes that represent the first value in the byte-comparable format with bytes that represent the second value in the byte-comparable format.

12. The non-transitory computer-readable medium of claim 11 wherein the values in the particular column vector are strings.

13. The non-transitory computer-readable medium of claim 11 wherein the values in the particular column vector are dates.

14. The non-transitory computer-readable medium of claim 11 wherein the first value is represented by a different number of bytes than the second value.

15. The non-transitory computer-readable medium of claim 9 wherein the at least one operation includes a comparison operation specified in a predicate of the database command.

16. The non-transitory computer-readable medium of claim 9 wherein:

transferring the contiguous series of values includes loading the contiguous series of values into a single register within the CPU; and

concurrently performing at least one operation on each value in the contiguous series of values includes concurrently performing the at least one operation on each value, in the contiguous series of values, loaded in the single register.

17. A computing device, comprising volatile memory and a CPU, configured to perform a method comprising:

maintaining, within the volatile memory, a plurality of column vectors for a relational table of a relational database;

wherein each column vector, of the plurality of column vectors, corresponds to a distinct column of the relational table;

wherein each column vector, of the plurality of column vectors, is a contiguous array of values;

wherein, within a particular column vector of the plurality of column vectors, values for the corresponding column are represented in a byte-comparable format;

wherein the values in the particular column vector are of a data type that is not binary numeric;

during execution of a database command, transferring, from the volatile memory, a contiguous series of values in the byte-comparable format from the particular column vector to the CPU; and

within the CPU, concurrently performing at least one operation on each value in the contiguous series of values.

18. The computing device of claim 17 wherein the step of concurrently performing is performed by the CPU in response to a single instruction sent to the CPU.

19. The computing device of claim 17 wherein:

the database command specifies a comparison operation;

the step of concurrently performing the at least one operation comprises performing the comparison operation specified in the database command;

wherein performing the comparison operation specified in the database command comprises comparing a first value from the particular column vector to a second value;

the second value is of the data type;

the first value is compared to the second value by executing a binary number comparison operation that compares bytes that represent the first value in the byte-comparable format with bytes that represent the second value in the byte-comparable format.

20. The computing device of claim 19 wherein the values in the particular column vector are strings.

21. The computing device of claim 19 wherein the values in the particular column vector are dates.

22. The computing device of claim 19 wherein the first value is represented by a different number of bytes than the second value.

23. The computing device of claim 17 wherein the at least one operation includes a comparison operation specified in a predicate of the database command.

24. The computing device of claim 17 wherein:

transferring the contiguous series of values includes loading the contiguous series of values into a single register within the CPU; and

concurrently performing at least one operation on each value in the contiguous series of values includes concurrently performing the at least one operation on each value, in the contiguous series of values, loaded in the single register.