Permutation Tests Over Unmaterialized Joins for Relational Feature Selection

When a model is trained on a company database, the usual first step is to join the tables into one flat table and compute summary features, such as "average price of products this user bought." A hub entity (a product bought by 100,000 users, or a user with 10,000 orders) then gets copied thousands of times. That copying causes two separate problems. It makes the joined table explode in size. It also makes useless features look statistically significant, because one entity's quirks are echoed across many rows. Database research has solved the first problem by computing aggregates without ever building the join. Statistical relational learning has solved the second with permutation tests, which shuffle attribute values while keeping the link structure fixed. These tests are expensive, and they have always run on explicit graphs or flattened samples.

This note proposes to merge the two. The central observation is simple. If you shuffle an attribute within its own base table (for example, reassign product prices among products), every key and every join path stays intact. Each shuffled replicate is therefore just another aggregate query that a factorized engine can answer. Many replicates can be packed into one pass. The result is a calibrated significance test for every candidate relational feature, with cost that scales with the size of the database rather than the size of the join. We then use it to prune automatically generated feature sets before gradient-boosted trees.

Core Claim

Two lines of work are relevant, and each covers half the problem. In-database factorized learning (In-Database Factorized Learning) and the LMFAO engine (A Layered Aggregate Engine for Analytics Workloads: Meet LMFAO) rewrite training into batches of sums and counts that are pushed past joins. Their runtime is bounded by database size and join width, not join output. Both, however, treat joined tuples as independent observations, so a hub's attributes enter the sums once per link. Relational probability trees (Learning relational probability trees) show exactly why this matters. Aggregated features such as COUNT and MAX correlate with node degree, and standard split tests therefore accept noise. Their fix is a randomization test: permute values while holding the network fixed, then compare the observed statistic to that empirical null. It needs hundreds of permuted pseudosamples per candidate and was never run at database scale.

The research file suggests that permutation and factorized pushdown are fundamentally at odds, since shuffling seems to break the fixed join paths. We argue this is only true for the wrong kind of shuffle.

Consider a target entity $u$ (say a user), a candidate feature built along a join path $u \to o \to p$ (user to order to product), and an attribute $x_p$ stored in the product table. The feature is

$$g_u = \bigoplus_{(u,o,p)\,\in\, \text{paths}(u)} \phi(x_p),$$

Here $\phi$ is a per-value transform and $\bigoplus$ is a distributive aggregate: sum, count, or max. The observed test statistic is $T = \text{corr}(y, g)$ over target entities, where $y$ is the label.

Now draw permutations $\pi_1,\dots,\pi_B$ of the rows of the product table. The replicate feature $g_u^{(b)}$ is the same query with $x_p$ replaced by $x_{\pi_b(p)}$. The keys never move, so all $B$ replicates can be carried as a $B$-dimensional value in one bottom-up pass of LMFAO-style directional views. For acyclic schemas, that pass costs roughly $O(B\cdot|D|)$, where $|D|$ is the total size of the base tables. Recomputing the feature on a materialized join instead costs $O(B\cdot|J|)$, where $|J|$ is the join size. The additive-instead-of-multiplicative saving follows directly from the distributive rewriting in In-Database Factorized Learning.

This "feature-side" permutation also tests a better null hypothesis than the classic RPT recipe of shuffling the target labels. It keeps each user's link pattern, keeps any autocorrelation among the labels, and keeps the fact that users who share products receive correlated null features. That shared-neighbor effect is the concentrated-linkage source of excess variance that Relational Learning with One Network: An Asymptotic Analysis identifies as degrading estimation in densely connected networks. Label permutation breaks label autocorrelation, so we expect it to be anti-conservative, meaning it reports significance too often, exactly when the data are most networked.

Stated plainly, the claim is this. Feature-side permutation tests, evaluated as batched factorized aggregates, give calibrated p-values for relational aggregate features at a cost close to computing the features once. Pruning feature synthesis with these p-values should remove hub-driven spurious features without hurting downstream accuracy. The pruned set should be more stable across time splits.

Research Program

The first component is the test engine. We extend an LMFAO-style view compiler so that a leaf attribute can be replaced by $B$ permuted copies. The multi-output machinery then propagates a vector of length $B$ instead of a scalar. Sum, count, and mean are handled through sums, and max and min through max-plus arithmetic. MODE and COUNT DISTINCT do not push down cleanly, and we will state their exclusion rather than approximate them.

RelBench tasks restrict every feature to events before the prediction's seed time. That restriction is an additive inequality on timestamps, which is precisely the class of constraints handled by functional aggregate queries with inequalities (Functional Aggregate Queries with Additive Inequalities). The leakage-safe version of the test therefore stays inside the factorized setting.

When the permuted attribute is itself structured, for example product prices that drift over time, plain exchangeability fails. For that case we use restricted permutations within strata such as time buckets or categories. Because a restricted permutation still reassigns values within one base table, it also leaves the keys untouched.

The second component is the statistics. Automated feature synthesis produces thousands of candidates, so we control the false discovery rate across them. Features that share a permuted table and a permutation draw also allow max-statistic corrections at no extra cost. We will derive when the feature-side null is exact, namely when the attribute is exchangeable across rows of its own table given the strata. We will also characterize its power loss relative to an oracle null on synthetic generators, where the true dependence structure is known.

The third component is the pipeline. Deep feature synthesis, which generates SUM, MEAN, COUNT, and MAX features along foreign-key paths, feeds candidates into the test. Features that survive go to LightGBM. We also test the variant where surviving features are concatenated with graph embeddings, in the hybrid style that Grables: Tabular Learning Beyond Independent Rows found strongest.

We are explicit about scope. The proposal does not claim that pruned flat features can express what message passing expresses. Grables proves that row-local models cannot represent targets such as uniqueness or shared witnesses. Our contribution is to make the flattening route statistically honest and cheap, which is the route Relatron (Relatron: Automating Relational Machine Learning over Relational Databases) shows often wins on high-homophily tasks.

Baselines

The naive reference point is full deep feature synthesis with no selection, fed to LightGBM. It is run with the same RelBench temporal splits and the same LightGBM tuning budget as every other arm. The file gives no RelBench number for full deep feature synthesis plus LightGBM, so this is "no reported result found on Lacuna for DFS+LightGBM on individual RelBench tasks"; we will report our own runs. The nearest published reference is the single-table LightGBM baseline in RelBench: A Benchmark for Deep Learning on Relational Databases. Relational deep learning, which turns every row into a graph node and trains a graph neural network over foreign-key edges, beats that baseline by an average of 20.4% on classification.

The flattened-row significance test is the direct competitor on calibration. It is a chi-square or correlation test computed over rows of the materialized join, the mechanism that RPT showed overfits to hubs. We run it on identical candidate features. Our method beats it if its false-positive rate at nominal α=0.05 on planted-noise features is near 0.05 while the flattened test's is inflated.

The label-permutation randomization test of Learning relational probability trees is the strongest existing method for the statistical question. The file reports that it filtered 100% of inserted noise features and produced trees an order of magnitude smaller than C4.5. No runtime figure for it is reported on Lacuna. We implement it with the same $B$, on the same entity-level features, which makes it cheap too. That arm is the key ablation: it isolates whether the choice of null (shuffle features on their own table versus shuffle target labels) matters. Our method beats it if it stays calibrated on generators with label autocorrelation where label permutation does not, with comparable power elsewhere.

The strongest downstream competitors are Relatron and the Grables hybrid. Relatron routes each task to either feature synthesis or a graph neural network and reports up to an 18.5% improvement over strong baselines. We run it from its public code (Relatron Official Repository). The Grables hybrid of LightGBM plus graph-network embeddings reports 0.7486 AUC on relbench-trial, against 0.7009 for LightGBM and 0.6860 for a graph neural network alone. Beating either on raw accuracy is not the bar. The bar is matching the accuracy of the unpruned pipeline, both flat and hybrid, while cutting feature count substantially and improving rank stability of selected features across adjacent time windows.

For runtime, the reference is running the identical test on the materialized join in PostgreSQL or DuckDB with the same $B$. LMFAO's own reports supply context: up to three orders of magnitude over MonetDB and a commercial database on aggregate batches, and crashes of competitors on Yelp's many-to-many joins.

Why not just…?

Why not just select features by validation performance or permutation importance on a held-out split? This is the most serious threat, and we treat it as one. Validation selection is cheap and model-aware. It has two weaknesses. Temporal splits share hub entities between train and validation, so hub idiosyncrasies can look predictive in both. Permutation importance also shuffles the flattened feature column, which destroys the degree and shared-neighbor structure the null should keep. Neither argument is decisive in advance. We therefore include validation-based selection, with an equal compute budget, as a full arm in every experiment. If it matches our method on downstream accuracy and on stability across time windows, we will report that our contribution narrows to calibrated inference and scale.

Why not just normalize by degree, for instance use MEAN instead of SUM or add degree as a feature? Degree normalization addresses only first-order degree disparity. It leaves MAX-type features, whose null distribution shifts with degree, uncorrected. It also does nothing about concentrated linkage or label autocorrelation. The synthetic calibration study will include a degree-normalized flattened test so that this alternative is measured rather than dismissed.

Why not just sample the join, for example with the exact-weight sampler in NeuroCard: One Cardinality Estimator for All Tables, and run ordinary tests on the sample? Uniform samples of join rows are still join rows. Hubs remain overrepresented, and the tests' unit of analysis is still wrong. Do more observations bring more information in rare events? further indicates that test power depends on the count of rare events, which uniform sampling undersamples. We will include a sampled-join arm at matched runtime.

Why not just skip flattening and use a relational graph network such as RelGNN: Composite Message Passing for Relational Deep Learning? On tasks that need multi-hop structure, graph networks win, and we do not contest that. Two points from the file keep the flattened route relevant. Relatron shows that feature synthesis frequently wins on high-homophily or small-schema tasks. RelBench and RelGNN both report a persistent deficit on regression. We report per-task results against RelGNN rather than claiming dominance.

Proposed Experiments

The first decisive check is calibration on synthetic relational databases. We build three-table user–order–product schemas with power-law product popularity and tunable label autocorrelation among users who share products. We plant pure-noise product attributes and a few true signals. We then measure empirical false-positive rate and power at α=0.05 for five tests: the flattened-join test, the degree-normalized test, the sampled-join test, label permutation, and feature-side permutation. The prediction is that only feature-side permutation stays near nominal size as autocorrelation rises. If label permutation is equally calibrated, the null-choice argument fails and the contribution reduces to the speed-up.

The second check is downstream behavior on RelBench across all seven databases (rel-amazon, rel-hm, rel-stack, rel-event, rel-f1, rel-trial, rel-avito) and its classification and regression tasks. Every arm uses the official temporal splits and metrics. We report task metric, number of selected features, and overlap of selected features across consecutive time windows. We give regression tasks separate attention, since that is where the flattened route is most competitive.

The third check is scale. We time the batched test against materialized recomputation on the LMFAO workloads: Retailer (87M tuples), Favorita (125M), Yelp (8.7M with many-to-many joins), and TPC-DS. We vary $B$ from 100 to 1,000 and join depth. The prediction is near-linear growth in $B\cdot|D|$ for our method, and out-of-memory failure or $B\cdot|J|$ growth for the materialized version on Yelp.

The work succeeds if the synthetic study shows calibration where the alternatives fail, RelBench shows no accuracy loss with fewer and more stable features, and the runtime study shows the test costing a small multiple of one feature-computation pass.