Epic: Support Higher Order Functions #9249

This Epic is for adding support for higher order functions (HoFs) for complex datatypes, starting with List.

There are two main designs that we have considered:

1. HoFs that preserve row cardinality are implemented as ScalarFns, with lambdas stored in Options. The input list and arrays captured in the lambda body are scalarfn children. The expression layer remains responsible for representing lambdas, binding lambda variables and captures, and lowering the result into a scalar-function call. This is somewhat similar to DuckDB's implementation.
2. HoFs have a separate HoFVTable contract, HoFArray, and ecosystem parallel to scalarfn universe. This is somewhat similar to Datafusion's implementation.

We are partial to the simplicity of the first option, and only will pivot to the second if there is a compelling performance rationale. One potential issue is that the lambda expression is opaque to the array optimizer and can only be applied during the HoF's execution.

Status

Active

Proposed.

Goal

Support the complete lifecycle of a higher-order expression:

1. Represent lambda expressions and lambda variables.
2. Bind lambda variables using lexical scopes and identify captured expressions.
3. Lower a bound higher-order expression into an ordinary scalar function with lambda metadata.
4. Execute that scalar function over complex Vortex arrays.
5. Translate higher-order functions from query-engine expressions so they can be pushed down into
   Vortex.

The first supported operation will be:

  list_transform(list, lambda)

It should support:

• a single element parameter: lambda.x -> x (x represents a row of list.elements)
• captures from the outer row domain: lambda.x -> col("outer_scope_field")
• scalar-function calls within the lambda: lambda.x -> x + 1, lambda.x -> x + col("outer_scope_field")
• nested lists and nested higher-order calls

Motivation

Query engines expose higher-order functions for operating on complex values without first exploding them into rows. Supporting these operations directly allows Vortex to preserve complex array structure, evaluate operations lazily, and push more computation into Vortex execution.

In particular, the Statpopgen benchmark uses array_transform. Supporting its Vortex equivalent, list_transform, is the first concrete use case and provides an end-to-end target for expression translation and pushdown.

Steps

There are two largely independent implementation tracks.

Expression representation and binding

The expression layer will:

• represent lambda expressions and lambda variables
• distinguish lambda parameters from captured outer expressions
• type-check lambda parameters and bodies
• lower a bound lambda into scalar function options and captured array children

Conceptually:

list_transform(col("a"), lambda x. x + col("b"))

becomes:

  ScalarFnArray {
      scalar_fn: ListTransform {
          options: Lambda(add(parameter[0], capture[0]))
      },
      children: [
          col("a"),
          col("b"),
      ],
  }

Array execution

At the array layer, list_transform is an ordinary scalar function.

Its execution implementation will:

• flatten the logical element invocation domain
• expand captures and outer validity into that domain
• avoid evaluating elements hidden beneath null outer rows
• evaluate the lambda body using lazy scalar-function arrays
• reconstruct the result using the original list representation where possible.

No HigherOrderFn vtable or HigherOrderFnArray is required in this design.