Background
My team uses an expression computation library for our C++ feature
engineering pipeline. We currently use Exprtk
<https://github.com/ArashPartow/exprtk>. We recently tried out Gandiva and
wrote some benchmarks. We discovered that Gandiva is several times faster
than Exprtk in our use cases. Therefore we decided to switch to Gandiva for
computing expressions.
Objective
As of current, due to its lack of a frontend, we need to manually construct
an AST to use Gandiva. This is inconvenient and requires extra learning
costs. We also want to enable our ML engineers to dynamically create/update
an expression with runtime hot-loaded configs without restarting our
server. This is currently impossible with Gandiva because the Expression
tree is statically created with C++ and must be compiled in the server
binary.
Therefore, we would like to implement a parser frontend for Gandiva, so
that Gandiva becomes a standalone complete expression compiler and
evaluator, and a drop-in replacement for the existing libraries like Exprtk
<https://github.com/ArashPartow/exprtk> and TinyExpr
<https://github.com/codeplea/tinyexpr>. The goal is to enable the following
functionality:
// Create schema for gandiva
auto field_x = arrow::field("x", arrow::uint64());
auto field_y = arrow::field("y", arrow::float64());
auto field_z = arrow::field("z", arrow::boolean());
auto schema = arrow::schema({field_x, field_y, field_z});
/** BEGIN CHANGE **/
// Use the Parser to generate a NodePtr
std::string expr_str = "if(z, castFloat8(x), y * 1000.0)";
auto parser = gandiva::Parser(schema);
gandiva::NodePtr root_node;
auto status = parser.Parse(expr_str, &root_node);
/** END CHANGE **/
// The rest is normal usage of Gandiva projector
auto expr_ptr = std::make_shared<gandiva::Expression>(root_node, result_field);
std::shared_ptr<gandiva::Projector> projector;
auto status = gandiva::Projector::Make(schema, {expr_ptr}, &projector);
auto in_batch = arrow::RecordBatch::Make(schema, size, input_arr);
auto* pool = arrow::default_memory_pool();
arrow::ArrayVector outputs;
auto status = projector->Evaluate(*in_batch, pool, &outputs);
The code block enclosed by “BEGIN CHANGE” and “END CHANGE” is the proposed
usage of the parser. It offers two benefits:
1. It’s more intuitive to write math expressions compared to
constructing trees, thus easier to use.
2. It allows dynamically adding new expressions or and changing existing
ones with a runtime hot-loaded config file without restarting our server.
Syntax
The goal is to design a succinct and intuitive grammar for both schema and
Gandiva expressions. We will need a corresponding grammar for each Node
type in Gandiva.
-
Literals: We find Rust’s literal representation(
<https://doc.rust-lang.org/rust-by-example/types/literals.html>
https://doc.rust-lang.org/rust-by-example/types/literals.html) very
intuitive. We’ll support suffixes such as i32, u64, f32 to denote a
literal node’s type. The types of unsuffixed literals are inferred by their
usage. Otherwise, the default type for integers is int32 and float32 for
floating points. String and binary literals are wrapped with single or
double quotes. Decimal128 literals will not be supported in the first
version.
-
Fields: Just their names as defined in the schema. To avoid conflicts
with other node types, field names must start with alphabetical letters.
-
Functions: <function_name>(<param1>, <param2>, ...). For functions with
multiple overloads, their return type is inferred from input types. For
commonly used functions, we would also like to support infix forms. They
include:
- Comparisons: equal(==), not equal(!=), greater than(>), greater than
or equal to(>=), less than(<), less than or equal to(<=)
- Arithmetics: add(+), subtract(-), multiply(*), divide(/),
modulo(%), power(^), bitwise and(&), bitwise or(|), bitwise
xor(^), bitwise
not(~)
Function aliases with spaces in their names won’t be supported such as
“is not false” are not supported.
-
Ifs: We would like to support two grammars for if expressions:
- if(<cond>, <then>, <else>) for its simplicity and functional feel;
- if(<cond>) { <then> } else { <else> } since it’s the C++ if grammar
and has better formatting for complex expressions.
-
Booleans: We would like to support both && || and and or keywords the
same as C++.
-
InExpressions: <eval> in (<member1>, <member2>, ...) . Its type is also
inferred.
The grammar can be roughly represented as:
exp := term
term := literal | field | function | if | boolean | inexpression
literal := INT_LITERAL | INT_LITERAL_SUFFIX | FLOAT_LITERAL |
FLOAT_LITERAL_SUFFIX | "-" literal
field := IDENTIFIER
function := infix_function | named_function
infix_function := "-" term | term "+" term | term "-" term ...
named_function := IDENTIFIER(arguments)
arguments := term | argument "," term
if := "if" "(" term "," term "," term ")" | "if" "(" term ")" "{"
term"}" ELSE "{" term "}"
boolean := and_boolean | or_boolean
and_boolean := term AND term | term "&&" term
or_boolean := term OR term | term "||" term
inexpression := term IN "(" arguments ")"
lower cases are non-terminals and upper cases are tokens.
Implementation Lexing and Parsing
We would like to use flex and bison for lexing and parsing. They have
several advantages compared to other options like Antlr4 and Boost::Spirit.
1. They are the most classical and popular parsing library in the cpp
world.
2. They allow us to precompile the parser codes and have no runtime
dependencies.
Flex&bison takes a string and outputs a gandiva::node tree. The tree may
contain untyped nodes, e.g., unsuffixed literals and functions.
Type Inference
We’ll have a TypeInferenceVisitor class that inherits node visitor,
implementing a 2-pass DFS algorithm to do type inference. In each pass, the
visitor tries to infer current node’s and its children’s types from
currently available info:
If it’s a non-leaf node such as function ,if ,boolean:
1. First visit each child: let them infer their own types as much as
they can.
2. Create a SignaturePattern based on currently known types. The pattern
includes the current node’s type and children’s types. The types can be
nullptr meaning the type is currently unknown. For example, the
SignaturePattern for func(x: u64, 5: untyped) will be (u64,
nullptr)—>nullptr.
3. Get all available signatures of the current node. For functions, it’s
the signatures registered at the function registry. For if, it’s (bool,
<type>, <type>)—><type> for any type etc.
4. Try to match each signature with the current pattern SignaturePattern
1. If no one matches, it’s a type error.
2. If only one matches, it’s the matched signature. We then update
current node’s and their children’s types based on this signature.
3. If more than one matches, we extract a common pattern from the set
of matched signatures. For example, (nullptr, nullptr)—>bool can be
extracted from (double, double)—>bool and (int32, int32)—>bool . We
then update types based on this common pattern.
If it’s a leaf node, just update its value if its type is set by its
parent. We need to do this because untyped literals’ values are saved in a
generic container.
We run this procedure 2 times, with the second pass a bit different. In the
second pass, if a literal node is still untyped, give it a default type (
int32 for ints and float32 for floats).
1. The first pass is bottom up propagation of types. A parent’s type is
inferred from its children.
2. The second pass is both:
1. top down propagation of first pass’ info. Once a parent’s type is
known in the first pass, it may set it’s children’s type
2. bottom up of default literal types. A literal is given a default
type.
In the second pass, since all leaf nodes’ types are known. The types of all
nodes are guaranteed to be inferred.
Proof of correctness
I have a proof of correctness of this inference procedure in mind, but it’s
too long to be written down here. (Fermat did it too 🙂) But the
correctness is based on these two facts:
1. There are no overloads that differ only on their return types. E.g.
there are no func := (int32, int32)-->int32 and func := (int32,
int32)-->double in the Gandiva registry. Therefore we can always know a
function’s type if its children’s types are known.
2. There are no overloads that accept only non-default numeric types.
For example, if there is a func := (int16, int16)-->int16 and func :=
(int64, int64)-->int64, but no func := (int32, int32)-->int32, then the
inference procedure will fail on expression func(1, 2) because it cannot
tell the types of 1 and 2, and giving them default types won't work.
Prototype and Examples
I’ve already written a mostly working prototype of the parser and type
inference visitor and unit tests for them. They are on the branch
<https://github.com/js8544/arrow/tree/jinshang/gandiva/type_inference>
https://github.com/js8544/arrow/tree/jinshang/gandiva/type_inference.
You can checkout the diffs here:
<https://github.com/apache/arrow/compare/master...js8544:arrow:jinshang/gandiva/type_inference>
https://github.com/apache/arrow/compare/master...js8544:arrow:jinshang/gandiva/type_inference
The main files are:
1. cpp/src/gandiva/grammar.yy: grammar rules for Bison.
2. cpp/src/gandiva/lex.ll: lex rules for Flex.
3. cpp/src/gandiva/typeinference.h/cc: type inference procedure.
4. cpp/src/gandiva/parser.cc: the driver class that combines the three
components.
5. cpp/src/gandiva/parser_test.cc: unit tests containing examples of the
proposed syntax and the result expression trees the parser generates. You
can run the tests by running cmake .. --preset=ninja-debug-gandiva and ninja
test-gandiva-tests.
Any suggestion/question is appreciated!
Best regards,
Jin Shang
