Table of contents
Open Table of contents
A leaderboard with a skipped winner
This source walkthrough is for engineers new to TiDB’s SQL executors. Imagine that a leaderboard needs the second- and third-highest scores:
SELECT player, score
FROM leaderboard
ORDER BY score DESC
LIMIT 2 OFFSET 1;The executor cannot keep just two candidates: it needs the best three, then skips the first. If the scores arrive as 72, 94, 51, 88, 90, 61, the three candidates are 94, 90, 88, and the output scores are 90, 88. Equal scores have no guaranteed order without an additional ORDER BY key.
We’ll follow the ordinary TiDB-side, in-memory TopN path in pingcap/tidb at commit dfda1fd. This is a snapshot of upstream main, not a claim about every release or every plan. The optimizer might instead choose an ordered index scan with Limit, or push TopN into TiKV; check EXPLAIN before assuming this executor runs. The TiDB TopN/Limit pushdown documentation explains those alternatives.
Four pieces in one path
PhysicalTopN (ByItems: score DESC, Offset: 1, Count: 2)
|
v
executorBuilder.buildTopN() --- creates TopNExec and child executor
|
v
TopNExec: read child chunks ---> topNChunkHeap (keep best 3)
|
sort candidate row pointers
|
skip 1, return 2PhysicalTopN stores the order-by items, offset, and count. executorBuilder.buildTopN builds its child and creates TopNExec with those order and limit values. The executor embeds SortExec for row comparison, but it does not simply sort every input row in memory. Its topNChunkHeap holds row pointers into chunks plus the number of candidates to retain.
These are the four units to track: plan, builder, executor, and heap. The child executor is the source of batches, not another operator whose implementation we need to learn today.
Why the worst candidate sits on top
On its first Next call, TopNExec.fetchChunks starts the work once. For a normal TopN, initBeforeLoadingChunks gives the heap a totalLimit of Offset + Count and an output index of Offset: three candidate rows and a starting output index of one in our example. The executor loads enough initial chunks to populate the heap, then starts the remaining work. A child chunk can cross the target size; executeTopN initializes the heap and pops extra worst rows before processing further chunks.
For descending scores, the worst retained row is the smallest score. The heap places that row at its root, where it is cheap to compare with a newcomer. greaterRow reverses the comparison for descending keys; topNChunkHeap.Less uses that ordering to put the worst candidate at the root. When a better row arrives, update replaces the root pointer and repairs the heap with heap.Fix; a worse row is ignored.
incoming score best three retained (displayed sorted, not heap order)
72, 94, 51 94, 72, 51
88 94, 88, 72 evict 51
90 94, 90, 88 evict 72
61 94, 90, 88 ignore 61
|
skip 94; emit 90, 88The example shows the candidate values in sorted order for clarity. The heap itself is not a sorted list. TiDB sorts the final candidate pointers after reading the remaining child chunks, then generateTopNResultsWhenNoSpillTriggered sends rows starting at the offset to the result channel. The caller’s Next copies up to its requested rows from that channel into a result chunk; the initial fetch and channel read are separate from building the heap.
What the heap actually keeps in memory
Heap size is not the same as the total memory footprint. topNChunkHeap stores row values in a chunk list and keeps row pointers in the heap. When a better candidate arrives, update appends the row and changes a pointer; the old row’s bytes can remain in the list. Otherwise a stream of improving rows could grow memory even though the heap pointer count stays at three.
The no-spill loop compacts the chunk list when its row count exceeds four times the number of retained pointers. doCompaction copies just the current candidates into a new chunk list. Thus “keeps only the best three” describes the logical candidate set, not a strict three-row cap on every intermediate allocation.
Ordinary TopN still needs to see the whole unsorted input before it knows the winners. The initial load explicitly avoids setting RequiredRows to the output limit on its child. This is different from a plain LIMIT without ORDER BY: a late score might beat the current leader. A pushdown plan or an already ordered source changes where or how that work occurs, not the meaning of the SQL result.
The knobs, and the boundary of this story
tidb_mem_quota_querysets a statement’s query memory quota.TopNExec.OpenSelfattaches its memory tracker to the statement tracker; the variable definition shows how the limit is set.tidb_enable_tmp_storage_on_oomgates this executor’s spill setup. When enabled,OpenSelfcreates a disk tracker, spill helper, and workers; the no-spill path above is only one branch of that executor. See the TiDB memory-control documentation for operational context.tidb_executor_concurrencyis passed by the builder to TopN’sConcurrency. In this snapshot it sizes the spill-related worker/channel setup; it does not mean the ordinary heap loop automatically runs in parallel. The system-variable definition is the source for its name and constraints.
We leave spill merging, partial-order short-circuiting, and TiKV’s own TopN implementation for separate posts. Check a real plan and your release’s settings before changing memory or concurrency limits.
The mental model
ORDER BY ... LIMIT count OFFSET offset needs the best count + offset rows. The local TopN executor reads child chunks, retains candidates through a worst-at-root heap, sorts the survivors, skips the offset, and returns the rest. Chunk compaction keeps replaced rows from piling up; spill and pushdown are distinct paths. The key contrast with plain LIMIT is that, without an ordered input, TopN cannot know the winners until it has examined all candidates.