Add string_view and binary_view Logical types

[wjones127]

I'd like to add new logical types:

String value	Arrow type
string_view	Utf8View
binary_view	BinaryView

These would be encoded by default the same as LargeUtf8 and LargeBinary (using 64-bit offsets). And they could be decoded either from 32-bit or 64-bit offsets. The default encoding of 64-bit offsets is chosen to be safe for large values (> 2GB).

Proposed spec changes: wjones127#5
In progress library changes: #5685

[westonpace]

I guess this raises the question of what does it mean for a logical type to be added to lance? Does this mean that engines will need to support this type? Do Spark and/or Ray have support for the view types?

[wjones127]

I guess this raises the question of what does it mean for a logical type to be added to lance?

At a minimum, we need to define the string value that goes in the logical type field in the protobuf, what it means, and how it is allowed to be encoded in Lance files.

[wjones127]

I don't think we need to define the in-memory format that's it's decoded into. An engine might decode String, LargeString, and StringView into the same type if it didn't really differentiate those.

If we wanted to, we could alternatively deprecate the large_string logical type, and use the Arrow dataset approach of putting the expected Arrow schema in the metadata. Then the choice of String, LargeString, and StringView could be somehow separate from the Lance definition of logical type. But then that becomes a sort of standard on it's own that multiple engines might want to read.

[westonpace]

Here's some things we need to consider.

• Basic
  • String value that goes into the logical type field in the protobuf
  • Semantic definition of the type (purely informative, a type is really formally defined by its compute functions)
• Storage (two possibilities I can think of)
  • The spec declares what arrow type is used for storage (less flexible but storage doesn't need to know about lance types)
  • The storage receives the lance type and decides how to store it on its own (more flexible but I don't think we need this flexibility, in other words, the arrow type and the data itself will be sufficient to pick encodings)
• SQL
  • How are literals formed?
• Ingestion
  • What arrow types will be accepted when receiving new data (e.g. if the column is int32 and the user provides an int64 array do we downcast)? Or do we just always force the user to explicitly convert (some precedent for implicit conversion here with JSON)
• Output
  • What arrow type will be output by default?
• Compute Functions
  • What compute functions are provided for the type?
  • What casts are allowed for the type and what are the casting rules?
• Indexes
  • Which indexes are supported for the type (e.g. can we do btree on string view)

[westonpace]

Now that I think about it more, I have a new question. When do we need to add a new logical type? I can think off the top of my head of two potential criteria.

1. We need to add a new type when we have a different semantic concept (e.g. there are a different set of compute functions and their behavior is different)
2. We need to add a new type to give some hint on how the type should be stored and decoded

So far, the motivation for our types, has mostly been category 1. I think this is more traditional for databases. I think it is rare that a database allows for category 2 to be a valid justification for a new type. For example, there is no Dictionary type in Snowflake, Postgres, or Databricks.

By this rationale, I would argue that we should not create string_view and binary_view logical types. What if, instead, we had the following...

• Users pick types based on semantic meaning
• If a proposed type does not offer any new semantic meaning it is simply a variation or encoding
• The storage layer looks at the data to pick the best encoding to use for storage
• During a query the user states the encoding they want
• The compute engine decides what encodings to use between the storage and the user output

So, for example:

The user ask for a string column and they say they will accept any encoding. The query engine looks at the plan and doesn't see any fancy operations. The query engine asks for the array from the storage layer and says it will accept any encoding. The storage layer just gives back the default string array, the compute layer passes that to the user.

The user asks for a string column and they say they will accept any encoding. The query engine looks at the plan and sees a sort on the string column and knows it will be faster as string view. The query engine asks for the array from the storage layer but indicates it would prefer the string view encoding. The storage layer decodes directly into string view and passes the data back that way. The string view array is given back to the user.

The user asks for a string column and says they want a basic arrow string array. The query engine then looks at the plan (maybe there is a sort) and has to make a judgement call to do string-view -> sort -> string cast -> user or just do string -> sort -> user.

Anyways, the point I am getting at here, is that it should be the query engine (and perhaps the storage layer) that picks between various encodings. These should not be logical types. (disclaimer: this is basically the same as the Substrait rules for data types too)

[wjones127]

that it should be the query engine (and perhaps the storage layer) that picks between various encodings.

I do like that idea. It would be cool if we can implement physical optimizer rules that can alter the schemas read based on optimizations like these. Using string_view in for plans that involve sorting strings is a good example. I imagine we might have similar rules for dictionary encoding, maybe based on cardinality statistics or even operations.

[wjones127]

I've spent a bit more time thinking about this, and started a proposal to simplify our current logical types along these ideas: #5864