Kwker

Tutorial: sort a file larger than memory

Some data does not fit in memory: a day of event timestamps, a log of trades, a table export. sort_file sorts a binary file on disk while using only the memory you allow. It sorts pieces that fit, writes them to temporary files, and merges them into the output.

In this tutorial you sort a file of 64-bit keys with a 16 MiB budget, check the result, watch the progress, and then sort a file of records by one of their fields.

It takes about 10 minutes. You need Python with NumPy and Kwker installed (Installation), and about 400 MB of free disk space.

Step 1: a file of keys

sort_file reads keys stored back to back in the machine's byte order: what NumPy's tofile writes. Make a file of ten million random 64-bit keys, 80 MB.

PythonRuns on your machine.
import os
import shutil
import tempfile

import numpy as np
import kwker

work = tempfile.mkdtemp()
src = os.path.join(work, "keys.bin")
rng = np.random.default_rng(5)
rng.integers(0, 2**64, 10_000_000, dtype=np.uint64).tofile(src)
print(os.path.getsize(src) // 2**20, "MiB")
Output
76 MiB

Step 2: sort it with 16 MiB

Give the output path, the key type and the memory budget in bytes. The input is not changed. Temporary files go next to the output unless you pass temp_dir, and they are removed when the call returns.

PythonRuns on your machine.
dst = os.path.join(work, "sorted.bin")
kwker.sort_file(src, dst, "uint64", memory=16 * 2**20)
print(os.path.getsize(dst) // 2**20, "MiB")
Output
76 MiB

Step 3: check the result

Map the output with numpy.memmap to look at it without reading it all in. Then check two things: every key is at most the next one, and the file holds the same keys as the input. This file fits in memory, so you can sort a copy with NumPy to compare.

PythonRuns on your machine.
out = np.memmap(dst, dtype=np.uint64, mode="r")
print(bool(np.all(out[:-1] <= out[1:])))
print(np.array_equal(out, np.sort(np.fromfile(src, dtype=np.uint64))))
Output
True
True

Step 4: follow the progress

For files that take minutes, pass a progress function. Kwker calls it with the number of keys done and the total after each sorted piece and each merge round. Return True from it to cancel the sort.

PythonRuns on your machine.
calls = []
kwker.sort_file(src, dst, "uint64", memory=16 * 2**20, progress=lambda done, total: calls.append(done / total))
print(len(calls), "progress calls, ending at", f"{calls[-1]:.0%}")
Output
141 progress calls, ending at 100%

Step 5: sort records by one field

Files often hold records, not bare keys. Describe a record with a NumPy structured type, and name the field to sort by. The records move whole, byte for byte, and records with equal keys keep their order in the file.

PythonRuns on your machine.
trade = np.dtype([("price", "<f8"), ("qty", "<u4"), ("id", "<u4")])
trades = np.zeros(1_000_000, dtype=trade)
trades["price"] = np.round(rng.uniform(10, 20, trades.size), 2)
trades["qty"] = rng.integers(1, 100, trades.size)
trades["id"] = np.arange(trades.size)
trades.tofile(os.path.join(work, "trades.bin"))

kwker.sort_file(os.path.join(work, "trades.bin"), os.path.join(work, "by_price.bin"), trade, key="price",
                memory=4 * 2**20)
by_price = np.fromfile(os.path.join(work, "by_price.bin"), dtype=trade)
print(by_price[:3])
print(np.array_equal(by_price, trades[np.argsort(trades["price"], kind="stable")]))
shutil.rmtree(work)
Output
[(10., 99, 2482) (10., 45, 4332) (10., 88, 6833)]
True

The last line removes the files of this tutorial.

What you built

Next steps