[C++] String algorithm library for StringArray/BinaryArray

[asfimport]

This is a parent JIRA for starting a module for processing strings in-memory arranged in Arrow format. This will include using the re2 C++ regular expression library and other standard string manipulations (such as those found on Python's string objects)

Reporter: Wes McKinney / @wesm

Related issues:

• [C++/Python] Kernel for SetItem(IntegerArray, values) (is a parent of)
• [C++] String concatenate aggregate kernel (is a parent of)
• [C++] Implement string space trimming kernels: trim, ltrim, and rtrim (is a parent of)
• [C++] Add string struct extract kernel using re2 (is a parent of)
• [C++] Add scalar string join kernel (is a parent of)
• [C++] Add string length kernel (is a parent of)
• [C++] Add regex string match kernel (is a parent of)
• [C++][Python][Compute] String hex to numeric conversion and bit shifting (is a parent of)
• [C++] Add variadic string join kernel (is a parent of)
• [C++] String repeat kernel (is a parent of)
• [C++] String reverse kernel (is a parent of)
• [C++] String title case kernel (is a parent of)
• [C++] SQL-style glob string match kernel (is a parent of)
• [C++] Left/right/center string padding kernels (is a parent of)
• [C++] Substring find position kernel (is a parent of)
• [C++] String capitalize kernel (is a parent of)
• [C++] String swap case kernel (is a parent of)
• [C++] Add string slice replace kernel (is a parent of)
• [C++] Add string starts-with/ends-with kernels (is a parent of)
• [C++] Add substring count kernel (is a parent of)
• [C++] Add regex count kernel (is a parent of)
• [C++] Add find_substring_regex kernel and implement ignore_case for find_substring (is a parent of)
• [C++] Implement min_max kernel for array[string] (is a parent of)
• [C++] String formatting kernel (is a parent of)
• [C++][Python][Compute] Number to string hex conversion (is a parent of)
• [C++][Compute] Add string translate kernel (is a parent of)
• [C++] Add is{alnum,alpha,...} kernels for strings (is a parent of)
• [C++] split kernels for strings/binary (is a parent of)
• [C++] Add scalar string slicing/substring extract kernel (is a parent of)
• [C++] Add split_pattern_regex function (is a parent of)
• [C++] Implement case insenstive match in match_substring(_regex) and match_like (is a parent of)
• [C++] Add string replacement kernel (is a parent of)
• [C++][Compute] Add binary reverse kernel (is a parent of)
• [C++][Compute] Add utf8_format kernel (is a parent of)
• [C++] Add locale support for relevant string compute functions (is a parent of)
• [C++] Add ascii_lower kernel (is a parent of)
• [C++] C++ array kernels framework and execution buildout (umbrella issue) (is a child of)
• [C++] Faster ascii_lower and ascii_upper (relates to)
• [C++] Add utf8_upper and utf8_lower (relates to)
• [C++] Implement example string scalar kernel function to assist with string kernels buildout per ARROW-555 (is related to)
• [C++/Python] Support necessary functionality to have an Arrow-string type in pandas (is depended upon by)

PRs and other links:

• Fletcher string kernel issue

_{Note: This issue was originally created as ARROW-555. Please see the migration documentation for further details.}

[asfimport]

Wes McKinney / @wesm:
Now that re2 is in our toolchain, we can implement kernels for each type of regular expression operation

[asfimport]

Wes McKinney / @wesm:
cc @maartenbreddels

[asfimport]

Joris Van den Bossche / @jorisvandenbossche:
Do we already have a good idea of how we want to approach this?
Because I think there has been some discussion on implementing custom C++ kernels (similar to other existing kernels in the compute module) vs finding a way to re-use the scalar kernels that are already implemented for gandiva.

For reference: Gandiva already has several string functions implemented. Illustration with the python interface for the "upper" function:

from pyarrow import gandiva
table = pa.table({'a': ['a', 'b', 'c']})

builder = gandiva.TreeExprBuilder()
node_a = builder.make_field(table.schema.field("a"))
node_upper = builder.make_function("upper", [node_a], pa.string())
field_result = pa.field('res', pa.string())
expr = builder.make_expression(node_upper, field_result)
projector = gandiva.make_projector(table.schema, [expr], pa.default_memory_pool())

>>> projector.evaluate(table.to_batches()[0])
[<pyarrow.lib.StringArray object at 0x7fc324f71580>
 [
   "A",
   "B",
   "C"
 ]]

[asfimport]

Maarten Breddels / @maartenbreddels:
Related: https://issues.apache.org/jira/browse/ARROW-7083

I will probably start working on this a few weeks from now. My initial intention would be to separate the algorithms as much as possible so it would be possible to add them both to gandiva and a 'bare' kernel, or with a minimal amount of refactoring.

@wesm: what's your reason to choose re2? Gandiva and vaex both use pcre, but I have no strong preference (except being a bit familiar with pcre).

 

[asfimport]

Wes McKinney / @wesm:
We've been having some discussions about this topic in other places, e.g. ARROW-7083. One idea that has been proposed is to generate single-function kernels at compile time based on the LLVM IR that Gandiva spits out. So the process would work like this:

• Generate a library of LLVM IR for all supported Gandiva kernels, with an exported manifest so that you can dynamically determine what kernels are available and what are their input and output signatures

• Compile that LLVM IR into a C shared library

• Implement a generic "invoker" that takes a C function kernel (the result of compiling the LLVM IR produced by Gandiva) and evaluates it (with memory allocation, etc. as needed)

  Then the LLVM runtime would not be required to use the output of this process.

  This would require some investment of time (perhaps not that much) to set up the machinery to enable this, but it would seem to greatly simplify the process of implementing new kernels, especially simple elementwise functions (for numbers, strings, etc.)

  We've been dancing around this idea for several months now so I would be interested to see if someone would be interested to explore this before tunneling too far in different directions.

  cc @emkornfield @pitrou @fsaintjacques @jacques-n [~ravindra] for any comments / thoughts if what I've written above jives with prior discussions

[asfimport]

Antoine Pitrou / @pitrou:
I think going through LLVM IR is a bit convoluted. More simply, since those functions are already raw C in Gandiva, we could reintegrate those C functions somewhere in Arrow (taking care that the Gandiva toolchain can still compile them to LLVM bitcode).

It would also avoid depending on LLVM for builds with Gandiva disabled.

[asfimport]

Antoine Pitrou / @pitrou:
I'm assuming C functions btw, but those may just as well be C++ functions (with the C wrappers on the Gandiva side). However, they can't use certain C++ stdlib facilities such as iostream (hence the split between Decimal and BasicDecimal).

[asfimport]

Maarten Breddels / @maartenbreddels:
What are the limitation, and is this somewhere documented? It might be good to keep those in mind.

[asfimport]

Wes McKinney / @wesm:
@pitrou that seems reasonable, cross-compilation (where a code unit is compiled both into a static/shared lib and to LLVM IR at the same time) indeed would be easier. This is a popular technique (e.g. Apache Impala does a lot of it – see all files with "-ir" in them in https://github.com/apache/impala/tree/master/be/src/exprs) so we should try not to reinvent the wheel

[asfimport]

Wes McKinney / @wesm:
We could even use Impala's string exprs (which is what Impala calls its "kernels") as a guideline for what we need to have available as Arrow kernels

https://github.com/apache/impala/blob/master/be/src/exprs/string-functions.h

[asfimport]

Micah Kornfield / @emkornfield:
+1 for simplicity, I think it is unlikely I will have time to contribute to this effort in the near future.

[asfimport]

Wes McKinney / @wesm:
Update: I'm in the middle of an overhaul of the API for implementing new Array functions / kernels, with the goal of making it much easier to add new functions (e.g. generating a string function given an inlineable implementation of computing a single value). Once that's done (since I'm working on it right now, it will be this month) I will probably ask someone from my team to make an initial cut at a precompiled string function set based on the functions that are already in Gandiva / LLVM codegen and add new functions (from e.g. Impala or other SQL engines) that are not yet present. The work need not be monolithic so as soon as the framework is in place it should be straightforward to add new functions and test them. Additionally, adding Python bindings for the new functions should also be easy (all you will need is the name of the function you're calling, so some of the Cython binding boilerplate that exists now should also go away).

[asfimport]

Maarten Breddels / @maartenbreddels:
I am likely to be able to start working on strings in Arrow this month, so I think the timing is good. Some pointers/examples to get me started would be great.

[asfimport]

Wes McKinney / @wesm:
Cool. I will circle back here once I have a PR up for the work I described in my comment, and will add an example string function to provide a template for adding more functions.

[asfimport]

Maarten Breddels / @maartenbreddels:
Something to consider (or should I move this discussion to the list?), is the support of ASCII vs utf8. I noticed the Gandiva code assumed ASCII (at least not utf8), while Arrow assumes strings are utf8 only. Having written the vaex string code, I'm pretty sure ASCII will be much faster though (you know the byte length of a string in advance). Is there interest in supporting more than utf8, ASCII for instance, or utf16/32? Or should it be utf8 only?