Repository navigation
perf: use compact pruning for large string IN lists #24526
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Changes from 1 commit
9447680
168b7b5
df65b7c
80898fa
1a2b38c
File filter
Filter by extension
Conversations
Jump to
Diff view
Diff view
- Loading branch information
There are no files selected for viewing
| Original file line number | Diff line number | Diff line change |
|---|---|---|
|
|
@@ -139,23 +139,23 @@ impl PagePruningResult { | |
| impl PagePruningAccessPlanFilter { | ||
| /// Create a new [`PagePruningAccessPlanFilter`] from a physical | ||
| /// expression, using the default `IN (...)` pruning limit. | ||
| #[expect(clippy::needless_pass_by_value)] | ||
| pub fn new(expr: &Arc<dyn PhysicalExpr>, schema: SchemaRef) -> Self { | ||
| Self::new_with_max_in_list_size(expr, schema, MAX_IN_LIST_SIZE) | ||
| Self::new_with_max_in_list_size(expr, &schema, MAX_IN_LIST_SIZE) | ||
| } | ||
|
|
||
| /// Create a page filter using the same `IN (...)` limit as row-group pruning. | ||
| #[expect(clippy::needless_pass_by_value)] | ||
| pub(crate) fn new_with_max_in_list_size( | ||
| expr: &Arc<dyn PhysicalExpr>, | ||
| schema: SchemaRef, | ||
| schema: &SchemaRef, | ||
| max_in_list_size: usize, | ||
| ) -> Self { | ||
| // extract any single column predicates | ||
| let predicates = split_conjunction(expr) | ||
| .into_iter() | ||
| .filter_map(|predicate| { | ||
| let pp = match PruningPredicateBuilder::new() | ||
| .with_file_schema(Arc::clone(&schema)) | ||
| .with_file_schema(Arc::clone(schema)) | ||
| .with_max_in_list_size(max_in_list_size) | ||
|
Contributor
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Indeed seems like this is all a thin wrapper around a builder, might be a sign...
Member
Author
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Yes, the construction already delegates to |
||
| .try_build(Arc::clone(predicate)) | ||
| { | ||
|
|
||
| Original file line number | Diff line number | Diff line change |
|---|---|---|
|
|
@@ -1629,6 +1629,9 @@ fn build_predicate_expression( | |
| } | ||
| } | ||
| if let Some(in_list) = expr.downcast_ref::<phys_expr::InListExpr>() { | ||
| // Preserve the existing per-value representation for lists within | ||
| // the default limit. Use the compact form only when callers raise | ||
| // the cap; MAX_IN_LIST_SIZE is not a measured performance crossover. | ||
| if in_list.list().len() > MAX_IN_LIST_SIZE | ||
|
Member
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. The window is
Member
Author
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. The lower bound preserves the existing pruning-expression representation for lists of at most 20 values and keeps this PR focused on the cost of large lists when callers explicitly raise the cap. The value 20 comes from the existing default; it is not an established performance crossover. Using the compact form for smaller eligible string lists is worth considering separately. The current benchmark keeps the 20-value case on the legacy path, so it does not establish that compact construction/normalization is cheaper across the small-list cases. A focused comparison could justify broadening the optimization later. Agreed that the scope/default-behavior rationale should be stated next to this condition.
Member
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. This is the one remaining item from the earlier thread — you agreed the scope/default-behaviour rationale should sit next to this condition, and it doesn't appear to be in
Member
Author
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Made this explicit beside the condition in 80898fa: the lower bound is a scope/compatibility choice, not a measured performance threshold. It preserves the existing expression shape for lists of at most 20 values. I also added the exact inclusive boundaries to the builder docs and PR description. |
||
| && in_list.list().len() <= max_in_list_size | ||
| && let Some(pruning_expr) = | ||
|
|
||
| Original file line number | Diff line number | Diff line change |
|---|---|---|
|
|
@@ -133,10 +133,16 @@ impl PhysicalExpr for StringInListPruningExpr { | |
| if min > max { | ||
| return None; | ||
| } | ||
| // Rust string ordering and these byte comparisons both use | ||
| // unsigned lexicographic UTF-8 order. Statistics providers | ||
|
Member
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. This comment states a contract on statistics providers generally, but the enforcement it points at is Parquet-specific. I checked the other providers that can reach this expression — eligibility keys only on the schema type being a string, so it carries no knowledge of who supplied the bounds:
The exposure isn't new; the per-value
Member
Author
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Agreed. 80898fa documents the shared contract on |
||
| // must supply bounds in that order or mark them unavailable; | ||
| // Parquet adapters already mask bounds with unusable ordering. | ||
| let index = self.values.partition_point(|v| v.as_bytes() < min); | ||
|
Member
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. The set is sorted with Relatedly: is there any path where the column's
Member
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Following up on my own question: I see now that #24525 — the PR this one is stacked on — is precisely about this, distinguishing the legacy signed-byte What's still worth confirming is narrower: does the compact path here sit behind the same ordering gate that #24525 introduces? Since
Member
Author
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Yes—the compact expression reads the same gated min/max columns as the per-value expressions; it does not access raw Parquet metadata. The row-group adapter withholds bounds for unusable footer ordering and masks deprecated byte-array bounds to NULL. The page adapter also withholds untrusted bounds, and runtime row-group pruning reuses the row-group adapter. The distinction is that we suppress unusable bounds, not the entire predicate: the compact expression can still run with NULL bounds and return UNKNOWN, keeping the container unless independent statistics, such as an all-null count, safely exclude it. The 22-value page regression explicitly asserts Agreed about making the ordering assumption explicit: Rust string ordering and these byte comparisons both use unsigned lexicographic UTF-8 byte order. Generic |
||
| Some(self.values.get(index).is_some_and(|v| v.as_bytes() <= max)) | ||
| } | ||
| // A single known bound can still exclude the whole domain. | ||
| // A missing bound makes that end of the interval unbounded. | ||
| // Exclude only when the whole domain lies beyond the known bound; | ||
| // gaps within the domain and equality cannot prove disjointness. | ||
| (Some(min), None) | ||
|
Member
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. These single-bound arms exclude via
Member
Author
There was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Yes, that is the intended reading. With only The interval regression checks both exclusions and equality at the endpoints for lists of 20, 21, 256, and 10,000 values. Agreed that spelling out the unbounded-interval interpretation would improve the comment. |
||
| if self.values.last().is_some_and(|v| v.as_bytes() < min) => | ||
| { | ||
|
|
||
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
This seems to me like the kind of thing where we would want a
PagePruningAccessPlanFilterBuilderin the future if we add any more options / constructors. But maybe this is fine for now.There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Agreed that a builder would be the next step if we add more options. For this PR I kept the public
newAPI unchanged and used the internal helper only to pass the existing configured cap through to page pruning. I'll leave the broader constructor refactor separate.