# Patent

## Title
Visionary query processing in Hadoop utilizing opportunistic views

## Abstract

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.

## Background
This application claims priority to Provisional Application 61/909,364 filed Nov. 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 (2m−m−1) for a special case of the VQP problem where all queries are join-only, and a competitive ratio of (2m−m−1)lnN 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 Q1=ABC1, Q2=ABC2, . . . , and suppose there are two possible plans for each query Qx: Px1=(AB)Cx, which first joins A and B, and Px2=A(BCx), which first joins B and Cx. c(AB)=100, c((AB)Cx)=∈ where ∈ is a negligibly small positive number, and C(Px2)=10. If there are 10 queries or less in the sequence, the best solution is to use plan Px2 for all queries; the total cost is 10n where n is the number of queries. Choosing plan Px1 for any Qx will incur a cost of 100+∈, which exceeds 10n. On the other hand, if there are 11 or more queries, ideally we should use plan P11 for the first query Q1, which enables opportunistic view AB to be reused by other queries, so that other queries can all use plan Px1 with a cost of ∈. In this way, the total cost is 100+n∈, which is lower than 10n.
If we use a greedy approach that chooses the plan with the lowest cost for the current query, we will always choose Px2 for every query Qx. Since n can be arbitrarily large and c 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 (2m−m−1) for a special case of the VQP problem where all queries are join-only, and a competitive ratio of (2m−m−1)lnN 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.
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

(Aa<10,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 BC; ABC denotes a view of ABC.
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(BC), 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 2m−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 Px1, since it is more expensive than Px2. 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 sQ 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 sIQ, 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)/k. 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 Px2 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 P11,1 is 100/11+∈, which is smaller than the normalized cost of plan P11,2 (10). Thus method Normalize uses plan P11,1, 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 non-competitive even if each query involves at most two joins.
Consider a sequence of queries (A,B,C1),(A,B,C2), . . . , (A,B,Cn), and suppose that there are two possible plans for each query Qx: Px1=(AB)Cx, which first joins A and B, and Px2=A(BCx), which first joins B and Cx. c(AB)=n. For 1≦x≦n−1, C(Px2)=∈, and c((AB)Cx)=∈. For the last query, C(Pn2)=1+2∈, and c((AB)Cn)=∈.
For this query sequence, Normalize will choose plan Px2 for the first n−1 queries, incurring a cost of (n−1)∈. For the last query, the normalized cost of subexpression AB is 1 since it is contained in all n queries. Thus C(Pn1)=1+∈<C(Pn2)=1+2∈, and Normalize chooses plan Pn1. The total cost of Normalize is n+n∈. On the other hand, an optimal method would choose plan Px2 for all queries for a total cost of 1+(n+1)∈. 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)Cn, 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 Q1, Q2, . . . be a sequence of join-only queries, and let Pi denote the plan selected for Qi. For each query Qi and each subexpression sQi, the regret of s wrt Qi, denoted by rgi(s) or rgQi(s), is recursively defined as: if the result of s is not produced in any Pj(1≦j<i),




  
    
      
        
          
            rg
            i
          
          ⁡
          
            (
            s
            )
          
        
        =
        
          
            ∑
            
              
                
                  Q
                  j
                
                ❘
                
                  j
                  <
                  i
                
              
              ,
              
                s
                ⊲
                
                  Q
                  j
                
              
            
          
          ⁢
          
            max
            ⁢
            
              {
              
                
                  
                    C
                    ⁡
                    
                      (
                      
                        P
                        j
                      
                      )
                    
                  
                  -
                  
                    
                      ∑
                      
                        
                          s
                          ′
                        
                        ∈
                        
                          P
                          j
                        
                      
                    
                    ⁢
                    
                      
                        rg
                        j
                      
                      ⁡
                      
                        (
                        
                          s
                          ′
                        
                        )
                      
                    
                  
                
                ,
                0
              
              }
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




If the result of s is available for reuse when Qi is processed, i.e., it is produced in a query Qj(1≦j<i), rgi(s)=0.
Intuitively, rgi(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 rgi(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 rgi(s). Note that the total regret of subexpressions used in each Pj (i.e., rgj(s′) in Eq. (1)) are subtracted from rgi(s). This is because rgj(s′) has already influenced the choice of Pj for query Qj (and hence matches the damage if it is a bad choice), and it should not make another impact on choosing a plan for Qi.
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 Qi in the sequence it enumerates the plans of Qi similar as Greedy and Normalize. For each plan Pij, it uses a scoring function score(Pij) defined as




  
    
      
        
          score
          ⁡
          
            (
            
              P
              ij
            
            )
          
        
        =
        
          
            
              ∑
              
                s
                ∈
                
                  P
                  ij
                
              
            
            ⁢
            
              
                rg
                i
              
              ⁡
              
                (
                s
                )
              
            
          
          -
          
            C
            ⁡
            
              (
              
                P
                ij
              
              )
            
          
        
      
    
    
      
        (
        2
        )
      
    
  




A plan that contains high-regret subexpressions and has a low cost gets a high score. ManagedRisk chooses the plan for Qi with the maximum score among all plans for Qi.
Consider the query sequence in Example 1. For the first 10 queries, ManagedRisk uses plan Px2, and pays a cost of 10 for each plan. We it processes the 11th query, we have rg11(AB)=100, and the regrets of all other subexpressions are 0. Since

rg11(AB)−C((AB)C11)=−∈>C(A(BC11))=−10,

method ManagedRisk chooses plan P11,1 for this query. Note that even if the 11th query is the last query, which means using P11,1 at this point is a bad choice, since rg11(AB) is large enough, it is able to “match” the “damage” caused by using P11,1, 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 1≦x≦n−1, ManagedRisk uses plan Px2, incurring a cost of (n−1)∈, and thus rgn(AB)=(n−1)∈. For the nth query, since the regrets of all other subexpression are 0, we have

rgn(AB)−C((AB)Cn)<−C(A(BCn))

thus ManagedRisk will use Pn2. 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., rgn(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.







TABLE 1





Summary of Symbols
















(r1, r2, . . .)
a query that joins source tables r1, r2, . . .


Q < Q′
query Q is before Q′ in the sequence


Q ≦ Q′
Q = Q′ or Q < Q′


cost(•)
total cost of all query plans selected by ON/OFF


PN/F(Q)
plan selected by ON/OFF for query Q


c(s)
cost of a subexpression s


C(P)
cost of a plan P


CN/F(P)
cost or a plan P paid by ON/OFF


CN/F(Q)
CN/F(PN/F(Q))


un(P)
subexpressions in P whose results have not been



produced


rgi(s)
regret of s wrt the ith query


rgQ(s)
regret of s wrt query Q


rgi(P)
regret of plan P wrt the ith query


rg(P)
regret of plan P wrt the current query


fy(Q)
first late subexpression in Q used for the first



time by ON in Q


fn(Q)
first late subexpression in Q used by OFF, but



not used by ON in or before Q


difs
the set of queries where OFF uses s but ON doesn't,



and the result of s is not available for ON


ldifs
the last query in difs


fsts
the first query where ON uses s


dms
damage of subexpression s









In the following proofs we use ON to denote method ManagedRisk, and OFF to denote an optimal offline method. CN(•) represents the cost paid by method ON for a query or query plan, and CF(•) is the cost paid by method OFF for a query or query plan. Let PN(Q) and PF(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+1 relations, and has at most m! plans, each with a different join order.
For two queries Qi and Qj in the sequence, let QiQj represent that Qi is before Qj in the sequence. Let Qi′Qj represent that either Qi=Qj, or QiQj.
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




  
    
      
        
          
            ∑
            
              Q
              ∈
              S
            
          
          ⁢
          
            rg
            ⁡
            
              (
              
                
                  P
                  N
                
                ⁡
                
                  (
                  Q
                  )
                
              
              )
            
          
        
        ≤
        
          
            (
            
              
                2
                m
              
              -
              m
              -
              1
            
            )
          
          ·
          
            cost
            ⁡
            
              (
              OFF
              )
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




where m is the maximum number of subexpressions in a query plan, and rg(PN(Q)) is the total regret of all subexpressions in PN(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′, QQ′. For each late subexpression s, let difs denote a set of queries such that for each Q∈difs, OFF uses s (i.e., s∈PF(Q)) but ON does not use s in either Q or any query before Q in the sequence. Let ldifs denote the last query in difs. If ON uses s, let fsts 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 ldif, i.e., if ldifsldifs′, 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 Ly(Q) denote the set of late subexpressions contained in Q that are used by ON, and let Ln(Q) denote the set of late subexpressions contained in S that are used by OFF but not by ON, i.e.,

Ly(Q)={s|sQ,sislate,s∈PN(Q)}

Ln(Q)={s|sQ,sislate,s∈PF(Q),s∉PN(Q)}

Also let fy(Q) and fn(Q) be the first late subexpression in Ly(Q) and Ln(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 is defined as:

    
    
        If s is late, dms=dms(1)+dms(2), where
    
    





  
    
      dm
      s
      
        (
        1
        )
      
    
    =
    
      
        
          ∑
          
            
              Q
              ❘
              
                Q
                ∈
                
                  dif
                  s
                
              
            
            ,
            
              s
              =
              
                
                  f
                  n
                
                ⁡
                
                  (
                  Q
                  )
                
              
            
          
        
        ⁢
        
          
            C
            N
          
          ⁡
          
            (
            Q
            )
          
        
      
      -
      
        
          C
          F
        
        ⁡
        
          (
          Q
          )
        
      
    
  




  
    
      dm
      s
      
        (
        2
        )
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    
                      
                        
                          C
                          N
                        
                        ⁡
                        
                          (
                          
                            fst
                            s
                          
                          )
                        
                      
                      -
                      
                        
                          C
                          F
                        
                        ⁡
                        
                          (
                          
                            fst
                            s
                          
                          )
                        
                      
                    
                    ;
                  
                
                
                  
                    if
                    ⁢
                    
                      
                    
                    ⁢
                    
                      fst
                      s
                    
                    ⁢
                    
                      
                    
                    ⁢
                    exists
                  
                
              
            
          
        
        
          
            
              
                and
                ⁢
                
                  
                
                ⁢
                s
              
              =
              
                
                  
                    
                      f
                      y
                    
                    ⁡
                    
                      (
                      
                        fst
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  and
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      f
                      n
                    
                    ⁡
                    
                      (
                      
                        fst
                        s
                      
                      )
                    
                  
                
                =
                Ø
              
            
          
        
        
          
            
              
                
                  
                    0
                    ;
                  
                
                
                  otherwise
                
              
            
          
        
      
    
  



    
    
        otherwise, dms=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




  
    
      
        
          
            ∑
            s
          
          ⁢
          
            dm
            s
          
        
        ≥
        
          
            cost
            ⁡
            
              (
              ON
              )
            
          
          -
          
            cost
            ⁡
            
              (
              OFF
              )
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




Finally we prove the competitive ratio for method ManagedRisk. The competitive ratio of method ManagedRisk is (2m−m+1) for VQP-SP.
With the presence of predicates, we extend the notations of view and subexpression in as follows.

















OP
←
<,>,=



Attr
←
a,b,c,...



Const
←
Real Numbers



Pred
←
Attr OP Const



Pred
←
Pred & Pred



Pred
←
Pred | Pred



View
←
Table Pred



View
←
View View



SubEx
←
View Pred










For example, subexpression ABCp denotes the operation of applying predicate p on the view of ABC (according to the last rule), and subexpression (ABp1)Cp2 denotes a join of two views: ABp1 and Cp2.
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(BCc<5) and Aα>10(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 Qj, denoted as sjs′, i, if and only if: s and s′ are cognate; s is contained in a query Q′Qi and s is contained in a query Q′′Qi; and the predicate in s is weaker than the predicate in s′.
s directly dominates s′ wrt Qj, denoted as sjs′, if and only if: sjs′, and there does not exist a subexpression s′′, such that sjs′′ and s′′js′.
sjs′ represents that s=s′, or sjs′.
When Qj 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 Q1, Q2, . . . , the dominance graph wrt query Qi is a DAG Gi(Vi,Ai). Vertices of Gi has a 1-1 mapping to all subexpressions contained in queries Q1:Qi whose results are not available when Qi is processed. There is an arc from node u to v if the subexpression corresponding to u directly dominates that corresponding to v wrt Qi.
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 Qi, its dominance graph Gi, and two nodes u and v in Gi 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 Qi, denoted as norm(s, s′, Qi) 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
              
            
            )
          
        
        =
        
          
            ∑
            
              p
              ∈
              
                
                  PATH
                  ⁡
                  
                    (
                    
                      u
                      ,
                      v
                      ,
                      
                        G
                        i
                      
                    
                    )
                  
                
                ⁢
                w
              
              ∈
              P
            
          
          ⁢
          
            
              ∏
              
                w
                ∈
                p
              
            
            ⁢
            
              (
              
                
                  
                    deg
                    o
                  
                  ⁡
                  
                    (
                    w
                    )
                  
                
                +
                1
              
              )
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




    
    
        where dego(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 Qi is recursively defined as




  
    
      
        
          
            rg
            i
          
          ⁡
          
            (
            s
            )
          
        
        =
        
          
            
              ∑
              
                
                  
                    Q
                    j
                  
                  ❘
                  
                    j
                    <
                    i
                  
                
                ,
                
                  
                    s
                    ′
                  
                  ⊲
                  
                    Q
                    j
                  
                
                ,
                
                  
                    s
                    ′
                  
                  ⁢
                  s
                
              
            
            ⁢
            
              
                
                  C
                  ⁡
                  
                    [
                    
                      P
                      j
                    
                    ]
                  
                
                -
                
                  
                    ∑
                    
                      
                        s
                        ′′′
                      
                      ∈
                      
                        P
                        j
                      
                    
                  
                  ⁢
                  
                    
                      rg
                      j
                    
                    ⁡
                    
                      (
                      
                        s
                        ′′′
                      
                      )
                    
                  
                
              
              
                norm
                ⁡
                
                  (
                  
                    
                      s
                      ′
                    
                    ,
                    s
                    ,
                    
                      Q
                      i
                    
                  
                  )
                
              
            
          
          +
          
            
              ∑
              
                
                  
                    Q
                    j
                  
                  ❘
                  
                    j
                    <
                    i
                  
                
                ,
                
                  
                    s
                    ′′
                  
                  ⊲
                  
                    Q
                    j
                  
                
                ,
                
                  ss
                  ′′
                
              
            
            ⁢
            
              (
              
                
                  C
                  ⁡
                  
                    [
                    
                      P
                      j
                    
                    ]
                  
                
                -
                
                  
                    ∑
                    
                      
                        s
                        ′′′
                      
                      ∈
                      
                        P
                        j
                      
                    
                  
                  ⁢
                  
                    
                      rg
                      j
                    
                    ⁡
                    
                      (
                      
                        s
                        ′′′
                      
                      )
                    
                  
                
              
              )
            
          
          -
          
            
              ∑
              
                
                  s
                  ′′
                
                ❘
                
                  ss
                  ′′
                
              
            
            ⁢
            
              
                lrg
                i
              
              ⁡
              
                (
                
                  s
                  ′′
                
                )
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




where lrgi(s) (also referred to as lrgQi(s)) is the Last Regret of s wrt Qi, defined as




  
    
      
        
          
            lrg
            i
          
          ⁡
          
            (
            s
            )
          
        
        =
        
          {
          
            
              
                
                  
                    
                      
                        
                          
                            rg
                            Q
                          
                          ⁡
                          
                            (
                            s
                            )
                          
                        
                        ,
                        
                          
                            s
                            .
                            t
                            .
                            
                              
                            
                            ⁢
                            Q
                          
                          ≺
                          
                            Q
                            i
                          
                        
                        ,
                      
                    
                    
                      
                        s
                        ∈
                        
                          
                            
                              P
                              ⁡
                              
                                (
                                Q
                                )
                              
                            
                            ⁢
                            
                              
                            
                            ⁢
                            and
                            ⁢
                            
                              
                            
                            ⁢
                            
                              
                                rg
                                Q
                              
                              ⁡
                              
                                (
                                s
                                )
                              
                            
                          
                          >
                          0
                        
                      
                    
                  
                
              
            
            
              
                
                  if
                  ⁢
                  
                    
                  
                  ⁢
                  Q
                  ⁢
                  
                    
                  
                  ⁢
                  exists
                
              
            
            
              
                
                  
                    
                      
                        0
                        ,
                      
                    
                    
                      otherwise
                    
                  
                
              
            
          
        
      
    
    
      
        (
        7
        )
      
    
  




Also, define lrg(s) as: if s or a subexpression that dominates s is used for the first time in query Qi, then lrg(s)=lrgi(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 “last regret” because it is the last query where the regret of s is non-zero. 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′,Qi). 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., lrgi(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,Cp), i.e., join of tables A, B and C with a predicate on table C, if a subexpression BCp′ is contained in a previous query, and p′ is weaker than p, then ManagedRisk will consider a plan of Q that materializes BCp′.
    
    


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 ln N. 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




  
    
      ∑
      
        Q
        ∈
        S
      
    
    ⁢
    
      rg
      ⁡
      
        (
        
          
            P
            N
          
          ⁡
          
            (
            Q
            )
          
        
        )
      
    
  
  ≤
  
    
      (
      
        
          2
          m
        
        -
        m
        -
        1
      
      )
    
    ⁢
    ln
    ⁢
    
      
    
    ⁢
    
      N
      ·
      
        cost
        ⁡
        
          (
          OFF
          )
        
      
    
  




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 difs, 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, still refers to the last query in difs. The total ordering of all subexpressions is similar as before, except that if s s′ and ldifs=ldifs′, then s<s′. fn(Q), fy(Q) and fsts 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 dms(1), rather than dms(1) (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




  
    
      
        
          
            ∑
            s
          
          ⁢
          
            
          
          ⁢
          
            d
            ⁢
            
              
            
            ⁢
            
              m
              s
            
          
        
        ≥
        
          
            cost
            ⁡
            
              (
              ON
              )
            
          
          -
          
            cost
            ⁡
            
              (
              OFF
              )
            
          
        
      
    
    
      
        (
        8
        )
      
    
  




The competitive ratio of method ManagedRisk is (2m−m−1) in N+2 for the general VQP problem. Let s be a late subexpression, and let Qj=ldifs. That is, Qj is the last query where OFF uses a subexpression s′, s s′, but ON does not use s′ in or before Qj. If s≠s′, make a change to PF(Qj) such that OFF uses s instead of s′. OFF still pays the same cost since has already been used by OFF, and can be reused. Let PF′(Qj) be the revised plan. Since ON chooses PN(Qj) over PF′(Qj), we have

score(PN(Qj))≧score(PF′(Qj))

rgj(PF′(Qj))−CN(PF′(Qj))≦rgj(PN(Qj))−CN(PN(Qj))

rgj(PF′(Qj))+CN(PN(Qj))−rgj(PN(Qj))≦CN(PF′(Qj))  (9)

Since PF′(Qj) contains s, we have




  
    
      rg
      j
    
    ⁡
    
      (
      
        
          P
          
            F
            ′
          
        
        ⁡
        
          (
          
            Q
            j
          
          )
        
      
      )
    
  
  ≥
  
    
      rg
      j
    
    ⁡
    
      (
      s
      )
    
  
  ≥
  
    
      ∑
      
        Q
        ❘
        
          Q
          ∈
          
            
              dif
              s
            
            -
            
              Q
              j
            
          
        
      
    
    ⁢
    
      
    
    ⁢
    
      (
      
        
          
            C
            N
          
          ⁡
          
            (
            Q
            )
          
        
        -
        
          rg
          ⁡
          
            (
            
              
                P
                N
              
              ⁡
              
                (
                Q
                )
              
            
            )
          
        
      
      )
    
  




Thus




  
    
      
        
          
            
              rg
              j
            
            ⁡
            
              (
              
                
                  P
                  
                    F
                    ′
                  
                
                ⁡
                
                  (
                  
                    Q
                    j
                  
                  )
                
              
              )
            
          
          +
          
            
              C
              N
            
            ⁡
            
              (
              
                
                  P
                  N
                
                ⁡
                
                  (
                  
                    Q
                    j
                  
                  )
                
              
              )
            
          
          -
          
            
              rg
              j
            
            ⁡
            
              (
              
                
                  P
                  N
                
                ⁡
                
                  (
                  
                    Q
                    j
                  
                  )
                
              
              )
            
          
        
        ≥
        
          
            ∑
            
              
                Q
                ❘
                
                  Q
                  ∈
                  
                    dif
                    s
                  
                
              
              ,
              
                s
                =
                
                  
                    f
                    n
                  
                  ⁡
                  
                    (
                    Q
                    )
                  
                
              
            
          
          ⁢
          
            (
            
              
                
                  C
                  N
                
                ⁡
                
                  (
                  Q
                  )
                
              
              -
              
                rg
                ⁡
                
                  (
                  
                    
                      P
                      N
                    
                    ⁡
                    
                      (
                      Q
                      )
                    
                  
                  )
                
              
            
            )
          
        
        ≥
        
          
            d
            ⁢
            
              
            
            ⁢
            
              m
              s
              
                (
                1
                )
              
            
          
          +
          
            
              ∑
              
                
                  Q
                  ❘
                  
                    Q
                    ∈
                    
                      dif
                      s
                    
                  
                
                ,
                
                  s
                  =
                  
                    
                      f
                      n
                    
                    ⁡
                    
                      (
                      Q
                      )
                    
                  
                
              
            
            ⁢
            
              (
              
                
                  
                    C
                    F
                  
                  ⁡
                  
                    (
                    Q
                    )
                  
                
                -
                
                  rg
                  ⁡
                  
                    (
                    
                      
                        P
                        N
                      
                      ⁡
                      
                        (
                        Q
                        )
                      
                    
                    )
                  
                
              
              )
            
          
        
      
    
    
      
        (
        10
        )
      
    
  




From Eq. (9) and (10):




  
    d
    ⁢
    
      
    
    ⁢
    
      m
      s
      
        (
        1
        )
      
    
  
  ≤
  
    
      
        C
        N
      
      ⁡
      
        (
        
          
            P
            
              F
              ′
            
          
          ⁡
          
            (
            
              Q
              j
            
            )
          
        
        )
      
    
    +
    
      
        ∑
        
          Q
          ∈
          
            dif
            s
          
        
      
      ⁢
      
        rg
        ⁡
        
          (
          
            
              P
              N
            
            ⁡
            
              (
              Q
              )
            
          
          )
        
      
    
  




The cost of PF′(Qj) is part of cost(OFF). For each subexpression s′∈PF′(Qj), 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 dms(1), and will not be used to match dm(1) of any other subexpressions:

    
    
        if ON and OFF both use s′ for the first time in Qj, then they both pay c(s′) in Qj; if ON and OFF have both used s′ before, they both do not pay for s′ in Qj.
        if ON has used s′ before Qj but OFF hasn't, then ON pays zero but OFF pays c(s′) in Qj;
        if OFF has used s′ before Qj but ON hasn't, since the subexpressions are sorted by decreasing order of ldif, and s=f(Qj), ldifs′≦ldifs, which means Qj is also the last query in difs′. This means that c(s′) is not counted in dms′′(1) of any other subexpression s′′.
    
    


Therefore,




  
    
      
        
          d
          ⁢
          
            
          
          ⁢
          
            m
            s
            
              (
              1
              )
            
          
        
        ≤
        
          
            ∑
            
              
                Q
                ∈
                
                  dif
                  s
                
              
              ,
              
                s
                =
                
                  
                    f
                    n
                  
                  ⁡
                  
                    (
                    Q
                    )
                  
                
              
            
          
          ⁢
          
            rg
            ⁡
            
              (
              
                
                  P
                  N
                
                ⁡
                
                  (
                  Q
                  )
                
              
              )
            
          
        
      
    
    
      
        (
        11
        )
      
    
  




For dm(2), for each s, CN(fsts)−CF(fsts) comprises the costs of those subexpressions in fy(fsts), i.e., those subexpressions that have been used by OFF before fsts, and that are used by ON for the first time in fsts. Thus for each subexpression s′∈PN(fst(s)), ON and OFF both pays for c(s′). Thus




  
    
      
        
          
            ∑
            s
          
          ⁢
          
            
          
          ⁢
          
            d
            ⁢
            
              
            
            ⁢
            
              m
              s
              
                (
                2
                )
              
            
          
        
        ≤
        
          cost
          ⁡
          
            (
            OFF
            )
          
        
      
    
    
      
        (
        12
        )
      
    
  




From Eq. (11) and (12), and the fact that for any two subexpressions s and s′, sets {Q|Q∈difs,s=fn(Q)} and {Q|Q∈difs′,s′=fn(Q)} do not overlap, we have




  
    
      
        
          
            ∑
            s
          
          ⁢
          
            
          
          ⁢
          
            d
            ⁢
            
              
            
            ⁢
            
              m
              s
            
          
        
        =
        
        ⁢
        
          
            
              ∑
              s
            
            ⁢
            
              
            
            ⁢
            
              d
              ⁢
              
                
              
              ⁢
              
                m
                s
                
                  (
                  1
                  )
                
              
            
          
          +
          
            
              ∑
              s
            
            ⁢
            
              
            
            ⁢
            
              d
              ⁢
              
                
              
              ⁢
              
                m
                s
                
                  (
                  2
                  )
                
              
            
          
        
      
    
  
  
    
      
        ≤
        
        ⁢
        
          
            
              ∑
              
                
                  Q
                  ∈
                  
                    dif
                    s
                  
                
                ,
                
                  s
                  =
                  
                    
                      f
                      n
                    
                    ⁡
                    
                      (
                      Q
                      )
                    
                  
                
              
            
            ⁢
            
              rg
              ⁡
              
                (
                
                  
                    P
                    N
                  
                  ⁡
                  
                    (
                    Q
                    )
                  
                
                )
              
            
          
          +
          
            cost
            ⁡
            
              (
              OFF
              )
            
          
        
      
    
  
  
    
      
        ≤
        
        ⁢
        
          
            
              ∑
              
                Q
                ∈
                S
              
            
            ⁢
            
              rg
              ⁡
              
                (
                
                  
                    P
                    N
                  
                  ⁡
                  
                    (
                    Q
                    )
                  
                
                )
              
            
          
          +
          
            cost
            ⁡
            
              (
              OFF
              )
            
          
        
      
    
  
  
    
      
        ≤
        
        ⁢
        
          
            
              (
              
                
                  2
                  m
                
                -
                m
                -
                1
              
              )
            
            ⁢
            ln
            ⁢
            
              
            
            ⁢
            
              N
              ·
              
                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 v, we may build this view proactively when the system is idle, rather than waiting till we actually receive a query that needs to use v.
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, i), which means that view v is built after query Qi is processed (hence v can be reused by queries later than Qi). 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 (2m−m−1) In N+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 2m−m+1. 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 (2m−m−1) ln N+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 2m−m+1 when queries are join-only, and a competitive ratio of (2m−m−1)ln N+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.

## Claims

1. A method for query processing in a big data analytics platform, comprising:
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;
wherein for each plan Pij, using a scoring function score(Pij) defined as





  
    
      score
      ⁡
      
        (
        
          P
          ij
        
        )
      
    
    =
    
      
        
          ∑
          
            s
            ∈
            
              P
              ij
            
          
        
        ⁢
        
          
            rg
            i
          
          ⁡
          
            (
            s
            )
          
        
      
      -
      
        C
        ⁡
        
          (
          
            P
            ij
          
          )
        
      
    
  
  ;



with rgi(s) representing a regret of s wrt the ith query, and C(Pij) representing cost of plan Pij.

2. The method of claim 1, comprising receiving as input previous queries, current query, and a cost model.

3. The method of claim 1, comprising processing each query without knowing future queries with a worst case performance guarantee.

4. The method of claim 1, comprising determining regret, wherein Q1, Q2, . . . is a sequence of join-only queries, Pi denote the plan selected for Qi and for each query Qi and each subexpression sQi, the regret of s wrt Qi, denoted by rgi(s) or rgQi(s), is recursively defined as: if the result of s is not produced in any Pj(1≦j<i),




  
    
      rg
      i
    
    ⁡
    
      (
      s
      )
    
  
  =
  
    
      ∑
      
        
          
            Q
            j
          
          ❘
          
            j
            <
            i
          
        
        ,
        
          s
          ⊲
          
            Q
            j
          
        
      
    
    ⁢
    
      max
      ⁢
      
        {
        
          
            
              C
              ⁡
              
                (
                
                  P
                  j
                
                )
              
            
            -
            
              
                ∑
                
                  
                    s
                    ′
                  
                  ∈
                  
                    P
                    j
                  
                
              
              ⁢
              
                
                  rg
                  j
                
                ⁡
                
                  (
                  
                    s
                    ′
                  
                  )
                
              
            
          
          ,
          0
        
        }
      
    
  




if the result of s is available for reuse when Qi is processed, i.e., it is produced in a query Qj(1≦j<i), rgi(s)=0.

5. The method of claim 1, wherein a plan that contains high-regret subexpressions and has a low cost gets a high score, comprising choosing the plan for Qi with the maximum score among all plans for Qi.

6. The method of claim 1, comprising determining damage.

7. The method of claim 6, with a sequence of queries S and the query plans generated by ON and OFF, the damage of a subexpression s, denoted as dms, is defined as:
if s is late, dms=dms(1)+dms(2), where




  
    
      d
      ⁢
      
        
      
      ⁢
      
        m
        s
        
          (
          1
          )
        
      
    
    =
    
      
        
          ∑
          
            
              Q
              ❘
              
                Q
                ∈
                
                  dif
                  s
                
              
            
            ,
            
              s
              =
              
                
                  f
                  n
                
                ⁡
                
                  (
                  Q
                  )
                
              
            
          
        
        ⁢
        
          
            C
            N
          
          ⁡
          
            (
            Q
            )
          
        
      
      -
      
        
          C
          F
        
        ⁡
        
          (
          Q
          )
        
      
    
  




  
    
      d
      ⁢
      
        
      
      ⁢
      
        m
        s
        
          (
          2
          )
        
      
    
    =
    
      {
      
        
          
            
              
                
                  
                    C
                    N
                  
                  ⁡
                  
                    (
                    
                      fst
                      s
                    
                    )
                  
                
                -
                
                  
                    C
                    F
                  
                  ⁡
                  
                    (
                    
                      fst
                      s
                    
                    )
                  
                
              
              ;
              
                if
                ⁢
                
                  
                
                ⁢
                
                  fst
                  s
                
                ⁢
                
                  
                
                ⁢
                exists
              
            
          
        
        
          
            
              
                and
                ⁢
                
                  
                
                ⁢
                s
              
              =
              
                
                  
                    
                      f
                      y
                    
                    ⁡
                    
                      (
                      
                        fst
                        s
                      
                      )
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  and
                  ⁢
                  
                    
                  
                  ⁢
                  
                    
                      f
                      n
                    
                    ⁡
                    
                      (
                      
                        fst
                        s
                      
                      )
                    
                  
                
                =
                ∅
              
            
          
        
        
          
            
              0
              ;
              otherwise
            
          
        
      
    
  


otherwise, dms=0.

8. A method for query processing in a big data analytics platform, comprising:
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,
wherein for a sequence of queries Q1, Q2, . . . , the dominance graph Gj with respect to a query Qi is a directed acyclic graph (DAG) with Gi(Vi,Ai) with Vi and Ai being mapping points in the dominance graph Gj,
wherein vertices of Gi has a 1-1 mapping to all subexpressions contained in queries Q1: Qi whose results are not available when query Qi is processed and an arc from node u to node v if the subexpression corresponding to u directly dominates that corresponding to v with respect to Qi.

9. The method of claim 1, comprising determining regret of a subexpression s for query Qi recursively as




  
    
      rg
      i
    
    ⁡
    
      (
      s
      )
    
  
  =
  
    
      
        ∑
        
          
            
              Q
              j
            
            ❘
            
              j
              <
              i
            
          
          ,
          
            
              s
              ′
            
            ⊲
            
              Q
              j
            
          
          ,
          
            
              s
              ′
            
            ⁢
            
              
            
            ⁢
            
              □
              
                
              
              ⁢
              s
            
          
        
      
      ⁢
      
        
          
            C
            ⁡
            
              [
              
                P
                j
              
              ]
            
          
          -
          
            
              ∑
              
                
                  s
                  ′′′
                
                ∈
                
                  P
                  j
                
              
            
            ⁢
            
              
                rg
                j
              
              ⁡
              
                (
                
                  s
                  ′′′
                
                )
              
            
          
        
        
          norm
          ⁡
          
            (
            
              
                s
                ′
              
              ,
              s
              ,
              
                Q
                i
              
            
            )
          
        
      
    
    +
    
      
        ∑
        
          
            
              Q
              j
            
            ❘
            
              j
              <
              i
            
          
          ,
          
            
              s
              ′′
            
            ⊲
            
              Q
              j
            
          
          ,
          
            s
            ⁢
            
              
            
            ⁢
            
              s
              ′′
            
          
        
      
      ⁢
      
        (
        
          
            C
            ⁡
            
              [
              
                P
                j
              
              ]
            
          
          -
          
            
              ∑
              
                
                  s
                  ′′′
                
                ∈
                
                  P
                  j
                
              
            
            ⁢
            
              
                rg
                j
              
              ⁡
              
                (
                
                  s
                  ′′′
                
                )
              
            
          
        
        )
      
    
    -
    
      
        ∑
        
          
            s
            ′′
          
          ❘
          
            s
            ⁢
            
              
            
            ⁢
            
              □
              
                
              
              ⁢
              
                s
                ′′
              
            
          
        
      
      ⁢
      
        
          lrg
          i
        
        ⁡
        
          (
          
            s
            ′′
          
          )
        
      
    
  




where lrgi(s) (also referred to as lrgQi(s)) is the Last Regret of s for Qi, defined as




  
    
      lrg
      i
    
    ⁡
    
      (
      s
      )
    
  
  =
  
    {
    
      
        
          
            
              
                
                  rg
                  Q
                
                ⁡
                
                  (
                  s
                  )
                
              
              ,
              
                
                  s
                  .
                  t
                  .
                  Q
                
                ≺
                
                  Q
                  i
                
              
              ,
              
                s
                ∈
                
                  
                    
                      P
                      ⁡
                      
                        (
                        Q
                        )
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    and
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        rg
                        Q
                      
                      ⁡
                      
                        (
                        s
                        )
                      
                    
                  
                  >
                  0
                
              
            
          
        
        
          
            
              if
              ⁢
              
                
              
              ⁢
              Q
              ⁢
              
                
              
              ⁢
              exists
            
          
        
        
          
            
              0
              ,
              otherwise
            
          
        
      
      .

10. A system for query processing in a big data analytics platform, comprising:
a processor;
code executed by the processor for:
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;
comprising code for determining regret, wherein Q1,Q2, . . . is a sequence of join-only queries, Pi denote the respective plan selected for Qi and for each query Qi and each subexpression sQi, the regret rgi(s) of subexpression s wrt Qi, denoted by rgi(s) or rgQi(s), is recursively defined as: if the result of subexpression s is not produced in any plan Pj(1≦j<i),





  
    
      rg
      i
    
    ⁡
    
      (
      s
      )
    
  
  =
  
    
      ∑
      
        
          
            Q
            j
          
          ❘
          
            j
            <
            i
          
        
        ,
        
          s
          ⊲
          
            Q
            j
          
        
      
    
    ⁢
    
      max
      ⁢
      
        
          {
          
            
              
                C
                ⁡
                
                  (
                  
                    P
                    j
                  
                  )
                
              
              -
              
                
                  ∑
                  
                    
                      s
                      ′
                    
                    ∈
                    
                      P
                      j
                    
                  
                
                ⁢
                
                  
                    rg
                    j
                  
                  ⁡
                  
                    (
                    
                      s
                      ′
                    
                    )
                  
                
              
            
            ,
            0
          
          }
        
        .
      
    
  




if the result of subexpression s is available for reuse when Qi is processed, i.e., it is produced in a query Qj(1≦j<i), rgi(s)=0;
with C(Pj) representing cost of plan Pj, and rgj(s′),0 in the equation representing the total regret of subexpressions used in each plan Pj.

11. The system of claim 10, comprising code for receiving as input previous queries, current query, and a cost model.

12. The system of claim 10, comprising code for processing each query without knowing future queries with a worst case performance guarantee.

13. The system of claim 10, comprising code for determining regret of a subexpression s for query Qi recursively as




  
    
      rg
      i
    
    ⁡
    
      (
      s
      )
    
  
  =
  
    
      
        ∑
        
          
            
              Q
              j
            
            ❘
            
              j
              <
              i
            
          
          ,
          
            
              s
              ′
            
            ⊲
            
              Q
              j
            
          
          ,
          
            
              s
              ′
            
            ⁢
            
              
            
            ⁢
            
              □
              
                
              
              ⁢
              s
            
          
        
      
      ⁢
      
        
          
            C
            ⁡
            
              [
              
                P
                j
              
              ]
            
          
          -
          
            
              ∑
              
                
                  s
                  ′′′
                
                ∈
                
                  P
                  j
                
              
            
            ⁢
            
              
                rg
                j
              
              ⁡
              
                (
                
                  s
                  ′′′
                
                )
              
            
          
        
        
          norm
          ⁡
          
            (
            
              
                s
                ′
              
              ,
              s
              ,
              
                Q
                i
              
            
            )
          
        
      
    
    +
    
      
        ∑
        
          
            
              Q
              j
            
            ❘
            
              j
              <
              i
            
          
          ,
          
            
              s
              ′′
            
            ⊲
            
              Q
              j
            
          
          ,
          
            s
            ⁢
            
              
            
            ⁢
            
              s
              ′′
            
          
        
      
      ⁢
      
        (
        
          
            C
            ⁡
            
              [
              
                P
                j
              
              ]
            
          
          -
          
            
              ∑
              
                
                  s
                  ′′′
                
                ∈
                
                  P
                  j
                
              
            
            ⁢
            
              
                rg
                j
              
              ⁡
              
                (
                
                  s
                  ′′′
                
                )
              
            
          
        
        )
      
    
    -
    
      
        ∑
        
          
            s
            ′′
          
          ❘
          
            s
            ⁢
            
              
            
            ⁢
            
              □
              
                
              
              ⁢
              
                s
                ′′
              
            
          
        
      
      ⁢
      
        
          lrg
          i
        
        ⁡
        
          (
          
            s
            ′′
          
          )
        
      
    
  




where lrgi(s) (also referred to as lrgQi(s)) is the Last Regret of s for Qi, defined as




  
    
      lrg
      i
    
    ⁡
    
      (
      s
      )
    
  
  =
  
    {
    
      
        
          
            
              
                
                  rg
                  Q
                
                ⁡
                
                  (
                  s
                  )
                
              
              ,
              
                
                  s
                  .
                  t
                  .
                  Q
                
                ≺
                
                  Q
                  i
                
              
              ,
              
                s
                ∈
                
                  
                    
                      P
                      ⁡
                      
                        (
                        Q
                        )
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    and
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        rg
                        Q
                      
                      ⁡
                      
                        (
                        s
                        )
                      
                    
                  
                  >
                  0
                
              
            
          
        
        
          
            
              if
              ⁢
              
                
              
              ⁢
              Q
              ⁢
              
                
              
              ⁢
              exists
            
          
        
        
          
            
              0
              ,
              otherwise
            
          
        
      
      .