arrow: [C++] Wrong and low inefficient expression execution for [if/else, case/when ... etc] expression
Describe the bug, including details regarding any error messages, version, and platform.
A bug is found here. When we execute a similar case when a != 0 then b / a, div 0 exception will be reported. But logically, such a statement should be executed. The reason why the above execution will report an error is because of the existing ExecuteScalarExpression execution system logic, as shown in the following code:
for (size_t i = 0; i < arguments.size(); ++i) {
ARROW_ASSIGN_OR_RAISE(
arguments[i], ExecuteScalarExpression(call->arguments[i], input, exec_context));
if (arguments[i].is_array()) {
all_scalar = false;
}
}
For the above statement, the expression arguments[0] corresponding to the judgment condition a != 0 will be executed first, and then the arguments[1] corresponding to b / a will be executed. Obviously, logically speaking, b / a should not be fully executed, it should be partially executed based on a != 0
Because if-else related expressions have a special execution order, should we extend ExecuteScalarIfElseExpression to handle such expressions separately? The execution order is as follows:
- First execute the condition corresponding to the if statement
- Filter the corresponding data based on the execution result of the if statement
- Perform the remaining operations
To do this, we obviously need to extend Expression to support if-else related logic and callbacks
laotan332 qinpengxiang@outlook.com
Component(s)
C++
About this issue
- Original URL
- State: open
- Created 3 years ago
- Comments: 18 (14 by maintainers)
I think both 2 and 3 could potentially benefit from leveraging special attributes of specific data types such as list/string-view, ree and dict, though I’m not exactly sure how. I’m now working on an overall framework, maybe things will become clearer when I get there. I can use some help/comment from you guys then 😃
The solution should not be specific to if-then-else. Other constructs pose similar challenges (e.g.
CASE WHEN):Velox (a vectorized query engine) calls these constructs “special forms”. Lisp uses the same terminology. Although
ifandcondlook like function calls in Lisp [1][2], they are special in that not all arguments are eagerly evaluated:Other special forms are
and,or, andcond:andis special because after the firstfalseyou get, you don’t have to evaluate more input expressions.oris special because after the firsttrueyou get, you…condis likeCASE .. WHENin SQL — a chain of if-then-else’s.This can’t be done properly when
if_then_else,case_when,and,orare implemented as functions like in Arrow currently. We need to create special expression fragments that can receive unevaluated expressions as input parameters.They would look like
compute::Expression::Callthat can receivecompute::Expressioninstances as parameters [3].Vectorized evaluation of special forms
Here I will try to expand on what @bkietz meant by “support for selection vectors”.
Let’s say we want to eval the following special form:
if bool_expr then list_value_length(a) else list_value_length(b)bool_expris always evaluated. When it’s evaluated, aType::BOOLarray is produced.The naive algorithm to evaluate the whole expression would then, be:
this would be very inefficient since we’re dealing with columnar data layouts here.
The vectorization friendly solution is to make every compute function “maskable”/“selectable”. This can be made efficient if
list_value_lengthcan receive an extra “filter” parameter that selects the positions thatlist_value_lengthshould read read from input and write to output:A “selection vector” is an array of indices.
GetTakeIndicesFromBitmap[4] produces one from boolean arrays/bitmaps. By passing the selection vectors to the kernels, you allow each kernel to vectorize as is most appropriate to what it’s doing: for instance,list_value_lengthcan gather the offsets of the indices in the selection vector, perform all the subtractions to calculate the sizes, and scatter the values into the value buffer inout.Incremental improvement
It’s unrealistic to expect we will specialize all kernel functions to handle the optional selection vector parameter, but we should at least push them all the way down to
Function::Execute. If aFunctiondoesn’t handle selection vectors, then a call is dispatched for all the values (as it is today) and code similar toTakeis used to gather the values that the selection vector selects. The more functions become aware of selection vectors, the less we have to rely on this slow code.It’s not a trivial project.
[1] https://courses.cs.northwestern.edu/325/readings/special-forms.html [2] https://docs.racket-lang.org/guide/conditionals.html [3] https://github.com/apache/arrow/blob/0d7fac0d49eae7f139735c3e7c9256fc304a698a/cpp/src/arrow/compute/expression.h#L136 [4] https://github.com/apache/arrow/blob/main/cpp/src/arrow/compute/kernels/vector_selection_take_internal.cc#L275
You’re right. It’s not just taking/gathering the values, we have to stitch the output array from many different outputs. And you’re right — we don’t have a scatter facility — but note that for some array types (e.g. list and binary/string), you can’t scatter based on destination indices. You will have to append in order from the arrays resulting from each if/else or case/when branch.
This is where the recent additions (list-view and string-view) can shine because you can scatter by index to them in any order as the variable-length data doesn’t have to be packed in the same order as the offsets and sizes.
The starting point is making special forms representable in
Expression::Impl, then adding placeholder implementations that don’t prevent the full vectorization.PR #42106 drafted to show the main sketch. I’ve also put some notes in PR description. @felipecrv would you please to take a look? Thanks.
In the implementation, maybe we can first implement gather-scatter? Since Arrow doesn’t gurantee a data type supports un-ordered write currently ( which is different from velox )
Hi @felipecrv , I’m interested in this and doing some POC in my local (thanks for the instructive proposal!). One thing that I’m having trouble with is that, to allow the kernels to become “selection vector aware” incrementally:
We not only
Takethe selected rows to pass to a kernel that has not yet been selection vector aware, but also “scatter” the “partial” output by putting the rows back to the corresponding position to the original input rows. However I couldn’t find any existing facility for this scatter operation as handy asTake/Filterfor gather. Do you know any? Or do we need aScatterfunction, or something more light-weight likeConcatenate[1], to be implemented first? Thanks.[1] https://github.com/apache/arrow/blob/4a2df663bc88c73b863e0c0036160f7f936574c2/cpp/src/arrow/array/concatenate.h#L34-L35
should not be executed?
I think a
Selectorwould be help here. But I don’t know whether it breaks the current design. I’ll dive into it later