Skip to content

Commit fdb5ed4

Browse files
alxmrsclaude
andauthored
Detect fold pipelines in DataFusion's plans: demo 1's attention (#72)
🪭 Claude (einfold) Fourth of M2's stack, on #70's `PipelineNode`. `DetectFolds` now finds demo 1's causal attention, written in plain SQL, in DataFusion's optimized plans, and replaces it with a `PipelineNode`, keeping the plan it replaced as the fallback. That makes demo 1's "found, not told" criterion testable. The rule mentions no attention-specific operator. It matches the parts of a softmax-weighted average of a fold's results (`detect_pipelines.rs`): - **the scores:** a fold, as the rule's first shape, under a projection of its group keys and its sum, scaled by `* c`, `/ c`, or neither. Its join may carry **conditions** comparing two of its group keys, such as `q.t >= k.t`, which become the fold's mask (#59). Any other join condition declines; - **the weights:** `exp(s - m)`, with `m` the largest score per kept key, in either spelling: - a window, `MAX(s) OVER (PARTITION BY i)`, over the whole partition, with no `ORDER BY` or filter; - `MAX(s) … GROUP BY i` joined back on `i`, which is ddx's spelling. Or `exp(s)`, with no shift; - **the average:** `SUM(w * v.x)`, grouped by the kept key and the values' other columns, over the weights joined with a values relation on the summed key, divided by either: - `norm.z`: the same weights summed per kept key, joined on it and grouped by too. This is demo 1's spelling, and `Normalizer::KeptGroups`; - `SUM(w)` in the same aggregate: `Normalizer::JoinedRows`, as a kernel smoother or recommender writes it. **What must hold, or it declines:** - DataFusion copies each CTE into every place it's read, so the scores and weights appear two to four times. Every copy must be the same fold, with the same scale and shift. Otherwise the shift wouldn't cancel between the numerator and the normalizer. - The maximum must be taken per the kept key, not the summed one. - The joins must be plain inner equi-joins on `=`. **Order.** Pipelines are found from the top down, before folds: a pipeline's scores are themselves a fold, which the rule's bottom-up pass would replace first. `DetectFolds::detect` runs both passes, and `EinFoldQueryPlanner` calls it. As an `OptimizerRule`, `DetectFolds` still finds folds only. **Refactor.** Fold analysis (`analyze`) is split out of the first shape, so pipelines can reuse it, and so it can take a join's comparisons as conditions. A fold with conditions on its own is still left alone, since the fold kernels don't compute masks yet. **Invariants** (`tests/detect_pipelines.rs`, 1,500 cases searched), for random `q`, `k`, `v`, complete or with a hole, and queries drawn from: - both spellings; - three scales; - four masks: either way round, strict or not, or none; - the `SUM(w) / SUM(w)` form with no shift; - five look-alikes: a maximum partitioned by the summed key; one with `ORDER BY`; a normalizer of `exp(2w)`; a normalizer of weights over the same fold scaled differently; and an unmasked fold, which the M1 tests already cover. The invariants: 1. The same rows as DataFusion, values within `1e-9`. 2. A pipeline found exactly when the query is one. 3. The fused algorithm run whenever the tables are complete. The first draft accepted a maximum partitioned by the summed key, which the look-alikes caught. A mutant that skips the normalizer's same-scores check survived until the different-scale look-alike went in. One mutant is equivalent: a scores relation's only bare `DOUBLE` column is the score. `detect_vs_host.rs` still passes. **Not yet.** One spelling waits for a later PR: a projection that reads `norm.z`. ddx's attention program, which normalizes inside the sum, is this PR's second commit (#76). The Gaussian-kernel average, whose producer isn't a sum of products, is #99 to #102, which add row expressions. **Size.** About 810 lines that aren't tests, 620 of them the new matcher. It is one rule: each part (scores, weights, maximum, normalizer, consumer) is checked against the others, so splitting it would leave pieces that can't be tested on their own. <!-- - [x] cargo fmt / clippy -D warnings / test / doc -D warnings / reuse lint --> It also finds attention normalized inside the sum, `SUM(w / norm.z * v.x)`, the spelling ddx (an XQL Systems project for differentiating SQL queries) can differentiate, since it groups by no key that depends on a differentiated column. Fixes #76. ## After CodeRabbit's review - **Detection declines three more look-alikes:** a projection with two score columns, one that shows a group key twice (and so hides another), and a join of the scores to their maximum that matches NULL keys. - **The property test damages its tables in more ways.** One of `q`, `k` and `v` sometimes has a row missing or repeated, a NULL value, a NaN or infinite value, a NULL key, or no rows at all. With NaN and infinite values the tables are still complete, so the fused algorithm must still run and agree. 1,500 cases pass. 🤖 Generated with [Claude Code](https://claude.com/claude-code) https://claude.ai/code/session_01M96xSez6PZwTmfaGh2eJgS --------- Co-authored-by: Claude Opus 5.5 <[email protected]>
1 parent 7ac28a8 commit fdb5ed4

5 files changed

Lines changed: 1268 additions & 31 deletions

File tree

‎crates/einfold-datafusion/src/detect_folds.rs‎

Lines changed: 131 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -49,10 +49,11 @@ use datafusion::logical_expr::{
4949
};
5050
use datafusion::optimizer::{ApplyOrder, OptimizerConfig, OptimizerRule};
5151
use einfold_ir::{
52-
Aggregate as FoldAggregate, ColumnIndex, Dimension, DimensionId, Domain, DomainKey, Fold, Key,
53-
KeyEquality, Operand, Output, RowValue,
52+
Aggregate as FoldAggregate, ColumnIndex, Comparison, Condition, Dimension, DimensionId, Domain,
53+
DomainKey, Fold, Key, KeyEquality, Operand, Output, RowValue,
5454
};
5555

56+
use crate::detect_pipelines;
5657
use crate::fold_node::FoldNode;
5758
use crate::join_back;
5859

@@ -99,6 +100,32 @@ impl DetectFolds {
99100
}
100101
}
101102

103+
impl DetectFolds {
104+
/// `plan` with every fold pipeline and fold this rule finds replaced by
105+
/// its node. Pipelines are found first, from the top down, since a
106+
/// pipeline's producer is itself a fold, which the rule's bottom-up pass
107+
/// would otherwise replace first. As an optimizer rule, [`DetectFolds`]
108+
/// finds folds only.
109+
pub fn detect(&self, plan: LogicalPlan) -> Result<LogicalPlan> {
110+
use datafusion::common::tree_node::TreeNode;
111+
use datafusion::optimizer::OptimizerContext;
112+
let plan = plan
113+
.transform_down(|node| {
114+
let found = match &node {
115+
LogicalPlan::Projection(p) => detect_pipelines::pipeline(p)?,
116+
_ => None,
117+
};
118+
Ok(match found {
119+
Some(rewritten) => Transformed::yes(rewritten),
120+
None => Transformed::no(node),
121+
})
122+
})?
123+
.data;
124+
let config = OptimizerContext::new();
125+
Ok(plan.transform_up(|node| self.rewrite(node, &config))?.data)
126+
}
127+
}
128+
102129
impl OptimizerRule for DetectFolds {
103130
fn name(&self) -> &str {
104131
"detect_folds"
@@ -253,9 +280,15 @@ fn widens(from: &DataType, to: &DataType) -> bool {
253280

254281
/// The sum's argument, if `agg` computes exactly one plain `SUM`.
255282
pub(crate) fn sum_argument(agg: &Aggregate) -> Option<Expr> {
256-
let [aggregate] = agg.aggr_expr.as_slice() else {
257-
return None;
258-
};
283+
match agg.aggr_expr.len() {
284+
1 => sum_argument_at(agg, 0),
285+
_ => None,
286+
}
287+
}
288+
289+
/// The argument of `agg`'s aggregate `a`, if it is a plain `SUM`.
290+
pub(crate) fn sum_argument_at(agg: &Aggregate, a: usize) -> Option<Expr> {
291+
let aggregate = agg.aggr_expr.get(a)?;
259292
let Expr::AggregateFunction(f) = aggregate.clone().unalias() else {
260293
return None;
261294
};
@@ -267,9 +300,49 @@ pub(crate) fn sum_argument(agg: &Aggregate) -> Option<Expr> {
267300
(function.is::<Sum>() && plain).then(|| p.args[0].clone())
268301
}
269302

303+
/// A fold found in an aggregate: its description, and its operands' plans.
304+
pub(crate) struct Found {
305+
pub(crate) fold: Fold,
306+
pub(crate) operands: Vec<LogicalPlan>,
307+
}
308+
270309
/// `agg` as a fold, if it is one: a [`FoldNode`] under a projection giving it
271-
/// `agg`'s schema.
310+
/// `agg`'s schema. A fold whose join has a condition, a mask, is left alone:
311+
/// the fold kernels don't compute masks yet.
272312
fn fold(agg: &Aggregate, fallback: Fallback) -> Result<Option<LogicalPlan>> {
313+
let Some(Found {
314+
fold: spec,
315+
operands: plans,
316+
}) = analyze(agg)?
317+
else {
318+
return Ok(None);
319+
};
320+
if !spec.conditions().is_empty() {
321+
return Ok(None);
322+
}
323+
let original = LogicalPlan::Aggregate(agg.clone());
324+
let names: Vec<String> = (0..agg.group_expr.len())
325+
.map(|i| format!("{PREFIX}o{i}"))
326+
.chain([format!("{PREFIX}v")])
327+
.collect();
328+
let Ok(node) = FoldNode::try_new(spec, plans, None, names.clone()) else {
329+
return Ok(None);
330+
};
331+
let node = match fallback {
332+
Fallback::HostPlan => node.with_fallback(original),
333+
Fallback::Kernels => node.marked_found(),
334+
}
335+
.into_plan();
336+
// Give the node the aggregate's schema: its names, qualifiers, types
337+
// and nullability.
338+
restore(node, &names, &agg.schema)
339+
}
340+
341+
/// `agg` as a fold, if it is one: a `SUM` of a product of one factor from
342+
/// each side of an inner equi-join, grouped by columns, through projections.
343+
/// A condition of the join that compares two of the fold's dimensions, such
344+
/// as `q.t >= k.t`, becomes one of the fold's conditions; any other declines.
345+
pub(crate) fn analyze(agg: &Aggregate) -> Result<Option<Found>> {
273346
use datafusion::logical_expr::ExprSchemable;
274347
let Some(arg) = sum_argument(agg) else {
275348
return Ok(None);
@@ -291,7 +364,7 @@ fn fold(agg: &Aggregate, fallback: Fallback) -> Result<Option<LogicalPlan>> {
291364
_ => return Ok(None),
292365
}
293366
};
294-
if join.join_type != JoinType::Inner || join.filter.is_some() || join.on.is_empty() {
367+
if join.join_type != JoinType::Inner || join.on.is_empty() {
295368
return Ok(None);
296369
}
297370
let inputs = [join.left.schema().as_ref(), join.right.schema().as_ref()];
@@ -374,6 +447,16 @@ fn fold(agg: &Aggregate, fallback: Fallback) -> Result<Option<LogicalPlan>> {
374447
domain_key: None,
375448
});
376449
}
450+
// The join's condition: comparisons between two of the dimensions.
451+
let mut conditions = Vec::new();
452+
if let Some(filter) = &join.filter {
453+
for c in datafusion::logical_expr::utils::split_conjunction(filter) {
454+
let Some(condition) = comparison(c, &columns, &keys, inputs) else {
455+
return Ok(None);
456+
};
457+
conditions.push(condition);
458+
}
459+
}
377460
let mut operands = Vec::new();
378461
for (s, (input, factor)) in [(&join.left, lf), (&join.right, rf)]
379462
.into_iter()
@@ -393,33 +476,58 @@ fn fold(agg: &Aggregate, fallback: Fallback) -> Result<Option<LogicalPlan>> {
393476
LogicalPlan::Projection(Projection::try_new(exprs, Arc::clone(input))?),
394477
));
395478
}
479+
let operand_specs = operands.iter().map(|(o, _)| o.clone()).collect();
396480
let Ok(spec) = Fold::try_new(
397481
dimensions,
398-
operands.iter().map(|(o, _)| o.clone()).collect(),
482+
operand_specs,
399483
outputs,
400484
RowValue::Product,
401485
FoldAggregate::sum(),
402486
None,
403487
) else {
404488
return Ok(None);
405489
};
406-
let plans = operands.into_iter().map(|(_, p)| p).collect();
407-
let original = LogicalPlan::Aggregate(agg.clone());
408-
let names: Vec<String> = (0..agg.group_expr.len())
409-
.map(|i| format!("{PREFIX}o{i}"))
410-
.chain([format!("{PREFIX}v")])
411-
.collect();
412-
let Ok(node) = FoldNode::try_new(spec, plans, None, names.clone()) else {
490+
let Ok(spec) = spec.with_conditions(conditions) else {
413491
return Ok(None);
414492
};
415-
let node = match fallback {
416-
Fallback::HostPlan => node.with_fallback(original),
417-
Fallback::Kernels => node.marked_found(),
418-
}
419-
.into_plan();
420-
// Give the node the aggregate's schema: its names, qualifiers, types
421-
// and nullability.
422-
restore(node, &names, &agg.schema)
493+
let operands = operands.into_iter().map(|(_, p)| p).collect();
494+
Ok(Some(Found {
495+
fold: spec,
496+
operands,
497+
}))
498+
}
499+
500+
/// `e` as a condition between two of a fold's dimensions: `l <op> r` with
501+
/// `l` and `r` columns that an operand holds as keys (`columns` and `keys`,
502+
/// per side of the join), on different sides.
503+
fn comparison(
504+
e: &Expr,
505+
columns: &[Vec<Expr>; 2],
506+
keys: &[Vec<Key>; 2],
507+
inputs: [&DFSchema; 2],
508+
) -> Option<Condition> {
509+
let Expr::BinaryExpr(BinaryExpr { left, op, right }) = e else {
510+
return None;
511+
};
512+
let comparison = match op {
513+
Operator::Lt => Comparison::Less,
514+
Operator::LtEq => Comparison::LessOrEqual,
515+
Operator::Gt => Comparison::Greater,
516+
Operator::GtEq => Comparison::GreaterOrEqual,
517+
_ => return None,
518+
};
519+
let dimension = |e: &Expr| -> Option<(usize, DimensionId)> {
520+
let s = side(e, inputs)?;
521+
let c = columns[s].iter().position(|k| k == e)?;
522+
let key = keys[s].iter().find(|k| k.column == ColumnIndex(c))?;
523+
Some((s, key.dimension))
524+
};
525+
let ((ls, l), (rs, r)) = (dimension(left)?, dimension(right)?);
526+
(ls != rs && l != r).then_some(Condition {
527+
left: l,
528+
comparison,
529+
right: r,
530+
})
423531
}
424532

425533
/// `plan` with each [`FoldNode`] that keeps the plan it replaced swapped

0 commit comments

Comments
 (0)