Techniques for more efficient usage of memory-to-CPU bandwidth

• US 8,572,131 B2
• Filed: 12/07/2012
• Issued: 10/29/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,054
• Publication Number:
  US 20130151567A1
• Time in Patent Office: 326 Days
• Field of Search: 707/802, 707/693, 707/769, 707/716, 711/150, 711/100, 719/318
• 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, a plurality of column vectors for a relational table of a relational database;

wherein the plurality of column vectors includes a particular column vector;

wherein the particular column vector contiguously stores values from a particular column of the relation table;

wherein the values within the particular column vector are stored in the volatile memory in a particular format;

wherein the particular format is one of (a) a compressed format, or (b) a variable-width format;

during execution of a database command, transferring, in the particular format, a contiguous portion of the particular column vector from the volatile memory to a CPU;

wherein the contiguous portion includes a first set of values that corresponds to a plurality of values of the particular column of the relational table; and

based on the first set of values, for each value of the plurality of values, the CPU generating results of performing at least one operation, required by the database command, on said each value;

wherein the step of generating results is performed after transferring the contiguous portion to the CPU, and before any further communication, between the volatile memory and the CPU, of data corresponding to the plurality of values.

2. The method of claim 1 wherein the step of generating results comprises executing, within the CPU, a vector processing operation that concurrently generates results of performing the at least one on said each value of the plurality of values.

3. The method of claim 2 wherein executing the vector processing operation is performed in response to a single SIMD instruction.

4. The method of claim 1 wherein:

the database command includes a predicate that specifies a comparison operation involving values from the particular column; and

the at least one operation includes the comparison operation specified in the predicate.

5. The method of claim 1 wherein:

the at least one operation involves values from the particular column and values from a second column, of the relational table, that is different than the particular column;

wherein a second column vector of the plurality of column vectors corresponds to the second column; and

the method further comprises, during execution of the database command, transferring a contiguous series of values of the second column vector from the volatile memory to the CPU.

6. The method of claim 5 further comprising padding the first set of values within the CPU prior to generating results of performing the at least one operation on said each value.

7. The method of claim 6 wherein padding the first set of values is performed by specialized hardware present on the CPU.

8. The method of claim 6 wherein padding the first set of values is performed by general purpose hardware on the CPU in response to executing instructions.

9. The method of claim 5 wherein the step of generating results is performed without padding the first set of values.

10. The method of claim 9 wherein the step of generating results comprises executing, within the CPU, a vector processing operation directly on the first set of values in the variable-length format.

11. The method of claim 1 wherein the particular format is a compressed format.

12. The method of claim 11 wherein:

within the compressed format, values from the particular column are represented by pointers; and

generating results of performing the at least one operation involves performing the at least one operation on the pointers.

13. The method of claim 12 wherein:

the compressed format is produced by using one or more encoding techniques;

the one or more encoding techniques include dictionary encoding; and

the pointers are pointers into a dictionary used to perform the dictionary encoding.

14. The method of claim 11 further comprising decompressing the first set of values within the CPU prior to generating results of performing the at least one operation on said each value.

15. The method of claim 14 wherein the step of decompressing is performed by specialized hardware present on the CPU.

16. The method of claim 14 wherein the step of decompressing is performed by general purpose hardware on the CPU in response to executing instructions.

17. The method of claim 14 further comprising transferring decoding data from the volatile memory to the CPU to enable the CPU to decompress the compressed values.

18. The method of claim 17 wherein the decoding data that is transferred to the CPU is transferred to the CPU in a compressed format.

19. The method of claim 11 wherein the step of generating results is performed without decompressing the first set of values.

20. The method of claim 1 wherein the particular format is a variable-length format.

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

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

wherein the plurality of column vectors includes a particular column vector;

wherein the particular column vector contiguously stores values from a particular column of the relation table;

wherein the values within the particular column vector are stored in the volatile memory in a particular format;

wherein the particular format is one of (a) a compressed format, or (b) a variable-width format;

during execution of a database command, transferring, in the particular format, a contiguous portion of the particular column vector from the volatile memory to a CPU;

wherein the contiguous portion includes a first set of values that corresponds to a plurality of values of the particular column of the relational table; and

based on the first set of values, for each value of the plurality of values, the CPU generating results of performing at least one operation, required by the database command, on said each value;

wherein the step of generating results is performed after transferring the contiguous portion to the CPU, and before any further communication, between the volatile memory and the CPU, of data corresponding to the plurality of values.

22. The non-transitory computer-readable storage medium of claim 21 wherein the step of generating results comprises executing, within the CPU, a vector processing operation that concurrently generates results of performing the at least one on said each value of the plurality of values.

23. The non-transitory computer-readable storage medium of claim 22 wherein executing the vector processing operation is performed in response to a single SIMD instruction.

24. The non-transitory computer-readable storage medium of claim 21 wherein the particular format is a compressed format.

25. The non-transitory computer-readable storage medium of claim 24 wherein the step of generating results is performed without decompressing the first set of values.

26. The non-transitory computer-readable storage medium of claim 25 wherein the method further comprises padding the first set of values within the CPU prior to generating results of performing the at least one operation on said each value.

27. The non-transitory computer-readable storage medium of claim 26 wherein padding the first set of values is performed by specialized hardware present on the CPU.

28. The non-transitory computer-readable storage medium of claim 25 wherein the step of generating results is performed without padding the first set of values.

29. The non-transitory computer-readable storage medium of claim 28 wherein the step of generating results comprises executing, within the CPU, a vector processing operation directly on the first set of values in the variable-length format.

30. The non-transitory computer-readable storage medium of claim 21 wherein the particular format is a variable-length format.