Spec Formalization: Consensus on type system

[jacques-n]

To start to make progress towards a complete specification, the first step of formalization is to try to decide on the type system. The sketched approach has the following properties:

• Only include a type that exists in at least two of Spark, Trino, Iceberg and Arrow.
• Collapse physical representations into the logical type system as variations as opposed to a separate system. For example string versus large string in Arrow.
• Expose user-defined types as named constructions of existing types. For example, uint16 could be a user-defined type of FixedBinary(2)
• Avoid parameterizing date/time types for resolution. Instead just have two resolutions at most (typically micro and milli).

Some important discussion points:

• Union is not included as only Arrow has a union type.
• UUID is not included as UUID isn't clearly defined in Iceberg. I believe it is in the code but not in the published spec.
• No unsigned integer types (only exist in Arrow)
• Can a map have the same key multiple times in the same record? (I believe this should be disallowed)

[jorgecarleitao]

Collapse physical representations into the logical type system as variations as opposed to a separate system. For example string versus large string in Arrow.

What is meant with this? That from our perspective Utf8 and LargeUtf8 should be both mapped to a common physical representation (or to a logical one?)

[jacques-n]

I think we have differing expectations of how decomposed this process can be. I think that's okay. While it may be the case that some systems do all of this internally, I think some systems will try to federate it. I think the key goal should be something that doesn't limit this use case. So what I'd like to propose is something simpler. Extensible "variations" where a user can create there own variations and still integrate with other systems. In the common case, people use the default variation. If two systems want to work together with several variations, they can express those within Substrait effectively (and across systems). The variations can be expressed similar to how other extensions in substrait are done. Namespacing the variations allows things to be compatible even if individual systems have specialized representations.

I'll post a patch with this pattern to further this discussion.

[jacques-n]

You know what, the more I worked on this patch the more I'm inclined to just dump the idea entirely and rely on the user defined types. As I stubbed out variations, it just felt like a second version of user defined types and I don't think we win anything with introducing it within the existing types. As such, I've posted this PR. It's on top of another pr so in my local repo until the other is merged. Each system can decide what the default representation is. If someone wants to write a plan across two variations of utf8, they can do so (e.g. dict and not). They can do so, they just need to agree on the user defined type definitions for each variation.

[jacques-n]

Posted #23

[westonpace]

Apologies if this feels like I'm arguing both sides but I am -0.5 on just custom types. I do agree with Micah's point from the PR:

Logical Encodings - On the surface I think I agree with your assertion from the thread that having this modeled is likely important.

I've been trying to think up example use cases on this topic and I have a few more and I'll restate the one I described above regarding dictionary encoding. In these use cases interpret "general purpose" as "implementation agnostic":

1. I want to create a general purpose plan optimization library that rewrites WHERE X < 50 AND (Y > 20 AND X <= 100) into WHERE X < 50 AND Y > 20. This will rely on me knowing that the < operator for the given types is transitive. If X is "int16 with XYZ encoding" then I know this is true. If X is "int16_XYZ" then I don't know this.
2. I want to create a general purpose plan validation/sanitization library that identifies WHERE X > Y as an error because X is of type "int16" and Y is of type "string" and those two types are not comparable. This works if X is "int16 with XYZ encoding" but not if X is "int16_XYZ"
3. I want to create a general purpose optimization library that identifies when converting to dictionary encoding would be more efficient (because several operations will be carried out on the type that are cheaper in dictionary encoding) and it expresses this by introducing "dictionary_encode" and "dictionary_decode" steps.

Now, there are other ways to enable these use cases too:

A. We could allow arbitrary metadata to be attached to types. Then the plan that wants to use "int16 with XYZ encoding" can simply attach "with XYZ encoding" as some kind of custom metadata
B. The query engine that wants to use "int16 with XYZ encoding" simply doesn't attach it to the query plan until some kind of final plan that doesn't get sent out to any third party library
C. Point 2 Could be solved by sending the available function registry into the library along with the query plan so it could look up if "gt(int16_XYZ,string)" is supported

[jacques-n]

I created a new alternative proposal for type variations @ #25. It allows for variations for a single logical type. It also specifies whether the functions for a canonical variation can be used for another variation (which I think is probably important to be able to configure depending on the nature of the execution engines capabilities).

[michaelmior]

Given that I saw your announcement of Substrait on the Calcite mailing list, I'm curious why Calcite isn't on the list of systems :)

[jacques-n]

Good question :). A few reasons:

• Much of Calcite's type system is relatively old. For example, here is a todo from 2004. Just because a type was important (using inclusion in pre-Calcite Calcite as an indicator of importance) in the early 2000s, doesn't mean it's still important.
• Calcite is (by and large) a library as opposed to being an end user system. Just because a type exists in Calcite doesn't mean any end-user systems use that type.
• I felt like keeping the list small was important. We already have two projects that lean towards the SQL/database side of the world (Trino and Iceberg) so I didn't think we needed another one.

A key thing to point out is the list is absolutely open for discussion. I tried to come up with a list of systems that were:

• Directly exposed to end users.
• Built around open source community
• High amount of usage (or trending that way)
• Did a good job of representing both databases and data science tools/workloads
• Relatively modern
• Not too many

[TheNeuralBit]

It's still a good point that the list feels arbitrary. Is it fixed, or is there a way for a system (maybe "project" or "community" is a better term here) to become a "voting member"?

I like the idea of starting something new to foster cross-project collaboration, but to me calling out specific consumer projects like this feels almost the same as if the spec were defined in one of those projects.

[wesm]

Since data types are a pretty foundational concept in substrait, it seems like we would want to be very explicit that the project wants to hear from as many producers/consumers as possible to try to accommodate as much real world use as is feasible. To list projects that are affiliated with one or more Substrait contributors would help to highlight the intention to be broadly inclusive

[jacques-n]

Since every separate project generally prefers "their" types, the collection + quorum approach seemed like a reasonable way to move to start with a reasonable set of types. @TheNeuralBit, do you think the overall approach is reasonable or do you think something else would be better?

In terms of the content of the list, I'd like to think it is more subjective (given the set of criteria described above) than arbitrary. :D

I think we're all definitely open to adding more projects that people think are relevant. @TheNeuralBit, is your concern that a particular set of use cases or types are missing?

As @wesm said, the goal here is to be collaborative and inclusive. Right now the "substrait community" is pretty much anyone who shows up and has an opinion. If you argue for the inclusion or exclusion of a system and others agree, great!

@wesm, since contribution is relatively casual right now, what do you think would be a good way of going about highlighting the inclusivity? I guess I could post something akin to an "interested parties" page and people could add themselves to that if they wanted to.

[cpcloud]

No unsigned integer types (only exist in Arrow)

Other than the fact that this doesn't exist anywhere except Arrow, is there a reason not to include unsigned integer types? I guess it's not clear to me why they are deemed unimportant.

[jacques-n]

Totally up for grabs. Would love to hear people's thoughts on this.

I thought of slotting Arrow into the same category as Calcite as "framework as opposed to end user facing" however it feels like Arrow is much more end user facing. Since the Arrow type system is defined once, I was inclined to consider as one of the voting systems. Some of the same questions around Arrow could probably be asked around Spark, where there are many tools that "expose" Spark concepts.

Do you think an alternative or adjusted rubric makes would be better?

[pdet]

Now that we are pushing substrait integration in DuckDB, I would like to advocate for DuckDB to be one of the systems used in the type selection rule.
The main things we are currently missing in terms of types (which are also present in Arrow) are unsigned integers and hugeint (128-bit). The unsigned integers are mainly used in casts for certain query optimizations, and the hugeint is used in most scalar aggregations. I'm currently hacking it up on the DuckDB side by upcasting uints to signed ints and having hugeints as decimals; that's of course not desirable.
If you are all ok with these types, I'm happy to send a PR to substrait.

[emkornfield]

small nit, Arrow doesn't support 128-bit integers. I guess they could be closely emulated with DECIMAL(38, 0) though.

[westonpace]

I'm +1 on adding DuckDb as one of the systems. I agree with Micah though, this doesn't give you hugeint support (and I'm uncertain if 2 out of 5 would be sufficient for unsigned integers).

I'm hoping to make progress on YAML for all Arrow types over the next few months (by the 9.0.0 release)

[jacques-n]

Hey all, I feel like there are several separate points to discuss here:

1. What is the purpose of the four system pattern described in this original post and should we update it?
2. When should we add new types versus use type extensions?
3. Should we add u8, u16, u32, u64 (unsigned variations of existing types)?
4. Should we add a i128?

For (1): two main thoughts:

• The four system pattern was: "at least half of common systems have the types". It was designed to try to come up with some kind of "average" of common systems to support an initial list of native types. It was never meant to be used on an ongoing basis. Once we have an initial implementation, the intention was to discuss and decide as a community what types should be added. It was subjective and about a point in time. In general, I'm more inclined to simply remove the whole reasoning around the original four types perspective. It was for when this started six months ago, not for now. Further, I think it would be unhealthy for a "Switzerland" project to start having a process in Substrait of deciding what systems are first class versus second class. We shouldn't be the arbiter of what systems are "worthy" of being included in such a list.
• If we were to add other systems' types bulk to the list, I would expect us to still maintain the "at least half" rule, meaning that we'd say at least 3 out of 5 systems need a type. This makes things super confusing since that would imply that not only should certain types be added, certain existing types would be tagged for possible removal. (Thus, my general thought that this system served its initial purpose but should now be retired.)

For 2: several thoughts:

• I think it would be good to start to stratify committers or a similar concept and have a process around these kinds of changes. We should definitely define something here so that people feel like the system is documented, reasonable and consistent. (Similar to how we do format changes in Arrow.)
• We could make part of that process be that initially the types identified are being shared across at least two serious consumption systems using a common user-defined type definition. (Seems like a reasonable lower bar.)
• There are actually three levels of definition and we need to come up with an approach of where things should be located.
  • 3rd party extension defined: Easiest way to establish a new types for your Substrait plan.
  • 1st party extension defined: Show up in many places, not sure we want them to be defined in the format spec yet.
  • 1st party native: We think it is worth having these in the most central place.
• I'm curious what reason specifically drives people to want native types over user-defined types. Are there specific things that are too painful right now with user-defined types? If so, we should also look to address those issues. Two challenges I'm aware of:
  • Function to udt resolution currently requires being defined in the same extension file I believe (we should fix this)
  • We haven't defined a way to have a parameterized user defined type (we should fix this)

For 3: I'm open to this. I think it should be evaluated in the context of where this is needed and how pressing the need is. Which systems are trying to use these together and struggling? (I think Arrow and DuckDB?)

For 4: As noted above, it sounds like this is only in DuckDB of the 5 systems mentioned. If that's the case, it seems like it makes the most sense to treat it as either a 1st or 3rd party extension defined type(?).

[emkornfield]

Would it make sense to start with a simpler type system? Having duplicative representation of some of the types (time and timestamp) I think has caused some awkwardness for consumers of Arrow (I'm thinking of some threads on there use in DataFusion, but I could be misremembering).

Interval<Day> I think has also caused some confusion (Is the seconds component always normalized to be less than 1 day or not). There is also more esoteric interval definitions (parquet and avro define it as a triple of unsigned month, day, and year I believe).

[emkornfield]

For time I'm assuming you mean milli versus micro? The milli is more due to legacy reason than anything else.

Yes.

In all honesty, I'd love to drop to only resolution 6 for time and timestamp. They have better cross-system coverage.

I think it was worth considering, until someone complains. I guess one way of interpreting two system approach is necessary but not necessarily sufficient condition for inclusion. I'm OK leaving the values as is, but thought it was worth a discussion. Maybe other people have opinions here.

[jacques-n]

I'm +1 on removing the milli types for timestamp/time/timestamp_tz.

Honestly, it's hard to shed some of the old peculiarities of the Dremio codebase given how long I worked on it :) Using a more objective approach, I wouldn't have added these types too. I also like you're point on inclusion 2 minimum being necessary but not sufficient. We should continue try to better codify the concept if people are on board with it.

[westonpace]

I'm also +1 on only microsecond resolution. Even if a platform didn't support microsecond resolution (e.g. browser-based JS) it is usually easier to truncate at the boundary than it is to try and manipulate the data in transit and there is no practical performance reason to do so since both types are 8 bytes.

[jacques-n]

Posted patch #22 that only includes microsecond resolution. The one thing a little awkward is that means time must be 64 bytes instead of millis's requirement for 4 bytes. I'm okay with this.

[emkornfield]

One other item on timestamps. Pandas only supports Nanos, so I suppose plans that it could generate would have to do the conversion at the boundary?

[emkornfield]

Should Decimal(P, S) where P <= 38 be added as a type? It exists in Arrow and Trino

[emkornfield]

As such, I think we should adopt the same range. Want to propose a patch to update the language to declare the restricted range?

Will do.

As an additional note, I'm struggling with the need for a second physical type (128b) for decimal beyond system default. Wouldn't a system simply define that a decimal(p<=18,x) is 128bit and decimal(18>p<=38,x) is 256 bit? Do we really need a second physical type in the Arrow case?

Arrow's Decimal256 allows for precision <= 76 (I think the math is above little off. precision <= 18 is 64 bits I think and 18>p<=38 128 bit, 38>p<=76 is 256 bits). Most SQL systems seem to have Decimal/Numeric max precision 38. The exceptions
are postgress (insanely large range), vertica (seems to be precision <= 1024) and BQ which only has a Decimal(76.xx, 38) type.

[emkornfield]

#19

[jacques-n]

Wow, I was thinking arrow was 64 and 128. In my comment I reviewed everything except Arrow (as I was thinking I knew it offhand). So let me clarify, everything has a decimal(>=38,*). Arrow has a second thing that we should probably keep out here given two system rule.

I didn't see the discussion to add the 256 bit version. Sadness. It actually makes me start to wonder whether Arrow is actually the right system to include here. Introducing a single operation or a small set of operations for a single type is a relatively low bar compared to figuring out how it works inside a more complex ecosystem. Decimal is especially gnarly. Part of the reason to limit the size of decimal in a query system is that otherwise decimal operations get arbitrarily slow since virtually all operations cause up-promotion until you hit the precision limit.

[emkornfield]

So let me clarify, everything has a decimal(>=38,*). Arrow has a second thing that we should probably keep out here given two system rule.

Agreed (>38 doesn't belong as a core part of the spec) except I think this statement is meant to be (<=38) above.

I didn't see the discussion to add the 256 bit version. Sadness.

I think you actually expressed some reservation on the type when it was being proposed.

Part of the reason to limit the size of decimal in a query system is that otherwise decimal operations get arbitrarily slow since virtually all operations cause up-promotion until you hit the precision limit.

Yes, I think this is one good reason for limiting to 256 bytes, and not going to essentially unlimited precision like Vertica/PostGres. It is probably on the upper bound of giving decent performance.

It actually makes me start to wonder whether Arrow is actually the right system to include here.

I think the two system rule serves us well here. As discussed earlier in the thread there are a lot of one off variants that are odd and arose for different reasons. Traditional RDBMS do seem to have more of these peculiarities and I think making Arrow more friendly towards them has potentially introduced some rough edges.

[jacques-n]

I think you actually expressed some reservation on the type when it was being proposed.

I guess it is better to be forgetful and consistent than not forgetful and inconsistent :D

[westonpace]

Piggybacking on @emkornfield 's suggestion of a simpler type system I would at least open for discussion the idea dropping support for TIMESTAMP_*_TZ. A field-level TZ offers near-zero useful information. And the concept itself introduces plenty of confusion. For example, if I were to read the current definition in Substrait A timestamp in microseconds with a timezone TZ. I could (incorrectly I presume) assume that every cell has an independent timezone.

If the info is needed for compatibility / pass through then we could define a standard way to expose that in metadata or it could be exposed by the serialization / deserialization of data.

Functions that need to operate on a particular time zone could simply take the time zone as an argument. For example, if I want to convert a timezone to a display string in my local timezone then the function should be strftime(timestamp, timezone) If I want to do what pandas calls tz_localize (and what C++Arrow is going to call assume_timezone) then the function could be tz_localize(local_datetime_as_utc_timestamp, timezone) where the function only makes sense if given a UTC timestamp.

Alternatively, we could have timestamp and localdatetime (or naivedatetime). The latter could be represented by a timestamp (as it is in Arrow) or even by a DATE32/TIME64 tuple but it would represent the semantic concept of a "local/naive datetime". This is closer to Parquet's isAdjustedToUtc than Arrow's timezone.

[jacques-n]

In most systems there is also a concept of session timezone (let's call this presentation timezone). When you do a select * on a timestamp with timezone column you see the time presented in the context of presentation timezone. The purpose of timezone in the in-flight types like substrait and arrow is that the schema carries the same kind of knowledge. In a distributed system, the "session" timezone may be defined a long way from the system interpreting the data. In the context of substrait I was applying this knowledge to the type.

To me, the alternative way to interpret the meaning of timestamptz operations is that functions that need it take "presentation timezone" as an additional input. This should provide the same functionality as the parameterization being on the type itself. The only confusing part I see about this is that if a system does an auto-discovery of available functions (or similar), this additional "internal" argument may be confusing and would typically be populated by a plan producer rather than an end-user.

Net net, I'm fine either way. Interested if others have a specific preference.

[jacques-n]

As a I've thought about this more, I'm inclined to drop the parameter and instead introduce context. See the discussion here #24.

[rdblue]

I agree with @westonpace. I don't think that there is a need for the zone parameter in timestamptz. The session time zone is a different thing: it is what zone your timestamptz will be shown in. But in my opinion, timestamptz should always use UTC as the reference zone. That makes all timestamptz values directly comparable and avoids needing to specify zones. Zones are managed by processing engines, but concrete values are always UTC.

[jacques-n]

I will post an update that removes the timezone parameterization as soon as the type variation patch gets merged. Thanks!

[jacques-n]

Update in #27