1 // Licensed to the Apache Software Foundation (ASF) under one
2 // or more contributor license agreements. See the NOTICE file
3 // distributed with this work for additional information
4 // regarding copyright ownership. The ASF licenses this file
5 // to you under the Apache License, Version 2.0 (the
6 // "License"); you may not use this file except in compliance
7 // with the License. You may obtain a copy of the License at
8 //
9 // http://www.apache.org/licenses/LICENSE-2.0
10 //
11 // Unless required by applicable law or agreed to in writing,
12 // software distributed under the License is distributed on an
13 // "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14 // KIND, either express or implied. See the License for the
15 // specific language governing permissions and limitations
16 // under the License.
17
18 #include "gandiva/expr_decomposer.h"
19
20 #include <memory>
21 #include <stack>
22 #include <string>
23 #include <unordered_set>
24 #include <vector>
25
26 #include "gandiva/annotator.h"
27 #include "gandiva/dex.h"
28 #include "gandiva/function_holder_registry.h"
29 #include "gandiva/function_registry.h"
30 #include "gandiva/function_signature.h"
31 #include "gandiva/in_holder.h"
32 #include "gandiva/node.h"
33
34 namespace gandiva {
35
36 // Decompose a field node - simply separate out validity & value arrays.
Visit(const FieldNode & node)37 Status ExprDecomposer::Visit(const FieldNode& node) {
38 auto desc = annotator_.CheckAndAddInputFieldDescriptor(node.field());
39
40 DexPtr validity_dex = std::make_shared<VectorReadValidityDex>(desc);
41 DexPtr value_dex;
42 if (desc->HasOffsetsIdx()) {
43 value_dex = std::make_shared<VectorReadVarLenValueDex>(desc);
44 } else {
45 value_dex = std::make_shared<VectorReadFixedLenValueDex>(desc);
46 }
47 result_ = std::make_shared<ValueValidityPair>(validity_dex, value_dex);
48 return Status::OK();
49 }
50
51 // Try and optimize a function node, by substituting with cheaper alternatives.
52 // eg. replacing 'like' with 'starts_with' can save function calls at evaluation
53 // time.
TryOptimize(const FunctionNode & node)54 const FunctionNode ExprDecomposer::TryOptimize(const FunctionNode& node) {
55 if (node.descriptor()->name() == "like") {
56 return LikeHolder::TryOptimize(node);
57 } else {
58 return node;
59 }
60 }
61
62 // Decompose a field node - wherever possible, merge the validity vectors of the
63 // child nodes.
Visit(const FunctionNode & in_node)64 Status ExprDecomposer::Visit(const FunctionNode& in_node) {
65 auto node = TryOptimize(in_node);
66 auto desc = node.descriptor();
67 FunctionSignature signature(desc->name(), desc->params(), desc->return_type());
68 const NativeFunction* native_function = registry_.LookupSignature(signature);
69 DCHECK(native_function) << "Missing Signature " << signature.ToString();
70
71 // decompose the children.
72 std::vector<ValueValidityPairPtr> args;
73 for (auto& child : node.children()) {
74 auto status = child->Accept(*this);
75 ARROW_RETURN_NOT_OK(status);
76
77 args.push_back(result());
78 }
79
80 // Make a function holder, if required.
81 std::shared_ptr<FunctionHolder> holder;
82 if (native_function->NeedsFunctionHolder()) {
83 auto status = FunctionHolderRegistry::Make(desc->name(), node, &holder);
84 ARROW_RETURN_NOT_OK(status);
85 }
86
87 if (native_function->result_nullable_type() == kResultNullIfNull) {
88 // These functions are decomposable, merge the validity bits of the children.
89
90 std::vector<DexPtr> merged_validity;
91 for (auto& decomposed : args) {
92 // Merge the validity_expressions of the children to build a combined validity
93 // expression.
94 merged_validity.insert(merged_validity.end(), decomposed->validity_exprs().begin(),
95 decomposed->validity_exprs().end());
96 }
97
98 auto value_dex =
99 std::make_shared<NonNullableFuncDex>(desc, native_function, holder, args);
100 result_ = std::make_shared<ValueValidityPair>(merged_validity, value_dex);
101 } else if (native_function->result_nullable_type() == kResultNullNever) {
102 // These functions always output valid results. So, no validity dex.
103 auto value_dex =
104 std::make_shared<NullableNeverFuncDex>(desc, native_function, holder, args);
105 result_ = std::make_shared<ValueValidityPair>(value_dex);
106 } else {
107 DCHECK(native_function->result_nullable_type() == kResultNullInternal);
108
109 // Add a local bitmap to track the output validity.
110 int local_bitmap_idx = annotator_.AddLocalBitMap();
111 auto validity_dex = std::make_shared<LocalBitMapValidityDex>(local_bitmap_idx);
112
113 auto value_dex = std::make_shared<NullableInternalFuncDex>(
114 desc, native_function, holder, args, local_bitmap_idx);
115 result_ = std::make_shared<ValueValidityPair>(validity_dex, value_dex);
116 }
117 return Status::OK();
118 }
119
120 // Decompose an IfNode
Visit(const IfNode & node)121 Status ExprDecomposer::Visit(const IfNode& node) {
122 // nested_if_else_ might get overwritten when visiting the condition-node, so
123 // saving the value to a local variable and resetting nested_if_else_ to false
124 bool svd_nested_if_else = nested_if_else_;
125 nested_if_else_ = false;
126
127 PushConditionEntry(node);
128 auto status = node.condition()->Accept(*this);
129 ARROW_RETURN_NOT_OK(status);
130 auto condition_vv = result();
131 PopConditionEntry(node);
132
133 // Add a local bitmap to track the output validity.
134 int local_bitmap_idx = PushThenEntry(node, svd_nested_if_else);
135 status = node.then_node()->Accept(*this);
136 ARROW_RETURN_NOT_OK(status);
137 auto then_vv = result();
138 PopThenEntry(node);
139
140 PushElseEntry(node, local_bitmap_idx);
141 nested_if_else_ = (dynamic_cast<IfNode*>(node.else_node().get()) != nullptr);
142
143 status = node.else_node()->Accept(*this);
144 ARROW_RETURN_NOT_OK(status);
145 auto else_vv = result();
146 bool is_terminal_else = PopElseEntry(node);
147
148 auto validity_dex = std::make_shared<LocalBitMapValidityDex>(local_bitmap_idx);
149 auto value_dex =
150 std::make_shared<IfDex>(condition_vv, then_vv, else_vv, node.return_type(),
151 local_bitmap_idx, is_terminal_else);
152
153 result_ = std::make_shared<ValueValidityPair>(validity_dex, value_dex);
154 return Status::OK();
155 }
156
157 // Decompose a BooleanNode
Visit(const BooleanNode & node)158 Status ExprDecomposer::Visit(const BooleanNode& node) {
159 // decompose the children.
160 std::vector<ValueValidityPairPtr> args;
161 for (auto& child : node.children()) {
162 auto status = child->Accept(*this);
163 ARROW_RETURN_NOT_OK(status);
164
165 args.push_back(result());
166 }
167
168 // Add a local bitmap to track the output validity.
169 int local_bitmap_idx = annotator_.AddLocalBitMap();
170 auto validity_dex = std::make_shared<LocalBitMapValidityDex>(local_bitmap_idx);
171
172 std::shared_ptr<BooleanDex> value_dex;
173 switch (node.expr_type()) {
174 case BooleanNode::AND:
175 value_dex = std::make_shared<BooleanAndDex>(args, local_bitmap_idx);
176 break;
177 case BooleanNode::OR:
178 value_dex = std::make_shared<BooleanOrDex>(args, local_bitmap_idx);
179 break;
180 }
181 result_ = std::make_shared<ValueValidityPair>(validity_dex, value_dex);
182 return Status::OK();
183 }
Visit(const InExpressionNode<gandiva::DecimalScalar128> & node)184 Status ExprDecomposer::Visit(const InExpressionNode<gandiva::DecimalScalar128>& node) {
185 /* decompose the children. */
186 std::vector<ValueValidityPairPtr> args;
187 auto status = node.eval_expr()->Accept(*this);
188 ARROW_RETURN_NOT_OK(status);
189 args.push_back(result());
190 /* In always outputs valid results, so no validity dex */
191 auto value_dex = std::make_shared<InExprDex<gandiva::DecimalScalar128>>(
192 args, node.values(), node.get_precision(), node.get_scale());
193 result_ = std::make_shared<ValueValidityPair>(value_dex);
194 return Status::OK();
195 }
196
197 #define MAKE_VISIT_IN(ctype) \
198 Status ExprDecomposer::Visit(const InExpressionNode<ctype>& node) { \
199 /* decompose the children. */ \
200 std::vector<ValueValidityPairPtr> args; \
201 auto status = node.eval_expr()->Accept(*this); \
202 ARROW_RETURN_NOT_OK(status); \
203 args.push_back(result()); \
204 /* In always outputs valid results, so no validity dex */ \
205 auto value_dex = std::make_shared<InExprDex<ctype>>(args, node.values()); \
206 result_ = std::make_shared<ValueValidityPair>(value_dex); \
207 return Status::OK(); \
208 }
209
210 MAKE_VISIT_IN(int32_t);
211 MAKE_VISIT_IN(int64_t);
212 MAKE_VISIT_IN(float);
213 MAKE_VISIT_IN(double);
214 MAKE_VISIT_IN(std::string);
215
Visit(const LiteralNode & node)216 Status ExprDecomposer::Visit(const LiteralNode& node) {
217 auto value_dex = std::make_shared<LiteralDex>(node.return_type(), node.holder());
218 DexPtr validity_dex;
219 if (node.is_null()) {
220 validity_dex = std::make_shared<FalseDex>();
221 } else {
222 validity_dex = std::make_shared<TrueDex>();
223 }
224 result_ = std::make_shared<ValueValidityPair>(validity_dex, value_dex);
225 return Status::OK();
226 }
227
228 // The bolow functions use a stack to detect :
229 // a. nested if-else expressions.
230 // In such cases, the local bitmap can be re-used.
231 // b. detect terminal else expressions
232 // The non-terminal else expressions do not need to track validity (the if statement
233 // that has a match will do it).
234 // Both of the above optimisations save CPU cycles during expression evaluation.
235
PushThenEntry(const IfNode & node,bool reuse_bitmap)236 int ExprDecomposer::PushThenEntry(const IfNode& node, bool reuse_bitmap) {
237 int local_bitmap_idx;
238
239 if (reuse_bitmap) {
240 // we also need stack in addition to reuse_bitmap flag since we
241 // can also enter other if-else nodes when we visit the condition-node
242 // (which themselves might be nested) before we visit then-node
243 DCHECK_EQ(if_entries_stack_.empty(), false) << "PushThenEntry: stack is empty";
244 DCHECK_EQ(if_entries_stack_.top()->entry_type_, kStackEntryElse)
245 << "PushThenEntry: top of stack is not of type entry_else";
246 auto top = if_entries_stack_.top().get();
247
248 // inside a nested else statement (i.e if-else-if). use the parent's bitmap.
249 local_bitmap_idx = top->local_bitmap_idx_;
250
251 // clear the is_terminal bit in the current top entry (else).
252 top->is_terminal_else_ = false;
253 } else {
254 // alloc a new bitmap.
255 local_bitmap_idx = annotator_.AddLocalBitMap();
256 }
257
258 // push new entry to the stack.
259 std::unique_ptr<IfStackEntry> entry(new IfStackEntry(
260 node, kStackEntryThen, false /*is_terminal_else*/, local_bitmap_idx));
261 if_entries_stack_.emplace(std::move(entry));
262 return local_bitmap_idx;
263 }
264
PopThenEntry(const IfNode & node)265 void ExprDecomposer::PopThenEntry(const IfNode& node) {
266 DCHECK_EQ(if_entries_stack_.empty(), false) << "PopThenEntry: found empty stack";
267
268 auto top = if_entries_stack_.top().get();
269 DCHECK_EQ(top->entry_type_, kStackEntryThen)
270 << "PopThenEntry: found " << top->entry_type_ << " expected then";
271 DCHECK_EQ(&top->if_node_, &node) << "PopThenEntry: found mismatched node";
272
273 if_entries_stack_.pop();
274 }
275
PushElseEntry(const IfNode & node,int local_bitmap_idx)276 void ExprDecomposer::PushElseEntry(const IfNode& node, int local_bitmap_idx) {
277 std::unique_ptr<IfStackEntry> entry(new IfStackEntry(
278 node, kStackEntryElse, true /*is_terminal_else*/, local_bitmap_idx));
279 if_entries_stack_.emplace(std::move(entry));
280 }
281
PopElseEntry(const IfNode & node)282 bool ExprDecomposer::PopElseEntry(const IfNode& node) {
283 DCHECK_EQ(if_entries_stack_.empty(), false) << "PopElseEntry: found empty stack";
284
285 auto top = if_entries_stack_.top().get();
286 DCHECK_EQ(top->entry_type_, kStackEntryElse)
287 << "PopElseEntry: found " << top->entry_type_ << " expected else";
288 DCHECK_EQ(&top->if_node_, &node) << "PopElseEntry: found mismatched node";
289 bool is_terminal_else = top->is_terminal_else_;
290
291 if_entries_stack_.pop();
292 return is_terminal_else;
293 }
294
PushConditionEntry(const IfNode & node)295 void ExprDecomposer::PushConditionEntry(const IfNode& node) {
296 std::unique_ptr<IfStackEntry> entry(new IfStackEntry(node, kStackEntryCondition));
297 if_entries_stack_.emplace(std::move(entry));
298 }
299
PopConditionEntry(const IfNode & node)300 void ExprDecomposer::PopConditionEntry(const IfNode& node) {
301 DCHECK_EQ(if_entries_stack_.empty(), false) << "PopConditionEntry: found empty stack";
302
303 auto top = if_entries_stack_.top().get();
304 DCHECK_EQ(top->entry_type_, kStackEntryCondition)
305 << "PopConditionEntry: found " << top->entry_type_ << " expected condition";
306 DCHECK_EQ(&top->if_node_, &node) << "PopConditionEntry: found mismatched node";
307 if_entries_stack_.pop();
308 }
309
310 } // namespace gandiva
311