Skip to content

Commit 1d42473

Browse files
committed
[core] Decide bitmap exactness from shards that survive pruning
1 parent 103d7fa commit 1d42473

2 files changed

Lines changed: 49 additions & 36 deletions

File tree

‎crates/paimon/src/table/de_vector_scan/tests.rs‎

Lines changed: 37 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1008,10 +1008,13 @@ async fn transported_vector_sources_keep_pk_positions_separate_from_global_ids()
10081008
assert!(mixed.is_err());
10091009
}
10101010

1011-
#[tokio::test]
1012-
async fn pruned_null_bitmap_keeps_btree_answer_exact() {
1013-
// The bitmap shard covers only NULL rows, so `f > 1.5` prunes it and the
1014-
// BTree answer stays exact even without refinement.
1011+
/// Writes ids 0..2 with `first_f`, builds a bitmap on `f`, then writes
1012+
/// f = [2, 3], builds a BTree on `f` and IVF-flat on `embedding`, and returns
1013+
/// the Top-1 ids for `filter` without refinement from data.
1014+
async fn top1_after_bitmap_then_btree(
1015+
first_f: Vec<Option<f64>>,
1016+
filter: fn(&crate::spec::PredicateBuilder) -> crate::spec::Predicate,
1017+
) -> Vec<i32> {
10151018
use crate::spec::{ArrayType, DataType, Datum, DoubleType, FloatType, IntType};
10161019
use arrow_array::types::Float32Type;
10171020
use arrow_array::{Float64Array, ListArray};
@@ -1066,12 +1069,7 @@ async fn pruned_null_bitmap_keeps_btree_answer_exact() {
10661069
.unwrap();
10671070
}
10681071
};
1069-
write(
1070-
vec![0, 1],
1071-
vec![None, None],
1072-
vec![vec![0.0, 1.0], vec![0.0, 1.0]],
1073-
)
1074-
.await;
1072+
write(vec![0, 1], first_f, vec![vec![0.0, 1.0], vec![0.0, 1.0]]).await;
10751073
let mut builder = table.new_global_index_build_builder();
10761074
builder.with_index_type("bitmap").with_index_column("f");
10771075
builder.execute().await.unwrap();
@@ -1105,7 +1103,7 @@ async fn pruned_null_bitmap_keeps_btree_answer_exact() {
11051103
.with_vector_column("embedding")
11061104
.with_query_vector(vec![1.0, 0.0])
11071105
.with_limit(1)
1108-
.with_filter(pb.greater_than("f", Datum::Double(1.5)).unwrap())
1106+
.with_filter(filter(&pb))
11091107
.execute()
11101108
.await
11111109
.unwrap()
@@ -1116,7 +1114,7 @@ async fn pruned_null_bitmap_keeps_btree_answer_exact() {
11161114
.try_collect()
11171115
.await
11181116
.unwrap();
1119-
let ids: Vec<i32> = batches
1117+
batches
11201118
.iter()
11211119
.flat_map(|batch| {
11221120
batch
@@ -1128,7 +1126,33 @@ async fn pruned_null_bitmap_keeps_btree_answer_exact() {
11281126
.values()
11291127
.to_vec()
11301128
})
1131-
.collect();
1129+
.collect()
1130+
}
1131+
1132+
#[tokio::test]
1133+
async fn pruned_null_bitmap_keeps_btree_answer_exact() {
1134+
// The bitmap shard covers only NULL rows, so `f > 1.5` prunes it and the
1135+
// BTree answer stays exact even without refinement.
1136+
let ids = top1_after_bitmap_then_btree(vec![None, None], |pb| {
1137+
pb.greater_than("f", crate::spec::Datum::Double(1.5))
1138+
.unwrap()
1139+
})
1140+
.await;
1141+
assert_eq!(ids, vec![2]);
1142+
}
1143+
1144+
#[tokio::test]
1145+
async fn bitmap_pruned_by_another_conjunct_keeps_btree_answer_exact() {
1146+
// The bitmap shard holds f = [0, 1]. `f = 2` prunes it by metadata, so
1147+
// only the BTree answers `f > 1.5 AND f = 2`, and it does so exactly.
1148+
let ids = top1_after_bitmap_then_btree(vec![Some(0.0), Some(1.0)], |pb| {
1149+
crate::spec::Predicate::and(vec![
1150+
pb.greater_than("f", crate::spec::Datum::Double(1.5))
1151+
.unwrap(),
1152+
pb.equal("f", crate::spec::Datum::Double(2.0)).unwrap(),
1153+
])
1154+
})
1155+
.await;
11321156
assert_eq!(ids, vec![2]);
11331157
}
11341158

‎crates/paimon/src/table/global_index_scanner/evaluator.rs‎

Lines changed: 12 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -387,28 +387,6 @@ impl GlobalIndexScanner {
387387
&self,
388388
entries: &[&GlobalIndexEntry],
389389
predicates: &[(PredicateOperator, &[Datum], &DataType)],
390-
) -> Result<Option<(Vec<RowRange>, Vec<RowRange>, bool)>> {
391-
// A bitmap answers floating ranges and negations with every non-null
392-
// row (see `bitmap_meta_may_match`), so those results are candidates
393-
// only. Sorted indexes answer them exactly.
394-
// An all-NULL bitmap shard is pruned before it answers anything.
395-
let bitmap_superset = entries.iter().any(|entry| {
396-
matches!(entry.index_type, GlobalIndexFileKind::Bitmap)
397-
&& !sorted_entry_meta(entry).only_nulls()
398-
}) && predicates.iter().any(|(op, _, data_type)| {
399-
is_floating_point(data_type) && is_bitmap_floating_residual_sensitive_op(*op)
400-
});
401-
Ok(self.evaluate_leaf_entries(entries, predicates).await?.map(
402-
|(row_ranges, coverage, fully_evaluated)| {
403-
(row_ranges, coverage, fully_evaluated && !bitmap_superset)
404-
},
405-
))
406-
}
407-
408-
async fn evaluate_leaf_entries(
409-
&self,
410-
entries: &[&GlobalIndexEntry],
411-
predicates: &[(PredicateOperator, &[Datum], &DataType)],
412390
) -> Result<Option<(Vec<RowRange>, Vec<RowRange>, bool)>> {
413391
let Some(normalized_predicates) = predicates
414392
.iter()
@@ -614,6 +592,14 @@ impl GlobalIndexScanner {
614592
)
615593
});
616594

595+
// A bitmap answers floating ranges and negations with every non-null
596+
// row (see `bitmap_meta_may_match`), so its results are candidates
597+
// only. Sorted indexes answer them exactly. Only bitmap shards that
598+
// survive pruning by every conjunct below contribute rows.
599+
let bitmap_superset_ops = predicates.iter().any(|(op, _, data_type)| {
600+
is_floating_point(data_type) && is_bitmap_floating_residual_sensitive_op(*op)
601+
});
602+
let mut bitmap_retained = false;
617603
let mut query_plans = Vec::with_capacity(entries.len());
618604
let mut all_matching_ranges = Vec::new();
619605
let mut fully_evaluated = true;
@@ -623,6 +609,7 @@ impl GlobalIndexScanner {
623609
.iter()
624610
.all(|matches| matches[entry_idx])
625611
{
612+
bitmap_retained |= matches!(entry.index_type, GlobalIndexFileKind::Bitmap);
626613
all_matching_ranges.push(RowRange::new(entry.row_range_start, entry.row_range_end));
627614
continue;
628615
}
@@ -693,9 +680,11 @@ impl GlobalIndexScanner {
693680
// Only a proven identity remains (other conjuncts may have
694681
// declined their budget). Preserve its indexed domain and
695682
// leave the residual filter to the ordinary table reader.
683+
bitmap_retained |= matches!(entry.index_type, GlobalIndexFileKind::Bitmap);
696684
all_matching_ranges.push(RowRange::new(entry.row_range_start, entry.row_range_end));
697685
continue;
698686
}
687+
bitmap_retained |= matches!(entry.index_type, GlobalIndexFileKind::Bitmap);
699688
query_plans.push(EntryQueryPlan {
700689
entry_idx,
701690
between_matches,
@@ -771,7 +760,7 @@ impl GlobalIndexScanner {
771760
Ok(Some((
772761
crate::table::merge_row_ranges(all_ranges),
773762
coverage(),
774-
fully_evaluated,
763+
fully_evaluated && !(bitmap_retained && bitmap_superset_ops),
775764
)))
776765
}
777766

0 commit comments

Comments
 (0)