External Sorting, Merge Strategies, and Parallel Sort (TAOCP Vol. 3) — The Real Bottleneck in Indexer Rebuilds TODO
Concept
External sorting is used when data doesn't fit in memory: it splits into a run-generation phase, where memory-sized runs are sorted and written to disk, and a merge phase, where those runs are combined via k-way merging. Raising the merge fan-in k shrinks the number of passes needed — it's log base k of the number of runs — but each run needs its own input buffer, so a bigger k means smaller per-run buffers and worse sequential-read efficiency; that's the tradeoff. Using replacement selection during run generation can produce runs longer than memory on average, which cuts the number of runs outright. Parallel sorting either splits the data, sorts each part, and merges, or uses sample sort — sampling to pick partition boundaries and sorting each partition independently — and in both cases the real bottleneck is memory bandwidth and data movement, not comparisons. In other words, the cost model for external and parallel sorting should be built on blocks and bytes transferred, not comparison count.
Sorts that exceed memory come up constantly in practice — index rebuilds, large joins, log reprocessing — and what actually decides performance there is buffer size and merge fan-in, not algorithm choice.
Code & Formula
# 외부 정렬 — 메모리에 다 못 올리는 데이터를 런(run)으로 쪼개 정렬 후 k-way 병합한다.
# 비용은 비교 횟수가 아니라 "몇 번 디스크를 훑는가(패스 수)"로 세는 게 핵심이다.
import heapq
import random
random.seed(1)
data = random.sample(range(1000), 37) # "디스크에 있는" 전체 데이터
MEMORY_CAPACITY = 6 # 메모리에 한 번에 올릴 수 있는 크기
def make_sorted_runs(data, capacity):
runs = []
for i in range(0, len(data), capacity):
chunk = data[i:i + capacity]
runs.append(sorted(chunk)) # 런 하나 = 메모리에 올려 정렬 후 "디스크"에 기록
return runs
def k_way_merge(runs):
# heapq.merge 는 여러 정렬된 이터러블을 O(N log k) 로 병합한다 (k = 런 개수)
return list(heapq.merge(*runs))
runs = make_sorted_runs(data, MEMORY_CAPACITY)
merged = k_way_merge(runs)
import math
num_passes = math.ceil(math.log(len(runs), MEMORY_CAPACITY)) if len(runs) > 1 else 1
print("input size:", len(data), "| memory capacity:", MEMORY_CAPACITY)
print("number of sorted runs:", len(runs))
for i, r in enumerate(runs):
print(f" run {i}: {r}")
print("merged result is sorted:", merged == sorted(data))
print("approx merge passes needed (log_k of run count):", num_passes)
docs/code/algorithms/algorithms-80.py
Exercise
Implement external sort over a file larger than memory using a fixed buffer, then vary the merge fan-in and measure total runtime and actual bytes read/written to find the optimum.
Practical Connection
Re-indexing chain events from genesis makes sorting block/log keys a real bottleneck, and tuning batch size and merge fan-in there determines the total re-sync time.
Where it lands in Jayverse
- Devnet indexer: tune merge fan-in and buffer size as a benchmarked config. When rebuilding chain-event indexes from genesis, measure the optimum rather than using a default, and record the chosen k with the benchmark it came from.
- gitboard: apply the same tuning to cross-service log exports. If gitboard re-sorts large exported logs from multiple services, don't assume an off-the-shelf sort library scales; apply the same buffer/fan-in benchmark used for the indexer.
- CI: track bytes read/written, not just wall-clock time, in resync benchmarks. Add an I/O-efficiency metric to any reindex or resync test in CI, since the card's point is that memory bandwidth, not comparisons, is the real bottleneck.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| fan-in | (병합 시) 동시에 합치는 입력 개수 · k-way merge에서 한 번에 합치는 런의 개수. "Raising the merge fan-in k shrinks the number of passes" |
| bottleneck | 병목 · 전체 성능을 좌우하는 가장 느린 구간을 가리킬 때. "the real bottleneck is memory bandwidth and data movement" |
| tradeoff | 절충·맞바꿈 · 하나를 키우면 다른 게 나빠지는 관계를 말할 때. "worse sequential-read efficiency; that's the tradeoff" |
| come up constantly in practice | 실무에서 끊임없이 등장하다 · 이론이 아니라 실제로 자주 부딪히는 상황임을 강조할 때. "Sorts that exceed memory come up constantly in practice" |
| built on ... not | ~을 기준으로 세워진 것이지 ~이 아니다 · 비용 모델을 무엇 위에 세워야 하는지 말할 때. "should be built on blocks and bytes transferred, not comparison count" |
| cuts ... outright | ~을 아예 줄여버리다 · 부분적이 아니라 근본적으로 개수를 줄이는 효과. "which cuts the number of runs outright" |
| TAOCP | 도널드 크누스의 저서(The Art of Computer Programming) · 이 외부 정렬·병합 전략이 참고하는 알고리즘 고전 교과서. "External Sorting, Merge Strategies, and Parallel Sort (TAOCP Vol. 3)" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.