1515// specific language governing permissions and limitations
1616// under the License.
1717
18- //! Compare compact string IN-list pruning with per-value min/max expansion.
18+ //! Compare string IN-list pruning with per-value min/max expansion.
1919//!
2020//! Every case raises `max_in_list_size` to the domain size. On a baseline
2121//! without compact pruning, `in_list` and `not_in_list` measure the ordinary
2222//! raised-cap path. The explicit `expanded_or` and `expanded_and` are balanced
2323//! trees of (in)equalities, which produce the same per-value statistics checks
2424//! without making the baseline depend on a deeply nested expression.
2525//!
26- //! The main cases alternate intervals pinned to a domain member with intervals
27- //! that span a sparse gap. NULL-containing variants cover the optimized
26+ //! Small domain sizes make representation threshold changes measurable, and the
27+ //! evaluation matrix varies the number of statistics containers. The main cases
28+ //! alternate intervals pinned to a domain member with intervals that span a
29+ //! sparse gap. NULL-containing variants cover the optimized
2830//! filter-semantics paths, including the constant-false `NOT IN` rewrite.
2931//! Supplemental `NOT IN` cases measure uniform singleton containers, long bounds,
3032//! and long literals that share bounds' prefixes. Bloom filters are not involved.
3133//!
3234//! Run with `cargo bench -p datafusion-pruning --bench string_in_list_pruning`.
33- //! The construction benchmarks reuse their input physical expressions; the
34- //! evaluation benchmarks reuse their already-built pruning predicates.
35+ //! Construction is independent of the statistics batch size, so it varies only
36+ //! the IN-list domain size. Evaluation varies both the domain size and number
37+ //! of containers, reusing already-built pruning predicates and statistics.
3538
3639use std:: collections:: HashSet ;
3740use std:: hint:: black_box;
@@ -44,15 +47,47 @@ use datafusion_common::{Column, ScalarValue};
4447use datafusion_expr_common:: operator:: Operator ;
4548use datafusion_physical_expr:: PhysicalExprRef ;
4649use datafusion_physical_expr:: expressions:: { BinaryExpr , col, in_list, lit} ;
47- use datafusion_pruning:: { PruningPredicate , PruningPredicateBuilder , PruningStatistics } ;
50+ use datafusion_pruning:: {
51+ MAX_IN_LIST_SIZE , PruningPredicate , PruningPredicateBuilder , PruningStatistics ,
52+ } ;
4853
49- const DOMAIN_SIZES : [ usize ; 4 ] = [ 20 , 21 , 256 , 1024 ] ;
50- const CONTAINERS : usize = 4096 ;
54+ const DOMAIN_SIZES : [ usize ; 9 ] = [ 1 , 2 , 4 , 8 , 16 , 20 , 21 , 256 , 1024 ] ;
55+ const CONTAINER_COUNTS : [ usize ; 3 ] = [ 16 , 256 , 4096 ] ;
56+ const BASELINE_CONTAINER_COUNT : usize = 4096 ;
5157
5258fn value ( index : usize ) -> String {
5359 format ! ( "key{index:08}" )
5460}
5561
62+ /// Maps an interval pair to an evenly distributed position in the full domain.
63+ ///
64+ /// When there are more pairs than domain values, the full distribution repeats.
65+ fn sampled_domain_index (
66+ pair_index : usize ,
67+ pair_count : usize ,
68+ domain_size : usize ,
69+ ) -> usize {
70+ let sampled_positions = pair_count. min ( domain_size) ;
71+ let position = pair_index % sampled_positions;
72+ if sampled_positions == 1 {
73+ 0
74+ } else {
75+ position * ( domain_size - 1 ) / ( sampled_positions - 1 )
76+ }
77+ }
78+
79+ fn validate_sampling_distribution ( ) {
80+ assert_eq ! (
81+ ( 0 ..8 )
82+ . map( |pair| sampled_domain_index( pair, 8 , 1024 ) )
83+ . collect:: <Vec <_>>( ) ,
84+ vec![ 0 , 146 , 292 , 438 , 584 , 730 , 876 , 1023 ]
85+ ) ;
86+ assert_eq ! ( sampled_domain_index( 0 , 8 , 1 ) , 0 ) ;
87+ assert_eq ! ( sampled_domain_index( 1024 , 2048 , 1024 ) , 0 ) ;
88+ assert_eq ! ( sampled_domain_index( 2047 , 2048 , 1024 ) , 1023 ) ;
89+ }
90+
5691fn balanced ( expressions : & [ PhysicalExprRef ] , op : Operator ) -> PhysicalExprRef {
5792 if expressions. len ( ) == 1 {
5893 return Arc :: clone ( & expressions[ 0 ] ) ;
@@ -102,20 +137,21 @@ struct IntervalStatistics {
102137}
103138
104139impl IntervalStatistics {
105- fn new ( domain_size : usize ) -> Self {
106- let min = StringViewArray :: from_iter_values ( ( 0 ..CONTAINERS ) . map ( |index| {
107- let start = ( index / 2 % domain_size) * 10 ;
140+ fn new ( domain_size : usize , container_count : usize ) -> Self {
141+ let pair_count = container_count. div_ceil ( 2 ) ;
142+ let min = StringViewArray :: from_iter_values ( ( 0 ..container_count) . map ( |index| {
143+ let start = sampled_domain_index ( index / 2 , pair_count, domain_size) * 10 ;
108144 value ( start + if index % 2 == 0 { 0 } else { 3 } )
109145 } ) ) ;
110- let max = StringViewArray :: from_iter_values ( ( 0 ..CONTAINERS ) . map ( |index| {
111- let start = ( index / 2 % domain_size) * 10 ;
146+ let max = StringViewArray :: from_iter_values ( ( 0 ..container_count ) . map ( |index| {
147+ let start = sampled_domain_index ( index / 2 , pair_count , domain_size) * 10 ;
112148 value ( start + if index % 2 == 0 { 0 } else { 7 } )
113149 } ) ) ;
114150 Self {
115151 min : Arc :: new ( min) ,
116152 max : Arc :: new ( max) ,
117- null_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 0 ; CONTAINERS ] ) ) ,
118- row_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 128 ; CONTAINERS ] ) ) ,
153+ null_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 0 ; container_count ] ) ) ,
154+ row_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 128 ; container_count ] ) ) ,
119155 }
120156 }
121157
@@ -125,14 +161,16 @@ impl IntervalStatistics {
125161 }
126162
127163 fn singleton ( value : & str ) -> Self {
128- let min =
129- StringViewArray :: from_iter_values ( std:: iter:: repeat_n ( value, CONTAINERS ) ) ;
164+ let min = StringViewArray :: from_iter_values ( std:: iter:: repeat_n (
165+ value,
166+ BASELINE_CONTAINER_COUNT ,
167+ ) ) ;
130168 let max = min. clone ( ) ;
131169 Self {
132170 min : Arc :: new ( min) ,
133171 max : Arc :: new ( max) ,
134- null_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 0 ; CONTAINERS ] ) ) ,
135- row_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 128 ; CONTAINERS ] ) ) ,
172+ null_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 0 ; BASELINE_CONTAINER_COUNT ] ) ) ,
173+ row_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 128 ; BASELINE_CONTAINER_COUNT ] ) ) ,
136174 }
137175 }
138176
@@ -143,14 +181,14 @@ impl IntervalStatistics {
143181 Self {
144182 min : Arc :: new ( StringViewArray :: from_iter_values ( std:: iter:: repeat_n (
145183 min. as_str ( ) ,
146- CONTAINERS ,
184+ BASELINE_CONTAINER_COUNT ,
147185 ) ) ) ,
148186 max : Arc :: new ( StringViewArray :: from_iter_values ( std:: iter:: repeat_n (
149187 max. as_str ( ) ,
150- CONTAINERS ,
188+ BASELINE_CONTAINER_COUNT ,
151189 ) ) ) ,
152- null_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 0 ; CONTAINERS ] ) ) ,
153- row_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 128 ; CONTAINERS ] ) ) ,
190+ null_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 0 ; BASELINE_CONTAINER_COUNT ] ) ) ,
191+ row_counts : Arc :: new ( UInt64Array :: from ( vec ! [ 128 ; BASELINE_CONTAINER_COUNT ] ) ) ,
154192 }
155193 }
156194}
@@ -165,7 +203,7 @@ impl PruningStatistics for IntervalStatistics {
165203 }
166204
167205 fn num_containers ( & self ) -> usize {
168- CONTAINERS
206+ self . min . len ( )
169207 }
170208
171209 fn null_counts ( & self , column : & Column ) -> Option < ArrayRef > {
@@ -200,7 +238,6 @@ struct BenchmarkCase {
200238 not_in_list_predicate : PruningPredicate ,
201239 not_in_list_with_null_predicate : PruningPredicate ,
202240 expanded_and_predicate : PruningPredicate ,
203- statistics : IntervalStatistics ,
204241}
205242
206243impl BenchmarkCase {
@@ -250,36 +287,6 @@ impl BenchmarkCase {
250287 . to_string( )
251288 . contains( "NOT_IN_SET_MAY_MATCH" )
252289 ) ;
253- let statistics = IntervalStatistics :: new ( size) ;
254-
255- // Check that every benchmark path does the same useful work, rather
256- // than comparing compact pruning with an always-true fallback.
257- let kept = ( 0 ..CONTAINERS )
258- . map ( |index| index % 2 == 0 )
259- . collect :: < Vec < _ > > ( ) ;
260- let negated_kept = kept. iter ( ) . map ( |keep| !keep) . collect :: < Vec < _ > > ( ) ;
261- assert_eq ! ( in_list_predicate. prune( & statistics) . unwrap( ) , kept) ;
262- assert_eq ! (
263- in_list_with_null_predicate. prune( & statistics) . unwrap( ) ,
264- kept
265- ) ;
266- assert_eq ! ( expanded_or_predicate. prune( & statistics) . unwrap( ) , kept) ;
267- assert_eq ! (
268- not_in_list_predicate. prune( & statistics) . unwrap( ) ,
269- negated_kept
270- ) ;
271- assert_eq ! (
272- expanded_and_predicate. prune( & statistics) . unwrap( ) ,
273- negated_kept
274- ) ;
275- assert ! (
276- not_in_list_with_null_predicate
277- . prune( & statistics)
278- . unwrap( )
279- . iter( )
280- . all( |keep| !keep)
281- ) ;
282-
283290 Self {
284291 size,
285292 schema,
@@ -295,12 +302,61 @@ impl BenchmarkCase {
295302 not_in_list_predicate,
296303 not_in_list_with_null_predicate,
297304 expanded_and_predicate,
298- statistics,
299305 }
300306 }
301307}
302308
309+ fn expected_results ( container_count : usize ) -> Vec < bool > {
310+ ( 0 ..container_count) . map ( |index| index % 2 == 0 ) . collect ( )
311+ }
312+
313+ fn assert_equivalent_results ( case : & BenchmarkCase , statistics : & IntervalStatistics ) {
314+ let expected = expected_results ( statistics. num_containers ( ) ) ;
315+ assert_eq ! ( case. in_list_predicate. prune( statistics) . unwrap( ) , expected) ;
316+ assert_eq ! (
317+ case. expanded_or_predicate. prune( statistics) . unwrap( ) ,
318+ expected
319+ ) ;
320+ let negated_expected = expected. iter ( ) . map ( |keep| !keep) . collect :: < Vec < _ > > ( ) ;
321+ assert_eq ! (
322+ case. not_in_list_predicate. prune( statistics) . unwrap( ) ,
323+ negated_expected
324+ ) ;
325+ assert_eq ! (
326+ case. expanded_and_predicate. prune( statistics) . unwrap( ) ,
327+ negated_expected
328+ ) ;
329+
330+ let in_with_null = case. in_list_with_null_predicate . prune ( statistics) . unwrap ( ) ;
331+ let not_in_with_null = case
332+ . not_in_list_with_null_predicate
333+ . prune ( statistics)
334+ . unwrap ( ) ;
335+ if case. size + 1 > MAX_IN_LIST_SIZE {
336+ // Compact pruning applies filter semantics: NULL does not change which
337+ // rows can satisfy IN, while NOT IN (..., NULL) can never be true.
338+ assert_eq ! ( in_with_null, expected) ;
339+ assert ! ( not_in_with_null. iter( ) . all( |keep| !keep) ) ;
340+ } else {
341+ // The legacy per-value rewrite keeps UNKNOWN IN results and drops the
342+ // NULL term from NOT IN statistics pruning.
343+ assert ! ( in_with_null. iter( ) . all( |keep| * keep) ) ;
344+ assert_eq ! ( not_in_with_null, negated_expected) ;
345+ }
346+ }
347+
348+ fn evaluation_group_name ( container_count : usize ) -> String {
349+ // Keep the original benchmark IDs for the pre-existing 4,096-container
350+ // cases so Criterion baselines remain directly comparable.
351+ if container_count == BASELINE_CONTAINER_COUNT {
352+ "string_in_list_pruning/evaluate" . to_string ( )
353+ } else {
354+ format ! ( "string_in_list_pruning/evaluate/{container_count}_containers" )
355+ }
356+ }
357+
303358fn criterion_benchmark ( criterion : & mut Criterion ) {
359+ validate_sampling_distribution ( ) ;
304360 let cases = DOMAIN_SIZES . map ( BenchmarkCase :: new) ;
305361 let mut construction = criterion. benchmark_group ( "string_in_list_pruning/construct" ) ;
306362 for case in & cases {
@@ -334,41 +390,50 @@ fn criterion_benchmark(criterion: &mut Criterion) {
334390 }
335391 construction. finish ( ) ;
336392
337- let mut evaluation = criterion. benchmark_group ( "string_in_list_pruning/evaluate" ) ;
338- evaluation. throughput ( Throughput :: Elements ( CONTAINERS as u64 ) ) ;
339- for case in & cases {
340- for ( name, predicate, list_size) in [
341- ( "in_list" , & case. in_list_predicate , case. size ) ,
342- (
343- "in_list_with_null" ,
344- & case. in_list_with_null_predicate ,
345- case. size + 1 ,
346- ) ,
347- ( "expanded_or" , & case. expanded_or_predicate , case. size ) ,
348- ( "not_in_list" , & case. not_in_list_predicate , case. size ) ,
349- (
350- "not_in_list_with_null_constant_false" ,
351- & case. not_in_list_with_null_predicate ,
352- case. size + 1 ,
353- ) ,
354- ( "expanded_and" , & case. expanded_and_predicate , case. size ) ,
355- ] {
356- evaluation. bench_with_input (
357- BenchmarkId :: new ( name, list_size) ,
358- predicate,
359- |bencher, predicate| {
360- bencher. iter ( || {
361- black_box ( predicate. prune ( black_box ( & case. statistics ) ) . unwrap ( ) )
362- } ) ;
363- } ,
364- ) ;
393+ for container_count in CONTAINER_COUNTS {
394+ let mut evaluation =
395+ criterion. benchmark_group ( evaluation_group_name ( container_count) ) ;
396+ evaluation. throughput ( Throughput :: Elements ( container_count as u64 ) ) ;
397+ for case in & cases {
398+ let statistics = IntervalStatistics :: new ( case. size , container_count) ;
399+
400+ // Check every matrix cell outside the timed loop so all paths do
401+ // the same useful work rather than measuring an always-true fallback.
402+ assert_equivalent_results ( case, & statistics) ;
403+
404+ for ( name, predicate, list_size) in [
405+ ( "in_list" , & case. in_list_predicate , case. size ) ,
406+ (
407+ "in_list_with_null" ,
408+ & case. in_list_with_null_predicate ,
409+ case. size + 1 ,
410+ ) ,
411+ ( "expanded_or" , & case. expanded_or_predicate , case. size ) ,
412+ ( "not_in_list" , & case. not_in_list_predicate , case. size ) ,
413+ (
414+ "not_in_list_with_null_constant_false" ,
415+ & case. not_in_list_with_null_predicate ,
416+ case. size + 1 ,
417+ ) ,
418+ ( "expanded_and" , & case. expanded_and_predicate , case. size ) ,
419+ ] {
420+ evaluation. bench_with_input (
421+ BenchmarkId :: new ( name, list_size) ,
422+ predicate,
423+ |bencher, predicate| {
424+ bencher. iter ( || {
425+ black_box ( predicate. prune ( black_box ( & statistics) ) . unwrap ( ) )
426+ } ) ;
427+ } ,
428+ ) ;
429+ }
365430 }
431+ evaluation. finish ( ) ;
366432 }
367- evaluation. finish ( ) ;
368433
369434 let mut distributions =
370435 criterion. benchmark_group ( "string_in_list_pruning/not_in_distributions" ) ;
371- distributions. throughput ( Throughput :: Elements ( CONTAINERS as u64 ) ) ;
436+ distributions. throughput ( Throughput :: Elements ( BASELINE_CONTAINER_COUNT as u64 ) ) ;
372437 let singleton = IntervalStatistics :: uniform_singleton ( ) ;
373438 for case in cases. iter ( ) . filter ( |case| case. size > 20 ) {
374439 let compact = case. not_in_list_predicate . prune ( & singleton) . unwrap ( ) ;
0 commit comments