infer_rel_schema keeps outer and single join fields required on the null-padded side #267

Plans that DuckDB 1.5.5 (substrait extension 4ea63dd) and Isthmus (substrait-java 0.103.0) write for an ordinary LEFT JOIN hit this. For SELECT a.c0, b.c1 FROM a LEFT JOIN b ON a.c0 = b.c1 with b.c1 declared required, infer_rel_schema keeps c1 required on both plans, while DuckDB and DataFusion, executing either plan, return a row where it is NULL.

infer_rel_schema preserves the input field nullabilities for LEFT, RIGHT, OUTER, LEFT_SINGLE and RIGHT_SINGLE joins. A required field on the null-padded side stays required, even though that join can return NULL for it.

Reproduced with substrait 0.31.0. main at 2f138c1 carries the same type_inference.py: the one commit between them touches a CI workflow.

The Join Operation rules in spec v0.99.0 describe the null padding for unmatched rows. It needs to be reflected in the output field types.

Reproducer

from substrait import algebra_pb2 as a, type_pb2 as t
from substrait.type_inference import infer_rel_schema

R, N = t.Type.NULLABILITY_REQUIRED, t.Type.NULLABILITY_NULLABLE

def read(name):
    return a.Rel(read=a.ReadRel(
        named_table=a.ReadRel.NamedTable(names=[name]),
        base_schema=t.NamedStruct(
            names=[name],
            struct=t.Type.Struct(
                types=[t.Type(i64=t.Type.I64(nullability=R))],
                nullability=R,
            ),
        ),
    ))

for kind in ("INNER", "LEFT", "RIGHT", "OUTER", "LEFT_SINGLE", "RIGHT_SINGLE"):
    rel = a.Rel(join=a.JoinRel(
        left=read("l"), right=read("r"),
        type=a.JoinRel.JoinType.Value("JOIN_TYPE_" + kind),
        expression=a.Expression(literal=a.Expression.Literal(boolean=True)),
    ))
    schema = infer_rel_schema(rel)
    print(kind, ["N" if f.i64.nullability == N else "R" for f in schema.types])

Every row prints ['R', 'R']. The expected patterns are:

I also checked all four combinations of input nullability for these six join types: 11 of 24 schemas differ. INNER and already-nullable sides behave as expected, and inference does not mutate the inputs.

_join_struct_from_schemas currently concatenates the two input type lists for these JoinRel types without making the null-padded side nullable. The mark-join output columns are separate: #263 reports them and #265 changes them.