Implement sequence natively for integral types instead of JVM codegen dispatch #5349

Summary

sequence is the highest-upside remaining codegen-dispatched expression. The dispatcher kernel makes
3 heap allocations per non-null row and passes over every generated element three times, and two
of those allocations scale with the sequence length rather than with the row count. For a 365-element
date spine that is roughly 48 MB of transient long[] garbage per 8192-row batch.

Assessed with the suggest-native-expression skill: compatibility confidence Medium (clean
plan-time guard, see scope), native upside High, and the upside is measured from the emitted
kernel, not inferred from Spark's source.

Recommendation is scoped: implement the integral element type natively, keep the date and timestamp
variants on the dispatcher.

How it runs today

object CometSequence extends CometCodegenDispatch[Sequence]
(spark/src/main/scala/org/apache/comet/serde/arrays.scala:867). A plain CometCodegenDispatch means
the dispatcher is the only path and getSupportLevel is Compatible().

ArrayType(IntegralType) is inside CometBatchKernelCodegen.isSupportedDataType, and I confirmed the
kernel really does compile (CometBatchKernelCodegen.compile with two nullable BigIntVector inputs
returns without throwing), so there is no hidden whole-operator Spark fallback here. The only
fallback trigger is spark.comet.exec.scalaUDF.codegen.enabled=false.

Native upside: High (measured)

Dumped the real kernel via CometBatchKernelCodegen.generateSource for
Sequence(BoundReference(0, LongType), BoundReference(1, LongType), None, Some("UTC")) over two
nullable BigIntVector inputs. The relevant emitted Java, verbatim:

arr_0 = new long[i_1];
while (i_1 > 0) {
  i_1--;
  arr_0[i_1] = (long) (value_1 + (value_1 <= value_2 ? 1L : -1L) * i_1);
}
value_0 = UnsafeArrayData.fromPrimitiveArray(arr_0);

and on the output side:

org.apache.spark.sql.catalyst.util.ArrayData arr_1 = value_5;
int n_0 = arr_1.numElements();
int cidx_0 = output.startNewValue(i);
for (int j_0 = 0; j_0 < n_0; j_0++) {
  outListChild_0.setSafe(cidx_0 + j_0, arr_1.getLong(j_0));
}
output.endValue(i, n_0);

Per non-null row, where n is the sequence length:

Plus three passes over every element: the fill loop, the Platform.copyMemory inside
fromPrimitiveArray, and the output-side getLong / setSafe loop.

Concretely, for a 365-element date spine at the default batch size: 2 arrays × 365 × 8 bytes × 8192
rows = ~48 MB of transient long[] per batch, all on the JVM heap and therefore invisible to
Comet's native memory pool, plus ~3M element writes where one pass would do.

A native kernel writes values straight into the Arrow ListArray child buffer and pushes offsets:
one pass, zero per-row heap allocation, no intermediate ArrayData representation at all.

Honest limits:

• Workload presence is unmeasured. grep over benchmarks/tpc/queries/ finds no sequence
  usage. explode(sequence(start, stop, interval 1 day)) for date spines is a common ETL shape, but
  that is a judgment call rather than evidence.
• The 48 MB figure is arithmetic on the measured allocation sites, not a heap profile.

Compatibility assessment: Medium (with a clean plan-time guard)

Spark versions

Behavior is stable across 3.4.3, 3.5.8, 4.0.1, and 4.1.1. Diffing the Sequence class body
across the four tags shows only:

• 3.4.3 → 3.5.8: internal refactors (startType.sameType → DataTypeUtils.sameType,
  iType.integral → PhysicalIntegralType.integral).
• 3.5.8 → 4.0.1: adds override lazy val throwable: Boolean = stepOpt.isDefined (an optimizer hint)
  and code.toString in doGenCode.
• 4.0.1 → 4.1.1: byte-identical.

No shims needed. TimeType is not accepted by sequence on 4.1.

Hazard checklist

The timezone hazard is what makes this Medium rather than High. It is fully contained in the
temporal element types, and Sequence.impl selects on dataType.elementType, so the split is
knowable at plan time from start.dataType with no runtime probing.

Upstream is not usable

• datafusion-spark 54.1.0 has no sequence.
• datafusion-functions-nested has range / generate_series, but the semantics differ (for
  example "Cannot generate date range less than 1 day." at range.rs:379 and a different
  zero-step message at range.rs:460), and they are shaped for scalar arguments rather than a
  per-row columnar sequence.

So this needs a Comet kernel.

Proposed approach

See the implement-comet-expression skill.

1. Add a native spark_sequence under native/spark-expr/, handling Int8/Int16/Int32/Int64
   start, stop, and step. Compute each row's length with Spark's overflow rules, reserve the child
   buffer once for the whole batch, write values directly, push offsets. No per-row allocation.
2. Reproduce the two error conditions with matching classes and messages
   (_LEGACY_ERROR_TEMP_3243 and the array-size-limit error).
3. Change CometSequence from CometCodegenDispatch[Sequence] to a CometExpressionSerde[Sequence]
   with CodegenDispatchFallback, returning Unsupported(Some(...)) from getSupportLevel when
   start.dataType is not an IntegralType so date and timestamp sequences keep running on the
   dispatcher exactly as they do today.
4. Add native/spark-expr/benches/sequence.rs covering the shapes from
   optimizing_expressions.md: short sequences (2 to 5 elements), long sequences (365, 10k),
   ascending / descending / zero-step, sparse and dense nulls, and the error path.
5. Add Comet SQL Tests at spark/src/test/resources/sql-tests/expressions/array_funcs/sequence.sql.

Non-goals

• Native DateType / TimestampType / TimestampNTZType sequences. These stay on the dispatcher
  until someone takes on the timezone, DST, and legacy-calendar work as a separate issue.
• Any change to explode, which is where sequence output usually goes.

Acceptance criteria

• Output bit-identical to the codegen-dispatch path for all integral element types, including null
  placement, containsNull = false on the result array, step == 0 && start == stop, and both error
  conditions with matching error class and message.
• Date and timestamp sequences demonstrably still route through the dispatcher (assert on the
  [COMET-INFO: JVM codegen dispatcher: ...] EXPLAIN segment).
• Criterion benchmark committed, no regression on any shape.
• The sequence entry in docs/source/contributor-guide/expression-audits/array_funcs.md updated
  when the work lands.

Filed by the suggest-native-expression skill. Motivation:
Native Coverage for Codegen-Dispatched Expressions.
The assessment is recorded in
docs/source/contributor-guide/expression-audits/array_funcs.md under ## sequence.
Previous run of the same skill produced #5347.