What happens after you hand over your insurance card
You have probably done this. You see a doctor, hand your insurance card to the front desk, and a few weeks later a letter arrives explaining what your plan paid and what you still owe. From where you sit, that is one visit, one bill, and one payment. Done.
Now picture the same visit from inside the insurance company. The doctor's office sends in a claim describing the visit. A week later their billing team spots a wrong code and sends a corrected copy. Months after that, your employer reports that you had already left the job before the appointment, and the question of who should have paid is open again. None of this overwrites what came before. Each step is written down as a new record, because the old records explain why money moved when it did.
So one ordinary visit can leave a trail of records behind it. Most days nobody notices. Then someone asks a plain question, like how much we spent on MRIs last year or how many claims we turned down, and the honest answer depends on knowing which records describe the same visit and which of them is true today.
An email thread is a good way to picture it. The first message asks for something. The second corrects a detail, and the third adds one more item. To know what was finally agreed, you read the whole thread in order. The first message alone is out of date, and the third alone makes no sense without the two before it. Claims data works the same way, except the thread is scattered across several tables, and some of its messages arrive months late.
Gathering every record that belongs to the same visit into one chain, and then working out what that chain adds up to today, is called claims chaining. It sounds like bookkeeping. It turns out to be a graph problem with real engineering trade-offs, and getting it wrong quietly skews cost reports, claim counts, and the money a health plan is owed.
This guide is written for engineers and analysts who are new to health insurance data. Phase 1 needs no technical background at all. Phases 2 and 3 get technical, and if you can read a SQL query you have what you need. Specialist terms are defined as they come up: words with a dotted underline show their meaning when you hover over them, tap them, or tab to them.
Three visits. Nine rows. Four are real.
Here is what that trail looks like in data. The table below is a small synthetic sample from
the working project this guide is built on, modelled on CMC_CLCL_CLAIM, the main
claim table in Facets. No real member data is used.
Facets is a claims system that many health plans run on, and section 2.1 looks at it closely. For now,
you only need to read the table.
Insurers call patients members, so M01 to M03 in the table's header are three different patients. Each row is one record the insurance company stored. Reading left to right, you get the claim's ID number, the date of the appointment, the date the insurer decided what to pay, and the amount it paid. The last column is not in the Facets table. It is the answer you only get after untangling the rows, and working it out is what the rest of this guide is about. Give the table a moment and it will show you which rows are real.
| Claim ID | Service date | Adjudicated | Paid | What it really is |
|---|---|---|---|---|
| C1001 | 2025-02-20 | 2025-03-05 | 500.00 | replaced by C1002 |
| C1002 | 2025-02-20 | 2025-04-10 | 750.00 | replaced by C1003 |
| C1003 | 2025-02-20 | 2025-05-20 | 800.00 | the real claim |
| C2001 | 2025-01-18 | 2025-02-01 | 300.00 | voided, then rebilled |
| C2002 | 2025-01-18 | 2025-02-20 | 0.00 | the void record itself |
| C2003 | 2025-01-18 | 2025-02-25 | 425.00 | the real claim |
| C3001 | 2025-01-05 | 2025-01-15 | 1200.00 | split into two claims |
| C3002 | 2025-01-05 | 2025-02-01 | 700.00 | real claim, first half |
| C3003 | 2025-01-07 | 2025-02-01 | 500.00 | real claim, second half |
Three patients, one appointment each, nine rows in the claims table. Add the rows up and you overstate what you paid by 113%. Take the newest row from each and you lose half of a hospital stay. This page is about why that happens, how to state it precisely, and how to solve it in a way that stays solved.
The nine rows above are synthetic and come from a small dbt project that runs on DuckDB, so it needs no warehouse account. It holds the sample data, the three chain walks from Phase 3, and the tests that check them. Get the code on GitHub.
How this guide is laid out
The guide moves in three phases, and each one builds on the one before.
- The business problem. Who is involved in a claim, and the four everyday forces that turn one claim into many. No data background needed.
- The data problem. How that mess becomes a precise problem an engineer can solve, using the real tables and a little graph vocabulary.
- The solutions. Three ways to solve it, what each one costs as the data grows, and how to choose between them and prove the answer is right.
Short on time? Read Phase 1, then skip to the five takeaways at the end of section 3.7.
Why one visit turns into a pile of rows
Nobody designed it this way. It falls out of the fact that the people who deliver care and the people who pay for it are different companies, keeping different records, learning the truth at different times.
1.1 Who is in the room
- Payer: the insurance company. That's us. We decide what is covered and we send the money.
- Provider: whoever delivered the care.
- Member: the patient, the person with the insurance card.
- Employer group: the company that buys the insurance for its employees, and tells us when someone leaves. Usually late. This matters enormously later.
- Clearinghouse: the postal service for claims. Takes them from thousands of providers, checks the format, routes them to the right payer.
How a claim is supposed to work
- The member sees a doctor.
- The provider sends us a claim, a standardised message describing what happened. 98% arrive electronically.[1]
- We confirm the member was covered on the date of service. This is an eligibility check.
- We apply the benefit rules and decide what to pay. This is adjudication.
- We pay the provider and send a remittance advice.
- One claim, one row, one payment.
That path is real and it happens often. It is not what your data looks like, because four independent forces keep pushing claims off it, and each one adds rows.
1.2 The structural reason this is hard
The payer and the provider are separate companies with separate systems. They do not share a database. They communicate by sending each other standardised messages, and neither can force the other to correct anything. Add the employer group, which knows things we don't, and the member, who may hold a second policy we've never heard of. Four parties, four partial views, no shared source of truth.
A claim is not a fact. It is somebody's assertion at a point in time, and any of four parties can revise it later. You are not storing claims. You are storing a conversation, and your job is to reconstruct what the conversation currently concludes.
The scale rules out doing that by hand. CAQH, an industry non-profit that benchmarks administrative transactions, put 2024 electronic medical claim submissions at about 9.6 billion.[1] Read that word carefully: every correction and every blind resubmission is counted again. The number of distinct episodes of care behind them is smaller and nobody publishes it, which is this entire page in one sentence. Plans covering 217 million lives, about 63% of everyone insured in the US, reported 4 billion claims in a single year.[2]
1.3 Four forces that turn one claim into many
They are orthogonal: each happens on its own, and any combination happens at once. Learn them as four separate shapes.
The provider fixes something and resends it
Wrong procedure code, missing modifier, wrong unit count. The provider notices, or we tell them, and they send a corrected claim. The standard has a field for it: element CLM05-3 carries a claim frequency code, where 1 is original, 7 is replacement and 8 is void. A 7 or an 8 must carry our original claim number back to us in REF*F8, so we know what is being corrected.[3][4] A replacement says "right to send, wrong in the details." A void says "withdraw it entirely."
If that notation is new to you, it comes from X12 837, the standard file format claims travel in. A claim file is a series of short records called segments, and each segment is a list of fields, usually separated by asterisks. CLM05-3 means the third part of the fifth field in the claim segment, CLM. REF*F8 is a reference segment whose F8 code says the value after it is our original claim number.
What it does to your data: a new row with a pointer to the old one. Three corrections, four rows, one real claim.
We learn later that the member wasn't covered
An employee is let go on 31 January. HR is busy, and the termination reaches our eligibility system on 15 June. On 10 February that person is admitted for a three-day hospital stay. On 1 March we check eligibility, see active coverage, and pay; after a correction the claim settles at 2,500 dollars. On 15 June the termination lands, backdated to 31 January, and the stay is now outside the coverage window. Money went out for care the member was not entitled to. Payers call reversing such a payment a retroactive denial, and document it openly.[5]
Whether the plan may act on it is a legal question, not a data question. The Affordable Care Act bars retroactive cancellation of coverage except for fraud, with 30 days notice,[16] self-funded employer plans follow their own contracts, and state recoupment windows of 12 to 18 months apply to insured business only.[7] The largest single source of this data shape is not termination at all but the marketplace premium grace period, which payers list first among their own reasons for retroactive denial.[5] Retroactivity even runs the other way: Medicaid has covered care for up to three months before the application date since 1972.[6] Your pipeline's job is to surface the exposure precisely and let the people who know the contract decide.
A few of those terms carry a lot of weight. To recoup is to take back money already paid, often by holding it back from the provider's next payments. Insured business means plans where the insurance company carries the financial risk, so state insurance law applies. A self-funded plan is one where the employer pays its employees' claims from its own funds and hires the insurer only to process them. Federal law, mainly ERISA, governs those plans, which is why state recoupment windows usually do not reach them. The marketplace is the individual insurance exchange set up under the Affordable Care Act: HealthCare.gov and the state-run exchanges.
What it does to your data: nothing in the claims table changes. A row in a different table changes, and the correct answer for a claim you settled four months ago silently flips. Nothing about the claim's own dates tells you.
The same claim arrives twice with no link between them
A provider hears nothing, assumes the claim was lost, and sends it again. Or their software retries. Or they send a correction and forget REF*F8, so we have no idea it relates to anything. Omitting that reference is reportedly the single most common reason corrected claims fail, and we treat the correction as brand new, which usually earns a duplicate denial.[8]
Denials are frequent enough to matter. Marketplace insurers received 471 million claims in 2023 and denied about 20%, with individual insurers anywhere from 1% to 54%.[9] That figure covers HealthCare.gov plans only, not employer group business, so use it as evidence that denials generate resubmissions, not as anyone's denial rate.
What it does to your data: two rows for the same care with no pointer between them. Force A gives you rows that are linked. Force C gives you rows that should be and aren't, and the two need completely different handling.
One becomes two, or two become one
- Splits. A hospital stay crosses a plan-year boundary, so one claim becomes two so each part can be priced. One row in, two out. Both real.
- Merges. Two claims turn out to be one episode and are combined. Two in, one out.
- Coordination of benefits. We pay, then discover another insurer was primary, and reprocess months later.[10]
- System migration. The plan changes claims platforms. One claim, two identifiers in two formats, connected only by a crosswalk table somewhere else.
Two of those shapes need a word more. Deductibles and out-of-pocket limits reset at the start of each plan year, so days on either side of the boundary can count toward different totals. That is one common reason a stay is split into two claims. The split in the working project, C3001, carries no plan-year data, so read it as a split of any cause. A crosswalk is a lookup table that maps each old identifier to its new one, and it usually lives outside the claim table entirely.
What it does to your data: it breaks the mental model. People picture a correction chain as a line. Splits and merges mean it branches and rejoins.
1.4 What it costs to get this wrong
- You overstate spending. Sum every row in a correction chain and you count the same care three times. That lands in medical cost trend, in pricing, in reserves.
- Your counts are wrong. "How many claims did we process" and "what is our denial rate" both depend on what counts as one claim.
- You miss money you're owed. A retroactive termination creates recoverable overpayment inside a bounded window.[7] If the pipeline can't see the change, the window closes.
- Providers stop trusting you. A record that says one visit was paid three times becomes a phone call, then a dispute.
One more distinction before the trap below, because it changes how money adds up. A correction can be recorded in two ways. A restatement is a complete new copy of the claim with the right amounts, and it replaces the row before it. A delta records only the change, say minus 50 dollars, and is meant to be added to what came before. Both appear in claims data, sometimes inside the same chain.
"Take the most recent claim." It works on the first example and fails on the rest: on splits, where two claims are current at once and picking one loses half the money, and on delta adjustments, where the newest row is a 50 dollar reduction and taking it alone gives you minus 50 dollars instead of 1,150. Phase 3 shows both failures with real numbers.
Turning that mess into a problem you can solve
Phase 1 was stories. This phase converts them into a definition precise enough to hand to an engineer: the real table, the real shape, the real constraints.
2.1 Where it lives: the Facets claim table
Facets
adjudicates claims for many health plans.[11]
Its base claim table is CMC_CLCL_CLAIM, and three of its columns do all the work.[12]
| Column | Meaning | Why it matters |
|---|---|---|
CLCL_ID |
Claim Identification Number. Twelve characters: ten of claim number, then a two-character suffix starting at 00. |
Identifies one claim event. Not stable across corrections. |
CLCL_ID_ADJ_TO |
The id of the claim created when this claim was adjusted. | Forward pointer: who replaced me. |
CLCL_ID_ADJ_FROM |
The id of the claim this claim was adjusted from. | Backward pointer: who I replaced. |
The working project is designed against the Facets concepts in Cognizant's documentation, but
it uses simplified names: claim_id rather than CLCL_ID, and a separate
link table rather than the pointer pair on every row. Facets itself uses the names in the table
above, though they can differ by release and installation, and other claims systems use their
own. Map the ideas, not the spellings.
Here is how the pair would work on the first patient in the sample table, if those rows lived
in Facets.
When C1001 is corrected, the system creates C1002, writes
C1002 into C1001's CLCL_ID_ADJ_TO, and writes
C1001 into C1002's CLCL_ID_ADJ_FROM. The same happens again
when C1002 becomes C1003. Each row knows only its immediate neighbours,
so finding all three means starting from any one of them and following pointers.
There is no chain identifier column. Facets stores single-hop pointers between neighbours. The chain is not a field you select; it is a structure you reconstruct by following pointers until there are none left. That reconstruction is the whole problem.
The suffix is where people go wrong. The dominant in-Facets adjustment reuses the ten-character
claim number and bumps the suffix, so …789000 adjusts to …789001. It is
common, and it tempts everyone into chaining on the first ten characters. That catches the easy
cases and silently misses the hard ones: a void-and-rebill under a new claim number, a claim
reprocessed after coordination of benefits, a claim migrated from a legacy platform. Each has a
different CLCL_ID and belongs in the same chain. Chain on the pointers.
They are right in both cases; the prefix is right only in the easy one.
2.2 The other tables you need
The claim table alone cannot answer the business question, because Force B lives somewhere else. The minimum input set:
| Feed | Grain | Contributes |
|---|---|---|
| Claim header | one row per claim event | amounts, dates, status, the pointer pair |
| Claim links and crosswalks | one row per relationship | the edges, including cross-system links the claim table can't express |
| Member eligibility | one row per restatement | coverage windows, and when we learned about them |
| Employment events | one row per HR event | why a termination was retroactive, and how late it arrived |
| Payment ledger | one row per cash movement | an independent check on the arithmetic |
The grain column says what a single row stands for. Eligibility is kept as one row per restatement: each time an employer resends a member's coverage, a new row is added and the old one is left alone. That habit of adding rather than editing is what later lets you ask what we knew, and when.
The payment ledger never helps build the chain, which is exactly what makes it valuable: if the chain logic is right, the cash that actually moved must equal the reconciled amount. That is verification from a different direction, and Phase 3 leans on it.
Two things are deliberately out of scope. Facets also stores claim lines
(CMC_CDML_CL_LINE), and a lot of real chaining happens there: an adjustment changes
some service lines and not others, and splits are often line-driven. Everything here generalises
to line grain; modelling it would double the work and bury the ideas. Coordination of benefits
and BlueCard host/home claims add further identity layers by the same mechanism: more edge
sources, same graph.
In plainer terms: a claim line is one service on a claim, so an office visit and the blood test done during it can arrive as two lines on one claim. BlueCard is how a member of one Blue Cross Blue Shield plan (the home plan) gets care in another Blue plan's area (the host plan), so the same claim sits in both plans' systems under different numbers.
One constraint you get for free bounds the lookback your pipeline needs. Timely filing limits cap how late a genuinely new claim can arrive, commonly 90 to 365 days from service. Corrections and retroactive eligibility changes are not bounded that way, which is why Phase 3 keys the incremental design on arrival time rather than service date.
Incremental means each run processes only what is new since the last run, instead of rebuilding every chain from scratch. Section 3.6 shows how defining "new" by the wrong date loses data without a single error.
2.3 What the graph looks like
Look at those six pictures together and the abstraction is obvious. This is not a list and not a tree. It is a graph, and "which rows describe the same claim" is the question "which nodes are connected."
- Node: one claim row.
- Edge: one adjustment pointer.
- Undirected: we treat every pointer as two-way, because "is A related to B" doesn't care who pointed at whom.
- Connected component: a group of nodes all reachable from each other and from nothing outside. This is exactly what a claim chain is.
- Cycle: a loop. Only ever a data defect here, but it happens, and it hangs a naive algorithm forever.
- Diameter: hops across the widest part of a component. For claim chains, the longest correction sequence.
Put the sample table from the start of this guide into those words. Its nine rows are nine nodes, and they form three connected components, one per patient: a linear chain, a void and rebill, and a split, three of the six shapes above. Finding those components is the first half of the job. Section 3.6 covers the second half: which claims in each chain are real, and what the chain is worth.
2.4 The problem, stated precisely
Here is everything so far as one statement. It borrows a little set notation: V
is the set of claim rows, E is the set of pointers between them, and
G = (V, E) is simply the graph they make together. An append-only log is one where
rows are only ever added, never edited or deleted.
Given claim rows V and adjustment pointers E drawn from
several tables, forming an undirected graph G = (V, E); and an append-only
eligibility log recording both each coverage window and the moment we learned of it;
produce, for every claim: its chain_id, whether it is currently
authoritative, the reconciled amount for its chain counting no care twice, and whether its
coverage answer has changed since it was paid.
Naming a chain
A component needs a name that comes out the same every run. Label it with the minimum claim id it contains: deterministic, stateless, identical whichever node you start from. One property to design around: when a late edge merges two components, the smaller id wins and the other chain's name changes. If a downstream system must hold a durable key, it holds a surrogate from a mapping table that records merges, not this label.
An example makes the design point concrete. Say two chains exist on Monday, named
X5001 and X5007. On Tuesday a late link arrives that connects them. Now
they are one chain, named X5001, and any report that saved the name X5007
points at a chain that no longer exists. A surrogate key avoids that: a separate table gives each
chain a stable number of its own, and records that X5007 was merged into
X5001.
Two clocks
- Valid time: the coverage window. "Covered 1 January to 31 January."
- Transaction time: when we found out. "Told on 15 June."
- Bitemporal: keeping both, so you can ask what we believed on date X about date Y.
Both clocks let you compute two answers for one claim and compare them:
- Eligible at adjudication: using only eligibility rows recorded on or before the moment we adjudicated. What the adjudicator saw, and why the money went out.
- Eligible as known now: using every row recorded up to today.
True then, false now: that is your recoupment exposure, exactly. The project works out both answers for every claim in one eligibility model.
Run the hospital stay from Force B through both. On 1 March, when the claim was adjudicated, the log held no termination, so eligible at adjudication is true. Today the log includes the termination recorded on 15 June and backdated to 31 January, so eligible as known now is false for a 10 February service. That claim is exactly the exposure the plan may try to recoup.
Not the adjudication date. Coverage stops at a point in valid time, so two claims for one member can land on opposite sides of the same termination. A member terminated effective 31 January: a 20 January visit stays covered, a 5 February visit loses coverage. Both were adjudicated in the same month and both looked fine at the time.
2.5 Size, shape, and how often you redo it
The algorithm you choose depends entirely on these numbers, so they belong in the problem statement.
| Property | Value | Basis |
|---|---|---|
| Claim rows in scope | 107 to 109 | 4 billion claims across 217 million lives is about 18 per member per year.[2] Multiply by your membership and your retention window. |
| Edges per node | well below 1 | Most claims are never adjusted. Assumption; measure it on your own history. |
| Component size | 1 for most; 2–8 when adjusted | Each correction adds one node. |
| Diameter | usually single digits | Each hop is a human resubmitting. A retroactive fee-schedule load can re-adjust one claim many times, so typical, not bounded. |
| Dense clusters | absent from raw Facets; introduced by you | Adjustment pointers are one-to-one and produce paths. Density arrives with fuzzy duplicate matching, many-to-many crosswalks, or a fanned-out join. See 3.2. |
| Refresh | nightly, some plans intraday | Common practice. |
| Retro lookback | 12–18 months | State recoupment windows.[7] |
The graph is enormous but overwhelmingly sparse and shallow: billions of nodes, almost no edges, tiny components, small diameter. That is forgiving enough that several very different algorithms work. It also means the rare dense cluster is where they diverge violently, so you pick for the worst component, not the average one.
Non-negotiable
- Terminates. Cycles exist in production data.
- Deterministic. Same input, same
chain_id, every run. - Idempotent. Re-running changes nothing and double-counts nothing.
- Catches retroactive arrivals. Old business dates with new arrival timestamps must trigger recomputation. This is where most implementations quietly fail.
- Refuses to guess. When links contradict themselves, publish nothing.
That is the whole problem: an enormous but sparse graph, a precise list of outputs, and five rules any solution has to follow. Phase 3 puts three standard algorithms against it.
Three ways to solve it, and how to choose
Every number in this phase was measured. The benchmark setup is in [15], and the working dbt project is described in 3.7 and linked in [17].
All three methods do the same job: take the claims and their pointers, and give every claim the name of its connected component. They differ in how much work and memory that takes as the data grows. Two tools appear throughout. dbt builds warehouse tables from models, which are mostly SQL select statements, and keeps tests alongside them. One of the three walks in this project, union-find, is a Python model. DuckDB is a database that runs inside a single program on one machine. The timings below were measured with it, so read them for how cost grows rather than for exact seconds.
3.1 Notation
A handful of symbols make the three methods easy to compare. Here they are, with the values they take on real claims data.
| Symbol | Meaning | Realistic value |
|---|---|---|
n | claim rows (nodes) | 107–109 |
m | adjustment pointers (edges) | much smaller than n |
D | diameter, hops across the widest component | single digits |
k | size of the largest component | 1–8 typically, occasionally large |
α(n) | inverse Ackermann function | below 5 for any n that fits in the universe |
- O(…): how cost
grows with input, ignoring constants.
O(n): double the data, double the work. - Time and space are separate. An algorithm can be fine on one and fatal on the other.
- α(n): treat
O(α(n))as constant; that is why union-find is called near-linear. - Fixpoint: the stopping condition.
In a warehouse the unit that matters is often the number of passes over the data and the peak size of intermediate results. Beautiful asymptotics lose to a clumsier method that never materialises a huge intermediate table. You will see that happen below.
Put plainly: the best O(…) growth does not always win. Union-find has the best growth of the three, yet at a million shallow claims in 3.5 it ran slowest. Materialising means building and storing a table of rows on the way to the answer. The recursive query in 3.2 builds the biggest such table, and on dense data that is what sinks it.
One graph, three films
Each method below is shown as a filmstrip over the same seven claims. Time runs left to right, one frame per step. Every frame has the same three layers, so the methods can be read against each other:
- The graph. Whatever lights up green is where the method is working at that moment. Bold edges are edges it is reading.
- The state strip. Seven cells, one per claim, holding whatever the method actually stores. Amber cells changed in that step.
- The memory gauge. Live rows held at that moment, on one scale shared by all three figures.
A A A A E E G: each claim labelled with the smallest id in its chain.3.2 Method 1: Recursive query
The database-native answer. A recursive common table expression takes a starting set and a rule for one more step, and applies the rule until no new rows come back. Start from every claim, walk outward over the symmetrised pointers, label each claim with the smallest id it can reach.
The query reads two tables: claims, with one row per claim, and edges,
with two rows per pointer. Symmetrised means every pointer is stored twice, once in each direction,
which is how the walk can travel from an old claim to its replacement and back again.
with recursive walk (root, node, depth, visited_path) as (
select claim_id, claim_id, 0, '|' || claim_id || '|' from claims
union all
select w.root, e.dst, w.depth + 1, w.visited_path || e.dst || '|'
from walk w join edges e on e.src = w.node
where w.depth < 25
and position('|' || e.dst || '|' in w.visited_path) = 0 -- cycle guard
)
select root as claim_id, min(node) as chain_id from walk group by root
Simplified from the project's recursive model: it uses longer names
(stg_claims, int_claim_edges) and reads its depth cap from a project
variable.
The highlighted line is the part people forget. Without it, only the depth cap stops the walk.
Because every pointer is stored both ways, even a plain eight-claim correction chain produces
about 108 million rows before it does, and the three-claim cycle from Phase 2 about 200 million. The breadcrumb path records every node visited so far, and the
delimiters stop C100 matching inside C1001. The project's full version
is the recursive model.
Two more lines are worth reading closely. w.depth < 25 is a second safety net,
a hard cap on how far any single walk can go. The final select turns the pile of
walks into the answer: for each starting claim, the smallest id it reached becomes its
chain_id.
Watch it run
GROUP BY.Read the strip and the gauge together. The anchor plants one row per claim. Each depth
joins the previous depth's rows to the edge table and keeps every result, so the
frontier of active claims narrows (six, then four, then two, then none) while the total keeps
climbing. By depth 3 the four-claim chain alone has produced sixteen rows: every simple path
from every starting point. The singleton G never appears in a join and never
produces another row, which is exactly why the anchor must start from the claims table rather
than from the edges.
Two things to notice. The method never computes an answer as it goes; the strip holds only counts of evidence, and the labels appear in one aggregation at the very end. And the memory line is monotone. On a chain that is fine. On a dense cluster, the number of simple paths is what explodes, and this figure is showing you the mechanism in miniature.
What it costs
This decides whether you should use it. The recursive query does not walk each component
once. It enumerates every simple path in every component, from every starting
node. For a fully cross-linked component of k nodes:
rows = k × ΣL=0..k−1 P(k−1, L)
P(a, b) counts ordered selections of b from a. The
sum is factorial in k.
In words: a clique is a group in which every claim links directly to every other. Starting from
any one claim, the walk can step to any of the other k−1, then to any of the
k−2 not yet visited, and so on, keeping every partial path as a row.
P(k−1, L) counts the paths that take L steps. Adding those up for every
length, then multiplying by the k starting claims, gives the total. For
k = 4 that is 4 × (1 + 3 + 6 + 6) = 64, the first row of the measured table below.
Where would a cross-linked cluster come from? Facets adjustment pointers are one-to-one, so raw Facets gives you paths, never cliques. Density arrives the moment you add anything else, and you will: fuzzy duplicate matching to fix Force C links suspects pairwise and builds a clique by construction; a many-to-many migration crosswalk does the same; a join with a missing predicate turns a link table into a near-Cartesian product. This is what happens on the day you ship duplicate detection.
Measured against the formula:
| k | rows measured | closed form | match |
|---|---|---|---|
| 4 | 64 | 64 | yes |
| 6 | 1,956 | 1,956 | yes |
| 8 | 109,600 | 109,600 | yes |
| 9 | 986,409 | 986,409 | yes |
| 10 | 9,864,100 | 9,864,100 | yes |
| 12 | out of memory | 1,302,061,344 | n/a |
| 16 | not attempted | 56,874,039,553,216 | n/a |
| k | recursive | memory | union-find | memory |
|---|---|---|---|---|
| 8 | 0.116 s | 106 MB | 0.0008 s | 106 MB |
| 10 | 15.1 s | 2,880 MB | 0.0008 s | 106 MB |
| 12 | no result in 300 s | n/a | 0.0007 s | 106 MB |
Not ten million. Ten, cross-linked: 9.9 million intermediate rows, 15 seconds and nearly 3 gigabytes of memory. Twelve never finished: one run exhausted an 8 GB cap, another was still going after five minutes. Union-find did twelve in under a millisecond. This is not a tuning problem. It is the algorithm doing exactly what it is defined to do, and a recursive query that has run fine for two years will take the pipeline down the night a mass adjustment cross-links a batch.
Complexity. Time and space are both O(simple paths): O(n·k!)
worst case, a comfortable O(n·k) when components are paths, which they usually are.
Merits. One query, portable, termination is the engine's problem. For sparse, shallow,
path-shaped claim data it is the right default. Risk. Cost is governed by the worst
component in the data, and you cannot see that component coming from a row count.
3.3 Method 2: Iterative fixpoint
The literal version of "keep going until nothing changes." Every claim starts labelled with its own id. Each pass, every claim adopts the smallest label among itself and its neighbours. Count the labels that changed. Zero means every component now carries its minimum id.
-- one pass; repeat until changed = 0
create or replace table next as
select w.node, least(w.chain_id, coalesce(min(nb.chain_id), w.chain_id)) as chain_id
from work w
left join edges e on e.src = w.node
left join work nb on nb.node = e.dst
group by w.node, w.chain_id;
select count(*) from next a join work b on a.node = b.node
where a.chain_id <> b.chain_id;
Simplified from the project's fixpoint materialization, which wraps this pass in a loop and names the same tables more fully.
The highlighted expression is the whole rule: keep your own label unless a neighbour's is
smaller, and coalesce covers claims with no neighbours, which keep their own. The code
is one pass. Before the first pass, work holds every claim labelled with its own id.
After each pass, the second query counts how many labels differ between next and
work, and only then does next take the place of work.
Something has to repeat the pass until that count reaches zero. In this project that is a custom
dbt materialization, which stops with an error if 25 passes are not enough.
Watch it run
The strip is now the answer under construction. In pass 1 each claim looks at its
neighbours' labels and takes the smallest: B sees A and adopts it,
C sees B, D sees C. The label A
is three hops from D, so it takes three passes to arrive, and a fourth pass to
confirm nothing moved. Count the amber cells: 4, 2, 1, 0. That sequence is the diameter of the
longest chain, made visible.
Now look at the graph layer. Every edge is bold in every pass. The method does not know which labels are still travelling, so it re-reads everything, and that is the price of its flat memory line: two tables of seven rows, overwritten each round, never a third.
A pass touches every node and edge once: O(n + m). A label moves one hop per
pass, so the passes needed equal the diameter D, plus one to observe that nothing
moved. Time O(D·(n + m)), space O(n + m), and space does not
grow with depth because each pass overwrites the working table instead of accumulating paths.
Both predictions are testable. Fix the data at 60,000 claims and vary only the chain length:
| chain length | passes | time | peak memory |
|---|---|---|---|
| 2 | 2 | 0.110 s | 143 MB |
| 4 | 4 | 0.202 s | 149 MB |
| 8 | 8 | 0.386 s | 152 MB |
| 16 | 16 | 0.774 s | 159 MB |
| 32 | 32 | 1.52 s | 158 MB |
Passes equal chain length exactly. Time is linear in passes: 16× the depth costs 14× the time. Memory moves 143 to 159 MB while the recursive query on the same data moved 146 to 376 MB, because one accumulates paths and the other does not.
Merits. Cost you can predict before running. Immune to the density blow-up, since it never enumerates paths. Flat memory. It reports its own progress. Costs. Slower on shallow data, because each pass carries query overhead. Needs something to run the loop. In the project that is a custom dbt materialization, and it follows the advice below.
Write the loop as a bounded loop with a convergence check, not an
open-ended while, and raise an error if it hits the bound. That turns an unexpectedly deep
chain into a loud failure at a known cost instead of a session that runs all night. Cycles need
no special handling here: labels only ever get smaller, so the loop settles on a cycle like any
other chain.
A bound is a feature.
3.4 Method 3: Union-find
The classical answer. Union-find keeps a pointer from each item to a representative of its group. Find follows pointers up to the representative; union merges two groups by pointing one representative at the other. Process every edge once and the groups are the connected components.
If the terms are new, picture every group as a team with a captain, and every claim as
reporting to someone. find(x) follows who reports to whom until it reaches someone who
reports to nobody: that is the captain. A union has one captain start reporting to the other, and
at once both teams share a captain.
def find(x):
root = x
while parent[root] != root: root = parent[root]
while parent[x] != root: # path compression
parent[x], x = root, parent[x]
return root
for src, dst in edges:
a, b = find(src), find(dst)
if a != b:
if size[a] < size[b]: a, b = b, a # union by size
parent[b] = a; size[a] += size[b]
label[a] = min(label[a], label[b]) # chain_id = min claim id, as in SQL
Path compression re-points every node you climbed through straight at the
representative. Union by size keeps trees shallow. Together they give
O((n + m)·α(n)) total, effectively linear, proved by Tarjan in
1975.[13] The label is tracked separately from the
representative, so it can be the minimum claim id without disturbing the balancing. The project
runs the same routine as a dbt Python model.
The snippet leaves out the first and last steps. Before the loop, every claim is its own team of
one: parent[x] = x, size[x] = 1 and label[x] = x. After the
loop, a claim's chain_id is label[find(x)], the label kept at its
captain.
Watch it run
B, C and D all point straight at A. Memory is one slot per claim, throughout.This film has a different rhythm. The graph layer lights up one link at a time, never the
whole graph. Each step asks two questions, who is A's root, who is B's root, and if the
answers differ, hangs the smaller tree under the larger. The arcs are the data structure:
D is joined by walking up to C's root, finds A
immediately because the previous union hung C directly under A, and
gets attached in one move.
The strip converges to the same A A A A E E G as the fixpoint, but by a
different route. The fixpoint moved labels one hop per pass across the whole graph; union-find
moved pointers one link per step and never revisited a link. Depth of the chain did not appear
anywhere in the work, and neither did density: a fifth link inside an already-joined group
would return the same root twice and cost nothing.
The decisive property: cost does not depend on depth or density. An edge is an edge.
| chain length | recursive | iterative | union-find |
|---|---|---|---|
| 2 | 0.061 s | 0.110 s | 0.077 s |
| 4 | 0.126 s | 0.202 s | 0.092 s |
| 8 | 0.258 s | 0.386 s | 0.109 s |
| 16 | 0.605 s | 0.774 s | 0.122 s |
| 32 | 1.58 s | 1.52 s | 0.126 s |
Depth went up 16×. Union-find moved 1.6×. The other two moved 26× and 14×, because depth is a term in their cost and not in this one.
Merits. Immune to depth and density both. Cycles need no guard: an edge inside a group is a no-op. Costs. The logic leaves SQL. In dbt it runs as a Python model: locally on dbt-duckdb with pandas installed, which is how the project runs it, and in production on Snowflake, Databricks or BigQuery.[14] Interpreted Python pays a constant-factor tax on easy data: at a million shallow claims it was the slowest of the three. And it needs every claim and link in memory: hundreds of gigabytes at a billion claims in one process.
- Only feed it claims that have edges. Almost every claim is never adjusted and is trivially its own chain. Filter first and the graph collapses.
- Partition by member. A chain almost never crosses members, so the problem decomposes into millions of tiny independent problems with bounded memory each. Every method benefits, not just this one. The one exception is an adjustment correcting a wrong member id, which does cross, so partitioning is a strong heuristic backed by a reconciliation pass, not an invariant.
3.5 Head to head, and how to choose
On seven claims the differences look small. The shapes are what matter, because each one is a rule about how cost grows. The recursive line rises with the number of simple paths; the fixpoint's flat line is bought by re-reading the whole graph every pass, so its length grows with diameter; union-find's flat line comes with a step count equal to the number of links, and nothing else. The measurements below are those three rules at a million claims.
Peak memory below includes about 52 MB of fixed process overhead, measured on an empty connection, and union-find carries another 55 MB or so for pandas, so compare figures to each other and to those floors. These are single-node DuckDB timings: the shapes transfer to a distributed warehouse, the seconds do not.
| claims | recursive | iterative | union-find | peak memory |
|---|---|---|---|---|
| 1,000 | 0.0040 s | 0.0094 s | 0.0016 s | 107 MB |
| 10,000 | 0.014 s | 0.031 s | 0.011 s | 116 MB |
| 100,000 | 0.116 s | 0.241 s | 0.169 s | 227 MB |
| 1,000,000 | 1.01 s | 1.28 s | 2.66 s | 1,260 MB |
Notice how close they are. On sparse, shallow data all three finish a million claims in a couple of seconds, within a factor of three of each other, and which one leads changes with the setup: here the recursive query led and union-find trailed. That is the trap. A benchmark on realistic average data says the choice doesn't matter. It matters only on the worst component in the dataset, which is why 3.2 exists.
| Recursive query | Iterative fixpoint | Union-find | |
|---|---|---|---|
| Time | O(paths), up to O(n·k!) | O(D·(n+m)) | O((n+m)·α(n)) |
| Space | O(paths) | O(n+m) | O(n) |
| Sensitive to depth | strongly | linearly | no |
| Sensitive to density | catastrophically | no | no |
| Cycles | explicit guard | natural | natural |
| Stays in SQL | yes | yes | no |
| Predictable cost | no | yes | yes |
- Default to the recursive query. Sparse, shallow, path-shaped data is its best case, it is one readable query, and it stays where your analysts can see it.
- Switch to the iterative fixpoint when you need a cost you can bound, or when you have dense clusters and must stay in SQL.
- Switch to union-find when depth or density is unbounded and the walk is on the critical path of the nightly load.
And run more than one. They are cheap on normal data, and a test that fails when any two disagree is worth more than either implementation alone.
3.6 The walk is half the job
Connecting the rows tells you which claims belong together. It does not tell you which one is real, what the chain is worth, or whether the coverage answer has changed.
Which claim is authoritative
A claim is current if nothing supersedes it, it is not a void record, and it is in a final status. Not every pointer supersedes: an adjustment that layers a delta onto a claim leaves the original standing, so classify link types first. The project keeps that list, and the statuses that count as final, in one small macro file. A chain can have two authoritative claims, from a split, or zero, from a cycle. Zero is the correct answer there.
Two phrases there need unpacking. A final status means the insurer has finished processing the claim. A claim that is pended, parked while someone waits on medical records or a coding review, is still moving and is not an answer yet. Classifying a link means recording what kind of change it made: a replacement, a void, a split, a merge, a reprocess, a crosswalk from a migrated claim's old id, or a delta layered on top. Every kind except the delta supersedes the claim it points at.
Adding up the money
Both obvious rules are wrong, on different scenarios, which is why neither will do:
| Scenario | Correct | Sum every row | Newest row |
|---|---|---|---|
| Three-version correction chain | 800.00 | 2,050.00 | 800.00 |
| One claim split into two | 1,200.00 | 2,400.00 | 500.00 |
| Base claim plus two deltas | 1,150.00 | 1,150.00 | −50.00 |
| Eight-version chain | 170.00 | 1,080.00 | 170.00 |
Read it row by row. In the split, the original 1,200 was replaced by claims of 700 and 500: summing counts the 1,200 on top of its replacements, and the newest row keeps only the 500. Both halves carry the same adjudication time, 2025-02-01 09:00, so the project breaks the tie by claim id and picks C3003. The deltas behave the other way round. Summing gets 1,150 right because deltas are meant to be added, while the newest row alone is just the minus 50 correction. So summing is right only when the rows that no longer count carry no money, and the newest row is right only when every other row that still counts carries none. Real chains mix both, which is why links are classified before anything is added up.
The correct rule: non-superseded restatements, plus deltas still in force. For a chain with a cycle, publish nothing. The chain totals model computes both naive rules next to the correct one, and a test checks all three against hand-worked answers.
Catching retroactive arrivals
Warehouses rebuild incrementally, processing only what is new. The obvious definition of new
is by business date: where adjudication_ts > last_run_max. On this problem that
is wrong, because retroactive data has old business dates and new arrival timestamps.
Here last_run_max is a high-water mark: the latest adjudication date the previous
run saw. Anything dated after it counts as new, and anything dated before it is assumed to have
been handled already. A row that arrives today carrying a date from last year fails that test and
is skipped.
| What arrived | business date | arrived | by business date | by arrival time |
|---|---|---|---|---|
| A late adjustment claim | 2025-06-30 | 2026-09-08 | missed | caught |
| A retroactive termination | 2025-04-30 | 2026-09-08 | missed | caught |
The business-date filter catches neither. The run completes, reports zero errors, every dashboard is green, the chain totals table keeps a superseded claim marked current, and 1,150 dollars of exposure is never recorded. The fix is one line: filter on when the row arrived, tracked as a high-water mark across the feeds that can change a chain's answer: claims, links and eligibility.
With the arrival-time filter, an incremental run over those two arrivals rebuilt exactly 2 of 14 chains and left the other twelve untouched. To watch it happen, run the demo script: it builds the project, injects both arrivals, and rebuilds without a full refresh. The filter itself is the last block of the chain totals model.
3.7 How we know it is right
- Three implementations must agree. A test fails if any two differ on any claim. They agreed on all 37, cycles and splits included.
- Hand-derived expected answers. Worked out from the scenarios, not from the code, so the comparison is a real check.
- Cash reconciliation. The payment ledger never participates in building the chain,
so
sum(payments) = reconciled amountis verification from a different table. It held for all 13 non-cyclic chains, before and after the retroactive batch. - A structural invariant. Both ends of every surviving edge land in the same chain, which is what proves the walk ran to completion.
Each check is a file you can open: the agreement test, the expected answers, the cash check, and the invariant.
A dbt project: 13 models, 20 tests, 6 source tables, 13 scenarios across 37 claims, covering corrections, void-and-rebill, splits, merges, cross-system chains, a cycle, a self-referencing link, an orphan pointer, a link arriving three months late, delta-versus-restatement amounts, and a termination landing between two claims for one member. All 20 tests pass on a clean build and again after a retroactive batch is injected and the pipeline rebuilt incrementally. Benchmarks ran each method in an isolated process so peak memory is attributable.
All of it is in the project on GitHub.
Taking it to Snowflake
The project writes the portable form directly wherever one exists, and routes the one construct that has no portable form through a macro. The ones that differ:
| Need | DuckDB | Snowflake |
|---|---|---|
| Conditional count | count(*) filter (where x) | count_if(x) |
| Boolean aggregate | bool_or(x) | boolor_agg(x) |
| Ordered string aggregate | string_agg(x, d order by o) | listagg(x, d) within group (order by o) |
| Date difference | date_diff('day', a, b) | datediff(day, a, b) |
A macro is a small reusable template in dbt. Where one spelling works on both DuckDB and
Snowflake, the project writes it directly. String aggregation does not have one, so it has a
version per warehouse, and date difference uses dbt's own datediff macro, which also has one per
warehouse. The SQL models call the macros instead of either spelling. The Python model needs its
own Snowflake edits, starting with .df() becoming .to_pandas().
Aggregates whose output you compare for equality always carry an explicit order.
Without an order, a string aggregate may list the same values in a different order on another run or another warehouse. A test comparing two results would then fail on answers that are actually the same.
If you remember five things
- A claim row is a belief at a point in time. Four parties can revise it.
- A chain is a connected component, not a linked list. Splits and merges branch and rejoin.
- Coverage has two clocks. Compare what we believed then against what we know now, at the service date.
- Incremental filters go on arrival time, never business date, or retroactivity is invisible.
- Pick the algorithm for your worst component, not your average one. Ten cross-linked claims cost 15 seconds and nearly 3 GB in the wrong one.
Where every claim on this page comes from
Statistics are cited to the publishing organisation, standards to payer companion guides, Facets fields to Cognizant's own material. Performance figures were measured as described in [15]. The code for the working dbt project is [17]. Three sizing rows are labelled as assumptions where they appear.
bench/ of the project in
[17], run on 23 September 2026. DuckDB 1.5.5 through its Python API,
Python 3.10, 4 DuckDB threads, in-memory database, an 8 GB memory cap, AMD Ryzen 5 5600X.
Graphs are generated by rule rather than sampled, so they rebuild anywhere. Each method runs
in its own process, the first call is discarded, and every figure is the median of 5 timed
calls in each of 3 processes, with the full range kept in bench/results/results.json.
Peak memory is each process's own high-water mark, read from /proc because the
usual call inherits the parent's peak. The machine was shared during the run, so read the
seconds as approximate; the row counts are exact and reproduce on any engine. Closed-form
path counts match measured rows at cluster sizes 4, 6, 8, 9 and 10.Claims chaining onboarding tutorial. Phases 2 and 3 are grounded in a working dbt project with 13 models and 20 passing tests, including three independent implementations of the chain walk asserted to agree on every claim.