Distributed REFRESH INDEX for incremental scalar index maintenance

[ivscheianu]

CREATE INDEX rebuilds every fragment, so keeping a scalar index current on an append heavy table
costs the whole table each time. The only incremental path today is Dataset.optimizeIndices, which
runs on one node; SQL OPTIMIZE compacts fragments and does not train indexes. This adds the
distributed counterpart.

ALTER TABLE lance.db.users REFRESH INDEX user_id_idx [WITH (num_segments = 8)];

The five sets everything is built from

A Lance index is a set of physical segments. Each declares a fragment_bitmap, absent only on
segments predating coverage tracking, and a bitmap can name fragments that no longer exist, so
coverage only means anything against the live set.

   ┌────────────────────────────────────────────────────────────────────────────────────────────┐
   │  live           fragments present in the manifest                                          │
   │                                                                                            │
   │  covered        union of existing segment bitmaps,  intersected with live                  │
   │                                                                                            │
   │  unindexed      live  minus  covered                        <---   the work                │
   │                                                                                            │
   │  declared       union of the bitmaps we built               <---   the claim               │
   │                                                                                            │
   │  established    union of committed[ours],  intersected       <---   the truth              │
   │                 with live after the commit                                                 │
   └────────────────────────────────────────────────────────────────────────────────────────────┘

For a segment that declares a bitmap, intersecting with live reproduces core's
effective_fragment_bitmap exactly, so the two sides do not disagree about what an index covers. A
segment with no bitmap is the exception: it reads as covering nothing here, while core calls its
coverage unknown and accepts only a full replacement of it.

Flow

   ┌────────────────────────────────────────────────────────────────────────────────────────────┐
   │  DRIVER                                                                                    │
   ├────────────────────────────────────────────────────────────────────────────────────────────┤
   │                                                                                            │
   │  1   PLAN                                                                                  │
   │                                                                                            │
   │          open @ latest  ----------------------------------->  V_plan                       │
   │                                                                                            │
   │          resolve the index by name, case insensitively                                     │
   │          unindexed  =  live  minus  covered                                                │
   │                                                                                            │
   │             nothing to do  ------>  report 0, 0    no version committed                    │
   │                                                                                            │
   │                                                                                            │
   │  2   BATCH                                                                                 │
   │                                                                                            │
   │          unindexed  ------>  exactly N contiguous runs of fragment ids,                    │
   │                             chosen so the heaviest run's rows are minimal                  │
   │                                                                                            │
   └────────────────────────────────────────────────────────────────────────────────────────────┘
                                          │
                                          │   read options pinned @ V_plan
                                          v
   ┌────────────────────────────────────────────────────────────────────────────────────────────┐
   │  EXECUTORS                                                                                 │
   ├────────────────────────────────────────────────────────────────────────────────────────────┤
   │                                                                                            │
   │  3   BUILD         one task per run                                                        │
   │                                                                                            │
   │          open @ V_plan                                                                     │
   │          createIndex( fragmentIds = run,  name = index,  replace )                         │
   │                                                                                            │
   │             ------>  uncommitted segment       invisible to readers                        │
   │                                                                                            │
   └────────────────────────────────────────────────────────────────────────────────────────────┘
                                          │
                                          │   collect
                                          v
   ┌────────────────────────────────────────────────────────────────────────────────────────────┐
   │  DRIVER                                                                                    │
   ├────────────────────────────────────────────────────────────────────────────────────────────┤
   │                                                                                            │
   │  4   VERIFY                                                                                │
   │                                                                                            │
   │          open @ latest  ----------------------------------->  V_commit                     │
   │                                                                                            │
   │          index still exists ?           no  ----->  fail, nothing done                     │
   │          fts details match retained ?   no  ----->  fail, nothing done                     │
   │          declared meets live ?          no  ----->  fail, nothing done                     │
   │                                                                                            │
   │                                                                                            │
   │  5   COMMIT                                                                                │
   │                                                                                            │
   │          commitExistingIndexSegments( index, column, built )                               │
   │          one CreateIndex transaction,  handle advances --->  V_new                         │
   │                                                                                            │
   │             established  =  committed[ours]  intersect  live(V_new)                        │
   │             report  fragments_indexed  =  size of established                              │
   │                                                                                            │
   └────────────────────────────────────────────────────────────────────────────────────────────┘

Pinned build, unpinned commit. Tasks open the dataset themselves, so without a pin each resolves
the latest version independently. Which fragments a segment covers is fixed by the driver's batch
either way; what diverges is what sits behind them. Each sibling would read its fragments at a
different version and stamp its segment with that version, and a fragment compacted away since planning
fails its task outright. Step 4 opens at latest on purpose, because the commit has to fit the table as
it is now, which is also why the index is re-resolved there rather than carried over from step 1.

Range mode btree stays unpinned throughout. Its coverage comes from the fragment ids in the
scanned rows, and the scan pins its own version through the catalog, so pinning the executor open to
V_plan would stamp a segment with a version older than the rows inside it.

Batching

unindexed is split into exactly num_segments contiguous runs of fragment ids, chosen so the
heaviest run's row count is minimal.

Runs are contiguous because compaction groups two fragments only when the identical set of index
segments covers both.

                             fragment:        0           1           2           3


   interleaved               segment A      █████                   █████

                             segment B                  █████                   █████

                             covered by       {A}         {B}         {A}         {B}
                                               └───────────┴───────────┴───────────┘
                                                 no two neighbours match,
                                                 so OPTIMIZE groups nothing


   contiguous                segment A      █████       █████

                             segment B                              █████       █████

                             covered by       {A}         {A}         {B}         {B}
                                               └─────┬─────┘           └─────┬─────┘
                                                 {0,1} groups           {2,3} groups

Measured on four single fragment appends, with coverage committed directly so the layout is the only
variable, then OPTIMIZE ... target_rows_per_fragment = 1000:

coverage over the four fragments	they become
no index at all	1
one segment {0,1,2,3}	1
two contiguous, {0,1} {2,3}	2, one per segment
two interleaved, {0,2} {1,3}	4, unchanged
four segments of one fragment each	4, unchanged

Interleaving is what freezes compaction, not the number of segments: contiguous coverage still
coalesces within each run. The last row is the limit accumulated refreshes approach, one segment per
refresh, which is why the docs ask for OPTIMIZE before REFRESH INDEX rather than after.

Runs are balanced exactly, by binary searching the smallest row budget a contiguous packing can
respect. Greedy packing at a fixed budget uses the fewest runs, so the smallest feasible budget is the
optimal maximum, floored by the widest single fragment. If packing lands on fewer runs than asked for,
the rest split at their balance points, which only lowers the maximum.

What the commit does with an existing segment

                                declared  intersect  segment.bitmap
                                                │
                        ┌───────────────────────┴───────────────────────┐
                        │                                               │
                      empty                                         overlaps
                        │                                               │
            ┌───────────┴───────────┐                   ┌───────────────┴───────────────┐
            │                       │                   │                               │
     bitmap meets no            otherwise         fully covered                  partly covered
     live fragment                  │              by declared                     by declared
            │                       │                   │                               │
            v                       v                   v                               v

        REMOVED                   KEPT              REMOVED                        REJECTED
    it covered nothing        its coverage         superseded                    would orphan
                                survives                                          fragments

A refresh only builds unindexed, so on a quiet table its segments are disjoint from every existing
segment's live coverage. One that still covers a live fragment is therefore KEPT; one that covers none,
including the empty segment a deferred train = false index leaves behind, is REMOVED, and that is what
lets a refresh populate a deferred index.

The tree covers segments that declare a bitmap. Core has two further rejections, for a segment with no
bitmap and for a change of index type, both refusing a partial replacement. Either command can reach a
rejection when the table moves underneath it, and core stays the authority.

Guards

step 4 check	catches
index re-resolved	a DROP INDEX during the build, otherwise silently undone
uniform details	an fts refresh configured differently from the segments it joins
declared meets live	a build whose every fragment was retired while it ran

Reporting after step 5 is a correction rather than a guard. A count taken before the commit is a
prediction: it reads the manifest its handle opened at, and Lance prunes coverage both for a fragment
that is gone and for one whose indexed field was rewritten under the same id, which no comparison of
ids can see. So the count is read back from what the commit returned.

Observability

SHOW INDEXES gains three columns, all from metadata it already fetches.

column	meaning	signal
indexed_percent	rows covered, truncated so it never overstates, null when empty	refresh is due
num_segments	physical segments behind the logical index	rebuild is due
size_bytes	total across their files, null if any predates size tracking	cost

Queries search every segment, so a growing num_segments is a read cost in its own right as well as a
brake on compaction.

Scope

In

• incremental distributed build of the fragments the index does not yet cover
• populating a deferred index, which train = false leaves covering nothing
• coverage made visible in SHOW INDEXES

Out

• distributed segment merge, since every refresh adds segments and consolidating them still needs
  CREATE INDEX
• vector indexes, which Spark SQL cannot create either, so a refresh points at the SDK rather than at
  a rebuild
• inheriting build parameters, since no binding reads a built index's parameters back, so options come
  from the WITH clause and fall back to type defaults

On that last one, for most methods a mismatch costs performance only, because each segment is queried
on its own. fts is the exception, it is read with one configuration for all of its segments, so the
refresh compares what it built against the segments it would join and refuses a mismatch. Exposing
derive_index_params() through the Java binding would remove the caveat.

Known gaps

Concurrent DROP INDEX. Re-resolving the index and committing are separate transactions, and Lance
does not treat a concurrent same name drop as a conflict, so a drop landing between them is undone. No
connector side fix exists: the commit takes no expected predecessor, CommitBuilder has no conflict
policy, and a compensating drop carries the same race. Needs
lance#6806. Pinned by a disabled regression.

Partially covered zonemap drops rows. A predicate on the indexed column can return fewer rows
than the table holds, while an unfiltered COUNT(*) stays correct. This one is ours, not core's: zone
statistics come from the committed segments only, and the driver's fragment pruner builds its surviving
set purely from the fragments those zones name, with no gate on coverage, so a fragment no segment
covers contributes no zones and is pruned away. It reproduces from CREATE INDEX plus an append, so it
predates this proposal, but indexed_percent is what makes it visible, and a coverage gate on the
pruner would close it. btree, bitmap and bloomfilter stay complete while partially covered.

Edit: fixed by #781.

Plan

Six PRs against main, tracked in #789. The first three are pre-existing bugs and land independently
of this proposal.

#	PR	what it does
1	#791	normalize WITH clause option names at the parser boundary
2	#792	keep index segment coverage contiguous
3	#793	name the index on uncommitted segment builds
4	#794	coverage columns in SHOW INDEXES
5	#795	version consistent builds, coverage read from the commit
6	#784	ALTER TABLE ... REFRESH INDEX

#784 keeps the whole change set until 1 to 5 land, since it does not compile without them, then rebases
to the REFRESH INDEX slice.