What ordering structures forbid

Which kinds of order can no structure give, and what does each escape cost?

What this article forbids

You cannot output ordered results before you have read all input: sorting is blocking by construction. That makes it impossible on an unbounded stream and memory-hungry on a bounded one.
You cannot establish a total order in parallel without first partitioning the domain, which means you cannot sort in parallel without an estimate of the distribution.
You cannot maintain order incrementally without paying on every write.
You cannot physically sort a dataset by more than one key.

The escapes and what each costs

Escape	What it costs
Partial order (heap)	You can answer nothing except "what is next". It buys bounded memory with exactness when the question is top-k
Range partitioning	A sampling pass and exposure to skew: the sort's runtime is the maximum over tasks, so one bad boundary sets the stage duration
Bounded disorder (watermarks, LSM level structure, nearly sorted input)	An assumption you cannot verify, paid by whoever produced the record that violated it
Precomputed order (clustered, bucketed or sorted tables)	Write-time work, and lock-in to exactly one order; it pays off after a computable number of queries
Restricting the question, not the answer (top-k, monotonic windows)	The cheapest escape, because it costs no accuracy. Always check for it before reaching for approximation
Approximation	The last escape and the subject of Probabilistic structures

Case, resolvedConstructed case · Arjun at Parcelo

A top-10 query that writes 800 GB

A top-10 dashboard query ran 40 minutes and wrote 800 GB of temporary files, one task of a 200-task sorted export got ten times the data, and a 30-minute sliding-max streaming job ran out of memory. Where it started: Ordering structures →

The 40-minute top-10. The engine compiled ORDER BY delay DESC LIMIT 10 as a full sort of billions of rows. Arjun rewrites the plan to use a bounded heap of size 10: O(n log 10) time and memory for 10 items, so it never spills (the question was restricted, not the answer). The job drops from 40 minutes to about the time of one scan.

The slow export. The range boundaries were drawn from a sample of only 1,000 rows, and one depot dominated the data. He increases the sample (reservoir sampling per partition) to be comfortably larger than the number of distinct keys per boundary, and splits the hot depot's range. The slowest task now takes about as long as the others, and the stage time (the maximum over tasks) falls from hours to minutes. He also marks the table as bucketed and sorted on (depot, timestamp) for the customers who need this export every week: the sort cost is paid once and shared over every export.

The out-of-memory window. "Max in the last 30 minutes per depot" is not invertible (you cannot subtract a max), and the job was keeping the whole window per depot. For the single-threaded per-depot loop, he uses a monotonic deque: only the staircase of live candidates stays in memory. In the distributed version he uses panes of one minute each: aggregate each minute once, combine 30 panes per emission. For the "distinct parcels in the last hour" metric there is no exact bounded answer, which sends him to the next article: sketches.