Gabriel39 commented on code in PR #69625:
URL: https://github.com/apache/doris/pull/69625#discussion_r4378086221
##########
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:
Updated in f1d1441169ca046338e4cf8edeca406a493043f3. This PR now pins merged
upstream lance-c commit a51ab47a9c814a746cb1714c99fad93dd3a188b8 from
lance-format/lance-c#98. The local runtime-selection patch and its
application/checksum handling have been removed, so the decoded-memory guards
are supplied directly by upstream. The existing Foyer patch is unchanged. All
515 native Rust tests passed on the downloaded source plus that patch,
including the compressed-string regression and decoded-budget cases; C/C++
header syntax checks also passed.
--
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]
