amplab/shark — pull request #310 by chenghao-intel (2014-03-17 13:33:11+00:00)
Title: Expression Eval in Projection & Filter

Shark expression evaluation is based on Hive ObjectInspector/Evaluator framework, however, the "interpret" mode introduces many small objects creation, duplicated sub expression computing, and extra branch predictions etc., when computing the expression. As an in-memory computing framework, Shark need a faster way of expr eval.

Expr Eval codegen is the solution compile the expr once in master, and distributed the expr eval byte code on executor.
The major steps are:
1) Analysis the Expression Tree (ExprNodeDesc in Hive), and transform to internal expr node tree (TypedExprNode), with type info determined and constant folded.
2) Transform the TypedExprNode tree to executing ordered tree(ExecuteExprNode), and the expression node is joint by wedge node (e.g. variable declare and null value checking statement node.)
3) Simplify the ExecuteExprNode tree, by removing the duplicated checking / common sub expression from every executing path.
4) Generate the Java Source Code, compile it on master, and then distribute the classloader across the whole cluster via Spark broadcast API.

1. Performance Improvements

HQL | Interpret (Secs) | Codegen (Secs) | Improved
------------- | ----------------- | --------------- | -------------
C1 | 75.706 | 19.851 | 3.81X
C2 |	72.092 | 21.243 | 3.39X
C3 |	88.496 | 40.052 | 2.21X
C4 |	23.677 | 22.251 | 1.06X
C5 |	10.291 | 11.108 | 0.93X

ID | HQL
---- | ----
C1 | select count(1) from test where b+c+d+e+f+g+h+b+c+d+e+f+g+h+e+f+f+d+b+c+d+e+f+g+h+e+e+f+f+f+e+e+e>0;
C2 | select count(1) from (select b+c+d+e+f+g+h+b+c+d+e+f+g+h+e+f+f+d+b+c+d+e+f+g+h+e+e+f+f+f+e+e+e as b from test) t where t.b>0;
C3 | select sum(c1), sum(c2), sum(c3), sum(c4), sum(c5), sum(c6), sum(c7) from (select b+c+d+e as c1, f+g+h+b+c as c2, d+e+f+g as c3, h+e+f+f as c4, d+b+c+d as c5, e+f+g+h+e as c6, e+f+f+f+e+e+e as c7 from test) t where t.c1>0 and t.c2>0 and t.c3>0 and t.c4>0 and t.c5>0 and t.c6>0 and t.c7>0;
C4 | select sum(t.b), sum(t.c), sum(t.d), sum( t.e), sum(t.f ), sum( t.g) from (select a, b, c, d, e,f, g, h, I, j from test) t;
C5 | select count(1) from (select b+c+d from test) t;

The codegen & compiling time is from 50ms ~ 500ms depends on the complexity of the expression.