Optimizer statistics and cost model for in-memory tables

• US 10,073,885 B2
• Filed: 07/22/2015
• Issued: 09/11/2018
• Est. Priority Date: 05/29/2015
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Das, Dinesh, Yan, Jiaqi, Kamp, Jesse, Gaharwar, Prashant, Valluri, Satyanarayana R.
• Primary Examiner(s): Ly, Anh
• Application Number:
  US14/806,597
• Publication Number:
  US 20160350371A1
• Time in Patent Office: 1,147 Days
• CPC Class Codes: G06F 11/34 Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
• CPC Class Codes: G06F 12/023 Free address space management
• CPC Class Codes: G06F 16/2282 Tablespace storage structures; Management thereof
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database
• CPC Class Codes: G06F 2212/1044 Space efficiency improvement
• CPC Class Codes: G06F 2212/401 Compressed data

Abstract

Techniques are provided for determining costs for alternative execution plans for a query, where at least a portion of the data items required by the query are in in-memory compression-units within volatile memory. The techniques involve maintaining in-memory statistics, such as statistics that indicate what fraction of a table is currently present in in-memory compression units, and the cost of decompressing in-memory compression units. Those statistics are used to determine, for example, the cost of a table scan that retrieves some or all of the necessary data items from the in-memory compression-units.

Claims

1. A method comprising:

receiving, at a database server, a query that requires performance of particular operations;

wherein the particular operations include operations that access a particular set of data items;

wherein copies of the data items of the particular set of data items reside in a particular row-major table on persistent storage;

wherein additional copies of at least a subset of the particular set of data items reside, in volatile memory, in one or more column-major in-memory compression-units;

evaluating a plurality of alternative execution plans for performance of the particular operations;

wherein the plurality of alternative execution plans includes at least;

a first execution plan that performs a full table scan that accesses copies of data items in the one or more column-major in-memory compression-units;

a second execution plan that does not perform a full table scan that accesses copies of data items in the one or more column-major in-memory compression-units;

for each execution plan of the plurality of alternative execution plans, determining a cost associated with the execution plan;

wherein determining the cost for the first execution plan includes at least one of;

determining what fraction of the particular row-major table is duplicated in the one or more column-major in-memory compression units;

determining how many column-major in-memory compression-units will need to be scanned, as part of the full table scan, after pruning non-matching column-major in-memory compression-units based on (a) filter predicates of the query, and (b) minimum and maximum values maintained for each column-major in-memory compression-unit;

determining a decompression cost for decompressing those column-major in-memory compression-units to be used during performance of the full table scan;

determining a row-stitching cost that represents overhead required to produce row-major results from data items extracted from column-major in-memory compression-units;

or

determining a journal-scan cost for scanning a journal, maintained in volatile memory, that contains updates for data items that have become invalid in the one or more column-major in-memory compression-units;

selecting a particular execution plan, of the plurality of alternative execution plans, based on the cost determined for the particular execution plan;

obtaining a result set for the query by executing the particular execution plan; and

returning the result set of the query.

2. The method of claim 1 wherein the second execution plan performs a full table scan that does not access copies of data items in the one or more column-major in-memory compression-units.

3. The method of claim 1 wherein the second execution plan makes use of an index to perform the particular operations without performing any full table scan.

4. The method of claim 1 wherein determining the cost for the first execution plan includes determining what fraction of the particular row-major table is duplicated in the one or more column-major in-memory compression units.

5. The method of claim 1 wherein determining the cost for the first execution plan includes determining how many column-major in-memory compression-units will need to be scanned, as part of the full table scan, after pruning non-matching column-major in-memory compression-units based on (a) filter predicates of the query, and (b) minimum and maximum values maintained for each column-major in-memory compression-unit.

6. The method of claim 1 wherein determining the cost for the first execution plan includes determining a decompression cost for decompressing those column-major in-memory compression-units to be used during performance of the full table scan.

7. The method of claim 1 wherein determining the cost for the first execution plan includes determining a row-stitching cost that represents overhead required to produce row-major results from data items extracted from column-major in-memory compression-units.

8. The method of claim 1 wherein determining the cost for the first execution plan includes determining a journal-scan cost for scanning a journal, maintained in volatile memory, that contains updates for data items that have become invalid in the column-major in-memory compression-units.

9. The method of claim 1 wherein:

the database server is executing on one node of a multi-node database cluster;

the query specifies a join between that particular row-major table and a second row-major table;

the join requires particular data items from the particular row-major table to be joined with particular data items from the second row-major table;

copies of the particular data items from the particular row-major table are in a first column-major in-memory compression unit;

copies of the particular data items from the second row-major table are in a second column-major in-memory compression unit; and

determining the cost for the first execution plan further includes determining whether the first column-major in-memory compression unit is in the same node of the cluster as the second column-major in-memory compression unit.

10. A method comprising:

receiving, at a database server, a query that requires performance of particular operations;

wherein the particular operations include operations that access particular data items;

wherein copies of the particular data items reside in a particular row-major table on persistent storage;

wherein additional copies of at least a subset of the particular data items reside, in volatile memory, in one or more column-major in-memory compression-units;

splitting the query into;

a first query that accesses portions of the particular table that are not duplicated in the one or more column-major in-memory compression units, and

a second query that accesses portions of the particular table that are duplicated in the one or more column-major in-memory compression units;

evaluating a first plurality of alternative execution plans for the first query;

wherein evaluating the first plurality of alternative execution plans includes determining costs for each of the first plurality of alternative execution plans;

evaluating a second plurality of alternative execution plans for the second query;

wherein evaluating the second plurality of alternative execution plans includes determining costs for each of the second plurality of alternative execution plans;

selecting a first particular execution plan, of the first plurality of alternative execution plans, based on the cost determined for the first particular execution plan;

selecting a second particular execution plan, of the second plurality of alternative execution plans, based on the cost determined for the second particular execution plan;

obtaining a result set for the query by;

executing the first particular execution plan to produce a first result set, executing the second particular execution plan to produce a second result set, and

combining the first result set and the second result set into a combined result set for the query; and

returning the combined result set for the query.

11. The method of claim 10 wherein the first particular execution plan uses a different access path to obtain data items from the particular table than the second particular execution plan.

12. The method of claim 10, wherein the second plurality of alternative execution plans for the second query includes at least a first alternative execution plan that retrieves at least some data from a row-major table, and a second alternative execution plan that retrieves at least some data from a column-major in-memory compression unit.

13. One or more non-transitory computer-readable media storing instructions which, when executed by one or more processors, cause selection of execution plans for queries submitted to a dual-format database system by:

receiving, at a database server, a query that requires performance of particular operations;

wherein the particular operations include operations that access a particular set of data items;

wherein copies of the data items of the particular set of data items reside in a particular row-major table on persistent storage;

wherein additional copies of at least a subset of the particular set of data items reside, in volatile memory, in one or more column-major in-memory compression-units;

evaluating a plurality of alternative execution plans for performance of the particular operations;

wherein the plurality of alternative execution plans includes at least;

a first execution plan that performs a full table scan that accesses copies of data items in the one or more column-major in-memory compression-units;

a second execution plan that does not perform a full table scan that accesses copies of data items in the one or more column-major in-memory compression-units;

for each execution plan of the plurality of alternative execution plans, determining a cost associated with the execution plan;

wherein determining the cost for the first execution plan includes at least one of;

determining what fraction of the particular row-major table is duplicated in the one or more column-major in-memory compression units;

determining how many column-major in-memory compression-units will need to be scanned, as part of the full table scan, after pruning non-matching column-major in-memory compression-units based on (a) filter predicates of the query, and (b) minimum and maximum values maintained for each column-major in-memory compression-unit;

determining a decompression cost for decompressing those column-major in-memory compression-units to be used during performance of the full table scan;

determining a row-stitching cost that represents overhead required to produce row-major results from data items extracted from column-major in-memory compression-units;

or

determining a journal-scan cost for scanning a journal, maintained in volatile memory, that contains updates for data items that have become invalid in the one or more column-major in-memory compression-units;

selecting a particular execution plan, of the plurality of alternative execution plans, based on the cost determined for the particular execution plan;

obtaining a result set for the query by executing the particular execution plan; and

returning the result set of the query.

14. The one or more non-transitory computer-readable media of claim 13 wherein the second execution plan performs a full table scan that does not access copies of data items in the one or more column-major in-memory compression-units.

15. The one or more non-transitory computer-readable media of claim 13 wherein the second execution plan makes use of an index to perform the particular operations without performing any full table scan.

16. The one or more non-transitory computer-readable media of claim 13 wherein determining the cost for the first execution plan includes instructions for determining what fraction of the particular row-major table is duplicated in the one or more column-major in-memory compression units.

17. The one or more non-transitory computer-readable media of claim 13 wherein determining the cost for the first execution plan includes determining how many column-major in-memory compression-units will need to be scanned, as part of the full table scan, after pruning non-matching column-major in-memory compression-units based on (a) filter predicates of the query, and (b) minimum and maximum values maintained for each column-major in-memory compression-unit.

18. The one or more non-transitory computer-readable media of claim 13 wherein determining the cost for the first execution plan includes determining a decompression cost for decompressing those column-major in-memory compression-units to be used during performance of the full table scan.

19. The one or more non-transitory computer-readable media of claim 13 wherein determining the cost for the first execution plan includes determining a row-stitching cost that represents overhead required to produce row-major results from data items extracted from column-major in-memory compression-units.

20. The one or more non-transitory computer-readable media of claim 13 wherein determining the cost for the first execution plan includes determining a journal-scan cost for scanning a journal, maintained in volatile memory, that contains updates for data items that have become invalid in the column-major in-memory compression-units.

21. The one or more non-transitory computer-readable media of claim 13 wherein:

the database server is executing on one node of a multi-node database cluster;

the query specifies a join between that particular row-major table and a second row-major table;

the join requires particular data items from the particular row-major table to be joined with particular data items from the second row-major table;

copies of the particular data items from the particular row-major table are in a first column-major in-memory compression unit;

copies of the particular data items from the second row-major table are in a second column-major in-memory compression unit; and

determining the cost for the first execution plan further includes determining whether the first column-major in-memory compression unit is in the same node of the cluster as the second column-major in-memory compression unit.

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

receiving, at a database server, a query that requires performance of particular operations;

wherein the particular operations include operations that access particular data items;

wherein copies of the particular data items reside in a particular row-major table on persistent storage;

wherein additional copies of at least a subset of the particular data items reside, in volatile memory, in one or more column-major in-memory compression-units;

splitting the query into;

a first query that accesses portions of the particular table that are not duplicated in the one or more column-major in-memory compression units, and

a second query that accesses portions of the particular table that are duplicated in the one or more column-major in-memory compression units;

evaluating a first plurality of alternative execution plans for the first query;

wherein evaluating the first plurality of alternative execution plans includes determining costs for each of the first plurality of alternative execution plans;

evaluating a second plurality of alternative execution plans for the second query;

wherein evaluating the second plurality of alternative execution plans includes determining costs for each of the second plurality of alternative execution plans;

selecting a first particular execution plan, of the first plurality of alternative execution plans, based on the cost determined for the first particular execution plan;

selecting a second particular execution plan, of the second plurality of alternative execution plans, based on the cost determined for the second particular execution plan;

obtaining a result set for the query by;

executing the first particular execution plan to produce a first result set,

executing the second particular execution plan to produce a second result set, and

combining the first result set and the second result set into a combined result set for the query; and

returning the combined result set for the query.

23. The one or more non-transitory computer-readable media of claim 22 wherein the first particular execution plan uses a different access path to obtain data items from the particular table than the second particular execution plan.

24. The one or more non-transitory computer-readable media of claim 22, wherein the second plurality of alternative execution plans for the second query includes at least a first alternative execution plan that retrieves at least some data from a row-major table, and a second alternative execution plan that retrieves at least some data from a column-major in-memory compression unit.