Indexed APPROX NEAREST join over Lance for Spark 4.2 (SQL-only, no-shuffle)

[sezruby]

Summary

Transparently accelerate Spark 4.2's APPROX NEAREST join (NearestByJoin, SPARK-56395) when the right side is a Lance dataset that carries a vector index. A Catalyst rule intercepts the resolved NearestByJoin and, when the right side is an indexed Lance table, substitutes a native per-partition index probe in place of Spark's default brute-force rewrite (cross product + min_by).

SELECT *
FROM   queries q
LEFT OUTER JOIN documents d
  APPROX NEAREST 10 BY DISTANCE vector_l2_distance(q.vec, d.vec)

When the right side is not an indexed Lance table — no vector index, a variable-length vector column, a blob payload column, etc. — the rule declines and Spark's built-in RewriteNearestByJoin handles the query unchanged. The optimization is opt-in: registering one session extension is the entire surface, and end-user SQL does not change.

Scope

This narrows the earlier tracking issue (#541) to a single, minimal, independently reviewable deliverable:

• One module — lance-spark-knn-4.2_2.13 (Scala 2.13, Spark 4.2.0, Java 17). Opt-in via a session extension; no change to existing modules.
• SQL only — the entry point is Spark 4.2's APPROX NEAREST SQL / NearestByJoin.
• No shuffle — each left-side partition probes the Lance index directly and folds the nearest search and payload projection into a single scan. There is no staged Probe → Shuffle → Merge → Materialize pipeline.

Explicitly deferred

• df.kNearestJoin DataFrame API — the SQL path covers the SPARK-56395 entry point; a DataFrame extension can follow if there is demand.
• Multi-version support (Spark 3.5 / 4.0 / 4.1) — 4.2 is where NearestByJoin is first-class.
• The 3-exec staged shuffle pipeline described in Indexed nearest-neighbor join optimization for lance-spark (tracking issue, 7-PR split) #541 — replaced by the no-shuffle per-partition probe above.

Implementation

• Umbrella PR (full end-to-end change, kept open for reference): feat: indexed nearest-by join over Lance (Spark 4.2 SQL) #796
• Reviewable slices, split by architectural layer:
  • [1/3] probe-core primitives — feat(knn): probe core + no-shuffle join stage for indexed Lance vector join (Spark 4.2) #797
  • [2/3] no-shuffle per-partition join execution — to follow
  • [3/3] Catalyst interception rule, physical operator, session extension, SQL/recall tests, and docs — to follow

Supersedes #541.