System for Multi-store Analytics Execution Environments with Storage Constraints

• US 20140207755A1
• Filed: 11/06/2013
• Published: 07/24/2014
• Est. Priority Date: 11/19/2012
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Hacigumus, Vahit Hakan, Sankaranarayanan, Jagan, Tatemura, Junichi, Polyzotis, Neoklis, LeFevre, Jeffrey Paul
• Granted Patent: US 9,477,708 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Systems and methods are disclosed for managing a multi-store execution environment by applying opportunistic materialized views to improve workload performance and executing a plan on multiple database engines to increase query processing speed by leveraging unique capabilities of each engine by enabling stages of a query to execute on multiple engines, and by moving materialized views across engines.

Claims

1. A method for managing an execution environment, comprising:

applying opportunistic materialized views to improve workload performance; and

executing a plan on multiple database engines to increase query processing speed by enabling stages of a query to execute on multiple engines, and by moving materialized views across engines.

2. The method of claim 1, comprising moving views across engines by piggybacking moves along a query execution path.

3. The method of claim 1, comprising minimizing an execution time of a sequence of queries by creating beneficial physical designs through the movement of views during stages of query execution.

4. The method of claim 1, comprising generating a view selection policy for a use-case of evolving

queries.

5. The method of claim 4, wherein the materialized views are opportunistic, and wherein the view selection policy only considers dropping views to reclaim storage.

6. The method of claim 1, comprising selectingsubset of views for each store such that a storage budget and a transfer budget constraints are satisfied.

7. The method of claim 1, comprising retaining opportunistic views from previous versions of the query that will be beneficial for future versions of the query.

8. The method of claim 1, comprising generating a sequence of multi-store execution plans P1, P2, . . . Pn that minimizes a cost of executing an input query sequence.

9. The method of claim 8, comprising ensuring the set of views most beneficial to the workload are moved to a correct engine early during workload processing.

10. The method of claim 8, comprising minimizing the cost of the workload sequence by moving views at the right time in the sequence.

11. The method of claim 8, comprising identifying a sequence that provides the opportunity to move views at the right time.

12. The method of claim 1, comprising benefit computations to a sequence of the next m queries, rather than all remaining queries to optimize locally using a sliding window over a future query sequence.

13. The method of claim 1, comprising determining a multi-store execution plan P is defined in the following way:

P=(G,ƒ

,t)

where G represents the DAG for a plan, and is ordered topologically with a vertex in G corresponding to a stage s in plan P,ƒ

;

PE is a mapping function that maps a stage in P to an execution engine in E. t;

VE is a transfer function that indicates transfer of views in V to an engine in E, and a stage sε

P may be executed on any engine.

14. The method of claim 13, comprising determining:

16. The method of claim 13, comprising determining a multi-store configuration created after executing all plans prior to P_i by:

17. The method of claim 13, comprising determining a cost of executing a stage on an engine as:

cost(s,ƒ

(s),inputDesign(s,D))

18. The method of claim 13, comprising determining a cost to transfer a view is given by:

tcost(v,ƒ

(s_a),ƒ

(s_b))

19. The method of claim 14, comprising determining a cost for a plan P given a multistore configuration D as:

20. The method of claim 1, comprising optimizing an objective function given as input a sequence of queries, q₁, q₂, . . . , q_n and a multi-store design D, generating a sequence of multi-store execution plans P₁, P₂, . . . , P_n that minimizes the cost of executing the input query sequence with the objective function as: