Skip to content

Commit fef4259

Browse files
proto: serialize and dedupe dynamic filters
Informs: datafusion-contrib/datafusion-distributed#180 Closes: apache#20418 Consider this scenario 1. You have a plan with a `HashJoinExec` and `DataSourceExec` 2. You run the physical optimizer and the `DataSourceExec` accepts `DynamicFilterPhysicalExpr` pushdown from the `HashJoinExec` 3. You serialize the plan, deserialize it, and execute it What should happen is that the dynamic filter should "work", meaning 1. When you deserialize the plan, both the `HashJoinExec` and `DataSourceExec` should have pointers to the same `DynamicFilterPhysicalExpr` 2. The `DynamicFilterPhysicalExpr` should be updated during execution by the `HashJoinExec` and the `DataSourceExec` should filter out rows This does not happen today for a few reasons, a couple of which this PR aims to address 1. `DynamicFilterPhysicalExpr` is not survive round-tripping. The internal exprs get inlined (ex. it may be serialized as `Literal`) 2. Even if `DynamicFilterPhysicalExpr` survives round-tripping, during pushdown, it's often the case that the `DynamicFilterPhysicalExpr` is rewritten. In this case, you have two `DynamicFilterPhysicalExpr` which are different `Arc`s but share the same `Inner` dynamic filter state. The current `DeduplicatingProtoConverter` does not handle this specific form of deduping. This PR aims to fix those problems by adding serde for `DynamicFilterPhysicalExpr` and deduping logic for the inner state of dynamic filters. It does not yet add a test for the `HashJoinExec` and `DataSourceExec` filter pushdown case, but this is relevant follow up work. I tried to keep the PR small for reviewers. Yes, via unit tests. `DynamicFilterPhysicalExpr` are now serialized by the default codec
1 parent 0022d8e commit fef4259

9 files changed

Lines changed: 949 additions & 42 deletions

File tree

‎datafusion/physical-expr/src/expressions/dynamic_filters.rs‎

Lines changed: 245 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ use tokio::sync::watch;
2222
use crate::PhysicalExpr;
2323
use arrow::datatypes::{DataType, Schema};
2424
use datafusion_common::{
25-
Result,
25+
Result, internal_err,
2626
tree_node::{Transformed, TransformedResult, TreeNode},
2727
};
2828
use datafusion_expr::ColumnarValue;
@@ -88,6 +88,117 @@ struct Inner {
8888
is_complete: bool,
8989
}
9090

91+
/// An atomic snapshot of a [`DynamicFilterPhysicalExpr`] used to reconstruct the expression during
92+
/// serialization / deserialization.
93+
pub struct DynamicFilterSnapshot {
94+
children: Vec<Arc<dyn PhysicalExpr>>,
95+
remapped_children: Option<Vec<Arc<dyn PhysicalExpr>>>,
96+
// Inner state.
97+
generation: u64,
98+
inner_expr: Arc<dyn PhysicalExpr>,
99+
is_complete: bool,
100+
}
101+
102+
impl DynamicFilterSnapshot {
103+
pub fn new(
104+
children: Vec<Arc<dyn PhysicalExpr>>,
105+
remapped_children: Option<Vec<Arc<dyn PhysicalExpr>>>,
106+
generation: u64,
107+
inner_expr: Arc<dyn PhysicalExpr>,
108+
is_complete: bool,
109+
) -> Self {
110+
Self {
111+
children,
112+
remapped_children,
113+
generation,
114+
inner_expr,
115+
is_complete,
116+
}
117+
}
118+
119+
pub fn children(&self) -> &[Arc<dyn PhysicalExpr>] {
120+
&self.children
121+
}
122+
123+
pub fn remapped_children(&self) -> Option<&[Arc<dyn PhysicalExpr>]> {
124+
self.remapped_children.as_deref()
125+
}
126+
127+
pub fn generation(&self) -> u64 {
128+
self.generation
129+
}
130+
131+
pub fn inner_expr(&self) -> &Arc<dyn PhysicalExpr> {
132+
&self.inner_expr
133+
}
134+
135+
pub fn is_complete(&self) -> bool {
136+
self.is_complete
137+
}
138+
}
139+
140+
impl Display for DynamicFilterSnapshot {
141+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
142+
write!(
143+
f,
144+
"DynamicFilterSnapshot {{ children: {:?}, remapped_children: {:?}, generation: {}, inner_expr: {:?}, is_complete: {} }}",
145+
self.children,
146+
self.remapped_children,
147+
self.generation,
148+
self.inner_expr,
149+
self.is_complete
150+
)
151+
}
152+
}
153+
154+
impl From<DynamicFilterSnapshot> for DynamicFilterPhysicalExpr {
155+
fn from(snapshot: DynamicFilterSnapshot) -> Self {
156+
let DynamicFilterSnapshot {
157+
children,
158+
remapped_children,
159+
generation,
160+
inner_expr,
161+
is_complete,
162+
} = snapshot;
163+
164+
let state = if is_complete {
165+
FilterState::Complete { generation }
166+
} else {
167+
FilterState::InProgress { generation }
168+
};
169+
let (state_watch, _) = watch::channel(state);
170+
171+
Self {
172+
children,
173+
remapped_children,
174+
inner: Arc::new(RwLock::new(Inner {
175+
generation,
176+
expr: inner_expr,
177+
is_complete,
178+
})),
179+
state_watch,
180+
data_type: Arc::new(RwLock::new(None)),
181+
nullable: Arc::new(RwLock::new(None)),
182+
}
183+
}
184+
}
185+
186+
impl From<&DynamicFilterPhysicalExpr> for DynamicFilterSnapshot {
187+
fn from(expr: &DynamicFilterPhysicalExpr) -> Self {
188+
let (generation, inner_expr, is_complete) = {
189+
let inner = expr.inner.read();
190+
(inner.generation, Arc::clone(&inner.expr), inner.is_complete)
191+
};
192+
DynamicFilterSnapshot {
193+
children: expr.children.clone(),
194+
remapped_children: expr.remapped_children.clone(),
195+
generation,
196+
inner_expr,
197+
is_complete,
198+
}
199+
}
200+
}
201+
91202
impl Inner {
92203
fn new(expr: Arc<dyn PhysicalExpr>) -> Self {
93204
Self {
@@ -180,18 +291,52 @@ impl DynamicFilterPhysicalExpr {
180291
}
181292
}
182293

294+
/// Create a new [`DynamicFilterPhysicalExpr`] from `self`, except it overwrites the
295+
/// internal state with the source filter's state.
296+
///
297+
/// This is a low-level API intended for use by the proto deserialization layer.
298+
///
299+
/// # Safety
300+
///
301+
/// The dynamic filter should not be in use when calling this method, otherwise there
302+
/// may be undefined behavior. Changing the inner state of a filter may do the following:
303+
/// - transition the state to complete without notifying the watch
304+
/// - cause a generation number to be emitted which is out of order
305+
pub fn new_from_source(
306+
self: &Arc<Self>,
307+
source: &DynamicFilterPhysicalExpr,
308+
) -> Result<Self> {
309+
// If there's any references to this filter or any watchers, we should not replace the
310+
// inner state.
311+
if self.is_used() {
312+
return internal_err!(
313+
"Cannot replace the inner state of a DynamicFilterPhysicalExpr that is in use"
314+
);
315+
};
316+
317+
Ok(Self {
318+
children: self.children.clone(),
319+
remapped_children: self.remapped_children.clone(),
320+
inner: Arc::clone(&source.inner),
321+
state_watch: self.state_watch.clone(),
322+
data_type: Arc::clone(&self.data_type),
323+
nullable: Arc::clone(&self.nullable),
324+
})
325+
}
326+
183327
fn remap_children(
184-
children: &[Arc<dyn PhysicalExpr>],
185-
remapped_children: Option<&Vec<Arc<dyn PhysicalExpr>>>,
328+
&self,
186329
expr: Arc<dyn PhysicalExpr>,
187330
) -> Result<Arc<dyn PhysicalExpr>> {
188-
if let Some(remapped_children) = remapped_children {
331+
if let Some(remapped_children) = &self.remapped_children {
189332
// Remap the children to the new children
190333
// of the expression.
191334
expr.transform_up(|child| {
192335
// Check if this is any of our original children
193-
if let Some(pos) =
194-
children.iter().position(|c| c.as_ref() == child.as_ref())
336+
if let Some(pos) = self
337+
.children
338+
.iter()
339+
.position(|c| c.as_ref() == child.as_ref())
195340
{
196341
// If so, remap it to the current children
197342
// of the expression.
@@ -219,7 +364,7 @@ impl DynamicFilterPhysicalExpr {
219364
/// remapped to match calls to [`PhysicalExpr::with_new_children`].
220365
pub fn current(&self) -> Result<Arc<dyn PhysicalExpr>> {
221366
let expr = Arc::clone(self.inner.read().expr());
222-
Self::remap_children(&self.children, self.remapped_children.as_ref(), expr)
367+
self.remap_children(expr)
223368
}
224369

225370
/// Update the current expression and notify all waiters.
@@ -233,11 +378,7 @@ impl DynamicFilterPhysicalExpr {
233378
// We still do this again in `current()` but doing it preventively here
234379
// reduces the work needed in some cases if `current()` is called multiple times
235380
// and the same externally facing `PhysicalExpr` is used for both `with_new_children` and `update()`.`
236-
let new_expr = Self::remap_children(
237-
&self.children,
238-
self.remapped_children.as_ref(),
239-
new_expr,
240-
)?;
381+
let new_expr = self.remap_children(new_expr)?;
241382

242383
// Load the current inner, increment generation, and store the new one
243384
let mut current = self.inner.write();
@@ -327,6 +468,14 @@ impl DynamicFilterPhysicalExpr {
327468
Arc::strong_count(self) > 1 || Arc::strong_count(&self.inner) > 1
328469
}
329470

471+
/// Returns a unique identifier for the inner shared state.
472+
///
473+
/// Useful for checking if two [`Arc<PhysicalExpr>`] with the same
474+
/// underlying [`DynamicFilterPhysicalExpr`] are the same.
475+
pub fn inner_id(&self) -> u64 {
476+
Arc::as_ptr(&self.inner) as *const () as u64
477+
}
478+
330479
fn render(
331480
&self,
332481
f: &mut std::fmt::Formatter<'_>,
@@ -867,4 +1016,88 @@ mod test {
8671016
"Hash should be stable after update (identity-based)"
8681017
);
8691018
}
1019+
1020+
#[test]
1021+
fn test_current_snapshot_roundtrip() {
1022+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
1023+
let col_a = col("a", &schema).unwrap();
1024+
1025+
// Create a dynamic filter with children
1026+
let expr = Arc::new(BinaryExpr::new(
1027+
Arc::clone(&col_a),
1028+
datafusion_expr::Operator::Gt,
1029+
lit(10) as Arc<dyn PhysicalExpr>,
1030+
));
1031+
let filter = DynamicFilterPhysicalExpr::new(
1032+
vec![Arc::clone(&col_a)],
1033+
expr as Arc<dyn PhysicalExpr>,
1034+
);
1035+
1036+
// Update expression and mark complete
1037+
filter
1038+
.update(lit(42) as Arc<dyn PhysicalExpr>)
1039+
.expect("Update should succeed");
1040+
filter.mark_complete();
1041+
1042+
// Take a snapshot and reconstruct
1043+
let snapshot = DynamicFilterSnapshot::from(&filter);
1044+
let reconstructed = DynamicFilterPhysicalExpr::from(snapshot);
1045+
1046+
// String representations should be equal
1047+
assert_eq!(
1048+
DynamicFilterSnapshot::from(&filter).to_string(),
1049+
DynamicFilterSnapshot::from(&reconstructed).to_string(),
1050+
);
1051+
}
1052+
1053+
#[test]
1054+
fn test_new_from_source() {
1055+
// Create a source filter
1056+
let source = Arc::new(DynamicFilterPhysicalExpr::new(
1057+
vec![],
1058+
lit(42) as Arc<dyn PhysicalExpr>,
1059+
));
1060+
1061+
// Update and mark complete
1062+
source.update(lit(100) as Arc<dyn PhysicalExpr>).unwrap();
1063+
source.mark_complete();
1064+
1065+
// Create a target filter with different children
1066+
let schema = Arc::new(Schema::new(vec![Field::new("x", DataType::Int32, false)]));
1067+
let col_x = col("x", &schema).unwrap();
1068+
let target = Arc::new(DynamicFilterPhysicalExpr::new(
1069+
vec![Arc::clone(&col_x)],
1070+
lit(0) as Arc<dyn PhysicalExpr>,
1071+
));
1072+
1073+
// Create new filter from source's inner state
1074+
let combined = target.new_from_source(&source).unwrap();
1075+
1076+
// Verify inner state is shared (same inner_id)
1077+
assert_eq!(
1078+
combined.inner_id(),
1079+
source.inner_id(),
1080+
"new_from_source should share inner state with source"
1081+
);
1082+
1083+
// Verify children are from target, not source
1084+
let combined_snapshot = DynamicFilterSnapshot::from(&combined);
1085+
assert_eq!(
1086+
combined_snapshot.children().len(),
1087+
1,
1088+
"Combined filter should have target's children"
1089+
);
1090+
assert_eq!(
1091+
format!("{:?}", combined_snapshot.children()[0]),
1092+
format!("{:?}", col_x),
1093+
"Combined filter should have target's children"
1094+
);
1095+
1096+
// Verify inner expression comes from source
1097+
assert_eq!(
1098+
format!("{:?}", combined_snapshot.inner_expr()),
1099+
format!("{:?}", lit(100)),
1100+
"Combined filter should have source's inner expression"
1101+
);
1102+
}
8701103
}

‎datafusion/physical-expr/src/expressions/mod.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ pub use cast::{CastExpr, cast};
4545
pub use cast_column::CastColumnExpr;
4646
pub use column::{Column, col, with_new_schema};
4747
pub use datafusion_expr::utils::format_state_name;
48-
pub use dynamic_filters::DynamicFilterPhysicalExpr;
48+
pub use dynamic_filters::{DynamicFilterPhysicalExpr, DynamicFilterSnapshot};
4949
pub use in_list::{InListExpr, in_list};
5050
pub use is_not_null::{IsNotNullExpr, is_not_null};
5151
pub use is_null::{IsNullExpr, is_null};

‎datafusion/proto/proto/datafusion.proto‎

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -860,6 +860,12 @@ message PhysicalExprNode {
860860
// across serde roundtrips.
861861
optional uint64 expr_id = 30;
862862

863+
// For DynamicFilterPhysicalExpr, this identifies the shared inner state.
864+
// Multiple expressions may have different expr_id values (different outer Arc wrappers)
865+
// but the same dynamic_filter_inner_id (shared inner state).
866+
// Used to reconstruct shared inner state during deserialization.
867+
optional uint64 dynamic_filter_inner_id = 31;
868+
863869
oneof ExprType {
864870
// column references
865871
PhysicalColumn column = 1;
@@ -897,9 +903,19 @@ message PhysicalExprNode {
897903
UnknownColumn unknown_column = 20;
898904

899905
PhysicalHashExprNode hash_expr = 21;
906+
907+
PhysicalDynamicFilterNode dynamic_filter = 22;
900908
}
901909
}
902910

911+
message PhysicalDynamicFilterNode {
912+
repeated PhysicalExprNode children = 1;
913+
repeated PhysicalExprNode remapped_children = 2;
914+
uint64 generation = 3;
915+
PhysicalExprNode inner_expr = 4;
916+
bool is_complete = 5;
917+
}
918+
903919
message PhysicalScalarUdfNode {
904920
string name = 1;
905921
repeated PhysicalExprNode args = 2;

0 commit comments

Comments
 (0)