[FEA] Support segmented apply_boolean_mask

[revans2]

Is your feature request related to a problem? Please describe.
Apache Spark has a list remove (array_remove in Spark) operator that will take a list column and a search column. There is also a map_filter operator that takes a higher order function and filters out entries in the map that match it. In order to implement both of these we would love to have a segmented apply_boolean_mask operator that would take two list columns. One that is being filtered and another that is a list of booleans that would be the boolean mask. The dimensions of both columns must match (lengths of each list in the column).

Describe the solution you'd like
It feels rather simple to implement. But it feels like something that is basic enough it should be a part of CUDF.

Describe alternatives you've considered
We probably could write our own segmented filter using segmented gather, or a regular apply_boolean_mask along with some aggregations and segmented scan to create the output offsets. But it feels like something that should be a part of CUDF.

[revans2]

@jrhemstad I rewrote this to just be about segmented apply_boolean_mask like you asked.

[mythrocks]

I haven't thought it through yet, but it sounds like this might be achievable via cudf::segmented_gather(), if the list<bool> is transformed into a gather map.

[mythrocks]

I'll take a quick stab at it.

[jrhemstad]

cudf::segmented_gather(), if the list<bool> is transformed into a gather map.

Doing the stream compaction step of generating the gather map would be the hard part.

bool mask: { [T, T, F], [F, F], [F, T, F, T] }
// maps to:
gather map: { [0, 1], [], [1, 3] }

Typically stream compaction algorithms like copy_if are implemented via a sum scan + scatter_if where the sum scan is over the predicate condition and will then tell you for each element that passes the filter where it should be scattered to. The column level apply_boolean_mask does this but with a custom kernel largely to handle the null masks.

I like @revans2 idea of just using the regular apply_boolean_mask against the child columns with a post-processing step to figure out how many elements in each list passed the filter to calculate what the offsets should be for the resulting list column.

[jrhemstad]

I like @revans2 idea of just using the regular apply_boolean_mask against the child columns with a post-processing step to figure out how many elements in each list passed the filter to calculate what the offsets should be for the resulting list column.

Alternatively, you could run the normal apply_boolean_mask with the filter extracted from the segmented filter column against a segmented sequence to generate the gather map.

E.g.,

bool mask: { T, T, F, F, F, F, T, F, T } // extract segmented mask child, zero copy

segmented sequence: { 0, 1, 2, 0, 1, 0, 1, 2, 3 }

apply_boolean_mask result:  {0, 1, 1, 3}

I think the only benefit of doing it this way is it defers any support for arbitrary nesting to the implementation of gather. Unless apply_boolean_mask supports arbitrary lists/structs already?

[mythrocks]

run the normal apply_boolean_mask with the filter extracted from the segmented filter column against a segmented sequence to generate the gather map.

This is what I was considering. But my view is coloured by my familiarity with segmented_gather(). It could well be true that apply_boolean_mask handles arbitrary nesting already.