System for multi-store analytics execution environments with storage constraints

• US 9,477,708 B2
• Filed: 11/06/2013
• Issued: 10/25/2016
• Est. Priority Date: 11/19/2012
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Hacigumus, Vahit Hakan, Sankaranarayanan, Jagan, LeFevre, Jeffrey Paul, Tatemura, Junichi, Polyzotis, Neoklis
• Primary Examiner(s): MACKES, KRIS E
• Application Number:
  US14/073,782
• Publication Number:
  US 20140207755A1
• Time in Patent Office: 1,084 Days
• US Class Current: 1/1
• 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;

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;

determining a multi-store execution plan P, as;

P=(G,ƒ

,t)

where G represents a directed acyclic graph (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; and

determining a multi-store configuration created after executing all plans prior to P_i by;

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 selecting subset of views for each store such that a storage budget and a transfer budget constraints are satisfied.

5. The method of claim 1, comprising retaining opportunistic views from previous versions of the query for future versions of the query.

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

7. The method of claim 6, comprising ensuring a predetermined set of views are moved to a correct engine early during workload processing.

8. The method of claim 6, comprising minimizing the cost of the workload sequence by moving views at a predetermined time in the sequence.

9. The method of claim 6, comprising identifying a sequence that provides the opportunity to move views at a predetermined time.

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

11. The method of claim 1, comprising determining:

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

cost(s,ƒ

(s),inputDesign(s,D)).

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

tcost(v,ƒ

(s_a),ƒ

(s_b)).

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

15. 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 objective function as: