System for evolutionary analytics

1. A method to support evolutionary queries, comprising:

retaining artifacts from previous query or workflow execution runs materialized views;

providing a gray-box model of a user defined function (UDF) to support search for rewrites of the UDF;

automatically producing a rewrite that uses artifacts to reduce workflow execution time;

incrementally searching the space of rewrites to create explode and searching a minimum amount of a solution space to find an optimal rewrite;

supporting simultaneous evolution along three dimensions including workflow, user and data evolution; and

determining the optimal rewrite r* of W by:

performing an efficient search of rewrites for all targets in W and outputs a globally optimal rewrite for W n ; and

enumerating one or more candidate views for a single target based on their potential to produce a low-cost rewrite of the target.

2. The method of claim 1 , comprising extending the rewrite language to include the UDF.

3. The method of claim 1 , comprising determining an optimistic cost function OptCost(W i , v) that takes a candidate view v and target W i as inputs and providing a lower-bound on a rewrite r i of W i using v, where r i is a rewrite of W i that uses the candidate view v and where a property of the lower bound is determined as:

OptCost( W i ,v )≦Cost( r i ).

4. The method of claim 3 , comprising creating the search space of candidate views ordered by OptCost, providing the OptCost of a next candidate view, and determining a rewrite of the target using the next candidate view.

5. The method of claim 1 , comprising producing a rewrite r* of W composed of rewrites found at multiple targets in W, wherein the computed rewrite r* has a minimum cost among rewrites in the same class.

6. The method of claim 1 , comprising:

using W as a rewrite for a plan;

spawning n concurrent search problems at each target in W and iteratively finding a better rewrite, wherein each iteration chooses one target W i and examines a candidate view at W i ; and

using the better rewrite results for pruning a search space of other targets in W.

7. The method of claim 1 , comprising optimizing execution of UDFs over unstructured data sets.

8. The method of claim 1 , comprising optimizing for evolution of user workflows.

9. A system to support evolutionary analytical queries, comprising:

a processor configured for enabling an optimizer receiving a query from the input and translating the query into an execution plan, the processor coupled to a storage, and input and output connections;

the processor configured for enabling a query rewriter coupled to the optimizer to support simultaneous evolution along three dimensions including workflow, user and data evolution;

storage with a materialized view metadata store coupled to the query rewriter, the store containing information about materialized views including view definitions and standard data statistics used in query optimization;

the processor configured for enabling a query execution engine within the computer coupled to the query rewriter to execute the query; and

the processor configured for a rewriter for determining the optimal rewrite r* of W by:

performing an efficient search of rewrites for all targets in W and outputs a globally optimal rewrite for W n ; and enumerating one or more candidate views for a single target based on their potential to produce a low-cost rewrite of the target.

10. The system of claim 9 , wherein queries are expressed against base data including large logs and queries contain UDFs.

11. The system of claim 9 , wherein the optimizer provides cost estimates for UDFs admitted to the system.

12. The system of claim 9 , wherein the optimizer generates a plan with two types of annotations on each plan node: (1) a logical expression of its computation and (2) an estimated execution cost.

13. The system of claim 9 , wherein the rewriter uses the logical expression in the annotation when searching for rewrites for the output of a node.

14. The system of claim 13 , wherein the expression consists of relational operators or UDFs.

15. The system of claim 9 , for each rewrite found during the search, the rewriter utilizes the optimizer to obtain a plan and estimated cost.

16. The system of claim 9 , wherein by-products of query processing during query execution are retained as opportunistic materialized views and stored as an opportunistic physical design configuration.

17. The system of claim 9 , comprising computer code for determining an optimistic cost function OptCost(W i , v) that takes a candidate view v and target W i as inputs and providing a lower-bound on a rewrite r i of W i using v, where r i is a rewrite of W i that uses the candidate view v and where a property of the lower bound is determined as:

OptCost( W i ,v )≦Cost( r i ).

18. The system of claim 17 , comprising computer code for creating the search space of candidate views ordered by OptCost , providing the OptCost of a next candidate view, and determining a rewrite of the target using the next candidate view.

19. The system of claim 9 , comprising computer code for:

using W as a rewrite for a plan;

spawning n concurrent search problems at each target in W and iteratively finding a better rewrite, wherein each iteration chooses one target W, and examines a candidate view at W i ; and

using the better rewrite results for pruning a search space of other targets in W.