Tusk: Deep Feature Synthesis for Narwhals Lazy Frames¶

Design document. Status: approved for planning. Date: 2026-08-17.

1. Purpose¶

Tusk implements the Deep Feature Synthesis (DFS) algorithm over narwhals lazy frames. It offers a featuretools-shaped interface — an EntitySet of related tables plus a dfs() entry point — but computes features by building a single lazy query plan instead of materializing intermediate frames.

Three goals drive every tradeoff below:

1. Scale beyond memory. Feature synthesis pushes down into the backend engine. Tusk never calls collect() in its own logic.
2. Backend portability. Tusk uses the narwhals API only, so the same DFS code runs on any narwhals-supported backend.
3. A lean rewrite. Featuretools' long tail is deliberately omitted. Every feature in this document earns its place.

Non-goals¶

• Per-row cutoff times, training windows, and approximate (see §12).
• where clauses, interesting values, seed_features, primitive_options.
• Woodwork logical types or semantic tags.
• Python-callable primitives that operate on materialized values.
• Composite primary or foreign keys.

2. Public API¶

import tusk
from tusk.primitives import Quantiles

es = tusk.EntitySet("retail")
es.add_dataframe("customers", customers_lf,
                 primary_key="id", row_creation_time="signed_up_at")
es.add_dataframe("sessions", sessions_lf,
                 primary_key="id", row_creation_time="started_at")
es.add_dataframe("transactions", tx_lf,
                 primary_key="id", row_creation_time="occurred_at")

es.add_relationship(parent="customers", child="sessions", foreign_key="customer_id")
es.add_relationship(parent="sessions", child="transactions", foreign_key="session_id")

feature_matrix, features = tusk.dfs(
    entityset=es,
    target_dataframe_name="customers",
    agg_primitives=["mean", "count", Quantiles(qs=(0.25, 0.5, 0.75))],
    trans_primitives=["month", "weekday"],
    groupby_trans_primitives=["cum_sum"],
    max_depth=2,
    cutoff_time=datetime(2026, 1, 1),
    features_only=False,
)

# Re-apply a fitted feature set to new data.
matrix = tusk.calculate_feature_matrix(features, es_new, cutoff_time=...)

Parameter names track featuretools where the concept is unchanged, so existing knowledge transfers. feature_matrix is returned in the caller's native frame type; features is a list of inspectable Feature objects.

Defaults and return contract:

• max_depth=2, matching featuretools.
• cutoff_time=None means no time filtering is applied. A cutoff filters the target table as well as its relatives (§8), so the matrix can have fewer rows than the target: a row that did not exist yet at the cutoff has no features to compute. This matches featuretools. With features_only=True the cutoff is ignored entirely, since nothing is computed and feature definitions do not record it.
• features_only=True returns the feature list alone, not a tuple.
• The feature matrix has one row per visible target row, keyed by the target's primary_key. The target table must therefore have a primary_key; a positional correspondence would be meaningless on a lazy frame.

calculate_feature_matrix exists because the two-phase architecture provides it for free, and it is the reason users care about features_only: fit a feature set on training data, apply it unchanged to new data.

3. Architecture¶

Two phases with a hard boundary between them.

Phase 1 — synthesis (synthesis.py) walks the relationship graph using only schemas: column names, dtypes, keys, relationships. It emits an immutable graph of Feature definitions. No frame is touched. features_only=True returns after this phase.

Phase 2 — compilation (compiler.py) turns a feature list into narwhals operations, batching aggressively so that feature count does not drive join count.

synthesis.py must not import compiler.py. Phase 1 is therefore testable with zero dataframes, which is what keeps a single-backend test matrix defensible.

Module layout¶

src/tusk/
  __init__.py        # EntitySet, dfs, calculate_feature_matrix
  entityset.py       # EntitySet, TableSchema, Relationship
  dtypes.py          # dtype-family predicates over narwhals dtypes
  features.py        # Feature definitions (phase-1 output)
  synthesis.py       # phase 1
  compiler.py        # phase 2
  primitives/
    base.py          # Primitive ABCs and metadata
    registry.py      # name -> primitive, decorator sugar
    aggregation.py
    transform.py
  exceptions.py

Runtime dependency: narwhals only.

4. Schema model¶

EntitySet.add_dataframe(name, dataframe, primary_key=None, row_creation_time=None)¶

dataframe accepts a native frame or a narwhals frame. Native inputs are wrapped with nw.from_native; the original type is recorded so results can be returned in kind.

primary_key is optional. It is required only when the table is a relationship parent (it is the join key) or when an order-dependent primitive needs a deterministic tiebreak. Omitting it raises MissingPrimaryKeyWarning at add_dataframe() time, naming exactly what is forfeited:

sessions has no primary_key: it cannot be used as a relationship parent, and order-dependent primitives (e.g. cum_sum) on it will have non-deterministic tiebreaks.

MissingPrimaryKeyWarning is its own class so legitimate leaf tables can filter it in one line.

row_creation_time names the column recording when a row became knowable. This is the semantic the cutoff filter tests and the order that order-dependent primitives sort by. The name is deliberate: a transactions table may carry occurred_at, settled_at, and refunded_at, and only one of them belongs in this slot. (The temporal-database term of art is valid_from, rejected because it implies a matching valid_to that does not exist here.)

Single-backend rule. Narwhals cannot join a polars LazyFrame to a DuckDB relation. Every frame added after the first must share the first frame's backend, enforced at add_dataframe() with a SchemaError. This also makes the round-trip return type unambiguous.

EntitySet.add_relationship(parent, child, foreign_key)¶

foreign_key names the child's column. The parent side is always the parent's primary_key. Differing column names are the normal case (customers.id ← sessions.customer_id).

Three arguments rather than featuretools' four, with identical expressive power: featuretools also requires the parent column to be the parent's index. The form covers multiple relationships between the same pair (orders.billing_customer_id and orders.shipping_customer_id → customers) and self-references (employees.manager_id → employees).

Composite keys raise SchemaError rather than silently misbehaving.

Type system¶

Primitive matching uses narwhals dtypes only — numeric, temporal, string, boolean — via predicates in dtypes.py. No logical types, no semantic tags, no woodwork. The cost is a lost distinction between an integer that is a quantity and an integer that is a category; the benefit is zero extra concepts, zero dependencies, and identical behaviour on every backend.

The families are NUMERIC, TEMPORAL, STRING, BOOLEAN, and ANY. ANY is required by zero-arity and dtype-agnostic primitives (count, n_unique).

Categorical and Enum columns¶

Narwhals treats String, Categorical, and Enum as three distinct dtypes; none compares equal to another, and .str accessors fail on the latter two. STRING therefore matches String only.

This is deliberate rather than incidental. Casting a column to Categorical is an assertion that its values are labels, not text — and a word count or character count over a genuine category is meaningless. String-only primitives should skip these columns.

What must not happen is skipping them silently. A user who cast a column to Categorical upstream to save memory would otherwise get a feature matrix with columns quietly missing and nothing to explain why. So when synthesis skips a Categorical or Enum column solely because a requested primitive requires STRING, it emits CategoricalDtypeWarning naming both the column and the primitive.

The warning fires from synthesis rather than add_dataframe, because only synthesis knows which primitives were actually requested. A consequence: with the v1 built-in set it never fires, since no built-in requires STRING. That is correct — nothing is being skipped yet. It becomes live the moment a text primitive such as num_characters is added.

5. Primitive model¶

A primitive is a frozen dataclass that builds narwhals expressions. It never sees a value. This is what preserves pushdown:

build(*inputs: nw.Expr, **params) -> nw.Expr

Featuretools' model — get_function() returning a callable over a pandas Series — is incompatible with every goal in §1 and is not used.

Metadata¶

Phase 1 builds the feature graph before touching data, so stacking at depth ≥ 2 requires this metadata statically:

return_dtype and number_of_outputs are a method and a property rather than class attributes because both may depend on instance parameters (max preserves its input dtype; Quantiles(qs=(0.25, 0.5, 0.75)) yields three columns).

Extension¶

Built-ins live in a registry keyed by name. Users subclass AggregationPrimitive / TransformPrimitive and register. dfs() accepts names or instances interchangeably. Parameters are ordinary dataclass fields — which is why plain decorated functions were rejected as the primary form: they collapse the moment a primitive takes parameters. A decorator is provided as sugar for the zero-parameter case, producing the same instance type.

Backend capability¶

Primitives declare no capability metadata. If a backend cannot compute skew or a given window function, the user sees that backend's own error at collect(). This is an accepted rough edge, documented rather than papered over; a per-backend support matrix is a maintenance treadmill this project does not need.

6. Feature definitions¶

Frozen dataclasses with structural equality, so duplicate sub-features collapse via a set with no bookkeeping.

Each exposes .name, .display_name, .dtype, .depth, .table, .base_features, .output_names, .display_output_names, and .is_multi_output. Multi-output primitives yield indexed names: N_MOST_COMMON__product__0 … __2.

Names are SQL identifiers. Every construct joins with __ rather than the conventional dots, parentheses and spaces. This is not cosmetic: on a backend that generates SQL, MEAN(transactions.amount) parses as a function call over table transactions and customers.age as a column of table customers, so the conventional form cannot be selected at all — narwhals interpolates the identifier unquoted and duckdb raises BinderException. The conventional form is preserved on .display_name for logs, docs and error messages, and the differential tier translates featuretools' names to compare values.

Joining with __ makes a source column already containing __ capable of colliding with a generated name. compile_features refuses that case rather than silently dropping a column.

.dtype is derived statically from primitive metadata, never from data.

A multi-output feature is a valid output but never an input. Only its indexed columns are materialized; the un-indexed stem (QUANTILES__transactions__amount) never exists, so there is no single column another primitive could read, and .dtype — being singular — cannot describe it either. .is_multi_output is derived from len(.output_names) rather than from a primitive's number_of_outputs, so it is defined for IdentityFeature and DirectFeature, which have no primitive. A DirectFeature is filtered on the same grounds: it carries exactly one column across a join.

Depth rule: identity features are depth 0; every primitive application adds 1. SUM__sessions__MEAN__transactions__amount is depth 2. Featuretools has subtler rules here that routinely confuse users; this one is predictable.

7. Phase 1: synthesis¶

build(table, budget, path):
    feats = identity features of table
    if budget > 0:
        for child not reachable back along path:
            for base in build(child, budget-1, path+[rel]):
                feats += AggregationFeature(prim, base, rel)   # per matching prim
        for parent not reachable back along path:
            for base in build(parent, budget-1, path+[rel]):
                feats += DirectFeature(base, rel)
    feats += TransformFeature(prim, combo) for matching combos within budget
    return feats

Two rules carry the algorithm:

• Never traverse back along the path you arrived on. This prevents customers → sessions → customers from feeding the target's own columns back as derived features, and it makes diamond-shaped and self-referential schemas terminate.
• Primary keys and foreign keys are excluded from primitive inputs. MEAN(customer_id) is noise. Foreign keys remain usable as groupby keys and as inputs to count and n_unique.

Two exclusion sets, not one. The rule above is about inputs, and the row_creation_time is deliberately not in it: it is a measurement, and MONTH(signed_up_at) — §6's own exemplar TransformFeature — plus N_UNIQUE or CUM_COUNT over a temporal column, are exactly the features this split unblocks. (MAX stays out of reach: its input_dtypes is numeric-only, so no temporal column can ever satisfy it, split or no split.) Excluding row_creation_time from the input set would leave a zero-configuration run, whose transform defaults are all temporal, with no transform features at all.

A second, larger set governs output passthrough: the raw columns that never appear in the feature matrix are the join keys plus the row_creation_time. Passing the time index through as a feature invites target leakage, and featuretools drops it for the same reason. Only the raw column is dropped; features derived from it are unaffected. EntitySet exposes these as input_excluded_columns() and output_excluded_columns(); conflating them is the mistake the split exists to prevent.

Beyond those, stacking is governed by stack_on_self, by the multi-output rule in §6, and by dtype-family matching, which naturally blocks nonsense such as MONTH(MEAN(...)).

Identical features produced along different routes deduplicate by structural equality.

8. Phase 2: compilation¶

compile(features, entityset, cutoff) -> nw.LazyFrame. dfs() is synthesize() piped into compile(); calculate_feature_matrix() is compile() with a user-supplied feature list. There is no second code path.

1. Transitive closure. Walk .base_features to find the tables and sub-features actually needed.
2. Cutoff first. For each table carrying a row_creation_time, apply filter(nw.col(rct) <= cutoff) before anything else, so it pushes to the scan. This includes the target table, so the matrix may be shorter than the target. Tables without one are timeless and pass through unfiltered — documented, not warned, which makes a cutoff a silent no-op on an entity set that declares no row_creation_time anywhere. Cutoff effects do not cascade across relationships.
3. Compile bottom-up, deepest table first. Per table: with_columns() for transforms, then fold in aggregations from children.
4. Batch. All aggregation features sharing a (child table, relationship path) collapse into one group_by(fk).agg(...) and one left join. Direct features from a shared parent path collapse into one select and one join. Thirty features across two child tables produce two joins, not thirty.
5. Assemble. Select the target's primary key plus feature columns, aliased to .name.
6. Round-trip. .to_native(), or .collect().to_native() when the caller passed an eager frame.

Tusk calls collect() nowhere else.

Ordering¶

Order-dependent primitives must not rely on a frame-level .sort(). On lazy backends a sort is not guaranteed to survive subsequent operations. Ordering rides on the window expression instead:

nw.col("amount").cum_sum().over("customer_id", order_by=("occurred_at", "id"))

Narwhals requires order_by on Expr.over for order-dependent functions on lazy backends — cum_sum, cum_count, cum_min, cum_max, cum_prod, diff, shift, rank, and all rolling functions. Tusk's rule that order-dependent primitives require a row_creation_time is therefore narwhals' contract, not a local policy. The primary_key tiebreak is what the MissingPrimaryKeyWarning is about; without it, ties resolve arbitrarily.

.over(order_by=...) also works without a partition, so ungrouped order-dependent transforms are supported.

Correctness rules¶

• Left joins everywhere, so target rows never disappear when a child group is empty.
• Empty groups receive the primitive's default_value. After a left join a customer with zero transactions has null for MEAN (correct) and must be fill_null(0) for COUNT (also correct). This lives on the primitive dataclass, not as a special case in the compiler. It is a common source of silent bugs in naive reimplementations.

9. Built-in primitives¶

Aggregation: count, sum, mean, min, max, std, median, n_unique, percent_true, quantiles (multi-output).

quantiles is the v1 multi-output primitive rather than featuretools' n_most_common. Narwhals rejects length-changing expressions such as mode() inside a lazy group_by().agg() — "Length-changing expressions are not supported for use in LazyFrame" — so mode-based primitives have no portable lazy implementation. Quantiles(qs=(0.25, 0.5, 0.75)) exercises the same multi-output machinery and is expressible as expr.quantile(q).

Transform: year, month, day, hour, weekday, is_weekend, absolute, natural_log.

GroupBy transform: cum_sum, cum_count, cum_min, cum_max, diff, time_since_previous. Narwhals has no cum_mean; if wanted it must be composed from cum_sum / cum_count, so it is left out of v1.

What may go in groupby_trans_primitives¶

Only group-aware primitives — ones whose expression reduces or scans across the group. The built-in order-dependent primitives above all qualify.

Every other built-in transform is elementwise (absolute, month, add_numeric, …), and narwhals rejects .over() on an elementwise expression: InvalidOperationError: Cannot apply over to elementwise expression. Passing one in groupby_trans_primitives therefore fails — but it fails at expression-build time, raising synchronously out of compile_features rather than at collect(), so the user learns immediately rather than after a long query.

This leaves the grouped, non-order-dependent window path reachable only by user-defined primitives. That is the intended extension point: a primitive such as x / x.sum() ("share of group total") is group-aware without being order-dependent, and is exactly what that path exists to serve.

Multi-input arithmetic — add_numeric, subtract_numeric, multiply_numeric, divide_numeric — ships but stays out of the defaults. On a twenty-column table these generate hundreds of features, and featuretools users are routinely burned by it. Available by name, off unless requested.

Defaults¶

agg_primitives=None resolves to ["count", "sum", "mean", "min", "max", "std", "n_unique"]. trans_primitives=None resolves to ["year", "month", "weekday"]. groupby_trans_primitives=None resolves to [].

A zero-configuration dfs() call therefore does something sensible.

10. Errors and warnings¶

TuskError is the base class.

• SchemaError — unknown table or column; composite key; backend mismatch; missing primary_key on a relationship parent or on the DFS target; a relationship graph that cannot terminate.
• PrimitiveError — unknown primitive name; order-dependent primitive on a table without row_creation_time.
• MissingPrimaryKeyWarning — as described in §4.
• CategoricalDtypeWarning — a Categorical or Enum column was skipped by a requested primitive that requires STRING input. Its own class, so it can be filtered independently.
• UnmatchedPrimitiveWarning — a requested primitive found no column matching its input dtypes anywhere in the walk. This warns rather than raises: raising would break a zero-configuration dfs() on any schema that happens to lack a dtype family, and the case is the same shape as CategoricalDtypeWarning — skipping is correct, skipping silently is the bug. A primitive that produced features somewhere is not reported, since being inapplicable to one table among several is ordinary; each surviving (primitive, table) pair warns once per run. Its own class, so it can be filtered independently.

Every one of these fires during phase 1, from schemas alone, before any query is built. The single deliberate exception is backend capability (§5): those surface as the backend's own error at collect().

11. Testing¶

Test-driven throughout. The backend fixture is parametrized over a list that currently reads ["polars"].

Tier 1 — core suite (permanent, dev group)¶

Hand-built fixtures of a dozen rows, constructed in Python, with every expected value computed by hand. The forbid-binary pre-commit hook rules out committed parquet or feather fixtures in any case.

• Phase 1 needs no dataframes. Given a schema fixture, assert the exact set of generated feature names, their depths and dtypes; assert termination on diamond and self-referential schemas; assert the never-traverse-back rule blocks target-column leakage. Most of the algorithm's risk lives here and all of it is testable with zero I/O.
• Phase 2 against hand-computed values on a customers/sessions/transactions fixture, including empty groups, null-only groups, single-row groups, and ties — the cases real data contains only by accident.
• Laziness is tested behaviorally, not by grepping for .collect(). Scan a real parquet file, build the EntitySet, delete the file, then run dfs(): assert it returns normally and that FileNotFoundError appears only at .collect(). Anything that materializes early fails this test. (Scanning a nonexistent file instead would fail at add_dataframe(), since reading the schema touches the file.)
• Batching guard. Assert that N aggregation features from one child table produce exactly one join in explain(). Polars-specific and white-box, but it is the only way to keep the compiler's central performance property from regressing silently.

Tier 2 — differential vs featuretools (scaffolding, validation group)¶

Generate small synthetic multi-table data, run featuretools on pandas and tusk on polars, compare overlapping feature values. This is the sharpest available signal that DFS was reimplemented correctly rather than merely plausibly.

It must therefore cover deep synthesis, not just depth-1 aggregation over a single relationship: three tables at max_depth=2, cross-checking stacked aggregations and nested empty groups. Depth-1 over two tables is the easy part, and the defects this tier is meant to catch do not live there.

Where the two tools genuinely disagree, the disagreement is recorded and argued, not smoothed over by adjusting tusk or loosening a tolerance. Featuretools is a reference, not an oracle.

This tier is temporary. It exists to validate the algorithm during development and is removed once the library settles — concretely, once the differential suite has passed unchanged across two consecutive releases that added primitives. Removal is a deliberate decision, recorded in the changelog.

Tier 3 — relbench performance (benchmark group)¶

Run tusk against a relbench dataset and record runtime and peak memory. Relbench is the only tier that can put evidence behind the scale-beyond-memory goal in §1, and its schema model maps one-to-one onto ours (pkey_col, time_col, fkey_col_to_pkey_table → primary_key, row_creation_time, relationships — verified against relbench 2.1.2). Relbench also publishes a featuretools-DFS baseline to compare against.

The dataset is rel-ratebeer (13 tables, 16 foreign keys, 11.8M rows in the target) on duckdb. Both choices are load-bearing. rel-f1's largest table held 28k rows, which measures startup cost rather than scale. And at 339 features over 11.8M rows the backend stops being interchangeable: polars' streaming engine was measured growing to ~21GB and being killed rather than spilling, by every route tried — one plan, forced engine="streaming", feature-batched with the parts joined afterwards, and pairwise joins sinking between steps. duckdb computes the same matrix in a single call by spilling to disk under a 12GB buffer-pool limit (~16GB peak RSS, since the limit does not cover allocations outside the buffer manager). The tier runs on the backend that can demonstrate the claim the tier exists to make.

Kept until deliberately cut.

Execution¶

Tiers 2 and 3 are marked (@pytest.mark.differential, @pytest.mark.benchmark) and excluded from the default pytest run and from pre-commit. Their dependencies live in separate [dependency-groups] entries so neither the runtime nor the core test loop carries them.

12. Known risks and accepted tradeoffs¶

• Portability is verified on two backends, polars and duckdb. It was asserted rather than verified until duckdb was actually run, and the first run failed outright: feature names carried dots and parentheses, which a backend that generates SQL parses as table qualifiers and function calls, so no multi-table feature could be selected at all. The backend fixture in conftest was parametrized but unused, so nothing exercised the claim. tests/test_backend_duckdb.py now covers it directly. Backends beyond these two remain unverified.
• Backend capability errors surface late, at collect(), in the backend's own vocabulary (§5).
• A single global cutoff is not leak-free for ML. Per-row cutoff times are what prevent target leakage in a training set; §13 covers the path there.
• Multi-input arithmetic primitives can explode feature counts if requested on wide tables. Mitigated by keeping them out of the defaults.

13. Future work¶

Deliberately deferred; none requires restructuring the feature graph.

• Per-row cutoff times, training windows, approximate.
• where clauses / interesting values, seed_features, primitive_options.
• Additional backends in the test matrix beyond polars and duckdb.
• tusk.from_relbench(db) — roughly fifteen lines once the schema model exists.
• Feature serialization to disk.

14. Packaging and tooling¶

• Add [build-system] with hatchling and adopt a src/ layout; the project currently has neither.
• Runtime dependency: narwhals. Dev adds pytest and polars.
• Dependency groups: dev, validation (featuretools, pandas), benchmark (relbench).
• Google-style docstrings, configured in pydoclint. Both interrogate and pydoclint are already in pre-commit, so every public symbol needs a complete docstring.