Skip to content

Commit f7f780a

Browse files
committed
perf: target profitable dictionary preservation
1 parent b814a49 commit f7f780a

17 files changed

Lines changed: 2177 additions & 216 deletions

File tree

‎Cargo.lock‎

Lines changed: 2 additions & 0 deletions
Some generated files are not rendered by default. Learn more about customizing how changed files appear on GitHub.

‎datafusion/catalog-listing/src/table.rs‎

Lines changed: 132 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -34,7 +34,8 @@ use datafusion_expr::dml::InsertOp;
3434
use datafusion_expr::execution_props::ExecutionProps;
3535
use datafusion_expr::physical_planning_context::PhysicalPlanningContext;
3636
use datafusion_expr::{
37-
Expr, Partitioning as LogicalPartitioning, TableProviderFilterPushDown, TableType,
37+
Expr, Operator, Partitioning as LogicalPartitioning, TableProviderFilterPushDown,
38+
TableType,
3839
};
3940
use datafusion_physical_expr::{create_lex_ordering, create_physical_partitioning};
4041
use datafusion_physical_expr_adapter::PhysicalExprAdapterFactory;
@@ -627,29 +628,81 @@ impl TableProvider for ListingTable {
627628
}
628629

629630
impl ListingTable {
631+
fn filter_supports_dictionary_column(expr: &Expr, column_name: &str) -> bool {
632+
if !expr
633+
.column_refs()
634+
.iter()
635+
.any(|column| column.name == column_name)
636+
{
637+
return true;
638+
}
639+
640+
match expr {
641+
Expr::BinaryExpr(binary) => match binary.op {
642+
Operator::And | Operator::Or => {
643+
Self::filter_supports_dictionary_column(
644+
binary.left.as_ref(),
645+
column_name,
646+
) && Self::filter_supports_dictionary_column(
647+
binary.right.as_ref(),
648+
column_name,
649+
)
650+
}
651+
Operator::Eq => {
652+
let is_column = |expr: &Expr| matches!(expr, Expr::Column(column) if column.name == column_name);
653+
(is_column(binary.left.as_ref())
654+
&& matches!(binary.right.as_ref(), Expr::Literal(_, _)))
655+
|| (is_column(binary.right.as_ref())
656+
&& matches!(binary.left.as_ref(), Expr::Literal(_, _)))
657+
}
658+
_ => false,
659+
},
660+
Expr::InList(in_list) => {
661+
!in_list.negated
662+
&& !in_list.list.is_empty()
663+
&& matches!(in_list.expr.as_ref(), Expr::Column(column) if column.name == column_name)
664+
&& in_list
665+
.list
666+
.iter()
667+
.all(|expr| matches!(expr, Expr::Literal(_, _)))
668+
}
669+
Expr::Like(like) => {
670+
like.negated
671+
&& !like.case_insensitive
672+
&& like.escape_char.is_none()
673+
&& matches!(like.expr.as_ref(), Expr::Column(column) if column.name == column_name)
674+
&& matches!(like.pattern.as_ref(), Expr::Literal(_, _))
675+
}
676+
_ => false,
677+
}
678+
}
679+
630680
fn physical_statistics_required(
631681
&self,
632682
state: &dyn Session,
633683
projection: Option<&[usize]>,
684+
excluded_columns: &HashSet<&str>,
634685
) -> bool {
635686
if !state
636687
.config_options()
637688
.optimizer
638-
.enable_dictionary_aggregation
689+
.enable_dictionary_preservation
639690
{
640691
return false;
641692
}
642693

643694
let file_fields = self.file_schema.fields();
644695
match projection {
645696
Some(projection) => projection.iter().any(|index| {
646-
file_fields
647-
.get(*index)
648-
.is_some_and(|field| field.data_type() == &DataType::Utf8View)
697+
file_fields.get(*index).is_some_and(|field| {
698+
field.data_type() == &DataType::Utf8View
699+
&& !excluded_columns.contains(field.name().as_str())
700+
})
701+
}),
702+
None => file_fields.iter().any(|field| {
703+
field.data_type() == &DataType::Utf8View
704+
&& !excluded_columns.contains(field.name().as_str())
649705
}),
650-
None => file_fields
651-
.iter()
652-
.any(|field| field.data_type() == &DataType::Utf8View),
653706
}
654707
}
655708

@@ -693,12 +746,31 @@ impl ListingTable {
693746
filters.iter().cloned().partition(|filter| {
694747
can_be_evaluated_for_partition_pruning(&table_partition_col_names, filter)
695748
});
696-
// The dictionary aggregation rule rejects scans with data filters or
697-
// limits, so avoid collecting its optional file metadata for plans it
698-
// cannot rewrite. Partition-only filters remain eligible.
699-
let physical_statistics_required = filters.is_empty()
700-
&& limit.is_none()
701-
&& self.physical_statistics_required(state, projection.as_deref());
749+
// A data filter can remain transparent to a dictionary grouping column
750+
// when it does not reference that column. Case-sensitive literal
751+
// `NOT LIKE` filters can keep the dictionary through grouping, while
752+
// equality and `IN` filters can benefit when the string is discarded
753+
// immediately afterwards.
754+
// Exclude only columns whose filter use cannot support either rewrite.
755+
let filtered_columns: HashSet<_> = filters
756+
.iter()
757+
.flat_map(Expr::column_refs)
758+
.map(|column| column.name.as_str())
759+
.collect();
760+
let excluded_columns: HashSet<_> = filtered_columns
761+
.into_iter()
762+
.filter(|column_name| {
763+
filters.iter().any(|filter| {
764+
!Self::filter_supports_dictionary_column(filter, column_name)
765+
})
766+
})
767+
.collect();
768+
let physical_statistics_required = limit.is_none()
769+
&& self.physical_statistics_required(
770+
state,
771+
projection.as_deref(),
772+
&excluded_columns,
773+
);
702774

703775
let declared_output_partitioning = self.options.output_partitioning.as_ref();
704776

@@ -979,7 +1051,8 @@ impl ListingTable {
9791051
filters: &'a [Expr],
9801052
limit: Option<usize>,
9811053
) -> datafusion_common::Result<ListFilesResult> {
982-
let physical_statistics_required = self.physical_statistics_required(ctx, None);
1054+
let physical_statistics_required =
1055+
self.physical_statistics_required(ctx, None, &HashSet::new());
9831056
self.list_files_for_scan_inner(
9841057
ctx,
9851058
filters,
@@ -1041,15 +1114,7 @@ impl ListingTable {
10411114
.await?;
10421115
let meta_fetch_concurrency =
10431116
ctx.config_options().execution.meta_fetch_concurrency.get();
1044-
// Table paths can overlap, for example when one path is a directory and
1045-
// another names a file inside it. A ListingTable uses one object store,
1046-
// so the object path uniquely identifies a file within this scan.
1047-
let mut seen_files = HashSet::new();
1048-
let file_list = stream::iter(file_list)
1049-
.flatten_unordered(meta_fetch_concurrency)
1050-
.try_filter(move |file| {
1051-
future::ready(seen_files.insert(file.object_meta.location.clone()))
1052-
});
1117+
let file_list = stream::iter(file_list).flatten_unordered(meta_fetch_concurrency);
10531118
// collect the statistics and ordering if required by the config
10541119
let files = file_list
10551120
.map(|part_file| async {
@@ -1517,6 +1582,49 @@ mod tests {
15171582
ListingTable::try_new(config).unwrap()
15181583
}
15191584

1585+
#[test]
1586+
fn dictionary_filter_support_matches_q16_candidates() {
1587+
use datafusion_expr::{col, lit};
1588+
1589+
let filter = col("p_brand")
1590+
.not_eq(lit("Brand#45"))
1591+
.and(col("p_type").not_like(lit("MEDIUM POLISHED%")));
1592+
assert!(ListingTable::filter_supports_dictionary_column(
1593+
&filter, "p_type"
1594+
));
1595+
assert!(!ListingTable::filter_supports_dictionary_column(
1596+
&filter, "p_brand"
1597+
));
1598+
assert!(!ListingTable::filter_supports_dictionary_column(
1599+
&col("p_type").like(col("pattern")),
1600+
"p_type"
1601+
));
1602+
assert!(!ListingTable::filter_supports_dictionary_column(
1603+
&col("p_type").like(lit("MEDIUM POLISHED%")),
1604+
"p_type"
1605+
));
1606+
assert!(!ListingTable::filter_supports_dictionary_column(
1607+
&col("p_type").not_ilike(lit("MEDIUM POLISHED%")),
1608+
"p_type"
1609+
));
1610+
1611+
let q19_filter = col("l_shipinstruct")
1612+
.eq(lit("DELIVER IN PERSON"))
1613+
.and(col("l_shipmode").in_list(vec![lit("AIR"), lit("AIR REG")], false));
1614+
assert!(ListingTable::filter_supports_dictionary_column(
1615+
&q19_filter,
1616+
"l_shipinstruct"
1617+
));
1618+
assert!(ListingTable::filter_supports_dictionary_column(
1619+
&q19_filter,
1620+
"l_shipmode"
1621+
));
1622+
assert!(!ListingTable::filter_supports_dictionary_column(
1623+
&col("l_shipmode").in_list(vec![lit("AIR")], true),
1624+
"l_shipmode"
1625+
));
1626+
}
1627+
15201628
/// Helper to create a PhysicalSortExpr
15211629
fn sort_expr(
15221630
name: &str,

‎datafusion/common/src/config.rs‎

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1642,11 +1642,11 @@ config_namespace! {
16421642
/// [`SessionConfig`]: https://docs.rs/datafusion/latest/datafusion/prelude/struct.SessionConfig.html
16431643
pub struct OptimizerOptions {
16441644
/// When set to true, the physical optimizer may preserve native
1645-
/// dictionary encoding for eligible string GROUP BY columns. The
1646-
/// optimization only applies when file metadata proves that all data
1647-
/// pages are dictionary encoded and the decoded value bytes are large
1648-
/// enough relative to the stored Parquet column bytes.
1649-
pub enable_dictionary_aggregation: bool, default = false
1645+
/// dictionary encoding for eligible string columns through supported
1646+
/// operators. The optimization only applies when file metadata proves
1647+
/// that all data pages are dictionary encoded and the decoded value
1648+
/// bytes are large enough relative to the stored Parquet column bytes.
1649+
pub enable_dictionary_preservation: bool, default = false
16501650

16511651
/// When set to true, the optimizer will push a limit operation into
16521652
/// grouped aggregations which have no aggregate expressions, as a soft limit,

‎datafusion/common/src/stats.rs‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -383,6 +383,11 @@ pub struct Statistics {
383383
#[doc(hidden)]
384384
#[derive(Clone, Debug, PartialEq, Eq)]
385385
pub struct PhysicalFileStatistics {
386+
/// Exact number of rows described by the file footer.
387+
///
388+
/// `None` means the format did not provide a valid count or the count
389+
/// could not be represented by `usize`.
390+
pub num_rows: Option<usize>,
386391
/// One entry for each column in the file schema.
387392
pub column_statistics: Vec<PhysicalColumnStatistics>,
388393
}

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

Lines changed: 30 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -6,9 +6,8 @@ use std::fs::{File, create_dir_all};
66
use std::path::Path;
77
use std::sync::Arc;
88

9-
use arrow::array::{Array, ArrayRef, Int64Array, StringViewArray};
9+
use arrow::array::{Array, Int64Array, StringViewArray};
1010
use arrow::datatypes::{DataType, Field, Schema};
11-
use arrow::record_batch::RecordBatch;
1211
use datafusion::datasource::source::DataSourceExec;
1312
use datafusion::execution::runtime_env::RuntimeEnv;
1413
use datafusion::physical_plan::{ExecutionPlan, collect};
@@ -30,8 +29,8 @@ const VALUE: &str = "dictionary-value-dictionary-value";
3029
const OTHER_VALUE: &str = "second-dictionary-value-second-dictionary-value";
3130
const ROWS_PER_ROW_GROUP: usize = 150_000;
3231
const FILE_COUNT: usize = 2;
33-
const QUERY: &str = "SELECT t.key, COUNT(*) AS count FROM t JOIN dim ON t.bucket = dim.bucket \
34-
GROUP BY t.key ORDER BY t.key NULLS FIRST";
32+
const QUERY: &str =
33+
"SELECT key, COUNT(*) AS count FROM t GROUP BY key ORDER BY key NULLS FIRST";
3534
// Keep this independent from the optimizer implementation so a policy change
3635
// must update both the fixture and its asserted eligibility evidence.
3736
const MIN_VALUE_BYTES_PER_PARQUET_BYTE_FOR_TEST: usize = 4;
@@ -108,19 +107,14 @@ fn scan_has_physical_statistics(plan: &Arc<dyn ExecutionPlan>) -> Option<bool> {
108107
.find_map(scan_has_physical_statistics)
109108
}
110109

111-
async fn register_tables(ctx: &SessionContext, path: &Path) -> Result<()> {
110+
async fn register_table(ctx: &SessionContext, path: &Path) -> Result<()> {
112111
ctx.register_parquet(
113112
"t",
114113
path.to_str().expect("temporary path should be UTF-8"),
115114
ParquetReadOptions::default()
116115
.table_partition_cols(vec![("bucket".to_string(), DataType::Int64)]),
117116
)
118117
.await?;
119-
let batch = RecordBatch::try_from_iter([(
120-
"bucket",
121-
Arc::new(Int64Array::from(vec![1, 2])) as ArrayRef,
122-
)])?;
123-
ctx.register_batch("dim", batch)?;
124118
Ok(())
125119
}
126120

@@ -202,7 +196,7 @@ async fn preserves_native_dictionary_for_profitable_group_by() -> Result<()> {
202196
let runtime = Arc::new(RuntimeEnv::default());
203197
let baseline_ctx =
204198
SessionContext::new_with_config_rt(baseline_config, Arc::clone(&runtime));
205-
register_tables(&baseline_ctx, &table_path).await?;
199+
register_table(&baseline_ctx, &table_path).await?;
206200
let baseline_plan = baseline_ctx
207201
.sql(QUERY)
208202
.await?
@@ -226,13 +220,16 @@ async fn preserves_native_dictionary_for_profitable_group_by() -> Result<()> {
226220
);
227221

228222
let mut config = SessionConfig::new();
229-
config.options_mut().optimizer.enable_dictionary_aggregation = true;
223+
config
224+
.options_mut()
225+
.optimizer
226+
.enable_dictionary_preservation = true;
230227
config.options_mut().execution.target_partitions = FILE_COUNT;
231228
// Reuse the runtime so this request sees the file-statistics cache entry
232229
// populated above without physical encoding statistics. Enabling the rule
233230
// must backfill those statistics instead of treating the entry as complete.
234231
let ctx = SessionContext::new_with_config_rt(config, Arc::clone(&runtime));
235-
register_tables(&ctx, &table_path).await?;
232+
register_table(&ctx, &table_path).await?;
236233

237234
// Enabling the optimizer must not backfill physical metadata for scans
238235
// that project no Utf8View columns and therefore cannot be rewritten.
@@ -253,8 +250,8 @@ async fn preserves_native_dictionary_for_profitable_group_by() -> Result<()> {
253250
.all(|entry| entry.value.physical_statistics.is_none())
254251
);
255252

256-
// Data filters and scan limits make the dictionary rewrite ineligible, so
257-
// they must not backfill or attach its optional physical metadata.
253+
// Unsupported data filters and scan limits make the dictionary rewrite
254+
// ineligible, so they must not backfill or attach its optional metadata.
258255
for query in [
259256
"SELECT key, COUNT(*) FROM t WHERE key IS NOT NULL GROUP BY key",
260257
"SELECT key FROM t LIMIT 1",
@@ -273,6 +270,24 @@ async fn preserves_native_dictionary_for_profitable_group_by() -> Result<()> {
273270
.all(|entry| entry.value.physical_statistics.is_none())
274271
);
275272

273+
// An equality-filtered column can be profitable when filtering is its last
274+
// consumer, so the listing scan must request physical encoding metadata.
275+
// This fixture is deliberately below the filter workload threshold: it
276+
// verifies metadata reachability without changing the scan representation.
277+
let equality_filter_plan = ctx
278+
.sql(&format!("SELECT COUNT(*) FROM t WHERE key = '{VALUE}'"))
279+
.await?
280+
.create_physical_plan()
281+
.await?;
282+
assert_eq!(
283+
scan_has_physical_statistics(&equality_filter_plan),
284+
Some(true)
285+
);
286+
assert!(matches!(
287+
scan_details(&equality_filter_plan),
288+
Some((DataType::Utf8View, _))
289+
));
290+
276291
let dataframe = ctx.sql(QUERY).await?;
277292
let plan = dataframe.create_physical_plan().await?;
278293
let cached = statistics_cache.list_entries();

‎datafusion/datasource-parquet/src/metadata.rs‎

Lines changed: 13 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -150,7 +150,18 @@ pub(crate) fn physical_file_statistics(
150150
})
151151
.collect();
152152

153-
PhysicalFileStatistics { column_statistics }
153+
let num_rows = metadata
154+
.row_groups()
155+
.iter()
156+
.try_fold(0usize, |total, row_group| {
157+
let rows = usize::try_from(row_group.num_rows()).ok()?;
158+
total.checked_add(rows)
159+
});
160+
161+
PhysicalFileStatistics {
162+
num_rows,
163+
column_statistics,
164+
}
154165
}
155166

156167
fn requires_unsigned_byte_array_order(column: &ColumnDescriptor) -> bool {
@@ -1511,6 +1522,7 @@ mod tests {
15111522
assert_eq!(
15121523
physical_file_statistics(&metadata, &logical_schema),
15131524
PhysicalFileStatistics {
1525+
num_rows: Some(20),
15141526
column_statistics: vec![PhysicalColumnStatistics {
15151527
all_dictionary_encoded: true,
15161528
native_dictionary_value_type: Some(DataType::Utf8),

0 commit comments

Comments
 (0)