Skip to content

Commit eaf7fff

Browse files
authored
perf: use compact pruning for large string NOT IN lists (apache#24781)
## Which issue does this PR close? <!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes apache#123` indicates that this PR will close issue apache#123. --> - Part of apache#24711. ## Rationale for this change Large string NOT IN lists create long expression chains for Parquet pruning. These expressions are expensive to build and evaluate. <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. Please explain the problem you are trying to solve in terms of the user-visible behavior, rather than the implementation. For example, "The code in `foo.rs` doesn't handle nulls" is a symptom of the implementation. "COUNT(DISTINCT) returns wrong results when the column contains nulls" is the user-visible problem. --> ## What changes are included in this PR? - Use a compact sorted domain for large, non-null string NOT IN lists. - Preserve the existing behavior for lists containing NULL. - Add unit tests and Parquet row-group and page-pruning tests. - Add a mixed-container regression test. - Extend the existing benchmark and configuration documentation. - In a local benchmark with 1,024 values, construction was about 17 times faster and evaluation was about 27 times faster. <!-- There is no need to duplicate the description in the issue here, but it is sometimes worth providing a summary of the individual changes in this PR. --> ## Are these changes tested? Yes <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> ## Are there any user-facing changes? No public API changes <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent 39d36f0 commit eaf7fff

7 files changed

Lines changed: 823 additions & 101 deletions

File tree

‎datafusion/common/src/config.rs‎

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1373,10 +1373,10 @@ config_namespace! {
13731373
/// rewrite; other predicates and Bloom-filter pruning remain available.
13741374
///
13751375
/// Within the cap, nonempty lists of at most 20 values use the existing
1376-
/// per-value rewrite. Larger positive, non-null literal string lists
1377-
/// on a string column use a compact sorted domain. Other lists retain
1378-
/// the existing per-value rewrite, so raising the cap can make those
1379-
/// predicates expensive to build and evaluate.
1376+
/// per-value rewrite. Larger non-null literal string lists on a string
1377+
/// column use a compact sorted domain, for both `IN` and `NOT IN`.
1378+
/// Other lists retain the existing per-value rewrite, so raising the cap
1379+
/// can make those predicates expensive to build and evaluate.
13801380
///
13811381
/// Defaults to 20.
13821382
pub max_in_list_size: usize, default = 20

‎datafusion/core/tests/parquet/string_in_list_pruning.rs‎

Lines changed: 192 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -15,8 +15,8 @@
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
2121
use std::sync::Arc;
2222

@@ -47,10 +47,37 @@ const UNITS: usize = 4;
4747
const TOTAL_ROWS: usize = ROWS_PER_UNIT * UNITS;
4848
const 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.
5354
fn 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]
259417
async 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]
269443
async fn string_not_in_list_with_null_does_not_bypass_row_filter() {
270444
let mut file = tempfile::Builder::new()

0 commit comments

Comments
 (0)