@@ -648,104 +648,116 @@ async fn scalar_coverage_gaps_follow_scalar_and_vector_modes() {
648648async 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}
0 commit comments