feat: add SubqueryAliasRel

[Blizzara]

Add SubqueryAliasRel that can be used to name/(re)qualify a downstream relation.

As Substrait mostly only referes to columns by their index, there is no inherent need for table name/qualifiers within Substrait. However, some consumers, e.g. DataFusion, require column names to be either unique or qualified for joins, which is troublesome w/o the possibility to qualify relations.

[Blizzara]

In my usecase, this is mainly a problem with VirtualTables in DataFusion. An alternative would be to add a name into the VirtualTable (or ReadRel) directly. However, having this SubqueryAliasRel would be more general.

FWIW, both Spark and DataFusion have some version of SubqueryAlias: Spark, DataFusion

[EpsilonPrime]

For Substrait, the answer might be to automatically name/number the tables in order to provide that distinction. Ignoring how the tables are numbered for a bit, just being able to say column X from table Y should be enough to solve the naming problem without actually naming.

A number of ways to number are possible including just referring to the location in the plan (plan id in Spark), registering the read relations in some discovery order, or using a URN for the local file/virtual table so that table references could be coalesced despite being read multiple times.

Technically I would not call this a subquery alias we aren't aliasing the subtree but instead the fields at a point in the subtree.

[Blizzara]

Technically I would not call this a subquery alias we aren't aliasing the subtree but instead the fields at a point in the subtree.

The proposal here was to alias the subtree specifically, ie. do the same as what Spark's and DataFusion's SubqueryAlias does.

For Substrait, the answer might be to automatically name/number the tables in order to provide that distinction. Ignoring how the tables are numbered for a bit, just being able to say column X from table Y should be enough to solve the naming problem without actually naming.

Yes, Substrait itself does not require this addition - the Substrait plan is valid w/o it, as columns are referred by indices. However it is not possible (or at least I couldn't figure out how, yet) to do lossless roundtrips from DataFusion -> Substrait -> DataFusion for some cases without this. Like for example: SELECT * FROM (VALUES (1, 'a')) AS t1(c1,c2) JOIN (VALUES (1, 'b')) AS t2(c3,c4) ON t1.c1 == t2.c3 or SELECT p1.a p1_a, p2.a p2_a FROM data p1, data p2

I don't know how much value that argument holds, but I've found the roundtrip tests super useful when developing Substrait functionality for DataFusion and Spark - makes it much easier to confirm correctness.

A number of ways to number are possible including just referring to the location in the plan (plan id in Spark), registering the read relations in some discovery order, or using a URN for the local file/virtual table so that table references could be coalesced despite being read multiple times.

Yeah, there are ways. But it will make the roundtrip testing more difficult (since now the Substrait consumer has different logic for naming things than the original producer of the query plan), and may make debugging more difficult for users if the tables are not identifiable by human-written ids but only locations or generated ids. Again, not sure how much weight that argument holds - depends on what the priorities are, I guess :)

[Blizzara]

Actually, when I say "roundtrip", it's a bit more than that - w/o this, I think it's also impossible to maintain output schema for the roundtrip, as the columns after X -> Substrait -> X conversions would have different qualifiers than at the beginning. That is also not crucial for correctness, but helps with "quality of life", I think.

[EpsilonPrime]

Actually, when I say "roundtrip", it's a bit more than that - w/o this, I think it's also impossible to maintain output schema for the roundtrip, as the columns after X -> Substrait -> X conversions would have different qualifiers than at the beginning. That is also not crucial for correctness, but helps with "quality of life", I think.

Side note: If you were to do roundtrip testing starting with Substrait (Substrait -> X -> Substrait) you'd get nearly the same guarantees but without needing to ensure that the names were preserved.

[Blizzara]

Side note: If you were to do roundtrip testing starting with Substrait (Substrait -> X -> Substrait) you'd get nearly the same guarantees but without needing to ensure that the names were preserved.

True. But that feels less natural and requires one to use something else to generate the original substrait (or write it manually). There are cases where it makes sense, to ensure interoperability, but I'm not sure if it's feasible to be the main way for testing.

Also, it doesn't help with the human understandability/debuggability of the plans created from Substrait, which I think would/will be important.

[westonpace]

Side note: If you were to do roundtrip testing starting with Substrait (Substrait -> X -> Substrait) you'd get nearly the same guarantees but without needing to ensure that the names were preserved.

I do think the X -> Substrait -> X path is an important one. I think there are going to be many cases where people are using Substrait internally and they feel comfortable relying the fact that the consumer / producer are part of the "same solution" and can thus, for example, rely on the same extensions. I think this would mean that information that survives X -> Substrait -> X is valid even if it wouldn't survive X -> Substrait -> Y -> Substrait -> X (because Y wouldn't know how to interpret the field).

[westonpace]

Mutually exclusive - both independently provides the needed functionality, just in different ways. I added the other one for discussion to decide which one makes more sense (if either) :)

If we go with the other approach (metadata on RelCommon) do we still need some kind of "no-op" node that can be used to alias a relation tree? Or would you envision that we just map DF Subquery -> SubqueryAlias to a single node (subquery) that has alias metadata?

Also, are you wanting to add a node for the "subquery physical operator"? (e.g. LogicalPlan::Subquery). That would be a different PR, I'm just curious.

[Blizzara]

If we go with the other approach (metadata on RelCommon) do we still need some kind of "no-op" node that can be used to alias a relation tree? Or would you envision that we just map DF Subquery -> SubqueryAlias to a single node (subquery) that has alias metadata?

In that case I don't think there'd be need to add "no-op" node. Producers could map their "SubqueryAlias" by adding metadata to the preceding Rel node, and consumers could read the metadata (if they want to) and add a "SubqueryAlias" to wrap the Rel.

I kinda like that approach since it makes it clear the metadata/alias is optional, and consumers/producers don't need to care about it at all unless they want to. Contrast to this SubqueryAliasRel where consumers would need to start handling the node (even if just to pass through the input rel).

Also, are you wanting to add a node for the "subquery physical operator"? (e.g. LogicalPlan::Subquery). That would be a different PR, I'm just curious.

I haven't seen the need for that, yet at least, so not planning on it currently.

[vbarua]

I kinda like that approach since it makes it clear the metadata/alias is optional, and consumers/producers don't need to care about it at all unless they want to. Contrast to this SubqueryAliasRel where consumers would need to start handling the node (even if just to pass through the input rel).

I was going to say something similar, but you said it better than I could myself. This is the reason I'm in favour of the solution you're proposing in https://github.com/substrait-io/substrait/pull/649.

[Blizzara]

Closing in favor of https://github.com/substrait-io/substrait/pull/649 - that approach seems like the better path forward overall, so let's focus discussion there!