What comes next is a relational question

Why is sorting the one unavoidable superlinear, blocking operation, and why is full order usually more than a question needs?

"what is next" is a relational question

The lookup group answered "where is k?": a question about one key, answerable without looking at any other key. That independence is what made sharding, hashing and parallelism simple.

Ordering structures answer "what is next?". That question is relational: the answer for one element depends on its relationship to every other element. A global property cannot be established without global communication, directly or in steps. This is why the whole group sits on the tension order versus parallelism, and why it behaves so differently from the lookup group.

Three consequences set up everything below.

Sorting is the only unavoidably superlinear operation

In a data pipeline, scans are linear (cost O(n)). Hash joins are linear. Filters are linear. Aggregations are linear. Sort is O(n log n), and the comparison lower bound says you cannot argue your way out: any sort that works by comparing items needs log₂(n!) ≈ n log₂ n − 1.44 n comparisons. So every system spends its effort on one of two strategies:

• Avoid the sort: use interesting orders (explained below), use hashing instead of sorting, or use data that is already clustered.
• Amortize the sort: maintain order a little at a time so you never pay it in one lump.

Sorting is a pipeline breaker

You cannot output the first row of a sort until you have read the last input row. This is a structural property, not an implementation detail. An operator that behaves this way is called a pipeline breaker or blocking operator. It has two hard consequences:

1. The operator needs memory proportional to its input. That is why sorts spill.
2. It is impossible on an unbounded stream. Streaming systems do not sort. They substitute a watermark: an assertion that disorder is bounded ("no event will arrive more than 5 minutes late"). They pay by dropping or correcting whatever violates the assertion.

A watermark is the streaming replacement for a sort, and its price is exactly the assumption it makes plus the cost when the assumption breaks. Every such shortcut can be tested with two questions: what does it assume? and who pays when the assumption fails? Here: it assumes bounded lateness, which it cannot verify, and the owner of the late record pays.

Order is not one thing

There are three levels:

Most real overpayment in data pipelines comes from establishing more order than the query needed. ORDER BY x LIMIT 10 compiled as a full sort is the canonical example, and it is not rare.