Materializing expressions within in-memory virtual column units to accelerate analytic queries

• US 10,204,135 B2
• Filed: 05/04/2016
• Issued: 02/12/2019
• Est. Priority Date: 07/29/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Mishra, Aurosish, Chavan, Shasank K., Holloway, Allison L., Kamp, Jesse, Kumar, Ramesh, Liu, Zhen Hua, Mukherjee, Niloy, Ganesh, Amit, Lahiri, Tirthankar, Marwah, Vineet
• Primary Examiner(s): Jami, Hares
• Application Number:
  US15/146,799
• Publication Number:
  US 20170031975A1
• Time in Patent Office: 1,014 Days
• Field of Search: 707705, 707713, 707717, 707722
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2393 Updating materialised views
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/2455 Query execution

Abstract

Techniques are described for materializing pre-computed results of expressions. In an embodiment, a set of one or more column units are stored in volatile or non-volatile memory. Each column unit corresponds to a column that belongs to an on-disk table within a database managed by a database server instance and includes data items from the corresponding column. A set of one or more virtual column units, and data that associates the set of one or more column units with the set of one or more virtual column units, are also stored in memory. The set of one or more virtual column units includes a particular virtual column unit storing results that are derived by evaluating an expression on at least one column of the on-disk table.

Claims

1. A method comprising:

storing, in volatile or non-volatile memory, a set of one or more column units;

wherein the set of one or more column units correspond to one or more columns;

wherein each column unit of the set of one or more column units includes data items from the column to which the column unit corresponds;

wherein the one or more columns belong to one or more on-disk tables within a database managed by a database server instance;

wherein the set of one or more column units includes a particular column unit that corresponds to at least one particular column of a particular table within the database;

storing, in volatile or non-volatile memory, a set of one or more virtual column units;

wherein the set of one or more virtual column units includes a particular virtual column unit that stores results that are derived by evaluating an expression on the at least one particular column;

storing, in volatile or non-volatile memory, data that associates the set of one or more column units with the set of one or more virtual column units;

wherein the set of one or more column units belong to a first in-memory columnar unit;

wherein the set of one or more virtual column units belong to a first in-memory expression unit;

wherein the first in-memory columnar unit and the first in-memory expression unit correspond to a first set of rows from the one or more columns;

wherein the results stored in the particular virtual column unit are derived using values in the first set of rows from the at least one particular column;

wherein the first set of rows include a first row and a second row;

maintaining, within a shared metadata unit, data that indicates which rows in the first set of rows have become stale within both the first in-memory columnar unit and the first in-memory expression unit

storing, in volatile or non-volatile memory, data that associates the shared metadata unit with the first in-memory columnar unit and the first in-memory expression unit;

in response to detecting an update to the first row, updating the data in the shared metadata unit to indicate that, within both the first in-memory columnar unit and the first in-memory expression unit, the first row has become stale;

after updating the data in the shared metadata unit, receiving a query that requires evaluation of the expression;

in response to receiving the query;

based on the data in the shared metadata unit, determining that, within the first in-memory columnar unit and the first in-memory expression unit, the first row has become stale;

responsive to determining that, within the first in-memory columnar unit and the first in-memory expression unit, the first row has become stale, evaluating the expression for the first row based on values obtained from a source other than the first in-memory columnar unit and the first in-memory expression unit;

based on the data in the shared metadata unit, determining that, within the first in-memory columnar unit and the first in-memory expression unit, the second row is not stale; and

responsive to determining that, within the first in-memory columnar unit and the first in-memory expression unit, the second row is not stale, obtaining results of the expression for the second row by reading cached results of the expression, for the second row, from the first in-memory expression unit.

2. The method of claim 1 further comprising maintaining, in volatile or non-volatile memory, an in-memory internal unit that stores pre-computed results that:

are derived from values in the one or more columns; and

do not have a one-to-one correspondence with rows of the one or more on-disk tables.

3. The method of claim 1,

wherein the particular virtual column unit stores data for a particular virtual column;

wherein the particular virtual column is defined using the expression; and

wherein the particular virtual column does not correspond to an on-disk column.

4. The method of claim 1, the method further comprising:

storing, in volatile or non-volatile memory, a second in-memory columnar unit and a second in-memory expression unit;

wherein the second in-memory columnar unit and the second in-memory expression unit correspond to a second set of rows from the one or more columns;

wherein the second in-memory columnar unit includes a second set of one or more column units corresponding to the one or more columns;

wherein the second in-memory expression unit includes a second set of one or more virtual column units; and

wherein the second set of one or more virtual column units includes a second virtual column unit stores results for the expression that are derived using values in the second set of rows from the at least one particular column.

5. The method of claim 1, further comprising:

wherein the expression operates on the at least one particular column;

wherein the query includes the expression that operates on the at least one particular column;

in response to receiving the query, identifying, based on the data that associates the set of one or more column units with the set of one or more virtual column units, the particular virtual column unit; and

rewriting the query to access the results stored in the particular virtual column unit rather than re-computing the results for the expression.

6. The method of claim 1, further comprising:

receiving a query that includes a second expression that operates on at least one column of the one or more columns;

wherein results for the second expression are not stored in the set of one or more virtual column units;

in response to receiving the query, updating a set of statistics for the second expression during evaluation of the second expression;

determining, based on the set of statistics updated during evaluation of the second expression, whether to materialize results for the second expression within volatile or non-volatile memory; and

in response to determining to materialize results for the second expression, generating and storing, within volatile or non-volatile memory, at least one virtual column unit that includes results of evaluating the second expression.

7. The method of claim 1, further comprising:

determining, based on a set of statistics maintained for the expression, that the results for the expression should be evicted from volatile or non-volatile memory; and

in response to determining that the results should be evicted from volatile or non-volatile memory, removing the particular virtual column unit from volatile or non-volatile memory.

8. The method of claim 1, further comprising repopulating the set of one or more virtual column units in response to detecting that the set of one or more column units has been repopulated with data from the one or more columns.

9. The method of claim 1, wherein the results that are populated in the particular virtual column unit are computed from a set of data as the set of data existed when the set of one or more column units were populated;

and wherein the results are populated in the particular virtual column unit by a background process.

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

storing, in volatile or non-volatile memory, a set of one or more column units;

wherein the set of one or more column units correspond to one or more columns;

wherein each column unit of the set of one or more column units includes data items from the column to which the column unit corresponds;

wherein the one or more columns belong to one or more on-disk tables within a database managed by a database server instance;

wherein the set of one or more column units includes a particular column unit that corresponds to at least one particular column of a particular table within the database;

storing, in volatile or non-volatile memory, a set of one or more virtual column units;

wherein the set of one or more virtual column units includes a particular virtual column unit that stores results that are derived by evaluating an expression on the at least one particular column;

storing, in volatile or non-volatile memory, data that associates the set of one or more column units with the set of one or more virtual column units;

wherein the set of one or more column units belong to a first in-memory columnar unit

wherein the set of one or more virtual column units belong to a first in-memory expression unit;

wherein the first in-memory columnar unit and the first in-memory expression unit correspond to a first set of rows from the one or more columns;

wherein the results stored in the particular virtual column unit are derived using values in the first set of rows from the at least one particular column;

wherein the first set of rows include a first row and a second row;

maintaining, within a shared metadata unit, data that indicates which rows in the first set of rows have become stale within both the first in-memory columnar unit and the first in-memory expression unit;

storing, in volatile or non-volatile memory, data that associates the shared metadata unit with the first in-memory columnar unit and the first in-memory expression unit;

in response to detecting an update to the first row, updating the data in the shared metadata unit to indicate that, within both the first in-memory columnar unit and the first in-memory expression unit, the first row has become stale;

after updating the data in the shared metadata unit, receiving a query that requires evaluation of the expression;

in response to receiving the query;

based on the data in the shared metadata unit, determining that, within the first in-memory columnar unit and the first in-memory expression unit, the first row has become stale;

responsive to determining that, within the first in-memory columnar unit and the first in-memory expression unit, the first row has become stale, evaluating the expression for the first row based on values obtained from a source other than the first in-memory columnar unit and the first in-memory expression unit;

based on the data in the shared metadata unit, determining that, within the first in-memory columnar unit and the first in-memory expression unit, the second row is not stale; and

responsive to determining that, within the first in-memory columnar unit and the first in-memory expression unit, the second row is not stale, obtaining results of the expression for the second row by reading cached results of the expression, for the second row, from the first in-memory expression unit.

11. The one or more non-transitory computer-readable media of claim 10,

wherein the particular virtual column unit stores data for a particular virtual column;

wherein the particular virtual column is defined using the expression; and

wherein the particular virtual column does not correspond to an on-disk column.

12. The one or more non-transitory computer-readable media of claim 10, wherein the instructions further cause:

storing, in volatile or non-volatile memory, a second in-memory columnar unit and a second in-memory expression unit;

wherein the second in-memory columnar unit and the second in-memory expression unit correspond to a second set of rows from the one or more columns;

wherein the second in-memory columnar unit includes a second set of one or more column units corresponding to the one or more columns;

wherein the second in-memory expression unit includes a second set of one or more virtual column units; and

wherein the second set of one or more virtual column units includes a second virtual column unit stores results for the expression that are derived using values in the second set of rows from the at least one particular column.

13. The one or more non-transitory computer-readable media of claim 10, wherein the instructions further cause:

wherein the expression operates on the at least one particular column;

wherein the query includes the expression that operates on the at least one particular column;

in response to receiving the query, identifying, based on the data that associates the set of one or more column units with the set of one or more virtual column units, the particular virtual column unit; and

rewriting the query to access the results stored in the particular virtual column unit rather than re-computing the results for the expression.

14. The one or more non-transitory computer-readable media of claim 10, wherein the instructions further cause:

receiving a query that includes a second expression that operates on at least one column of the one or more columns;

wherein results for the second expression are not stored in the set of one or more virtual column units;

in response to receiving the query, updating a set of statistics for the second expression during evaluation of the second expression;

determining, based on the set of statistics updated during evaluation of the second expression, whether to materialize results for the second expression within volatile or non-volatile memory; and

in response to determining to materialize results for the second expression, generating and storing, within volatile or non-volatile memory, at least one virtual column unit that includes results for the second expression.

15. The one or more non-transitory computer-readable media of claim 10, wherein the instructions further cause:

determining, based on a set of statistics maintained for the expression, that the results for the expression should be evicted from volatile or non-volatile memory; and

in response to determining that the results should be evicted from volatile or non-volatile memory, removing the particular virtual column unit from volatile or non-volatile memory.

16. The one or more non-transitory computer-readable media of claim 10, wherein the instructions further cause repopulating the set of one or more virtual column units in response to detecting that the set of one or more column units has been repopulated with data from the one or more columns.

17. The one or more non-transitory computer-readable media of claim 10, wherein the results that are populated in the particular virtual column unit are computed from a set of data as the set of data existed when the set of one or more column units were populated;

and wherein the results are populated in the particular virtual column unit by a background process.