Instead of using Concatenate here, I think it'd be better to use std::vector<ArrayVector> RechunkArraysConsistently(const std::vector<ArrayVector>&); (defined in array.h). After that the the chunks will be equal length, suitable for filtering.

Thanks, I'll look into that.

This can be addressed later, but: there's an unfortunate missed optimization here. Since we're reusing the same filter for each column we don't need to recount the set bits in each chunk of the filter for every column (see the record batch overload which takes advantage of this optimization).

Another missed (deferred) optimization would be to parallelize the filtering across the columns rather than iterating in serial.

I'll take a look at the one you reference and see if I can translate it for tables; otherwise I'll make followup Jiras.

I don't think it's necessary to pre-emptively add every possible permutation here. I added the RecordBatch overload because I specifically planned to use it in arrow::dataset::. Although it saves a few lines of code which would otherwise be necessary to box/unbox from compute::Datum, I think most consumers should rely on the Datum overload.

It's not preemptive, there are different implementations for each signature. Maybe you can show me what you mean; I haven't worked with Datum objects.

Instead of concatenating here, you could flatten chunks from current_chunk directly into new_chunks:

ArrayVector new_chunks;
for (const auto& indices_chunk : indices.chunks()) {
  std::shared_ptr<ChunkedArray> taken;
  RETURN_NOT_OK(Take(ctx, values, *indices_chunk, options, &taken));
  std::move(taken->chunks()->begin(), taken->chunks()->end(), std::back_inserter(new_chunks));
}

(of course it's a moot point until Take(ChunkedArray values, Array indices) can also avoid concatenation)

The point of this concatenate was that the resulting chunks should correspond to the chunks defined by indices, as @jorisvandenbossche suggested. This, of course, gets us back to the original discussion of what chunks are for, whether they are purely an internal implementation detail or something that users should govern, what "optimal" chunking is, etc.

I think optimal chunking for output from a kernel is whatever allows the consumer greatest control over allocation and other performance overhead. Based on this: concatenation should be kept to a minimum since that generates new allocations instead of cheaply slicing existing ones. As a secondary consideration, the chunked array should have as few chunks as possible since large contiguous chunks can be processed more efficiently than lots of short chunks. Based on that: an output chunked array should not contain empty chunks.

The point of this concatenate was that the resulting chunks should correspond to the chunks defined by indices, as @jorisvandenbossche suggested. This, of course, gets us back to the original discussion of what chunks are for, whether they are purely an internal implementation detail or something that users should govern, what "optimal" chunking is, etc.

Another missed (deferred) optimization would be to parallelize the filtering across the columns rather than iterating in serial.

I'll take a look at the one you reference and see if I can translate it for tables; otherwise I'll make followup Jiras.

It's not preemptive, there are different implementations for each signature. Maybe you can show me what you mean; I haven't worked with Datum objects.

Thanks, I'll look into that.

We should create a function that accepts a lambda for chunked evaluation so this logic can be reused in other places. Does not have to happen in this patch

Same with this logic. I'm not sure about the concatenation part, it seems like you would want to split larger chunks into smaller pieces, yielding an output that has more chunks than the input

e.g.

array chunks [10, 10, 10, 3]
filter chunks [5, 5, 5, 15, 3]

output chunks [5, 5, 5, 5, 10, 3]

Re: chunking strategy, see https://issues.apache.org/jira/browse/ARROW-7012

nit: not fond of condensed variable names like schm

If I don't do something like this, I collide with the function named schema:

/Users/enpiar/Documents/ursa/arrow/cpp/src/arrow/compute/kernels/filter_test.cc:492:17: error: variable 'schema' declared with deduced type 'auto' cannot appear in its own initializer
  auto schema = schema(fields);
                ^

This is wasteful because values is going to be concatenated over and over for each chunk in indices. Can you add a note here to note this is bad and open a follow up JIRA?

I'll add the note. I think this falls under https://issues.apache.org/jira/browse/ARROW-7012.

Frankly I would prefer a Take(FunctionContext*, const Datum&, const Datum&, ...) based API to this combinatorial explosion of functions. If this is not done in this PR, can you mark these functions as experimental so that we can change things without need for a deprecation cycle?

Will mark as experimental. See also https://issues.apache.org/jira/browse/ARROW-6959 about Datum policy.

Per comments on Take below I think that using Datum and having fewer public APIs would be better. There are implicit ctors for Datum to make the usage easier

I briefly looked into refactoring to use Datum but it didn't seem like a good use of my time right now to figure it out. https://issues.apache.org/jira/browse/ARROW-7009 is for someone else to pick that up.

No problem