[FEA] Support reverse

[viadea]

I wish we can support reverse function.

select reverse(a) from test_diff_schema_evo;
    ! <Reverse> reverse(a#0) cannot run on GPU because GPU does not currently support the operator class org.apache.spark.sql.catalyst.expressions.Reverse

[revans2]

I don't see any existing cudf functionality that will do what we want. @viadea do you want revers for string, array, or both?

We will need separate kernels or APIs for each of these. This is because just reversing the bits in a UTF-8 string will not reverse the string because strings are multi-byte.

[viadea]

@revans2 String is good for now. i can show you a real example offline

[ttnghia]

In cudf string is just a special case of array: array of chars. So we can support both at the same time.

[ttnghia]

Some example:

scala> val df = Seq("this is a string", "another test string").toDF("s")
df: org.apache.spark.sql.DataFrame = [s: string]

scala> df.show
+-------------------+
|                  s|
+-------------------+
|   this is a string|
|another test string|
+-------------------+


scala> df.selectExpr("reverse(s)").show
+-------------------+
|         reverse(s)|
+-------------------+
|   gnirts a si siht|
|gnirts tset rehtona|
+-------------------+


scala> val df2 = Seq(Seq(1, 2, 3), Seq(4, 5, 6)).toDF("i")
df2: org.apache.spark.sql.DataFrame = [i: array<int>]

scala> df2.show
+---------+
|        i|
+---------+
|[1, 2, 3]|
|[4, 5, 6]|
+---------+


scala> df2.selectExpr("reverse(i)").show
+----------+
|reverse(i)|
+----------+
| [3, 2, 1]|
| [6, 5, 4]|
+----------+

[ttnghia]

I was worried if reverse("this is a string") could produce "string a is this" but it didn't, which is very good.

[revans2]

The problem is that strings are stored in UTF-8, which supports multi-byte characters. ASCII we can probably do it very simply, but for anything that is not ASCII it will potentially corrupt the string.

[ttnghia]

I see-so the same implementation can't be used for both, but the implementation should be very similar and straightforward.

[revans2]

For a list reverse a gather map would likely work well. It would be even better if you could not have to materialize the gather map, because for some list types the gather map is going to be larger than the list column itself. But that is probably a minor optimization.

If you look at https://github.com/rapidsai/cudf/blob/branch-23.02/cpp/include/cudf/strings/detail/utf8.hpp it provides APIs to be able to see if the current byte is part of a multi-byte character or not, and what the length of it is. If you can find a good way to do this type of thing in parallel, then great. But from what I have seen most of the string APIs work by having a single thread per string. Even then we might be able to play some games to coalesce reads and writes to speed things up.

[ttnghia]

We also have a duplicate FEA issue: #4375.

[sameerz]

Also depends on rapidsai/cudf#12283

[ttnghia]

The libcudf PR for array input type was merged (rapidsai/cudf#12336). We can continue to complete our plugin work.