1515// specific language governing permissions and limitations
1616// under the License.
1717
18- //! End-to-end coverage for compact, large string IN-list pruning. The positive
19- //! IN-list cases disable the row and Bloom filters to isolate min/max pruning.
18+ //! End-to-end coverage for compact, large string IN-list pruning. The `IN` and
19+ //! `NOT IN` cases disable the row and Bloom filters to isolate min/max pruning.
2020
2121use std:: sync:: Arc ;
2222
@@ -47,10 +47,37 @@ const UNITS: usize = 4;
4747const TOTAL_ROWS : usize = ROWS_PER_UNIT * UNITS ;
4848const MATCHING_ROWS : usize = ROWS_PER_UNIT * 2 ;
4949
50- /// Write either four row groups or four pages in one row group. The second
51- /// unit lies in a gap between two members of every test IN list; an enclosing
52- /// min/max range for the list cannot prune it.
50+ /// Write either four row groups or four pages in one row group. Each unit holds
51+ /// a single repeated value, so `NOT IN` can exclude the two units whose value is
52+ /// a list member. The second unit lies in a gap between two members of every
53+ /// test IN list; an enclosing min/max range for the list cannot prune it.
5354fn make_file ( page_pruning : bool ) -> NamedTempFile {
55+ let values = [ "v000000" , "v000001" , "v000010" , "v999999" ]
56+ . into_iter ( )
57+ . flat_map ( |value| std:: iter:: repeat_n ( value, ROWS_PER_UNIT ) )
58+ . collect :: < Vec < _ > > ( ) ;
59+ write_file ( page_pruning, values)
60+ }
61+
62+ /// Write one mixed unit and one single-valued unit. The mixed unit contains
63+ /// both a list member and a value that satisfies `NOT IN`.
64+ fn make_mixed_not_in_file ( page_pruning : bool ) -> NamedTempFile {
65+ let values = std:: iter:: repeat_n ( "v000000" , ROWS_PER_UNIT / 2 )
66+ . chain ( std:: iter:: repeat_n ( "v000001" , ROWS_PER_UNIT / 2 ) )
67+ . chain ( std:: iter:: repeat_n ( "v000010" , ROWS_PER_UNIT ) )
68+ . collect :: < Vec < _ > > ( ) ;
69+ write_file ( page_pruning, values)
70+ }
71+
72+ fn write_file ( page_pruning : bool , values : Vec < & str > ) -> NamedTempFile {
73+ write_file_with_truncation ( page_pruning, values, None )
74+ }
75+
76+ fn write_file_with_truncation (
77+ page_pruning : bool ,
78+ values : Vec < & str > ,
79+ truncation_length : Option < usize > ,
80+ ) -> NamedTempFile {
5481 let mut file = tempfile:: Builder :: new ( )
5582 . prefix ( "string_in_list_pruning" )
5683 . suffix ( ".parquet" )
@@ -61,32 +88,35 @@ fn make_file(page_pruning: bool) -> NamedTempFile {
6188 DataType :: Utf8 ,
6289 false ,
6390 ) ] ) ) ;
64- let values = [ "v000000" , "v000001" , "v000010" , "v999999" ]
65- . into_iter ( )
66- . flat_map ( |value| std:: iter:: repeat_n ( value, ROWS_PER_UNIT ) )
67- . collect :: < Vec < _ > > ( ) ;
91+ let total_rows = values. len ( ) ;
92+ assert_eq ! ( total_rows % ROWS_PER_UNIT , 0 ) ;
6893 let batch = RecordBatch :: try_new (
6994 Arc :: clone ( & schema) ,
7095 vec ! [ Arc :: new( StringArray :: from( values) ) ] ,
7196 )
7297 . unwrap ( ) ;
7398 let rows_per_group = if page_pruning {
74- TOTAL_ROWS
99+ total_rows
75100 } else {
76101 ROWS_PER_UNIT
77102 } ;
78- let properties = WriterProperties :: builder ( )
103+ let mut properties = WriterProperties :: builder ( )
79104 . set_max_row_group_row_count ( Some ( rows_per_group) )
80105 . set_data_page_row_count_limit ( ROWS_PER_UNIT )
81106 . set_write_batch_size ( ROWS_PER_UNIT )
82107 . set_dictionary_enabled ( false )
83108 . set_bloom_filter_enabled ( false )
84- . set_statistics_enabled ( EnabledStatistics :: Page )
85- . build ( ) ;
109+ . set_statistics_enabled ( EnabledStatistics :: Page ) ;
110+ if let Some ( truncation_length) = truncation_length {
111+ properties = properties
112+ . set_statistics_truncate_length ( Some ( truncation_length) )
113+ . set_column_index_truncate_length ( Some ( truncation_length) ) ;
114+ }
115+ let properties = properties. build ( ) ;
86116 let mut writer = ArrowWriter :: try_new ( & mut file, schema, Some ( properties) ) . unwrap ( ) ;
87117 writer. write ( & batch) . unwrap ( ) ;
88118 let metadata = writer. close ( ) . unwrap ( ) ;
89- assert_eq ! ( metadata. num_row_groups( ) , TOTAL_ROWS / rows_per_group) ;
119+ assert_eq ! ( metadata. num_row_groups( ) , total_rows / rows_per_group) ;
90120 let offsets = metadata. offset_index ( ) . unwrap ( ) ;
91121 for row_group in offsets {
92122 assert_eq ! (
@@ -151,6 +181,27 @@ impl ScanOutput {
151181 ] ,
152182 & self . batches
153183 ) ;
184+ self . assert_no_filter_interference ( ) ;
185+ }
186+
187+ /// The complement of [`Self::assert_results`]: the two units whose value is
188+ /// not a list member.
189+ fn assert_negated_results ( & self ) {
190+ assert_batches_eq ! (
191+ [
192+ "+---------+----+" ,
193+ "| value | n |" ,
194+ "+---------+----+" ,
195+ "| v000001 | 16 |" ,
196+ "| v999999 | 16 |" ,
197+ "+---------+----+" ,
198+ ] ,
199+ & self . batches
200+ ) ;
201+ self . assert_no_filter_interference ( ) ;
202+ }
203+
204+ fn assert_no_filter_interference ( & self ) {
154205 assert_eq ! ( self . counter( "predicate_evaluation_errors" ) , 0 ) ;
155206 assert_eq ! ( self . counter( "pushdown_rows_pruned" ) , 0 ) ;
156207 assert_eq ! ( self . pruned( "row_groups_pruned_bloom_filter" ) , 0 ) ;
@@ -162,6 +213,7 @@ async fn scan(
162213 list_size : usize ,
163214 max_in_list_size : Option < usize > ,
164215 page_pruning : bool ,
216+ negated : bool ,
165217) -> ScanOutput {
166218 let mut config = SessionConfig :: new ( )
167219 . with_target_partitions ( 1 )
@@ -183,9 +235,10 @@ async fn scan(
183235 . map ( |index| format ! ( "'v{:06}'" , index * 10 ) )
184236 . collect :: < Vec < _ > > ( )
185237 . join ( ", " ) ;
238+ let op = if negated { "NOT IN" } else { "IN" } ;
186239 let sql = format ! (
187240 "SELECT value, count(*) AS n FROM t \
188- WHERE value IN ({values}) GROUP BY value ORDER BY value"
241+ WHERE value {op} ({values}) GROUP BY value ORDER BY value"
189242 ) ;
190243 let plan = ctx
191244 . sql ( & sql)
@@ -209,14 +262,14 @@ async fn check_string_in_list_pruning(page_pruning: bool) {
209262 for list_size in [ 20 , 21 , 256 , 1024 ] {
210263 // A zero cap provides a result-equivalence control that cannot use
211264 // min/max IN-list pruning at either granularity.
212- let unpruned = scan ( & file, list_size, Some ( 0 ) , page_pruning) . await ;
265+ let unpruned = scan ( & file, list_size, Some ( 0 ) , page_pruning, false ) . await ;
213266 unpruned. assert_results ( ) ;
214267 assert ! ( !unpruned. plan. contains( "IN_SET_INTERSECTS" ) ) ;
215268 assert_eq ! ( unpruned. pruned( "row_groups_pruned_statistics" ) , 0 ) ;
216269 assert_eq ! ( unpruned. pruned( "page_index_rows_pruned" ) , 0 ) ;
217270 assert_eq ! ( unpruned. counter( "output_rows" ) , TOTAL_ROWS ) ;
218271
219- let output = scan ( & file, list_size, Some ( list_size) , page_pruning) . await ;
272+ let output = scan ( & file, list_size, Some ( list_size) , page_pruning, false ) . await ;
220273 output. assert_results ( ) ;
221274 assert_eq ! (
222275 pretty_format_batches( & output. batches) . unwrap( ) . to_string( ) ,
@@ -247,14 +300,119 @@ async fn check_string_in_list_pruning(page_pruning: bool) {
247300
248301 // The default remains 20: enabling the compact representation must not
249302 // silently change the public cap's meaning.
250- let default = scan ( & file, 21 , None , page_pruning) . await ;
303+ let default = scan ( & file, 21 , None , page_pruning, false ) . await ;
251304 default. assert_results ( ) ;
252305 assert ! ( !default . plan. contains( "IN_SET_INTERSECTS" ) ) ;
253306 assert_eq ! ( default . pruned( "row_groups_pruned_statistics" ) , 0 ) ;
254307 assert_eq ! ( default . pruned( "page_index_rows_pruned" ) , 0 ) ;
255308 assert_eq ! ( default . counter( "output_rows" ) , TOTAL_ROWS ) ;
256309}
257310
311+ /// The compact `NOT IN` form must prune exactly the units whose single repeated
312+ /// value is a list member, and nothing else. Overlapping a list member is not
313+ /// enough: units 1 and 3 each sit inside the list's enclosing range.
314+ async fn check_string_not_in_list_pruning ( page_pruning : bool ) {
315+ let file = make_file ( page_pruning) ;
316+ for list_size in [ 20 , 21 , 256 , 1024 ] {
317+ let unpruned = scan ( & file, list_size, Some ( 0 ) , page_pruning, true ) . await ;
318+ unpruned. assert_negated_results ( ) ;
319+ assert ! ( !unpruned. plan. contains( "NOT_IN_SET_MAY_MATCH" ) ) ;
320+ assert_eq ! ( unpruned. pruned( "row_groups_pruned_statistics" ) , 0 ) ;
321+ assert_eq ! ( unpruned. pruned( "page_index_rows_pruned" ) , 0 ) ;
322+ assert_eq ! ( unpruned. counter( "output_rows" ) , TOTAL_ROWS ) ;
323+
324+ let output = scan ( & file, list_size, Some ( list_size) , page_pruning, true ) . await ;
325+ output. assert_negated_results ( ) ;
326+ assert_eq ! (
327+ pretty_format_batches( & output. batches) . unwrap( ) . to_string( ) ,
328+ pretty_format_batches( & unpruned. batches)
329+ . unwrap( )
330+ . to_string( )
331+ ) ;
332+ assert_eq ! (
333+ output. plan. contains( "NOT_IN_SET_MAY_MATCH" ) ,
334+ list_size > 20 ,
335+ "list_size={list_size}, plan={}" ,
336+ output. plan
337+ ) ;
338+ // The compact form and the per-value AND chain it replaces prune the
339+ // same units, so the counts do not depend on which one ran.
340+ assert_eq ! (
341+ output. pruned( "row_groups_pruned_statistics" ) ,
342+ if page_pruning { 0 } else { 2 } ,
343+ "list_size={list_size}, metrics={}" ,
344+ output. metrics
345+ ) ;
346+ assert_eq ! (
347+ output. pruned( "page_index_rows_pruned" ) ,
348+ if page_pruning { MATCHING_ROWS } else { 0 } ,
349+ "list_size={list_size}, metrics={}" ,
350+ output. metrics
351+ ) ;
352+ assert_eq ! ( output. counter( "output_rows" ) , MATCHING_ROWS ) ;
353+ }
354+
355+ let default = scan ( & file, 21 , None , page_pruning, true ) . await ;
356+ default. assert_negated_results ( ) ;
357+ assert ! ( !default . plan. contains( "NOT_IN_SET_MAY_MATCH" ) ) ;
358+ assert_eq ! ( default . pruned( "row_groups_pruned_statistics" ) , 0 ) ;
359+ assert_eq ! ( default . pruned( "page_index_rows_pruned" ) , 0 ) ;
360+ assert_eq ! ( default . counter( "output_rows" ) , TOTAL_ROWS ) ;
361+
362+ // A mixed interval that overlaps a list member can still contain matching
363+ // rows. Only the adjacent single-valued unit can be excluded.
364+ let mixed_file = make_mixed_not_in_file ( page_pruning) ;
365+ let unpruned = scan ( & mixed_file, 21 , Some ( 0 ) , page_pruning, true ) . await ;
366+ assert_batches_eq ! (
367+ [
368+ "+---------+---+" ,
369+ "| value | n |" ,
370+ "+---------+---+" ,
371+ "| v000001 | 8 |" ,
372+ "+---------+---+" ,
373+ ] ,
374+ & unpruned. batches
375+ ) ;
376+ unpruned. assert_no_filter_interference ( ) ;
377+ assert_eq ! ( unpruned. pruned( "row_groups_pruned_statistics" ) , 0 ) ;
378+ assert_eq ! ( unpruned. pruned( "page_index_rows_pruned" ) , 0 ) ;
379+ assert_eq ! ( unpruned. counter( "output_rows" ) , ROWS_PER_UNIT * 2 ) ;
380+
381+ let output = scan ( & mixed_file, 21 , Some ( 21 ) , page_pruning, true ) . await ;
382+ assert_eq ! (
383+ pretty_format_batches( & output. batches) . unwrap( ) . to_string( ) ,
384+ pretty_format_batches( & unpruned. batches)
385+ . unwrap( )
386+ . to_string( )
387+ ) ;
388+ output. assert_no_filter_interference ( ) ;
389+ assert ! ( output. plan. contains( "NOT_IN_SET_MAY_MATCH" ) ) ;
390+ assert_eq ! (
391+ output. pruned( "row_groups_pruned_statistics" ) ,
392+ usize :: from( !page_pruning)
393+ ) ;
394+ assert_eq ! (
395+ output. pruned( "page_index_rows_pruned" ) ,
396+ if page_pruning { ROWS_PER_UNIT } else { 0 }
397+ ) ;
398+ assert_eq ! ( output. counter( "output_rows" ) , ROWS_PER_UNIT ) ;
399+ }
400+
401+ async fn check_string_not_in_list_with_truncated_bounds ( page_pruning : bool ) {
402+ // Exact bounds for this singleton are equal and can exclude the unit. With
403+ // four-byte truncation, Parquet lowers the min and raises the max instead.
404+ let values = std:: iter:: repeat_n ( "v000000" , ROWS_PER_UNIT ) . collect ( ) ;
405+ let file = write_file_with_truncation ( page_pruning, values, Some ( 4 ) ) ;
406+ let output = scan ( & file, 21 , Some ( 21 ) , page_pruning, true ) . await ;
407+
408+ assert ! ( output. batches. iter( ) . all( |batch| batch. num_rows( ) == 0 ) ) ;
409+ output. assert_no_filter_interference ( ) ;
410+ assert ! ( output. plan. contains( "NOT_IN_SET_MAY_MATCH" ) ) ;
411+ assert_eq ! ( output. pruned( "row_groups_pruned_statistics" ) , 0 ) ;
412+ assert_eq ! ( output. pruned( "page_index_rows_pruned" ) , 0 ) ;
413+ assert_eq ! ( output. counter( "output_rows" ) , ROWS_PER_UNIT ) ;
414+ }
415+
258416#[ tokio:: test]
259417async fn string_in_list_row_group_pruning ( ) {
260418 check_string_in_list_pruning ( false ) . await ;
@@ -265,6 +423,22 @@ async fn string_in_list_page_pruning() {
265423 check_string_in_list_pruning ( true ) . await ;
266424}
267425
426+ #[ tokio:: test]
427+ async fn string_not_in_list_row_group_pruning ( ) {
428+ check_string_not_in_list_pruning ( false ) . await ;
429+ }
430+
431+ #[ tokio:: test]
432+ async fn string_not_in_list_page_pruning ( ) {
433+ check_string_not_in_list_pruning ( true ) . await ;
434+ }
435+
436+ #[ tokio:: test]
437+ async fn string_not_in_list_with_truncated_bounds ( ) {
438+ check_string_not_in_list_with_truncated_bounds ( false ) . await ;
439+ check_string_not_in_list_with_truncated_bounds ( true ) . await ;
440+ }
441+
268442#[ tokio:: test]
269443async fn string_not_in_list_with_null_does_not_bypass_row_filter ( ) {
270444 let mut file = tempfile:: Builder :: new ( )
0 commit comments