Orphan Keys: Checking Referential Integrity Without Foreign Keys

A fact table’s foreign key points at a dimension row. In a transactional database, that relationship is enforced on every insert: the engine looks up the parent row and refuses the write if it is absent. In a warehouse, the same relationship is usually declared in the DDL and then not enforced at all, because checking it on every load means a lookup per row against a table that may be partitioned differently, and the cost is prohibitive at the scale warehouses operate on.

The declaration remains, and it is misleading. A query optimiser may use it to skip a join, on the assumption that every fact row has a matching dimension row, and that assumption is exactly what is not verified. The integrity is therefore a property that has to be tested rather than maintained, and the test is a scheduled anti-join whose cost and semantics both deserve attention.

Why the constraint is declared and not enforced

The standard allows a foreign key to be declared with enforcement deferred to commit, which reduces the per-row cost to a per-transaction check. Warehouses go further and support declaring a constraint as informational, meaning the engine records it for the optimiser and never validates it. The reason is structural rather than historical.

Enforcement requires a lookup into the parent table for each child row, or a set-based check at commit. A set-based check is a join between the new rows and the parent, and it must be evaluated against a consistent snapshot of the parent. In a warehouse, the parent and child are typically written by different jobs at different times, and the child’s load may complete hours before the dimension’s load. Enforcing at write time would make the child’s load depend on the dimension’s, serialising two jobs that are otherwise independent, and it would fail every night in the window where the dimension has not yet been rebuilt.

Enforcement also interacts badly with partition replacement. A job that replaces a partition of the dimension removes rows that facts elsewhere still reference, and the check would have to scan the whole fact table to notice. The cost of the check is proportional to the table, not to the change, which is the opposite of what an incremental write path wants.

So the constraint becomes a claim about intent. The optimiser trusts it, the loader ignores it, and the gap between the two is where orphan keys accumulate. Some engines make this explicit by distinguishing enforced from trusted constraints, where a trusted constraint is one the user asserts and the engine will not verify; that distinction is the honest version of the arrangement.

The check is an anti-join, in both directions

Detecting orphans is a left anti-join: rows of the fact table for which no dimension row exists. Written as SQL, the natural form is a NOT EXISTS or a left join with a null test on the dimension’s key.

-- Orphan fact rows: keys that resolve to no dimension row at all.
SELECT f.customer_key, count(*) AS orphan_rows
FROM fact_orders f
WHERE NOT EXISTS (
  SELECT 1 FROM dim_customer d WHERE d.customer_key = f.customer_key
)
GROUP BY f.customer_key
ORDER BY orphan_rows DESC
LIMIT 50;

The plan for this query is a build-side hash of the dimension’s keys, then a probe for each fact row. The cost is a full scan of the fact table plus a hash table sized by the dimension’s distinct key count, which is usually small relative to the fact. That is the cheap direction.

The expensive direction is the one that is usually skipped: a dimension row that no fact row references. It is not an integrity violation, since a dimension may legitimately contain entities that have not yet transacted, but it is a strong signal of a join that failed upstream or of a dimension loaded with the wrong key space. Checking it requires the reverse anti-join, whose build side is the fact table’s distinct keys, which is much larger. The cost asymmetry is why the reverse check is run less often, on a sample, or not at all.

A third direction matters more than either: a fact row whose key resolves to a dimension row that is not the right one. Referential integrity in the strict sense says nothing about this, because the key exists. It is detected only by comparing attributes, such as checking that the fact’s recorded region matches the dimension’s region for that key, which is a join plus a predicate rather than an anti-join. This is the point where an integrity check becomes a correctness check, and it is the same step from marginal profiles to relational assertions over column combinations.

The time dimension breaks the simple formulation

A dimension that tracks history has multiple rows per entity, each valid over an interval, and a fact row must resolve to the version that was current when the event occurred. That turns a key equality into an interval containment, and the check becomes a join on key plus a predicate on the event timestamp.

The failure mode this creates is specific: a fact row can resolve to a dimension version that exists but whose validity interval does not contain the event time. The key matches, so a key-based anti-join reports no orphan, and the fact is nevertheless attributed to a version that did not exist when it happened. The check has to be written against the interval, not the key, and the cost rises because the join is now a range join rather than an equality join.

Late-arriving dimensions add the complementary problem. A fact row for an event on day $d$ arrives on day $d$, and the dimension row describing the entity as of day $d$ is not created until day $d+3$, when the source system first reports the entity. Between those days the fact is a genuine orphan, and after them it is not. A check that runs on day $d+1$ and alerts produces an alert for a condition that resolves itself. The remedy is either to delay the check past the dimension’s lateness horizon, or to classify orphans by age and alert only on those older than the horizon.

The horizon is a property of the dimension’s source, not of the warehouse, and it has to be stated. Without it, every check either fires constantly on recent partitions or is delayed so far that it detects nothing in time.

Making the check affordable

A full anti-join per load is often too expensive to run at the frequency the check needs, and three techniques reduce the cost without changing the answer.

The first exploits clustering. If the fact table is partitioned or sorted by the foreign key, the anti-join can be restricted to the partitions whose keys are new. When the dimension is append-mostly and its key space grows slowly, the set of keys added since the last check is small, and only fact rows with those keys need checking. This converts a full scan into a lookup for each new key, which is proportional to the rate of change rather than the size of the table.

The second uses a probabilistic structure on the build side. A Bloom filter over the dimension’s keys answers “definitely absent” or “possibly present” in a fixed number of bits per key, with a false-positive rate that falls as the filter grows. With $m$ bits and $k$ hash functions, the false-positive rate is approximately $(1 - e^{-kn/m})^k$ for $n$ keys, so ten bits per key with seven hash functions gives around one percent. A fact key that the filter rejects is certainly an orphan; one that it accepts needs verification against the dimension. The filter is small enough to be broadcast, which removes the shuffle that a full join would require. The catch is that the filter must be rebuilt whenever the dimension changes, and a stale filter produces false orphans for keys added after it was built.

The third is to check a sample. Sampling gives an estimate of the orphan rate rather than a list of orphans, and it is appropriate when the question is “is the rate acceptable” rather than “which rows are wrong”. A sample of a few million rows can estimate a rate near one percent to within a fraction of a percent, which is enough for a threshold check and not enough to drive a repair.

# Bloom filter sized from an expected key count and a target false-positive rate.
import math, hashlib

class KeyFilter:
    def __init__(self, n, fp=0.01):
        self.m = max(64, int(-n * math.log(fp) / (math.log(2) ** 2)))
        self.k = max(1, round(self.m / n * math.log(2)))
        self.bits = bytearray(self.m // 8 + 1)

    def _hashes(self, key):
        h = hashlib.sha256(key).digest()
        # Two 64-bit halves, combined as h1 + i*h2 (Kirsch-Mitzenmacher).
        h1 = int.from_bytes(h[:8], "little")
        h2 = int.from_bytes(h[8:16], "little") | 1
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, key):
        for pos in self._hashes(key):
            self.bits[pos >> 3] |= 1 << (pos & 7)

    def might_contain(self, key):
        return all(self.bits[p >> 3] & (1 << (p & 7)) for p in self._hashes(key))

What an orphan actually indicates

The presence of orphan keys has several distinct causes, and the appropriate response differs for each, which is why a bare count is a poor signal.

A dimension that is late produces orphans that disappear. A dimension that is incomplete, because a source filter excluded some entities, produces orphans that persist. A fact load that produced keys from a source with a different key format produces orphans in bulk, all at once, and the count is proportional to the batch. A single bad record produces one orphan and is invisible in a rate.

Separating these requires the orphan’s age and its volume. A small number of young orphans is normal in any system with independent load schedules. A large number of young orphans is a bulk format mismatch, which is urgent. A small number of old orphans is a persistent defect that will never resolve itself. The check should therefore report orphans bucketed by age rather than a single total, and the thresholds should differ per bucket.

There is also a class of orphan that is legitimate and should be modelled explicitly rather than counted as a defect. A fact row can reference an entity that has been deleted from the source, and the deletion may be intentional. Kimball-style dimensional models handle this with an inferred or unknown member row, a synthetic dimension key that all otherwise-unmatched facts map to. That arrangement converts an integrity violation into a modelled state, and it makes the orphan check meaningful again, because any fact that fails to resolve to either a real member or the unknown member is a genuine defect rather than an expected one.

Where the check belongs in the pipeline

The check can run before the fact table is published, after it, or on a schedule independent of the load.

Before publication, it can block the commit, which means a load with orphans is rejected entirely. That is appropriate when the orphans indicate a format mismatch that will affect every row, and inappropriate when they indicate a dimension that is merely late, since blocking would fail the load every night. The distinction cannot be made from the orphan count alone, which is why a blocking check needs the age classification described above.

After publication, the check is advisory and the facts are already visible to consumers. That is acceptable when consumers join through the unknown member and tolerate the misattribution, and not acceptable when a report sums facts by dimension attribute, since orphan facts either drop out of the report or appear under the unknown member and distort it.

On an independent schedule, the check is decoupled from the load and can run at whatever frequency its cost permits. This is the arrangement that survives, because it does not couple the load’s success to the check’s cost, and because it can be run against historical snapshots to determine when an orphan appeared. The cost is detection latency, which is bounded by the schedule rather than by the load.

Whichever arrangement is chosen, the result should be recorded rather than only alerted, since the value of the check over time is in the trend. A rate that rises slowly over months is a different problem from a rate that jumps in one night, and only the history distinguishes them. That history is the same shape as the partition-level volume record, and it is worth keeping both in one place so that an integrity fault can be correlated with a volume change on the same day.