This application claims priority to Provisional Application 61/909,364 filed 11/26/2013, the content of which is incorporated by reference.

BACKGROUND

Big data analytics is receiving significant interest from research and engineering organizations. The efforts from big data practitioners have helped advance the state-of-the-art in recent years. MapReduce (MR) (and Hadoop as the open source implementation of MR) has risen as the platform of choice for many of those practitioners as it offers scalability to large data sets, easy incorporation of new data sources, and the ability to query without lengthy schema definition processes. These approaches usually provide SQL or SQL-like (e.g., Hive) query APIs for easier programmability.

An evolutionary nature has been observed in how data analysts use analytical queries on big data. For example, an analyst wishes to identify top- 1000 wine lovers in Northern California, who could be a good target customer set for a promotion campaign. Obviously, many aspects in this request are vague, e.g., how to define a top customer; which data sets are the most appropriate to do the analysis, etc. Therefore, the analyst typically starts with a best-effort query and issues a sequence of refined queries before getting the satisfactory result. This will be increasingly the case with the lower and lower cost of querying big data, which enables more people, including non-database-experts, to perform analytics on big data. Naturally, a data analytics system that selectively reuses the results and intermediate results produced by previous queries, referred to as opportunistic views, could deliver a much greater performance for such workloads. In Hadoop, each MR job involves the materialization of intermediate results for the purpose of failure recovery. A typical Hive query spawns a multi-stage job that will involve several of such materializations. These materialized results are the artifacts of query execution and generated automatically as a by-product of query processing, which is the reason they are called opportunistic views. SUMMARY

Systems and methods are disclosed for query processing in a big data analytics platform by enumerating plans for a current query using a processor; building a dominance graph for the current query; for each plan, determining a regret value and a score for the plan based on the regret value and cost; and selecting query plans in an online fashion for query processing in big data analytics platforms where intermediate results are materialized and can be reused later.

In one implementation, a method named ManagedRisk, which, for each query, takes into account both the current cost of a query plan as well as whether a plan will produce useful opportunistic views for future query. Since it does not know or make assumptions on what queries it will receive in future, it gauges the usefulness of a query via previous queries.

ManagedRisk has a competitive ratio of (2 ^m -m-l) for a special case of the VQP problem where all queries are join-only, and a competitive ratio of for the general VQP problem where queries are SPJGA, where m is the maximum number of joins in a query, and N is the number of queries.

Advantages of the system may include one or more of the following. By carefully designing the way of computing the regret and the score of a query plan, we are able to develop a competitive online algorithm that processes each query without knowing future queries, and has a worst case performance guarantee.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows an exemplary process for performing Visionary Query Processing. FIG. 2 shows an exemplary system for performing Visionary Query Processing.

DESCRIPTION

The present system performs optimization of online query processing in big data analytics platforms such as Hadoop. Hadoop and similar systems usually materialize

intermediate results (referred to as "opportunistic views") of a query plan for fault tolerance, which can be reused to speed up future queries. Thus to minimize the total cost of a sequence of queries, each query should not simply use the currently cheapest, but should consider whether a plan will produce useful opportunistic views that may benefit future queries. We name this problem Visionary Query Processing.

The system chooses an execution plan for each query, in a setup where the result and intermediate results (opportunistic views) of the plan can be reused for future queries.

Specifically, given a schema, a cost model, and an online workload of SPJGA queries, we aim to find a plan for each query such that the total cost (which can be response time, dollar cost, etc.) is minimized for the whole workload. The challenge of the problem is that, if we choose plans in a greedy manner, i.e., for each query in the sequence, choose the plan with the minimum cost, it may ultimately lead to an unbounded cost compared with the ideal solution. In addition to the cost of a query plan, we should also consider whether a plan might produce opportunistic views that can potentially benefit future queries. However, queries are received in an online fashion, which means that at any point we do not know how many queries will be received in the future and what they are, and to make the solution widely applicable we should not make assumptions on that. The following example shows the challenge. C(P) is the cost of plan P , and c(s) is the cost of subexpression s .

Consider a sequence of join-only queries Q _} = A x B x C _} , Q ₂ = A x B x C ₂ , ^■■■ , and suppose there are two possible plans for each query Q _x : P _xl = (AB)C _X , which first joins A and B , and P _x2 = A(BC _x ) , which first joins B and C _x . c(A >< B) = 100 , c((A x B) x C _x ) = ε where ε is a negligibly small positive number, and C(P _x2 ) = 10 . If there are 10 queries or less in the sequence, the best solution is to use plan P _x2 for all queries; the total cost is lOn where n is the number of queries. Choosing plan P _xl for any Q _x will incur a cost of 100+ ε , which exceeds 10η . On the other hand, if there are 11 or more queries, ideally we should use plan P _n for the first query Q ₁ , which enables opportunistic view A >< B to be reused by other queries, so that other queries can all use plan P _A with a cost of ε . In this way, the total cost is 100 + ηε , which is lower than 10« .

If we use a greedy approach that chooses the plan with the lowest cost for the current query, we will always choose P _x2 for every query Q _x . Since n can be arbitrarily large and ε can be arbitrarily small, the total cost of such a greedy method is unbounded compared to the optimal cost.

We focus on selecting the query execution plans that would produce the most useful opportunistic views for the whole workload. It is important to note that the plan selection problem in this context has similarities and also significant differences the view/index selection and maintenance related problems.

FIG. 1 shows an exemplary process for performing Visionary Query Processing. The process uses as inputs previous queries, current query, and a cost model. The process then enumerates plans for the current query and builds a dominance graph for the current query. For each plan, the process determines a regret value, and for each plan, determine a score based on the regret value and cost. The process then generates as output a plan for the current query with the highest score. By carefully designing the way of computing the regret and the score of a query plan, we are able to develop a competitive online algorithm that processes each query without knowing future queries, and has a worst case performance guarantee.

A method named ManagedRisk, which, for each query, takes into account both the current cost of a query plan as well as whether a plan will produce useful opportunistic views for future query. Since it does not know or make assumptions on what queries it will receive in future, it gauges the usefulness of a query via previous queries. ManagedRisk has a competitive ratio of (2 ^m -m-\) for a special case of the VQP problem where all queries are join-only, and a competitive ratio of general VQP problem where queries are SPJGA, where m is the maximum number of joins in a query, and N is the number of queries.

We use capital letters A , B , etc., to denote tables, and small letters a , b , etc., to denote attributes. We do not discuss projections or group-bys, since they can be handled in the same way as predicates. For ease of illustration we assume that all joins are natural joins. Other join types can also be supported without changing the method. Thus a query can be represented by a set of relations accompanied by predicates. An example is

( _<l0 ,B, C) which represents a query that joins relations A , B , C with predicate A.a < 10.

We use P to denote a query plan, and C(P) to denote the cost of P . Each plan contains multiple subexpressions. A subexpression has one of the following two types: (1) join of two tables or views; (2) applying a predicate on a table or view.

Each subexpression produces an intermediate result (or simply result), also called opportunistic view (or simply view). These terms are used interchangeably. Formally, the notation for subexpressions and views are as follows. For simplicity, the following rules are for join-only queries, and general SPJGA queries are discussed later. Notations are summarized as follows:

TABLE <- A,B,C, ^{■■ ■}

VIEW <- TABLE TABLE

VIEW <- TABLE VIEW

SUBEX <- TABLE TABLE

SUBEX <- TABLE (VIEW)

SUBEX <- (VIEW) TABLE

SUBEX <- (VIEW) (VIEW)

Note that this notation can be ambiguous, e.g., AB can represent both a subexpression and a view. However, this is not a problem when the context is clear, and for clarity, we do not attempt to use more complicated notations.

For example, AB denotes a subexpression that joins tables A and B (or the view it produces); A(BC) denotes a subexpression that joins table A with the view of B x C ; ABC denotes a view of A x B x C .

The cost of a subexpression s is denoted by c(s) . For example, for a query (A,B, C) (i.e., natural join of three relations A , B , C with no predicates or projections), one possible plan is P = A x (B >< C) , which first joins B with C , and then joins the result with A . There are two subexpressions in this plan: BC and A(BC) . Thus C{P) = c(BC) + c{A(BC)) . We say that an method uses a subexpression s or produces the result/view of a subexpression s in query Q , if the plan chosen by the method for query Q contains s .

As a starting point, we first study a special case of the VQP problem, where each query is join-only with no predicates, projections or group-bys. We first present two straightforward methods, method Greedy and method Normalize, and show that they are not competitive even if each query involves at most two joins. Then we present method ManagedRisk, and prove its competitive ratio of 2 ^m - m + 1 where m is the largest number of joins involved in a query. At a high level, for each query, all three methods enumerate all possible plans, but use different criteria to decide which plan to choose.

For each query, a conventional baseline method called method Greedy can be used that chooses the plan with the lowest cost. Method Greedy is non-competitive even if each query involves at most two joins. The reason for its non-competitiveness is that, method Greedy processes each query in a selfish manner, and is not willing to take any risk. In particular, in Example 1, ^" risk" refers to using plan P _xl , since it is more expensive than P _x2 . Doing so

^" sacrifices" the efficiency of the current query, and is beneficial only if there are future queries that reuse opportunistic view AB . At the first glance, this seems what an method should do, since it does not know the future queries (unless it assumes that future queries will be similar as past queries, but we do not make such an assumption), and in the worst case, no future query will reuse AB . However, we will show in Section 3.3 when we introduce method ManagedRisk, that certain risk should be taken in order to obtain a competitive method.

Another conventional method Normalize can be used which attempts to solve the problem of method Greedy with the following idea: for each query, it not only considers which plan has the lowest cost, but also considers how many times the subexpressions in a plan have occurred before. It favors a query plan if it contains subexpressions that have occurred many times in previous queries.

Method Normalize chooses query plans based on how many previous queries can potentially benefit from the result of a subexpression, in addition to the cost of the query plan. It normalizes the cost of a subexpression based on the number of previous potential beneficiaries. To explain it we introduce the following definition. Subexpression Containment is discussed next. A query is said to contain a subexpression s , if s occurs in one of the possible plans for the query. We use s < Q to denote that subexpression s is contained in query Q . For example, a query (A,B, C, D) may contain subexpressions AB , BC , CD , AC , (AB)C , A(BCD) , (AB)(CD) , etc., depending on which two tables can be joined.

Note the difference between contained and used. A subexpression is contained in a query if it belongs to one of the possible plans; a subexpression is used in a query if it belongs to the plan selected by a certain method.

If s < Q , then if the result of s is available when Q is processed, and if we decide to choose a plan of Q that includes s , then this plan can reuse the result of s , and doest not need to pay for the cost of s , c{s) . Method Normalize favors a query plan if it includes a subexpression that is contained in many previous queries. Specifically, if a subexpression s is contained in k previous queries (including the current query), its normalized cost is c{s)lk . The normalized cost of a plan is the total normalized cost of all subexpressions in the plan, and method Normalize chooses the plan with the lowest normalized cost.

For the query sequence in Example 1, method Normalize uses plan P _x2 for the first 10 queries. When it processes the 11th query, the normalized cost of subexpression AB is 100/11 since it is contained in all 11 queries. Therefore, the normalized cost of plan P _l is 100/1 1 + ε , which is smaller than the normalized cost of plan P _{n 2} (10). Thus method Normalize uses plan

Ρ _ηΛ , which enables view AB to be reused by future queries, and avoids having an unbounded total cost, as method Greedy does.

Although Normalize works better than Greedy for this particular example, it is still noncompetitive even if each query involves at most two joins.

Consider a sequence of queries (A,B, C _l ), (A,B, C ₂ ),- - - , (A,B, C _n ) , and suppose that there are two possible plans for each query Q _x : P _xl = (AB)C _X , which first joins A and B , and P _x2 = A(BC _x ) , which first joins B and C _x . c(AB) = n . For l≤x≤n -l , C(P _x2 ) = s , and c((AB)C _x ) = ε . For the last query, C(P _n2 ) = 1 + 2ε , and c((AB)C _n ) = ε . For this query sequence, Normalize will choose plan P _x2 for the first n -l queries, incurring a cost of {η - \)ε . For the last query, the normalized cost of subexpression AB is 1 since it is contained in all n queries. Thus C(P _nl ) = Ι + ε < C(P _n2 ) = 1 + 2ε , and Normalize chooses plan P _nl . The total cost of Normalize is η + ηε . On the other hand, an optimal method would choose plan P _x2 for all queries for a total cost of \ + (η + \)ε . Thus Normalize has an unbounded cost compared to the optimal solution.

As we can see, Normalize takes a big risk on the last query by using plan (AB)C _n , for which it gets no reward since it is the last query. Next we present method ManagedRisk that addresses the problems in both methods discussed so far.

It can be seen from the two methods previously discussed that we need to take some risk, but the risk should somehow be controlled to avoid the situation in Example 3.2. The high level idea of method ManagedRisk is that it only takes a risk if, in case it makes a wrong decision, the damage can be ^" matched" by part of the cost of the optimal solution, which prevents the cost of the method to go unbounded. We introduce the concept of regret to capture this idea, and now we introduce our method, Method ManagedRisk, for the special case of the VQP problem (VQP- SP). The VQP problem addresses the situation where each query in the sequence is an SPJGA query. For simplicity we only discuss predicates. Projections and group-bys can be handled in the same way as predicates, since they essentially are the same problem: they all impose a partial order on the opportunistic views, such that a view with a predicate, projection and/or group-by can be reused by a query with the same or a stronger predicate, projection and/or group-by, but not weaker. More details on the VQP problem are discussed in depth below.

Regret for VQP-SP is detailed next. Let (¾, (¾, · · · be a sequence of join-only queries, and let P _; denote the plan selected for Q _; . For each query Q _; and each subexpression s < Q _; , the regret of s wrt Q _i , denoted by rg^s) or rg _Q (s) , is recursively defined as: if the result of s is not produced in any P l < j < i) , rSi(s) = ∑ max{C( .) -∑rg . (s'),0} (1) s'eP . If the result of s is available for reuse when Q _i is processed, i.e., it is produced in a query Q _] (l < j < i) , r _gi (s) = 0 .

Intuitively, rg _i (s) roughly represents the consequence of the fact that the result of s is not available when Q is processed, i.e., Q needs to pay a cost of c{s) if we wish to use s in Q 's plan. If rg^s) is large, we are motivated to use a plan for Q that produces the result of s , because even if this is a bad decision, its damage can be ^{" "} matched" by rg^s) . Note that the total regret of subexpressions used in each P. (i.e., rg . (s') in Eq. (1)) are subtracted from rg _; {s) . This is because rg . (s') has already influenced the choice of P. for query Q . (and hence matches the damage if it is a bad choice), and it should not make another impact on choosing a plan for Q _i .

There is a similar notion of regret (also called opportunity loss) in decision theory, which is defined as the additional payoff if a different action is chosen. Although the idea is somewhat similar, there are some key differences. First, decision theory aims to make a choice (such as determining the inventory level of a product) that minimizes the future regret if something goes wrong in future; while in our case, we do not analyze what can possibly happen in the future (because we don't know or make assumptions on how many queries we will receive in the future, and what they are). Instead, regret is computed from previous queries. Second, regret in decision theory is simply the difference in payoff, whereas in our problem the ^" difference in payoff cannot be easily computed. For example, what would be the cost difference if, when we processed a query Q in the sequence, an intermediate result had been available? It depends on many factors such as what are the other possible plans of Q , what are the other intermediate results that can be reused by Q , etc. Using a different plan for one query may affect the

^" difference in payoff of many other queries. Third, in our problem, regrets have cascading effects, e.g., the regret of a subexpression may influence our choice on a plan for one query, which in turn influence the regret of other subexpressions, as well as the choice on plans for future queries. Method ManagedRisk works as follows. For each query Q _i in the sequence it enumerates the plans of Q _i similar as Greedy and Normalize. For each plan P _i} , it uses a scoring function scoreiP _jj ) defined as score(P _ij ) = _j rg _i (s) - C(P _ij ) (2)

y

A plan that contains high-regret subexpressions and has a low cost gets a high score. ManagedRisk chooses the plan for Q _i with the maximum score among all plans for Q _i .

Consider the query sequence in Example 1. For the first 10 queries, ManagedRisk uses plan P _x2 , and pays a cost of 10 for each plan. We it processes the 11th query, we have rg _u (AB) = 100 , and the regrets of all other subexpressions are 0. Since rg _u (AB) - C((AB)C _u ) = -ε > -C(A(BC _U )) = -10, method ManagedRisk chooses plan P _l for this query. Note that even if the 11th query is the last query, which means using P _{u l} at this point is a bad choice, since rg _u (AB) is large enough, it is able to ^" match" the ^" damage" caused by using P _{u l} , which avoids the total cost of

ManagedRisk being arbitrarily worse than the optimal cost. In this example the cost of ManagedRisk is no more than twice the optimal cost.

Now consider the query sequence in Example 3.2. For \ < x < n - l , ManagedRisk uses plan P _x2 , incurring a cost of (« - \)ε , and thus rg _n {AB) = {η -\)ε . For the n th query, since the regrets of all other subexpression are 0, we have rg _n (AB) - C((AB)C _n ) < -C(A(BC _n )) thus ManagedRisk will use P _n2 . In this case, even though subexpression AB is contained in many queries seen before, ManagedRisk still doesn't use AB for the n th query, as the total cost of all previous queries that contain AB (i.e., rg _n {AB) ) is too small and thus using AB is too risky. ManagedRisk finds the optimal plans for this query sequence. Before analyzing the competitiveness of method ManagedRisk, we first prove that in order to get a competitive ratio better than O(N) (which is a trivial competitive ratio) where N is the number of queries in the sequence, the competitive ratio of an online method must be a function of # Join(S) , which is the maximum number of joins involved in a query in sequence S . There does not exist an online method for VQP-SP with a competitive ratio better than O(N) , N being the number of queries in the sequence, if the maximum number of joins involved in a query ( # Join(S) ) is unbounded.

In the following proofs we use ON to denote method ManagedRisk, and OFF to denote an optimal offline method. C _N (·) represents the cost paid by method ON for a query or query plan, and C _P (-) is the cost paid by method OFF for a query or query plan. Let P _N (Q) and P _F (Q) denote the plan chosen by ON and OFF, respectively, for query Q . Let m =# Join(S) . Since each query has at most m joins, each query has at most m + l relations, and has at most ml plans, each with a different join order.

For two queries Q _i and Q _j in the sequence, let Q _t Q _j represent that Q _i is before Q _j in the sequence. Let β β - represent that either Q _t = Q _j , or Q _t Q _j .

To prove the competitive ratio, we first present Lemma 3.4, which proves that the total regret of all subexpressions is bounded. Given a query sequence S , the plans selected by ON and OFF satisfy

∑rg(P _N (0) < (2 ^m - m - 1) · cost(OW) (3) where m is the maximum number of subexpressions in a query plan, and rg(P _N (Q)) is the total regret of all subexpressions in P _N (Q) wrt Q .

Next we introduce the concept of late subexpressions, based on which we define the damage of incorrect choices made by ON. [Late Subexpression] Given a sequence of queries S and the query plans generated by ON and OFF, a subexpression s is late if the result of s is produced by OFF for the first time in query Q , and the result of s is either never produced by ON, or is produced by ON in a query Q' , Q Q' . For each late subexpression s , let dif _s denote a set of queries such that for each Q e dif _s , OFF uses s (i.e., s e P _F (Q) ) but ON does not use s in either Q or any query before Q in the sequence. Let ldif _s denote the last query in dif _s . If ON uses s , let fst _s be the first query where ON uses s .

In the following, we give a total order to all late subexpressions. The late subexpressions are ordered by decreasing order of the index of Idif , i.e., if ldif _s ldif _s , , then s' is before s in the total ordering, i.e., s' < s . Ties are broken arbitrarily. Given the query plans selected by ON and OFF, for each query Q in the sequence, let L (Q) denote the set of late subexpressions contained in Q that are used by ON, and let L _n (Q) denote the set of late subexpressions contained in S that are used by OFF but not by ON, i.e., = Q, sislate, s e P _N (0} L _n (Q) = {s \ s < e,5islate,5 e P _F (Q), s £ P _N (Q)}

Also let f (Q) and f„(Q) be the first late subexpression in L (Q) and L _n (Q) , respectively, according to the total order defined previously.

Damage for VQP-SP is discussed next. Given a sequence of queries S and the query plans generated by ON and OFF, the damage of a subexpression s , denoted as dm _s , is defined as:

• If s is late, dm _s = dm^ + dm , where Q\Qedif _s , _s =f _n (Q)

C _N (fst _s ) - C _F (fst _s ); if/¾ exists

and? = f _y (fst _s )and _B (fst _s ) = 0

0; otherwise

• otherwise, dm _s = 0 .

Lemma 3.4 proves the validity of the definition of damage, i.e., the total damage of all subexpressions covers the cost difference between ON and OFF. Given a query sequence and the query plans generated by ON and OFF, the total damage of all subexpressions in the plans satisfies dm _s > cost(ON) - cost(OFF) (4)

Finally we prove the competitive ratio for method ManagedRisk. The competitive ratio of method ManagedRisk is (2 ^m - m + 1) for VQP-SP.

With the presence of predicates, we extend the notations of view and subexpression in as follows. OP <,>,=

<-

Attr a, ¾,< ,· · ·

<-

Const <- Real Numbers

Pred Attr OP Const

<-

Pred <- Pred & Pred

Pred Pred Pred

View Table _Pred

View View View

SubEx View^

For example, subexpression ABC denotes the operation of applying predicate p on the view of A x B x C (according to the last rule), and subexpression {AB )C _p ^ denotes a join of two views: AB _n and C .

When queries have predicates, a subexpression with a predicate can reuse a view with the same or a weaker predicate, but not a view with a stronger predicate. There are three naive adaptations of method ManagedRisk for handling predicates: (1) method Same, i.e., use the same way as before to calculate regrets of subexpressions and choose query plans. If a query contains but does not use a subexpression, it will only contribute to the regret of the subexpression with the exact same predicate; (2) method Weaker: if a query contains but does not use a subexpression, it contributes to the regrets of subexpressions with the same or weaker predicates; (3) method Stronger: the opposite of Weaker, i.e., if a query contains but does not use a subexpression, it contributes to the regrets of subexpressions with the same or stronger predicates.

Examples that illustrate these methods are provided in Appendix F. These examples show that none of these three methods is competitive. Next, we show how to extend method ManagedRisk to obtain a competitive method for the general VQP problem. The main idea is that when a subexpression s with a predicate occurs, subexpressions with weaker predicates get the same regret as s , and subexpressions with stronger predicates get a fraction of the regret of s .

We first introduce several necessary concepts for Adaptation of Method ManagedRisk.

Cognate Subexpressions: Two subexpressions s and s' are cognate, if the views produced by s and s' are joins of the same set of tables (possibly with different predicates).

For example, subexpressions A(BC _C<5 ) and A _a>l0 (BC) are cognate, because they are both joins of A and BC , although with different predicates.

Dominance: A subexpression s dominates a subexpression s' wrt query g. , denoted as S _j s' , if and only if: s and s' are cognate; s is contained in a query Q ^' Q _; and s is contained in a query Q ^' Q _t ; and the predicate in s is weaker than the predicate in s' . s directly dominates s' wrt Q . , denoted as s s' , if and only if: s s' , and there does not exist a subexpression s" , such that S _j s" and s" s' .

S _j s' represents that s = s' , or s s' .

When Q _j is clear from the context, we omit the subscript, and use s s' , s s' and s s' .

Dominance Graph: For a sequence of queries Q _x , Q ₂ , · · · , the dominance graph wrt query Q _i is a DAG G^V^ A^ . Vertices of G _i has a 1-1 mapping to all subexpressions contained in queries Q _l : Q _i whose results are not available when Q _i is processed. There is an arc from node u to v if the subexpression corresponding to u directly dominates that corresponding to v wrt

Let PATH(u,v, G) be the set of nodes on all directed paths from u to v in DAG G (including u but excluding v). Based on Definition 4.2, we define the normalization factor as follows.

[Normalization Factor] Consider a query Q _; , its dominance graph G _; , and two nodes u and v in G _i whose corresponding subexpressions are s' and s , where there is a directed path from u to v (i.e., s' s ). The normalization factor of s wrt s' and Q denoted as norm(s,s', Q _i ) or norm(s, s',i) , or simply norm{s, s') if the query is clear from the context, is defined as: norm( _S , _S ', Q _i ) = ∑ Π(^ _< » ^{+ 1} ) ( ⁵ )

? e PA TH ( w , v , G. ) w e p where deg ₀ (w) is the outdegree of w .

Next we introduce the new definition of regret for the general VQP problem. The explanation is given after the definition.

Regret, Last Regret for VQP: The regret of a subexpression s wrt query Q _i is recursively defined as

) = ∑ ^

Qj \j<i <Qj s normis'^^)

∑ (CiP _j ] -∑r _gj (s'")) - ∑lr _gi (s")

Qj\j<i,s"<Qj , s"'eP . where lrg _i (s) (also referred to as lrg _Q (s) ) is the Last Regret of s wrt Q _i , defined as rg _Q (s) -Q Q _t , s e P(Q)^rg _Q (s) > 0

ifOexists

lr _gi (s) (7)

0, otherwise

Also, define lrg(s) as: if s or a subexpression that dominates s is used for the first time in query Q _t , then lrg(s) = lrg _t (s) ; otherwise lrg(s) = 0 .

The last regret of s is the regret of s wrt the first query that uses s in the plan, if such a query exists. It is called ^" Tast regret" because it is the last query where the regret of s is nonzero. After s is used, rg(s) will be 0.

With the presence of predicates, there are three differences of the definition of regret. First, for each query that contains a subexpression s' s , its contribution to the regret of a subexpression s is divided by the normalization factor, norm(s,s' , Q _t ) . This ensures that if a s' s and s' is contained in a query, then s only gets a fraction of the regret of s' . Second, for each query that contains a subexpression s" , s s" , this query contributes to the regret of s . Third, if s" is a descendant of s and s" has already been used, then the last regret of s" (i.e., Irg^s") ) should be subtracted from the regret of s .

Note that when there's no predicate, Eq. (6) is equivalent as Eq. (1).

Now we are ready to introduce the new method ManagedRisk for the general VQP problem. It has two differences with the previous method ManagedRisk for join-only queries:

1. It uses Eq. (6) to compute regrets for subexpressions.

2. When it enumerates query plans, it also consider using dominating subexpressions that have occurred before. For example, for query Q = (A,B, C ) , i.e., join of tables A , B and

C with a predicate on table C , if a subexpression BC _p , is contained in a previous query, and p' is weaker than p , then ManagedRisk will consider a plan of Q that materializes BC , .

Next we analyze the competitiveness of ManagedRisk for the VQP problem.

We first prove that the total regret of all subexpressions are bounded, similar as Lemma 3.4. The proof idea is similar, and the proofs have much overlap, although the proof of Lemma 4.3 has several additional key steps that establish the additional factor of InN . Due to space constraint, the proof of Lemma 4.3 is presented in Appendix G.

Given a query sequence S , the plans generated by ON and OFF satisfy ∑rg(P _N (Q)) < (2 ^m - m - \)\nN - cost(OW) where m is the maximum number of joins in a query plan and N is the number of queries in the sequence.

For the purpose of the following proofs, we need to modify the definition of Damage as well as a few notations previously used in Section 3. The new definition of damage of a late subexpression s includes the cost differences between ON and OFF not only for queries that contain s , but also for queries that contain subexpressions dominated by s . To that end, we modify notation dif _s , which now refers to all queries where OFF uses s or a subexpression s' dominated by s , but ON has not used s or s' . ldif _s still refers to the last query in dif _s . The total ordering of all subexpressions is similar as before, except that if s s' and ldif _s = ldif _s , , then s < s' . f„(Q) , f _y (Q) and fst _s are the same as in Section 3.

With these modifications, the formal definition for Damage does not need to be rewritten, i.e., it is written the same way as Definition 3.4. Note that if a query contains a subexpression s , then it also contains a subexpression s' if s' s . And since s' < s (according to the modified definition of total order above), the damages of both subexpressions are counted in dm^ , rather than dm^ (unless there exists s" s' which is also late).

Given a query sequence and the query plans generated by ON and OFF, the total damage of all subexpressions in the plans satisfies dm _s > cost(ON) -cost(OFF) (8)

The competitive ratio of method ManagedRisk is (2 ^m - m - 1) In N +2 for the general VQP problem. Let s be a late subexpression, and let Q . = ldif _s . That is, Q . is the last query where OFF uses a subexpression s' , s s' , but ON does not use s' in or before g . . If s≠ s' , make a change to P _F (Q _j ) such that OFF uses s instead of s' . OFF still pays the same cost since s has already been used by OFF, and can be reused. Let P _F , (Q _j ) be the revised plan. Since ON chooses P _N (Q _j ) over P _F . (Q -) , we have score(P _N (Q _j ))≥ score(P _F . (Q,)) rg _j (P _F (Q _j )) - C _N (P _F ^, (Q _j )) < rg _j (P _N (Q _j )) - C _N (P _N (Q _j )) rg _j (PAQ _j )) + C _N (P _N (Q _j )) - rg _j (P _N (Q _j )) < C _N (P Q _j )) (9)

Since P _F (Q ) contains s , we have r _gj (PAQ _j ))>r _gj (s)> ∑ (C _N (Q)-rg(P _N (Q)))

Q\Q dif _s -Q

Thus rg _j (P _? (Q _j )) + C _N (P _N (Q _j )) - r _gj . (P _N (Q . ))

≥ ∑ (CAQ)-rg(PAQ))) (10)

Q\Qedif _s ,s=f _n (Q)

≥dm + ∑ (C _F (Q)-rg(P _N (Q)))

Q\Qedif _s ,s=f _n (Q)

From Eq. (9) and (10): dm^ <C _N (PAQj))+ ∑rg(P _N (Q))

Q dif _s

The cost of Pp iQ _j ) is part of cost( OFF) . For each subexpression s' e P _F {Q _j )■ _> ^{we can} prove in a similar way as the corresponding part in the proof of Theorem 3.4, that if it has been used by OFF but not by ON, then its cost is only used to match the dm^ , and will not be used to match dm ^(l) of any other subexpressions:

• if ON and OFF both use s' for the first time in Q _} , then they both pay c(s') in Q _} ; if ON and OFF have both used s' before, they both do not pay for s' in Q _} .

• if ON has used s before Q . but OFF hasn't, then ON pays zero but OFF pays c(s') in Q _j .

• if OFF has used s' before Q . but ON hasn't, since the subexpressions are sorted by decreasing order of Idif , and s = f _n (Q .) , ldif _s , < ldif _s , which means Q . is also the last query in dif _s , . This means that c(s') is not counted in dm^) of any other subexpression s" .

Therefore, dm < ∑ rg(P _N (Q)) (11)

Qedif _s ,s=f _n (Q) For dnv ' , for each s , C _N (fst _s ) - C _F (fst _s ) comprises the costs of those subexpressions in f _y {fst _s ) , i.e., those subexpressions that have been used by OFF before fst _s , and that are used by ON for the first time in fst _s . Thus for each subexpression s' e P _N (fst(s)) , ON and OFF both pays for c(s') . Thus

s

From Eq. (1 1) and (12), and the fact that for any two subexpressions s and s' , sets {Q \ Q e dif _s , s = f _n (0} and {Q \ Q e dif _s , ,s' = f„ (0} do not overlap, we have

≤ ⁵ ∑ rg(P _N (Q)) + co _S t(OFF)

Qedif _s ,s=f _n (Q)

<∑rg(P _N (Q)) + cost(OFF)

≤ (2 ^m - m - l)lnN · cost(OFF) + cost(OFF)

Besides using opportunistic views, a big data platform that processes analytical workloads may also benefit from proactively building views. If we anticipate that there will likely be future queries that will benefit from a view , we may build this view proactively when the system is idle, rather than waiting till we actually receive a query that needs to use .

Which views to build proactively, and when to build them, are out of the scope of this paper. It can either be decided manually be a system administrator, or automatically using some heuristics, such as looking at which views are useful for a window of recent queries [10, 6]. In this subsection we discuss that, if views are proactively built during the process of the query sequence, how it will affect the competitiveness of method ManagedRisk.

We assume that given a certain query sequence, the proactive views to be built are fixed, i.e., it does not depend on the method for processing the query sequence. Each proactive view can be represented as (v, , which means that view v is built after query Q _i is processed (hence v can be reused by queries later than Q _t ). An online method does not know what views will be proactively created in the future and when will they be created, just like it doesn't know what queries it will see in the future. On the other hand, an optimal offline method knows all queries and proactive views in advance.

The following theorem shows that there is no need to handle proactively views in a special way. We can run method ManagedRisk and treats each proactive view as a normal query (except that there is only one possible plan for such queries), and the competitive ratio is still valid. The competitive ratio of method ManagedRisk is (2 ^m - m -l) lnN + 2 when there are proactive views.

As a starting point we discuss a special case of the VQP problem (referred to as VQP- SP), where each query is join-only (no predicates, projections or group-bys). We show that two baseline methods, method Greedy and method Normalize, are not competitive even if each query has at most two joins. We prove that for VQP-SP (and thus for VQP as well), any competitive method must have a competitive ratio which is a function of m , where m is the maximum number of joins in a query in the sequence. If m is unlimited, there does not exist an online method with a non-trivial competitive ratio. For the VQP-SP problem we develop an method named ManagedRisk, analyze its competitiveness and prove that it has a competitive ratio of 2 ^m - m + l . Note that the competitive ratio is independent of the number of queries in the workload. We then study the general VQP problem where each query is SPJGA. When there are predicates, projections and group-bys in the query, an opportunistic view v is useful for a query Q only if v 's predicate, projection and group-by is equal to or weaker than Q 's predicate, projection and group-by. We extend method ManagedRisk for the general VQP problem, and prove that it has a competitive ratio of (2 ^m - m - l) lnN + 2 where N is the number of queries in the sequence. In the end we discuss the case where there are views proactively built during the query sequence, and prove that the presence of proactively built views does not change the competitive ratio of Method ManagedRisk.

This system performs visionary query processing on big data analytics platforms. Hadoop and similar systems usually materialize intermediate results of a query plan for fault tolerance, and they can be reused to speed up future queries. Given a sequence of SPJGA queries, we tackle the online optimization problem of how to choose a query plan for each query, such that the total cost of all query plans is minimized. To do so, each query should not simply use the currently cheapest plan (doing so is uncompetitive even for very simple instances of the problem), but should consider whether a plan will produce useful opportunistic views that may benefit future queries. We present Method ManagedRisk, which has a competitive ratio of 2 ^m - m + l when queries are join-only, and a competitive ratio of (2 ^m - m - l) lnN + 2 when queries are SPJGA, where m is the maximum number of joins involved in a query, and N is the number of queries in the sequence.

The invention may be implemented in hardware, firmware or software, or a combination of the three. Preferably the invention is implemented in a computer program executed on a programmable computer having a processor, a data storage system, volatile and non-volatile memory and/or storage elements, at least one input device and at least one output device.

Each computer program is tangibly stored in a machine-readable storage media or device (e.g., program memory or magnetic disk) readable by a general or special purpose programmable computer, for configuring and controlling operation of a computer when the storage media or device is read by the computer to perform the procedures described herein. The inventive system may also be considered to be embodied in a computer-readable storage medium, configured with a computer program, where the storage medium so configured causes a computer to operate in a specific and predefined manner to perform the functions described herein.

The invention has been described herein in considerable detail in order to comply with the patent Statutes and to provide those skilled in the art with the information needed to apply the novel principles and to construct and use such specialized components as are required. However, it is to be understood that the invention can be carried out by specifically different equipment and devices, and that various modifications, both as to the equipment details and operating procedures, can be accomplished without departing from the scope of the invention itself.