github-actions[bot] commented on code in PR #68613: URL: https://github.com/apache/doris/pull/68613#discussion_r4129869462
########## thirdparty/test/lance-prefilter-patch-test.sh: ########## @@ -0,0 +1,109 @@ +#!/usr/bin/env bash +# 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. + +set -euo pipefail + +ROOT="$(cd "$(dirname "${BASH_SOURCE[0]}")/.." &>/dev/null && pwd)" +ARCHIVE_DIR="${1:?Usage: $0 directory-containing-the-pinned-lance-and-lance-c-archives}" +ARCHIVE_DIR="$(cd "${ARCHIVE_DIR}" && pwd)" +TP_DIR="${ROOT}" +# Load only the repository-owned archive definitions, never extracted code. +source "${ROOT}/vars.sh" Review Comment: [P3] Keep the patch harness runnable on macOS `set -u` is active when this sources `vars.sh`, but `ARROW_ADBC_FLIGHTSQL_SOURCE` is initialized only on Linux and is expanded unconditionally later in `vars.sh`. On Darwin, the documented test command exits with an unbound-variable error before any Lance case runs. Initialize the variable or source `vars.sh` with nounset disabled. ########## thirdparty/patches/lance-pq4-float-scores.patch: ########## @@ -0,0 +1,232 @@ +Correctness prerequisite for the ANN prefilter optimization. +Adapt the float-scoring invariant from https://github.com/lance-format/lance/pull/9537 +to the pinned dependency using its existing float loop. The newer SIMD screening +implementation is not imported; 4-bit bulk scoring can use more CPU than the old +lossy uint8 path. Preserve pairwise per-row scores before removing allowlists. + +--- a/rust/lance-index/src/vector/pq/distance.rs ++++ b/rust/lance-index/src/vector/pq/distance.rs +@@ -2,20 +2,10 @@ + // SPDX-FileCopyrightText: Copyright The Lance Authors + + use core::panic; +-use std::cmp::{max, min}; + + use super::utils::get_sub_vector_centroids; + use lance_core::assume_eq; + use lance_linalg::distance::{Dot, L2, dot_distance_batch, l2::L2Prepared, l2_distance_batch}; +-use lance_linalg::simd::u8::u8x16; +-use lance_linalg::simd::{SIMD, Shuffle}; +- +-// for quantizing the distance table, we need to know the max possible distance, +-// so we perform a flat search on the first `FLAT_NUM_4BIT_PQ` rows. +-// increasing this number will increase the accuracy of the quantization, +-// but also increase the computation time. +-// 200 is a good trade-off according to the original paper. +-const FLAT_NUM_4BIT_PQ: usize = 200; + + /// Build a Distance Table from the query to each PQ centroid + /// using L2 distance. +@@ -181,96 +171,23 @@ + distance_table: &[f32], + num_sub_vectors: usize, + code: &[u8], +- k_hint: usize, ++ _k_hint: usize, + ) -> Vec<f32> { + let num_vectors = code.len() * 2 / num_sub_vectors; + let mut distances = vec![0.0f32; num_vectors]; +- +- // compute the distances for first k_hint rows +- // then use the max distance as qmax to quantize the distance table +- let k_hint = min(k_hint, num_vectors); +- let flat_num = max(FLAT_NUM_4BIT_PQ, k_hint).min(num_vectors); +- compute_pq_distance_4bit_flat( +- distance_table, +- num_vectors, +- code, +- 0, +- flat_num, +- &mut distances, +- ); +- let qmax = *distances +- .iter() +- .take(flat_num) +- .max_by(|a, b| a.total_cmp(b)) +- .unwrap(); +- +- let (qmin, quantized_dists_table) = quantize_distance_table(distance_table, qmax); +- const NUM_CENTROIDS: usize = 2_usize.pow(4); +- let mut quantized_dists = vec![0_u8; num_vectors]; +- +- let remainder = num_vectors % NUM_CENTROIDS; +- for i in (0..num_vectors - remainder).step_by(NUM_CENTROIDS) { +- let mut block_distances = u8x16::zeros(); +- +- for (sub_vec_idx, vec_indices) in code.chunks_exact(num_vectors).enumerate() { +- let origin_dist_table = unsafe { +- u8x16::load_unaligned( +- quantized_dists_table +- .as_ptr() +- .add(sub_vec_idx * 2 * NUM_CENTROIDS), +- ) +- }; +- let origin_next_dist_table = unsafe { +- u8x16::load_unaligned( +- quantized_dists_table +- .as_ptr() +- .add((sub_vec_idx * 2 + 1) * NUM_CENTROIDS), +- ) +- }; +- +- let indices = unsafe { u8x16::load_unaligned(vec_indices.as_ptr().add(i)) }; +- +- // compute current distances +- let current_indices = indices.bit_and(0x0F); +- block_distances += origin_dist_table.shuffle(current_indices); +- +- // compute next distances +- let next_indices = indices.right_shift::<4>(); +- block_distances += origin_next_dist_table.shuffle(next_indices); +- } +- +- unsafe { +- block_distances.store_unaligned(quantized_dists.as_mut_ptr().add(i)); +- } +- } +- if remainder > 0 { +- let offset = max(num_vectors - remainder, flat_num); ++ // Removing an all-row prefilter must not change PQ candidate ordering. ++ // Use the same float scores as PQDistCalculator::distance instead of mixing ++ // float prefix/tail scores with rounded, saturating uint8 bulk scores. ++ if num_vectors > 0 { Review Comment: [P2] Preserve throughput for large 4-bit PQ partitions This replaces the 16-lane u8 bulk loop with scalar f32 lookup for every row in every 4-bit PQ bulk search, including existing full-snapshot scans. [Upstream Lance #9537](https://github.com/lance-format/lance/pull/9537) measured this float-only kernel at 472.215 us versus 98.553 us for 16,384 rows and 96 subvectors (an isolated kernel result, not Doris latency), then added exact u16 screening to recover throughput. Large IVF-PQ scans can therefore regress even when they do not use the new prefilter shortcut. Please carry an exact fast path for large partitions and benchmark representative Doris ANN scans. -- 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]
