Run-time optimizations of queries with SQL spreadsheet

• US 20040133567A1
• Filed: 11/06/2003
• Published: 07/08/2004
• Est. Priority Date: 06/20/2001
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Gupta, Abhinav, Witkowski, Andrew, Bellamkonda, Srikanth, Subramanian, Sankar, Bozkaya, Tolga, Folkert, Nathan
• Granted Patent: US 7,761,403 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: G06F 40/18 of spreadsheets form-filling G06F40/174
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database
• CPC Class Codes: Y10S 707/99939 Privileged access

Abstract

Described herein are optimizations and execution strategies for spreadsheet extensions to SQL. The partitioning of data, as specified in a spreadsheet clause, provides a way to parallelize the computation of spreadsheet and to provide and improve scalability. Even if the partitioning is not explicitly specified in the spreadsheet clause, the database optimizer can automatically infer the partitioning in some cases. Efficient hash based access structures on relations can be used for symbolic array addressing, enabling fast computation of formulas. When rewriting SQL statements, formulas whose results are not referenced in outer blocks can be removed from the spreadsheet clause, thus removing unnecessary computations. The predicates from other query blocks can be moved inside query blocks with spreadsheets clauses, thus considerably reducing the amount of data to be processed. Conditions for validity of this transformation are given.

Claims

1. A method for processing a query, the method comprising the steps of:

examining said query;

wherein said query evaluates to a relation;

wherein the query defines an array and a set of formulas that reference the array;

wherein the array has one or more dimensions that correspond to columns of the relation;

wherein the query includes a clause specifying at least one partition column of said relation by which to partition the relation into partitions;

assigning a plurality of partitions to processing elements for processing, wherein the relation is partitioned into said plurality of partitions based on a set of one or more partition columns that include said at least one partition column; and

processing said query based on the assignment of said plurality of partitions.

2. The method of claim 1,

a dimension of said one or more dimensions corresponds to a dimension column in said relation;

each formula of said set of formulas has a right side and a left side;

the method further includes the steps of;

determining whether each formula of said set of formulas satisfy one or more criteria, wherein the one or more criteria include that for each value of the dimension referenced by the left side by said each formula, the value referenced on the right side of said each formula for said dimension is the same as said each value referenced on the left side;

if said each formula of said set of formulas satisfy one or more criteria, then performing the step of assigning based on a set of one or more partition columns that include said at least one partition column and the dimension column.

3. The method of claim 2, wherein:

the one or more criteria include that for each formula of said set of formulas, said each formula references all values of the dimension on the left side of said each formula; and

if said each formula of said set of formulas satisfy the one or more criteria, then rewriting said second query by rewriting;

the clause to specify the dimension, and

the set of formulas by removing references to the dimension.

4. The method of claim 2, wherein:

the one or more criteria include that for each formula of said set of formulas said each formula references all values of the dimension on the left side of said each formula; and

if said each formula of said set of formulas does not satisfy said one or more criteria, then rewriting said second query by rewriting;

the clause to specify the dimension.

5. The method of claim 4, wherein:

the second query specifies an operation that can cause rows corresponding to cells of said array to be inserted;

wherein the set of formulas includes a formula that references a specific value in said dimension;

wherein the step of assigning a plurality of partitions to processing elements includes assigning a particular partition to a particular processing element;

before said particular processing element evaluates a particular formula, determining based on said specific value whether said particular formula modifies data that belongs to the partition; and

if said formula does not modify data that belongs to the partition, then foregoing execution of the particular formula.

6. The method of claim 5, including means for determining based on said specific value whether said formula modifies data that belongs to the particular partition.

7. The method of claim 1, including means for assigning a plurality of partitions to processing elements for processing and processing said query based on the assignment.

8. A method for determining an order for evaluating a set of formulas defined by a query, the method comprising the steps of:

examining said query;

wherein said query evaluates to a relation;

wherein the query defines an array and the set of formulas, wherein the set of formulas reference the array;

wherein the array has one or more dimensions that correspond to columns of the relation;

grouping the set of formulas into levels, wherein each level includes one or more formulas of said set of formulas, wherein the levels satisfy a first set of one or more criteria, wherein said first set of one or more criteria include;

evaluation of any formula in each level of said levels does not depend;

on another formula in the same level, and

on another formula in a level higher than said each level;

evaluating the formulas in each of the levels, wherein;

the one or more formulas in the level are evaluated before another formula in a higher level is evaluated; and

if said each level includes one or more formulas that specify an aggregate function, computing each aggregate function specified by the one or more formulas before evaluating a formula in said each level.

9. The method of claim 8, wherein:

determining if the set of formulas satisfy second one or more criteria, wherein the second one or more criteria include;

no formula in said set of formulas references a range of values in each dimension of said one or more dimension; and

each aggregate function specified by the set of formulas has an inverse;

if said set of formulas satisfy second one or more criteria, then;

before evaluating any formula of the set of formulas, computing each aggregate function specified by the set of formulas to generate a result for said each aggregate function;

after computing each aggregate function and in response to detecting that evaluation of a formula from said set of formulas changes a measure of a cell upon which the result of a particular aggregate function depends, modifying the result for said particular aggregate function by applying the current value of the measure and the inverse of the old value of the measure.

10. The method of claim 9, further including:

storing in association with a particular cell modified by a formula from said set of formulas, a list of aggregate functions affected by changes to the measure of said particular cell; and

using said list to determine which aggregate functions have a result affected by a change to the measure of said particular cell.

11. The method of claim 8, wherein the step of evaluating the formulas in each of the levels includes a means for evaluating the formulas.

12. A method for evaluating a set of formulas defined by a query, the method comprising the steps of:

examining said query;

wherein said query evaluates to a relation;

wherein the query defines an array and the set of formulas;

wherein the set of formulas reference the array;

wherein the array has one or more dimensions that correspond to columns of the relation;

establishing a subset of said set of formulas as not being acyclic;

grouping the set of formulas into levels, wherein each level includes one or more formulas of said set of formulas,

wherein the step of grouping includes assigning each formula of said subset to consecutive levels;

wherein the levels satisfy a first set of one or more criteria, wherein said first set of one or more criteria include;

if a particular level of said levels belongs to the consecutive levels, evaluation of the formula in the particular level does not depend on a formula in a higher level that does not belong to the consecutive levels;

if the particular level of said levels does not belong to the consecutive levels, then;

evaluation of any formula in the particular level of said levels does not depend;

on another formula in the particular level, and

on another formula in a level higher than said particular level; and

evaluating the set of formulas in an order based on said levels, wherein the step of evaluating includes determining whether the formulas in the subset converge.

13. The method of claim 12, wherein the step of determining whether said formulas in the subset converge includes:

as a first iteration, evaluating each formula in the consecutive levels;

determining as N a number of cells modified during the first iteration;

performing no more than N−

12 iterations, wherein in each iteration of the N−

12 iterations, each formula in the consecutive levels is evaluated;

detecting that the formulas in the consecutive levels converge after a particular iteration; and

foregoing additional iterations in response to detecting that the formulas in the consecutive levels converge.

14. The method of claim 13, wherein:

a first flag is associated with cells of the array referenced by the formulas in the consecutive levels;

evaluation of a particular formula during a particular iteration of said no more than N−

12 iterations causes setting of a particular first flag associated with a cell that is referenced by the particular formula but not modified by the particular formula; and

in response to detecting that the value of the cell for which the particular first flag has been set was changed by the evaluation of a formula made in the particular iteration, performing another iteration of said N−

12 iterations.

15. The method of claim 14, wherein:

a second flag in addition to said first flag is associated with cells of the array referenced by the formulas in the consecutive levels; and

unsetting one of the first and second flags associated with a cell of the array when setting the other of the first and second flags.

16. The method of claim 12, wherein the method further includes the steps of:

generating a node graph with edges between nodes;

wherein the nodes each correspond to a particular formula of said set of formulas;

wherein an edge from a first node to a second node represents that the formula associated with the first node is dependant on the formula associated with the second node; and

wherein the step of establishing a subset of said set of formulas as not being acyclic includes using the node graph to determine that the subset corresponds to a set of strongly connected components.

17. The method of claim 12, wherein the step of evaluating the set of formulas includes a means for determining whether said formulas in the subset converge.

18. A method for accessing data needed to process a query, the method comprising the steps of:

examining said query;

wherein said query evaluates to a relation with rows;

wherein the query defines an array with cells and a set of formulas that reference the array;

wherein the array has one or more dimensions that correspond to a column of the relation as a dimension column;

wherein each cell of said cells corresponds to a row in said relation;

wherein the query includes a clause specifying at least one partition column of said relation by which to partition the relation into partitions that each contain rows within said relation;

accessing data for each partition in a multi-level hash access structure having a first level and a second level and a plurality of tables;

wherein the first level correlates each partition of said partitions to a particular table of said plurality of tables based on values in said at least one partition column, said particular table containing records holding data for the cells of said array the correspond to said each partition; and

wherein the second level correlates records within the particular table for a partition to values in the one or more dimension columns.

19. The method of claim 18, wherein the method includes:

determining a number of partitions for which to evaluate said set of formulas based on an estimate of;

(1) an amount of memory available to store a set of tables from said plurality of tables, and

(2) an amount memory needed to store said set of tables;

in response to determining said number of partitions, evaluating formulas for said number of partitions.

20. The method of claim 18, wherein the method further includes:

determining which rows are required to evaluate said set of formulas; and

building a table of said plurality of tables based on the rows required to evaluate said set of formulas.

21. The method of claim 20, wherein the step of determining which rows are required includes means for determining which rows are required based on a bounding rectangle.

22. The method of claim 18, wherein records within a table of said plurality of tables are clustered based on said one or more dimension columns and the at least one partition column.

23. The method of claim 18, wherein the method includes:

evaluating a particular formula of said set of formulas;

wherein said particular formula references a cell and, for said cell, a value for each of said one or more dimension columns; and

accessing the multi-level hash access structure based on said value for each of said one or more dimension columns.

24. The method of claim 18, the method including performing one or more operations involving records in the particular table, said one or more operations including at least one from a set that includes probe, update, upsert, insert, and scan.

25. The method of claim 18, wherein said multi-level access structure includes means for a two-level hash access structure.