Skip to content

Commit eff224e

Browse files
committed
[core] Keep NaN rows under negation and refine floating bitmap candidates
Negating a FLOAT/DOUBLE comparison keeps Not, since NaN makes the flipped operator non-complementary. Scalar index exactness treats FLOAT/DOUBLE leaves that the bitmap index answers with every non-null row as inexact, so filtered Top-K refines them before ranking.
1 parent 7b63fe5 commit eff224e

4 files changed

Lines changed: 206 additions & 33 deletions

File tree

‎crates/paimon/src/spec/predicate.rs‎

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -322,7 +322,13 @@ impl PredicateOperator {
322322

323323
/// The operator [`Predicate::negate`] flips `op` to on a field of `data_type`.
324324
fn negated_op(op: PredicateOperator, data_type: &DataType) -> Option<PredicateOperator> {
325-
let _ = data_type;
325+
// `NaN < 1.0` and `NaN >= 1.0` are both false, so a flipped comparison
326+
// would drop NaN. `Not` keeps it, as Java's NaN-last ordering does.
327+
if matches!(data_type, DataType::Float(_) | DataType::Double(_))
328+
&& !matches!(op, PredicateOperator::IsNull | PredicateOperator::IsNotNull)
329+
{
330+
return None;
331+
}
326332
op.negate()
327333
}
328334

@@ -512,7 +518,8 @@ impl Predicate {
512518
/// - `NOT(NOT(p))` → `p` (double negation elimination)
513519
/// - `NOT(AlwaysTrue)` → `AlwaysFalse`
514520
/// - `NOT(AlwaysFalse)` → `AlwaysTrue`
515-
/// - Leaves without a negated operator stay wrapped in `Not`.
521+
/// - Leaves without a negated operator stay wrapped in `Not`, and so do
522+
/// FLOAT/DOUBLE comparisons, which NaN makes non-complementary.
516523
pub fn negate(predicate: Predicate) -> Predicate {
517524
match predicate {
518525
Predicate::Not(inner) => *inner,

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

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -643,3 +643,109 @@ async fn scalar_coverage_gaps_follow_scalar_and_vector_modes() {
643643
}
644644
}
645645
}
646+
647+
#[tokio::test]
648+
async fn floating_bitmap_candidates_are_refined_before_top_k() {
649+
// A bitmap index answers `!=` and range filters on FLOAT/DOUBLE with all
650+
// non-null rows. Row 0 is closest to [1, 0] but fails every filter, so
651+
// ranking those candidates unrefined would return it.
652+
use crate::spec::{ArrayType, DataType, Datum, DoubleType, FloatType, IntType};
653+
use arrow_array::types::Float32Type;
654+
use arrow_array::{Float64Array, ListArray};
655+
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()),
711+
]));
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()
727+
.await
728+
.unwrap()
729+
.new_read_builder()
730+
.read()
731+
.await
732+
.unwrap()
733+
.try_collect()
734+
.await
735+
.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}");
750+
}
751+
}

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

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -385,11 +385,19 @@ impl GlobalIndexScanner {
385385
predicate: &Predicate,
386386
evaluated_fields: &std::collections::HashSet<i32>,
387387
) -> bool {
388-
use crate::spec::PredicateOperator;
388+
use crate::spec::{DataType, PredicateOperator};
389389
match predicate {
390390
Predicate::NestedLeaf { .. } => false,
391-
Predicate::Leaf { column, op, .. } => {
391+
Predicate::Leaf {
392+
column,
393+
op,
394+
data_type,
395+
..
396+
} => {
392397
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))
393401
&& !matches!(
394402
op,
395403
PredicateOperator::Contains

‎crates/paimon/tests/table_predicate_delete_test.rs‎

Lines changed: 81 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -20,12 +20,12 @@ mod common;
2020
use std::collections::HashMap;
2121
use std::sync::Arc;
2222

23-
use arrow_array::{ArrayRef, Int32Array, Int64Array, RecordBatch, StringArray};
23+
use arrow_array::{ArrayRef, Float64Array, Int32Array, Int64Array, RecordBatch, StringArray};
2424
use common::incremental_helpers::{memory_table, persist_table_schema, setup_dirs, write_batch};
2525
use futures::TryStreamExt;
2626
use paimon::spec::{
27-
DataType, Datum, IndexManifest, IntType, Predicate, PredicateBuilder, Schema, TableSchema,
28-
VarCharType,
27+
DataType, Datum, DoubleType, IndexManifest, IntType, Predicate, PredicateBuilder, Schema,
28+
TableSchema, VarCharType,
2929
};
3030
use paimon::table::{CommitMessage, Table};
3131

@@ -129,6 +129,35 @@ async fn ids(table: &Table) -> Vec<i32> {
129129
ids
130130
}
131131

132+
async fn read_ids(table: &Table, filter: Predicate) -> Vec<i32> {
133+
let mut read = table.new_read_builder();
134+
read.with_projection(&["id"]).unwrap();
135+
read.with_filter(filter);
136+
let plan = read.new_scan().plan().await.unwrap();
137+
let batches: Vec<RecordBatch> = read
138+
.new_read()
139+
.unwrap()
140+
.to_arrow(plan.splits())
141+
.unwrap()
142+
.try_collect()
143+
.await
144+
.unwrap();
145+
let mut ids: Vec<i32> = batches
146+
.iter()
147+
.flat_map(|batch| {
148+
batch
149+
.column(0)
150+
.as_any()
151+
.downcast_ref::<Int32Array>()
152+
.unwrap()
153+
.values()
154+
.to_vec()
155+
})
156+
.collect();
157+
ids.sort_unstable();
158+
ids
159+
}
160+
132161
async fn snapshot_id(table: &Table) -> i64 {
133162
table
134163
.snapshot_manager()
@@ -655,32 +684,7 @@ async fn negated_data_predicate_keeps_null_rows() {
655684
let pb = PredicateBuilder::new(&table.schema().fields_with_read_metadata());
656685
let predicate = Predicate::negate(pb.equal("v", Datum::Int(10)).unwrap());
657686

658-
let mut read = table.new_read_builder();
659-
read.with_projection(&["id"]).unwrap();
660-
read.with_filter(predicate.clone());
661-
let plan = read.new_scan().plan().await.unwrap();
662-
let batches: Vec<RecordBatch> = read
663-
.new_read()
664-
.unwrap()
665-
.to_arrow(plan.splits())
666-
.unwrap()
667-
.try_collect()
668-
.await
669-
.unwrap();
670-
let mut read_ids: Vec<i32> = batches
671-
.iter()
672-
.flat_map(|batch| {
673-
batch
674-
.column(0)
675-
.as_any()
676-
.downcast_ref::<Int32Array>()
677-
.unwrap()
678-
.values()
679-
.to_vec()
680-
})
681-
.collect();
682-
read_ids.sort_unstable();
683-
assert_eq!(read_ids, vec![1, 2]);
687+
assert_eq!(read_ids(&table, predicate.clone()).await, vec![1, 2]);
684688

685689
let update = table.new_write_builder().new_update().unwrap();
686690
commit(
@@ -690,3 +694,51 @@ async fn negated_data_predicate_keeps_null_rows() {
690694
.await;
691695
assert_eq!(ids(&table).await, vec![0, 3]);
692696
}
697+
698+
#[tokio::test]
699+
async fn negated_float_comparison_keeps_nan_rows() {
700+
// `NaN < 1.0` and `NaN >= 1.0` are both false. Java orders NaN above
701+
// every number, so NOT(f < 1.0) selects it, partitioned by `f` or not.
702+
for partitioned in [false, true] {
703+
let mut schema = Schema::builder()
704+
.column("id", DataType::Int(IntType::new()))
705+
.column("f", DataType::Double(DoubleType::new()))
706+
.option("data-evolution.enabled", "true")
707+
.option("row-tracking.enabled", "true")
708+
.option("deletion-vectors.enabled", "true");
709+
if partitioned {
710+
schema = schema.partition_keys(["f"]);
711+
}
712+
let path = "memory:/negated_float";
713+
let (io, table) = memory_table(path, TableSchema::new(0, &schema.build().unwrap()));
714+
setup_dirs(&io, path).await;
715+
persist_table_schema(&io, path, table.schema()).await;
716+
write_batch(
717+
&table,
718+
&RecordBatch::try_from_iter([
719+
("id", Arc::new(Int32Array::from(vec![0, 1, 2])) as ArrayRef),
720+
(
721+
"f",
722+
Arc::new(Float64Array::from(vec![0.0, f64::NAN, 2.0])) as ArrayRef,
723+
),
724+
])
725+
.unwrap(),
726+
)
727+
.await;
728+
let pb = PredicateBuilder::new(&table.schema().fields_with_read_metadata());
729+
let predicate = Predicate::negate(pb.less_than("f", Datum::Double(1.0)).unwrap());
730+
731+
assert_eq!(
732+
read_ids(&table, predicate.clone()).await,
733+
vec![1, 2],
734+
"partitioned={partitioned}"
735+
);
736+
let update = table.new_write_builder().new_update().unwrap();
737+
commit(
738+
&table,
739+
update.delete_by_predicate(Some(predicate)).await.unwrap(),
740+
)
741+
.await;
742+
assert_eq!(ids(&table).await, vec![0], "partitioned={partitioned}");
743+
}
744+
}

0 commit comments

Comments
 (0)