Skip to content

Commit a91d801

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 c792700 commit a91d801

10 files changed

Lines changed: 1248 additions & 120 deletions

File tree

‎datafusion/physical-expr-common/src/physical_expr.rs‎

Lines changed: 46 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -18,7 +18,7 @@
1818
use std::any::Any;
1919
use std::fmt;
2020
use std::fmt::{Debug, Display, Formatter};
21-
use std::hash::{Hash, Hasher};
21+
use std::hash::{DefaultHasher, Hash, Hasher};
2222
use std::sync::Arc;
2323

2424
use crate::utils::scatter;
@@ -441,6 +441,51 @@ pub trait PhysicalExpr: Any + Send + Sync + Display + Debug + DynEq + DynHash {
441441
fn placement(&self) -> ExpressionPlacement {
442442
ExpressionPlacement::KeepInPlace
443443
}
444+
445+
/// Returns a composite identifier for a [`PhysicalExpr`]. Note that if the expression
446+
/// is dropped, then the returned id may no longer be valid and other ids may collide
447+
/// with it.
448+
fn expr_id(self: Arc<Self>, salt: &[u64]) -> Option<PhysicalExprId> {
449+
Some(PhysicalExprId::new(expr_id_from_arc(&self, salt), None))
450+
}
451+
}
452+
453+
/// A composite identifier for [`PhysicalExpr`].
454+
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
455+
pub struct PhysicalExprId {
456+
exact: u64,
457+
shallow: Option<u64>,
458+
}
459+
460+
impl PhysicalExprId {
461+
/// Create a new [`PhysicalExprId`]. Both ids must be globally unique within
462+
/// a process.
463+
pub fn new(exact: u64, shallow: Option<u64>) -> Self {
464+
Self { exact, shallow }
465+
}
466+
467+
/// Returns the identifier for the full expression tree, including children.
468+
pub fn exact(&self) -> u64 {
469+
self.exact
470+
}
471+
472+
/// Returns the identifier for just the expression root, ignoring children.
473+
pub fn shallow(&self) -> Option<u64> {
474+
self.shallow
475+
}
476+
}
477+
478+
/// Computes a unique identifier for a type contained within an [`Arc`]. It hashes
479+
/// the [`Arc`] pointer to create a process-local identifier that remains valid
480+
/// only while that allocation is still alive.
481+
pub fn expr_id_from_arc<T: ?Sized>(expr: &Arc<T>, salt: &[u64]) -> u64 {
482+
let mut hasher = DefaultHasher::new();
483+
let ptr = Arc::as_ptr(expr) as *const () as u64;
484+
ptr.hash(&mut hasher);
485+
for &salt in salt {
486+
salt.hash(&mut hasher);
487+
}
488+
hasher.finish()
444489
}
445490

446491
#[deprecated(

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

Lines changed: 244 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -26,7 +26,9 @@ use datafusion_common::{
2626
tree_node::{Transformed, TransformedResult, TreeNode},
2727
};
2828
use datafusion_expr::ColumnarValue;
29-
use datafusion_physical_expr_common::physical_expr::DynHash;
29+
use datafusion_physical_expr_common::physical_expr::{
30+
DynHash, PhysicalExprId, expr_id_from_arc,
31+
};
3032

3133
/// State of a dynamic filter, tracking both updates and completion.
3234
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
@@ -88,6 +90,116 @@ struct Inner {
8890
is_complete: bool,
8991
}
9092

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

183295
fn remap_children(
184-
children: &[Arc<dyn PhysicalExpr>],
185-
remapped_children: Option<&Vec<Arc<dyn PhysicalExpr>>>,
296+
&self,
186297
expr: Arc<dyn PhysicalExpr>,
187298
) -> Result<Arc<dyn PhysicalExpr>> {
188-
if let Some(remapped_children) = remapped_children {
299+
if let Some(remapped_children) = &self.remapped_children {
189300
// Remap the children to the new children
190301
// of the expression.
191302
expr.transform_up(|child| {
192303
// 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())
304+
if let Some(pos) = self
305+
.children
306+
.iter()
307+
.position(|c| c.as_ref() == child.as_ref())
195308
{
196309
// If so, remap it to the current children
197310
// of the expression.
@@ -219,7 +332,7 @@ impl DynamicFilterPhysicalExpr {
219332
/// remapped to match calls to [`PhysicalExpr::with_new_children`].
220333
pub fn current(&self) -> Result<Arc<dyn PhysicalExpr>> {
221334
let expr = Arc::clone(self.inner.read().expr());
222-
Self::remap_children(&self.children, self.remapped_children.as_ref(), expr)
335+
self.remap_children(expr)
223336
}
224337

225338
/// Update the current expression and notify all waiters.
@@ -233,11 +346,7 @@ impl DynamicFilterPhysicalExpr {
233346
// We still do this again in `current()` but doing it preventively here
234347
// reduces the work needed in some cases if `current()` is called multiple times
235348
// 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-
)?;
349+
let new_expr = self.remap_children(new_expr)?;
241350

242351
// Load the current inner, increment generation, and store the new one
243352
let mut current = self.inner.write();
@@ -448,6 +557,13 @@ impl PhysicalExpr for DynamicFilterPhysicalExpr {
448557
// Return the current generation of the expression.
449558
self.inner.read().generation
450559
}
560+
561+
fn expr_id(self: Arc<Self>, salt: &[u64]) -> Option<PhysicalExprId> {
562+
Some(PhysicalExprId::new(
563+
expr_id_from_arc(&self, salt),
564+
Some(expr_id_from_arc(&self.inner, salt)),
565+
))
566+
}
451567
}
452568

453569
#[cfg(test)]
@@ -867,4 +983,120 @@ mod test {
867983
"Hash should be stable after update (identity-based)"
868984
);
869985
}
986+
987+
#[test]
988+
fn test_current_snapshot_roundtrip() {
989+
let schema = Arc::new(Schema::new(vec![Field::new("a", DataType::Int32, false)]));
990+
let col_a = col("a", &schema).unwrap();
991+
992+
// Create a dynamic filter with children
993+
let expr = Arc::new(BinaryExpr::new(
994+
Arc::clone(&col_a),
995+
datafusion_expr::Operator::Gt,
996+
lit(10) as Arc<dyn PhysicalExpr>,
997+
));
998+
let filter = DynamicFilterPhysicalExpr::new(
999+
vec![Arc::clone(&col_a)],
1000+
expr as Arc<dyn PhysicalExpr>,
1001+
);
1002+
1003+
// Update expression and mark complete
1004+
filter
1005+
.update(lit(42) as Arc<dyn PhysicalExpr>)
1006+
.expect("Update should succeed");
1007+
filter.mark_complete();
1008+
1009+
// Take a snapshot and reconstruct
1010+
let snapshot = DynamicFilterSnapshot::from(&filter);
1011+
let reconstructed = DynamicFilterPhysicalExpr::from(snapshot);
1012+
1013+
// String representations should be equal
1014+
assert_eq!(
1015+
DynamicFilterSnapshot::from(&filter).to_string(),
1016+
DynamicFilterSnapshot::from(&reconstructed).to_string(),
1017+
);
1018+
}
1019+
1020+
#[tokio::test]
1021+
async fn test_with_new_children_preserves_shared_inner_state() {
1022+
// Create a source filter
1023+
let source = Arc::new(DynamicFilterPhysicalExpr::new(
1024+
vec![],
1025+
lit(42) as Arc<dyn PhysicalExpr>,
1026+
));
1027+
1028+
// Create a target filter with different children
1029+
let schema = Arc::new(Schema::new(vec![Field::new("x", DataType::Int32, false)]));
1030+
let col_x = col("x", &schema).unwrap();
1031+
// Rebuild a wrapper from the source filter using the target's children.
1032+
let combined = Arc::clone(&source)
1033+
.with_new_children(vec![Arc::clone(&col_x)])
1034+
.unwrap();
1035+
1036+
let combined_expr_id = Arc::clone(&combined)
1037+
.expr_id(&[])
1038+
.expect("combined filter should have an expr_id");
1039+
let source_expr_id = Arc::clone(&source)
1040+
.expr_id(&[])
1041+
.expect("source filter should have an expr_id");
1042+
assert_ne!(
1043+
combined_expr_id.exact(),
1044+
source_expr_id.exact(),
1045+
"with_new_children should produce a distinct outer Arc identity",
1046+
);
1047+
assert_eq!(
1048+
combined_expr_id.shallow(),
1049+
source_expr_id.shallow(),
1050+
"dynamic filters with shared inner state should have the same shallow identity",
1051+
);
1052+
1053+
let combined_dyn_filter = combined
1054+
.as_any()
1055+
.downcast_ref::<DynamicFilterPhysicalExpr>()
1056+
.unwrap();
1057+
1058+
// Verify the children are unchanged.
1059+
assert_eq!(
1060+
format!("{:?}", combined.children()),
1061+
format!("{:?}", vec![col_x]),
1062+
"Combined filter's children should be unchanged"
1063+
);
1064+
1065+
// Verify inner expression changed to the one from source.
1066+
assert_eq!(
1067+
format!("{:?}", combined_dyn_filter.current().unwrap()),
1068+
format!("{:?}", lit(42)),
1069+
"Combined filter should have inner expression from source filter"
1070+
);
1071+
1072+
// Verify that completing one filter also completes the other.
1073+
let combined_binding = Arc::clone(&combined) as Arc<dyn PhysicalExpr>;
1074+
#[expect(clippy::disallowed_methods)]
1075+
let wait_handle = tokio::task::spawn({
1076+
async move {
1077+
let df = combined_binding
1078+
.as_any()
1079+
.downcast_ref::<DynamicFilterPhysicalExpr>()
1080+
.unwrap();
1081+
df.wait_complete().await;
1082+
format!("{:?}", df.current().unwrap())
1083+
}
1084+
});
1085+
source.update(lit(999) as Arc<dyn PhysicalExpr>).unwrap();
1086+
source.mark_complete();
1087+
1088+
// The linked filter should be notified via the shared watch
1089+
let result = tokio::time::timeout(std::time::Duration::from_secs(1), wait_handle)
1090+
.await
1091+
.expect(
1092+
"linked filter should have been notified of completion within timeout",
1093+
)
1094+
.expect("task should not panic");
1095+
1096+
assert_eq!(
1097+
result,
1098+
format!("{:?}", lit(999)),
1099+
"linked filter should see source's updated inner expression"
1100+
);
1101+
}
8701102
}

‎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};

0 commit comments

Comments
 (0)