Before running a match of two tables on a key, how do you predict its output row count?
answer
- size is not the input to the prediction
- occurrences per key value, on each side
- multiply within a key, sum across keys
- row count against distinct key count
- unique side bounds the output
basics
~20 sSum, over every key value present on both sides, the product of its occurrence count on each side. In practice you first ask the cheap question: is either side unique on the key? If one is, the output cannot exceed the other side's rows.
solid answer
~50 sThe exact prediction is the **per-key row product**: for each key value present on both sides, multiply its occurrence count on one side by its count on the other, and sum those products. You rarely need the full distribution, because one measurement settles most cases - compare each side's row count with its number of distinct key values. If the reference side is unique on the key, every partnered row of the other side yields exactly one output row, so the output is bounded by that side's row count. If neither side is unique, the match is many-to-many and the output is bounded by nothing either input can show you. The shape you pick only changes what happens to key values absent from one side: they contribute either zero rows or one row of holes. Everything present on both sides is governed by the product.
go deeper
Remember that a repeated key value on either side copies rows, so an output can be longer than both inputs. Knowing that the question of size is really a question about repeats is enough at this stage.
Give the arithmetic and the screening test: multiply the occurrence counts within a key value and sum across key values, and establish uniqueness by comparing a side's row count with its distinct key count.
Show that you predict before you run, and that you notice the dangerous case - an output near the input size built from offsetting drops and copies - rather than only the obviously inflated one.
Consider what makes the prediction cheap enough to run on every execution rather than once by hand, and what the step should do when the measured count and the predicted count disagree.
## What you need before you can predict anything A prediction needs two facts about each side, and neither is its size: - how many **distinct key values** it holds in the columns being compared; - how many times each of those values **occurs**. The number of rows is a consequence of those two, not an input to the prediction. A 10-row reference table with one key value repeated ten times inflates a million-row table exactly as effectively as a million-row one would. ## The exact formula For a match that keeps only the rows that found a partner: ``` output rows = sum over key values k present on BOTH sides of (occurrences of k on side A) * (occurrences of k on side B) ``` Each key value is independent of the others, which is what makes the sum work: pairs are formed inside one key value and never across two. ## The cheap proxy almost everyone should use Computing the full per-key distribution is rarely necessary. Comparing one number per side is: | what is true of the key columns | what bounds the output | |---|---| | both sides unique on the key | one row per shared key value; at most the smaller input's row count | | side B unique, side A repeats | exactly one output row per partnered row of A; at most A's row count | | neither side unique | the sum of products; bounded by neither input and possibly far larger than both | A side is unique on the key exactly when its **row count equals its distinct key count**. That single comparison, run on each side, tells you which row of the table above you are in, and it is the measurement worth building the habit around. ## Where the choice of shape enters The product governs every key value that is present on both sides. The only thing the shape - the choice of which unpartnered rows survive - can change is the contribution of key values missing from one side: - a key value with occurrences on both sides contributes `m * n` rows under **every** shape; - a key value present on one side only contributes `0` rows when unpartnered rows are dropped, and `1` row per occurrence, with holes where the other side's columns would be, when that side is kept whole. So choosing to keep one side whole never protects you from the product. It only stops the drops, which is why a total that looks right can still be built from copied rows. ## A worked prediction A nightly step matches 1,000 orders against a customer reference, keeping only partnered rows. You measure: 1. Of the 1,000 orders, 950 carry an identifier that also appears in the reference; 50 do not. 2. The reference has 480 distinct identifiers over 500 rows, so 20 identifiers are listed twice. 3. Of the 950 partnered orders, 40 carry one of those 20 twice-listed identifiers. The prediction is `910 * 1 + 40 * 2 = 990` rows. Now read what that means: the step returns **990 rows from a 1,000-row input**, and a reviewer glancing at it concludes nothing changed. In fact 50 orders vanished and 40 were counted twice - two defects that happen to nearly cancel. This is why the prediction is worth making in advance: the surprise is not that the number is large, it is that the number is unremarkable. ## What the prediction is actually for - **It turns a match into a testable step.** A number you wrote down beforehand can disagree with the result; a number you read afterwards cannot. - **It locates the defect.** If the output exceeds the prediction, a key value repeats more than you measured. If it falls short, key values you expected to be shared are not comparing equal. - **It survives being automated.** The same two counts per side run cheaply on every execution, which is what makes the check worth keeping rather than performing once by hand. ## One caution about the tools The arithmetic above is a property of the operation and holds everywhere. Whether the tool helps you is not: some return an inflated table silently, some emit a warning once the match turns out to be many-to-many, and some let you declare the relationship you expect on the call and fail rather than return an unexpected size. Predict the count yourself, and the prediction is portable across all three.
- Why does the prediction need the per-key occurrence counts rather than just the distinct key counts?Because distinct counts tell you whether a side repeats at all, not how badly. Two references each with 20 repeated identifiers behave completely differently if one repeats them twice and the other repeats one of them 5,000 times. The distinct count is the screening question; the occurrence distribution is what turns an alarm into a number.
- Does keeping one side whole rather than dropping unpartnered rows reduce the inflation?No. Key values present on both sides contribute the same product under every shape. Keeping a side whole only adds rows for its key values that have no partner, each contributing one row with holes where the other side's columns would sit. The shape changes the drops, never the copies.
- A prediction says 990 rows and the match returns 990 rows. Is the step verified?Only against the expectation you encoded. Matching the prediction confirms the occurrence counts you measured, not that the step is right: those 990 rows may still contain 40 orders counted twice and be missing 50 that found no partner. Verify the quantity that must not change - a distinct count of orders, or a revenue total - alongside the row count.
saying these in an interview costs you the question
- Predicts the output row count from the two tables' sizes alone
- Believes the output cannot exceed the sum of the two inputs' rows
- Thinks keeping one side whole prevents the rows from multiplying
- Treats a small lookup table as incapable of inflating a large one
- Assumes a prediction that matched means nothing else went wrong