An ordering step returns rows with equal keys in a different order on a bigger input — why, and what fixes it?
answer
- ties are unconstrained by definition
- arrival order is a promise, not a law
- the promise differs by design
- add keys until the order is total
basics
~20 sNothing constrained those rows. An ordering step orders rows whose keys differ; rows that tie keep the order they arrived in only where the design promises it, and where it does not, their arrangement can shift with size, version or parallelism. Add a tie-breaking key.
solid answer
~40 sOrdering by a key constrains only rows whose key values differ. Rows that tie on the key are unconstrained unless the step promises that equal rows keep the order they arrived in — and that promise varies: some designs document it, some make it only on certain paths or certain key types, and some make it not at all. Where it is absent, the arrangement among equals can change as the row count crosses an internal threshold, as the work is split across more threads, or between versions. That is why it looked deterministic until the input grew. The fix is not to memorise whose default is what. Append a further ordering key that makes the comparison total — an identifier, or a composite of columns that cannot tie — so every run agrees.
go deeper
Know that ordering on a key says nothing about rows that tie on that key, and that if it matters which of two equal rows comes first, you have to add a second key saying so.
Explain that keeping arrival order among equals is a promise a design may or may not make, and that where it is absent the arrangement can move with row count, thread count or version while the data is unchanged.
Demonstrate the diagnosis: the output moved but the code and the key values did not, so look for an unconstrained tie rather than for a data change, and then make the ordering total rather than tracking down which run was right.
The call you own is where a total order is mandatory — anything published, diffed between runs, or asserted in a test — weighed against carrying an extra key on every ordering step in the codebase and the review rule that enforces it.
## What an ordering actually constrains An **ordering step** — the operation that puts rows into an order you specify, taking one or more keys each with its own direction — makes exactly one kind of promise: for any two rows whose keys **differ**, the one that compares lower under the direction you gave comes first. That is the whole contract of the comparison. It says nothing at all about two rows whose keys **compare equal**. Those rows are, from the step's point of view, interchangeable. Any arrangement of them satisfies the request you made. So when the arrangement changes between runs, the step has not misbehaved — you asked a question that had more than one correct answer and got a different one. ## The promise, and who makes it There is a separate, optional promise a design may add on top: **equal rows come back in the order they arrived in**. This is the property usually called a stable ordering, and it is worth knowing the word — but here it means a guarantee the *table operation* gives you, which is a different thing from a property of whatever comparison routine sits underneath. | The design | What you can rely on | What breaks | |---|---|---| | Documents that equal rows keep their arrival order | The arrangement among equals, given the same input in the same arrival order | A change in the input's own arrival order — a re-read of a file, a different upstream step | | Promises nothing | Only the ordering of rows whose keys differ | Arrangement among equals, with size, thread count or version | | Offers it as something you request | Whatever you actually requested, so read the call | Assuming the request was made when it was not | Notice the first row is not a safe harbour either. Even where arrival order is preserved, it is preserved from *the order the rows arrived in*, which is itself not a thing a pipeline usually promises. ## Why it looked deterministic until it did not The most misleading property of an unconstrained arrangement is that it is often perfectly repeatable — right up to the moment it is not. - The number of rows can cross a threshold inside the implementation and change which path the work takes. - The work can be split across more units of execution on a larger machine, so equal rows finish in a different sequence. - A version upgrade can change the internal choice without changing any documented behaviour, because nothing was documented. - The upstream step can change the order the rows arrived in, which moves equals even under a design that faithfully preserves arrival order. Each of these is invisible in the diff of your own code, which is why the investigation usually starts by looking for a data change that is not there. ## Diagnosing it 1. **Check whether the rows that moved are tied on every key you supplied.** If they are, the ordering step is not the suspect; the missing constraint is. 2. **Check whether any row whose keys differ moved.** If one did, this is a different bug — a key changed type, or the comparison is not what you think. 3. **Look at what downstream consumes the order.** A step that takes the first row for each key from an ordered result, a diff against yesterday's output, a fixture in a test, a paged listing — all of these turn an unconstrained arrangement into a visible defect. ## The fix: make the order total Do not try to establish which design promises what, and above all do not rely on having observed the arrangement hold. Make the ordering **total** — give the step enough keys that no two rows can tie: - Append an identifier that is unique per row where one exists. This is the cheapest and clearest fix and it survives a change of tool. - Where no single column is unique, append a composite of two or three that cannot collide in practice, and say in a comment why it cannot. - Prefer a key that is stable across runs. A value derived from arrival position only helps if arrival position is itself reproducible, which for a re-read source it may not be. - Keep the tie-break as the last key. It changes nothing about the output the business cares about, and it is the only part of the specification a reviewer can check by eye. The cost is one more comparison per pair, paid once, against a class of defect that produces no error, no warning and no failing test until an artefact is compared between two runs.
- The arrangement among equal rows never changed in two years of runs. Why is that not evidence of a guarantee?A design that promises nothing can still be entirely repeatable for one input size on one machine, because the path it takes is the same every time. What varies is the path: a different row count, more threads, or a new version can pick another arrangement. Repeatability you observed is not a contract you can cite.
- What makes a good tie-breaking key when no single column is unique?Anything that makes the comparison total and is itself reproducible: an identifier carried from the source, or a composite of two or three columns that cannot collide. Avoid deriving it from arrival position unless arrival position is guaranteed, since a re-read of the same source may present rows differently.
- Is an arrangement that keeps arrival order among equals the same as a deterministic result?No, they are separate guarantees. Keeping arrival order is relative to the order the rows came in, so if that order changes the output changes with it. Determinism means the same input yields the same output anywhere. A total ordering gives you determinism without depending on arrival order at all.
Ordering a stack of forms by date only is a complete instruction, and two forms dated the same day satisfy it in either arrangement. If which of the two ends up on top matters to whoever reads the stack next, that is a second instruction, and it has to be given.
saying these in an interview costs you the question
- Assumes every ordering step keeps equal rows in arrival order.
- Calls the earlier output correct and the new one a tool bug.
- Says the result is deterministic because it never changed locally.
- Re-runs the ordering a second time hoping the ties settle.
- Adds a tie-break that still leaves ties and calls the order deterministic.