# US 2015/0149434 A1 · Visionary Query Processing in Hadoop Utilizing Opportunistic Views

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2015/0149434 A1
- Document ID: US20150149434A1
- Status: Published application
- Kind: A1
- Application number: 14/506,625
- Filed: 2014-10-04
- Published: 2015-05-28
- Earliest claimed: 2013-11-26
- Assignees: NEC Laboratories America, Inc.
- Applicants: NEC Laboratories America, Inc.
- Inventors: Ziyang Liu; Vahit Hacigumus
- Web page: https://patentgrep.com/patent/US20150149434A1

## CPC

- G06F 16/24544: {Join order optimisation}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

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

## Claims

### Claim 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.

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 1)

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

### Claim 4 (depends on 1)

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 sQ, 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.

### Claim 5 (depends on 1)

The method of claim 1, for each plan Pij, using a scoring function score(Pij) defined as
score

(
P
ij
)
=
∑
s
∈
P
ij

rg
i

(
s
)
-
C

(
P
ij
)
.

### Claim 6 (depends on 5)

The method of claim 5, 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.

### Claim 7 (depends on 1)

The method of claim 1, comprising determining damage.

### Claim 8 (depends on 7)

The method of claim 7, with 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
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.

### Claim 9 (depends on 1)

The method of claim 1, wherein for a sequence of queries Q1, Q2, . . . , the dominance graph with respect to a query Qi is a directed acyclic graph (DAG) with Gi(Vi, Ai).

### Claim 10 (depends on 9)

The method of claim 9, wherein 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 and an arc from node u to v if the subexpression corresponding to u directly dominates that corresponding to v with respect to Qi.

### Claim 11 (depends on 1)

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
.

### Claim 12

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.

### Claim 13 (depends on 12)

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

### Claim 14 (depends on 12)

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

### Claim 15 (depends on 12)

The system of claim 12, comprising code for 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.

### Claim 16 (depends on 12)

The system of claim 12, 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
.
