Materializing internal computations in-memory to improve query performance

• US 10,366,083 B2
• Filed: 05/04/2016
• Issued: 07/30/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: Chavan, Shasank K., Mishra, Aurosish, Ganesh, Amit
• Primary Examiner(s): Jami, Hares
• Application Number:
  US15/146,801
• Publication Number:
  US 20170031976A1
• Time in Patent Office: 1,182 Days
• Field of Search: 707713, 707717, 707736, 707769
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 16/2255 Hash tables
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/23 Updating
• CPC Class Codes: G06F 16/2393 Updating materialised views
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 2212/60 Details of cache memory

Abstract

Techniques are described for materializing computations in memory. In an embodiment, responsive to a database server instance receiving a query, the database server instance identifies a set of computations for evaluation during execution of the query. Responsive to identifying the set of computations, the database server instance evaluates at least one computation in the set of computations to obtain a first set of computation results for a first computation in the set of computations. After evaluating the at least one computation, the database server instance stores, within an in-memory unit, the first set of computation results. The database server also stores mapping data that maps a set of metadata values associated with the first computation to the first set of computation results.

Claims

1. A method comprising:

receiving, by a database server instance, a query;

responsive to receiving the query, identifying, by the database server instance, a set of computations for evaluation during execution of the query;

wherein the set of computations includes a first computation;

responsive to identifying the set of computations, evaluating the first computation, by the database server instance, to obtain a first set of computation results for the first computation;

after evaluating the first computation, materializing, by the database server instance, within an in-memory unit, the first set of computation results for use during execution of another query,

wherein the in-memory unit includes a materialized results area,

wherein the materialized results area stores a set of bit-vectors derived from evaluating predicate evaluations and a set of columns derived from non-predicate evaluations, and

wherein the in-memory unit stores;

a first pointer for allocating space for bit-vector result sets, and

a second pointer for allocating space for result sets derived from non-predicate evaluations; and

storing, by the database server instance, within the in-memory unit, mapping data that maps a set of metadata values associated with the first computation to the first set of computation results;

using, by the database server instance, the first set of computation results, which were materialized within the in-memory unit, to answer a subsequently-received query that involves the first computation.

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

storing, within the in-memory unit, a hash table of computations;

wherein the hash table of computations includes a set of entries that correspond to different computations;

wherein the set of entries includes a particular entry corresponding to the first computation;

wherein the set of metadata values for the first computation is stored in a particular entry in the set of entries;

wherein the particular entry includes a pointer to the first set of computation results for the first computation.

3. The method of claim 2, further comprising;

applying a hash function to a representation of the first computation to identify a location of the particular entry within the hash table of computations;

in response to evaluating the first computation, updating the set of metadata values within the particular entry of the hash table of computations.

4. The method of claim 2, wherein the particular entry of the hash table of computations includes a set of concurrency values for managing concurrent accesses to the particular entry by separate processes.

5. The method of claim 1, further comprising:

receiving, by the database server instance, a second query;

responsive to receiving the second query, the database server instance identifying a second set of computations for evaluation during execution of the second query;

wherein the second set of computations includes the first computation;

wherein the second set of computations includes at least one computation that is not included in the first set of computations;

rewriting the second query to access the first set of expression results from the in-memory unit instead of computing the first expression result.

6. The method of claim 1, further comprising, prior to storing the first set of computation results in the in-memory unit, performing:

determining that there is not enough space to store the first set of computation results within the in-memory unit;

in response to determining that there is not enough space to store the first set of computation results within the in-memory unit, performing one of;

evicting, from the in-memory unit, a second set of computation results for a second computation to free space for the first set of computation results;

or

allocating an additional in-memory extent for the in-memory unit and storing the first set of computation results in the additional in-memory extent.

7. The method of claim 1, wherein the set of metadata values that are associated with the first computation include one or more of:

a computation representation for the first computation,

an evaluation count that tracks how many times the first computation has been evaluated,

an access count that tracks how many times the first computation has been accessed by queries,

a timestamp indicating a time that the first computation was last evaluated, or

a reader count indicating how many processes are accessing the first set of computation results from the in-memory unit.

8. The method of claim 1, wherein the plurality of computations includes a plurality of predicates, the method further comprising:

determining which predicate results for the plurality of predicates are currently cached in the in-memory unit;

changing an evaluation order for evaluating the plurality of predicates included in the query based, at least in part, on which predicates of the plurality of predicates have predicate results currently cached in the in-memory unit.

9. A method comprising:

receiving, by a database server instance, a query;

responsive to receiving the query, identifying, by the database server instance, a set of computations for evaluation during execution of the query;

wherein the set of computations includes a first computation;

responsive to identifying the set of computations, evaluating the first computation, by the database server instance, to obtain a first set of computation results for the first computation;

determining, by the database server instance, a score for the first computation based, at least in part, on a frequency with which the first computation is evaluated;

determining, whether the score for the first computation satisfies a threshold;

after evaluating the first computation, and responsive to determining that the score of the first computation satisfies the threshold, storing, by the database server instance within an in-memory unit, the first set of computation results; and

storing, by the database server instance within the in-memory unit, mapping data that maps a set of metadata values associated with the first computation to the first set of computation results.

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

receiving, by a database server instance, a query;

responsive to receiving the query, identifying, by the database server instance, a set of computations for evaluation during execution of the query;

wherein the set of computations includes a first computation;

responsive to identifying the set of computations, evaluating the first computation, by the database server instance, to obtain a first set of computation results for the first computation;

after evaluating the first computation, materializing, by the database server instance, within an in-memory unit, the first set of computation results for use during execution of another query,

wherein the in-memory unit includes a materialized results area,

wherein the materialized results area stores a set of bit-vectors derived from evaluating predicate evaluations and a set of columns derived from non-predicate evaluations, and

wherein the in-memory unit stores;

a first pointer for allocating space for bit-vector result sets, and

a second pointer for allocating space for result sets derived from non-predicate evaluations; and

storing, by the database server instance, within the in-memory unit, mapping data that maps a set of metadata values associated with the first computation to the first set of computation results;

using, by the database server instance, the first set of computation results, which were materialized within the in-memory unit, to answer a subsequently-received query that involves the first computation.

11. The one or more non-transitory computer-readable media of claim 10, the instructions further causing:

storing, within the in-memory unit, a hash table of computations;

wherein the hash table of computations includes a set of entries that correspond to different computations;

wherein the set of entries includes a particular entry corresponding to the first computation;

wherein the set of metadata values for the first computation is stored in a particular entry in the set of entries;

wherein the particular entry includes a pointer to the first set of computation results for the first computation.

12. The one or more non-transitory computer-readable media of claim 11, the instructions further causing;

applying a hash function to a representation of the first computation to identify a location of the particular entry within the hash table of computations;

in response to evaluating the first computation, updating the set of metadata values within the particular entry of the hash table of computations.

13. The one or more non-transitory computer-readable media of claim 11, wherein the particular entry of the hash table of computations includes a set of concurrency values for managing concurrent accesses to the particular entry by separate processes.

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

receiving, by the database server instance, a second query;

responsive to receiving the second query, the database server instance identifying a second set of computations for evaluation during execution of the second query;

wherein the second set of computations includes the first computation;

wherein the second set of computations includes at least one computation that is not included in the first set of computations;

rewriting the second query to access the first set of expression results from the in-memory unit instead of computing the first expression result.

15. The one or more non-transitory computer-readable media of claim 10, the instructions further causing, prior to storing the first set of computation results in the in-memory unit, performing:

determining that there is not enough space to store the first set of computation results within the in-memory unit;

in response to determining that there is not enough space to store the first set of computation results within the in-memory unit, performing one of;

evicting, from the in-memory unit, a second set of computation results for a second computation to free space for the first set of computation results;

or

allocating an additional in-memory extent for the in-memory unit and storing the first set of computation results in the additional in-memory extent.

16. The one or more non-transitory computer-readable media of claim 10, wherein the set of metadata values that are associated with the first computation include one or more of:

a computation representation for the first computation,

an evaluation count that tracks how many times the first computation has been evaluated,

an access count that tracks how many times the first computation has been accessed by queries,

a timestamp indicating a time that the first computation was last evaluated, or

a reader count indicating how many processes are accessing the first set of computation results from the in-memory unit.

17. The one or more non-transitory computer-readable media of claim 10, wherein the plurality of computations includes a plurality of predicates, the instructions further causing:

determining which predicate results for the plurality of predicates are currently cached in the in-memory unit;

changing an evaluation order for evaluating the plurality of predicates included in the query based, at least in part, on which predicates of the plurality of predicates have predicate results currently cached in the in-memory unit.

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

receiving, by a database server instance, a query;

responsive to receiving the query, identifying, by the database server instance, a set of computations for evaluation during execution of the query;

wherein the set of computations includes a first computation;

responsive to identifying the set of computations, evaluating the first computation, by the database server instance, to obtain a first set of computation results for the first computation;

determining, by the database server instance, a score for the first computation based, at least in part, on a frequency with which the first computation is evaluated;

determining, whether the score for the first computation satisfies a threshold;

after evaluating the first computation, and responsive to determining that the score of the first computation satisfies the threshold, storing, by the database server instance within an in-memory unit, the first set of computation results; and

storing, by the database server instance within the in-memory unit, mapping data that maps a set of metadata values associated with the first computation to the first set of computation results.