Compile-time optimizations of queries with SQL spreadsheet

• US 7,177,855 B2
• Filed: 11/06/2003
• Issued: 02/13/2007
• 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: Gupta, Abhinav, Witkowski, Andrew, Bellamkonda, Srikanth, Subramanian, Sankar, Bozkaya, Tolga, Folkert, Nathan
• Primary Examiner(s): Alam; Hosain
• Assistant Examiner(s): Ahn; Sangwoo
• Application Number:
  US10/704,192
• Publication Number:
  US 20040133568A1
• Time in Patent Office: 1,195 Days
• Field of Search: 707/2, 707/3, 707/4, 707/5
• US Class Current: 707/718
• 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 sets of formulas defined by 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 on 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

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

2. The method of claim 1, wherein the step of grouping includes performing the following steps while said set of 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 computer-readable storage medium carrying one or more sequences of instructions for determining orders for evaluating sets of formulas defined by queries, which instructions, executed by one or more processors, cause the one or more processors to perform:

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 on 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

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

5. The computer-readable storage medium of claim 4, wherein the instructions that cause grouping include instructions which, executed by the one or more processors, cause the one or more processors to perform the following steps while said set of 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.

6. The computer-readable storage medium of claim 4, wherein the instructions that cause grouping include instructions which, executed by the one or more processors, cause the one or more processors to perform means for grouping based on said one or more criteria.