Combined row and columnar storage for in-memory databases for OLTP and analytics workloads

• US 10,311,154 B2
• Filed: 12/05/2013
• Issued: 06/04/2019
• Est. Priority Date: 09/21/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Lahiri, Tirthankar, Reames, Martin A., Edson, Kirk, Goyal, Neelam, Makino, Kao, Patthak, Anindya, Thomas, Dina, Sarkar, Subhradyuti, Hoang, Chi-Kim, Jiang, Qingchun
• Primary Examiner(s): Alam, Hosain T
• Assistant Examiner(s): Allen, Nicholas E
• Application Number:
  US14/097,575
• Publication Number:
  US 20150088813A1
• Time in Patent Office: 2,007 Days
• Field of Search: 707609
• CPC Class Codes: G06F 16/21 Design, administration or maintenance of databases
• CPC Class Codes: G06F 16/211 Schema design and management
• CPC Class Codes: G06F 16/278 Data partitioning, e.g. horizontal or vertical partitioning

Abstract

Columns of a table are stored in either row-major format or column-major format in an in-memory DBMS. For a given table, one set of columns is stored in column-major format; another set of columns for a table are stored in row-major format. This way of storing columns of a table is referred to herein as dual-major format. In addition, a row in a dual-major table is updated “in-place”, that is, updates are made directly to column-major columns without creating an interim row-major form of the column-major columns of the row. Users may submit database definition language (“DDL”) commands that declare the row-major columns and column-major columns of a table.

Claims

1. A method, said method comprising steps of:

storing rows in a table in a database, wherein storing rows in said table comprises storing one or more column-major columns of said rows in column-major format and storing one or more row-major columns of said rows in row-major format;

wherein storing rows in said table further comprises;

storing said one or more row-major columns in a row partition comprising row pages;

storing said one or more column-major columns in one or more column partitions, each column partition of said one or more column partitions comprising column pages, wherein said one or more column-major columns include a particular column-major column;

executing a database transaction, wherein executing said database transaction comprises updating in said database said particular column-major column in-place to a new value;

committing said database transaction; and

wherein said updating comprises storing said new value in a column page of said one or more column partitions before committing said database transaction.

2. The method of claim 1, wherein:

based on a functional mapping, a row slot in said row partition has one-to-one association with a column slot in each column partition of said one or more column partitions.

3. The method of claim 2, the method further including:

determining a location of a row in said column partition of said one or more column partitions; and

based on said functional mapping and said location of said row in said column partition, determining a location of said row in said row partition.

4. The method of claim 1, the method further including compressing at least one column partition of said one or more column partitions using run-length encoding.

5. The method of claim 4, where the steps further comprise:

based on a location of a row in said row partition, traversing an index that indexes said at least one column partition to determine a location of an encoded run in said at least one column partition corresponding to a column of said row.

6. The method of claim 5, the steps further comprising:

determining a location of a column value in said at least one column partition; and

based on said index and said location of said column value, determining a location of row holding said column value.

7. The method of claim 1, wherein for one or more column pages of said one or more column partitions, each column page of said one or more column pages is associated with a Bloom filter derived from column values in said each column page.

8. One or more non-transitory computer-readable media storing sequences of instructions, which, when executed by one or more processors, cause:

storing rows in a table in a database, wherein storing rows in said table comprises storing one or more column-major columns of said rows in column-major format and storing one or more row-major columns of said rows in row-major format;

wherein storing rows in said table further comprises;

storing said one or more row-major columns in a row partition comprising row pages;

storing said one or more column-major columns in one or more column partitions, each column partition of said one or more column partitions comprising column pages, wherein said one or more column-major columns include a particular column-major column;

executing a database transaction, wherein executing said database transaction comprises updating in said database said particular column-major column in-place to a new value;

committing said database transaction; and

wherein said updating comprises storing said new value in a column page of said one or more column partitions before committing said database transaction.

9. The one or more non-transitory computer-readable media of claim 8, wherein:

based on a functional mapping, a row slot in said row partition has one-to-one association with a column slot in each column partition of said one or more column partitions.

10. The one or more non-transitory computer-readable media of claim 9, the sequences of instructions further including instructions that, when executed by said one or more processors, cause:

determining a location of a row in said column partition of said one or more column partitions; and

based on said functional mapping and said location of said row in said column partition, determining a location of said row in said row partition.

11. The one or more non-transitory computer-readable media of claim 8, the sequences of instructions further including instructions that, when executed by said one or more processors, cause compressing at least one column partition of said one or more column partitions using run-length encoding.

12. The one or more non-transitory computer-readable media of claim 11, the sequences of instructions further including instructions that, when executed by said one or more processors, cause:

based on a location of a row in said row partition, traversing an index that indexes said at least one column partition to determine a location of an encoded run in said at least one column partition corresponding to a column of said row.

13. The one or more non-transitory computer-readable media of claim 12, the sequences of instructions further including instructions that, when executed by said one or more processors, cause:

determining a location of a column value in said at least one column partition; and

based on said index and said location of said column value, determining a location of a row holding said column value.

14. The one or more non-transitory computer-readable media of claim 8, wherein for one or more column pages of said one or more column partitions, each column page of said one or more column pages is associated with a Bloom filter derived from column values in said each column page.