Gabriel39 commented on code in PR #68028:
URL: https://github.com/apache/doris/pull/68028#discussion_r4021778050
##########
be/src/format_v2/table/lance_reader.cpp:
##########
@@ -1235,6 +1265,26 @@ Status LanceTableReader::_fill_block_from_record_batch(
->read_column_from_arrow(*columns[output_idx],
normalized_column.get(), 0, row_count,
_ctz));
+ if (_search_kind == SearchKind::VECTOR && field->name() ==
LANCE_DISTANCE_COLUMN) {
+ const auto& query =
_scan_params->lance_scan_params.external_search_request
+
.search_query.vector_search.query_vector;
+ if (query.__isset.num_vectors) {
+ // Lance's exact score is 1 - sum(1 - distance). Expose
sum(min distance)
+ // so one logical row has the same scoring contract for
every query size.
+ IColumn* output = columns[output_idx].get();
+ if (auto* nullable =
check_and_get_column<ColumnNullable>(*output)) {
+ output = &nullable->get_nested_column();
+ }
+ auto* distances =
check_and_get_column<ColumnFloat32>(*output);
+ if (distances == nullptr) {
+ return Status::InternalError("Lance multi-vector
distance must be FLOAT");
+ }
+ auto& data = distances->get_data();
+ for (size_t i = data.size() - row_count; i < data.size();
++i) {
+ data[i] += static_cast<float>(query.num_vectors - 1);
Review Comment:
Fixed in cd8255cb4c. The Lance-C scoring adapter now accumulates
sum(min(distance)) directly before the plan's TopK operators, using an f64
accumulator with the existing f32 distance kernels/output. Removed the BE
post-truncation normalization. Native, BE and SQL regression cases assert the
winning row and score for top_k=1 with L2 distances around 1e-8 and 2.25e-8.
##########
thirdparty/patches/lance-c-0.1.9-multivector.patch:
##########
@@ -0,0 +1,508 @@
+diff --git a/src/scanner.rs b/src/scanner.rs
+--- a/src/scanner.rs
++++ b/src/scanner.rs
+@@ -226,8 +226,18 @@
+ if let Some(cols) = &self.columns {
+ scanner.project(cols)?;
+ }
++ let multi_vector = self.nearest.as_ref().is_some_and(|query| {
++ matches!(
++ query.query.data_type(),
++ arrow_schema::DataType::FixedSizeList(_, _)
++ )
++ });
+ if self.limit.is_some() || self.offset.is_some() {
+ scanner.limit(self.limit, self.offset)?;
++ if multi_vector {
++ // Retain Lance's window validation, but defer truncation
until the final sort.
++ scanner.limit(None, None)?;
++ }
+ }
+ if let Some(bs) = self.batch_size {
+ scanner.batch_size(bs);
+@@ -300,6 +310,12 @@
+ Ok(PreparedScanner {
+ scanner,
+ distributed_fts,
++ multi_vector_window: multi_vector.then_some((
++ self.offset.unwrap_or(0) as usize,
++ self.limit.map(|n| n as usize),
++ )),
++ batch_size: self.batch_size,
++ scan_statistics_callback: self.scan_statistics_callback.clone(),
+ })
+ }
+ }
+@@ -314,10 +330,45 @@
+ struct PreparedScanner {
+ scanner: lance::dataset::scanner::Scanner,
+ distributed_fts: Option<PreparedFtsExecution>,
++ multi_vector_window: Option<(usize, Option<usize>)>,
++ batch_size: Option<usize>,
++ scan_statistics_callback: Option<ExecutionStatsCallback>,
+ }
+
+ impl PreparedScanner {
+ async fn try_into_stream(self) -> Result<DatasetRecordBatchStream> {
++ if let Some((offset, limit)) = self.multi_vector_window {
++ use datafusion::physical_expr::{PhysicalSortExpr, expressions};
++ use datafusion::physical_plan::{
++ coalesce_partitions::CoalescePartitionsExec,
limit::GlobalLimitExec,
++ sorts::sort::SortExec,
++ };
++ let plan = self.scanner.create_plan().await?;
++ let sort = PhysicalSortExpr {
++ expr: expressions::col("_distance", plan.schema().as_ref())?,
++ options: arrow::compute::SortOptions {
++ descending: false,
++ nulls_first: false,
++ },
++ };
++ // Fragment-scoped Lance plans can reorder candidate batches
during payload take.
++ // Apply the result window only after restoring distance order
across all partitions.
++ // The nearest plan already bounds the candidate rows by k.
++ let sorted = Arc::new(SortExec::new(
++ [sort].into(),
++ Arc::new(CoalescePartitionsExec::new(plan)),
++ ));
++ let plan = Arc::new(GlobalLimitExec::new(sorted, offset, limit));
++ let stream = lance_datafusion::exec::execute_plan(
++ plan,
++ lance_datafusion::exec::LanceExecutionOptions {
++ batch_size: self.batch_size,
Review Comment:
Fixed in cd8255cb4c. Indexed scoring reduces each logical query child over
its complete stream before combining query contributions. The truncating Top1
regression uses batch sizes 1, 2 and 1024 and asserts the same winning row and
distance; it reproduces the wrong winner with the previous library. Covered in
native, BE and SQL tests.
##########
docs/lance-multivector-search.md:
##########
@@ -0,0 +1,105 @@
+<!--
+Licensed to the Apache Software Foundation (ASF) under one
+or more contributor license agreements. See the NOTICE file
+distributed with this work for additional information
+regarding copyright ownership. The ASF licenses this file
+to you under the Apache License, Version 2.0 (the
+"License"); you may not use this file except in compliance
+with the License. You may obtain a copy of the License at
+
+ http://www.apache.org/licenses/LICENSE-2.0
+
+Unless required by applicable law or agreed to in writing,
+software distributed under the License is distributed on an
+"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+KIND, either express or implied. See the License for the
+specific language governing permissions and limitations
+under the License.
+-->
+
+# Lance multi-vector search
+
+A Lance `List<FixedSizeList<T, D>>` column stores a variable number of
D-dimensional
+subvectors in each table row. Doris exposes it as `ARRAY<ARRAY<FLOAT>>` for
Float16
+and Float32, or `ARRAY<ARRAY<DOUBLE>>` for Float64.
+
+`vector_search` accepts a non-empty JSON matrix for such a column. Every inner
+array must contain exactly D finite numeric values representable in the
column's
+element type. A matrix with one inner array is still one multi-vector query.
+This is not a batch of independent searches or a search across several columns.
+Ordinary `FixedSizeList` columns continue to accept a one-dimensional JSON
array.
+
+```sql
+SELECT id, _distance
+FROM vector_search(
+ "table" = "lance_catalog.default.documents",
+ "column" = "embeddings",
+ "query_vector" = "[[1,0],[0,1]]",
+ "top_k" = "10",
+ "metric" = "cosine",
+ "filter" = "id > 100"
+)
+ORDER BY _distance, id;
+```
+
+## Row-level score and filtering
+
+For query subvectors Q and a row's subvectors V, Doris reports:
+
+`_distance = sum(q in Q, min(v in V, distance(q, v)))`
+
+Smaller is better. The base distance is squared Euclidean distance for `l2`,
+`1 - cosine_similarity` for `cosine`, or `1 - dot_product` for `dot`. Each
query
+subvector contributes once; the same stored subvector may match several query
+subvectors. The score is a sum, not an average, so duplicating a query
subvector
+changes the score. `_distance` uses Doris FLOAT, including for Float64 inputs.
+
+`top_k` and `offset` count table rows, not subvectors. The TVF `filter` is
applied
+before candidate search; an outer SQL WHERE filters the search's results.
+Distributed fragments return row candidates for the global TopK. Ties at the
+TopK boundary have no guaranteed row order.
+
+`use_index=false` computes exact scores over the selected rows. With indexes,
+candidate selection is approximate. Doris always refines multi-vector
candidates
+against their original values so indexed and unindexed rows use the same score.
+`refine_factor` can increase the candidate pool beyond this default refinement.
+It does not turn ANN candidate selection into an exhaustive search.
+
+The pinned Lance version supports multi-vector indexes with the cosine metric.
+Use `use_index=false` for L2 or dot searches. `nprobes`, `ef`, and
`refine_factor`
Review Comment:
Fixed in cd8255cb4c. FE materializes L2 when metric is omitted, split
construction preserves that resolved metric, and BE explicitly configures it on
every scanner. The new C API also defaults multi-vector searches to L2. Added
omitted-metric tests over a cosine-indexed fragment plus an appended fragment,
checking comparable L2 distances and final ordering.
##########
be/src/format_v2/table/lance_reader.cpp:
##########
@@ -537,13 +538,27 @@ Status
LanceTableReader::_validate_external_search_request() const {
return Status::NotSupported("unsupported Lance query vector
element type: {}",
static_cast<int>(query_vector.element_type));
}
+ const bool multi_vector = query_vector.__isset.num_vectors;
+ if (multi_vector != (request.schema_version == 2) ||
+ (multi_vector && query_vector.num_vectors <= 0)) {
Review Comment:
Fixed in cd8255cb4c. FE, BE and the C API cap queries at 128 subvectors and
enforce a 100000 budget for num_vectors * candidate_k and refine_factor *
candidate_k, where Doris candidate_k includes the offset. Checks precede ANN
plan construction and use division/checked arithmetic to avoid overflow. Tests
cover accepted boundaries, excessive counts, offset expansion and excessive
refinement.
--
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]
