dofs: resolving a directory scans its children as the directory grows #236

Looking up /wide gets slower as children are added under it, even though the lookup does not request a child. I found this while investigating file recovery in OpenMeld.

This reproduces with the resolver SQL and core schema taken directly from 0.5.1, ef00c0a790cb87887bf209fa87838cb1a281220b, without our application or its patches.

What happens

Looking up /wide, with 20,000 children:

Before: find /wide -> inspect its children -> discover the path is finished
After:  find /wide -> discover the path is finished

Time for 100 lookups of the same directory, median of seven samples:

Linux arm64, Node 24.21.0, SQLite 3.53.4, Docker limited to 1 CPU / 1 GiB, no swap. macOS with SQLite 3.51.2 shows the same trend. These are in-memory query timings, not whole-sync or production recovery timings.

Reproduce

Script, raw samples, query plans and proposed patch

Save repro.mjs, then run:

node repro.mjs > results.json

Requires Node 24+ and network access to download two pinned upstream source files. No npm packages. Setup is outside the timed section; the two variants alternate which runs first.

Cause and proposed fix

In resolveViaCte, SQLite joins directory entries before reading the next path segment. The directory lookup can use only the parent half of its existing primary key:

Before: SEARCH d USING PRIMARY KEY (parent_inode=?)
After:  SEARCH d USING PRIMARY KEY (parent_inode=? AND name=?)

Changing the three recursive JOINs to CROSS JOINs keeps the segment ahead of the directory lookup. Predicates, result ordering and schema stay unchanged. No new index or cache.

The script checks equal results for five path shapes at each width. After applying the patch to the clean upstream source, all 37 resolver, symlink and stat tests passed. This is focused coverage, not a full runtime test.

May I submit a PR?

I read the contribution policy, so I have not opened a PR. Would you be willing to invite me to submit this fix with regression coverage? The three-join patch is in the reproduction above. I am happy to adjust it to your preferred approach.