github-actions[bot] commented on code in PR #69625:
URL: https://github.com/apache/doris/pull/69625#discussion_r4375895764
##########
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:
[P2] Bound decoded lookup memory before materializing probes
For a valid V2.0 Lance table with full-coverage BTree indexes `a_id_idx` on
integer `id` and `z_s_idx` on low-cardinality STRING `s`, `WHERE id = 123 AND s
>= 'a'` groups on `a_id_idx` but also fully decodes the unused `z_s_idx` lookup
here. With 1,024 index pages containing the same 64-KiB string, the decoded
min/max buffers alone occupy 128 MiB. The normal writer dictionary-encodes
these repeated extrema, so the lookup still passes the 8-MiB serialized-file
budget and 65,536-page cap; the pinned dictionary decoder expands them into
ordinary StringArray values.
The Session cache weighs entries only after this loader finishes, so even a
small or disabled metadata cache cannot bound the transient allocation. Larger
roots and concurrent readers can exhaust BE memory during advisory selection,
whereas disabling the new default-on option leaves the string index unopened
and reads it only as a residual column after the selective integer mask.
Enforce a decoded-byte budget before materialization, or use a bounded
streaming probe that returns an unknown estimate when exceeded, and cover a
compressed long-string alternative in regression tests.
--
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]
