Table of contents
Open Table of contents
The leaderboard that arrived out of order
Suppose a game records scores in whatever order players finish:
SELECT player, score FROM scores ORDER BY score DESC;If TiDB chooses a root Sort operator, it must produce a globally ordered stream even when its child sends unsorted chunks (batches of rows). Several workers can sort their own slices in parallel, but that is not enough: [90, 70] from one worker and [95, 80] from another must become [95, 90, 80, 70] for the caller. This article follows that handoff through four source units in pingcap/tidb at commit 0073665, dated October 24, 2026. It describes the root parallel SortExec path, not TiKV-side sorting, every ORDER BY plan, or the separate TopN algorithm. Use EXPLAIN to see which plan your query actually got.
Four pieces on the stage
+-------------------+ +------------------------+
| PhysicalSort |------>| builder.buildSort |
| ORDER BY keys | | wires child + ByItems |
+-------------------+ +-----------+------------+
|
v
unsorted child chunks -------> +-------+---------+
| SortExec |
| fetcher/channel |
+---+---------+---+
| ^
v | sorted worker streams
+------+---------+------+
| parallelSortWorker x N |
| sort local row batches |
+------------+-----------+
|
v
+------------+-----------+
| multiWayMerger |
| globally ordered rows |
+------------+-----------+
|
v
caller's chunkPhysicalSort carries the ByItems expressions and directions for the chosen physical plan. executorBuilder.buildSort builds its child, then gives those ByItems to a SortExec. The builder itself is the wiring step, not another sorting algorithm.
SortExec owns the child, channels, workers, comparison functions, result merger, and memory/disk trackers. A parallelSortWorker sorts local rows, while multiWayMerger picks the next row across sorted inputs using a heap. These are Go structs, not separate network services.
From a child’s chunks to sorted worker streams
On Open, SortExec creates ExecutorConcurrency workers and channels. In this pinned revision it explicitly sets IsUnparallel = false on the normal path; the alternative un-parallelized code remains in the file, but is not the path we follow. The first Next initializes key comparators and starts the fetch/sort pipeline. Later Next calls drain the already-started ordered result channel into the caller’s chunk.
The fetcher repeatedly pulls chunks from the child and puts them on a shared channel. fetchChunksParallel launches the workers and a result generator. A worker accumulates rows, sorts a batch with slices.SortFunc, and, if it made several locally sorted batches, merges those batches into one sorted iterator for that worker. Workers share the input channel, so which worker receives a given chunk is not a property of the SQL query.
The comparison is not a string comparison of printed values. SortExec builds type-specific comparison functions from the ORDER BY expressions; its lessRow compares keys in order and reverses a nonzero comparison for DESC. If two rows tie on all ORDER BY keys, do not assume a stable order between them; add a unique tie-breaker such as ORDER BY score DESC, player if your application needs deterministic results.
The final merge, one row at a time
When the worker streams are ready, the result generator initializes the in-memory merger. Its memorySource contributes the first row from each nonempty worker iterator to a heap. Calling multiWayMerger.next takes the heap’s best row and replaces it with the next row from that same iterator; when an iterator is exhausted, the heap shrinks. Only the resulting row stream reaches the caller. Neither sorting each chunk nor concatenating the worker results would satisfy ORDER BY.
worker 1: 90 -> 70 heap front: 95, then 90, then 80, then 70
worker 2: 95 -> 80 output: 95 -> 90 -> 80 -> 70The example has distinct scores for clarity. The merger holds a front row per input, but the workers’ sorted input rows still consume memory. Global sort must see its input before it can guarantee which row comes first; do not mistake the output Next API for an early-exit algorithm. If the optimizer chooses a TopN for ORDER BY ... LIMIT, that is a different executor with different trade-offs.
Memory and configuration boundaries
tidb_executor_concurrencysupplies thisSortExec’s worker count throughExecutorConcurrency. More workers can increase CPU parallelism, but also maintain more local sorting state; it does not alter SQL ordering semantics.tidb_mem_quota_querysets the session’s query memory limit.SortExecattaches memory and disk trackers onOpen.tidb_enable_tmp_storage_on_oomis global. When enabled,Openinstalls a spill action; the generator can merge sorted rows from disk instead of keeping every run in memory. Disk spilling is a fallback with I/O cost, not a guarantee that every memory failure is recoverable.
Check the version-specific system-variable reference before changing settings; this walkthrough is tied to a development commit, not every TiDB release. For a given query, check its actual EXPLAIN plan before applying root-sort advice.
Takeaway
The plan specifies what ordering is needed. The builder wires the child and sort keys. SortExec hands input chunks to workers, workers sort local streams, and a heap-backed merger produces one globally sorted stream. Following those four pieces explains why local parallelism does not lose global ordering—and why sorting can trade memory, CPU, and temporary-disk I/O.