Visionary query processing in Hadoop utilizing opportunistic views
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.
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 P ij , using a scoring function score(P ij ) defined as
score
(
P
ij
)
=
∑
s
∈
P
ij
rg
i
(
s
)
-
C
(
P
ij
)
;
with rg i (s) representing a regret of s wrt the ith query, and C(P ij ) representing cost of plan P ij .
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 Q 1 , Q 2 , . . . is a sequence of join-only queries, P i denote the plan selected for Q i and for each query Q i and each subexpression s Q i , the regret of s wrt Q i , denoted by rg i (s) or rg Q i (s), is recursively defined as: if the result of s is not produced in any P j (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 Q i is processed, i.e., it is produced in a query Q j ( 1 ≦j<i), rg i (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 Q i with the maximum score among all plans for Q i .
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 dm s , is defined as:
if s is late, dm s =dm s (1) +dm s (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, dm s =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 Q 1 , Q 2 , . . . , the dominance graph G j with respect to a query Q i is a directed acyclic graph (DAG) with G i (V i ,A i ) with V i and A i being mapping points in the dominance graph G j ,
wherein vertices of G i has a 1-1 mapping to all subexpressions contained in queries Q 1 : Q i whose results are not available when query Q i 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 Q i .
9. The method of claim 1 , comprising determining regret of a subexpression s for query Q i 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 lrg i (s) (also referred to as lrg Q i (s)) is the Last Regret of s for Q i , 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 Q 1 ,Q 2 , . . . is a sequence of join-only queries, P i denote the respective plan selected for Q i and for each query Q i and each subexpression s Q i , the regret rg i (s) of subexpression s wrt Q i , denoted by rg i (s) or rg Q i (s), is recursively defined as: if the result of subexpression s is not produced in any plan P j (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 Q i is processed, i.e., it is produced in a query Q j (1≦j<i), rg i (s)=0;
with C(P j ) representing cost of plan P j , and rg j (s′),0 in the equation representing the total regret of subexpressions used in each plan P j .
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 Q i 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 lrg i (s) (also referred to as lrg Q i (s)) is the Last Regret of s for Q i , 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
.