Compile-time optimizations of queries with SQL spreadsheet

• US 20040133568A1
• 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,177,855 B2
• Time in Patent Office: Days
• US Class Current: 707/3
• CPC Class Codes: G06F 16/24 Querying
• CPC Class Codes: G06F 16/244 Grouping and aggregation
• 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/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact 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 determining orders for evaluating a set of formulas defined by a queries, the method comprising the steps of:

examining a 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 a subset of formulas of the set of formulas require cells corresponding to a range of values of said dimension;

grouping, based one or more criteria, the set of formulas into groups of formulas,

wherein the groups are associated with an order, and

wherein said one or more criteria include that, for each group of said groups of formulas, evaluation of any formula in said each group does not depend;

on another formula in said each group, and

does not depend on another formula in a group higher in said order than said each group; and

evaluating in said order each group of said groups of formula.

2. The method of claim 1, wherein the step of grouping includes performing the following steps while said set formulas is not empty:

establishing as members of an independent subset one or more formulas from said set of formulas that are not dependant on other formulas in said set of formulas;

if said independent subset contains only formulas that reference single cells, then establishing the independent subset as a new group of formulas higher in order than any other group currently in said group of formulas;

if said independent subset does not contain only formulas that reference single cells, establishing the independent subset as a new group higher in order than any other group currently in said group of formulas; and

removing the new group of formulas from the set of formulas.

3. The method of claim 1, wherein the step of grouping includes means for grouping based on said one or more criteria.

4. A method for rewriting queries, the method comprising the computer implemented steps of:

examining a first query that references a relation to which a second query evaluates;

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

wherein the array has one or more dimensions;

wherein the first query includes one or more predicates;

wherein the second query does not include the one or more predicates;

determining whether one or more criteria for rewriting said first query or second query are satisfied; and

if said one or more criteria for rewriting said first query or second query are satisfied, then making, based on said one or more predicates included in said first query, modifications to said second query involving one or more predicate conditions; and

generating a rewritten query based on the modifications to said second query.

5. The method of claim 4, wherein:

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

said one or more predicates includes a particular predicate that references said dimension column;

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

the one or more criteria include for each value of the dimension referenced by the left side, the value referenced on the right side for the dimension is the same as said each value referenced on the left side; and

the step of making modifications to said second query includes pushing said predicate into said second query.

6. The method of claim 4, wherein:

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

said one or more predicates includes a particular predicate that references said dimension column;

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

each formula of said set of formulas references array cells of said second array and dimension values of the one or more dimensions;

for each formula, constructing a bounding predicate that;

references the dimension values referenced by said each formula, and

bounds the array cells that are referenced by said each formula;

extending said particular predicate based on the union of the bounding predicates constructed for said set of formulas.

7. The method of claim 4, wherein:

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

said one or more predicates includes a particular predicate that references said dimension column;

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

wherein each formula of said set of formulas references a second array;

the one or more criteria includes, for each formula of said set of formulas;

(A) for each value of the dimension referenced on the left side;

(1) the value of the dimension on the right side is the same as the value of the dimension referenced on the left side, or

(2) the value of the dimension on the right side depends on a value of particular cell in the second array and on a function of the value of the dimension referenced on the left side;

(B) said each formula specifies an operation that does not modify the second array.

8. The method of claim 7, wherein the step of making modifications to said second query includes:

wherein a first subset of values in said dimension column satisfy said particular predicate;

wherein a second subset of values from said dimension column are contained in said second array;

generating a third query whose results include the first subset of values and the second subset of values; and

adding a predicate to the second-query that restricts said dimension column to the results of the third query.

9. The method of claim 8, wherein the step of making modifications to said second query includes:

determining the subset of values that are contained in said second array; and

adding a predicate to the second query that restricts said dimension column based on a disjunction of said subset of values and the particular predicate.

10. The method of claim 9, wherein the step of making modifications to said second query includes:

determining a set of cells in said second array required to satisfy said particular predicate;

wherein the set of formulas reference the set of cells; and

replacing the first set of formulas with a second set of formulas that reference the values of the set of cells.

11. The method of claim 7, wherein the step of making modifications to said second query includes a means for making said modifications when said one or more criteria are satisfied.

12. The method of claim 4, wherein the step of making modifications to said second query involving one or more predicate conditions includes a means for making modifications to said second query involving one or more predicate conditions.

13. The method of claim 4, wherein

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

said one or more predicates includes a particular predicate that references said dimension column;

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

the step of making modifications to said second query involving one or more predicate conditions includes a means for making modifications to the second query when, for at least one formula of said set of formulas, a value of the dimension referenced by the left side is different than a value referenced on the right side for the dimension.

14. The method of claim 5, wherein

said second query specifies an upsert operation;

and

the one or more criteria include that said first query filters out any row upserted by said second query.

15. A method for rewriting queries, the method comprising the computer implemented steps of:

examining a first query that defines an array and a formula that references the array;

wherein the formula has a right side and a left side;

determining whether one or more criteria for rewriting said first query are satisfied;

wherein said one or more criteria include that;

said left side and said right side do not depend on each other, and

all aggregate functions referenced on the right side can be rewritten using a window function; and

if said one or more criteria for rewriting said first query are satisfied, then generating a rewritten formula that uses a window function.

16. A method for rewriting queries, the method comprising the computer implemented steps of:

examining a first query that references a relation to which a second query evaluates;

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

wherein the first query includes one or more predicates;

wherein the second query does not include the one or more predicates;

generating a rewritten set of formulas by rewriting, based on said one or more predicates, said first set of formulas to produce said rewritten set of formulas;

and

generating a rewritten query based on the rewritten set of formulas.

17. The method of claim 16, wherein:

the first set of formulas includes a first formula and the rewritten set of formulas does not include a first formula; and

the step of rewriting includes pruning said first formula from said first set of formulas.

18. The method of claim 17, wherein:

wherein each formula of said first set of formulas;

evaluates one or more cells in said array, and

modifies as one or more cells in said array a measure column in said relation;

the step of pruning is performed in response to detecting a set of conditions that include;

(1) the one or more cells modified by said first formula are not evaluated by any other formula of said first set of formulas, and

(2) the one or more cells modified by said first formula are filtered out by said one or more predicates or the measure column is not referenced by said first query.

19. The method of claim 17, wherein:

each formula of said first set of formulas;

evaluates one or more cells in said array, and

modifies as one or more cells in said array a measure column in said relation;

the step of rewriting is based on a set of conditions for a given formula of said first set of formulas that include a first condition, a second condition, and a third condition, wherein;

(1) the first condition is that one or more cells modified by the given formula of said first set of formulas are not evaluated by any other formula of said first set of formulas,

(2) the second condition is that the one or more cells modified by the given formula are filtered out by said one or more predicates, and

(3) the third condition is that the measure column is not referenced by said first query;

the step of rewriting includes;

(A) establishing a first subset of said first set of formulas that meet the first condition;

(B) for each of formula of said first subset, pruning said each formula from said first set of formulas if said each formula meets either the second condition or the third condition;

(C) after performing step B, establishing a second subset of the remaining formulas in said first set of formulas that meet the first condition.

20. The method of claim 19, wherein:

after performing step (B), the first subset includes a second formula that does not meet either the second condition or the third condition;

the method includes performing after step (B) but before step (C), the step of rewriting said second formula to produce a third formula in place of said second formula that modifies a portion of the cells in said array that would have been modified by said second formula.

21. The method of claim 17, wherein the method includes the steps of:

means for generating a graph with nodes and an edge between at least one pair of nodes of said nodes, wherein the edge represents a dependency between the formulas that correspond to the pair; and

means for pruning, based on said graph, formulas from said first set of formulas.

22. The method of claim 16, wherein:

the first set of formulas includes a first formula and the rewritten set of formulas does not include the first formula; and

the step of rewriting includes rewriting said first formula to produce a second formula that modifies a portion of the cells in said array that would have been modified by said first formula.