Range boundaries drawn from a sample leave one piece holding most of the records; what went wrong and what does it cost?
answer
- the boundaries are a guess, not a measurement
- correctness holds, the run does not
- sample the whole input, not its front
- one enormous key is a different problem
basics
~20 sThe sample misrepresented the key distribution, so the cut points do not split the data evenly. The output is still correctly ordered; what suffers is the run, which is now bounded by the one oversized unit of work and its memory pressure.
solid answer
~50 sBoundaries are a guess at the distribution, made from a sample, and a guess can be wrong in a few recognisable ways: the sample was too small to see the shape; it was drawn from one part of an input that is itself ordered or grouped, so it saw one slice of the range; the boundaries were reused from an earlier run over differently distributed data; or a handful of key values are so frequent that no placement of cut points can split them. The first three are sampling problems and you fix them by sampling more, and sampling across the whole input rather than the cheapest part of it. The last is not a boundary problem at all — one key cannot straddle two pieces — and belongs with the treatment of a single overweight key. In every case the result is still ordered correctly; the damage is wall-clock time and memory on one worker.
go deeper
Recall that the cut points come from a sample, so they are an estimate of where the keys fall, and a bad estimate makes the pieces unequal rather than making the answer wrong.
Explain the difference between a sample that is too small and one that is unrepresentative, and why an input written grouped by date makes sampling its first part actively misleading.
Diagnose from the evidence — piece sizes against the spans they were given — separate a misplaced cut point from a single overweight key, and say which remedy belongs to which, because they do not overlap.
Decide whether boundaries are derived per run or owned as configuration, and who carries that; stale hand-placed cut points are a standing liability that surfaces as a slow job months after anyone remembers setting them.
## What the boundaries are, and why they can be wrong To produce an end-to-end ordered result, the key range is cut at **range boundaries** — the key values separating one piece's span from the next — so each piece receives one contiguous span and can be sorted on its own. Those boundaries are chosen from a **sample** of the ordering key, because the real distribution is not known until the data has been read. A sample is an estimate, and an estimate can be off. When it is, the spans are still contiguous and still correct; they are just not equal shares of the data. ## The four ways the estimate goes wrong 1. **The sample was too small.** A handful of keys cannot resolve a distribution with a long tail or sharp clusters, so the cut points land in near-empty regions and one span absorbs the mass. 2. **The sample was not representative of the whole input.** This is the most common and the most deceptive. Inputs are frequently written grouped or ordered by something — a date, an ingestion batch, an upstream layout — so sampling the first part of the input samples one slice of the key range. The sample looks fine and describes a distribution the job will never see. 3. **The boundaries were stale.** Cut points computed on an earlier run, or configured by hand from statistics someone gathered once, drift as the data shifts underneath them. 4. **The distribution genuinely cannot be split there.** If one key value accounts for a large share of the records, no arrangement of boundaries helps, because a boundary separates keys and cannot separate records that share a key. That is a different subject — an overweight single key, and the remedies for it — and the right move in an interview is to name it and hand it off rather than pretend better sampling fixes it. ## What it actually costs | dimension | effect of badly placed boundaries | |---|---| | correctness of the output | none — the spans are still contiguous and disjoint, so the result reads back in order | | wall-clock time | the run is bounded by the one oversized unit of work, while the others finish and their workers idle | | memory on one worker | that unit's local sort has a far larger working set, so part of it may be written to local disk, with the extra cost that carries | | cluster utilisation | most of the cluster is idle for the tail of the step, so the job pays for capacity it is not using | | the read afterwards | unchanged in order, but the output pieces are wildly uneven in size, which every downstream consumer inherits | The first row is the one candidates get wrong in both directions: some claim the output is corrupted, others claim nothing is wrong at all. The honest answer is that the contract holds and the economics do not. ## How you find out The symptom is a step where nearly every unit of work finishes quickly and one runs far longer, which is the same symptom as several other causes — an unevenly distributed key, or simply a slow machine. What points at the boundaries specifically is that the oversized piece covers a wide span of keys that the sample thought was sparse, and that the sizes of the pieces map onto the boundary values in a way that says the cut points, rather than any single key, are misplaced. Reading how many records each piece received, against the span it was given, is the diagnostic; diagnosing uneven distribution as a subject in its own right belongs elsewhere. ## What to do about it - **Sample more.** A larger sample costs more to draw and resolves the shape better; this is the first and cheapest lever. - **Sample across the whole input, not the front of it.** If the input is ordered or grouped, take the sample from across all pieces rather than from whichever part is cheapest to read. This fixes the deceptive case. - **Recompute boundaries per run.** Treat them as derived data, not configuration. Hand-placed cut points are appropriate only when the distribution is genuinely known and stable, and they need an owner and a review cadence. - **Check whether you needed an end-to-end order at all.** Frequently the requirement is the top few records, or order inside each key, neither of which needs boundaries. - **If the culprit is one enormous key, stop.** No boundary placement separates records sharing a key; that is the overweight-key subject and its own set of remedies. One caveat on what varies: some runtimes revise the remainder of a plan after measuring what a finished step actually produced, which can soften an uneven split after the fact. Others do not, and in a continuous job largely cannot. Treat that as a property of the runtime you are on, not as something the class does — and the mechanism itself is a separate subject from ordering.
- How do you tell a badly placed boundary from one key that is simply too heavy?Look at how many distinct keys the oversized piece holds. A misplaced cut point gives one piece a wide span with many keys in it, and resampling or recutting fixes it. A single dominant key gives a piece whose records nearly all share one value, and no boundary placement helps, because a cut point separates keys and not records within a key.
- The input is written grouped by ingestion date. Why does that make sampling dangerous?Because the cheapest sample — the first part of the input — then covers one date's worth of keys rather than the whole range. The sample looks healthy and describes a distribution the job never sees, so the cut points are placed for data that is not there. Draw the sample across all of the input instead.
- Does a bad split make the ordered output unusable for downstream consumers?No. The order is intact, so any reader consuming the pieces in sequence gets exactly what was promised. What downstream inherits is uneven piece sizes, which can matter for whoever reads the output in parallel, since one of their units of work will be far larger than the rest.
saying these in an interview costs you the question
- Says badly placed boundaries corrupt the output or break the ordering guarantee.
- Blames an overweight single key on the sample, when no cut point can split one key.
- Samples only the beginning of an input that is written grouped by date.
- Treats hand-configured boundaries as permanent rather than as data that goes stale.
- Assumes the runtime will always notice the uneven split and re-plan around it.