FANNG1 opened a new pull request, #69596:
URL: https://github.com/apache/doris/pull/69596
### What problem does this PR solve?
Issue Number: close #69573
Related PR: None
Problem Summary:
When a Lance vector index covers only part of a dataset, FE plans a mixed
set of splits: one per
physical index segment, which BE searches with `use_index=true`, plus one
flat split per uncovered
fragment, which BE searches with `use_index=false`. A Doris TopN above the
scan merges the union of
their candidates by `_distance`.
Those two kinds of split did not report `_distance` on the same scale. A
flat split computes exact
distances. An index split on a quantized index (`IVF_PQ`, `IVF_SQ`,
`IVF_RQ`, `IVF_HNSW_PQ`,
`IVF_HNSW_SQ`) computes them from the quantized codes unless refinement is
enabled, and Doris never
enabled it on its own: `refine_factor` reached lance-c only when the user
passed it, and the single
forced `set_refine_factor(1)` covered multi-vector queries. In the pinned
lance-c, a single-vector
scan without `refine_factor` makes no `scanner.refine()` call at all. So a
plain single-vector
`vector_search` over a partially indexed table sorted approximate distances
against exact ones in
one TopN, and the `_distance` column handed to the user mixed two scales.
Measured on the fixture this PR adds (row_id 1..512 indexed by `vec_idx`,
row_id 513..640 appended
uncovered, `vec = [row_id, row_id + 1, row_id + 2, row_id + 3]` so the
squared L2 distance between
rows r and n is exactly `4 * (n - r)^2`), with query `[512.25, 513.25,
514.25, 515.25]`:
| row_id | fragment | before | after | exact |
|---|---|---|---|---|
| 512 | 0, indexed | 1.2808 | 0.25 | 0.25 |
| 513 | 1, flat | 2.25 | 2.25 | 2.25 |
| 511 | 0, indexed | 4.3113 | 6.25 | 6.25 |
| 514 | 1, flat | 12.25 | 12.25 | 12.25 |
| 510 | 0, indexed | 25.25 | 20.25 | 20.25 |
| 515 | 1, flat | 30.25 | 30.25 | 30.25 |
The indexed rows were reported 1.03 too high, 1.94 too low and 5.0 too high
while the rows from the
uncovered fragment in the same result were exact. Whether the merged order
also changes depends on
whether that error exceeds the gap to the neighbouring exactly scored row;
the error is a property
of the trained codebook rather than of the data shape, so what is
deterministic is that the
distances are wrong, not that a particular pair swaps.
This is not a Lance defect. Lance defines the approximation and offers
`refine_factor` as the
remedy, and it treats putting every arm of a merge on one scale as the
caller's job - see
lance-format/lance#9849, which fixed the same class of bug inside Lance's
own LSM vector planner.
Lance cannot fix it here, because Doris creates the arms: each index split's
fragment range equals
its segment's coverage, so each split's internal uncovered-fragment fallback
is empty and Lance
never sees a mixed scan. lance-format/lance-spark#860 hit the same thing
when it moved
`VECTOR_SEARCH` onto Spark tasks, and resolved it the same way.
The fix: when a vector plan contains both index-segment splits and
uncovered-fragment splits, and
the selected index does not store full vectors, FE marks that plan's
index-segment splits with a new
`TLanceFileDesc.refine_vector_distances` (field id 7, free and consistent on
branch-4.2, branch-4.1,
branch-4.0, branch-3.1 and HEAD). BE applies it in
`_configure_vector_search` as
`set_refine_factor(1)`, before the user options block, so a larger explicit
`refine_factor` still
wins, and before the split's own result limit. `IVF_FLAT` and
`IVF_HNSW_FLAT` are exempt because
they keep the stored vectors; every other type, including the generic
`VECTOR` an older manifest
reports without details, is rescored. A split carrying the flag without an
index segment is rejected
rather than silently honored. `EXPLAIN` reports the decision as
`lanceSearchRefineDistances`.
Refinement rescores the candidates the index already chose and does not
widen that choice, so this
makes the distances and their merge correct without turning ANN candidate
selection into an
exhaustive search.
### Release note
Fixed Lance `vector_search` returning distances on two different scales, and
an order that could be
distorted, when a quantized vector index (`IVF_PQ`, `IVF_SQ`, `IVF_RQ`,
`IVF_HNSW_PQ`,
`IVF_HNSW_SQ`) covered only part of the dataset. Such a query now rescores
the indexed candidates
against the stored vectors, at the cost of one additional read of those
vectors. `EXPLAIN` shows
this as `lanceSearchRefineDistances`.
### Check List (For Author)
- Test: Unit Test
- FE: `LanceScanNodeTest` extended with the index-type x coverage matrix
and the
`use_index=false` case; run and passing (40 tests, 0 failures).
- BE: `lance_reader_test.cpp` extended with a forced-refinement case
over the existing
`distance_range_sq.lance` fixture and a guard case. Their expected
distances were read off
that fixture directly with pylance 7: the query quantizes onto the
bucket row 0 holds, so an
unrefined candidate reports the squared distance to that bucket
instead of to the query.
Written but not yet run - the BE unit test build for this change is
still in progress, which
is why this opens as a draft.
- Regression: a new `external_table_p0/lance` suite and the fixture it
needs are prepared but
held back from this commit, because its `.out` must be generated by a
test run against the
docker Lance environment rather than written by hand.
- Behavior changed: Yes. A single-vector search on a partially covered
quantized index now returns
exact distances and the correctly ordered merge; it previously returned
quantized distances for
the indexed rows. The cost is one read of the stored vectors for the
candidates of each index
split. Fully covered plans, `IVF_FLAT` / `IVF_HNSW_FLAT` plans,
`use_index=false` and multi-vector
queries are unchanged.
- Does this need documentation: Yes. `docs/lance-multivector-search.md` is
updated in this commit;
the Lance catalog page on the website should get the same note about
`refine_factor` and partially
covered quantized indexes (no doc PR yet).
### Why this targets branch-4.1
The Lance connector exists only on `branch-4.1` and `branch-4.2`; master
carries the Thrift
placeholders but no connector, so there is no master commit to backport
from. `fe/.../datasource/lance/**`
and `be/src/format_v2/table/lance_reader.cpp` are byte-identical between the
two branches and
`TLanceFileDesc` has the same field ids on both, so the same change
cherry-picks to `branch-4.2`
without conflict. I will open that PR once this one is agreed.
### Draft status
Opened as a draft because the BE unit tests added here are written but have
not been run yet - the
BE unit test build is still compiling locally. I will mark this ready for
review once
`LanceTableReaderVectorSearchTest.*` passes and I have posted the end-to-end
evidence promised on
the issue (`EXPLAIN` plus the three `(row_id, _distance)` result sets from
the docker Lance
environment).
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
