Compile-time optimizations of queries with SQL spreadsheet

• US 7,809,712 B2
• Filed: 11/02/2006
• Issued: 10/05/2010
• Est. Priority Date: 06/20/2001
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Folkert, Nathan, Gupta, Abhinav, Witkowski, Andrew, Bellamkonda, Srikanth, Subramanian, Sankar, Bozkaya, Tolga
• Primary Examiner(s): Vo; Tim T.
• Assistant Examiner(s): Ahn; Sangwoo
• Application Number:
  US11/592,470
• Publication Number:
  US 20070055661A1
• Time in Patent Office: 1,433 Days
• Field of Search: None
• US Class Current: 707/713
• 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 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 said second query are satisfied;

if said one or more criteria for rewriting said first query or said 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;

wherein the steps of the method are performed by one or more computing devices.

2. The method of claim 1, wherein:

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

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

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

said 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.

3. The method of claim 1, wherein:

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

said one or more predicates include 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 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; and

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

4. The method of claim 1, wherein:

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

said one or more predicates include 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; and

the one or more criteria include, 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.

5. The method of claim 4, 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.

6. The method of claim 5, 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 said second query that restricts said dimension column based on a disjunction of said subset of values and the particular predicate.

7. The method of claim 6, 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.

8. The method of claim 4, 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.

9. The method of claim 1, 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.

10. The method of claim 1, 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.

11. The method of claim 2, 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.

12. 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 query that uses a window function;

wherein the steps of the method are performed by one or more computing devices.

13. 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;

wherein the steps of the method are performed by one or more computing devices.

14. The method of claim 13, 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.

15. The method of claim 14, 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.

16. The method of claim 14, 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 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.

17. The method of claim 16, 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.

18. The method of claim 14, 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 at least one pair of nodes; and

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

19. The method of claim 13, 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.

20. A computer-readable volatile or non-volatile medium storing one or more sequences of instructions for rewriting queries, which instructions when executed by one or more processers cause performance of steps comprising:

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 said second query are satisfied;

if said one or more criteria for rewriting said first query or said 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.

21. The computer-readable volatile or non-volatile medium of claim 20, wherein:

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

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

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

said 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 instructions that cause performance of the step of making modifications to said second query includes instructions which, when executed by the one or more processors, cause pushing said predicate into said second query.

22. The computer-readable volatile or non-volatile medium of claim 20, wherein:

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

said one or more predicates include 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 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; and

the one or more sequences of instructions further comprise instructions which, when executed by the one or more processors, cause extending said particular predicate based on the union of the bounding predicates constructed for said set of formulas.

23. The computer-readable volatile or non-volatile medium of claim 20, wherein:

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

said one or more predicates include 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; and

the one or more criteria include, 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.

24. The computer-readable volatile or non-volatile medium of claim 23, wherein the instructions that cause performance of the step of making modifications to said second query include instructions which, when executed by the one or more processors, cause performance of the steps of:

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.

25. The computer-readable volatile or non-volatile medium of claim 24, wherein the instructions that cause performance of the step of making modifications to said second query include instructions which, when executed by the one or more processors, cause performance of the steps of:

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

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

26. The computer-readable volatile or non-volatile medium of claim 25, wherein the instructions that cause performance of the step of making modifications to said second query include instructions which, when executed by the one or more processors, cause performance of the steps of:

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.

27. The computer-readable volatile or non-volatile medium of claim 23, wherein the instructions that cause performance of the step of making modifications to said second query include instructions which, when executed by the one or more processors, cause making said modifications when said one or more criteria are satisfied.

28. The computer-readable volatile or non-volatile medium of claim 20, wherein the instructions that cause performance of the step of making modifications to said second query involving one or more predicate conditions include instructions which, when executed by the one or more processors, cause making modifications to said second query involving one or more predicate conditions.

29. The computer-readable volatile or non-volatile medium of claim 20, 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; and

the instructions that cause performance of the step of making modifications to said second query involving one or more predicate conditions include instructions which, when executed by the one or more processors, cause 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.

30. The computer-readable volatile or non-volatile medium of claim 21, 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.

31. A computer-readable volatile or non-volatile medium storing one or more sequences of instructions for rewriting queries, which instructions when executed by one or more processers cause performance of steps comprising:

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 query that uses a window function.

32. A computer-readable volatile or non-volatile medium storing one or more sequences of instructions for rewriting queries, which instructions when executed by one or more processers cause performance of steps comprising:

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.

33. The computer-readable volatile or non-volatile medium of claim 32, wherein:

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

the instructions that cause performance of the step of rewriting include instructions which, when executed by the one or more processors, cause pruning said first formula from said first set of formulas.

34. The computer-readable volatile or non-volatile medium of claim 33, 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 instructions that cause performance of the step of pruning are 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.

35. The computer-readable volatile or non-volatile medium of claim 33, 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 instructions that cause performance of the step of rewriting are performed 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 instructions that cause performance of the step of rewriting include instructions which, when executed by the one or more processors, cause performance of the steps of;

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

(B) for each 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.

36. The computer-readable volatile or non-volatile medium of claim 35, 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 one or more sequences of instructions further include instructions which, when executed by the one or more processors, cause 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.

37. The computer-readable volatile or non-volatile medium of claim 33, wherein the one or more sequences of instructions include instructions which, when executed by the one or more processors, cause performance of the steps of:

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 at least one pair of nodes; and

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

38. The computer-readable volatile or non-volatile medium of claim 32, wherein:

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

the instructions that cause performance of the step of rewriting include instructions which, when executed by the one or more processors, cause 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.