Gabriel39 commented on code in PR #69625:
URL: https://github.com/apache/doris/pull/69625#discussion_r4376921059
##########
thirdparty/patches/lance-c-runtime-index-selection.patch:
##########
@@ -0,0 +1,723 @@
+diff --git a/include/lance/lance.h b/include/lance/lance.h
+index b592396..052a0fc 100644
+--- a/include/lance/lance.h
++++ b/include/lance/lance.h
+@@ -2439,6 +2439,11 @@ int32_t lance_scanner_set_index_segments(
+ int32_t lance_scanner_set_scalar_index_segment(
+ LanceScanner* scanner, const uint8_t* segment_uuid);
+
++/* Opt in to bounded runtime BTree page-cost selection for a scalar segment
scan.
++ * Defaults to false. The explicit fragment domain and complete filter are
preserved.
++ * Unsupported/unknown estimates retain the selected segment. Returns 0 or
-1. */
++int32_t lance_scanner_set_scalar_index_auto_selection(LanceScanner* scanner,
bool enabled);
++
+ /* ─── Full-text search (Phase 2) ─── */
+
+ /**
+diff --git a/src/lib.rs b/src/lib.rs
+index 4a96bb5..267e63b 100644
+--- a/src/lib.rs
++++ b/src/lib.rs
+@@ -43,6 +43,7 @@ mod merge_insert;
+ mod multivector;
+ mod restore;
+ pub mod runtime;
++mod scalar_index_selection;
+ mod scalar_segment;
+ mod scanner;
+ mod session;
+diff --git a/src/scalar_index_selection.rs b/src/scalar_index_selection.rs
+new file mode 100644
+index 0000000..87270ff
+--- /dev/null
++++ b/src/scalar_index_selection.rs
+@@ -0,0 +1,408 @@
++// SPDX-License-Identifier: Apache-2.0
++// SPDX-FileCopyrightText: Copyright The Lance Authors
++
++//! Bounded runtime BTree cost comparison. Estimates affect only acceleration;
++//! the caller always retains its explicit fragment domain and complete
filter.
++
++use std::{borrow::Cow, cmp::Ordering, ops::Bound};
++
++use arrow_array::{Array, RecordBatch, UInt32Array};
++use datafusion::common::ScalarValue;
++use lance::{
++ Dataset,
++ dataset::{index::LanceIndexStoreExt, scanner::ExecutionSummaryCounts},
++};
++use lance_core::{
++ Error,
++ cache::CacheKey,
++ deepsize::{Context, DeepSizeOf},
++};
++use lance_index::scalar::{
++ IndexStore, SargableQuery,
++ btree::{BTREE_LOOKUP_NAME, DEFAULT_BTREE_BATCH_SIZE},
++ expression::ScalarIndexExpr,
++ lance_format::LanceIndexStore,
++};
++use lance_table::format::IndexMetadata;
++use uuid::Uuid;
++
++use crate::scalar_segment::scoped_expression;
++
++const MAX_CANDIDATES: usize = 8;
++const MAX_LOOKUP_BYTES: u64 = 8 * 1024 * 1024;
++const MAX_LOOKUP_PAGES: usize = 65_536;
++const MAX_IN_VALUES: usize = 256;
++const MAX_ESTIMATE_COMPARISONS: usize = 1_000_000;
++
++struct Lookup {
++ batch: RecordBatch,
++ rows_per_page: u64,
++}
++
++impl DeepSizeOf for Lookup {
++ fn deep_size_of_children(&self, _context: &mut Context) -> usize {
++ self.batch.get_array_memory_size()
++ }
++}
++
++struct LookupKey(String);
++impl CacheKey for LookupKey {
++ type ValueType = Lookup;
++ fn key(&self) -> Cow<'_, str> {
++ self.0.as_str().into()
++ }
++ fn type_name() -> &'static str {
++ "DorisBTreeCostLookup"
++ }
++}
++
++fn is_btree_expression(expr: &ScalarIndexExpr) -> bool {
++ match expr {
++ ScalarIndexExpr::Query(search) =>
search.index_type.eq_ignore_ascii_case("btree"),
++ ScalarIndexExpr::And(a, b) | ScalarIndexExpr::Or(a, b) => {
++ is_btree_expression(a) && is_btree_expression(b)
++ }
++ ScalarIndexExpr::Not(_) => false,
++ }
++}
++
++fn overlaps(
++ min: &ScalarValue,
++ max: &ScalarValue,
++ query: &SargableQuery,
++ nulls: u32,
++) -> Option<bool> {
++ let contains = |value: &ScalarValue| -> Option<bool> {
++ if value.is_null() {
++ return Some(nulls != 0);
++ }
++ if min.is_null() || max.is_null() {
++ return Some(false);
++ }
++ Some(
++ min.partial_cmp(value)? != Ordering::Greater
++ && max.partial_cmp(value)? != Ordering::Less,
++ )
++ };
++ match query {
++ SargableQuery::Equals(value) => contains(value),
++ SargableQuery::IsNull() => Some(nulls != 0),
++ SargableQuery::IsIn(values) if values.len() <= MAX_IN_VALUES => {
++ for value in values {
++ if contains(value)? {
++ return Some(true);
++ }
++ }
++ Some(false)
++ }
++ SargableQuery::Range(start, end) => {
++ if min.is_null() || max.is_null() {
++ return Some(false);
++ }
++ let above_lower = match start {
++ Bound::Included(v) if !v.is_null() => max.partial_cmp(v)? !=
Ordering::Less,
++ Bound::Excluded(v) if !v.is_null() => max.partial_cmp(v)? ==
Ordering::Greater,
++ Bound::Unbounded => true,
++ _ => return None,
++ };
++ let below_upper = match end {
++ Bound::Included(v) if !v.is_null() => min.partial_cmp(v)? !=
Ordering::Greater,
++ Bound::Excluded(v) if !v.is_null() => min.partial_cmp(v)? ==
Ordering::Less,
++ Bound::Unbounded => true,
++ _ => return None,
++ };
++ Some(above_lower && below_upper)
++ }
++ _ => None,
++ }
++}
++
++fn matches_page(
++ expr: &ScalarIndexExpr,
++ min: &ScalarValue,
++ max: &ScalarValue,
++ nulls: u32,
++) -> Option<bool> {
++ match expr {
++ ScalarIndexExpr::Query(search) => overlaps(
++ min,
++ max,
++ search.query.as_any().downcast_ref::<SargableQuery>()?,
++ nulls,
++ ),
++ ScalarIndexExpr::And(a, b) => {
++ Some(matches_page(a, min, max, nulls)? && matches_page(b, min,
max, nulls)?)
++ }
++ ScalarIndexExpr::Or(a, b) => {
++ Some(matches_page(a, min, max, nulls)? || matches_page(b, min,
max, nulls)?)
++ }
++ // A page's min/max cannot determine which rows survive a complement.
++ ScalarIndexExpr::Not(_) => None,
++ }
++}
++
++fn comparisons_per_page(expr: &ScalarIndexExpr) -> Option<usize> {
++ match expr {
++ ScalarIndexExpr::Query(search) => {
++ match search.query.as_any().downcast_ref::<SargableQuery>()? {
++ SargableQuery::IsIn(values) if values.len() <= MAX_IN_VALUES
=> {
++ Some(values.len().max(1))
++ }
++ SargableQuery::Equals(_) | SargableQuery::Range(_, _) |
SargableQuery::IsNull() => {
++ Some(1)
++ }
++ _ => None,
++ }
++ }
++ ScalarIndexExpr::And(a, b) | ScalarIndexExpr::Or(a, b) => {
++ comparisons_per_page(a)?.checked_add(comparisons_per_page(b)?)
++ }
++ ScalarIndexExpr::Not(_) => None,
++ }
++}
++
++fn estimate_pages(batch: &RecordBatch, expr: &ScalarIndexExpr) ->
Option<usize> {
++ if batch.num_columns() < 3 || batch.num_rows() > MAX_LOOKUP_PAGES {
++ return None;
++ }
++ // Node and byte limits alone still allow pages * IN-values * leaves work.
++ if batch.num_rows().checked_mul(comparisons_per_page(expr)?)? >
MAX_ESTIMATE_COMPARISONS {
++ return None;
++ }
++ let nulls = batch.column(2).as_any().downcast_ref::<UInt32Array>()?;
++ let mut pages = 0;
++ for row in 0..batch.num_rows() {
++ let min = ScalarValue::try_from_array(batch.column(0), row).ok()?;
++ let max = ScalarValue::try_from_array(batch.column(1), row).ok()?;
++ pages += usize::from(matches_page(expr, &min, &max,
nulls.value(row))?);
++ }
++ Some(pages)
++}
++
++async fn estimate_cost(
++ dataset: &Dataset,
++ index: &IndexMetadata,
++ expr: &ScalarIndexExpr,
++ remaining_bytes: &mut u64,
++) -> Option<(u64, usize)> {
++ if !is_btree_expression(expr) {
++ return None;
++ }
++ // Inspect immutable manifest sizes before opening a file.
Older/partition-only
++ // layouts without this root are deliberately left to the existing search
path.
++ let size = index
++ .files
++ .as_ref()?
++ .iter()
++ .find(|f| f.path == BTREE_LOOKUP_NAME)?
++ .size_bytes;
++ if size > *remaining_bytes {
++ return None;
++ }
++ *remaining_bytes -= size;
++ let key = LookupKey(format!("{}/{}", dataset.uri(), index.uuid));
++ let session = dataset.session();
++ let lookup = session
++ .file_metadata_cache()
++ .get_or_insert_with_key(key, || async {
++ let store = LanceIndexStore::from_dataset_for_existing(dataset,
index).await?;
++ let reader = store.open_index_file(BTREE_LOOKUP_NAME).await?;
++ if reader.num_rows() > MAX_LOOKUP_PAGES {
++ return Err(Error::not_supported(
++ "BTree cost lookup exceeds the page budget",
++ ));
++ }
++ let rows_per_page = reader
++ .schema()
++ .metadata
++ .get("batch_size")
++ .map(|s| s.parse::<u64>())
++ .transpose()
++ .map_err(|_| Error::not_supported("invalid BTree page size"))?
++ .unwrap_or(DEFAULT_BTREE_BATCH_SIZE);
++ if rows_per_page == 0 {
++ return Err(Error::not_supported("zero BTree page size"));
++ }
++ let batch = reader.read_range(0..reader.num_rows(), None).await?;
Review Comment:
Confirmed and fixed upstream in
https://github.com/lance-format/lance-c/pull/98/commits/c6cbde1452f10792a9e8c12bae9727919cf888d4.
The selector now checks a separate cumulative 8 MiB decoded-buffer allowance
from fixed-width schema and row count before materialization; cached lookups
are charged as well. Since the current IndexReader API cannot bound decoded
variable-width values, string/binary probes return unknown before opening their
lookup, preserving such a default or skipping such an alternative.
The regression uses 1,024 pages of repeated 64 KiB strings: the serialized
lookup fits the original limit, while decoded extrema would occupy 128 MiB. It
failed on the old implementation and now passes, including retaining a
selective integer driver without caching the string probe. All 501 Rust tests,
Rustfmt and Clippy passed locally.
This draft's vendored patch is still awaiting replacement: after the
upstream PR merges, I will pin the latest upstream main commit containing the
fix and remove the new local runtime-selection patch. Keeping this thread open
until that downstream update lands.
--
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]
