Skip to content

Commit ae3660e

Browse files
committed
[core] Keep exact BTree answers for floating filters
Only a bitmap answers floating ranges and negations with every non-null row, so mark a leaf inexact only when a bitmap entry answered it.
1 parent 1053c4f commit ae3660e

3 files changed

Lines changed: 129 additions & 103 deletions

File tree

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

Lines changed: 103 additions & 91 deletions
Original file line numberDiff line numberDiff line change
@@ -648,104 +648,116 @@ async fn scalar_coverage_gaps_follow_scalar_and_vector_modes() {
648648
async fn floating_bitmap_candidates_are_refined_before_top_k() {
649649
// A bitmap index answers `!=` and range filters on FLOAT/DOUBLE with all
650650
// non-null rows. Row 0 is closest to [1, 0] but fails every filter, so
651-
// ranking those candidates unrefined would return it.
651+
// ranking those candidates unrefined would return it. A BTree answers the
652+
// same filters exactly, so its candidates need no refinement.
652653
use crate::spec::{ArrayType, DataType, Datum, DoubleType, FloatType, IntType};
653654
use arrow_array::types::Float32Type;
654655
use arrow_array::{Float64Array, ListArray};
655656

656-
let schema = crate::spec::Schema::builder()
657-
.column("id", DataType::Int(IntType::new()))
658-
.column("f", DataType::Double(DoubleType::new()))
659-
.column(
660-
"embedding",
661-
DataType::Array(ArrayType::new(DataType::Float(FloatType::new()))),
662-
)
663-
.options(HashMap::from([
664-
("bucket".into(), "-1".into()),
665-
("row-tracking.enabled".into(), "true".into()),
666-
("data-evolution.enabled".into(), "true".into()),
667-
("global-index.enabled".into(), "true".into()),
668-
]))
669-
.build()
670-
.unwrap();
671-
let table = Table::new(
672-
crate::io::FileIOBuilder::new("memory").build().unwrap(),
673-
crate::catalog::Identifier::new("default", "float_bitmap"),
674-
format!("memory:/float-bitmap-{}", uuid::Uuid::new_v4()),
675-
crate::spec::TableSchema::new(0, &schema),
676-
None,
677-
);
678-
let columns: Vec<ArrayRef> = vec![
679-
Arc::new(Int32Array::from(vec![0, 1])),
680-
Arc::new(Float64Array::from(vec![1.0, 2.0])),
681-
Arc::new(ListArray::from_iter_primitive::<Float32Type, _, _>(vec![
682-
Some(vec![Some(1.0), Some(0.0)]),
683-
Some(vec![Some(0.0), Some(1.0)]),
684-
])),
685-
];
686-
let arrow_schema = Arc::new(ArrowSchema::new(vec![
687-
ArrowField::new("id", ArrowDataType::Int32, true),
688-
ArrowField::new("f", ArrowDataType::Float64, true),
689-
ArrowField::new("embedding", columns[2].data_type().clone(), true),
690-
]));
691-
let mut writer = TableWrite::new(&table, "test".to_string()).unwrap();
692-
writer
693-
.write_arrow_batch(&RecordBatch::try_new(arrow_schema, columns).unwrap())
694-
.await
695-
.unwrap();
696-
TableCommit::new(table.clone(), "test".to_string())
697-
.commit(writer.prepare_commit().await.unwrap())
698-
.await
699-
.unwrap();
700-
let mut builder = table.new_global_index_build_builder();
701-
builder.with_index_type("bitmap").with_index_column("f");
702-
builder.execute().await.unwrap();
703-
let mut builder = table.new_global_index_build_builder();
704-
builder
705-
.with_index_type("ivf-flat")
706-
.with_index_column("embedding")
707-
.with_options(HashMap::from([
708-
("ivf-flat.dimension".into(), "2".into()),
709-
("ivf-flat.nlist".into(), "1".into()),
710-
("ivf-flat.distance.metric".into(), "l2".into()),
657+
for (index_type, refine_from_data) in
658+
[("bitmap", None), ("btree", None), ("btree", Some("false"))]
659+
{
660+
let schema = crate::spec::Schema::builder()
661+
.column("id", DataType::Int(IntType::new()))
662+
.column("f", DataType::Double(DoubleType::new()))
663+
.column(
664+
"embedding",
665+
DataType::Array(ArrayType::new(DataType::Float(FloatType::new()))),
666+
)
667+
.options(HashMap::from([
668+
("bucket".into(), "-1".into()),
669+
("row-tracking.enabled".into(), "true".into()),
670+
("data-evolution.enabled".into(), "true".into()),
671+
("global-index.enabled".into(), "true".into()),
672+
]))
673+
.build()
674+
.unwrap();
675+
let table = Table::new(
676+
crate::io::FileIOBuilder::new("memory").build().unwrap(),
677+
crate::catalog::Identifier::new("default", "float_bitmap"),
678+
format!("memory:/float-bitmap-{}", uuid::Uuid::new_v4()),
679+
crate::spec::TableSchema::new(0, &schema),
680+
None,
681+
);
682+
let columns: Vec<ArrayRef> = vec![
683+
Arc::new(Int32Array::from(vec![0, 1])),
684+
Arc::new(Float64Array::from(vec![1.0, 2.0])),
685+
Arc::new(ListArray::from_iter_primitive::<Float32Type, _, _>(vec![
686+
Some(vec![Some(1.0), Some(0.0)]),
687+
Some(vec![Some(0.0), Some(1.0)]),
688+
])),
689+
];
690+
let arrow_schema = Arc::new(ArrowSchema::new(vec![
691+
ArrowField::new("id", ArrowDataType::Int32, true),
692+
ArrowField::new("f", ArrowDataType::Float64, true),
693+
ArrowField::new("embedding", columns[2].data_type().clone(), true),
711694
]));
712-
builder.execute().await.unwrap();
713-
714-
let pb = crate::spec::PredicateBuilder::new(table.schema().fields());
715-
for filter in [
716-
Predicate::negate(pb.equal("f", Datum::Double(1.0)).unwrap()),
717-
pb.not_equal("f", Datum::Double(1.0)).unwrap(),
718-
pb.greater_than("f", Datum::Double(1.5)).unwrap(),
719-
] {
720-
let batches: Vec<RecordBatch> = table
721-
.new_vector_search_builder()
722-
.with_vector_column("embedding")
723-
.with_query_vector(vec![1.0, 0.0])
724-
.with_limit(1)
725-
.with_filter(filter.clone())
726-
.execute()
695+
let mut writer = TableWrite::new(&table, "test".to_string()).unwrap();
696+
writer
697+
.write_arrow_batch(&RecordBatch::try_new(arrow_schema, columns).unwrap())
727698
.await
728-
.unwrap()
729-
.new_read_builder()
730-
.read()
731-
.await
732-
.unwrap()
733-
.try_collect()
699+
.unwrap();
700+
TableCommit::new(table.clone(), "test".to_string())
701+
.commit(writer.prepare_commit().await.unwrap())
734702
.await
735703
.unwrap();
736-
let ids: Vec<i32> = batches
737-
.iter()
738-
.flat_map(|batch| {
739-
batch
740-
.column_by_name("id")
741-
.unwrap()
742-
.as_any()
743-
.downcast_ref::<Int32Array>()
744-
.unwrap()
745-
.values()
746-
.to_vec()
747-
})
748-
.collect();
749-
assert_eq!(ids, vec![1], "{filter}");
704+
let mut builder = table.new_global_index_build_builder();
705+
builder.with_index_type(index_type).with_index_column("f");
706+
builder.execute().await.unwrap();
707+
let mut builder = table.new_global_index_build_builder();
708+
builder
709+
.with_index_type("ivf-flat")
710+
.with_index_column("embedding")
711+
.with_options(HashMap::from([
712+
("ivf-flat.dimension".into(), "2".into()),
713+
("ivf-flat.nlist".into(), "1".into()),
714+
("ivf-flat.distance.metric".into(), "l2".into()),
715+
]));
716+
builder.execute().await.unwrap();
717+
718+
let table = match refine_from_data {
719+
Some(refine) => table.copy_with_options(HashMap::from([(
720+
"global-index.filter.refine-from-data".to_string(),
721+
refine.to_string(),
722+
)])),
723+
None => table,
724+
};
725+
let pb = crate::spec::PredicateBuilder::new(table.schema().fields());
726+
for filter in [
727+
Predicate::negate(pb.equal("f", Datum::Double(1.0)).unwrap()),
728+
pb.not_equal("f", Datum::Double(1.0)).unwrap(),
729+
pb.greater_than("f", Datum::Double(1.5)).unwrap(),
730+
] {
731+
let batches: Vec<RecordBatch> = table
732+
.new_vector_search_builder()
733+
.with_vector_column("embedding")
734+
.with_query_vector(vec![1.0, 0.0])
735+
.with_limit(1)
736+
.with_filter(filter.clone())
737+
.execute()
738+
.await
739+
.unwrap()
740+
.new_read_builder()
741+
.read()
742+
.await
743+
.unwrap()
744+
.try_collect()
745+
.await
746+
.unwrap();
747+
let ids: Vec<i32> = batches
748+
.iter()
749+
.flat_map(|batch| {
750+
batch
751+
.column_by_name("id")
752+
.unwrap()
753+
.as_any()
754+
.downcast_ref::<Int32Array>()
755+
.unwrap()
756+
.values()
757+
.to_vec()
758+
})
759+
.collect();
760+
assert_eq!(ids, vec![1], "{index_type} {refine_from_data:?} {filter}");
761+
}
750762
}
751763
}

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

Lines changed: 2 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -385,19 +385,11 @@ impl GlobalIndexScanner {
385385
predicate: &Predicate,
386386
evaluated_fields: &std::collections::HashSet<i32>,
387387
) -> bool {
388-
use crate::spec::{DataType, PredicateOperator};
388+
use crate::spec::PredicateOperator;
389389
match predicate {
390390
Predicate::NestedLeaf { .. } => false,
391-
Predicate::Leaf {
392-
column,
393-
op,
394-
data_type,
395-
..
396-
} => {
391+
Predicate::Leaf { column, op, .. } => {
397392
predicates::is_sorted_global_index_supported_op(*op)
398-
// Bitmap answers these with every non-null row.
399-
&& !(matches!(data_type, DataType::Float(_) | DataType::Double(_))
400-
&& super::bitmap_global_index_format::is_bitmap_floating_residual_sensitive_op(*op))
401393
&& !matches!(
402394
op,
403395
PredicateOperator::Contains

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

Lines changed: 24 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,8 +19,8 @@
1919
2020
use super::all_match::all_matching_entries;
2121
use super::entry::{
22-
bitmap_meta_may_match, bitmap_meta_may_match_between, multivalue_meta_may_match,
23-
sorted_entry_meta, GlobalIndexEntry, GlobalIndexFileKind,
22+
bitmap_meta_may_match, bitmap_meta_may_match_between, is_floating_point,
23+
multivalue_meta_may_match, sorted_entry_meta, GlobalIndexEntry, GlobalIndexFileKind,
2424
};
2525
use super::predicates::{
2626
entries_support_predicate, is_multivalue_predicate, is_sorted_global_index_supported_op,
@@ -39,6 +39,7 @@ use crate::btree::{make_key_comparator, serialize_datum};
3939
#[cfg(test)]
4040
use crate::spec::GlobalIndexSearchMode;
4141
use crate::spec::{DataType, Datum, Predicate, PredicateOperator};
42+
use crate::table::bitmap_global_index_format::is_bitmap_floating_residual_sensitive_op;
4243
use crate::table::bitmap_global_index_format::{
4344
make_bitmap_key_comparator, serialize_bitmap_datum,
4445
};
@@ -386,6 +387,27 @@ impl GlobalIndexScanner {
386387
&self,
387388
entries: &[&GlobalIndexEntry],
388389
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+
let bitmap_superset = entries
395+
.iter()
396+
.any(|entry| matches!(entry.index_type, GlobalIndexFileKind::Bitmap))
397+
&& predicates.iter().any(|(op, _, data_type)| {
398+
is_floating_point(data_type) && is_bitmap_floating_residual_sensitive_op(*op)
399+
});
400+
Ok(self.evaluate_leaf_entries(entries, predicates).await?.map(
401+
|(row_ranges, coverage, fully_evaluated)| {
402+
(row_ranges, coverage, fully_evaluated && !bitmap_superset)
403+
},
404+
))
405+
}
406+
407+
async fn evaluate_leaf_entries(
408+
&self,
409+
entries: &[&GlobalIndexEntry],
410+
predicates: &[(PredicateOperator, &[Datum], &DataType)],
389411
) -> Result<Option<(Vec<RowRange>, Vec<RowRange>, bool)>> {
390412
let Some(normalized_predicates) = predicates
391413
.iter()

0 commit comments

Comments
 (0)