* Problem
The official protobuf library has a limit in depth during deserialization (https://protobuf.dev/programming-guides/proto-limits/#depth). The artificial limit is 100. Although the 100 limit seems reasonable for some applications, a reasonably complex production query plan can often go far beyond 100 nesting.
Substrait currently employs protobuf to describe the spec as well as de facto serialization/deserialization method. This means that the Substrait applications are likely to use the "official" protobuf library and will hit a dead-end on receiving a plan with more than 100 depth nesting.
* ProposalWe propose to extend Substrait spec to support fragmenting expression tree like RelOp tree.
This involves updating both serialization and deserialization. The serialization should be done in this "depth limit" conscious way – that is, the serialization should be done in fragments so that each fragment does not exceed the imposed depth limit. Note that another irk is that the nesting is in terms of protobuf nesting and we will need to validate whether oneof, for instance, is considered a nesting. There is also overhead of outer message as well (e.g., Plan itself takes up "1" in the limit).
Substrait Plan already has a way to do this by substrait.Plan.relations and ReferenceRel (i.e., fragment a large relational graph and re-build based on referencing fragments) but there is no such mechanism for an Expression.
Thus, we will need a similar way to fragment a large expression tree and referencing the fragment. Below is the proposed change to support fragmenting expressions.
message ReferenceExpression {
int32 subtree_ordinal = 1;
}
message Expression {
oneof rex_type {
ReferenceExpression reference = 14;
}
}
message Plan {
repeated Expression expressions = 6;
}
In addition to proto changes, we will need to update reference Substrait IR implementations to ease serialization and deserialization for applications.
* AlternativesThe consuming application simply fails on receiving such plans.
* Option b. Use other protobuf implementations without limitIf there is a good one... Anyone?
* Option c. Recompile official protobuf library with a higher limitThe current limit is hardcoded in the library and the only way to lift the limit is recompilation. Unless the official library provides a mechanism to override without recompilation, the only way to work around is to update the constant and recompile the library.
* Option d. Support beyond protobufThis practically means that we translate into other IDLs/schema description language (e.g., Apache Thrift, Cap'n Proto, FlatBuffers) and supported serialization/deserialization do not impose artificial limit. That is, Substrait is a "meta" spec, and supports multiple frameworks. This is maybe something to consider in the long run.