[
https://issues.apache.org/jira/browse/ARROW-17668?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated ARROW-17668:
-----------------------------------
Labels: pull-request-available (was: )
> [C++][Gandiva] Add parser frontend for Gandiva
> ----------------------------------------------
>
> Key: ARROW-17668
> URL: https://issues.apache.org/jira/browse/ARROW-17668
> Project: Apache Arrow
> Issue Type: New Feature
> Components: C++ - Gandiva
> Reporter: Jin Shang
> Assignee: Jin Shang
> Priority: Minor
> Labels: pull-request-available
> Time Spent: 10m
> Remaining Estimate: 0h
>
> h2. 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.
> h2. 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:
>
> {{}}
> {code:java}
> // 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);{code}
> {{ }}
> The code block enclosed by “BEGIN CHANGE” and “END CHANGE” is the proposed
> usage of the parser. It offers two benefits:
> # It’s more intuitive to write math expressions compared to constructing
> trees, thus easier to use.
> # It allows dynamically adding new expressions or and changing existing ones
> with a runtime hot-loaded config file without restarting our server.
> h2. 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])
> 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:
>
> {{}}
> {code:java}
> // 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);{code}
> {{ }}
> lower cases are non-terminals and upper cases are tokens.
> h2. Implementation
> h3. 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.
> # They are the most classical and popular parsing library in the cpp world.
> # 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.
> h3. 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{}}}:
> # First visit each child: let them infer their own types as much as they can.
> # 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.}}
> # Get all available signatures of the current node. For {{{}function{}}}s,
> it’s the signatures registered at the function registry. For {{{}if{}}}, it’s
> {{(bool, <type>, <type>)—><type>}} for any type etc.
> # Try to match each signature with the current pattern {{SignaturePattern}}
> ## If no one matches, it’s a type error.
> ## If only one matches, it’s the matched signature. We then update current
> node’s and their children’s types based on this signature.
> ## 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).
> # The first pass is bottom up propagation of types. A parent’s type is
> inferred from its children.
> # The second pass is both:
> ## 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
> ## 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.
> h3. 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:
> # 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.
> # 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.
> h2. 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].
> You can checkout the diffs here:
> [https://github.com/apache/arrow/compare/master...js8544:arrow:jinshang/gandiva/type_inference]
> The main files are:
> # cpp/src/gandiva/grammar.yy: grammar rules for Bison.
> # cpp/src/gandiva/lex.ll: lex rules for Flex.
> # cpp/src/gandiva/typeinference.h/cc: type inference procedure.
> # cpp/src/gandiva/parser.cc: the driver class that combines the three
> components.
> # 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!
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
