search

apache / datafusion

Apache DataFusion SQL Query Engine
https://datafusion.apache.org/
Apache License 2.0
5.47k stars 1.01k forks source link

[Epic] Implement support for `StringView` in DataFusion #10918

Open alamb opened 2 weeks ago

alamb commented 2 weeks ago

Is your feature request related to a problem or challenge?

StringView / BinaryView were added to the Arrow format that make it more suitable for certain types of operations on strings. Specifically when filtering with string data, creating the output StringArray requires copying the strings to a new, packed binary buffer.

GenericByteViewArrary was designed to solve this limitation and the arrow-rs implementation, tracked by https://github.com/apache/arrow-rs/issues/5374, is now complete enough to start adding support into DataFusion

I think we can improve performance in certain cases by using StringView (this is also described in more details in the Pola.rs blog post)

  1. Reading strings / binary from Parquet files as StringViewArray/BinaryViewArray rather than StringArray / BinaryArray saves a copy (and @ariesdevil is quite close to having it integrated into the parquet reader https://github.com/apache/arrow-rs/issues/5530)
  2. Evaluating predicates on string expressions (for example substr(url, 4) = 'http') as the intermediate result of substr can be called without copying string values

Describe the solution you'd like

I would like to support StringView / BinaryView support in DataFusion.

While my primary usecase is for reading data from parquet, I think teaching DataFusion to use StringView (at least as intermediate values when evaluating expressions may help significantly

Development branch: string-view

Since this feature requires upstream arrow-rs support https://github.com/apache/arrow-rs/issues/5374 that is not yet released we plan to do development on a string-view feature branch:

https://github.com/apache/datafusion/tree/string-view

Task List

Here are some high level tasks (I can help flesh these out for anyone who is interested in helping)

Describe alternatives you've considered

No response

Additional context

Polars implemented it recently in rust so that can serve as a motivation Blog Post https://pola.rs/posts/polars-string-type/ https://twitter.com/RitchieVink/status/1749466861069115790

Facebook/Velox's take: https://engineering.fb.com/2024/02/20/developer-tools/velox-apache-arrow-15-composable-data-management/

Related PRs: https://github.com/pola-rs/polars/pull/13748 https://github.com/pola-rs/polars/pull/13839 https://github.com/pola-rs/polars/pull/13489

alamb commented 2 weeks ago

I think we should aim for a first "milestone" of showing improvements for some clickbench queries

jayzhan211 commented 1 week ago

Will we completely change StringArray to StringViewArray in Datafusion? While I try to utilize StringViewArray in #10976 , I found there is schema mismatched issue UTF8 vs UTF8View. To avoid converting StringViewArray to StringArray, we might need to change the schema to UTF8View overall from logical plan to physical plan. If we need to keep both String and StringView, then we need to think about how to deal with the conversion between these two types.

A more concrete example is

statement ok
create table t(a int, b varchar, c int) as values (1, 'a', 3), (2, 'c', 1), (1, 'c', 2), (1, 'a', 4);

We have the string column b as StringArray and DataType::Utf8 now. Should we convert it to StringViewArray and DataType::Utf8View?

If not, if we somehow want to utilize StringViewArray, how do we minize the cost of conversion between String and StringView?

It seems Polars completely refactor their String to StringView 🤔

alamb commented 1 week ago

Will we completely change StringArray to StringViewArray in Datafusion?

I think since they are two separate types in Arrow we couldn't fully switch to StringView the way polars could as it controls the whole stack. Users could still feed DataFusion StringViewArray from custom TableProviders and would expect StringView at the output.

However what I think we could do is internally to DataFusion (e.g. within the plan, before the final output) is use StringView in the batches that flow through intermediate nodes in the plan.

I found there is schema mismatched issue UTF8 vs UTF8View. To avoid converting StringViewArray to StringArray, we might need to change the schema to UTF8View

Indeed, As you point out, I don't think we can transparently switch to using StringView -- instead we would have to start encoding information in the plans about the new types.

I wonder if we could have a new logical optimzier pass that tried to annotate operations that support it to use StringView in their schema rather than String. Then the ExecutionPlans would know if they were supposed to generate StringView as output or the more traditional StringArray 🤔

Here is an idea of one place to start: https://github.com/apache/datafusion/issues/9403#issuecomment-2178347730

alamb commented 1 week ago

I think @XiangpengHao is looking into another place to use StringView which is https://github.com/apache/datafusion/issues/10921 -- where we have a similar idea to use StringView in some sub portion of the plan. Here is more info about the optimizer pass idea: https://github.com/apache/datafusion/issues/10921#issuecomment-2178364966

alamb commented 1 week ago

I think this project is going pretty well :bowtie:

We are at the point of starting to implement some basic functions using StringView.