The index scan: a directory at a time, with bounded memory (2026-09-26)
Issue #302, split out of #22. fullScan — first open, explicit re-index and
the periodic rescan fallback — used to load the whole library into memory
before it wrote anything: every index row into one Map<String, Note>, the
disk walk into one List<DiskEntry>, and the parsed text of every changed
note into one map. d30ae0b4 measured that at a million notes on
2026-09-10: about nine seconds and a gigabyte, which on a phone is an OOM
kill that recurs on every rescan.
What it does now
- One streamed walk.
DirWalkerdrives one long-lived background isolate that answers oneDirListing— a directory’s direct children — per request, depth-first, parents first. The caller mirrors a directory, then asks for the next: one request per directory is the backpressure, so neither side holds more than one listing. A short-livedIsolate.runper directory would have been an isolate spawn per folder, and the FUSElistSync/statSyncbehind a listing cannot run on the UI isolate. - The diff is per directory. A listing is compared with the rows whose parent it is, written in one transaction, and forgotten; content is read and written for that directory only, in the batches the content pass already used.
- Renames pair across directories through two scan-scoped temp tables.
A note gone from a folder the walk has passed stays in
notes(deleting it would take its FTS, tag and link rows, and pairing repoints the row rather than resurrecting it) and joinsscan_orphans; the folder paths no pairing claims go toscan_gonefor the prune at the end. A new note in a later folder pairs against the orphan table, immediately. A note whose new home the walk reached before its old one leaves a fresh row behind; a second pass after the walk pairs what is left, deletes the fresh row and repoints the orphan. Both tables are SQLite’s, not Dart’s: a mass delete costs disk, not heap. - The indexer’s lock is taken a step at a time (#697). The setup, each
directory and the close each hold it; the walk’s requests in between do
not. A note made, renamed or deleted during the scan is written at once
instead of after the walk — on a phone’s first index that wait was 28 s
for 443 notes, and a million notes’ rescan would make it minutes. Two
scans still run one after the other. A listing can then be older than a
write that went through before its step: what such a write touched
(
ScanTouches) is the write’s, so the scan neither writes a row for it from the older listing nor prunes it, nor a folder above it, and pairs no rename through it. A directory’s notes are read before its step, off the lock — the phone’s first index spent 31.8 s reading one folder’s 15 notes, and holding the lock through that was the same wait in one step — and the step writes only; it reads the rows again only when a write came in between. The disk fixture’s first scan costs about 5 % more, an unchanged library’s rescan about 8 %. - Link edges are resolved after the walk. Directory-at-a-time writing
made the old inline resolution wrong twice over: a link to a note a later
directory introduces found no row, and a link to a note moving into an
earlier directory found two. Each directory’s edges go to the durable
pending_linkstable; at the end, after the pairing and the prune, they resolve against the final tree in pages of 500. Durable rather than scan-scoped: a scan that never reaches its end would leave a note whose FTS row is written but whose edges are not — and the content-row check cannot see the difference. The event paths (applyEvents,rescanFiles) still resolve inline, as before. - A dead link waits in the index for its note (#974). An edge is written
only for a link that resolves, and only when its own note is indexed, so a
note made later had no referrers until the notes that named it were saved
again. The targets no note answers are kept in
dangling_links, keyed by the stem a note must carry to answer them (schemaVersion11). Every stem the content store writes — a file stem or an alias — is noted, and the entry point that finished the write (applyEvents,rescanFiles,resync, the end of a scan) resolves the links waiting on those stems by thedangling_stemindex; past 256 stems it resolves all the waiting links in pages instead, so a first index keeps no set of them. A row stays after its edge is made — deleting the note drops the edge, and the note restored must find the link still waiting — and goes when its own note is indexed again or deleted. - The one-time repairs are paged. Missing file stems and frontmatter
recorded against a non-note are written a page at a time
(
repairDerivedRows), and the “notes without a content row” check is scoped to the directory being mirrored instead of returning every missing path as a list. - The first index is streamed too.
indexTreeFirstwrites the tree directory by directory instead of materializing the whole walk.
Measured
test/perf/index_scale_test.dart, “a full scan holds a directory, not the
library”: a real library on disk, a fresh index, RSS delta and wall clock.
NIMAN_FIXTURE_DIR=<dir> points it at the library
dart run tool/make_fixture.dart <dir> 1000000 writes, which is the gate;
without it the test writes a small fixture (2 000 notes, 7 MB).
| Notes | First scan | RSS delta | Unchanged rescan | Rescan RSS |
|---|---|---|---|---|
| 2 000 | 3.9 s | 7 MB | 91 ms | 0 MB |
| 50 000 | 47 s | 38 MB | 786 ms | 0 MB |
| 200 000 | 189 s | 45 MB | 3.3 s | -4 MB |
The delta is what the old reconciliation scaled linearly — a gigabyte at a million. What is left is SQLite’s page cache and a directory’s worth of Dart objects, not the library. The first scan’s wall clock is the content pass (one read per note, one short-lived read isolate per 200), not the tree diff; an unchanged rescan pays the walk and no reads.
Decisions worth keeping
- Sequential ids of a scan’s new rows.
maxId()before the walk is the baseline: every row above it was inserted by this scan, which is how the second pairing pass finds the fresh rows a rename left behind without a third temp table. - Ambiguity pairs nothing. Two orphans with identical size, mtime and digest make a move ambiguous, and guessing would repoint the wrong id; the same rule the in-listing pairing already had.
- A failed listing is not an error. A folder that vanishes between its
parent’s listing and its own comes back marked
failed; the scan skips it and the next one repairs the row. The old walk threw and failed the whole scan. - The link queue is a schema table, not a temp one.
pending_linksis written and deleted in the same pages, so it is empty whenever a scan finishes; a kill between pages leaves rows the next scan flushes. The index is a cache, so a schema bump wipes and rescans it anyway (schemaVersion5).