Techniques for maintaining column vectors of relational data within volatile memory

• US 9,965,501 B2
• Filed: 12/01/2015
• Issued: 05/08/2018
• 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:
  US14/955,368
• Publication Number:
  US 20160085781A1
• Time in Patent Office: 889 Days
• Field of Search: 707714, 707802, 707845, 711109
• 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 computing device that is executing a database server, 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, has a contiguous array of values;

wherein the plurality of column vectors includes a particular column vector that has a contiguous array of whole uncompressed variable-length values of a particular column of the relational table;

in response to a database command received by the database server, the database server reading multiple values into a central processing unit (CPU) during a single clock cycle from the contiguous array of whole uncompressed variable-length values of the particular column to determine a result set for the database command.

2. The method of claim 1 wherein, within the particular column vector of the plurality of column vectors, values for the particular column are represented in a byte-comparable format.

3. The method of claim 1 further comprising during execution of a database command, transferring data from the particular column vector to the CPU of said computing device without converting values from the particular column vector to a fixed length format.

4. The method of claim 3 further comprising converting, by the CPU, values from the particular column vector to a particular fixed length format.

5. The method of claim 4 wherein:

the method further comprises performing, within the CPU, an operation on multiple values from the particular column vector in said particular fixed length format;

no values in said particular fixed length format are transferred out of the CPU during or between the performance of said converting and said operation.

6. The method of claim 4 wherein:

said converting comprises converting a first subset of values from the particular column vector to a first fixed length format and converting a second subset of values from the particular column vector to a second fixed length format;

said first fixed length format is shorter than said second fixed length format.

7. The method of claim 3 wherein execution of the database command comprises processing, within the CPU, a single-instruction multiple-data (SIMD) instruction that performs an operation on multiple values, from the particular column vector, in parallel.

8. The method of claim 7 wherein said SIMD instruction begins and finishes execution during a same clock cycle.

9. The method of claim 7 wherein:

the method further comprises detecting whether said CPU supports said SIMD instruction;

executing said SIMD instruction if said CPU supports said SIMD instruction;

emulating, by executing multiple instructions, said SIMD instruction if said CPU does not support said SIMD instruction.

10. The method of claim 3 further comprising performing, by the CPU, a comparison operation required by the database command on values from the particular column vector without converting the values to a fixed length format.

11. The method of claim 1 further comprising maintaining within said volatile memory, for each column vector of at least one of said plurality of column vectors, a respective length vector containing a plurality of length values that indicate an amount of memory needed to store each value of said each column vector.

12. The method of claim 11 wherein said respective length vector of said each column vector comprises length values that are compressed.

13. One or more non-transitory computer-readable media comprising stored instructions wherein:

said stored instructions comprise first instructions that, when executed by one or more processors, cause maintaining, within volatile memory of a computing device that is executing a database server, a plurality of column vectors for a relational table of a relational database;

the plurality of column vectors includes a particular column vector that has a contiguous array of whole uncompressed variable-length values of a particular column of the relational table;

said stored instructions comprise second instructions that, when executed by the one or more processors, cause during execution of a database command, transferring data from the particular column vector to a central processing unit (CPU) of said computing device without converting values from the particular column vector to a fixed length format;

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

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

said stored instructions comprise third instructions that, when executed by the one or more processors, cause in response to a database command received by the database server, the database server reading multiple values into a central processing unit (CPU) during a single clock cycle from the contiguous array of whole uncompressed variable-length values of the particular column to determine a result set for the database command.

14. The one or more non-transitory computer-readable media of claim 13 wherein said stored instructions comprise instructions that, when executed by said one or more processors, cause converting, by the CPU, values from the particular column vector to a particular fixed length format.

15. The one or more non-transitory computer-readable media of claim 14 wherein:

said stored instructions comprise instructions that, when executed by said one or more processors, cause performing, within the CPU, an operation on multiple values in said particular fixed length format;

no values in said particular fixed length format are transferred out of the CPU during or between the performance of said converting and said operation.

16. The one or more non-transitory computer-readable media of claim 14 wherein:

said converting comprises converting a first subset of values from the particular column vector to a first fixed length format and converting a second subset of values from the particular column vector to a second fixed length format;

said first fixed length format is shorter than said second fixed length format.

17. The one or more non-transitory computer-readable media of claim 13 wherein execution of the database command comprises processing, within the CPU, a single-instruction multiple-data (SIMD) instruction that performs an operation on multiple values, from the particular column vector, in parallel.

18. The one or more non-transitory computer-readable media of claim 17 wherein:

said stored instructions comprise instructions that, when executed by said one or more processors, cause;

detecting whether said CPU supports said SIMD instruction;

executing said SIMD instruction if said CPU supports said SIMD instruction; and

emulating, by executing multiple instructions, said SIMD instruction if said CPU does not support said SIMD instruction.

19. The one or more non-transitory computer-readable media of claim 13 wherein said stored instructions comprise instructions that, when executed by said one or more processors, cause performing, by the CPU, a comparison operation required by the database command on values from the particular column vector without converting the values to a fixed length format.

20. The one or more non-transitory computer-readable media of claim 13 wherein said stored instructions comprise instructions that, when executed by said one or more processors, cause maintaining within said volatile memory, for each column vector of at least one of said plurality of column vectors, a respective length vector containing a plurality of length values that indicate an amount of memory needed to store each value of said each column vector.