update_columns on a heavily deleted fragment fails with "Failed to add blanks: Offset overflow error"

Description

Hit this in production while updating a column on a fragment with a high deletion
rate. LanceFragment.update_columns fails outright:

File "/usr/local/lib/python3.10/dist-packages/lance/fragment.py", line 731, in update_columns
    metadata, fields_modified = self._fragment.update_columns(
RuntimeError: LanceError(Arrow): Failed to add blanks: Offset overflow error: 2148272826

2148272826 is just past i32::MAX (2147483647), i.e. the offset buffer of a
variable-width column overflowed while the updater was restoring deleted rows.

Chasing this down led straight to a TODO that has been sitting in add_blanks
since 2023 — the current placeholder strategy is explicitly marked as the
simple-but-wasteful one, and it is exactly what makes this overflow reachable. This
issue proposes doing that TODO.

The TODO

Location: add_blanks in rust/lance/src/dataset/updater.rs.

selection_vector.extend(batch_pos..batch_pos + num_rows);
// For simplicity, we just use the first value for deleted rows
// TODO: optimize this to use small value for each column.
selection_vector.push(0);

History:

• Introduced in #995 ("feat: handle deletes in count_rows, updater, merge",
  2023-06-23), originally in rust/src/dataset/updater.rs, where the blank was
  picked inside the selection_vector closure.
• Moved to its current path by #1250 ("[Rust] Refactor lance rust crate into
  sub-modules").
• Carried forward by #2311 ("feat: add v2 support to fragment merge / update
  paths", 2024-05-10), which rewrote the surrounding blank-offset computation to
  stop depending on the file's batch size but kept the copy-row-0 placeholder and
  the TODO as-is.

Root cause

All data files in a fragment must have the same number of physical rows, so when a
fragment is rewritten the updater has to write a placeholder ("blank") for every
deleted row. Per the TODO above, add_blanks builds those blanks by pushing
index 0 into the selection vector, so every deleted slot is a copy of the batch's
first live row, and the whole column is then produced with a single
arrow::compute::take.

For a fixed-width column that is free — every value costs the same. For a
variable-width column (Utf8, Binary, List, LargeBinary, ...) each blank
duplicates row 0's entire payload. On a fragment where most rows are deleted, the
rewritten file therefore carries roughly num_deleted * len(row_0_payload) bytes
that no reader will ever return, and once that exceeds i32::MAX the Binary /
Utf8 offset buffer overflows and the operation fails.

So the TODO is not only a size optimization: without it, any operation that
rewrites a heavily deleted fragment carrying a large variable-width column fails.
LanceFragment.update_columns and add_columns / merge_columns are both
affected, because both drive the same Updater:

• FileFragment::update_columns -> self.updater(..)
• schema_evolution::add_columns_to_fragments -> self.updater(..)

and the updater restores deleted rows through DeletionRestorer::restore ->
add_blanks in either case.

Reproduction

Needs (a) a large variable-width column, (b) a high deletion rate, and (c) no
compaction in between:

import lance
import numpy as np
import pyarrow as pa

n = 200_000
payload = np.random.bytes(16 * 1024)  # ~16 KiB per row
tab = pa.table({
    "id": pa.array(range(n), pa.int64()),
    "blob": pa.array([payload] * n, pa.binary()),
})
ds = lance.write_dataset(tab, "repro.lance", max_rows_per_file=n)

# Keep 0.1% of the rows. Deletions are not materialized until compaction.
ds.delete("id % 1000 != 0")

# Update the blob column on the surviving rows.
rowids = ds.to_table(columns=["id"], with_row_id=True)["_rowid"]
new_blob = pa.table({
    "_rowid": rowids,
    "blob": pa.array([b"x"] * len(rowids), pa.binary()),
})

frag = ds.get_fragments()[0]
# ~199,800 blanks, each a copy of row 0's 16 KiB payload -> i32 offset overflow.
frag.update_columns(new_blob, left_on="_rowid")

add_columns / merge_columns on the same dataset fail the same way. Compaction is
what normally materializes deletions, so this is hit by workloads that delete
heavily and then rewrite columns before compacting.

Expected behavior

A blank carries no information, so it should cost as little as the column's layout
allows, and rewriting a fragment should succeed regardless of the deletion rate.

Proposed fix

Do the TODO: choose a per-column blank instead of always copying row 0.

• Null, when the column is nullable in both the write schema and the Arrow
  field and the target file version can store nulls for that type
  (Dataset::lance_supports_nulls).
• Empty value for the types whose byte cost depends on the value but which
  cannot take a null — empty string / empty binary / empty list / empty map. This
  is done by rebuilding the offset buffer, leaving the child/values array
  untouched.
• Copy row 0 only for the fixed-width layouts, where every value costs the
  same and copying is already optimal (this also keeps dictionary values buffers
  shared rather than duplicated).

Struct and fixed-size-list columns need to recurse so a variable-width child does
not silently keep the old behavior.

Two related problems show up on the same path and would be fixed together:

1. The trailing deleted run is unbounded — for v2 files the updater appended as
   many trailing deleted rows as it could to the last batch, so a fragment with a
   long deleted tail materialized one very large output batch. It should be capped
   by the updater's output batch size.
2. Blank nullability was derived from the Arrow field alone. It must also respect
   the dataset's write schema, otherwise a nullable Arrow source over a
   non-nullable Lance column produces a batch the writer rejects.

Environment

• Lance version: 2.0.0 / main
• OS: Linux
• Python: 3.10

Start in rust/lance/src/dataset/updater.rs at add_blanks, then trace DeletionRestorer::restore and the shared Updater paths used by update_columns and add_columns/merge_columns. Run the provided Python reproduction and inspect the existing nullability, blank-offset, and trailing-deleted-row handling. Done means heavily deleted fragments with variable-width columns rewrite successfully without offset overflow, including the related nullability and batch-size cases.